summaryrefslogtreecommitdiff
path: root/render
diff options
context:
space:
mode:
Diffstat (limited to 'render')
-rw-r--r--render/edgelist.c288
-rw-r--r--render/fill.c123
-rw-r--r--render/glyphcache.c370
-rw-r--r--render/pixmap.c60
-rw-r--r--render/porterduff.c74
-rw-r--r--render/render.c183
-rw-r--r--render/scanconv.c176
-rw-r--r--render/stroke.c716
8 files changed, 1990 insertions, 0 deletions
diff --git a/render/edgelist.c b/render/edgelist.c
new file mode 100644
index 00000000..d62ffad4
--- /dev/null
+++ b/render/edgelist.c
@@ -0,0 +1,288 @@
+#include <fitz.h>
+
+/*
+ * Global Edge List -- list of straight path segments for scan conversion
+ *
+ * Stepping along the edges is with bresenham's line algorithm.
+ *
+ * See Mike Abrash -- Graphics Programming Black Book (notably chapter 40)
+ */
+
+fz_error *
+fz_newgel(fz_gel **gelp)
+{
+ fz_gel *gel;
+
+ gel = *gelp = fz_malloc(sizeof(fz_gel));
+ if (!gel)
+ return fz_outofmem;
+
+ gel->edges = nil;
+
+ gel->cap = 512;
+ gel->len = 0;
+ gel->edges = fz_malloc(sizeof(fz_edge) * gel->cap);
+ if (!gel->edges) {
+ fz_free(gel);
+ return fz_outofmem;
+ }
+
+ gel->xmin = gel->ymin = INT_MAX;
+ gel->xmax = gel->ymax = INT_MIN;
+ gel->hs = 1;
+ gel->vs = 1;
+
+ return nil;
+}
+
+void
+fz_resetgel(fz_gel *gel, int hs, int vs)
+{
+ gel->xmin = gel->ymin = INT_MAX;
+ gel->xmax = gel->ymax = INT_MIN;
+ gel->hs = hs;
+ gel->vs = vs;
+ gel->len = 0;
+}
+
+void
+fz_freegel(fz_gel *gel)
+{
+ fz_free(gel->edges);
+ fz_free(gel);
+}
+
+fz_error *
+fz_insertgel(fz_gel *gel, float fx0, float fy0, float fx1, float fy1)
+{
+ fz_edge *edge;
+ int dx, dy;
+ int winding;
+ int width;
+ int tmp;
+
+ fx0 *= gel->hs;
+ fy0 *= gel->vs;
+ fx1 *= gel->hs;
+ fy1 *= gel->vs;
+
+ /* TODO: should we round or truncate? */
+ int x0 = fx0 < 0 ? fx0 - 0.5 : fx0 + 0.5;
+ int y0 = fy0 < 0 ? fy0 - 0.5 : fy0 + 0.5;
+ int x1 = fx1 < 0 ? fx1 - 0.5 : fx1 + 0.5;
+ int y1 = fy1 < 0 ? fy1 - 0.5 : fy1 + 0.5;
+
+ if (y0 == y1)
+ return nil;
+
+ if (y0 > y1) {
+ winding = -1;
+ tmp = x0; x0 = x1; x1 = tmp;
+ tmp = y0; y0 = y1; y1 = tmp;
+ }
+ else
+ winding = 1;
+
+ if (x0 < gel->xmin) gel->xmin = x0;
+ if (x0 > gel->xmax) gel->xmax = x0;
+ if (x1 < gel->xmin) gel->xmin = x1;
+ if (x1 > gel->xmax) gel->xmax = x1;
+
+ if (y0 < gel->ymin) gel->ymin = y0;
+ if (y1 > gel->ymax) gel->ymax = y1;
+
+ if (gel->len + 1 == gel->cap) {
+ int newcap = gel->cap + 512;
+ fz_edge *newedges = fz_realloc(gel->edges, sizeof(fz_edge) * newcap);
+ if (!newedges)
+ return fz_outofmem;
+ gel->cap = newcap;
+ gel->edges = newedges;
+ }
+
+ edge = &gel->edges[gel->len++];
+
+ dy = y1 - y0;
+ dx = x1 - x0;
+ width = dx < 0 ? -dx : dx;
+
+ edge->xdir = dx > 0 ? 1 : -1;
+ edge->ydir = winding;
+ edge->x = x0;
+ edge->y = y0;
+ edge->h = dy;
+ edge->adjdown = dy;
+
+ /* initial error term going l->r and r->l */
+ if (dx >= 0)
+ edge->e = 0;
+ else
+ edge->e = -dy + 1;
+
+ /* y-major edge */
+ if (dy >= width) {
+ edge->xmove = 0;
+ edge->adjup = width;
+ }
+
+ /* x-major edge */
+ else {
+ edge->xmove = (width / dy) * edge->xdir;
+ edge->adjup = width % dy;
+ }
+
+ return nil;
+}
+
+void
+fz_sortgel(fz_gel *gel)
+{
+ fz_edge *a = gel->edges;
+ int n = gel->len;
+
+ int h, i, k;
+ fz_edge t;
+
+ h = 1;
+ if (n < 14) {
+ h = 1;
+ }
+ else {
+ while (h < n)
+ h = 3 * h + 1;
+ h /= 3;
+ h /= 3;
+ }
+
+ while (h > 0)
+ {
+ for (i = 0; i < n; i++) {
+ t = a[i];
+ k = i - h;
+ /* TODO: sort on y major, x minor */
+ while (k >= 0 && a[k].y > t.y) {
+ a[k + h] = a[k];
+ k -= h;
+ }
+ a[k + h] = t;
+ }
+
+ h /= 3;
+ }
+}
+
+/*
+ * Active Edge List -- keep track of active edges while sweeping
+ */
+
+fz_error *
+fz_newael(fz_ael **aelp)
+{
+ fz_ael *ael;
+
+ ael = *aelp = fz_malloc(sizeof(fz_ael));
+ if (!ael)
+ return fz_outofmem;
+
+ ael->cap = 64;
+ ael->len = 0;
+ ael->edges = fz_malloc(sizeof(fz_edge*) * ael->cap);
+ if (!ael->edges) {
+ fz_free(ael);
+ return fz_outofmem;
+ }
+
+ return nil;
+}
+
+void
+fz_freeael(fz_ael *ael)
+{
+ fz_free(ael->edges);
+ fz_free(ael);
+}
+
+static inline void
+sortael(fz_edge **a, int n)
+{
+ int h, i, k;
+ fz_edge *t;
+
+ h = 1;
+ if (n < 14) {
+ h = 1;
+ }
+ else {
+ while (h < n)
+ h = 3 * h + 1;
+ h /= 3;
+ h /= 3;
+ }
+
+ while (h > 0)
+ {
+ for (i = 0; i < n; i++) {
+ t = a[i];
+ k = i - h;
+ while (k >= 0 && a[k]->x > t->x) {
+ a[k + h] = a[k];
+ k -= h;
+ }
+ a[k + h] = t;
+ }
+
+ h /= 3;
+ }
+}
+
+fz_error *
+fz_insertael(fz_ael *ael, fz_gel *gel, int y, int *e)
+{
+ /* insert edges that start here */
+ while (*e < gel->len && gel->edges[*e].y == y) {
+ if (ael->len + 1 == ael->cap) {
+ int newcap = ael->cap + 64;
+ fz_edge **newedges = fz_realloc(ael->edges, sizeof(fz_edge*) * newcap);
+ if (!newedges)
+ return fz_outofmem;
+ ael->edges = newedges;
+ ael->cap = newcap;
+ }
+ ael->edges[ael->len++] = &gel->edges[(*e)++];
+ }
+
+ /* shell-sort the edges by increasing x */
+ sortael(ael->edges, ael->len);
+
+ return nil;
+}
+
+void
+fz_advanceael(fz_ael *ael)
+{
+ fz_edge *edge;
+ int i = 0;
+
+ while (i < ael->len)
+ {
+ edge = ael->edges[i];
+
+ edge->h --;
+
+ /* terminator! */
+ if (edge->h == 0) {
+ ael->edges[i] = ael->edges[--ael->len];
+ }
+
+ else {
+ edge->x += edge->xmove;
+ edge->e += edge->adjup;
+ if (edge->e > 0) {
+ edge->x += edge->xdir;
+ edge->e -= edge->adjdown;
+ }
+ i ++;
+ }
+ }
+}
+
diff --git a/render/fill.c b/render/fill.c
new file mode 100644
index 00000000..4605726d
--- /dev/null
+++ b/render/fill.c
@@ -0,0 +1,123 @@
+#include <fitz.h>
+
+static fz_error *
+line(fz_gel *gel, fz_matrix *ctm, float x0, float y0, float x1, float y1)
+{
+ float tx0 = ctm->a * x0 + ctm->c * y0 + ctm->e;
+ float ty0 = ctm->b * x0 + ctm->d * y0 + ctm->f;
+ float tx1 = ctm->a * x1 + ctm->c * y1 + ctm->e;
+ float ty1 = ctm->b * x1 + ctm->d * y1 + ctm->f;
+ return fz_insertgel(gel, tx0, ty0, tx1, ty1);
+}
+
+static fz_error *
+bezier(fz_gel *gel, fz_matrix *ctm, float flatness,
+ float xa, float ya,
+ float xb, float yb,
+ float xc, float yc,
+ float xd, float yd)
+{
+ fz_error *error;
+ float dmax;
+ float xab, yab;
+ float xbc, ybc;
+ float xcd, ycd;
+ float xabc, yabc;
+ float xbcd, ybcd;
+ float xabcd, yabcd;
+
+ /* termination check */
+ dmax = ABS(xa - xb);
+ dmax = MAX(dmax, ABS(ya - yb));
+ dmax = MAX(dmax, ABS(xd - xc));
+ dmax = MAX(dmax, ABS(yd - yc));
+ if (dmax < flatness)
+ return line(gel, ctm, xa, ya, xd, yd);
+
+ xab = xa + xb;
+ yab = ya + yb;
+ xbc = xb + xc;
+ ybc = yb + yc;
+ xcd = xc + xd;
+ ycd = yc + yd;
+
+ xabc = xab + xbc;
+ yabc = yab + ybc;
+ xbcd = xbc + xcd;
+ ybcd = ybc + ycd;
+
+ xabcd = xabc + xbcd;
+ yabcd = yabc + ybcd;
+
+ xab *= 0.5f; yab *= 0.5f;
+ xbc *= 0.5f; ybc *= 0.5f;
+ xcd *= 0.5f; ycd *= 0.5f;
+
+ xabc *= 0.25f; yabc *= 0.25f;
+ xbcd *= 0.25f; ybcd *= 0.25f;
+
+ xabcd *= 0.125f; yabcd *= 0.125f;
+
+ error = bezier(gel, ctm, flatness, xa, ya, xab, yab, xabc, yabc, xabcd, yabcd);
+ if (error)
+ return error;
+ return bezier(gel, ctm, flatness, xabcd, yabcd, xbcd, ybcd, xcd, ycd, xd, yd);
+}
+
+fz_error *
+fz_fillpath(fz_gel *gel, fz_path *path, fz_matrix ctm, float flatness)
+{
+ fz_error *error;
+ float x1, y1, x2, y2, x3, y3;
+ float cx = 0;
+ float cy = 0;
+ float bx = 0;
+ float by = 0;
+ int i = 0;
+
+ while (i < path->len)
+ {
+ switch (path->els[i++].k)
+ {
+ case FZ_MOVETO:
+ x1 = path->els[i++].v;
+ y1 = path->els[i++].v;
+ cx = bx = x1;
+ cy = by = y1;
+ break;
+
+ case FZ_LINETO:
+ x1 = path->els[i++].v;
+ y1 = path->els[i++].v;
+ error = line(gel, &ctm, cx, cy, x1, y1);
+ if (error)
+ return error;
+ cx = x1;
+ cy = y1;
+ break;
+
+ case FZ_CURVETO:
+ x1 = path->els[i++].v;
+ y1 = path->els[i++].v;
+ x2 = path->els[i++].v;
+ y2 = path->els[i++].v;
+ x3 = path->els[i++].v;
+ y3 = path->els[i++].v;
+ error = bezier(gel, &ctm, flatness, cx, cy, x1, y1, x2, y2, x3, y3);
+ if (error)
+ return error;
+ cx = x3;
+ cy = y3;
+ break;
+
+ case FZ_CLOSEPATH:
+ error = line(gel, &ctm, cx, cy, bx, by);
+ if (error)
+ return error;
+ break;
+ }
+ }
+
+ return nil;
+}
+
diff --git a/render/glyphcache.c b/render/glyphcache.c
new file mode 100644
index 00000000..81b1f5d5
--- /dev/null
+++ b/render/glyphcache.c
@@ -0,0 +1,370 @@
+#include <fitz.h>
+
+#define HSUBPIX 5.0
+#define VSUBPIX 5.0
+
+typedef struct fz_hash_s fz_hash;
+typedef struct fz_key_s fz_key;
+typedef struct fz_val_s fz_val;
+
+struct fz_glyphcache_s
+{
+ int slots;
+ int size;
+ fz_hash *hash;
+ fz_val *lru;
+ unsigned char *buffer;
+ int load;
+ int used;
+};
+
+struct fz_key_s
+{
+ void *fid;
+ int a, b;
+ int c, d;
+ unsigned short gid;
+ unsigned char e, f;
+};
+
+struct fz_hash_s
+{
+ fz_key key;
+ fz_val *val;
+};
+
+struct fz_val_s
+{
+ fz_hash *ent;
+ unsigned char *data;
+ short w, h, lsb, top;
+ int uses;
+};
+
+static unsigned int hashkey(fz_key *key)
+{
+ unsigned char *s = (char*)key;
+ unsigned int hash = 0;
+ unsigned int i;
+ for (i = 0; i < sizeof(fz_key); i++)
+ {
+ hash += s[i];
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ }
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+ return hash;
+}
+
+fz_error *
+fz_newglyphcache(fz_glyphcache **arenap, int slots, int size)
+{
+ fz_glyphcache *arena;
+
+ arena = *arenap = fz_malloc(sizeof(fz_glyphcache));
+ if (!arena)
+ return fz_outofmem;
+
+ arena->slots = slots;
+ arena->size = size;
+
+ arena->hash = nil;
+ arena->lru = nil;
+ arena->buffer = nil;
+
+ arena->hash = fz_malloc(sizeof(fz_hash) * slots);
+ if (!arena->hash)
+ goto cleanup;
+
+ arena->lru = fz_malloc(sizeof(fz_val) * slots);
+ if (!arena->lru)
+ goto cleanup;
+
+ arena->buffer = fz_malloc(size);
+ if (!arena->buffer)
+ goto cleanup;
+
+ memset(arena->hash, 0, sizeof(fz_hash) * slots);
+ memset(arena->lru, 0, sizeof(fz_val) * slots);
+ memset(arena->buffer, 0, size);
+ arena->load = 0;
+ arena->used = 0;
+
+ return nil;
+
+cleanup:
+ fz_free(arena->hash);
+ fz_free(arena->lru);
+ fz_free(arena->buffer);
+ fz_free(arena);
+ return fz_outofmem;
+}
+
+void
+fz_freeglyphcache(fz_glyphcache *arena)
+{
+ fz_free(arena->hash);
+ fz_free(arena->lru);
+ fz_free(arena->buffer);
+ fz_free(arena);
+}
+
+static int hokay = 0;
+static int hcoll = 0;
+static int hdist = 0;
+static int coos = 0;
+static int covf = 0;
+
+static fz_val *
+hashfind(fz_glyphcache *arena, fz_key *key)
+{
+ fz_hash *tab = arena->hash;
+ int pos = hashkey(key) % arena->slots;
+
+ while (1)
+ {
+ if (!tab[pos].val)
+ return nil;
+
+ if (memcmp(key, &tab[pos].key, sizeof (fz_key)) == 0)
+ return tab[pos].val;
+
+ pos = pos + 1;
+ if (pos == arena->slots)
+ pos = 0;
+ }
+}
+
+static void
+hashinsert(fz_glyphcache *arena, fz_key *key, fz_val *val)
+{
+ fz_hash *tab = arena->hash;
+ int pos = hashkey(key) % arena->slots;
+int didcoll = 0;
+
+ while (1)
+ {
+ if (!tab[pos].val)
+ {
+ tab[pos].key = *key;
+ tab[pos].val = val;
+ tab[pos].val->ent = &tab[pos];
+if (didcoll) hcoll ++; else hokay ++; hdist += didcoll;
+ return;
+ }
+
+ pos = pos + 1;
+ if (pos == arena->slots)
+ pos = 0;
+didcoll ++;
+ }
+}
+
+static void
+hashremove(fz_glyphcache *arena, fz_key *key)
+{
+ fz_hash *tab = arena->hash;
+ unsigned int pos = hashkey(key) % arena->slots;
+ unsigned int hole;
+ unsigned int look;
+ unsigned int code;
+
+ while (1)
+ {
+ if (!tab[pos].val)
+ return; /* boo hoo! tried to remove non-existant key */
+
+ if (memcmp(key, &tab[pos].key, sizeof (fz_key)) == 0)
+ {
+ tab[pos].val = nil;
+
+ hole = pos;
+ look = hole + 1;
+ if (look == arena->slots)
+ look = 0;
+
+ while (tab[look].val)
+ {
+ code = (hashkey(&tab[look].key) % arena->slots);
+ if ((code <= hole && hole < look) ||
+ (look < code && code <= hole) ||
+ (hole < look && look < code))
+ {
+ tab[hole] = tab[look];
+ tab[hole].val->ent = &tab[hole];
+ tab[look].val = nil;
+ hole = look;
+ }
+
+ look = look + 1;
+ if (look == arena->slots)
+ look = 0;
+ }
+
+ return;
+ }
+
+ pos = pos + 1;
+ if (pos == arena->slots)
+ pos = 0;
+ }
+}
+
+void
+fz_debugglyphcache(fz_glyphcache *arena)
+{
+ int i;
+
+ printf("cache load %d / %d (%d / %d bytes)\n",
+ arena->load, arena->slots, arena->used, arena->size);
+ printf("no-colliders: %d colliders: %d\n", hokay, hcoll);
+ printf("avg dist: %d / %d: %g\n", hdist, hcoll, (double)hdist / hcoll);
+ printf("out-of-space evicts: %d\n", coos);
+ printf("out-of-hash evicts: %d\n", covf);
+
+ for (i = 0; i < arena->slots; i++)
+ {
+ if (!arena->hash[i].val)
+ printf("glyph % 4d: empty\n", i);
+ else {
+ fz_key *k = &arena->hash[i].key;
+ fz_val *b = arena->hash[i].val;
+ printf("glyph % 4d: %p %d [%g %g %g %g + %d %d] "
+ "-> [%dx%d %d,%d]\n", i,
+ k->fid, k->gid,
+ k->a / 65536.0,
+ k->b / 65536.0,
+ k->c / 65536.0,
+ k->d / 65536.0,
+ k->e, k->f,
+ b->w, b->h, b->lsb, b->top);
+ }
+ }
+
+ for (i = 0; i < arena->load; i++)
+ printf("lru %04d: glyph %d (%d)\n", i,
+ arena->lru[i].ent - arena->hash, arena->lru[i].uses);
+}
+
+static void
+bubble(fz_glyphcache *arena, int i)
+{
+ fz_val tmp;
+
+ if (i == 0 || arena->load < 2)
+ return;
+
+ tmp = arena->lru[i - 1];
+ arena->lru[i - 1] = arena->lru[i];
+ arena->lru[i] = tmp;
+
+ arena->lru[i - 1].ent->val = &arena->lru[i - 1];
+ arena->lru[i].ent->val = &arena->lru[i];
+}
+
+static void
+evictlast(fz_glyphcache *arena)
+{
+ fz_val *lru = arena->lru;
+ unsigned char *s, *e;
+ int i, k;
+ fz_key key;
+
+ if (arena->load == 0)
+ return;
+
+ k = arena->load - 1;
+ s = lru[k].data;
+ e = s + lru[k].w * lru[k].h;
+
+ /* pack buffer to fill hole */
+ memmove(s, e, arena->buffer + arena->used - e);
+ memset(arena->buffer + arena->used - (e - s), 0, e - s);
+ arena->used -= e - s;
+
+ /* update lru pointers */
+ for (i = 0; i < k; i++)
+ if (lru[i].data >= e)
+ lru[i].data -= e - s;
+
+ /* remove hash entry */
+ key = lru[k].ent->key;
+ hashremove(arena, &key);
+
+ arena->load --;
+}
+
+fz_error *
+fz_renderglyph(fz_glyphcache *arena, fz_glyph *glyph, fz_font *font, int gid, fz_matrix ctm)
+{
+ fz_error *error;
+ fz_key key;
+ fz_val *val;
+ int size;
+
+ key.fid = font;
+ key.gid = gid;
+ key.a = ctm.a * 65536;
+ key.b = ctm.b * 65536;
+ key.c = ctm.c * 65536;
+ key.d = ctm.d * 65536;
+ key.e = (ctm.e - floor(ctm.e)) * HSUBPIX;
+ key.f = (ctm.f - floor(ctm.f)) * VSUBPIX;
+
+ val = hashfind(arena, &key);
+ if (val)
+ {
+ val->uses ++;
+ glyph->w = val->w;
+ glyph->h = val->h;
+ glyph->lsb = val->lsb;
+ glyph->top = val->top;
+ glyph->bitmap = val->data;
+
+ bubble(arena, val - arena->lru);
+
+ return nil;
+ }
+
+ ctm.e = floor(ctm.e) + key.e / HSUBPIX;
+ ctm.f = floor(ctm.f) + key.f / HSUBPIX;
+
+ error = font->render(glyph, font, gid, ctm);
+ if (error)
+ return error;
+
+ size = glyph->w * glyph->h;
+
+ if (size > arena->size / 6)
+ return nil;
+
+ while (arena->load > arena->slots * 75 / 100) {
+ covf ++;
+ evictlast(arena);
+ }
+
+ while (arena->used + size >= arena->size) {
+ coos ++;
+ evictlast(arena);
+ }
+
+ val = &arena->lru[arena->load++];
+ val->uses = 0;
+ val->w = glyph->w;
+ val->h = glyph->h;
+ val->lsb = glyph->lsb;
+ val->top = glyph->top;
+ val->data = arena->buffer + arena->used;
+
+ arena->used += size;
+
+ memcpy(val->data, glyph->bitmap, glyph->w * glyph->h);
+ glyph->bitmap = val->data;
+
+ hashinsert(arena, &key, val);
+
+ return nil;
+}
+
diff --git a/render/pixmap.c b/render/pixmap.c
new file mode 100644
index 00000000..57402d81
--- /dev/null
+++ b/render/pixmap.c
@@ -0,0 +1,60 @@
+#include <fitz.h>
+
+fz_error *
+fz_newpixmap(fz_pixmap **pixp, int x, int y, int w, int h, int n, int a)
+{
+ fz_pixmap *pix;
+
+ pix = *pixp = fz_malloc(sizeof (fz_pixmap));
+ if (!pix)
+ return fz_outofmem;
+
+ pix->x = x;
+ pix->y = y;
+ pix->w = w;
+ pix->h = h;
+ pix->n = n;
+ pix->a = a;
+ pix->cs = nil;
+ pix->stride = (pix->n + pix->a) * pix->w;
+
+ pix->samples = fz_malloc(sizeof(short) * pix->stride * pix->h);
+ if (!pix->samples) {
+ fz_free(pix);
+ return fz_outofmem;
+ }
+
+ memset(pix->samples, 0, sizeof(short) * pix->stride * pix->h);
+
+ return nil;
+}
+
+void
+fz_freepixmap(fz_pixmap *pix)
+{
+ fz_free(pix->samples);
+ fz_free(pix);
+}
+
+void
+fz_clearpixmap(fz_pixmap *pix)
+{
+ memset(pix->samples, 0, sizeof(short) * pix->stride * pix->h);
+}
+
+void
+fz_debugpixmap(fz_pixmap *pix)
+{
+ int x, y;
+ FILE *f = fopen("out.ppm", "w");
+ fprintf(f, "P6\n%d %d\n255\n", pix->w, pix->h);
+ for (y = 0; y < pix->h; y++)
+ for (x = 0; x < pix->w; x++)
+ {
+ putc(255 - pix->samples[x + y * pix->stride], f);
+ putc(255 - pix->samples[x + y * pix->stride], f);
+ putc(255 - pix->samples[x + y * pix->stride], f);
+ }
+ fclose(f);
+}
+
diff --git a/render/porterduff.c b/render/porterduff.c
new file mode 100644
index 00000000..1cedbc38
--- /dev/null
+++ b/render/porterduff.c
@@ -0,0 +1,74 @@
+#include <fitz.h>
+
+/* Porter-Duff compositing arithmetic on premultiplied ARGB buffers */
+
+void
+fz_blendover(unsigned char *C, unsigned char *A, unsigned char *B, int n)
+{
+ while (n--)
+ {
+ unsigned char Fa = 255;
+ unsigned char Fb = 255 - A[0];
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ }
+}
+
+void
+fz_blendin(unsigned char *C, unsigned char *A, unsigned char *B, int n)
+{
+ while (n--)
+ {
+ unsigned char Fa = B[0];
+ unsigned char Fb = 0;
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ }
+}
+
+void
+fz_blendout(unsigned char *C, unsigned char *A, unsigned char *B, int n)
+{
+ while (n--)
+ {
+ unsigned char Fa = 255 - B[0];
+ unsigned char Fb = 0;
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ }
+}
+
+void
+fz_blendatop(unsigned char *C, unsigned char *A, unsigned char *B, int n)
+{
+ while (n--)
+ {
+ unsigned char Fa = B[0];
+ unsigned char Fb = 255 - A[0];
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ }
+}
+
+void
+fz_blendxor(unsigned char *C, unsigned char *A, unsigned char *B, int n)
+{
+ while (n--)
+ {
+ unsigned char Fa = 255 - B[0];
+ unsigned char Fb = 255 - A[0];
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ *C++ = fz_mul255(*A++, Fa) + fz_mul255(*B++, Fb);
+ }
+}
+
diff --git a/render/render.c b/render/render.c
new file mode 100644
index 00000000..64856dd2
--- /dev/null
+++ b/render/render.c
@@ -0,0 +1,183 @@
+#include <fitz.h>
+
+struct fz_renderer_s
+{
+ fz_glyphcache *cache;
+ fz_gel *gel;
+ fz_ael *ael;
+};
+
+fz_error *
+fz_newrenderer(fz_renderer **gcp)
+{
+ fz_error *error;
+ fz_renderer *gc;
+
+ gc = *gcp = fz_malloc(sizeof(fz_renderer));
+ if (!gc)
+ return fz_outofmem;
+
+ gc->cache = nil;
+ gc->gel = nil;
+ gc->ael = nil;
+
+ error = fz_newglyphcache(&gc->cache, 1024, 65536);
+ if (error)
+ goto cleanup;
+
+ error = fz_newgel(&gc->gel);
+ if (error)
+ goto cleanup;
+
+ error = fz_newael(&gc->ael);
+ if (error)
+ goto cleanup;
+
+ return nil;
+
+cleanup:
+ if (gc->cache)
+ fz_freeglyphcache(gc->cache);
+ if (gc->gel)
+ fz_freegel(gc->gel);
+ if (gc->ael)
+ fz_freeael(gc->ael);
+ fz_free(gc);
+
+ return error;
+}
+
+void
+fz_freerenderer(fz_renderer *gc)
+{
+ if (gc->cache)
+ fz_freeglyphcache(gc->cache);
+ if (gc->gel)
+ fz_freegel(gc->gel);
+ if (gc->ael)
+ fz_freeael(gc->ael);
+ fz_free(gc);
+}
+
+fz_error *
+fz_renderover(fz_renderer *gc, fz_over *over, fz_matrix ctm, fz_pixmap *out)
+{
+ fz_error *error;
+ fz_node *node;
+
+ for (node = over->child; node; node = node->next)
+ {
+ error = fz_rendernode(gc, node, ctm, out);
+ if (error)
+ return error;
+ }
+
+ return nil;
+}
+
+fz_error *
+fz_rendermask(fz_renderer *gc, fz_mask *mask, fz_matrix ctm, fz_pixmap *out)
+{
+ fz_error *error;
+ fz_node *node;
+
+ for (node = mask->child; node; node = node->next)
+ {
+ error = fz_rendernode(gc, node, ctm, out);
+ if (error)
+ return error;
+ }
+
+ return nil;
+}
+
+fz_error *
+fz_rendertransform(fz_renderer *gc, fz_transform *xform, fz_matrix ctm, fz_pixmap *out)
+{
+ ctm = fz_concat(ctm, xform->m);
+ return fz_rendernode(gc, xform->child, ctm, out);
+}
+
+
+void composite(fz_pixmap *out, fz_glyph *gl, int xo, int yo)
+{
+ int sx, sy, dx, dy, a, b, c;
+
+ for (sy = 0; sy < gl->h; sy++)
+ {
+ for (sx = 0; sx < gl->w; sx++)
+ {
+ dx = xo + sx + gl->lsb;
+ dy = yo - sy + gl->top;
+
+ if (dx < 0) continue;
+ if (dy < 0) continue;
+ if (dx >= out->w) continue;
+ if (dy >= out->h) continue;
+
+ a = gl->bitmap[sx + sy * gl->w];
+ b = out->samples[dx + dy * out->stride];
+ c = MAX(a, b);
+ out->samples[dx + dy * out->stride] = c;
+ }
+ }
+}
+
+fz_error *
+fz_rendertext(fz_renderer *gc, fz_text *text, fz_matrix ctm, fz_pixmap *out)
+{
+ fz_error *error;
+ fz_glyph gl;
+ float x, y;
+ int g, i, ix, iy;
+ fz_matrix tm, trm;
+
+ tm = text->trm;
+
+ for (i = 0; i < text->len; i++)
+ {
+ g = text->els[i].g;
+ x = text->els[i].x;
+ y = text->els[i].y;
+
+ tm.e = x;
+ tm.f = y;
+ trm = fz_concat(tm, ctm);
+
+ ix = floor(trm.e);
+ iy = floor(trm.f);
+
+ trm.e = (trm.e - floor(trm.e));
+ trm.f = (trm.f - floor(trm.f));
+
+ error = fz_renderglyph(gc->cache, &gl, text->font, g, trm);
+ if (error)
+ return error;
+
+ composite(out, &gl, ix, iy);
+ }
+
+ return nil;
+}
+
+fz_error *
+fz_rendernode(fz_renderer *gc, fz_node *node, fz_matrix ctm, fz_pixmap *out)
+{
+ if (!node)
+ return nil;
+
+ switch (node->kind)
+ {
+ case FZ_NOVER:
+ return fz_renderover(gc, (fz_over*)node, ctm, out);
+ case FZ_NMASK:
+ return fz_rendermask(gc, (fz_mask*)node, ctm, out);
+ case FZ_NTRANSFORM:
+ return fz_rendertransform(gc, (fz_transform*)node, ctm, out);
+ case FZ_NTEXT:
+ return fz_rendertext(gc, (fz_text*)node, ctm, out);
+ default:
+ return nil;
+ }
+}
+
diff --git a/render/scanconv.c b/render/scanconv.c
new file mode 100644
index 00000000..b2d32363
--- /dev/null
+++ b/render/scanconv.c
@@ -0,0 +1,176 @@
+#include <fitz.h>
+
+static inline void
+addspan(short *list, int x0, int x1, int xofs, int hs)
+{
+ int x0pix, x0sub;
+ int x1pix, x1sub;
+
+ if (x0 == x1)
+ return;
+
+ /* x between 0 and width of bbox */
+ x0 -= xofs;
+ x1 -= xofs;
+
+ x0pix = x0 / hs;
+ x0sub = x0 % hs;
+ x1pix = x1 / hs;
+ x1sub = x1 % hs;
+
+ if (x0pix == x1pix)
+ {
+ list[x0pix] += x1sub - x0sub;
+ list[x0pix+1] += x0sub - x1sub;
+ }
+
+ else
+ {
+ list[x0pix] += hs - x0sub;
+ list[x0pix+1] += x0sub;
+ list[x1pix] += x1sub - hs;
+ list[x1pix+1] += -x1sub;
+ }
+}
+
+static inline void
+nonzerowinding(fz_ael *ael, short *list, int xofs, int hs)
+{
+ int winding = 0;
+ int x = 0;
+ int i;
+ for (i = 0; i < ael->len; i++)
+ {
+ if (!winding && (winding + ael->edges[i]->ydir))
+ x = ael->edges[i]->x;
+ if (winding && !(winding + ael->edges[i]->ydir))
+ addspan(list, x, ael->edges[i]->x, xofs, hs);
+ winding += ael->edges[i]->ydir;
+ }
+}
+
+static inline void
+evenodd(fz_ael *ael, short *list, int xofs, int hs)
+{
+ int even = 0;
+ int x = 0;
+ int i;
+ for (i = 0; i < ael->len; i++)
+ {
+ if (!even)
+ x = ael->edges[i]->x;
+ else
+ addspan(list, x, ael->edges[i]->x, xofs, hs);
+ even = !even;
+ }
+}
+
+/* XXX */
+
+unsigned char pixmap[1000 * 1000];
+
+void
+fz_emitdeltas(short *list, int y, int x, int n)
+{
+ short a = 0;
+ short d = 0;
+ while (n--) {
+ d = *list++;
+ a += d;
+ pixmap[y * 1000 + x] = 0xff - a;
+ x ++;
+ }
+}
+
+void
+savestuff(void)
+{
+ FILE *f = fopen("out.pgm", "w");
+ fprintf(f, "P5\n1000 1000\n255\n");
+ fwrite(pixmap, 1, 1000 * 1000, f);
+ fclose(f);
+}
+
+/* XXX */
+
+void
+fz_emitdeltas0(short *list, int y, int xofs, int n)
+{
+ int d = 0;
+ while (n--)
+ d += *list++;
+}
+
+fz_error *
+fz_scanconvert(fz_gel *gel, fz_ael *ael, int eofill)
+{
+ fz_error *error;
+ short *deltas;
+ int y, e;
+ int yd, yc;
+
+ int xmin = fz_idiv(gel->xmin, gel->hs);
+ int xmax = fz_idiv(gel->xmax, gel->hs) + 1;
+ int ymin = fz_idiv(gel->ymin, gel->vs);
+ int ymax = fz_idiv(gel->ymax, gel->vs) + 1;
+
+ int xofs = xmin * gel->hs;
+ int hs = gel->hs;
+ int vs = gel->vs;
+
+ if (gel->len == 0)
+ return nil;
+
+memset(pixmap, 0xff, sizeof pixmap);
+
+printf("bbox [%d %d %d %d] samp %d/%d edges %d\n",
+ xmin, ymin, xmax, ymax, hs, vs, gel->len);
+
+ deltas = fz_malloc(sizeof(short) * (xmax - xmin));
+ if (!deltas)
+ return fz_outofmem;
+ memset(deltas, 0, sizeof(short) * (xmax - xmin));
+
+ e = 0;
+ y = gel->edges[0].y;
+ yc = fz_idiv(y, vs);
+ yd = yc;
+
+ while (ael->len > 0 || e < gel->len)
+ {
+ yc = fz_idiv(y, vs);
+ if (yc != yd) {
+ fz_emitdeltas(deltas, yd, xmin, xmax - xmin);
+ memset(deltas, 0, sizeof(short) * (xmax - xmin));
+ }
+ yd = yc;
+
+ error = fz_insertael(ael, gel, y, &e);
+ if (error) {
+ fz_free(deltas);
+ return error;
+ }
+
+// { int i; for (i = 0; i < ael->len; i++)
+// pixmap[yd * 1000 + (ael->edges[i]->x / hs)] = 0; }
+
+ if (eofill)
+ evenodd(ael, deltas, xofs, hs);
+ else
+ nonzerowinding(ael, deltas, xofs, hs);
+
+ fz_advanceael(ael);
+
+ if (ael->len > 0)
+ y ++;
+ else if (e < gel->len)
+ y = gel->edges[e].y;
+ }
+
+ fz_emitdeltas(deltas, yd, xmin, xmax - xmin);
+
+ savestuff();
+
+ return nil;
+}
+
diff --git a/render/stroke.c b/render/stroke.c
new file mode 100644
index 00000000..1203f71b
--- /dev/null
+++ b/render/stroke.c
@@ -0,0 +1,716 @@
+#include <fitz.h>
+
+enum { BUTT = 0, ROUND = 1, SQUARE = 2, MITER = 0, BEVEL = 2 };
+
+struct sctx
+{
+ fz_gel *gel;
+ fz_matrix *ctm;
+ float flatness;
+
+ fz_stroke *stroke;
+ fz_point beg[2];
+ fz_point seg[2];
+ int sn, bn;
+ int dot;
+
+ fz_dash *dash;
+ int toggle;
+ int offset;
+ float phase;
+ fz_point cur;
+};
+
+static fz_error *
+line(struct sctx *s, float x0, float y0, float x1, float y1)
+{
+ float tx0 = s->ctm->a * x0 + s->ctm->c * y0 + s->ctm->e;
+ float ty0 = s->ctm->b * x0 + s->ctm->d * y0 + s->ctm->f;
+ float tx1 = s->ctm->a * x1 + s->ctm->c * y1 + s->ctm->e;
+ float ty1 = s->ctm->b * x1 + s->ctm->d * y1 + s->ctm->f;
+ return fz_insertgel(s->gel, tx0, ty0, tx1, ty1);
+}
+
+static fz_error *
+arc(struct sctx *s,
+ float xc, float yc,
+ float x0, float y0,
+ float x1, float y1)
+{
+ fz_error *error;
+ float th0, th1, r;
+ float theta;
+ float ox, oy, nx, ny;
+ int n, i;
+
+ r = fabs(s->stroke->linewidth);
+ theta = 2 * M_SQRT2 * sqrt(s->flatness / r);
+ th0 = atan2(y0, x0);
+ th1 = atan2(y1, x1);
+
+ if (r > 0)
+ {
+ if (th0 < th1)
+ th0 += M_PI * 2;
+ n = ceil((th0 - th1) / theta);
+ }
+ else
+ {
+ if (th1 < th0)
+ th1 += M_PI * 2;
+ n = ceil((th1 - th0) / theta);
+ }
+
+ ox = x0;
+ oy = y0;
+ for (i = 1; i < n; i++)
+ {
+ theta = th0 + (th1 - th0) * i / n;
+ nx = cos(theta) * r;
+ ny = sin(theta) * r;
+ error = line(s, xc + ox, yc + oy, xc + nx, yc + ny);
+ if (error) return error;
+ ox = nx;
+ oy = ny;
+ }
+
+ error = line(s, xc + ox, yc + oy, xc + x1, yc + y1);
+ if (error) return error;
+
+ return nil;
+}
+
+static fz_error *
+linestroke(struct sctx *s, fz_point a, fz_point b)
+{
+ fz_error *error;
+
+ float dx = b.x - a.x;
+ float dy = b.y - a.y;
+ float scale = s->stroke->linewidth / sqrt(dx * dx + dy * dy);
+ float dlx = dy * scale;
+ float dly = -dx * scale;
+
+ error = line(s, a.x - dlx, a.y - dly, b.x - dlx, b.y - dly);
+ if (error) return error;
+
+ error = line(s, b.x + dlx, b.y + dly, a.x + dlx, a.y + dly);
+ if (error) return error;
+
+ return nil;
+}
+
+static fz_error *
+linejoin(struct sctx *s, fz_point a, fz_point b, fz_point c)
+{
+ fz_error *error;
+ float miterlimit = s->stroke->miterlimit;
+ float linewidth = s->stroke->linewidth;
+ int linejoin = s->stroke->linejoin;
+ float dx0, dy0;
+ float dx1, dy1;
+ float dlx0, dly0;
+ float dlx1, dly1;
+ float dmx, dmy;
+ float dmr2;
+ float scale;
+ float cross;
+
+ dx0 = b.x - a.x;
+ dy0 = b.y - a.y;
+
+ dx1 = c.x - b.x;
+ dy1 = c.y - b.y;
+
+ if (dx0 * dx0 + dy0 * dy0 < FLT_EPSILON)
+ return nil;
+ if (dx1 * dx1 + dy1 * dy1 < FLT_EPSILON)
+ return nil;
+
+ scale = linewidth / sqrt(dx0 * dx0 + dy0 * dy0);
+ dlx0 = dy0 * scale;
+ dly0 = -dx0 * scale;
+
+ scale = linewidth / sqrt(dx1 * dx1 + dy1 * dy1);
+ dlx1 = dy1 * scale;
+ dly1 = -dx1 * scale;
+
+ cross = dx1 * dy0 - dx0 * dy1;
+
+ dmx = (dlx0 + dlx1) * 0.5;
+ dmy = (dly0 + dly1) * 0.5;
+ dmr2 = dmx * dmx + dmy * dmy;
+
+ if (cross * cross < FLT_EPSILON && dx0 * dx1 + dy0 * dy1 >= 0)
+ linejoin = BEVEL;
+
+ if (linejoin == MITER)
+ if (dmr2 * miterlimit * miterlimit < linewidth * linewidth)
+ linejoin = BEVEL;
+
+ if (linejoin == BEVEL)
+ {
+ error = line(s, b.x - dlx0, b.y - dly0, b.x - dlx1, b.y - dly1);
+ if (error) return error;
+ error = line(s, b.x + dlx1, b.y + dly1, b.x + dlx0, b.y + dly0);
+ if (error) return error;
+ }
+
+ if (linejoin == MITER)
+ {
+ scale = linewidth * linewidth / dmr2;
+ dmx *= scale;
+ dmy *= scale;
+
+ if (cross < 0)
+ {
+ error = line(s, b.x - dlx0, b.y - dly0, b.x - dlx1, b.y - dly1);
+ if (error) return error;
+ error = line(s, b.x + dlx1, b.y + dly1, b.x + dmx, b.y + dmy);
+ if (error) return error;
+ error = line(s, b.x + dmx, b.y + dmy, b.x + dlx0, b.y + dly0);
+ if (error) return error;
+ }
+ else
+ {
+ error = line(s, b.x + dlx1, b.y + dly1, b.x + dlx0, b.y + dly0);
+ if (error) return error;
+ error = line(s, b.x - dlx0, b.y - dly0, b.x - dmx, b.y - dmy);
+ if (error) return error;
+ error = line(s, b.x - dmx, b.y - dmy, b.x - dlx1, b.y - dly1);
+ if (error) return error;
+ }
+ }
+
+ if (linejoin == ROUND)
+ {
+ if (cross < 0)
+ {
+ error = line(s, b.x - dlx0, b.y - dly0, b.x - dlx1, b.y - dly1);
+ if (error) return error;
+ error = arc(s, b.x, b.y, dlx1, dly1, dlx0, dly0);
+ if (error) return error;
+ }
+ else
+ {
+ error = line(s, b.x + dlx1, b.y + dly1, b.x + dlx0, b.y + dly0);
+ if (error) return error;
+ error = arc(s, b.x, b.y, -dlx0, -dly0, -dlx1, -dly1);
+ if (error) return error;
+ }
+ }
+
+ return nil;
+}
+
+static fz_error *
+linecap(struct sctx *s, fz_point a, fz_point b)
+{
+ fz_error *error;
+ float flatness = s->flatness;
+ float linewidth = s->stroke->linewidth;
+ int linecap = s->stroke->linecap;
+
+ float dx = b.x - a.x;
+ float dy = b.y - a.y;
+
+ float scale = linewidth / sqrt(dx * dx + dy * dy);
+ float dlx = dy * scale;
+ float dly = -dx * scale;
+
+ if (linecap == BUTT)
+ return line(s, b.x - dlx, b.y - dly, b.x + dlx, b.y + dly);
+
+ if (linecap == ROUND)
+ {
+ int i;
+ int n = ceil(M_PI / (2.0 * M_SQRT2 * sqrt(flatness / linewidth)));
+ float ox = b.x - dlx;
+ float oy = b.y - dly;
+ for (i = 1; i < n; i++)
+ {
+ float theta = M_PI * i / n;
+ float cth = cos(theta);
+ float sth = sin(theta);
+ float nx = b.x - dlx * cth - dly * sth;
+ float ny = b.y - dly * cth + dlx * sth;
+ error = line(s, ox, oy, nx, ny);
+ if (error) return error;
+ ox = nx;
+ oy = ny;
+ }
+ error = line(s, ox, oy, b.x + dlx, b.y + dly);
+ if (error) return error;
+ }
+
+ if (linecap == SQUARE)
+ {
+ error = line(s, b.x - dlx, b.y - dly,
+ b.x - dlx - dly,
+ b.y - dly + dlx);
+ if (error) return error;
+ error = line(s, b.x - dlx - dly,
+ b.y - dly + dlx,
+ b.x + dlx - dly,
+ b.y + dly + dlx);
+ if (error) return error;
+ error = line(s, b.x + dlx - dly,
+ b.y + dly + dlx,
+ b.x + dlx, b.y + dly);
+ if (error) return error;
+ }
+
+ return nil;
+}
+
+static fz_error *
+linedot(struct sctx *s, fz_point a)
+{
+ fz_error *error;
+ float flatness = s->flatness;
+ float linewidth = s->stroke->linewidth;
+ int n = ceil(M_PI / (M_SQRT2 * sqrt(flatness / linewidth)));
+ float ox = a.x - linewidth;
+ float oy = a.y;
+ int i;
+ for (i = 1; i < n; i++)
+ {
+ float theta = M_PI * 2 * i / n;
+ float cth = cos(theta);
+ float sth = sin(theta);
+ float nx = a.x - cth * linewidth;
+ float ny = a.y + sth * linewidth;
+ error = line(s, ox, oy, nx, ny);
+ if (error) return error;
+ ox = nx;
+ oy = ny;
+ }
+ error = line(s, ox, oy, a.x - linewidth, a.y);
+ if (error) return error;
+ return nil;
+}
+
+static fz_error *
+strokeflush(struct sctx *s)
+{
+ fz_error *error;
+
+ if (s->sn == 2)
+ {
+ error = linecap(s, s->beg[1], s->beg[0]);
+ if (error) return error;
+ error = linecap(s, s->seg[0], s->seg[1]);
+ if (error) return error;
+ }
+ else if (s->dot)
+ {
+ error = linedot(s, s->beg[0]);
+ if (error) return error;
+ }
+
+ s->dot = 0;
+
+ return nil;
+}
+
+static fz_error *
+strokemoveto(struct sctx *s, fz_point cur)
+{
+ fz_error *error;
+
+ error = strokeflush(s);
+ if (error) return error;
+
+ s->seg[0] = cur;
+ s->beg[0] = cur;
+ s->sn = 1;
+ s->bn = 1;
+
+ return nil;
+}
+
+static fz_error *
+strokelineto(struct sctx *s, fz_point cur)
+{
+ fz_error *error;
+
+ float dx = cur.x - s->seg[s->sn-1].x;
+ float dy = cur.y - s->seg[s->sn-1].y;
+
+ if (dx * dx + dy * dy < s->flatness * s->flatness * 0.25)
+ {
+ s->dot = 1;
+ return nil;
+ }
+
+ error = linestroke(s, s->seg[s->sn-1], cur);
+ if (error) return error;
+
+ if (s->sn == 2)
+ {
+ error = linejoin(s, s->seg[0], s->seg[1], cur);
+ if (error) return error;
+
+ s->seg[0] = s->seg[1];
+ s->seg[1] = cur;
+ }
+
+ if (s->sn == 1)
+ s->seg[s->sn++] = cur;
+ if (s->bn == 1)
+ s->beg[s->bn++] = cur;
+
+ return nil;
+}
+
+static fz_error *
+strokeclosepath(struct sctx *s)
+{
+ fz_error *error;
+
+ if (s->sn == 2)
+ {
+ error = strokelineto(s, s->beg[0]);
+ if (error) return error;
+
+ if (s->seg[1].x == s->beg[0].x && s->seg[1].y == s->beg[0].y)
+ error = linejoin(s, s->seg[0], s->beg[0], s->beg[1]);
+ else
+ error = linejoin(s, s->seg[1], s->beg[0], s->beg[1]);
+ if (error) return error;
+ }
+
+ else if (s->dot)
+ {
+ error = linedot(s, s->beg[0]);
+ if (error) return error;
+ }
+
+ s->bn = 0;
+ s->sn = 0;
+ s->dot = 0;
+
+ return nil;
+}
+
+static fz_error *
+strokebezier(struct sctx *s,
+ float xa, float ya,
+ float xb, float yb,
+ float xc, float yc,
+ float xd, float yd)
+{
+ fz_error *error;
+ float dmax;
+ float xab, yab;
+ float xbc, ybc;
+ float xcd, ycd;
+ float xabc, yabc;
+ float xbcd, ybcd;
+ float xabcd, yabcd;
+
+ /* termination check */
+ dmax = ABS(xa - xb);
+ dmax = MAX(dmax, ABS(ya - yb));
+ dmax = MAX(dmax, ABS(xd - xc));
+ dmax = MAX(dmax, ABS(yd - yc));
+ if (dmax < s->flatness) {
+ fz_point p;
+ p.x = xd;
+ p.y = yd;
+ return strokelineto(s, p);
+ }
+
+ xab = xa + xb;
+ yab = ya + yb;
+ xbc = xb + xc;
+ ybc = yb + yc;
+ xcd = xc + xd;
+ ycd = yc + yd;
+
+ xabc = xab + xbc;
+ yabc = yab + ybc;
+ xbcd = xbc + xcd;
+ ybcd = ybc + ycd;
+
+ xabcd = xabc + xbcd;
+ yabcd = yabc + ybcd;
+
+ xab *= 0.5f; yab *= 0.5f;
+ xbc *= 0.5f; ybc *= 0.5f;
+ xcd *= 0.5f; ycd *= 0.5f;
+
+ xabc *= 0.25f; yabc *= 0.25f;
+ xbcd *= 0.25f; ybcd *= 0.25f;
+
+ xabcd *= 0.125f; yabcd *= 0.125f;
+
+ error = strokebezier(s, xa, ya, xab, yab, xabc, yabc, xabcd, yabcd);
+ if (error)
+ return error;
+
+ return strokebezier(s, xabcd, yabcd, xbcd, ybcd, xcd, ycd, xd, yd);
+}
+
+fz_error *
+fz_strokepath(fz_gel *gel, fz_path *path, fz_matrix ctm, float flatness)
+{
+ fz_error *error;
+ struct sctx s;
+ fz_point p0, p1, p2, p3;
+ int i;
+
+ s.gel = gel;
+ s.ctm = &ctm;
+ s.flatness = flatness;
+
+ s.stroke = path->stroke;
+ s.sn = 0;
+ s.bn = 0;
+ s.dot = 0;
+
+ i = 0;
+
+ while (i < path->len)
+ {
+ switch (path->els[i++].k)
+ {
+ case FZ_MOVETO:
+ p1.x = path->els[i++].v;
+ p1.y = path->els[i++].v;
+ error = strokemoveto(&s, p1);
+ if (error)
+ return error;
+ p0 = p1;
+ break;
+
+ case FZ_LINETO:
+ p1.x = path->els[i++].v;
+ p1.y = path->els[i++].v;
+ error = strokelineto(&s, p1);
+ if (error)
+ return error;
+ p0 = p1;
+ break;
+
+ case FZ_CURVETO:
+ p1.x = path->els[i++].v;
+ p1.y = path->els[i++].v;
+ p2.x = path->els[i++].v;
+ p2.y = path->els[i++].v;
+ p3.x = path->els[i++].v;
+ p3.y = path->els[i++].v;
+ error = strokebezier(&s, p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
+ if (error)
+ return error;
+ p0 = p3;
+ break;
+
+ case FZ_CLOSEPATH:
+ error = strokeclosepath(&s);
+ if (error)
+ return error;
+ break;
+ }
+ }
+
+ return strokeflush(&s);
+}
+
+static fz_error *
+dashmoveto(struct sctx *s, fz_point a)
+{
+ s->toggle = 1;
+ s->offset = 0;
+ s->phase = s->dash->phase;
+
+ while (s->phase >= s->dash->array[s->offset])
+ {
+ s->toggle = !s->toggle;
+ s->phase -= s->dash->array[s->offset];
+ s->offset ++;
+ if (s->offset == s->dash->len)
+ s->offset = 0;
+ }
+
+ s->cur = a;
+
+ if (s->toggle)
+ return strokemoveto(s, a);
+
+ return nil;
+}
+
+static fz_error *
+dashlineto(struct sctx *s, fz_point b)
+{
+ fz_error *error;
+ float dx, dy;
+ float total, used, ratio;
+ fz_point a;
+ fz_point m;
+
+ a = s->cur;
+ dx = b.x - a.x;
+ dy = b.y - a.y;
+ total = sqrt(dx * dx + dy * dy);
+ used = 0;
+
+ while (total - used > s->dash->array[s->offset] - s->phase)
+ {
+ used += s->dash->array[s->offset] - s->phase;
+ ratio = used / total;
+ m.x = a.x + ratio * dx;
+ m.y = a.y + ratio * dy;
+
+ if (s->toggle)
+ error = strokelineto(s, m);
+ else
+ error = strokemoveto(s, m);
+ if (error)
+ return error;
+
+ s->toggle = !s->toggle;
+ s->phase = 0;
+ s->offset ++;
+ if (s->offset == s->dash->len)
+ s->offset = 0;
+ }
+
+ s->phase += total - used;
+
+ s->cur = b;
+
+ if (s->toggle)
+ return strokelineto(s, b);
+
+ return nil;
+}
+
+static fz_error *
+dashbezier(struct sctx *s,
+ float xa, float ya,
+ float xb, float yb,
+ float xc, float yc,
+ float xd, float yd)
+{
+ fz_error *error;
+ float dmax;
+ float xab, yab;
+ float xbc, ybc;
+ float xcd, ycd;
+ float xabc, yabc;
+ float xbcd, ybcd;
+ float xabcd, yabcd;
+
+ /* termination check */
+ dmax = ABS(xa - xb);
+ dmax = MAX(dmax, ABS(ya - yb));
+ dmax = MAX(dmax, ABS(xd - xc));
+ dmax = MAX(dmax, ABS(yd - yc));
+ if (dmax < s->flatness) {
+ fz_point p;
+ p.x = xd;
+ p.y = yd;
+ return dashlineto(s, p);
+ }
+
+ xab = xa + xb;
+ yab = ya + yb;
+ xbc = xb + xc;
+ ybc = yb + yc;
+ xcd = xc + xd;
+ ycd = yc + yd;
+
+ xabc = xab + xbc;
+ yabc = yab + ybc;
+ xbcd = xbc + xcd;
+ ybcd = ybc + ycd;
+
+ xabcd = xabc + xbcd;
+ yabcd = yabc + ybcd;
+
+ xab *= 0.5f; yab *= 0.5f;
+ xbc *= 0.5f; ybc *= 0.5f;
+ xcd *= 0.5f; ycd *= 0.5f;
+
+ xabc *= 0.25f; yabc *= 0.25f;
+ xbcd *= 0.25f; ybcd *= 0.25f;
+
+ xabcd *= 0.125f; yabcd *= 0.125f;
+
+ error = dashbezier(s, xa, ya, xab, yab, xabc, yabc, xabcd, yabcd);
+ if (error) return error;
+ return dashbezier(s, xabcd, yabcd, xbcd, ybcd, xcd, ycd, xd, yd);
+}
+
+fz_error *
+fz_dashpath(fz_gel *gel, fz_path *path, fz_matrix ctm, float flatness)
+{
+ fz_error *error;
+ struct sctx s;
+ fz_point p0, p1, p2, p3, beg;
+ int i;
+
+ s.gel = gel;
+ s.ctm = &ctm;
+ s.flatness = flatness;
+
+ s.stroke = path->stroke;
+ s.sn = 0;
+ s.bn = 0;
+ s.dot = 0;
+
+ s.dash = path->dash;
+ s.toggle = 0;
+ s.offset = 0;
+ s.phase = 0;
+
+ i = 0;
+
+ while (i < path->len)
+ {
+ switch (path->els[i++].k)
+ {
+ case FZ_MOVETO:
+ p1.x = path->els[i++].v;
+ p1.y = path->els[i++].v;
+ error = dashmoveto(&s, p1);
+ if (error)
+ return error;
+ beg = p0 = p1;
+ break;
+
+ case FZ_LINETO:
+ p1.x = path->els[i++].v;
+ p1.y = path->els[i++].v;
+ error = dashlineto(&s, p1);
+ if (error)
+ return error;
+ p0 = p1;
+ break;
+
+ case FZ_CURVETO:
+ p1.x = path->els[i++].v;
+ p1.y = path->els[i++].v;
+ p2.x = path->els[i++].v;
+ p2.y = path->els[i++].v;
+ p3.x = path->els[i++].v;
+ p3.y = path->els[i++].v;
+ error = dashbezier(&s, p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
+ if (error)
+ return error;
+ p0 = p3;
+ break;
+
+ case FZ_CLOSEPATH:
+ error = dashlineto(&s, beg);
+ if (error)
+ return error;
+ break;
+ }
+ }
+
+ return strokeflush(&s);
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-20 10:57:17 +0000