From 6346f1621916916cb7064251f38c1f770012a7a8 Mon Sep 17 00:00:00 2001
From: Massimo Valentini <mvalentini@src.gnome.org>
Date: Tue, 30 Sep 2014 06:19:50 +0200
Subject: [PATCH] cairo-tor-scan-converter is off by half of a subrow

---
 src/cairo-tor-scan-converter.c | 76 +++++++++++++++++++++++++++++++-----------
 1 file changed, 57 insertions(+), 19 deletions(-)

diff --git a/src/cairo-tor-scan-converter.c b/src/cairo-tor-scan-converter.c
index 89ef20f..7f79c07 100644
--- a/src/cairo-tor-scan-converter.c
+++ b/src/cairo-tor-scan-converter.c
@@ -1012,7 +1012,7 @@ polygon_add_edge (struct polygon *polygon,
 	e->dxdy_full.rem = 0;
     } else {
 	e->vertical = FALSE;
-	e->dxdy = floored_divrem (dx, dy);
+	e->dxdy = floored_divrem (dx, 2 * dy);
 	if (ytop == edge->line.p1.y) {
 	    e->x.quo = edge->line.p1.x;
 	    e->x.rem = 0;
@@ -1041,11 +1041,19 @@ active_list_reset (struct active_list *active)
     active->head.vertical = 1;
     active->head.height_left = INT_MAX;
     active->head.x.quo = INT_MIN;
+    active->head.x.rem = -1;
+    active->head.dxdy.quo = 0;
+    active->head.dxdy.rem = 0;
+    active->head.dy = 1;
     active->head.prev = NULL;
     active->head.next = &active->tail;
     active->tail.prev = &active->head;
     active->tail.next = NULL;
     active->tail.x.quo = INT_MAX;
+    active->tail.x.rem = -1;
+    active->tail.dxdy.quo = 0;
+    active->tail.dxdy.rem = 0;
+    active->tail.dy = 1;
     active->tail.height_left = INT_MAX;
     active->tail.vertical = 1;
     active->min_height = 0;
@@ -1058,6 +1066,15 @@ active_list_init(struct active_list *active)
     active_list_reset(active);
 }
 
+inline static int
+half_subrow_later (const struct quorem x,
+                   const struct edge* e)
+{
+  int rem = 2 * x.rem + e->dxdy.rem;
+
+  return ((x.quo + e->dxdy.quo + (rem >= -e->dy))) ;
+}
+
 /*
  * Merge two sorted edge lists.
  * Input:
@@ -1084,7 +1101,7 @@ merge_sorted_edges (struct edge *head_a, struct edge *head_b)
 
     prev = head_a->prev;
     next = &head;
-    if (head_a->x.quo <= head_b->x.quo) {
+    if (half_subrow_later (head_a->x, head_a) <= half_subrow_later (head_b->x, head_b)) {
 	head = head_a;
     } else {
 	head = head_b;
@@ -1093,8 +1110,8 @@ merge_sorted_edges (struct edge *head_a, struct edge *head_b)
     }
 
     do {
-	x = head_b->x.quo;
-	while (head_a != NULL && head_a->x.quo <= x) {
+	x = half_subrow_later (head_b->x, head_b);
+	while (head_a != NULL && half_subrow_later (head_a->x, head_a) <= x) {
 	    prev = head_a;
 	    next = &head_a->next;
 	    head_a = head_a->next;
@@ -1106,8 +1123,8 @@ merge_sorted_edges (struct edge *head_a, struct edge *head_b)
 	    return head;
 
 start_with_b:
-	x = head_a->x.quo;
-	while (head_b != NULL && head_b->x.quo <= x) {
+	x = half_subrow_later (head_a->x, head_a);
+	while (head_b != NULL && half_subrow_later (head_b->x, head_b) <= x) {
 	    prev = head_b;
 	    next = &head_b->next;
 	    head_b = head_b->next;
@@ -1153,7 +1170,7 @@ sort_edges (struct edge *list,
     }
 
     remaining = head_other->next;
-    if (list->x.quo <= head_other->x.quo) {
+    if (half_subrow_later (list->x, list) <= half_subrow_later (head_other->x, head_other)) {
 	*head_out = list;
 	head_other->next = NULL;
     } else {
@@ -1212,6 +1229,9 @@ can_do_full_row (struct active_list *active)
     for (e = active->head.next; e != &active->tail; e = e->next) {
 	struct quorem x = e->x;
 
+	if (x.quo < e->prev->x.quo)
+	  return 0;
+
 	if (! e->vertical) {
 	    x.quo += e->dxdy_full.quo;
 	    x.rem += e->dxdy_full.rem;
@@ -1264,6 +1284,22 @@ polygon_fill_buckets (struct active_list *active,
     active->min_height = min_height;
 }
 
+inline static struct quorem
+a_subrow_later (const struct edge *e)
+{
+    struct quorem r;
+    int rem = 2 * e->x.rem  + e->dxdy.rem;
+
+    r.quo = e->x.quo + e->dxdy.quo + (rem >= 0);
+    r.rem = (rem >= 0) ? rem - 2 * e->dy : rem;
+
+    rem = r.rem + e->dxdy.rem;
+    r.quo = r.quo + e->dxdy.quo + (rem >= 0);
+    r.rem = ((rem >= 0) ? rem - 2 * e->dy : rem) / 2;
+
+    return r;
+}
+
 inline static void
 sub_row (struct active_list *active,
 	 struct cell_list *coverages,
@@ -1277,39 +1313,41 @@ sub_row (struct active_list *active,
 
     while (&active->tail != edge) {
 	struct edge *next = edge->next;
-	int xend = edge->x.quo;
+	int xend = half_subrow_later (edge->x, edge);
 
 	if (--edge->height_left) {
-	    edge->x.quo += edge->dxdy.quo;
-	    edge->x.rem += edge->dxdy.rem;
-	    if (edge->x.rem >= 0) {
-		++edge->x.quo;
-		edge->x.rem -= edge->dy;
-	    }
+	    int next_x;
+
+	    edge->x = a_subrow_later (edge);
+	    next_x = half_subrow_later (edge->x, edge);
 
-	    if (edge->x.quo < prev_x) {
+	    if (next_x < prev_x) {
 		struct edge *pos = edge->prev;
 		pos->next = next;
 		next->prev = pos;
 		do {
 		    pos = pos->prev;
-		} while (edge->x.quo < pos->x.quo);
+		} while (next_x < half_subrow_later (pos->x, pos));
 		pos->next->prev = edge;
 		edge->next = pos->next;
 		edge->prev = pos;
 		pos->next = edge;
 	    } else
-		prev_x = edge->x.quo;
-	    active->min_height = -1;
+		prev_x = next_x;
 	} else {
 	    edge->prev->next = next;
 	    next->prev = edge->prev;
+	    active->min_height = -1;
 	}
 
 	winding += edge->dir;
 	if ((winding & mask) == 0) {
-	    if (next->x.quo != xend) {
+	    struct quorem nx = a_subrow_later (next);
+
+	    if (half_subrow_later (nx, next) != xend) {
+
 		cell_list_add_subspan (coverages, xstart, xend);
+
 		xstart = INT_MIN;
 	    }
 	} else if (xstart == INT_MIN)
-- 
1.9.3