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

   1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
   2 /*
   3  * Copyright (c) 2011  Intel Corporation
   4  *
   5  * Permission is hereby granted, free of charge, to any person
   6  * obtaining a copy of this software and associated documentation
   7  * files (the "Software"), to deal in the Software without
   8  * restriction, including without limitation the rights to use,
   9  * copy, modify, merge, publish, distribute, sublicense, and/or sell
  10  * copies of the Software, and to permit persons to whom the
  11  * Software is furnished to do so, subject to the following
  12  * conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be
  15  * included in all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  19  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  20  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  21  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  22  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  23  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  24  * OTHER DEALINGS IN THE SOFTWARE.
  25  */
  26 #include "cairoint.h"
  27 #include "cairo-spans-private.h"
  28 #include "cairo-error-private.h"
  29
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <limits.h>
  33
  34 struct quorem {
  35     int32_t quo;
  36     int32_t rem;
  37 };
  38
  39 struct edge {
  40     struct edge *next, *prev;
  41
  42     int32_t height_left;
  43     int32_t dir;
  44     int32_t vertical;
  45
  46     int32_t dy;
  47     struct quorem x;
  48     struct quorem dxdy;
  49 };
  50
  51 /* A collection of sorted and vertically clipped edges of the polygon.
  52  * Edges are moved from the polygon to an active list while scan
  53  * converting. */
  54 struct polygon {
  55     /* The vertical clip extents. */
  56     int32_t ymin, ymax;
  57
  58     int num_edges;
  59     struct edge *edges;
  60
  61     /* Array of edges all starting in the same bucket.  An edge is put
  62      * into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when
  63      * it is added to the polygon. */
  64     struct edge **y_buckets;
  65
  66     struct edge *y_buckets_embedded[64];
  67     struct edge edges_embedded[32];
  68 };
  69
  70 struct mono_scan_converter {
  71     struct polygon polygon[1];
  72
  73     /* Leftmost edge on the current scan line. */
  74     struct edge head, tail;
  75     int is_vertical;
  76
  77     cairo_half_open_span_t *spans;
  78     cairo_half_open_span_t spans_embedded[64];
  79     int num_spans;
  80
  81     /* Clip box. */
  82     int32_t xmin, xmax;
  83     int32_t ymin, ymax;
  84 };
  85
  86 #define I(x) _cairo_fixed_integer_round_down(x)
  87
  88 /* Compute the floored division a/b. Assumes / and % perform symmetric
  89  * division. */
  90 inline static struct quorem
  91 floored_divrem(int a, int b)
  92 {
  93     struct quorem qr;
  94     qr.quo = a/b;
  95     qr.rem = a%b;
  96     if ((a^b)<0 && qr.rem) {
  97         qr.quo -= 1;
  98         qr.rem += b;
  99     }
 100     return qr;
 101 }
 102
 103 /* Compute the floored division (x*a)/b. Assumes / and % perform symmetric
 104  * division. */
 105 static struct quorem
 106 floored_muldivrem(int x, int a, int b)
 107 {
 108     struct quorem qr;
 109     long long xa = (long long)x*a;
 110     qr.quo = xa/b;
 111     qr.rem = xa%b;
 112     if ((xa>=0) != (b>=0) && qr.rem) {
 113         qr.quo -= 1;
 114         qr.rem += b;
 115     }
 116     return qr;
 117 }
 118
 119 static cairo_status_t
 120 polygon_init (struct polygon *polygon, int ymin, int ymax)
 121 {
 122     unsigned h = ymax - ymin + 1;
 123
 124     polygon->y_buckets = polygon->y_buckets_embedded;
 125     if (h > ARRAY_LENGTH (polygon->y_buckets_embedded)) {
 126         polygon->y_buckets = _cairo_malloc_ab (h, sizeof (struct edge *));
 127         if (unlikely (NULL == polygon->y_buckets))
 128             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 129     }
 130     memset (polygon->y_buckets, 0, h * sizeof (struct edge *));
 131     polygon->y_buckets[h-1] = (void *)-1;
 132
 133     polygon->ymin = ymin;
 134     polygon->ymax = ymax;
 135     return CAIRO_STATUS_SUCCESS;
 136 }
 137
 138 static void
 139 polygon_fini (struct polygon *polygon)
 140 {
 141     if (polygon->y_buckets != polygon->y_buckets_embedded)
 142         free (polygon->y_buckets);
 143
 144     if (polygon->edges != polygon->edges_embedded)
 145         free (polygon->edges);
 146 }
 147
 148 static void
 149 _polygon_insert_edge_into_its_y_bucket(struct polygon *polygon,
 150                                        struct edge *e,
 151                                        int y)
 152 {
 153     struct edge **ptail = &polygon->y_buckets[y - polygon->ymin];
 154     if (*ptail)
 155         (*ptail)->prev = e;
 156     e->next = *ptail;
 157     e->prev = NULL;
 158     *ptail = e;
 159 }
 160
 161 inline static void
 162 polygon_add_edge (struct polygon *polygon,
 163                   const cairo_edge_t *edge)
 164 {
 165     struct edge *e;
 166     cairo_fixed_t dx;
 167     cairo_fixed_t dy;
 168     int y, ytop, ybot;
 169     int ymin = polygon->ymin;
 170     int ymax = polygon->ymax;
 171
 172     y = I(edge->top);
 173     ytop = MAX(y, ymin);
 174
 175     y = I(edge->bottom);
 176     ybot = MIN(y, ymax);
 177
 178     if (ybot <= ytop)
 179         return;
 180
 181     e = polygon->edges + polygon->num_edges++;
 182     e->height_left = ybot - ytop;
 183     e->dir = edge->dir;
 184
 185     dx = edge->line.p2.x - edge->line.p1.x;
 186     dy = edge->line.p2.y - edge->line.p1.y;
 187
 188     if (dx == 0) {
 189         e->vertical = TRUE;
 190         e->x.quo = edge->line.p1.x;
 191         e->x.rem = 0;
 192         e->dxdy.quo = 0;
 193         e->dxdy.rem = 0;
 194         e->dy = 0;
 195     } else {
 196         e->vertical = FALSE;
 197         e->dxdy = floored_muldivrem (dx, CAIRO_FIXED_ONE, dy);
 198         e->dy = dy;
 199
 200         e->x = floored_muldivrem (ytop * CAIRO_FIXED_ONE + CAIRO_FIXED_FRAC_MASK/2 - edge->line.p1.y,
 201                                   dx, dy);
 202         e->x.quo += edge->line.p1.x;
 203     }
 204     e->x.rem -= dy;
 205
 206     _polygon_insert_edge_into_its_y_bucket (polygon, e, ytop);
 207 }
 208
 209 static struct edge *
 210 merge_sorted_edges (struct edge *head_a, struct edge *head_b)
 211 {
 212     struct edge *head, **next, *prev;
 213     int32_t x;
 214
 215     prev = head_a->prev;
 216     next = &head;
 217     if (head_a->x.quo <= head_b->x.quo) {
 218         head = head_a;
 219     } else {
 220         head = head_b;
 221         head_b->prev = prev;
 222         goto start_with_b;
 223     }
 224
 225     do {
 226         x = head_b->x.quo;
 227         while (head_a != NULL && head_a->x.quo <= x) {
 228             prev = head_a;
 229             next = &head_a->next;
 230             head_a = head_a->next;
 231         }
 232
 233         head_b->prev = prev;
 234         *next = head_b;
 235         if (head_a == NULL)
 236             return head;
 237
 238 start_with_b:
 239         x = head_a->x.quo;
 240         while (head_b != NULL && head_b->x.quo <= x) {
 241             prev = head_b;
 242             next = &head_b->next;
 243             head_b = head_b->next;
 244         }
 245
 246         head_a->prev = prev;
 247         *next = head_a;
 248         if (head_b == NULL)
 249             return head;
 250     } while (1);
 251 }
 252
 253 static struct edge *
 254 sort_edges (struct edge *list,
 255             unsigned int level,
 256             struct edge **head_out)
 257 {
 258     struct edge *head_other, *remaining;
 259     unsigned int i;
 260
 261     head_other = list->next;
 262
 263     if (head_other == NULL) {
 264         *head_out = list;
 265         return NULL;
 266     }
 267
 268     remaining = head_other->next;
 269     if (list->x.quo <= head_other->x.quo) {
 270         *head_out = list;
 271         head_other->next = NULL;
 272     } else {
 273         *head_out = head_other;
 274         head_other->prev = list->prev;
 275         head_other->next = list;
 276         list->prev = head_other;
 277         list->next = NULL;
 278     }
 279
 280     for (i = 0; i < level && remaining; i++) {
 281         remaining = sort_edges (remaining, i, &head_other);
 282         *head_out = merge_sorted_edges (*head_out, head_other);
 283     }
 284
 285     return remaining;
 286 }
 287
 288 static struct edge *
 289 merge_unsorted_edges (struct edge *head, struct edge *unsorted)
 290 {
 291     sort_edges (unsorted, UINT_MAX, &unsorted);
 292     return merge_sorted_edges (head, unsorted);
 293 }
 294
 295 inline static void
 296 active_list_merge_edges (struct mono_scan_converter *c, struct edge *edges)
 297 {
 298     struct edge *e;
 299
 300     for (e = edges; c->is_vertical && e; e = e->next)
 301         c->is_vertical = e->vertical;
 302
 303     c->head.next = merge_unsorted_edges (c->head.next, edges);
 304 }
 305
 306 inline static void
 307 add_span (struct mono_scan_converter *c, int x1, int x2)
 308 {
 309     int n;
 310
 311     if (x1 < c->xmin)
 312         x1 = c->xmin;
 313     if (x2 > c->xmax)
 314         x2 = c->xmax;
 315     if (x2 <= x1)
 316         return;
 317
 318     n = c->num_spans++;
 319     c->spans[n].x = x1;
 320     c->spans[n].coverage = 255;
 321
 322     n = c->num_spans++;
 323     c->spans[n].x = x2;
 324     c->spans[n].coverage = 0;
 325 }
 326
 327 inline static void
 328 row (struct mono_scan_converter *c, unsigned int mask)
 329 {
 330     struct edge *edge = c->head.next;
 331     int xstart = INT_MIN, prev_x = INT_MIN;
 332     int winding = 0;
 333
 334     c->num_spans = 0;
 335     while (&c->tail != edge) {
 336         struct edge *next = edge->next;
 337         int xend = I(edge->x.quo);
 338
 339         if (--edge->height_left) {
 340             if (!edge->vertical) {
 341                 edge->x.quo += edge->dxdy.quo;
 342                 edge->x.rem += edge->dxdy.rem;
 343                 if (edge->x.rem >= 0) {
 344                     ++edge->x.quo;
 345                     edge->x.rem -= edge->dy;
 346                 }
 347             }
 348
 349             if (edge->x.quo < prev_x) {
 350                 struct edge *pos = edge->prev;
 351                 pos->next = next;
 352                 next->prev = pos;
 353                 do {
 354                     pos = pos->prev;
 355                 } while (edge->x.quo < pos->x.quo);
 356                 pos->next->prev = edge;
 357                 edge->next = pos->next;
 358                 edge->prev = pos;
 359                 pos->next = edge;
 360             } else
 361                 prev_x = edge->x.quo;
 362         } else {
 363             edge->prev->next = next;
 364             next->prev = edge->prev;
 365         }
 366
 367         winding += edge->dir;
 368         if ((winding & mask) == 0) {
 369             if (I(next->x.quo) > xend + 1) {
 370                 add_span (c, xstart, xend);
 371                 xstart = INT_MIN;
 372             }
 373         } else if (xstart == INT_MIN)
 374             xstart = xend;
 375
 376         edge = next;
 377     }
 378 }
 379
 380 inline static void dec (struct edge *e, int h)
 381 {
 382     e->height_left -= h;
 383     if (e->height_left == 0) {
 384         e->prev->next = e->next;
 385         e->next->prev = e->prev;
 386     }
 387 }
 388
 389 static cairo_status_t
 390 _mono_scan_converter_init(struct mono_scan_converter *c,
 391                           int xmin, int ymin,
 392                           int xmax, int ymax)
 393 {
 394     cairo_status_t status;
 395     int max_num_spans;
 396
 397     status = polygon_init (c->polygon, ymin, ymax);
 398     if  (unlikely (status))
 399         return status;
 400
 401     max_num_spans = xmax - xmin + 1;
 402     if (max_num_spans > ARRAY_LENGTH(c->spans_embedded)) {
 403         c->spans = _cairo_malloc_ab (max_num_spans,
 404                                      sizeof (cairo_half_open_span_t));
 405         if (unlikely (c->spans == NULL)) {
 406             polygon_fini (c->polygon);
 407             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 408         }
 409     } else
 410         c->spans = c->spans_embedded;
 411
 412     c->xmin = xmin;
 413     c->xmax = xmax;
 414     c->ymin = ymin;
 415     c->ymax = ymax;
 416
 417     c->head.vertical = 1;
 418     c->head.height_left = INT_MAX;
 419     c->head.x.quo = _cairo_fixed_from_int (_cairo_fixed_integer_part (INT_MIN));
 420     c->head.prev = NULL;
 421     c->head.next = &c->tail;
 422     c->tail.prev = &c->head;
 423     c->tail.next = NULL;
 424     c->tail.x.quo = _cairo_fixed_from_int (_cairo_fixed_integer_part (INT_MAX));
 425     c->tail.height_left = INT_MAX;
 426     c->tail.vertical = 1;
 427
 428     c->is_vertical = 1;
 429     return CAIRO_STATUS_SUCCESS;
 430 }
 431
 432 static void
 433 _mono_scan_converter_fini(struct mono_scan_converter *self)
 434 {
 435     if (self->spans != self->spans_embedded)
 436         free (self->spans);
 437
 438     polygon_fini(self->polygon);
 439 }
 440
 441 static cairo_status_t
 442 mono_scan_converter_allocate_edges(struct mono_scan_converter *c,
 443                                    int num_edges)
 444
 445 {
 446     c->polygon->num_edges = 0;
 447     c->polygon->edges = c->polygon->edges_embedded;
 448     if (num_edges > ARRAY_LENGTH (c->polygon->edges_embedded)) {
 449         c->polygon->edges = _cairo_malloc_ab (num_edges, sizeof (struct edge));
 450         if (unlikely (c->polygon->edges == NULL))
 451             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 452     }
 453
 454     return CAIRO_STATUS_SUCCESS;
 455 }
 456
 457 static void
 458 mono_scan_converter_add_edge (struct mono_scan_converter *c,
 459                               const cairo_edge_t *edge)
 460 {
 461     polygon_add_edge (c->polygon, edge);
 462 }
 463
 464 static void
 465 step_edges (struct mono_scan_converter *c, int count)
 466 {
 467     struct edge *edge;
 468
 469     for (edge = c->head.next; edge != &c->tail; edge = edge->next) {
 470         edge->height_left -= count;
 471         if (! edge->height_left) {
 472             edge->prev->next = edge->next;
 473             edge->next->prev = edge->prev;
 474         }
 475     }
 476 }
 477
 478 static cairo_status_t
 479 mono_scan_converter_render(struct mono_scan_converter *c,
 480                            unsigned int winding_mask,
 481                            cairo_span_renderer_t *renderer)
 482 {
 483     struct polygon *polygon = c->polygon;
 484     int i, j, h = c->ymax - c->ymin;
 485     cairo_status_t status;
 486
 487     for (i = 0; i < h; i = j) {
 488         j = i + 1;
 489
 490         if (polygon->y_buckets[i])
 491             active_list_merge_edges (c, polygon->y_buckets[i]);
 492
 493         if (c->is_vertical) {
 494             int min_height;
 495             struct edge *e;
 496
 497             e = c->head.next;
 498             min_height = e->height_left;
 499             while (e != &c->tail) {
 500                 if (e->height_left < min_height)
 501                     min_height = e->height_left;
 502                 e = e->next;
 503             }
 504
 505             while (--min_height >= 1 && polygon->y_buckets[j] == NULL)
 506                 j++;
 507             if (j != i + 1)
 508                 step_edges (c, j - (i + 1));
 509         }
 510
 511         row (c, winding_mask);
 512         if (c->num_spans) {
 513             status = renderer->render_rows (renderer, c->ymin+i, j-i,
 514                                             c->spans, c->num_spans);
 515             if (unlikely (status))
 516                 return status;
 517         }
 518
 519         /* XXX recompute after dropping edges? */
 520         if (c->head.next == &c->tail)
 521             c->is_vertical = 1;
 522     }
 523
 524     return CAIRO_STATUS_SUCCESS;
 525 }
 526
 527 struct _cairo_mono_scan_converter {
 528     cairo_scan_converter_t base;
 529
 530     struct mono_scan_converter converter[1];
 531     cairo_fill_rule_t fill_rule;
 532 };
 533
 534 typedef struct _cairo_mono_scan_converter cairo_mono_scan_converter_t;
 535
 536 static void
 537 _cairo_mono_scan_converter_destroy (void *converter)
 538 {
 539     cairo_mono_scan_converter_t *self = converter;
 540     _mono_scan_converter_fini (self->converter);
 541     free(self);
 542 }
 543
 544 cairo_status_t
 545 _cairo_mono_scan_converter_add_polygon (void            *converter,
 546                                        const cairo_polygon_t *polygon)
 547 {
 548     cairo_mono_scan_converter_t *self = converter;
 549     cairo_status_t status;
 550     int i;
 551
 552 #if 0
 553     FILE *file = fopen ("polygon.txt", "w");
 554     _cairo_debug_print_polygon (file, polygon);
 555     fclose (file);
 556 #endif
 557
 558     status = mono_scan_converter_allocate_edges (self->converter,
 559                                                  polygon->num_edges);
 560     if (unlikely (status))
 561         return status;
 562
 563     for (i = 0; i < polygon->num_edges; i++)
 564          mono_scan_converter_add_edge (self->converter, &polygon->edges[i]);
 565
 566     return CAIRO_STATUS_SUCCESS;
 567 }
 568
 569 static cairo_status_t
 570 _cairo_mono_scan_converter_generate (void                       *converter,
 571                                     cairo_span_renderer_t       *renderer)
 572 {
 573     cairo_mono_scan_converter_t *self = converter;
 574
 575     return mono_scan_converter_render (self->converter,
 576                                        self->fill_rule == CAIRO_FILL_RULE_WINDING ? ~0 : 1,
 577                                        renderer);
 578 }
 579
 580 cairo_scan_converter_t *
 581 _cairo_mono_scan_converter_create (int                  xmin,
 582                                   int                   ymin,
 583                                   int                   xmax,
 584                                   int                   ymax,
 585                                   cairo_fill_rule_t     fill_rule)
 586 {
 587     cairo_mono_scan_converter_t *self;
 588     cairo_status_t status;
 589
 590     self = malloc (sizeof(struct _cairo_mono_scan_converter));
 591     if (unlikely (self == NULL)) {
 592         status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 593         goto bail_nomem;
 594     }
 595
 596     self->base.destroy = _cairo_mono_scan_converter_destroy;
 597     self->base.generate = _cairo_mono_scan_converter_generate;
 598
 599     status = _mono_scan_converter_init (self->converter,
 600                                         xmin, ymin, xmax, ymax);
 601     if (unlikely (status))
 602         goto bail;
 603
 604     self->fill_rule = fill_rule;
 605
 606     return &self->base;
 607
 608  bail:
 609     self->base.destroy(&self->base);
 610  bail_nomem:
 611     return _cairo_scan_converter_create_in_error (status);
 612 }