Source code
Revision control
Copy as Markdown
Other Tools
/* 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
*
* 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;
}