1 /* cairo - a vector graphics library with display and print output
2 *
3 * Copyright © 2009 Intel Corporation
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it either under the terms of the GNU Lesser General Public
7 * License version 2.1 as published by the Free Software Foundation
8 * (the "LGPL") or, at your option, under the terms of the Mozilla
9 * Public License Version 1.1 (the "MPL"). If you do not alter this
10 * notice, a recipient may use your version of this file under either
11 * the MPL or the LGPL.
12 *
13 * You should have received a copy of the LGPL along with this library
14 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
16 * You should have received a copy of the MPL along with this library
17 * in the file COPYING-MPL-1.1
18 *
19 * The contents of this file are subject to the Mozilla Public License
20 * Version 1.1 (the "License"); you may not use this file except in
21 * compliance with the License. You may obtain a copy of the License at
22 * http://www.mozilla.org/MPL/
23 *
24 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
25 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
26 * the specific language governing rights and limitations.
27 *
28 * The Original Code is the cairo graphics library.
29 *
30 * Contributor(s):
31 * Chris Wilson <chris@chris-wilson.co.uk>
32 */
33
34 #include "cairoint.h"
35
36 #include "cairo-combsort-private.h"
37 #include "cairo-error-private.h"
38 #include "cairo-freelist-private.h"
39 #include "cairo-list-private.h"
40 #include "cairo-spans-private.h"
41
42 #include <setjmp.h>
43
44 typedef struct _rectangle {
45 struct _rectangle *next, *prev;
46 cairo_fixed_t left, right;
47 cairo_fixed_t top, bottom;
48 int32_t top_y, bottom_y;
49 int dir;
50 } rectangle_t;
51
52 #define UNROLL3(x) x x x
53
54 /* the parent is always given by index/2 */
55 #define PQ_PARENT_INDEX(i) ((i) >> 1)
56 #define PQ_FIRST_ENTRY 1
57
58 /* left and right children are index * 2 and (index * 2) +1 respectively */
59 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
60
61 typedef struct _pqueue {
62 int size, max_size;
63
64 rectangle_t **elements;
65 rectangle_t *elements_embedded[1024];
66 } pqueue_t;
67
68 typedef struct {
69 rectangle_t **start;
70 pqueue_t stop;
71 rectangle_t head, tail;
72 rectangle_t *insert_cursor;
73 int32_t current_y;
74 int32_t xmin, xmax;
75
76 struct coverage {
77 struct cell {
78 struct cell *prev, *next;
79 int x, covered, uncovered;
80 } head, tail, *cursor;
81 unsigned int count;
82 cairo_freepool_t pool;
83 } coverage;
84
85 cairo_half_open_span_t spans_stack[CAIRO_STACK_ARRAY_LENGTH (cairo_half_open_span_t)];
86 cairo_half_open_span_t *spans;
87 unsigned int num_spans;
88 unsigned int size_spans;
89
90 jmp_buf jmpbuf;
91 } sweep_line_t;
92
93 static inline int
rectangle_compare_start(const rectangle_t * a,const rectangle_t * b)94 rectangle_compare_start (const rectangle_t *a,
95 const rectangle_t *b)
96 {
97 int cmp;
98
99 cmp = a->top_y - b->top_y;
100 if (cmp)
101 return cmp;
102
103 return a->left - b->left;
104 }
105
106 static inline int
rectangle_compare_stop(const rectangle_t * a,const rectangle_t * b)107 rectangle_compare_stop (const rectangle_t *a,
108 const rectangle_t *b)
109 {
110 return a->bottom_y - b->bottom_y;
111 }
112
113 static inline void
pqueue_init(pqueue_t * pq)114 pqueue_init (pqueue_t *pq)
115 {
116 pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
117 pq->size = 0;
118
119 pq->elements = pq->elements_embedded;
120 pq->elements[PQ_FIRST_ENTRY] = NULL;
121 }
122
123 static inline void
pqueue_fini(pqueue_t * pq)124 pqueue_fini (pqueue_t *pq)
125 {
126 if (pq->elements != pq->elements_embedded)
127 free (pq->elements);
128 }
129
130 static cairo_bool_t
pqueue_grow(pqueue_t * pq)131 pqueue_grow (pqueue_t *pq)
132 {
133 rectangle_t **new_elements;
134 pq->max_size *= 2;
135
136 if (pq->elements == pq->elements_embedded) {
137 new_elements = _cairo_malloc_ab (pq->max_size,
138 sizeof (rectangle_t *));
139 if (unlikely (new_elements == NULL))
140 return FALSE;
141
142 memcpy (new_elements, pq->elements_embedded,
143 sizeof (pq->elements_embedded));
144 } else {
145 new_elements = _cairo_realloc_ab (pq->elements,
146 pq->max_size,
147 sizeof (rectangle_t *));
148 if (unlikely (new_elements == NULL))
149 return FALSE;
150 }
151
152 pq->elements = new_elements;
153 return TRUE;
154 }
155
156 static inline void
pqueue_push(sweep_line_t * sweep,rectangle_t * rectangle)157 pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
158 {
159 rectangle_t **elements;
160 int i, parent;
161
162 if (unlikely (sweep->stop.size + 1 == sweep->stop.max_size)) {
163 if (unlikely (! pqueue_grow (&sweep->stop)))
164 longjmp (sweep->jmpbuf,
165 _cairo_error (CAIRO_STATUS_NO_MEMORY));
166 }
167
168 elements = sweep->stop.elements;
169 for (i = ++sweep->stop.size;
170 i != PQ_FIRST_ENTRY &&
171 rectangle_compare_stop (rectangle,
172 elements[parent = PQ_PARENT_INDEX (i)]) < 0;
173 i = parent)
174 {
175 elements[i] = elements[parent];
176 }
177
178 elements[i] = rectangle;
179 }
180
181 static inline void
pqueue_pop(pqueue_t * pq)182 pqueue_pop (pqueue_t *pq)
183 {
184 rectangle_t **elements = pq->elements;
185 rectangle_t *tail;
186 int child, i;
187
188 tail = elements[pq->size--];
189 if (pq->size == 0) {
190 elements[PQ_FIRST_ENTRY] = NULL;
191 return;
192 }
193
194 for (i = PQ_FIRST_ENTRY;
195 (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
196 i = child)
197 {
198 if (child != pq->size &&
199 rectangle_compare_stop (elements[child+1],
200 elements[child]) < 0)
201 {
202 child++;
203 }
204
205 if (rectangle_compare_stop (elements[child], tail) >= 0)
206 break;
207
208 elements[i] = elements[child];
209 }
210 elements[i] = tail;
211 }
212
213 static inline rectangle_t *
peek_stop(sweep_line_t * sweep)214 peek_stop (sweep_line_t *sweep)
215 {
216 return sweep->stop.elements[PQ_FIRST_ENTRY];
217 }
218
CAIRO_COMBSORT_DECLARE(rectangle_sort,rectangle_t *,rectangle_compare_start)219 CAIRO_COMBSORT_DECLARE (rectangle_sort, rectangle_t *, rectangle_compare_start)
220
221 static void
222 sweep_line_init (sweep_line_t *sweep)
223 {
224 sweep->head.left = INT_MIN;
225 sweep->head.next = &sweep->tail;
226 sweep->tail.left = INT_MAX;
227 sweep->tail.prev = &sweep->head;
228 sweep->insert_cursor = &sweep->tail;
229
230 _cairo_freepool_init (&sweep->coverage.pool, sizeof (struct cell));
231
232 sweep->spans = sweep->spans_stack;
233 sweep->size_spans = ARRAY_LENGTH (sweep->spans_stack);
234
235 sweep->coverage.head.prev = NULL;
236 sweep->coverage.head.x = INT_MIN;
237 sweep->coverage.tail.next = NULL;
238 sweep->coverage.tail.x = INT_MAX;
239
240 pqueue_init (&sweep->stop);
241 }
242
243 static void
sweep_line_fini(sweep_line_t * sweep)244 sweep_line_fini (sweep_line_t *sweep)
245 {
246 _cairo_freepool_fini (&sweep->coverage.pool);
247 pqueue_fini (&sweep->stop);
248
249 if (sweep->spans != sweep->spans_stack)
250 free (sweep->spans);
251 }
252
253 static inline void
add_cell(sweep_line_t * sweep,int x,int covered,int uncovered)254 add_cell (sweep_line_t *sweep, int x, int covered, int uncovered)
255 {
256 struct cell *cell;
257
258 cell = sweep->coverage.cursor;
259 if (cell->x > x) {
260 do {
261 UNROLL3({
262 if (cell->prev->x < x)
263 break;
264 cell = cell->prev;
265 })
266 } while (TRUE);
267 } else {
268 if (cell->x == x)
269 goto found;
270
271 do {
272 UNROLL3({
273 cell = cell->next;
274 if (cell->x >= x)
275 break;
276 })
277 } while (TRUE);
278 }
279
280 if (x != cell->x) {
281 struct cell *c;
282
283 sweep->coverage.count++;
284
285 c = _cairo_freepool_alloc (&sweep->coverage.pool);
286 if (unlikely (c == NULL)) {
287 longjmp (sweep->jmpbuf,
288 _cairo_error (CAIRO_STATUS_NO_MEMORY));
289 }
290
291 cell->prev->next = c;
292 c->prev = cell->prev;
293 c->next = cell;
294 cell->prev = c;
295
296 c->x = x;
297 c->covered = 0;
298 c->uncovered = 0;
299
300 cell = c;
301 }
302
303 found:
304 cell->covered += covered;
305 cell->uncovered += uncovered;
306 sweep->coverage.cursor = cell;
307 }
308
309 static inline void
_active_edges_to_spans(sweep_line_t * sweep)310 _active_edges_to_spans (sweep_line_t *sweep)
311 {
312 int32_t y = sweep->current_y;
313 rectangle_t *rectangle;
314 int coverage, prev_coverage;
315 int prev_x;
316 struct cell *cell;
317
318 sweep->num_spans = 0;
319 if (sweep->head.next == &sweep->tail)
320 return;
321
322 sweep->coverage.head.next = &sweep->coverage.tail;
323 sweep->coverage.tail.prev = &sweep->coverage.head;
324 sweep->coverage.cursor = &sweep->coverage.tail;
325 sweep->coverage.count = 0;
326
327 /* XXX cell coverage only changes when a rectangle appears or
328 * disappears. Try only modifying coverage at such times.
329 */
330 for (rectangle = sweep->head.next;
331 rectangle != &sweep->tail;
332 rectangle = rectangle->next)
333 {
334 int height;
335 int frac, i;
336
337 if (y == rectangle->bottom_y) {
338 height = rectangle->bottom & CAIRO_FIXED_FRAC_MASK;
339 if (height == 0)
340 continue;
341 } else
342 height = CAIRO_FIXED_ONE;
343 if (y == rectangle->top_y)
344 height -= rectangle->top & CAIRO_FIXED_FRAC_MASK;
345 height *= rectangle->dir;
346
347 i = _cairo_fixed_integer_part (rectangle->left),
348 frac = _cairo_fixed_fractional_part (rectangle->left);
349 add_cell (sweep, i,
350 (CAIRO_FIXED_ONE-frac) * height,
351 frac * height);
352
353 i = _cairo_fixed_integer_part (rectangle->right),
354 frac = _cairo_fixed_fractional_part (rectangle->right);
355 add_cell (sweep, i,
356 -(CAIRO_FIXED_ONE-frac) * height,
357 -frac * height);
358 }
359
360 if (2*sweep->coverage.count >= sweep->size_spans) {
361 unsigned size;
362
363 size = sweep->size_spans;
364 while (size <= 2*sweep->coverage.count)
365 size <<= 1;
366
367 if (sweep->spans != sweep->spans_stack)
368 free (sweep->spans);
369
370 sweep->spans = _cairo_malloc_ab (size, sizeof (cairo_half_open_span_t));
371 if (unlikely (sweep->spans == NULL))
372 longjmp (sweep->jmpbuf, _cairo_error (CAIRO_STATUS_NO_MEMORY));
373
374 sweep->size_spans = size;
375 }
376
377 prev_coverage = coverage = 0;
378 prev_x = INT_MIN;
379 for (cell = sweep->coverage.head.next; cell != &sweep->coverage.tail; cell = cell->next) {
380 if (cell->x != prev_x && coverage != prev_coverage) {
381 int n = sweep->num_spans++;
382 sweep->spans[n].x = prev_x;
383 sweep->spans[n].coverage = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8);
384 sweep->spans[n].coverage -= sweep->spans[n].coverage >> 8;
385 prev_coverage = coverage;
386 }
387
388 coverage += cell->covered;
389 if (coverage != prev_coverage) {
390 int n = sweep->num_spans++;
391 sweep->spans[n].x = cell->x;
392 sweep->spans[n].coverage = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8);
393 sweep->spans[n].coverage -= sweep->spans[n].coverage >> 8;
394 prev_coverage = coverage;
395 }
396 coverage += cell->uncovered;
397 prev_x = cell->x + 1;
398 }
399 _cairo_freepool_reset (&sweep->coverage.pool);
400
401 if (sweep->num_spans) {
402 if (prev_x <= sweep->xmax) {
403 int n = sweep->num_spans++;
404 sweep->spans[n].x = prev_x;
405 sweep->spans[n].coverage = coverage;
406 }
407
408 if (coverage && prev_x < sweep->xmax) {
409 int n = sweep->num_spans++;
410 sweep->spans[n].x = sweep->xmax;
411 sweep->spans[n].coverage = 0;
412 }
413 }
414 }
415
416 static inline void
sweep_line_delete(sweep_line_t * sweep,rectangle_t * rectangle)417 sweep_line_delete (sweep_line_t *sweep,
418 rectangle_t *rectangle)
419 {
420 if (sweep->insert_cursor == rectangle)
421 sweep->insert_cursor = rectangle->next;
422
423 rectangle->prev->next = rectangle->next;
424 rectangle->next->prev = rectangle->prev;
425
426 pqueue_pop (&sweep->stop);
427 }
428
429 static inline void
sweep_line_insert(sweep_line_t * sweep,rectangle_t * rectangle)430 sweep_line_insert (sweep_line_t *sweep,
431 rectangle_t *rectangle)
432 {
433 rectangle_t *pos;
434
435 pos = sweep->insert_cursor;
436 if (pos->left != rectangle->left) {
437 if (pos->left > rectangle->left) {
438 do {
439 UNROLL3({
440 if (pos->prev->left < rectangle->left)
441 break;
442 pos = pos->prev;
443 })
444 } while (TRUE);
445 } else {
446 do {
447 UNROLL3({
448 pos = pos->next;
449 if (pos->left >= rectangle->left)
450 break;
451 });
452 } while (TRUE);
453 }
454 }
455
456 pos->prev->next = rectangle;
457 rectangle->prev = pos->prev;
458 rectangle->next = pos;
459 pos->prev = rectangle;
460 sweep->insert_cursor = rectangle;
461
462 pqueue_push (sweep, rectangle);
463 }
464
465 static void
render_rows(sweep_line_t * sweep_line,cairo_span_renderer_t * renderer,int height)466 render_rows (sweep_line_t *sweep_line,
467 cairo_span_renderer_t *renderer,
468 int height)
469 {
470 cairo_status_t status;
471
472 _active_edges_to_spans (sweep_line);
473
474 status = renderer->render_rows (renderer,
475 sweep_line->current_y, height,
476 sweep_line->spans,
477 sweep_line->num_spans);
478 if (unlikely (status))
479 longjmp (sweep_line->jmpbuf, status);
480 }
481
482 static cairo_status_t
generate(cairo_rectangular_scan_converter_t * self,cairo_span_renderer_t * renderer,rectangle_t ** rectangles)483 generate (cairo_rectangular_scan_converter_t *self,
484 cairo_span_renderer_t *renderer,
485 rectangle_t **rectangles)
486 {
487 sweep_line_t sweep_line;
488 rectangle_t *start, *stop;
489 cairo_status_t status;
490
491 sweep_line_init (&sweep_line);
492 sweep_line.xmin = self->xmin;
493 sweep_line.xmax = self->xmax;
494 sweep_line.start = rectangles;
495 if ((status = setjmp (sweep_line.jmpbuf)))
496 goto BAIL;
497
498 sweep_line.current_y = self->ymin;
499 start = *sweep_line.start++;
500 do {
501 if (start->top_y != sweep_line.current_y) {
502 render_rows (&sweep_line, renderer,
503 start->top_y - sweep_line.current_y);
504 sweep_line.current_y = start->top_y;
505 }
506
507 do {
508 sweep_line_insert (&sweep_line, start);
509 start = *sweep_line.start++;
510 if (start == NULL)
511 goto end;
512 if (start->top_y != sweep_line.current_y)
513 break;
514 } while (TRUE);
515
516 render_rows (&sweep_line, renderer, 1);
517
518 stop = peek_stop (&sweep_line);
519 while (stop->bottom_y == sweep_line.current_y) {
520 sweep_line_delete (&sweep_line, stop);
521 stop = peek_stop (&sweep_line);
522 if (stop == NULL)
523 break;
524 }
525
526 sweep_line.current_y++;
527
528 while (stop != NULL && stop->bottom_y < start->top_y) {
529 if (stop->bottom_y != sweep_line.current_y) {
530 render_rows (&sweep_line, renderer,
531 stop->bottom_y - sweep_line.current_y);
532 sweep_line.current_y = stop->bottom_y;
533 }
534
535 render_rows (&sweep_line, renderer, 1);
536
537 do {
538 sweep_line_delete (&sweep_line, stop);
539 stop = peek_stop (&sweep_line);
540 } while (stop != NULL && stop->bottom_y == sweep_line.current_y);
541
542 sweep_line.current_y++;
543 }
544 } while (TRUE);
545
546 end:
547 render_rows (&sweep_line, renderer, 1);
548
549 stop = peek_stop (&sweep_line);
550 while (stop->bottom_y == sweep_line.current_y) {
551 sweep_line_delete (&sweep_line, stop);
552 stop = peek_stop (&sweep_line);
553 if (stop == NULL)
554 goto out;
555 }
556
557 sweep_line.current_y++;
558
559 do {
560 if (stop->bottom_y != sweep_line.current_y) {
561 render_rows (&sweep_line, renderer,
562 stop->bottom_y - sweep_line.current_y);
563 sweep_line.current_y = stop->bottom_y;
564 }
565
566 render_rows (&sweep_line, renderer, 1);
567
568 do {
569 sweep_line_delete (&sweep_line, stop);
570 stop = peek_stop (&sweep_line);
571 if (stop == NULL)
572 goto out;
573 } while (stop->bottom_y == sweep_line.current_y);
574
575 sweep_line.current_y++;
576 } while (TRUE);
577
578 out:
579 status = renderer->render_rows (renderer,
580 sweep_line.current_y,
581 self->ymax - sweep_line.current_y,
582 NULL, 0);
583
584 BAIL:
585 sweep_line_fini (&sweep_line);
586
587 return status;
588 }
589
590 static cairo_status_t
_cairo_rectangular_scan_converter_generate(void * converter,cairo_span_renderer_t * renderer)591 _cairo_rectangular_scan_converter_generate (void *converter,
592 cairo_span_renderer_t *renderer)
593 {
594 cairo_rectangular_scan_converter_t *self = converter;
595 rectangle_t *rectangles_stack[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *)];
596 rectangle_t **rectangles;
597 struct _cairo_rectangular_scan_converter_chunk *chunk;
598 cairo_status_t status;
599 int i, j;
600
601 if (unlikely (self->num_rectangles == 0)) {
602 return renderer->render_rows (renderer,
603 self->ymin, self->ymax - self->ymin,
604 NULL, 0);
605 }
606
607 rectangles = rectangles_stack;
608 if (unlikely (self->num_rectangles >= ARRAY_LENGTH (rectangles_stack))) {
609 rectangles = _cairo_malloc_ab (self->num_rectangles + 1,
610 sizeof (rectangle_t *));
611 if (unlikely (rectangles == NULL))
612 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
613 }
614
615 j = 0;
616 for (chunk = &self->chunks; chunk != NULL; chunk = chunk->next) {
617 rectangle_t *rectangle;
618
619 rectangle = chunk->base;
620 for (i = 0; i < chunk->count; i++)
621 rectangles[j++] = &rectangle[i];
622 }
623 rectangle_sort (rectangles, j);
624 rectangles[j] = NULL;
625
626 status = generate (self, renderer, rectangles);
627
628 if (rectangles != rectangles_stack)
629 free (rectangles);
630
631 return status;
632 }
633
634 static rectangle_t *
_allocate_rectangle(cairo_rectangular_scan_converter_t * self)635 _allocate_rectangle (cairo_rectangular_scan_converter_t *self)
636 {
637 rectangle_t *rectangle;
638 struct _cairo_rectangular_scan_converter_chunk *chunk;
639
640 chunk = self->tail;
641 if (chunk->count == chunk->size) {
642 int size;
643
644 size = chunk->size * 2;
645 chunk->next = _cairo_malloc_ab_plus_c (size,
646 sizeof (rectangle_t),
647 sizeof (struct _cairo_rectangular_scan_converter_chunk));
648
649 if (unlikely (chunk->next == NULL))
650 return NULL;
651
652 chunk = chunk->next;
653 chunk->next = NULL;
654 chunk->count = 0;
655 chunk->size = size;
656 chunk->base = chunk + 1;
657 self->tail = chunk;
658 }
659
660 rectangle = chunk->base;
661 return rectangle + chunk->count++;
662 }
663
664 cairo_status_t
_cairo_rectangular_scan_converter_add_box(cairo_rectangular_scan_converter_t * self,const cairo_box_t * box,int dir)665 _cairo_rectangular_scan_converter_add_box (cairo_rectangular_scan_converter_t *self,
666 const cairo_box_t *box,
667 int dir)
668 {
669 rectangle_t *rectangle;
670
671 rectangle = _allocate_rectangle (self);
672 if (unlikely (rectangle == NULL))
673 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
674
675 rectangle->left = box->p1.x;
676 rectangle->right = box->p2.x;
677 rectangle->dir = dir;
678
679 rectangle->top = box->p1.y;
680 rectangle->top_y = _cairo_fixed_integer_floor (box->p1.y);
681 rectangle->bottom = box->p2.y;
682 rectangle->bottom_y = _cairo_fixed_integer_floor (box->p2.y);
683 assert (rectangle->bottom_y >= rectangle->top_y);
684
685 self->num_rectangles++;
686
687 return CAIRO_STATUS_SUCCESS;
688 }
689
690 static void
_cairo_rectangular_scan_converter_destroy(void * converter)691 _cairo_rectangular_scan_converter_destroy (void *converter)
692 {
693 cairo_rectangular_scan_converter_t *self = converter;
694 struct _cairo_rectangular_scan_converter_chunk *chunk, *next;
695
696 for (chunk = self->chunks.next; chunk != NULL; chunk = next) {
697 next = chunk->next;
698 free (chunk);
699 }
700 }
701
702 void
_cairo_rectangular_scan_converter_init(cairo_rectangular_scan_converter_t * self,const cairo_rectangle_int_t * extents)703 _cairo_rectangular_scan_converter_init (cairo_rectangular_scan_converter_t *self,
704 const cairo_rectangle_int_t *extents)
705 {
706 self->base.destroy = _cairo_rectangular_scan_converter_destroy;
707 self->base.add_edge = NULL;
708 self->base.add_polygon = NULL;
709 self->base.generate = _cairo_rectangular_scan_converter_generate;
710
711 self->xmin = extents->x;
712 self->xmax = extents->x + extents->width;
713 self->ymin = extents->y;
714 self->ymax = extents->y + extents->height;
715
716 self->chunks.base = self->buf;
717 self->chunks.next = NULL;
718 self->chunks.count = 0;
719 self->chunks.size = sizeof (self->buf) / sizeof (rectangle_t);
720 self->tail = &self->chunks;
721
722 self->num_rectangles = 0;
723 }
724