xref: /linux/fs/unicode/mkutf8data.c (revision 3d0fe49454652117522f60bfbefb978ba0e5300b)

/*
 * Copyright (c) 2014 SGI.
 * All rights reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it would be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write the Free Software Foundation,
 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

/* Generator for a compact trie for unicode normalization */

#include <sys/types.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>

/* Default names of the in- and output files. */

#define AGE_NAME	"DerivedAge.txt"
#define CCC_NAME	"DerivedCombiningClass.txt"
#define PROP_NAME	"DerivedCoreProperties.txt"
#define DATA_NAME	"UnicodeData.txt"
#define FOLD_NAME	"CaseFolding.txt"
#define NORM_NAME	"NormalizationCorrections.txt"
#define TEST_NAME	"NormalizationTest.txt"
#define UTF8_NAME	"utf8data.h"

const char	*age_name  = AGE_NAME;
const char	*ccc_name  = CCC_NAME;
const char	*prop_name = PROP_NAME;
const char	*data_name = DATA_NAME;
const char	*fold_name = FOLD_NAME;
const char	*norm_name = NORM_NAME;
const char	*test_name = TEST_NAME;
const char	*utf8_name = UTF8_NAME;

int verbose = 0;

/* An arbitrary line size limit on input lines. */

#define LINESIZE	1024
char line[LINESIZE];
char buf0[LINESIZE];
char buf1[LINESIZE];
char buf2[LINESIZE];
char buf3[LINESIZE];

const char *argv0;

#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))

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

/*
 * Unicode version numbers consist of three parts: major, minor, and a
 * revision.  These numbers are packed into an unsigned int to obtain
 * a single version number.
 *
 * To save space in the generated trie, the unicode version is not
 * stored directly, instead we calculate a generation number from the
 * unicode versions seen in the DerivedAge file, and use that as an
 * index into a table of unicode versions.
 */
#define UNICODE_MAJ_SHIFT		(16)
#define UNICODE_MIN_SHIFT		(8)

#define UNICODE_MAJ_MAX			((unsigned short)-1)
#define UNICODE_MIN_MAX			((unsigned char)-1)
#define UNICODE_REV_MAX			((unsigned char)-1)

#define UNICODE_AGE(MAJ,MIN,REV)			\
	(((unsigned int)(MAJ) << UNICODE_MAJ_SHIFT) |	\
	 ((unsigned int)(MIN) << UNICODE_MIN_SHIFT) |	\
	 ((unsigned int)(REV)))

unsigned int *ages;
int ages_count;

unsigned int unicode_maxage;

static int age_valid(unsigned int major, unsigned int minor,
		     unsigned int revision)
{
	if (major > UNICODE_MAJ_MAX)
		return 0;
	if (minor > UNICODE_MIN_MAX)
		return 0;
	if (revision > UNICODE_REV_MAX)
		return 0;
	return 1;
}

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

/*
 * utf8trie_t
 *
 * A compact binary tree, used to decode UTF-8 characters.
 *
 * Internal nodes are one byte for the node itself, and up to three
 * bytes for an offset into the tree.  The first byte contains the
 * following information:
 *  NEXTBYTE  - flag        - advance to next byte if set
 *  BITNUM    - 3 bit field - the bit number to tested
 *  OFFLEN    - 2 bit field - number of bytes in the offset
 * if offlen == 0 (non-branching node)
 *  RIGHTPATH - 1 bit field - set if the following node is for the
 *                            right-hand path (tested bit is set)
 *  TRIENODE  - 1 bit field - set if the following node is an internal
 *                            node, otherwise it is a leaf node
 * if offlen != 0 (branching node)
 *  LEFTNODE  - 1 bit field - set if the left-hand node is internal
 *  RIGHTNODE - 1 bit field - set if the right-hand node is internal
 *
 * Due to the way utf8 works, there cannot be branching nodes with
 * NEXTBYTE set, and moreover those nodes always have a righthand
 * descendant.
 */
typedef unsigned char utf8trie_t;
#define BITNUM		0x07
#define NEXTBYTE	0x08
#define OFFLEN		0x30
#define OFFLEN_SHIFT	4
#define RIGHTPATH	0x40
#define TRIENODE	0x80
#define RIGHTNODE	0x40
#define LEFTNODE	0x80

/*
 * utf8leaf_t
 *
 * The leaves of the trie are embedded in the trie, and so the same
 * underlying datatype, unsigned char.
 *
 * leaf[0]: The unicode version, stored as a generation number that is
 *          an index into utf8agetab[].  With this we can filter code
 *          points based on the unicode version in which they were
 *          defined.  The CCC of a non-defined code point is 0.
 * leaf[1]: Canonical Combining Class. During normalization, we need
 *          to do a stable sort into ascending order of all characters
 *          with a non-zero CCC that occur between two characters with
 *          a CCC of 0, or at the begin or end of a string.
 *          The unicode standard guarantees that all CCC values are
 *          between 0 and 254 inclusive, which leaves 255 available as
 *          a special value.
 *          Code points with CCC 0 are known as stoppers.
 * leaf[2]: Decomposition. If leaf[1] == 255, then leaf[2] is the
 *          start of a NUL-terminated string that is the decomposition
 *          of the character.
 *          The CCC of a decomposable character is the same as the CCC
 *          of the first character of its decomposition.
 *          Some characters decompose as the empty string: these are
 *          characters with the Default_Ignorable_Code_Point property.
 *          These do affect normalization, as they all have CCC 0.
 *
 * The decompositions in the trie have been fully expanded.
 *
 * Casefolding, if applicable, is also done using decompositions.
 */
typedef unsigned char utf8leaf_t;

#define LEAF_GEN(LEAF)	((LEAF)[0])
#define LEAF_CCC(LEAF)	((LEAF)[1])
#define LEAF_STR(LEAF)	((const char*)((LEAF) + 2))

#define MAXGEN		(255)

#define MINCCC		(0)
#define MAXCCC		(254)
#define STOPPER		(0)
#define DECOMPOSE	(255)
#define HANGUL		((char)(255))

#define UTF8HANGULLEAF	(12)

struct tree;
static utf8leaf_t *utf8nlookup(struct tree *, unsigned char *,
			       const char *, size_t);
static utf8leaf_t *utf8lookup(struct tree *, unsigned char *, const char *);

unsigned char *utf8data;
size_t utf8data_size;

utf8trie_t *nfdi;
utf8trie_t *nfdicf;

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

/*
 * UTF8 valid ranges.
 *
 * The UTF-8 encoding spreads the bits of a 32bit word over several
 * bytes. This table gives the ranges that can be held and how they'd
 * be represented.
 *
 * 0x00000000 0x0000007F: 0xxxxxxx
 * 0x00000000 0x000007FF: 110xxxxx 10xxxxxx
 * 0x00000000 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx
 * 0x00000000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
 * 0x00000000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
 * 0x00000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
 *
 * There is an additional requirement on UTF-8, in that only the
 * shortest representation of a 32bit value is to be used.  A decoder
 * must not decode sequences that do not satisfy this requirement.
 * Thus the allowed ranges have a lower bound.
 *
 * 0x00000000 0x0000007F: 0xxxxxxx
 * 0x00000080 0x000007FF: 110xxxxx 10xxxxxx
 * 0x00000800 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx
 * 0x00010000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
 * 0x00200000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
 * 0x04000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
 *
 * Actual unicode characters are limited to the range 0x0 - 0x10FFFF,
 * 17 planes of 65536 values.  This limits the sequences actually seen
 * even more, to just the following.
 *
 *          0 -     0x7f: 0                     0x7f
 *       0x80 -    0x7ff: 0xc2 0x80             0xdf 0xbf
 *      0x800 -   0xffff: 0xe0 0xa0 0x80        0xef 0xbf 0xbf
 *    0x10000 - 0x10ffff: 0xf0 0x90 0x80 0x80   0xf4 0x8f 0xbf 0xbf
 *
 * Even within those ranges not all values are allowed: the surrogates
 * 0xd800 - 0xdfff should never be seen.
 *
 * Note that the longest sequence seen with valid usage is 4 bytes,
 * the same a single UTF-32 character.  This makes the UTF-8
 * representation of Unicode strictly smaller than UTF-32.
 *
 * The shortest sequence requirement was introduced by:
 *    Corrigendum #1: UTF-8 Shortest Form
 * It can be found here:
 *    http://www.unicode.org/versions/corrigendum1.html
 *
 */

#define UTF8_2_BITS     0xC0
#define UTF8_3_BITS     0xE0
#define UTF8_4_BITS     0xF0
#define UTF8_N_BITS     0x80
#define UTF8_2_MASK     0xE0
#define UTF8_3_MASK     0xF0
#define UTF8_4_MASK     0xF8
#define UTF8_N_MASK     0xC0
#define UTF8_V_MASK     0x3F
#define UTF8_V_SHIFT    6

static int utf8encode(char *str, unsigned int val)
{
	int len;

	if (val < 0x80) {
		str[0] = val;
		len = 1;
	} else if (val < 0x800) {
		str[1] = val & UTF8_V_MASK;
		str[1] |= UTF8_N_BITS;
		val >>= UTF8_V_SHIFT;
		str[0] = val;
		str[0] |= UTF8_2_BITS;
		len = 2;
	} else if (val < 0x10000) {
		str[2] = val & UTF8_V_MASK;
		str[2] |= UTF8_N_BITS;
		val >>= UTF8_V_SHIFT;
		str[1] = val & UTF8_V_MASK;
		str[1] |= UTF8_N_BITS;
		val >>= UTF8_V_SHIFT;
		str[0] = val;
		str[0] |= UTF8_3_BITS;
		len = 3;
	} else if (val < 0x110000) {
		str[3] = val & UTF8_V_MASK;
		str[3] |= UTF8_N_BITS;
		val >>= UTF8_V_SHIFT;
		str[2] = val & UTF8_V_MASK;
		str[2] |= UTF8_N_BITS;
		val >>= UTF8_V_SHIFT;
		str[1] = val & UTF8_V_MASK;
		str[1] |= UTF8_N_BITS;
		val >>= UTF8_V_SHIFT;
		str[0] = val;
		str[0] |= UTF8_4_BITS;
		len = 4;
	} else {
		printf("%#x: illegal val\n", val);
		len = 0;
	}
	return len;
}

static unsigned int utf8decode(const char *str)
{
	const unsigned char *s = (const unsigned char*)str;
	unsigned int unichar = 0;

	if (*s < 0x80) {
		unichar = *s;
	} else if (*s < UTF8_3_BITS) {
		unichar = *s++ & 0x1F;
		unichar <<= UTF8_V_SHIFT;
		unichar |= *s & 0x3F;
	} else if (*s < UTF8_4_BITS) {
		unichar = *s++ & 0x0F;
		unichar <<= UTF8_V_SHIFT;
		unichar |= *s++ & 0x3F;
		unichar <<= UTF8_V_SHIFT;
		unichar |= *s & 0x3F;
	} else {
		unichar = *s++ & 0x0F;
		unichar <<= UTF8_V_SHIFT;
		unichar |= *s++ & 0x3F;
		unichar <<= UTF8_V_SHIFT;
		unichar |= *s++ & 0x3F;
		unichar <<= UTF8_V_SHIFT;
		unichar |= *s & 0x3F;
	}
	return unichar;
}

static int utf32valid(unsigned int unichar)
{
	return unichar < 0x110000;
}

#define HANGUL_SYLLABLE(U)	((U) >= 0xAC00 && (U) <= 0xD7A3)

#define NODE 1
#define LEAF 0

struct tree {
	void *root;
	int childnode;
	const char *type;
	unsigned int maxage;
	struct tree *next;
	int (*leaf_equal)(void *, void *);
	void (*leaf_print)(void *, int);
	int (*leaf_mark)(void *);
	int (*leaf_size)(void *);
	int *(*leaf_index)(struct tree *, void *);
	unsigned char *(*leaf_emit)(void *, unsigned char *);
	int leafindex[0x110000];
	int index;
};

struct node {
	int index;
	int offset;
	int mark;
	int size;
	struct node *parent;
	void *left;
	void *right;
	unsigned char bitnum;
	unsigned char nextbyte;
	unsigned char leftnode;
	unsigned char rightnode;
	unsigned int keybits;
	unsigned int keymask;
};

/*
 * Example lookup function for a tree.
 */
static void *lookup(struct tree *tree, const char *key)
{
	struct node *node;
	void *leaf = NULL;

	node = tree->root;
	while (!leaf && node) {
		if (node->nextbyte)
			key++;
		if (*key & (1 << (node->bitnum & 7))) {
			/* Right leg */
			if (node->rightnode == NODE) {
				node = node->right;
			} else if (node->rightnode == LEAF) {
				leaf = node->right;
			} else {
				node = NULL;
			}
		} else {
			/* Left leg */
			if (node->leftnode == NODE) {
				node = node->left;
			} else if (node->leftnode == LEAF) {
				leaf = node->left;
			} else {
				node = NULL;
			}
		}
	}

	return leaf;
}

/*
 * A simple non-recursive tree walker: keep track of visits to the
 * left and right branches in the leftmask and rightmask.
 */
static void tree_walk(struct tree *tree)
{
	struct node *node;
	unsigned int leftmask;
	unsigned int rightmask;
	unsigned int bitmask;
	int indent = 1;
	int nodes, singletons, leaves;

	nodes = singletons = leaves = 0;

	printf("%s_%x root %p\n", tree->type, tree->maxage, tree->root);
	if (tree->childnode == LEAF) {
		assert(tree->root);
		tree->leaf_print(tree->root, indent);
		leaves = 1;
	} else {
		assert(tree->childnode == NODE);
		node = tree->root;
		leftmask = rightmask = 0;
		while (node) {
			printf("%*snode @ %p bitnum %d nextbyte %d"
			       " left %p right %p mask %x bits %x\n",
				indent, "", node,
				node->bitnum, node->nextbyte,
				node->left, node->right,
				node->keymask, node->keybits);
			nodes += 1;
			if (!(node->left && node->right))
				singletons += 1;

			while (node) {
				bitmask = 1 << node->bitnum;
				if ((leftmask & bitmask) == 0) {
					leftmask |= bitmask;
					if (node->leftnode == LEAF) {
						assert(node->left);
						tree->leaf_print(node->left,
								 indent+1);
						leaves += 1;
					} else if (node->left) {
						assert(node->leftnode == NODE);
						indent += 1;
						node = node->left;
						break;
					}
				}
				if ((rightmask & bitmask) == 0) {
					rightmask |= bitmask;
					if (node->rightnode == LEAF) {
						assert(node->right);
						tree->leaf_print(node->right,
								 indent+1);
						leaves += 1;
					} else if (node->right) {
						assert(node->rightnode == NODE);
						indent += 1;
						node = node->right;
						break;
					}
				}
				leftmask &= ~bitmask;
				rightmask &= ~bitmask;
				node = node->parent;
				indent -= 1;
			}
		}
	}
	printf("nodes %d leaves %d singletons %d\n",
	       nodes, leaves, singletons);
}

/*
 * Allocate an initialize a new internal node.
 */
static struct node *alloc_node(struct node *parent)
{
	struct node *node;
	int bitnum;

	node = malloc(sizeof(*node));
	node->left = node->right = NULL;
	node->parent = parent;
	node->leftnode = NODE;
	node->rightnode = NODE;
	node->keybits = 0;
	node->keymask = 0;
	node->mark = 0;
	node->index = 0;
	node->offset = -1;
	node->size = 4;

	if (node->parent) {
		bitnum = parent->bitnum;
		if ((bitnum & 7) == 0) {
			node->bitnum = bitnum + 7 + 8;
			node->nextbyte = 1;
		} else {
			node->bitnum = bitnum - 1;
			node->nextbyte = 0;
		}
	} else {
		node->bitnum = 7;
		node->nextbyte = 0;
	}

	return node;
}

/*
 * Insert a new leaf into the tree, and collapse any subtrees that are
 * fully populated and end in identical leaves. A nextbyte tagged
 * internal node will not be removed to preserve the tree's integrity.
 * Note that due to the structure of utf8, no nextbyte tagged node
 * will be a candidate for removal.
 */
static int insert(struct tree *tree, char *key, int keylen, void *leaf)
{
	struct node *node;
	struct node *parent;
	void **cursor;
	int keybits;

	assert(keylen >= 1 && keylen <= 4);

	node = NULL;
	cursor = &tree->root;
	keybits = 8 * keylen;

	/* Insert, creating path along the way. */
	while (keybits) {
		if (!*cursor)
			*cursor = alloc_node(node);
		node = *cursor;
		if (node->nextbyte)
			key++;
		if (*key & (1 << (node->bitnum & 7)))
			cursor = &node->right;
		else
			cursor = &node->left;
		keybits--;
	}
	*cursor = leaf;

	/* Merge subtrees if possible. */
	while (node) {
		if (*key & (1 << (node->bitnum & 7)))
			node->rightnode = LEAF;
		else
			node->leftnode = LEAF;
		if (node->nextbyte)
			break;
		if (node->leftnode == NODE || node->rightnode == NODE)
			break;
		assert(node->left);
		assert(node->right);
		/* Compare */
		if (! tree->leaf_equal(node->left, node->right))
			break;
		/* Keep left, drop right leaf. */
		leaf = node->left;
		/* Check in parent */
		parent = node->parent;
		if (!parent) {
			/* root of tree! */
			tree->root = leaf;
			tree->childnode = LEAF;
		} else if (parent->left == node) {
			parent->left = leaf;
			parent->leftnode = LEAF;
			if (parent->right) {
				parent->keymask = 0;
				parent->keybits = 0;
			} else {
				parent->keymask |= (1 << node->bitnum);
			}
		} else if (parent->right == node) {
			parent->right = leaf;
			parent->rightnode = LEAF;
			if (parent->left) {
				parent->keymask = 0;
				parent->keybits = 0;
			} else {
				parent->keymask |= (1 << node->bitnum);
				parent->keybits |= (1 << node->bitnum);
			}
		} else {
			/* internal tree error */
			assert(0);
		}
		free(node);
		node = parent;
	}

	/* Propagate keymasks up along singleton chains. */
	while (node) {
		parent = node->parent;
		if (!parent)
			break;
		/* Nix the mask for parents with two children. */
		if (node->keymask == 0) {
			parent->keymask = 0;
			parent->keybits = 0;
		} else if (parent->left && parent->right) {
			parent->keymask = 0;
			parent->keybits = 0;
		} else {
			assert((parent->keymask & node->keymask) == 0);
			parent->keymask |= node->keymask;
			parent->keymask |= (1 << parent->bitnum);
			parent->keybits |= node->keybits;
			if (parent->right)
				parent->keybits |= (1 << parent->bitnum);
		}
		node = parent;
	}

	return 0;
}

/*
 * Prune internal nodes.
 *
 * Fully populated subtrees that end at the same leaf have already
 * been collapsed.  There are still internal nodes that have for both
 * their left and right branches a sequence of singletons that make
 * identical choices and end in identical leaves.  The keymask and
 * keybits collected in the nodes describe the choices made in these
 * singleton chains.  When they are identical for the left and right
 * branch of a node, and the two leaves comare identical, the node in
 * question can be removed.
 *
 * Note that nodes with the nextbyte tag set will not be removed by
 * this to ensure tree integrity.  Note as well that the structure of
 * utf8 ensures that these nodes would not have been candidates for
 * removal in any case.
 */
static void prune(struct tree *tree)
{
	struct node *node;
	struct node *left;
	struct node *right;
	struct node *parent;
	void *leftleaf;
	void *rightleaf;
	unsigned int leftmask;
	unsigned int rightmask;
	unsigned int bitmask;
	int count;

	if (verbose > 0)
		printf("Pruning %s_%x\n", tree->type, tree->maxage);

	count = 0;
	if (tree->childnode == LEAF)
		return;
	if (!tree->root)
		return;

	leftmask = rightmask = 0;
	node = tree->root;
	while (node) {
		if (node->nextbyte)
			goto advance;
		if (node->leftnode == LEAF)
			goto advance;
		if (node->rightnode == LEAF)
			goto advance;
		if (!node->left)
			goto advance;
		if (!node->right)
			goto advance;
		left = node->left;
		right = node->right;
		if (left->keymask == 0)
			goto advance;
		if (right->keymask == 0)
			goto advance;
		if (left->keymask != right->keymask)
			goto advance;
		if (left->keybits != right->keybits)
			goto advance;
		leftleaf = NULL;
		while (!leftleaf) {
			assert(left->left || left->right);
			if (left->leftnode == LEAF)
				leftleaf = left->left;
			else if (left->rightnode == LEAF)
				leftleaf = left->right;
			else if (left->left)
				left = left->left;
			else if (left->right)
				left = left->right;
			else
				assert(0);
		}
		rightleaf = NULL;
		while (!rightleaf) {
			assert(right->left || right->right);
			if (right->leftnode == LEAF)
				rightleaf = right->left;
			else if (right->rightnode == LEAF)
				rightleaf = right->right;
			else if (right->left)
				right = right->left;
			else if (right->right)
				right = right->right;
			else
				assert(0);
		}
		if (! tree->leaf_equal(leftleaf, rightleaf))
			goto advance;
		/*
		 * This node has identical singleton-only subtrees.
		 * Remove it.
		 */
		parent = node->parent;
		left = node->left;
		right = node->right;
		if (parent->left == node)
			parent->left = left;
		else if (parent->right == node)
			parent->right = left;
		else
			assert(0);
		left->parent = parent;
		left->keymask |= (1 << node->bitnum);
		node->left = NULL;
		while (node) {
			bitmask = 1 << node->bitnum;
			leftmask &= ~bitmask;
			rightmask &= ~bitmask;
			if (node->leftnode == NODE && node->left) {
				left = node->left;
				free(node);
				count++;
				node = left;
			} else if (node->rightnode == NODE && node->right) {
				right = node->right;
				free(node);
				count++;
				node = right;
			} else {
				node = NULL;
			}
		}
		/* Propagate keymasks up along singleton chains. */
		node = parent;
		/* Force re-check */
		bitmask = 1 << node->bitnum;
		leftmask &= ~bitmask;
		rightmask &= ~bitmask;
		for (;;) {
			if (node->left && node->right)
				break;
			if (node->left) {
				left = node->left;
				node->keymask |= left->keymask;
				node->keybits |= left->keybits;
			}
			if (node->right) {
				right = node->right;
				node->keymask |= right->keymask;
				node->keybits |= right->keybits;
			}
			node->keymask |= (1 << node->bitnum);
			node = node->parent;
			/* Force re-check */
			bitmask = 1 << node->bitnum;
			leftmask &= ~bitmask;
			rightmask &= ~bitmask;
		}
	advance:
		bitmask = 1 << node->bitnum;
		if ((leftmask & bitmask) == 0 &&
		    node->leftnode == NODE &&
		    node->left) {
			leftmask |= bitmask;
			node = node->left;
		} else if ((rightmask & bitmask) == 0 &&
			   node->rightnode == NODE &&
			   node->right) {
			rightmask |= bitmask;
			node = node->right;
		} else {
			leftmask &= ~bitmask;
			rightmask &= ~bitmask;
			node = node->parent;
		}
	}
	if (verbose > 0)
		printf("Pruned %d nodes\n", count);
}

/*
 * Mark the nodes in the tree that lead to leaves that must be
 * emitted.
 */
static void mark_nodes(struct tree *tree)
{
	struct node *node;
	struct node *n;
	unsigned int leftmask;
	unsigned int rightmask;
	unsigned int bitmask;
	int marked;

	marked = 0;
	if (verbose > 0)
		printf("Marking %s_%x\n", tree->type, tree->maxage);
	if (tree->childnode == LEAF)
		goto done;

	assert(tree->childnode == NODE);
	node = tree->root;
	leftmask = rightmask = 0;
	while (node) {
		bitmask = 1 << node->bitnum;
		if ((leftmask & bitmask) == 0) {
			leftmask |= bitmask;
			if (node->leftnode == LEAF) {
				assert(node->left);
				if (tree->leaf_mark(node->left)) {
					n = node;
					while (n && !n->mark) {
						marked++;
						n->mark = 1;
						n = n->parent;
					}
				}
			} else if (node->left) {
				assert(node->leftnode == NODE);
				node = node->left;
				continue;
			}
		}
		if ((rightmask & bitmask) == 0) {
			rightmask |= bitmask;
			if (node->rightnode == LEAF) {
				assert(node->right);
				if (tree->leaf_mark(node->right)) {
					n = node;
					while (n && !n->mark) {
						marked++;
						n->mark = 1;
						n = n->parent;
					}
				}
			} else if (node->right) {
				assert(node->rightnode == NODE);
				node = node->right;
				continue;
			}
		}
		leftmask &= ~bitmask;
		rightmask &= ~bitmask;
		node = node->parent;
	}

	/* second pass: left siblings and singletons */

	assert(tree->childnode == NODE);
	node = tree->root;
	leftmask = rightmask = 0;
	while (node) {
		bitmask = 1 << node->bitnum;
		if ((leftmask & bitmask) == 0) {
			leftmask |= bitmask;
			if (node->leftnode == LEAF) {
				assert(node->left);
				if (tree->leaf_mark(node->left)) {
					n = node;
					while (n && !n->mark) {
						marked++;
						n->mark = 1;
						n = n->parent;
					}
				}
			} else if (node->left) {
				assert(node->leftnode == NODE);
				node = node->left;
				if (!node->mark && node->parent->mark) {
					marked++;
					node->mark = 1;
				}
				continue;
			}
		}
		if ((rightmask & bitmask) == 0) {
			rightmask |= bitmask;
			if (node->rightnode == LEAF) {
				assert(node->right);
				if (tree->leaf_mark(node->right)) {
					n = node;
					while (n && !n->mark) {
						marked++;
						n->mark = 1;
						n = n->parent;
					}
				}
			} else if (node->right) {
				assert(node->rightnode == NODE);
				node = node->right;
				if (!node->mark && node->parent->mark &&
				    !node->parent->left) {
					marked++;
					node->mark = 1;
				}
				continue;
			}
		}
		leftmask &= ~bitmask;
		rightmask &= ~bitmask;
		node = node->parent;
	}
done:
	if (verbose > 0)
		printf("Marked %d nodes\n", marked);
}

/*
 * Compute the index of each node and leaf, which is the offset in the
 * emitted trie.  These values must be pre-computed because relative
 * offsets between nodes are used to navigate the tree.
 */
static int index_nodes(struct tree *tree, int index)
{
	struct node *node;
	unsigned int leftmask;
	unsigned int rightmask;
	unsigned int bitmask;
	int count;
	int indent;

	/* Align to a cache line (or half a cache line?). */
	while (index % 64)
		index++;
	tree->index = index;
	indent = 1;
	count = 0;

	if (verbose > 0)
		printf("Indexing %s_%x: %d\n", tree->type, tree->maxage, index);
	if (tree->childnode == LEAF) {
		index += tree->leaf_size(tree->root);
		goto done;
	}

	assert(tree->childnode == NODE);
	node = tree->root;
	leftmask = rightmask = 0;
	while (node) {
		if (!node->mark)
			goto skip;
		count++;
		if (node->index != index)
			node->index = index;
		index += node->size;
skip:
		while (node) {
			bitmask = 1 << node->bitnum;
			if (node->mark && (leftmask & bitmask) == 0) {
				leftmask |= bitmask;
				if (node->leftnode == LEAF) {
					assert(node->left);
					*tree->leaf_index(tree, node->left) =
									index;
					index += tree->leaf_size(node->left);
					count++;
				} else if (node->left) {
					assert(node->leftnode == NODE);
					indent += 1;
					node = node->left;
					break;
				}
			}
			if (node->mark && (rightmask & bitmask) == 0) {
				rightmask |= bitmask;
				if (node->rightnode == LEAF) {
					assert(node->right);
					*tree->leaf_index(tree, node->right) = index;
					index += tree->leaf_size(node->right);
					count++;
				} else if (node->right) {
					assert(node->rightnode == NODE);
					indent += 1;
					node = node->right;
					break;
				}
			}
			leftmask &= ~bitmask;
			rightmask &= ~bitmask;
			node = node->parent;
			indent -= 1;
		}
	}
done:
	/* Round up to a multiple of 16 */
	while (index % 16)
		index++;
	if (verbose > 0)
		printf("Final index %d\n", index);
	return index;
}

/*
 * Mark the nodes in a subtree, helper for size_nodes().
 */
static int mark_subtree(struct node *node)
{
	int changed;

	if (!node || node->mark)
		return 0;
	node->mark = 1;
	node->index = node->parent->index;
	changed = 1;
	if (node->leftnode == NODE)
		changed += mark_subtree(node->left);
	if (node->rightnode == NODE)
		changed += mark_subtree(node->right);
	return changed;
}

/*
 * Compute the size of nodes and leaves. We start by assuming that
 * each node needs to store a three-byte offset. The indexes of the
 * nodes are calculated based on that, and then this function is
 * called to see if the sizes of some nodes can be reduced.  This is
 * repeated until no more changes are seen.
 */
static int size_nodes(struct tree *tree)
{
	struct tree *next;
	struct node *node;
	struct node *right;
	struct node *n;
	unsigned int leftmask;
	unsigned int rightmask;
	unsigned int bitmask;
	unsigned int pathbits;
	unsigned int pathmask;
	unsigned int nbit;
	int changed;
	int offset;
	int size;
	int indent;

	indent = 1;
	changed = 0;
	size = 0;

	if (verbose > 0)
		printf("Sizing %s_%x\n", tree->type, tree->maxage);
	if (tree->childnode == LEAF)
		goto done;

	assert(tree->childnode == NODE);
	pathbits = 0;
	pathmask = 0;
	node = tree->root;
	leftmask = rightmask = 0;
	while (node) {
		if (!node->mark)
			goto skip;
		offset = 0;
		if (!node->left || !node->right) {
			size = 1;
		} else {
			if (node->rightnode == NODE) {
				/*
				 * If the right node is not marked,
				 * look for a corresponding node in
				 * the next tree.  Such a node need
				 * not exist.
				 */
				right = node->right;
				next = tree->next;
				while (!right->mark) {
					assert(next);
					n = next->root;
					while (n->bitnum != node->bitnum) {
						nbit = 1 << n->bitnum;
						if (!(pathmask & nbit))
							break;
						if (pathbits & nbit) {
							if (n->rightnode == LEAF)
								break;
							n = n->right;
						} else {
							if (n->leftnode == LEAF)
								break;
							n = n->left;
						}
					}
					if (n->bitnum != node->bitnum)
						break;
					n = n->right;
					right = n;
					next = next->next;
				}
				/* Make sure the right node is marked. */
				if (!right->mark)
					changed += mark_subtree(right);
				offset = right->index - node->index;
			} else {
				offset = *tree->leaf_index(tree, node->right);
				offset -= node->index;
			}
			assert(offset >= 0);
			assert(offset <= 0xffffff);
			if (offset <= 0xff) {
				size = 2;
			} else if (offset <= 0xffff) {
				size = 3;
			} else { /* offset <= 0xffffff */
				size = 4;
			}
		}
		if (node->size != size || node->offset != offset) {
			node->size = size;
			node->offset = offset;
			changed++;
		}
skip:
		while (node) {
			bitmask = 1 << node->bitnum;
			pathmask |= bitmask;
			if (node->mark && (leftmask & bitmask) == 0) {
				leftmask |= bitmask;
				if (node->leftnode == LEAF) {
					assert(node->left);
				} else if (node->left) {
					assert(node->leftnode == NODE);
					indent += 1;
					node = node->left;
					break;
				}
			}
			if (node->mark && (rightmask & bitmask) == 0) {
				rightmask |= bitmask;
				pathbits |= bitmask;
				if (node->rightnode == LEAF) {
					assert(node->right);
				} else if (node->right) {
					assert(node->rightnode == NODE);
					indent += 1;
					node = node->right;
					break;
				}
			}
			leftmask &= ~bitmask;
			rightmask &= ~bitmask;
			pathmask &= ~bitmask;
			pathbits &= ~bitmask;
			node = node->parent;
			indent -= 1;
		}
	}
done:
	if (verbose > 0)
		printf("Found %d changes\n", changed);
	return changed;
}

/*
 * Emit a trie for the given tree into the data array.
 */
static void emit(struct tree *tree, unsigned char *data)
{
	struct node *node;
	unsigned int leftmask;
	unsigned int rightmask;
	unsigned int bitmask;
	int offlen;
	int offset;
	int index;
	int indent;
	int size;
	int bytes;
	int leaves;
	int nodes[4];
	unsigned char byte;

	nodes[0] = nodes[1] = nodes[2] = nodes[3] = 0;
	leaves = 0;
	bytes = 0;
	index = tree->index;
	data += index;
	indent = 1;
	if (verbose > 0)
		printf("Emitting %s_%x\n", tree->type, tree->maxage);
	if (tree->childnode == LEAF) {
		assert(tree->root);
		tree->leaf_emit(tree->root, data);
		size = tree->leaf_size(tree->root);
		index += size;
		leaves++;
		goto done;
	}

	assert(tree->childnode == NODE);
	node = tree->root;
	leftmask = rightmask = 0;
	while (node) {
		if (!node->mark)
			goto skip;
		assert(node->offset != -1);
		assert(node->index == index);

		byte = 0;
		if (node->nextbyte)
			byte |= NEXTBYTE;
		byte |= (node->bitnum & BITNUM);
		if (node->left && node->right) {
			if (node->leftnode == NODE)
				byte |= LEFTNODE;
			if (node->rightnode == NODE)
				byte |= RIGHTNODE;
			if (node->offset <= 0xff)
				offlen = 1;
			else if (node->offset <= 0xffff)
				offlen = 2;
			else
				offlen = 3;
			nodes[offlen]++;
			offset = node->offset;
			byte |= offlen << OFFLEN_SHIFT;
			*data++ = byte;
			index++;
			while (offlen--) {
				*data++ = offset & 0xff;
				index++;
				offset >>= 8;
			}
		} else if (node->left) {
			if (node->leftnode == NODE)
				byte |= TRIENODE;
			nodes[0]++;
			*data++ = byte;
			index++;
		} else if (node->right) {
			byte |= RIGHTNODE;
			if (node->rightnode == NODE)
				byte |= TRIENODE;
			nodes[0]++;
			*data++ = byte;
			index++;
		} else {
			assert(0);
		}
skip:
		while (node) {
			bitmask = 1 << node->bitnum;
			if (node->mark && (leftmask & bitmask) == 0) {
				leftmask |= bitmask;
				if (node->leftnode == LEAF) {
					assert(node->left);
					data = tree->leaf_emit(node->left,
							       data);
					size = tree->leaf_size(node->left);
					index += size;
					bytes += size;
					leaves++;
				} else if (node->left) {
					assert(node->leftnode == NODE);
					indent += 1;
					node = node->left;
					break;
				}
			}
			if (node->mark && (rightmask & bitmask) == 0) {
				rightmask |= bitmask;
				if (node->rightnode == LEAF) {
					assert(node->right);
					data = tree->leaf_emit(node->right,
							       data);
					size = tree->leaf_size(node->right);
					index += size;
					bytes += size;
					leaves++;
				} else if (node->right) {
					assert(node->rightnode == NODE);
					indent += 1;
					node = node->right;
					break;
				}
			}
			leftmask &= ~bitmask;
			rightmask &= ~bitmask;
			node = node->parent;
			indent -= 1;
		}
	}
done:
	if (verbose > 0) {
		printf("Emitted %d (%d) leaves",
			leaves, bytes);
		printf(" %d (%d+%d+%d+%d) nodes",
			nodes[0] + nodes[1] + nodes[2] + nodes[3],
			nodes[0], nodes[1], nodes[2], nodes[3]);
		printf(" %d total\n", index - tree->index);
	}
}

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

/*
 * Unicode data.
 *
 * We need to keep track of the Canonical Combining Class, the Age,
 * and decompositions for a code point.
 *
 * For the Age, we store the index into the ages table.  Effectively
 * this is a generation number that the table maps to a unicode
 * version.
 *
 * The correction field is used to indicate that this entry is in the
 * corrections array, which contains decompositions that were
 * corrected in later revisions.  The value of the correction field is
 * the Unicode version in which the mapping was corrected.
 */
struct unicode_data {
	unsigned int code;
	int ccc;
	int gen;
	int correction;
	unsigned int *utf32nfdi;
	unsigned int *utf32nfdicf;
	char *utf8nfdi;
	char *utf8nfdicf;
};

struct unicode_data unicode_data[0x110000];
struct unicode_data *corrections;
int    corrections_count;

struct tree *nfdi_tree;
struct tree *nfdicf_tree;

struct tree *trees;
int          trees_count;

/*
 * Check the corrections array to see if this entry was corrected at
 * some point.
 */
static struct unicode_data *corrections_lookup(struct unicode_data *u)
{
	int i;

	for (i = 0; i != corrections_count; i++)
		if (u->code == corrections[i].code)
			return &corrections[i];
	return u;
}

static int nfdi_equal(void *l, void *r)
{
	struct unicode_data *left = l;
	struct unicode_data *right = r;

	if (left->gen != right->gen)
		return 0;
	if (left->ccc != right->ccc)
		return 0;
	if (left->utf8nfdi && right->utf8nfdi &&
	    strcmp(left->utf8nfdi, right->utf8nfdi) == 0)
		return 1;
	if (left->utf8nfdi || right->utf8nfdi)
		return 0;
	return 1;
}

static int nfdicf_equal(void *l, void *r)
{
	struct unicode_data *left = l;
	struct unicode_data *right = r;

	if (left->gen != right->gen)
		return 0;
	if (left->ccc != right->ccc)
		return 0;
	if (left->utf8nfdicf && right->utf8nfdicf &&
	    strcmp(left->utf8nfdicf, right->utf8nfdicf) == 0)
		return 1;
	if (left->utf8nfdicf && right->utf8nfdicf)
		return 0;
	if (left->utf8nfdicf || right->utf8nfdicf)
		return 0;
	if (left->utf8nfdi && right->utf8nfdi &&
	    strcmp(left->utf8nfdi, right->utf8nfdi) == 0)
		return 1;
	if (left->utf8nfdi || right->utf8nfdi)
		return 0;
	return 1;
}

static void nfdi_print(void *l, int indent)
{
	struct unicode_data *leaf = l;

	printf("%*sleaf @ %p code %X ccc %d gen %d", indent, "", leaf,
		leaf->code, leaf->ccc, leaf->gen);

	if (leaf->utf8nfdi && leaf->utf8nfdi[0] == HANGUL)
		printf(" nfdi \"%s\"", "HANGUL SYLLABLE");
	else if (leaf->utf8nfdi)
		printf(" nfdi \"%s\"", (const char*)leaf->utf8nfdi);

	printf("\n");
}

static void nfdicf_print(void *l, int indent)
{
	struct unicode_data *leaf = l;

	printf("%*sleaf @ %p code %X ccc %d gen %d", indent, "", leaf,
		leaf->code, leaf->ccc, leaf->gen);

	if (leaf->utf8nfdicf)
		printf(" nfdicf \"%s\"", (const char*)leaf->utf8nfdicf);
	else if (leaf->utf8nfdi && leaf->utf8nfdi[0] == HANGUL)
		printf(" nfdi \"%s\"", "HANGUL SYLLABLE");
	else if (leaf->utf8nfdi)
		printf(" nfdi \"%s\"", (const char*)leaf->utf8nfdi);
	printf("\n");
}

static int nfdi_mark(void *l)
{
	return 1;
}

static int nfdicf_mark(void *l)
{
	struct unicode_data *leaf = l;

	if (leaf->utf8nfdicf)
		return 1;
	return 0;
}

static int correction_mark(void *l)
{
	struct unicode_data *leaf = l;

	return leaf->correction;
}

static int nfdi_size(void *l)
{
	struct unicode_data *leaf = l;
	int size = 2;

	if (HANGUL_SYLLABLE(leaf->code))
		size += 1;
	else if (leaf->utf8nfdi)
		size += strlen(leaf->utf8nfdi) + 1;
	return size;
}

static int nfdicf_size(void *l)
{
	struct unicode_data *leaf = l;
	int size = 2;

	if (HANGUL_SYLLABLE(leaf->code))
		size += 1;
	else if (leaf->utf8nfdicf)
		size += strlen(leaf->utf8nfdicf) + 1;
	else if (leaf->utf8nfdi)
		size += strlen(leaf->utf8nfdi) + 1;
	return size;
}

static int *nfdi_index(struct tree *tree, void *l)
{
	struct unicode_data *leaf = l;

	return &tree->leafindex[leaf->code];
}

static int *nfdicf_index(struct tree *tree, void *l)
{
	struct unicode_data *leaf = l;

	return &tree->leafindex[leaf->code];
}

static unsigned char *nfdi_emit(void *l, unsigned char *data)
{
	struct unicode_data *leaf = l;
	unsigned char *s;

	*data++ = leaf->gen;

	if (HANGUL_SYLLABLE(leaf->code)) {
		*data++ = DECOMPOSE;
		*data++ = HANGUL;
	} else if (leaf->utf8nfdi) {
		*data++ = DECOMPOSE;
		s = (unsigned char*)leaf->utf8nfdi;
		while ((*data++ = *s++) != 0)
			;
	} else {
		*data++ = leaf->ccc;
	}
	return data;
}

static unsigned char *nfdicf_emit(void *l, unsigned char *data)
{
	struct unicode_data *leaf = l;
	unsigned char *s;

	*data++ = leaf->gen;

	if (HANGUL_SYLLABLE(leaf->code)) {
		*data++ = DECOMPOSE;
		*data++ = HANGUL;
	} else if (leaf->utf8nfdicf) {
		*data++ = DECOMPOSE;
		s = (unsigned char*)leaf->utf8nfdicf;
		while ((*data++ = *s++) != 0)
			;
	} else if (leaf->utf8nfdi) {
		*data++ = DECOMPOSE;
		s = (unsigned char*)leaf->utf8nfdi;
		while ((*data++ = *s++) != 0)
			;
	} else {
		*data++ = leaf->ccc;
	}
	return data;
}

static void utf8_create(struct unicode_data *data)
{
	char utf[18*4+1];
	char *u;
	unsigned int *um;
	int i;

	if (data->utf8nfdi) {
		assert(data->utf8nfdi[0] == HANGUL);
		return;
	}

	u = utf;
	um = data->utf32nfdi;
	if (um) {
		for (i = 0; um[i]; i++)
			u += utf8encode(u, um[i]);
		*u = '\0';
		data->utf8nfdi = strdup(utf);
	}
	u = utf;
	um = data->utf32nfdicf;
	if (um) {
		for (i = 0; um[i]; i++)
			u += utf8encode(u, um[i]);
		*u = '\0';
		if (!data->utf8nfdi || strcmp(data->utf8nfdi, utf))
			data->utf8nfdicf = strdup(utf);
	}
}

static void utf8_init(void)
{
	unsigned int unichar;
	int i;

	for (unichar = 0; unichar != 0x110000; unichar++)
		utf8_create(&unicode_data[unichar]);

	for (i = 0; i != corrections_count; i++)
		utf8_create(&corrections[i]);
}

static void trees_init(void)
{
	struct unicode_data *data;
	unsigned int maxage;
	unsigned int nextage;
	int count;
	int i;
	int j;

	/* Count the number of different ages. */
	count = 0;
	nextage = (unsigned int)-1;
	do {
		maxage = nextage;
		nextage = 0;
		for (i = 0; i <= corrections_count; i++) {
			data = &corrections[i];
			if (nextage < data->correction &&
			    data->correction < maxage)
				nextage = data->correction;
		}
		count++;
	} while (nextage);

	/* Two trees per age: nfdi and nfdicf */
	trees_count = count * 2;
	trees = calloc(trees_count, sizeof(struct tree));

	/* Assign ages to the trees. */
	count = trees_count;
	nextage = (unsigned int)-1;
	do {
		maxage = nextage;
		trees[--count].maxage = maxage;
		trees[--count].maxage = maxage;
		nextage = 0;
		for (i = 0; i <= corrections_count; i++) {
			data = &corrections[i];
			if (nextage < data->correction &&
			    data->correction < maxage)
				nextage = data->correction;
		}
	} while (nextage);

	/* The ages assigned above are off by one. */
	for (i = 0; i != trees_count; i++) {
		j = 0;
		while (ages[j] < trees[i].maxage)
			j++;
		trees[i].maxage = ages[j-1];
	}

	/* Set up the forwarding between trees. */
	trees[trees_count-2].next = &trees[trees_count-1];
	trees[trees_count-1].leaf_mark = nfdi_mark;
	trees[trees_count-2].leaf_mark = nfdicf_mark;
	for (i = 0; i != trees_count-2; i += 2) {
		trees[i].next = &trees[trees_count-2];
		trees[i].leaf_mark = correction_mark;
		trees[i+1].next = &trees[trees_count-1];
		trees[i+1].leaf_mark = correction_mark;
	}

	/* Assign the callouts. */
	for (i = 0; i != trees_count; i += 2) {
		trees[i].type = "nfdicf";
		trees[i].leaf_equal = nfdicf_equal;
		trees[i].leaf_print = nfdicf_print;
		trees[i].leaf_size = nfdicf_size;
		trees[i].leaf_index = nfdicf_index;
		trees[i].leaf_emit = nfdicf_emit;

		trees[i+1].type = "nfdi";
		trees[i+1].leaf_equal = nfdi_equal;
		trees[i+1].leaf_print = nfdi_print;
		trees[i+1].leaf_size = nfdi_size;
		trees[i+1].leaf_index = nfdi_index;
		trees[i+1].leaf_emit = nfdi_emit;
	}

	/* Finish init. */
	for (i = 0; i != trees_count; i++)
		trees[i].childnode = NODE;
}

static void trees_populate(void)
{
	struct unicode_data *data;
	unsigned int unichar;
	char keyval[4];
	int keylen;
	int i;

	for (i = 0; i != trees_count; i++) {
		if (verbose > 0) {
			printf("Populating %s_%x\n",
				trees[i].type, trees[i].maxage);
		}
		for (unichar = 0; unichar != 0x110000; unichar++) {
			if (unicode_data[unichar].gen < 0)
				continue;
			keylen = utf8encode(keyval, unichar);
			data = corrections_lookup(&unicode_data[unichar]);
			if (data->correction <= trees[i].maxage)
				data = &unicode_data[unichar];
			insert(&trees[i], keyval, keylen, data);
		}
	}
}

static void trees_reduce(void)
{
	int i;
	int size;
	int changed;

	for (i = 0; i != trees_count; i++)
		prune(&trees[i]);
	for (i = 0; i != trees_count; i++)
		mark_nodes(&trees[i]);
	do {
		size = 0;
		for (i = 0; i != trees_count; i++)
			size = index_nodes(&trees[i], size);
		changed = 0;
		for (i = 0; i != trees_count; i++)
			changed += size_nodes(&trees[i]);
	} while (changed);

	utf8data = calloc(size, 1);
	utf8data_size = size;
	for (i = 0; i != trees_count; i++)
		emit(&trees[i], utf8data);

	if (verbose > 0) {
		for (i = 0; i != trees_count; i++) {
			printf("%s_%x idx %d\n",
				trees[i].type, trees[i].maxage, trees[i].index);
		}
	}

	nfdi = utf8data + trees[trees_count-1].index;
	nfdicf = utf8data + trees[trees_count-2].index;

	nfdi_tree = &trees[trees_count-1];
	nfdicf_tree = &trees[trees_count-2];
}

static void verify(struct tree *tree)
{
	struct unicode_data *data;
	utf8leaf_t	*leaf;
	unsigned int	unichar;
	char		key[4];
	unsigned char	hangul[UTF8HANGULLEAF];
	int		report;
	int		nocf;

	if (verbose > 0)
		printf("Verifying %s_%x\n", tree->type, tree->maxage);
	nocf = strcmp(tree->type, "nfdicf");

	for (unichar = 0; unichar != 0x110000; unichar++) {
		report = 0;
		data = corrections_lookup(&unicode_data[unichar]);
		if (data->correction <= tree->maxage)
			data = &unicode_data[unichar];
		utf8encode(key,unichar);
		leaf = utf8lookup(tree, hangul, key);

		if (!leaf) {
			if (data->gen != -1)
				report++;
			if (unichar < 0xd800 || unichar > 0xdfff)
				report++;
		} else {
			if (unichar >= 0xd800 && unichar <= 0xdfff)
				report++;
			if (data->gen == -1)
				report++;
			if (data->gen != LEAF_GEN(leaf))
				report++;
			if (LEAF_CCC(leaf) == DECOMPOSE) {
				if (HANGUL_SYLLABLE(data->code)) {
					if (data->utf8nfdi[0] != HANGUL)
						report++;
				} else if (nocf) {
					if (!data->utf8nfdi) {
						report++;
					} else if (strcmp(data->utf8nfdi,
							  LEAF_STR(leaf))) {
						report++;
					}
				} else {
					if (!data->utf8nfdicf &&
					    !data->utf8nfdi) {
						report++;
					} else if (data->utf8nfdicf) {
						if (strcmp(data->utf8nfdicf,
							   LEAF_STR(leaf)))
							report++;
					} else if (strcmp(data->utf8nfdi,
							  LEAF_STR(leaf))) {
						report++;
					}
				}
			} else if (data->ccc != LEAF_CCC(leaf)) {
				report++;
			}
		}
		if (report) {
			printf("%X code %X gen %d ccc %d"
				" nfdi -> \"%s\"",
				unichar, data->code, data->gen,
				data->ccc,
				data->utf8nfdi);
			if (leaf) {
				printf(" gen %d ccc %d"
					" nfdi -> \"%s\"",
					LEAF_GEN(leaf),
					LEAF_CCC(leaf),
					LEAF_CCC(leaf) == DECOMPOSE ?
						LEAF_STR(leaf) : "");
			}
			printf("\n");
		}
	}
}

static void trees_verify(void)
{
	int i;

	for (i = 0; i != trees_count; i++)
		verify(&trees[i]);
}

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

static void help(void)
{
	printf("Usage: %s [options]\n", argv0);
	printf("\n");
	printf("This program creates an a data trie used for parsing and\n");
	printf("normalization of UTF-8 strings. The trie is derived from\n");
	printf("a set of input files from the Unicode character database\n");
	printf("found at: http://www.unicode.org/Public/UCD/latest/ucd/\n");
	printf("\n");
	printf("The generated tree supports two normalization forms:\n");
	printf("\n");
	printf("\tnfdi:\n");
	printf("\t- Apply unicode normalization form NFD.\n");
	printf("\t- Remove any Default_Ignorable_Code_Point.\n");
	printf("\n");
	printf("\tnfdicf:\n");
	printf("\t- Apply unicode normalization form NFD.\n");
	printf("\t- Remove any Default_Ignorable_Code_Point.\n");
	printf("\t- Apply a full casefold (C + F).\n");
	printf("\n");
	printf("These forms were chosen as being most useful when dealing\n");
	printf("with file names: NFD catches most cases where characters\n");
	printf("should be considered equivalent. The ignorables are mostly\n");
	printf("invisible, making names hard to type.\n");
	printf("\n");
	printf("The options to specify the files to be used are listed\n");
	printf("below with their default values, which are the names used\n");
	printf("by version 11.0.0 of the Unicode Character Database.\n");
	printf("\n");
	printf("The input files:\n");
	printf("\t-a %s\n", AGE_NAME);
	printf("\t-c %s\n", CCC_NAME);
	printf("\t-p %s\n", PROP_NAME);
	printf("\t-d %s\n", DATA_NAME);
	printf("\t-f %s\n", FOLD_NAME);
	printf("\t-n %s\n", NORM_NAME);
	printf("\n");
	printf("Additionally, the generated tables are tested using:\n");
	printf("\t-t %s\n", TEST_NAME);
	printf("\n");
	printf("Finally, the output file:\n");
	printf("\t-o %s\n", UTF8_NAME);
	printf("\n");
}

static void usage(void)
{
	help();
	exit(1);
}

static void open_fail(const char *name, int error)
{
	printf("Error %d opening %s: %s\n", error, name, strerror(error));
	exit(1);
}

static void file_fail(const char *filename)
{
	printf("Error parsing %s\n", filename);
	exit(1);
}

static void line_fail(const char *filename, const char *line)
{
	printf("Error parsing %s:%s\n", filename, line);
	exit(1);
}

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

static void print_utf32(unsigned int *utf32str)
{
	int	i;

	for (i = 0; utf32str[i]; i++)
		printf(" %X", utf32str[i]);
}

static void print_utf32nfdi(unsigned int unichar)
{
	printf(" %X ->", unichar);
	print_utf32(unicode_data[unichar].utf32nfdi);
	printf("\n");
}

static void print_utf32nfdicf(unsigned int unichar)
{
	printf(" %X ->", unichar);
	print_utf32(unicode_data[unichar].utf32nfdicf);
	printf("\n");
}

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

static void age_init(void)
{
	FILE *file;
	unsigned int first;
	unsigned int last;
	unsigned int unichar;
	unsigned int major;
	unsigned int minor;
	unsigned int revision;
	int gen;
	int count;
	int ret;

	if (verbose > 0)
		printf("Parsing %s\n", age_name);

	file = fopen(age_name, "r");
	if (!file)
		open_fail(age_name, errno);
	count = 0;

	gen = 0;
	while (fgets(line, LINESIZE, file)) {
		ret = sscanf(line, "# Age=V%d_%d_%d",
				&major, &minor, &revision);
		if (ret == 3) {
			ages_count++;
			if (verbose > 1)
				printf(" Age V%d_%d_%d\n",
					major, minor, revision);
			if (!age_valid(major, minor, revision))
				line_fail(age_name, line);
			continue;
		}
		ret = sscanf(line, "# Age=V%d_%d", &major, &minor);
		if (ret == 2) {
			ages_count++;
			if (verbose > 1)
				printf(" Age V%d_%d\n", major, minor);
			if (!age_valid(major, minor, 0))
				line_fail(age_name, line);
			continue;
		}
	}

	/* We must have found something above. */
	if (verbose > 1)
		printf("%d age entries\n", ages_count);
	if (ages_count == 0 || ages_count > MAXGEN)
		file_fail(age_name);

	/* There is a 0 entry. */
	ages_count++;
	ages = calloc(ages_count + 1, sizeof(*ages));
	/* And a guard entry. */
	ages[ages_count] = (unsigned int)-1;

	rewind(file);
	count = 0;
	gen = 0;
	while (fgets(line, LINESIZE, file)) {
		ret = sscanf(line, "# Age=V%d_%d_%d",
				&major, &minor, &revision);
		if (ret == 3) {
			ages[++gen] =
				UNICODE_AGE(major, minor, revision);
			if (verbose > 1)
				printf(" Age V%d_%d_%d = gen %d\n",
					major, minor, revision, gen);
			if (!age_valid(major, minor, revision))
				line_fail(age_name, line);
			continue;
		}
		ret = sscanf(line, "# Age=V%d_%d", &major, &minor);
		if (ret == 2) {
			ages[++gen] = UNICODE_AGE(major, minor, 0);
			if (verbose > 1)
				printf(" Age V%d_%d = %d\n",
					major, minor, gen);
			if (!age_valid(major, minor, 0))
				line_fail(age_name, line);
			continue;
		}
		ret = sscanf(line, "%X..%X ; %d.%d #",
			     &first, &last, &major, &minor);
		if (ret == 4) {
			for (unichar = first; unichar <= last; unichar++)
				unicode_data[unichar].gen = gen;
			count += 1 + last - first;
			if (verbose > 1)
				printf("  %X..%X gen %d\n", first, last, gen);
			if (!utf32valid(first) || !utf32valid(last))
				line_fail(age_name, line);
			continue;
		}
		ret = sscanf(line, "%X ; %d.%d #", &unichar, &major, &minor);
		if (ret == 3) {
			unicode_data[unichar].gen = gen;
			count++;
			if (verbose > 1)
				printf("  %X gen %d\n", unichar, gen);
			if (!utf32valid(unichar))
				line_fail(age_name, line);
			continue;
		}
	}
	unicode_maxage = ages[gen];
	fclose(file);

	/* Nix surrogate block */
	if (verbose > 1)
		printf(" Removing surrogate block D800..DFFF\n");
	for (unichar = 0xd800; unichar <= 0xdfff; unichar++)
		unicode_data[unichar].gen = -1;

	if (verbose > 0)
	        printf("Found %d entries\n", count);
	if (count == 0)
		file_fail(age_name);
}

static void ccc_init(void)
{
	FILE *file;
	unsigned int first;
	unsigned int last;
	unsigned int unichar;
	unsigned int value;
	int count;
	int ret;

	if (verbose > 0)
		printf("Parsing %s\n", ccc_name);

	file = fopen(ccc_name, "r");
	if (!file)
		open_fail(ccc_name, errno);

	count = 0;
	while (fgets(line, LINESIZE, file)) {
		ret = sscanf(line, "%X..%X ; %d #", &first, &last, &value);
		if (ret == 3) {
			for (unichar = first; unichar <= last; unichar++) {
				unicode_data[unichar].ccc = value;
                                count++;
			}
			if (verbose > 1)
				printf(" %X..%X ccc %d\n", first, last, value);
			if (!utf32valid(first) || !utf32valid(last))
				line_fail(ccc_name, line);
			continue;
		}
		ret = sscanf(line, "%X ; %d #", &unichar, &value);
		if (ret == 2) {
			unicode_data[unichar].ccc = value;
                        count++;
			if (verbose > 1)
				printf(" %X ccc %d\n", unichar, value);
			if (!utf32valid(unichar))
				line_fail(ccc_name, line);
			continue;
		}
	}
	fclose(file);

	if (verbose > 0)
		printf("Found %d entries\n", count);
	if (count == 0)
		file_fail(ccc_name);
}

static int ignore_compatibility_form(char *type)
{
	int i;
	char *ignored_types[] = {"font", "noBreak", "initial", "medial",
				 "final", "isolated", "circle", "super",
				 "sub", "vertical", "wide", "narrow",
				 "small", "square", "fraction", "compat"};

	for (i = 0 ; i < ARRAY_SIZE(ignored_types); i++)
		if (strcmp(type, ignored_types[i]) == 0)
			return 1;
	return 0;
}

static void nfdi_init(void)
{
	FILE *file;
	unsigned int unichar;
	unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */
	char *s;
	char *type;
	unsigned int *um;
	int count;
	int i;
	int ret;

	if (verbose > 0)
		printf("Parsing %s\n", data_name);
	file = fopen(data_name, "r");
	if (!file)
		open_fail(data_name, errno);

	count = 0;
	while (fgets(line, LINESIZE, file)) {
		ret = sscanf(line, "%X;%*[^;];%*[^;];%*[^;];%*[^;];%[^;];",
			     &unichar, buf0);
		if (ret != 2)
			continue;
		if (!utf32valid(unichar))
			line_fail(data_name, line);

		s = buf0;
		/* skip over <tag> */
		if (*s == '<') {
			type = ++s;
			while (*++s != '>');
			*s++ = '\0';
			if(ignore_compatibility_form(type))
				continue;
		}
		/* decode the decomposition into UTF-32 */
		i = 0;
		while (*s) {
			mapping[i] = strtoul(s, &s, 16);
			if (!utf32valid(mapping[i]))
				line_fail(data_name, line);
			i++;
		}
		mapping[i++] = 0;

		um = malloc(i * sizeof(unsigned int));
		memcpy(um, mapping, i * sizeof(unsigned int));
		unicode_data[unichar].utf32nfdi = um;

		if (verbose > 1)
			print_utf32nfdi(unichar);
		count++;
	}
	fclose(file);
	if (verbose > 0)
		printf("Found %d entries\n", count);
	if (count == 0)
		file_fail(data_name);
}

static void nfdicf_init(void)
{
	FILE *file;
	unsigned int unichar;
	unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */
	char status;
	char *s;
	unsigned int *um;
	int i;
	int count;
	int ret;

	if (verbose > 0)
		printf("Parsing %s\n", fold_name);
	file = fopen(fold_name, "r");
	if (!file)
		open_fail(fold_name, errno);

	count = 0;
	while (fgets(line, LINESIZE, file)) {
		ret = sscanf(line, "%X; %c; %[^;];", &unichar, &status, buf0);
		if (ret != 3)
			continue;
		if (!utf32valid(unichar))
			line_fail(fold_name, line);
		/* Use the C+F casefold. */
		if (status != 'C' && status != 'F')
			continue;
		s = buf0;
		if (*s == '<')
			while (*s++ != ' ')
				;
		i = 0;
		while (*s) {
			mapping[i] = strtoul(s, &s, 16);
			if (!utf32valid(mapping[i]))
				line_fail(fold_name, line);
			i++;
		}
		mapping[i++] = 0;

		um = malloc(i * sizeof(unsigned int));
		memcpy(um, mapping, i * sizeof(unsigned int));
		unicode_data[unichar].utf32nfdicf = um;

		if (verbose > 1)
			print_utf32nfdicf(unichar);
		count++;
	}
	fclose(file);
	if (verbose > 0)
		printf("Found %d entries\n", count);
	if (count == 0)
		file_fail(fold_name);
}

static void ignore_init(void)
{
	FILE *file;
	unsigned int unichar;
	unsigned int first;
	unsigned int last;
	unsigned int *um;
	int count;
	int ret;

	if (verbose > 0)
		printf("Parsing %s\n", prop_name);
	file = fopen(prop_name, "r");
	if (!file)
		open_fail(prop_name, errno);
	assert(file);
	count = 0;
	while (fgets(line, LINESIZE, file)) {
		ret = sscanf(line, "%X..%X ; %s # ", &first, &last, buf0);
		if (ret == 3) {
			if (strcmp(buf0, "Default_Ignorable_Code_Point"))
				continue;
			if (!utf32valid(first) || !utf32valid(last))
				line_fail(prop_name, line);
			for (unichar = first; unichar <= last; unichar++) {
				free(unicode_data[unichar].utf32nfdi);
				um = malloc(sizeof(unsigned int));
				*um = 0;
				unicode_data[unichar].utf32nfdi = um;
				free(unicode_data[unichar].utf32nfdicf);
				um = malloc(sizeof(unsigned int));
				*um = 0;
				unicode_data[unichar].utf32nfdicf = um;
				count++;
			}
			if (verbose > 1)
				printf(" %X..%X Default_Ignorable_Code_Point\n",
					first, last);
			continue;
		}
		ret = sscanf(line, "%X ; %s # ", &unichar, buf0);
		if (ret == 2) {
			if (strcmp(buf0, "Default_Ignorable_Code_Point"))
				continue;
			if (!utf32valid(unichar))
				line_fail(prop_name, line);
			free(unicode_data[unichar].utf32nfdi);
			um = malloc(sizeof(unsigned int));
			*um = 0;
			unicode_data[unichar].utf32nfdi = um;
			free(unicode_data[unichar].utf32nfdicf);
			um = malloc(sizeof(unsigned int));
			*um = 0;
			unicode_data[unichar].utf32nfdicf = um;
			if (verbose > 1)
				printf(" %X Default_Ignorable_Code_Point\n",
					unichar);
			count++;
			continue;
		}
	}
	fclose(file);

	if (verbose > 0)
		printf("Found %d entries\n", count);
	if (count == 0)
		file_fail(prop_name);
}

static void corrections_init(void)
{
	FILE *file;
	unsigned int unichar;
	unsigned int major;
	unsigned int minor;
	unsigned int revision;
	unsigned int age;
	unsigned int *um;
	unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */
	char *s;
	int i;
	int count;
	int ret;

	if (verbose > 0)
		printf("Parsing %s\n", norm_name);
	file = fopen(norm_name, "r");
	if (!file)
		open_fail(norm_name, errno);

	count = 0;
	while (fgets(line, LINESIZE, file)) {
		ret = sscanf(line, "%X;%[^;];%[^;];%d.%d.%d #",
				&unichar, buf0, buf1,
				&major, &minor, &revision);
		if (ret != 6)
			continue;
		if (!utf32valid(unichar) || !age_valid(major, minor, revision))
			line_fail(norm_name, line);
		count++;
	}
	corrections = calloc(count, sizeof(struct unicode_data));
	corrections_count = count;
	rewind(file);

	count = 0;
	while (fgets(line, LINESIZE, file)) {
		ret = sscanf(line, "%X;%[^;];%[^;];%d.%d.%d #",
				&unichar, buf0, buf1,
				&major, &minor, &revision);
		if (ret != 6)
			continue;
		if (!utf32valid(unichar) || !age_valid(major, minor, revision))
			line_fail(norm_name, line);
		corrections[count] = unicode_data[unichar];
		assert(corrections[count].code == unichar);
		age = UNICODE_AGE(major, minor, revision);
		corrections[count].correction = age;

		i = 0;
		s = buf0;
		while (*s) {
			mapping[i] = strtoul(s, &s, 16);
			if (!utf32valid(mapping[i]))
				line_fail(norm_name, line);
			i++;
		}
		mapping[i++] = 0;

		um = malloc(i * sizeof(unsigned int));
		memcpy(um, mapping, i * sizeof(unsigned int));
		corrections[count].utf32nfdi = um;

		if (verbose > 1)
			printf(" %X -> %s -> %s V%d_%d_%d\n",
				unichar, buf0, buf1, major, minor, revision);
		count++;
	}
	fclose(file);

	if (verbose > 0)
	        printf("Found %d entries\n", count);
	if (count == 0)
		file_fail(norm_name);
}

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

/*
 * Hangul decomposition (algorithm from Section 3.12 of Unicode 6.3.0)
 *
 * AC00;<Hangul Syllable, First>;Lo;0;L;;;;;N;;;;;
 * D7A3;<Hangul Syllable, Last>;Lo;0;L;;;;;N;;;;;
 *
 * SBase = 0xAC00
 * LBase = 0x1100
 * VBase = 0x1161
 * TBase = 0x11A7
 * LCount = 19
 * VCount = 21
 * TCount = 28
 * NCount = 588 (VCount * TCount)
 * SCount = 11172 (LCount * NCount)
 *
 * Decomposition:
 *   SIndex = s - SBase
 *
 * LV (Canonical/Full)
 *   LIndex = SIndex / NCount
 *   VIndex = (Sindex % NCount) / TCount
 *   LPart = LBase + LIndex
 *   VPart = VBase + VIndex
 *
 * LVT (Canonical)
 *   LVIndex = (SIndex / TCount) * TCount
 *   TIndex = (Sindex % TCount)
 *   LVPart = SBase + LVIndex
 *   TPart = TBase + TIndex
 *
 * LVT (Full)
 *   LIndex = SIndex / NCount
 *   VIndex = (Sindex % NCount) / TCount
 *   TIndex = (Sindex % TCount)
 *   LPart = LBase + LIndex
 *   VPart = VBase + VIndex
 *   if (TIndex == 0) {
 *          d = <LPart, VPart>
 *   } else {
 *          TPart = TBase + TIndex
 *          d = <LPart, VPart, TPart>
 *   }
 *
 */

static void hangul_decompose(void)
{
	unsigned int sb = 0xAC00;
	unsigned int lb = 0x1100;
	unsigned int vb = 0x1161;
	unsigned int tb = 0x11a7;
	/* unsigned int lc = 19; */
	unsigned int vc = 21;
	unsigned int tc = 28;
	unsigned int nc = (vc * tc);
	/* unsigned int sc = (lc * nc); */
	unsigned int unichar;
	unsigned int mapping[4];
	unsigned int *um;
        int count;
	int i;

	if (verbose > 0)
		printf("Decomposing hangul\n");
	/* Hangul */
	count = 0;
	for (unichar = 0xAC00; unichar <= 0xD7A3; unichar++) {
		unsigned int si = unichar - sb;
		unsigned int li = si / nc;
		unsigned int vi = (si % nc) / tc;
		unsigned int ti = si % tc;

		i = 0;
		mapping[i++] = lb + li;
		mapping[i++] = vb + vi;
		if (ti)
			mapping[i++] = tb + ti;
		mapping[i++] = 0;

		assert(!unicode_data[unichar].utf32nfdi);
		um = malloc(i * sizeof(unsigned int));
		memcpy(um, mapping, i * sizeof(unsigned int));
		unicode_data[unichar].utf32nfdi = um;

		assert(!unicode_data[unichar].utf32nfdicf);
		um = malloc(i * sizeof(unsigned int));
		memcpy(um, mapping, i * sizeof(unsigned int));
		unicode_data[unichar].utf32nfdicf = um;

		/*
		 * Add a cookie as a reminder that the hangul syllable
		 * decompositions must not be stored in the generated
		 * trie.
		 */
		unicode_data[unichar].utf8nfdi = malloc(2);
		unicode_data[unichar].utf8nfdi[0] = HANGUL;
		unicode_data[unichar].utf8nfdi[1] = '\0';

		if (verbose > 1)
			print_utf32nfdi(unichar);

		count++;
	}
	if (verbose > 0)
		printf("Created %d entries\n", count);
}

static void nfdi_decompose(void)
{
	unsigned int unichar;
	unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */
	unsigned int *um;
	unsigned int *dc;
	int count;
	int i;
	int j;
	int ret;

	if (verbose > 0)
		printf("Decomposing nfdi\n");

	count = 0;
	for (unichar = 0; unichar != 0x110000; unichar++) {
		if (!unicode_data[unichar].utf32nfdi)
			continue;
		for (;;) {
			ret = 1;
			i = 0;
			um = unicode_data[unichar].utf32nfdi;
			while (*um) {
				dc = unicode_data[*um].utf32nfdi;
				if (dc) {
					for (j = 0; dc[j]; j++)
						mapping[i++] = dc[j];
					ret = 0;
				} else {
					mapping[i++] = *um;
				}
				um++;
			}
			mapping[i++] = 0;
			if (ret)
				break;
			free(unicode_data[unichar].utf32nfdi);
			um = malloc(i * sizeof(unsigned int));
			memcpy(um, mapping, i * sizeof(unsigned int));
			unicode_data[unichar].utf32nfdi = um;
		}
		/* Add this decomposition to nfdicf if there is no entry. */
		if (!unicode_data[unichar].utf32nfdicf) {
			um = malloc(i * sizeof(unsigned int));
			memcpy(um, mapping, i * sizeof(unsigned int));
			unicode_data[unichar].utf32nfdicf = um;
		}
		if (verbose > 1)
			print_utf32nfdi(unichar);
		count++;
	}
	if (verbose > 0)
		printf("Processed %d entries\n", count);
}

static void nfdicf_decompose(void)
{
	unsigned int unichar;
	unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */
	unsigned int *um;
	unsigned int *dc;
	int count;
	int i;
	int j;
	int ret;

	if (verbose > 0)
		printf("Decomposing nfdicf\n");
	count = 0;
	for (unichar = 0; unichar != 0x110000; unichar++) {
		if (!unicode_data[unichar].utf32nfdicf)
			continue;
		for (;;) {
			ret = 1;
			i = 0;
			um = unicode_data[unichar].utf32nfdicf;
			while (*um) {
				dc = unicode_data[*um].utf32nfdicf;
				if (dc) {
					for (j = 0; dc[j]; j++)
						mapping[i++] = dc[j];
					ret = 0;
				} else {
					mapping[i++] = *um;
				}
				um++;
			}
			mapping[i++] = 0;
			if (ret)
				break;
			free(unicode_data[unichar].utf32nfdicf);
			um = malloc(i * sizeof(unsigned int));
			memcpy(um, mapping, i * sizeof(unsigned int));
			unicode_data[unichar].utf32nfdicf = um;
		}
		if (verbose > 1)
			print_utf32nfdicf(unichar);
		count++;
	}
	if (verbose > 0)
		printf("Processed %d entries\n", count);
}

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

int utf8agemax(struct tree *, const char *);
int utf8nagemax(struct tree *, const char *, size_t);
int utf8agemin(struct tree *, const char *);
int utf8nagemin(struct tree *, const char *, size_t);
ssize_t utf8len(struct tree *, const char *);
ssize_t utf8nlen(struct tree *, const char *, size_t);
struct utf8cursor;
int utf8cursor(struct utf8cursor *, struct tree *, const char *);
int utf8ncursor(struct utf8cursor *, struct tree *, const char *, size_t);
int utf8byte(struct utf8cursor *);

/*
 * Hangul decomposition (algorithm from Section 3.12 of Unicode 6.3.0)
 *
 * AC00;<Hangul Syllable, First>;Lo;0;L;;;;;N;;;;;
 * D7A3;<Hangul Syllable, Last>;Lo;0;L;;;;;N;;;;;
 *
 * SBase = 0xAC00
 * LBase = 0x1100
 * VBase = 0x1161
 * TBase = 0x11A7
 * LCount = 19
 * VCount = 21
 * TCount = 28
 * NCount = 588 (VCount * TCount)
 * SCount = 11172 (LCount * NCount)
 *
 * Decomposition:
 *   SIndex = s - SBase
 *
 * LV (Canonical/Full)
 *   LIndex = SIndex / NCount
 *   VIndex = (Sindex % NCount) / TCount
 *   LPart = LBase + LIndex
 *   VPart = VBase + VIndex
 *
 * LVT (Canonical)
 *   LVIndex = (SIndex / TCount) * TCount
 *   TIndex = (Sindex % TCount)
 *   LVPart = SBase + LVIndex
 *   TPart = TBase + TIndex
 *
 * LVT (Full)
 *   LIndex = SIndex / NCount
 *   VIndex = (Sindex % NCount) / TCount
 *   TIndex = (Sindex % TCount)
 *   LPart = LBase + LIndex
 *   VPart = VBase + VIndex
 *   if (TIndex == 0) {
 *          d = <LPart, VPart>
 *   } else {
 *          TPart = TBase + TIndex
 *          d = <LPart, VPart, TPart>
 *   }
 */

/* Constants */
#define SB	(0xAC00)
#define LB	(0x1100)
#define VB	(0x1161)
#define TB	(0x11A7)
#define LC	(19)
#define VC	(21)
#define TC	(28)
#define NC	(VC * TC)
#define SC	(LC * NC)

/* Algorithmic decomposition of hangul syllable. */
static utf8leaf_t *utf8hangul(const char *str, unsigned char *hangul)
{
	unsigned int	si;
	unsigned int	li;
	unsigned int	vi;
	unsigned int	ti;
	unsigned char	*h;

	/* Calculate the SI, LI, VI, and TI values. */
	si = utf8decode(str) - SB;
	li = si / NC;
	vi = (si % NC) / TC;
	ti = si % TC;

	/* Fill in base of leaf. */
	h = hangul;
	LEAF_GEN(h) = 2;
	LEAF_CCC(h) = DECOMPOSE;
	h += 2;

	/* Add LPart, a 3-byte UTF-8 sequence. */
	h += utf8encode((char *)h, li + LB);

	/* Add VPart, a 3-byte UTF-8 sequence. */
	h += utf8encode((char *)h, vi + VB);

	/* Add TPart if required, also a 3-byte UTF-8 sequence. */
	if (ti)
		h += utf8encode((char *)h, ti + TB);

	/* Terminate string. */
	h[0] = '\0';

	return hangul;
}

/*
 * Use trie to scan s, touching at most len bytes.
 * Returns the leaf if one exists, NULL otherwise.
 *
 * A non-NULL return guarantees that the UTF-8 sequence starting at s
 * is well-formed and corresponds to a known unicode code point.  The
 * shorthand for this will be "is valid UTF-8 unicode".
 */
static utf8leaf_t *utf8nlookup(struct tree *tree, unsigned char *hangul,
			       const char *s, size_t len)
{
	utf8trie_t	*trie;
	int		offlen;
	int		offset;
	int		mask;
	int		node;

	if (!tree)
		return NULL;
	if (len == 0)
		return NULL;
	node = 1;
	trie = utf8data + tree->index;
	while (node) {
		offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT;
		if (*trie & NEXTBYTE) {
			if (--len == 0)
				return NULL;
			s++;
		}
		mask = 1 << (*trie & BITNUM);
		if (*s & mask) {
			/* Right leg */
			if (offlen) {
				/* Right node at offset of trie */
				node = (*trie & RIGHTNODE);
				offset = trie[offlen];
				while (--offlen) {
					offset <<= 8;
					offset |= trie[offlen];
				}
				trie += offset;
			} else if (*trie & RIGHTPATH) {
				/* Right node after this node */
				node = (*trie & TRIENODE);
				trie++;
			} else {
				/* No right node. */
				return NULL;
			}
		} else {
			/* Left leg */
			if (offlen) {
				/* Left node after this node. */
				node = (*trie & LEFTNODE);
				trie += offlen + 1;
			} else if (*trie & RIGHTPATH) {
				/* No left node. */
				return NULL;
			} else {
				/* Left node after this node */
				node = (*trie & TRIENODE);
				trie++;
			}
		}
	}
	/*
	 * Hangul decomposition is done algorithmically. These are the
	 * codepoints >= 0xAC00 and <= 0xD7A3. Their UTF-8 encoding is
	 * always 3 bytes long, so s has been advanced twice, and the
	 * start of the sequence is at s-2.
	 */
	if (LEAF_CCC(trie) == DECOMPOSE && LEAF_STR(trie)[0] == HANGUL)
		trie = utf8hangul(s - 2, hangul);
	return trie;
}

/*
 * Use trie to scan s.
 * Returns the leaf if one exists, NULL otherwise.
 *
 * Forwards to trie_nlookup().
 */
static utf8leaf_t *utf8lookup(struct tree *tree, unsigned char *hangul,
			      const char *s)
{
	return utf8nlookup(tree, hangul, s, (size_t)-1);
}

/*
 * Return the number of bytes used by the current UTF-8 sequence.
 * Assumes the input points to the first byte of a valid UTF-8
 * sequence.
 */
static inline int utf8clen(const char *s)
{
	unsigned char c = *s;
	return 1 + (c >= 0xC0) + (c >= 0xE0) + (c >= 0xF0);
}

/*
 * Maximum age of any character in s.
 * Return -1 if s is not valid UTF-8 unicode.
 * Return 0 if only non-assigned code points are used.
 */
int utf8agemax(struct tree *tree, const char *s)
{
	utf8leaf_t	*leaf;
	int		age = 0;
	int		leaf_age;
	unsigned char	hangul[UTF8HANGULLEAF];

	if (!tree)
		return -1;

	while (*s) {
		leaf = utf8lookup(tree, hangul, s);
		if (!leaf)
			return -1;
		leaf_age = ages[LEAF_GEN(leaf)];
		if (leaf_age <= tree->maxage && leaf_age > age)
			age = leaf_age;
		s += utf8clen(s);
	}
	return age;
}

/*
 * Minimum age of any character in s.
 * Return -1 if s is not valid UTF-8 unicode.
 * Return 0 if non-assigned code points are used.
 */
int utf8agemin(struct tree *tree, const char *s)
{
	utf8leaf_t	*leaf;
	int		age;
	int		leaf_age;
	unsigned char	hangul[UTF8HANGULLEAF];

	if (!tree)
		return -1;
	age = tree->maxage;
	while (*s) {
		leaf = utf8lookup(tree, hangul, s);
		if (!leaf)
			return -1;
		leaf_age = ages[LEAF_GEN(leaf)];
		if (leaf_age <= tree->maxage && leaf_age < age)
			age = leaf_age;
		s += utf8clen(s);
	}
	return age;
}

/*
 * Maximum age of any character in s, touch at most len bytes.
 * Return -1 if s is not valid UTF-8 unicode.
 */
int utf8nagemax(struct tree *tree, const char *s, size_t len)
{
	utf8leaf_t	*leaf;
	int		age = 0;
	int		leaf_age;
	unsigned char	hangul[UTF8HANGULLEAF];

	if (!tree)
		return -1;

        while (len && *s) {
		leaf = utf8nlookup(tree, hangul, s, len);
		if (!leaf)
			return -1;
		leaf_age = ages[LEAF_GEN(leaf)];
		if (leaf_age <= tree->maxage && leaf_age > age)
			age = leaf_age;
		len -= utf8clen(s);
		s += utf8clen(s);
	}
	return age;
}

/*
 * Maximum age of any character in s, touch at most len bytes.
 * Return -1 if s is not valid UTF-8 unicode.
 */
int utf8nagemin(struct tree *tree, const char *s, size_t len)
{
	utf8leaf_t	*leaf;
	int		leaf_age;
	int		age;
	unsigned char	hangul[UTF8HANGULLEAF];

	if (!tree)
		return -1;
	age = tree->maxage;
        while (len && *s) {
		leaf = utf8nlookup(tree, hangul, s, len);
		if (!leaf)
			return -1;
		leaf_age = ages[LEAF_GEN(leaf)];
		if (leaf_age <= tree->maxage && leaf_age < age)
			age = leaf_age;
		len -= utf8clen(s);
		s += utf8clen(s);
	}
	return age;
}

/*
 * Length of the normalization of s.
 * Return -1 if s is not valid UTF-8 unicode.
 *
 * A string of Default_Ignorable_Code_Point has length 0.
 */
ssize_t utf8len(struct tree *tree, const char *s)
{
	utf8leaf_t	*leaf;
	size_t		ret = 0;
	unsigned char	hangul[UTF8HANGULLEAF];

	if (!tree)
		return -1;
	while (*s) {
		leaf = utf8lookup(tree, hangul, s);
		if (!leaf)
			return -1;
		if (ages[LEAF_GEN(leaf)] > tree->maxage)
			ret += utf8clen(s);
		else if (LEAF_CCC(leaf) == DECOMPOSE)
			ret += strlen(LEAF_STR(leaf));
		else
			ret += utf8clen(s);
		s += utf8clen(s);
	}
	return ret;
}

/*
 * Length of the normalization of s, touch at most len bytes.
 * Return -1 if s is not valid UTF-8 unicode.
 */
ssize_t utf8nlen(struct tree *tree, const char *s, size_t len)
{
	utf8leaf_t	*leaf;
	size_t		ret = 0;
	unsigned char	hangul[UTF8HANGULLEAF];

	if (!tree)
		return -1;
	while (len && *s) {
		leaf = utf8nlookup(tree, hangul, s, len);
		if (!leaf)
			return -1;
		if (ages[LEAF_GEN(leaf)] > tree->maxage)
			ret += utf8clen(s);
		else if (LEAF_CCC(leaf) == DECOMPOSE)
			ret += strlen(LEAF_STR(leaf));
		else
			ret += utf8clen(s);
		len -= utf8clen(s);
		s += utf8clen(s);
	}
	return ret;
}

/*
 * Cursor structure used by the normalizer.
 */
struct utf8cursor {
	struct tree	*tree;
	const char	*s;
	const char	*p;
	const char	*ss;
	const char	*sp;
	unsigned int	len;
	unsigned int	slen;
	short int	ccc;
	short int	nccc;
	unsigned int	unichar;
	unsigned char	hangul[UTF8HANGULLEAF];
};

/*
 * Set up an utf8cursor for use by utf8byte().
 *
 *   s      : string.
 *   len    : length of s.
 *   u8c    : pointer to cursor.
 *   trie   : utf8trie_t to use for normalization.
 *
 * Returns -1 on error, 0 on success.
 */
int utf8ncursor(struct utf8cursor *u8c, struct tree *tree, const char *s,
		size_t len)
{
	if (!tree)
		return -1;
	if (!s)
		return -1;
	u8c->tree = tree;
	u8c->s = s;
	u8c->p = NULL;
	u8c->ss = NULL;
	u8c->sp = NULL;
	u8c->len = len;
	u8c->slen = 0;
	u8c->ccc = STOPPER;
	u8c->nccc = STOPPER;
	u8c->unichar = 0;
	/* Check we didn't clobber the maximum length. */
	if (u8c->len != len)
		return -1;
	/* The first byte of s may not be an utf8 continuation. */
	if (len > 0 && (*s & 0xC0) == 0x80)
		return -1;
	return 0;
}

/*
 * Set up an utf8cursor for use by utf8byte().
 *
 *   s      : NUL-terminated string.
 *   u8c    : pointer to cursor.
 *   trie   : utf8trie_t to use for normalization.
 *
 * Returns -1 on error, 0 on success.
 */
int utf8cursor(struct utf8cursor *u8c, struct tree *tree, const char *s)
{
	return utf8ncursor(u8c, tree, s, (unsigned int)-1);
}

/*
 * Get one byte from the normalized form of the string described by u8c.
 *
 * Returns the byte cast to an unsigned char on succes, and -1 on failure.
 *
 * The cursor keeps track of the location in the string in u8c->s.
 * When a character is decomposed, the current location is stored in
 * u8c->p, and u8c->s is set to the start of the decomposition. Note
 * that bytes from a decomposition do not count against u8c->len.
 *
 * Characters are emitted if they match the current CCC in u8c->ccc.
 * Hitting end-of-string while u8c->ccc == STOPPER means we're done,
 * and the function returns 0 in that case.
 *
 * Sorting by CCC is done by repeatedly scanning the string.  The
 * values of u8c->s and u8c->p are stored in u8c->ss and u8c->sp at
 * the start of the scan.  The first pass finds the lowest CCC to be
 * emitted and stores it in u8c->nccc, the second pass emits the
 * characters with this CCC and finds the next lowest CCC. This limits
 * the number of passes to 1 + the number of different CCCs in the
 * sequence being scanned.
 *
 * Therefore:
 *  u8c->p  != NULL -> a decomposition is being scanned.
 *  u8c->ss != NULL -> this is a repeating scan.
 *  u8c->ccc == -1  -> this is the first scan of a repeating scan.
 */
int utf8byte(struct utf8cursor *u8c)
{
	utf8leaf_t *leaf;
	int ccc;

	for (;;) {
		/* Check for the end of a decomposed character. */
		if (u8c->p && *u8c->s == '\0') {
			u8c->s = u8c->p;
			u8c->p = NULL;
		}

		/* Check for end-of-string. */
		if (!u8c->p && (u8c->len == 0 || *u8c->s == '\0')) {
			/* There is no next byte. */
			if (u8c->ccc == STOPPER)
				return 0;
			/* End-of-string during a scan counts as a stopper. */
			ccc = STOPPER;
			goto ccc_mismatch;
		} else if ((*u8c->s & 0xC0) == 0x80) {
			/* This is a continuation of the current character. */
			if (!u8c->p)
				u8c->len--;
			return (unsigned char)*u8c->s++;
		}

		/* Look up the data for the current character. */
		if (u8c->p) {
			leaf = utf8lookup(u8c->tree, u8c->hangul, u8c->s);
		} else {
			leaf = utf8nlookup(u8c->tree, u8c->hangul,
					   u8c->s, u8c->len);
		}

		/* No leaf found implies that the input is a binary blob. */
		if (!leaf)
			return -1;

		/* Characters that are too new have CCC 0. */
		if (ages[LEAF_GEN(leaf)] > u8c->tree->maxage) {
			ccc = STOPPER;
		} else if ((ccc = LEAF_CCC(leaf)) == DECOMPOSE) {
			u8c->len -= utf8clen(u8c->s);
			u8c->p = u8c->s + utf8clen(u8c->s);
			u8c->s = LEAF_STR(leaf);
			/* Empty decomposition implies CCC 0. */
			if (*u8c->s == '\0') {
				if (u8c->ccc == STOPPER)
					continue;
				ccc = STOPPER;
				goto ccc_mismatch;
			}
			leaf = utf8lookup(u8c->tree, u8c->hangul, u8c->s);
			ccc = LEAF_CCC(leaf);
		}
		u8c->unichar = utf8decode(u8c->s);

		/*
		 * If this is not a stopper, then see if it updates
		 * the next canonical class to be emitted.
		 */
		if (ccc != STOPPER && u8c->ccc < ccc && ccc < u8c->nccc)
			u8c->nccc = ccc;

		/*
		 * Return the current byte if this is the current
		 * combining class.
		 */
		if (ccc == u8c->ccc) {
			if (!u8c->p)
				u8c->len--;
			return (unsigned char)*u8c->s++;
		}

		/* Current combining class mismatch. */
	ccc_mismatch:
		if (u8c->nccc == STOPPER) {
			/*
			 * Scan forward for the first canonical class
			 * to be emitted.  Save the position from
			 * which to restart.
			 */
			assert(u8c->ccc == STOPPER);
			u8c->ccc = MINCCC - 1;
			u8c->nccc = ccc;
			u8c->sp = u8c->p;
			u8c->ss = u8c->s;
			u8c->slen = u8c->len;
			if (!u8c->p)
				u8c->len -= utf8clen(u8c->s);
			u8c->s += utf8clen(u8c->s);
		} else if (ccc != STOPPER) {
			/* Not a stopper, and not the ccc we're emitting. */
			if (!u8c->p)
				u8c->len -= utf8clen(u8c->s);
			u8c->s += utf8clen(u8c->s);
		} else if (u8c->nccc != MAXCCC + 1) {
			/* At a stopper, restart for next ccc. */
			u8c->ccc = u8c->nccc;
			u8c->nccc = MAXCCC + 1;
			u8c->s = u8c->ss;
			u8c->p = u8c->sp;
			u8c->len = u8c->slen;
		} else {
			/* All done, proceed from here. */
			u8c->ccc = STOPPER;
			u8c->nccc = STOPPER;
			u8c->sp = NULL;
			u8c->ss = NULL;
			u8c->slen = 0;
		}
	}
}

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

static int normalize_line(struct tree *tree)
{
	char *s;
	char *t;
	int c;
	struct utf8cursor u8c;

	/* First test: null-terminated string. */
	s = buf2;
	t = buf3;
	if (utf8cursor(&u8c, tree, s))
		return -1;
	while ((c = utf8byte(&u8c)) > 0)
		if (c != (unsigned char)*t++)
			return -1;
	if (c < 0)
		return -1;
	if (*t != 0)
		return -1;

	/* Second test: length-limited string. */
	s = buf2;
	/* Replace NUL with a value that will cause an error if seen. */
	s[strlen(s) + 1] = -1;
	t = buf3;
	if (utf8cursor(&u8c, tree, s))
		return -1;
	while ((c = utf8byte(&u8c)) > 0)
		if (c != (unsigned char)*t++)
			return -1;
	if (c < 0)
		return -1;
	if (*t != 0)
		return -1;

	return 0;
}

static void normalization_test(void)
{
	FILE *file;
	unsigned int unichar;
	struct unicode_data *data;
	char *s;
	char *t;
	int ret;
	int ignorables;
	int tests = 0;
	int failures = 0;

	if (verbose > 0)
		printf("Parsing %s\n", test_name);
	/* Step one, read data from file. */
	file = fopen(test_name, "r");
	if (!file)
		open_fail(test_name, errno);

	while (fgets(line, LINESIZE, file)) {
		ret = sscanf(line, "%[^;];%*[^;];%[^;];%*[^;];%*[^;];",
			     buf0, buf1);
		if (ret != 2 || *line == '#')
			continue;
		s = buf0;
		t = buf2;
		while (*s) {
			unichar = strtoul(s, &s, 16);
			t += utf8encode(t, unichar);
		}
		*t = '\0';

		ignorables = 0;
		s = buf1;
		t = buf3;
		while (*s) {
			unichar = strtoul(s, &s, 16);
			data = &unicode_data[unichar];
			if (data->utf8nfdi && !*data->utf8nfdi)
				ignorables = 1;
			else
				t += utf8encode(t, unichar);
		}
		*t = '\0';

		tests++;
		if (normalize_line(nfdi_tree) < 0) {
			printf("Line %s -> %s", buf0, buf1);
			if (ignorables)
				printf(" (ignorables removed)");
			printf(" failure\n");
			failures++;
		}
	}
	fclose(file);
	if (verbose > 0)
		printf("Ran %d tests with %d failures\n", tests, failures);
	if (failures)
		file_fail(test_name);
}

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

static void write_file(void)
{
	FILE *file;
	int i;
	int j;
	int t;
	int gen;

	if (verbose > 0)
		printf("Writing %s\n", utf8_name);
	file = fopen(utf8_name, "w");
	if (!file)
		open_fail(utf8_name, errno);

	fprintf(file, "/* This file is generated code, do not edit. */\n");
	fprintf(file, "\n");
	fprintf(file, "#include <linux/module.h>\n");
	fprintf(file, "#include <linux/kernel.h>\n");
	fprintf(file, "#include \"utf8n.h\"\n");
	fprintf(file, "\n");
	fprintf(file, "static const unsigned int utf8agetab[] = {\n");
	for (i = 0; i != ages_count; i++)
		fprintf(file, "\t%#x%s\n", ages[i],
			ages[i] == unicode_maxage ? "" : ",");
	fprintf(file, "};\n");
	fprintf(file, "\n");
	fprintf(file, "static const struct utf8data utf8nfdicfdata[] = {\n");
	t = 0;
	for (gen = 0; gen < ages_count; gen++) {
		fprintf(file, "\t{ %#x, %d }%s\n",
			ages[gen], trees[t].index,
			ages[gen] == unicode_maxage ? "" : ",");
		if (trees[t].maxage == ages[gen])
			t += 2;
	}
	fprintf(file, "};\n");
	fprintf(file, "\n");
	fprintf(file, "static const struct utf8data utf8nfdidata[] = {\n");
	t = 1;
	for (gen = 0; gen < ages_count; gen++) {
		fprintf(file, "\t{ %#x, %d }%s\n",
			ages[gen], trees[t].index,
			ages[gen] == unicode_maxage ? "" : ",");
		if (trees[t].maxage == ages[gen])
			t += 2;
	}
	fprintf(file, "};\n");
	fprintf(file, "\n");
	fprintf(file, "static const unsigned char utf8data[%zd] = {\n",
		utf8data_size);
	t = 0;
	for (i = 0; i != utf8data_size; i += 16) {
		if (i == trees[t].index) {
			fprintf(file, "\t/* %s_%x */\n",
				trees[t].type, trees[t].maxage);
			if (t < trees_count-1)
				t++;
		}
		fprintf(file, "\t");
		for (j = i; j != i + 16; j++)
			fprintf(file, "0x%.2x%s", utf8data[j],
				(j < utf8data_size -1 ? "," : ""));
		fprintf(file, "\n");
	}
	fprintf(file, "};\n");
	fprintf(file, "\n");
	fprintf(file, "struct utf8data_table utf8_data_table = {\n");
	fprintf(file, "\t.utf8agetab = utf8agetab,\n");
	fprintf(file, "\t.utf8agetab_size = ARRAY_SIZE(utf8agetab),\n");
	fprintf(file, "\n");
	fprintf(file, "\t.utf8nfdicfdata = utf8nfdicfdata,\n");
	fprintf(file, "\t.utf8nfdicfdata_size = ARRAY_SIZE(utf8nfdicfdata),\n");
	fprintf(file, "\n");
	fprintf(file, "\t.utf8nfdidata = utf8nfdidata,\n");
	fprintf(file, "\t.utf8nfdidata_size = ARRAY_SIZE(utf8nfdidata),\n");
	fprintf(file, "\n");
	fprintf(file, "\t.utf8data = utf8data,\n");
	fprintf(file, "};\n");
	fprintf(file, "EXPORT_SYMBOL_GPL(utf8_data_table);");
	fprintf(file, "\n");
	fprintf(file, "MODULE_LICENSE(\"GPL v2\");\n");
	fclose(file);
}

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

int main(int argc, char *argv[])
{
	unsigned int unichar;
	int opt;

	argv0 = argv[0];

	while ((opt = getopt(argc, argv, "a:c:d:f:hn:o:p:t:v")) != -1) {
		switch (opt) {
		case 'a':
			age_name = optarg;
			break;
		case 'c':
			ccc_name = optarg;
			break;
		case 'd':
			data_name = optarg;
			break;
		case 'f':
			fold_name = optarg;
			break;
		case 'n':
			norm_name = optarg;
			break;
		case 'o':
			utf8_name = optarg;
			break;
		case 'p':
			prop_name = optarg;
			break;
		case 't':
			test_name = optarg;
			break;
		case 'v':
			verbose++;
			break;
		case 'h':
			help();
			exit(0);
		default:
			usage();
		}
	}

	if (verbose > 1)
		help();
	for (unichar = 0; unichar != 0x110000; unichar++)
		unicode_data[unichar].code = unichar;
	age_init();
	ccc_init();
	nfdi_init();
	nfdicf_init();
	ignore_init();
	corrections_init();
	hangul_decompose();
	nfdi_decompose();
	nfdicf_decompose();
	utf8_init();
	trees_init();
	trees_populate();
	trees_reduce();
	trees_verify();
	/* Prevent "unused function" warning. */
	(void)lookup(nfdi_tree, " ");
	if (verbose > 2)
		tree_walk(nfdi_tree);
	if (verbose > 2)
		tree_walk(nfdicf_tree);
	normalization_test();
	write_file();

	return 0;
}