/* Make uname2c.h from various sources.   Copyright (C) 2005-2026 Free Software Foundation, Inc.   Contributed by Jakub Jelinek <jakub@redhat.com> This program is free software; you can redistribute it and/or modify itunder the terms of the GNU General Public License as published by theFree Software Foundation; either version 3, or (at your option) anylater version. This program is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See theGNU General Public License for more details. You should have received a copy of the GNU General Public Licensealong with this program; see the file COPYING3.  If not see<http://www.gnu.org/licenses/>.  */ /* Run this program as   ./makeuname2c UnicodeData.txt NameAliases.txt > uname2c.h    This program generates 2 big arrays and 2 small ones.   The large ones are uname2c_dict, initialized by string literal   representing dictionary, and uname2c_tree, which is a space optimized   radix tree.   The format of the radix tree is:   byte 0	either 0x80 + (key[0] - ' ')	(if key_len == 1)		or key_len			(otherwise)		either of them ored with 0x40 if it has a codepoint   byte 1	LSB of offset into uname2c_dict for key	(only if key_len > 1)   byte 2	MSB of offset into uname2c_dict for key	(only if key_len > 1)		if key_len == 1, the above 2 bytes are omitted   byte 3	LSB of codepoint (only if it has a codepoint)   byte 4	middle byte of codepoint (ditto)   byte 5	MSB of codepoint (ditto), ored with 0x80 if node has children				   ored with 0x40 if it doesn't have siblings		if it doesn't have a codepoint, the above 3 bytes are omitted		and we assume that the node has children   byte 6, 7, 8	uleb128 encoded offset to first child relative to the end		of the uleb128 (only if node has children)   byte 9	0xff (only if node doesn't have a codepoint and doesn't		      have siblings)    For prefixes of Unicode NR1 or NR2 rule generated names, on a node   representing end of the prefix codepoint is 0xd800 + index into   uname2c_generated array with indexes into uname2c_pairs array of   code points (low, high) of the ranges terminated by single 0.   0xd800 is NR1 rule (Hangul syllables), rest are NR2 rules.*/ #include <assert.h>#include <stdio.h>#include <string.h>#include <stdint.h>#include <ctype.h>#include <limits.h>#include <stdarg.h>#include <stdbool.h>#include <stdlib.h> #define ARRAY_SIZE(a) (sizeof (a) / sizeof ((a)[0])) #define NUM_CODE_POINTS 0x110000#define MAX_CODE_POINT 0x10ffff#define NO_VALUE 0xdc00#define GENERATED 0xd800 struct entry { const char *name; unsigned long codepoint; };static struct entry *entries;static unsigned long num_allocated, num_entries; /* Unicode 16.0 Table 4-8.  */struct generated {  const char *prefix;  /* max_high is a workaround for UnicodeData.txt inconsistencies     on a few CJK UNIFIED IDEOGRAPH- ranges where the "*, Last>"     entry is a few code points above the end of the range.  */  unsigned long low, high, max_high;  int idx, ok;};static struct generated generated_ranges[] ={ { "HANGUL SYLLABLE ", 0xac00, 0xd7a3, 0, 0, 0 }, /* NR1 rule */  { "CJK UNIFIED IDEOGRAPH-", 0x3400, 0x4dbf, 0, 1, 0 }, /* NR2 rules */  { "CJK UNIFIED IDEOGRAPH-", 0x4e00, 0x9fff, 0, 1, 0 },  { "CJK UNIFIED IDEOGRAPH-", 0x20000, 0x2a6df, 0, 1, 0 },  { "CJK UNIFIED IDEOGRAPH-", 0x2a700, 0x2b73f, 0, 1, 0 },  { "CJK UNIFIED IDEOGRAPH-", 0x2b740, 0x2b81d, 0, 1, 0 },  { "CJK UNIFIED IDEOGRAPH-", 0x2b820, 0x2cead, 0, 1, 0 },  { "CJK UNIFIED IDEOGRAPH-", 0x2ceb0, 0x2ebe0, 0, 1, 0 },  { "CJK UNIFIED IDEOGRAPH-", 0x2ebf0, 0x2ee5d, 0, 1, 0 },  { "CJK UNIFIED IDEOGRAPH-", 0x30000, 0x3134a, 0, 1, 0 },  { "CJK UNIFIED IDEOGRAPH-", 0x31350, 0x323af, 0, 1, 0 },  { "CJK UNIFIED IDEOGRAPH-", 0x323b0, 0x33479, 0, 1, 0 },  { "EGYPTIAN HIEROGLYPH-", 0x13460, 0x143fa, 0, 2, 0 },  { "TANGUT IDEOGRAPH-", 0x17000, 0x187ff, 0, 3, 0 },  { "TANGUT IDEOGRAPH-", 0x18d00, 0x18d1e, 0, 3, 0 },  { "KHITAN SMALL SCRIPT CHARACTER-", 0x18b00, 0x18cd5, 0, 4, 0 },  { "NUSHU CHARACTER-", 0x1b170, 0x1b2fb, 0, 5, 0 },  { "CJK COMPATIBILITY IDEOGRAPH-", 0xf900, 0xfa6d, 0, 6, 0 },  { "CJK COMPATIBILITY IDEOGRAPH-", 0xfa70, 0xfad9, 0, 6, 0 },  { "CJK COMPATIBILITY IDEOGRAPH-", 0x2f800, 0x2fa1d, 0, 6, 0 }}; struct node {  struct node *sibling, *child;  const char *key;  size_t key_len, key_idx, node_size, size_sum, child_off;  unsigned long codepoint;  bool in_dict;};static struct node *root, **nodes;static unsigned long num_nodes;static size_t dict_size, tree_size, max_entry_len;static char *dict;static unsigned char *tree; /* Die!  */ static voidfail (const char *s, ...){  va_list ap;   va_start (ap, s);  vfprintf (stderr, s, ap);  va_end (ap);  fputc ('\n', stderr);  exit (1);} static void *xmalloc (size_t size){  void *ret = malloc (size);   if (ret == NULL)    fail ("failed to allocate %ld bytes", (long) size);  return ret;} static void *xrealloc (void *p, size_t size){  void *ret = p ? realloc (p, size) : malloc (size);   if (ret == NULL)    fail ("failed to allocate %ld bytes", (long) size);  return ret;} static intentrycmp (const void *p1, const void *p2){  const struct entry *e1 = (const struct entry *) p1;  const struct entry *e2 = (const struct entry *) p2;  int ret = strcmp (e1->name, e2->name);   if (ret != 0)    return ret;  if (e1->codepoint < e2->codepoint)    return -1;  if (e1->codepoint > e2->codepoint)    return 1;  return 0;} static intnodecmp (const void *p1, const void *p2){  const struct node *n1 = *(const struct node *const *) p1;  const struct node *n2 = *(const struct node *const *) p2;  if (n1->key_len > n2->key_len)    return -1;  if (n1->key_len < n2->key_len)    return 1;  return memcmp (n1->key, n2->key, n1->key_len);} /* Read UnicodeData.txt and fill in the 'decomp' table to be the   decompositions of characters for which both the character   decomposed and all the code points in the decomposition are valid   for some supported language version, and the 'all_decomp' table to   be the decompositions of all characters without those   constraints.  */ static voidread_table (char *fname, bool aliases_p){  FILE *f = fopen (fname, "r");  const char *sname = aliases_p ? "NameAliases.txt" : "UnicodeData.txt";   if (!f)    fail ("opening %s", sname);  for (;;)    {      char line[256];      unsigned long codepoint;      const char *name, *aname;      char *l;      size_t i;       if (!fgets (line, sizeof (line), f))	break;      codepoint = strtoul (line, &l, 16);      if (l == line && aliases_p)	{	  /* NameAliased.txt can contain comments and empty lines.  */	  if (*line == '#' || *line == '\n')	    continue;	}      if (l == line || *l != ';')	fail ("parsing %s, reading code point", sname);      if (codepoint > MAX_CODE_POINT)	fail ("parsing %s, code point too large", sname);       name = l + 1;      do {	++l;      } while (*l != ';');       aname = NULL;      if (aliases_p)	{	  /* Ignore figment and abbreviation aliases.  */	  if (strcmp (l + 1, "correction\n") != 0	      && strcmp (l + 1, "control\n") != 0	      && strcmp (l + 1, "alternate\n") != 0)	    continue;	  i = ARRAY_SIZE (generated_ranges);	}      else	{	  for (i = 0; i < ARRAY_SIZE (generated_ranges); ++i)	    if (codepoint >= generated_ranges[i].low		&& codepoint <= generated_ranges[i].max_high)	      break;	  if (i != ARRAY_SIZE (generated_ranges))	    {	      if (*name == '<' && l[-1] == '>')		{		  if (codepoint == generated_ranges[i].low		      && l - name >= 9		      && memcmp (l - 8, ", First>", 8) == 0		      && generated_ranges[i].ok == 0)		    {		      generated_ranges[i].ok = INT_MAX - 1;		      aname = generated_ranges[i].prefix;		      codepoint = GENERATED + generated_ranges[i].idx;		    }		  /* Unfortunately, UnicodeData.txt isn't consistent		     with the Table 4-8 range endpoints in 3 cases,		     the ranges are longer there by a few codepoints.		     So use the max_high hack to avoid verification		     failures.  */		  else if (codepoint == generated_ranges[i].max_high			   && l - name >= 8			   && memcmp (l - 7, ", Last>", 7) == 0			   && generated_ranges[i].ok == INT_MAX - 1)		    {		      generated_ranges[i].ok = INT_MAX;		      continue;		    }		  else		    fail ("unexpected generated entry %lx %.*s",			  codepoint, (int) (l - name), name);		}	      else if (codepoint		       == generated_ranges[i].low + generated_ranges[i].ok		       && l - name == (strlen (generated_ranges[i].prefix)				       + (name - 1 - line))		       && memcmp (name, generated_ranges[i].prefix,				  strlen (generated_ranges[i].prefix)) == 0		       && memcmp (name + strlen (generated_ranges[i].prefix),				  line, name - 1 - line) == 0)		{		  ++generated_ranges[i].ok;		  if (codepoint != generated_ranges[i].low)		    continue;		  aname = generated_ranges[i].prefix;		  codepoint = GENERATED + generated_ranges[i].idx;		}	      else		fail ("unexpected generated entry %lx %.*s",		      codepoint, (int) (l - name), name);	      if (aname == generated_ranges[i].prefix)		{		  size_t j; 		  /* Don't add an entry for a generated range where the		     same prefix has been added already.  */		  for (j = 0; j < i; ++j)		    if (generated_ranges[j].idx == generated_ranges[i].idx			&& generated_ranges[j].ok != 0)		      break;		  if (j < i)		    continue;		}	    }	  else if (*name == '<' && l[-1] == '>')	    continue;	}       if (num_entries == num_allocated)	{	  num_allocated = num_allocated ? 2 * num_allocated : 65536;	  entries = (struct entry *) xrealloc (entries, num_allocated							* sizeof (entries[0]));	}       if (aname == NULL)	{	  char *a = (char *) xmalloc (l + 1 - name);	  if (l - name > max_entry_len)	    max_entry_len = l - name;	  memcpy (a, name, l - name);	  a[l - name] = '\0';	  aname = a;	}      entries[num_entries].name = aname;      entries[num_entries++].codepoint = codepoint;    }  if (ferror (f))    fail ("reading %s", sname);  fclose (f);} /* Assumes nodes are added from sorted array, so we never   add any node before existing one, only after it.  */ static voidnode_add (struct node **p, const char *key, size_t key_len,	  unsigned long codepoint){  struct node *n;  size_t i;   do    {      if (*p == NULL)	{	  *p = n = (struct node *) xmalloc (sizeof (struct node));	  ++num_nodes;	  assert (key_len);	  n->sibling = NULL;	  n->child = NULL;	  n->key = key;	  n->key_len = key_len;	  n->codepoint = codepoint;	  return;	}      n = *p;      for (i = 0; i < n->key_len && i < key_len; ++i)	if (n->key[i] != key[i])	  break;      if (i == 0)	{	  p = &n->sibling;	  continue;	}      if (i == n->key_len)	{	  assert (key_len > n->key_len);	  p = &n->child;	  key += n->key_len;	  key_len -= n->key_len;	  continue;	}      /* Need to split the node.  */      assert (i < key_len);      n = (struct node *) xmalloc (sizeof (struct node));      ++num_nodes;      n->sibling = NULL;      n->child = (*p)->child;      n->key = (*p)->key + i;      n->key_len = (*p)->key_len - i;      n->codepoint = (*p)->codepoint;      (*p)->child = n;      (*p)->key_len = i;      (*p)->codepoint = NO_VALUE;      key += i;      key_len -= i;      p = &n->sibling;    }  while (1);} static voidappend_nodes (struct node *n){  for (; n; n = n->sibling)    {      nodes[num_nodes++] = n;      append_nodes (n->child);    }} static size_tsizeof_uleb128 (size_t val){  size_t sz = 0;  do    {      val >>= 7;      sz += 1;    }  while (val != 0);  return sz;} static voidsize_nodes (struct node *n){  if (n->child)    size_nodes (n->child);  if (n->sibling)    size_nodes (n->sibling);  n->node_size = 1 + (n->key_len > 1) * 2;  if (n->codepoint != NO_VALUE)    n->node_size += 3;  else if (n->sibling == NULL)    ++n->node_size;  n->size_sum = 0;  n->child_off = 0;  if (n->sibling)    n->size_sum += n->sibling->size_sum;  if (n->child)    {      n->child_off = n->size_sum + (n->codepoint == NO_VALUE				    && n->sibling == NULL);      n->node_size += sizeof_uleb128 (n->child_off);    }  n->size_sum += n->node_size;  if (n->child)    n->size_sum += n->child->size_sum;  tree_size += n->node_size;} static voidwrite_uleb128 (unsigned char *p, size_t val){  unsigned char c;  do    {      c = val & 0x7f;      val >>= 7;      if (val)	c |= 0x80;      *p++ = c;    }  while (val);} static voidwrite_nodes (struct node *n, size_t off){  for (; n; n = n->sibling)    {      assert (off < tree_size && tree[off] == 0);      if (n->key_len > 1)	{	  assert (n->key_len < 64);	  tree[off] = n->key_len;	}      else	tree[off] = (n->key[0] - ' ') | 0x80;      assert ((tree[off] & 0x40) == 0);      if (n->codepoint != NO_VALUE)	tree[off] |= 0x40;      off++;      if (n->key_len > 1)	{	  tree[off++] = n->key_idx & 0xff;	  tree[off++] = (n->key_idx >> 8) & 0xff;	}      if (n->codepoint != NO_VALUE)	{	  assert (n->codepoint < (1L << 21));	  tree[off++] = n->codepoint & 0xff;	  tree[off++] = (n->codepoint >> 8) & 0xff;	  tree[off] = (n->codepoint >> 16) & 0xff;	  if (n->child)	    tree[off] |= 0x80;	  if (!n->sibling)	    tree[off] |= 0x40;	  off++;	}      if (n->child)	{	  write_uleb128 (&tree[off], n->child_off);	  off += sizeof_uleb128 (n->child_off);	  write_nodes (n->child, off + n->child_off);	}      if (n->codepoint == NO_VALUE	  && n->sibling == NULL)	tree[off++] = 0xff;    }  assert (off <= tree_size);} static void

Lines 1–500 of 797. Load more