[cairo-commit] 16 commits - src/cairo-bentley-ottmann.c
src/cairo-freelist.c src/cairo-freelist-private.h
src/cairoint.h src/cairo-path-fill.c src/cairo-path-stroke.c
src/cairo-pen.c src/cairo-skiplist.c
src/cairo-skiplist-private.h src/cairo-traps.c
src/cairo-wideint.c src/cairo-wideint-private.h src/Makefile.am
Carl Worth
cworth at kemper.freedesktop.org
Wed Nov 22 17:57:04 PST 2006
src/Makefile.am | 5
src/cairo-bentley-ottmann.c | 1694 +++++++++++++++++++++++++++++++++++++++++++
src/cairo-freelist-private.h | 71 +
src/cairo-freelist.c | 72 +
src/cairo-path-fill.c | 6
src/cairo-path-stroke.c | 2
src/cairo-pen.c | 2
src/cairo-skiplist-private.h | 97 ++
src/cairo-skiplist.c | 469 +++++++++++
src/cairo-traps.c | 7
src/cairo-wideint-private.h | 8
src/cairo-wideint.c | 152 +++
src/cairoint.h | 10
13 files changed, 2584 insertions(+), 11 deletions(-)
New commits:
diff-tree fac3684e686a259658151dac13907fa69f43f727 (from 6bd72ce74aba4a576e5aa76a5c92bd5557ae97f1)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Wed Nov 22 08:30:28 2006 +0200
perf: new-tessellator: Deferred trapezoid generation (first try)
diff --git a/src/Makefile.am b/src/Makefile.am
index 5079ec8..2e7abf3 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -180,6 +180,8 @@ libcairo_la_SOURCES = \
cairo-fixed.c \
cairo-font.c \
cairo-font-options.c \
+ cairo-freelist.c \
+ cairo-freelist-private.h \
cairo-gstate.c \
cairo-gstate-private.h \
cairo-hash.c \
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index d15457c..2c0f98c 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -37,6 +37,7 @@
#include "cairoint.h"
#include "cairo-skiplist-private.h"
+#include "cairo-freelist-private.h"
#define CAIRO_BO_GUARD_BITS 2
@@ -59,6 +60,19 @@ typedef struct _cairo_bo_intersect_point
typedef struct _cairo_bo_edge cairo_bo_edge_t;
typedef struct _sweep_line_elt sweep_line_elt_t;
+typedef struct _cairo_bo_trap cairo_bo_trap_t;
+typedef struct _cairo_bo_traps cairo_bo_traps_t;
+
+/* A deferred trapezoid of an edge. */
+struct _cairo_bo_trap {
+ cairo_bo_edge_t *right;
+ int32_t top;
+};
+
+struct _cairo_bo_traps {
+ cairo_traps_t *traps;
+ cairo_freelist_t freelist;
+};
struct _cairo_bo_edge {
cairo_bo_point32_t top;
@@ -67,6 +81,7 @@ struct _cairo_bo_edge {
cairo_bool_t reversed;
cairo_bo_edge_t *prev;
cairo_bo_edge_t *next;
+ cairo_bo_trap_t *deferred_trap;
sweep_line_elt_t *sweep_line_elt;
};
@@ -1021,6 +1036,101 @@ print_state (const char *msg,
}
#endif
+/* Adds the trapezoid, if any, of the left edge to the cairo_traps_t
+ * of bo_traps. */
+static cairo_status_t
+_cairo_bo_edge_end_trap (cairo_bo_edge_t *left,
+ int32_t bot,
+ cairo_bo_traps_t *bo_traps)
+{
+ cairo_fixed_t fixed_top, fixed_bot;
+ cairo_status_t status = CAIRO_STATUS_SUCCESS;
+ cairo_bo_trap_t *trap = left->deferred_trap;
+
+ if (!trap)
+ return CAIRO_STATUS_SUCCESS;
+
+ fixed_top = trap->top >> CAIRO_BO_GUARD_BITS;
+ fixed_bot = bot >> CAIRO_BO_GUARD_BITS;
+
+ if (fixed_top < fixed_bot) {
+ cairo_bo_edge_t *right = trap->right;
+ cairo_point_t left_top, left_bot, right_top, right_bot;
+
+ left_top.x = left->top.x >> CAIRO_BO_GUARD_BITS;
+ left_top.y = left->top.y >> CAIRO_BO_GUARD_BITS;
+ right_top.x = right->top.x >> CAIRO_BO_GUARD_BITS;
+ right_top.y = right->top.y >> CAIRO_BO_GUARD_BITS;
+ left_bot.x = left->bottom.x >> CAIRO_BO_GUARD_BITS;
+ left_bot.y = left->bottom.y >> CAIRO_BO_GUARD_BITS;
+ right_bot.x = right->bottom.x >> CAIRO_BO_GUARD_BITS;
+ right_bot.y = right->bottom.y >> CAIRO_BO_GUARD_BITS;
+
+ status = _cairo_traps_add_trap_from_points (bo_traps->traps,
+ fixed_top,
+ fixed_bot,
+ left_top, left_bot,
+ right_top, right_bot);
+
+#if DEBUG_PRINT_STATE
+ printf ("Deferred trap: left=(%08x, %08x)-(%08x,%08x) "
+ "right=(%08x,%08x)-(%08x,%08x) top=%08x, bot=%08x\n",
+ left->top.x, left->top.y, left->bottom.x, left->bottom.y,
+ right->top.x, right->top.y, right->bottom.x, right->bottom.y,
+ trap->top, bot);
+#endif
+ }
+
+ _cairo_freelist_free (&bo_traps->freelist, trap);
+ left->deferred_trap = NULL;
+ return status;
+}
+
+/* Start a new trapezoid at the given top y coordinate, whose edges
+ * are `edge' and `edge->next'. If `edge' already has a trapezoid,
+ * then either add it to the traps in `bo_traps', if the trapezoid's
+ * right edge differs from `edge->next', or do nothing if the new
+ * trapezoid would be a continuation of the existing one. */
+static cairo_status_t
+_cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t *edge,
+ int32_t top,
+ cairo_bo_traps_t *bo_traps)
+{
+ cairo_status_t status;
+ cairo_bo_trap_t *trap = edge->deferred_trap;
+
+ if (trap) {
+ if (trap->right == edge->next) return CAIRO_STATUS_SUCCESS;
+ status = _cairo_bo_edge_end_trap (edge, top, bo_traps);
+ if (status)
+ return status;
+ }
+
+ if (edge->next) {
+ trap = edge->deferred_trap = _cairo_freelist_alloc (&bo_traps->freelist);
+ if (!edge->deferred_trap)
+ return CAIRO_STATUS_NO_MEMORY;
+
+ trap->right = edge->next;
+ trap->top = top;
+ }
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static void
+_cairo_bo_traps_init (cairo_bo_traps_t *bo_traps,
+ cairo_traps_t *traps)
+{
+ bo_traps->traps = traps;
+ _cairo_freelist_init (&bo_traps->freelist, sizeof(cairo_bo_trap_t));
+}
+
+static void
+_cairo_bo_traps_fini (cairo_bo_traps_t *bo_traps)
+{
+ _cairo_freelist_fini (&bo_traps->freelist);
+}
+
static void
_cairo_bo_sweep_line_validate (cairo_bo_sweep_line_t *sweep_line)
{
@@ -1047,17 +1157,17 @@ _cairo_bo_sweep_line_validate (cairo_bo_
}
}
+
static cairo_status_t
_active_edges_to_traps (cairo_bo_edge_t *head,
int32_t top,
int32_t bottom,
cairo_fill_rule_t fill_rule,
- cairo_traps_t *traps)
+ cairo_bo_traps_t *bo_traps)
{
cairo_status_t status;
int in_out = 0;
cairo_bo_edge_t *edge;
- cairo_bo_point32_t left_top, left_bottom, right_top, right_bottom;
for (edge = head; edge && edge->next; edge = edge->next) {
if (fill_rule == CAIRO_FILL_RULE_WINDING) {
@@ -1065,31 +1175,23 @@ _active_edges_to_traps (cairo_bo_edge_t
in_out++;
else
in_out--;
- if (in_out == 0)
+ if (in_out == 0) {
+ status = _cairo_bo_edge_end_trap (edge, top, bo_traps);
+ if (status)
+ return status;
continue;
+ }
} else {
in_out++;
- if ((in_out & 1) == 0)
+ if ((in_out & 1) == 0) {
+ status = _cairo_bo_edge_end_trap (edge, top, bo_traps);
+ if (status)
+ return status;
continue;
+ }
}
-#if DEBUG_PRINT_STATE
- printf ("Adding trap 0x%x 0x%x: ", top, bottom);
- _cairo_bo_edge_print (edge);
- _cairo_bo_edge_print (edge->next);
-#endif
- left_top.x = edge->middle.x >> CAIRO_BO_GUARD_BITS;
- left_top.y = edge->middle.y >> CAIRO_BO_GUARD_BITS;
- left_bottom.x = edge->bottom.x >> CAIRO_BO_GUARD_BITS;
- left_bottom.y = edge->bottom.y >> CAIRO_BO_GUARD_BITS;
- right_top.x = edge->next->middle.x >> CAIRO_BO_GUARD_BITS;
- right_top.y = edge->next->middle.y >> CAIRO_BO_GUARD_BITS;
- right_bottom.x = edge->next->bottom.x >> CAIRO_BO_GUARD_BITS;
- right_bottom.y = edge->next->bottom.y >> CAIRO_BO_GUARD_BITS;
- status = _cairo_traps_add_trap_from_points (traps,
- top >> CAIRO_BO_GUARD_BITS,
- bottom >> CAIRO_BO_GUARD_BITS,
- left_top, left_bottom,
- right_top, right_bottom);
+
+ status = _cairo_bo_edge_start_or_continue_trap (edge, top, bo_traps);
if (status)
return status;
}
@@ -1111,6 +1213,7 @@ _cairo_bentley_ottmann_tessellate_bo_edg
int intersection_count = 0;
cairo_bo_event_queue_t event_queue;
cairo_bo_sweep_line_t sweep_line;
+ cairo_bo_traps_t bo_traps;
cairo_bo_event_t *event, event_saved;
cairo_bo_edge_t *edge;
cairo_bo_edge_t *left, *right;
@@ -1129,6 +1232,7 @@ _cairo_bentley_ottmann_tessellate_bo_edg
_cairo_bo_event_queue_init (&event_queue, edges, num_edges);
_cairo_bo_sweep_line_init (&sweep_line);
+ _cairo_bo_traps_init (&bo_traps, traps);
#if DEBUG_PRINT_STATE
print_state ("After initializing", &event_queue, &sweep_line);
@@ -1143,7 +1247,7 @@ _cairo_bentley_ottmann_tessellate_bo_edg
if (event->point.y != sweep_line.current_y) {
status = _active_edges_to_traps (sweep_line.head,
sweep_line.current_y, event->point.y,
- fill_rule, traps);
+ fill_rule, &bo_traps);
if (status)
goto unwind;
@@ -1184,6 +1288,10 @@ _cairo_bentley_ottmann_tessellate_bo_edg
_cairo_bo_sweep_line_delete (&sweep_line, edge);
+ status = _cairo_bo_edge_end_trap (edge, edge->bottom.y, &bo_traps);
+ if (status)
+ goto unwind;
+
_cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right);
#if DEBUG_PRINT_STATE
@@ -1229,6 +1337,14 @@ _cairo_bentley_ottmann_tessellate_bo_edg
*num_intersections = intersection_count;
unwind:
+ for (edge = sweep_line.head; edge; edge = edge->next) {
+ cairo_status_t status2 = _cairo_bo_edge_end_trap (edge,
+ sweep_line.current_y,
+ &bo_traps);
+ if (!status)
+ status = status2;
+ }
+ _cairo_bo_traps_fini (&bo_traps);
_cairo_bo_sweep_line_fini (&sweep_line);
_cairo_bo_event_queue_fini (&event_queue);
return status;
@@ -1256,6 +1372,7 @@ _cairo_bentley_ottmann_tessellate_polygo
* totally bogus. It's really a (negated!) description of
* whether the edge is reversed. */
edges[i].reversed = (! polygon->edges[i].clockWise);
+ edges[i].deferred_trap = NULL;
edges[i].prev = NULL;
edges[i].next = NULL;
edges[i].sweep_line_elt = NULL;
diff --git a/src/cairo-freelist-private.h b/src/cairo-freelist-private.h
new file mode 100644
index 0000000..7a225ff
--- /dev/null
+++ b/src/cairo-freelist-private.h
@@ -0,0 +1,71 @@
+/*
+ * Copyright © 2006 Joonas Pihlaja
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that copyright
+ * notice and this permission notice appear in supporting documentation, and
+ * that the name of the copyright holders not be used in advertising or
+ * publicity pertaining to distribution of the software without specific,
+ * written prior permission. The copyright holders make no representations
+ * about the suitability of this software for any purpose. It is provided "as
+ * is" without express or implied warranty.
+ *
+ * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
+ * OF THIS SOFTWARE.
+ */
+#ifndef CAIRO_FREELIST_H
+#define CAIRO_FREELIST_H
+#include <stddef.h>
+
+/* Opaque implementation types. */
+struct _cairo_freelist;
+struct _cairo_freelist_node;
+typedef struct _cairo_freelist cairo_freelist_t;
+typedef struct _cairo_freelist_node cairo_freelist_node_t;
+
+struct _cairo_freelist_node {
+ cairo_freelist_node_t *next;
+};
+
+struct _cairo_freelist {
+ cairo_freelist_node_t *first_free_node;
+ unsigned nodesize;
+};
+
+
+/* Initialise a freelist that will be responsible for allocating
+ * nodes of size nodesize. */
+void
+_cairo_freelist_init (cairo_freelist_t *freelist, unsigned nodesize);
+
+/* Deallocate any nodes in the freelist. */
+void
+_cairo_freelist_fini (cairo_freelist_t *freelist);
+
+/* Allocate a new node from the freelist. If the freelist contains no
+ * nodes, a new one will be allocated using malloc(). The caller is
+ * responsible for calling _cairo_freelist_free() or free() on the
+ * returned node. Returns NULL on memory allocation error. */
+void *
+_cairo_freelist_alloc (cairo_freelist_t *freelist);
+
+/* Allocate a new node from the freelist. If the freelist contains no
+ * nodes, a new one will be allocated using calloc(). The caller is
+ * responsible for calling _cairo_freelist_free() or free() on the
+ * returned node. Returns NULL on memory allocation error. */
+void *
+_cairo_freelist_calloc (cairo_freelist_t *freelist);
+
+/* Return a node to the freelist. This does not deallocate the memory,
+ * but makes it available for later reuse by
+ * _cairo_freelist_alloc(). */
+void
+_cairo_freelist_free (cairo_freelist_t *freelist, void *node);
+
+#endif /* CAIRO_FREELIST_H */
diff --git a/src/cairo-freelist.c b/src/cairo-freelist.c
new file mode 100644
index 0000000..eed1934
--- /dev/null
+++ b/src/cairo-freelist.c
@@ -0,0 +1,72 @@
+/*
+ * Copyright © 2006 Joonas Pihlaja
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that copyright
+ * notice and this permission notice appear in supporting documentation, and
+ * that the name of the copyright holders not be used in advertising or
+ * publicity pertaining to distribution of the software without specific,
+ * written prior permission. The copyright holders make no representations
+ * about the suitability of this software for any purpose. It is provided "as
+ * is" without express or implied warranty.
+ *
+ * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
+ * OF THIS SOFTWARE.
+ */
+#include <stdlib.h>
+#include <string.h>
+#include "cairo-freelist-private.h"
+
+void
+_cairo_freelist_init (cairo_freelist_t *freelist, unsigned nodesize)
+{
+ memset (freelist, 0, sizeof(cairo_freelist_t));
+ freelist->nodesize = nodesize;
+}
+
+void
+_cairo_freelist_fini (cairo_freelist_t *freelist)
+{
+ cairo_freelist_node_t *node = freelist->first_free_node;
+ while (node) {
+ cairo_freelist_node_t *next = node->next;
+ free (node);
+ node = next;
+ }
+}
+
+void *
+_cairo_freelist_alloc (cairo_freelist_t *freelist)
+{
+ if (freelist->first_free_node) {
+ cairo_freelist_node_t *node = freelist->first_free_node;
+ freelist->first_free_node = node->next;
+ return (void*)node;
+ }
+ return malloc (freelist->nodesize);
+}
+
+void *
+_cairo_freelist_calloc (cairo_freelist_t *freelist)
+{
+ void *node = _cairo_freelist_alloc (freelist);
+ if (node)
+ memset (node, 0, freelist->nodesize);
+ return node;
+}
+
+void
+_cairo_freelist_free (cairo_freelist_t *freelist, void *voidnode)
+{
+ cairo_freelist_node_t *node = voidnode;
+ if (node) {
+ node->next = freelist->first_free_node;
+ freelist->first_free_node = node;
+ }
+}
diff-tree 6bd72ce74aba4a576e5aa76a5c92bd5557ae97f1 (from b177573b729401117a061cd6f07743fa81c01724)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Mon Nov 20 04:19:17 2006 +0200
Sort pointers instead of cairo_bo_events in the tessellator.
We were spending a lot of time in memcpy.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index c959e2f..d15457c 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -104,6 +104,7 @@ typedef struct _cairo_bo_event_queue {
skip_list_t intersection_queue;
cairo_bo_event_t *startstop_events;
+ cairo_bo_event_t **sorted_startstop_event_ptrs;
unsigned next_startstop_event_index;
unsigned num_startstop_events;
} cairo_bo_event_queue_t;
@@ -416,18 +417,20 @@ cairo_bo_event_compare_abstract (void *
}
static int
-cairo_bo_event_compare_stable (void const *voida,
- void const *voidb)
+cairo_bo_event_compare_pointers (void const *voida,
+ void const *voidb)
{
- cairo_bo_event_t const *a = voida;
- cairo_bo_event_t const *b = voidb;
- int cmp = cairo_bo_event_compare (a, b);
- if (cmp)
- return cmp;
- if (a < b)
- return -1;
- if (a > b)
- return +1;
+ cairo_bo_event_t const * const *a = voida;
+ cairo_bo_event_t const * const *b = voidb;
+ if (*a != *b) {
+ int cmp = cairo_bo_event_compare (*a, *b);
+ if (cmp)
+ return cmp;
+ if (*a < *b)
+ return -1;
+ if (*a > *b)
+ return +1;
+ }
return 0;
}
@@ -677,11 +680,12 @@ _cairo_bo_event_dequeue (cairo_bo_event_
{
skip_elt_t *elt = event_queue->intersection_queue.chains[0];
cairo_bo_event_t *intersection = elt ? SKIP_ELT_TO_EVENT (elt) : NULL;
- cairo_bo_event_t *startstop = &event_queue->startstop_events[
- event_queue->next_startstop_event_index];
+ cairo_bo_event_t *startstop;
if (event_queue->next_startstop_event_index == event_queue->num_startstop_events)
return intersection;
+ startstop = event_queue->sorted_startstop_event_ptrs[
+ event_queue->next_startstop_event_index];
if (!intersection || cairo_bo_event_compare (startstop, intersection) <= 0)
{
@@ -697,7 +701,8 @@ _cairo_bo_event_queue_init (cairo_bo_eve
int num_edges)
{
int i;
- cairo_bo_event_t *events;
+ cairo_bo_event_t *events, **sorted_event_ptrs;
+ unsigned num_events = 2*num_edges;
memset (event_queue, 0, sizeof(*event_queue));
@@ -711,14 +716,21 @@ _cairo_bo_event_queue_init (cairo_bo_eve
* or stop events, so this allocation is safe. XXX: make the
* event type a union so it doesn't always contain the skip
* elt? */
- events = calloc (2*num_edges, sizeof(cairo_bo_event_t));
- if (!events)
+ events = malloc (num_events * sizeof(cairo_bo_event_t));
+ sorted_event_ptrs = malloc (num_events * sizeof(cairo_bo_event_t*));
+ if (!events || !sorted_event_ptrs) {
+ if (events) free(events);
+ if (sorted_event_ptrs) free(sorted_event_ptrs);
return CAIRO_STATUS_NO_MEMORY;
+ }
event_queue->startstop_events = events;
- event_queue->num_startstop_events = (unsigned)(2*num_edges);
+ event_queue->sorted_startstop_event_ptrs = sorted_event_ptrs;
+ event_queue->num_startstop_events = (unsigned)(num_events);
event_queue->next_startstop_event_index = 0;
for (i = 0; i < num_edges; i++) {
+ sorted_event_ptrs[2*i] = &events[2*i];
+ sorted_event_ptrs[2*i+1] = &events[2*i+1];
/* We must not be given horizontal edges. */
assert (edges[i].top.y != edges[i].bottom.y);
@@ -740,9 +752,9 @@ _cairo_bo_event_queue_init (cairo_bo_eve
edges[i].bottom);
}
- qsort (events, (unsigned)(2*num_edges),
- sizeof(cairo_bo_event_t),
- cairo_bo_event_compare_stable);
+ qsort (sorted_event_ptrs, num_events,
+ sizeof(cairo_bo_event_t *),
+ cairo_bo_event_compare_pointers);
return CAIRO_STATUS_SUCCESS;
}
@@ -752,6 +764,8 @@ _cairo_bo_event_queue_fini (cairo_bo_eve
skip_list_fini (&event_queue->intersection_queue);
if (event_queue->startstop_events)
free (event_queue->startstop_events);
+ if (event_queue->sorted_startstop_event_ptrs)
+ free (event_queue->sorted_startstop_event_ptrs);
}
static void
diff-tree b177573b729401117a061cd6f07743fa81c01724 (from 8bec0bac56785434f5e5860cf5f3560cac82ebb2)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Mon Nov 20 03:56:07 2006 +0200
Make the skip list check for uniqueness.
This patch removes a redundant call to skip_list_find()
that was being used to detect duplicate intersection events.
Instead, skip_list_insert() now takes an additional parameter
letting it know what to do with duplicates.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index d3cdce4..c959e2f 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -660,13 +660,8 @@ _cairo_bo_event_queue_insert (cairo_bo_e
cairo_bo_event_t *event)
{
/* Don't insert if there's already an equivalent intersection event in the queue. */
- if (event->type == CAIRO_BO_EVENT_TYPE_INTERSECTION &&
- skip_list_find (&queue->intersection_queue, event) != NULL)
- {
- return;
- }
-
- skip_list_insert (&queue->intersection_queue, event);
+ skip_list_insert (&queue->intersection_queue, event,
+ event->type == CAIRO_BO_EVENT_TYPE_INTERSECTION);
}
static void
@@ -819,7 +814,8 @@ _cairo_bo_sweep_line_insert (cairo_bo_sw
sweep_line_elt_t *sweep_line_elt;
cairo_bo_edge_t **prev_of_next, **next_of_prev;
- sweep_line_elt = skip_list_insert (&sweep_line->active_edges, &edge);
+ sweep_line_elt = skip_list_insert (&sweep_line->active_edges, &edge,
+ 1 /* unique inserts*/);
next_elt = sweep_line_elt->elt.next[0];
if (next_elt)
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h
index 4cbbf09..d433398 100644
--- a/src/cairo-skiplist-private.h
+++ b/src/cairo-skiplist-private.h
@@ -75,10 +75,12 @@ void
skip_list_fini (skip_list_t *list);
/* Insert a new element into the list at the correct sort order as
- * determined by compare. Data will be copied (elt_size bytes from
- * <data> via memcpy). The new element is returned. */
+ * determined by compare. If unique is true, then duplicate elements
+ * are ignored and the already inserted element is returned.
+ * Otherwise data will be copied (elt_size bytes from <data> via
+ * memcpy) and the new element is returned. */
void *
-skip_list_insert (skip_list_t *list, void *data);
+skip_list_insert (skip_list_t *list, void *data, int unique);
/* Find an element which compare considers equal to <data> */
void *
diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
index 7a542d9..6dc4e3c 100644
--- a/src/cairo-skiplist.c
+++ b/src/cairo-skiplist.c
@@ -304,32 +304,36 @@ free_elt (skip_list_t *list, skip_elt_t
* Insert 'data' into the list
*/
void *
-skip_list_insert (skip_list_t *list, void *data)
+skip_list_insert (skip_list_t *list, void *data, int unique)
{
skip_elt_t **update[MAX_LEVEL];
+ skip_elt_t *prev[MAX_LEVEL];
char *data_and_elt;
- skip_elt_t *elt, *prev, **next;
+ skip_elt_t *elt, **next;
int i, level, prev_index;
- level = random_level ();
- prev_index = level - 1;
-
/*
* Find links along each chain
*/
- prev = NULL;
next = list->chains;
for (i = list->max_level; --i >= 0; )
{
for (; (elt = next[i]); next = elt->next)
{
- if (list->compare (list, ELT_DATA(elt), data) > 0)
+ int cmp = list->compare (list, ELT_DATA(elt), data);
+ if (unique && 0 == cmp)
+ return ELT_DATA(elt);
+ if (cmp > 0)
break;
}
update[i] = next;
- if (i == prev_index && next != list->chains)
- prev = NEXT_TO_ELT (next);
+ if (next != list->chains)
+ prev[i] = NEXT_TO_ELT (next);
+ else
+ prev[i] = NULL;
}
+ level = random_level ();
+ prev_index = level - 1;
/*
* Create new list element
@@ -338,6 +342,7 @@ skip_list_insert (skip_list_t *list, voi
{
level = list->max_level + 1;
prev_index = level - 1;
+ prev[prev_index] = NULL;
update[list->max_level] = list->chains;
list->max_level = level;
}
@@ -347,7 +352,7 @@ skip_list_insert (skip_list_t *list, voi
elt = (skip_elt_t *) (data_and_elt + list->data_size);
elt->prev_index = prev_index;
- elt->prev = prev;
+ elt->prev = prev[prev_index];
/*
* Insert into all chains
diff-tree 8bec0bac56785434f5e5860cf5f3560cac82ebb2 (from de0e327b3d9aec50d970d8cfc881fb3949df59cc)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Mon Nov 20 03:45:26 2006 +0200
Malloc less using a free list of nodes.
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h
index 74d495c..4cbbf09 100644
--- a/src/cairo-skiplist-private.h
+++ b/src/cairo-skiplist-private.h
@@ -50,6 +50,7 @@ typedef struct _skip_list {
size_t elt_size;
size_t data_size;
skip_elt_t *chains[MAX_LEVEL];
+ skip_elt_t *freelists[MAX_LEVEL];
int max_level;
} skip_list_t;
diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
index 07c76d2..7a542d9 100644
--- a/src/cairo-skiplist.c
+++ b/src/cairo-skiplist.c
@@ -233,8 +233,10 @@ skip_list_init (skip_list_t *list,
list->elt_size = elt_size;
list->data_size = elt_size - sizeof (skip_elt_t);
- for (i = 0; i < MAX_LEVEL; i++)
+ for (i = 0; i < MAX_LEVEL; i++) {
list->chains[i] = NULL;
+ list->freelists[i] = NULL;
+ }
list->max_level = 0;
}
@@ -242,11 +244,20 @@ skip_list_init (skip_list_t *list,
void
skip_list_fini (skip_list_t *list)
{
- skip_elt_t *elt;
- while ((elt = list->chains[0])) {
- /* XXX: make me faster. */
- skip_list_delete_given (list, elt);
+ skip_elt_t *elt;
+ int i;
+
+ while ((elt = list->chains[0])) {
+ skip_list_delete_given (list, elt);
+ }
+ for (i=0; i<MAX_LEVEL; i++) {
+ elt = list->freelists[i];
+ while (elt) {
+ skip_elt_t *nextfree = elt->prev;
+ free (ELT_DATA(elt));
+ elt = nextfree;
}
+ }
}
/*
@@ -271,6 +282,24 @@ random_level (void)
return level;
}
+static void *
+alloc_node_for_level (skip_list_t *list, unsigned level)
+{
+ if (list->freelists[level-1]) {
+ skip_elt_t *elt = list->freelists[level-1];
+ list->freelists[level-1] = elt->prev;
+ return ELT_DATA(elt);
+ }
+ return malloc (list->elt_size + (level-1) * sizeof (skip_elt_t *));
+}
+
+static void
+free_elt (skip_list_t *list, skip_elt_t *elt)
+{
+ elt->prev = list->freelists[elt->prev_index];
+ list->freelists[elt->prev_index] = elt;
+}
+
/*
* Insert 'data' into the list
*/
@@ -313,7 +342,7 @@ skip_list_insert (skip_list_t *list, voi
list->max_level = level;
}
- data_and_elt = malloc (list->elt_size + (level-1) * sizeof (skip_elt_t *));
+ data_and_elt = alloc_node_for_level (list, level);
memcpy (data_and_elt, data, list->data_size);
elt = (skip_elt_t *) (data_and_elt + list->data_size);
@@ -392,7 +421,7 @@ skip_list_delete (skip_list_t *list, voi
}
while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL)
list->max_level--;
- free (ELT_DATA (elt));
+ free_elt (list, elt);
}
void
@@ -431,5 +460,5 @@ skip_list_delete_given (skip_list_t *lis
}
while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL)
list->max_level--;
- free (ELT_DATA (elt));
+ free_elt (list, elt);
}
diff-tree de0e327b3d9aec50d970d8cfc881fb3949df59cc (from 67359d7a58c14851936345417833b1e610987c19)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Mon Nov 20 03:14:20 2006 +0200
Tweak comparators.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index bb72fc6..d3cdce4 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -116,21 +116,13 @@ typedef struct _cairo_bo_sweep_line {
int32_t current_y;
} cairo_bo_sweep_line_t;
-static int
-_cairo_bo_point32_compare (cairo_bo_point32_t *a,
- cairo_bo_point32_t *b)
+static inline int
+_cairo_bo_point32_compare (cairo_bo_point32_t const *a,
+ cairo_bo_point32_t const *b)
{
- if (a->y > b->y)
- return 1;
- else if (a->y < b->y)
- return -1;
-
- if (a->x > b->x)
- return 1;
- else if (a->x < b->x)
- return -1;
-
- return 0;
+ int cmp = a->y - b->y;
+ if (cmp) return cmp;
+ return a->x - b->x;
}
/* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
@@ -177,23 +169,29 @@ _slope_compare (cairo_bo_edge_t *a,
* begins.
*/
int32_t adx = a->bottom.x - a->top.x;
- int32_t ady = a->bottom.y - a->top.y;
-
int32_t bdx = b->bottom.x - b->top.x;
- int32_t bdy = b->bottom.y - b->top.y;
- int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
- int64_t bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
+ /* Since the dy's are all positive by construction we can fast
+ * path the case where the two edges point in different directions
+ * with respect to x. */
+ if ((adx ^ bdx) < 0) {
+ return adx < 0 ? -1 : +1;
+ }
+ else {
+ int32_t ady = a->bottom.y - a->top.y;
+ int32_t bdy = b->bottom.y - b->top.y;
+ int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
+ int64_t bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
- /* if (adx * bdy > bdx * ady) */
- if (_cairo_int64_gt (adx_bdy, bdx_ady))
- return 1;
-
- /* if (adx * bdy < bdx * ady) */
- if (_cairo_int64_lt (adx_bdy, bdx_ady))
- return -1;
+ /* if (adx * bdy > bdx * ady) */
+ if (_cairo_int64_gt (adx_bdy, bdx_ady))
+ return 1;
- return 0;
+ /* if (adx * bdy < bdx * ady) */
+ if (_cairo_int64_lt (adx_bdy, bdx_ady))
+ return -1;
+ return 0;
+ }
}
static cairo_quorem64_t
@@ -328,9 +326,9 @@ _sweep_line_elt_compare (void *list,
edge_elt_b->edge);
}
-static int
-cairo_bo_event_compare (cairo_bo_event_t *a,
- cairo_bo_event_t *b)
+static inline int
+cairo_bo_event_compare (cairo_bo_event_t const *a,
+ cairo_bo_event_t const *b)
{
int cmp;
diff-tree 67359d7a58c14851936345417833b1e610987c19 (from 97f02dca5d97c9ab815abf881525542ba86cbb11)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Sat Nov 18 14:59:23 2006 +0200
Separate start and stop events from intersections (first try.)
Don't use the skip list for start and stop events, but presort
those first.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 4e544af..bb72fc6 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -100,7 +100,13 @@ typedef struct _cairo_bo_event {
#define SKIP_ELT_TO_EVENT(elt) SKIP_LIST_ELT_TO_DATA (cairo_bo_event_t, (elt))
-typedef skip_list_t cairo_bo_event_queue_t;
+typedef struct _cairo_bo_event_queue {
+ skip_list_t intersection_queue;
+
+ cairo_bo_event_t *startstop_events;
+ unsigned next_startstop_event_index;
+ unsigned num_startstop_events;
+} cairo_bo_event_queue_t;
/* This structure extends skip_list_t, which must come first. */
typedef struct _cairo_bo_sweep_line {
@@ -411,6 +417,22 @@ cairo_bo_event_compare_abstract (void *
return cairo_bo_event_compare (event_a, event_b);
}
+static int
+cairo_bo_event_compare_stable (void const *voida,
+ void const *voidb)
+{
+ cairo_bo_event_t const *a = voida;
+ cairo_bo_event_t const *b = voidb;
+ int cmp = cairo_bo_event_compare (a, b);
+ if (cmp)
+ return cmp;
+ if (a < b)
+ return -1;
+ if (a > b)
+ return +1;
+ return 0;
+}
+
static inline cairo_int64_t
det32_64 (int32_t a,
int32_t b,
@@ -641,34 +663,70 @@ _cairo_bo_event_queue_insert (cairo_bo_e
{
/* Don't insert if there's already an equivalent intersection event in the queue. */
if (event->type == CAIRO_BO_EVENT_TYPE_INTERSECTION &&
- skip_list_find (queue, event) != NULL)
+ skip_list_find (&queue->intersection_queue, event) != NULL)
{
return;
}
- skip_list_insert (queue, event);
+ skip_list_insert (&queue->intersection_queue, event);
}
static void
_cairo_bo_event_queue_delete (cairo_bo_event_queue_t *queue,
cairo_bo_event_t *event)
{
- skip_list_delete_given ( queue, &event->elt );
+ if (CAIRO_BO_EVENT_TYPE_INTERSECTION == event->type)
+ skip_list_delete_given ( &queue->intersection_queue, &event->elt );
}
-static void
+static cairo_bo_event_t *
+_cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
+{
+ skip_elt_t *elt = event_queue->intersection_queue.chains[0];
+ cairo_bo_event_t *intersection = elt ? SKIP_ELT_TO_EVENT (elt) : NULL;
+ cairo_bo_event_t *startstop = &event_queue->startstop_events[
+ event_queue->next_startstop_event_index];
+
+ if (event_queue->next_startstop_event_index == event_queue->num_startstop_events)
+ return intersection;
+
+ if (!intersection || cairo_bo_event_compare (startstop, intersection) <= 0)
+ {
+ event_queue->next_startstop_event_index++;
+ return startstop;
+ }
+ return intersection;
+}
+
+static cairo_status_t
_cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue,
cairo_bo_edge_t *edges,
int num_edges)
{
int i;
- cairo_bo_event_t event;
+ cairo_bo_event_t *events;
+
+ memset (event_queue, 0, sizeof(*event_queue));
- skip_list_init (event_queue,
+ skip_list_init (&event_queue->intersection_queue,
cairo_bo_event_compare_abstract,
sizeof (cairo_bo_event_t));
+ if (0 == num_edges)
+ return CAIRO_STATUS_SUCCESS;
+
+ /* The skip_elt_t field of a cairo_bo_event_t isn't used for start
+ * or stop events, so this allocation is safe. XXX: make the
+ * event type a union so it doesn't always contain the skip
+ * elt? */
+ events = calloc (2*num_edges, sizeof(cairo_bo_event_t));
+ if (!events)
+ return CAIRO_STATUS_NO_MEMORY;
+ event_queue->startstop_events = events;
+ event_queue->num_startstop_events = (unsigned)(2*num_edges);
+ event_queue->next_startstop_event_index = 0;
for (i = 0; i < num_edges; i++) {
+
/* We must not be given horizontal edges. */
assert (edges[i].top.y != edges[i].bottom.y);
@@ -678,20 +736,29 @@ _cairo_bo_event_queue_init (cairo_bo_eve
/* Initialize "middle" to top */
edges[i].middle = edges[i].top;
- _cairo_bo_event_init (&event,
+ _cairo_bo_event_init (&events[2*i],
CAIRO_BO_EVENT_TYPE_START,
&edges[i], NULL,
edges[i].top);
- _cairo_bo_event_queue_insert (event_queue, &event);
-
- _cairo_bo_event_init (&event,
+ _cairo_bo_event_init (&events[2*i+1],
CAIRO_BO_EVENT_TYPE_STOP,
&edges[i], NULL,
edges[i].bottom);
-
- _cairo_bo_event_queue_insert (event_queue, &event);
}
+
+ qsort (events, (unsigned)(2*num_edges),
+ sizeof(cairo_bo_event_t),
+ cairo_bo_event_compare_stable);
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static void
+_cairo_bo_event_queue_fini (cairo_bo_event_queue_t *event_queue)
+{
+ skip_list_fini (&event_queue->intersection_queue);
+ if (event_queue->startstop_events)
+ free (event_queue->startstop_events);
}
static void
@@ -741,6 +808,12 @@ _cairo_bo_sweep_line_init (cairo_bo_swee
}
static void
+_cairo_bo_sweep_line_fini (cairo_bo_sweep_line_t *sweep_line)
+{
+ skip_list_fini (&sweep_line->active_edges);
+}
+
+static void
_cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t *sweep_line,
cairo_bo_edge_t *edge)
{
@@ -862,9 +935,11 @@ _cairo_bo_event_print (cairo_bo_event_t
}
static void
-_cairo_bo_event_queue_print (cairo_bo_event_queue_t *queue)
+_cairo_bo_event_queue_print (cairo_bo_event_queue_t *event_queue)
{
skip_elt_t *elt;
+ /* XXX: fixme to print the start/stop array too. */
+ skip_list_t *queue = &event_queue->intersection_queue;
cairo_bo_event_t *event;
printf ("Event queue:\n");
@@ -1024,11 +1099,10 @@ _cairo_bentley_ottmann_tessellate_bo_edg
cairo_traps_t *traps,
int *num_intersections)
{
- cairo_status_t status;
+ cairo_status_t status = CAIRO_STATUS_SUCCESS;
int intersection_count = 0;
cairo_bo_event_queue_t event_queue;
cairo_bo_sweep_line_t sweep_line;
- skip_elt_t *elt;
cairo_bo_event_t *event, event_saved;
cairo_bo_edge_t *edge;
cairo_bo_edge_t *left, *right;
@@ -1054,17 +1128,16 @@ _cairo_bentley_ottmann_tessellate_bo_edg
while (1)
{
- elt = event_queue.chains[0];
- if (elt == NULL)
+ event = _cairo_bo_event_dequeue (&event_queue);
+ if (!event)
break;
- event = SKIP_ELT_TO_EVENT (elt);
if (event->point.y != sweep_line.current_y) {
status = _active_edges_to_traps (sweep_line.head,
sweep_line.current_y, event->point.y,
fill_rule, traps);
if (status)
- return status;
+ goto unwind;
sweep_line.current_y = event->point.y;
}
@@ -1147,8 +1220,10 @@ _cairo_bentley_ottmann_tessellate_bo_edg
}
*num_intersections = intersection_count;
-
- return CAIRO_STATUS_SUCCESS;
+ unwind:
+ _cairo_bo_sweep_line_fini (&sweep_line);
+ _cairo_bo_event_queue_fini (&event_queue);
+ return status;
}
cairo_status_t
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h
index 616609e..74d495c 100644
--- a/src/cairo-skiplist-private.h
+++ b/src/cairo-skiplist-private.h
@@ -66,6 +66,13 @@ skip_list_init (skip_list_t *list,
skip_list_compare_t compare,
size_t elt_size);
+
+/* Deallocate resources associated with a skip list and all elements
+ * in it. (XXX: currently this simply deletes all elements.)
+ */
+void
+skip_list_fini (skip_list_t *list);
+
/* Insert a new element into the list at the correct sort order as
* determined by compare. Data will be copied (elt_size bytes from
* <data> via memcpy). The new element is returned. */
diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
index f7b296b..07c76d2 100644
--- a/src/cairo-skiplist.c
+++ b/src/cairo-skiplist.c
@@ -239,6 +239,16 @@ skip_list_init (skip_list_t *list,
list->max_level = 0;
}
+void
+skip_list_fini (skip_list_t *list)
+{
+ skip_elt_t *elt;
+ while ((elt = list->chains[0])) {
+ /* XXX: make me faster. */
+ skip_list_delete_given (list, elt);
+ }
+}
+
/*
* Generate a random level number, distributed
* so that each level is 1/4 as likely as the one before
diff-tree 97f02dca5d97c9ab815abf881525542ba86cbb11 (from 99f8a5313d336a2779689122feef03b874ed930e)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Sat Nov 18 01:08:56 2006 +0200
Avoid a skip-list lookup when deactivating edges.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 7b892f6..4e544af 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -653,7 +653,7 @@ static void
_cairo_bo_event_queue_delete (cairo_bo_event_queue_t *queue,
cairo_bo_event_t *event)
{
- skip_list_delete (queue, event);
+ skip_list_delete_given ( queue, &event->elt );
}
static void
diff-tree 99f8a5313d336a2779689122feef03b874ed930e (from fd8cd39cda7bfde429d840ffd7d5c78ac3045505)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Sat Nov 18 01:01:04 2006 +0200
Special cases for skip list comparators.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 960aa0d..7b892f6 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -204,6 +204,16 @@ edge_x_for_y (cairo_bo_edge_t *edge,
int64_t numerator;
cairo_quorem64_t quorem;
+ if (edge->middle.y == y) {
+ quorem.quo = edge->middle.x;
+ quorem.rem = 0;
+ return quorem;
+ }
+ if (edge->bottom.y == y) {
+ quorem.quo = edge->bottom.x;
+ quorem.rem = 0;
+ return quorem;
+ }
if (dy == 0) {
quorem.quo = _cairo_int32_to_int64 (edge->top.x);
quorem.rem = 0;
@@ -224,13 +234,38 @@ _cairo_bo_sweep_line_compare_edges (cair
cairo_bo_edge_t *a,
cairo_bo_edge_t *b)
{
- cairo_quorem64_t ax = edge_x_for_y (a, sweep_line->current_y);
- cairo_quorem64_t bx = edge_x_for_y (b, sweep_line->current_y);
+ cairo_quorem64_t ax;
+ cairo_quorem64_t bx;
int cmp;
if (a == b)
return 0;
+ /* don't bother solving for abscissa if the edges' bounding boxes
+ * can be used to order them. */
+ {
+ int32_t amin, amax;
+ int32_t bmin, bmax;
+ if (a->middle.x < a->bottom.x) {
+ amin = a->middle.x;
+ amax = a->bottom.x;
+ } else {
+ amin = a->bottom.x;
+ amax = a->middle.x;
+ }
+ if (b->middle.x < b->bottom.x) {
+ bmin = b->middle.x;
+ bmax = b->bottom.x;
+ } else {
+ bmin = b->bottom.x;
+ bmax = b->middle.x;
+ }
+ if (amax < bmin) return -1;
+ if (amin > bmax) return +1;
+ }
+
+ ax = edge_x_for_y (a, sweep_line->current_y);
+ bx = edge_x_for_y (b, sweep_line->current_y);
if (ax.quo > bx.quo)
return 1;
else if (ax.quo < bx.quo)
diff-tree fd8cd39cda7bfde429d840ffd7d5c78ac3045505 (from d957e59744ba6fc482d3ddbce041877e703c0489)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Fri Nov 17 12:24:44 2006 +0200
Use an LFSR instead of random().
diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
index 49b78de..f7b296b 100644
--- a/src/cairo-skiplist.c
+++ b/src/cairo-skiplist.c
@@ -32,6 +32,193 @@
#define ELT_DATA(elt) (void *) ((char*) (elt) - list->data_size)
#define NEXT_TO_ELT(next) (skip_elt_t *) ((char *) (next) - offsetof (skip_elt_t, next))
+/* Four 256 element lookup tables back to back implementing a linear
+ * feedback shift register of degree 32. */
+static unsigned const lfsr_lut[1024] = {
+ 0x00000000, 0x9a795537, 0xae8bff59, 0x34f2aa6e, 0xc76eab85, 0x5d17feb2,
+ 0x69e554dc, 0xf39c01eb, 0x14a4023d, 0x8edd570a, 0xba2ffd64, 0x2056a853,
+ 0xd3caa9b8, 0x49b3fc8f, 0x7d4156e1, 0xe73803d6, 0x2948047a, 0xb331514d,
+ 0x87c3fb23, 0x1dbaae14, 0xee26afff, 0x745ffac8, 0x40ad50a6, 0xdad40591,
+ 0x3dec0647, 0xa7955370, 0x9367f91e, 0x091eac29, 0xfa82adc2, 0x60fbf8f5,
+ 0x5409529b, 0xce7007ac, 0x529008f4, 0xc8e95dc3, 0xfc1bf7ad, 0x6662a29a,
+ 0x95fea371, 0x0f87f646, 0x3b755c28, 0xa10c091f, 0x46340ac9, 0xdc4d5ffe,
+ 0xe8bff590, 0x72c6a0a7, 0x815aa14c, 0x1b23f47b, 0x2fd15e15, 0xb5a80b22,
+ 0x7bd80c8e, 0xe1a159b9, 0xd553f3d7, 0x4f2aa6e0, 0xbcb6a70b, 0x26cff23c,
+ 0x123d5852, 0x88440d65, 0x6f7c0eb3, 0xf5055b84, 0xc1f7f1ea, 0x5b8ea4dd,
+ 0xa812a536, 0x326bf001, 0x06995a6f, 0x9ce00f58, 0xa52011e8, 0x3f5944df,
+ 0x0babeeb1, 0x91d2bb86, 0x624eba6d, 0xf837ef5a, 0xccc54534, 0x56bc1003,
+ 0xb18413d5, 0x2bfd46e2, 0x1f0fec8c, 0x8576b9bb, 0x76eab850, 0xec93ed67,
+ 0xd8614709, 0x4218123e, 0x8c681592, 0x161140a5, 0x22e3eacb, 0xb89abffc,
+ 0x4b06be17, 0xd17feb20, 0xe58d414e, 0x7ff41479, 0x98cc17af, 0x02b54298,
+ 0x3647e8f6, 0xac3ebdc1, 0x5fa2bc2a, 0xc5dbe91d, 0xf1294373, 0x6b501644,
+ 0xf7b0191c, 0x6dc94c2b, 0x593be645, 0xc342b372, 0x30deb299, 0xaaa7e7ae,
+ 0x9e554dc0, 0x042c18f7, 0xe3141b21, 0x796d4e16, 0x4d9fe478, 0xd7e6b14f,
+ 0x247ab0a4, 0xbe03e593, 0x8af14ffd, 0x10881aca, 0xdef81d66, 0x44814851,
+ 0x7073e23f, 0xea0ab708, 0x1996b6e3, 0x83efe3d4, 0xb71d49ba, 0x2d641c8d,
+ 0xca5c1f5b, 0x50254a6c, 0x64d7e002, 0xfeaeb535, 0x0d32b4de, 0x974be1e9,
+ 0xa3b94b87, 0x39c01eb0, 0xd03976e7, 0x4a4023d0, 0x7eb289be, 0xe4cbdc89,
+ 0x1757dd62, 0x8d2e8855, 0xb9dc223b, 0x23a5770c, 0xc49d74da, 0x5ee421ed,
+ 0x6a168b83, 0xf06fdeb4, 0x03f3df5f, 0x998a8a68, 0xad782006, 0x37017531,
+ 0xf971729d, 0x630827aa, 0x57fa8dc4, 0xcd83d8f3, 0x3e1fd918, 0xa4668c2f,
+ 0x90942641, 0x0aed7376, 0xedd570a0, 0x77ac2597, 0x435e8ff9, 0xd927dace,
+ 0x2abbdb25, 0xb0c28e12, 0x8430247c, 0x1e49714b, 0x82a97e13, 0x18d02b24,
+ 0x2c22814a, 0xb65bd47d, 0x45c7d596, 0xdfbe80a1, 0xeb4c2acf, 0x71357ff8,
+ 0x960d7c2e, 0x0c742919, 0x38868377, 0xa2ffd640, 0x5163d7ab, 0xcb1a829c,
+ 0xffe828f2, 0x65917dc5, 0xabe17a69, 0x31982f5e, 0x056a8530, 0x9f13d007,
+ 0x6c8fd1ec, 0xf6f684db, 0xc2042eb5, 0x587d7b82, 0xbf457854, 0x253c2d63,
+ 0x11ce870d, 0x8bb7d23a, 0x782bd3d1, 0xe25286e6, 0xd6a02c88, 0x4cd979bf,
+ 0x7519670f, 0xef603238, 0xdb929856, 0x41ebcd61, 0xb277cc8a, 0x280e99bd,
+ 0x1cfc33d3, 0x868566e4, 0x61bd6532, 0xfbc43005, 0xcf369a6b, 0x554fcf5c,
+ 0xa6d3ceb7, 0x3caa9b80, 0x085831ee, 0x922164d9, 0x5c516375, 0xc6283642,
+ 0xf2da9c2c, 0x68a3c91b, 0x9b3fc8f0, 0x01469dc7, 0x35b437a9, 0xafcd629e,
+ 0x48f56148, 0xd28c347f, 0xe67e9e11, 0x7c07cb26, 0x8f9bcacd, 0x15e29ffa,
+ 0x21103594, 0xbb6960a3, 0x27896ffb, 0xbdf03acc, 0x890290a2, 0x137bc595,
+ 0xe0e7c47e, 0x7a9e9149, 0x4e6c3b27, 0xd4156e10, 0x332d6dc6, 0xa95438f1,
+ 0x9da6929f, 0x07dfc7a8, 0xf443c643, 0x6e3a9374, 0x5ac8391a, 0xc0b16c2d,
+ 0x0ec16b81, 0x94b83eb6, 0xa04a94d8, 0x3a33c1ef, 0xc9afc004, 0x53d69533,
+ 0x67243f5d, 0xfd5d6a6a, 0x1a6569bc, 0x801c3c8b, 0xb4ee96e5, 0x2e97c3d2,
+ 0xdd0bc239, 0x4772970e, 0x73803d60, 0xe9f96857, 0x00000000, 0x3a0bb8f9,
+ 0x741771f2, 0x4e1cc90b, 0xe82ee3e4, 0xd2255b1d, 0x9c399216, 0xa6322aef,
+ 0x4a2492ff, 0x702f2a06, 0x3e33e30d, 0x04385bf4, 0xa20a711b, 0x9801c9e2,
+ 0xd61d00e9, 0xec16b810, 0x944925fe, 0xae429d07, 0xe05e540c, 0xda55ecf5,
+ 0x7c67c61a, 0x466c7ee3, 0x0870b7e8, 0x327b0f11, 0xde6db701, 0xe4660ff8,
+ 0xaa7ac6f3, 0x90717e0a, 0x364354e5, 0x0c48ec1c, 0x42542517, 0x785f9dee,
+ 0xb2eb1ecb, 0x88e0a632, 0xc6fc6f39, 0xfcf7d7c0, 0x5ac5fd2f, 0x60ce45d6,
+ 0x2ed28cdd, 0x14d93424, 0xf8cf8c34, 0xc2c434cd, 0x8cd8fdc6, 0xb6d3453f,
+ 0x10e16fd0, 0x2aead729, 0x64f61e22, 0x5efda6db, 0x26a23b35, 0x1ca983cc,
+ 0x52b54ac7, 0x68bef23e, 0xce8cd8d1, 0xf4876028, 0xba9ba923, 0x809011da,
+ 0x6c86a9ca, 0x568d1133, 0x1891d838, 0x229a60c1, 0x84a84a2e, 0xbea3f2d7,
+ 0xf0bf3bdc, 0xcab48325, 0xffaf68a1, 0xc5a4d058, 0x8bb81953, 0xb1b3a1aa,
+ 0x17818b45, 0x2d8a33bc, 0x6396fab7, 0x599d424e, 0xb58bfa5e, 0x8f8042a7,
+ 0xc19c8bac, 0xfb973355, 0x5da519ba, 0x67aea143, 0x29b26848, 0x13b9d0b1,
+ 0x6be64d5f, 0x51edf5a6, 0x1ff13cad, 0x25fa8454, 0x83c8aebb, 0xb9c31642,
+ 0xf7dfdf49, 0xcdd467b0, 0x21c2dfa0, 0x1bc96759, 0x55d5ae52, 0x6fde16ab,
+ 0xc9ec3c44, 0xf3e784bd, 0xbdfb4db6, 0x87f0f54f, 0x4d44766a, 0x774fce93,
+ 0x39530798, 0x0358bf61, 0xa56a958e, 0x9f612d77, 0xd17de47c, 0xeb765c85,
+ 0x0760e495, 0x3d6b5c6c, 0x73779567, 0x497c2d9e, 0xef4e0771, 0xd545bf88,
+ 0x9b597683, 0xa152ce7a, 0xd90d5394, 0xe306eb6d, 0xad1a2266, 0x97119a9f,
+ 0x3123b070, 0x0b280889, 0x4534c182, 0x7f3f797b, 0x9329c16b, 0xa9227992,
+ 0xe73eb099, 0xdd350860, 0x7b07228f, 0x410c9a76, 0x0f10537d, 0x351beb84,
+ 0x65278475, 0x5f2c3c8c, 0x1130f587, 0x2b3b4d7e, 0x8d096791, 0xb702df68,
+ 0xf91e1663, 0xc315ae9a, 0x2f03168a, 0x1508ae73, 0x5b146778, 0x611fdf81,
+ 0xc72df56e, 0xfd264d97, 0xb33a849c, 0x89313c65, 0xf16ea18b, 0xcb651972,
+ 0x8579d079, 0xbf726880, 0x1940426f, 0x234bfa96, 0x6d57339d, 0x575c8b64,
+ 0xbb4a3374, 0x81418b8d, 0xcf5d4286, 0xf556fa7f, 0x5364d090, 0x696f6869,
+ 0x2773a162, 0x1d78199b, 0xd7cc9abe, 0xedc72247, 0xa3dbeb4c, 0x99d053b5,
+ 0x3fe2795a, 0x05e9c1a3, 0x4bf508a8, 0x71feb051, 0x9de80841, 0xa7e3b0b8,
+ 0xe9ff79b3, 0xd3f4c14a, 0x75c6eba5, 0x4fcd535c, 0x01d19a57, 0x3bda22ae,
+ 0x4385bf40, 0x798e07b9, 0x3792ceb2, 0x0d99764b, 0xabab5ca4, 0x91a0e45d,
+ 0xdfbc2d56, 0xe5b795af, 0x09a12dbf, 0x33aa9546, 0x7db65c4d, 0x47bde4b4,
+ 0xe18fce5b, 0xdb8476a2, 0x9598bfa9, 0xaf930750, 0x9a88ecd4, 0xa083542d,
+ 0xee9f9d26, 0xd49425df, 0x72a60f30, 0x48adb7c9, 0x06b17ec2, 0x3cbac63b,
+ 0xd0ac7e2b, 0xeaa7c6d2, 0xa4bb0fd9, 0x9eb0b720, 0x38829dcf, 0x02892536,
+ 0x4c95ec3d, 0x769e54c4, 0x0ec1c92a, 0x34ca71d3, 0x7ad6b8d8, 0x40dd0021,
+ 0xe6ef2ace, 0xdce49237, 0x92f85b3c, 0xa8f3e3c5, 0x44e55bd5, 0x7eeee32c,
+ 0x30f22a27, 0x0af992de, 0xaccbb831, 0x96c000c8, 0xd8dcc9c3, 0xe2d7713a,
+ 0x2863f21f, 0x12684ae6, 0x5c7483ed, 0x667f3b14, 0xc04d11fb, 0xfa46a902,
+ 0xb45a6009, 0x8e51d8f0, 0x624760e0, 0x584cd819, 0x16501112, 0x2c5ba9eb,
+ 0x8a698304, 0xb0623bfd, 0xfe7ef2f6, 0xc4754a0f, 0xbc2ad7e1, 0x86216f18,
+ 0xc83da613, 0xf2361eea, 0x54043405, 0x6e0f8cfc, 0x201345f7, 0x1a18fd0e,
+ 0xf60e451e, 0xcc05fde7, 0x821934ec, 0xb8128c15, 0x1e20a6fa, 0x242b1e03,
+ 0x6a37d708, 0x503c6ff1, 0x00000000, 0xca4f08ea, 0x0ee744e3, 0xc4a84c09,
+ 0x1dce89c6, 0xd781812c, 0x1329cd25, 0xd966c5cf, 0x3b9d138c, 0xf1d21b66,
+ 0x357a576f, 0xff355f85, 0x26539a4a, 0xec1c92a0, 0x28b4dea9, 0xe2fbd643,
+ 0x773a2718, 0xbd752ff2, 0x79dd63fb, 0xb3926b11, 0x6af4aede, 0xa0bba634,
+ 0x6413ea3d, 0xae5ce2d7, 0x4ca73494, 0x86e83c7e, 0x42407077, 0x880f789d,
+ 0x5169bd52, 0x9b26b5b8, 0x5f8ef9b1, 0x95c1f15b, 0xee744e30, 0x243b46da,
+ 0xe0930ad3, 0x2adc0239, 0xf3bac7f6, 0x39f5cf1c, 0xfd5d8315, 0x37128bff,
+ 0xd5e95dbc, 0x1fa65556, 0xdb0e195f, 0x114111b5, 0xc827d47a, 0x0268dc90,
+ 0xc6c09099, 0x0c8f9873, 0x994e6928, 0x530161c2, 0x97a92dcb, 0x5de62521,
+ 0x8480e0ee, 0x4ecfe804, 0x8a67a40d, 0x4028ace7, 0xa2d37aa4, 0x689c724e,
+ 0xac343e47, 0x667b36ad, 0xbf1df362, 0x7552fb88, 0xb1fab781, 0x7bb5bf6b,
+ 0x4691c957, 0x8cdec1bd, 0x48768db4, 0x8239855e, 0x5b5f4091, 0x9110487b,
+ 0x55b80472, 0x9ff70c98, 0x7d0cdadb, 0xb743d231, 0x73eb9e38, 0xb9a496d2,
+ 0x60c2531d, 0xaa8d5bf7, 0x6e2517fe, 0xa46a1f14, 0x31abee4f, 0xfbe4e6a5,
+ 0x3f4caaac, 0xf503a246, 0x2c656789, 0xe62a6f63, 0x2282236a, 0xe8cd2b80,
+ 0x0a36fdc3, 0xc079f529, 0x04d1b920, 0xce9eb1ca, 0x17f87405, 0xddb77cef,
+ 0x191f30e6, 0xd350380c, 0xa8e58767, 0x62aa8f8d, 0xa602c384, 0x6c4dcb6e,
+ 0xb52b0ea1, 0x7f64064b, 0xbbcc4a42, 0x718342a8, 0x937894eb, 0x59379c01,
+ 0x9d9fd008, 0x57d0d8e2, 0x8eb61d2d, 0x44f915c7, 0x805159ce, 0x4a1e5124,
+ 0xdfdfa07f, 0x1590a895, 0xd138e49c, 0x1b77ec76, 0xc21129b9, 0x085e2153,
+ 0xccf66d5a, 0x06b965b0, 0xe442b3f3, 0x2e0dbb19, 0xeaa5f710, 0x20eafffa,
+ 0xf98c3a35, 0x33c332df, 0xf76b7ed6, 0x3d24763c, 0x8d2392ae, 0x476c9a44,
+ 0x83c4d64d, 0x498bdea7, 0x90ed1b68, 0x5aa21382, 0x9e0a5f8b, 0x54455761,
+ 0xb6be8122, 0x7cf189c8, 0xb859c5c1, 0x7216cd2b, 0xab7008e4, 0x613f000e,
+ 0xa5974c07, 0x6fd844ed, 0xfa19b5b6, 0x3056bd5c, 0xf4fef155, 0x3eb1f9bf,
+ 0xe7d73c70, 0x2d98349a, 0xe9307893, 0x237f7079, 0xc184a63a, 0x0bcbaed0,
+ 0xcf63e2d9, 0x052cea33, 0xdc4a2ffc, 0x16052716, 0xd2ad6b1f, 0x18e263f5,
+ 0x6357dc9e, 0xa918d474, 0x6db0987d, 0xa7ff9097, 0x7e995558, 0xb4d65db2,
+ 0x707e11bb, 0xba311951, 0x58cacf12, 0x9285c7f8, 0x562d8bf1, 0x9c62831b,
+ 0x450446d4, 0x8f4b4e3e, 0x4be30237, 0x81ac0add, 0x146dfb86, 0xde22f36c,
+ 0x1a8abf65, 0xd0c5b78f, 0x09a37240, 0xc3ec7aaa, 0x074436a3, 0xcd0b3e49,
+ 0x2ff0e80a, 0xe5bfe0e0, 0x2117ace9, 0xeb58a403, 0x323e61cc, 0xf8716926,
+ 0x3cd9252f, 0xf6962dc5, 0xcbb25bf9, 0x01fd5313, 0xc5551f1a, 0x0f1a17f0,
+ 0xd67cd23f, 0x1c33dad5, 0xd89b96dc, 0x12d49e36, 0xf02f4875, 0x3a60409f,
+ 0xfec80c96, 0x3487047c, 0xede1c1b3, 0x27aec959, 0xe3068550, 0x29498dba,
+ 0xbc887ce1, 0x76c7740b, 0xb26f3802, 0x782030e8, 0xa146f527, 0x6b09fdcd,
+ 0xafa1b1c4, 0x65eeb92e, 0x87156f6d, 0x4d5a6787, 0x89f22b8e, 0x43bd2364,
+ 0x9adbe6ab, 0x5094ee41, 0x943ca248, 0x5e73aaa2, 0x25c615c9, 0xef891d23,
+ 0x2b21512a, 0xe16e59c0, 0x38089c0f, 0xf24794e5, 0x36efd8ec, 0xfca0d006,
+ 0x1e5b0645, 0xd4140eaf, 0x10bc42a6, 0xdaf34a4c, 0x03958f83, 0xc9da8769,
+ 0x0d72cb60, 0xc73dc38a, 0x52fc32d1, 0x98b33a3b, 0x5c1b7632, 0x96547ed8,
+ 0x4f32bb17, 0x857db3fd, 0x41d5fff4, 0x8b9af71e, 0x6961215d, 0xa32e29b7,
+ 0x678665be, 0xadc96d54, 0x74afa89b, 0xbee0a071, 0x7a48ec78, 0xb007e492,
+ 0x00000000, 0x803e706b, 0x9a05b5e1, 0x1a3bc58a, 0xae723ef5, 0x2e4c4e9e,
+ 0x34778b14, 0xb449fb7f, 0xc69d28dd, 0x46a358b6, 0x5c989d3c, 0xdca6ed57,
+ 0x68ef1628, 0xe8d16643, 0xf2eaa3c9, 0x72d4d3a2, 0x1743048d, 0x977d74e6,
+ 0x8d46b16c, 0x0d78c107, 0xb9313a78, 0x390f4a13, 0x23348f99, 0xa30afff2,
+ 0xd1de2c50, 0x51e05c3b, 0x4bdb99b1, 0xcbe5e9da, 0x7fac12a5, 0xff9262ce,
+ 0xe5a9a744, 0x6597d72f, 0x2e86091a, 0xaeb87971, 0xb483bcfb, 0x34bdcc90,
+ 0x80f437ef, 0x00ca4784, 0x1af1820e, 0x9acff265, 0xe81b21c7, 0x682551ac,
+ 0x721e9426, 0xf220e44d, 0x46691f32, 0xc6576f59, 0xdc6caad3, 0x5c52dab8,
+ 0x39c50d97, 0xb9fb7dfc, 0xa3c0b876, 0x23fec81d, 0x97b73362, 0x17894309,
+ 0x0db28683, 0x8d8cf6e8, 0xff58254a, 0x7f665521, 0x655d90ab, 0xe563e0c0,
+ 0x512a1bbf, 0xd1146bd4, 0xcb2fae5e, 0x4b11de35, 0x5d0c1234, 0xdd32625f,
+ 0xc709a7d5, 0x4737d7be, 0xf37e2cc1, 0x73405caa, 0x697b9920, 0xe945e94b,
+ 0x9b913ae9, 0x1baf4a82, 0x01948f08, 0x81aaff63, 0x35e3041c, 0xb5dd7477,
+ 0xafe6b1fd, 0x2fd8c196, 0x4a4f16b9, 0xca7166d2, 0xd04aa358, 0x5074d333,
+ 0xe43d284c, 0x64035827, 0x7e389dad, 0xfe06edc6, 0x8cd23e64, 0x0cec4e0f,
+ 0x16d78b85, 0x96e9fbee, 0x22a00091, 0xa29e70fa, 0xb8a5b570, 0x389bc51b,
+ 0x738a1b2e, 0xf3b46b45, 0xe98faecf, 0x69b1dea4, 0xddf825db, 0x5dc655b0,
+ 0x47fd903a, 0xc7c3e051, 0xb51733f3, 0x35294398, 0x2f128612, 0xaf2cf679,
+ 0x1b650d06, 0x9b5b7d6d, 0x8160b8e7, 0x015ec88c, 0x64c91fa3, 0xe4f76fc8,
+ 0xfeccaa42, 0x7ef2da29, 0xcabb2156, 0x4a85513d, 0x50be94b7, 0xd080e4dc,
+ 0xa254377e, 0x226a4715, 0x3851829f, 0xb86ff2f4, 0x0c26098b, 0x8c1879e0,
+ 0x9623bc6a, 0x161dcc01, 0xba182468, 0x3a265403, 0x201d9189, 0xa023e1e2,
+ 0x146a1a9d, 0x94546af6, 0x8e6faf7c, 0x0e51df17, 0x7c850cb5, 0xfcbb7cde,
+ 0xe680b954, 0x66bec93f, 0xd2f73240, 0x52c9422b, 0x48f287a1, 0xc8ccf7ca,
+ 0xad5b20e5, 0x2d65508e, 0x375e9504, 0xb760e56f, 0x03291e10, 0x83176e7b,
+ 0x992cabf1, 0x1912db9a, 0x6bc60838, 0xebf87853, 0xf1c3bdd9, 0x71fdcdb2,
+ 0xc5b436cd, 0x458a46a6, 0x5fb1832c, 0xdf8ff347, 0x949e2d72, 0x14a05d19,
+ 0x0e9b9893, 0x8ea5e8f8, 0x3aec1387, 0xbad263ec, 0xa0e9a666, 0x20d7d60d,
+ 0x520305af, 0xd23d75c4, 0xc806b04e, 0x4838c025, 0xfc713b5a, 0x7c4f4b31,
+ 0x66748ebb, 0xe64afed0, 0x83dd29ff, 0x03e35994, 0x19d89c1e, 0x99e6ec75,
+ 0x2daf170a, 0xad916761, 0xb7aaa2eb, 0x3794d280, 0x45400122, 0xc57e7149,
+ 0xdf45b4c3, 0x5f7bc4a8, 0xeb323fd7, 0x6b0c4fbc, 0x71378a36, 0xf109fa5d,
+ 0xe714365c, 0x672a4637, 0x7d1183bd, 0xfd2ff3d6, 0x496608a9, 0xc95878c2,
+ 0xd363bd48, 0x535dcd23, 0x21891e81, 0xa1b76eea, 0xbb8cab60, 0x3bb2db0b,
+ 0x8ffb2074, 0x0fc5501f, 0x15fe9595, 0x95c0e5fe, 0xf05732d1, 0x706942ba,
+ 0x6a528730, 0xea6cf75b, 0x5e250c24, 0xde1b7c4f, 0xc420b9c5, 0x441ec9ae,
+ 0x36ca1a0c, 0xb6f46a67, 0xaccfafed, 0x2cf1df86, 0x98b824f9, 0x18865492,
+ 0x02bd9118, 0x8283e173, 0xc9923f46, 0x49ac4f2d, 0x53978aa7, 0xd3a9facc,
+ 0x67e001b3, 0xe7de71d8, 0xfde5b452, 0x7ddbc439, 0x0f0f179b, 0x8f3167f0,
+ 0x950aa27a, 0x1534d211, 0xa17d296e, 0x21435905, 0x3b789c8f, 0xbb46ece4,
+ 0xded13bcb, 0x5eef4ba0, 0x44d48e2a, 0xc4eafe41, 0x70a3053e, 0xf09d7555,
+ 0xeaa6b0df, 0x6a98c0b4, 0x184c1316, 0x9872637d, 0x8249a6f7, 0x0277d69c,
+ 0xb63e2de3, 0x36005d88, 0x2c3b9802, 0xac05e869};
+
+static unsigned
+lfsr_random(void)
+{
+ static unsigned state = 0x12345678;
+ unsigned next;
+ next = lfsr_lut[((state>> 0) & 0xFF) + 0*256];
+ next ^= lfsr_lut[((state>> 8) & 0xFF) + 1*256];
+ next ^= lfsr_lut[((state>>16) & 0xFF) + 2*256];
+ next ^= lfsr_lut[((state>>24) & 0xFF) + 3*256];
+ return state = next;
+}
+
/*
* Initialize an empty skip list
*/
@@ -62,7 +249,7 @@ static int
random_level (void)
{
/* tricky bit -- each bit is '1' 75% of the time */
- long int bits = random () | random ();
+ long int bits = lfsr_random() | lfsr_random();
int level = 0;
while (++level < MAX_LEVEL)
diff-tree d957e59744ba6fc482d3ddbce041877e703c0489 (from 1da14262ea059836ae63b875c987fdb5c526db83)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Wed Nov 15 19:58:54 2006 +0200
Replace the 128 bit divrem by a 96/64 bit one.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 384372b..960aa0d 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -47,10 +47,15 @@ typedef struct _cairo_bo_point128 {
cairo_int128_t y;
} cairo_bo_point128_t;
-typedef struct _cairo_bo_point_quorem128 {
- cairo_quorem128_t x;
- cairo_quorem128_t y;
-} cairo_bo_point_quorem128_t;
+typedef struct _cairo_bo_intersect_ordinate {
+ int32_t ordinate;
+ enum { EXACT, INEXACT } exactness;
+} cairo_bo_intersect_ordinate_t;
+
+typedef struct _cairo_bo_intersect_point {
+ cairo_bo_intersect_ordinate_t x;
+ cairo_bo_intersect_ordinate_t y;
+} cairo_bo_intersect_point_t;
typedef struct _cairo_bo_edge cairo_bo_edge_t;
typedef struct _sweep_line_elt sweep_line_elt_t;
@@ -414,7 +419,7 @@ det64_128 (cairo_int64_t a,
static cairo_bo_status_t
intersect_lines (cairo_bo_edge_t *a,
cairo_bo_edge_t *b,
- cairo_bo_point_quorem128_t *intersection)
+ cairo_bo_intersect_point_t *intersection)
{
cairo_int64_t a_det, b_det;
@@ -430,6 +435,7 @@ intersect_lines (cairo_bo_edge_t *a,
int32_t dy2 = b->top.y - b->bottom.y;
cairo_int64_t den_det = det32_64 (dx1, dy1, dx2, dy2);
+ cairo_quorem64_t qr;
if (_cairo_int64_eq (den_det, 0))
return CAIRO_BO_STATUS_PARALLEL;
@@ -442,38 +448,38 @@ intersect_lines (cairo_bo_edge_t *a,
b->bottom.x, b->bottom.y);
/* x = det (a_det, dx1, b_det, dx2) / den_det */
- intersection->x = _cairo_int128_divrem (det64_128 (a_det, dx1,
- b_det, dx2),
- _cairo_int64_to_int128 (den_det));
+ qr = _cairo_int_96by64_32x64_divrem (det64_128 (a_det, dx1,
+ b_det, dx2),
+ den_det);
+ if (_cairo_int64_eq (qr.rem,den_det))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+ intersection->x.ordinate = qr.quo;
+ intersection->x.exactness = qr.rem ? INEXACT : EXACT;
/* y = det (a_det, dy1, b_det, dy2) / den_det */
- intersection->y = _cairo_int128_divrem (det64_128 (a_det, dy1,
- b_det, dy2),
- _cairo_int64_to_int128 (den_det));
+ qr = _cairo_int_96by64_32x64_divrem (det64_128 (a_det, dy1,
+ b_det, dy2),
+ den_det);
+ if (_cairo_int64_eq (qr.rem, den_det))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+ intersection->y.ordinate = qr.quo;
+ intersection->y.exactness = qr.rem ? INEXACT : EXACT;
return CAIRO_BO_STATUS_INTERSECTION;
}
static int
-_cairo_quorem128_32_compare (cairo_quorem128_t a,
- int32_t b)
+_cairo_bo_intersect_ordinate_32_compare (cairo_bo_intersect_ordinate_t a,
+ int32_t b)
{
- /* XXX: Converting up to a int128_t here is silly, but I'm lazy. */
- cairo_int128_t b_128 = _cairo_int32_to_int128 (b);
- cairo_int128_t zero = _cairo_int32_to_int128 (0);
-
/* First compare the quotient */
- if (_cairo_int128_gt (a.quo, b_128))
- return 1;
- if (_cairo_int128_lt (a.quo, b_128))
+ if (a.ordinate > b)
+ return +1;
+ if (a.ordinate < b)
return -1;
-
/* With quotient identical, if remainder is 0 then compare equal */
- if (_cairo_int128_eq (a.rem, zero))
- return 0;
-
/* Otherwise, the non-zero remainder makes a > b */
- return 1;
+ return INEXACT == a.exactness;
}
/* Does the given edge contain the given point. The point must already
@@ -494,8 +500,8 @@ _cairo_quorem128_32_compare (cairo_quore
* in the implementation for more details.
*/
static cairo_bool_t
-_cairo_bo_edge_contains_point_quorem128 (cairo_bo_edge_t *edge,
- cairo_bo_point_quorem128_t *point)
+_cairo_bo_edge_contains_intersect_point (cairo_bo_edge_t *edge,
+ cairo_bo_intersect_point_t *point)
{
int cmp_top, cmp_bottom;
@@ -506,8 +512,8 @@ _cairo_bo_edge_contains_point_quorem128
* finder which needs them.
*/
- cmp_top = _cairo_quorem128_32_compare (point->y, edge->top.y);
- cmp_bottom = _cairo_quorem128_32_compare (point->y, edge->bottom.y);
+ cmp_top = _cairo_bo_intersect_ordinate_32_compare (point->y, edge->top.y);
+ cmp_bottom = _cairo_bo_intersect_ordinate_32_compare (point->y, edge->bottom.y);
if (cmp_top < 0 || cmp_bottom > 0)
{
@@ -531,9 +537,9 @@ _cairo_bo_edge_contains_point_quorem128
* considered as inside. */
if (cmp_top == 0)
- return (_cairo_quorem128_32_compare (point->x, edge->top.x) > 0);
+ return (_cairo_bo_intersect_ordinate_32_compare (point->x, edge->top.x) > 0);
else /* cmp_bottom == 0 */
- return (_cairo_quorem128_32_compare (point->x, edge->bottom.x) < 0);
+ return (_cairo_bo_intersect_ordinate_32_compare (point->x, edge->bottom.x) < 0);
}
/* Compute the intersection of two edges. The result is provided as a
@@ -558,16 +564,16 @@ _cairo_bo_edge_intersect (cairo_bo_edge_
cairo_bo_point32_t *intersection)
{
cairo_bo_status_t status;
- cairo_bo_point_quorem128_t quorem;
+ cairo_bo_intersect_point_t quorem;
status = intersect_lines (a, b, &quorem);
if (status)
return status;
- if (! _cairo_bo_edge_contains_point_quorem128 (a, &quorem))
+ if (! _cairo_bo_edge_contains_intersect_point (a, &quorem))
return CAIRO_BO_STATUS_NO_INTERSECTION;
- if (! _cairo_bo_edge_contains_point_quorem128 (b, &quorem))
+ if (! _cairo_bo_edge_contains_intersect_point (b, &quorem))
return CAIRO_BO_STATUS_NO_INTERSECTION;
/* Now that we've correctly compared the intersection point and
@@ -575,8 +581,8 @@ _cairo_bo_edge_intersect (cairo_bo_edge_
* no longer need any more bits of storage for the intersection
* than we do for our edge coordinates. We also no longer need the
* remainder from the division. */
- intersection->x = _cairo_int128_to_int32 (quorem.x.quo);
- intersection->y = _cairo_int128_to_int32 (quorem.y.quo);
+ intersection->x = quorem.x.ordinate;
+ intersection->y = quorem.y.ordinate;
return CAIRO_BO_STATUS_INTERSECTION;
}
diff-tree 1da14262ea059836ae63b875c987fdb5c526db83 (from 762bd1330d5e3148ddd60949866227cb75b782d6)
Author: Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Wed Nov 15 19:57:04 2006 +0200
A 96 by 64 bit divrem that produces a 32 bit quotient and 64 bit remainder.
diff --git a/src/cairo-wideint-private.h b/src/cairo-wideint-private.h
index 1841a44..3d5ae13 100644
--- a/src/cairo-wideint-private.h
+++ b/src/cairo-wideint-private.h
@@ -298,6 +298,14 @@ _cairo_uint128_divrem (cairo_uint128_t n
cairo_quorem128_t I
_cairo_int128_divrem (cairo_int128_t num, cairo_int128_t den);
+cairo_uquorem64_t I
+_cairo_uint_96by64_32x64_divrem (cairo_uint128_t num,
+ cairo_uint64_t den);
+
+cairo_quorem64_t I
+_cairo_int_96by64_32x64_divrem (cairo_int128_t num,
+ cairo_int64_t den);
+
#define _cairo_uint128_le(a,b) (!_cairo_uint128_gt(a,b))
#define _cairo_uint128_ne(a,b) (!_cairo_uint128_eq(a,b))
#define _cairo_uint128_ge(a,b) (!_cairo_uint128_lt(a,b))
diff --git a/src/cairo-wideint.c b/src/cairo-wideint.c
index da68f1b..4de3994 100644
--- a/src/cairo-wideint.c
+++ b/src/cairo-wideint.c
@@ -656,3 +656,155 @@ _cairo_int128_divrem (cairo_int128_t num
qr.quo = uqr.quo;
return qr;
}
+
+/**
+ * _cairo_uint_96by64_32x64_divrem:
+ *
+ * Compute a 32 bit quotient and 64 bit remainder of a 96 bit unsigned
+ * dividend and 64 bit divisor. If the quotient doesn't fit into 32
+ * bits then the returned remainder is equal to the divisor, and the
+ * qoutient is the largest representable 64 bit integer. It is an
+ * error to call this function with the high 32 bits of @num being
+ * non-zero. */
+cairo_uquorem64_t
+_cairo_uint_96by64_32x64_divrem (cairo_uint128_t num,
+ cairo_uint64_t den)
+{
+ cairo_uquorem64_t result;
+ uint64_t B = _cairo_uint32s_to_uint64 (1, 0);
+
+ /* These are the high 64 bits of the *96* bit numerator. We're
+ * going to represent the numerator as xB + y, where x is a 64,
+ * and y is a 32 bit number. */
+ cairo_uint64_t x = _cairo_uint128_to_uint64 (_cairo_uint128_rsl(num, 32));
+
+ /* Initialise the result to indicate overflow. */
+ result.quo = _cairo_uint32s_to_uint64 (-1U, -1U);
+ result.rem = den;
+
+ /* Don't bother if the quotient is going to overflow. */
+ if (_cairo_uint64_ge (x, den)) {
+ return /* overflow */ result;
+ }
+
+ if (_cairo_uint64_lt (x, B)) {
+ /* When the final quotient is known to fit in 32 bits, then
+ * num < 2^64 if and only if den < 2^32. */
+ return _cairo_uint64_divrem (_cairo_uint128_to_uint64 (num), den);
+ }
+ else {
+ /* Denominator is >= 2^32. the numerator is >= 2^64, and the
+ * division won't overflow: need two divrems. Write the
+ * numerator and denominator as
+ *
+ * num = xB + y x : 64 bits, y : 32 bits
+ * den = uB + v u, v : 32 bits
+ */
+ uint32_t y = _cairo_uint128_to_uint32 (num);
+ uint32_t u = uint64_hi (den);
+ uint32_t v = _cairo_uint64_to_uint32 (den);
+
+ /* Compute a lower bound approximate quotient of num/den
+ * from x/(u+1). Then we have
+ *
+ * x = q(u+1) + r ; q : 32 bits, r <= u : 32 bits.
+ *
+ * xB + y = q(u+1)B + (rB+y)
+ * = q(uB + B + v - v) + (rB+y)
+ * = q(uB + v) + qB - qv + (rB+y)
+ * = q(uB + v) + q(B-v) + (rB+y)
+ *
+ * The true quotient of num/den then is q plus the
+ * contribution of q(B-v) + (rB+y). The main contribution
+ * comes from the term q(B-v), with the term (rB+y) only
+ * contributing at most one part.
+ *
+ * The term q(B-v) must fit into 64 bits, since q fits into 32
+ * bits on account of being a lower bound to the true
+ * quotient, and as B-v <= 2^32, we may safely use a single
+ * 64/64 bit division to find its contribution. */
+
+ cairo_uquorem64_t quorem;
+ cairo_uint64_t remainder; /* will contain final remainder */
+ uint32_t quotient; /* will contain final quotient. */
+ uint32_t q;
+ uint32_t r;
+
+ /* Approximate quotient by dividing the high 64 bits of num by
+ * u+1. Watch out for overflow of u+1. */
+ if (u+1) {
+ quorem = _cairo_uint64_divrem (x, _cairo_uint32_to_uint64 (u+1));
+ q = _cairo_uint64_to_uint32 (quorem.quo);
+ r = _cairo_uint64_to_uint32 (quorem.rem);
+ }
+ else {
+ q = uint64_hi (x);
+ r = _cairo_uint64_to_uint32 (x);
+ }
+ quotient = q;
+
+ /* Add the main term's contribution to quotient. Note B-v =
+ * -v as an uint32 (unless v = 0) */
+ if (v)
+ quorem = _cairo_uint64_divrem (_cairo_uint32x32_64_mul (q, -v), den);
+ else
+ quorem = _cairo_uint64_divrem (_cairo_uint32s_to_uint64 (q, 0), den);
+ quotient += _cairo_uint64_to_uint32 (quorem.quo);
+
+ /* Add the contribution of the subterm and start computing the
+ * true remainder. */
+ remainder = _cairo_uint32s_to_uint64 (r, y);
+ if (_cairo_uint64_ge (remainder, den)) {
+ remainder = _cairo_uint64_sub (remainder, den);
+ quotient++;
+ }
+
+ /* Add the contribution of the main term's remainder. The
+ * funky test here checks that remainder + main_rem >= den,
+ * taking into account overflow of the addition. */
+ remainder = _cairo_uint64_add (remainder, quorem.rem);
+ if (_cairo_uint64_ge (remainder, den) ||
+ _cairo_uint64_lt (remainder, quorem.rem))
+ {
+ remainder = _cairo_uint64_sub (remainder, den);
+ quotient++;
+ }
+
+ result.quo = _cairo_uint32_to_uint64 (quotient);
+ result.rem = remainder;
+ }
+ return result;
+}
+
+cairo_quorem64_t
+_cairo_int_96by64_32x64_divrem (cairo_int128_t num, cairo_int64_t den)
+{
+ int num_neg = _cairo_int128_negative (num);
+ int den_neg = _cairo_int64_negative (den);
+ cairo_int64_t nonneg_den = den;
+ cairo_uquorem64_t uqr;
+ cairo_quorem64_t qr;
+
+ if (num_neg)
+ num = _cairo_int128_negate (num);
+ if (den_neg)
+ nonneg_den = _cairo_int64_negate (den);
+
+ uqr = _cairo_uint_96by64_32x64_divrem (num, nonneg_den);
+ if (_cairo_uint64_eq (uqr.rem, nonneg_den)) {
+ /* bail on overflow. */
+ qr.quo = _cairo_uint32s_to_uint64 (0x7FFFFFFF, -1U);;
+ qr.rem = den;
+ return qr;
+ }
+
+ if (num_neg)
+ qr.rem = _cairo_int64_negate (uqr.rem);
+ else
+ qr.rem = uqr.rem;
+ if (num_neg != den_neg)
+ qr.quo = _cairo_int64_negate (uqr.quo);
+ else
+ qr.quo = uqr.quo;
+ return qr;
+}
diff-tree 762bd1330d5e3148ddd60949866227cb75b782d6 (from 4cd871b6f371e86c252c2fa8d8af481d822a1dec)
Author: Carl Worth <cworth at cworth.org>
Date: Fri Sep 22 17:28:00 2006 -0700
Make event_queue_insert ignore duplicate intersection events (not duplicate start/stop events)
This fixes the failures of the new tessellator with the 3 tests:
bitmap-font, rectangle-rounding-error, and close-path
The problem was that identical edges from separate polygons
were not being added to the event queue, (because of a check
that was actually only intended to prevent an intersection
event from being scheduled multiple times).
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index d300dca..384372b 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -598,9 +598,14 @@ static void
_cairo_bo_event_queue_insert (cairo_bo_event_queue_t *queue,
cairo_bo_event_t *event)
{
- /* Don't insert if there's already an equivalent event in the queue. */
- if (skip_list_find (queue, event) == NULL)
- skip_list_insert (queue, event);
+ /* Don't insert if there's already an equivalent intersection event in the queue. */
+ if (event->type == CAIRO_BO_EVENT_TYPE_INTERSECTION &&
+ skip_list_find (queue, event) != NULL)
+ {
+ return;
+ }
+
+ skip_list_insert (queue, event);
}
static void
diff-tree 4cd871b6f371e86c252c2fa8d8af481d822a1dec (from 0f7c488906128557807ca98aed5c442abf0a0b75)
Author: Carl Worth <cworth at cworth.org>
Date: Wed Sep 20 10:47:58 2006 -0700
Switch from old tessellator to new tessellator
diff --git a/src/Makefile.am b/src/Makefile.am
index 71df10e..5079ec8 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -170,6 +170,7 @@ libcairo_la_SOURCES = \
cairo-arc-private.h \
cairo-array.c \
cairo-base85-stream.c \
+ cairo-bentley-ottmann.c \
cairo-cache.c \
cairo-cache-private.h \
cairo-clip.c \
@@ -201,6 +202,8 @@ libcairo_la_SOURCES = \
cairo-region.c \
cairo-scaled-font.c \
cairo-scaled-font-test.h \
+ cairo-skiplist.c \
+ cairo-skiplist-private.h \
cairo-slope.c \
cairo-spline.c \
cairo-stroke-style.c \
diff --git a/src/cairo-path-fill.c b/src/cairo-path-fill.c
index 51e067f..7377960 100644
--- a/src/cairo-path-fill.c
+++ b/src/cairo-path-fill.c
@@ -194,9 +194,9 @@ _cairo_path_fixed_fill_to_traps (cairo_p
if (status)
goto BAIL;
- status = _cairo_traps_tessellate_polygon (filler.traps,
- &filler.polygon,
- fill_rule);
+ status = _cairo_bentley_ottmann_tessellate_polygon (filler.traps,
+ &filler.polygon,
+ fill_rule);
if (status)
goto BAIL;
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 86dd074..ced31c1 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -418,7 +418,7 @@ _cairo_stroker_add_cap (cairo_stroker_t
_cairo_polygon_line_to (&polygon, &f->ccw);
_cairo_polygon_close (&polygon);
- status = _cairo_traps_tessellate_polygon (stroker->traps, &polygon, CAIRO_FILL_RULE_WINDING);
+ status = _cairo_bentley_ottmann_tessellate_polygon (stroker->traps, &polygon, CAIRO_FILL_RULE_WINDING);
_cairo_polygon_fini (&polygon);
return status;
diff --git a/src/cairo-pen.c b/src/cairo-pen.c
index 0e24f2d..1af8c36 100644
--- a/src/cairo-pen.c
+++ b/src/cairo-pen.c
@@ -448,7 +448,7 @@ _cairo_pen_stroke_spline (cairo_pen_t *
return status;
_cairo_polygon_close (&polygon);
- _cairo_traps_tessellate_polygon (traps, &polygon, CAIRO_FILL_RULE_WINDING);
+ _cairo_bentley_ottmann_tessellate_polygon (traps, &polygon, CAIRO_FILL_RULE_WINDING);
_cairo_polygon_fini (&polygon);
return CAIRO_STATUS_SUCCESS;
diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index e29c283..9b3931f 100644
--- a/src/cairo-traps.c
+++ b/src/cairo-traps.c
@@ -46,11 +46,6 @@ static cairo_status_t
_cairo_traps_add_trap (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
cairo_line_t *left, cairo_line_t *right);
-static cairo_status_t
-_cairo_traps_add_trap_from_points (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
- cairo_point_t left_p1, cairo_point_t left_p2,
- cairo_point_t right_p1, cairo_point_t right_p2);
-
static int
_compare_point_fixed_by_y (const void *av, const void *bv);
@@ -178,7 +173,7 @@ _cairo_traps_add_trap (cairo_traps_t *tr
return traps->status;
}
-static cairo_status_t
+cairo_status_t
_cairo_traps_add_trap_from_points (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
cairo_point_t left_p1, cairo_point_t left_p2,
cairo_point_t right_p1, cairo_point_t right_p2)
diff --git a/src/cairoint.h b/src/cairoint.h
index 2ae9090..aa17467 100755
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -2236,6 +2236,16 @@ _cairo_traps_tessellate_polygon (cairo_t
cairo_polygon_t *poly,
cairo_fill_rule_t fill_rule);
+cairo_status_t
+_cairo_traps_add_trap_from_points (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
+ cairo_point_t left_p1, cairo_point_t left_p2,
+ cairo_point_t right_p1, cairo_point_t right_p2);
+
+cairo_status_t
+_cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t *traps,
+ cairo_polygon_t *polygon,
+ cairo_fill_rule_t fill_rule);
+
cairo_private int
_cairo_traps_contain (cairo_traps_t *traps, double x, double y);
diff-tree 0f7c488906128557807ca98aed5c442abf0a0b75 (from 8921f733995bc003c6977fd071f0be9e346e0f79)
Author: Carl Worth <cworth at cworth.org>
Date: Wed Sep 20 10:47:01 2006 -0700
Adapt new tessellator to match the interface provided by the old tessellator.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 4eb55e1..d300dca 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -40,10 +40,7 @@
#define CAIRO_BO_GUARD_BITS 2
-typedef struct _cairo_bo_point32 {
- int32_t x;
- int32_t y;
-} cairo_bo_point32_t;
+typedef cairo_point_t cairo_bo_point32_t;
typedef struct _cairo_bo_point128 {
cairo_int128_t x;
@@ -62,6 +59,7 @@ struct _cairo_bo_edge {
cairo_bo_point32_t top;
cairo_bo_point32_t middle;
cairo_bo_point32_t bottom;
+ cairo_bool_t reversed;
cairo_bo_edge_t *prev;
cairo_bo_edge_t *next;
sweep_line_elt_t *sweep_line_elt;
@@ -789,7 +787,7 @@ _cairo_bo_sweep_line_swap (cairo_bo_swee
static void
_cairo_bo_edge_print (cairo_bo_edge_t *edge)
{
- printf ("(%2d, %2d)-(%2d, %2d)",
+ printf ("(0x%x, 0x%x)-(0x%x, 0x%x)",
edge->top.x, edge->top.y,
edge->bottom.x, edge->bottom.y);
}
@@ -921,28 +919,66 @@ _cairo_bo_sweep_line_validate (cairo_bo_
}
static cairo_status_t
-_add_result_edge (cairo_array_t *array,
- cairo_bo_edge_t *edge)
+_active_edges_to_traps (cairo_bo_edge_t *head,
+ int32_t top,
+ int32_t bottom,
+ cairo_fill_rule_t fill_rule,
+ cairo_traps_t *traps)
{
- /* Avoid creating any horizontal edges due to bending. */
- if (edge->top.y == edge->bottom.y)
- return CAIRO_STATUS_SUCCESS;
-
- /* Fix up any edge that got bent so badly as to reverse top and bottom */
- if (edge->top.y > edge->bottom.y) {
- edge->middle = edge->bottom;
- edge->bottom = edge->top;
- edge->top = edge->middle;
- }
-
- return _cairo_array_append (array, edge);
-}
+ cairo_status_t status;
+ int in_out = 0;
+ cairo_bo_edge_t *edge;
+ cairo_bo_point32_t left_top, left_bottom, right_top, right_bottom;
-static int
-_cairo_bentley_ottmann_intersect_edges (cairo_bo_edge_t *edges,
- int num_edges,
- cairo_array_t *intersected_edges)
+ for (edge = head; edge && edge->next; edge = edge->next) {
+ if (fill_rule == CAIRO_FILL_RULE_WINDING) {
+ if (edge->reversed)
+ in_out++;
+ else
+ in_out--;
+ if (in_out == 0)
+ continue;
+ } else {
+ in_out++;
+ if ((in_out & 1) == 0)
+ continue;
+ }
+#if DEBUG_PRINT_STATE
+ printf ("Adding trap 0x%x 0x%x: ", top, bottom);
+ _cairo_bo_edge_print (edge);
+ _cairo_bo_edge_print (edge->next);
+#endif
+ left_top.x = edge->middle.x >> CAIRO_BO_GUARD_BITS;
+ left_top.y = edge->middle.y >> CAIRO_BO_GUARD_BITS;
+ left_bottom.x = edge->bottom.x >> CAIRO_BO_GUARD_BITS;
+ left_bottom.y = edge->bottom.y >> CAIRO_BO_GUARD_BITS;
+ right_top.x = edge->next->middle.x >> CAIRO_BO_GUARD_BITS;
+ right_top.y = edge->next->middle.y >> CAIRO_BO_GUARD_BITS;
+ right_bottom.x = edge->next->bottom.x >> CAIRO_BO_GUARD_BITS;
+ right_bottom.y = edge->next->bottom.y >> CAIRO_BO_GUARD_BITS;
+ status = _cairo_traps_add_trap_from_points (traps,
+ top >> CAIRO_BO_GUARD_BITS,
+ bottom >> CAIRO_BO_GUARD_BITS,
+ left_top, left_bottom,
+ right_top, right_bottom);
+ if (status)
+ return status;
+ }
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+/* Execute a single pass of the Bentley-Ottmann algorithm on edges,
+ * generating trapezoids according to the fill_rule and appending them
+ * to traps. */
+static cairo_status_t
+_cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_edge_t *edges,
+ int num_edges,
+ cairo_fill_rule_t fill_rule,
+ cairo_traps_t *traps,
+ int *num_intersections)
{
+ cairo_status_t status;
int intersection_count = 0;
cairo_bo_event_queue_t event_queue;
cairo_bo_sweep_line_t sweep_line;
@@ -958,6 +994,7 @@ _cairo_bentley_ottmann_intersect_edges (
edge = &edges[i];
edge->top.x <<= CAIRO_BO_GUARD_BITS;
edge->top.y <<= CAIRO_BO_GUARD_BITS;
+ edge->middle = edge->top;
edge->bottom.x <<= CAIRO_BO_GUARD_BITS;
edge->bottom.y <<= CAIRO_BO_GUARD_BITS;
}
@@ -976,7 +1013,15 @@ _cairo_bentley_ottmann_intersect_edges (
break;
event = SKIP_ELT_TO_EVENT (elt);
- sweep_line.current_y = event->point.y;
+ if (event->point.y != sweep_line.current_y) {
+ status = _active_edges_to_traps (sweep_line.head,
+ sweep_line.current_y, event->point.y,
+ fill_rule, traps);
+ if (status)
+ return status;
+
+ sweep_line.current_y = event->point.y;
+ }
event_saved = *event;
_cairo_bo_event_queue_delete (&event_queue, event);
@@ -1007,15 +1052,6 @@ _cairo_bentley_ottmann_intersect_edges (
case CAIRO_BO_EVENT_TYPE_STOP:
edge = event->e1;
- {
- cairo_bo_edge_t intersected;
- intersected.top.x = edge->middle.x >> CAIRO_BO_GUARD_BITS;
- intersected.top.y = edge->middle.y >> CAIRO_BO_GUARD_BITS;
- intersected.bottom.x = edge->bottom.x >> CAIRO_BO_GUARD_BITS;
- intersected.bottom.y = edge->bottom.y >> CAIRO_BO_GUARD_BITS;
- _add_result_edge (intersected_edges, &intersected);
- }
-
left = edge->prev;
right = edge->next;
@@ -1039,23 +1075,8 @@ _cairo_bentley_ottmann_intersect_edges (
intersection_count++;
- {
- cairo_bo_edge_t intersected;
- intersected.top.x = edge1->middle.x >> CAIRO_BO_GUARD_BITS;
- intersected.top.y = edge1->middle.y >> CAIRO_BO_GUARD_BITS;
- intersected.bottom.x = event->point.x >> CAIRO_BO_GUARD_BITS;
- intersected.bottom.y = event->point.y >> CAIRO_BO_GUARD_BITS;
- _add_result_edge (intersected_edges, &intersected);
-
- intersected.top.x = edge2->middle.x >> CAIRO_BO_GUARD_BITS;
- intersected.top.y = edge2->middle.y >> CAIRO_BO_GUARD_BITS;
- intersected.bottom.x = event->point.x >> CAIRO_BO_GUARD_BITS;
- intersected.bottom.y = event->point.y >> CAIRO_BO_GUARD_BITS;
- _add_result_edge (intersected_edges, &intersected);
-
- edge1->middle = event->point;
- edge2->middle = event->point;
- }
+ edge1->middle = event->point;
+ edge2->middle = event->point;
left = edge1->prev;
right = edge2->next;
@@ -1079,9 +1100,51 @@ _cairo_bentley_ottmann_intersect_edges (
}
}
- return intersection_count;
+ *num_intersections = intersection_count;
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_status_t
+_cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t *traps,
+ cairo_polygon_t *polygon,
+ cairo_fill_rule_t fill_rule)
+{
+ int intersections;
+ cairo_status_t status;
+ cairo_bo_edge_t *edges;
+ int i;
+
+ edges = malloc (polygon->num_edges * sizeof (cairo_bo_edge_t));
+ if (edges == NULL)
+ return CAIRO_STATUS_NO_MEMORY;
+
+ for (i = 0; i < polygon->num_edges; i++) {
+ edges[i].top = polygon->edges[i].edge.p1;
+ edges[i].middle = edges[i].top;
+ edges[i].bottom = polygon->edges[i].edge.p2;
+ /* XXX: The 'clockWise' name that cairo_polygon_t uses is
+ * totally bogus. It's really a (negated!) description of
+ * whether the edge is reversed. */
+ edges[i].reversed = (! polygon->edges[i].clockWise);
+ edges[i].prev = NULL;
+ edges[i].next = NULL;
+ edges[i].sweep_line_elt = NULL;
+ }
+
+ /* XXX: This would be the convenient place to throw in multiple
+ * passes of the Bentley-Ottmann algorithm. It would merely
+ * require storing the results of each pass into a temporary
+ * cairo_traps_t. */
+ status = _cairo_bentley_ottmann_tessellate_bo_edges (edges, polygon->num_edges,
+ fill_rule, traps, &intersections);
+
+ free (edges);
+
+ return status;
}
+#if 0
static cairo_bool_t
edges_have_an_intersection_quadratic (cairo_bo_edge_t *edges,
int num_edges)
@@ -1381,3 +1444,5 @@ main (void)
return 0;
}
+#endif
+
diff-tree 8921f733995bc003c6977fd071f0be9e346e0f79 (from c2509f8a721ec489e1b44fa8a68be165363787a7)
Author: Carl Worth <cworth at cworth.org>
Date: Wed Sep 20 10:41:42 2006 -0700
Add new tessellator (unused) in cairo-bentley-ottmann.c
This is the implementation as it cooked in the new-tessellator branch
available from:
git://people.freedesktop.org/~cworth/cairo
The file here comes from commit eee4faf79900be2c5fda1fddd49737681a9e37d6 in
that branch. It's sitting here not hooked up to anything in cairo yet,
and still with a main function with test cases, etc.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
new file mode 100644
index 0000000..4eb55e1
--- /dev/null
+++ b/src/cairo-bentley-ottmann.c
@@ -0,0 +1,1383 @@
+/*
+ * Copyright © 2004 Carl Worth
+ * Copyright © 2006 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Carl Worth
+ *
+ * Contributor(s):
+ * Carl D. Worth <cworth at cworth.org>
+ */
+
+/* Provide definitions for standalone compilation */
+#include "cairoint.h"
+
+#include "cairo-skiplist-private.h"
+
+#define CAIRO_BO_GUARD_BITS 2
+
+typedef struct _cairo_bo_point32 {
+ int32_t x;
+ int32_t y;
+} cairo_bo_point32_t;
+
+typedef struct _cairo_bo_point128 {
+ cairo_int128_t x;
+ cairo_int128_t y;
+} cairo_bo_point128_t;
+
+typedef struct _cairo_bo_point_quorem128 {
+ cairo_quorem128_t x;
+ cairo_quorem128_t y;
+} cairo_bo_point_quorem128_t;
+
+typedef struct _cairo_bo_edge cairo_bo_edge_t;
+typedef struct _sweep_line_elt sweep_line_elt_t;
+
+struct _cairo_bo_edge {
+ cairo_bo_point32_t top;
+ cairo_bo_point32_t middle;
+ cairo_bo_point32_t bottom;
+ cairo_bo_edge_t *prev;
+ cairo_bo_edge_t *next;
+ sweep_line_elt_t *sweep_line_elt;
+};
+
+struct _sweep_line_elt {
+ cairo_bo_edge_t *edge;
+ skip_elt_t elt;
+};
+
+#define SKIP_ELT_TO_EDGE_ELT(elt) SKIP_LIST_ELT_TO_DATA (sweep_line_elt_t, (elt))
+#define SKIP_ELT_TO_EDGE(elt) (SKIP_ELT_TO_EDGE_ELT (elt)->edge)
+
+typedef enum {
+ CAIRO_BO_STATUS_INTERSECTION,
+ CAIRO_BO_STATUS_PARALLEL,
+ CAIRO_BO_STATUS_NO_INTERSECTION
+} cairo_bo_status_t;
+
+typedef enum {
+ CAIRO_BO_EVENT_TYPE_START,
+ CAIRO_BO_EVENT_TYPE_STOP,
+ CAIRO_BO_EVENT_TYPE_INTERSECTION
+} cairo_bo_event_type_t;
+
+typedef struct _cairo_bo_event {
+ cairo_bo_event_type_t type;
+ cairo_bo_edge_t *e1;
+ cairo_bo_edge_t *e2;
+ cairo_bo_point32_t point;
+ skip_elt_t elt;
+} cairo_bo_event_t;
+
+#define SKIP_ELT_TO_EVENT(elt) SKIP_LIST_ELT_TO_DATA (cairo_bo_event_t, (elt))
+
+typedef skip_list_t cairo_bo_event_queue_t;
+
+/* This structure extends skip_list_t, which must come first. */
+typedef struct _cairo_bo_sweep_line {
+ skip_list_t active_edges;
+ cairo_bo_edge_t *head;
+ cairo_bo_edge_t *tail;
+ int32_t current_y;
+} cairo_bo_sweep_line_t;
+
+static int
+_cairo_bo_point32_compare (cairo_bo_point32_t *a,
+ cairo_bo_point32_t *b)
+{
+ if (a->y > b->y)
+ return 1;
+ else if (a->y < b->y)
+ return -1;
+
+ if (a->x > b->x)
+ return 1;
+ else if (a->x < b->x)
+ return -1;
+
+ return 0;
+}
+
+/* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
+ * slope a is respectively greater than, equal to, or less than the
+ * slope of b.
+ *
+ * For each edge, consider the direction vector formed from:
+ *
+ * top -> bottom
+ *
+ * which is:
+ *
+ * (dx, dy) = (bottom.x - top.x, bottom.y - top.y)
+ *
+ * We then define the slope of each edge as dx/dy, (which is the
+ * inverse of the slope typically used in math instruction). We never
+ * compute a slope directly as the value approaches infinity, but we
+ * can derive a slope comparison without division as follows, (where
+ * the ? represents our compare operator).
+ *
+ * 1. slope(a) ? slope(b)
+ * 2. adx/ady ? bdx/bdy
+ * 3. (adx * bdy) ? (bdx * ady)
+ *
+ * Note that from step 2 to step 3 there is no change needed in the
+ * sign of the result since both ady and bdy are guaranteed to be
+ * greater than or equal to 0.
+ *
+ * When using this slope comparison to sort edges, some care is needed
+ * when interpreting the results. Since the slope compare operates on
+ * distance vectors from top to bottom it gives a correct left to
+ * right sort for edges that have a common top point, (such as two
+ * edges with start events at the same location). On the other hand,
+ * the sense of the result will be exactly reversed for two edges that
+ * have a common stop point.
+ */
+static int
+_slope_compare (cairo_bo_edge_t *a,
+ cairo_bo_edge_t *b)
+{
+ /* XXX: We're assuming here that dx and dy will still fit in 32
+ * bits. That's not true in general as there could be overflow. We
+ * should prevent that before the tessellation algorithm
+ * begins.
+ */
+ int32_t adx = a->bottom.x - a->top.x;
+ int32_t ady = a->bottom.y - a->top.y;
+
+ int32_t bdx = b->bottom.x - b->top.x;
+ int32_t bdy = b->bottom.y - b->top.y;
+
+ int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
+ int64_t bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
+
+ /* if (adx * bdy > bdx * ady) */
+ if (_cairo_int64_gt (adx_bdy, bdx_ady))
+ return 1;
+
+ /* if (adx * bdy < bdx * ady) */
+ if (_cairo_int64_lt (adx_bdy, bdx_ady))
+ return -1;
+
+ return 0;
+}
+
+static cairo_quorem64_t
+edge_x_for_y (cairo_bo_edge_t *edge,
+ int32_t y)
+{
+ /* XXX: We're assuming here that dx and dy will still fit in 32
+ * bits. That's not true in general as there could be overflow. We
+ * should prevent that before the tessellation algorithm
+ * begins.
+ */
+ int32_t dx = edge->bottom.x - edge->top.x;
+ int32_t dy = edge->bottom.y - edge->top.y;
+ int64_t numerator;
+ cairo_quorem64_t quorem;
+
+ if (dy == 0) {
+ quorem.quo = _cairo_int32_to_int64 (edge->top.x);
+ quorem.rem = 0;
+ return quorem;
+ }
+
+ /* edge->top.x + (y - edge->top.y) * dx / dy */
+ /* Multiplication followed by division means the guard bits cancel out. */
+ numerator = _cairo_int32x32_64_mul ((y - edge->top.y), dx);
+ quorem = _cairo_int64_divrem (numerator, dy);
+ quorem.quo += edge->top.x;
+
+ return quorem;
+}
+
+static int
+_cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t *sweep_line,
+ cairo_bo_edge_t *a,
+ cairo_bo_edge_t *b)
+{
+ cairo_quorem64_t ax = edge_x_for_y (a, sweep_line->current_y);
+ cairo_quorem64_t bx = edge_x_for_y (b, sweep_line->current_y);
+ int cmp;
+
+ if (a == b)
+ return 0;
+
+ if (ax.quo > bx.quo)
+ return 1;
+ else if (ax.quo < bx.quo)
+ return -1;
+
+ /* Quotients are identical, test remainder. */
+ if (ax.rem > bx.rem)
+ return 1;
+ else if (ax.rem < bx.rem)
+ return -1;
+
+ /* The two edges intersect exactly at y, so fall back on slope
+ * comparison. We know that this compare_edges function will be
+ * called only when starting a new edge, (not when stopping an
+ * edge), so we don't have to worry about conditionally inverting
+ * the sense of _slope_compare. */
+ cmp = _slope_compare (a, b);
+ if (cmp)
+ return cmp;
+
+ /* We've got two collinear edges now. */
+
+ /* Since we're dealing with start events, prefer comparing top
+ * edges before bottom edges. */
+ cmp = _cairo_bo_point32_compare (&a->top, &b->top);
+ if (cmp)
+ return cmp;
+
+ cmp = _cairo_bo_point32_compare (&a->bottom, &b->bottom);
+ if (cmp)
+ return cmp;
+
+ /* Finally, we've got two identical edges. Let's finally
+ * discriminate by a simple pointer comparison, (which works only
+ * because we "know" the edges are all in a single array and don't
+ * move. */
+ if (a > b)
+ return 1;
+ else
+ return -1;
+}
+
+static int
+_sweep_line_elt_compare (void *list,
+ void *a,
+ void *b)
+{
+ cairo_bo_sweep_line_t *sweep_line = list;
+ sweep_line_elt_t *edge_elt_a = a;
+ sweep_line_elt_t *edge_elt_b = b;
+
+ return _cairo_bo_sweep_line_compare_edges (sweep_line,
+ edge_elt_a->edge,
+ edge_elt_b->edge);
+}
+
+static int
+cairo_bo_event_compare (cairo_bo_event_t *a,
+ cairo_bo_event_t *b)
+{
+ int cmp;
+
+ /* The major motion of the sweep line is vertical (top-to-bottom),
+ * and the minor motion is horizontal (left-to-right), dues to the
+ * infinitesimal tilt rule.
+ *
+ * Our point comparison function respects these rules.
+ */
+ cmp = _cairo_bo_point32_compare (&a->point, &b->point);
+ if (cmp)
+ return cmp;
+
+ /* The events share a common point, so further discrimination is
+ * determined by the event type. Due to the infinitesimal
+ * shortening rule, stop events come first, then intersection
+ * events, then start events.
+ */
+ if (a->type != b->type) {
+ if (a->type == CAIRO_BO_EVENT_TYPE_STOP)
+ return -1;
+ if (a->type == CAIRO_BO_EVENT_TYPE_START)
+ return 1;
+
+ if (b->type == CAIRO_BO_EVENT_TYPE_STOP)
+ return 1;
+ if (b->type == CAIRO_BO_EVENT_TYPE_START)
+ return -1;
+ }
+
+ /* At this stage we are looking at two events of the same type at
+ * the same point. The final sort key is a slope comparison. We
+ * need a different sense for start and stop events based on the
+ * shortening rule.
+ *
+ * NOTE: Fortunately, we get to ignore errors in the relative
+ * ordering of intersection events. This means we don't even have
+ * to look at e2 here, nor worry about which sense of the slope
+ * comparison test is used for intersection events.
+ */
+ cmp = _slope_compare (a->e1, b->e1);
+ if (cmp) {
+ if (a->type == CAIRO_BO_EVENT_TYPE_START)
+ return cmp;
+ else
+ return - cmp;
+ }
+
+ /* As a final discrimination, look at the opposite point. This
+ * leaves ambiguities only for identical edges.
+ */
+ if (a->type == CAIRO_BO_EVENT_TYPE_START)
+ return _cairo_bo_point32_compare (&b->e1->bottom,
+ &a->e1->bottom);
+ else if (a->type == CAIRO_BO_EVENT_TYPE_STOP)
+ return _cairo_bo_point32_compare (&a->e1->top,
+ &b->e1->top);
+ else { /* CAIRO_BO_EVENT_TYPE_INTERSECT */
+ /* For two intersection events at the identical point, we
+ * don't care what order they sort in, but we do care that we
+ * have a stable sort. In particular intersections between
+ * different pairs of edges must never return 0. */
+ cmp = _cairo_bo_point32_compare (&a->e2->top, &b->e2->top);
+ if (cmp)
+ return cmp;
+ cmp = _cairo_bo_point32_compare (&a->e2->bottom, &b->e2->bottom);
+ if (cmp)
+ return cmp;
+ cmp = _cairo_bo_point32_compare (&a->e1->top, &b->e1->top);
+ if (cmp)
+ return cmp;
+ return _cairo_bo_point32_compare (&a->e1->bottom, &b->e1->bottom);
+ }
+}
+
+static inline int
+cairo_bo_event_compare_abstract (void *list,
+ void *a,
+ void *b)
+{
+ cairo_bo_event_t *event_a = a;
+ cairo_bo_event_t *event_b = b;
+
+ return cairo_bo_event_compare (event_a, event_b);
+}
+
+static inline cairo_int64_t
+det32_64 (int32_t a,
+ int32_t b,
+ int32_t c,
+ int32_t d)
+{
+ cairo_int64_t ad;
+ cairo_int64_t bc;
+
+ /* det = a * d - b * c */
+ ad = _cairo_int64_rsa (_cairo_int32x32_64_mul (a, d), CAIRO_BO_GUARD_BITS);
+ bc = _cairo_int64_rsa (_cairo_int32x32_64_mul (b, c), CAIRO_BO_GUARD_BITS);
+
+ return _cairo_int64_sub (ad, bc);
+}
+
+/* We don't shift right by CAIRO_BO_GUARD_BITS here, anticipating a
+ * subsequent division. */
+static inline cairo_int128_t
+det64_128 (cairo_int64_t a,
+ cairo_int64_t b,
+ cairo_int64_t c,
+ cairo_int64_t d)
+{
+ cairo_int128_t ad;
+ cairo_int128_t bc;
+
+ /* det = a * d - b * c */
+ ad = _cairo_int64x64_128_mul (a, d);
+ bc = _cairo_int64x64_128_mul (b, c);
+
+ return _cairo_int128_sub (ad, bc);
+}
+
+/* Compute the intersection of two lines as defined by two edges. The
+ * result is provided as a coordinate pair of 128-bit integers.
+ *
+ * Returns CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
+ * CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
+ */
+static cairo_bo_status_t
+intersect_lines (cairo_bo_edge_t *a,
+ cairo_bo_edge_t *b,
+ cairo_bo_point_quorem128_t *intersection)
+{
+ cairo_int64_t a_det, b_det;
+
+ /* XXX: We're assuming here that dx and dy will still fit in 32
+ * bits. That's not true in general as there could be overflow. We
+ * should prevent that before the tessellation algorithm
+ * begins.
+ */
+ int32_t dx1 = a->top.x - a->bottom.x;
+ int32_t dy1 = a->top.y - a->bottom.y;
+
+ int32_t dx2 = b->top.x - b->bottom.x;
+ int32_t dy2 = b->top.y - b->bottom.y;
+
+ cairo_int64_t den_det = det32_64 (dx1, dy1, dx2, dy2);
+
+ if (_cairo_int64_eq (den_det, 0))
+ return CAIRO_BO_STATUS_PARALLEL;
+
+ /* The expansion of guard bits in this multiplication is left to
+ * be reduced again by the subsequent division. */
+ a_det = det32_64 (a->top.x, a->top.y,
+ a->bottom.x, a->bottom.y);
+ b_det = det32_64 (b->top.x, b->top.y,
+ b->bottom.x, b->bottom.y);
+
+ /* x = det (a_det, dx1, b_det, dx2) / den_det */
+ intersection->x = _cairo_int128_divrem (det64_128 (a_det, dx1,
+ b_det, dx2),
+ _cairo_int64_to_int128 (den_det));
+
+ /* y = det (a_det, dy1, b_det, dy2) / den_det */
+ intersection->y = _cairo_int128_divrem (det64_128 (a_det, dy1,
+ b_det, dy2),
+ _cairo_int64_to_int128 (den_det));
+
+ return CAIRO_BO_STATUS_INTERSECTION;
+}
+
+static int
+_cairo_quorem128_32_compare (cairo_quorem128_t a,
+ int32_t b)
+{
+ /* XXX: Converting up to a int128_t here is silly, but I'm lazy. */
+ cairo_int128_t b_128 = _cairo_int32_to_int128 (b);
+ cairo_int128_t zero = _cairo_int32_to_int128 (0);
+
+ /* First compare the quotient */
+ if (_cairo_int128_gt (a.quo, b_128))
+ return 1;
+ if (_cairo_int128_lt (a.quo, b_128))
+ return -1;
+
+ /* With quotient identical, if remainder is 0 then compare equal */
+ if (_cairo_int128_eq (a.rem, zero))
+ return 0;
+
+ /* Otherwise, the non-zero remainder makes a > b */
+ return 1;
+}
+
+/* Does the given edge contain the given point. The point must already
+ * be known to be contained within the line determined by the edge,
+ * (most likely the point results from an intersection of this edge
+ * with another).
+ *
+ * If we had exact arithmetic, then this function would simply be a
+ * matter of examining whether the y value of the point lies within
+ * the range of y values of the edge. But since intersection points
+ * are not exact due to being rounded to the nearest integer within
+ * the available precision, we must also examine the x value of the
+ * point.
+ *
+ * The definition of "contains" here is that the given intersection
+ * point will be seen by the sweep line after the start event for the
+ * given edge and before the stop event for the edge. See the comments
+ * in the implementation for more details.
+ */
+static cairo_bool_t
+_cairo_bo_edge_contains_point_quorem128 (cairo_bo_edge_t *edge,
+ cairo_bo_point_quorem128_t *point)
+{
+ int cmp_top, cmp_bottom;
+
+ /* XXX: When running the actual algorithm, we don't actually need to
+ * compare against edge->top at all here, since any intersection above
+ * top is eliminated early via a slope comparison. We're leaving these
+ * here for now only for the sake of the quadratic-time intersection
+ * finder which needs them.
+ */
+
+ cmp_top = _cairo_quorem128_32_compare (point->y, edge->top.y);
+ cmp_bottom = _cairo_quorem128_32_compare (point->y, edge->bottom.y);
+
+ if (cmp_top < 0 || cmp_bottom > 0)
+ {
+ return FALSE;
+ }
+
+ if (cmp_top > 0 && cmp_bottom < 0)
+ {
+ return TRUE;
+ }
+
+ /* At this stage, the point lies on the same y value as either
+ * edge->top or edge->bottom, so we have to examine the x value in
+ * order to properly determine containment. */
+
+ /* If the y value of the point is the same as the y value of the
+ * top of the edge, then the x value of the point must be greater
+ * to be considered as inside the edge. Similarly, if the y value
+ * of the point is the same as the y value of the bottom of the
+ * edge, then the x value of the point must be less to be
+ * considered as inside. */
+
+ if (cmp_top == 0)
+ return (_cairo_quorem128_32_compare (point->x, edge->top.x) > 0);
+ else /* cmp_bottom == 0 */
+ return (_cairo_quorem128_32_compare (point->x, edge->bottom.x) < 0);
+}
+
+/* Compute the intersection of two edges. The result is provided as a
+ * coordinate pair of 128-bit integers.
+ *
+ * Returns CAIRO_BO_STATUS_INTERSECTION if there is an intersection
+ * that is within both edges, CAIRO_BO_STATUS_NO_INTERSECTION if the
+ * intersection of the lines defined by the edges occurs outside of
+ * one or both edges, and CAIRO_BO_STATUS_PARALLEL if the two edges
+ * are exactly parallel.
+ *
+ * Note that when determining if a candidate intersection is "inside"
+ * an edge, we consider both the infinitesimal shortening and the
+ * infinitesimal tilt rules described by John Hobby. Specifically, if
+ * the intersection is exactly the same as an edge point, it is
+ * effectively outside (no intersection is returned). Also, if the
+ * intersection point has the same
+ */
+static cairo_bo_status_t
+_cairo_bo_edge_intersect (cairo_bo_edge_t *a,
+ cairo_bo_edge_t *b,
+ cairo_bo_point32_t *intersection)
+{
+ cairo_bo_status_t status;
+ cairo_bo_point_quorem128_t quorem;
+
+ status = intersect_lines (a, b, &quorem);
+ if (status)
+ return status;
+
+ if (! _cairo_bo_edge_contains_point_quorem128 (a, &quorem))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+
+ if (! _cairo_bo_edge_contains_point_quorem128 (b, &quorem))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+
+ /* Now that we've correctly compared the intersection point and
+ * determined that it lies within the edge, then we know that we
+ * no longer need any more bits of storage for the intersection
+ * than we do for our edge coordinates. We also no longer need the
+ * remainder from the division. */
+ intersection->x = _cairo_int128_to_int32 (quorem.x.quo);
+ intersection->y = _cairo_int128_to_int32 (quorem.y.quo);
+
+ return CAIRO_BO_STATUS_INTERSECTION;
+}
+
+static void
+_cairo_bo_event_init (cairo_bo_event_t *event,
+ cairo_bo_event_type_t type,
+ cairo_bo_edge_t *e1,
+ cairo_bo_edge_t *e2,
+ cairo_bo_point32_t point)
+{
+ event->type = type;
+ event->e1 = e1;
+ event->e2 = e2;
+ event->point = point;
+}
+
+static void
+_cairo_bo_event_queue_insert (cairo_bo_event_queue_t *queue,
+ cairo_bo_event_t *event)
+{
+ /* Don't insert if there's already an equivalent event in the queue. */
+ if (skip_list_find (queue, event) == NULL)
+ skip_list_insert (queue, event);
+}
+
+static void
+_cairo_bo_event_queue_delete (cairo_bo_event_queue_t *queue,
+ cairo_bo_event_t *event)
+{
+ skip_list_delete (queue, event);
+}
+
+static void
+_cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue,
+ cairo_bo_edge_t *edges,
+ int num_edges)
+{
+ int i;
+ cairo_bo_event_t event;
+
+ skip_list_init (event_queue,
+ cairo_bo_event_compare_abstract,
+ sizeof (cairo_bo_event_t));
+
+ for (i = 0; i < num_edges; i++) {
+ /* We must not be given horizontal edges. */
+ assert (edges[i].top.y != edges[i].bottom.y);
+
+ /* We also must not be given any upside-down edges. */
+ assert (_cairo_bo_point32_compare (&edges[i].top, &edges[i].bottom) < 0);
+
+ /* Initialize "middle" to top */
+ edges[i].middle = edges[i].top;
+
+ _cairo_bo_event_init (&event,
+ CAIRO_BO_EVENT_TYPE_START,
+ &edges[i], NULL,
+ edges[i].top);
+
+ _cairo_bo_event_queue_insert (event_queue, &event);
+
+ _cairo_bo_event_init (&event,
+ CAIRO_BO_EVENT_TYPE_STOP,
+ &edges[i], NULL,
+ edges[i].bottom);
+
+ _cairo_bo_event_queue_insert (event_queue, &event);
+ }
+}
+
+static void
+_cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_t *event_queue,
+ cairo_bo_edge_t *left,
+ cairo_bo_edge_t *right)
+{
+ cairo_bo_status_t status;
+ cairo_bo_point32_t intersection;
+ cairo_bo_event_t event;
+
+ if (left == NULL || right == NULL)
+ return;
+
+ /* The names "left" and "right" here are correct descriptions of
+ * the order of the two edges within the active edge list. So if a
+ * slope comparison also puts left less than right, then we know
+ * that the intersection of these two segments has oalready
+ * occurred before the current sweep line position. */
+ if (_slope_compare (left, right) < 0)
+ return;
+
+ status = _cairo_bo_edge_intersect (left, right, &intersection);
+ if (status == CAIRO_BO_STATUS_PARALLEL ||
+ status == CAIRO_BO_STATUS_NO_INTERSECTION)
+ {
+ return;
+ }
+
+ _cairo_bo_event_init (&event,
+ CAIRO_BO_EVENT_TYPE_INTERSECTION,
+ left, right,
+ intersection);
+
+ _cairo_bo_event_queue_insert (event_queue, &event);
+}
+
+static void
+_cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line)
+{
+ skip_list_init (&sweep_line->active_edges,
+ _sweep_line_elt_compare,
+ sizeof (sweep_line_elt_t));
+ sweep_line->head = NULL;
+ sweep_line->tail = NULL;
+ sweep_line->current_y = 0;
+}
+
+static void
+_cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t *sweep_line,
+ cairo_bo_edge_t *edge)
+{
+ skip_elt_t *next_elt;
+ sweep_line_elt_t *sweep_line_elt;
+ cairo_bo_edge_t **prev_of_next, **next_of_prev;
+
+ sweep_line_elt = skip_list_insert (&sweep_line->active_edges, &edge);
+
+ next_elt = sweep_line_elt->elt.next[0];
+ if (next_elt)
+ prev_of_next = & (SKIP_ELT_TO_EDGE (next_elt)->prev);
+ else
+ prev_of_next = &sweep_line->tail;
+
+ if (*prev_of_next)
+ next_of_prev = &(*prev_of_next)->next;
+ else
+ next_of_prev = &sweep_line->head;
+
+ edge->prev = *prev_of_next;
+ edge->next = *next_of_prev;
+ *prev_of_next = edge;
+ *next_of_prev = edge;
+
+ edge->sweep_line_elt = sweep_line_elt;
+}
+
+static void
+_cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t *sweep_line,
+ cairo_bo_edge_t *edge)
+{
+ cairo_bo_edge_t **left_next, **right_prev;
+
+ skip_list_delete_given (&sweep_line->active_edges, &edge->sweep_line_elt->elt);
+
+ left_next = &sweep_line->head;
+ if (edge->prev)
+ left_next = &edge->prev->next;
+
+ right_prev = &sweep_line->tail;
+ if (edge->next)
+ right_prev = &edge->next->prev;
+
+ *left_next = edge->next;
+ *right_prev = edge->prev;
+}
+
+static void
+_cairo_bo_sweep_line_swap (cairo_bo_sweep_line_t *sweep_line,
+ cairo_bo_edge_t *left,
+ cairo_bo_edge_t *right)
+{
+ sweep_line_elt_t *left_elt, *right_elt;
+ cairo_bo_edge_t **before_left, **after_right;
+
+ /* Within the skip list we can do the swap simply by swapping the
+ * pointers to the edge elements and leaving all of the skip list
+ * elements and pointers unchanged. */
+ left_elt = left->sweep_line_elt;
+ right_elt = SKIP_ELT_TO_EDGE_ELT (left_elt->elt.next[0]);
+
+ left_elt->edge = right;
+ right->sweep_line_elt = left_elt;
+
+ right_elt->edge = left;
+ left->sweep_line_elt = right_elt;
+
+ /* Within the doubly-linked list of edges, there's a bit more
+ * bookkeeping involved with the swap. */
+ before_left = &sweep_line->head;
+ if (left->prev)
+ before_left = &left->prev->next;
+ *before_left = right;
+
+ after_right = &sweep_line->tail;
+ if (right->next)
+ after_right = &right->next->prev;
+ *after_right = left;
+
+ left->next = right->next;
+ right->next = left;
+
+ right->prev = left->prev;
+ left->prev = right;
+}
+
+#define DEBUG_PRINT_STATE 0
+#if DEBUG_PRINT_STATE
+static void
+_cairo_bo_edge_print (cairo_bo_edge_t *edge)
+{
+ printf ("(%2d, %2d)-(%2d, %2d)",
+ edge->top.x, edge->top.y,
+ edge->bottom.x, edge->bottom.y);
+}
+
+static void
+_cairo_bo_event_print (cairo_bo_event_t *event)
+{
+ switch (event->type) {
+ case CAIRO_BO_EVENT_TYPE_START:
+ printf ("Start: ");
+ break;
+ case CAIRO_BO_EVENT_TYPE_STOP:
+ printf ("Stop: ");
+ break;
+ case CAIRO_BO_EVENT_TYPE_INTERSECTION:
+ printf ("Intersection: ");
+ break;
+ }
+ printf ("(%d, %d)\t", event->point.x, event->point.y);
+ _cairo_bo_edge_print (event->e1);
+ if (event->type == CAIRO_BO_EVENT_TYPE_INTERSECTION) {
+ printf (" X ");
+ _cairo_bo_edge_print (event->e2);
+ }
+ printf ("\n");
+}
+
+static void
+_cairo_bo_event_queue_print (cairo_bo_event_queue_t *queue)
+{
+ skip_elt_t *elt;
+ cairo_bo_event_t *event;
+
+ printf ("Event queue:\n");
+
+ for (elt = queue->chains[0];
+ elt;
+ elt = elt->next[0])
+ {
+ event = SKIP_ELT_TO_EVENT (elt);
+ _cairo_bo_event_print (event);
+ }
+}
+
+static void
+_cairo_bo_sweep_line_print (cairo_bo_sweep_line_t *sweep_line)
+{
+ cairo_bool_t first = TRUE;
+ skip_elt_t *elt;
+ cairo_bo_edge_t *edge;
+
+ printf ("Sweep line (reversed): ");
+
+ for (edge = sweep_line->tail;
+ edge;
+ edge = edge->prev)
+ {
+ if (!first)
+ printf (", ");
+ _cairo_bo_edge_print (edge);
+ first = FALSE;
+ }
+ printf ("\n");
+
+
+ printf ("Sweep line from edge list: ");
+ first = TRUE;
+ for (edge = sweep_line->head;
+ edge;
+ edge = edge->next)
+ {
+ if (!first)
+ printf (", ");
+ _cairo_bo_edge_print (edge);
+ first = FALSE;
+ }
+ printf ("\n");
+
+ printf ("Sweep line from skip list: ");
+ first = TRUE;
+ for (elt = sweep_line->active_edges.chains[0];
+ elt;
+ elt = elt->next[0])
+ {
+ if (!first)
+ printf (", ");
+ _cairo_bo_edge_print (SKIP_ELT_TO_EDGE (elt));
+ first = FALSE;
+ }
+ printf ("\n");
+}
+
+static void
+print_state (const char *msg,
+ cairo_bo_event_queue_t *event_queue,
+ cairo_bo_sweep_line_t *sweep_line)
+{
+ printf ("%s\n", msg);
+ _cairo_bo_event_queue_print (event_queue);
+ _cairo_bo_sweep_line_print (sweep_line);
+ printf ("\n");
+}
+#endif
+
+static void
+_cairo_bo_sweep_line_validate (cairo_bo_sweep_line_t *sweep_line)
+{
+ cairo_bo_edge_t *edge;
+ skip_elt_t *elt;
+
+ /* March through both the skip list's singly-linked list and the
+ * sweep line's own list through pointers in the edges themselves
+ * and make sure they agree at every point. */
+
+ for (edge = sweep_line->head, elt = sweep_line->active_edges.chains[0];
+ edge && elt;
+ edge = edge->next, elt = elt->next[0])
+ {
+ if (SKIP_ELT_TO_EDGE (elt) != edge) {
+ fprintf (stderr, "*** Error: Sweep line fails to validate: Inconsistent data in the two lists.\n");
+ exit (1);
+ }
+ }
+
+ if (edge || elt) {
+ fprintf (stderr, "*** Error: Sweep line fails to validate: One list ran out before the other.\n");
+ exit (1);
+ }
+}
+
+static cairo_status_t
+_add_result_edge (cairo_array_t *array,
+ cairo_bo_edge_t *edge)
+{
+ /* Avoid creating any horizontal edges due to bending. */
+ if (edge->top.y == edge->bottom.y)
+ return CAIRO_STATUS_SUCCESS;
+
+ /* Fix up any edge that got bent so badly as to reverse top and bottom */
+ if (edge->top.y > edge->bottom.y) {
+ edge->middle = edge->bottom;
+ edge->bottom = edge->top;
+ edge->top = edge->middle;
+ }
+
+ return _cairo_array_append (array, edge);
+}
+
+static int
+_cairo_bentley_ottmann_intersect_edges (cairo_bo_edge_t *edges,
+ int num_edges,
+ cairo_array_t *intersected_edges)
+{
+ int intersection_count = 0;
+ cairo_bo_event_queue_t event_queue;
+ cairo_bo_sweep_line_t sweep_line;
+ skip_elt_t *elt;
+ cairo_bo_event_t *event, event_saved;
+ cairo_bo_edge_t *edge;
+ cairo_bo_edge_t *left, *right;
+ cairo_bo_edge_t *edge1, *edge2;
+
+ int i;
+
+ for (i = 0; i < num_edges; i++) {
+ edge = &edges[i];
+ edge->top.x <<= CAIRO_BO_GUARD_BITS;
+ edge->top.y <<= CAIRO_BO_GUARD_BITS;
+ edge->bottom.x <<= CAIRO_BO_GUARD_BITS;
+ edge->bottom.y <<= CAIRO_BO_GUARD_BITS;
+ }
+
+ _cairo_bo_event_queue_init (&event_queue, edges, num_edges);
+ _cairo_bo_sweep_line_init (&sweep_line);
+
+#if DEBUG_PRINT_STATE
+ print_state ("After initializing", &event_queue, &sweep_line);
+#endif
+
+ while (1)
+ {
+ elt = event_queue.chains[0];
+ if (elt == NULL)
+ break;
+ event = SKIP_ELT_TO_EVENT (elt);
+
+ sweep_line.current_y = event->point.y;
+
+ event_saved = *event;
+ _cairo_bo_event_queue_delete (&event_queue, event);
+ event = &event_saved;
+
+ switch (event->type) {
+ case CAIRO_BO_EVENT_TYPE_START:
+ edge = event->e1;
+
+ _cairo_bo_sweep_line_insert (&sweep_line, edge);
+ /* Cache the insert position for use in pass 2.
+ event->e2 = Sortlist::prev (sweep_line, edge);
+ */
+
+ left = edge->prev;
+ right = edge->next;
+
+ _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, edge);
+
+ _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, edge, right);
+
+#if DEBUG_PRINT_STATE
+ print_state ("After processing start", &event_queue, &sweep_line);
+#endif
+ _cairo_bo_sweep_line_validate (&sweep_line);
+
+ break;
+ case CAIRO_BO_EVENT_TYPE_STOP:
+ edge = event->e1;
+
+ {
+ cairo_bo_edge_t intersected;
+ intersected.top.x = edge->middle.x >> CAIRO_BO_GUARD_BITS;
+ intersected.top.y = edge->middle.y >> CAIRO_BO_GUARD_BITS;
+ intersected.bottom.x = edge->bottom.x >> CAIRO_BO_GUARD_BITS;
+ intersected.bottom.y = edge->bottom.y >> CAIRO_BO_GUARD_BITS;
+ _add_result_edge (intersected_edges, &intersected);
+ }
+
+ left = edge->prev;
+ right = edge->next;
+
+ _cairo_bo_sweep_line_delete (&sweep_line, edge);
+
+ _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right);
+
+#if DEBUG_PRINT_STATE
+ print_state ("After processing stop", &event_queue, &sweep_line);
+#endif
+ _cairo_bo_sweep_line_validate (&sweep_line);
+
+ break;
+ case CAIRO_BO_EVENT_TYPE_INTERSECTION:
+ edge1 = event->e1;
+ edge2 = event->e2;
+
+ /* skip this intersection if its edges are not adjacent */
+ if (edge2 != edge1->next)
+ break;
+
+ intersection_count++;
+
+ {
+ cairo_bo_edge_t intersected;
+ intersected.top.x = edge1->middle.x >> CAIRO_BO_GUARD_BITS;
+ intersected.top.y = edge1->middle.y >> CAIRO_BO_GUARD_BITS;
+ intersected.bottom.x = event->point.x >> CAIRO_BO_GUARD_BITS;
+ intersected.bottom.y = event->point.y >> CAIRO_BO_GUARD_BITS;
+ _add_result_edge (intersected_edges, &intersected);
+
+ intersected.top.x = edge2->middle.x >> CAIRO_BO_GUARD_BITS;
+ intersected.top.y = edge2->middle.y >> CAIRO_BO_GUARD_BITS;
+ intersected.bottom.x = event->point.x >> CAIRO_BO_GUARD_BITS;
+ intersected.bottom.y = event->point.y >> CAIRO_BO_GUARD_BITS;
+ _add_result_edge (intersected_edges, &intersected);
+
+ edge1->middle = event->point;
+ edge2->middle = event->point;
+ }
+
+ left = edge1->prev;
+ right = edge2->next;
+
+ _cairo_bo_sweep_line_swap (&sweep_line, edge1, edge2);
+
+ /* after the swap e2 is left of e1 */
+
+ _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue,
+ left, edge2);
+
+ _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue,
+ edge1, right);
+
+#if DEBUG_PRINT_STATE
+ print_state ("After processing intersection", &event_queue, &sweep_line);
+#endif
+ _cairo_bo_sweep_line_validate (&sweep_line);
+
+ break;
+ }
+ }
+
+ return intersection_count;
+}
+
+static cairo_bool_t
+edges_have_an_intersection_quadratic (cairo_bo_edge_t *edges,
+ int num_edges)
+
+{
+ int i, j;
+ cairo_bo_edge_t *a, *b;
+ cairo_bo_point32_t intersection;
+ cairo_bo_status_t status;
+
+ /* We must not be given any upside-down edges. */
+ for (i = 0; i < num_edges; i++) {
+ assert (_cairo_bo_point32_compare (&edges[i].top, &edges[i].bottom) < 0);
+ edges[i].top.x <<= CAIRO_BO_GUARD_BITS;
+ edges[i].top.y <<= CAIRO_BO_GUARD_BITS;
+ edges[i].bottom.x <<= CAIRO_BO_GUARD_BITS;
+ edges[i].bottom.y <<= CAIRO_BO_GUARD_BITS;
+ }
+
+ for (i = 0; i < num_edges; i++) {
+ for (j = 0; j < num_edges; j++) {
+ if (i == j)
+ continue;
+
+ a = &edges[i];
+ b = &edges[j];
+
+ status = _cairo_bo_edge_intersect (a, b, &intersection);
+ if (status == CAIRO_BO_STATUS_PARALLEL ||
+ status == CAIRO_BO_STATUS_NO_INTERSECTION)
+ {
+ continue;
+ }
+
+ printf ("Found intersection (%d,%d) between (%d,%d)-(%d,%d) and (%d,%d)-(%d,%d)\n",
+ intersection.x,
+ intersection.y,
+ a->top.x, a->top.y,
+ a->bottom.x, a->bottom.y,
+ b->top.x, b->top.y,
+ b->bottom.x, b->bottom.y);
+
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
+
+#define TEST_MAX_EDGES 10
+
+typedef struct test {
+ const char *name;
+ const char *description;
+ int num_edges;
+ cairo_bo_edge_t edges[TEST_MAX_EDGES];
+} test_t;
+
+static test_t
+tests[] = {
+ {
+ "3 near misses",
+ "3 edges all intersecting very close to each other",
+ 3,
+ {
+ { { 4, 2}, {0, 0}, { 9, 9}, NULL, NULL },
+ { { 7, 2}, {0, 0}, { 2, 3}, NULL, NULL },
+ { { 5, 2}, {0, 0}, { 1, 7}, NULL, NULL }
+ }
+ },
+ {
+ "inconsistent data",
+ "Derived from random testing---was leading to skip list and edge list disagreeing.",
+ 2,
+ {
+ { { 2, 3}, {0, 0}, { 8, 9}, NULL, NULL },
+ { { 2, 3}, {0, 0}, { 6, 7}, NULL, NULL }
+ }
+ },
+ {
+ "failed sort",
+ "A test derived from random testing that leads to an inconsistent sort --- looks like we just can't attempt to validate the sweep line with edge_compare?",
+ 3,
+ {
+ { { 6, 2}, {0, 0}, { 6, 5}, NULL, NULL },
+ { { 3, 5}, {0, 0}, { 5, 6}, NULL, NULL },
+ { { 9, 2}, {0, 0}, { 5, 6}, NULL, NULL },
+ }
+ },
+ {
+ "minimal-intersection",
+ "Intersection of a two from among the smallest possible edges.",
+ 2,
+ {
+ { { 0, 0}, {0, 0}, { 1, 1}, NULL, NULL },
+ { { 1, 0}, {0, 0}, { 0, 1}, NULL, NULL }
+ }
+ },
+ {
+ "simple",
+ "A simple intersection of two edges at an integer (2,2).",
+ 2,
+ {
+ { { 1, 1}, {0, 0}, { 3, 3}, NULL, NULL },
+ { { 2, 1}, {0, 0}, { 2, 3}, NULL, NULL }
+ }
+ },
+ {
+ "bend-to-horizontal",
+ "With intersection truncation one edge bends to horizontal",
+ 2,
+ {
+ { { 9, 1}, {0, 0}, {3, 7}, NULL, NULL },
+ { { 3, 5}, {0, 0}, {9, 9}, NULL, NULL }
+ }
+ }
+};
+
+/*
+ {
+ "endpoint",
+ "An intersection that occurs at the endpoint of a segment.",
+ {
+ { { 4, 6}, { 5, 6}, NULL, { { NULL }} },
+ { { 4, 5}, { 5, 7}, NULL, { { NULL }} },
+ { { 0, 0}, { 0, 0}, NULL, { { NULL }} },
+ }
+ }
+ {
+ name = "overlapping",
+ desc = "Parallel segments that share an endpoint, with different slopes.",
+ edges = {
+ { top = { x = 2, y = 0}, bottom = { x = 1, y = 1}},
+ { top = { x = 2, y = 0}, bottom = { x = 0, y = 2}},
+ { top = { x = 0, y = 3}, bottom = { x = 1, y = 3}},
+ { top = { x = 0, y = 3}, bottom = { x = 2, y = 3}},
+ { top = { x = 0, y = 4}, bottom = { x = 0, y = 6}},
+ { top = { x = 0, y = 5}, bottom = { x = 0, y = 6}}
+ }
+ },
+ {
+ name = "hobby_stage_3",
+ desc = "A particularly tricky part of the 3rd stage of the 'hobby' test below.",
+ edges = {
+ { top = { x = -1, y = -2}, bottom = { x = 4, y = 2}},
+ { top = { x = 5, y = 3}, bottom = { x = 9, y = 5}},
+ { top = { x = 5, y = 3}, bottom = { x = 6, y = 3}},
+ }
+ },
+ {
+ name = "hobby",
+ desc = "Example from John Hobby's paper. Requires 3 passes of the iterative algorithm.",
+ edges = {
+ { top = { x = 0, y = 0}, bottom = { x = 9, y = 5}},
+ { top = { x = 0, y = 0}, bottom = { x = 13, y = 6}},
+ { top = { x = -1, y = -2}, bottom = { x = 9, y = 5}}
+ }
+ },
+ {
+ name = "slope",
+ desc = "Edges with same start/stop points but different slopes",
+ edges = {
+ { top = { x = 4, y = 1}, bottom = { x = 6, y = 3}},
+ { top = { x = 4, y = 1}, bottom = { x = 2, y = 3}},
+ { top = { x = 2, y = 4}, bottom = { x = 4, y = 6}},
+ { top = { x = 6, y = 4}, bottom = { x = 4, y = 6}}
+ }
+ },
+ {
+ name = "horizontal",
+ desc = "Test of a horizontal edge",
+ edges = {
+ { top = { x = 1, y = 1}, bottom = { x = 6, y = 6}},
+ { top = { x = 2, y = 3}, bottom = { x = 5, y = 3}}
+ }
+ },
+ {
+ name = "vertical",
+ desc = "Test of a vertical edge",
+ edges = {
+ { top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
+ { top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
+ }
+ },
+ {
+ name = "congruent",
+ desc = "Two overlapping edges with the same slope",
+ edges = {
+ { top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
+ { top = { x = 5, y = 2}, bottom = { x = 5, y = 6}},
+ { top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
+ }
+ },
+ {
+ name = "multi",
+ desc = "Several segments with a common intersection point",
+ edges = {
+ { top = { x = 1, y = 2}, bottom = { x = 5, y = 4} },
+ { top = { x = 1, y = 1}, bottom = { x = 5, y = 5} },
+ { top = { x = 2, y = 1}, bottom = { x = 4, y = 5} },
+ { top = { x = 4, y = 1}, bottom = { x = 2, y = 5} },
+ { top = { x = 5, y = 1}, bottom = { x = 1, y = 5} },
+ { top = { x = 5, y = 2}, bottom = { x = 1, y = 4} }
+ }
+ }
+};
+*/
+
+static int
+run_test (const char *test_name,
+ cairo_bo_edge_t *test_edges,
+ int num_edges)
+{
+ int i, intersections, passes;
+ cairo_bo_edge_t *edges;
+ cairo_array_t intersected_edges;
+
+ printf ("Testing: %s\n", test_name);
+
+ _cairo_array_init (&intersected_edges, sizeof (cairo_bo_edge_t));
+
+ intersections = _cairo_bentley_ottmann_intersect_edges (test_edges, num_edges, &intersected_edges);
+ if (intersections)
+ printf ("Pass 1 found %d intersections:\n", intersections);
+
+
+ /* XXX: Multi-pass Bentley-Ottmmann. Preferable would be to add a
+ * pass of Hobby's tolerance-square algorithm instead. */
+ passes = 1;
+ while (intersections) {
+ int num_edges = _cairo_array_num_elements (&intersected_edges);
+ passes++;
+ edges = malloc (num_edges * sizeof (cairo_bo_edge_t));
+ assert (edges != NULL);
+ memcpy (edges, _cairo_array_index (&intersected_edges, 0), num_edges * sizeof (cairo_bo_edge_t));
+ _cairo_array_fini (&intersected_edges);
+ _cairo_array_init (&intersected_edges, sizeof (cairo_bo_edge_t));
+ intersections = _cairo_bentley_ottmann_intersect_edges (edges, num_edges, &intersected_edges);
+ free (edges);
+
+ if (intersections){
+ printf ("Pass %d found %d remaining intersections:\n", passes, intersections);
+ } else {
+ if (passes > 3)
+ for (i = 0; i < passes; i++)
+ printf ("*");
+ printf ("No remainining intersections found after pass %d\n", passes);
+ }
+ }
+
+ if (edges_have_an_intersection_quadratic (_cairo_array_index (&intersected_edges, 0),
+ _cairo_array_num_elements (&intersected_edges)))
+ printf ("*** FAIL ***\n");
+ else
+ printf ("PASS\n");
+
+ _cairo_array_fini (&intersected_edges);
+
+ return 0;
+}
+
+#define MAX_RANDOM 300
+
+int
+main (void)
+{
+ char random_name[] = "random-XX";
+ static cairo_bo_edge_t random_edges[MAX_RANDOM], *edge;
+ unsigned int i, num_random;
+ test_t *test;
+
+ for (i = 0; i < sizeof (tests) / sizeof (tests[0]); i++) {
+ test = &tests[i];
+ run_test (test->name, test->edges, test->num_edges);
+ }
+
+ for (num_random = 0; num_random < MAX_RANDOM; num_random++) {
+ srand (0);
+ for (i = 0; i < num_random; i++) {
+ do {
+ edge = &random_edges[i];
+ edge->top.x = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
+ edge->top.y = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
+ edge->bottom.x = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
+ edge->bottom.y = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
+ if (edge->top.y > edge->bottom.y) {
+ int32_t tmp = edge->top.y;
+ edge->top.y = edge->bottom.y;
+ edge->bottom.y = tmp;
+ }
+ } while (edge->top.y == edge->bottom.y);
+ }
+
+ sprintf (random_name, "random-%02d", num_random);
+
+ run_test (random_name, random_edges, num_random);
+ }
+
+ return 0;
+}
diff-tree c2509f8a721ec489e1b44fa8a68be165363787a7 (from 02804773e7ef521adfbd26f90f303879198acde5)
Author: Carl Worth <cworth at cworth.org>
Date: Wed Sep 20 10:27:35 2006 -0700
Add skip list implementation (many thanks to Keith Packard)
The files here are copied directly from the standalone skiplist module
available from:
git clone git://cworth.org/~cworth/skiplist
In particular the files come from the double branch and the following
commit on that branch:
8b5a439c68e220cf1514d9b3141a1dbdce8af585
Also of interest is the original skiplist module hosted by Keith Packard
that is the original implementation on which these files were based.
Since the cworth/skiplist branched off of keithp's, Keith has also
now implemented a doubly-linked variant which might be interesting for
further simplification of the code. See:
git clone git://keithp.com/git/skiplist
and the double-link branch there.
diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h
new file mode 100644
index 0000000..616609e
--- /dev/null
+++ b/src/cairo-skiplist-private.h
@@ -0,0 +1,87 @@
+/*
+ * Copyright © 2006 Keith Packard
+ * Copyright © 2006 Carl Worth
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that copyright
+ * notice and this permission notice appear in supporting documentation, and
+ * that the name of the copyright holders not be used in advertising or
+ * publicity pertaining to distribution of the software without specific,
+ * written prior permission. The copyright holders make no representations
+ * about the suitability of this software for any purpose. It is provided "as
+ * is" without express or implied warranty.
+ *
+ * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
+ * OF THIS SOFTWARE.
+ */
+
+#ifndef SKIPLIST_H
+#define SKIPLIST_H
+
+#define MAX_LEVEL 31
+
+/*
+ * Skip list element. In order to use the skip list, the caller must
+ * generate a structure for list elements that has as its final member
+ * a skip_elt_t, (which will be allocated with variable size).
+ *
+ * The caller must also pass the size of the structure to
+ * skip_list_init.
+ */
+typedef struct _skip_elt {
+ int prev_index;
+ struct _skip_elt *prev;
+ struct _skip_elt *next[1];
+} skip_elt_t;
+
+#define SKIP_LIST_ELT_TO_DATA(type, elt) ((type *) ((char *) (elt) - (sizeof (type) - sizeof (skip_elt_t))))
+
+typedef int
+(*skip_list_compare_t) (void *list, void *a, void *b);
+
+typedef struct _skip_list {
+ skip_list_compare_t compare;
+ size_t elt_size;
+ size_t data_size;
+ skip_elt_t *chains[MAX_LEVEL];
+ int max_level;
+} skip_list_t;
+
+/* Initialize a new skip list. The compare function accepts a pointer
+ * to the list as well as pointers to two elements. The function must
+ * return a value greater than zero, zero, or less then 0 if the first
+ * element is considered respectively greater than, equal to, or less
+ * than the second element. The size of each object, (as computed by
+ * sizeof) is passed for elt_size. Note that the structure used for
+ * list elements must have as its final member a skip_elt_t
+ */
+void
+skip_list_init (skip_list_t *list,
+ skip_list_compare_t compare,
+ size_t elt_size);
+
+/* Insert a new element into the list at the correct sort order as
+ * determined by compare. Data will be copied (elt_size bytes from
+ * <data> via memcpy). The new element is returned. */
+void *
+skip_list_insert (skip_list_t *list, void *data);
+
+/* Find an element which compare considers equal to <data> */
+void *
+skip_list_find (skip_list_t *list, void *data);
+
+/* Delete an element which compare considers equal to <data> */
+void
+skip_list_delete (skip_list_t *list, void *data);
+
+/* Delete the given element from the list. */
+void
+skip_list_delete_given (skip_list_t *list, skip_elt_t *given);
+
+#endif
diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c
new file mode 100644
index 0000000..49b78de
--- /dev/null
+++ b/src/cairo-skiplist.c
@@ -0,0 +1,238 @@
+/*
+ * Copyright © 2006 Keith Packard
+ * Copyright © 2006 Carl Worth
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that copyright
+ * notice and this permission notice appear in supporting documentation, and
+ * that the name of the copyright holders not be used in advertising or
+ * publicity pertaining to distribution of the software without specific,
+ * written prior permission. The copyright holders make no representations
+ * about the suitability of this software for any purpose. It is provided "as
+ * is" without express or implied warranty.
+ *
+ * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
+ * OF THIS SOFTWARE.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stddef.h>
+#include <string.h>
+#include <assert.h>
+
+#include "cairo-skiplist-private.h"
+
+#define ELT_DATA(elt) (void *) ((char*) (elt) - list->data_size)
+#define NEXT_TO_ELT(next) (skip_elt_t *) ((char *) (next) - offsetof (skip_elt_t, next))
+
+/*
+ * Initialize an empty skip list
+ */
+void
+skip_list_init (skip_list_t *list,
+ skip_list_compare_t compare,
+ size_t elt_size)
+{
+ int i;
+
+ list->compare = compare;
+ list->elt_size = elt_size;
+ list->data_size = elt_size - sizeof (skip_elt_t);
+
+ for (i = 0; i < MAX_LEVEL; i++)
+ list->chains[i] = NULL;
+
+ list->max_level = 0;
+}
+
+/*
+ * Generate a random level number, distributed
+ * so that each level is 1/4 as likely as the one before
+ *
+ * Note that level numbers run 1 <= level <= MAX_LEVEL
+ */
+static int
+random_level (void)
+{
+ /* tricky bit -- each bit is '1' 75% of the time */
+ long int bits = random () | random ();
+ int level = 0;
+
+ while (++level < MAX_LEVEL)
+ {
+ if (bits & 1)
+ break;
+ bits >>= 1;
+ }
+ return level;
+}
+
+/*
+ * Insert 'data' into the list
+ */
+void *
+skip_list_insert (skip_list_t *list, void *data)
+{
+ skip_elt_t **update[MAX_LEVEL];
+ char *data_and_elt;
+ skip_elt_t *elt, *prev, **next;
+ int i, level, prev_index;
+
+ level = random_level ();
+ prev_index = level - 1;
+
+ /*
+ * Find links along each chain
+ */
+ prev = NULL;
+ next = list->chains;
+ for (i = list->max_level; --i >= 0; )
+ {
+ for (; (elt = next[i]); next = elt->next)
+ {
+ if (list->compare (list, ELT_DATA(elt), data) > 0)
+ break;
+ }
+ update[i] = next;
+ if (i == prev_index && next != list->chains)
+ prev = NEXT_TO_ELT (next);
+ }
+
+ /*
+ * Create new list element
+ */
+ if (level > list->max_level)
+ {
+ level = list->max_level + 1;
+ prev_index = level - 1;
+ update[list->max_level] = list->chains;
+ list->max_level = level;
+ }
+
+ data_and_elt = malloc (list->elt_size + (level-1) * sizeof (skip_elt_t *));
+ memcpy (data_and_elt, data, list->data_size);
+ elt = (skip_elt_t *) (data_and_elt + list->data_size);
+
+ elt->prev_index = prev_index;
+ elt->prev = prev;
+
+ /*
+ * Insert into all chains
+ */
+ for (i = 0; i < level; i++)
+ {
+ elt->next[i] = update[i][i];
+ if (elt->next[i] && elt->next[i]->prev_index == i)
+ elt->next[i]->prev = elt;
+ update[i][i] = elt;
+ }
+
+ return data_and_elt;
+}
+
+void *
+skip_list_find (skip_list_t *list, void *data)
+{
+ int i;
+ skip_elt_t **next = list->chains;
+ skip_elt_t *elt;
+
+ /*
+ * Walk chain pointers one level at a time
+ */
+ for (i = list->max_level; --i >= 0;)
+ while (next[i] && list->compare (list, data, ELT_DATA(next[i])) > 0)
+ {
+ next = next[i]->next;
+ }
+ /*
+ * Here we are
+ */
+ elt = next[0];
+ if (elt && list->compare (list, data, ELT_DATA (elt)) == 0)
+ return ELT_DATA (elt);
+
+ return NULL;
+}
+
+void
+skip_list_delete (skip_list_t *list, void *data)
+{
+ skip_elt_t **update[MAX_LEVEL], *prev[MAX_LEVEL];
+ skip_elt_t *elt, **next;
+ int i;
+
+ /*
+ * Find links along each chain
+ */
+ next = list->chains;
+ for (i = list->max_level; --i >= 0; )
+ {
+ for (; (elt = next[i]); next = elt->next)
+ {
+ if (list->compare (list, ELT_DATA (elt), data) >= 0)
+ break;
+ }
+ update[i] = &next[i];
+ if (next == list->chains)
+ prev[i] = NULL;
+ else
+ prev[i] = NEXT_TO_ELT (next);
+ }
+ elt = next[0];
+ assert (list->compare (list, ELT_DATA (elt), data) == 0);
+ for (i = 0; i < list->max_level && *update[i] == elt; i++) {
+ *update[i] = elt->next[i];
+ if (elt->next[i] && elt->next[i]->prev_index == i)
+ elt->next[i]->prev = prev[i];
+ }
+ while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL)
+ list->max_level--;
+ free (ELT_DATA (elt));
+}
+
+void
+skip_list_delete_given (skip_list_t *list, skip_elt_t *given)
+{
+ skip_elt_t **update[MAX_LEVEL], *prev[MAX_LEVEL];
+ skip_elt_t *elt, **next;
+ int i;
+
+ /*
+ * Find links along each chain
+ */
+ if (given->prev)
+ next = given->prev->next;
+ else
+ next = list->chains;
+ for (i = given->prev_index + 1; --i >= 0; )
+ {
+ for (; (elt = next[i]); next = elt->next)
+ {
+ if (elt == given)
+ break;
+ }
+ update[i] = &next[i];
+ if (next == list->chains)
+ prev[i] = NULL;
+ else
+ prev[i] = NEXT_TO_ELT (next);
+ }
+ elt = next[0];
+ assert (elt == given);
+ for (i = 0; i < (given->prev_index + 1) && *update[i] == elt; i++) {
+ *update[i] = elt->next[i];
+ if (elt->next[i] && elt->next[i]->prev_index == i)
+ elt->next[i]->prev = prev[i];
+ }
+ while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL)
+ list->max_level--;
+ free (ELT_DATA (elt));
+}
More information about the cairo-commit
mailing list