Coverage Report

Created: 2025-02-19 06:30

/src/cairo/src/cairo-mono-scan-converter.c
Line
Count
Source (jump to first uncovered line)
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
0
#define I(x) _cairo_fixed_integer_round_down(x)
87
88
/* Compute the floored division (x*a)/b. Assumes / and % perform symmetric
89
 * division. */
90
static struct quorem
91
floored_muldivrem(int x, int a, int b)
92
0
{
93
0
    struct quorem qr;
94
0
    long long xa = (long long)x*a;
95
0
    qr.quo = xa/b;
96
0
    qr.rem = xa%b;
97
0
    if ((xa>=0) != (b>=0) && qr.rem) {
98
0
  qr.quo -= 1;
99
0
  qr.rem += b;
100
0
    }
101
0
    return qr;
102
0
}
103
104
static cairo_status_t
105
polygon_init (struct polygon *polygon, int ymin, int ymax)
106
0
{
107
0
    unsigned h = ymax - ymin + 1;
108
109
0
    polygon->y_buckets = polygon->y_buckets_embedded;
110
0
    if (h > ARRAY_LENGTH (polygon->y_buckets_embedded)) {
111
0
  polygon->y_buckets = _cairo_malloc_ab (h, sizeof (struct edge *));
112
0
  if (unlikely (NULL == polygon->y_buckets))
113
0
      return _cairo_error (CAIRO_STATUS_NO_MEMORY);
114
0
    }
115
0
    memset (polygon->y_buckets, 0, h * sizeof (struct edge *));
116
0
    polygon->y_buckets[h-1] = (void *)-1;
117
118
0
    polygon->ymin = ymin;
119
0
    polygon->ymax = ymax;
120
0
    return CAIRO_STATUS_SUCCESS;
121
0
}
122
123
static void
124
polygon_fini (struct polygon *polygon)
125
0
{
126
0
    if (polygon->y_buckets != polygon->y_buckets_embedded)
127
0
  free (polygon->y_buckets);
128
129
0
    if (polygon->edges != polygon->edges_embedded)
130
0
  free (polygon->edges);
131
0
}
132
133
static void
134
_polygon_insert_edge_into_its_y_bucket(struct polygon *polygon,
135
               struct edge *e,
136
               int y)
137
0
{
138
0
    struct edge **ptail = &polygon->y_buckets[y - polygon->ymin];
139
0
    if (*ptail)
140
0
  (*ptail)->prev = e;
141
0
    e->next = *ptail;
142
0
    e->prev = NULL;
143
0
    *ptail = e;
144
0
}
145
146
inline static void
147
polygon_add_edge (struct polygon *polygon,
148
      const cairo_edge_t *edge)
149
0
{
150
0
    struct edge *e;
151
0
    cairo_fixed_t dx;
152
0
    cairo_fixed_t dy;
153
0
    int y, ytop, ybot;
154
0
    int ymin = polygon->ymin;
155
0
    int ymax = polygon->ymax;
156
157
0
    y = I(edge->top);
158
0
    ytop = MAX(y, ymin);
159
160
0
    y = I(edge->bottom);
161
0
    ybot = MIN(y, ymax);
162
163
0
    if (ybot <= ytop)
164
0
  return;
165
166
0
    e = polygon->edges + polygon->num_edges++;
167
0
    e->height_left = ybot - ytop;
168
0
    e->dir = edge->dir;
169
170
0
    dx = edge->line.p2.x - edge->line.p1.x;
171
0
    dy = edge->line.p2.y - edge->line.p1.y;
172
173
0
    if (dx == 0) {
174
0
  e->vertical = TRUE;
175
0
  e->x.quo = edge->line.p1.x;
176
0
  e->x.rem = 0;
177
0
  e->dxdy.quo = 0;
178
0
  e->dxdy.rem = 0;
179
0
  e->dy = 0;
180
0
    } else {
181
0
  e->vertical = FALSE;
182
0
  e->dxdy = floored_muldivrem (dx, CAIRO_FIXED_ONE, dy);
183
0
  e->dy = dy;
184
185
0
  e->x = floored_muldivrem (ytop * CAIRO_FIXED_ONE + CAIRO_FIXED_FRAC_MASK/2 - edge->line.p1.y,
186
0
          dx, dy);
187
0
  e->x.quo += edge->line.p1.x;
188
0
    }
189
0
    e->x.rem -= dy;
190
191
0
    _polygon_insert_edge_into_its_y_bucket (polygon, e, ytop);
192
0
}
193
194
static struct edge *
195
merge_sorted_edges (struct edge *head_a, struct edge *head_b)
196
0
{
197
0
    struct edge *head, **next, *prev;
198
0
    int32_t x;
199
200
0
    prev = head_a->prev;
201
0
    next = &head;
202
0
    if (head_a->x.quo <= head_b->x.quo) {
203
0
  head = head_a;
204
0
    } else {
205
0
  head = head_b;
206
0
  head_b->prev = prev;
207
0
  goto start_with_b;
208
0
    }
209
210
0
    do {
211
0
  x = head_b->x.quo;
212
0
  while (head_a != NULL && head_a->x.quo <= x) {
213
0
      prev = head_a;
214
0
      next = &head_a->next;
215
0
      head_a = head_a->next;
216
0
  }
217
218
0
  head_b->prev = prev;
219
0
  *next = head_b;
220
0
  if (head_a == NULL)
221
0
      return head;
222
223
0
start_with_b:
224
0
  x = head_a->x.quo;
225
0
  while (head_b != NULL && head_b->x.quo <= x) {
226
0
      prev = head_b;
227
0
      next = &head_b->next;
228
0
      head_b = head_b->next;
229
0
  }
230
231
0
  head_a->prev = prev;
232
0
  *next = head_a;
233
0
  if (head_b == NULL)
234
0
      return head;
235
0
    } while (1);
236
0
}
237
238
static struct edge *
239
sort_edges (struct edge *list,
240
      unsigned int level,
241
      struct edge **head_out)
242
0
{
243
0
    struct edge *head_other, *remaining;
244
0
    unsigned int i;
245
246
0
    head_other = list->next;
247
248
0
    if (head_other == NULL) {
249
0
  *head_out = list;
250
0
  return NULL;
251
0
    }
252
253
0
    remaining = head_other->next;
254
0
    if (list->x.quo <= head_other->x.quo) {
255
0
  *head_out = list;
256
0
  head_other->next = NULL;
257
0
    } else {
258
0
  *head_out = head_other;
259
0
  head_other->prev = list->prev;
260
0
  head_other->next = list;
261
0
  list->prev = head_other;
262
0
  list->next = NULL;
263
0
    }
264
265
0
    for (i = 0; i < level && remaining; i++) {
266
0
  remaining = sort_edges (remaining, i, &head_other);
267
0
  *head_out = merge_sorted_edges (*head_out, head_other);
268
0
    }
269
270
0
    return remaining;
271
0
}
272
273
static struct edge *
274
merge_unsorted_edges (struct edge *head, struct edge *unsorted)
275
0
{
276
0
    sort_edges (unsorted, UINT_MAX, &unsorted);
277
0
    return merge_sorted_edges (head, unsorted);
278
0
}
279
280
inline static void
281
active_list_merge_edges (struct mono_scan_converter *c, struct edge *edges)
282
0
{
283
0
    struct edge *e;
284
285
0
    for (e = edges; c->is_vertical && e; e = e->next)
286
0
  c->is_vertical = e->vertical;
287
288
0
    c->head.next = merge_unsorted_edges (c->head.next, edges);
289
0
}
290
291
inline static void
292
add_span (struct mono_scan_converter *c, int x1, int x2)
293
0
{
294
0
    int n;
295
296
0
    if (x1 < c->xmin)
297
0
  x1 = c->xmin;
298
0
    if (x2 > c->xmax)
299
0
  x2 = c->xmax;
300
0
    if (x2 <= x1)
301
0
  return;
302
303
0
    n = c->num_spans++;
304
0
    c->spans[n].x = x1;
305
0
    c->spans[n].coverage = 255;
306
307
0
    n = c->num_spans++;
308
0
    c->spans[n].x = x2;
309
0
    c->spans[n].coverage = 0;
310
0
}
311
312
inline static void
313
row (struct mono_scan_converter *c, unsigned int mask)
314
0
{
315
0
    struct edge *edge = c->head.next;
316
0
    int xstart = INT_MIN, prev_x = INT_MIN;
317
0
    int winding = 0;
318
319
0
    c->num_spans = 0;
320
0
    while (&c->tail != edge) {
321
0
  struct edge *next = edge->next;
322
0
  int xend = I(edge->x.quo);
323
324
0
  if (--edge->height_left) {
325
0
      if (!edge->vertical) {
326
0
    edge->x.quo += edge->dxdy.quo;
327
0
    edge->x.rem += edge->dxdy.rem;
328
0
    if (edge->x.rem >= 0) {
329
0
        ++edge->x.quo;
330
0
        edge->x.rem -= edge->dy;
331
0
    }
332
0
      }
333
334
0
      if (edge->x.quo < prev_x) {
335
0
    struct edge *pos = edge->prev;
336
0
    pos->next = next;
337
0
    next->prev = pos;
338
0
    do {
339
0
        pos = pos->prev;
340
0
    } while (edge->x.quo < pos->x.quo);
341
0
    pos->next->prev = edge;
342
0
    edge->next = pos->next;
343
0
    edge->prev = pos;
344
0
    pos->next = edge;
345
0
      } else
346
0
    prev_x = edge->x.quo;
347
0
  } else {
348
0
      edge->prev->next = next;
349
0
      next->prev = edge->prev;
350
0
  }
351
352
0
  winding += edge->dir;
353
0
  if ((winding & mask) == 0) {
354
0
      if (I(next->x.quo) > xend + 1) {
355
0
    add_span (c, xstart, xend);
356
0
    xstart = INT_MIN;
357
0
      }
358
0
  } else if (xstart == INT_MIN)
359
0
      xstart = xend;
360
361
0
  edge = next;
362
0
    }
363
0
}
364
365
static cairo_status_t
366
_mono_scan_converter_init(struct mono_scan_converter *c,
367
        int xmin, int ymin,
368
        int xmax, int ymax)
369
0
{
370
0
    cairo_status_t status;
371
0
    int max_num_spans;
372
373
0
    status = polygon_init (c->polygon, ymin, ymax);
374
0
    if  (unlikely (status))
375
0
  return status;
376
377
0
    max_num_spans = xmax - xmin + 1;
378
0
    if (max_num_spans > ARRAY_LENGTH(c->spans_embedded)) {
379
0
  c->spans = _cairo_malloc_ab (max_num_spans,
380
0
             sizeof (cairo_half_open_span_t));
381
0
  if (unlikely (c->spans == NULL)) {
382
0
      return _cairo_error (CAIRO_STATUS_NO_MEMORY);
383
0
  }
384
0
    } else
385
0
  c->spans = c->spans_embedded;
386
387
0
    c->xmin = xmin;
388
0
    c->xmax = xmax;
389
0
    c->ymin = ymin;
390
0
    c->ymax = ymax;
391
392
0
    c->head.vertical = 1;
393
0
    c->head.height_left = INT_MAX;
394
0
    c->head.x.quo = _cairo_fixed_from_int (_cairo_fixed_integer_part (INT_MIN));
395
0
    c->head.prev = NULL;
396
0
    c->head.next = &c->tail;
397
0
    c->tail.prev = &c->head;
398
0
    c->tail.next = NULL;
399
0
    c->tail.x.quo = _cairo_fixed_from_int (_cairo_fixed_integer_part (INT_MAX));
400
0
    c->tail.height_left = INT_MAX;
401
0
    c->tail.vertical = 1;
402
403
0
    c->is_vertical = 1;
404
0
    return CAIRO_STATUS_SUCCESS;
405
0
}
406
407
static void
408
_mono_scan_converter_fini(struct mono_scan_converter *self)
409
0
{
410
0
    if (self->spans != self->spans_embedded)
411
0
  free (self->spans);
412
413
0
    polygon_fini(self->polygon);
414
0
}
415
416
static cairo_status_t
417
mono_scan_converter_allocate_edges(struct mono_scan_converter *c,
418
           int num_edges)
419
420
0
{
421
0
    c->polygon->num_edges = 0;
422
0
    c->polygon->edges = c->polygon->edges_embedded;
423
0
    if (num_edges > ARRAY_LENGTH (c->polygon->edges_embedded)) {
424
0
  c->polygon->edges = _cairo_malloc_ab (num_edges, sizeof (struct edge));
425
0
  if (unlikely (c->polygon->edges == NULL))
426
0
      return _cairo_error (CAIRO_STATUS_NO_MEMORY);
427
0
    }
428
429
0
    return CAIRO_STATUS_SUCCESS;
430
0
}
431
432
static void
433
mono_scan_converter_add_edge (struct mono_scan_converter *c,
434
            const cairo_edge_t *edge)
435
0
{
436
0
    polygon_add_edge (c->polygon, edge);
437
0
}
438
439
static void
440
step_edges (struct mono_scan_converter *c, int count)
441
0
{
442
0
    struct edge *edge;
443
444
0
    for (edge = c->head.next; edge != &c->tail; edge = edge->next) {
445
0
  edge->height_left -= count;
446
0
  if (! edge->height_left) {
447
0
      edge->prev->next = edge->next;
448
0
      edge->next->prev = edge->prev;
449
0
  }
450
0
    }
451
0
}
452
453
static cairo_status_t
454
mono_scan_converter_render(struct mono_scan_converter *c,
455
         unsigned int winding_mask,
456
         cairo_span_renderer_t *renderer)
457
0
{
458
0
    struct polygon *polygon = c->polygon;
459
0
    int i, j, h = c->ymax - c->ymin;
460
0
    cairo_status_t status;
461
462
0
    for (i = 0; i < h; i = j) {
463
0
  j = i + 1;
464
465
0
  if (polygon->y_buckets[i])
466
0
      active_list_merge_edges (c, polygon->y_buckets[i]);
467
468
0
  if (c->is_vertical) {
469
0
      int min_height;
470
0
      struct edge *e;
471
472
0
      e = c->head.next;
473
0
      min_height = e->height_left;
474
0
      while (e != &c->tail) {
475
0
    if (e->height_left < min_height)
476
0
        min_height = e->height_left;
477
0
    e = e->next;
478
0
      }
479
480
0
      while (--min_height >= 1 && polygon->y_buckets[j] == NULL)
481
0
    j++;
482
0
      if (j != i + 1)
483
0
    step_edges (c, j - (i + 1));
484
0
  }
485
486
0
  row (c, winding_mask);
487
0
  if (c->num_spans) {
488
0
      status = renderer->render_rows (renderer, c->ymin+i, j-i,
489
0
              c->spans, c->num_spans);
490
0
      if (unlikely (status))
491
0
    return status;
492
0
  }
493
494
  /* XXX recompute after dropping edges? */
495
0
  if (c->head.next == &c->tail)
496
0
      c->is_vertical = 1;
497
0
    }
498
499
0
    return CAIRO_STATUS_SUCCESS;
500
0
}
501
502
struct _cairo_mono_scan_converter {
503
    cairo_scan_converter_t base;
504
505
    struct mono_scan_converter converter[1];
506
    cairo_fill_rule_t fill_rule;
507
};
508
509
typedef struct _cairo_mono_scan_converter cairo_mono_scan_converter_t;
510
511
static void
512
_cairo_mono_scan_converter_destroy (void *converter)
513
0
{
514
0
    cairo_mono_scan_converter_t *self = converter;
515
0
    _mono_scan_converter_fini (self->converter);
516
0
    free(self);
517
0
}
518
519
cairo_status_t
520
_cairo_mono_scan_converter_add_polygon (void    *converter,
521
               const cairo_polygon_t *polygon)
522
0
{
523
0
    cairo_mono_scan_converter_t *self = converter;
524
0
    cairo_status_t status;
525
0
    int i;
526
527
#if 0
528
    FILE *file = fopen ("polygon.txt", "w");
529
    _cairo_debug_print_polygon (file, polygon);
530
    fclose (file);
531
#endif
532
533
0
    status = mono_scan_converter_allocate_edges (self->converter,
534
0
             polygon->num_edges);
535
0
    if (unlikely (status))
536
0
  return status;
537
538
0
    for (i = 0; i < polygon->num_edges; i++)
539
0
   mono_scan_converter_add_edge (self->converter, &polygon->edges[i]);
540
541
0
    return CAIRO_STATUS_SUCCESS;
542
0
}
543
544
static cairo_status_t
545
_cairo_mono_scan_converter_generate (void     *converter,
546
            cairo_span_renderer_t *renderer)
547
0
{
548
0
    cairo_mono_scan_converter_t *self = converter;
549
550
0
    return mono_scan_converter_render (self->converter,
551
0
               self->fill_rule == CAIRO_FILL_RULE_WINDING ? ~0 : 1,
552
0
               renderer);
553
0
}
554
555
cairo_scan_converter_t *
556
_cairo_mono_scan_converter_create (int      xmin,
557
          int     ymin,
558
          int     xmax,
559
          int     ymax,
560
          cairo_fill_rule_t fill_rule)
561
0
{
562
0
    cairo_mono_scan_converter_t *self;
563
0
    cairo_status_t status;
564
565
0
    self = _cairo_calloc (sizeof(struct _cairo_mono_scan_converter));
566
0
    if (unlikely (self == NULL)) {
567
0
  status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
568
0
  goto bail_nomem;
569
0
    }
570
571
0
    self->base.destroy = _cairo_mono_scan_converter_destroy;
572
0
    self->base.generate = _cairo_mono_scan_converter_generate;
573
574
0
    status = _mono_scan_converter_init (self->converter,
575
0
          xmin, ymin, xmax, ymax);
576
0
    if (unlikely (status))
577
0
  goto bail;
578
579
0
    self->fill_rule = fill_rule;
580
581
0
    return &self->base;
582
583
0
 bail:
584
0
    self->base.destroy(&self->base);
585
0
 bail_nomem:
586
0
    return _cairo_scan_converter_create_in_error (status);
587
0
}