1#include "mupdf/fitz.h"
2#include "draw-imp.h"
3
4#include <assert.h>
5#include <stdlib.h>
6#include <string.h>
7
8#undef DEBUG_SCAN_CONVERTER
9
10/* Define ourselves a 'fixed' type for clarity */
11typedef int fixed;
12
13#define fixed_shift 8
14#define float2fixed(x) ((int)((x)*(1<<fixed_shift)))
15#define fixed2int(x) ((int)((x)>>fixed_shift))
16#define fixed_half (1<<(fixed_shift-1))
17#define fixed_1 (1<<fixed_shift)
18#define int2fixed(x) ((x)<<fixed_shift)
19
20enum
21{
22 DIRN_UNSET = -1,
23 DIRN_UP = 0,
24 DIRN_DOWN = 1
25};
26
27typedef struct
28{
29 fixed left;
30 fixed right;
31 fixed y;
32 signed char d; /* 0 up (or horiz), 1 down, -1 uninited */
33
34 /* unset == 1, iff the values in the above are unset */
35 unsigned char unset;
36 /* can_save == 1, iff we are eligible to 'save'. i.e. if we
37 * have not yet output a cursor, and have not detected
38 * any line segments completely out of range. */
39 unsigned char can_save;
40 unsigned char saved;
41
42 fixed save_left;
43 fixed save_right;
44 int save_iy;
45 int save_d;
46}
47cursor_t;
48
49typedef struct fz_edgebuffer_s
50{
51 fz_rasterizer super;
52 int app;
53 int sorted;
54 int n;
55 int index_cap;
56 int *index;
57 int table_cap;
58 int *table;
59
60 /* cursor section, for use with any part of pixel mode */
61 cursor_t cursor[3];
62} fz_edgebuffer;
63
64static fz_rasterizer_insert_fn fz_insert_edgebuffer_app;
65static fz_rasterizer_insert_fn fz_insert_edgebuffer;
66
67#ifdef DEBUG_SCAN_CONVERTER
68int debugging_scan_converter = 1;
69
70static void
71fz_edgebuffer_print(fz_context *ctx, fz_output *out, fz_edgebuffer * edgebuffer)
72{
73 int i;
74 int height = edgebuffer->super.clip.y1 - edgebuffer->super.clip.y0;
75
76 fz_write_printf(ctx, out, "Edgebuffer %x\n", edgebuffer);
77 fz_write_printf(ctx, out, "xmin=%x xmax=%x base=%x height=%x\n",
78 edgebuffer->super.clip.x0, edgebuffer->super.clip.x1, edgebuffer->super.clip.y0, height);
79 for (i=0; i < height; i++) {
80 int offset = edgebuffer->index[i];
81 int *row = &edgebuffer->table[offset];
82 int count = *row++;
83 assert ((count & 1) == 0);
84 fz_write_printf(ctx, out, "%x @ %x: %d =", i, offset, count);
85 while (count-- > 0) {
86 int v = *row++;
87 fz_write_printf(ctx, out, " %x:%d", v&~1, v&1);
88 }
89 fz_write_printf(ctx, out, "\n");
90 }
91}
92
93static void
94fz_edgebuffer_print_app(fz_context *ctx, fz_output *out, fz_edgebuffer * edgebuffer)
95{
96 int i;
97 int height = edgebuffer->super.clip.y1 - edgebuffer->super.clip.y0;
98
99 fz_write_printf(ctx, out, "Edgebuffer %x\n", edgebuffer);
100 fz_write_printf(ctx, out, "xmin=%x xmax=%x base=%x height=%x\n",
101 edgebuffer->super.clip.x0, edgebuffer->super.clip.x1, edgebuffer->super.clip.y0, height);
102 if (edgebuffer->table == NULL)
103 return;
104 for (i=0; i < height; i++) {
105 int offset = edgebuffer->index[i];
106 int *row = &edgebuffer->table[offset];
107 int count = *row++;
108 int count0 = count;
109 fz_write_printf(ctx, out, "%x @ %x: %d =", i, offset, count);
110 while (count-- > 0) {
111 int l = *row++;
112 int r = *row++;
113 fz_write_printf(ctx, out, " %x:%x", l, r);
114 }
115 assert((count0 & 1) == 0); (void)count0;
116 fz_write_printf(ctx, out, "\n");
117 }
118}
119#endif
120
121static void fz_drop_edgebuffer(fz_context *ctx, fz_rasterizer *r)
122{
123 fz_edgebuffer *eb = (fz_edgebuffer *)r;
124
125 if (eb)
126 {
127 fz_free(ctx, eb->index);
128 fz_free(ctx, eb->table);
129 }
130 fz_free(ctx, eb);
131}
132
133static void index_edgebuffer_insert(fz_context *ctx, fz_rasterizer *ras, float fsx, float fsy, float fex, float fey, int rev)
134{
135 fz_edgebuffer *eb = (fz_edgebuffer *)ras;
136 int iminy, imaxy;
137 int height = eb->super.clip.y1 - eb->super.clip.y0;
138
139 if (fsy == fey)
140 return;
141
142 if (fsx < fex)
143 {
144 if (fsx < eb->super.bbox.x0) eb->super.bbox.x0 = fsx;
145 if (fex > eb->super.bbox.x1) eb->super.bbox.x1 = fex;
146 }
147 else
148 {
149 if (fsx > eb->super.bbox.x1) eb->super.bbox.x1 = fsx;
150 if (fex < eb->super.bbox.x0) eb->super.bbox.x0 = fex;
151 }
152 if (fsy < fey)
153 {
154 if (fsy < eb->super.bbox.y0) eb->super.bbox.y0 = fsy;
155 if (fey > eb->super.bbox.y1) eb->super.bbox.y1 = fey;
156 }
157 else
158 {
159 if (fey < eb->super.bbox.y0) eb->super.bbox.y0 = fey;
160 if (fsy > eb->super.bbox.y1) eb->super.bbox.y1 = fsy;
161 }
162
163 /* To strictly match, this should be:
164 * iminy = int2fixed(float2fixed(fsy))
165 * imaxy = int2fixed(float2fixed(fsx))
166 * but this is faster. It can round differently,
167 * (on some machines at least) hence the iminy--; below.
168 */
169 iminy = (int)fsy;
170 imaxy = (int)fey;
171
172 if (iminy > imaxy)
173 {
174 int t;
175 t = iminy; iminy = imaxy; imaxy = t;
176 }
177 imaxy++;
178 iminy--;
179
180 imaxy -= eb->super.clip.y0;
181 if (imaxy < 0)
182 return;
183 iminy -= eb->super.clip.y0;
184 if (iminy < 0)
185 iminy = 0;
186 else if (iminy > height)
187 return;
188 if (imaxy > height-1)
189 imaxy = height-1;
190#ifdef DEBUG_SCAN_CONVERTER
191 if (debugging_scan_converter)
192 fprintf(stderr, "%x->%x:%d\n", iminy, imaxy, eb->n);
193#endif
194 eb->index[iminy] += eb->n;
195 eb->index[imaxy+1] -= eb->n;
196}
197
198static void fz_postindex_edgebuffer(fz_context *ctx, fz_rasterizer *r)
199{
200 fz_edgebuffer *eb = (fz_edgebuffer *)r;
201 int height = eb->super.clip.y1 - eb->super.clip.y0 + 1;
202 int n = eb->n;
203 int total = 0;
204 int delta = 0;
205 int i;
206
207 eb->super.fns.insert = (eb->app ? fz_insert_edgebuffer_app : fz_insert_edgebuffer);
208
209 for (i = 0; i < height; i++)
210 {
211 delta += eb->index[i];
212 eb->index[i] = total;
213 total += 1 + delta*n;
214 }
215 assert(delta == 0);
216
217 if (eb->table_cap < total)
218 {
219 eb->table = fz_realloc_array(ctx, eb->table, total, int);
220 eb->table_cap = total;
221 }
222
223 for (i = 0; i < height; i++)
224 {
225 eb->table[eb->index[i]] = 0;
226 }
227}
228
229static int fz_reset_edgebuffer(fz_context *ctx, fz_rasterizer *r)
230{
231 fz_edgebuffer *eb = (fz_edgebuffer *)r;
232 int height = eb->super.clip.y1 - eb->super.clip.y0 + 1;
233 int n;
234
235 eb->sorted = 0;
236
237 if (eb->index_cap < height)
238 {
239 eb->index = fz_realloc_array(ctx, eb->index, height, int);
240 eb->index_cap = height;
241 }
242 memset(eb->index, 0, sizeof(int) * height);
243
244 n = 1;
245
246 if (eb->app)
247 {
248 n = 2;
249 eb->cursor[0].saved = 0;
250 eb->cursor[0].unset = 1;
251 eb->cursor[0].can_save = 1;
252 eb->cursor[0].d = DIRN_UNSET;
253 eb->cursor[1].saved = 0;
254 eb->cursor[1].unset = 1;
255 eb->cursor[1].can_save = 1;
256 eb->cursor[1].d = DIRN_UNSET;
257 eb->cursor[2].saved = 0;
258 eb->cursor[2].unset = 1;
259 eb->cursor[2].can_save = 1;
260 eb->cursor[2].d = DIRN_UNSET;
261 }
262
263 eb->n = n;
264
265 eb->super.fns.insert = index_edgebuffer_insert;
266 return 1;
267}
268
269static void mark_line(fz_context *ctx, fz_edgebuffer *eb, fixed sx, fixed sy, fixed ex, fixed ey)
270{
271 int base_y = eb->super.clip.y0;
272 int height = eb->super.clip.y1 - eb->super.clip.y0;
273 int *table = eb->table;
274 int *index = eb->index;
275 int delta;
276 int iy, ih;
277 fixed clip_sy, clip_ey;
278 int dirn = DIRN_UP;
279 int *row;
280
281 if (fixed2int(sy + fixed_half-1) == fixed2int(ey + fixed_half-1))
282 return;
283 if (sy > ey) {
284 int t;
285 t = sy; sy = ey; ey = t;
286 t = sx; sx = ex; ex = t;
287 dirn = DIRN_DOWN;
288 }
289
290 if (fixed2int(sx) < eb->super.bbox.x0)
291 eb->super.bbox.x0 = fixed2int(sx);
292 if (fixed2int(sx + fixed_1 - 1) > eb->super.bbox.x1)
293 eb->super.bbox.x1 = fixed2int(sx + fixed_1 - 1);
294 if (fixed2int(ex) < eb->super.bbox.x0)
295 eb->super.bbox.x0 = fixed2int(ex);
296 if (fixed2int(ex + fixed_1 - 1) > eb->super.bbox.x1)
297 eb->super.bbox.x1 = fixed2int(ex + fixed_1 - 1);
298
299 if (fixed2int(sy) < eb->super.bbox.y0)
300 eb->super.bbox.y0 = fixed2int(sy);
301 if (fixed2int(ey + fixed_1 - 1) > eb->super.bbox.y1)
302 eb->super.bbox.y1 = fixed2int(ey + fixed_1 - 1);
303
304 /* Lines go from sy to ey, closed at the start, open at the end. */
305 /* We clip them to a region to make them closed at both ends. */
306 /* Thus the unset scanline marked (>= sy) is: */
307 clip_sy = ((sy + fixed_half - 1) & ~(fixed_1-1)) | fixed_half;
308 /* The last scanline marked (< ey) is: */
309 clip_ey = ((ey - fixed_half - 1) & ~(fixed_1-1)) | fixed_half;
310 /* Now allow for banding */
311 if (clip_sy < int2fixed(base_y) + fixed_half)
312 clip_sy = int2fixed(base_y) + fixed_half;
313 if (ey <= clip_sy)
314 return;
315 if (clip_ey > int2fixed(base_y + height - 1) + fixed_half)
316 clip_ey = int2fixed(base_y + height - 1) + fixed_half;
317 if (sy > clip_ey)
318 return;
319 delta = clip_sy - sy;
320 if (delta > 0)
321 {
322 int dx = ex - sx;
323 int dy = ey - sy;
324 int advance = (int)(((int64_t)dx * delta + (dy>>1)) / dy);
325 sx += advance;
326 sy += delta;
327 }
328 ex -= sx;
329 ey -= sy;
330 clip_ey -= clip_sy;
331 delta = ey - clip_ey;
332 if (delta > 0)
333 {
334 int advance = (int)(((int64_t)ex * delta + (ey>>1)) / ey);
335 ex -= advance;
336 ey -= delta;
337 }
338 ih = fixed2int(ey);
339 assert(ih >= 0);
340 iy = fixed2int(sy) - base_y;
341#ifdef DEBUG_SCAN_CONVERTER
342 if (debugging_scan_converter)
343 fz_write_printf(ctx, fz_stderr(ctx), " iy=%x ih=%x\n", iy, ih);
344#endif
345 assert(iy >= 0 && iy < height);
346 /* We always cross at least one scanline */
347 row = &table[index[iy]];
348 *row = (*row)+1; /* Increment the count */
349 row[*row] = (sx&~1) | dirn;
350 if (ih == 0)
351 return;
352 if (ex >= 0) {
353 int x_inc, n_inc, f;
354
355 /* We want to change sx by ex in ih steps. So each step, we add
356 * ex/ih to sx. That's x_inc + n_inc/ih.
357 */
358 x_inc = ex/ih;
359 n_inc = ex-(x_inc*ih);
360 f = ih>>1;
361 delta = ih;
362 do {
363 int count;
364 iy++;
365 sx += x_inc;
366 f -= n_inc;
367 if (f < 0) {
368 f += ih;
369 sx++;
370 }
371 assert(iy >= 0 && iy < height);
372 row = &table[index[iy]];
373 count = *row = (*row)+1; /* Increment the count */
374 row[count] = (sx&~1) | dirn;
375 } while (--delta);
376 } else {
377 int x_dec, n_dec, f;
378
379 ex = -ex;
380 /* We want to change sx by ex in ih steps. So each step, we subtract
381 * ex/ih from sx. That's x_dec + n_dec/ih.
382 */
383 x_dec = ex/ih;
384 n_dec = ex-(x_dec*ih);
385 f = ih>>1;
386 delta = ih;
387 do {
388 int count;
389 iy++;
390 sx -= x_dec;
391 f -= n_dec;
392 if (f < 0) {
393 f += ih;
394 sx--;
395 }
396 assert(iy >= 0 && iy < height);
397 row = &table[index[iy]];
398 count = *row = (*row)+1; /* Increment the count */
399 row[count] = (sx&~1) | dirn;
400 } while (--delta);
401 }
402}
403
404static void fz_insert_edgebuffer(fz_context *ctx, fz_rasterizer *ras, float fsx, float fsy, float fex, float fey, int rev)
405{
406 fz_edgebuffer *eb = (fz_edgebuffer *)ras;
407 fixed sx = float2fixed(fsx);
408 fixed sy = float2fixed(fsy);
409 fixed ex = float2fixed(fex);
410 fixed ey = float2fixed(fey);
411
412 mark_line(ctx, eb, sx, sy, ex, ey);
413}
414
415static inline void
416cursor_output(fz_edgebuffer * FZ_RESTRICT eb, int rev, int iy)
417{
418 int *row;
419 int count;
420 int height = eb->super.clip.y1 - eb->super.clip.y0;
421 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
422
423 rev &= 1; /* Edge label 0 is forwards, 1 and 2 are reverse */
424
425 if (iy >= 0 && iy < height) {
426 if (cr->can_save) {
427 /* Save it for later in case we join up */
428 cr->save_left = cr->left;
429 cr->save_right = cr->right;
430 cr->save_iy = iy;
431 cr->save_d = cr->d;
432 cr->saved = 1;
433 } else {
434 /* Enter it into the table */
435 row = &eb->table[eb->index[iy]];
436 if (cr->d == DIRN_UNSET)
437 {
438 /* Move 0 0; line 10 0; line 0 0; */
439 /* FIXME */
440 }
441 else
442 {
443 *row = count = (*row)+1; /* Increment the count */
444#ifdef DEBUG_SCAN_CONVERTER
445 if (debugging_scan_converter)
446 fprintf(stderr, "row: %x: %x->%x %c\n", iy, cr->left, cr->right, (cr->d^rev) == DIRN_UP ? '^' : (cr->d^rev) == DIRN_DOWN ? 'v' : '-');
447#endif
448 assert(count <= (eb->index[iy+1] - eb->index[iy] - 1)/2);
449 row[2 * count - 1] = (cr->left&~1) | (cr->d ^ rev);
450 row[2 * count] = cr->right;
451 }
452 }
453 }
454 cr->can_save = 0;
455}
456
457static inline void
458cursor_output_inrange(fz_edgebuffer * FZ_RESTRICT eb, int rev, int iy)
459{
460 int *row;
461 int count;
462 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
463
464 rev &= 1; /* Edge label 0 is forwards, 1 and 2 are reverse */
465
466 assert(iy >= 0 && iy < eb->super.clip.y1 - eb->super.clip.y0);
467 if (cr->can_save) {
468 /* Save it for later in case we join up */
469 cr->save_left = cr->left;
470 cr->save_right = cr->right;
471 cr->save_iy = iy;
472 cr->save_d = cr->d;
473 cr->saved = 1;
474 } else {
475 /* Enter it into the table */
476 assert(cr->d != DIRN_UNSET);
477
478 row = &eb->table[eb->index[iy]];
479 *row = count = (*row)+1; /* Increment the count */
480#ifdef DEBUG_SCAN_CONVERTER
481 if (debugging_scan_converter)
482 printf("row= %x: %x->%x %c\n", iy, cr->left, cr->right, (cr->d^rev) == DIRN_UP ? '^' : (cr->d^rev) == DIRN_DOWN ? 'v' : '-');
483#endif
484 row[2 * count - 1] = (cr->left&~1) | (cr->d ^ rev);
485 row[2 * count] = cr->right;
486 }
487 cr->can_save = 0;
488}
489
490/* Step the cursor in y, allowing for maybe crossing a scanline */
491static inline void
492cursor_step(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed dy, fixed x)
493{
494 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
495 int new_iy;
496 int base = eb->super.clip.y0;
497 int iy = fixed2int(cr->y) - base;
498
499 cr->y += dy;
500 new_iy = fixed2int(cr->y) - base;
501 if (new_iy != iy) {
502 cursor_output(eb, rev, iy);
503 cr->left = x;
504 cr->right = x;
505 } else {
506 if (x < cr->left)
507 cr->left = x;
508 if (x > cr->right)
509 cr->right = x;
510 }
511}
512
513/* Step the cursor in y, never by enough to cross a scanline. */
514static inline void
515cursor_never_step_vertical(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed dy, fixed x)
516{
517 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
518
519 assert(fixed2int(cr->y+dy) == fixed2int(cr->y));
520
521 cr->y += dy;
522}
523
524/* Step the cursor in y, never by enough to cross a scanline,
525 * knowing that we are moving left, and that the right edge
526 * has already been accounted for. */
527static inline void
528cursor_never_step_left(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed dy, fixed x)
529{
530 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
531
532 assert(fixed2int(cr->y+dy) == fixed2int(cr->y));
533
534 if (x < cr->left)
535 cr->left = x;
536 cr->y += dy;
537}
538
539/* Step the cursor in y, never by enough to cross a scanline,
540 * knowing that we are moving right, and that the left edge
541 * has already been accounted for. */
542static inline void
543cursor_never_step_right(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed dy, fixed x)
544{
545 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
546
547 assert(fixed2int(cr->y+dy) == fixed2int(cr->y));
548
549 if (x > cr->right)
550 cr->right = x;
551 cr->y += dy;
552}
553
554/* Step the cursor in y, always by enough to cross a scanline. */
555static inline void
556cursor_always_step(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed dy, fixed x)
557{
558 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
559 int base = eb->super.clip.y0;
560 int iy = fixed2int(cr->y) - base;
561
562 cursor_output(eb, rev, iy);
563 cr->y += dy;
564 cr->left = x;
565 cr->right = x;
566}
567
568/* Step the cursor in y, always by enough to cross a scanline, as
569 * part of a vertical line, knowing that we are moving from a
570 * position guaranteed to be in the valid y range. */
571static inline void
572cursor_always_step_inrange_vertical(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed dy, fixed x)
573{
574 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
575 int base = eb->super.clip.y0;
576 int iy = fixed2int(cr->y) - base;
577
578 cursor_output(eb, rev, iy);
579 cr->y += dy;
580}
581
582/* Step the cursor in y, always by enough to cross a scanline, as
583 * part of a left moving line, knowing that we are moving from a
584 * position guaranteed to be in the valid y range. */
585static inline void
586cursor_always_inrange_step_left(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed dy, fixed x)
587{
588 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
589 int base = eb->super.clip.y0;
590 int iy = fixed2int(cr->y) - base;
591
592 cr->y += dy;
593 cursor_output_inrange(eb, rev, iy);
594 cr->right = x;
595}
596
597/* Step the cursor in y, always by enough to cross a scanline, as
598 * part of a right moving line, knowing that we are moving from a
599 * position guaranteed to be in the valid y range. */
600static inline void
601cursor_always_inrange_step_right(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed dy, fixed x)
602{
603 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
604 int base = eb->super.clip.y0;
605 int iy = fixed2int(cr->y) - base;
606
607 cr->y += dy;
608 cursor_output_inrange(eb, rev, iy);
609 cr->left = x;
610}
611
612static inline void cursor_init(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed y, fixed x)
613{
614 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
615
616 assert(y >= int2fixed(eb->super.clip.y0) && y <= int2fixed(eb->super.clip.y1));
617
618 cr->y = y;
619 cr->left = x;
620 cr->right = x;
621 cr->d = DIRN_UNSET;
622}
623
624static inline void cursor_left_merge(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed x)
625{
626 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
627
628 if (x < cr->left)
629 cr->left = x;
630}
631
632static inline void cursor_left(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed x)
633{
634 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
635
636 cr->left = x;
637}
638
639static inline void cursor_right_merge(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed x)
640{
641 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
642
643 if (x > cr->right)
644 cr->right = x;
645}
646
647static inline void cursor_right(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed x)
648{
649 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
650
651 cr->right = x;
652}
653
654static inline void cursor_down(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed x)
655{
656 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
657 int base = eb->super.clip.y0;
658
659 if (cr->d == DIRN_UP)
660 {
661 cursor_output(eb, rev, fixed2int(cr->y) - base);
662 cr->left = x;
663 cr->right = x;
664 }
665 cr->d = DIRN_DOWN;
666}
667
668static inline void cursor_up(fz_edgebuffer * FZ_RESTRICT eb, int rev, fixed x)
669{
670 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
671 int base = eb->super.clip.y0;
672
673 if (cr->d == DIRN_DOWN)
674 {
675 cursor_output(eb, rev, fixed2int(cr->y) - base);
676 cr->left = x;
677 cr->right = x;
678 }
679 cr->d = DIRN_UP;
680}
681
682static inline int dirns_match(int d0, int d1)
683{
684 return d0 == d1 || d0 == DIRN_UNSET || d1 == DIRN_UNSET;
685}
686
687static inline int dirn_flip(int d)
688{
689 return d < 0 ? d : d^1;
690}
691
692static inline int dirns_merge(int d0, int d1)
693{
694 if (d0 == DIRN_UNSET)
695 return d1;
696 assert(dirns_match(d0, d1));
697 return d0;
698}
699
700static void
701cursor_flush(fz_edgebuffer * FZ_RESTRICT eb)
702{
703 int base = eb->super.clip.y0;
704 int iy0, iy1, iy2;
705 cursor_t * FZ_RESTRICT cr0 = &eb->cursor[0];
706 cursor_t * FZ_RESTRICT cr1 = &eb->cursor[1];
707 cursor_t * FZ_RESTRICT cr2 = &eb->cursor[2];
708
709 if (cr0->unset)
710 {
711 assert(cr1->unset && cr2->unset);
712 return;
713 }
714
715 iy0 = fixed2int(cr0->y) - base;
716 iy1 = fixed2int(cr1->y) - base;
717 if (!cr2->unset)
718 {
719 assert(!cr1->unset);
720 iy2 = fixed2int(cr2->y) - base;
721 /* Try to merge the end of cursor 0 with the end of cursor 1 */
722 if (iy0 == iy1 && dirns_match(cr0->d, dirn_flip(cr1->d)))
723 {
724 /* Succeeded! Just one to output. */
725 cr0->d = dirns_merge(cr0->d, dirn_flip(cr1->d));
726 if (cr0->left > cr1->left)
727 cr0->left = cr1->left;
728 if (cr0->right < cr1->right)
729 cr0->right = cr1->right;
730 cr1->unset = 1; /* Stop us outputting cursor 1 later */
731 }
732
733 /* Try to merge the end of cursor 2 with the start of cursor 0 */
734 if (cr0->saved)
735 {
736 if (cr0->save_iy == iy2 && dirns_match(cr0->save_d, cr2->d))
737 {
738 cr0->save_d = dirns_merge(cr0->save_d, cr2->d);
739 if (cr0->save_left > cr2->left)
740 cr0->save_left = cr2->left;
741 if (cr0->save_right > cr2->right)
742 cr0->save_right = cr2->right;
743 cr2->unset = 1; /* Stop us outputting cursor 2 later */
744 }
745 }
746 else
747 {
748 /* Maybe cursor 0 never moved from the original pixel */
749 if (iy0 == iy2 && dirns_match(cr0->d, cr2->d))
750 {
751 cr0->d = dirns_merge(cr0->d, cr2->d);
752 if (cr0->left > cr2->left)
753 cr0->left = cr2->left;
754 if (cr0->right > cr2->right)
755 cr0->right = cr2->right;
756 cr2->unset = 1; /* Stop us outputting cursor 2 later */
757 }
758 }
759
760 /* Try to merge the start of cursor 2 with the start of cursor 1 */
761 if (cr1->saved)
762 {
763 if (cr2->saved)
764 {
765 if (cr2->save_iy == cr1->save_iy && dirns_match(cr2->save_d, dirn_flip(cr1->save_d)))
766 {
767 cr2->save_d = dirns_merge(cr2->save_d, dirn_flip(cr1->save_d));
768 if (cr2->save_left > cr1->save_left)
769 cr2->save_left = cr1->save_left;
770 if (cr2->save_right > cr1->save_right)
771 cr2->save_right = cr1->save_right;
772 cr1->saved = 0; /* Don't output cr1->saved again later */
773 }
774 }
775 else if (!cr2->unset)
776 {
777 /* Maybe cursor 2 never moved from the original pixel */
778 if (iy2 == cr1->save_iy && dirns_match(cr2->d, dirn_flip(cr1->save_d)))
779 {
780 cr2->d = dirns_merge(cr2->d, dirn_flip(cr1->save_d));
781 if (cr2->left > cr1->save_left)
782 cr2->left = cr1->save_left;
783 if (cr2->right > cr1->save_right)
784 cr2->right = cr1->save_right;
785 cr1->saved = 0; /* Don't output cr1->saved again later */
786 }
787 }
788 }
789 else if (!cr1->unset)
790 {
791 /* Cursor 1 might not have moved from the original pixel, hence nothing saved */
792 if (cr2->saved)
793 {
794 if (cr2->save_iy == iy1 && dirns_match(cr2->save_d, dirn_flip(cr1->d)))
795 {
796 cr2->save_d = dirns_merge(cr2->save_d, dirn_flip(cr1->d));
797 if (cr2->save_left > cr1->left)
798 cr2->save_left = cr1->left;
799 if (cr2->save_right > cr1->right)
800 cr2->save_right = cr1->right;
801 cr1->unset = 1; /* Stop us outputting cursor 1 later */
802 }
803 }
804 else if (!cr2->unset)
805 {
806 /* Maybe cursor 2 never moved from the original pixel */
807 if (iy2 == iy1 && dirns_match(cr2->d, dirn_flip(cr1->d)))
808 {
809 cr2->d = dirns_merge(cr2->d, dirn_flip(cr1->d));
810 if (cr2->left > cr1->left)
811 cr2->left = cr1->left;
812 if (cr2->right > cr1->right)
813 cr2->right = cr1->right;
814 cr1->unset = 1; /* Stop us outputting cursor 1 later */
815 }
816 }
817 }
818 else
819 {
820 /* Cursor 1 might not have moved from the original pixel, hence nothing saved,
821 * AND we might have merged it with cursor 0 already! */
822 if (cr2->saved)
823 {
824 if (iy0 == cr2->save_iy && dirns_match(cr0->d, cr2->save_d))
825 {
826 cr0->d = dirns_merge(cr0->d, cr2->save_d);
827 if (cr0->left > cr2->save_left)
828 cr0->left = cr2->save_left;
829 if (cr0->right > cr2->save_right)
830 cr0->right = cr2->save_right;
831 cr2->saved = 0; /* Stop us outputting saved cursor 2 later */
832 }
833 }
834 else if (!cr2->unset)
835 {
836 /* Maybe cursor 2 never moved from the original pixel */
837 if (iy0 == iy2 && dirns_match(cr0->d, cr2->d))
838 {
839 cr0->d = dirns_merge(cr0->d, cr2->d);
840 if (cr0->left > cr2->left)
841 cr0->left = cr2->left;
842 if (cr0->right > cr2->right)
843 cr0->right = cr2->right;
844 cr2->unset = 1; /* Stop us outputting cursor 2 later */
845 }
846 }
847 }
848 }
849 else
850 {
851 /* Try to merge the end of cursor 0 with the start of cursor 0 */
852 if (cr0->saved)
853 {
854 if (iy0 == cr0->save_iy && dirns_match(cr0->d, cr0->save_d))
855 {
856 cr0->d = dirns_merge(cr0->d, cr0->save_d);
857 if (cr0->left > cr0->save_left)
858 cr0->left = cr0->save_left;
859 if (cr0->right > cr0->save_right)
860 cr0->right = cr0->save_right;
861 cr0->saved = 0; /* Stop us outputting saved cursor 0 later */
862 }
863 }
864
865 if (!cr1->unset)
866 {
867 /* Try to merge the end of cursor 1 with the start of cursor 1 */
868 if (cr1->saved)
869 {
870 if (iy1 == cr1->save_iy && dirns_match(cr1->d, cr1->save_d))
871 {
872 cr1->d = dirns_merge(cr1->d, cr1->save_d);
873 if (cr1->left > cr1->save_left)
874 cr1->left = cr1->save_left;
875 if (cr1->right > cr1->save_right)
876 cr1->right = cr1->save_right;
877 cr1->saved = 0; /* Stop us outputting saved cursor 1 later */
878 }
879 }
880 }
881 }
882
883 if (!cr0->unset)
884 cursor_output(eb, 0, iy0);
885 if (cr0->saved)
886 {
887 cr0->left = cr0->save_left;
888 cr0->right = cr0->save_right;
889 cr0->d = cr0->save_d;
890 cursor_output(eb, 0, cr0->save_iy);
891 }
892 if (!cr1->unset)
893 cursor_output(eb, 1, iy1);
894 if (cr1->saved)
895 {
896 cr1->left = cr1->save_left;
897 cr1->right = cr1->save_right;
898 cr1->d = cr1->save_d;
899 cursor_output(eb, 1, cr1->save_iy);
900 }
901 if (!cr2->unset)
902 cursor_output(eb, 2, iy2);
903 if (cr2->saved)
904 {
905 cr2->left = cr2->save_left;
906 cr2->right = cr2->save_right;
907 cr2->d = cr2->save_d;
908 cursor_output(eb, 2, cr2->save_iy);
909 }
910}
911
912static void do_mark_line_app(fz_context *ctx, fz_edgebuffer *eb, fixed sx, fixed sy, fixed ex, fixed ey, int rev)
913{
914 int base_y = eb->super.clip.y0;
915 int height = eb->super.clip.y1 - eb->super.clip.y0;
916 int isy, iey;
917 fixed y_steps;
918 fixed save_sy = sy;
919 fixed save_ex = ex;
920 fixed save_ey = ey;
921 int truncated;
922 cursor_t * FZ_RESTRICT cr = &eb->cursor[rev];
923
924 if (cr->unset)
925 cr->y = sy, cr->left = sx, cr->right = sx, cr->unset = 0;
926
927 /* Floating point inaccuracies can cause these not *quite* to be true. */
928 assert(cr->y == sy && cr->left <= sx && cr->right >= sx && cr->d >= DIRN_UNSET && cr->d <= DIRN_DOWN);
929 sy = cr->y;
930 if (cr->left > sx)
931 sx = cr->left;
932 else if (cr->right < sx)
933 sx = cr->right;
934
935 if (sx == ex && sy == ey)
936 return;
937
938 isy = fixed2int(sy) - base_y;
939 iey = fixed2int(ey) - base_y;
940#ifdef DEBUG_SCAN_CONVERTER
941 if (debugging_scan_converter)
942 fz_write_printf(ctx, fz_stderr(ctx), "Marking line (app) from %x,%x to %x,%x (%x,%x) %d\n", sx, sy, ex, ey, isy, iey, rev);
943#endif
944
945 if (isy < iey) {
946 /* Rising line */
947 if (iey < 0 || isy >= height) {
948 /* All line is outside. */
949 cr->y = ey;
950 cr->left = ex;
951 cr->right = ex;
952 cr->can_save = 0;
953 return;
954 }
955 if (isy < 0) {
956 /* Move sy up */
957 int y = ey - sy;
958 int new_sy = int2fixed(base_y);
959 int dy = new_sy - sy;
960 sx += (int)((((int64_t)(ex-sx))*dy + y/2)/y);
961 sy = new_sy;
962 cursor_init(eb, rev, sy, sx);
963 isy = 0;
964 }
965 truncated = iey > height;
966 if (truncated) {
967 /* Move ey down */
968 int y = ey - sy;
969 int new_ey = int2fixed(base_y + height);
970 int dy = ey - new_ey;
971 save_ex = ex;
972 save_ey = ey;
973 ex -= (int)((((int64_t)(ex-sx))*dy + y/2)/y);
974 ey = new_ey;
975 iey = height;
976 }
977 } else {
978 /* Falling line */
979 if (isy < 0 || iey >= height) {
980 /* All line is outside. */
981 cr->y = ey;
982 cr->left = ex;
983 cr->right = ex;
984 cr->can_save = 0;
985 return;
986 }
987 truncated = iey < 0;
988 if (truncated) {
989 /* Move ey up */
990 int y = ey - sy;
991 int new_ey = int2fixed(base_y);
992 int dy = ey - new_ey;
993 ex -= (int)((((int64_t)(ex-sx))*dy + y/2)/y);
994 ey = new_ey;
995 iey = 0;
996 }
997 if (isy >= height) {
998 /* Move sy down */
999 int y = ey - sy;
1000 if (y) {
1001 int new_sy = int2fixed(base_y + height);
1002 int dy = new_sy - sy;
1003 sx += (int)((((int64_t)(ex-sx))*dy + y/2)/y);
1004 sy = new_sy;
1005 cursor_init(eb, rev, sy, sx);
1006 isy = height;
1007 }
1008 }
1009 }
1010
1011 assert(cr->left <= sx);
1012 assert(cr->right >= sx);
1013 assert(cr->y == sy);
1014
1015 /* A note: The code below used to be of the form:
1016 * if (isy == iey) ... deal with horizontal lines
1017 * else if (ey > sy) {
1018 * fixed y_steps = ey - sy;
1019 * ... deal with rising lines ...
1020 * } else {
1021 * fixed y_steps = ey - sy;
1022 * ... deal with falling lines
1023 * }
1024 * but that lead to problems, for instance, an example seen
1025 * has sx=2aa8e, sy=8aee7, ex=7ffc1686, ey=8003e97a.
1026 * Thus isy=84f, iey=ff80038a. We can see that ey < sy, but
1027 * sy - ey < 0!
1028 * We therefore rejig our code so that the choice between
1029 * cases is done based on the sign of y_steps rather than
1030 * the relative size of ey and sy.
1031 */
1032
1033 /* First, deal with lines that don't change scanline.
1034 * This accommodates horizontal lines. */
1035 if (isy == iey) {
1036 if (save_sy == save_ey) {
1037 /* Horizontal line. Don't change cr->d, don't flush. */
1038 } else if (save_sy > save_ey) {
1039 /* Falling line, flush if previous was rising */
1040 cursor_down(eb, rev, sx);
1041 } else {
1042 /* Rising line, flush if previous was falling */
1043 cursor_up(eb, rev, sx);
1044 }
1045 if (sx <= ex) {
1046 cursor_left_merge(eb, rev, sx);
1047 cursor_right_merge(eb, rev, ex);
1048 } else {
1049 cursor_left_merge(eb, rev, ex);
1050 cursor_right_merge(eb, rev, sx);
1051 }
1052 cr->y = ey;
1053 if (sy > save_ey)
1054 goto endFalling;
1055 } else if ((y_steps = ey - sy) > 0) {
1056 /* We want to change from sy to ey, which are guaranteed to be on
1057 * different scanlines. We do this in 3 phases.
1058 * Phase 1 gets us from sy to the next scanline boundary.
1059 * Phase 2 gets us all the way to the last scanline boundary.
1060 * Phase 3 gets us from the last scanline boundary to ey.
1061 */
1062 /* We want to change from sy to ey, which are guaranteed to be on
1063 * different scanlines. We do this in 3 phases.
1064 * Phase 1 gets us from sy to the next scanline boundary. (We may exit after phase 1).
1065 * Phase 2 gets us all the way to the last scanline boundary. (This may be a null operation)
1066 * Phase 3 gets us from the last scanline boundary to ey. (We are guaranteed to have output the cursor at least once before phase 3).
1067 */
1068 int phase1_y_steps = (-sy) & (fixed_1 - 1);
1069 int phase3_y_steps = ey & (fixed_1 - 1);
1070
1071 cursor_up(eb, rev, sx);
1072
1073 if (sx == ex) {
1074 /* Vertical line. (Rising) */
1075
1076 /* Phase 1: */
1077 cursor_left_merge(eb, rev, sx);
1078 cursor_right_merge(eb, rev, sx);
1079 if (phase1_y_steps) {
1080 /* If phase 1 will move us into a new scanline, then we must
1081 * flush it before we move. */
1082 cursor_step(eb, rev, phase1_y_steps, sx);
1083 sy += phase1_y_steps;
1084 y_steps -= phase1_y_steps;
1085 if (y_steps == 0)
1086 goto end;
1087 }
1088
1089 /* Phase 3: precalculation */
1090 y_steps -= phase3_y_steps;
1091
1092 /* Phase 2: */
1093 y_steps = fixed2int(y_steps);
1094 assert(y_steps >= 0);
1095 if (y_steps > 0) {
1096 cursor_always_step(eb, rev, fixed_1, sx);
1097 y_steps--;
1098 while (y_steps) {
1099 cursor_always_step_inrange_vertical(eb, rev, fixed_1, sx);
1100 y_steps--;
1101 }
1102 }
1103
1104 /* Phase 3 */
1105 assert(cr->left == sx && cr->right == sx);
1106 cr->y += phase3_y_steps;
1107 } else if (sx < ex) {
1108 /* Lines increasing in x. (Rightwards, rising) */
1109 int phase1_x_steps, phase3_x_steps;
1110 fixed x_steps = ex - sx;
1111
1112 /* Phase 1: */
1113 cursor_left_merge(eb, rev, sx);
1114 if (phase1_y_steps) {
1115 phase1_x_steps = (int)(((int64_t)x_steps * phase1_y_steps + y_steps/2) / y_steps);
1116 sx += phase1_x_steps;
1117 cursor_right_merge(eb, rev, sx);
1118 x_steps -= phase1_x_steps;
1119 cursor_step(eb, rev, phase1_y_steps, sx);
1120 sy += phase1_y_steps;
1121 y_steps -= phase1_y_steps;
1122 if (y_steps == 0)
1123 goto end;
1124 }
1125
1126 /* Phase 3: precalculation */
1127 phase3_x_steps = (int)(((int64_t)x_steps * phase3_y_steps + y_steps/2) / y_steps);
1128 x_steps -= phase3_x_steps;
1129 y_steps -= phase3_y_steps;
1130 assert((y_steps & (fixed_1 - 1)) == 0);
1131
1132 /* Phase 2: */
1133 y_steps = fixed2int(y_steps);
1134 assert(y_steps >= 0);
1135 if (y_steps) {
1136 /* We want to change sx by x_steps in y_steps steps.
1137 * So each step, we add x_steps/y_steps to sx. That's x_inc + n_inc/y_steps. */
1138 int x_inc = x_steps/y_steps;
1139 int n_inc = x_steps - (x_inc * y_steps);
1140 int f = y_steps/2;
1141 int d = y_steps;
1142
1143 /* Special casing the unset iteration, allows us to simplify
1144 * the following loop. */
1145 sx += x_inc;
1146 f -= n_inc;
1147 if (f < 0)
1148 f += d, sx++;
1149 cursor_right_merge(eb, rev, sx);
1150 cursor_always_step(eb, rev, fixed_1, sx);
1151 y_steps--;
1152
1153 while (y_steps) {
1154 sx += x_inc;
1155 f -= n_inc;
1156 if (f < 0)
1157 f += d, sx++;
1158 cursor_right(eb, rev, sx);
1159 cursor_always_inrange_step_right(eb, rev, fixed_1, sx);
1160 y_steps--;
1161 };
1162 }
1163
1164 /* Phase 3 */
1165 assert(cr->left <= ex && cr->right >= sx);
1166 cursor_right(eb, rev, ex);
1167 cr->y += phase3_y_steps;
1168 } else {
1169 /* Lines decreasing in x. (Leftwards, rising) */
1170 int phase1_x_steps, phase3_x_steps;
1171 fixed x_steps = sx - ex;
1172
1173 /* Phase 1: */
1174 cursor_right_merge(eb, rev, sx);
1175 if (phase1_y_steps) {
1176 phase1_x_steps = (int)(((int64_t)x_steps * phase1_y_steps + y_steps/2) / y_steps);
1177 x_steps -= phase1_x_steps;
1178 sx -= phase1_x_steps;
1179 cursor_left_merge(eb, rev, sx);
1180 cursor_step(eb, rev, phase1_y_steps, sx);
1181 sy += phase1_y_steps;
1182 y_steps -= phase1_y_steps;
1183 if (y_steps == 0)
1184 goto end;
1185 }
1186
1187 /* Phase 3: precalculation */
1188 phase3_x_steps = (int)(((int64_t)x_steps * phase3_y_steps + y_steps/2) / y_steps);
1189 x_steps -= phase3_x_steps;
1190 y_steps -= phase3_y_steps;
1191 assert((y_steps & (fixed_1 - 1)) == 0);
1192
1193 /* Phase 2: */
1194 y_steps = fixed2int(y_steps);
1195 assert(y_steps >= 0);
1196 if (y_steps) {
1197 /* We want to change sx by x_steps in y_steps steps.
1198 * So each step, we sub x_steps/y_steps from sx. That's x_inc + n_inc/ey. */
1199 int x_inc = x_steps/y_steps;
1200 int n_inc = x_steps - (x_inc * y_steps);
1201 int f = y_steps/2;
1202 int d = y_steps;
1203
1204 /* Special casing the unset iteration, allows us to simplify
1205 * the following loop. */
1206 sx -= x_inc;
1207 f -= n_inc;
1208 if (f < 0)
1209 f += d, sx--;
1210 cursor_left_merge(eb, rev, sx);
1211 cursor_always_step(eb, rev, fixed_1, sx);
1212 y_steps--;
1213
1214 while (y_steps) {
1215 sx -= x_inc;
1216 f -= n_inc;
1217 if (f < 0)
1218 f += d, sx--;
1219 cursor_left(eb, rev, sx);
1220 cursor_always_inrange_step_left(eb, rev, fixed_1, sx);
1221 y_steps--;
1222 }
1223 }
1224
1225 /* Phase 3 */
1226 assert(cr->right >= ex && cr->left <= sx);
1227 cursor_left(eb, rev, ex);
1228 cr->y += phase3_y_steps;
1229 }
1230 } else {
1231 /* So lines decreasing in y. */
1232 /* We want to change from sy to ey, which are guaranteed to be on
1233 * different scanlines. We do this in 3 phases.
1234 * Phase 1 gets us from sy to the next scanline boundary. This never causes an output.
1235 * Phase 2 gets us all the way to the last scanline boundary. This is guaranteed to cause an output.
1236 * Phase 3 gets us from the last scanline boundary to ey. We are guaranteed to have outputted by now.
1237 */
1238 int phase1_y_steps = sy & (fixed_1 - 1);
1239 int phase3_y_steps = (-ey) & (fixed_1 - 1);
1240
1241 y_steps = -y_steps;
1242 /* Cope with the awkward 0x80000000 case. */
1243 if (y_steps < 0)
1244 {
1245 int mx, my;
1246 mx = sx + ((ex-sx)>>1);
1247 my = sy + ((ey-sy)>>1);
1248 do_mark_line_app(ctx, eb, sx, sy, mx, my, rev);
1249 do_mark_line_app(ctx, eb, mx, my, ex, ey, rev);
1250 return;
1251 }
1252
1253 cursor_down(eb, rev, sx);
1254
1255 if (sx == ex) {
1256 /* Vertical line. (Falling) */
1257
1258 /* Phase 1: */
1259 cursor_left_merge(eb, rev, sx);
1260 cursor_right_merge(eb, rev, sx);
1261 if (phase1_y_steps) {
1262 /* Phase 1 in a falling line never moves us into a new scanline. */
1263 cursor_never_step_vertical(eb, rev, -phase1_y_steps, sx);
1264 sy -= phase1_y_steps;
1265 y_steps -= phase1_y_steps;
1266 if (y_steps == 0)
1267 goto endFalling;
1268 }
1269
1270 /* Phase 3: precalculation */
1271 y_steps -= phase3_y_steps;
1272 assert((y_steps & (fixed_1 - 1)) == 0);
1273
1274 /* Phase 2: */
1275 y_steps = fixed2int(y_steps);
1276 assert(y_steps >= 0);
1277 if (y_steps) {
1278 cursor_always_step(eb, rev, -fixed_1, sx);
1279 y_steps--;
1280 while (y_steps) {
1281 cursor_always_step_inrange_vertical(eb, rev, -fixed_1, sx);
1282 y_steps--;
1283 }
1284 }
1285
1286 /* Phase 3 */
1287 if (phase3_y_steps > 0) {
1288 cursor_step(eb, rev, -phase3_y_steps, sx);
1289 assert(cr->left == sx && cr->right == sx);
1290 }
1291 } else if (sx < ex) {
1292 /* Lines increasing in x. (Rightwards, falling) */
1293 int phase1_x_steps, phase3_x_steps;
1294 fixed x_steps = ex - sx;
1295
1296 /* Phase 1: */
1297 cursor_left_merge(eb, rev, sx);
1298 if (phase1_y_steps) {
1299 phase1_x_steps = (int)(((int64_t)x_steps * phase1_y_steps + y_steps/2) / y_steps);
1300 x_steps -= phase1_x_steps;
1301 sx += phase1_x_steps;
1302 /* Phase 1 in a falling line never moves us into a new scanline. */
1303 cursor_never_step_right(eb, rev, -phase1_y_steps, sx);
1304 sy -= phase1_y_steps;
1305 y_steps -= phase1_y_steps;
1306 if (y_steps == 0)
1307 goto endFalling;
1308 } else
1309 cursor_right_merge(eb, rev, sx);
1310
1311 /* Phase 3: precalculation */
1312 phase3_x_steps = (int)(((int64_t)x_steps * phase3_y_steps + y_steps/2) / y_steps);
1313 x_steps -= phase3_x_steps;
1314 y_steps -= phase3_y_steps;
1315 assert((y_steps & (fixed_1 - 1)) == 0);
1316
1317 /* Phase 2: */
1318 y_steps = fixed2int(y_steps);
1319 assert(y_steps >= 0);
1320 if (y_steps) {
1321 /* We want to change sx by x_steps in y_steps steps.
1322 * So each step, we add x_steps/y_steps to sx. That's x_inc + n_inc/ey. */
1323 int x_inc = x_steps/y_steps;
1324 int n_inc = x_steps - (x_inc * y_steps);
1325 int f = y_steps/2;
1326 int d = y_steps;
1327
1328 cursor_always_step(eb, rev, -fixed_1, sx);
1329 sx += x_inc;
1330 f -= n_inc;
1331 if (f < 0)
1332 f += d, sx++;
1333 cursor_right(eb, rev, sx);
1334 y_steps--;
1335
1336 while (y_steps) {
1337 cursor_always_inrange_step_right(eb, rev, -fixed_1, sx);
1338 sx += x_inc;
1339 f -= n_inc;
1340 if (f < 0)
1341 f += d, sx++;
1342 cursor_right(eb, rev, sx);
1343 y_steps--;
1344 }
1345 }
1346
1347 /* Phase 3 */
1348 if (phase3_y_steps > 0) {
1349 cursor_step(eb, rev, -phase3_y_steps, sx);
1350 cursor_right(eb, rev, ex);
1351 assert(cr->left == sx && cr->right == ex);
1352 }
1353 } else {
1354 /* Lines decreasing in x. (Falling) */
1355 int phase1_x_steps, phase3_x_steps;
1356 fixed x_steps = sx - ex;
1357
1358 /* Phase 1: */
1359 cursor_right_merge(eb, rev, sx);
1360 if (phase1_y_steps) {
1361 phase1_x_steps = (int)(((int64_t)x_steps * phase1_y_steps + y_steps/2) / y_steps);
1362 x_steps -= phase1_x_steps;
1363 sx -= phase1_x_steps;
1364 /* Phase 1 in a falling line never moves us into a new scanline. */
1365 cursor_never_step_left(eb, rev, -phase1_y_steps, sx);
1366 sy -= phase1_y_steps;
1367 y_steps -= phase1_y_steps;
1368 if (y_steps == 0)
1369 goto endFalling;
1370 } else
1371 cursor_left_merge(eb, rev, sx);
1372
1373 /* Phase 3: precalculation */
1374 phase3_x_steps = (int)(((int64_t)x_steps * phase3_y_steps + y_steps/2) / y_steps);
1375 x_steps -= phase3_x_steps;
1376 y_steps -= phase3_y_steps;
1377 assert((y_steps & (fixed_1 - 1)) == 0);
1378
1379 /* Phase 2: */
1380 y_steps = fixed2int(y_steps);
1381 assert(y_steps >= 0);
1382 if (y_steps) {
1383 /* We want to change sx by x_steps in y_steps steps.
1384 * So each step, we sub x_steps/y_steps from sx. That's x_inc + n_inc/ey. */
1385 int x_inc = x_steps/y_steps;
1386 int n_inc = x_steps - (x_inc * y_steps);
1387 int f = y_steps/2;
1388 int d = y_steps;
1389
1390 cursor_always_step(eb, rev, -fixed_1, sx);
1391 sx -= x_inc;
1392 f -= n_inc;
1393 if (f < 0)
1394 f += d, sx--;
1395 cursor_left(eb, rev, sx);
1396 y_steps--;
1397
1398 while (y_steps) {
1399 cursor_always_inrange_step_left(eb, rev, -fixed_1, sx);
1400 sx -= x_inc;
1401 f -= n_inc;
1402 if (f < 0)
1403 f += d, sx--;
1404 cursor_left(eb, rev, sx);
1405 y_steps--;
1406 }
1407 }
1408
1409 /* Phase 3 */
1410 if (phase3_y_steps > 0) {
1411 cursor_step(eb, rev, -phase3_y_steps, sx);
1412 cursor_left(eb, rev, ex);
1413 assert(cr->left == ex && cr->right == sx);
1414 }
1415 }
1416endFalling:
1417 if (truncated)
1418 cursor_output(eb, rev, fixed2int(cr->y) - base_y);
1419 }
1420
1421end:
1422 if (truncated) {
1423 cr->left = save_ex;
1424 cr->right = save_ex;
1425 cr->y = save_ey;
1426 }
1427}
1428
1429static void mark_line_app(fz_context *ctx, fz_edgebuffer *eb, fixed sx, fixed sy, fixed ex, fixed ey, int rev)
1430{
1431 if (rev == 1)
1432 {
1433 fixed t;
1434 t = sx, sx = ex, ex = t;
1435 t = sy, sy = ey, ey = t;
1436 }
1437 do_mark_line_app(ctx, eb, sx, sy, ex, ey, rev);
1438}
1439
1440static void fz_insert_edgebuffer_app(fz_context *ctx, fz_rasterizer *ras, float fsx, float fsy, float fex, float fey, int rev)
1441{
1442 fz_edgebuffer *eb = (fz_edgebuffer *)ras;
1443 fixed sx = float2fixed(fsx);
1444 fixed sy = float2fixed(fsy);
1445 fixed ex = float2fixed(fex);
1446 fixed ey = float2fixed(fey);
1447
1448 if (fsx < fex)
1449 {
1450 if (fsx < eb->super.bbox.x0) eb->super.bbox.x0 = fsx;
1451 if (fex > eb->super.bbox.x1) eb->super.bbox.x1 = fex;
1452 }
1453 else
1454 {
1455 if (fsx > eb->super.bbox.x1) eb->super.bbox.x1 = fsx;
1456 if (fex < eb->super.bbox.x0) eb->super.bbox.x0 = fex;
1457 }
1458 if (fsy < fey)
1459 {
1460 if (fsy < eb->super.bbox.y0) eb->super.bbox.y0 = fsy;
1461 if (fey > eb->super.bbox.y1) eb->super.bbox.y1 = fey;
1462 }
1463 else
1464 {
1465 if (fey < eb->super.bbox.y0) eb->super.bbox.y0 = fey;
1466 if (fsy > eb->super.bbox.y1) eb->super.bbox.y1 = fsy;
1467 }
1468
1469 mark_line_app(ctx, eb, sx, sy, ex, ey, rev);
1470}
1471
1472static int intcmp(const void *a, const void *b)
1473{
1474 return *((int*)a) - *((int *)b);
1475}
1476
1477static void fz_convert_edgebuffer(fz_context *ctx, fz_rasterizer *ras, int eofill, const fz_irect *clip, fz_pixmap *pix, unsigned char *color, fz_overprint *eop)
1478{
1479 fz_edgebuffer *eb = (fz_edgebuffer *)ras;
1480 int scanlines = ras->clip.y1 - ras->clip.y0;
1481 int i, n, a, pl, pr;
1482 int *table = eb->table;
1483 int *index = eb->index;
1484 uint8_t *out;
1485 fz_solid_color_painter_t *fn;
1486
1487 fn = fz_get_solid_color_painter(pix->n, color, pix->alpha, eop);
1488 assert(fn);
1489 if (fn == NULL)
1490 return;
1491
1492#ifdef DEBUG_SCAN_CONVERTER
1493 if (debugging_scan_converter)
1494 {
1495 fz_output *err = fz_stderr(ctx);
1496 fz_write_printf(ctx, err, "Before sort:\n");
1497 fz_edgebuffer_print(ctx, err, eb);
1498 }
1499#endif
1500
1501 if (!eb->sorted)
1502 {
1503 eb->sorted = 1;
1504 for (i = 0; i < scanlines; i++)
1505 {
1506 int *row = &table[index[i]];
1507 int rowlen = *row++;
1508
1509 /* Bubblesort short runs, qsort longer ones. */
1510 /* FIXME: Check "6" below */
1511 if (rowlen <= 6) {
1512 int j, k;
1513 for (j = 0; j < rowlen-1; j++)
1514 {
1515 int t = row[j];
1516 for (k = j+1; k < rowlen; k++)
1517 {
1518 int s = row[k];
1519 if (t > s)
1520 row[k] = t, t = row[j] = s;
1521 }
1522 }
1523 } else
1524 qsort(row, rowlen, sizeof(int), intcmp);
1525 }
1526
1527#ifdef DEBUG_SCAN_CONVERTER
1528 if (debugging_scan_converter)
1529 {
1530 fz_output *err = fz_stderr(ctx);
1531 fz_write_printf(ctx, err, "Before filter: %s\n", eofill ? "EO" : "NZ");
1532 fz_edgebuffer_print(ctx, err, eb);
1533 }
1534#endif
1535
1536 for (i=0; i < scanlines; i++) {
1537 int *row = &table[index[i]];
1538 int *rowstart = row;
1539 int rowlen = *row++;
1540 int *rowout = row;
1541
1542 while (rowlen > 0)
1543 {
1544 int left, right;
1545
1546 if (eofill) {
1547 /* Even Odd */
1548 left = (*row++)&~1;
1549 right = (*row++)&~1;
1550 rowlen -= 2;
1551 } else {
1552 /* Non-Zero */
1553 int w;
1554
1555 left = *row++;
1556 w = ((left&1)-1) | (left&1);
1557 rowlen--;
1558 do {
1559 right = *row++;
1560 rowlen--;
1561 w += ((right&1)-1) | (right&1);
1562 } while (w != 0);
1563 left &= ~1;
1564 right &= ~1;
1565 }
1566
1567 if (right > left) {
1568 *rowout++ = left;
1569 *rowout++ = right;
1570 }
1571 }
1572 *rowstart = (rowout-rowstart)-1;
1573 }
1574 }
1575
1576#ifdef DEBUG_SCAN_CONVERTER
1577 if (debugging_scan_converter)
1578 {
1579 fz_output *err = fz_stderr(ctx);
1580 fz_write_printf(ctx, err, "Before render:\n");
1581 fz_edgebuffer_print(ctx, err, eb);
1582 }
1583#endif
1584
1585 n = pix->n;
1586 a = pix->alpha;
1587 pl = fz_maxi(ras->clip.x0, pix->x);
1588 pr = fz_mini(ras->clip.x1, pix->x + pix->w);
1589 pr -= pl;
1590 out = pix->samples + pix->stride * fz_maxi(ras->clip.y0 - pix->y, 0) + fz_maxi(ras->clip.x0 - pix->x, 0) * n;
1591 if (scanlines > pix->y + pix->h - ras->clip.y0)
1592 scanlines = pix->y + pix->h - ras->clip.y0;
1593 for (i = fz_maxi(pix->y - ras->clip.y0, 0); i < scanlines; i++) {
1594 int *row = &table[index[i]];
1595 int rowlen = *row++;
1596
1597 while (rowlen > 0) {
1598 int left, right;
1599
1600 left = *row++;
1601 right = *row++;
1602 rowlen -= 2;
1603 left = fixed2int(left + fixed_half) - pl;
1604 right = fixed2int(right + fixed_half) - pl;
1605
1606 if (right <= 0)
1607 continue;
1608 if (left >= pr)
1609 continue;
1610 if (right > pr)
1611 right = pr;
1612 if (left < 0)
1613 left = 0;
1614 right -= left;
1615 if (right > 0) {
1616 (*fn)(out + left*n, n, right, color, a, eop);
1617 }
1618 }
1619 out += pix->stride;
1620 }
1621}
1622
1623static int edgecmp(const void *a, const void *b)
1624{
1625 int left = ((int*)a)[0];
1626 int right = ((int*)b)[0];
1627 left -= right;
1628 if (left)
1629 return left;
1630 return ((int*)a)[1] - ((int*)b)[1];
1631}
1632
1633static void fz_convert_edgebuffer_app(fz_context *ctx, fz_rasterizer *ras, int eofill, const fz_irect *clip, fz_pixmap *pix, unsigned char *color, fz_overprint *eop)
1634{
1635 fz_edgebuffer *eb = (fz_edgebuffer *)ras;
1636 int scanlines = ras->clip.y1 - ras->clip.y0;
1637 int i, n, a, pl, pr;
1638 int *table = eb->table;
1639 int *index = eb->index;
1640 uint8_t *out;
1641 fz_solid_color_painter_t *fn;
1642
1643 fn = fz_get_solid_color_painter(pix->n, color, pix->alpha, eop);
1644 assert(fn);
1645 if (fn == NULL)
1646 return;
1647
1648#ifdef DEBUG_SCAN_CONVERTER
1649 if (debugging_scan_converter)
1650 {
1651 fz_output *err = fz_stderr(ctx);
1652 fz_write_printf(ctx, err, "Before sort:\n");
1653 fz_edgebuffer_print_app(ctx, err, eb);
1654 }
1655#endif
1656
1657 if (!eb->sorted)
1658 {
1659 eb->sorted = 1;
1660 for (i = 0; i < scanlines; i++)
1661 {
1662 int *row = &table[index[i]];
1663 int rowlen = *row++;
1664
1665 /* Bubblesort short runs, qsort longer ones. */
1666 /* FIXME: Check "6" below */
1667 if (rowlen <= 6) {
1668 int j, k;
1669 for (j = 0; j < rowlen-1; j++) {
1670 int * FZ_RESTRICT t = &row[j<<1];
1671 for (k = j+1; k < rowlen; k++) {
1672 int * FZ_RESTRICT s = &row[k<<1];
1673 int tmp;
1674 if (t[0] < s[0])
1675 continue;
1676 if (t[0] > s[0])
1677 tmp = t[0], t[0] = s[0], s[0] = tmp;
1678 else if (t[0] <= s[1])
1679 continue;
1680 tmp = t[1]; t[1] = s[1]; s[1] = tmp;
1681 }
1682 }
1683 } else
1684 qsort(row, rowlen, 2*sizeof(int), edgecmp);
1685 }
1686
1687#ifdef DEBUG_SCAN_CONVERTER
1688 if (debugging_scan_converter)
1689 {
1690 fz_output *err = fz_stderr(ctx);
1691 fz_write_printf(ctx, err, "Before filter: %s\n", eofill ? "EO" : "NZ");
1692 fz_edgebuffer_print_app(ctx, err, eb);
1693 }
1694#endif
1695
1696 for (i=0; i < scanlines; i++) {
1697 int *row = &table[index[i]];
1698 int rowlen = *row++;
1699 int *rowstart = row;
1700 int *rowout = row;
1701 int ll, lr, rl, rr, wind, marked_to;
1702
1703 /* Avoid double setting pixels, by keeping where we have marked to. */
1704 marked_to = int2fixed(clip->x0);
1705 while (rowlen > 0) {
1706 if (eofill) {
1707 /* Even Odd */
1708 ll = (*row++)&~1;
1709 lr = *row;
1710 row += 2;
1711 rowlen-=2;
1712
1713 /* We will fill solidly from ll to at least lr, possibly further */
1714 assert(rowlen >= 0);
1715 rr = (*row++);
1716 if (rr > lr)
1717 lr = rr;
1718 } else {
1719 /* Non-Zero */
1720 int w;
1721
1722 ll = *row++;
1723 lr = *row++;
1724 wind = -(ll&1) | 1;
1725 ll &= ~1;
1726 rowlen--;
1727
1728 assert(rowlen > 0);
1729 do {
1730 rl = *row++;
1731 rr = *row++;
1732 w = -(rl&1) | 1;
1733 rl &= ~1;
1734 rowlen--;
1735 if (rr > lr)
1736 lr = rr;
1737 wind += w;
1738 if (wind == 0)
1739 break;
1740 } while (rowlen > 0);
1741 }
1742
1743 if (marked_to >= lr)
1744 continue;
1745
1746 if (marked_to >= ll) {
1747 if (rowout == rowstart)
1748 ll = marked_to;
1749 else {
1750 rowout -= 2;
1751 ll = *rowout;
1752 }
1753 }
1754
1755 if (lr > ll) {
1756 *rowout++ = ll;
1757 *rowout++ = lr;
1758 marked_to = lr;
1759 }
1760 }
1761 rowstart[-1] = rowout-rowstart;
1762 }
1763 }
1764
1765#ifdef DEBUG_SCAN_CONVERTER
1766 if (debugging_scan_converter)
1767 {
1768 fz_output *err = fz_stderr(ctx);
1769 fz_write_printf(ctx, err, "Before render:\n");
1770 fz_edgebuffer_print_app(ctx, err, eb);
1771 }
1772#endif
1773
1774 n = pix->n;
1775 a = pix->alpha;
1776 pl = clip->x0;
1777 pr = clip->x1 - pl;
1778 out = pix->samples + pix->stride * (clip->y0 - pix->y) + (clip->x0 - pix->x) * n;
1779 if (scanlines > clip->y1 - ras->clip.y0)
1780 scanlines = clip->y1 - ras->clip.y0;
1781
1782 i = (clip->y0 - ras->clip.y0);
1783 if (i < 0)
1784 return;
1785 for (; i < scanlines; i++) {
1786 int *row = &table[index[i]];
1787 int rowlen = *row++;
1788
1789 while (rowlen > 0) {
1790 int left, right;
1791
1792 left = *row++;
1793 right = *row++;
1794 rowlen -= 2;
1795 left = fixed2int(left + fixed_half) - pl;
1796 right = fixed2int(right + fixed_half) - pl;
1797
1798 if (right <= 0)
1799 continue;
1800 if (left >= pr)
1801 break;
1802 if (right > pr)
1803 right = pr;
1804 if (left < 0)
1805 left = 0;
1806 right -= left;
1807 if (right > 0) {
1808 (*fn)(out + left*n, n, right, color, a, eop);
1809 }
1810 }
1811 out += pix->stride;
1812 }
1813}
1814
1815static void fz_gap_edgebuffer(fz_context *ctx, fz_rasterizer *ras)
1816{
1817 fz_edgebuffer *eb = (fz_edgebuffer *)ras;
1818
1819 if (eb->app)
1820 {
1821#ifdef DEBUG_SCAN_CONVERTER
1822 if (0 && debugging_scan_converter)
1823 {
1824 fz_output *err = fz_stderr(ctx);
1825 fz_write_printf(ctx, fz_stderr(ctx), "Pen up move.\n");
1826 fz_write_printf(ctx, err, "Before flush:\n");
1827 fz_edgebuffer_print_app(ctx, err, eb);
1828 }
1829#endif
1830 cursor_flush(eb);
1831 eb->cursor[0].saved = 0;
1832 eb->cursor[0].unset = 1;
1833 eb->cursor[0].can_save = 1;
1834 eb->cursor[0].d = DIRN_UNSET;
1835 eb->cursor[1].saved = 0;
1836 eb->cursor[1].unset = 1;
1837 eb->cursor[1].can_save = 1;
1838 eb->cursor[1].d = DIRN_UNSET;
1839 eb->cursor[2].saved = 0;
1840 eb->cursor[2].unset = 1;
1841 eb->cursor[2].can_save = 1;
1842 eb->cursor[2].d = DIRN_UNSET;
1843 }
1844}
1845
1846static int fz_is_rect_edgebuffer(fz_context *ctx, fz_rasterizer *r)
1847{
1848 return 0;
1849}
1850
1851static const fz_rasterizer_fns edgebuffer_app =
1852{
1853 fz_drop_edgebuffer,
1854 fz_reset_edgebuffer,
1855 fz_postindex_edgebuffer,
1856 fz_insert_edgebuffer_app,
1857 NULL,
1858 fz_gap_edgebuffer,
1859 fz_convert_edgebuffer_app,
1860 fz_is_rect_edgebuffer,
1861 1 /* Reusable */
1862};
1863
1864static const fz_rasterizer_fns edgebuffer_cop =
1865{
1866 fz_drop_edgebuffer,
1867 fz_reset_edgebuffer,
1868 fz_postindex_edgebuffer,
1869 fz_insert_edgebuffer,
1870 NULL,
1871 NULL, /* gap */
1872 fz_convert_edgebuffer,
1873 fz_is_rect_edgebuffer,
1874 1 /* Reusable */
1875};
1876
1877fz_rasterizer *
1878fz_new_edgebuffer(fz_context *ctx, fz_edgebuffer_rule rule)
1879{
1880 fz_edgebuffer *eb;
1881 eb = fz_new_derived_rasterizer(ctx, fz_edgebuffer, rule == FZ_EDGEBUFFER_ANY_PART_OF_PIXEL ? &edgebuffer_app : &edgebuffer_cop);
1882 eb->app = rule == FZ_EDGEBUFFER_ANY_PART_OF_PIXEL;
1883 return &eb->super;
1884}
1885