Subversion Repositories Kolibri OS

/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */

/* glitter-paths - polygon scan converter

 *

 * Copyright (c) 2008  M Joonas Pihlaja

 * Copyright (c) 2007  David Turner

 *

 * Permission is hereby granted, free of charge, to any person

 * obtaining a copy of this software and associated documentation

 * files (the "Software"), to deal in the Software without

 * restriction, including without limitation the rights to use,

 * copy, modify, merge, publish, distribute, sublicense, and/or sell

 * copies of the Software, and to permit persons to whom the

 * Software is furnished to do so, subject to the following

 * conditions:

 *

 * The above copyright notice and this permission notice shall be

 * included in all copies or substantial portions of the Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES

 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT

 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,

 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

 * OTHER DEALINGS IN THE SOFTWARE.

 */

/* This is the Glitter paths scan converter incorporated into cairo.

 * The source is from commit 734c53237a867a773640bd5b64816249fa1730f8

 * of

 *

 *   http://gitweb.freedesktop.org/?p=users/joonas/glitter-paths

 */

/* Glitter-paths is a stand alone polygon rasteriser derived from

 * David Turner's reimplementation of Tor Anderssons's 15x17

 * supersampling rasteriser from the Apparition graphics library.  The

 * main new feature here is cheaply choosing per-scan line between

 * doing fully analytical coverage computation for an entire row at a

 * time vs. using a supersampling approach.

 *

 * David Turner's code can be found at

 *

 *   http://david.freetype.org/rasterizer-shootout/raster-comparison-20070813.tar.bz2

 *

 * In particular this file incorporates large parts of ftgrays_tor10.h

 * from raster-comparison-20070813.tar.bz2

 */

/* Overview

 *

 * A scan converter's basic purpose to take polygon edges and convert

 * them into an RLE compressed A8 mask.  This one works in two phases:

 * gathering edges and generating spans.

 *

 * 1) As the user feeds the scan converter edges they are vertically

 * clipped and bucketted into a _polygon_ data structure.  The edges

 * are also snapped from the user's coordinates to the subpixel grid

 * coordinates used during scan conversion.

 *

 *     user

 *      |

 *      | edges

 *      V

 *    polygon buckets

 *

 * 2) Generating spans works by performing a vertical sweep of pixel

 * rows from top to bottom and maintaining an _active_list_ of edges

 * that intersect the row.  From the active list the fill rule

 * determines which edges are the left and right edges of the start of

 * each span, and their contribution is then accumulated into a pixel

 * coverage list (_cell_list_) as coverage deltas.  Once the coverage

 * deltas of all edges are known we can form spans of constant pixel

 * coverage by summing the deltas during a traversal of the cell list.

 * At the end of a pixel row the cell list is sent to a coverage

 * blitter for rendering to some target surface.

 *

 * The pixel coverages are computed by either supersampling the row

 * and box filtering a mono rasterisation, or by computing the exact

 * coverages of edges in the active list.  The supersampling method is

 * used whenever some edge starts or stops within the row or there are

 * edge intersections in the row.

 *

 *   polygon bucket for       \

 *   current pixel row        |

 *      |                     |

 *      | activate new edges  |  Repeat GRID_Y times if we

 *      V                     \  are supersampling this row,

 *   active list              /  or just once if we're computing

 *      |                     |  analytical coverage.

 *      | coverage deltas     |

 *      V                     |

 *   pixel coverage list     /

 *      |

 *      V

 *   coverage blitter

 */

#include "cairoint.h"

#include "cairo-spans-private.h"

#include "cairo-error-private.h"

#include 

#include 

#include 

#include 

#include 

/* The input coordinate scale and the rasterisation grid scales. */

#define GLITTER_INPUT_BITS CAIRO_FIXED_FRAC_BITS

#define GRID_X_BITS CAIRO_FIXED_FRAC_BITS

#define GRID_Y 15

/* Set glitter up to use a cairo span renderer to do the coverage

 * blitting. */

struct pool;

struct cell_list;

/*-------------------------------------------------------------------------

 * glitter-paths.h

 */

/* "Input scaled" numbers are fixed precision reals with multiplier

 * 2**GLITTER_INPUT_BITS.  Input coordinates are given to glitter as

 * pixel scaled numbers.  These get converted to the internal grid

 * scaled numbers as soon as possible. Internal overflow is possible

 * if GRID_X/Y inside glitter-paths.c is larger than

 * 1<

#ifndef GLITTER_INPUT_BITS

#  define GLITTER_INPUT_BITS 8

#endif

#define GLITTER_INPUT_SCALE (1<

typedef int glitter_input_scaled_t;

/* Opaque type for scan converting. */

typedef struct glitter_scan_converter glitter_scan_converter_t;

/*-------------------------------------------------------------------------

 * glitter-paths.c: Implementation internal types

 */

#include 

#include 

#include 

/* All polygon coordinates are snapped onto a subsample grid. "Grid

 * scaled" numbers are fixed precision reals with multiplier GRID_X or

 * GRID_Y. */

typedef int grid_scaled_t;

typedef int grid_scaled_x_t;

typedef int grid_scaled_y_t;

/* Default x/y scale factors.

 *  You can either define GRID_X/Y_BITS to get a power-of-two scale

 *  or define GRID_X/Y separately. */

#if !defined(GRID_X) && !defined(GRID_X_BITS)

#  define GRID_X_BITS 8

#endif

#if !defined(GRID_Y) && !defined(GRID_Y_BITS)

#  define GRID_Y 15

#endif

/* Use GRID_X/Y_BITS to define GRID_X/Y if they're available. */

#ifdef GRID_X_BITS

#  define GRID_X (1 << GRID_X_BITS)

#endif

#ifdef GRID_Y_BITS

#  define GRID_Y (1 << GRID_Y_BITS)

#endif

/* The GRID_X_TO_INT_FRAC macro splits a grid scaled coordinate into

 * integer and fractional parts. The integer part is floored. */

#if defined(GRID_X_TO_INT_FRAC)

  /* do nothing */

#elif defined(GRID_X_BITS)

#  define GRID_X_TO_INT_FRAC(x, i, f) \

	_GRID_TO_INT_FRAC_shift(x, i, f, GRID_X_BITS)

#else

#  define GRID_X_TO_INT_FRAC(x, i, f) \

	_GRID_TO_INT_FRAC_general(x, i, f, GRID_X)

#endif

#define _GRID_TO_INT_FRAC_general(t, i, f, m) do {	\

    (i) = (t) / (m);					\

    (f) = (t) % (m);					\

    if ((f) < 0) {					\

	--(i);						\

	(f) += (m);					\

    }							\

} while (0)

#define _GRID_TO_INT_FRAC_shift(t, i, f, b) do {	\

    (f) = (t) & ((1 << (b)) - 1);			\

    (i) = (t) >> (b);					\

} while (0)

/* 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

#  define GRID_AREA_TO_ALPHA(c)	  (((c)+1) >> 1)

#elif GRID_XY == 255

#  define  GRID_AREA_TO_ALPHA(c)  (c)

#elif GRID_XY == 64

#  define  GRID_AREA_TO_ALPHA(c)  (((c) << 2) | -(((c) & 0x40) >> 6))

#elif GRID_XY == 128

#  define  GRID_AREA_TO_ALPHA(c)  ((((c) << 1) | -((c) >> 7)) & 255)

#elif GRID_XY == 256

#  define  GRID_AREA_TO_ALPHA(c)  (((c) | -((c) >> 8)) & 255)

#elif GRID_XY == 15

#  define  GRID_AREA_TO_ALPHA(c)  (((c) << 4) + (c))

#elif GRID_XY == 2*256*15

#  define  GRID_AREA_TO_ALPHA(c)  (((c) + ((c)<<4) + 256) >> 9)

#else

#  define  GRID_AREA_TO_ALPHA(c)  (((c)*255 + GRID_XY/2) / GRID_XY)

#endif

#define UNROLL3(x) x x x

struct quorem {

    int32_t quo;

    int32_t rem;

};

/* Header for a chunk of memory in a memory pool. */

struct _pool_chunk {

    /* # bytes used in this chunk. */

    size_t size;

    /* # bytes total in this chunk */

    size_t capacity;

    /* Pointer to the previous chunk or %NULL if this is the sentinel

     * chunk in the pool header. */

    struct _pool_chunk *prev_chunk;

    /* Actual data starts here.	 Well aligned for pointers. */

};

/* A memory pool.  This is supposed to be embedded on the stack or

 * within some other structure.	 It may optionally be followed by an

 * embedded array from which requests are fulfilled until

 * 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;

    /* The default capacity of a chunk. */

    size_t default_capacity;

    /* Header for the sentinel chunk.  Directly following the pool

     * struct should be some space for embedded elements from which

     * the sentinel chunk allocates from. */

    struct _pool_chunk sentinel[1];

};

/* A polygon edge. */

struct edge {

    /* Next in y-bucket or active list. */

    struct edge *next;

    /* Current x coordinate while the edge is on the active

     * list. Initialised to the x coordinate of the top of the

     * edge. The quotient is in grid_scaled_x_t units and the

     * remainder is mod dy in grid_scaled_y_t units.*/

    struct quorem x;

    /* Advance of the current x when moving down a subsample line. */

    struct quorem dxdy;

    /* Advance of the current x when moving down a full pixel

     * row. Only initialised when the height of the edge is large

     * enough that there's a chance the edge could be stepped by a

     * full row's worth of subsample rows at a time. */

    struct quorem dxdy_full;

    /* 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;

    int clip;

};

/* 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)

/* A collection of sorted and vertically clipped edges of the polygon.

 * Edges are moved from the polygon to an active list while scan

 * converting. */

struct polygon {

    /* The vertical clip extents. */

    grid_scaled_y_t ymin, ymax;

    /* Array of edges all starting in the same bucket.	An edge is put

     * into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when

     * it is added to the polygon. */

    struct edge **y_buckets;

    struct edge *y_buckets_embedded[64];

    struct {

	struct pool base[1];

	struct edge embedded[32];

    } edge_pool;

};

/* A cell records the effect on pixel coverage of polygon edges

 * passing through a pixel.  It contains two accumulators of pixel

 * coverage.

 *

 * Consider the effects of a polygon edge on the coverage of a pixel

 * it intersects and that of the following one.  The coverage of the

 * following pixel is the height of the edge multiplied by the width

 * of the pixel, and the coverage of the pixel itself is the area of

 * the trapezoid formed by the edge and the right side of the pixel.

 *

 * +-----------------------+-----------------------+

 * |                       |                       |

 * |                       |                       |

 * |_______________________|_______________________|

 * |   \...................|.......................|\

 * |    \..................|.......................| |

 * |     \.................|.......................| |

 * |      \....covered.....|.......................| |

 * |       \....area.......|.......................| } covered height

 * |        \..............|.......................| |

 * |uncovered\.............|.......................| |

 * |  area    \............|.......................| |

 * |___________\...........|.......................|/

 * |                       |                       |

 * |                       |                       |

 * |                       |                       |

 * +-----------------------+-----------------------+

 *

 * Since the coverage of the following pixel will always be a multiple

 * of the width of the pixel, we can store the height of the covered

 * area instead.  The coverage of the pixel itself is the total

 * coverage minus the area of the uncovered area to the left of the

 * edge.  As it's faster to compute the uncovered area we only store

 * that and subtract it from the total coverage later when forming

 * spans to blit.

 *

 * The heights and areas are signed, with left edges of the polygon

 * having positive sign and right edges having negative sign.  When

 * two edges intersect they swap their left/rightness so their

 * contribution above and below the intersection point must be

 * computed separately. */

struct cell {

    struct cell		*next;

    int			 x;

    grid_area_t		 uncovered_area;

    grid_scaled_y_t	 covered_height;

    grid_scaled_y_t	 clipped_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 {

    /* Sentinel nodes */

    struct cell head, tail;

    /* Cursor state for iterating through the cell list. */

    struct cell *cursor;

    /* Cells in the cell list are owned by the cell list and are

     * allocated from this pool.  */

    struct {

	struct pool base[1];

	struct cell embedded[32];

    } cell_pool;

};

struct cell_pair {

    struct cell *cell1;

    struct cell *cell2;

};

/* 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;

    /* 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. */

    grid_scaled_y_t min_height;

};

struct glitter_scan_converter {

    struct polygon	polygon[1];

    struct active_list	active[1];

    struct cell_list	coverages[1];

    /* Clip box. */

    grid_scaled_y_t ymin, ymax;

};

/* Compute the floored division a/b. Assumes / and % perform symmetric

 * division. */

inline static struct quorem

floored_divrem(int a, int b)

{

    struct quorem qr;

    qr.quo = a/b;

    qr.rem = a%b;

    if ((a^b)<0 && qr.rem) {

	qr.quo -= 1;

	qr.rem += b;

    }

    return qr;

}

/* Compute the floored division (x*a)/b. Assumes / and % perform symmetric

 * division. */

static struct quorem

floored_muldivrem(int x, int a, int b)

{

    struct quorem qr;

    long long xa = (long long)x*a;

    qr.quo = xa/b;

    qr.rem = xa%b;

    if ((xa>=0) != (b>=0) && qr.rem) {

	qr.quo -= 1;

	qr.rem += b;

    }

    return qr;

}

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;

    return p;

}

static struct _pool_chunk *

_pool_chunk_create(struct pool *pool, size_t size)

{

    struct _pool_chunk *p;

    p = malloc(size + sizeof(struct _pool_chunk));

    if (unlikely (NULL == p))

	longjmp (*pool->jmp, _cairo_error (CAIRO_STATUS_NO_MEMORY));

    return _pool_chunk_init(p, pool->current, size);

}

static void

pool_init(struct pool *pool,

	  jmp_buf *jmp,

	  size_t default_capacity,

	  size_t embedded_capacity)

{

    pool->jmp = jmp;

    pool->current = pool->sentinel;

    pool->first_free = NULL;

    pool->default_capacity = default_capacity;

    _pool_chunk_init(pool->sentinel, NULL, embedded_capacity);

}

static void

pool_fini(struct pool *pool)

{

    struct _pool_chunk *p = pool->current;

    do {

	while (NULL != p) {

	    struct _pool_chunk *prev = p->prev_chunk;

	    if (p != pool->sentinel)

		free(p);

	    p = prev;

	}

	p = pool->first_free;

	pool->first_free = NULL;

    } while (NULL != p);

}

/* 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

 * is called as a fallback if pool_alloc() couldn't do a quick

 * allocation from the current chunk in the pool. */

static void *

_pool_alloc_from_new_chunk(

    struct pool *pool,

    size_t size)

{

    struct _pool_chunk *chunk;

    void *obj;

    size_t capacity;

    /* If the allocation is smaller than the default chunk size then

     * try getting a chunk off the free list.  Force alloc of a new

     * chunk for large requests. */

    capacity = size;

    chunk = NULL;

    if (size < pool->default_capacity) {

	capacity = pool->default_capacity;

	chunk = pool->first_free;

	if (chunk) {

	    pool->first_free = chunk->prev_chunk;

	    _pool_chunk_init(chunk, pool->current, chunk->capacity);

	}

    }

    if (NULL == chunk)

	chunk = _pool_chunk_create (pool, capacity);

    pool->current = chunk;

    obj = ((unsigned char*)chunk + sizeof(*chunk) + chunk->size);

    chunk->size += size;

    return obj;

}

/* Allocate size bytes from the pool.  The first allocated address

 * returned from a pool is aligned to sizeof(void*).  Subsequent

 * addresses will maintain alignment as long as multiples of void* are

 * allocated.  Returns the address of a new memory area or %NULL on

 * allocation failures.	 The pool retains ownership of the returned

 * memory. */

inline static void *

pool_alloc (struct pool *pool, size_t size)

{

    struct _pool_chunk *chunk = pool->current;

    if (size <= chunk->capacity - chunk->size) {

	void *obj = ((unsigned char*)chunk + sizeof(*chunk) + chunk->size);

	chunk->size += size;

	return obj;

    } else {

	return _pool_alloc_from_new_chunk(pool, size);

    }

}

/* Relinquish all pool_alloced memory back to the pool. */

static void

pool_reset (struct pool *pool)

{

    /* Transfer all used chunks to the chunk free list. */

    struct _pool_chunk *chunk = pool->current;

    if (chunk != pool->sentinel) {

	while (chunk->prev_chunk != pool->sentinel) {

	    chunk = chunk->prev_chunk;

	}

	chunk->prev_chunk = pool->first_free;

	pool->first_free = pool->current;

    }

    /* Reset the sentinel as the current chunk. */

    pool->current = pool->sentinel;

    pool->sentinel->size = 0;

}

/* Rewinds the cell list's cursor to the beginning.  After rewinding

 * we're good to cell_list_find() the cell any x coordinate. */

inline static void

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)

{

    struct cell *tail = cells->cursor;

    if (tail->x > x)

	cell_list_rewind (cells);

}

static void

cell_list_init(struct cell_list *cells, jmp_buf *jmp)

{

    pool_init(cells->cell_pool.base, jmp,

	      256*sizeof(struct cell),

	      sizeof(cells->cell_pool.embedded));

    cells->tail.next = NULL;

    cells->tail.x = INT_MAX;

    cells->head.x = INT_MIN;

    cells->head.next = &cells->tail;

    cell_list_rewind (cells);

}

static void

cell_list_fini(struct cell_list *cells)

{

    pool_fini (cells->cell_pool.base);

}

/* Empty the cell list.  This is called at the start of every pixel

 * row. */

inline static void

cell_list_reset (struct cell_list *cells)

{

    cell_list_rewind (cells);

    cells->head.next = &cells->tail;

    pool_reset (cells->cell_pool.base);

}

static struct cell *

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));

    cell->next = tail->next;

    tail->next = cell;

    cell->x = x;

    cell->uncovered_area = 0;

    cell->covered_height = 0;

    cell->clipped_height = 0;

    return cell;

}

/* Find a cell at the given x-coordinate.  Returns %NULL if a new cell

 * needed to be allocated but couldn't be.  Cells must be found with

 * non-decreasing x-coordinate until the cell list is rewound using

 * 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 *tail = cells->cursor;

    while (1) {

	UNROLL3({

	    if (tail->next->x > x)

		break;

	    tail = tail->next;

	});

    }

    if (tail->x != x)

	tail = cell_list_alloc (cells, tail, x);

    return cells->cursor = tail;

}

/* Find two cells at x1 and x2.	 This is exactly equivalent

 * to

 *

 *   pair.cell1 = cell_list_find(cells, x1);

 *   pair.cell2 = cell_list_find(cells, x2);

 *

 * 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;

    pair.cell1 = cells->cursor;

    while (1) {

	UNROLL3({

	    if (pair.cell1->next->x > x1)

		break;

	    pair.cell1 = pair.cell1->next;

	});

    }

    if (pair.cell1->x != x1) {

	struct cell *cell = pool_alloc (cells->cell_pool.base,

					sizeof (struct cell));

	cell->x = x1;

	cell->uncovered_area = 0;

	cell->covered_height = 0;

	cell->clipped_height = 0;

	cell->next = pair.cell1->next;

	pair.cell1->next = cell;

	pair.cell1 = cell;

    }

    pair.cell2 = pair.cell1;

    while (1) {

	UNROLL3({

	    if (pair.cell2->next->x > x2)

		break;

	    pair.cell2 = pair.cell2->next;

	});

    }

    if (pair.cell2->x != x2) {

	struct cell *cell = pool_alloc (cells->cell_pool.base,

					sizeof (struct cell));

	cell->uncovered_area = 0;

	cell->covered_height = 0;

	cell->clipped_height = 0;

	cell->x = x2;

	cell->next = pair.cell2->next;

	pair.cell2->next = cell;

	pair.cell2 = cell;

    }

    cells->cursor = pair.cell2;

    return pair;

}

/* Add a subpixel span covering [x1, x2) to the coverage cells. */

inline static void

cell_list_add_subspan(struct cell_list *cells,

		      grid_scaled_x_t x1,

		      grid_scaled_x_t x2)

{

    int ix1, fx1;

    int 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;

	p = cell_list_find_pair(cells, ix1, ix2);

	p.cell1->uncovered_area += 2*fx1;

	++p.cell1->covered_height;

	p.cell2->uncovered_area -= 2*fx2;

	--p.cell2->covered_height;

    } else {

	struct cell *cell = cell_list_find(cells, ix1);

	cell->uncovered_area += 2*(fx1-fx2);

    }

}

/* Adds the analytical coverage of an edge crossing the current pixel

 * row to the coverage cells and advances the edge's x position to the

 * following row.

 *

 * This function is only called when we know that during this pixel row:

 *

 * 1) The relative order of all edges on the active list doesn't

 * change.  In particular, no edges intersect within this row to pixel

 * precision.

 *

 * 2) No new edges start in this row.

 *

 * 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 void

cell_list_render_edge(

    struct cell_list *cells,

    struct edge *edge,

    int sign)

{

    grid_scaled_y_t y1, y2, dy;

    grid_scaled_x_t dx;

    int ix1, ix2;

    grid_scaled_x_t fx1, fx2;

    struct quorem x1 = edge->x;

    struct quorem x2 = x1;

    if (! edge->vertical) {

	x2.quo += edge->dxdy_full.quo;

	x2.rem += edge->dxdy_full.rem;

	if (x2.rem >= 0) {

	    ++x2.quo;

	    x2.rem -= edge->dy;

	}

	edge->x = x2;

    }

    GRID_X_TO_INT_FRAC(x1.quo, ix1, fx1);

    GRID_X_TO_INT_FRAC(x2.quo, ix2, fx2);

    /* 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);

	cell->covered_height += sign*GRID_Y;

	cell->uncovered_area += sign*(fx1 + fx2)*GRID_Y;

	return;

    }

    /* Orient the edge left-to-right. */

    dx = x2.quo - x1.quo;

    if (dx >= 0) {

	y1 = 0;

	y2 = GRID_Y;

    } else {

	int tmp;

	tmp = ix1; ix1 = ix2; ix2 = tmp;

	tmp = fx1; fx1 = fx2; fx2 = tmp;

	dx = -dx;

	sign = -sign;

	y1 = GRID_Y;

	y2 = 0;

    }

    dy = y2 - y1;

    /* Add coverage for all pixels [ix1,ix2] on this row crossed

     * by the edge. */

    {

	struct cell_pair pair;

	struct quorem y = floored_divrem((GRID_X - fx1)*dy, dx);

	/* When rendering a previous edge on the active list we may

	 * advance the cell list cursor past the leftmost pixel of the

	 * current edge even though the two edges don't intersect.

	 * e.g. consider two edges going down and rightwards:

	 *

	 *  --\_+---\_+-----+-----+----

	 *      \_    \_    |     |

	 *      | \_  | \_  |     |

	 *      |   \_|   \_|     |

	 *      |     \_    \_    |

	 *  ----+-----+-\---+-\---+----

	 *

	 * The left edge touches cells past the starting cell of the

	 * right edge.  Fortunately such cases are rare.

	 *

	 * The rewinding is never necessary if the current edge stays

	 * 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);

	pair.cell1->uncovered_area += sign*y.quo*(GRID_X + fx1);

	pair.cell1->covered_height += sign*y.quo;

	y.quo += y1;

	if (ix1+1 < ix2) {

	    struct quorem dydx_full = floored_divrem(GRID_X*dy, dx);

	    struct cell *cell = pair.cell2;

	    ++ix1;

	    do {

		grid_scaled_y_t y_skip = dydx_full.quo;

		y.rem += dydx_full.rem;

		if (y.rem >= dx) {

		    ++y_skip;

		    y.rem -= dx;

		}

		y.quo += y_skip;

		y_skip *= sign;

		cell->uncovered_area += y_skip*GRID_X;

		cell->covered_height += y_skip;

		++ix1;

		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);

    }

}

static void

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, jmp,

	       8192 - sizeof (struct _pool_chunk),

	       sizeof (polygon->edge_pool.embedded));

}

static void

polygon_fini (struct polygon *polygon)

{

    if (polygon->y_buckets != polygon->y_buckets_embedded)

	free (polygon->y_buckets);

    pool_fini (polygon->edge_pool.base);

}

/* Empties the polygon of all edges. The polygon is then prepared to

 * receive new edges and clip them to the vertical range

 * [ymin,ymax). */

static cairo_status_t

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,

					       ymin);

    pool_reset(polygon->edge_pool.base);

    if (unlikely (h > 0x7FFFFFFFU - EDGE_Y_BUCKET_HEIGHT))

	goto bail_no_mem; /* even if you could, you wouldn't want to. */

    if (polygon->y_buckets != polygon->y_buckets_embedded)

	free (polygon->y_buckets);

    polygon->y_buckets =  polygon->y_buckets_embedded;

    if (num_buckets > ARRAY_LENGTH (polygon->y_buckets_embedded)) {

	polygon->y_buckets = _cairo_malloc_ab (num_buckets,

					       sizeof (struct edge *));

	if (unlikely (NULL == polygon->y_buckets))

	    goto bail_no_mem;

    }

    memset (polygon->y_buckets, 0, num_buckets * sizeof (struct edge *));

    polygon->ymin = ymin;

    polygon->ymax = ymax;

    return CAIRO_STATUS_SUCCESS;

 bail_no_mem:

    polygon->ymin = 0;

    polygon->ymax = 0;

    return CAIRO_STATUS_NO_MEMORY;

}

static void

_polygon_insert_edge_into_its_y_bucket(

    struct polygon *polygon,

    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 void

polygon_add_edge (struct polygon *polygon,

		  const cairo_edge_t *edge,

		  int clip)

{

    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;

    assert (edge->bottom > edge->top);

    if (unlikely (edge->top >= ymax || edge->bottom <= ymin))

	return;

    e = pool_alloc (polygon->edge_pool.base, sizeof (struct edge));

    dx = edge->line.p2.x - edge->line.p1.x;

    dy = edge->line.p2.y - edge->line.p1.y;

    e->dy = dy;

    e->dir = edge->dir;

    e->clip = clip;

    ytop = edge->top >= ymin ? edge->top : ymin;

    ybot = edge->bottom <= ymax ? edge->bottom : ymax;

    e->ytop = ytop;

    e->height_left = ybot - ytop;

    if (dx == 0) {

	e->vertical = TRUE;

	e->x.quo = edge->line.p1.x;

	e->x.rem = 0;

	e->dxdy.quo = 0;

	e->dxdy.rem = 0;

	e->dxdy_full.quo = 0;

	e->dxdy_full.rem = 0;

    } else {

	e->vertical = FALSE;

	e->dxdy = floored_divrem (dx, dy);

	if (ytop == edge->line.p1.y) {

	    e->x.quo = edge->line.p1.x;

	    e->x.rem = 0;

	} else {

	    e->x = floored_muldivrem (ytop - edge->line.p1.y, dx, dy);

	    e->x.quo += edge->line.p1.x;

	}

	if (e->height_left >= GRID_Y) {

	    e->dxdy_full = floored_muldivrem (GRID_Y, dx, dy);

	} else {

	    e->dxdy_full.quo = 0;

	    e->dxdy_full.rem = 0;

	}

    }

    _polygon_insert_edge_into_its_y_bucket (polygon, e);

    e->x.rem -= dy;		/* Bias the remainder for faster

				 * edge advancement. */

}

static void

active_list_reset (struct active_list *active)

{

    active->head = NULL;

    active->min_height = 0;

}

static void

active_list_init(struct active_list *active)

{

    active_list_reset(active);

}

/*

 * Merge two sorted edge lists.

 * Input:

 *  - head_a: The head of the first list.

 *  - head_b: The head of the second list; head_b cannot be NULL.

 * Output:

 * Returns the head of the merged list.

 *

 * Implementation notes:

 * To make it fast (in particular, to reduce to an insertion sort whenever

 * one of the two input lists only has a single element) we iterate through

 * a list until its head becomes greater than the head of the other list,

 * then we switch their roles. As soon as one of the two lists is empty, we

 * just attach the other one to the current list and exit.

 * Writes to memory are only needed to "switch" lists (as it also requires

 * attaching to the output list the list which we will be iterating next) and

 * 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;

    int32_t x;

    if (head_a == NULL)

	return head_b;

    next = &head;

    if (head_a->x.quo <= head_b->x.quo) {

	head = head_a;

    } else {

	head = head_b;

	goto start_with_b;

    }

    do {

	x = head_b->x.quo;

	while (head_a != NULL && head_a->x.quo <= x) {

	    next = &head_a->next;

	    head_a = head_a->next;

	}

	*next = head_b;

	if (head_a == NULL)

	    return head;

start_with_b:

	x = head_a->x.quo;

	while (head_b != NULL && head_b->x.quo <= x) {

	    next = &head_b->next;

	    head_b = head_b->next;

	}

	*next = head_a;

	if (head_b == NULL)

	    return head;

    } while (1);

}

/*

 * Sort (part of) a list.

 * Input:

 *  - list: The list to be sorted; list cannot be NULL.

 *  - limit: Recursion limit.

 * Output:

 *  - head_out: The head of the sorted list containing the first 2^(level+1) elements of the

 *              input list; if the input list has fewer elements, head_out be a sorted list

 *              containing all the elements of the input list.

 * Returns the head of the list of unprocessed elements (NULL if the sorted list contains

 * all the elements of the input list).

 *

 * Implementation notes:

 * Special case single element list, unroll/inline the sorting of the first two elements.

 * Some tail recursion is used since we iterate on the bottom-up solution of the problem

 * (we start with a small sorted list and keep merging other lists of the same size to it).

 */

static struct edge *

sort_edges (struct edge  *list,

	    unsigned int  level,

	    struct edge **head_out)

{

    struct edge *head_other, *remaining;

    unsigned int i;

    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.

     *  - 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) {

	*head_out = list;

	/* list->next = head_other; */ /* The input list is already like this. */

	head_other->next = NULL;

    } else {

	*head_out = head_other;

	head_other->next = list;

	list->next = NULL;

    }