diff options
Diffstat (limited to 'Build/source/libs/cairo/cairo-src/src/cairo-rectangular-scan-converter.c')
-rw-r--r-- | Build/source/libs/cairo/cairo-src/src/cairo-rectangular-scan-converter.c | 791 |
1 files changed, 0 insertions, 791 deletions
diff --git a/Build/source/libs/cairo/cairo-src/src/cairo-rectangular-scan-converter.c b/Build/source/libs/cairo/cairo-src/src/cairo-rectangular-scan-converter.c deleted file mode 100644 index e353b34e853..00000000000 --- a/Build/source/libs/cairo/cairo-src/src/cairo-rectangular-scan-converter.c +++ /dev/null @@ -1,791 +0,0 @@ -/* cairo - a vector graphics library with display and print output - * - * Copyright © 2009 Intel Corporation - * - * This library is free software; you can redistribute it and/or - * modify it either under the terms of the GNU Lesser General Public - * License version 2.1 as published by the Free Software Foundation - * (the "LGPL") or, at your option, under the terms of the Mozilla - * Public License Version 1.1 (the "MPL"). If you do not alter this - * notice, a recipient may use your version of this file under either - * the MPL or the LGPL. - * - * You should have received a copy of the LGPL along with this library - * in the file COPYING-LGPL-2.1; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA - * You should have received a copy of the MPL along with this library - * in the file COPYING-MPL-1.1 - * - * The contents of this file are subject to the Mozilla Public License - * Version 1.1 (the "License"); you may not use this file except in - * compliance with the License. You may obtain a copy of the License at - * http://www.mozilla.org/MPL/ - * - * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY - * OF ANY KIND, either express or implied. See the LGPL or the MPL for - * the specific language governing rights and limitations. - * - * The Original Code is the cairo graphics library. - * - * Contributor(s): - * Chris Wilson <chris@chris-wilson.co.uk> - */ - -#include "cairoint.h" - -#include "cairo-combsort-inline.h" -#include "cairo-error-private.h" -#include "cairo-freelist-private.h" -#include "cairo-list-private.h" -#include "cairo-spans-private.h" - -#include <setjmp.h> - -typedef struct _rectangle { - struct _rectangle *next, *prev; - cairo_fixed_t left, right; - cairo_fixed_t top, bottom; - int32_t top_y, bottom_y; - int dir; -} rectangle_t; - -#define UNROLL3(x) x x x - -/* the parent is always given by index/2 */ -#define PQ_PARENT_INDEX(i) ((i) >> 1) -#define PQ_FIRST_ENTRY 1 - -/* left and right children are index * 2 and (index * 2) +1 respectively */ -#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1) - -typedef struct _pqueue { - int size, max_size; - - rectangle_t **elements; - rectangle_t *elements_embedded[1024]; -} pqueue_t; - -typedef struct { - rectangle_t **start; - pqueue_t stop; - rectangle_t head, tail; - rectangle_t *insert_cursor; - int32_t current_y; - int32_t xmin, xmax; - - struct coverage { - struct cell { - struct cell *prev, *next; - int x, covered, uncovered; - } head, tail, *cursor; - unsigned int count; - cairo_freepool_t pool; - } coverage; - - cairo_half_open_span_t spans_stack[CAIRO_STACK_ARRAY_LENGTH (cairo_half_open_span_t)]; - cairo_half_open_span_t *spans; - unsigned int num_spans; - unsigned int size_spans; - - jmp_buf jmpbuf; -} sweep_line_t; - -static inline int -rectangle_compare_start (const rectangle_t *a, - const rectangle_t *b) -{ - int cmp; - - cmp = a->top_y - b->top_y; - if (cmp) - return cmp; - - return a->left - b->left; -} - -static inline int -rectangle_compare_stop (const rectangle_t *a, - const rectangle_t *b) -{ - return a->bottom_y - b->bottom_y; -} - -static inline void -pqueue_init (pqueue_t *pq) -{ - pq->max_size = ARRAY_LENGTH (pq->elements_embedded); - pq->size = 0; - - pq->elements = pq->elements_embedded; - pq->elements[PQ_FIRST_ENTRY] = NULL; -} - -static inline void -pqueue_fini (pqueue_t *pq) -{ - if (pq->elements != pq->elements_embedded) - free (pq->elements); -} - -static cairo_bool_t -pqueue_grow (pqueue_t *pq) -{ - rectangle_t **new_elements; - pq->max_size *= 2; - - if (pq->elements == pq->elements_embedded) { - new_elements = _cairo_malloc_ab (pq->max_size, - sizeof (rectangle_t *)); - if (unlikely (new_elements == NULL)) - return FALSE; - - memcpy (new_elements, pq->elements_embedded, - sizeof (pq->elements_embedded)); - } else { - new_elements = _cairo_realloc_ab (pq->elements, - pq->max_size, - sizeof (rectangle_t *)); - if (unlikely (new_elements == NULL)) - return FALSE; - } - - pq->elements = new_elements; - return TRUE; -} - -static inline void -pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle) -{ - rectangle_t **elements; - int i, parent; - - if (unlikely (sweep->stop.size + 1 == sweep->stop.max_size)) { - if (unlikely (! pqueue_grow (&sweep->stop))) - longjmp (sweep->jmpbuf, - _cairo_error (CAIRO_STATUS_NO_MEMORY)); - } - - elements = sweep->stop.elements; - for (i = ++sweep->stop.size; - i != PQ_FIRST_ENTRY && - rectangle_compare_stop (rectangle, - elements[parent = PQ_PARENT_INDEX (i)]) < 0; - i = parent) - { - elements[i] = elements[parent]; - } - - elements[i] = rectangle; -} - -static inline void -pqueue_pop (pqueue_t *pq) -{ - rectangle_t **elements = pq->elements; - rectangle_t *tail; - int child, i; - - tail = elements[pq->size--]; - if (pq->size == 0) { - elements[PQ_FIRST_ENTRY] = NULL; - return; - } - - for (i = PQ_FIRST_ENTRY; - (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size; - i = child) - { - if (child != pq->size && - rectangle_compare_stop (elements[child+1], - elements[child]) < 0) - { - child++; - } - - if (rectangle_compare_stop (elements[child], tail) >= 0) - break; - - elements[i] = elements[child]; - } - elements[i] = tail; -} - -static inline rectangle_t * -peek_stop (sweep_line_t *sweep) -{ - return sweep->stop.elements[PQ_FIRST_ENTRY]; -} - -CAIRO_COMBSORT_DECLARE (rectangle_sort, rectangle_t *, rectangle_compare_start) - -static void -sweep_line_init (sweep_line_t *sweep) -{ - sweep->head.left = INT_MIN; - sweep->head.next = &sweep->tail; - sweep->tail.left = INT_MAX; - sweep->tail.prev = &sweep->head; - sweep->insert_cursor = &sweep->tail; - - _cairo_freepool_init (&sweep->coverage.pool, sizeof (struct cell)); - - sweep->spans = sweep->spans_stack; - sweep->size_spans = ARRAY_LENGTH (sweep->spans_stack); - - sweep->coverage.head.prev = NULL; - sweep->coverage.head.x = INT_MIN; - sweep->coverage.tail.next = NULL; - sweep->coverage.tail.x = INT_MAX; - - pqueue_init (&sweep->stop); -} - -static void -sweep_line_fini (sweep_line_t *sweep) -{ - _cairo_freepool_fini (&sweep->coverage.pool); - pqueue_fini (&sweep->stop); - - if (sweep->spans != sweep->spans_stack) - free (sweep->spans); -} - -static inline void -add_cell (sweep_line_t *sweep, int x, int covered, int uncovered) -{ - struct cell *cell; - - cell = sweep->coverage.cursor; - if (cell->x > x) { - do { - UNROLL3({ - if (cell->prev->x < x) - break; - cell = cell->prev; - }) - } while (TRUE); - } else { - if (cell->x == x) - goto found; - - do { - UNROLL3({ - cell = cell->next; - if (cell->x >= x) - break; - }) - } while (TRUE); - } - - if (x != cell->x) { - struct cell *c; - - sweep->coverage.count++; - - c = _cairo_freepool_alloc (&sweep->coverage.pool); - if (unlikely (c == NULL)) { - longjmp (sweep->jmpbuf, - _cairo_error (CAIRO_STATUS_NO_MEMORY)); - } - - cell->prev->next = c; - c->prev = cell->prev; - c->next = cell; - cell->prev = c; - - c->x = x; - c->covered = 0; - c->uncovered = 0; - - cell = c; - } - -found: - cell->covered += covered; - cell->uncovered += uncovered; - sweep->coverage.cursor = cell; -} - -static inline void -_active_edges_to_spans (sweep_line_t *sweep) -{ - int32_t y = sweep->current_y; - rectangle_t *rectangle; - int coverage, prev_coverage; - int prev_x; - struct cell *cell; - - sweep->num_spans = 0; - if (sweep->head.next == &sweep->tail) - return; - - sweep->coverage.head.next = &sweep->coverage.tail; - sweep->coverage.tail.prev = &sweep->coverage.head; - sweep->coverage.cursor = &sweep->coverage.tail; - sweep->coverage.count = 0; - - /* XXX cell coverage only changes when a rectangle appears or - * disappears. Try only modifying coverage at such times. - */ - for (rectangle = sweep->head.next; - rectangle != &sweep->tail; - rectangle = rectangle->next) - { - int height; - int frac, i; - - if (y == rectangle->bottom_y) { - height = rectangle->bottom & CAIRO_FIXED_FRAC_MASK; - if (height == 0) - continue; - } else - height = CAIRO_FIXED_ONE; - if (y == rectangle->top_y) - height -= rectangle->top & CAIRO_FIXED_FRAC_MASK; - height *= rectangle->dir; - - i = _cairo_fixed_integer_part (rectangle->left), - frac = _cairo_fixed_fractional_part (rectangle->left); - add_cell (sweep, i, - (CAIRO_FIXED_ONE-frac) * height, - frac * height); - - i = _cairo_fixed_integer_part (rectangle->right), - frac = _cairo_fixed_fractional_part (rectangle->right); - add_cell (sweep, i, - -(CAIRO_FIXED_ONE-frac) * height, - -frac * height); - } - - if (2*sweep->coverage.count >= sweep->size_spans) { - unsigned size; - - size = sweep->size_spans; - while (size <= 2*sweep->coverage.count) - size <<= 1; - - if (sweep->spans != sweep->spans_stack) - free (sweep->spans); - - sweep->spans = _cairo_malloc_ab (size, sizeof (cairo_half_open_span_t)); - if (unlikely (sweep->spans == NULL)) - longjmp (sweep->jmpbuf, _cairo_error (CAIRO_STATUS_NO_MEMORY)); - - sweep->size_spans = size; - } - - prev_coverage = coverage = 0; - prev_x = INT_MIN; - for (cell = sweep->coverage.head.next; cell != &sweep->coverage.tail; cell = cell->next) { - if (cell->x != prev_x && coverage != prev_coverage) { - int n = sweep->num_spans++; - int c = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8); - sweep->spans[n].x = prev_x; - sweep->spans[n].inverse = 0; - sweep->spans[n].coverage = c - (c >> 8); - prev_coverage = coverage; - } - - coverage += cell->covered; - if (coverage != prev_coverage) { - int n = sweep->num_spans++; - int c = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8); - sweep->spans[n].x = cell->x; - sweep->spans[n].inverse = 0; - sweep->spans[n].coverage = c - (c >> 8); - prev_coverage = coverage; - } - coverage += cell->uncovered; - prev_x = cell->x + 1; - } - _cairo_freepool_reset (&sweep->coverage.pool); - - if (sweep->num_spans) { - if (prev_x <= sweep->xmax) { - int n = sweep->num_spans++; - int c = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8); - sweep->spans[n].x = prev_x; - sweep->spans[n].inverse = 0; - sweep->spans[n].coverage = c - (c >> 8); - } - - if (coverage && prev_x < sweep->xmax) { - int n = sweep->num_spans++; - sweep->spans[n].x = sweep->xmax; - sweep->spans[n].inverse = 1; - sweep->spans[n].coverage = 0; - } - } -} - -static inline void -sweep_line_delete (sweep_line_t *sweep, - rectangle_t *rectangle) -{ - if (sweep->insert_cursor == rectangle) - sweep->insert_cursor = rectangle->next; - - rectangle->prev->next = rectangle->next; - rectangle->next->prev = rectangle->prev; - - pqueue_pop (&sweep->stop); -} - -static inline void -sweep_line_insert (sweep_line_t *sweep, - rectangle_t *rectangle) -{ - rectangle_t *pos; - - pos = sweep->insert_cursor; - if (pos->left != rectangle->left) { - if (pos->left > rectangle->left) { - do { - UNROLL3({ - if (pos->prev->left < rectangle->left) - break; - pos = pos->prev; - }) - } while (TRUE); - } else { - do { - UNROLL3({ - pos = pos->next; - if (pos->left >= rectangle->left) - break; - }); - } while (TRUE); - } - } - - pos->prev->next = rectangle; - rectangle->prev = pos->prev; - rectangle->next = pos; - pos->prev = rectangle; - sweep->insert_cursor = rectangle; - - pqueue_push (sweep, rectangle); -} - -static void -render_rows (sweep_line_t *sweep_line, - cairo_span_renderer_t *renderer, - int height) -{ - cairo_status_t status; - - _active_edges_to_spans (sweep_line); - - status = renderer->render_rows (renderer, - sweep_line->current_y, height, - sweep_line->spans, - sweep_line->num_spans); - if (unlikely (status)) - longjmp (sweep_line->jmpbuf, status); -} - -static cairo_status_t -generate (cairo_rectangular_scan_converter_t *self, - cairo_span_renderer_t *renderer, - rectangle_t **rectangles) -{ - sweep_line_t sweep_line; - rectangle_t *start, *stop; - cairo_status_t status; - - sweep_line_init (&sweep_line); - sweep_line.xmin = _cairo_fixed_integer_part (self->extents.p1.x); - sweep_line.xmax = _cairo_fixed_integer_part (self->extents.p2.x); - sweep_line.start = rectangles; - if ((status = setjmp (sweep_line.jmpbuf))) - goto out; - - sweep_line.current_y = _cairo_fixed_integer_part (self->extents.p1.y); - start = *sweep_line.start++; - do { - if (start->top_y != sweep_line.current_y) { - render_rows (&sweep_line, renderer, - start->top_y - sweep_line.current_y); - sweep_line.current_y = start->top_y; - } - - do { - sweep_line_insert (&sweep_line, start); - start = *sweep_line.start++; - if (start == NULL) - goto end; - if (start->top_y != sweep_line.current_y) - break; - } while (TRUE); - - render_rows (&sweep_line, renderer, 1); - - stop = peek_stop (&sweep_line); - while (stop->bottom_y == sweep_line.current_y) { - sweep_line_delete (&sweep_line, stop); - stop = peek_stop (&sweep_line); - if (stop == NULL) - break; - } - - sweep_line.current_y++; - - while (stop != NULL && stop->bottom_y < start->top_y) { - if (stop->bottom_y != sweep_line.current_y) { - render_rows (&sweep_line, renderer, - stop->bottom_y - sweep_line.current_y); - sweep_line.current_y = stop->bottom_y; - } - - render_rows (&sweep_line, renderer, 1); - - do { - sweep_line_delete (&sweep_line, stop); - stop = peek_stop (&sweep_line); - } while (stop != NULL && stop->bottom_y == sweep_line.current_y); - - sweep_line.current_y++; - } - } while (TRUE); - - end: - render_rows (&sweep_line, renderer, 1); - - stop = peek_stop (&sweep_line); - while (stop->bottom_y == sweep_line.current_y) { - sweep_line_delete (&sweep_line, stop); - stop = peek_stop (&sweep_line); - if (stop == NULL) - goto out; - } - - while (++sweep_line.current_y < _cairo_fixed_integer_part (self->extents.p2.y)) { - if (stop->bottom_y != sweep_line.current_y) { - render_rows (&sweep_line, renderer, - stop->bottom_y - sweep_line.current_y); - sweep_line.current_y = stop->bottom_y; - } - - render_rows (&sweep_line, renderer, 1); - - do { - sweep_line_delete (&sweep_line, stop); - stop = peek_stop (&sweep_line); - if (stop == NULL) - goto out; - } while (stop->bottom_y == sweep_line.current_y); - - } - - out: - sweep_line_fini (&sweep_line); - - return status; -} -static void generate_row(cairo_span_renderer_t *renderer, - const rectangle_t *r, - int y, int h, - uint16_t coverage) -{ - cairo_half_open_span_t spans[4]; - unsigned int num_spans = 0; - int x1 = _cairo_fixed_integer_part (r->left); - int x2 = _cairo_fixed_integer_part (r->right); - if (x2 > x1) { - if (! _cairo_fixed_is_integer (r->left)) { - spans[num_spans].x = x1; - spans[num_spans].coverage = - coverage * (256 - _cairo_fixed_fractional_part (r->left)) >> 8; - num_spans++; - x1++; - } - - if (x2 > x1) { - spans[num_spans].x = x1; - spans[num_spans].coverage = coverage - (coverage >> 8); - num_spans++; - } - - if (! _cairo_fixed_is_integer (r->right)) { - spans[num_spans].x = x2++; - spans[num_spans].coverage = - coverage * _cairo_fixed_fractional_part (r->right) >> 8; - num_spans++; - } - } else { - spans[num_spans].x = x2++; - spans[num_spans].coverage = coverage * (r->right - r->left) >> 8; - num_spans++; - } - - spans[num_spans].x = x2; - spans[num_spans].coverage = 0; - num_spans++; - - renderer->render_rows (renderer, y, h, spans, num_spans); -} - -static cairo_status_t -generate_box (cairo_rectangular_scan_converter_t *self, - cairo_span_renderer_t *renderer) -{ - const rectangle_t *r = self->chunks.base; - int y1 = _cairo_fixed_integer_part (r->top); - int y2 = _cairo_fixed_integer_part (r->bottom); - if (y2 > y1) { - if (! _cairo_fixed_is_integer (r->top)) { - generate_row(renderer, r, y1, 1, - 256 - _cairo_fixed_fractional_part (r->top)); - y1++; - } - - if (y2 > y1) - generate_row(renderer, r, y1, y2-y1, 256); - - if (! _cairo_fixed_is_integer (r->bottom)) - generate_row(renderer, r, y2, 1, - _cairo_fixed_fractional_part (r->bottom)); - } else - generate_row(renderer, r, y1, 1, r->bottom - r->top); - - return CAIRO_STATUS_SUCCESS; -} - -static cairo_status_t -_cairo_rectangular_scan_converter_generate (void *converter, - cairo_span_renderer_t *renderer) -{ - cairo_rectangular_scan_converter_t *self = converter; - rectangle_t *rectangles_stack[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *)]; - rectangle_t **rectangles; - struct _cairo_rectangular_scan_converter_chunk *chunk; - cairo_status_t status; - int i, j; - - if (unlikely (self->num_rectangles == 0)) { - return renderer->render_rows (renderer, - _cairo_fixed_integer_part (self->extents.p1.y), - _cairo_fixed_integer_part (self->extents.p2.y - self->extents.p1.y), - NULL, 0); - } - - if (self->num_rectangles == 1) - return generate_box (self, renderer); - - rectangles = rectangles_stack; - if (unlikely (self->num_rectangles >= ARRAY_LENGTH (rectangles_stack))) { - rectangles = _cairo_malloc_ab (self->num_rectangles + 1, - sizeof (rectangle_t *)); - if (unlikely (rectangles == NULL)) - return _cairo_error (CAIRO_STATUS_NO_MEMORY); - } - - j = 0; - for (chunk = &self->chunks; chunk != NULL; chunk = chunk->next) { - rectangle_t *rectangle; - - rectangle = chunk->base; - for (i = 0; i < chunk->count; i++) - rectangles[j++] = &rectangle[i]; - } - rectangle_sort (rectangles, j); - rectangles[j] = NULL; - - status = generate (self, renderer, rectangles); - - if (rectangles != rectangles_stack) - free (rectangles); - - return status; -} - -static rectangle_t * -_allocate_rectangle (cairo_rectangular_scan_converter_t *self) -{ - rectangle_t *rectangle; - struct _cairo_rectangular_scan_converter_chunk *chunk; - - chunk = self->tail; - if (chunk->count == chunk->size) { - int size; - - size = chunk->size * 2; - chunk->next = _cairo_malloc_ab_plus_c (size, - sizeof (rectangle_t), - sizeof (struct _cairo_rectangular_scan_converter_chunk)); - - if (unlikely (chunk->next == NULL)) - return NULL; - - chunk = chunk->next; - chunk->next = NULL; - chunk->count = 0; - chunk->size = size; - chunk->base = chunk + 1; - self->tail = chunk; - } - - rectangle = chunk->base; - return rectangle + chunk->count++; -} - -cairo_status_t -_cairo_rectangular_scan_converter_add_box (cairo_rectangular_scan_converter_t *self, - const cairo_box_t *box, - int dir) -{ - rectangle_t *rectangle; - - rectangle = _allocate_rectangle (self); - if (unlikely (rectangle == NULL)) - return _cairo_error (CAIRO_STATUS_NO_MEMORY); - - rectangle->dir = dir; - rectangle->left = MAX (box->p1.x, self->extents.p1.x); - rectangle->right = MIN (box->p2.x, self->extents.p2.x); - if (unlikely (rectangle->right <= rectangle->left)) { - self->tail->count--; - return CAIRO_STATUS_SUCCESS; - } - - rectangle->top = MAX (box->p1.y, self->extents.p1.y); - rectangle->top_y = _cairo_fixed_integer_floor (rectangle->top); - rectangle->bottom = MIN (box->p2.y, self->extents.p2.y); - rectangle->bottom_y = _cairo_fixed_integer_floor (rectangle->bottom); - if (likely (rectangle->bottom > rectangle->top)) - self->num_rectangles++; - else - self->tail->count--; - - return CAIRO_STATUS_SUCCESS; -} - -static void -_cairo_rectangular_scan_converter_destroy (void *converter) -{ - cairo_rectangular_scan_converter_t *self = converter; - struct _cairo_rectangular_scan_converter_chunk *chunk, *next; - - for (chunk = self->chunks.next; chunk != NULL; chunk = next) { - next = chunk->next; - free (chunk); - } -} - -void -_cairo_rectangular_scan_converter_init (cairo_rectangular_scan_converter_t *self, - const cairo_rectangle_int_t *extents) -{ - self->base.destroy = _cairo_rectangular_scan_converter_destroy; - self->base.generate = _cairo_rectangular_scan_converter_generate; - - _cairo_box_from_rectangle (&self->extents, extents); - - self->chunks.base = self->buf; - self->chunks.next = NULL; - self->chunks.count = 0; - self->chunks.size = sizeof (self->buf) / sizeof (rectangle_t); - self->tail = &self->chunks; - - self->num_rectangles = 0; -} |