Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/source/fitz/draw-edgebuffer.c @ 2:b50eed0cc0ef upstream

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