/* * 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	1024char 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;

Lines 1–500 of 3434. Load more