diff options
Diffstat (limited to 'libs/cairo-1.16.0/src/cairo-rectangular-scan-converter.c')
| -rw-r--r-- | libs/cairo-1.16.0/src/cairo-rectangular-scan-converter.c | 791 |
1 files changed, 791 insertions, 0 deletions
diff --git a/libs/cairo-1.16.0/src/cairo-rectangular-scan-converter.c b/libs/cairo-1.16.0/src/cairo-rectangular-scan-converter.c new file mode 100644 index 0000000..e353b34 --- /dev/null +++ b/libs/cairo-1.16.0/src/cairo-rectangular-scan-converter.c @@ -0,0 +1,791 @@ +/* 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; +} |