brintos / linux-shallow public Read only

1/*2 * Copyright (c) 2014 SGI.3 * All rights reserved.4 *5 * This program is free software; you can redistribute it and/or6 * modify it under the terms of the GNU General Public License as7 * published by the Free Software Foundation.8 *9 * This program is distributed in the hope that it would be useful,10 * but WITHOUT ANY WARRANTY; without even the implied warranty of11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the12 * GNU General Public License for more details.13 *14 * You should have received a copy of the GNU General Public License15 * along with this program; if not, write the Free Software Foundation,16 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA17 */18 19/* Generator for a compact trie for unicode normalization */20 21#include <sys/types.h>22#include <stddef.h>23#include <stdlib.h>24#include <stdio.h>25#include <assert.h>26#include <string.h>27#include <unistd.h>28#include <errno.h>29 30/* Default names of the in- and output files. */31 32#define AGE_NAME	"DerivedAge.txt"33#define CCC_NAME	"DerivedCombiningClass.txt"34#define PROP_NAME	"DerivedCoreProperties.txt"35#define DATA_NAME	"UnicodeData.txt"36#define FOLD_NAME	"CaseFolding.txt"37#define NORM_NAME	"NormalizationCorrections.txt"38#define TEST_NAME	"NormalizationTest.txt"39#define UTF8_NAME	"utf8data.h"40 41const char	*age_name  = AGE_NAME;42const char	*ccc_name  = CCC_NAME;43const char	*prop_name = PROP_NAME;44const char	*data_name = DATA_NAME;45const char	*fold_name = FOLD_NAME;46const char	*norm_name = NORM_NAME;47const char	*test_name = TEST_NAME;48const char	*utf8_name = UTF8_NAME;49 50int verbose = 0;51 52/* An arbitrary line size limit on input lines. */53 54#define LINESIZE	102455char line[LINESIZE];56char buf0[LINESIZE];57char buf1[LINESIZE];58char buf2[LINESIZE];59char buf3[LINESIZE];60 61const char *argv0;62 63#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))64 65/* ------------------------------------------------------------------ */66 67/*68 * Unicode version numbers consist of three parts: major, minor, and a69 * revision.  These numbers are packed into an unsigned int to obtain70 * a single version number.71 *72 * To save space in the generated trie, the unicode version is not73 * stored directly, instead we calculate a generation number from the74 * unicode versions seen in the DerivedAge file, and use that as an75 * index into a table of unicode versions.76 */77#define UNICODE_MAJ_SHIFT		(16)78#define UNICODE_MIN_SHIFT		(8)79 80#define UNICODE_MAJ_MAX			((unsigned short)-1)81#define UNICODE_MIN_MAX			((unsigned char)-1)82#define UNICODE_REV_MAX			((unsigned char)-1)83 84#define UNICODE_AGE(MAJ,MIN,REV)			\85	(((unsigned int)(MAJ) << UNICODE_MAJ_SHIFT) |	\86	 ((unsigned int)(MIN) << UNICODE_MIN_SHIFT) |	\87	 ((unsigned int)(REV)))88 89unsigned int *ages;90int ages_count;91 92unsigned int unicode_maxage;93 94static int age_valid(unsigned int major, unsigned int minor,95		     unsigned int revision)96{97	if (major > UNICODE_MAJ_MAX)98		return 0;99	if (minor > UNICODE_MIN_MAX)100		return 0;101	if (revision > UNICODE_REV_MAX)102		return 0;103	return 1;104}105 106/* ------------------------------------------------------------------ */107 108/*109 * utf8trie_t110 *111 * A compact binary tree, used to decode UTF-8 characters.112 *113 * Internal nodes are one byte for the node itself, and up to three114 * bytes for an offset into the tree.  The first byte contains the115 * following information:116 *  NEXTBYTE  - flag        - advance to next byte if set117 *  BITNUM    - 3 bit field - the bit number to tested118 *  OFFLEN    - 2 bit field - number of bytes in the offset119 * if offlen == 0 (non-branching node)120 *  RIGHTPATH - 1 bit field - set if the following node is for the121 *                            right-hand path (tested bit is set)122 *  TRIENODE  - 1 bit field - set if the following node is an internal123 *                            node, otherwise it is a leaf node124 * if offlen != 0 (branching node)125 *  LEFTNODE  - 1 bit field - set if the left-hand node is internal126 *  RIGHTNODE - 1 bit field - set if the right-hand node is internal127 *128 * Due to the way utf8 works, there cannot be branching nodes with129 * NEXTBYTE set, and moreover those nodes always have a righthand130 * descendant.131 */132typedef unsigned char utf8trie_t;133#define BITNUM		0x07134#define NEXTBYTE	0x08135#define OFFLEN		0x30136#define OFFLEN_SHIFT	4137#define RIGHTPATH	0x40138#define TRIENODE	0x80139#define RIGHTNODE	0x40140#define LEFTNODE	0x80141 142/*143 * utf8leaf_t144 *145 * The leaves of the trie are embedded in the trie, and so the same146 * underlying datatype, unsigned char.147 *148 * leaf[0]: The unicode version, stored as a generation number that is149 *          an index into utf8agetab[].  With this we can filter code150 *          points based on the unicode version in which they were151 *          defined.  The CCC of a non-defined code point is 0.152 * leaf[1]: Canonical Combining Class. During normalization, we need153 *          to do a stable sort into ascending order of all characters154 *          with a non-zero CCC that occur between two characters with155 *          a CCC of 0, or at the begin or end of a string.156 *          The unicode standard guarantees that all CCC values are157 *          between 0 and 254 inclusive, which leaves 255 available as158 *          a special value.159 *          Code points with CCC 0 are known as stoppers.160 * leaf[2]: Decomposition. If leaf[1] == 255, then leaf[2] is the161 *          start of a NUL-terminated string that is the decomposition162 *          of the character.163 *          The CCC of a decomposable character is the same as the CCC164 *          of the first character of its decomposition.165 *          Some characters decompose as the empty string: these are166 *          characters with the Default_Ignorable_Code_Point property.167 *          These do affect normalization, as they all have CCC 0.168 *169 * The decompositions in the trie have been fully expanded.170 *171 * Casefolding, if applicable, is also done using decompositions.172 */173typedef unsigned char utf8leaf_t;174 175#define LEAF_GEN(LEAF)	((LEAF)[0])176#define LEAF_CCC(LEAF)	((LEAF)[1])177#define LEAF_STR(LEAF)	((const char*)((LEAF) + 2))178 179#define MAXGEN		(255)180 181#define MINCCC		(0)182#define MAXCCC		(254)183#define STOPPER		(0)184#define DECOMPOSE	(255)185#define HANGUL		((char)(255))186 187#define UTF8HANGULLEAF	(12)188 189struct tree;190static utf8leaf_t *utf8nlookup(struct tree *, unsigned char *,191			       const char *, size_t);192static utf8leaf_t *utf8lookup(struct tree *, unsigned char *, const char *);193 194unsigned char *utf8data;195size_t utf8data_size;196 197utf8trie_t *nfdi;198utf8trie_t *nfdicf;199 200/* ------------------------------------------------------------------ */201 202/*203 * UTF8 valid ranges.204 *205 * The UTF-8 encoding spreads the bits of a 32bit word over several206 * bytes. This table gives the ranges that can be held and how they'd207 * be represented.208 *209 * 0x00000000 0x0000007F: 0xxxxxxx210 * 0x00000000 0x000007FF: 110xxxxx 10xxxxxx211 * 0x00000000 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx212 * 0x00000000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx213 * 0x00000000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx214 * 0x00000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx215 *216 * There is an additional requirement on UTF-8, in that only the217 * shortest representation of a 32bit value is to be used.  A decoder218 * must not decode sequences that do not satisfy this requirement.219 * Thus the allowed ranges have a lower bound.220 *221 * 0x00000000 0x0000007F: 0xxxxxxx222 * 0x00000080 0x000007FF: 110xxxxx 10xxxxxx223 * 0x00000800 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx224 * 0x00010000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx225 * 0x00200000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx226 * 0x04000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx227 *228 * Actual unicode characters are limited to the range 0x0 - 0x10FFFF,229 * 17 planes of 65536 values.  This limits the sequences actually seen230 * even more, to just the following.231 *232 *          0 -     0x7f: 0                     0x7f233 *       0x80 -    0x7ff: 0xc2 0x80             0xdf 0xbf234 *      0x800 -   0xffff: 0xe0 0xa0 0x80        0xef 0xbf 0xbf235 *    0x10000 - 0x10ffff: 0xf0 0x90 0x80 0x80   0xf4 0x8f 0xbf 0xbf236 *237 * Even within those ranges not all values are allowed: the surrogates238 * 0xd800 - 0xdfff should never be seen.239 *240 * Note that the longest sequence seen with valid usage is 4 bytes,241 * the same a single UTF-32 character.  This makes the UTF-8242 * representation of Unicode strictly smaller than UTF-32.243 *244 * The shortest sequence requirement was introduced by:245 *    Corrigendum #1: UTF-8 Shortest Form246 * It can be found here:247 *    http://www.unicode.org/versions/corrigendum1.html248 *249 */250 251#define UTF8_2_BITS     0xC0252#define UTF8_3_BITS     0xE0253#define UTF8_4_BITS     0xF0254#define UTF8_N_BITS     0x80255#define UTF8_2_MASK     0xE0256#define UTF8_3_MASK     0xF0257#define UTF8_4_MASK     0xF8258#define UTF8_N_MASK     0xC0259#define UTF8_V_MASK     0x3F260#define UTF8_V_SHIFT    6261 262static int utf8encode(char *str, unsigned int val)263{264	int len;265 266	if (val < 0x80) {267		str[0] = val;268		len = 1;269	} else if (val < 0x800) {270		str[1] = val & UTF8_V_MASK;271		str[1] |= UTF8_N_BITS;272		val >>= UTF8_V_SHIFT;273		str[0] = val;274		str[0] |= UTF8_2_BITS;275		len = 2;276	} else if (val < 0x10000) {277		str[2] = val & UTF8_V_MASK;278		str[2] |= UTF8_N_BITS;279		val >>= UTF8_V_SHIFT;280		str[1] = val & UTF8_V_MASK;281		str[1] |= UTF8_N_BITS;282		val >>= UTF8_V_SHIFT;283		str[0] = val;284		str[0] |= UTF8_3_BITS;285		len = 3;286	} else if (val < 0x110000) {287		str[3] = val & UTF8_V_MASK;288		str[3] |= UTF8_N_BITS;289		val >>= UTF8_V_SHIFT;290		str[2] = val & UTF8_V_MASK;291		str[2] |= UTF8_N_BITS;292		val >>= UTF8_V_SHIFT;293		str[1] = val & UTF8_V_MASK;294		str[1] |= UTF8_N_BITS;295		val >>= UTF8_V_SHIFT;296		str[0] = val;297		str[0] |= UTF8_4_BITS;298		len = 4;299	} else {300		printf("%#x: illegal val\n", val);301		len = 0;302	}303	return len;304}305 306static unsigned int utf8decode(const char *str)307{308	const unsigned char *s = (const unsigned char*)str;309	unsigned int unichar = 0;310 311	if (*s < 0x80) {312		unichar = *s;313	} else if (*s < UTF8_3_BITS) {314		unichar = *s++ & 0x1F;315		unichar <<= UTF8_V_SHIFT;316		unichar |= *s & 0x3F;317	} else if (*s < UTF8_4_BITS) {318		unichar = *s++ & 0x0F;319		unichar <<= UTF8_V_SHIFT;320		unichar |= *s++ & 0x3F;321		unichar <<= UTF8_V_SHIFT;322		unichar |= *s & 0x3F;323	} else {324		unichar = *s++ & 0x0F;325		unichar <<= UTF8_V_SHIFT;326		unichar |= *s++ & 0x3F;327		unichar <<= UTF8_V_SHIFT;328		unichar |= *s++ & 0x3F;329		unichar <<= UTF8_V_SHIFT;330		unichar |= *s & 0x3F;331	}332	return unichar;333}334 335static int utf32valid(unsigned int unichar)336{337	return unichar < 0x110000;338}339 340#define HANGUL_SYLLABLE(U)	((U) >= 0xAC00 && (U) <= 0xD7A3)341 342#define NODE 1343#define LEAF 0344 345struct tree {346	void *root;347	int childnode;348	const char *type;349	unsigned int maxage;350	struct tree *next;351	int (*leaf_equal)(void *, void *);352	void (*leaf_print)(void *, int);353	int (*leaf_mark)(void *);354	int (*leaf_size)(void *);355	int *(*leaf_index)(struct tree *, void *);356	unsigned char *(*leaf_emit)(void *, unsigned char *);357	int leafindex[0x110000];358	int index;359};360 361struct node {362	int index;363	int offset;364	int mark;365	int size;366	struct node *parent;367	void *left;368	void *right;369	unsigned char bitnum;370	unsigned char nextbyte;371	unsigned char leftnode;372	unsigned char rightnode;373	unsigned int keybits;374	unsigned int keymask;375};376 377/*378 * Example lookup function for a tree.379 */380static void *lookup(struct tree *tree, const char *key)381{382	struct node *node;383	void *leaf = NULL;384 385	node = tree->root;386	while (!leaf && node) {387		if (node->nextbyte)388			key++;389		if (*key & (1 << (node->bitnum & 7))) {390			/* Right leg */391			if (node->rightnode == NODE) {392				node = node->right;393			} else if (node->rightnode == LEAF) {394				leaf = node->right;395			} else {396				node = NULL;397			}398		} else {399			/* Left leg */400			if (node->leftnode == NODE) {401				node = node->left;402			} else if (node->leftnode == LEAF) {403				leaf = node->left;404			} else {405				node = NULL;406			}407		}408	}409 410	return leaf;411}412 413/*414 * A simple non-recursive tree walker: keep track of visits to the415 * left and right branches in the leftmask and rightmask.416 */417static void tree_walk(struct tree *tree)418{419	struct node *node;420	unsigned int leftmask;421	unsigned int rightmask;422	unsigned int bitmask;423	int indent = 1;424	int nodes, singletons, leaves;425 426	nodes = singletons = leaves = 0;427 428	printf("%s_%x root %p\n", tree->type, tree->maxage, tree->root);429	if (tree->childnode == LEAF) {430		assert(tree->root);431		tree->leaf_print(tree->root, indent);432		leaves = 1;433	} else {434		assert(tree->childnode == NODE);435		node = tree->root;436		leftmask = rightmask = 0;437		while (node) {438			printf("%*snode @ %p bitnum %d nextbyte %d"439			       " left %p right %p mask %x bits %x\n",440				indent, "", node,441				node->bitnum, node->nextbyte,442				node->left, node->right,443				node->keymask, node->keybits);444			nodes += 1;445			if (!(node->left && node->right))446				singletons += 1;447 448			while (node) {449				bitmask = 1 << node->bitnum;450				if ((leftmask & bitmask) == 0) {451					leftmask |= bitmask;452					if (node->leftnode == LEAF) {453						assert(node->left);454						tree->leaf_print(node->left,455								 indent+1);456						leaves += 1;457					} else if (node->left) {458						assert(node->leftnode == NODE);459						indent += 1;460						node = node->left;461						break;462					}463				}464				if ((rightmask & bitmask) == 0) {465					rightmask |= bitmask;466					if (node->rightnode == LEAF) {467						assert(node->right);468						tree->leaf_print(node->right,469								 indent+1);470						leaves += 1;471					} else if (node->right) {472						assert(node->rightnode == NODE);473						indent += 1;474						node = node->right;475						break;476					}477				}478				leftmask &= ~bitmask;479				rightmask &= ~bitmask;480				node = node->parent;481				indent -= 1;482			}483		}484	}485	printf("nodes %d leaves %d singletons %d\n",486	       nodes, leaves, singletons);487}488 489/*490 * Allocate an initialize a new internal node.491 */492static struct node *alloc_node(struct node *parent)493{494	struct node *node;495	int bitnum;496 497	node = malloc(sizeof(*node));498	node->left = node->right = NULL;499	node->parent = parent;500	node->leftnode = NODE;501	node->rightnode = NODE;502	node->keybits = 0;503	node->keymask = 0;504	node->mark = 0;505	node->index = 0;506	node->offset = -1;507	node->size = 4;508 509	if (node->parent) {510		bitnum = parent->bitnum;511		if ((bitnum & 7) == 0) {512			node->bitnum = bitnum + 7 + 8;513			node->nextbyte = 1;514		} else {515			node->bitnum = bitnum - 1;516			node->nextbyte = 0;517		}518	} else {519		node->bitnum = 7;520		node->nextbyte = 0;521	}522 523	return node;524}525 526/*527 * Insert a new leaf into the tree, and collapse any subtrees that are528 * fully populated and end in identical leaves. A nextbyte tagged529 * internal node will not be removed to preserve the tree's integrity.530 * Note that due to the structure of utf8, no nextbyte tagged node531 * will be a candidate for removal.532 */533static int insert(struct tree *tree, char *key, int keylen, void *leaf)534{535	struct node *node;536	struct node *parent;537	void **cursor;538	int keybits;539 540	assert(keylen >= 1 && keylen <= 4);541 542	node = NULL;543	cursor = &tree->root;544	keybits = 8 * keylen;545 546	/* Insert, creating path along the way. */547	while (keybits) {548		if (!*cursor)549			*cursor = alloc_node(node);550		node = *cursor;551		if (node->nextbyte)552			key++;553		if (*key & (1 << (node->bitnum & 7)))554			cursor = &node->right;555		else556			cursor = &node->left;557		keybits--;558	}559	*cursor = leaf;560 561	/* Merge subtrees if possible. */562	while (node) {563		if (*key & (1 << (node->bitnum & 7)))564			node->rightnode = LEAF;565		else566			node->leftnode = LEAF;567		if (node->nextbyte)568			break;569		if (node->leftnode == NODE || node->rightnode == NODE)570			break;571		assert(node->left);572		assert(node->right);573		/* Compare */574		if (! tree->leaf_equal(node->left, node->right))575			break;576		/* Keep left, drop right leaf. */577		leaf = node->left;578		/* Check in parent */579		parent = node->parent;580		if (!parent) {581			/* root of tree! */582			tree->root = leaf;583			tree->childnode = LEAF;584		} else if (parent->left == node) {585			parent->left = leaf;586			parent->leftnode = LEAF;587			if (parent->right) {588				parent->keymask = 0;589				parent->keybits = 0;590			} else {591				parent->keymask |= (1 << node->bitnum);592			}593		} else if (parent->right == node) {594			parent->right = leaf;595			parent->rightnode = LEAF;596			if (parent->left) {597				parent->keymask = 0;598				parent->keybits = 0;599			} else {600				parent->keymask |= (1 << node->bitnum);601				parent->keybits |= (1 << node->bitnum);602			}603		} else {604			/* internal tree error */605			assert(0);606		}607		free(node);608		node = parent;609	}610 611	/* Propagate keymasks up along singleton chains. */612	while (node) {613		parent = node->parent;614		if (!parent)615			break;616		/* Nix the mask for parents with two children. */617		if (node->keymask == 0) {618			parent->keymask = 0;619			parent->keybits = 0;620		} else if (parent->left && parent->right) {621			parent->keymask = 0;622			parent->keybits = 0;623		} else {624			assert((parent->keymask & node->keymask) == 0);625			parent->keymask |= node->keymask;626			parent->keymask |= (1 << parent->bitnum);627			parent->keybits |= node->keybits;628			if (parent->right)629				parent->keybits |= (1 << parent->bitnum);630		}631		node = parent;632	}633 634	return 0;635}636 637/*638 * Prune internal nodes.639 *640 * Fully populated subtrees that end at the same leaf have already641 * been collapsed.  There are still internal nodes that have for both642 * their left and right branches a sequence of singletons that make643 * identical choices and end in identical leaves.  The keymask and644 * keybits collected in the nodes describe the choices made in these645 * singleton chains.  When they are identical for the left and right646 * branch of a node, and the two leaves comare identical, the node in647 * question can be removed.648 *649 * Note that nodes with the nextbyte tag set will not be removed by650 * this to ensure tree integrity.  Note as well that the structure of651 * utf8 ensures that these nodes would not have been candidates for652 * removal in any case.653 */654static void prune(struct tree *tree)655{656	struct node *node;657	struct node *left;658	struct node *right;659	struct node *parent;660	void *leftleaf;661	void *rightleaf;662	unsigned int leftmask;663	unsigned int rightmask;664	unsigned int bitmask;665	int count;666 667	if (verbose > 0)668		printf("Pruning %s_%x\n", tree->type, tree->maxage);669 670	count = 0;671	if (tree->childnode == LEAF)672		return;673	if (!tree->root)674		return;675 676	leftmask = rightmask = 0;677	node = tree->root;678	while (node) {679		if (node->nextbyte)680			goto advance;681		if (node->leftnode == LEAF)682			goto advance;683		if (node->rightnode == LEAF)684			goto advance;685		if (!node->left)686			goto advance;687		if (!node->right)688			goto advance;689		left = node->left;690		right = node->right;691		if (left->keymask == 0)692			goto advance;693		if (right->keymask == 0)694			goto advance;695		if (left->keymask != right->keymask)696			goto advance;697		if (left->keybits != right->keybits)698			goto advance;699		leftleaf = NULL;700		while (!leftleaf) {701			assert(left->left || left->right);702			if (left->leftnode == LEAF)703				leftleaf = left->left;704			else if (left->rightnode == LEAF)705				leftleaf = left->right;706			else if (left->left)707				left = left->left;708			else if (left->right)709				left = left->right;710			else711				assert(0);712		}713		rightleaf = NULL;714		while (!rightleaf) {715			assert(right->left || right->right);716			if (right->leftnode == LEAF)717				rightleaf = right->left;718			else if (right->rightnode == LEAF)719				rightleaf = right->right;720			else if (right->left)721				right = right->left;722			else if (right->right)723				right = right->right;724			else725				assert(0);726		}727		if (! tree->leaf_equal(leftleaf, rightleaf))728			goto advance;729		/*730		 * This node has identical singleton-only subtrees.731		 * Remove it.732		 */733		parent = node->parent;734		left = node->left;735		right = node->right;736		if (parent->left == node)737			parent->left = left;738		else if (parent->right == node)739			parent->right = left;740		else741			assert(0);742		left->parent = parent;743		left->keymask |= (1 << node->bitnum);744		node->left = NULL;745		while (node) {746			bitmask = 1 << node->bitnum;747			leftmask &= ~bitmask;748			rightmask &= ~bitmask;749			if (node->leftnode == NODE && node->left) {750				left = node->left;751				free(node);752				count++;753				node = left;754			} else if (node->rightnode == NODE && node->right) {755				right = node->right;756				free(node);757				count++;758				node = right;759			} else {760				node = NULL;761			}762		}763		/* Propagate keymasks up along singleton chains. */764		node = parent;765		/* Force re-check */766		bitmask = 1 << node->bitnum;767		leftmask &= ~bitmask;768		rightmask &= ~bitmask;769		for (;;) {770			if (node->left && node->right)771				break;772			if (node->left) {773				left = node->left;774				node->keymask |= left->keymask;775				node->keybits |= left->keybits;776			}777			if (node->right) {778				right = node->right;779				node->keymask |= right->keymask;780				node->keybits |= right->keybits;781			}782			node->keymask |= (1 << node->bitnum);783			node = node->parent;784			/* Force re-check */785			bitmask = 1 << node->bitnum;786			leftmask &= ~bitmask;787			rightmask &= ~bitmask;788		}789	advance:790		bitmask = 1 << node->bitnum;791		if ((leftmask & bitmask) == 0 &&792		    node->leftnode == NODE &&793		    node->left) {794			leftmask |= bitmask;795			node = node->left;796		} else if ((rightmask & bitmask) == 0 &&797			   node->rightnode == NODE &&798			   node->right) {799			rightmask |= bitmask;800			node = node->right;801		} else {802			leftmask &= ~bitmask;803			rightmask &= ~bitmask;804			node = node->parent;805		}806	}807	if (verbose > 0)808		printf("Pruned %d nodes\n", count);809}810 811/*812 * Mark the nodes in the tree that lead to leaves that must be813 * emitted.814 */815static void mark_nodes(struct tree *tree)816{817	struct node *node;818	struct node *n;819	unsigned int leftmask;820	unsigned int rightmask;821	unsigned int bitmask;822	int marked;823 824	marked = 0;825	if (verbose > 0)826		printf("Marking %s_%x\n", tree->type, tree->maxage);827	if (tree->childnode == LEAF)828		goto done;829 830	assert(tree->childnode == NODE);831	node = tree->root;832	leftmask = rightmask = 0;833	while (node) {834		bitmask = 1 << node->bitnum;835		if ((leftmask & bitmask) == 0) {836			leftmask |= bitmask;837			if (node->leftnode == LEAF) {838				assert(node->left);839				if (tree->leaf_mark(node->left)) {840					n = node;841					while (n && !n->mark) {842						marked++;843						n->mark = 1;844						n = n->parent;845					}846				}847			} else if (node->left) {848				assert(node->leftnode == NODE);849				node = node->left;850				continue;851			}852		}853		if ((rightmask & bitmask) == 0) {854			rightmask |= bitmask;855			if (node->rightnode == LEAF) {856				assert(node->right);857				if (tree->leaf_mark(node->right)) {858					n = node;859					while (n && !n->mark) {860						marked++;861						n->mark = 1;862						n = n->parent;863					}864				}865			} else if (node->right) {866				assert(node->rightnode == NODE);867				node = node->right;868				continue;869			}870		}871		leftmask &= ~bitmask;872		rightmask &= ~bitmask;873		node = node->parent;874	}875 876	/* second pass: left siblings and singletons */877 878	assert(tree->childnode == NODE);879	node = tree->root;880	leftmask = rightmask = 0;881	while (node) {882		bitmask = 1 << node->bitnum;883		if ((leftmask & bitmask) == 0) {884			leftmask |= bitmask;885			if (node->leftnode == LEAF) {886				assert(node->left);887				if (tree->leaf_mark(node->left)) {888					n = node;889					while (n && !n->mark) {890						marked++;891						n->mark = 1;892						n = n->parent;893					}894				}895			} else if (node->left) {896				assert(node->leftnode == NODE);897				node = node->left;898				if (!node->mark && node->parent->mark) {899					marked++;900					node->mark = 1;901				}902				continue;903			}904		}905		if ((rightmask & bitmask) == 0) {906			rightmask |= bitmask;907			if (node->rightnode == LEAF) {908				assert(node->right);909				if (tree->leaf_mark(node->right)) {910					n = node;911					while (n && !n->mark) {912						marked++;913						n->mark = 1;914						n = n->parent;915					}916				}917			} else if (node->right) {918				assert(node->rightnode == NODE);919				node = node->right;920				if (!node->mark && node->parent->mark &&921				    !node->parent->left) {922					marked++;923					node->mark = 1;924				}925				continue;926			}927		}928		leftmask &= ~bitmask;929		rightmask &= ~bitmask;930		node = node->parent;931	}932done:933	if (verbose > 0)934		printf("Marked %d nodes\n", marked);935}936 937/*938 * Compute the index of each node and leaf, which is the offset in the939 * emitted trie.  These values must be pre-computed because relative940 * offsets between nodes are used to navigate the tree.941 */942static int index_nodes(struct tree *tree, int index)943{944	struct node *node;945	unsigned int leftmask;946	unsigned int rightmask;947	unsigned int bitmask;948	int count;949	int indent;950 951	/* Align to a cache line (or half a cache line?). */952	while (index % 64)953		index++;954	tree->index = index;955	indent = 1;956	count = 0;957 958	if (verbose > 0)959		printf("Indexing %s_%x: %d\n", tree->type, tree->maxage, index);960	if (tree->childnode == LEAF) {961		index += tree->leaf_size(tree->root);962		goto done;963	}964 965	assert(tree->childnode == NODE);966	node = tree->root;967	leftmask = rightmask = 0;968	while (node) {969		if (!node->mark)970			goto skip;971		count++;972		if (node->index != index)973			node->index = index;974		index += node->size;975skip:976		while (node) {977			bitmask = 1 << node->bitnum;978			if (node->mark && (leftmask & bitmask) == 0) {979				leftmask |= bitmask;980				if (node->leftnode == LEAF) {981					assert(node->left);982					*tree->leaf_index(tree, node->left) =983									index;984					index += tree->leaf_size(node->left);985					count++;986				} else if (node->left) {987					assert(node->leftnode == NODE);988					indent += 1;989					node = node->left;990					break;991				}992			}993			if (node->mark && (rightmask & bitmask) == 0) {994				rightmask |= bitmask;995				if (node->rightnode == LEAF) {996					assert(node->right);997					*tree->leaf_index(tree, node->right) = index;998					index += tree->leaf_size(node->right);999					count++;1000				} else if (node->right) {1001					assert(node->rightnode == NODE);1002					indent += 1;1003					node = node->right;1004					break;1005				}1006			}1007			leftmask &= ~bitmask;1008			rightmask &= ~bitmask;1009			node = node->parent;1010			indent -= 1;1011		}1012	}1013done:1014	/* Round up to a multiple of 16 */1015	while (index % 16)1016		index++;1017	if (verbose > 0)1018		printf("Final index %d\n", index);1019	return index;1020}1021 1022/*1023 * Mark the nodes in a subtree, helper for size_nodes().1024 */1025static int mark_subtree(struct node *node)1026{1027	int changed;1028 1029	if (!node || node->mark)1030		return 0;1031	node->mark = 1;1032	node->index = node->parent->index;1033	changed = 1;1034	if (node->leftnode == NODE)1035		changed += mark_subtree(node->left);1036	if (node->rightnode == NODE)1037		changed += mark_subtree(node->right);1038	return changed;1039}1040 1041/*1042 * Compute the size of nodes and leaves. We start by assuming that1043 * each node needs to store a three-byte offset. The indexes of the1044 * nodes are calculated based on that, and then this function is1045 * called to see if the sizes of some nodes can be reduced.  This is1046 * repeated until no more changes are seen.1047 */1048static int size_nodes(struct tree *tree)1049{1050	struct tree *next;1051	struct node *node;1052	struct node *right;1053	struct node *n;1054	unsigned int leftmask;1055	unsigned int rightmask;1056	unsigned int bitmask;1057	unsigned int pathbits;1058	unsigned int pathmask;1059	unsigned int nbit;1060	int changed;1061	int offset;1062	int size;1063	int indent;1064 1065	indent = 1;1066	changed = 0;1067	size = 0;1068 1069	if (verbose > 0)1070		printf("Sizing %s_%x\n", tree->type, tree->maxage);1071	if (tree->childnode == LEAF)1072		goto done;1073 1074	assert(tree->childnode == NODE);1075	pathbits = 0;1076	pathmask = 0;1077	node = tree->root;1078	leftmask = rightmask = 0;1079	while (node) {1080		if (!node->mark)1081			goto skip;1082		offset = 0;1083		if (!node->left || !node->right) {1084			size = 1;1085		} else {1086			if (node->rightnode == NODE) {1087				/*1088				 * If the right node is not marked,1089				 * look for a corresponding node in1090				 * the next tree.  Such a node need1091				 * not exist.1092				 */1093				right = node->right;1094				next = tree->next;1095				while (!right->mark) {1096					assert(next);1097					n = next->root;1098					while (n->bitnum != node->bitnum) {1099						nbit = 1 << n->bitnum;1100						if (!(pathmask & nbit))1101							break;1102						if (pathbits & nbit) {1103							if (n->rightnode == LEAF)1104								break;1105							n = n->right;1106						} else {1107							if (n->leftnode == LEAF)1108								break;1109							n = n->left;1110						}1111					}1112					if (n->bitnum != node->bitnum)1113						break;1114					n = n->right;1115					right = n;1116					next = next->next;1117				}1118				/* Make sure the right node is marked. */1119				if (!right->mark)1120					changed += mark_subtree(right);1121				offset = right->index - node->index;1122			} else {1123				offset = *tree->leaf_index(tree, node->right);1124				offset -= node->index;1125			}1126			assert(offset >= 0);1127			assert(offset <= 0xffffff);1128			if (offset <= 0xff) {1129				size = 2;1130			} else if (offset <= 0xffff) {1131				size = 3;1132			} else { /* offset <= 0xffffff */1133				size = 4;1134			}1135		}1136		if (node->size != size || node->offset != offset) {1137			node->size = size;1138			node->offset = offset;1139			changed++;1140		}1141skip:1142		while (node) {1143			bitmask = 1 << node->bitnum;1144			pathmask |= bitmask;1145			if (node->mark && (leftmask & bitmask) == 0) {1146				leftmask |= bitmask;1147				if (node->leftnode == LEAF) {1148					assert(node->left);1149				} else if (node->left) {1150					assert(node->leftnode == NODE);1151					indent += 1;1152					node = node->left;1153					break;1154				}1155			}1156			if (node->mark && (rightmask & bitmask) == 0) {1157				rightmask |= bitmask;1158				pathbits |= bitmask;1159				if (node->rightnode == LEAF) {1160					assert(node->right);1161				} else if (node->right) {1162					assert(node->rightnode == NODE);1163					indent += 1;1164					node = node->right;1165					break;1166				}1167			}1168			leftmask &= ~bitmask;1169			rightmask &= ~bitmask;1170			pathmask &= ~bitmask;1171			pathbits &= ~bitmask;1172			node = node->parent;1173			indent -= 1;1174		}1175	}1176done:1177	if (verbose > 0)1178		printf("Found %d changes\n", changed);1179	return changed;1180}1181 1182/*1183 * Emit a trie for the given tree into the data array.1184 */1185static void emit(struct tree *tree, unsigned char *data)1186{1187	struct node *node;1188	unsigned int leftmask;1189	unsigned int rightmask;1190	unsigned int bitmask;1191	int offlen;1192	int offset;1193	int index;1194	int indent;1195	int size;1196	int bytes;1197	int leaves;1198	int nodes[4];1199	unsigned char byte;1200 1201	nodes[0] = nodes[1] = nodes[2] = nodes[3] = 0;1202	leaves = 0;1203	bytes = 0;1204	index = tree->index;1205	data += index;1206	indent = 1;1207	if (verbose > 0)1208		printf("Emitting %s_%x\n", tree->type, tree->maxage);1209	if (tree->childnode == LEAF) {1210		assert(tree->root);1211		tree->leaf_emit(tree->root, data);1212		size = tree->leaf_size(tree->root);1213		index += size;1214		leaves++;1215		goto done;1216	}1217 1218	assert(tree->childnode == NODE);1219	node = tree->root;1220	leftmask = rightmask = 0;1221	while (node) {1222		if (!node->mark)1223			goto skip;1224		assert(node->offset != -1);1225		assert(node->index == index);1226 1227		byte = 0;1228		if (node->nextbyte)1229			byte |= NEXTBYTE;1230		byte |= (node->bitnum & BITNUM);1231		if (node->left && node->right) {1232			if (node->leftnode == NODE)1233				byte |= LEFTNODE;1234			if (node->rightnode == NODE)1235				byte |= RIGHTNODE;1236			if (node->offset <= 0xff)1237				offlen = 1;1238			else if (node->offset <= 0xffff)1239				offlen = 2;1240			else1241				offlen = 3;1242			nodes[offlen]++;1243			offset = node->offset;1244			byte |= offlen << OFFLEN_SHIFT;1245			*data++ = byte;1246			index++;1247			while (offlen--) {1248				*data++ = offset & 0xff;1249				index++;1250				offset >>= 8;1251			}1252		} else if (node->left) {1253			if (node->leftnode == NODE)1254				byte |= TRIENODE;1255			nodes[0]++;1256			*data++ = byte;1257			index++;1258		} else if (node->right) {1259			byte |= RIGHTNODE;1260			if (node->rightnode == NODE)1261				byte |= TRIENODE;1262			nodes[0]++;1263			*data++ = byte;1264			index++;1265		} else {1266			assert(0);1267		}1268skip:1269		while (node) {1270			bitmask = 1 << node->bitnum;1271			if (node->mark && (leftmask & bitmask) == 0) {1272				leftmask |= bitmask;1273				if (node->leftnode == LEAF) {1274					assert(node->left);1275					data = tree->leaf_emit(node->left,1276							       data);1277					size = tree->leaf_size(node->left);1278					index += size;1279					bytes += size;1280					leaves++;1281				} else if (node->left) {1282					assert(node->leftnode == NODE);1283					indent += 1;1284					node = node->left;1285					break;1286				}1287			}1288			if (node->mark && (rightmask & bitmask) == 0) {1289				rightmask |= bitmask;1290				if (node->rightnode == LEAF) {1291					assert(node->right);1292					data = tree->leaf_emit(node->right,1293							       data);1294					size = tree->leaf_size(node->right);1295					index += size;1296					bytes += size;1297					leaves++;1298				} else if (node->right) {1299					assert(node->rightnode == NODE);1300					indent += 1;1301					node = node->right;1302					break;1303				}1304			}1305			leftmask &= ~bitmask;1306			rightmask &= ~bitmask;1307			node = node->parent;1308			indent -= 1;1309		}1310	}1311done:1312	if (verbose > 0) {1313		printf("Emitted %d (%d) leaves",1314			leaves, bytes);1315		printf(" %d (%d+%d+%d+%d) nodes",1316			nodes[0] + nodes[1] + nodes[2] + nodes[3],1317			nodes[0], nodes[1], nodes[2], nodes[3]);1318		printf(" %d total\n", index - tree->index);1319	}1320}1321 1322/* ------------------------------------------------------------------ */1323 1324/*1325 * Unicode data.1326 *1327 * We need to keep track of the Canonical Combining Class, the Age,1328 * and decompositions for a code point.1329 *1330 * For the Age, we store the index into the ages table.  Effectively1331 * this is a generation number that the table maps to a unicode1332 * version.1333 *1334 * The correction field is used to indicate that this entry is in the1335 * corrections array, which contains decompositions that were1336 * corrected in later revisions.  The value of the correction field is1337 * the Unicode version in which the mapping was corrected.1338 */1339struct unicode_data {1340	unsigned int code;1341	int ccc;1342	int gen;1343	int correction;1344	unsigned int *utf32nfdi;1345	unsigned int *utf32nfdicf;1346	char *utf8nfdi;1347	char *utf8nfdicf;1348};1349 1350struct unicode_data unicode_data[0x110000];1351struct unicode_data *corrections;1352int    corrections_count;1353 1354struct tree *nfdi_tree;1355struct tree *nfdicf_tree;1356 1357struct tree *trees;1358int          trees_count;1359 1360/*1361 * Check the corrections array to see if this entry was corrected at1362 * some point.1363 */1364static struct unicode_data *corrections_lookup(struct unicode_data *u)1365{1366	int i;1367 1368	for (i = 0; i != corrections_count; i++)1369		if (u->code == corrections[i].code)1370			return &corrections[i];1371	return u;1372}1373 1374static int nfdi_equal(void *l, void *r)1375{1376	struct unicode_data *left = l;1377	struct unicode_data *right = r;1378 1379	if (left->gen != right->gen)1380		return 0;1381	if (left->ccc != right->ccc)1382		return 0;1383	if (left->utf8nfdi && right->utf8nfdi &&1384	    strcmp(left->utf8nfdi, right->utf8nfdi) == 0)1385		return 1;1386	if (left->utf8nfdi || right->utf8nfdi)1387		return 0;1388	return 1;1389}1390 1391static int nfdicf_equal(void *l, void *r)1392{1393	struct unicode_data *left = l;1394	struct unicode_data *right = r;1395 1396	if (left->gen != right->gen)1397		return 0;1398	if (left->ccc != right->ccc)1399		return 0;1400	if (left->utf8nfdicf && right->utf8nfdicf &&1401	    strcmp(left->utf8nfdicf, right->utf8nfdicf) == 0)1402		return 1;1403	if (left->utf8nfdicf && right->utf8nfdicf)1404		return 0;1405	if (left->utf8nfdicf || right->utf8nfdicf)1406		return 0;1407	if (left->utf8nfdi && right->utf8nfdi &&1408	    strcmp(left->utf8nfdi, right->utf8nfdi) == 0)1409		return 1;1410	if (left->utf8nfdi || right->utf8nfdi)1411		return 0;1412	return 1;1413}1414 1415static void nfdi_print(void *l, int indent)1416{1417	struct unicode_data *leaf = l;1418 1419	printf("%*sleaf @ %p code %X ccc %d gen %d", indent, "", leaf,1420		leaf->code, leaf->ccc, leaf->gen);1421 1422	if (leaf->utf8nfdi && leaf->utf8nfdi[0] == HANGUL)1423		printf(" nfdi \"%s\"", "HANGUL SYLLABLE");1424	else if (leaf->utf8nfdi)1425		printf(" nfdi \"%s\"", (const char*)leaf->utf8nfdi);1426 1427	printf("\n");1428}1429 1430static void nfdicf_print(void *l, int indent)1431{1432	struct unicode_data *leaf = l;1433 1434	printf("%*sleaf @ %p code %X ccc %d gen %d", indent, "", leaf,1435		leaf->code, leaf->ccc, leaf->gen);1436 1437	if (leaf->utf8nfdicf)1438		printf(" nfdicf \"%s\"", (const char*)leaf->utf8nfdicf);1439	else if (leaf->utf8nfdi && leaf->utf8nfdi[0] == HANGUL)1440		printf(" nfdi \"%s\"", "HANGUL SYLLABLE");1441	else if (leaf->utf8nfdi)1442		printf(" nfdi \"%s\"", (const char*)leaf->utf8nfdi);1443	printf("\n");1444}1445 1446static int nfdi_mark(void *l)1447{1448	return 1;1449}1450 1451static int nfdicf_mark(void *l)1452{1453	struct unicode_data *leaf = l;1454 1455	if (leaf->utf8nfdicf)1456		return 1;1457	return 0;1458}1459 1460static int correction_mark(void *l)1461{1462	struct unicode_data *leaf = l;1463 1464	return leaf->correction;1465}1466 1467static int nfdi_size(void *l)1468{1469	struct unicode_data *leaf = l;1470	int size = 2;1471 1472	if (HANGUL_SYLLABLE(leaf->code))1473		size += 1;1474	else if (leaf->utf8nfdi)1475		size += strlen(leaf->utf8nfdi) + 1;1476	return size;1477}1478 1479static int nfdicf_size(void *l)1480{1481	struct unicode_data *leaf = l;1482	int size = 2;1483 1484	if (HANGUL_SYLLABLE(leaf->code))1485		size += 1;1486	else if (leaf->utf8nfdicf)1487		size += strlen(leaf->utf8nfdicf) + 1;1488	else if (leaf->utf8nfdi)1489		size += strlen(leaf->utf8nfdi) + 1;1490	return size;1491}1492 1493static int *nfdi_index(struct tree *tree, void *l)1494{1495	struct unicode_data *leaf = l;1496 1497	return &tree->leafindex[leaf->code];1498}1499 1500static int *nfdicf_index(struct tree *tree, void *l)1501{1502	struct unicode_data *leaf = l;1503 1504	return &tree->leafindex[leaf->code];1505}1506 1507static unsigned char *nfdi_emit(void *l, unsigned char *data)1508{1509	struct unicode_data *leaf = l;1510	unsigned char *s;1511 1512	*data++ = leaf->gen;1513 1514	if (HANGUL_SYLLABLE(leaf->code)) {1515		*data++ = DECOMPOSE;1516		*data++ = HANGUL;1517	} else if (leaf->utf8nfdi) {1518		*data++ = DECOMPOSE;1519		s = (unsigned char*)leaf->utf8nfdi;1520		while ((*data++ = *s++) != 0)1521			;1522	} else {1523		*data++ = leaf->ccc;1524	}1525	return data;1526}1527 1528static unsigned char *nfdicf_emit(void *l, unsigned char *data)1529{1530	struct unicode_data *leaf = l;1531	unsigned char *s;1532 1533	*data++ = leaf->gen;1534 1535	if (HANGUL_SYLLABLE(leaf->code)) {1536		*data++ = DECOMPOSE;1537		*data++ = HANGUL;1538	} else if (leaf->utf8nfdicf) {1539		*data++ = DECOMPOSE;1540		s = (unsigned char*)leaf->utf8nfdicf;1541		while ((*data++ = *s++) != 0)1542			;1543	} else if (leaf->utf8nfdi) {1544		*data++ = DECOMPOSE;1545		s = (unsigned char*)leaf->utf8nfdi;1546		while ((*data++ = *s++) != 0)1547			;1548	} else {1549		*data++ = leaf->ccc;1550	}1551	return data;1552}1553 1554static void utf8_create(struct unicode_data *data)1555{1556	char utf[18*4+1];1557	char *u;1558	unsigned int *um;1559	int i;1560 1561	if (data->utf8nfdi) {1562		assert(data->utf8nfdi[0] == HANGUL);1563		return;1564	}1565 1566	u = utf;1567	um = data->utf32nfdi;1568	if (um) {1569		for (i = 0; um[i]; i++)1570			u += utf8encode(u, um[i]);1571		*u = '\0';1572		data->utf8nfdi = strdup(utf);1573	}1574	u = utf;1575	um = data->utf32nfdicf;1576	if (um) {1577		for (i = 0; um[i]; i++)1578			u += utf8encode(u, um[i]);1579		*u = '\0';1580		if (!data->utf8nfdi || strcmp(data->utf8nfdi, utf))1581			data->utf8nfdicf = strdup(utf);1582	}1583}1584 1585static void utf8_init(void)1586{1587	unsigned int unichar;1588	int i;1589 1590	for (unichar = 0; unichar != 0x110000; unichar++)1591		utf8_create(&unicode_data[unichar]);1592 1593	for (i = 0; i != corrections_count; i++)1594		utf8_create(&corrections[i]);1595}1596 1597static void trees_init(void)1598{1599	struct unicode_data *data;1600	unsigned int maxage;1601	unsigned int nextage;1602	int count;1603	int i;1604	int j;1605 1606	/* Count the number of different ages. */1607	count = 0;1608	nextage = (unsigned int)-1;1609	do {1610		maxage = nextage;1611		nextage = 0;1612		for (i = 0; i <= corrections_count; i++) {1613			data = &corrections[i];1614			if (nextage < data->correction &&1615			    data->correction < maxage)1616				nextage = data->correction;1617		}1618		count++;1619	} while (nextage);1620 1621	/* Two trees per age: nfdi and nfdicf */1622	trees_count = count * 2;1623	trees = calloc(trees_count, sizeof(struct tree));1624 1625	/* Assign ages to the trees. */1626	count = trees_count;1627	nextage = (unsigned int)-1;1628	do {1629		maxage = nextage;1630		trees[--count].maxage = maxage;1631		trees[--count].maxage = maxage;1632		nextage = 0;1633		for (i = 0; i <= corrections_count; i++) {1634			data = &corrections[i];1635			if (nextage < data->correction &&1636			    data->correction < maxage)1637				nextage = data->correction;1638		}1639	} while (nextage);1640 1641	/* The ages assigned above are off by one. */1642	for (i = 0; i != trees_count; i++) {1643		j = 0;1644		while (ages[j] < trees[i].maxage)1645			j++;1646		trees[i].maxage = ages[j-1];1647	}1648 1649	/* Set up the forwarding between trees. */1650	trees[trees_count-2].next = &trees[trees_count-1];1651	trees[trees_count-1].leaf_mark = nfdi_mark;1652	trees[trees_count-2].leaf_mark = nfdicf_mark;1653	for (i = 0; i != trees_count-2; i += 2) {1654		trees[i].next = &trees[trees_count-2];1655		trees[i].leaf_mark = correction_mark;1656		trees[i+1].next = &trees[trees_count-1];1657		trees[i+1].leaf_mark = correction_mark;1658	}1659 1660	/* Assign the callouts. */1661	for (i = 0; i != trees_count; i += 2) {1662		trees[i].type = "nfdicf";1663		trees[i].leaf_equal = nfdicf_equal;1664		trees[i].leaf_print = nfdicf_print;1665		trees[i].leaf_size = nfdicf_size;1666		trees[i].leaf_index = nfdicf_index;1667		trees[i].leaf_emit = nfdicf_emit;1668 1669		trees[i+1].type = "nfdi";1670		trees[i+1].leaf_equal = nfdi_equal;1671		trees[i+1].leaf_print = nfdi_print;1672		trees[i+1].leaf_size = nfdi_size;1673		trees[i+1].leaf_index = nfdi_index;1674		trees[i+1].leaf_emit = nfdi_emit;1675	}1676 1677	/* Finish init. */1678	for (i = 0; i != trees_count; i++)1679		trees[i].childnode = NODE;1680}1681 1682static void trees_populate(void)1683{1684	struct unicode_data *data;1685	unsigned int unichar;1686	char keyval[4];1687	int keylen;1688	int i;1689 1690	for (i = 0; i != trees_count; i++) {1691		if (verbose > 0) {1692			printf("Populating %s_%x\n",1693				trees[i].type, trees[i].maxage);1694		}1695		for (unichar = 0; unichar != 0x110000; unichar++) {1696			if (unicode_data[unichar].gen < 0)1697				continue;1698			keylen = utf8encode(keyval, unichar);1699			data = corrections_lookup(&unicode_data[unichar]);1700			if (data->correction <= trees[i].maxage)1701				data = &unicode_data[unichar];1702			insert(&trees[i], keyval, keylen, data);1703		}1704	}1705}1706 1707static void trees_reduce(void)1708{1709	int i;1710	int size;1711	int changed;1712 1713	for (i = 0; i != trees_count; i++)1714		prune(&trees[i]);1715	for (i = 0; i != trees_count; i++)1716		mark_nodes(&trees[i]);1717	do {1718		size = 0;1719		for (i = 0; i != trees_count; i++)1720			size = index_nodes(&trees[i], size);1721		changed = 0;1722		for (i = 0; i != trees_count; i++)1723			changed += size_nodes(&trees[i]);1724	} while (changed);1725 1726	utf8data = calloc(size, 1);1727	utf8data_size = size;1728	for (i = 0; i != trees_count; i++)1729		emit(&trees[i], utf8data);1730 1731	if (verbose > 0) {1732		for (i = 0; i != trees_count; i++) {1733			printf("%s_%x idx %d\n",1734				trees[i].type, trees[i].maxage, trees[i].index);1735		}1736	}1737 1738	nfdi = utf8data + trees[trees_count-1].index;1739	nfdicf = utf8data + trees[trees_count-2].index;1740 1741	nfdi_tree = &trees[trees_count-1];1742	nfdicf_tree = &trees[trees_count-2];1743}1744 1745static void verify(struct tree *tree)1746{1747	struct unicode_data *data;1748	utf8leaf_t	*leaf;1749	unsigned int	unichar;1750	char		key[4];1751	unsigned char	hangul[UTF8HANGULLEAF];1752	int		report;1753	int		nocf;1754 1755	if (verbose > 0)1756		printf("Verifying %s_%x\n", tree->type, tree->maxage);1757	nocf = strcmp(tree->type, "nfdicf");1758 1759	for (unichar = 0; unichar != 0x110000; unichar++) {1760		report = 0;1761		data = corrections_lookup(&unicode_data[unichar]);1762		if (data->correction <= tree->maxage)1763			data = &unicode_data[unichar];1764		utf8encode(key,unichar);1765		leaf = utf8lookup(tree, hangul, key);1766 1767		if (!leaf) {1768			if (data->gen != -1)1769				report++;1770			if (unichar < 0xd800 || unichar > 0xdfff)1771				report++;1772		} else {1773			if (unichar >= 0xd800 && unichar <= 0xdfff)1774				report++;1775			if (data->gen == -1)1776				report++;1777			if (data->gen != LEAF_GEN(leaf))1778				report++;1779			if (LEAF_CCC(leaf) == DECOMPOSE) {1780				if (HANGUL_SYLLABLE(data->code)) {1781					if (data->utf8nfdi[0] != HANGUL)1782						report++;1783				} else if (nocf) {1784					if (!data->utf8nfdi) {1785						report++;1786					} else if (strcmp(data->utf8nfdi,1787							  LEAF_STR(leaf))) {1788						report++;1789					}1790				} else {1791					if (!data->utf8nfdicf &&1792					    !data->utf8nfdi) {1793						report++;1794					} else if (data->utf8nfdicf) {1795						if (strcmp(data->utf8nfdicf,1796							   LEAF_STR(leaf)))1797							report++;1798					} else if (strcmp(data->utf8nfdi,1799							  LEAF_STR(leaf))) {1800						report++;1801					}1802				}1803			} else if (data->ccc != LEAF_CCC(leaf)) {1804				report++;1805			}1806		}1807		if (report) {1808			printf("%X code %X gen %d ccc %d"1809				" nfdi -> \"%s\"",1810				unichar, data->code, data->gen,1811				data->ccc,1812				data->utf8nfdi);1813			if (leaf) {1814				printf(" gen %d ccc %d"1815					" nfdi -> \"%s\"",1816					LEAF_GEN(leaf),1817					LEAF_CCC(leaf),1818					LEAF_CCC(leaf) == DECOMPOSE ?1819						LEAF_STR(leaf) : "");1820			}1821			printf("\n");1822		}1823	}1824}1825 1826static void trees_verify(void)1827{1828	int i;1829 1830	for (i = 0; i != trees_count; i++)1831		verify(&trees[i]);1832}1833 1834/* ------------------------------------------------------------------ */1835 1836static void help(void)1837{1838	printf("Usage: %s [options]\n", argv0);1839	printf("\n");1840	printf("This program creates an a data trie used for parsing and\n");1841	printf("normalization of UTF-8 strings. The trie is derived from\n");1842	printf("a set of input files from the Unicode character database\n");1843	printf("found at: http://www.unicode.org/Public/UCD/latest/ucd/\n");1844	printf("\n");1845	printf("The generated tree supports two normalization forms:\n");1846	printf("\n");1847	printf("\tnfdi:\n");1848	printf("\t- Apply unicode normalization form NFD.\n");1849	printf("\t- Remove any Default_Ignorable_Code_Point.\n");1850	printf("\n");1851	printf("\tnfdicf:\n");1852	printf("\t- Apply unicode normalization form NFD.\n");1853	printf("\t- Remove any Default_Ignorable_Code_Point.\n");1854	printf("\t- Apply a full casefold (C + F).\n");1855	printf("\n");1856	printf("These forms were chosen as being most useful when dealing\n");1857	printf("with file names: NFD catches most cases where characters\n");1858	printf("should be considered equivalent. The ignorables are mostly\n");1859	printf("invisible, making names hard to type.\n");1860	printf("\n");1861	printf("The options to specify the files to be used are listed\n");1862	printf("below with their default values, which are the names used\n");1863	printf("by version 11.0.0 of the Unicode Character Database.\n");1864	printf("\n");1865	printf("The input files:\n");1866	printf("\t-a %s\n", AGE_NAME);1867	printf("\t-c %s\n", CCC_NAME);1868	printf("\t-p %s\n", PROP_NAME);1869	printf("\t-d %s\n", DATA_NAME);1870	printf("\t-f %s\n", FOLD_NAME);1871	printf("\t-n %s\n", NORM_NAME);1872	printf("\n");1873	printf("Additionally, the generated tables are tested using:\n");1874	printf("\t-t %s\n", TEST_NAME);1875	printf("\n");1876	printf("Finally, the output file:\n");1877	printf("\t-o %s\n", UTF8_NAME);1878	printf("\n");1879}1880 1881static void usage(void)1882{1883	help();1884	exit(1);1885}1886 1887static void open_fail(const char *name, int error)1888{1889	printf("Error %d opening %s: %s\n", error, name, strerror(error));1890	exit(1);1891}1892 1893static void file_fail(const char *filename)1894{1895	printf("Error parsing %s\n", filename);1896	exit(1);1897}1898 1899static void line_fail(const char *filename, const char *line)1900{1901	printf("Error parsing %s:%s\n", filename, line);1902	exit(1);1903}1904 1905/* ------------------------------------------------------------------ */1906 1907static void print_utf32(unsigned int *utf32str)1908{1909	int	i;1910 1911	for (i = 0; utf32str[i]; i++)1912		printf(" %X", utf32str[i]);1913}1914 1915static void print_utf32nfdi(unsigned int unichar)1916{1917	printf(" %X ->", unichar);1918	print_utf32(unicode_data[unichar].utf32nfdi);1919	printf("\n");1920}1921 1922static void print_utf32nfdicf(unsigned int unichar)1923{1924	printf(" %X ->", unichar);1925	print_utf32(unicode_data[unichar].utf32nfdicf);1926	printf("\n");1927}1928 1929/* ------------------------------------------------------------------ */1930 1931static void age_init(void)1932{1933	FILE *file;1934	unsigned int first;1935	unsigned int last;1936	unsigned int unichar;1937	unsigned int major;1938	unsigned int minor;1939	unsigned int revision;1940	int gen;1941	int count;1942	int ret;1943 1944	if (verbose > 0)1945		printf("Parsing %s\n", age_name);1946 1947	file = fopen(age_name, "r");1948	if (!file)1949		open_fail(age_name, errno);1950	count = 0;1951 1952	gen = 0;1953	while (fgets(line, LINESIZE, file)) {1954		ret = sscanf(line, "# Age=V%d_%d_%d",1955				&major, &minor, &revision);1956		if (ret == 3) {1957			ages_count++;1958			if (verbose > 1)1959				printf(" Age V%d_%d_%d\n",1960					major, minor, revision);1961			if (!age_valid(major, minor, revision))1962				line_fail(age_name, line);1963			continue;1964		}1965		ret = sscanf(line, "# Age=V%d_%d", &major, &minor);1966		if (ret == 2) {1967			ages_count++;1968			if (verbose > 1)1969				printf(" Age V%d_%d\n", major, minor);1970			if (!age_valid(major, minor, 0))1971				line_fail(age_name, line);1972			continue;1973		}1974	}1975 1976	/* We must have found something above. */1977	if (verbose > 1)1978		printf("%d age entries\n", ages_count);1979	if (ages_count == 0 || ages_count > MAXGEN)1980		file_fail(age_name);1981 1982	/* There is a 0 entry. */1983	ages_count++;1984	ages = calloc(ages_count + 1, sizeof(*ages));1985	/* And a guard entry. */1986	ages[ages_count] = (unsigned int)-1;1987 1988	rewind(file);1989	count = 0;1990	gen = 0;1991	while (fgets(line, LINESIZE, file)) {1992		ret = sscanf(line, "# Age=V%d_%d_%d",1993				&major, &minor, &revision);1994		if (ret == 3) {1995			ages[++gen] =1996				UNICODE_AGE(major, minor, revision);1997			if (verbose > 1)1998				printf(" Age V%d_%d_%d = gen %d\n",1999					major, minor, revision, gen);2000			if (!age_valid(major, minor, revision))2001				line_fail(age_name, line);2002			continue;2003		}2004		ret = sscanf(line, "# Age=V%d_%d", &major, &minor);2005		if (ret == 2) {2006			ages[++gen] = UNICODE_AGE(major, minor, 0);2007			if (verbose > 1)2008				printf(" Age V%d_%d = %d\n",2009					major, minor, gen);2010			if (!age_valid(major, minor, 0))2011				line_fail(age_name, line);2012			continue;2013		}2014		ret = sscanf(line, "%X..%X ; %d.%d #",2015			     &first, &last, &major, &minor);2016		if (ret == 4) {2017			for (unichar = first; unichar <= last; unichar++)2018				unicode_data[unichar].gen = gen;2019			count += 1 + last - first;2020			if (verbose > 1)2021				printf("  %X..%X gen %d\n", first, last, gen);2022			if (!utf32valid(first) || !utf32valid(last))2023				line_fail(age_name, line);2024			continue;2025		}2026		ret = sscanf(line, "%X ; %d.%d #", &unichar, &major, &minor);2027		if (ret == 3) {2028			unicode_data[unichar].gen = gen;2029			count++;2030			if (verbose > 1)2031				printf("  %X gen %d\n", unichar, gen);2032			if (!utf32valid(unichar))2033				line_fail(age_name, line);2034			continue;2035		}2036	}2037	unicode_maxage = ages[gen];2038	fclose(file);2039 2040	/* Nix surrogate block */2041	if (verbose > 1)2042		printf(" Removing surrogate block D800..DFFF\n");2043	for (unichar = 0xd800; unichar <= 0xdfff; unichar++)2044		unicode_data[unichar].gen = -1;2045 2046	if (verbose > 0)2047	        printf("Found %d entries\n", count);2048	if (count == 0)2049		file_fail(age_name);2050}2051 2052static void ccc_init(void)2053{2054	FILE *file;2055	unsigned int first;2056	unsigned int last;2057	unsigned int unichar;2058	unsigned int value;2059	int count;2060	int ret;2061 2062	if (verbose > 0)2063		printf("Parsing %s\n", ccc_name);2064 2065	file = fopen(ccc_name, "r");2066	if (!file)2067		open_fail(ccc_name, errno);2068 2069	count = 0;2070	while (fgets(line, LINESIZE, file)) {2071		ret = sscanf(line, "%X..%X ; %d #", &first, &last, &value);2072		if (ret == 3) {2073			for (unichar = first; unichar <= last; unichar++) {2074				unicode_data[unichar].ccc = value;2075                                count++;2076			}2077			if (verbose > 1)2078				printf(" %X..%X ccc %d\n", first, last, value);2079			if (!utf32valid(first) || !utf32valid(last))2080				line_fail(ccc_name, line);2081			continue;2082		}2083		ret = sscanf(line, "%X ; %d #", &unichar, &value);2084		if (ret == 2) {2085			unicode_data[unichar].ccc = value;2086                        count++;2087			if (verbose > 1)2088				printf(" %X ccc %d\n", unichar, value);2089			if (!utf32valid(unichar))2090				line_fail(ccc_name, line);2091			continue;2092		}2093	}2094	fclose(file);2095 2096	if (verbose > 0)2097		printf("Found %d entries\n", count);2098	if (count == 0)2099		file_fail(ccc_name);2100}2101 2102static int ignore_compatibility_form(char *type)2103{2104	int i;2105	char *ignored_types[] = {"font", "noBreak", "initial", "medial",2106				 "final", "isolated", "circle", "super",2107				 "sub", "vertical", "wide", "narrow",2108				 "small", "square", "fraction", "compat"};2109 2110	for (i = 0 ; i < ARRAY_SIZE(ignored_types); i++)2111		if (strcmp(type, ignored_types[i]) == 0)2112			return 1;2113	return 0;2114}2115 2116static void nfdi_init(void)2117{2118	FILE *file;2119	unsigned int unichar;2120	unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */2121	char *s;2122	char *type;2123	unsigned int *um;2124	int count;2125	int i;2126	int ret;2127 2128	if (verbose > 0)2129		printf("Parsing %s\n", data_name);2130	file = fopen(data_name, "r");2131	if (!file)2132		open_fail(data_name, errno);2133 2134	count = 0;2135	while (fgets(line, LINESIZE, file)) {2136		ret = sscanf(line, "%X;%*[^;];%*[^;];%*[^;];%*[^;];%[^;];",2137			     &unichar, buf0);2138		if (ret != 2)2139			continue;2140		if (!utf32valid(unichar))2141			line_fail(data_name, line);2142 2143		s = buf0;2144		/* skip over <tag> */2145		if (*s == '<') {2146			type = ++s;2147			while (*++s != '>');2148			*s++ = '\0';2149			if(ignore_compatibility_form(type))2150				continue;2151		}2152		/* decode the decomposition into UTF-32 */2153		i = 0;2154		while (*s) {2155			mapping[i] = strtoul(s, &s, 16);2156			if (!utf32valid(mapping[i]))2157				line_fail(data_name, line);2158			i++;2159		}2160		mapping[i++] = 0;2161 2162		um = malloc(i * sizeof(unsigned int));2163		memcpy(um, mapping, i * sizeof(unsigned int));2164		unicode_data[unichar].utf32nfdi = um;2165 2166		if (verbose > 1)2167			print_utf32nfdi(unichar);2168		count++;2169	}2170	fclose(file);2171	if (verbose > 0)2172		printf("Found %d entries\n", count);2173	if (count == 0)2174		file_fail(data_name);2175}2176 2177static void nfdicf_init(void)2178{2179	FILE *file;2180	unsigned int unichar;2181	unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */2182	char status;2183	char *s;2184	unsigned int *um;2185	int i;2186	int count;2187	int ret;2188 2189	if (verbose > 0)2190		printf("Parsing %s\n", fold_name);2191	file = fopen(fold_name, "r");2192	if (!file)2193		open_fail(fold_name, errno);2194 2195	count = 0;2196	while (fgets(line, LINESIZE, file)) {2197		ret = sscanf(line, "%X; %c; %[^;];", &unichar, &status, buf0);2198		if (ret != 3)2199			continue;2200		if (!utf32valid(unichar))2201			line_fail(fold_name, line);2202		/* Use the C+F casefold. */2203		if (status != 'C' && status != 'F')2204			continue;2205		s = buf0;2206		if (*s == '<')2207			while (*s++ != ' ')2208				;2209		i = 0;2210		while (*s) {2211			mapping[i] = strtoul(s, &s, 16);2212			if (!utf32valid(mapping[i]))2213				line_fail(fold_name, line);2214			i++;2215		}2216		mapping[i++] = 0;2217 2218		um = malloc(i * sizeof(unsigned int));2219		memcpy(um, mapping, i * sizeof(unsigned int));2220		unicode_data[unichar].utf32nfdicf = um;2221 2222		if (verbose > 1)2223			print_utf32nfdicf(unichar);2224		count++;2225	}2226	fclose(file);2227	if (verbose > 0)2228		printf("Found %d entries\n", count);2229	if (count == 0)2230		file_fail(fold_name);2231}2232 2233static void corrections_init(void)2234{2235	FILE *file;2236	unsigned int unichar;2237	unsigned int major;2238	unsigned int minor;2239	unsigned int revision;2240	unsigned int age;2241	unsigned int *um;2242	unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */2243	char *s;2244	int i;2245	int count;2246	int ret;2247 2248	if (verbose > 0)2249		printf("Parsing %s\n", norm_name);2250	file = fopen(norm_name, "r");2251	if (!file)2252		open_fail(norm_name, errno);2253 2254	count = 0;2255	while (fgets(line, LINESIZE, file)) {2256		ret = sscanf(line, "%X;%[^;];%[^;];%d.%d.%d #",2257				&unichar, buf0, buf1,2258				&major, &minor, &revision);2259		if (ret != 6)2260			continue;2261		if (!utf32valid(unichar) || !age_valid(major, minor, revision))2262			line_fail(norm_name, line);2263		count++;2264	}2265	corrections = calloc(count, sizeof(struct unicode_data));2266	corrections_count = count;2267	rewind(file);2268 2269	count = 0;2270	while (fgets(line, LINESIZE, file)) {2271		ret = sscanf(line, "%X;%[^;];%[^;];%d.%d.%d #",2272				&unichar, buf0, buf1,2273				&major, &minor, &revision);2274		if (ret != 6)2275			continue;2276		if (!utf32valid(unichar) || !age_valid(major, minor, revision))2277			line_fail(norm_name, line);2278		corrections[count] = unicode_data[unichar];2279		assert(corrections[count].code == unichar);2280		age = UNICODE_AGE(major, minor, revision);2281		corrections[count].correction = age;2282 2283		i = 0;2284		s = buf0;2285		while (*s) {2286			mapping[i] = strtoul(s, &s, 16);2287			if (!utf32valid(mapping[i]))2288				line_fail(norm_name, line);2289			i++;2290		}2291		mapping[i++] = 0;2292 2293		um = malloc(i * sizeof(unsigned int));2294		memcpy(um, mapping, i * sizeof(unsigned int));2295		corrections[count].utf32nfdi = um;2296 2297		if (verbose > 1)2298			printf(" %X -> %s -> %s V%d_%d_%d\n",2299				unichar, buf0, buf1, major, minor, revision);2300		count++;2301	}2302	fclose(file);2303 2304	if (verbose > 0)2305	        printf("Found %d entries\n", count);2306	if (count == 0)2307		file_fail(norm_name);2308}2309 2310/* ------------------------------------------------------------------ */2311 2312/*2313 * Hangul decomposition (algorithm from Section 3.12 of Unicode 6.3.0)2314 *2315 * AC00;<Hangul Syllable, First>;Lo;0;L;;;;;N;;;;;2316 * D7A3;<Hangul Syllable, Last>;Lo;0;L;;;;;N;;;;;2317 *2318 * SBase = 0xAC002319 * LBase = 0x11002320 * VBase = 0x11612321 * TBase = 0x11A72322 * LCount = 192323 * VCount = 212324 * TCount = 282325 * NCount = 588 (VCount * TCount)2326 * SCount = 11172 (LCount * NCount)2327 *2328 * Decomposition:2329 *   SIndex = s - SBase2330 *2331 * LV (Canonical/Full)2332 *   LIndex = SIndex / NCount2333 *   VIndex = (Sindex % NCount) / TCount2334 *   LPart = LBase + LIndex2335 *   VPart = VBase + VIndex2336 *2337 * LVT (Canonical)2338 *   LVIndex = (SIndex / TCount) * TCount2339 *   TIndex = (Sindex % TCount)2340 *   LVPart = SBase + LVIndex2341 *   TPart = TBase + TIndex2342 *2343 * LVT (Full)2344 *   LIndex = SIndex / NCount2345 *   VIndex = (Sindex % NCount) / TCount2346 *   TIndex = (Sindex % TCount)2347 *   LPart = LBase + LIndex2348 *   VPart = VBase + VIndex2349 *   if (TIndex == 0) {2350 *          d = <LPart, VPart>2351 *   } else {2352 *          TPart = TBase + TIndex2353 *          d = <LPart, VPart, TPart>2354 *   }2355 *2356 */2357 2358static void hangul_decompose(void)2359{2360	unsigned int sb = 0xAC00;2361	unsigned int lb = 0x1100;2362	unsigned int vb = 0x1161;2363	unsigned int tb = 0x11a7;2364	/* unsigned int lc = 19; */2365	unsigned int vc = 21;2366	unsigned int tc = 28;2367	unsigned int nc = (vc * tc);2368	/* unsigned int sc = (lc * nc); */2369	unsigned int unichar;2370	unsigned int mapping[4];2371	unsigned int *um;2372        int count;2373	int i;2374 2375	if (verbose > 0)2376		printf("Decomposing hangul\n");2377	/* Hangul */2378	count = 0;2379	for (unichar = 0xAC00; unichar <= 0xD7A3; unichar++) {2380		unsigned int si = unichar - sb;2381		unsigned int li = si / nc;2382		unsigned int vi = (si % nc) / tc;2383		unsigned int ti = si % tc;2384 2385		i = 0;2386		mapping[i++] = lb + li;2387		mapping[i++] = vb + vi;2388		if (ti)2389			mapping[i++] = tb + ti;2390		mapping[i++] = 0;2391 2392		assert(!unicode_data[unichar].utf32nfdi);2393		um = malloc(i * sizeof(unsigned int));2394		memcpy(um, mapping, i * sizeof(unsigned int));2395		unicode_data[unichar].utf32nfdi = um;2396 2397		assert(!unicode_data[unichar].utf32nfdicf);2398		um = malloc(i * sizeof(unsigned int));2399		memcpy(um, mapping, i * sizeof(unsigned int));2400		unicode_data[unichar].utf32nfdicf = um;2401 2402		/*2403		 * Add a cookie as a reminder that the hangul syllable2404		 * decompositions must not be stored in the generated2405		 * trie.2406		 */2407		unicode_data[unichar].utf8nfdi = malloc(2);2408		unicode_data[unichar].utf8nfdi[0] = HANGUL;2409		unicode_data[unichar].utf8nfdi[1] = '\0';2410 2411		if (verbose > 1)2412			print_utf32nfdi(unichar);2413 2414		count++;2415	}2416	if (verbose > 0)2417		printf("Created %d entries\n", count);2418}2419 2420static void nfdi_decompose(void)2421{2422	unsigned int unichar;2423	unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */2424	unsigned int *um;2425	unsigned int *dc;2426	int count;2427	int i;2428	int j;2429	int ret;2430 2431	if (verbose > 0)2432		printf("Decomposing nfdi\n");2433 2434	count = 0;2435	for (unichar = 0; unichar != 0x110000; unichar++) {2436		if (!unicode_data[unichar].utf32nfdi)2437			continue;2438		for (;;) {2439			ret = 1;2440			i = 0;2441			um = unicode_data[unichar].utf32nfdi;2442			while (*um) {2443				dc = unicode_data[*um].utf32nfdi;2444				if (dc) {2445					for (j = 0; dc[j]; j++)2446						mapping[i++] = dc[j];2447					ret = 0;2448				} else {2449					mapping[i++] = *um;2450				}2451				um++;2452			}2453			mapping[i++] = 0;2454			if (ret)2455				break;2456			free(unicode_data[unichar].utf32nfdi);2457			um = malloc(i * sizeof(unsigned int));2458			memcpy(um, mapping, i * sizeof(unsigned int));2459			unicode_data[unichar].utf32nfdi = um;2460		}2461		/* Add this decomposition to nfdicf if there is no entry. */2462		if (!unicode_data[unichar].utf32nfdicf) {2463			um = malloc(i * sizeof(unsigned int));2464			memcpy(um, mapping, i * sizeof(unsigned int));2465			unicode_data[unichar].utf32nfdicf = um;2466		}2467		if (verbose > 1)2468			print_utf32nfdi(unichar);2469		count++;2470	}2471	if (verbose > 0)2472		printf("Processed %d entries\n", count);2473}2474 2475static void nfdicf_decompose(void)2476{2477	unsigned int unichar;2478	unsigned int mapping[19]; /* Magic - guaranteed not to be exceeded. */2479	unsigned int *um;2480	unsigned int *dc;2481	int count;2482	int i;2483	int j;2484	int ret;2485 2486	if (verbose > 0)2487		printf("Decomposing nfdicf\n");2488	count = 0;2489	for (unichar = 0; unichar != 0x110000; unichar++) {2490		if (!unicode_data[unichar].utf32nfdicf)2491			continue;2492		for (;;) {2493			ret = 1;2494			i = 0;2495			um = unicode_data[unichar].utf32nfdicf;2496			while (*um) {2497				dc = unicode_data[*um].utf32nfdicf;2498				if (dc) {2499					for (j = 0; dc[j]; j++)2500						mapping[i++] = dc[j];2501					ret = 0;2502				} else {2503					mapping[i++] = *um;2504				}2505				um++;2506			}2507			mapping[i++] = 0;2508			if (ret)2509				break;2510			free(unicode_data[unichar].utf32nfdicf);2511			um = malloc(i * sizeof(unsigned int));2512			memcpy(um, mapping, i * sizeof(unsigned int));2513			unicode_data[unichar].utf32nfdicf = um;2514		}2515		if (verbose > 1)2516			print_utf32nfdicf(unichar);2517		count++;2518	}2519	if (verbose > 0)2520		printf("Processed %d entries\n", count);2521}2522 2523/* ------------------------------------------------------------------ */2524 2525int utf8agemax(struct tree *, const char *);2526int utf8nagemax(struct tree *, const char *, size_t);2527int utf8agemin(struct tree *, const char *);2528int utf8nagemin(struct tree *, const char *, size_t);2529ssize_t utf8len(struct tree *, const char *);2530ssize_t utf8nlen(struct tree *, const char *, size_t);2531struct utf8cursor;2532int utf8cursor(struct utf8cursor *, struct tree *, const char *);2533int utf8ncursor(struct utf8cursor *, struct tree *, const char *, size_t);2534int utf8byte(struct utf8cursor *);2535 2536/*2537 * Hangul decomposition (algorithm from Section 3.12 of Unicode 6.3.0)2538 *2539 * AC00;<Hangul Syllable, First>;Lo;0;L;;;;;N;;;;;2540 * D7A3;<Hangul Syllable, Last>;Lo;0;L;;;;;N;;;;;2541 *2542 * SBase = 0xAC002543 * LBase = 0x11002544 * VBase = 0x11612545 * TBase = 0x11A72546 * LCount = 192547 * VCount = 212548 * TCount = 282549 * NCount = 588 (VCount * TCount)2550 * SCount = 11172 (LCount * NCount)2551 *2552 * Decomposition:2553 *   SIndex = s - SBase2554 *2555 * LV (Canonical/Full)2556 *   LIndex = SIndex / NCount2557 *   VIndex = (Sindex % NCount) / TCount2558 *   LPart = LBase + LIndex2559 *   VPart = VBase + VIndex2560 *2561 * LVT (Canonical)2562 *   LVIndex = (SIndex / TCount) * TCount2563 *   TIndex = (Sindex % TCount)2564 *   LVPart = SBase + LVIndex2565 *   TPart = TBase + TIndex2566 *2567 * LVT (Full)2568 *   LIndex = SIndex / NCount2569 *   VIndex = (Sindex % NCount) / TCount2570 *   TIndex = (Sindex % TCount)2571 *   LPart = LBase + LIndex2572 *   VPart = VBase + VIndex2573 *   if (TIndex == 0) {2574 *          d = <LPart, VPart>2575 *   } else {2576 *          TPart = TBase + TIndex2577 *          d = <LPart, VPart, TPart>2578 *   }2579 */2580 2581/* Constants */2582#define SB	(0xAC00)2583#define LB	(0x1100)2584#define VB	(0x1161)2585#define TB	(0x11A7)2586#define LC	(19)2587#define VC	(21)2588#define TC	(28)2589#define NC	(VC * TC)2590#define SC	(LC * NC)2591 2592/* Algorithmic decomposition of hangul syllable. */2593static utf8leaf_t *utf8hangul(const char *str, unsigned char *hangul)2594{2595	unsigned int	si;2596	unsigned int	li;2597	unsigned int	vi;2598	unsigned int	ti;2599	unsigned char	*h;2600 2601	/* Calculate the SI, LI, VI, and TI values. */2602	si = utf8decode(str) - SB;2603	li = si / NC;2604	vi = (si % NC) / TC;2605	ti = si % TC;2606 2607	/* Fill in base of leaf. */2608	h = hangul;2609	LEAF_GEN(h) = 2;2610	LEAF_CCC(h) = DECOMPOSE;2611	h += 2;2612 2613	/* Add LPart, a 3-byte UTF-8 sequence. */2614	h += utf8encode((char *)h, li + LB);2615 2616	/* Add VPart, a 3-byte UTF-8 sequence. */2617	h += utf8encode((char *)h, vi + VB);2618 2619	/* Add TPart if required, also a 3-byte UTF-8 sequence. */2620	if (ti)2621		h += utf8encode((char *)h, ti + TB);2622 2623	/* Terminate string. */2624	h[0] = '\0';2625 2626	return hangul;2627}2628 2629/*2630 * Use trie to scan s, touching at most len bytes.2631 * Returns the leaf if one exists, NULL otherwise.2632 *2633 * A non-NULL return guarantees that the UTF-8 sequence starting at s2634 * is well-formed and corresponds to a known unicode code point.  The2635 * shorthand for this will be "is valid UTF-8 unicode".2636 */2637static utf8leaf_t *utf8nlookup(struct tree *tree, unsigned char *hangul,2638			       const char *s, size_t len)2639{2640	utf8trie_t	*trie;2641	int		offlen;2642	int		offset;2643	int		mask;2644	int		node;2645 2646	if (!tree)2647		return NULL;2648	if (len == 0)2649		return NULL;2650	node = 1;2651	trie = utf8data + tree->index;2652	while (node) {2653		offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT;2654		if (*trie & NEXTBYTE) {2655			if (--len == 0)2656				return NULL;2657			s++;2658		}2659		mask = 1 << (*trie & BITNUM);2660		if (*s & mask) {2661			/* Right leg */2662			if (offlen) {2663				/* Right node at offset of trie */2664				node = (*trie & RIGHTNODE);2665				offset = trie[offlen];2666				while (--offlen) {2667					offset <<= 8;2668					offset |= trie[offlen];2669				}2670				trie += offset;2671			} else if (*trie & RIGHTPATH) {2672				/* Right node after this node */2673				node = (*trie & TRIENODE);2674				trie++;2675			} else {2676				/* No right node. */2677				return NULL;2678			}2679		} else {2680			/* Left leg */2681			if (offlen) {2682				/* Left node after this node. */2683				node = (*trie & LEFTNODE);2684				trie += offlen + 1;2685			} else if (*trie & RIGHTPATH) {2686				/* No left node. */2687				return NULL;2688			} else {2689				/* Left node after this node */2690				node = (*trie & TRIENODE);2691				trie++;2692			}2693		}2694	}2695	/*2696	 * Hangul decomposition is done algorithmically. These are the2697	 * codepoints >= 0xAC00 and <= 0xD7A3. Their UTF-8 encoding is2698	 * always 3 bytes long, so s has been advanced twice, and the2699	 * start of the sequence is at s-2.2700	 */2701	if (LEAF_CCC(trie) == DECOMPOSE && LEAF_STR(trie)[0] == HANGUL)2702		trie = utf8hangul(s - 2, hangul);2703	return trie;2704}2705 2706/*2707 * Use trie to scan s.2708 * Returns the leaf if one exists, NULL otherwise.2709 *2710 * Forwards to trie_nlookup().2711 */2712static utf8leaf_t *utf8lookup(struct tree *tree, unsigned char *hangul,2713			      const char *s)2714{2715	return utf8nlookup(tree, hangul, s, (size_t)-1);2716}2717 2718/*2719 * Return the number of bytes used by the current UTF-8 sequence.2720 * Assumes the input points to the first byte of a valid UTF-82721 * sequence.2722 */2723static inline int utf8clen(const char *s)2724{2725	unsigned char c = *s;2726	return 1 + (c >= 0xC0) + (c >= 0xE0) + (c >= 0xF0);2727}2728 2729/*2730 * Maximum age of any character in s.2731 * Return -1 if s is not valid UTF-8 unicode.2732 * Return 0 if only non-assigned code points are used.2733 */2734int utf8agemax(struct tree *tree, const char *s)2735{2736	utf8leaf_t	*leaf;2737	int		age = 0;2738	int		leaf_age;2739	unsigned char	hangul[UTF8HANGULLEAF];2740 2741	if (!tree)2742		return -1;2743 2744	while (*s) {2745		leaf = utf8lookup(tree, hangul, s);2746		if (!leaf)2747			return -1;2748		leaf_age = ages[LEAF_GEN(leaf)];2749		if (leaf_age <= tree->maxage && leaf_age > age)2750			age = leaf_age;2751		s += utf8clen(s);2752	}2753	return age;2754}2755 2756/*2757 * Minimum age of any character in s.2758 * Return -1 if s is not valid UTF-8 unicode.2759 * Return 0 if non-assigned code points are used.2760 */2761int utf8agemin(struct tree *tree, const char *s)2762{2763	utf8leaf_t	*leaf;2764	int		age;2765	int		leaf_age;2766	unsigned char	hangul[UTF8HANGULLEAF];2767 2768	if (!tree)2769		return -1;2770	age = tree->maxage;2771	while (*s) {2772		leaf = utf8lookup(tree, hangul, s);2773		if (!leaf)2774			return -1;2775		leaf_age = ages[LEAF_GEN(leaf)];2776		if (leaf_age <= tree->maxage && leaf_age < age)2777			age = leaf_age;2778		s += utf8clen(s);2779	}2780	return age;2781}2782 2783/*2784 * Maximum age of any character in s, touch at most len bytes.2785 * Return -1 if s is not valid UTF-8 unicode.2786 */2787int utf8nagemax(struct tree *tree, const char *s, size_t len)2788{2789	utf8leaf_t	*leaf;2790	int		age = 0;2791	int		leaf_age;2792	unsigned char	hangul[UTF8HANGULLEAF];2793 2794	if (!tree)2795		return -1;2796 2797        while (len && *s) {2798		leaf = utf8nlookup(tree, hangul, s, len);2799		if (!leaf)2800			return -1;2801		leaf_age = ages[LEAF_GEN(leaf)];2802		if (leaf_age <= tree->maxage && leaf_age > age)2803			age = leaf_age;2804		len -= utf8clen(s);2805		s += utf8clen(s);2806	}2807	return age;2808}2809 2810/*2811 * Maximum age of any character in s, touch at most len bytes.2812 * Return -1 if s is not valid UTF-8 unicode.2813 */2814int utf8nagemin(struct tree *tree, const char *s, size_t len)2815{2816	utf8leaf_t	*leaf;2817	int		leaf_age;2818	int		age;2819	unsigned char	hangul[UTF8HANGULLEAF];2820 2821	if (!tree)2822		return -1;2823	age = tree->maxage;2824        while (len && *s) {2825		leaf = utf8nlookup(tree, hangul, s, len);2826		if (!leaf)2827			return -1;2828		leaf_age = ages[LEAF_GEN(leaf)];2829		if (leaf_age <= tree->maxage && leaf_age < age)2830			age = leaf_age;2831		len -= utf8clen(s);2832		s += utf8clen(s);2833	}2834	return age;2835}2836 2837/*2838 * Length of the normalization of s.2839 * Return -1 if s is not valid UTF-8 unicode.2840 *2841 * A string of Default_Ignorable_Code_Point has length 0.2842 */2843ssize_t utf8len(struct tree *tree, const char *s)2844{2845	utf8leaf_t	*leaf;2846	size_t		ret = 0;2847	unsigned char	hangul[UTF8HANGULLEAF];2848 2849	if (!tree)2850		return -1;2851	while (*s) {2852		leaf = utf8lookup(tree, hangul, s);2853		if (!leaf)2854			return -1;2855		if (ages[LEAF_GEN(leaf)] > tree->maxage)2856			ret += utf8clen(s);2857		else if (LEAF_CCC(leaf) == DECOMPOSE)2858			ret += strlen(LEAF_STR(leaf));2859		else2860			ret += utf8clen(s);2861		s += utf8clen(s);2862	}2863	return ret;2864}2865 2866/*2867 * Length of the normalization of s, touch at most len bytes.2868 * Return -1 if s is not valid UTF-8 unicode.2869 */2870ssize_t utf8nlen(struct tree *tree, const char *s, size_t len)2871{2872	utf8leaf_t	*leaf;2873	size_t		ret = 0;2874	unsigned char	hangul[UTF8HANGULLEAF];2875 2876	if (!tree)2877		return -1;2878	while (len && *s) {2879		leaf = utf8nlookup(tree, hangul, s, len);2880		if (!leaf)2881			return -1;2882		if (ages[LEAF_GEN(leaf)] > tree->maxage)2883			ret += utf8clen(s);2884		else if (LEAF_CCC(leaf) == DECOMPOSE)2885			ret += strlen(LEAF_STR(leaf));2886		else2887			ret += utf8clen(s);2888		len -= utf8clen(s);2889		s += utf8clen(s);2890	}2891	return ret;2892}2893 2894/*2895 * Cursor structure used by the normalizer.2896 */2897struct utf8cursor {2898	struct tree	*tree;2899	const char	*s;2900	const char	*p;2901	const char	*ss;2902	const char	*sp;2903	unsigned int	len;2904	unsigned int	slen;2905	short int	ccc;2906	short int	nccc;2907	unsigned int	unichar;2908	unsigned char	hangul[UTF8HANGULLEAF];2909};2910 2911/*2912 * Set up an utf8cursor for use by utf8byte().2913 *2914 *   s      : string.2915 *   len    : length of s.2916 *   u8c    : pointer to cursor.2917 *   trie   : utf8trie_t to use for normalization.2918 *2919 * Returns -1 on error, 0 on success.2920 */2921int utf8ncursor(struct utf8cursor *u8c, struct tree *tree, const char *s,2922		size_t len)2923{2924	if (!tree)2925		return -1;2926	if (!s)2927		return -1;2928	u8c->tree = tree;2929	u8c->s = s;2930	u8c->p = NULL;2931	u8c->ss = NULL;2932	u8c->sp = NULL;2933	u8c->len = len;2934	u8c->slen = 0;2935	u8c->ccc = STOPPER;2936	u8c->nccc = STOPPER;2937	u8c->unichar = 0;2938	/* Check we didn't clobber the maximum length. */2939	if (u8c->len != len)2940		return -1;2941	/* The first byte of s may not be an utf8 continuation. */2942	if (len > 0 && (*s & 0xC0) == 0x80)2943		return -1;2944	return 0;2945}2946 2947/*2948 * Set up an utf8cursor for use by utf8byte().2949 *2950 *   s      : NUL-terminated string.2951 *   u8c    : pointer to cursor.2952 *   trie   : utf8trie_t to use for normalization.2953 *2954 * Returns -1 on error, 0 on success.2955 */2956int utf8cursor(struct utf8cursor *u8c, struct tree *tree, const char *s)2957{2958	return utf8ncursor(u8c, tree, s, (unsigned int)-1);2959}2960 2961/*2962 * Get one byte from the normalized form of the string described by u8c.2963 *2964 * Returns the byte cast to an unsigned char on succes, and -1 on failure.2965 *2966 * The cursor keeps track of the location in the string in u8c->s.2967 * When a character is decomposed, the current location is stored in2968 * u8c->p, and u8c->s is set to the start of the decomposition. Note2969 * that bytes from a decomposition do not count against u8c->len.2970 *2971 * Characters are emitted if they match the current CCC in u8c->ccc.2972 * Hitting end-of-string while u8c->ccc == STOPPER means we're done,2973 * and the function returns 0 in that case.2974 *2975 * Sorting by CCC is done by repeatedly scanning the string.  The2976 * values of u8c->s and u8c->p are stored in u8c->ss and u8c->sp at2977 * the start of the scan.  The first pass finds the lowest CCC to be2978 * emitted and stores it in u8c->nccc, the second pass emits the2979 * characters with this CCC and finds the next lowest CCC. This limits2980 * the number of passes to 1 + the number of different CCCs in the2981 * sequence being scanned.2982 *2983 * Therefore:2984 *  u8c->p  != NULL -> a decomposition is being scanned.2985 *  u8c->ss != NULL -> this is a repeating scan.2986 *  u8c->ccc == -1  -> this is the first scan of a repeating scan.2987 */2988int utf8byte(struct utf8cursor *u8c)2989{2990	utf8leaf_t *leaf;2991	int ccc;2992 2993	for (;;) {2994		/* Check for the end of a decomposed character. */2995		if (u8c->p && *u8c->s == '\0') {2996			u8c->s = u8c->p;2997			u8c->p = NULL;2998		}2999 3000		/* Check for end-of-string. */3001		if (!u8c->p && (u8c->len == 0 || *u8c->s == '\0')) {3002			/* There is no next byte. */3003			if (u8c->ccc == STOPPER)3004				return 0;3005			/* End-of-string during a scan counts as a stopper. */3006			ccc = STOPPER;3007			goto ccc_mismatch;3008		} else if ((*u8c->s & 0xC0) == 0x80) {3009			/* This is a continuation of the current character. */3010			if (!u8c->p)3011				u8c->len--;3012			return (unsigned char)*u8c->s++;3013		}3014 3015		/* Look up the data for the current character. */3016		if (u8c->p) {3017			leaf = utf8lookup(u8c->tree, u8c->hangul, u8c->s);3018		} else {3019			leaf = utf8nlookup(u8c->tree, u8c->hangul,3020					   u8c->s, u8c->len);3021		}3022 3023		/* No leaf found implies that the input is a binary blob. */3024		if (!leaf)3025			return -1;3026 3027		/* Characters that are too new have CCC 0. */3028		if (ages[LEAF_GEN(leaf)] > u8c->tree->maxage) {3029			ccc = STOPPER;3030		} else if ((ccc = LEAF_CCC(leaf)) == DECOMPOSE) {3031			u8c->len -= utf8clen(u8c->s);3032			u8c->p = u8c->s + utf8clen(u8c->s);3033			u8c->s = LEAF_STR(leaf);3034			/* Empty decomposition implies CCC 0. */3035			if (*u8c->s == '\0') {3036				if (u8c->ccc == STOPPER)3037					continue;3038				ccc = STOPPER;3039				goto ccc_mismatch;3040			}3041			leaf = utf8lookup(u8c->tree, u8c->hangul, u8c->s);3042			ccc = LEAF_CCC(leaf);3043		}3044		u8c->unichar = utf8decode(u8c->s);3045 3046		/*3047		 * If this is not a stopper, then see if it updates3048		 * the next canonical class to be emitted.3049		 */3050		if (ccc != STOPPER && u8c->ccc < ccc && ccc < u8c->nccc)3051			u8c->nccc = ccc;3052 3053		/*3054		 * Return the current byte if this is the current3055		 * combining class.3056		 */3057		if (ccc == u8c->ccc) {3058			if (!u8c->p)3059				u8c->len--;3060			return (unsigned char)*u8c->s++;3061		}3062 3063		/* Current combining class mismatch. */3064	ccc_mismatch:3065		if (u8c->nccc == STOPPER) {3066			/*3067			 * Scan forward for the first canonical class3068			 * to be emitted.  Save the position from3069			 * which to restart.3070			 */3071			assert(u8c->ccc == STOPPER);3072			u8c->ccc = MINCCC - 1;3073			u8c->nccc = ccc;3074			u8c->sp = u8c->p;3075			u8c->ss = u8c->s;3076			u8c->slen = u8c->len;3077			if (!u8c->p)3078				u8c->len -= utf8clen(u8c->s);3079			u8c->s += utf8clen(u8c->s);3080		} else if (ccc != STOPPER) {3081			/* Not a stopper, and not the ccc we're emitting. */3082			if (!u8c->p)3083				u8c->len -= utf8clen(u8c->s);3084			u8c->s += utf8clen(u8c->s);3085		} else if (u8c->nccc != MAXCCC + 1) {3086			/* At a stopper, restart for next ccc. */3087			u8c->ccc = u8c->nccc;3088			u8c->nccc = MAXCCC + 1;3089			u8c->s = u8c->ss;3090			u8c->p = u8c->sp;3091			u8c->len = u8c->slen;3092		} else {3093			/* All done, proceed from here. */3094			u8c->ccc = STOPPER;3095			u8c->nccc = STOPPER;3096			u8c->sp = NULL;3097			u8c->ss = NULL;3098			u8c->slen = 0;3099		}3100	}3101}3102 3103/* ------------------------------------------------------------------ */3104 3105static int normalize_line(struct tree *tree)3106{3107	char *s;3108	char *t;3109	int c;3110	struct utf8cursor u8c;3111 3112	/* First test: null-terminated string. */3113	s = buf2;3114	t = buf3;3115	if (utf8cursor(&u8c, tree, s))3116		return -1;3117	while ((c = utf8byte(&u8c)) > 0)3118		if (c != (unsigned char)*t++)3119			return -1;3120	if (c < 0)3121		return -1;3122	if (*t != 0)3123		return -1;3124 3125	/* Second test: length-limited string. */3126	s = buf2;3127	/* Replace NUL with a value that will cause an error if seen. */3128	s[strlen(s) + 1] = -1;3129	t = buf3;3130	if (utf8cursor(&u8c, tree, s))3131		return -1;3132	while ((c = utf8byte(&u8c)) > 0)3133		if (c != (unsigned char)*t++)3134			return -1;3135	if (c < 0)3136		return -1;3137	if (*t != 0)3138		return -1;3139 3140	return 0;3141}3142 3143static void normalization_test(void)3144{3145	FILE *file;3146	unsigned int unichar;3147	struct unicode_data *data;3148	char *s;3149	char *t;3150	int ret;3151	int ignorables;3152	int tests = 0;3153	int failures = 0;3154 3155	if (verbose > 0)3156		printf("Parsing %s\n", test_name);3157	/* Step one, read data from file. */3158	file = fopen(test_name, "r");3159	if (!file)3160		open_fail(test_name, errno);3161 3162	while (fgets(line, LINESIZE, file)) {3163		ret = sscanf(line, "%[^;];%*[^;];%[^;];%*[^;];%*[^;];",3164			     buf0, buf1);3165		if (ret != 2 || *line == '#')3166			continue;3167		s = buf0;3168		t = buf2;3169		while (*s) {3170			unichar = strtoul(s, &s, 16);3171			t += utf8encode(t, unichar);3172		}3173		*t = '\0';3174 3175		ignorables = 0;3176		s = buf1;3177		t = buf3;3178		while (*s) {3179			unichar = strtoul(s, &s, 16);3180			data = &unicode_data[unichar];3181			if (data->utf8nfdi && !*data->utf8nfdi)3182				ignorables = 1;3183			else3184				t += utf8encode(t, unichar);3185		}3186		*t = '\0';3187 3188		tests++;3189		if (normalize_line(nfdi_tree) < 0) {3190			printf("Line %s -> %s", buf0, buf1);3191			if (ignorables)3192				printf(" (ignorables removed)");3193			printf(" failure\n");3194			failures++;3195		}3196	}3197	fclose(file);3198	if (verbose > 0)3199		printf("Ran %d tests with %d failures\n", tests, failures);3200	if (failures)3201		file_fail(test_name);3202}3203 3204/* ------------------------------------------------------------------ */3205 3206static void write_file(void)3207{3208	FILE *file;3209	int i;3210	int j;3211	int t;3212	int gen;3213 3214	if (verbose > 0)3215		printf("Writing %s\n", utf8_name);3216	file = fopen(utf8_name, "w");3217	if (!file)3218		open_fail(utf8_name, errno);3219 3220	fprintf(file, "/* This file is generated code, do not edit. */\n");3221	fprintf(file, "\n");3222	fprintf(file, "#include <linux/module.h>\n");3223	fprintf(file, "#include <linux/kernel.h>\n");3224	fprintf(file, "#include \"utf8n.h\"\n");3225	fprintf(file, "\n");3226	fprintf(file, "static const unsigned int utf8agetab[] = {\n");3227	for (i = 0; i != ages_count; i++)3228		fprintf(file, "\t%#x%s\n", ages[i],3229			ages[i] == unicode_maxage ? "" : ",");3230	fprintf(file, "};\n");3231	fprintf(file, "\n");3232	fprintf(file, "static const struct utf8data utf8nfdicfdata[] = {\n");3233	t = 0;3234	for (gen = 0; gen < ages_count; gen++) {3235		fprintf(file, "\t{ %#x, %d }%s\n",3236			ages[gen], trees[t].index,3237			ages[gen] == unicode_maxage ? "" : ",");3238		if (trees[t].maxage == ages[gen])3239			t += 2;3240	}3241	fprintf(file, "};\n");3242	fprintf(file, "\n");3243	fprintf(file, "static const struct utf8data utf8nfdidata[] = {\n");3244	t = 1;3245	for (gen = 0; gen < ages_count; gen++) {3246		fprintf(file, "\t{ %#x, %d }%s\n",3247			ages[gen], trees[t].index,3248			ages[gen] == unicode_maxage ? "" : ",");3249		if (trees[t].maxage == ages[gen])3250			t += 2;3251	}3252	fprintf(file, "};\n");3253	fprintf(file, "\n");3254	fprintf(file, "static const unsigned char utf8data[%zd] = {\n",3255		utf8data_size);3256	t = 0;3257	for (i = 0; i != utf8data_size; i += 16) {3258		if (i == trees[t].index) {3259			fprintf(file, "\t/* %s_%x */\n",3260				trees[t].type, trees[t].maxage);3261			if (t < trees_count-1)3262				t++;3263		}3264		fprintf(file, "\t");3265		for (j = i; j != i + 16; j++)3266			fprintf(file, "0x%.2x%s", utf8data[j],3267				(j < utf8data_size -1 ? "," : ""));3268		fprintf(file, "\n");3269	}3270	fprintf(file, "};\n");3271	fprintf(file, "\n");3272	fprintf(file, "struct utf8data_table utf8_data_table = {\n");3273	fprintf(file, "\t.utf8agetab = utf8agetab,\n");3274	fprintf(file, "\t.utf8agetab_size = ARRAY_SIZE(utf8agetab),\n");3275	fprintf(file, "\n");3276	fprintf(file, "\t.utf8nfdicfdata = utf8nfdicfdata,\n");3277	fprintf(file, "\t.utf8nfdicfdata_size = ARRAY_SIZE(utf8nfdicfdata),\n");3278	fprintf(file, "\n");3279	fprintf(file, "\t.utf8nfdidata = utf8nfdidata,\n");3280	fprintf(file, "\t.utf8nfdidata_size = ARRAY_SIZE(utf8nfdidata),\n");3281	fprintf(file, "\n");3282	fprintf(file, "\t.utf8data = utf8data,\n");3283	fprintf(file, "};\n");3284	fprintf(file, "EXPORT_SYMBOL_GPL(utf8_data_table);");3285	fprintf(file, "\n");3286	fprintf(file, "MODULE_DESCRIPTION(\"UTF8 data table\");\n");3287	fprintf(file, "MODULE_LICENSE(\"GPL v2\");\n");3288	fclose(file);3289}3290 3291/* ------------------------------------------------------------------ */3292 3293int main(int argc, char *argv[])3294{3295	unsigned int unichar;3296	int opt;3297 3298	argv0 = argv[0];3299 3300	while ((opt = getopt(argc, argv, "a:c:d:f:hn:o:p:t:v")) != -1) {3301		switch (opt) {3302		case 'a':3303			age_name = optarg;3304			break;3305		case 'c':3306			ccc_name = optarg;3307			break;3308		case 'd':3309			data_name = optarg;3310			break;3311		case 'f':3312			fold_name = optarg;3313			break;3314		case 'n':3315			norm_name = optarg;3316			break;3317		case 'o':3318			utf8_name = optarg;3319			break;3320		case 'p':3321			prop_name = optarg;3322			break;3323		case 't':3324			test_name = optarg;3325			break;3326		case 'v':3327			verbose++;3328			break;3329		case 'h':3330			help();3331			exit(0);3332		default:3333			usage();3334		}3335	}3336 3337	if (verbose > 1)3338		help();3339	for (unichar = 0; unichar != 0x110000; unichar++)3340		unicode_data[unichar].code = unichar;3341	age_init();3342	ccc_init();3343	nfdi_init();3344	nfdicf_init();3345	corrections_init();3346	hangul_decompose();3347	nfdi_decompose();3348	nfdicf_decompose();3349	utf8_init();3350	trees_init();3351	trees_populate();3352	trees_reduce();3353	trees_verify();3354	/* Prevent "unused function" warning. */3355	(void)lookup(nfdi_tree, " ");3356	if (verbose > 2)3357		tree_walk(nfdi_tree);3358	if (verbose > 2)3359		tree_walk(nfdicf_tree);3360	normalization_test();3361	write_file();3362 3363	return 0;3364}3365