/* * Copyright (c) 2014 SGI. * All rights reserved. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation. * * This program is distributed in the hope that it would be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ /* Generator for a compact trie for unicode normalization */ #include <sys/types.h>#include <stddef.h>#include <stdlib.h>#include <stdio.h>#include <assert.h>#include <string.h>#include <unistd.h>#include <errno.h> /* Default names of the in- and output files. */ #define AGE_NAME "DerivedAge.txt"#define CCC_NAME "DerivedCombiningClass.txt"#define PROP_NAME "DerivedCoreProperties.txt"#define DATA_NAME "UnicodeData.txt"#define FOLD_NAME "CaseFolding.txt"#define NORM_NAME "NormalizationCorrections.txt"#define TEST_NAME "NormalizationTest.txt"#define UTF8_NAME "utf8data.h" const char *age_name = AGE_NAME;const char *ccc_name = CCC_NAME;const char *prop_name = PROP_NAME;const char *data_name = DATA_NAME;const char *fold_name = FOLD_NAME;const char *norm_name = NORM_NAME;const char *test_name = TEST_NAME;const char *utf8_name = UTF8_NAME; int verbose = 0; /* An arbitrary line size limit on input lines. */ #define LINESIZE 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 3433. Load more
/* * Copyright (c) 2014 SGI. * All rights reserved. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation. * * This program is distributed in the hope that it would be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ /* Generator for a compact trie for unicode normalization */ #include <sys/types.h> #include <stddef.h> #include <stdlib.h> #include <stdio.h> #include <assert.h> #include <string.h> #include <unistd.h> #include <errno.h> /* Default names of the in- and output files. */ #define AGE_NAME "DerivedAge.txt" #define CCC_NAME "DerivedCombiningClass.txt" #define PROP_NAME "DerivedCoreProperties.txt" #define DATA_NAME "UnicodeData.txt" #define FOLD_NAME "CaseFolding.txt" #define NORM_NAME "NormalizationCorrections.txt" #define TEST_NAME "NormalizationTest.txt" #define UTF8_NAME "utf8data.h" const char *age_name = AGE_NAME; const char *ccc_name = CCC_NAME; const char *prop_name = PROP_NAME; const char *data_name = DATA_NAME; const char *fold_name = FOLD_NAME; const char *norm_name = NORM_NAME; const char *test_name = TEST_NAME; const char *utf8_name = UTF8_NAME; int verbose = 0; /* An arbitrary line size limit on input lines. */ #define LINESIZE 1024 char line[LINESIZE]; char buf0[LINESIZE]; char buf1[LINESIZE]; char buf2[LINESIZE]; char buf3[LINESIZE]; const char *argv0; #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) /* ------------------------------------------------------------------ */ /* * Unicode version numbers consist of three parts: major, minor, and a * revision. These numbers are packed into an unsigned int to obtain * a single version number. * * To save space in the generated trie, the unicode version is not * stored directly, instead we calculate a generation number from the * unicode versions seen in the DerivedAge file, and use that as an * index into a table of unicode versions. */ #define UNICODE_MAJ_SHIFT (16) #define UNICODE_MIN_SHIFT (8) #define UNICODE_MAJ_MAX ((unsigned short)-1) #define UNICODE_MIN_MAX ((unsigned char)-1) #define UNICODE_REV_MAX ((unsigned char)-1) #define UNICODE_AGE(MAJ,MIN,REV) \ (((unsigned int)(MAJ) << UNICODE_MAJ_SHIFT) | \ ((unsigned int)(MIN) << UNICODE_MIN_SHIFT) | \ ((unsigned int)(REV))) unsigned int *ages; int ages_count; unsigned int unicode_maxage; static int age_valid(unsigned int major, unsigned int minor, unsigned int revision) { if (major > UNICODE_MAJ_MAX) return 0; if (minor > UNICODE_MIN_MAX) return 0; if (revision > UNICODE_REV_MAX) return 0; return 1; } /* ------------------------------------------------------------------ */ /* * utf8trie_t * * A compact binary tree, used to decode UTF-8 characters. * * Internal nodes are one byte for the node itself, and up to three * bytes for an offset into the tree. The first byte contains the * following information: * NEXTBYTE - flag - advance to next byte if set * BITNUM - 3 bit field - the bit number to tested * OFFLEN - 2 bit field - number of bytes in the offset * if offlen == 0 (non-branching node) * RIGHTPATH - 1 bit field - set if the following node is for the * right-hand path (tested bit is set) * TRIENODE - 1 bit field - set if the following node is an internal * node, otherwise it is a leaf node * if offlen != 0 (branching node) * LEFTNODE - 1 bit field - set if the left-hand node is internal * RIGHTNODE - 1 bit field - set if the right-hand node is internal * * Due to the way utf8 works, there cannot be branching nodes with * NEXTBYTE set, and moreover those nodes always have a righthand * descendant. */ typedef unsigned char utf8trie_t; #define BITNUM 0x07 #define NEXTBYTE 0x08 #define OFFLEN 0x30 #define OFFLEN_SHIFT 4 #define RIGHTPATH 0x40 #define TRIENODE 0x80 #define RIGHTNODE 0x40 #define LEFTNODE 0x80 /* * utf8leaf_t * * The leaves of the trie are embedded in the trie, and so the same * underlying datatype, unsigned char. * * leaf[0]: The unicode version, stored as a generation number that is * an index into utf8agetab[]. With this we can filter code * points based on the unicode version in which they were * defined. The CCC of a non-defined code point is 0. * leaf[1]: Canonical Combining Class. During normalization, we need * to do a stable sort into ascending order of all characters * with a non-zero CCC that occur between two characters with * a CCC of 0, or at the begin or end of a string. * The unicode standard guarantees that all CCC values are * between 0 and 254 inclusive, which leaves 255 available as * a special value. * Code points with CCC 0 are known as stoppers. * leaf[2]: Decomposition. If leaf[1] == 255, then leaf[2] is the * start of a NUL-terminated string that is the decomposition * of the character. * The CCC of a decomposable character is the same as the CCC * of the first character of its decomposition. * Some characters decompose as the empty string: these are * characters with the Default_Ignorable_Code_Point property. * These do affect normalization, as they all have CCC 0. * * The decompositions in the trie have been fully expanded. * * Casefolding, if applicable, is also done using decompositions. */ typedef unsigned char utf8leaf_t; #define LEAF_GEN(LEAF) ((LEAF)[0]) #define LEAF_CCC(LEAF) ((LEAF)[1]) #define LEAF_STR(LEAF) ((const char*)((LEAF) + 2)) #define MAXGEN (255) #define MINCCC (0) #define MAXCCC (254) #define STOPPER (0) #define DECOMPOSE (255) #define HANGUL ((char)(255)) #define UTF8HANGULLEAF (12) struct tree; static utf8leaf_t *utf8nlookup(struct tree *, unsigned char *, const char *, size_t); static utf8leaf_t *utf8lookup(struct tree *, unsigned char *, const char *); unsigned char *utf8data; size_t utf8data_size; utf8trie_t *nfdi; utf8trie_t *nfdicf; /* ------------------------------------------------------------------ */ /* * UTF8 valid ranges. * * The UTF-8 encoding spreads the bits of a 32bit word over several * bytes. This table gives the ranges that can be held and how they'd * be represented. * * 0x00000000 0x0000007F: 0xxxxxxx * 0x00000000 0x000007FF: 110xxxxx 10xxxxxx * 0x00000000 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx * 0x00000000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx * 0x00000000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx * 0x00000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx * * There is an additional requirement on UTF-8, in that only the * shortest representation of a 32bit value is to be used. A decoder * must not decode sequences that do not satisfy this requirement. * Thus the allowed ranges have a lower bound. * * 0x00000000 0x0000007F: 0xxxxxxx * 0x00000080 0x000007FF: 110xxxxx 10xxxxxx * 0x00000800 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx * 0x00010000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx * 0x00200000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx * 0x04000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx * * Actual unicode characters are limited to the range 0x0 - 0x10FFFF, * 17 planes of 65536 values. This limits the sequences actually seen * even more, to just the following. * * 0 - 0x7f: 0 0x7f * 0x80 - 0x7ff: 0xc2 0x80 0xdf 0xbf * 0x800 - 0xffff: 0xe0 0xa0 0x80 0xef 0xbf 0xbf * 0x10000 - 0x10ffff: 0xf0 0x90 0x80 0x80 0xf4 0x8f 0xbf 0xbf * * Even within those ranges not all values are allowed: the surrogates * 0xd800 - 0xdfff should never be seen. * * Note that the longest sequence seen with valid usage is 4 bytes, * the same a single UTF-32 character. This makes the UTF-8 * representation of Unicode strictly smaller than UTF-32. * * The shortest sequence requirement was introduced by: * Corrigendum #1: UTF-8 Shortest Form * It can be found here: * http://www.unicode.org/versions/corrigendum1.html * */ #define UTF8_2_BITS 0xC0 #define UTF8_3_BITS 0xE0 #define UTF8_4_BITS 0xF0 #define UTF8_N_BITS 0x80 #define UTF8_2_MASK 0xE0 #define UTF8_3_MASK 0xF0 #define UTF8_4_MASK 0xF8 #define UTF8_N_MASK 0xC0 #define UTF8_V_MASK 0x3F #define UTF8_V_SHIFT 6 static int utf8encode(char *str, unsigned int val) { int len; if (val < 0x80) { str[0] = val; len = 1; } else if (val < 0x800) { str[1] = val & UTF8_V_MASK; str[1] |= UTF8_N_BITS; val >>= UTF8_V_SHIFT; str[0] = val; str[0] |= UTF8_2_BITS; len = 2; } else if (val < 0x10000) { str[2] = val & UTF8_V_MASK; str[2] |= UTF8_N_BITS; val >>= UTF8_V_SHIFT; str[1] = val & UTF8_V_MASK; str[1] |= UTF8_N_BITS; val >>= UTF8_V_SHIFT; str[0] = val; str[0] |= UTF8_3_BITS; len = 3; } else if (val < 0x110000) { str[3] = val & UTF8_V_MASK; str[3] |= UTF8_N_BITS; val >>= UTF8_V_SHIFT; str[2] = val & UTF8_V_MASK; str[2] |= UTF8_N_BITS; val >>= UTF8_V_SHIFT; str[1] = val & UTF8_V_MASK; str[1] |= UTF8_N_BITS; val >>= UTF8_V_SHIFT; str[0] = val; str[0] |= UTF8_4_BITS; len = 4; } else { printf("%#x: illegal val\n", val); len = 0; } return len; } static unsigned int utf8decode(const char *str) { const unsigned char *s = (const unsigned char*)str; unsigned int unichar = 0; if (*s < 0x80) { unichar = *s; } else if (*s < UTF8_3_BITS) { unichar = *s++ & 0x1F; unichar <<= UTF8_V_SHIFT; unichar |= *s & 0x3F; } else if (*s < UTF8_4_BITS) { unichar = *s++ & 0x0F; unichar <<= UTF8_V_SHIFT; unichar |= *s++ & 0x3F; unichar <<= UTF8_V_SHIFT; unichar |= *s & 0x3F; } else { unichar = *s++ & 0x0F; unichar <<= UTF8_V_SHIFT; unichar |= *s++ & 0x3F; unichar <<= UTF8_V_SHIFT; unichar |= *s++ & 0x3F; unichar <<= UTF8_V_SHIFT; unichar |= *s & 0x3F; } return unichar; } static int utf32valid(unsigned int unichar) { return unichar < 0x110000; } #define HANGUL_SYLLABLE(U) ((U) >= 0xAC00 && (U) <= 0xD7A3) #define NODE 1 #define LEAF 0 struct tree { void *root; int childnode; const char *type; unsigned int maxage; struct tree *next; int (*leaf_equal)(void *, void *); void (*leaf_print)(void *, int); int (*leaf_mark)(void *); int (*leaf_size)(void *); int *(*leaf_index)(struct tree *, void *); unsigned char *(*leaf_emit)(void *, unsigned char *); int leafindex[0x110000]; int index; }; struct node { int index; int offset; int mark; int size; struct node *parent; void *left; void *right; unsigned char bitnum; unsigned char nextbyte; unsigned char leftnode; unsigned char rightnode; unsigned int keybits; unsigned int keymask; }; /* * Example lookup function for a tree. */ static void *lookup(struct tree *tree, const char *key) { struct node *node; void *leaf = NULL; node = tree->root; while (!leaf && node) { if (node->nextbyte) key++; if (*key & (1 << (node->bitnum & 7))) { /* Right leg */ if (node->rightnode == NODE) { node = node->right; } else if (node->rightnode == LEAF) { leaf = node->right; } else { node = NULL; } } else { /* Left leg */ if (node->leftnode == NODE) { node = node->left; } else if (node->leftnode == LEAF) { leaf = node->left; } else { node = NULL; } } } return leaf; } /* * A simple non-recursive tree walker: keep track of visits to the * left and right branches in the leftmask and rightmask. */ static void tree_walk(struct tree *tree) { struct node *node; unsigned int leftmask; unsigned int rightmask; unsigned int bitmask; int indent = 1; int nodes, singletons, leaves; nodes = singletons = leaves = 0; printf("%s_%x root %p\n", tree->type, tree->maxage, tree->root); if (tree->childnode == LEAF) { assert(tree->root); tree->leaf_print(tree->root, indent); leaves = 1; } else { assert(tree->childnode == NODE); node = tree->root; leftmask = rightmask = 0; while (node) { printf("%*snode @ %p bitnum %d nextbyte %d" " left %p right %p mask %x bits %x\n", indent, "", node, node->bitnum, node->nextbyte, node->left, node->right, node->keymask, node->keybits); nodes += 1; if (!(node->left && node->right)) singletons += 1; while (node) { bitmask = 1 << node->bitnum; if ((leftmask & bitmask) == 0) { leftmask |= bitmask; if (node->leftnode == LEAF) { assert(node->left); tree->leaf_print(node->left, indent+1); leaves += 1; } else if (node->left) { assert(node->leftnode == NODE); indent += 1; node = node->left; break; } } if ((rightmask & bitmask) == 0) { rightmask |= bitmask; if (node->rightnode == LEAF) { assert(node->right); tree->leaf_print(node->right, indent+1); leaves += 1; } else if (node->right) { assert(node->rightnode == NODE); indent += 1; node = node->right; break; } } leftmask &= ~bitmask; rightmask &= ~bitmask; node = node->parent; indent -= 1; } } } printf("nodes %d leaves %d singletons %d\n", nodes, leaves, singletons); } /* * Allocate an initialize a new internal node. */ static struct node *alloc_node(struct node *parent) { struct node *node; int bitnum; node = malloc(sizeof(*node)); node->left = node->right = NULL; node->parent = parent; node->leftnode = NODE;