Quelle  mkutf8data.c   Sprache: C

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

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

--> maximum size reached

--> --------------------