Add edgebuffer based rasterizer

3 files changed, 1915 insertions, 1 deletions

diff --git a/source/fitz/draw-edgebuffer.c b/source/fitz/draw-edgebuffer.c
new file mode 100644
index 00000000..d3145d4a
--- /dev/null
+++ b/source/fitz/draw-edgebuffer.c
@@ -0,0 +1,1903 @@
+#include "mupdf/fitz.h"
+#include "draw-imp.h"
+
+#undef DEBUG_SCAN_CONVERTER
+
+/* Define ourselves a 'fixed' type for clarity */
+typedef int fixed;
+
+#define fixed_shift 8
+#define float2fixed(x) ((int)((x)*(1<<fixed_shift)))
+#define fixed2int(x) ((int)((x)>>fixed_shift))
+#define fixed_half (1<<(fixed_shift-1))
+#define fixed_1 (1<<fixed_shift)
+#define int2fixed(x) ((x)<<fixed_shift)
+
+enum
+{
+	DIRN_UNSET = -1,
+	DIRN_UP = 0,
+	DIRN_DOWN = 1
+};
+
+typedef struct
+{
+	fixed left;
+	fixed right;
+	fixed y;
+	signed char d; /* 0 up (or horiz), 1 down, -1 uninited */
+
+	/* unset == 1, iff the values in the above are unset */
+	unsigned char unset;
+	/* can_save == 1, iff we are eligible to 'save'. i.e. if we
+	 * have not yet output a cursor, and have not detected
+	 * any line segments completely out of range. */
+	unsigned char can_save;
+	unsigned char saved;
+
+	fixed save_left;
+	fixed save_right;
+	int save_iy;
+	int save_d;
+}
+cursor_t;
+
+typedef struct fz_edgebuffer_s
+{
+	fz_rasterizer super;
+	int app;
+	int sorted;
+	int n;
+	int index_cap;
+	int *index;
+	int table_cap;
+	int *table;
+
+	/* cursor section, for use with any part of pixel mode */
+	cursor_t cursor[3];
+} fz_edgebuffer;
+
+static fz_rasterizer_insert_fn fz_insert_edgebuffer_app;
+static fz_rasterizer_insert_fn fz_insert_edgebuffer;
+
+#ifdef DEBUG_SCAN_CONVERTER
+int debugging_scan_converter = 1;
+
+static void
+fz_edgebuffer_print(fz_context *ctx, fz_output *out, fz_edgebuffer * edgebuffer)
+{
+	int i;
+	int height = edgebuffer->super.clip.y1 - edgebuffer->super.clip.y0;
+
+	fz_write_printf(ctx, out, "Edgebuffer %x\n", edgebuffer);
+	fz_write_printf(ctx, out, "xmin=%x xmax=%x base=%x height=%x\n",
+			  edgebuffer->super.clip.x0, edgebuffer->super.clip.x1, edgebuffer->super.clip.y0, height);
+	for (i=0; i < height; i++) {
+		int  offset = edgebuffer->index[i];
+		int *row = &edgebuffer->table[offset];
+		int count = *row++;
+		assert ((count & 1) == 0);
+		fz_write_printf(ctx, out, "%x @ %x: %d =", i, offset, count);
+		while (count-- > 0) {
+			int v = *row++;
+			fz_write_printf(ctx, out, " %x:%d", v&~1, v&1);
+		}
+		fz_write_printf(ctx, out, "\n");
+	}
+}
+
+static void
+fz_edgebuffer_print_app(fz_context *ctx, fz_output *out, fz_edgebuffer * edgebuffer)
+{
+	int i;
+	int height = edgebuffer->super.clip.y1 - edgebuffer->super.clip.y0;
+
+	fz_write_printf(ctx, out, "Edgebuffer %x\n", edgebuffer);
+	fz_write_printf(ctx, out, "xmin=%x xmax=%x base=%x height=%x\n",
+			  edgebuffer->super.clip.x0, edgebuffer->super.clip.x1, edgebuffer->super.clip.y0, height);
+	if (edgebuffer->table == NULL)
+		return;
+	for (i=0; i < height; i++) {
+		int  offset = edgebuffer->index[i];
+		int *row = &edgebuffer->table[offset];
+		int count = *row++;
+		int count0 = count;
+		fz_write_printf(ctx, out, "%x @ %x: %d =", i, offset, count);
+		while (count-- > 0) {
+			int l = *row++;
+			int r = *row++;
+			fz_write_printf(ctx, out, " %x:%x", l, r);
+		}
+		assert((count0 & 1) == 0); (void)count0;
+		fz_write_printf(ctx, out, "\n");
+	}
+}
+#endif
+
+static void fz_drop_edgebuffer(fz_context *ctx, fz_rasterizer *r)
+{
+	fz_edgebuffer *eb = (fz_edgebuffer *)r;
+
+	if (eb)
+	{
+		fz_free(ctx, eb->index);
+		fz_free(ctx, eb->table);
+	}
+	fz_free(ctx, eb);
+}
+
+static void index_edgebuffer_insert(fz_context *ctx, fz_rasterizer *ras, float fsx, float fsy, float fex, float fey, int rev)
+{
+	fz_edgebuffer *eb = (fz_edgebuffer *)ras;
+	int iminy, imaxy;
+	int height = eb->super.clip.y1 - eb->super.clip.y0;
+
+	if (fsy == fey)
+		return;
+
+	if (fsx < fex)
+	{
+		if (fsx < eb->super.bbox.x0) eb->super.bbox.x0 = fsx;
+		if (fex > eb->super.bbox.x1) eb->super.bbox.x1 = fex;
+	}
+	else
+	{
+		if (fsx > eb->super.bbox.x1) eb->super.bbox.x1 = fsx;
+		if (fex < eb->super.bbox.x0) eb->super.bbox.x0 = fex;
+	}
+	if (fsy < fey)
+	{
+		if (fsy < eb->super.bbox.y0) eb->super.bbox.y0 = fsy;
+		if (fey > eb->super.bbox.y1) eb->super.bbox.y1 = fey;
+	}
+	else
+	{
+		if (fey < eb->super.bbox.y0) eb->super.bbox.y0 = fey;
+		if (fsy > eb->super.bbox.y1) eb->super.bbox.y1 = fsy;
+	}
+
+	/* To strictly match, this should be:
+	 * iminy = int2fixed(float2fixed(fsy))
+	 * imaxy = int2fixed(float2fixed(fsx))
+	 * but this is faster. It can round differently,
+	 * (on some machines at least) hence the iminy--; below.
+	 */
+	iminy = (int)fsy;
+	imaxy = (int)fey;
+
+	if (iminy > imaxy)
+	{
+		int t;
+		t = iminy; iminy = imaxy; imaxy = t;
+	}
+	imaxy++;
+	iminy--;
+
+	imaxy -= eb->super.clip.y0;
+	if (imaxy < 0)
+		return;
+	iminy -= eb->super.clip.y0;
+	if (iminy < 0)
+		iminy = 0;
+	else if (iminy > height)
+		return;
+	if (imaxy > height-1)
+		imaxy = height-1;
+#ifdef DEBUG_SCAN_CONVERTER
+	if (debugging_scan_converter)
+		fprintf(stderr, "%x->%x:%d\n", iminy, imaxy, eb->n);
+#endif
+	eb->index[iminy] += eb->n;
+	eb->index[imaxy+1] -= eb->n;
+}
+
+static void fz_postindex_edgebuffer(fz_context *ctx, fz_rasterizer *r)
+{
+	fz_edgebuffer *eb = (fz_edgebuffer *)r;
+	int height = eb->super.clip.y1 - eb->super.clip.y0 + 1;
+	int n = eb->n;
+	int total = 0;
+	int delta = 0;
+	int i;
+
+	eb->super.fns.insert = (eb->app ? fz_insert_edgebuffer_app : fz_insert_edgebuffer);
+
+	for (i = 0; i < height; i++)
+	{
+		delta += eb->index[i];
+		eb->index[i] = total;
+		total += 1 + delta*n;
+	}
+	assert(delta == 0);
+
+	if (eb->table_cap < total)
+	{
+		eb->table = fz_resize_array(ctx, eb->table, total, sizeof(int));
+		eb->table_cap = total;
+	}
+
+	for (i = 0; i < height; i++)
+	{
+		eb->table[eb->index[i]] = 0;
+	}
+}
+
+static int fz_reset_edgebuffer(fz_context *ctx, fz_rasterizer *r)
+{
+	fz_edgebuffer *eb = (fz_edgebuffer *)r;
+	int height = eb->super.clip.y1 - eb->super.clip.y0 + 1;
+	int n;
+
+	eb->sorted = 0;
+
+	if (eb->index_cap < height)
+	{
+		eb->index = fz_resize_array(ctx, eb->index, height, sizeof(int));
+		eb->index_cap = height;
+	}
+	memset(eb->index, 0, sizeof(int) * height);
+
+	n = 1;
+
+	if (eb->app)
+	{
+		n = 2;
+		eb->cursor[0].saved = 0;
+		eb->cursor[0].unset = 1;
+		eb->cursor[0].can_save = 1;
+		eb->cursor[0].d = DIRN_UNSET;
+		eb->cursor[1].saved = 0;
+		eb->cursor[1].unset = 1;
+		eb->cursor[1].can_save = 1;
+		eb->cursor[1].d = DIRN_UNSET;
+		eb->cursor[2].saved = 0;
+		eb->cursor[2].unset = 1;
+		eb->cursor[2].can_save = 1;
+		eb->cursor[2].d = DIRN_UNSET;
+	}
+
+	eb->n = n;
+
+	eb->super.fns.insert = index_edgebuffer_insert;
+	return 1;
+}
+
+static void mark_line(fz_context *ctx, fz_edgebuffer *eb, fixed sx, fixed sy, fixed ex, fixed ey)
+{
+	int base_y = eb->super.clip.y0;
+	int height = eb->super.clip.y1 - eb->super.clip.y0;
+	int *table = eb->table;
+	int *index = eb->index;
+	int delta;
+	int iy, ih;
+	fixed clip_sy, clip_ey;
+	int dirn = DIRN_UP;
+	int *row;
+
+	if (fixed2int(sy + fixed_half-1) == fixed2int(ey + fixed_half-1))
+		return;
+	if (sy > ey) {
+		int t;
+		t = sy; sy = ey; ey = t;
+		t = sx; sx = ex; ex = t;
+		dirn = DIRN_DOWN;
+	}
+
+	if (fixed2int(sx) < eb->super.bbox.x0)
+		eb->super.bbox.x0 = fixed2int(sx);
+	if (fixed2int(sx + fixed_1 - 1) > eb->super.bbox.x1)
+		eb->super.bbox.x1 = fixed2int(sx + fixed_1 - 1);
+	if (fixed2int(ex) < eb->super.bbox.x0)
+		eb->super.bbox.x0 = fixed2int(ex);
+	if (fixed2int(ex + fixed_1 - 1) > eb->super.bbox.x1)
+		eb->super.bbox.x1 = fixed2int(ex + fixed_1 - 1);
+
+	if (fixed2int(sy) < eb->super.bbox.y0)
+		eb->super.bbox.y0 = fixed2int(sy);
+	if (fixed2int(ey + fixed_1 - 1) > eb->super.bbox.y1)
+		eb->super.bbox.y1 = fixed2int(ey + fixed_1 - 1);
+
+	/* Lines go from sy to ey, closed at the start, open at the end. */
+	/* We clip them to a region to make them closed at both ends. */
+	/* Thus the unset scanline marked (>= sy) is: */
+	clip_sy = ((sy + fixed_half - 1) & ~(fixed_1-1)) | fixed_half;
+	/* The last scanline marked (< ey) is: */
+	clip_ey = ((ey - fixed_half - 1) & ~(fixed_1-1)) | fixed_half;
+	/* Now allow for banding */
+	if (clip_sy < int2fixed(base_y) + fixed_half)
+		clip_sy = int2fixed(base_y) + fixed_half;
+	if (ey <= clip_sy)
+		return;
+	if (clip_ey > int2fixed(base_y + height - 1) + fixed_half)
+		clip_ey = int2fixed(base_y + height - 1) + fixed_half;
+	if (sy > clip_ey)
+		return;
+	delta = clip_sy - sy;
+	if (delta > 0)
+	{
+		int dx = ex - sx;
+		int dy = ey - sy;
+		int advance = (int)(((int64_t)dx * delta + (dy>>1)) / dy);
+		sx += advance;
+		sy += delta;
+	}
+	ex -= sx;
+	ey -= sy;
+	clip_ey -= clip_sy;
+	delta = ey - clip_ey;
+	if (delta > 0)
+	{
+		int advance = (int)(((int64_t)ex * delta + (ey>>1)) / ey);
+		ex -= advance;
+		ey -= delta;
+	}
+	ih = fixed2int(ey);
+	assert(ih >= 0);
+	iy = fixed2int(sy) - base_y;
+#ifdef DEBUG_SCAN_CONVERTER
+	if (debugging_scan_converter)
+		fz_write_printf(ctx, fz_stderr(ctx), "	iy=%x ih=%x\n", iy, ih);
+#endif
+	assert(iy >= 0 && iy < height);
+	/* We always cross at least one scanline */
+	row = &table[index[iy]];
+	*row = (*row)+1; /* Increment the count */
+	row[*row] = (sx&~1) | dirn;
+	if (ih == 0)
+		return;
+	if (ex >= 0) {
+		int x_inc, n_inc, f;
+
+		/* We want to change sx by ex in ih steps. So each step, we add
+		 * ex/ih to sx. That's x_inc + n_inc/ih.
+		 */
+		x_inc = ex/ih;
+		n_inc = ex-(x_inc*ih);
+		f	 = ih>>1;
+		delta = ih;
+		do {
+			int count;
+			iy++;
+			sx += x_inc;
+			f  -= n_inc;
+			if (f < 0) {
+				f += ih;
+				sx++;
+			}
+			assert(iy >= 0 && iy < height);
+			row = &table[index[iy]];
+			count = *row = (*row)+1; /* Increment the count */
+			row[count] = (sx&~1) | dirn;
+		} while (--delta);
+	} else {
+		int x_dec, n_dec, f;
+
+		ex = -ex;
+		/* We want to change sx by ex in ih steps. So each step, we subtract
+		 * ex/ih from sx. That's x_dec + n_dec/ih.
+		 */
+		x_dec = ex/ih;
+		n_dec = ex-(x_dec*ih);
+		f	 = ih>>1;
+		delta = ih;
+		do {
+			int count;
+			iy++;
+			sx -= x_dec;
+			f  -= n_dec;
+			if (f < 0) {
+				f += ih;
+				sx--;
+			}
+			assert(iy >= 0 && iy < height);
+			row = &table[index[iy]];
+			count = *row = (*row)+1; /* Increment the count */
+			row[count] = (sx&~1) | dirn;
+		} while (--delta);
+	}
+}
+
+static void fz_insert_edgebuffer(fz_context *ctx, fz_rasterizer *ras, float fsx, float fsy, float fex, float fey, int rev)
+{
+	fz_edgebuffer *eb = (fz_edgebuffer *)ras;
+	fixed sx = float2fixed(fsx);
+	fixed sy = float2fixed(fsy);
+	fixed ex = float2fixed(fex);
+	fixed ey = float2fixed(fey);
+
+	mark_line(ctx, eb, sx, sy, ex, ey);
+}
+
+static inline void
+cursor_output(fz_edgebuffer * restrict eb, int rev, int iy)
+{
+	int *row;
+	int count;
+	int height = eb->super.clip.y1 - eb->super.clip.y0;
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	rev &= 1; /* Edge label 0 is forwards, 1 and 2 are reverse */
+
+	if (iy >= 0 && iy < height) {
+		if (cr->can_save) {
+			/* Save it for later in case we join up */
+			cr->save_left = cr->left;
+			cr->save_right = cr->right;
+			cr->save_iy = iy;
+			cr->save_d = cr->d;
+			cr->saved = 1;
+		} else {
+			/* Enter it into the table */
+			row = &eb->table[eb->index[iy]];
+			if (cr->d == DIRN_UNSET)
+			{
+				/* Move 0 0; line 10 0; line 0 0; */
+				/* FIXME */
+			}
+			else
+			{
+				*row = count = (*row)+1; /* Increment the count */
+#ifdef DEBUG_SCAN_CONVERTER
+				if (debugging_scan_converter)
+					fprintf(stderr, "row: %x: %x->%x %c\n", iy, cr->left, cr->right, (cr->d^rev) == DIRN_UP ? '^' : (cr->d^rev) == DIRN_DOWN ? 'v' : '-');
+#endif
+				assert(count <= (eb->index[iy+1] - eb->index[iy] - 1)/2);
+				row[2 * count - 1] = (cr->left&~1) | (cr->d ^ rev);
+				row[2 * count] = cr->right;
+			}
+		}
+	}
+	cr->can_save = 0;
+}
+
+static inline void
+cursor_output_inrange(fz_edgebuffer * restrict eb, int rev, int iy)
+{
+	int *row;
+	int count;
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	rev &= 1; /* Edge label 0 is forwards, 1 and 2 are reverse */
+
+	assert(iy >= 0 && iy < eb->super.clip.y1 - eb->super.clip.y0);
+	if (cr->can_save) {
+		/* Save it for later in case we join up */
+		cr->save_left = cr->left;
+		cr->save_right = cr->right;
+		cr->save_iy = iy;
+		cr->save_d = cr->d;
+		cr->saved = 1;
+	} else {
+		/* Enter it into the table */
+		assert(cr->d != DIRN_UNSET);
+
+		row = &eb->table[eb->index[iy]];
+		*row = count = (*row)+1; /* Increment the count */
+#ifdef DEBUG_SCAN_CONVERTER
+			if (debugging_scan_converter)
+				printf("row= %x: %x->%x %c\n", iy, cr->left, cr->right, (cr->d^rev) == DIRN_UP ? '^' : (cr->d^rev) == DIRN_DOWN ? 'v' : '-');
+#endif
+		row[2 * count - 1] = (cr->left&~1) | (cr->d ^ rev);
+		row[2 * count] = cr->right;
+	}
+	cr->can_save = 0;
+}
+
+/* Step the cursor in y, allowing for maybe crossing a scanline */
+static inline void
+cursor_step(fz_edgebuffer * restrict eb, int rev, fixed dy, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+	int new_iy;
+	int base = eb->super.clip.y0;
+	int iy = fixed2int(cr->y) - base;
+
+	cr->y += dy;
+	new_iy = fixed2int(cr->y) - base;
+	if (new_iy != iy) {
+		cursor_output(eb, rev, iy);
+		cr->left = x;
+		cr->right = x;
+	} else {
+		if (x < cr->left)
+			cr->left = x;
+		if (x > cr->right)
+			cr->right = x;
+	}
+}
+
+/* Step the cursor in y, never by enough to cross a scanline. */
+static inline void
+cursor_never_step_vertical(fz_edgebuffer * restrict eb, int rev, fixed dy, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	assert(fixed2int(cr->y+dy) == fixed2int(cr->y));
+
+	cr->y += dy;
+}
+
+/* Step the cursor in y, never by enough to cross a scanline,
+ * knowing that we are moving left, and that the right edge
+ * has already been accounted for. */
+static inline void
+cursor_never_step_left(fz_edgebuffer * restrict eb, int rev, fixed dy, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	assert(fixed2int(cr->y+dy) == fixed2int(cr->y));
+
+	if (x < cr->left)
+		cr->left = x;
+	cr->y += dy;
+}
+
+/* Step the cursor in y, never by enough to cross a scanline,
+ * knowing that we are moving right, and that the left edge
+ * has already been accounted for. */
+static inline void
+cursor_never_step_right(fz_edgebuffer * restrict eb, int rev, fixed dy, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	assert(fixed2int(cr->y+dy) == fixed2int(cr->y));
+
+	if (x > cr->right)
+		cr->right = x;
+	cr->y += dy;
+}
+
+/* Step the cursor in y, always by enough to cross a scanline. */
+static inline void
+cursor_always_step(fz_edgebuffer * restrict eb, int rev, fixed dy, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+	int base = eb->super.clip.y0;
+	int iy = fixed2int(cr->y) - base;
+
+	cursor_output(eb, rev, iy);
+	cr->y += dy;
+	cr->left = x;
+	cr->right = x;
+}
+
+/* Step the cursor in y, always by enough to cross a scanline, as
+ * part of a vertical line, knowing that we are moving from a
+ * position guaranteed to be in the valid y range. */
+static inline void
+cursor_always_step_inrange_vertical(fz_edgebuffer * restrict eb, int rev, fixed dy, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+	int base = eb->super.clip.y0;
+	int iy = fixed2int(cr->y) - base;
+
+	cursor_output(eb, rev, iy);
+	cr->y += dy;
+}
+
+/* Step the cursor in y, always by enough to cross a scanline, as
+ * part of a left moving line, knowing that we are moving from a
+ * position guaranteed to be in the valid y range. */
+static inline void
+cursor_always_inrange_step_left(fz_edgebuffer * restrict eb, int rev, fixed dy, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+	int base = eb->super.clip.y0;
+	int iy = fixed2int(cr->y) - base;
+
+	cr->y += dy;
+	cursor_output_inrange(eb, rev, iy);
+	cr->right = x;
+}
+
+/* Step the cursor in y, always by enough to cross a scanline, as
+ * part of a right moving line, knowing that we are moving from a
+ * position guaranteed to be in the valid y range. */
+static inline void
+cursor_always_inrange_step_right(fz_edgebuffer * restrict eb, int rev, fixed dy, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+	int base = eb->super.clip.y0;
+	int iy = fixed2int(cr->y) - base;
+
+	cr->y += dy;
+	cursor_output_inrange(eb, rev, iy);
+	cr->left = x;
+}
+
+static inline void cursor_init(fz_edgebuffer * restrict eb, int rev, fixed y, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	assert(y >= int2fixed(eb->super.clip.y0) && y <= int2fixed(eb->super.clip.y1));
+
+	cr->y = y;
+	cr->left = x;
+	cr->right = x;
+	cr->d = DIRN_UNSET;
+}
+
+static inline void cursor_left_merge(fz_edgebuffer * restrict eb, int rev, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	if (x < cr->left)
+		cr->left = x;
+}
+
+static inline void cursor_left(fz_edgebuffer * restrict eb, int rev, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	cr->left = x;
+}
+
+static inline void cursor_right_merge(fz_edgebuffer * restrict eb, int rev, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	if (x > cr->right)
+		cr->right = x;
+}
+
+static inline void cursor_right(fz_edgebuffer * restrict eb, int rev, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	cr->right = x;
+}
+
+static inline void cursor_down(fz_edgebuffer * restrict eb, int rev, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+	int base = eb->super.clip.y0;
+
+	if (cr->d == DIRN_UP)
+	{
+		cursor_output(eb, rev, fixed2int(cr->y) - base);
+		cr->left = x;
+		cr->right = x;
+	}
+	cr->d = DIRN_DOWN;
+}
+
+static inline void cursor_up(fz_edgebuffer * restrict eb, int rev, fixed x)
+{
+	cursor_t * restrict cr = &eb->cursor[rev];
+	int base = eb->super.clip.y0;
+
+	if (cr->d == DIRN_DOWN)
+	{
+		cursor_output(eb, rev, fixed2int(cr->y) - base);
+		cr->left = x;
+		cr->right = x;
+	}
+	cr->d = DIRN_UP;
+}
+
+static inline int dirns_match(int d0, int d1)
+{
+	return d0 == d1 || d0 == DIRN_UNSET || d1 == DIRN_UNSET;
+}
+
+static inline int dirn_flip(int d)
+{
+	return d < 0 ? d : d^1;
+}
+
+static inline int dirns_set(int d0, int d1)
+{
+	return d0 != DIRN_UNSET || d1 != DIRN_UNSET;
+}
+
+static inline int dirns_merge(int d0, int d1)
+{
+	if (d0 == DIRN_UNSET)
+		return d1;
+	assert(dirns_match(d0, d1));
+	return d0;
+}
+
+static inline int dirns_merge_opposed(int d0, int d1)
+{
+	if (d0 == DIRN_UNSET)
+		return d1 == DIRN_UP ? DIRN_DOWN : DIRN_UP;
+	assert(dirns_match(d0, d1));
+	return d0;
+}
+
+static void
+cursor_flush(fz_edgebuffer * restrict eb)
+{
+	int base = eb->super.clip.y0;
+	int iy0, iy1, iy2;
+	cursor_t * restrict cr0 = &eb->cursor[0];
+	cursor_t * restrict cr1 = &eb->cursor[1];
+	cursor_t * restrict cr2 = &eb->cursor[2];
+
+	if (cr0->unset)
+	{
+		assert(cr1->unset && cr2->unset);
+		return;
+	}
+
+	iy0 = fixed2int(cr0->y) - base;
+	iy1 = fixed2int(cr1->y) - base;
+	if (!cr2->unset)
+	{
+		assert(!cr1->unset);
+		iy2 = fixed2int(cr2->y) - base;
+		/* Try to merge the end of cursor 0 with the end of cursor 1 */
+		if (iy0 == iy1 && dirns_match(cr0->d, dirn_flip(cr1->d)))
+		{
+			/* Succeeded! Just one to output. */
+			cr0->d = dirns_merge(cr0->d, dirn_flip(cr1->d));
+			if (cr0->left > cr1->left)
+				cr0->left = cr1->left;
+			if (cr0->right < cr1->right)
+				cr0->right = cr1->right;
+			cr1->unset = 1; /* Stop us outputting cursor 1 later */
+		}
+
+		/* Try to merge the end of cursor 2 with the start of cursor 0 */
+		if (cr0->saved)
+		{
+			if (cr0->save_iy == iy2 && dirns_match(cr0->save_d, cr2->d))
+			{
+				cr0->save_d = dirns_merge(cr0->save_d, cr2->d);
+				if (cr0->save_left > cr2->left)
+					cr0->save_left = cr2->left;
+				if (cr0->save_right > cr2->right)
+					cr0->save_right = cr2->right;
+				cr2->unset = 1; /* Stop us outputting cursor 2 later */
+			}
+		}
+		else
+		{
+			/* Maybe cursor 0 never moved from the original pixel */
+			if (iy0 == iy2 && dirns_match(cr0->d, cr2->d))
+			{
+				cr0->d = dirns_merge(cr0->d, cr2->d);
+				if (cr0->left > cr2->left)
+					cr0->left = cr2->left;
+				if (cr0->right > cr2->right)
+					cr0->right = cr2->right;
+				cr2->unset = 1; /* Stop us outputting cursor 2 later */
+			}
+		}
+
+		/* Try to merge the start of cursor 2 with the start of cursor 1 */
+		if (cr1->saved)
+		{
+			if (cr2->saved)
+			{
+				if (cr2->save_iy == cr1->save_iy && dirns_match(cr2->save_d, dirn_flip(cr1->save_d)))
+				{
+					cr2->save_d = dirns_merge(cr2->save_d, dirn_flip(cr1->save_d));
+					if (cr2->save_left > cr1->save_left)
+						cr2->save_left = cr1->save_left;
+					if (cr2->save_right > cr1->save_right)
+						cr2->save_right = cr1->save_right;
+					cr1->saved = 0; /* Don't output cr1->saved again later */
+				}
+			}
+			else if (!cr2->unset)
+			{
+				/* Maybe cursor 2 never moved from the original pixel */
+				if (iy2 == cr1->save_iy && dirns_match(cr2->d, dirn_flip(cr1->save_d)))
+				{
+					cr2->d = dirns_merge(cr2->d, dirn_flip(cr1->save_d));
+					if (cr2->left > cr1->save_left)
+						cr2->left = cr1->save_left;
+					if (cr2->right > cr1->save_right)
+						cr2->right = cr1->save_right;
+					cr1->saved = 0; /* Don't output cr1->saved again later */
+				}
+			}
+		}
+		else if (!cr1->unset)
+		{
+			/* Cursor 1 might not have moved from the original pixel, hence nothing saved */
+			if (cr2->saved)
+			{
+				if (cr2->save_iy == iy1 && dirns_match(cr2->save_d, dirn_flip(cr1->d)))
+				{
+					cr2->save_d = dirns_merge(cr2->save_d, dirn_flip(cr1->d));
+					if (cr2->save_left > cr1->left)
+						cr2->save_left = cr1->left;
+					if (cr2->save_right > cr1->right)
+						cr2->save_right = cr1->right;
+					cr1->unset = 1; /* Stop us outputting cursor 1 later */
+				}
+			}
+			else if (!cr2->unset)
+			{
+				/* Maybe cursor 2 never moved from the original pixel */
+				if (iy2 == iy1 && dirns_match(cr2->d, dirn_flip(cr1->d)))
+				{
+					cr2->d = dirns_merge(cr2->d, dirn_flip(cr1->d));
+					if (cr2->left > cr1->left)
+						cr2->left = cr1->left;
+					if (cr2->right > cr1->right)
+						cr2->right = cr1->right;
+					cr1->unset = 1; /* Stop us outputting cursor 1 later */
+				}
+			}
+		}
+		else
+		{
+			/* Cursor 1 might not have moved from the original pixel, hence nothing saved,
+			 * AND we might have merged it with cursor 0 already! */
+			if (cr2->saved)
+			{
+				if (iy0 == cr2->save_iy && dirns_match(cr0->d, cr2->save_d))
+				{
+					cr0->d = dirns_merge(cr0->d, cr2->save_d);
+					if (cr0->left > cr2->save_left)
+						cr0->left = cr2->save_left;
+					if (cr0->right > cr2->save_right)
+						cr0->right = cr2->save_right;
+					cr2->saved = 0; /* Stop us outputting saved cursor 2 later */
+				}
+			}
+			else if (!cr2->unset)
+			{
+				/* Maybe cursor 2 never moved from the original pixel */
+				if (iy0 == iy2 && dirns_match(cr0->d, cr2->d))
+				{
+					cr0->d = dirns_merge(cr0->d, cr2->d);
+					if (cr0->left > cr2->left)
+						cr0->left = cr2->left;
+					if (cr0->right > cr2->right)
+						cr0->right = cr2->right;
+					cr2->unset = 1; /* Stop us outputting cursor 2 later */
+				}
+			}
+		}
+	}
+	else
+	{
+		/* Try to merge the end of cursor 0 with the start of cursor 0 */
+		if (cr0->saved)
+		{
+			if (iy0 == cr0->save_iy && dirns_match(cr0->d, cr0->save_d))
+			{
+				cr0->d = dirns_merge(cr0->d, cr0->save_d);
+				if (cr0->left > cr0->save_left)
+					cr0->left = cr0->save_left;
+				if (cr0->right > cr0->save_right)
+					cr0->right = cr0->save_right;
+				cr0->saved = 0; /* Stop us outputting saved cursor 0 later */
+			}
+		}
+
+		if (!cr1->unset)
+		{
+			/* Try to merge the end of cursor 1 with the start of cursor 1 */
+			if (cr1->saved)
+			{
+				if (iy1 == cr1->save_iy && dirns_match(cr1->d, cr1->save_d))
+				{
+					cr1->d = dirns_merge(cr1->d, cr1->save_d);
+					if (cr1->left > cr1->save_left)
+						cr1->left = cr1->save_left;
+					if (cr1->right > cr1->save_right)
+						cr1->right = cr1->save_right;
+					cr1->saved = 0; /* Stop us outputting saved cursor 1 later */
+				}
+			}
+		}
+	}
+
+	if (!cr0->unset)
+		cursor_output(eb, 0, iy0);
+	if (cr0->saved)
+	{
+		cr0->left = cr0->save_left;
+		cr0->right = cr0->save_right;
+		cr0->d = cr0->save_d;
+		cursor_output(eb, 0, cr0->save_iy);
+	}
+	if (!cr1->unset)
+		cursor_output(eb, 1, iy1);
+	if (cr1->saved)
+	{
+		cr1->left = cr1->save_left;
+		cr1->right = cr1->save_right;
+		cr1->d = cr1->save_d;
+		cursor_output(eb, 1, cr1->save_iy);
+	}
+	if (!cr2->unset)
+		cursor_output(eb, 2, iy2);
+	if (cr2->saved)
+	{
+		cr2->left = cr2->save_left;
+		cr2->right = cr2->save_right;
+		cr2->d = cr2->save_d;
+		cursor_output(eb, 2, cr2->save_iy);
+	}
+}
+
+static void do_mark_line_app(fz_context *ctx, fz_edgebuffer *eb, fixed sx, fixed sy, fixed ex, fixed ey, int rev)
+{
+	int base_y = eb->super.clip.y0;
+	int height = eb->super.clip.y1 - eb->super.clip.y0;
+	int isy, iey;
+	fixed y_steps;
+	fixed save_sy = sy;
+	fixed save_ex = ex;
+	fixed save_ey = ey;
+	int truncated;
+	cursor_t * restrict cr = &eb->cursor[rev];
+
+	if (cr->unset)
+		cr->y = sy, cr->left = sx, cr->right = sx, cr->unset = 0;
+
+	/* Floating point inaccuracies can cause these not *quite* to be true. */
+	assert(cr->y == sy && cr->left <= sx && cr->right >= sx && cr->d >= DIRN_UNSET && cr->d <= DIRN_DOWN);
+	sy = cr->y;
+	if (cr->left > sx)
+		sx = cr->left;
+	else if (cr->right < sx)
+		sx = cr->right;
+
+	if (sx == ex && sy == ey)
+		return;
+
+	isy = fixed2int(sy) - base_y;
+	iey = fixed2int(ey) - base_y;
+#ifdef DEBUG_SCAN_CONVERTER
+	if (debugging_scan_converter)
+		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);
+#endif
+
+	if (isy < iey) {
+		/* Rising line */
+		if (iey < 0 || isy >= height) {
+			/* All line is outside. */
+			cr->y = ey;
+			cr->left = ex;
+			cr->right = ex;
+			cr->can_save = 0;
+			return;
+		}
+		if (isy < 0) {
+			/* Move sy up */
+			int y = ey - sy;
+			int new_sy = int2fixed(base_y);
+			int dy = new_sy - sy;
+			sx += (int)((((int64_t)(ex-sx))*dy + y/2)/y);
+			sy = new_sy;
+			cursor_init(eb, rev, sy, sx);
+			isy = 0;
+		}
+		truncated = iey > height;
+		if (truncated) {
+			/* Move ey down */
+			int y = ey - sy;
+			int new_ey = int2fixed(base_y + height);
+			int dy = ey - new_ey;
+			save_ex = ex;
+			save_ey = ey;
+			ex -= (int)((((int64_t)(ex-sx))*dy + y/2)/y);
+			ey = new_ey;
+			iey = height;
+		}
+	} else {
+		/* Falling line */
+		if (isy < 0 || iey >= height) {
+			/* All line is outside. */
+			cr->y = ey;
+			cr->left = ex;
+			cr->right = ex;
+			cr->can_save = 0;
+			return;
+		}
+		truncated = iey < 0;
+		if (truncated) {
+			/* Move ey up */
+			int y = ey - sy;
+			int new_ey = int2fixed(base_y);
+			int dy = ey - new_ey;
+			ex -= (int)((((int64_t)(ex-sx))*dy + y/2)/y);
+			ey = new_ey;
+			iey = 0;
+		}
+		if (isy >= height) {
+			/* Move sy down */
+			int y = ey - sy;
+			if (y) {
+				int new_sy = int2fixed(base_y + height);
+				int dy = new_sy - sy;
+				sx += (int)((((int64_t)(ex-sx))*dy + y/2)/y);
+				sy = new_sy;
+				cursor_init(eb, rev, sy, sx);
+				isy = height;
+			}
+		}
+	}
+
+	assert(cr->left <= sx);
+	assert(cr->right >= sx);
+	assert(cr->y == sy);
+
+	/* A note: The code below used to be of the form:
+	 *   if (isy == iey)   ... deal with horizontal lines
+	 *   else if (ey > sy) {
+	 *	 fixed y_steps = ey - sy;
+	 *	  ... deal with rising lines ...
+	 *   } else {
+	 *	 fixed y_steps = ey - sy;
+	 *	 ... deal with falling lines
+	 *   }
+	 * but that lead to problems, for instance, an example seen
+	 * has sx=2aa8e, sy=8aee7, ex=7ffc1686, ey=8003e97a.
+	 * Thus isy=84f, iey=ff80038a. We can see that ey < sy, but
+	 * sy - ey < 0!
+	 * We therefore rejig our code so that the choice between
+	 * cases is done based on the sign of y_steps rather than
+	 * the relative size of ey and sy.
+	 */
+
+	/* First, deal with lines that don't change scanline.
+	 * This accommodates horizontal lines. */
+	if (isy == iey) {
+		if (save_sy == save_ey) {
+			/* Horizontal line. Don't change cr->d, don't flush. */
+		} else if (save_sy > save_ey) {
+			/* Falling line, flush if previous was rising */
+			cursor_down(eb, rev, sx);
+		} else {
+			/* Rising line, flush if previous was falling */
+			cursor_up(eb, rev, sx);
+		}
+		if (sx <= ex) {
+			cursor_left_merge(eb, rev, sx);
+			cursor_right_merge(eb, rev, ex);
+		} else {
+			cursor_left_merge(eb, rev, ex);
+			cursor_right_merge(eb, rev, sx);
+		}
+		cr->y = ey;
+		if (sy > save_ey)
+			goto endFalling;
+	} else if ((y_steps = ey - sy) > 0) {
+		/* We want to change from sy to ey, which are guaranteed to be on
+		 * different scanlines. We do this in 3 phases.
+		 * Phase 1 gets us from sy to the next scanline boundary.
+		 * Phase 2 gets us all the way to the last scanline boundary.
+		 * Phase 3 gets us from the last scanline boundary to ey.
+		 */
+		/* We want to change from sy to ey, which are guaranteed to be on
+		 * different scanlines. We do this in 3 phases.
+		 * Phase 1 gets us from sy to the next scanline boundary. (We may exit after phase 1).
+		 * Phase 2 gets us all the way to the last scanline boundary. (This may be a null operation)
+		 * 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).
+		 */
+		int phase1_y_steps = (-sy) & (fixed_1 - 1);
+		int phase3_y_steps = ey & (fixed_1 - 1);
+
+		cursor_up(eb, rev, sx);
+
+		if (sx == ex) {
+			/* Vertical line. (Rising) */
+
+			/* Phase 1: */
+			cursor_left_merge(eb, rev, sx);
+			cursor_right_merge(eb, rev, sx);
+			if (phase1_y_steps) {
+				/* If phase 1 will move us into a new scanline, then we must
+				 * flush it before we move. */
+				cursor_step(eb, rev, phase1_y_steps, sx);
+				sy += phase1_y_steps;
+				y_steps -= phase1_y_steps;
+				if (y_steps == 0)
+					goto end;
+			}
+
+			/* Phase 3: precalculation */
+			y_steps -= phase3_y_steps;
+
+			/* Phase 2: */
+			y_steps = fixed2int(y_steps);
+			assert(y_steps >= 0);
+			if (y_steps > 0) {
+				cursor_always_step(eb, rev, fixed_1, sx);
+				y_steps--;
+				while (y_steps) {
+					cursor_always_step_inrange_vertical(eb, rev, fixed_1, sx);
+					y_steps--;
+				}
+			}
+
+			/* Phase 3 */
+			assert(cr->left == sx && cr->right == sx);
+			cr->y += phase3_y_steps;
+		} else if (sx < ex) {
+			/* Lines increasing in x. (Rightwards, rising) */
+			int phase1_x_steps, phase3_x_steps;
+			fixed x_steps = ex - sx;
+
+			/* Phase 1: */
+			cursor_left_merge(eb, rev, sx);
+			if (phase1_y_steps) {
+				phase1_x_steps = (int)(((int64_t)x_steps * phase1_y_steps + y_steps/2) / y_steps);
+				sx += phase1_x_steps;
+				cursor_right_merge(eb, rev, sx);
+				x_steps -= phase1_x_steps;
+				cursor_step(eb, rev, phase1_y_steps, sx);
+				sy += phase1_y_steps;
+				y_steps -= phase1_y_steps;
+				if (y_steps == 0)
+					goto end;
+			}
+
+			/* Phase 3: precalculation */
+			phase3_x_steps = (int)(((int64_t)x_steps * phase3_y_steps + y_steps/2) / y_steps);
+			x_steps -= phase3_x_steps;
+			y_steps -= phase3_y_steps;
+			assert((y_steps & (fixed_1 - 1)) == 0);
+
+			/* Phase 2: */
+			y_steps = fixed2int(y_steps);
+			assert(y_steps >= 0);
+			if (y_steps) {
+				/* We want to change sx by x_steps in y_steps steps.
+				 * So each step, we add x_steps/y_steps to sx. That's x_inc + n_inc/y_steps. */
+				int x_inc = x_steps/y_steps;
+				int n_inc = x_steps - (x_inc * y_steps);
+				int f = y_steps/2;
+				int d = y_steps;
+
+				/* Special casing the unset iteration, allows us to simplify
+				 * the following loop. */
+				sx += x_inc;
+				f -= n_inc;
+				if (f < 0)
+					f += d, sx++;
+				cursor_right_merge(eb, rev, sx);
+				cursor_always_step(eb, rev, fixed_1, sx);
+				y_steps--;
+
+				while (y_steps) {
+					sx += x_inc;
+					f -= n_inc;
+					if (f < 0)
+						f += d, sx++;
+					cursor_right(eb, rev, sx);
+					cursor_always_inrange_step_right(eb, rev, fixed_1, sx);
+					y_steps--;
+				};
+			}
+
+			/* Phase 3 */
+			assert(cr->left <= ex && cr->right >= sx);
+			cursor_right(eb, rev, ex);
+			cr->y += phase3_y_steps;
+		} else {
+			/* Lines decreasing in x. (Leftwards, rising) */
+			int phase1_x_steps, phase3_x_steps;
+			fixed x_steps = sx - ex;
+
+			/* Phase 1: */
+			cursor_right_merge(eb, rev, sx);
+			if (phase1_y_steps) {
+				phase1_x_steps = (int)(((int64_t)x_steps * phase1_y_steps + y_steps/2) / y_steps);
+				x_steps -= phase1_x_steps;
+				sx -= phase1_x_steps;
+				cursor_left_merge(eb, rev, sx);
+				cursor_step(eb, rev, phase1_y_steps, sx);
+				sy += phase1_y_steps;
+				y_steps -= phase1_y_steps;
+				if (y_steps == 0)
+					goto end;
+			}
+
+			/* Phase 3: precalculation */
+			phase3_x_steps = (int)(((int64_t)x_steps * phase3_y_steps + y_steps/2) / y_steps);
+			x_steps -= phase3_x_steps;
+			y_steps -= phase3_y_steps;
+			assert((y_steps & (fixed_1 - 1)) == 0);
+
+			/* Phase 2: */
+			y_steps = fixed2int(y_steps);
+			assert(y_steps >= 0);
+			if (y_steps) {
+				/* We want to change sx by x_steps in y_steps steps.
+				 * So each step, we sub x_steps/y_steps from sx. That's x_inc + n_inc/ey. */
+				int x_inc = x_steps/y_steps;
+				int n_inc = x_steps - (x_inc * y_steps);
+				int f = y_steps/2;
+				int d = y_steps;
+
+				/* Special casing the unset iteration, allows us to simplify
+				 * the following loop. */
+				sx -= x_inc;
+				f -= n_inc;
+				if (f < 0)
+					f += d, sx--;
+				cursor_left_merge(eb, rev, sx);
+				cursor_always_step(eb, rev, fixed_1, sx);
+				y_steps--;
+
+				while (y_steps) {
+					sx -= x_inc;
+					f -= n_inc;
+					if (f < 0)
+						f += d, sx--;
+					cursor_left(eb, rev, sx);
+					cursor_always_inrange_step_left(eb, rev, fixed_1, sx);
+					y_steps--;
+				}
+			}
+
+			/* Phase 3 */
+			assert(cr->right >= ex && cr->left <= sx);
+			cursor_left(eb, rev, ex);
+			cr->y += phase3_y_steps;
+		}
+	} else {
+		/* So lines decreasing in y. */
+		/* We want to change from sy to ey, which are guaranteed to be on
+		 * different scanlines. We do this in 3 phases.
+		 * Phase 1 gets us from sy to the next scanline boundary. This never causes an output.
+		 * Phase 2 gets us all the way to the last scanline boundary. This is guaranteed to cause an output.
+		 * Phase 3 gets us from the last scanline boundary to ey. We are guaranteed to have outputted by now.
+		 */
+		int phase1_y_steps = sy & (fixed_1 - 1);
+		int phase3_y_steps = (-ey) & (fixed_1 - 1);
+
+		y_steps = -y_steps;
+		/* Cope with the awkward 0x80000000 case. */
+		if (y_steps < 0)
+		{
+			int mx, my;
+			mx = sx + ((ex-sx)>>1);
+			my = sy + ((ey-sy)>>1);
+			do_mark_line_app(ctx, eb, sx, sy, mx, my, rev);
+			do_mark_line_app(ctx, eb, mx, my, ex, ey, rev);
+			return;
+		}
+
+		cursor_down(eb, rev, sx);
+
+		if (sx == ex) {
+			/* Vertical line. (Falling) */
+
+			/* Phase 1: */
+			cursor_left_merge(eb, rev, sx);
+			cursor_right_merge(eb, rev, sx);
+			if (phase1_y_steps) {
+				/* Phase 1 in a falling line never moves us into a new scanline. */
+				cursor_never_step_vertical(eb, rev, -phase1_y_steps, sx);
+				sy -= phase1_y_steps;
+				y_steps -= phase1_y_steps;
+				if (y_steps == 0)
+					goto endFalling;
+			}
+
+			/* Phase 3: precalculation */
+			y_steps -= phase3_y_steps;
+			assert((y_steps & (fixed_1 - 1)) == 0);
+
+			/* Phase 2: */
+			y_steps = fixed2int(y_steps);
+			assert(y_steps >= 0);
+			if (y_steps) {
+				cursor_always_step(eb, rev, -fixed_1, sx);
+				y_steps--;
+				while (y_steps) {
+					cursor_always_step_inrange_vertical(eb, rev, -fixed_1, sx);
+					y_steps--;
+				}
+			}
+
+			/* Phase 3 */
+			if (phase3_y_steps > 0) {
+				cursor_step(eb, rev, -phase3_y_steps, sx);
+				assert(cr->left == sx && cr->right == sx);
+			}
+		} else if (sx < ex) {
+			/* Lines increasing in x. (Rightwards, falling) */
+			int phase1_x_steps, phase3_x_steps;
+			fixed x_steps = ex - sx;
+
+			/* Phase 1: */
+			cursor_left_merge(eb, rev, sx);
+			if (phase1_y_steps) {
+				phase1_x_steps = (int)(((int64_t)x_steps * phase1_y_steps + y_steps/2) / y_steps);
+				x_steps -= phase1_x_steps;
+				sx += phase1_x_steps;
+				/* Phase 1 in a falling line never moves us into a new scanline. */
+				cursor_never_step_right(eb, rev, -phase1_y_steps, sx);
+				sy -= phase1_y_steps;
+				y_steps -= phase1_y_steps;
+				if (y_steps == 0)
+					goto endFalling;
+			} else
+				cursor_right_merge(eb, rev, sx);
+
+			/* Phase 3: precalculation */
+			phase3_x_steps = (int)(((int64_t)x_steps * phase3_y_steps + y_steps/2) / y_steps);
+			x_steps -= phase3_x_steps;
+			y_steps -= phase3_y_steps;
+			assert((y_steps & (fixed_1 - 1)) == 0);
+
+			/* Phase 2: */
+			y_steps = fixed2int(y_steps);
+			assert(y_steps >= 0);
+			if (y_steps) {
+				/* We want to change sx by x_steps in y_steps steps.
+				 * So each step, we add x_steps/y_steps to sx. That's x_inc + n_inc/ey. */
+				int x_inc = x_steps/y_steps;
+				int n_inc = x_steps - (x_inc * y_steps);
+				int f = y_steps/2;
+				int d = y_steps;
+
+				cursor_always_step(eb, rev, -fixed_1, sx);
+				sx += x_inc;
+				f -= n_inc;
+				if (f < 0)
+					f += d, sx++;
+				cursor_right(eb, rev, sx);
+				y_steps--;
+
+				while (y_steps) {
+					cursor_always_inrange_step_right(eb, rev, -fixed_1, sx);
+					sx += x_inc;
+					f -= n_inc;
+					if (f < 0)
+						f += d, sx++;
+					cursor_right(eb, rev, sx);
+					y_steps--;
+				}
+			}
+
+			/* Phase 3 */
+			if (phase3_y_steps > 0) {
+				cursor_step(eb, rev, -phase3_y_steps, sx);
+				cursor_right(eb, rev, ex);
+				assert(cr->left == sx && cr->right == ex);
+			}
+		} else {
+			/* Lines decreasing in x. (Falling) */
+			int phase1_x_steps, phase3_x_steps;
+			fixed x_steps = sx - ex;
+
+			/* Phase 1: */
+			cursor_right_merge(eb, rev, sx);
+			if (phase1_y_steps) {
+				phase1_x_steps = (int)(((int64_t)x_steps * phase1_y_steps + y_steps/2) / y_steps);
+				x_steps -= phase1_x_steps;
+				sx -= phase1_x_steps;
+				/* Phase 1 in a falling line never moves us into a new scanline. */
+				cursor_never_step_left(eb, rev, -phase1_y_steps, sx);
+				sy -= phase1_y_steps;
+				y_steps -= phase1_y_steps;
+				if (y_steps == 0)
+					goto endFalling;
+			} else
+				cursor_left_merge(eb, rev, sx);
+
+			/* Phase 3: precalculation */
+			phase3_x_steps = (int)(((int64_t)x_steps * phase3_y_steps + y_steps/2) / y_steps);
+			x_steps -= phase3_x_steps;
+			y_steps -= phase3_y_steps;
+			assert((y_steps & (fixed_1 - 1)) == 0);
+
+			/* Phase 2: */
+			y_steps = fixed2int(y_steps);
+			assert(y_steps >= 0);
+			if (y_steps) {
+				/* We want to change sx by x_steps in y_steps steps.
+				 * So each step, we sub x_steps/y_steps from sx. That's x_inc + n_inc/ey. */
+				int x_inc = x_steps/y_steps;
+				int n_inc = x_steps - (x_inc * y_steps);
+				int f = y_steps/2;
+				int d = y_steps;
+
+				cursor_always_step(eb, rev, -fixed_1, sx);
+				sx -= x_inc;
+				f -= n_inc;
+				if (f < 0)
+					f += d, sx--;
+				cursor_left(eb, rev, sx);
+				y_steps--;
+
+				while (y_steps) {
+					cursor_always_inrange_step_left(eb, rev, -fixed_1, sx);
+					sx -= x_inc;
+					f -= n_inc;
+					if (f < 0)
+						f += d, sx--;
+					cursor_left(eb, rev, sx);
+					y_steps--;
+				}
+			}
+
+			/* Phase 3 */
+			if (phase3_y_steps > 0) {
+				cursor_step(eb, rev, -phase3_y_steps, sx);
+				cursor_left(eb, rev, ex);
+				assert(cr->left == ex && cr->right == sx);
+			}
+		}
+endFalling:
+		if (truncated)
+			cursor_output(eb, rev, fixed2int(cr->y) - base_y);
+	}
+
+end:
+	if (truncated) {
+		cr->left = save_ex;
+		cr->right = save_ex;
+		cr->y = save_ey;
+	}
+}
+
+static void mark_line_app(fz_context *ctx, fz_edgebuffer *eb, fixed sx, fixed sy, fixed ex, fixed ey, int rev)
+{
+	if (rev == 1)
+	{
+		fixed t;
+		t = sx, sx = ex, ex = t;
+		t = sy, sy = ey, ey = t;
+	}
+	do_mark_line_app(ctx, eb, sx, sy, ex, ey, rev);
+
+}
+
+static void fz_insert_edgebuffer_app(fz_context *ctx, fz_rasterizer *ras, float fsx, float fsy, float fex, float fey, int rev)
+{
+	fz_edgebuffer *eb = (fz_edgebuffer *)ras;
+	fixed sx = float2fixed(fsx);
+	fixed sy = float2fixed(fsy);
+	fixed ex = float2fixed(fex);
+	fixed ey = float2fixed(fey);
+
+	if (fsx < fex)
+	{
+		if (fsx < eb->super.bbox.x0) eb->super.bbox.x0 = fsx;
+		if (fex > eb->super.bbox.x1) eb->super.bbox.x1 = fex;
+	}
+	else
+	{
+		if (fsx > eb->super.bbox.x1) eb->super.bbox.x1 = fsx;
+		if (fex < eb->super.bbox.x0) eb->super.bbox.x0 = fex;
+	}
+	if (fsy < fey)
+	{
+		if (fsy < eb->super.bbox.y0) eb->super.bbox.y0 = fsy;
+		if (fey > eb->super.bbox.y1) eb->super.bbox.y1 = fey;
+	}
+	else
+	{
+		if (fey < eb->super.bbox.y0) eb->super.bbox.y0 = fey;
+		if (fsy > eb->super.bbox.y1) eb->super.bbox.y1 = fsy;
+	}
+
+	mark_line_app(ctx, eb, sx, sy, ex, ey, rev);
+}
+
+static int intcmp(const void *a, const void *b)
+{
+	return *((int*)a) - *((int *)b);
+}
+
+static void fz_convert_edgebuffer(fz_context *ctx, fz_rasterizer *ras, int eofill, const fz_irect *clip, fz_pixmap *pix, unsigned char *color)
+{
+	fz_edgebuffer *eb = (fz_edgebuffer *)ras;
+	int scanlines = ras->clip.y1 - ras->clip.y0;
+	int i, n, a, pl, pr;
+	int *table = eb->table;
+	int *index = eb->index;
+	uint8_t *out;
+	fz_solid_color_painter_t *fn;
+
+	fn = fz_get_solid_color_painter(pix->n, color, pix->alpha);
+	assert(fn);
+	if (fn == NULL)
+		return;
+
+#ifdef DEBUG_SCAN_CONVERTER
+	if (debugging_scan_converter)
+	{
+		fz_output *err = fz_stderr(ctx);
+		fz_write_printf(ctx, err, "Before sort:\n");
+		fz_edgebuffer_print(ctx, err, eb);
+	}
+#endif
+
+	if (!eb->sorted)
+	{
+		eb->sorted = 1;
+		for (i = 0; i < scanlines; i++)
+		{
+			int *row = &table[index[i]];
+			int rowlen = *row++;
+
+			/* Bubblesort short runs, qsort longer ones. */
+			/* FIXME: Check "6" below */
+			if (rowlen <= 6) {
+				int j, k;
+				for (j = 0; j < rowlen-1; j++)
+				{
+					int t = row[j];
+					for (k = j+1; k < rowlen; k++)
+					{
+						int s = row[k];
+						if (t > s)
+							row[k] = t, t = row[j] = s;
+					}
+				}
+			} else
+				qsort(row, rowlen, sizeof(int), intcmp);
+		}
+
+#ifdef DEBUG_SCAN_CONVERTER
+		if (debugging_scan_converter)
+		{
+			fz_output *err = fz_stderr(ctx);
+			fz_write_printf(ctx, err, "Before filter: %s\n", eofill ? "EO" : "NZ");
+			fz_edgebuffer_print(ctx, err, eb);
+		}
+#endif
+
+		for (i=0; i < scanlines; i++) {
+			int *row = &table[index[i]];
+			int *rowstart = row;
+			int rowlen = *row++;
+			int *rowout = row;
+
+			while (rowlen > 0)
+			{
+				int left, right;
+
+				if (eofill) {
+					/* Even Odd */
+					left  = (*row++)&~1;
+					right = (*row++)&~1;
+					rowlen -= 2;
+				} else {
+					/* Non-Zero */
+					int w;
+
+					left = *row++;
+					w = ((left&1)-1) | (left&1);
+					rowlen--;
+					do {
+						right  = *row++;
+						rowlen--;
+						w += ((right&1)-1) | (right&1);
+					} while (w != 0);
+					left &= ~1;
+					right &= ~1;
+				}
+
+				if (right > left) {
+					*rowout++ = left;
+					*rowout++ = right;
+				}
+			}
+			*rowstart = (rowout-rowstart)-1;
+		}
+	}
+
+#ifdef DEBUG_SCAN_CONVERTER
+	if (debugging_scan_converter)
+	{
+		fz_output *err = fz_stderr(ctx);
+		fz_write_printf(ctx, err, "Before render:\n");
+		fz_edgebuffer_print(ctx, err, eb);
+	}
+#endif
+
+	n = pix->n;
+	a = pix->alpha;
+	pl = fz_maxi(ras->clip.x0, pix->x);
+	pr = fz_mini(ras->clip.x1, pix->x + pix->w);
+	out = pix->samples + pix->stride * fz_maxi(ras->clip.y0 - pix->y, 0) + fz_maxi(ras->clip.x0 - pix->x, 0) * n;
+	if (scanlines > pix->y + pix->h - ras->clip.y0)
+		scanlines = pix->y + pix->h - ras->clip.y0;
+	for (i = fz_maxi(pix->y - ras->clip.y0, 0); i < scanlines; i++) {
+		int *row = &table[index[i]];
+		int  rowlen = *row++;
+
+		while (rowlen > 0) {
+			int left, right;
+
+			left  = *row++;
+			right = *row++;
+			rowlen -= 2;
+			left  = fixed2int(left + fixed_half) - pl;
+			right = fixed2int(right + fixed_half) - pl;
+
+			if (right <= 0)
+				continue;
+			if (left >= pr)
+				continue;
+			if (right > pr)
+				right = pr;
+			if (left < 0)
+				left = 0;
+			right -= left;
+			if (right > 0) {
+				(*fn)(out + left*n, n, right, color, a);
+			}
+		}
+		out += pix->stride;
+	}
+}
+
+static int edgecmp(const void *a, const void *b)
+{
+	int left  = ((int*)a)[0];
+	int right = ((int*)b)[0];
+	left -= right;
+	if (left)
+		return left;
+	return ((int*)a)[1] - ((int*)b)[1];
+}
+
+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_edgebuffer *eb = (fz_edgebuffer *)ras;
+	int scanlines = ras->clip.y1 - ras->clip.y0;
+	int i, n, a, pl, pr;
+	int *table = eb->table;
+	int *index = eb->index;
+	uint8_t *out;
+	fz_solid_color_painter_t *fn;
+
+	fn = fz_get_solid_color_painter(pix->n, color, pix->alpha);
+	assert(fn);
+	if (fn == NULL)
+		return;
+
+#ifdef DEBUG_SCAN_CONVERTER
+	if (debugging_scan_converter)
+	{
+		fz_output *err = fz_stderr(ctx);
+		fz_write_printf(ctx, err, "Before sort:\n");
+		fz_edgebuffer_print_app(ctx, err, eb);
+	}
+#endif
+
+	if (!eb->sorted)
+	{
+		eb->sorted = 1;
+		for (i = 0; i < scanlines; i++)
+		{
+			int *row = &table[index[i]];
+			int rowlen = *row++;
+
+			/* Bubblesort short runs, qsort longer ones. */
+			/* FIXME: Check "6" below */
+			if (rowlen <= 6) {
+				int j, k;
+				for (j = 0; j < rowlen-1; j++) {
+					int * restrict t = &row[j<<1];
+					for (k = j+1; k < rowlen; k++) {
+						int * restrict s = &row[k<<1];
+						int tmp;
+						if (t[0] < s[0])
+							continue;
+						if (t[0] > s[0])
+							tmp = t[0], t[0] = s[0], s[0] = tmp;
+						else if (t[0] <= s[1])
+							continue;
+						tmp = t[1]; t[1] = s[1]; s[1] = tmp;
+					}
+				}
+			} else
+				qsort(row, rowlen, 2*sizeof(int), edgecmp);
+		}
+
+#ifdef DEBUG_SCAN_CONVERTER
+		if (debugging_scan_converter)
+		{
+			fz_output *err = fz_stderr(ctx);
+			fz_write_printf(ctx, err, "Before filter: %s\n", eofill ? "EO" : "NZ");
+			fz_edgebuffer_print_app(ctx, err, eb);
+		}
+#endif
+
+		for (i=0; i < scanlines; i++) {
+			int *row = &table[index[i]];
+			int rowlen = *row++;
+			int *rowstart = row;
+			int *rowout = row;
+			int  ll, lr, rl, rr, wind, marked_to;
+
+			/* Avoid double setting pixels, by keeping where we have marked to. */
+			marked_to = int2fixed(clip->x0);
+			while (rowlen > 0) {
+				if (eofill) {
+					/* Even Odd */
+					ll = (*row++)&~1;
+					lr = *row;
+					row += 2;
+					rowlen-=2;
+
+					/* We will fill solidly from ll to at least lr, possibly further */
+					assert(rowlen >= 0);
+					rr = (*row++);
+					if (rr > lr)
+						lr = rr;
+				} else {
+					/* Non-Zero */
+					int w;
+
+					ll = *row++;
+					lr = *row++;
+					wind = -(ll&1) | 1;
+					ll &= ~1;
+					rowlen--;
+
+					assert(rowlen > 0);
+					do {
+						rl = *row++;
+						rr = *row++;
+						w = -(rl&1) | 1;
+						rl &= ~1;
+						rowlen--;
+						if (rr > lr)
+							lr = rr;
+						wind += w;
+						if (wind == 0)
+							break;
+					} while (rowlen > 0);
+				}
+
+				if (marked_to >= lr)
+					continue;
+
+				if (marked_to >= ll) {
+					if (rowout == rowstart)
+						ll = marked_to;
+					else {
+						rowout -= 2;
+						ll = *rowout;
+					}
+				}
+
+				if (lr > ll) {
+					*rowout++ = ll;
+					*rowout++ = lr;
+					marked_to = lr;
+				}
+			}
+			rowstart[-1] = rowout-rowstart;
+		}
+	}
+
+#ifdef DEBUG_SCAN_CONVERTER
+	if (debugging_scan_converter)
+	{
+		fz_output *err = fz_stderr(ctx);
+		fz_write_printf(ctx, err, "Before render:\n");
+		fz_edgebuffer_print_app(ctx, err, eb);
+	}
+#endif
+
+	n = pix->n;
+	a = pix->alpha;
+	pl = clip->x0;
+	pr = clip->x1 - pl;
+	out = pix->samples + pix->stride * (clip->y0 - pix->y) + (clip->x0 - pix->x) * n;
+	if (scanlines > clip->y1 - ras->clip.y0)
+		scanlines = clip->y1 - ras->clip.y0;
+
+	i = (clip->y0 - ras->clip.y0);
+	if (i < 0)
+		return;
+	for (; i < scanlines; i++) {
+		int *row = &table[index[i]];
+		int  rowlen = *row++;
+
+		while (rowlen > 0) {
+			int left, right;
+
+			left  = *row++;
+			right = *row++;
+			rowlen -= 2;
+			left  = fixed2int(left + fixed_half) - pl;
+			right = fixed2int(right + fixed_half) - pl;
+
+			if (right <= 0)
+				continue;
+			if (left >= pr)
+				break;
+			if (right > pr)
+				right = pr;
+			if (left < 0)
+				left = 0;
+			right -= left;
+			if (right > 0) {
+				(*fn)(out + left*n, n, right, color, a);
+			}
+		}
+		out += pix->stride;
+	}
+}
+
+static void fz_gap_edgebuffer(fz_context *ctx, fz_rasterizer *ras)
+{
+	fz_edgebuffer *eb = (fz_edgebuffer *)ras;
+
+	if (eb->app)
+	{
+#ifdef DEBUG_SCAN_CONVERTER
+		if (0 && debugging_scan_converter)
+		{
+			fz_output *err = fz_stderr(ctx);
+			fz_write_printf(ctx, fz_stderr(ctx), "Pen up move.\n");
+			fz_write_printf(ctx, err, "Before flush:\n");
+			fz_edgebuffer_print_app(ctx, err, eb);
+		}
+#endif
+		cursor_flush(eb);
+		eb->cursor[0].saved = 0;
+		eb->cursor[0].unset = 1;
+		eb->cursor[0].can_save = 1;
+		eb->cursor[0].d = DIRN_UNSET;
+		eb->cursor[1].saved = 0;
+		eb->cursor[1].unset = 1;
+		eb->cursor[1].can_save = 1;
+		eb->cursor[1].d = DIRN_UNSET;
+		eb->cursor[2].saved = 0;
+		eb->cursor[2].unset = 1;
+		eb->cursor[2].can_save = 1;
+		eb->cursor[2].d = DIRN_UNSET;
+	}
+}
+
+static int fz_is_rect_edgebuffer(fz_context *ctx, fz_rasterizer *r)
+{
+	return 0;
+}
+
+static const fz_rasterizer_fns edgebuffer_app =
+{
+	fz_drop_edgebuffer,
+	fz_reset_edgebuffer,
+	fz_postindex_edgebuffer,
+	fz_insert_edgebuffer_app,
+	NULL,
+	fz_gap_edgebuffer,
+	fz_convert_edgebuffer_app,
+	fz_is_rect_edgebuffer,
+	1 /* Reusable */
+};
+
+static const fz_rasterizer_fns edgebuffer_cop =
+{
+	fz_drop_edgebuffer,
+	fz_reset_edgebuffer,
+	fz_postindex_edgebuffer,
+	fz_insert_edgebuffer,
+	NULL,
+	NULL, /* gap */
+	fz_convert_edgebuffer,
+	fz_is_rect_edgebuffer,
+	1 /* Reusable */
+};
+
+fz_rasterizer *
+fz_new_edgebuffer(fz_context *ctx, fz_edgebuffer_rule rule)
+{
+	fz_edgebuffer *eb;
+
+	eb = fz_new_derived_rasterizer(ctx, fz_edgebuffer, rule == FZ_EDGEBUFFER_ANY_PART_OF_PIXEL ? &edgebuffer_app : &edgebuffer_cop);
+	fz_try(ctx)
+	{
+		eb->app = rule == FZ_EDGEBUFFER_ANY_PART_OF_PIXEL;
+	}
+	fz_catch(ctx)
+	{
+		fz_free(ctx, eb);
+		fz_rethrow(ctx);
+	}
+
+	return &eb->super;
+}
diff --git a/source/fitz/draw-imp.h b/source/fitz/draw-imp.h
index 5ce1879e..48d0c7f0 100644
--- a/source/fitz/draw-imp.h
+++ b/source/fitz/draw-imp.h
@@ -316,7 +316,13 @@ void *fz_new_rasterizer_of_size(fz_context *ctx, int size, const fz_rasterizer_f
 
 fz_rasterizer *fz_new_gel(fz_context *ctx);
 
+typedef enum
+{
+	FZ_EDGEBUFFER_ANY_PART_OF_PIXEL,
+	FZ_EDGEBUFFER_CENTER_OF_PIXEL
+} fz_edgebuffer_rule;
 
+fz_rasterizer *fz_new_edgebuffer(fz_context *ctx, fz_edgebuffer_rule rule);
 
 int fz_flatten_fill_path(fz_context *ctx, fz_rasterizer *rast, const fz_path *path, const fz_matrix *ctm, float flatness, const fz_irect *irect, fz_irect *bounds);
 int fz_flatten_stroke_path(fz_context *ctx, fz_rasterizer *rast, const fz_path *path, const fz_stroke_state *stroke, const fz_matrix *ctm, float flatness, float linewidth, const fz_irect *irect, fz_irect *bounds);
diff --git a/source/fitz/draw-rasterize.c b/source/fitz/draw-rasterize.c
index 5998ece4..2231801e 100644
--- a/source/fitz/draw-rasterize.c
+++ b/source/fitz/draw-rasterize.c
@@ -241,7 +241,12 @@ void *fz_new_rasterizer_of_size(fz_context *ctx, int size, const fz_rasterizer_f
 
 fz_rasterizer *fz_new_rasterizer(fz_context *ctx)
 {
-	return fz_new_gel(ctx);
+	if (ctx->aa->bits == 10)
+		return fz_new_edgebuffer(ctx, FZ_EDGEBUFFER_ANY_PART_OF_PIXEL);
+	else if (ctx->aa->bits == 9)
+		return fz_new_edgebuffer(ctx, FZ_EDGEBUFFER_CENTER_OF_PIXEL);
+	else
+		return fz_new_gel(ctx);
 }
 
 void fz_convert_rasterizer(fz_context *ctx, fz_rasterizer *r, int eofill, fz_pixmap *pix, unsigned char *colorbv)