Initial import

16 files changed, 1908 insertions, 0 deletions

diff --git a/tree/blend.c b/tree/blend.c
new file mode 100644
index 00000000..d2154240
--- /dev/null
+++ b/tree/blend.c
@@ -0,0 +1,53 @@
+#include <fitz.h>
+
+fz_error *
+fz_newblend(fz_node **nodep, fz_blendkind b, int k, int i)
+{
+	fz_blend *node;
+
+	node = fz_malloc(sizeof (fz_blend));
+	if (!node)
+		return fz_outofmem;
+	*nodep = (fz_node*)node;
+
+	fz_initnode((fz_node*)node, FZ_NBLEND);
+	node->child = nil;
+	node->mode = b;
+	node->knockout = k;
+	node->isolated = i;
+
+	return nil;
+}
+
+void
+fz_freeblend(fz_blend *node)
+{
+	if (node->child)
+		fz_freenode(node->child);
+	fz_free(node);
+}
+
+fz_rect
+fz_boundblend(fz_blend *node, fz_matrix ctm)
+{
+	fz_node *child;
+	fz_rect bbox;
+	fz_rect r;
+
+	bbox = FZ_INFRECT;
+
+	for (child = node->child; child; child = child->next)
+	{
+		r = fz_boundnode(child, ctm);
+		if (r.max.x >= r.min.x)
+		{
+			if (bbox.max.x >= bbox.min.x)
+				bbox = fz_mergerects(r, bbox);
+			else
+				bbox = r;
+		}   
+	}
+
+	return bbox;
+}
+
diff --git a/tree/cache.c b/tree/cache.c
new file mode 100644
index 00000000..f4544844
--- /dev/null
+++ b/tree/cache.c
@@ -0,0 +1,98 @@
+#include <fitz.h>
+
+static int
+hash(fz_cachekey *k)
+{
+	int h;
+	int i;
+
+	h = (int)k->tree ^ (int)k->node ^ k->tag;
+
+	/* http://www.cs.yorku.ca/~oz/hash.html -- sdbm */
+	for (i = 0; i < k->len; i++)
+		h = k->key[i] + (h << 6) + (h << 16) - h;
+
+	return h;
+}
+
+static int
+equal(fz_cachekey *a, fz_cachekey *b)
+{
+	if (a->tree != b->tree) return 0;
+	if (a->node != b->node) return 0;
+	if (a->tag != b->tag) return 0;
+	if (a->len != b->len) return 0;
+	return memcmp(a->key, b->key, a->len) == 0;
+}
+
+fz_cache *
+fz_newcache(int maxentries, int maxdatasize)
+{
+	fz_cache *cache;
+	int i;
+
+	cache = fz_malloc(sizeof(fz_cache));
+	if (!cache) return nil;
+
+	cache->maxsize = maxdatasize;
+	cache->cursize = 0;
+	cache->len = maxentries;
+	cache->table = fz_malloc(sizeof(fz_cachebucket) * maxentries);
+	if (!cache->table) {
+		fz_free(cache);
+		return nil;
+	}
+
+	for (i = 0; i < cache->len; i++) {
+		cache->table[i].val = nil;
+	}
+
+	return cache;
+}
+
+void *
+fz_findincache(fz_cache *cache, fz_cachekey *key)
+{
+	int h;
+	int i;
+
+	h = hash(key); 
+
+	i = h % cache->len;
+	if (equal(key, &cache->table[i].key))
+		return cache->table[i].val;
+	return nil;
+}
+
+int
+fz_insertincache(fz_cache *cache, fz_cachekey *key, void *data, int size)
+{
+	int h;
+	int i;
+
+	h = hash(key);
+	i = h % cache->len;
+
+	if (cache->table[i].val)
+		fz_free(cache->table[i].val);
+	cache->table[i].key = *key;
+
+	return FZ_OKAY;
+}
+
+int
+fz_evictfromcache(fz_cache *cache, fz_cachekey *key)
+{
+	/* TODO */
+	return FZ_OKAY;
+}
+
+void
+fz_freecache(fz_cache *cache)
+{
+	/* FIXME evict everything from cache first? */
+	if (cache->table)
+		fz_free(cache->table);
+	fz_free(cache);
+}
+
diff --git a/tree/cmap.c b/tree/cmap.c
new file mode 100644
index 00000000..21b08274
--- /dev/null
+++ b/tree/cmap.c
@@ -0,0 +1,452 @@
+#include <fitz.h>
+
+typedef struct fz_range_s fz_range;
+
+enum { MAXCODESPACE = 10 };
+enum { SINGLE, RANGE, LOOKUP };
+
+struct fz_range_s
+{
+	int low;
+	int high;
+	int flag;
+	int offset;
+};
+
+struct fz_cmap_s
+{
+	char cmapname[32];
+
+	char usecmapname[32];
+	fz_cmap *usecmap;
+
+	int wmode;
+
+	int ncspace;
+	struct {
+		int n;
+		unsigned char lo[4];
+		unsigned char hi[4];
+	} cspace[MAXCODESPACE];
+
+	int rlen, rcap;
+	fz_range *ranges;
+
+	int tlen, tcap;
+	int *lookup;
+};
+
+fz_error *
+fz_newcmap(fz_cmap **cmapp)
+{
+	fz_cmap *cmap;
+
+	cmap = *cmapp = fz_malloc(sizeof(fz_cmap));
+	if (!cmap)
+		return fz_outofmem;
+
+	strcpy(cmap->cmapname, "");
+
+	strcpy(cmap->usecmapname, "");
+	cmap->usecmap = nil;
+
+	cmap->wmode = 0;
+
+	cmap->ncspace = 0;
+
+	cmap->rlen = 0;
+	cmap->rcap = 0;
+	cmap->ranges = nil;
+
+	cmap->tlen = 0;
+	cmap->tcap = 0;
+	cmap->lookup = nil;
+
+	return nil;
+}
+
+void
+fz_freecmap(fz_cmap *cmap)
+{
+	if (cmap->usecmap)
+		fz_freecmap(cmap->usecmap);
+	fz_free(cmap->ranges);
+	fz_free(cmap->lookup);
+	fz_free(cmap);
+}
+
+char *
+fz_getcmapname(fz_cmap *cmap)
+{
+	if (cmap->cmapname[0])
+		return cmap->cmapname;
+	return nil;
+}
+
+void
+fz_setcmapname(fz_cmap *cmap, char *cmapname)
+{
+	strlcpy(cmap->cmapname, cmapname, sizeof cmap->cmapname);
+}
+
+char *
+fz_getusecmapname(fz_cmap *cmap)
+{
+	if (cmap->usecmapname[0])
+		return cmap->usecmapname;
+	return nil;
+}
+
+void
+fz_setusecmapname(fz_cmap *cmap, char *usecmap)
+{
+	strlcpy(cmap->usecmapname, usecmap, sizeof cmap->usecmapname);
+}
+
+fz_cmap *
+fz_getusecmap(fz_cmap *cmap)
+{
+	return cmap->usecmap;
+}
+
+void
+fz_setusecmap(fz_cmap *cmap, fz_cmap *usecmap)
+{
+	int i;
+
+	cmap->usecmap = usecmap;
+
+	if (cmap->ncspace == 0)
+	{
+		cmap->ncspace = usecmap->ncspace;
+		for (i = 0; i < usecmap->ncspace; i++)
+			cmap->cspace[i] = usecmap->cspace[i];
+	}
+}
+
+void
+fz_setwmode(fz_cmap *cmap, int wmode)
+{
+	cmap->wmode = wmode;
+}
+
+int
+fz_getwmode(fz_cmap *cmap)
+{
+	return cmap->wmode;
+}
+
+fz_error *
+fz_addcodespacerange(fz_cmap *cmap, unsigned lo, unsigned hi, int n)
+{
+	int i;
+
+	if (cmap->ncspace + 1 == MAXCODESPACE)
+		return fz_throw("rangelimit: too many code space ranges");
+
+	cmap->cspace[cmap->ncspace].n = n;
+
+	for (i = 0; i < n; i++)
+	{
+		int o = (n - i - 1) * 8;
+		cmap->cspace[cmap->ncspace].lo[i] = (lo >> o) & 0xFF;
+		cmap->cspace[cmap->ncspace].hi[i] = (hi >> o) & 0xFF;
+	}
+
+	cmap->ncspace ++;
+
+	return nil;
+}
+
+fz_error *
+fz_addcidrange(fz_cmap *cmap, int low, int high, int offset)
+{
+	if (cmap->rlen + 1 > cmap->rcap)
+	{
+		fz_range *newranges;
+		int newcap = cmap->rcap == 0 ? 256 : cmap->rcap * 2;
+		newranges = fz_realloc(cmap->ranges, newcap * sizeof(fz_range));
+		if (!newranges)
+			return fz_outofmem;
+		cmap->rcap = newcap;
+		cmap->ranges = newranges;
+	}
+
+	cmap->ranges[cmap->rlen].low = low;
+	cmap->ranges[cmap->rlen].high = high;
+	cmap->ranges[cmap->rlen].flag = high - low == 0 ? SINGLE : RANGE;
+	cmap->ranges[cmap->rlen].offset = offset;
+	cmap->rlen ++;
+
+	return nil;
+}
+
+static fz_error *
+addlookup(fz_cmap *cmap, int value)
+{
+	if (cmap->tlen + 1 > cmap->tcap)
+	{
+		int newcap = cmap->tcap == 0 ? 256 : cmap->tcap * 2;
+		int *newlookup = fz_realloc(cmap->lookup, newcap * sizeof(int));
+		if (!newlookup)
+			return fz_outofmem;
+		cmap->tcap = newcap;
+		cmap->lookup = newlookup;
+	}
+
+	cmap->lookup[cmap->tlen++] = value;
+
+	return nil;
+}
+
+static int compare(const void *va, const void *vb)
+{
+	return ((const fz_range*)va)->low - ((const fz_range*)vb)->low;
+}
+
+fz_error *
+fz_endcidrange(fz_cmap *cmap)
+{
+	fz_error *err;
+	fz_range *newranges;
+	int *newlookup;
+	fz_range *a;			/* last written range on output */
+	fz_range *b;			/* current range examined on input */
+
+	qsort(cmap->ranges, cmap->rlen, sizeof(fz_range), compare);
+
+	a = cmap->ranges;
+	b = cmap->ranges + 1;
+
+	while (b < cmap->ranges + cmap->rlen)
+	{
+		/* input contiguous */
+		if (a->high + 1 == b->low)
+		{
+			/* output contiguous */
+			if (a->high - a->low + a->offset + 1 == b->offset)
+			{
+				/* SR -> R and SS -> R and RR -> R and RS -> R */
+				if (a->flag == SINGLE || a->flag == RANGE)
+				{
+					a->flag = RANGE;
+					a->high = b->high;
+				}
+
+				/* LS -> L */
+				else if (a->flag == LOOKUP && b->flag == SINGLE)
+				{
+					a->high = b->high;
+					err = addlookup(cmap, b->offset);
+					if (err)
+						return err;
+				}
+
+				/* LR -> LR */
+				else if (a->flag == LOOKUP && b->flag == RANGE)
+				{
+					*(++a) = *b;
+				}
+			}
+
+			/* output separated */
+			else
+			{
+				/* SS -> L */
+				if (a->flag == SINGLE && b->flag == SINGLE)
+				{
+					a->flag = LOOKUP;
+					a->high = b->high;
+
+					err = addlookup(cmap, a->offset);
+					if (err)
+						return err;
+
+					err = addlookup(cmap, b->offset);
+					if (err)
+						return err;
+
+					a->offset = cmap->tlen - 2;
+				}
+
+				/* LS -> L */
+				else if (a->flag == LOOKUP && b->flag == SINGLE)
+				{
+					a->high = b->high;
+					err = addlookup(cmap, b->offset);
+					if (err)
+						return err;
+				}
+
+				/* XX -> XX */
+				else
+				{
+					*(++a) = *b;
+				}
+			}
+		}
+
+		/* input separated: XX -> XX */
+		else
+		{
+			*(++a) = *b;
+		}
+
+		b ++;
+	}
+
+	cmap->rlen = a - cmap->ranges + 1;
+
+	assert(cmap->rlen > 0);
+
+	newranges = fz_realloc(cmap->ranges, cmap->rlen * sizeof(fz_range));
+	if (!newranges)
+		return fz_outofmem;
+	cmap->rcap = cmap->rlen;
+	cmap->ranges = newranges;
+
+	if (cmap->tlen)
+	{
+		newlookup = fz_realloc(cmap->lookup, cmap->tlen * sizeof(int));
+		if (!newlookup)
+			return fz_outofmem;
+		cmap->tcap = cmap->tlen;
+		cmap->lookup = newlookup;
+	}
+
+	return nil;
+}
+
+fz_error *
+fz_setcidlookup(fz_cmap *cmap, int map[256])
+{
+	int i;
+
+	cmap->rlen = cmap->rcap = 1;
+	cmap->ranges = fz_malloc(sizeof (fz_range));
+	if (!cmap->ranges) {
+		return fz_outofmem;
+	}
+
+	cmap->tlen = cmap->tcap = 256;
+	cmap->lookup = fz_malloc(sizeof (int) * 256);
+	if (!cmap->lookup) {
+		fz_free(cmap->ranges);
+		return fz_outofmem;
+	}
+
+	cmap->ranges[0].low = 0;
+	cmap->ranges[0].high = 255;
+	cmap->ranges[0].flag = LOOKUP;
+	cmap->ranges[0].offset = 0;
+
+	for (i = 0; i < 256; i++)
+		cmap->lookup[i] = map[i];
+
+	return nil;
+}
+
+int
+fz_lookupcid(fz_cmap *cmap, int cpt)
+{
+	int l = 0;
+	int r = cmap->rlen - 1;
+	int m;
+
+	while (l <= r)
+	{
+		m = (l + r) >> 1;
+		if (cpt < cmap->ranges[m].low)
+			r = m - 1;
+		else if (cpt > cmap->ranges[m].high)
+			l = m + 1;
+		else
+		{
+			int i = cpt - cmap->ranges[m].low + cmap->ranges[m].offset;
+			if (cmap->ranges[m].flag == LOOKUP)
+				return cmap->lookup[i];
+			return i;
+		}
+	}
+
+	if (cmap->usecmap)
+		return fz_lookupcid(cmap->usecmap, cpt);
+
+	return -1;
+}
+
+char *
+fz_decodecpt(fz_cmap *cmap, unsigned char *buf, int *cpt)
+{
+	int i, k;
+
+	for (k = 0; k < cmap->ncspace; k++)
+	{
+		unsigned char *lo = cmap->cspace[k].lo;
+		unsigned char *hi = cmap->cspace[k].hi;
+		int n = cmap->cspace[k].n;
+		int c = 0;
+
+		for (i = 0; i < n; i++)
+		{
+			if (lo[i] <= buf[i] && buf[i] <= hi[i])
+				c = (c << 8) | buf[i];
+			else
+				break;
+		}
+
+		if (i == n) {
+			*cpt = c;
+			return buf + n;
+		}
+	}
+
+	*cpt = 0;
+	return buf + 1;
+}
+
+void
+fz_debugcmap(fz_cmap *cmap)
+{
+	int i, k;
+
+	printf("cmap $%p /%s {\n", cmap, cmap->cmapname);
+
+	if (cmap->usecmapname[0])
+		printf("  usecmap /%s\n", cmap->usecmapname);
+	if (cmap->usecmap)
+		printf("  usecmap $%p\n", cmap->usecmap);
+
+	printf("  wmode %d\n", cmap->wmode);
+
+	printf("  codespaces {\n");
+	for (i = 0; i < cmap->ncspace; i++)
+	{
+		printf("    <");
+		for (k = 0; k < cmap->cspace[i].n; k++)
+			printf("%02x", cmap->cspace[i].lo[k]);
+		printf("> <");
+		for (k = 0; k < cmap->cspace[i].n; k++)
+			printf("%02x", cmap->cspace[i].hi[k]);
+		printf(">\n");
+	}
+	printf("  }\n");
+
+	printf("  ranges (%d,%d) {\n", cmap->rlen, cmap->tlen);
+	for (i = 0; i < cmap->rlen; i++)
+	{
+		fz_range *r = &cmap->ranges[i];
+		printf("    <%04x> <%04x> ", r->low, r->high);
+		if (r->flag == LOOKUP)
+		{
+			printf("[ ");
+			for (k = 0; k < r->high - r->low + 1; k++)
+				printf("%d ", cmap->lookup[r->offset + k]);
+			printf("]\n");
+		}
+		else
+			printf("%d\n", r->offset);
+	}
+	printf("  }\n}\n");
+}
+
diff --git a/tree/debug.c b/tree/debug.c
new file mode 100644
index 00000000..f5012c60
--- /dev/null
+++ b/tree/debug.c
@@ -0,0 +1,177 @@
+#include <fitz.h>
+
+static void indent(int level)
+{
+	while (level--)
+		putchar(' ');
+}
+
+static void lispnode(fz_node *node, int level);
+
+static void lispmeta(fz_meta *node, int level)
+{
+	fz_node *child;
+	indent(level);
+	printf("(meta ");
+	fz_fprintcobj(stdout, node->info);
+	printf("\n");
+	for (child = node->child; child; child = child->next)
+		lispnode(child, level + 1);
+	indent(level);
+	printf(")\n");
+}
+
+static void lispover(fz_over *node, int level)
+{
+	fz_node *child;
+	indent(level);
+	printf("(over\n");
+	for (child = node->child; child; child = child->next)
+		lispnode(child, level + 1);
+	indent(level);
+	printf(")\n");
+}
+
+static void lispmask(fz_mask *node, int level)
+{
+	fz_node *child;
+	indent(level);
+	printf("(mask\n");
+	for (child = node->child; child; child = child->next)
+		lispnode(child, level + 1);
+	indent(level);
+	printf(")\n");
+}
+
+static void lispblend(fz_blend *node, int level)
+{
+	fz_node *child;
+	indent(level);
+	printf("(blend-%d\n", node->mode);
+	for (child = node->child; child; child = child->next)
+		lispnode(child, level + 1);
+	indent(level);
+	printf(")\n");
+}
+
+static void lisptransform(fz_transform *node, int level)
+{
+	indent(level);
+	printf("(transform %g %g %g %g %g %g\n",
+		node->m.a, node->m.b,
+		node->m.c, node->m.d,
+		node->m.e, node->m.f);
+	lispnode(node->child, level + 1);
+	indent(level);
+	printf(")\n");
+}
+
+static void lispsolid(fz_solid *node, int level)
+{
+	indent(level);
+	printf("(solid %g %g %g)\n", node->r, node->g, node->b);
+}
+
+static void lispform(fz_form *node, int level)
+{
+	indent(level);
+	printf("(form %p)\n", node->tree);
+}
+
+static void lisppath(fz_path *node, int level)
+{
+	int i;
+
+	indent(level);
+
+	if (node->paint == FZ_STROKE)
+	{
+		printf("(path 'stroke %d %d %g %g ",
+			node->stroke->linecap,
+			node->stroke->linejoin,
+			node->stroke->linewidth,
+			node->stroke->miterlimit);
+		if (node->dash)
+		{
+			printf("%g '( ", node->dash->phase);
+			for (i = 0; i < node->dash->len; i++)
+				printf("%g ", node->dash->array[i]);
+			printf(")");
+		}
+		else
+			printf("0 '()");
+	}
+	else
+	{
+		printf("(path '%s", node->paint == FZ_FILL ? "fill" : "eofill");
+	}
+
+	printf("\n");
+	fz_debugpath(node);
+
+	indent(level);
+	printf(")\n");
+}
+
+static void lisptext(fz_text *node, int level)
+{
+	int i;
+
+	indent(level);
+	printf("(text %s [%g %g %g %g]\n", node->font->name,
+		node->trm.a, node->trm.b, node->trm.c, node->trm.d);
+
+	for (i = 0; i < node->len; i++)
+	{
+		indent(level + 1);
+		printf("(g %d %g %g)\n", node->els[i].g, node->els[i].x, node->els[i].y);
+	}
+
+	indent(level);
+	printf(")\n");
+}
+
+static void lispimage(fz_image *node, int level)
+{
+	indent(level);
+	printf("(image %d %d %d %d '", node->w, node->h, node->n, node->bpc);
+	switch (node->cs)
+	{
+	case FZ_CSGRAY: printf("gray"); break;
+	case FZ_CSRGB: printf("rgb"); break;
+	case FZ_CSCMYK: printf("cmyk"); break;
+	default: printf("unknown"); break;
+	}
+	printf(")\n");
+}
+
+static void lispnode(fz_node *node, int level)
+{
+	if (!node)
+	{
+		indent(level);
+		printf("(nil)\n");
+		return;
+	}
+
+	switch (node->kind)
+	{
+	case FZ_NMETA: lispmeta((fz_meta*)node, level); break;
+	case FZ_NOVER: lispover((fz_over*)node, level); break;
+	case FZ_NMASK: lispmask((fz_mask*)node, level); break;
+	case FZ_NBLEND: lispblend((fz_blend*)node, level); break;
+	case FZ_NTRANSFORM: lisptransform((fz_transform*)node, level); break;
+	case FZ_NSOLID: lispsolid((fz_solid*)node, level); break;
+	case FZ_NPATH: lisppath((fz_path*)node, level); break;
+	case FZ_NTEXT: lisptext((fz_text*)node, level); break;
+	case FZ_NIMAGE: lispimage((fz_image*)node, level); break;
+	case FZ_NFORM: lispform((fz_form*)node, level); break;
+	}
+}
+
+void
+fz_debugtree(fz_tree *tree)
+{
+	lispnode(tree->root, 0);
+}
+
diff --git a/tree/font.c b/tree/font.c
new file mode 100644
index 00000000..9ddbad04
--- /dev/null
+++ b/tree/font.c
@@ -0,0 +1,275 @@
+#include <fitz.h>
+
+void
+fz_initfont(fz_font *font, char *name)
+{
+	strlcpy(font->name, name, sizeof font->name);
+
+	font->wmode = 0;
+
+	font->bbox.min.x = 0;
+	font->bbox.min.y = 0;
+	font->bbox.max.x = 1000;
+	font->bbox.max.y = 1000;
+
+	font->hmtxcap = 0;
+	font->vmtxcap = 0;
+	font->nhmtx = 0;
+	font->nvmtx = 0;
+	font->hmtx = nil;
+	font->vmtx = nil;
+
+	font->dhmtx.c = 0x0000;
+	font->dhmtx.w = 0;
+
+	font->dvmtx.c = 0x0000;
+	font->dvmtx.x = 0;
+	font->dvmtx.y = 880;
+	font->dvmtx.w = -1000;
+}
+
+void
+fz_setfontwmode(fz_font *font, int wmode)
+{
+	font->wmode = wmode;
+}
+
+void
+fz_setfontbbox(fz_font *font, int xmin, int ymin, int xmax, int ymax)
+{
+    font->bbox.min.x = xmin;
+    font->bbox.min.y = ymin;
+    font->bbox.max.x = xmax;
+    font->bbox.max.y = ymax;
+}
+
+void
+fz_setdefaulthmtx(fz_font *font, int w)
+{
+	font->dhmtx.w = w;
+}
+
+void
+fz_setdefaultvmtx(fz_font *font, int y, int w)
+{
+	font->dvmtx.y = y;
+	font->dvmtx.w = w;
+}
+
+fz_error *
+fz_addhmtx(fz_font *font, int c, int w)
+{
+	int newcap;
+	fz_hmtx *newmtx;
+
+	if (font->nhmtx + 1 >= font->hmtxcap)
+	{
+		newcap = font->hmtxcap + 16;
+		newmtx = fz_realloc(font->hmtx, sizeof(fz_hmtx) * newcap);
+		if (!newmtx)
+			return fz_outofmem;
+		font->hmtxcap = newcap;
+		font->hmtx = newmtx;
+	}
+
+	font->hmtx[font->nhmtx].c = c;
+	font->hmtx[font->nhmtx].w = w;
+	font->nhmtx++;
+
+	return nil;
+}
+
+fz_error *
+fz_addvmtx(fz_font *font, int c, int x, int y, int w)
+{
+	int newcap;
+	fz_vmtx *newmtx;
+
+	if (font->nvmtx + 1 >= font->vmtxcap)
+	{
+		newcap = font->vmtxcap + 16;
+		newmtx = fz_realloc(font->vmtx, sizeof(fz_vmtx) * newcap);
+		if (!newmtx)
+			return fz_outofmem;
+		font->vmtxcap = newcap;
+		font->vmtx = newmtx;
+	}
+
+	font->vmtx[font->nvmtx].c = c;
+	font->vmtx[font->nvmtx].x = x;
+	font->vmtx[font->nvmtx].y = y;
+	font->vmtx[font->nvmtx].w = w;
+	font->nvmtx++;
+
+	return nil;
+}
+
+static int cmph(const void *a0, const void *b0)
+{
+	fz_hmtx *a = (fz_hmtx*)a0;
+	fz_hmtx *b = (fz_hmtx*)b0;
+	return a->c - b->c;
+}
+
+static int cmpv(const void *a0, const void *b0)
+{
+	fz_vmtx *a = (fz_vmtx*)a0;
+	fz_vmtx *b = (fz_vmtx*)b0;
+	return a->c - b->c;
+}
+
+static int uniq(void *ptr, int count, int size)
+{
+	char *a = ptr;
+	char *b = ((char*)ptr) + size;
+
+	while (count--)
+	{
+		if (memcmp(a, b, sizeof(short)) != 0)
+		{
+			a += size;
+			if (a != b)
+				memcpy(a, b, size);
+		}
+		b += size;
+	}
+
+	return (a - ((char*)ptr)) / size;
+}
+
+fz_error *
+fz_endhmtx(fz_font *font)
+{
+	fz_hmtx *newmtx;
+
+	if (!font->hmtx)
+		return nil;
+
+	qsort(font->hmtx, font->nhmtx, sizeof(fz_hmtx), cmph);
+	font->nhmtx = uniq(font->hmtx, font->nhmtx, sizeof(fz_hmtx));
+
+	newmtx = fz_realloc(font->hmtx, sizeof(fz_hmtx) * font->nhmtx);
+	if (!newmtx)
+		return fz_outofmem;
+	font->hmtxcap = font->nhmtx;
+	font->hmtx = newmtx;
+
+	return nil;
+}
+
+fz_error *
+fz_endvmtx(fz_font *font)
+{
+	fz_vmtx *newmtx;
+
+	if (!font->vmtx)
+		return nil;
+
+	qsort(font->vmtx, font->nvmtx, sizeof(fz_vmtx), cmpv);
+	font->nvmtx = uniq(font->vmtx, font->nvmtx, sizeof(fz_vmtx));
+
+	newmtx = fz_realloc(font->vmtx, sizeof(fz_vmtx) * font->nvmtx);
+	if (!newmtx)
+		return fz_outofmem;
+	font->vmtxcap = font->nvmtx;
+	font->vmtx = newmtx;
+
+	return nil;
+}
+
+fz_hmtx
+fz_gethmtx(fz_font *font, int gid)
+{
+	int l = 0;
+	int r = font->nhmtx;
+	int m;
+
+	if (!font->hmtx)
+		goto notfound;
+
+	while (l <= r)
+	{
+		m = (l + r) >> 1;
+		if (gid < font->hmtx[m].c)
+			r = m - 1;
+		else if (gid > font->hmtx[m].c)
+			l = m + 1;
+		else
+			return font->hmtx[m];
+	}
+
+notfound:
+	return font->dhmtx;
+}
+
+fz_vmtx
+fz_getvmtx(fz_font *font, int gid)
+{
+	fz_hmtx h;
+	fz_vmtx v;
+	int l = 0;
+	int r = font->nvmtx;
+	int m;
+
+	if (!font->vmtx)
+		goto notfound;
+
+	while (l <= r)
+	{
+		m = (l + r) >> 1;
+		if (gid < font->vmtx[m].c)
+			r = m - 1;
+		else if (gid > font->vmtx[m].c)
+			l = m + 1;
+		else
+			return font->vmtx[m];
+	}
+
+notfound:
+	h = fz_gethmtx(font, gid);
+	v = font->dvmtx;
+	v.x = h.w / 2;
+	return v;
+}
+
+void
+fz_freefont(fz_font *font)
+{
+	if (font->free)
+		font->free(font);
+	fz_free(font->hmtx);
+	fz_free(font->vmtx);
+	fz_free(font);
+}
+
+void
+fz_debugfont(fz_font *font)
+{
+	int i;
+
+	printf("font '%s' {\n", font->name);
+	printf("  wmode %d\n", font->wmode);
+	printf("  bbox [%d %d %d %d]\n",
+		font->bbox.min.x, font->bbox.min.y,
+		font->bbox.max.x, font->bbox.max.y);
+	printf("  DW %d\n", font->dhmtx.w);
+
+	printf("  W {\n");
+	for (i = 0; i < font->nhmtx; i++)
+		printf("    <%04x> %d\n",
+			font->hmtx[i].c, font->hmtx[i].w);
+	printf("  }\n");
+
+	if (font->wmode)
+	{
+		printf("  DW2 [%d %d]\n", font->dvmtx.y, font->dvmtx.w);
+		printf("  W2 {\n");
+		for (i = 0; i < font->nvmtx; i++)
+			printf("    <%04x> %d %d %d\n", font->vmtx[i].c,
+				font->vmtx[i].x, font->vmtx[i].y, font->vmtx[i].w);
+		printf("  }\n");
+	}
+
+	printf("}\n");
+}
+
diff --git a/tree/form.c b/tree/form.c
new file mode 100644
index 00000000..dd45aad9
--- /dev/null
+++ b/tree/form.c
@@ -0,0 +1,30 @@
+#include <fitz.h>
+
+fz_error *
+fz_newform(fz_node **nodep, fz_tree *child)
+{
+	fz_form *node;
+
+	node = fz_malloc(sizeof (fz_form));
+	if (!node)
+		return fz_outofmem;
+	*nodep = (fz_node*)node;
+
+	fz_initnode((fz_node*)node, FZ_NFORM);
+	node->tree = child;
+
+	return nil;
+}
+
+void
+fz_freeform(fz_form *node)
+{
+	fz_free(node);
+}
+
+fz_rect
+fz_boundform(fz_form *node, fz_matrix ctm)
+{
+	return fz_boundtree(node->tree, ctm);
+}
+
diff --git a/tree/image.c b/tree/image.c
new file mode 100644
index 00000000..7991ded3
--- /dev/null
+++ b/tree/image.c
@@ -0,0 +1,49 @@
+#include <fitz.h>
+
+fz_error *
+fz_newimage(fz_node **nodep, int w, int h, int n, int bpc, int cs)
+{
+	fz_image *node;
+
+	node = fz_malloc(sizeof (fz_image));
+	if (!node)
+		return fz_outofmem;
+	*nodep = (fz_node*)node;
+
+	fz_initnode((fz_node*)node, FZ_NIMAGE);
+	node->w = w;
+	node->h = h;
+	node->n = n;
+	node->bpc = bpc;
+	node->cs = cs;
+	node->data = nil;
+
+	return nil;
+}
+
+void
+fz_freeimage(fz_image *node)
+{
+	fz_free(node->data);
+	fz_free(node);
+}
+
+fz_rect
+fz_boundimage(fz_image *node, fz_matrix ctm)
+{
+	fz_point ll, lr, ul, ur;
+	fz_rect r;
+
+	ll = fz_transformpoint(ctm, (fz_point){0,0});
+	lr = fz_transformpoint(ctm, (fz_point){1,0});
+	ul = fz_transformpoint(ctm, (fz_point){0,1});
+	ur = fz_transformpoint(ctm, (fz_point){1,1});
+
+	r.min.x = MIN4(ll.x, lr.x, ul.x, ur.x);
+	r.min.y = MIN4(ll.y, lr.y, ul.y, ur.y);
+	r.max.x = MAX4(ll.x, lr.x, ul.x, ur.x);
+	r.max.y = MAX4(ll.y, lr.y, ul.y, ur.y);
+
+	return r;
+}
+
diff --git a/tree/mask.c b/tree/mask.c
new file mode 100644
index 00000000..62a469ff
--- /dev/null
+++ b/tree/mask.c
@@ -0,0 +1,50 @@
+#include <fitz.h>
+
+fz_error *
+fz_newmask(fz_node **nodep)
+{
+	fz_mask *node;
+
+	node = fz_malloc(sizeof (fz_mask));
+	if (!node)
+		return fz_outofmem;
+	*nodep = (fz_node*)node;
+
+	fz_initnode((fz_node*)node, FZ_NMASK);
+	node->child = nil;
+
+	return nil;
+}
+
+void
+fz_freemask(fz_mask *node)
+{
+	if (node->child)
+		fz_freenode(node->child);
+	fz_free(node);
+}
+
+fz_rect
+fz_boundmask(fz_mask* node, fz_matrix ctm)
+{
+	fz_node *child;
+	fz_rect bbox;
+	fz_rect r;
+
+	bbox = FZ_INFRECT;
+
+	for (child = node->child; child; child = child->next)
+	{
+		r = fz_boundnode(child, ctm);
+		if (r.max.x >= r.min.x)
+		{
+			if (bbox.max.x >= bbox.min.x)
+				bbox = fz_intersectrects(r, bbox);
+			else
+				bbox = r;
+		}
+	}
+
+	return bbox;
+}
+
diff --git a/tree/meta.c b/tree/meta.c
new file mode 100644
index 00000000..4d3a2a74
--- /dev/null
+++ b/tree/meta.c
@@ -0,0 +1,37 @@
+#include <fitz.h>
+
+fz_error *
+fz_newmeta(fz_node **nodep, fz_obj *info)
+{
+	fz_meta *node;
+
+	node = fz_malloc(sizeof (fz_meta));
+	if (!node)
+		return fz_outofmem;
+	*nodep = (fz_node*)node;
+
+	fz_initnode((fz_node*)node, FZ_NMETA);
+	node->info = fz_keepobj(info);
+	node->child = nil;
+
+	return nil;
+}
+
+void
+fz_freemeta(fz_meta *node)
+{
+	if (node->child)
+		fz_freenode(node->child);
+	if (node->info)
+		fz_dropobj(node->info);
+	fz_free(node);
+}
+
+fz_rect
+fz_boundmeta(fz_meta *node, fz_matrix ctm)
+{
+	if (!node->child)
+		return FZ_INFRECT;
+	return fz_boundnode(node->child, ctm);
+}
+
diff --git a/tree/node.c b/tree/node.c
new file mode 100644
index 00000000..8b9d48cc
--- /dev/null
+++ b/tree/node.c
@@ -0,0 +1,148 @@
+#include <fitz.h>
+
+void fz_freeover(fz_over* node);
+void fz_freemask(fz_mask* node);
+void fz_freeblend(fz_blend* node);
+void fz_freetransform(fz_transform* node);
+void fz_freeform(fz_form* node);
+void fz_freesolid(fz_solid* node);
+void fz_freepath(fz_path* node);
+void fz_freetext(fz_text* node);
+void fz_freeimage(fz_image* node);
+
+fz_rect fz_boundover(fz_over* node, fz_matrix ctm);
+fz_rect fz_boundmask(fz_mask* node, fz_matrix ctm);
+fz_rect fz_boundblend(fz_blend* node, fz_matrix ctm);
+fz_rect fz_boundtransform(fz_transform* node, fz_matrix ctm);
+fz_rect fz_boundform(fz_form* node, fz_matrix ctm);
+fz_rect fz_boundsolid(fz_solid* node, fz_matrix ctm);
+fz_rect fz_boundpath(fz_path* node, fz_matrix ctm);
+fz_rect fz_boundtext(fz_text* node, fz_matrix ctm);
+fz_rect fz_boundimage(fz_image* node, fz_matrix ctm);
+
+void
+fz_initnode(fz_node *node, fz_nodekind kind)
+{
+	node->kind = kind;
+	node->parent = nil;
+}
+
+void
+fz_freenode(fz_node *node)
+{
+	if (node->next)
+		fz_freenode(node->next);
+
+	switch (node->kind)
+	{
+	case FZ_NOVER:
+		fz_freeover((fz_over *) node);
+		break;
+	case FZ_NMASK:
+		fz_freemask((fz_mask *) node);
+		break;
+	case FZ_NBLEND:
+		fz_freeblend((fz_blend *) node);
+		break;
+	case FZ_NTRANSFORM:
+		fz_freetransform((fz_transform *) node);
+		break;
+	case FZ_NFORM:
+		fz_freeform((fz_form *) node);
+		break;
+	case FZ_NSOLID:
+		fz_freesolid((fz_solid *) node);
+		break;
+	case FZ_NPATH:
+		fz_freepath((fz_path *) node);
+		break;
+	case FZ_NTEXT:
+		fz_freetext((fz_text *) node);
+		break;
+	case FZ_NIMAGE:
+		fz_freeimage((fz_image *) node);
+		break;
+	}
+}
+
+fz_rect
+fz_boundnode(fz_node *node, fz_matrix ctm)
+{
+	switch (node->kind)
+	{
+	case FZ_NOVER:
+		return fz_boundover((fz_over *) node, ctm);
+	case FZ_NMASK:
+		return fz_boundmask((fz_mask *) node, ctm);
+	case FZ_NBLEND:
+		return fz_boundblend((fz_blend *) node, ctm);
+	case FZ_NTRANSFORM:
+		return fz_boundtransform((fz_transform *) node, ctm);
+	case FZ_NFORM:
+		return fz_boundform((fz_form *) node, ctm);
+	case FZ_NSOLID:
+		return fz_boundsolid((fz_solid *) node, ctm);
+	case FZ_NPATH:
+		return fz_boundpath((fz_path *) node, ctm);
+	case FZ_NTEXT:
+		return fz_boundtext((fz_text *) node, ctm);
+	case FZ_NIMAGE:
+		return fz_boundimage((fz_image *) node, ctm);
+	}
+	return FZ_INFRECT;
+}
+
+int
+fz_isover(fz_node *node)
+{
+	return node ? node->kind == FZ_NOVER : 0;
+}
+
+int
+fz_ismask(fz_node *node)
+{
+	return node ? node->kind == FZ_NMASK : 0;
+}
+
+int
+fz_isblend(fz_node *node)
+{
+	return node ? node->kind == FZ_NBLEND : 0;
+}
+
+int
+fz_istransform(fz_node *node)
+{
+	return node ? node->kind == FZ_NTRANSFORM : 0;
+}
+
+int
+fz_isform(fz_node *node)
+{
+	return node ? node->kind == FZ_NFORM : 0;
+}
+
+int
+fz_issolid(fz_node *node)
+{
+	return node ? node->kind == FZ_NSOLID : 0;
+}
+
+int
+fz_ispath(fz_node *node)
+{
+	return node ? node->kind == FZ_NPATH : 0;
+}
+
+int
+fz_istext(fz_node *node)
+{
+	return node ? node->kind == FZ_NTEXT : 0;
+}
+
+int
+fz_isimage(fz_node *node)
+{
+	return node ? node->kind == FZ_NIMAGE : 0;
+}
+
diff --git a/tree/over.c b/tree/over.c
new file mode 100644
index 00000000..d55bb297
--- /dev/null
+++ b/tree/over.c
@@ -0,0 +1,50 @@
+#include <fitz.h>
+
+fz_error *
+fz_newover(fz_node **nodep)
+{
+	fz_over *node;
+
+	node = fz_malloc(sizeof (fz_over));
+	if (!node)
+		return fz_outofmem;
+	*nodep = (fz_node*)node;
+
+	fz_initnode((fz_node*)node, FZ_NOVER);
+	node->child = nil;
+
+	return nil;
+}
+
+void
+fz_freeover(fz_over *node)
+{
+	if (node->child)
+		fz_freenode(node->child);
+	fz_free(node);
+}
+
+fz_rect
+fz_boundover(fz_over* node, fz_matrix ctm)
+{
+	fz_node *child;
+	fz_rect bbox;
+	fz_rect r;
+
+	bbox = FZ_INFRECT;
+
+	for (child = node->child; child; child = child->next)
+	{
+		r = fz_boundnode(child, ctm);
+		if (r.max.x >= r.min.x)
+		{
+			if (bbox.max.x >= bbox.min.x)
+				bbox = fz_mergerects(r, bbox);
+			else
+				bbox = r;
+		}
+	}
+
+	return bbox;
+}
+
diff --git a/tree/path.c b/tree/path.c
new file mode 100644
index 00000000..d21fda56
--- /dev/null
+++ b/tree/path.c
@@ -0,0 +1,291 @@
+#include <fitz.h>
+
+fz_error *
+fz_newpath(fz_path **pathp)
+{
+	fz_path *path;
+
+	path = *pathp = fz_malloc(sizeof(fz_path));
+	if (!path)
+		return fz_outofmem;
+
+	fz_initnode((fz_node*)path, FZ_NPATH);
+
+	path->paint = FZ_FILL;
+	path->stroke = nil;
+	path->dash = nil;
+	path->len = 0;
+	path->cap = 0;
+	path->els = nil;
+
+	return nil;
+}
+
+fz_error *
+fz_clonepath(fz_path **pathp, fz_path *oldpath)
+{
+	fz_path *path;
+
+	path = *pathp = fz_malloc(sizeof(fz_path));
+	if (!path)
+		return fz_outofmem;
+
+	fz_initnode((fz_node*)path, FZ_NPATH);
+
+	path->paint = FZ_FILL;
+	path->stroke = nil;
+	path->dash = nil;
+	path->len = oldpath->len;
+	path->cap = oldpath->len;
+
+	path->els = fz_malloc(sizeof (fz_pathel) * path->len);
+	if (!path->els) {
+		fz_free(path);
+		return fz_outofmem;
+	}
+	memcpy(path->els, oldpath->els, sizeof(fz_pathel) * path->len);
+
+	return nil;
+}
+
+void
+fz_freepath(fz_path *node)
+{
+	fz_free(node->stroke);
+	fz_free(node->dash);
+	fz_free(node->els);
+	fz_free(node);
+}
+
+static fz_error *
+growpath(fz_path *path, int n)
+{
+	int newcap;
+	fz_pathel *newels;
+
+	while (path->len + n > path->cap)
+	{
+		newcap = path->cap + 36;
+		newels = fz_realloc(path->els, sizeof (fz_pathel) * newcap);
+		if (!newels)
+			return fz_outofmem;
+		path->cap = newcap;
+		path->els = newels;
+	}
+
+	return nil;
+}
+
+fz_error *
+fz_moveto(fz_path *path, float x, float y)
+{
+	if (growpath(path, 3) != nil)
+		return fz_outofmem;
+	path->els[path->len++].k = FZ_MOVETO;
+	path->els[path->len++].v = x;
+	path->els[path->len++].v = y;
+	return nil;
+}
+
+fz_error *
+fz_lineto(fz_path *path, float x, float y)
+{
+	if (growpath(path, 3) != nil)
+		return fz_outofmem;
+	path->els[path->len++].k = FZ_LINETO;
+	path->els[path->len++].v = x;
+	path->els[path->len++].v = y;
+	return nil;
+}
+
+fz_error *
+fz_curveto(fz_path *path,
+		float x1, float y1,
+		float x2, float y2,
+		float x3, float y3)
+{
+	if (growpath(path, 7) != nil)
+		return fz_outofmem;
+	path->els[path->len++].k = FZ_CURVETO;
+	path->els[path->len++].v = x1;
+	path->els[path->len++].v = y1;
+	path->els[path->len++].v = x2;
+	path->els[path->len++].v = y2;
+	path->els[path->len++].v = x3;
+	path->els[path->len++].v = y3;
+	return nil;
+}
+
+fz_error *
+fz_curvetov(fz_path *path, float x2, float y2, float x3, float y3)
+{
+	float x1 = path->els[path->len-2].v;
+	float y1 = path->els[path->len-1].v;
+	return fz_curveto(path, x1, y1, x2, y2, x3, y3);
+}
+
+fz_error *
+fz_curvetoy(fz_path *path, float x1, float y1, float x3, float y3)
+{
+	return fz_curveto(path, x1, y1, x3, y3, x3, y3);
+}
+
+fz_error *
+fz_closepath(fz_path *path)
+{
+	if (growpath(path, 1) != nil)
+		return fz_outofmem;
+	path->els[path->len++].k = FZ_CLOSEPATH;
+	return nil;
+}
+
+fz_error *
+fz_endpath(fz_path *path, fz_pathkind paint, fz_stroke *stroke, fz_dash *dash)
+{
+	fz_pathel *newels;
+
+	newels = fz_realloc(path->els, path->len * sizeof(fz_pathel));
+	if (!newels)
+		return fz_outofmem;
+	path->els = newels;
+
+	path->paint = paint;
+	path->stroke = stroke;
+	path->dash = dash;
+
+	return nil;
+}
+
+static inline fz_rect boundexpand(fz_rect r, fz_point p)
+{
+	if (r.min.x > r.max.x)
+	{
+		r.min.x = r.max.x = p.x;
+		r.min.y = r.max.y = p.y;
+	}
+	else
+	{
+		if (p.x < r.min.x) r.min.x = p.x;
+		if (p.y < r.min.y) r.min.y = p.y;
+		if (p.x > r.max.x) r.max.x = p.x;
+		if (p.y > r.max.y) r.max.y = p.y;
+	}
+	return r;
+}
+
+fz_rect
+fz_boundpath(fz_path *path, fz_matrix ctm)
+{
+	fz_point p;
+	fz_rect r = FZ_INFRECT;
+	int i = 0;
+
+	while (i < path->len)
+	{
+		switch (path->els[i++].k)
+		{
+		case FZ_CURVETO:
+			p.x = path->els[i++].v;
+			p.y = path->els[i++].v;
+			r = boundexpand(r, fz_transformpoint(ctm, p));
+			p.x = path->els[i++].v;
+			p.y = path->els[i++].v;
+			r = boundexpand(r, fz_transformpoint(ctm, p));
+		case FZ_MOVETO:
+		case FZ_LINETO:
+			p.x = path->els[i++].v;
+			p.y = path->els[i++].v;
+			r = boundexpand(r, fz_transformpoint(ctm, p));
+			break;
+		case FZ_CLOSEPATH:
+			break;
+		}
+	}
+
+	if (path->paint == FZ_STROKE)
+	{
+		float miterlength = sin(path->stroke->miterlimit / 2.0);
+		float linewidth = path->stroke->linewidth;
+		float expand = MAX(miterlength, linewidth) / 2.0;
+		r.min.x -= expand;
+		r.min.y -= expand;
+		r.max.x += expand;
+		r.max.y += expand;
+	}
+
+	return r;
+}
+
+void
+fz_debugpath(fz_path *path)
+{
+	float x, y;
+	int i = 0;
+	while (i < path->len)
+	{
+		switch (path->els[i++].k)
+		{
+		case FZ_MOVETO:
+			x = path->els[i++].v;
+			y = path->els[i++].v;
+			printf("%g %g m\n", x, y);
+			break;
+		case FZ_LINETO:
+			x = path->els[i++].v;
+			y = path->els[i++].v;
+			printf("%g %g l\n", x, y);
+			break;
+		case FZ_CURVETO:
+			x = path->els[i++].v;
+			y = path->els[i++].v;
+			printf("%g %g ", x, y);
+			x = path->els[i++].v;
+			y = path->els[i++].v;
+			printf("%g %g ", x, y);
+			x = path->els[i++].v;
+			y = path->els[i++].v;
+			printf("%g %g c\n", x, y);
+			break;
+		case FZ_CLOSEPATH:
+			printf("h\n");
+		}
+	}
+
+	switch (path->paint)
+	{
+	case FZ_STROKE:
+		printf("S\n");
+		break;
+	case FZ_FILL:
+		printf("f\n");
+		break;
+	case FZ_EOFILL:
+		printf("f*\n");
+		break;
+	}
+}
+
+fz_error *
+fz_newdash(fz_dash **dashp, float phase, int len, float *array)
+{
+	fz_dash *dash;
+	int i;
+
+	dash = *dashp = fz_malloc(sizeof(fz_dash) + sizeof(float) * len);
+	if (!dash)
+		return fz_outofmem;
+
+	dash->len = len;
+	dash->phase = phase;
+	for (i = 0; i < len; i++)
+		dash->array[i] = array[i];
+
+	return nil;
+}
+
+void
+fz_freedash(fz_dash *dash)
+{
+	fz_free(dash);
+}
+
diff --git a/tree/solid.c b/tree/solid.c
new file mode 100644
index 00000000..37ff55eb
--- /dev/null
+++ b/tree/solid.c
@@ -0,0 +1,33 @@
+#include <fitz.h>
+
+fz_error *
+fz_newsolid(fz_node **nodep, float r, float g, float b)
+{
+	fz_solid *node;
+
+	node = fz_malloc(sizeof (fz_solid));
+	if (!node)
+		return fz_outofmem;
+	*nodep = (fz_node*)node;
+
+	fz_initnode((fz_node*)node, FZ_NSOLID);
+	node->r = r;
+	node->g = g;
+	node->b = b;
+
+	return nil;
+}
+
+void
+fz_freesolid(fz_solid *node)
+{
+	fz_free(node);
+}
+
+fz_rect
+fz_boundsolid(fz_solid *node, fz_matrix ctm)
+{
+        /* min > max => no bounds */
+        return (fz_rect) { {1,1}, {-1,-1} };
+}
+
diff --git a/tree/text.c b/tree/text.c
new file mode 100644
index 00000000..312e3bde
--- /dev/null
+++ b/tree/text.c
@@ -0,0 +1,67 @@
+#include <fitz.h>
+
+fz_error *
+fz_newtext(fz_text **textp, fz_font *font)
+{
+	fz_text *text;
+
+	text = *textp = fz_malloc(sizeof(fz_text));
+	if (!text)
+		return fz_outofmem;
+
+	fz_initnode((fz_node*)text, FZ_NTEXT);
+
+	text->font = font;
+	text->trm = fz_identity();
+	text->len = 0;
+	text->cap = 0;
+	text->els = nil;
+
+	return nil;
+}
+
+void
+fz_freetext(fz_text *text)
+{
+	fz_free(text->els);
+	fz_free(text);
+};
+
+fz_rect
+fz_boundtext(fz_text *text, fz_matrix ctm)
+{
+	/* fz_rect bounds = fz_boundglyph(text->font, text->els[0], ctm); */
+	return FZ_INFRECT;
+}
+
+static fz_error *
+growtext(fz_text *text, int n)
+{
+	int newcap;
+	fz_textel *newels;
+
+	while (text->len + n > text->cap)
+	{
+		newcap = text->cap + 36;
+		newels = fz_realloc(text->els, sizeof (fz_textel) * newcap);
+		if (!newels)
+			return fz_outofmem;
+		text->cap = newcap;
+		text->els = newels;
+	}
+
+	return nil;
+}
+
+fz_error *
+fz_addtext(fz_text *text, int g, float x, float y)
+{
+	if (growtext(text, 1) != nil)
+		return fz_outofmem;
+	text->els[text->len].g = g;
+	text->els[text->len].x = x;
+	text->els[text->len].y = y;
+	text->len++;
+	return nil;
+}
+
diff --git a/tree/transform.c b/tree/transform.c
new file mode 100644
index 00000000..18910d6b
--- /dev/null
+++ b/tree/transform.c
@@ -0,0 +1,35 @@
+#include <fitz.h>
+
+fz_error *
+fz_newtransform(fz_node **nodep, fz_matrix m)
+{
+	fz_transform *node;
+
+	node = fz_malloc(sizeof (fz_transform));
+	if (!node)
+		return fz_outofmem;
+	*nodep = (fz_node*)node;
+
+	fz_initnode((fz_node*)node, FZ_NTRANSFORM);
+	node->child = nil;
+	node->m = m;
+
+	return nil;
+}
+
+void
+fz_freetransform(fz_transform *node)
+{
+	if (node->child)
+		fz_freenode(node->child);
+	fz_free(node);
+}
+
+fz_rect
+fz_boundtransform(fz_transform *node, fz_matrix ctm)
+{
+	if (!node->child)
+		return FZ_INFRECT;
+	return fz_boundnode(node->child, fz_concat(node->m, ctm));
+}
+
diff --git a/tree/tree.c b/tree/tree.c
new file mode 100644
index 00000000..1a96ec38
--- /dev/null
+++ b/tree/tree.c
@@ -0,0 +1,63 @@
+#include <fitz.h>
+
+fz_error *
+fz_newtree(fz_tree **treep)
+{
+	fz_tree *tree;
+
+	tree = *treep = fz_malloc(sizeof (fz_tree));
+	if (!tree)
+		return fz_outofmem;
+
+	tree->root = nil;
+	tree->head = nil;
+
+	return nil;
+}
+
+void
+fz_freetree(fz_tree *tree)
+{
+	if (tree->root)
+		fz_freenode(tree->root);
+	fz_free(tree);
+}
+
+fz_rect
+fz_boundtree(fz_tree *tree, fz_matrix ctm)
+{
+	if (tree->root)
+		return fz_boundnode(tree->root, ctm);
+	return FZ_INFRECT;
+}
+
+void
+fz_insertnode(fz_node *node, fz_node *child)
+{
+	child->parent = node;
+
+	if (fz_isover(node))
+	{
+		child->next = ((fz_over*)node)->child;
+		((fz_over*)node)->child = child;
+	}
+
+	if (fz_ismask(node))
+	{
+		child->next = ((fz_mask*)node)->child;
+		((fz_mask*)node)->child = child;
+	}
+
+	if (fz_isblend(node))
+	{
+		child->next = ((fz_blend*)node)->child;
+		((fz_blend*)node)->child = child;
+	}
+
+	if (fz_istransform(node))
+	{
+		child->next = ((fz_transform*)node)->child;
+		((fz_transform*)node)->child = child;
+	}
+}
+