WebSVN – Kolibri OS – Diff – /programs/develop/libraries/cairo/src/cairo-tor-scan-converter.c

  */
 #include "cairoint.h"
 #include "cairo-spans-private.h"
 #include "cairo-error-private.h"
 #include
 #include
 #include
+#include
 #include
 /*-------------------------------------------------------------------------
  * cairo specific config
 /* Set glitter up to use a cairo span renderer to do the coverage
  * blitting. */
 struct pool;
 struct cell_list;
-static glitter_status_t
-blit_with_span_renderer(
-    struct cell_list		*coverages,
-    cairo_span_renderer_t	*span_renderer,
-    struct pool			*span_pool,
-    int				 y,
-    int				 height,
-    int				 xmin,
-    int				 xmax);
-static glitter_status_t
-blit_empty_with_span_renderer (cairo_span_renderer_t *renderer, int y, int height);
-#define GLITTER_BLIT_COVERAGES_ARGS \
-	cairo_span_renderer_t *span_renderer, \
-	struct pool *span_pool
-#define GLITTER_BLIT_COVERAGES(cells, y, height,xmin, xmax) do {	\
-    cairo_status_t status = blit_with_span_renderer (cells,		\
-						     span_renderer,	\
-						     span_pool,		\
-						     y, height,		\
-						     xmin, xmax);	\
-    if (unlikely (status))						\
-	return status;							\
-} while (0)
-#define GLITTER_BLIT_COVERAGES_EMPTY(y, height, xmin, xmax) do {		\
-    cairo_status_t status = blit_empty_with_span_renderer (span_renderer, y, height); \
-    if (unlikely (status))						\
-	return status;							\
-} while (0)
 /*-------------------------------------------------------------------------
  * glitter-paths.h
  */
 glitter_scan_converter_reset(
     glitter_scan_converter_t *converter,
     int xmin, int ymin,
     int xmax, int ymax);
-/* Add a new polygon edge from pixel (x1,y1) to (x2,y2) to the scan
- * converter.  The coordinates represent pixel positions scaled by
- * 2**GLITTER_PIXEL_BITS.  If this function fails then the scan
- * converter should be reset or destroyed.  Dir must be +1 or -1,
- * with the latter reversing the orientation of the edge. */
-I glitter_status_t
-glitter_scan_converter_add_edge (glitter_scan_converter_t *converter,
-				 const cairo_edge_t *edge);
 /* Render the polygon in the scan converter to the given A8 format
  * image raster.  Only the pixels accessible as pixels[y*stride+x] for
  * x,y inside the clip box are written to, where xmin <= x < xmax,
  * ymin <= y < ymax.  The image is assumed to be clear on input.
+ *
  * If nonzero_fill is true then the interior of the polygon is
  * computed with the non-zero fill rule.  Otherwise the even-odd fill
  * rule is used.
+ *
- * The scan converter must be reset or destroyed after this call. */
-#ifndef GLITTER_BLIT_COVERAGES_ARGS
-# define GLITTER_BLIT_COVERAGES_ARGS unsigned char *raster_pixels, long raster_stride
-#endif
-I glitter_status_t
-glitter_scan_converter_render(
-    glitter_scan_converter_t *converter,
-    int nonzero_fill,
-    GLITTER_BLIT_COVERAGES_ARGS);
+ * The scan converter must be reset or destroyed after this call. */
 /*-------------------------------------------------------------------------
  * glitter-paths.c: Implementation internal types
 /* A grid area is a real in [0,1] scaled by 2*GRID_X*GRID_Y.  We want
  * to be able to represent exactly areas of subpixel trapezoids whose
  * vertices are given in grid scaled coordinates.  The scale factor
  * comes from needing to accurately represent the area 0.5*dx*dy of a
  * triangle with base dx and height dy in grid scaled numbers. */
-typedef int grid_area_t;
 #define GRID_XY (2*GRID_X*GRID_Y) /* Unit area on the grid. */
 /* GRID_AREA_TO_ALPHA(area): map [0,GRID_XY] to [0,255]. */
 #if GRID_XY == 510
  * malloc needs to be called to allocate a first real chunk. */
 struct pool {
     /* Chunk we're allocating from. */
     struct _pool_chunk *current;
+    jmp_buf *jmp;
     /* Free list of previously allocated chunks.  All have >= default
      * capacity. */
     struct _pool_chunk *first_free;
 };
 /* A polygon edge. */
 struct edge {
     /* Next in y-bucket or active list. */
+    struct edge *next, *prev;
+    /* Number of subsample rows remaining to scan convert of this
+     * edge. */
+    grid_scaled_y_t height_left;
+    /* Original sign of the edge: +1 for downwards, -1 for upwards
+     * edges.  */
+    int dir;
-    struct edge *next;
+    int vertical;
     /* Current x coordinate while the edge is on the active
      * list. Initialised to the x coordinate of the top of the
     /* The clipped y of the top of the edge. */
     grid_scaled_y_t ytop;
     /* y2-y1 after orienting the edge downwards.  */
-    grid_scaled_y_t dy;
-    /* Number of subsample rows remaining to scan convert of this
-     * edge. */
-    grid_scaled_y_t height_left;
-    /* Original sign of the edge: +1 for downwards, -1 for upwards
-     * edges.  */
-    int dir;
-    int vertical;
+    grid_scaled_y_t dy;
-};
-/* Number of subsample rows per y-bucket. Must be GRID_Y. */
-#define EDGE_Y_BUCKET_HEIGHT GRID_Y
+};
-#define EDGE_Y_BUCKET_INDEX(y, ymin) (((y) - (ymin))/EDGE_Y_BUCKET_HEIGHT)
+#define EDGE_Y_BUCKET_INDEX(y, ymin) (((y) - (ymin))/GRID_Y)
 /* A collection of sorted and vertically clipped edges of the polygon.
  * contribution above and below the intersection point must be
  * computed separately. */
 struct cell {
     struct cell		*next;
     int			 x;
-    grid_area_t		 uncovered_area;
+    int16_t		 uncovered_area;
-    grid_scaled_y_t	 covered_height;
+    int16_t		 covered_height;
 };
 /* A cell list represents the scan line sparsely as cells ordered by
  * ascending x.  It is geared towards scanning the cells in order
  * using an internal cursor. */
-struct cell_list {
-    /* Points to the left-most cell in the scan line. */
-    struct cell *head;
+struct cell_list {
-    /* Sentinel node */
+    /* Sentinel nodes */
-    struct cell tail;
+    struct cell head, tail;
-    /* Cursor state for iterating through the cell list.  Points to
-     * a pointer to the current cell: either &cell_list->head or the next
-     * field of the previous cell. */
+    /* Cursor state for iterating through the cell list. */
-    struct cell **cursor;
+    struct cell *cursor, *rewind;
     /* Cells in the cell list are owned by the cell list and are
      * allocated from this pool.  */
 /* The active list contains edges in the current scan line ordered by
  * the x-coordinate of the intercept of the edge and the scan line. */
 struct active_list {
     /* Leftmost edge on the current scan line. */
-    struct edge *head;
+    struct edge head, tail;
     /* A lower bound on the height of the active edges is used to
      * estimate how soon some active edge ends.	 We can't advance the
      * scan conversion by a full pixel row if an edge ends somewhere
+     * within it. */
-     * within it. */
+    grid_scaled_y_t min_height;
-    grid_scaled_y_t min_height;
+    int is_vertical;
 };
 struct glitter_scan_converter {
+    struct polygon	polygon[1];
+    struct active_list	active[1];
+    struct cell_list	coverages[1];
     struct polygon	polygon[1];
-    struct active_list	active[1];
+    cairo_half_open_span_t *spans;
-    struct cell_list	coverages[1];
+    cairo_half_open_span_t spans_embedded[64];
 	qr.rem += b;
+    }
     return qr;
+}
-static void
+static struct _pool_chunk *
 _pool_chunk_init(
     struct _pool_chunk *p,
     struct _pool_chunk *prev_chunk,
     size_t capacity)
+{
     p->prev_chunk = prev_chunk;
     p->size = 0;
+    p->capacity = capacity;
-    p->capacity = capacity;
+    return p;
+}
-static struct _pool_chunk *
-_pool_chunk_create(
-    struct _pool_chunk *prev_chunk,
+static struct _pool_chunk *
-    size_t size)
+_pool_chunk_create(struct pool *pool, size_t size)
+{
-{
+    struct _pool_chunk *p;
-    struct _pool_chunk *p;
-    size_t size_with_head = size + sizeof(struct _pool_chunk);
-    if (size_with_head < size)
+    p = malloc(size + sizeof(struct _pool_chunk));
-	return NULL;
+    if (unlikely (NULL == p))
-    p = malloc(size_with_head);
+	longjmp (*pool->jmp, _cairo_error (CAIRO_STATUS_NO_MEMORY));
-    if (p)
 	_pool_chunk_init(p, prev_chunk, size);
-    return p;
+    return _pool_chunk_init(p, pool->current, size);
 }
 static void
-pool_init(
+pool_init(struct pool *pool,
-    struct pool *pool,
+	  jmp_buf *jmp,
+	  size_t default_capacity,
-    size_t default_capacity,
+	  size_t embedded_capacity)
     size_t embedded_capacity)
     pool->jmp = jmp;
     pool->current = pool->sentinel;
     pool->first_free = NULL;
 	    p = prev;
+	}
 	p = pool->first_free;
 	pool->first_free = NULL;
     } while (NULL != p);
-    pool_init(pool, 0, 0);
+}
 /* Satisfy an allocation by first allocating a new large enough chunk
  * and adding it to the head of the pool's chunk list. This function
 	    pool->first_free = chunk->prev_chunk;
 	    _pool_chunk_init(chunk, pool->current, chunk->capacity);
+	}
+    }
-    if (NULL == chunk) {
+    if (NULL == chunk)
-	chunk = _pool_chunk_create (pool->current, capacity);
-	if (unlikely (NULL == chunk))
-	    return NULL;
 	chunk = _pool_chunk_create (pool, capacity);
     pool->current = chunk;
     obj = ((unsigned char*)chunk + sizeof(*chunk) + chunk->size);
 cell_list_rewind (struct cell_list *cells)
+{
     cells->cursor = &cells->head;
+}
 /* Rewind the cell list if its cursor has been advanced past x. */
 inline static void
 cell_list_maybe_rewind (struct cell_list *cells, int x)
+{
+    if (x < cells->cursor->x) {
+	cells->cursor = cells->rewind;
-{
+	if (x < cells->cursor->x)
+	    cells->cursor = &cells->head;
+    }
+}
-    struct cell *tail = *cells->cursor;
+inline static void
+cell_list_set_rewind (struct cell_list *cells)
-    if (tail->x > x)
+{
-	cell_list_rewind (cells);
+    cells->rewind = cells->cursor;
+}
 static void
-cell_list_init(struct cell_list *cells)
+cell_list_init(struct cell_list *cells, jmp_buf *jmp)
+{
-    pool_init(cells->cell_pool.base,
+    pool_init(cells->cell_pool.base, jmp,
 *sizeof(struct cell),
 	      sizeof(cells->cell_pool.embedded));
+    cells->tail.next = NULL;
-    cells->tail.next = NULL;
+    cells->tail.x = INT_MAX;
-    cells->tail.x = INT_MAX;
+    cells->head.x = INT_MIN;
-    cells->head = &cells->tail;
+    cells->head.next = &cells->tail;
     cell_list_rewind (cells);
+}
  * row. */
 inline static void
 cell_list_reset (struct cell_list *cells)
+{
     cell_list_rewind (cells);
-    cells->head = &cells->tail;
+    cells->head.next = &cells->tail;
     pool_reset (cells->cell_pool.base);
+}
-static struct cell *
+inline static struct cell *
-cell_list_alloc (struct cell_list *cells,
-		 struct cell **cursor,
+cell_list_alloc (struct cell_list *cells,
 		 struct cell *tail,
 		 int x)
+{
     struct cell *cell;
-    cell = pool_alloc (cells->cell_pool.base, sizeof (struct cell));
-    if (unlikely (NULL == cell))
-	return NULL;
+    cell = pool_alloc (cells->cell_pool.base, sizeof (struct cell));
-    *cursor = cell;
+    cell->next = tail->next;
-    cell->next = tail;
+    tail->next = cell;
-    cell->x = x;
+    cell->x = x;
-    cell->uncovered_area = 0;
+    *(uint32_t *)&cell->uncovered_area = 0;
     cell->covered_height = 0;
     return cell;
+}
  * cell_list_rewind(). Ownership of the returned cell is retained by
  * the cell list. */
 inline static struct cell *
 cell_list_find (struct cell_list *cells, int x)
+{
-    struct cell **cursor = cells->cursor;
+    struct cell *tail = cells->cursor;
+    if (tail->x == x)
-    struct cell *tail;
+	return tail;
     while (1) {
-	UNROLL3({
-	    tail = *cursor;
+	UNROLL3({
-	    if (tail->x >= x) {
+		if (tail->next->x > x)
-		break;
-	    }
+			break;
-	    cursor = &tail->next;
+		tail = tail->next;
 	});
-    }
-    cells->cursor = cursor;
+    }
+    if (tail->x != x)
-    if (tail->x == x)
-	return tail;
+	tail = cell_list_alloc (cells, tail, x);
     return cells->cursor = tail;
     return cell_list_alloc (cells, cursor, tail, x);
+}
  * except with less function call overhead. */
 inline static struct cell_pair
 cell_list_find_pair(struct cell_list *cells, int x1, int x2)
+{
     struct cell_pair pair;
-    struct cell **cursor = cells->cursor;
-    struct cell *cell1;
-    struct cell *cell2;
-    struct cell *newcell;
-    /* Find first cell at x1. */
+    pair.cell1 = cells->cursor;
     while (1) {
-	UNROLL3({
-	    cell1 = *cursor;
+	UNROLL3({
-	    if (cell1->x > x1)
+		if (pair.cell1->next->x > x1)
-		break;
-	    if (cell1->x == x1)
-		goto found_first;
+			break;
-	    cursor = &cell1->next;
+		pair.cell1 = pair.cell1->next;
 	});
+    }
+    if (pair.cell1->x != x1)
-    }
-    /* New first cell at x1. */
-    newcell = pool_alloc (cells->cell_pool.base,
-			  sizeof (struct cell));
-    if (likely (NULL != newcell)) {
-	*cursor = newcell;
-	newcell->next = cell1;
-	newcell->x = x1;
-	newcell->uncovered_area = 0;
-	newcell->covered_height = 0;
+	pair.cell1 = cell_list_alloc (cells, pair.cell1, x1);
-    }
-    cell1 = newcell;
- found_first:
-    /* Find second cell at x2. */
+    pair.cell2 = pair.cell1;
-    while (1) {
-	UNROLL3({
+    while (1) {
-	    cell2 = *cursor;
+	UNROLL3({
-	    if (cell2->x > x2)
-		break;
-	    if (cell2->x == x2)
+		if (pair.cell2->next->x > x2)
-		goto found_second;
+			break;
-	    cursor = &cell2->next;
+		pair.cell2 = pair.cell2->next;
+	});
+    }
-	});
-    }
-    /* New second cell at x2. */
-    newcell = pool_alloc (cells->cell_pool.base,
-			 sizeof (struct cell));
-    if (likely (NULL != newcell)) {
-	*cursor = newcell;
-	newcell->next = cell2;
-	newcell->x = x2;
-	newcell->uncovered_area = 0;
-	newcell->covered_height = 0;
-    }
-    cell2 = newcell;
+    if (pair.cell2->x != x2)
- found_second:
-    cells->cursor = cursor;
+	pair.cell2 = cell_list_alloc (cells, pair.cell2, x2);
     pair.cell1 = cell1;
-    pair.cell2 = cell2;
-    return pair;
-}
-/* Add an unbounded subpixel span covering subpixels >= x to the
- * coverage cells. */
-static glitter_status_t
-cell_list_add_unbounded_subspan (struct cell_list *cells,
-				 grid_scaled_x_t x)
-{
-    struct cell *cell;
-    int ix, fx;
-    GRID_X_TO_INT_FRAC(x, ix, fx);
-    cell = cell_list_find (cells, ix);
-    if (likely (cell != NULL)) {
-	cell->uncovered_area += 2*fx;
-	cell->covered_height++;
-	return GLITTER_STATUS_SUCCESS;
-    }
     cells->cursor = pair.cell2;
-    return GLITTER_STATUS_NO_MEMORY;
+    return pair;
-}
+}
 /* Add a subpixel span covering [x1, x2) to the coverage cells. */
-inline static glitter_status_t
+/* Add a subpixel span covering [x1, x2) to the coverage cells. */
-cell_list_add_subspan(
+inline static void
-    struct cell_list *cells,
+cell_list_add_subspan(struct cell_list *cells,
-    grid_scaled_x_t x1,
+		      grid_scaled_x_t x1,
+		      grid_scaled_x_t x2)
+{
+    int ix1, fx1;
-    grid_scaled_x_t x2)
+    int ix2, fx2;
-    int ix1, fx1;
+    if (x1 == x2)
-    int ix2, fx2;
+	return;
-    GRID_X_TO_INT_FRAC(x1, ix1, fx1);
-    GRID_X_TO_INT_FRAC(x2, ix2, fx2);
+    GRID_X_TO_INT_FRAC(x1, ix1, fx1);
     GRID_X_TO_INT_FRAC(x2, ix2, fx2);
     if (ix1 != ix2) {
-	struct cell_pair p;
+    if (ix1 != ix2) {
-	p = cell_list_find_pair(cells, ix1, ix2);
-	if (likely (p.cell1 != NULL && p.cell2 != NULL)) {
-	    p.cell1->uncovered_area += 2*fx1;
+	struct cell_pair p;
-	    ++p.cell1->covered_height;
+	p = cell_list_find_pair(cells, ix1, ix2);
-	    p.cell2->uncovered_area -= 2*fx2;
-	    --p.cell2->covered_height;
+	p.cell1->uncovered_area += 2*fx1;
-	    return GLITTER_STATUS_SUCCESS;
 	++p.cell1->covered_height;
-    } else {
+	p.cell2->uncovered_area -= 2*fx2;
-	struct cell *cell = cell_list_find(cells, ix1);
-	if (likely (cell != NULL)) {
-	    cell->uncovered_area += 2*(fx1-fx2);
+	--p.cell2->covered_height;
-	    return GLITTER_STATUS_SUCCESS;
+    } else {
 	struct cell *cell = cell_list_find(cells, ix1);
 	cell->uncovered_area += 2*(fx1-fx2);
  * 3) No existing edges end mid-row.
+ *
  * This function depends on being called with all edges from the
  * active list in the order they appear on the list (i.e. with
  * non-decreasing x-coordinate.)  */
-static glitter_status_t
+static void
-cell_list_render_edge(
-    struct cell_list *cells,
+cell_list_render_edge(struct cell_list *cells,
-    struct edge *edge,
+		      struct edge *edge,
-    int sign)
+		      int sign)
+{
     grid_scaled_y_t y1, y2, dy;
     grid_scaled_x_t dx;
     /* Edge is entirely within a column? */
     if (ix1 == ix2) {
 	/* We always know that ix1 is >= the cell list cursor in this
 	 * case due to the no-intersections precondition.  */
 	struct cell *cell = cell_list_find(cells, ix1);
-	if (unlikely (NULL == cell))
-	    return GLITTER_STATUS_NO_MEMORY;
 	cell->covered_height += sign*GRID_Y;
 	cell->uncovered_area += sign*(fx1 + fx2)*GRID_Y;
-	return GLITTER_STATUS_SUCCESS;
+	return;
+    }
     /* Orient the edge left-to-right. */
     dx = x2.quo - x1.quo;
 	 * within a single column because we've checked before calling
 	 * this function that the active list order won't change. */
 	cell_list_maybe_rewind(cells, ix1);
-	pair = cell_list_find_pair(cells, ix1, ix1+1);
-	if (unlikely (!pair.cell1 || !pair.cell2))
-	    return GLITTER_STATUS_NO_MEMORY;
 	pair = cell_list_find_pair(cells, ix1, ix1+1);
 	pair.cell1->uncovered_area += sign*y.quo*(GRID_X + fx1);
 	pair.cell1->covered_height += sign*y.quo;
 	y.quo += y1;
 		cell->uncovered_area += y_skip*GRID_X;
 		cell->covered_height += y_skip;
 		++ix1;
-		cell = cell_list_find(cells, ix1);
-		if (unlikely (NULL == cell))
-		    return GLITTER_STATUS_NO_MEMORY;
+		cell = cell_list_find(cells, ix1);
 	    } while (ix1 != ix2);
 	    pair.cell2 = cell;
+	}
 	pair.cell2->uncovered_area += sign*(y2 - y.quo)*fx2;
-	pair.cell2->covered_height += sign*(y2 - y.quo);
-    }
 	pair.cell2->covered_height += sign*(y2 - y.quo);
     return GLITTER_STATUS_SUCCESS;
 }
 static void
-polygon_init (struct polygon *polygon)
+polygon_init (struct polygon *polygon, jmp_buf *jmp)
 {
     polygon->ymin = polygon->ymax = 0;
     polygon->y_buckets = polygon->y_buckets_embedded;
-    pool_init (polygon->edge_pool.base,
+    pool_init (polygon->edge_pool.base, jmp,
 - sizeof (struct _pool_chunk),
 polygon_reset (struct polygon *polygon,
 	       grid_scaled_y_t ymin,
 	       grid_scaled_y_t ymax)
+{
     unsigned h = ymax - ymin;
-    unsigned num_buckets = EDGE_Y_BUCKET_INDEX(ymax + EDGE_Y_BUCKET_HEIGHT-1,
+    unsigned num_buckets = EDGE_Y_BUCKET_INDEX(ymax + GRID_Y-1, ymin);
-					       ymin);
     pool_reset(polygon->edge_pool.base);
-    if (unlikely (h > 0x7FFFFFFFU - EDGE_Y_BUCKET_HEIGHT))
+    if (unlikely (h > 0x7FFFFFFFU - GRID_Y))
 	goto bail_no_mem; /* even if you could, you wouldn't want to. */
     polygon->ymax = 0;
     return GLITTER_STATUS_NO_MEMORY;
+}
 static void
-_polygon_insert_edge_into_its_y_bucket(
-    struct polygon *polygon,
+_polygon_insert_edge_into_its_y_bucket(struct polygon *polygon,
-    struct edge *e)
+				       struct edge *e)
+{
     unsigned ix = EDGE_Y_BUCKET_INDEX(e->ytop, polygon->ymin);
     struct edge **ptail = &polygon->y_buckets[ix];
     e->next = *ptail;
     *ptail = e;
 }
-inline static glitter_status_t
+inline static void
 polygon_add_edge (struct polygon *polygon,
 		  const cairo_edge_t *edge)
+{
     struct edge *e;
     grid_scaled_x_t dx;
     grid_scaled_y_t dy;
     grid_scaled_y_t ytop, ybot;
-    grid_scaled_y_t ymin = polygon->ymin;
-    grid_scaled_y_t ymax = polygon->ymax;
     grid_scaled_y_t ymin = polygon->ymin;
-    assert (edge->bottom > edge->top);
+    grid_scaled_y_t ymax = polygon->ymax;
-    if (unlikely (edge->top >= ymax || edge->bottom <= ymin))
-	return GLITTER_STATUS_SUCCESS;
     if (unlikely (edge->top >= ymax || edge->bottom <= ymin))
-    e = pool_alloc (polygon->edge_pool.base, sizeof (struct edge));
+	return;
     if (unlikely (NULL == e))
-	return GLITTER_STATUS_NO_MEMORY;
+    e = pool_alloc (polygon->edge_pool.base, sizeof (struct edge));
     _polygon_insert_edge_into_its_y_bucket (polygon, e);
-    e->x.rem -= dy;		/* Bias the remainder for faster
-				 * edge advancement. */
+    e->x.rem -= dy;		/* Bias the remainder for faster
-    return GLITTER_STATUS_SUCCESS;
+				 * edge advancement. */
+}
+static void
+active_list_reset (struct active_list *active)
+{
-static void
+    active->head.vertical = 1;
+    active->head.height_left = INT_MAX;
+    active->head.x.quo = INT_MIN;
+    active->head.prev = NULL;
+    active->head.next = &active->tail;
+    active->tail.prev = &active->head;
+    active->tail.next = NULL;
-active_list_reset (struct active_list *active)
+    active->tail.x.quo = INT_MAX;
+    active->tail.height_left = INT_MAX;
     active->tail.vertical = 1;
-    active->head = NULL;
+    active->min_height = 0;
-    active->min_height = 0;
+    active->is_vertical = 1;
+}
  * to attach the last non-empty list.
  */
 static struct edge *
 merge_sorted_edges (struct edge *head_a, struct edge *head_b)
+{
-    struct edge *head, **next;
+    struct edge *head, **next, *prev;
+    int32_t x;
-    head = head_a;
+    prev = head_a->prev;
+    next = &head;
+    if (head_a->x.quo <= head_b->x.quo) {
+	head = head_a;
+    } else {
+	head = head_b;
+	head_b->prev = prev;
+	goto start_with_b;
-    next = &head;
+    }
+    do {
+	x = head_b->x.quo;
-    while (1) {
+	while (head_a != NULL && head_a->x.quo <= x) {
-	while (head_a != NULL && head_a->x.quo <= head_b->x.quo) {
+	    prev = head_a;
 	    next = &head_a->next;
+	    head_a = head_a->next;
 	    head_a = head_a->next;
 	head_b->prev = prev;
+	*next = head_b;
+	if (head_a == NULL)
-	*next = head_b;
+	    return head;
-	if (head_a == NULL)
+start_with_b:
-	    return head;
+	x = head_a->x.quo;
 	while (head_b != NULL && head_b->x.quo <= x) {
+	    prev = head_b;
-	while (head_b != NULL && head_b->x.quo <= head_a->x.quo) {
+	    next = &head_b->next;
-	    next = &head_b->next;
+	    head_b = head_b->next;
 	    head_b = head_b->next;
-	}
 	head_a->prev = prev;
 	*next = head_a;
 	if (head_b == NULL)
 	    return head;
     struct edge *head_other, *remaining;
     unsigned int i;
-    head_other = list->next;
     head_other = list->next;
     /* Single element list -> return */
     if (head_other == NULL) {
 	*head_out = list;
-	return NULL;
-    }
-    /* Unroll the first iteration of the following loop (halves the number of calls to merge_sorted_edges):
-     *  - Initialize remaining to be the list containing the elements after the second in the input list.
+	return NULL;
      *  - Initialize *head_out to be the sorted list containing the first two element.
      */
-    remaining = head_other->next;
-    if (list->x.quo <= head_other->x.quo) {
+    remaining = head_other->next;
-	*head_out = list;
+    if (list->x.quo <= head_other->x.quo) {
-	/* list->next = head_other; */ /* The input list is already like this. */
+	*head_out = list;
+	head_other->next = NULL;
-	head_other->next = NULL;
+    } else {
+	*head_out = head_other;
-    } else {
+	head_other->prev = list->prev;
-	*head_out = head_other;
+	head_other->next = list;
-	head_other->next = list;
+	list->prev = head_other;
-	list->next = NULL;
-    }
 	list->next = NULL;
     for (i = 0; i < level && remaining; i++) {
 	/* Extract a sorted list of the same size as *head_out
-	 * (2^(i+1) elements) from the list of remaining elements. */
-	remaining = sort_edges (remaining, i, &head_other);
-	*head_out = merge_sorted_edges (*head_out, head_other);
+    for (i = 0; i < level && remaining; i++) {
 	remaining = sort_edges (remaining, i, &head_other);
+	*head_out = merge_sorted_edges (*head_out, head_other);
+    }
+    return remaining;
+}
+ static struct edge *
 merge_unsorted_edges (struct edge *head, struct edge *unsorted)
     /* *head_out now contains (at most) 2^(level+1) elements. */
     sort_edges (unsorted, UINT_MAX, &unsorted);
-    return remaining;
+    return merge_sorted_edges (head, unsorted);
+}
 /* Test if the edges on the active list can be safely advanced by a
  * full row without intersections or any edges ending. */
 inline static int
-active_list_can_step_full_row (struct active_list *active)
+can_do_full_row (struct active_list *active)
+{
+    const struct edge *e;
-    const struct edge *e;
+    int prev_x = INT_MIN;
     int prev_x = INT_MIN;
     /* Recomputes the minimum height of all edges on the active
-    /* Recomputes the minimum height of all edges on the active
+     * list if we have been dropping edges. */
+    if (active->min_height <= 0) {
-     * list if we have been dropping edges. */
+	int min_height = INT_MAX;
-    if (active->min_height <= 0) {
+	int is_vertical = 1;
-	int min_height = INT_MAX;
+	e = active->head.next;
 	while (NULL != e) {
-	e = active->head;
+	    if (e->height_left < min_height)
-	while (NULL != e) {
+		min_height = e->height_left;
-	    if (e->height_left < min_height)
+	    is_vertical &= e->vertical;
-		min_height = e->height_left;
+	    e = e->next;
-	    e = e->next;
+	}
-	active->min_height = min_height;
+	active->is_vertical = is_vertical;
 	active->min_height = min_height;
+    }
     if (active->min_height < GRID_Y)
-	return 0;
+    if (active->min_height < GRID_Y)
+	return 0;
     /* Check for intersections as no edges end during the next row. */
-    e = active->head;
+    /* Check for intersections as no edges end during the next row. */
-    while (NULL != e) {
-	struct quorem x = e->x;
+    for (e = active->head.next; e != &active->tail; e = e->next) {
 	struct quorem x = e->x;
 	if (! e->vertical) {
-	    x.quo += e->dxdy_full.quo;
+	if (! e->vertical) {
-	    x.rem += e->dxdy_full.rem;
+	    x.quo += e->dxdy_full.quo;
-	    if (x.rem >= 0)
+	    x.rem += e->dxdy_full.rem;
-		++x.quo;
+	    if (x.rem >= 0)
-	}
-	if (x.quo <= prev_x)
+		++x.quo;
-	    return 0;
+	}
-	prev_x = x.quo;
-	e = e->next;
-    }
-    return 1;
+	if (x.quo < prev_x)
+	    return 0;
+	prev_x = x.quo;
-}
+    }
+    return 1;
+}
-/* Merges edges on the given subpixel row from the polygon to the
+/* Merges edges on the given subpixel row from the polygon to the
+ * active_list. */
- * active_list. */
+inline static void
+active_list_merge_edges_from_bucket(struct active_list *active,
-inline static void
+				    struct edge *edges)
-active_list_merge_edges_from_polygon(
+{
-    struct active_list *active,
+    active->head.next = merge_unsorted_edges (active->head.next, edges);
+}
-    grid_scaled_y_t y,
-    struct polygon *polygon)
+inline static void
-{
-    /* Split off the edges on the current subrow and merge them into
+polygon_fill_buckets (struct active_list *active,
-     * the active list. */
+		      struct edge *edge,
-    unsigned ix = EDGE_Y_BUCKET_INDEX(y, polygon->ymin);
+		      int y,
+		      struct edge **buckets)
-    int min_height = active->min_height;
+{
-    struct edge *subrow_edges = NULL;
-    struct edge **ptail = &polygon->y_buckets[ix];
     grid_scaled_y_t min_height = active->min_height;
-    while (1) {
+    int is_vertical = active->is_vertical;
-	struct edge *tail = *ptail;
-	if (NULL == tail) break;
 	if (y == tail->ytop) {
-	    *ptail = tail->next;
+    while (edge) {
-	    tail->next = subrow_edges;
+	struct edge *next = edge->next;
+	int suby = edge->ytop - y;
-	    subrow_edges = tail;
+	if (buckets[suby])
-	    if (tail->height_left < min_height)
+	    buckets[suby]->prev = edge;
-		min_height = tail->height_left;
+	edge->next = buckets[suby];
-	} else {
+	edge->prev = NULL;
-	    ptail = &tail->next;
-	}
+	buckets[suby] = edge;
-    }
-    if (subrow_edges) {
+	if (edge->height_left < min_height)
-	sort_edges (subrow_edges, UINT_MAX, &subrow_edges);
+	    min_height = edge->height_left;
-	active->head = merge_sorted_edges (active->head, subrow_edges);
+	is_vertical &= edge->vertical;
-	active->min_height = min_height;
+	edge = next;
+    }
     active->is_vertical = is_vertical;
-/* Advance the edges on the active list by one subsample row by
+    active->min_height = min_height;
  * updating their x positions.  Drop edges from the list that end. */
 inline static void
-active_list_substep_edges(
+inline static void
+sub_row (struct active_list *active,
+	 struct cell_list *coverages,
+	 unsigned int mask)
+{
-    struct active_list *active)
+    struct edge *edge = active->head.next;
+    int xstart = INT_MIN, prev_x = INT_MIN;
+    int winding = 0;
-{
+    cell_list_rewind (coverages);
-    struct edge **cursor = &active->head;
-    grid_scaled_x_t prev_x = INT_MIN;
+    while (&active->tail != edge) {
-    struct edge *unsorted = NULL;
+	struct edge *next = edge->next;
+	int xend = edge->x.quo;
-    while (1) {
-	struct edge *edge;
+	if (--edge->height_left) {
-	UNROLL3({
+	    edge->x.quo += edge->dxdy.quo;
-	    edge = *cursor;
+	    edge->x.rem += edge->dxdy.rem;
-	    if (NULL == edge)
-		break;
-	    if (0 != --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;
-		}
-		if (edge->x.quo < prev_x) {
-		    *cursor = edge->next;
-		    edge->next = unsorted;
-		    unsorted = edge;
-		} else {
-		    prev_x = edge->x.quo;
-		    cursor = &edge->next;
-		}
-	    } else {
-		*cursor = edge->next;
-	    }
-	});
-    }
-    if (unsorted) {
-	sort_edges (unsorted, UINT_MAX, &unsorted);
-	active->head = merge_sorted_edges (active->head, unsorted);
+	    if (edge->x.rem >= 0) {
+		++edge->x.quo;
-    }
+		edge->x.rem -= edge->dy;
-}
+	    }
-inline static glitter_status_t
-apply_nonzero_fill_rule_for_subrow (struct active_list *active,
+	    if (edge->x.quo < prev_x) {
+		struct edge *pos = edge->prev;
+		pos->next = next;
-				    struct cell_list *coverages)
-{
-    struct edge *edge = active->head;
-    int winding = 0;
-    int xstart;
-    int xend;
+		next->prev = pos;
-    int status;
+		do {
-    cell_list_rewind (coverages);
 		    pos = pos->prev;
-    while (NULL != edge) {
-	xstart = edge->x.quo;
+		} while (edge->x.quo < pos->x.quo);
-	winding = edge->dir;
-	while (1) {
+		pos->next->prev = edge;
-	    edge = edge->next;
-	    if (NULL == edge)
-		return cell_list_add_unbounded_subspan (coverages, xstart);
+		edge->next = pos->next;
-	    winding += edge->dir;
-	    if (0 == winding) {
-		if (edge->next == NULL || edge->next->x.quo != edge->x.quo)
-		    break;
+		edge->prev = pos;
-	    }
-	}
-	xend = edge->x.quo;
+		pos->next = edge;
-	status = cell_list_add_subspan (coverages, xstart, xend);
+	    } else
-	if (unlikely (status))
-	    return status;
-	edge = edge->next;
-    }
+		prev_x = edge->x.quo;
-    return GLITTER_STATUS_SUCCESS;
+	    active->min_height = -1;
-}
-static glitter_status_t
-apply_evenodd_fill_rule_for_subrow (struct active_list *active,
-				    struct cell_list *coverages)
-{
-    struct edge *edge = active->head;
-    int xstart;
+	} else {
-    int xend;
-    int status;
-    cell_list_rewind (coverages);
-    while (NULL != edge) {
+	    edge->prev->next = next;
-	xstart = edge->x.quo;
-	while (1) {
-	    edge = edge->next;
-	    if (NULL == edge)
-		return cell_list_add_unbounded_subspan (coverages, xstart);
-	    if (edge->next == NULL || edge->next->x.quo != edge->x.quo)
-		break;
-	    edge = edge->next;
-	}
-	xend = edge->x.quo;
-	status = cell_list_add_subspan (coverages, xstart, xend);
-	if (unlikely (status))
-	    return status;
-	edge = edge->next;
-    }
-    return GLITTER_STATUS_SUCCESS;
-}
-static glitter_status_t
-apply_nonzero_fill_rule_and_step_edges (struct active_list *active,
-					struct cell_list *coverages)
-{
-    struct edge **cursor = &active->head;
-    struct edge *left_edge;
-    int status;
 	    next->prev = edge->prev;
-    left_edge = *cursor;
-    while (NULL != left_edge) {
-	struct edge *right_edge;
-	int winding = left_edge->dir;
+	}
-	left_edge->height_left -= GRID_Y;
-	if (left_edge->height_left)
+	winding += edge->dir;
-	    cursor = &left_edge->next;
+	if ((winding & mask) == 0) {
-	else
+	    if (next->x.quo != xend) {
-	    *cursor = left_edge->next;
+		cell_list_add_subspan (coverages, xstart, xend);
-	while (1) {
-	    right_edge = *cursor;
+		xstart = INT_MIN;
-	    if (NULL == right_edge)
-		return cell_list_render_edge (coverages, left_edge, +1);
-	    right_edge->height_left -= GRID_Y;
-	    if (right_edge->height_left)
-		cursor = &right_edge->next;
-	    else
-		*cursor = right_edge->next;
-	    winding += right_edge->dir;
 	    if (0 == winding) {
-		if (right_edge->next == NULL ||
-		    right_edge->next->x.quo != right_edge->x.quo)
 	} else if (xstart == INT_MIN)
-		    break;
+	    xstart = xend;
-		}
-	    }
+	edge = next;
-	    if (! right_edge->vertical) {
-		right_edge->x.quo += right_edge->dxdy_full.quo;
-		right_edge->x.rem += right_edge->dxdy_full.rem;
-		if (right_edge->x.rem >= 0) {
-		    ++right_edge->x.quo;
-		    right_edge->x.rem -= right_edge->dy;
-		}
-	    }
-	}
-	status = cell_list_render_edge (coverages, left_edge, +1);
-	if (unlikely (status))
-	    return status;
-	status = cell_list_render_edge (coverages, right_edge, -1);
-	if (unlikely (status))
+    }
-	    return status;
-	left_edge = *cursor;
-    }
-    return GLITTER_STATUS_SUCCESS;
-}
-static glitter_status_t
-apply_evenodd_fill_rule_and_step_edges (struct active_list *active,
-					struct cell_list *coverages)
+}
-    struct edge **cursor = &active->head;
-    struct edge *left_edge;
-    int status;
-    left_edge = *cursor;
-    while (NULL != left_edge) {
-	struct edge *right_edge;
-	left_edge->height_left -= GRID_Y;
-	if (left_edge->height_left)
-	    cursor = &left_edge->next;
-	else
-	    *cursor = left_edge->next;
+inline static void dec (struct active_list *a, struct edge *e, int h)
+{
-	while (1) {
+    e->height_left -= h;
-	    right_edge = *cursor;
-	    if (NULL == right_edge)
+    if (e->height_left == 0) {
-		return cell_list_render_edge (coverages, left_edge, +1);
+	e->prev->next = e->next;
-	    right_edge->height_left -= GRID_Y;
-	    if (right_edge->height_left)
-		cursor = &right_edge->next;
-	    else
-		*cursor = right_edge->next;
-	    if (right_edge->next == NULL ||
-		right_edge->next->x.quo != right_edge->x.quo)
-	    {
-		break;
-	    }
-	    if (! right_edge->vertical) {
-		right_edge->x.quo += right_edge->dxdy_full.quo;
-		right_edge->x.rem += right_edge->dxdy_full.rem;
-		if (right_edge->x.rem >= 0) {
-		    ++right_edge->x.quo;
-		    right_edge->x.rem -= right_edge->dy;
-		}
-	    }
-	}
-	status = cell_list_render_edge (coverages, left_edge, +1);
-	if (unlikely (status))
-	    return status;
-	status = cell_list_render_edge (coverages, right_edge, -1);
-	if (unlikely (status))
+	e->next->prev = e->prev;
-	    return status;
+	a->min_height = -1;
-	left_edge = *cursor;
     }
-    return GLITTER_STATUS_SUCCESS;
-}
-/* If the user hasn't configured a coverage blitter, use a default one
+}
- * that blits spans directly to an A8 raster. */
-#ifndef GLITTER_BLIT_COVERAGES
-inline static void
-blit_span(
-    unsigned char *row_pixels,
+inline static void full_step (struct edge *e)
-    int x, unsigned len,
-    grid_area_t coverage)
-{
-    int alpha = GRID_AREA_TO_ALPHA(coverage);
-    if (1 == len) {
+{
-	row_pixels[x] = alpha;
-    }
+    if (! e->vertical) {
-    else {
-	memset(row_pixels + x, alpha, len);
-    }
+	e->x.quo += e->dxdy_full.quo;
-}
-#define GLITTER_BLIT_COVERAGES(coverages, y, height, xmin, xmax) \
-    do { \
+	e->x.rem += e->dxdy_full.rem;
-	int __y = y; \
+	if (e->x.rem >= 0) {
-	int __h = height; \
-	do { \
+	    ++e->x.quo;
-	    blit_cells(coverages, raster_pixels + (__y)*raster_stride, xmin, xmax); \
-	} while (--__h); \
-    } while (0)
+	    e->x.rem -= e->dy;
-static void
 blit_cells(
     struct cell_list *cells,
-    unsigned char *row_pixels,
     int xmin, int xmax)
-{
-    struct cell *cell = cells->head;
+static void
-    int prev_x = xmin;
+full_row (struct active_list *active,
-    int coverage = 0;
+	  struct cell_list *coverages,
-    if (NULL == cell)
+	  unsigned int mask)
 	return;
     struct edge *left = active->head.next;
     while (NULL != cell && cell->x < xmin) {
-	coverage += cell->covered_height;
+    while (&active->tail != left) {
-	cell = cell->next;
+	struct edge *right;
 	int winding;
-    coverage *= GRID_X*2;
 	dec (active, left, GRID_Y);
+	winding = left->dir;
+	right = left->next;
-    for (; NULL != cell; cell = cell->next) {
+	do {
-	int x = cell->x;
+	    dec (active, right, GRID_Y);
-	int area;
+	    winding += right->dir;
-	if (x >= xmax)
+	    if ((winding & mask) == 0 && right->next->x.quo != right->x.quo)
-	    break;
+		break;
-	if (x > prev_x && 0 != coverage) {
-	    blit_span(row_pixels, prev_x, x - prev_x, coverage);
+	    full_step (right);
 	    right = right->next;
-	coverage += cell->covered_height * GRID_X*2;
+	} while (1);
-    glitter_scan_converter_t *converter,
+			     glitter_scan_converter_t *converter,
-    int xmin, int ymin,
+			     int xmin, int ymin,
-    int xmax, int ymax)
+			     int xmax, int ymax)
+{
     glitter_status_t status;
+    int max_num_spans;
     converter->xmin = 0; converter->xmax = 0;
+    converter->ymin = 0; converter->ymax = 0;
+    max_num_spans = xmax - xmin + 1;
+    if (max_num_spans > ARRAY_LENGTH(converter->spans_embedded)) {
+	converter->spans = _cairo_malloc_ab (max_num_spans,
+					     sizeof (cairo_half_open_span_t));
+	if (unlikely (converter->spans == NULL))
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+    } else
-    converter->ymin = 0; converter->ymax = 0;
+	converter->spans = converter->spans_embedded;
     xmin = int_to_grid_scaled_x(xmin);
     ymin = int_to_grid_scaled_y(ymin);
-	long long tmp__ = (long long)(grid_scale) * (in);	\
+    long long tmp__ = (long long)(grid_scale) * (in);	\
-	tmp__ >>= GLITTER_INPUT_BITS;				\
+    tmp__ >>= GLITTER_INPUT_BITS;				\
-	(out) = tmp__;						\
+    (out) = tmp__;						\
 } while (0)
+/* Add a new polygon edge from pixel (x1,y1) to (x2,y2) to the scan
+ * converter.  The coordinates represent pixel positions scaled by
+ * 2**GLITTER_PIXEL_BITS.  If this function fails then the scan
+ * converter should be reset or destroyed.  Dir must be +1 or -1,
+ * with the latter reversing the orientation of the edge. */
-I glitter_status_t
+I void
 glitter_scan_converter_add_edge (glitter_scan_converter_t *converter,
 				 const cairo_edge_t *edge)
+{
     cairo_edge_t e;
     INPUT_TO_GRID_Y (edge->top, e.top);
     INPUT_TO_GRID_Y (edge->bottom, e.bottom);
     if (e.top >= e.bottom)
-	return GLITTER_STATUS_SUCCESS;
+	return;
     /* XXX: possible overflows if GRID_X/Y > 2**GLITTER_INPUT_BITS */
     INPUT_TO_GRID_Y (edge->line.p1.y, e.line.p1.y);
     INPUT_TO_GRID_Y (edge->line.p2.y, e.line.p2.y);
     if (e.line.p1.y == e.line.p2.y)
-	return GLITTER_STATUS_SUCCESS;
+	e.line.p2.y++; /* little fudge to prevent a div-by-zero */
-    INPUT_TO_GRID_X (edge->line.p1.x, e.line.p1.x);
-    INPUT_TO_GRID_X (edge->line.p2.x, e.line.p2.x);
-    e.dir = edge->dir;
-    return polygon_add_edge (converter->polygon, &e);
-}
-#ifndef GLITTER_BLIT_COVERAGES_BEGIN
-# define GLITTER_BLIT_COVERAGES_BEGIN
-#endif
-#ifndef GLITTER_BLIT_COVERAGES_END
-# define GLITTER_BLIT_COVERAGES_END
-#endif
-#ifndef GLITTER_BLIT_COVERAGES_EMPTY
-# define GLITTER_BLIT_COVERAGES_EMPTY(y0, y1, xmin, xmax)
-#endif
-static cairo_bool_t
-active_list_is_vertical (struct active_list *active)
-{
-    struct edge *e;
-    for (e = active->head; e != NULL; e = e->next) {
+    INPUT_TO_GRID_X (edge->line.p1.x, e.line.p1.x);
-	if (! e->vertical)
+    INPUT_TO_GRID_X (edge->line.p2.x, e.line.p2.x);
 	    return FALSE;
     e.dir = edge->dir;
     return TRUE;
+    polygon_add_edge (converter->polygon, &e);
 }
 static void
 step_edges (struct active_list *active, int count)
 {
-    struct edge **cursor = &active->head;
+    struct edge *edge;
-    struct edge *edge;
+    count *= GRID_Y;
     for (edge = active->head.next; edge != &active->tail; edge = edge->next) {
-    for (edge = *cursor; edge != NULL; edge = *cursor) {
+	edge->height_left -= count;
-	edge->height_left -= GRID_Y * count;
+	if (! edge->height_left) {
-	if (edge->height_left)
+	    edge->prev->next = edge->next;
+	    edge->next->prev = edge->prev;
-	    cursor = &edge->next;
+	    active->min_height = -1;
-	else
+	}
 	    *cursor = edge->next;
-    }
-}
-I glitter_status_t
-glitter_scan_converter_render(
-    glitter_scan_converter_t *converter,
-    int nonzero_fill,
+}
-    GLITTER_BLIT_COVERAGES_ARGS)
-{
-    int i, j;
-    int ymax_i = converter->ymax / GRID_Y;
+static glitter_status_t
-    int ymin_i = converter->ymin / GRID_Y;
+blit_a8 (struct cell_list *cells,
-    int xmin_i, xmax_i;
-    int h = ymax_i - ymin_i;
-    struct polygon *polygon = converter->polygon;
-    struct cell_list *coverages = converter->coverages;
-    struct active_list *active = converter->active;
-    xmin_i = converter->xmin / GRID_X;
-    xmax_i = converter->xmax / GRID_X;
-    if (xmin_i >= xmax_i)
-	return GLITTER_STATUS_SUCCESS;
-    /* Let the coverage blitter initialise itself. */
-    GLITTER_BLIT_COVERAGES_BEGIN;
-    /* Render each pixel row. */
+	 cairo_span_renderer_t *renderer,
-    for (i = 0; i < h; i = j) {
+	 cairo_half_open_span_t *spans,
-	int do_full_step = 0;
-	glitter_status_t status = 0;
-	j = i + 1;
+	 int y, int height,
+	 int xmin, int xmax)
+{
+    struct cell *cell = cells->head.next;
-	/* Determine if we can ignore this row or use the full pixel
+    int prev_x = xmin, last_x = -1;
+    int16_t cover = 0, last_cover = 0;
-	 * stepper. */
-	if (GRID_Y == EDGE_Y_BUCKET_HEIGHT && ! polygon->y_buckets[i]) {
+    unsigned num_spans;
-	    if (! active->head) {
-		for (; j < h && ! polygon->y_buckets[j]; j++)
+    if (cell == &cells->tail)
-		    ;
-		GLITTER_BLIT_COVERAGES_EMPTY (i+ymin_i, j-i, xmin_i, xmax_i);
+	return CAIRO_STATUS_SUCCESS;
-		continue;
-	    }
-	    do_full_step = active_list_can_step_full_row (active);
+    /* Skip cells to the left of the clip region. */
-	}
+    while (cell->x < xmin) {
-	if (do_full_step) {
+	cover += cell->covered_height;
-	    /* Step by a full pixel row's worth. */
-	    if (nonzero_fill) {
+	cell = cell->next;
-		status = apply_nonzero_fill_rule_and_step_edges (active,
+    }
-								 coverages);
-	    } else {
+    cover *= GRID_X*2;
-		status = apply_evenodd_fill_rule_and_step_edges (active,
 								 coverages);
-	    }
-	    if (active_list_is_vertical (active)) {
-		while (j < h &&
-		       polygon->y_buckets[j] == NULL &&
-		       active->min_height >= 2*GRID_Y)
-		{
+    /* Form the spans from the coverages and areas. */
+    num_spans = 0;
-		    active->min_height -= GRID_Y;
+    for (; cell->x < xmax; cell = cell->next) {
+	int x = cell->x;
-		    j++;
+	int16_t area;
-		}
-		if (j != i + 1)
+	if (x > prev_x && cover != last_cover) {
-		    step_edges (active, j - (i + 1));
-	    }
+	    spans[num_spans].x = prev_x;
-	} else {
+	    spans[num_spans].coverage = GRID_AREA_TO_ALPHA (cover);
-	    grid_scaled_y_t suby;
+	    last_cover = cover;
-	    /* Subsample this row. */
+	    last_x = prev_x;
-	    for (suby = 0; suby < GRID_Y; suby++) {
+	    ++num_spans;
-		grid_scaled_y_t y = (i+ymin_i)*GRID_Y + suby;
+	}
-		active_list_merge_edges_from_polygon (active, y, polygon);
+	cover += cell->covered_height*GRID_X*2;
-		if (nonzero_fill) {
-		    status |= apply_nonzero_fill_rule_for_subrow (active,
+	area = cover - cell->uncovered_area;
-								  coverages);
-		} else {
-		    status |= apply_evenodd_fill_rule_for_subrow (active,
-								  coverages);
+	if (area != last_cover) {
-		}
+	    spans[num_spans].x = x;
+	    spans[num_spans].coverage = GRID_AREA_TO_ALPHA (area);
-		active_list_substep_edges(active);
-	    }
+	    last_cover = area;
+	    last_x = x;
 	    ++num_spans;
-	if (unlikely (status))
+	}
-	    return status;
+	prev_x = x+1;
+    }
-	GLITTER_BLIT_COVERAGES(coverages, i+ymin_i, j-i, xmin_i, xmax_i);
+    if (prev_x <= xmax && cover != last_cover) {
-	cell_list_reset (coverages);
+	spans[num_spans].x = prev_x;
+	spans[num_spans].coverage = GRID_AREA_TO_ALPHA (cover);
-	if (! active->head)
+	last_cover = cover;
-	    active->min_height = INT_MAX;
+	last_x = prev_x;
-	else
+	++num_spans;
-	    active->min_height -= GRID_Y;
+    }
-    }
+    if (last_x < xmax && last_cover) {
-    /* Clean up the coverage blitter. */
+	spans[num_spans].x = xmax;
-    GLITTER_BLIT_COVERAGES_END;
+	spans[num_spans].coverage = 0;
+	++num_spans;
-    return GLITTER_STATUS_SUCCESS;
+    }
+    /* Dump them into the renderer. */
-/*-------------------------------------------------------------------------
+    return renderer->render_rows (renderer, y, height, spans, num_spans);
  * cairo specific implementation: the coverage blitter and
  * scan converter subclass. */
 #define GRID_AREA_TO_A1(A)  ((GRID_AREA_TO_ALPHA (A) > 127) ? 255 : 0)
-static glitter_status_t
-blit_with_span_renderer (struct cell_list *cells,
-			 cairo_span_renderer_t *renderer,
-			 struct pool *span_pool,
-			 int y, int height,
-			 int xmin, int xmax)
-{
-    struct cell *cell = cells->head;
-    int prev_x = xmin;
-    int cover = 0;
-    cairo_half_open_span_t *spans;
-    unsigned num_spans;
-    if (cell == NULL)
-	return blit_empty_with_span_renderer (renderer, y, height);
-    /* Skip cells to the left of the clip region. */
-    while (cell != NULL && cell->x < xmin) {
-	cover += cell->covered_height;
-	cell = cell->next;
+static glitter_status_t
+blit_a1 (struct cell_list *cells,
-    }
+	 cairo_span_renderer_t *renderer,
-    cover *= GRID_X*2;
+	 cairo_half_open_span_t *spans,
+	 int y, int height,
-    /* Count number of cells remaining. */
-    {
-	struct cell *next = cell;
+	 int xmin, int xmax)
-	num_spans = 1;
+{
-	while (next != NULL) {
+    struct cell *cell = cells->head.next;
-	    next = next->next;
+    int prev_x = xmin, last_x = -1;
-	    ++num_spans;
+    int16_t cover = 0;
     uint8_t coverage, last_cover = 0;
-	num_spans = 2*num_spans;
+    unsigned num_spans;
+    if (cell == &cells->tail)
+	return CAIRO_STATUS_SUCCESS;
-    /* Allocate enough spans for the row. */
+    /* Skip cells to the left of the clip region. */
-    pool_reset (span_pool);
+    while (cell->x < xmin) {
+	cover += cell->covered_height;
-    spans = pool_alloc (span_pool, sizeof(spans[0])*num_spans);
+	cell = cell->next;
     if (unlikely (spans == NULL))
+    cover *= GRID_X*2;
-	return GLITTER_STATUS_NO_MEMORY;
+    /* Form the spans from the coverages and areas. */
     num_spans = 0;
     for (; cell->x < xmax; cell = cell->next) {
-    /* Form the spans from the coverages and areas. */
+	int x = cell->x;
-    for (; cell != NULL; cell = cell->next) {
+	int16_t area;
 	int x = cell->x;
-	int area;
+	coverage = GRID_AREA_TO_A1 (cover);
 	if (x > prev_x && coverage != last_cover) {
-	if (x >= xmax)
+	    last_x = spans[num_spans].x = prev_x;
+	    last_cover = spans[num_spans].coverage = coverage;
+	    ++num_spans;
 	    break;
-	if (x > prev_x) {
+	cover += cell->covered_height*GRID_X*2;
+	area = cover - cell->uncovered_area;
+	coverage = GRID_AREA_TO_A1 (area);
+	if (coverage != last_cover) {
-	    spans[num_spans].x = prev_x;
+	    last_x = spans[num_spans].x = x;
-	    spans[num_spans].coverage = GRID_AREA_TO_ALPHA (cover);
+	    last_cover = spans[num_spans].coverage = coverage;
 	    ++num_spans;
+	}
+	prev_x = x+1;
+    }
+    coverage = GRID_AREA_TO_A1 (cover);
+    if (prev_x <= xmax && coverage != last_cover) {
+	last_x = spans[num_spans].x = prev_x;
+	last_cover = spans[num_spans].coverage = coverage;
+	++num_spans;
+    }
+    if (last_x < xmax && last_cover) {
+	spans[num_spans].x = xmax;
+	spans[num_spans].coverage = 0;
+	++num_spans;
+    }
+    if (num_spans == 1)
+	return CAIRO_STATUS_SUCCESS;
+    /* Dump them into the renderer. */
+    return renderer->render_rows (renderer, y, height, spans, num_spans);
+}
+I void
+glitter_scan_converter_render(glitter_scan_converter_t *converter,
+			      unsigned int winding_mask,
+			      int antialias,
+			      cairo_span_renderer_t *renderer)
+{
+    int i, j;
+    int ymax_i = converter->ymax / GRID_Y;
+    int ymin_i = converter->ymin / GRID_Y;
+    int xmin_i, xmax_i;
+    int h = ymax_i - ymin_i;
+    struct polygon *polygon = converter->polygon;
+    struct cell_list *coverages = converter->coverages;
+    struct active_list *active = converter->active;
+    struct edge *buckets[GRID_Y] = { 0 };
+    xmin_i = converter->xmin / GRID_X;
+    xmax_i = converter->xmax / GRID_X;
+    if (xmin_i >= xmax_i)
+	return;
+    /* Render each pixel row. */
+    for (i = 0; i < h; i = j) {
+	int do_full_row = 0;
+	j = i + 1;
+	/* Determine if we can ignore this row or use the full pixel
+	 * stepper. */
+	if (! polygon->y_buckets[i]) {
+	    if (active->head.next == &active->tail) {
+		active->min_height = INT_MAX;
+		active->is_vertical = 1;
+		for (; j < h && ! polygon->y_buckets[j]; j++)
+		    ;
+		continue;
+	    }
+	    do_full_row = can_do_full_row (active);
+	}
+	if (do_full_row) {
+	    /* Step by a full pixel row's worth. */
+	    full_row (active, coverages, winding_mask);
+	    if (active->is_vertical) {
+		while (j < h &&
+		       polygon->y_buckets[j] == NULL &&
-	}
+		       active->min_height >= 2*GRID_Y)
+		{
+		    active->min_height -= GRID_Y;
+		    j++;
+		}
+		if (j != i + 1)
 		    step_edges (active, j - (i + 1));
 	cover += cell->covered_height*GRID_X*2;
-	area = cover - cell->uncovered_area;
+	} else {
 	    int sub;
 	spans[num_spans].x = x;
+	    polygon_fill_buckets (active,
-	spans[num_spans].coverage = GRID_AREA_TO_ALPHA (area);
-	++num_spans;
-	prev_x = x+1;
+				  polygon->y_buckets[i],
 				  (i+ymin_i)*GRID_Y,
 				  buckets);
     if (prev_x <= xmax) {
     cairo_tor_scan_converter_t *self = converter;
     if (self == NULL) {
 	return;
+    }
     _glitter_scan_converter_fini (self->converter);
-    pool_fini (self->span_pool.base);
     free(self);
+}
-static cairo_status_t
-_cairo_tor_scan_converter_add_edge (void		*converter,
-				    const cairo_point_t *p1,
-				    const cairo_point_t *p2,
-				    int top, int bottom,
-				    int dir)
-{
-    cairo_tor_scan_converter_t *self = converter;
-    cairo_status_t status;
-    cairo_edge_t edge;
-    edge.line.p1 = *p1;
-    edge.line.p2 = *p2;
-    edge.top = top;
-    edge.bottom = bottom;
-    edge.dir = dir;
-    status = glitter_scan_converter_add_edge (self->converter, &edge);
-    if (unlikely (status))
-	return _cairo_scan_converter_set_error (self, _cairo_error (status));
-    return CAIRO_STATUS_SUCCESS;
-}
-static cairo_status_t
+cairo_status_t
 _cairo_tor_scan_converter_add_polygon (void		*converter,
 				       const cairo_polygon_t *polygon)
+{
-    cairo_tor_scan_converter_t *self = converter;
-    cairo_status_t status;
+    cairo_tor_scan_converter_t *self = converter;
+    int i;
-    int i;
+#if 0
-    for (i = 0; i < polygon->num_edges; i++) {
+    FILE *file = fopen ("polygon.txt", "w");
-	status = glitter_scan_converter_add_edge (self->converter,
+    _cairo_debug_print_polygon (file, polygon);
+    fclose (file);
-						  &polygon->edges[i]);
+#endif
-	if (unlikely (status)) {
-	    return _cairo_scan_converter_set_error (self,
-						    _cairo_error (status));
     for (i = 0; i < polygon->num_edges; i++)
 	 glitter_scan_converter_add_edge (self->converter, &polygon->edges[i]);
 				    cairo_span_renderer_t	*renderer)
+{
     cairo_tor_scan_converter_t *self = converter;
     cairo_status_t status;
-   status = glitter_scan_converter_render (self->converter,
-					   self->fill_rule == CAIRO_FILL_RULE_WINDING,
-					   renderer,
-					   self->span_pool.base);
-    if (unlikely (status))
+    if ((status = setjmp (self->jmp)))
+	return _cairo_scan_converter_set_error (self, _cairo_error (status));
+    glitter_scan_converter_render (self->converter,
+				   self->fill_rule == CAIRO_FILL_RULE_WINDING ? ~0 : 1,
-	return _cairo_scan_converter_set_error (self, _cairo_error (status));
+				   self->antialias != CAIRO_ANTIALIAS_NONE,
 				   renderer);
     return CAIRO_STATUS_SUCCESS;
+}
 cairo_scan_converter_t *
 _cairo_tor_scan_converter_create (int			xmin,
 				  int			ymin,
+				  int			xmax,
-				  int			xmax,
+				  int			ymax,
-				  int			ymax,
+				  cairo_fill_rule_t	fill_rule,
-				  cairo_fill_rule_t	fill_rule)
+				  cairo_antialias_t	antialias)
 {
     cairo_tor_scan_converter_t *self;
     cairo_status_t status;
-    self = calloc (1, sizeof(struct _cairo_tor_scan_converter));
+    self = malloc (sizeof(struct _cairo_tor_scan_converter));
     if (unlikely (self == NULL)) {
-	status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
-	goto bail_nomem;
 	status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
-    self->base.destroy = _cairo_tor_scan_converter_destroy;
-    self->base.add_edge = _cairo_tor_scan_converter_add_edge;
-    self->base.add_polygon = _cairo_tor_scan_converter_add_polygon;
-    self->base.generate = _cairo_tor_scan_converter_generate;
+	goto bail_nomem;
+    }
     pool_init (self->span_pool.base,
-* sizeof(self->span_pool.embedded[0]),
+    self->base.destroy = _cairo_tor_scan_converter_destroy;
-	      sizeof(self->span_pool.embedded));
+    self->base.generate = _cairo_tor_scan_converter_generate;
+    _glitter_scan_converter_init (self->converter, &self->jmp);
-    _glitter_scan_converter_init (self->converter);
+    status = glitter_scan_converter_reset (self->converter,
-    status = glitter_scan_converter_reset (self->converter,
+					   xmin, ymin, xmax, ymax);
-					   xmin, ymin, xmax, ymax);
+    if (unlikely (status))

Subversion Repositories Kolibri OS

(root)/programs/develop/libraries/cairo/src/cairo-tor-scan-converter.c – Rev 1892 → 3959