source/libs/cairo/cairo-src/src/cairo-rectangular-scan-converter.c

   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-inline.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
  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
 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
 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
 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
 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
 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
 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 *
 214 peek_stop (sweep_line_t *sweep)
 215 {
 216     return sweep->stop.elements[PQ_FIRST_ENTRY];
 217 }
 218
 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
 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
 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
 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             int c = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8);
 383             sweep->spans[n].x = prev_x;
 384             sweep->spans[n].inverse = 0;
 385             sweep->spans[n].coverage = c - (c >> 8);
 386             prev_coverage = coverage;
 387         }
 388
 389         coverage += cell->covered;
 390         if (coverage != prev_coverage) {
 391             int n = sweep->num_spans++;
 392             int c = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8);
 393             sweep->spans[n].x = cell->x;
 394             sweep->spans[n].inverse = 0;
 395             sweep->spans[n].coverage = c - (c >> 8);
 396             prev_coverage = coverage;
 397         }
 398         coverage += cell->uncovered;
 399         prev_x = cell->x + 1;
 400     }
 401     _cairo_freepool_reset (&sweep->coverage.pool);
 402
 403     if (sweep->num_spans) {
 404         if (prev_x <= sweep->xmax) {
 405             int n = sweep->num_spans++;
 406             int c = coverage >> (CAIRO_FIXED_FRAC_BITS * 2 - 8);
 407             sweep->spans[n].x = prev_x;
 408             sweep->spans[n].inverse = 0;
 409             sweep->spans[n].coverage = c - (c >> 8);
 410         }
 411
 412         if (coverage && prev_x < sweep->xmax) {
 413             int n = sweep->num_spans++;
 414             sweep->spans[n].x = sweep->xmax;
 415             sweep->spans[n].inverse = 1;
 416             sweep->spans[n].coverage = 0;
 417         }
 418     }
 419 }
 420
 421 static inline void
 422 sweep_line_delete (sweep_line_t *sweep,
 423                              rectangle_t        *rectangle)
 424 {
 425     if (sweep->insert_cursor == rectangle)
 426         sweep->insert_cursor = rectangle->next;
 427
 428     rectangle->prev->next = rectangle->next;
 429     rectangle->next->prev = rectangle->prev;
 430
 431     pqueue_pop (&sweep->stop);
 432 }
 433
 434 static inline void
 435 sweep_line_insert (sweep_line_t *sweep,
 436                    rectangle_t  *rectangle)
 437 {
 438     rectangle_t *pos;
 439
 440     pos = sweep->insert_cursor;
 441     if (pos->left != rectangle->left) {
 442         if (pos->left > rectangle->left) {
 443             do {
 444                 UNROLL3({
 445                     if (pos->prev->left < rectangle->left)
 446                         break;
 447                     pos = pos->prev;
 448                 })
 449             } while (TRUE);
 450         } else {
 451             do {
 452                 UNROLL3({
 453                     pos = pos->next;
 454                     if (pos->left >= rectangle->left)
 455                         break;
 456                 });
 457             } while (TRUE);
 458         }
 459     }
 460
 461     pos->prev->next = rectangle;
 462     rectangle->prev = pos->prev;
 463     rectangle->next = pos;
 464     pos->prev = rectangle;
 465     sweep->insert_cursor = rectangle;
 466
 467     pqueue_push (sweep, rectangle);
 468 }
 469
 470 static void
 471 render_rows (sweep_line_t *sweep_line,
 472              cairo_span_renderer_t *renderer,
 473              int height)
 474 {
 475     cairo_status_t status;
 476
 477     _active_edges_to_spans (sweep_line);
 478
 479     status = renderer->render_rows (renderer,
 480                                     sweep_line->current_y, height,
 481                                     sweep_line->spans,
 482                                     sweep_line->num_spans);
 483     if (unlikely (status))
 484         longjmp (sweep_line->jmpbuf, status);
 485 }
 486
 487 static cairo_status_t
 488 generate (cairo_rectangular_scan_converter_t *self,
 489           cairo_span_renderer_t *renderer,
 490           rectangle_t **rectangles)
 491 {
 492     sweep_line_t sweep_line;
 493     rectangle_t *start, *stop;
 494     cairo_status_t status;
 495
 496     sweep_line_init (&sweep_line);
 497     sweep_line.xmin = _cairo_fixed_integer_part (self->extents.p1.x);
 498     sweep_line.xmax = _cairo_fixed_integer_part (self->extents.p2.x);
 499     sweep_line.start = rectangles;
 500     if ((status = setjmp (sweep_line.jmpbuf)))
 501         goto out;
 502
 503     sweep_line.current_y = _cairo_fixed_integer_part (self->extents.p1.y);
 504     start = *sweep_line.start++;
 505     do {
 506         if (start->top_y != sweep_line.current_y) {
 507             render_rows (&sweep_line, renderer,
 508                          start->top_y - sweep_line.current_y);
 509             sweep_line.current_y = start->top_y;
 510         }
 511
 512         do {
 513             sweep_line_insert (&sweep_line, start);
 514             start = *sweep_line.start++;
 515             if (start == NULL)
 516                 goto end;
 517             if (start->top_y != sweep_line.current_y)
 518                 break;
 519         } while (TRUE);
 520
 521         render_rows (&sweep_line, renderer, 1);
 522
 523         stop = peek_stop (&sweep_line);
 524         while (stop->bottom_y == sweep_line.current_y) {
 525             sweep_line_delete (&sweep_line, stop);
 526             stop = peek_stop (&sweep_line);
 527             if (stop == NULL)
 528                 break;
 529         }
 530
 531         sweep_line.current_y++;
 532
 533         while (stop != NULL && stop->bottom_y < start->top_y) {
 534             if (stop->bottom_y != sweep_line.current_y) {
 535                 render_rows (&sweep_line, renderer,
 536                              stop->bottom_y - sweep_line.current_y);
 537                 sweep_line.current_y = stop->bottom_y;
 538             }
 539
 540             render_rows (&sweep_line, renderer, 1);
 541
 542             do {
 543                 sweep_line_delete (&sweep_line, stop);
 544                 stop = peek_stop (&sweep_line);
 545             } while (stop != NULL && stop->bottom_y == sweep_line.current_y);
 546
 547             sweep_line.current_y++;
 548         }
 549     } while (TRUE);
 550
 551   end:
 552     render_rows (&sweep_line, renderer, 1);
 553
 554     stop = peek_stop (&sweep_line);
 555     while (stop->bottom_y == sweep_line.current_y) {
 556         sweep_line_delete (&sweep_line, stop);
 557         stop = peek_stop (&sweep_line);
 558         if (stop == NULL)
 559             goto out;
 560     }
 561
 562     while (++sweep_line.current_y < _cairo_fixed_integer_part (self->extents.p2.y)) {
 563         if (stop->bottom_y != sweep_line.current_y) {
 564             render_rows (&sweep_line, renderer,
 565                          stop->bottom_y - sweep_line.current_y);
 566             sweep_line.current_y = stop->bottom_y;
 567         }
 568
 569         render_rows (&sweep_line, renderer, 1);
 570
 571         do {
 572             sweep_line_delete (&sweep_line, stop);
 573             stop = peek_stop (&sweep_line);
 574             if (stop == NULL)
 575                 goto out;
 576         } while (stop->bottom_y == sweep_line.current_y);
 577
 578     }
 579
 580   out:
 581     sweep_line_fini (&sweep_line);
 582
 583     return status;
 584 }
 585 static void generate_row(cairo_span_renderer_t *renderer,
 586                          const rectangle_t *r,
 587                          int y, int h,
 588                          uint16_t coverage)
 589 {
 590     cairo_half_open_span_t spans[4];
 591     unsigned int num_spans = 0;
 592     int x1 = _cairo_fixed_integer_part (r->left);
 593     int x2 = _cairo_fixed_integer_part (r->right);
 594     if (x2 > x1) {
 595         if (! _cairo_fixed_is_integer (r->left)) {
 596             spans[num_spans].x = x1;
 597             spans[num_spans].coverage =
 598                 coverage * (256 - _cairo_fixed_fractional_part (r->left)) >> 8;
 599             num_spans++;
 600             x1++;
 601         }
 602
 603         if (x2 > x1) {
 604             spans[num_spans].x = x1;
 605             spans[num_spans].coverage = coverage - (coverage >> 8);
 606             num_spans++;
 607         }
 608
 609         if (! _cairo_fixed_is_integer (r->right)) {
 610             spans[num_spans].x = x2++;
 611             spans[num_spans].coverage =
 612                 coverage * _cairo_fixed_fractional_part (r->right) >> 8;
 613             num_spans++;
 614         }
 615     } else {
 616         spans[num_spans].x = x2++;
 617         spans[num_spans].coverage = coverage * (r->right - r->left) >> 8;
 618         num_spans++;
 619     }
 620
 621     spans[num_spans].x = x2;
 622     spans[num_spans].coverage = 0;
 623     num_spans++;
 624
 625     renderer->render_rows (renderer, y, h, spans, num_spans);
 626 }
 627
 628 static cairo_status_t
 629 generate_box (cairo_rectangular_scan_converter_t *self,
 630               cairo_span_renderer_t     *renderer)
 631 {
 632     const rectangle_t *r = self->chunks.base;
 633     int y1 = _cairo_fixed_integer_part (r->top);
 634     int y2 = _cairo_fixed_integer_part (r->bottom);
 635     if (y2 > y1) {
 636         if (! _cairo_fixed_is_integer (r->top)) {
 637             generate_row(renderer, r, y1, 1,
 638                          256 - _cairo_fixed_fractional_part (r->top));
 639             y1++;
 640         }
 641
 642         if (y2 > y1)
 643             generate_row(renderer, r, y1, y2-y1, 256);
 644
 645         if (! _cairo_fixed_is_integer (r->bottom))
 646             generate_row(renderer, r, y2, 1,
 647                          _cairo_fixed_fractional_part (r->bottom));
 648     } else
 649         generate_row(renderer, r, y1, 1, r->bottom - r->top);
 650
 651     return CAIRO_STATUS_SUCCESS;
 652 }
 653
 654 static cairo_status_t
 655 _cairo_rectangular_scan_converter_generate (void                        *converter,
 656                                             cairo_span_renderer_t       *renderer)
 657 {
 658     cairo_rectangular_scan_converter_t *self = converter;
 659     rectangle_t *rectangles_stack[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *)];
 660     rectangle_t **rectangles;
 661     struct _cairo_rectangular_scan_converter_chunk *chunk;
 662     cairo_status_t status;
 663     int i, j;
 664
 665     if (unlikely (self->num_rectangles == 0)) {
 666         return renderer->render_rows (renderer,
 667                                       _cairo_fixed_integer_part (self->extents.p1.y),
 668                                       _cairo_fixed_integer_part (self->extents.p2.y - self->extents.p1.y),
 669                                       NULL, 0);
 670     }
 671
 672     if (self->num_rectangles == 1)
 673         return generate_box (self, renderer);
 674
 675     rectangles = rectangles_stack;
 676     if (unlikely (self->num_rectangles >= ARRAY_LENGTH (rectangles_stack))) {
 677         rectangles = _cairo_malloc_ab (self->num_rectangles + 1,
 678                                        sizeof (rectangle_t *));
 679         if (unlikely (rectangles == NULL))
 680             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 681     }
 682
 683     j = 0;
 684     for (chunk = &self->chunks; chunk != NULL; chunk = chunk->next) {
 685         rectangle_t *rectangle;
 686
 687         rectangle = chunk->base;
 688         for (i = 0; i < chunk->count; i++)
 689             rectangles[j++] = &rectangle[i];
 690     }
 691     rectangle_sort (rectangles, j);
 692     rectangles[j] = NULL;
 693
 694     status = generate (self, renderer, rectangles);
 695
 696     if (rectangles != rectangles_stack)
 697         free (rectangles);
 698
 699     return status;
 700 }
 701
 702 static rectangle_t *
 703 _allocate_rectangle (cairo_rectangular_scan_converter_t *self)
 704 {
 705     rectangle_t *rectangle;
 706     struct _cairo_rectangular_scan_converter_chunk *chunk;
 707
 708     chunk = self->tail;
 709     if (chunk->count == chunk->size) {
 710         int size;
 711
 712         size = chunk->size * 2;
 713         chunk->next = _cairo_malloc_ab_plus_c (size,
 714                                                sizeof (rectangle_t),
 715                                                sizeof (struct _cairo_rectangular_scan_converter_chunk));
 716
 717         if (unlikely (chunk->next == NULL))
 718             return NULL;
 719
 720         chunk = chunk->next;
 721         chunk->next = NULL;
 722         chunk->count = 0;
 723         chunk->size = size;
 724         chunk->base = chunk + 1;
 725         self->tail = chunk;
 726     }
 727
 728     rectangle = chunk->base;
 729     return rectangle + chunk->count++;
 730 }
 731
 732 cairo_status_t
 733 _cairo_rectangular_scan_converter_add_box (cairo_rectangular_scan_converter_t *self,
 734                                            const cairo_box_t *box,
 735                                            int dir)
 736 {
 737     rectangle_t *rectangle;
 738
 739     rectangle = _allocate_rectangle (self);
 740     if (unlikely (rectangle == NULL))
 741         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 742
 743     rectangle->dir = dir;
 744     rectangle->left  = MAX (box->p1.x, self->extents.p1.x);
 745     rectangle->right = MIN (box->p2.x, self->extents.p2.x);
 746     if (unlikely (rectangle->right <= rectangle->left)) {
 747         self->tail->count--;
 748         return CAIRO_STATUS_SUCCESS;
 749     }
 750
 751     rectangle->top = MAX (box->p1.y, self->extents.p1.y);
 752     rectangle->top_y  = _cairo_fixed_integer_floor (rectangle->top);
 753     rectangle->bottom = MIN (box->p2.y, self->extents.p2.y);
 754     rectangle->bottom_y = _cairo_fixed_integer_floor (rectangle->bottom);
 755     if (likely (rectangle->bottom > rectangle->top))
 756         self->num_rectangles++;
 757     else
 758         self->tail->count--;
 759
 760     return CAIRO_STATUS_SUCCESS;
 761 }
 762
 763 static void
 764 _cairo_rectangular_scan_converter_destroy (void *converter)
 765 {
 766     cairo_rectangular_scan_converter_t *self = converter;
 767     struct _cairo_rectangular_scan_converter_chunk *chunk, *next;
 768
 769     for (chunk = self->chunks.next; chunk != NULL; chunk = next) {
 770         next = chunk->next;
 771         free (chunk);
 772     }
 773 }
 774
 775 void
 776 _cairo_rectangular_scan_converter_init (cairo_rectangular_scan_converter_t *self,
 777                                         const cairo_rectangle_int_t *extents)
 778 {
 779     self->base.destroy = _cairo_rectangular_scan_converter_destroy;
 780     self->base.generate = _cairo_rectangular_scan_converter_generate;
 781
 782     _cairo_box_from_rectangle (&self->extents, extents);
 783
 784     self->chunks.base = self->buf;
 785     self->chunks.next = NULL;
 786     self->chunks.count = 0;
 787     self->chunks.size = sizeof (self->buf) / sizeof (rectangle_t);
 788     self->tail = &self->chunks;
 789
 790     self->num_rectangles = 0;
 791 }