1#include "mupdf/fitz.h"
2#include "draw-imp.h"
3
4#include <assert.h>
5#include <limits.h>
6#include <math.h>
7#include <stdlib.h>
8#include <string.h>
9
10/*
11 * Global Edge List -- list of straight path segments for scan conversion
12 *
13 * Stepping along the edges is with Bresenham's line algorithm.
14 *
15 * See Mike Abrash -- Graphics Programming Black Book (notably chapter 40)
16 */
17
18typedef struct fz_edge_s
19{
20 int x, e, h, y;
21 int adj_up, adj_down;
22 int xmove;
23 int xdir, ydir; /* -1 or +1 */
24} fz_edge;
25
26typedef struct fz_gel_s
27{
28 fz_rasterizer super;
29 int cap, len;
30 fz_edge *edges;
31 int acap, alen;
32 fz_edge **active;
33 int bcap;
34 unsigned char *alphas;
35 int *deltas;
36} fz_gel;
37
38static int
39fz_reset_gel(fz_context *ctx, fz_rasterizer *rast)
40{
41 fz_gel *gel = (fz_gel *)rast;
42
43 gel->len = 0;
44 gel->alen = 0;
45
46 return 0;
47}
48
49static void
50fz_drop_gel(fz_context *ctx, fz_rasterizer *rast)
51{
52 fz_gel *gel = (fz_gel *)rast;
53 if (gel == NULL)
54 return;
55 fz_free(ctx, gel->active);
56 fz_free(ctx, gel->edges);
57 fz_free(ctx, gel->alphas);
58 fz_free(ctx, gel->deltas);
59 fz_free(ctx, gel);
60}
61
62enum { INSIDE, OUTSIDE, LEAVE, ENTER };
63
64#define clip_lerp_y(v,m,x0,y0,x1,y1,t) clip_lerp_x(v,m,y0,x0,y1,x1,t)
65
66static int
67clip_lerp_x(int val, int m, int x0, int y0, int x1, int y1, int *out)
68{
69 int v0out = m ? x0 > val : x0 < val;
70 int v1out = m ? x1 > val : x1 < val;
71
72 if (v0out + v1out == 0)
73 return INSIDE;
74
75 if (v0out + v1out == 2)
76 return OUTSIDE;
77
78 if (v1out)
79 {
80 *out = y0 + (int)(((float)(y1 - y0)) * (val - x0) / (x1 - x0));
81 return LEAVE;
82 }
83
84 else
85 {
86 *out = y1 + (int)(((float)(y0 - y1)) * (val - x1) / (x0 - x1));
87 return ENTER;
88 }
89}
90
91static void
92fz_insert_gel_raw(fz_context *ctx, fz_rasterizer *ras, int x0, int y0, int x1, int y1)
93{
94 fz_gel *gel = (fz_gel *)ras;
95 fz_edge *edge;
96 int dx, dy;
97 int winding;
98 int width;
99 int tmp;
100
101 if (y0 == y1)
102 return;
103
104 if (y0 > y1) {
105 winding = -1;
106 tmp = x0; x0 = x1; x1 = tmp;
107 tmp = y0; y0 = y1; y1 = tmp;
108 }
109 else
110 winding = 1;
111
112 if (x0 < gel->super.bbox.x0) gel->super.bbox.x0 = x0;
113 if (x0 > gel->super.bbox.x1) gel->super.bbox.x1 = x0;
114 if (x1 < gel->super.bbox.x0) gel->super.bbox.x0 = x1;
115 if (x1 > gel->super.bbox.x1) gel->super.bbox.x1 = x1;
116
117 if (y0 < gel->super.bbox.y0) gel->super.bbox.y0 = y0;
118 if (y1 > gel->super.bbox.y1) gel->super.bbox.y1 = y1;
119
120 if (gel->len + 1 == gel->cap) {
121 int new_cap = gel->cap * 2;
122 gel->edges = fz_realloc_array(ctx, gel->edges, new_cap, fz_edge);
123 gel->cap = new_cap;
124 }
125
126 edge = &gel->edges[gel->len++];
127
128 dy = y1 - y0;
129 dx = x1 - x0;
130 width = fz_absi(dx);
131
132 edge->xdir = dx > 0 ? 1 : -1;
133 edge->ydir = winding;
134 edge->x = x0;
135 edge->y = y0;
136 edge->h = dy;
137 edge->adj_down = dy;
138
139 /* initial error term going l->r and r->l */
140 if (dx >= 0)
141 edge->e = 0;
142 else
143 edge->e = -dy + 1;
144
145 /* y-major edge */
146 if (dy >= width) {
147 edge->xmove = 0;
148 edge->adj_up = width;
149 }
150
151 /* x-major edge */
152 else {
153 edge->xmove = (width / dy) * edge->xdir;
154 edge->adj_up = width % dy;
155 }
156}
157
158static void
159fz_insert_gel(fz_context *ctx, fz_rasterizer *ras, float fx0, float fy0, float fx1, float fy1, int rev)
160{
161 int x0, y0, x1, y1;
162 int d, v;
163 const int hscale = fz_rasterizer_aa_hscale(ras);
164 const int vscale = fz_rasterizer_aa_vscale(ras);
165
166 fx0 = floorf(fx0 * hscale);
167 fx1 = floorf(fx1 * hscale);
168 fy0 = floorf(fy0 * vscale);
169 fy1 = floorf(fy1 * vscale);
170
171 /* Call fz_clamp so that clamping is done in the float domain, THEN
172 * cast down to an int. Calling fz_clampi causes problems due to the
173 * implicit cast down from float to int of the first argument
174 * over/underflowing and flipping sign at extreme values. */
175 x0 = (int)fz_clamp(fx0, BBOX_MIN * hscale, BBOX_MAX * hscale);
176 y0 = (int)fz_clamp(fy0, BBOX_MIN * vscale, BBOX_MAX * vscale);
177 x1 = (int)fz_clamp(fx1, BBOX_MIN * hscale, BBOX_MAX * hscale);
178 y1 = (int)fz_clamp(fy1, BBOX_MIN * vscale, BBOX_MAX * vscale);
179
180 d = clip_lerp_y(ras->clip.y0, 0, x0, y0, x1, y1, &v);
181 if (d == OUTSIDE) return;
182 if (d == LEAVE) { y1 = ras->clip.y0; x1 = v; }
183 if (d == ENTER) { y0 = ras->clip.y0; x0 = v; }
184
185 d = clip_lerp_y(ras->clip.y1, 1, x0, y0, x1, y1, &v);
186 if (d == OUTSIDE) return;
187 if (d == LEAVE) { y1 = ras->clip.y1; x1 = v; }
188 if (d == ENTER) { y0 = ras->clip.y1; x0 = v; }
189
190 d = clip_lerp_x(ras->clip.x0, 0, x0, y0, x1, y1, &v);
191 if (d == OUTSIDE) {
192 x0 = x1 = ras->clip.x0;
193 }
194 if (d == LEAVE) {
195 fz_insert_gel_raw(ctx, ras, ras->clip.x0, v, ras->clip.x0, y1);
196 x1 = ras->clip.x0;
197 y1 = v;
198 }
199 if (d == ENTER) {
200 fz_insert_gel_raw(ctx, ras, ras->clip.x0, y0, ras->clip.x0, v);
201 x0 = ras->clip.x0;
202 y0 = v;
203 }
204
205 d = clip_lerp_x(ras->clip.x1, 1, x0, y0, x1, y1, &v);
206 if (d == OUTSIDE) {
207 x0 = x1 = ras->clip.x1;
208 }
209 if (d == LEAVE) {
210 fz_insert_gel_raw(ctx, ras, ras->clip.x1, v, ras->clip.x1, y1);
211 x1 = ras->clip.x1;
212 y1 = v;
213 }
214 if (d == ENTER) {
215 fz_insert_gel_raw(ctx, ras, ras->clip.x1, y0, ras->clip.x1, v);
216 x0 = ras->clip.x1;
217 y0 = v;
218 }
219
220 fz_insert_gel_raw(ctx, ras, x0, y0, x1, y1);
221}
222
223static void
224fz_insert_gel_rect(fz_context *ctx, fz_rasterizer *ras, float fx0, float fy0, float fx1, float fy1)
225{
226 int x0, y0, x1, y1;
227 const int hscale = fz_rasterizer_aa_hscale(ras);
228 const int vscale = fz_rasterizer_aa_vscale(ras);
229
230 if (fx0 <= fx1)
231 {
232 fx0 = floorf(fx0 * hscale);
233 fx1 = ceilf(fx1 * hscale);
234 }
235 else
236 {
237 fx0 = ceilf(fx0 * hscale);
238 fx1 = floorf(fx1 * hscale);
239 }
240 if (fy0 <= fy1)
241 {
242 fy0 = floorf(fy0 * vscale);
243 fy1 = ceilf(fy1 * vscale);
244 }
245 else
246 {
247 fy0 = ceilf(fy0 * vscale);
248 fy1 = floorf(fy1 * vscale);
249 }
250
251 fx0 = fz_clamp(fx0, ras->clip.x0, ras->clip.x1);
252 fx1 = fz_clamp(fx1, ras->clip.x0, ras->clip.x1);
253 fy0 = fz_clamp(fy0, ras->clip.y0, ras->clip.y1);
254 fy1 = fz_clamp(fy1, ras->clip.y0, ras->clip.y1);
255
256 /* Call fz_clamp so that clamping is done in the float domain, THEN
257 * cast down to an int. Calling fz_clampi causes problems due to the
258 * implicit cast down from float to int of the first argument
259 * over/underflowing and flipping sign at extreme values. */
260 x0 = (int)fz_clamp(fx0, BBOX_MIN * hscale, BBOX_MAX * hscale);
261 y0 = (int)fz_clamp(fy0, BBOX_MIN * vscale, BBOX_MAX * vscale);
262 x1 = (int)fz_clamp(fx1, BBOX_MIN * hscale, BBOX_MAX * hscale);
263 y1 = (int)fz_clamp(fy1, BBOX_MIN * vscale, BBOX_MAX * vscale);
264
265 fz_insert_gel_raw(ctx, ras, x1, y0, x1, y1);
266 fz_insert_gel_raw(ctx, ras, x0, y1, x0, y0);
267}
268
269static int
270cmpedge(const void *va, const void *vb)
271{
272 const fz_edge *a = va;
273 const fz_edge *b = vb;
274 return a->y - b->y;
275}
276
277static void
278sort_gel(fz_context *ctx, fz_gel *gel)
279{
280 fz_edge *a = gel->edges;
281 int n = gel->len;
282 int h, i, k;
283 fz_edge t;
284
285 /* quick sort for long lists */
286 if (n > 10000)
287 {
288 qsort(a, n, sizeof *a, cmpedge);
289 return;
290 }
291
292 /* shell sort for short lists */
293 h = 1;
294 if (n < 14) {
295 h = 1;
296 }
297 else {
298 while (h < n)
299 h = 3 * h + 1;
300 h /= 3;
301 h /= 3;
302 }
303
304 while (h > 0)
305 {
306 for (i = 0; i < n; i++) {
307 t = a[i];
308 k = i - h;
309 /* TODO: sort on y major, x minor */
310 while (k >= 0 && a[k].y > t.y) {
311 a[k + h] = a[k];
312 k -= h;
313 }
314 a[k + h] = t;
315 }
316 h /= 3;
317 }
318}
319
320static int
321fz_is_rect_gel(fz_context *ctx, fz_rasterizer *ras)
322{
323 fz_gel *gel = (fz_gel *)ras;
324 /* a rectangular path is converted into two vertical edges of identical height */
325 if (gel->len == 2)
326 {
327 fz_edge *a = gel->edges + 0;
328 fz_edge *b = gel->edges + 1;
329 return a->y == b->y && a->h == b->h &&
330 a->xmove == 0 && a->adj_up == 0 &&
331 b->xmove == 0 && b->adj_up == 0;
332 }
333 return 0;
334}
335
336/*
337 * Active Edge List -- keep track of active edges while sweeping
338 */
339
340static void
341sort_active(fz_edge **a, int n)
342{
343 int h, i, k;
344 fz_edge *t;
345
346 h = 1;
347 if (n < 14) {
348 h = 1;
349 }
350 else {
351 while (h < n)
352 h = 3 * h + 1;
353 h /= 3;
354 h /= 3;
355 }
356
357 while (h > 0)
358 {
359 for (i = 0; i < n; i++) {
360 t = a[i];
361 k = i - h;
362 while (k >= 0 && a[k]->x > t->x) {
363 a[k + h] = a[k];
364 k -= h;
365 }
366 a[k + h] = t;
367 }
368
369 h /= 3;
370 }
371}
372
373static int
374insert_active(fz_context *ctx, fz_gel *gel, int y, int *e_)
375{
376 int h_min = INT_MAX;
377 int e = *e_;
378
379 /* insert edges that start here */
380 if (e < gel->len && gel->edges[e].y == y)
381 {
382 do {
383 if (gel->alen + 1 == gel->acap) {
384 int newcap = gel->acap + 64;
385 fz_edge **newactive = fz_realloc_array(ctx, gel->active, newcap, fz_edge*);
386 gel->active = newactive;
387 gel->acap = newcap;
388 }
389 gel->active[gel->alen++] = &gel->edges[e++];
390 } while (e < gel->len && gel->edges[e].y == y);
391 *e_ = e;
392 }
393
394 if (e < gel->len)
395 h_min = gel->edges[e].y - y;
396
397 for (e=0; e < gel->alen; e++)
398 {
399 if (gel->active[e]->xmove != 0 || gel->active[e]->adj_up != 0)
400 {
401 h_min = 1;
402 break;
403 }
404 if (gel->active[e]->h < h_min)
405 {
406 h_min = gel->active[e]->h;
407 if (h_min == 1)
408 break;
409 }
410 }
411
412 /* shell-sort the edges by increasing x */
413 sort_active(gel->active, gel->alen);
414
415 return h_min;
416}
417
418static void
419advance_active(fz_context *ctx, fz_gel *gel, int inc)
420{
421 fz_edge *edge;
422 int i = 0;
423
424 while (i < gel->alen)
425 {
426 edge = gel->active[i];
427
428 edge->h -= inc;
429
430 /* terminator! */
431 if (edge->h == 0) {
432 gel->active[i] = gel->active[--gel->alen];
433 }
434
435 else {
436 edge->x += edge->xmove;
437 edge->e += edge->adj_up;
438 if (edge->e > 0) {
439 edge->x += edge->xdir;
440 edge->e -= edge->adj_down;
441 }
442 i ++;
443 }
444 }
445}
446
447/*
448 * Anti-aliased scan conversion.
449 */
450
451static inline void
452add_span_aa(fz_context *ctx, fz_gel *gel, int *list, int x0, int x1, int xofs, int h)
453{
454 int x0pix, x0sub;
455 int x1pix, x1sub;
456 const int hscale = fz_rasterizer_aa_hscale(&gel->super);
457
458 if (x0 == x1)
459 return;
460
461 /* x between 0 and width of bbox */
462 x0 -= xofs;
463 x1 -= xofs;
464
465 /* The cast to unsigned below helps the compiler produce faster
466 * code on ARMs as the multiply by reciprocal trick it uses does not
467 * need to correct for signedness. */
468 x0pix = ((unsigned int)x0) / hscale;
469 x0sub = ((unsigned int)x0) % hscale;
470 x1pix = ((unsigned int)x1) / hscale;
471 x1sub = ((unsigned int)x1) % hscale;
472
473 if (x0pix == x1pix)
474 {
475 list[x0pix] += h*(x1sub - x0sub);
476 list[x0pix+1] += h*(x0sub - x1sub);
477 }
478
479 else
480 {
481 list[x0pix] += h*(hscale - x0sub);
482 list[x0pix+1] += h*x0sub;
483 list[x1pix] += h*(x1sub - hscale);
484 list[x1pix+1] += h*-x1sub;
485 }
486}
487
488static inline void
489non_zero_winding_aa(fz_context *ctx, fz_gel *gel, int *list, int xofs, int h)
490{
491 int winding = 0;
492 int x = 0;
493 int i;
494
495 for (i = 0; i < gel->alen; i++)
496 {
497 if (!winding && (winding + gel->active[i]->ydir))
498 x = gel->active[i]->x;
499 if (winding && !(winding + gel->active[i]->ydir))
500 add_span_aa(ctx, gel, list, x, gel->active[i]->x, xofs, h);
501 winding += gel->active[i]->ydir;
502 }
503}
504
505static inline void
506even_odd_aa(fz_context *ctx, fz_gel *gel, int *list, int xofs, int h)
507{
508 int even = 0;
509 int x = 0;
510 int i;
511
512 for (i = 0; i < gel->alen; i++)
513 {
514 if (!even)
515 x = gel->active[i]->x;
516 else
517 add_span_aa(ctx, gel, list, x, gel->active[i]->x, xofs, h);
518 even = !even;
519 }
520}
521
522static inline void
523undelta_aa(fz_context *ctx, unsigned char * FZ_RESTRICT out, int * FZ_RESTRICT in, int n, int scale)
524{
525 int d = 0;
526 (void)scale; /* Avoid warnings in some builds */
527
528 while (n--)
529 {
530 d += *in++;
531 *out++ = AA_SCALE(scale, d);
532 }
533}
534
535static inline void
536blit_aa(fz_pixmap *dst, int x, int y, unsigned char *mp, int w, unsigned char *color, void *fn, fz_overprint *eop)
537{
538 unsigned char *dp;
539 dp = dst->samples + (unsigned int)((y - dst->y) * dst->stride + (x - dst->x) * dst->n);
540 if (color)
541 (*(fz_span_color_painter_t *)fn)(dp, mp, dst->n, w, color, dst->alpha, eop);
542 else
543 (*(fz_span_painter_t *)fn)(dp, dst->alpha, mp, 1, 0, w, 255, eop);
544}
545
546static void
547fz_scan_convert_aa(fz_context *ctx, fz_gel *gel, int eofill, const fz_irect *clip, fz_pixmap *dst, unsigned char *color, void *painter, fz_overprint *eop)
548{
549 unsigned char *alphas;
550 int *deltas;
551 int y, e;
552 int yd, yc;
553 int height, h0, rh;
554 int bcap;
555 const int hscale = fz_rasterizer_aa_hscale(&gel->super);
556 const int vscale = fz_rasterizer_aa_vscale(&gel->super);
557 const int scale = fz_rasterizer_aa_scale(&gel->super);
558
559 int xmin = fz_idiv(gel->super.bbox.x0, hscale);
560 int xmax = fz_idiv_up(gel->super.bbox.x1, hscale);
561
562 int xofs = xmin * hscale;
563
564 int skipx = clip->x0 - xmin;
565 int clipn = clip->x1 - clip->x0;
566
567 if (gel->len == 0)
568 return;
569
570 assert(xmin < xmax);
571 assert(clip->x0 >= xmin);
572 assert(clip->x1 <= xmax);
573
574 bcap = xmax - xmin + 2; /* big enough for both alphas and deltas */
575 if (bcap > gel->bcap)
576 {
577 gel->bcap = bcap;
578 fz_free(ctx, gel->alphas);
579 fz_free(ctx, gel->deltas);
580 gel->alphas = NULL;
581 gel->deltas = NULL;
582 alphas = gel->alphas = fz_malloc_array(ctx, bcap, unsigned char);
583 deltas = gel->deltas = fz_malloc_array(ctx, bcap, int);
584 }
585 alphas = gel->alphas;
586 deltas = gel->deltas;
587
588 memset(deltas, 0, (xmax - xmin + 1) * sizeof(int));
589 gel->alen = 0;
590
591 /* The theory here is that we have a list of the edges (gel) of length
592 * gel->len. We have an initially empty list of 'active' edges (of
593 * length gel->alen). As we increase y, we move any edge that is
594 * active at this point into the active list. We know that any edge
595 * before index 'e' is either active, or has been retired.
596 * Once the length of the active list is 0, and e has reached gel->len
597 * we know we are finished.
598 *
599 * As we move through the list, we group fz_aa_vscale 'sub scanlines'
600 * into single scanlines, and we blit them.
601 */
602
603 e = 0;
604 y = gel->edges[0].y;
605 yd = fz_idiv(y, vscale);
606
607 /* Quickly skip to the start of the clip region */
608 while (yd < clip->y0 && (gel->alen > 0 || e < gel->len))
609 {
610 /* rh = remaining height = number of subscanlines left to be
611 * inserted into the current scanline, which will be plotted
612 * at yd. */
613 rh = (yd+1)*vscale - y;
614
615 /* height = The number of subscanlines with identical edge
616 * positions (i.e. 1 if we have any non vertical edges). */
617 height = insert_active(ctx, gel, y, &e);
618 h0 = height;
619 if (h0 >= rh)
620 {
621 /* We have enough subscanlines to skip to the next
622 * scanline. */
623 h0 -= rh;
624 yd++;
625 }
626 /* Skip any whole scanlines we can */
627 while (yd < clip->y0 && h0 >= vscale)
628 {
629 h0 -= vscale;
630 yd++;
631 }
632 /* If we haven't hit the start of the clip region, then we
633 * have less than a scanline left. */
634 if (yd < clip->y0)
635 {
636 h0 = 0;
637 }
638 height -= h0;
639 advance_active(ctx, gel, height);
640
641 y += height;
642 }
643
644 /* Now do the active lines */
645 while (gel->alen > 0 || e < gel->len)
646 {
647 yc = fz_idiv(y, vscale); /* yc = current scanline */
648 /* rh = remaining height = number of subscanlines left to be
649 * inserted into the current scanline, which will be plotted
650 * at yd. */
651 rh = (yc+1)*vscale - y;
652 if (yc != yd)
653 {
654 undelta_aa(ctx, alphas, deltas, skipx + clipn, scale);
655 blit_aa(dst, xmin + skipx, yd, alphas + skipx, clipn, color, painter, eop);
656 memset(deltas, 0, (skipx + clipn) * sizeof(int));
657 }
658 yd = yc;
659 if (yd >= clip->y1)
660 break;
661
662 /* height = The number of subscanlines with identical edge
663 * positions (i.e. 1 if we have any non vertical edges). */
664 height = insert_active(ctx, gel, y, &e);
665 h0 = height;
666 if (h0 > rh)
667 {
668 if (rh < vscale)
669 {
670 /* We have to finish a scanline off, and we
671 * have more sub scanlines than will fit into
672 * it. */
673 if (eofill)
674 even_odd_aa(ctx, gel, deltas, xofs, rh);
675 else
676 non_zero_winding_aa(ctx, gel, deltas, xofs, rh);
677 undelta_aa(ctx, alphas, deltas, skipx + clipn, scale);
678 blit_aa(dst, xmin + skipx, yd, alphas + skipx, clipn, color, painter, eop);
679 memset(deltas, 0, (skipx + clipn) * sizeof(int));
680 yd++;
681 if (yd >= clip->y1)
682 break;
683 h0 -= rh;
684 }
685 if (h0 > vscale)
686 {
687 /* Calculate the deltas for any completely full
688 * scanlines. */
689 h0 -= vscale;
690 if (eofill)
691 even_odd_aa(ctx, gel, deltas, xofs, vscale);
692 else
693 non_zero_winding_aa(ctx, gel, deltas, xofs, vscale);
694 undelta_aa(ctx, alphas, deltas, skipx + clipn, scale);
695 do
696 {
697 /* Do any successive whole scanlines - no need
698 * to recalculate deltas here. */
699 blit_aa(dst, xmin + skipx, yd, alphas + skipx, clipn, color, painter, eop);
700 yd++;
701 if (yd >= clip->y1)
702 goto clip_ended;
703 h0 -= vscale;
704 }
705 while (h0 > 0);
706 /* If we have exactly one full scanline left
707 * to go, then the deltas/alphas are set up
708 * already. */
709 if (h0 == 0)
710 goto advance;
711 memset(deltas, 0, (skipx + clipn) * sizeof(int));
712 h0 += vscale;
713 }
714 }
715 if (eofill)
716 even_odd_aa(ctx, gel, deltas, xofs, h0);
717 else
718 non_zero_winding_aa(ctx, gel, deltas, xofs, h0);
719advance:
720 advance_active(ctx, gel, height);
721
722 y += height;
723 }
724
725 if (yd < clip->y1)
726 {
727 undelta_aa(ctx, alphas, deltas, skipx + clipn, scale);
728 blit_aa(dst, xmin + skipx, yd, alphas + skipx, clipn, color, painter, eop);
729 }
730clip_ended:
731 ;
732}
733
734/*
735 * Sharp (not anti-aliased) scan conversion
736 */
737
738static inline void
739blit_sharp(int x0, int x1, int y, const fz_irect *clip, fz_pixmap *dst, unsigned char *color, fz_solid_color_painter_t *fn, fz_overprint *eop)
740{
741 unsigned char *dp;
742 int da = dst->alpha;
743 x0 = fz_clampi(x0, dst->x, dst->x + dst->w);
744 x1 = fz_clampi(x1, dst->x, dst->x + dst->w);
745 if (x0 < x1)
746 {
747 dp = dst->samples + (unsigned int)((y - dst->y) * dst->stride + (x0 - dst->x) * dst->n);
748 if (color)
749 (*fn)(dp, dst->n, x1 - x0, color, da, eop);
750 else
751 memset(dp, 255, x1-x0);
752 }
753}
754
755static inline void
756non_zero_winding_sharp(fz_context *ctx, fz_gel *gel, int y, const fz_irect *clip, fz_pixmap *dst, unsigned char *color, fz_solid_color_painter_t *fn, fz_overprint *eop)
757{
758 int winding = 0;
759 int x = 0;
760 int i;
761 for (i = 0; i < gel->alen; i++)
762 {
763 if (!winding && (winding + gel->active[i]->ydir))
764 x = gel->active[i]->x;
765 if (winding && !(winding + gel->active[i]->ydir))
766 blit_sharp(x, gel->active[i]->x, y, clip, dst, color, fn, eop);
767 winding += gel->active[i]->ydir;
768 }
769}
770
771static inline void
772even_odd_sharp(fz_context *ctx, fz_gel *gel, int y, const fz_irect *clip, fz_pixmap *dst, unsigned char *color, fz_solid_color_painter_t *fn, fz_overprint *eop)
773{
774 int even = 0;
775 int x = 0;
776 int i;
777 for (i = 0; i < gel->alen; i++)
778 {
779 if (!even)
780 x = gel->active[i]->x;
781 else
782 blit_sharp(x, gel->active[i]->x, y, clip, dst, color, fn, eop);
783 even = !even;
784 }
785}
786
787static void
788fz_scan_convert_sharp(fz_context *ctx,
789 fz_gel *gel, int eofill, const fz_irect *clip,
790 fz_pixmap *dst, unsigned char *color, fz_solid_color_painter_t *fn, fz_overprint *eop)
791{
792 int e = 0;
793 int y = gel->edges[0].y;
794 int height;
795
796 gel->alen = 0;
797
798 /* Skip any lines before the clip region */
799 if (y < clip->y0)
800 {
801 while (gel->alen > 0 || e < gel->len)
802 {
803 height = insert_active(ctx, gel, y, &e);
804 y += height;
805 if (y >= clip->y0)
806 {
807 y = clip->y0;
808 break;
809 }
810 }
811 }
812
813 /* Now process as lines within the clip region */
814 while (gel->alen > 0 || e < gel->len)
815 {
816 height = insert_active(ctx, gel, y, &e);
817
818 if (gel->alen == 0)
819 y += height;
820 else
821 {
822 int h;
823 if (height >= clip->y1 - y)
824 height = clip->y1 - y;
825
826 h = height;
827 while (h--)
828 {
829 if (eofill)
830 even_odd_sharp(ctx, gel, y, clip, dst, color, fn, eop);
831 else
832 non_zero_winding_sharp(ctx, gel, y, clip, dst, color, fn, eop);
833 y++;
834 }
835 }
836 if (y >= clip->y1)
837 break;
838
839 advance_active(ctx, gel, height);
840 }
841}
842
843static void
844fz_convert_gel(fz_context *ctx, fz_rasterizer *rast, int eofill, const fz_irect *clip, fz_pixmap *dst, unsigned char *color, fz_overprint *eop)
845{
846 fz_gel *gel = (fz_gel *)rast;
847
848 sort_gel(ctx, gel);
849
850 if (fz_aa_bits > 0)
851 {
852 void *fn;
853 if (color)
854 fn = (void *)fz_get_span_color_painter(dst->n, dst->alpha, color, eop);
855 else
856 fn = (void *)fz_get_span_painter(dst->alpha, 1, 0, 255, eop);
857 assert(fn);
858 if (fn == NULL)
859 return;
860 fz_scan_convert_aa(ctx, gel, eofill, clip, dst, color, fn, eop);
861 }
862 else
863 {
864 fz_solid_color_painter_t *fn = fz_get_solid_color_painter(dst->n, color, dst->alpha, eop);
865 assert(fn);
866 if (fn == NULL)
867 return;
868 fz_scan_convert_sharp(ctx, gel, eofill, clip, dst, color, (fz_solid_color_painter_t *)fn, eop);
869 }
870}
871
872static const fz_rasterizer_fns gel_rasterizer =
873{
874 fz_drop_gel,
875 fz_reset_gel,
876 NULL, /* postindex */
877 fz_insert_gel,
878 fz_insert_gel_rect,
879 NULL, /* gap */
880 fz_convert_gel,
881 fz_is_rect_gel,
882 0 /* Not reusable */
883};
884
885fz_rasterizer *
886fz_new_gel(fz_context *ctx)
887{
888 fz_gel *gel;
889
890 gel = fz_new_derived_rasterizer(ctx, fz_gel, &gel_rasterizer);
891 fz_try(ctx)
892 {
893 gel->edges = NULL;
894 gel->cap = 512;
895 gel->len = 0;
896 gel->edges = fz_malloc_array(ctx, gel->cap, fz_edge);
897
898 gel->acap = 64;
899 gel->alen = 0;
900 gel->active = fz_malloc_array(ctx, gel->acap, fz_edge*);
901 }
902 fz_catch(ctx)
903 {
904 fz_free(ctx, gel->edges);
905 fz_free(ctx, gel);
906 fz_rethrow(ctx);
907 }
908
909 return &gel->super;
910}
911