lib/uniname/uniname.c

   1 /* Association between Unicode characters and their names.
   2    Copyright (C) 2000-2002, 2005-2007 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify it
   5    under the terms of the GNU Library General Public License as published
   6    by the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    Library General Public License for more details.
  13
  14    You should have received a copy of the GNU Library General Public
  15    License along with this program; if not, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  17    USA.  */
  18
  19 #include <config.h>
  20
  21 /* Specification.  */
  22 #include "uniname.h"
  23
  24 #include <assert.h>
  25 #include <stdbool.h>
  26 #include <stdint.h>
  27 #include <stdio.h>
  28 #include <string.h>
  29
  30 #define SIZEOF(a) (sizeof(a) / sizeof(a[0]))
  31
  32
  33 /* Table of Unicode character names, derived from UnicodeData.txt.
  34    This table is generated in a way to minimize the memory footprint:
  35      1. its compiled size is small (less than 350 KB),
  36      2. it resides entirely in the text or read-only data segment of the
  37         executable or shared library: the table contains only immediate
  38         integers, no pointers, and the functions don't do heap allocation.
  39  */
  40 #include "uninames.h"
  41 /* It contains:
  42   static const char unicode_name_words[36303] = ...;
  43   #define UNICODE_CHARNAME_NUM_WORDS 6260
  44   static const struct { uint16_t extra_offset; uint16_t ind_offset; } unicode_name_by_length[26] = ...;
  45   #define UNICODE_CHARNAME_WORD_HANGUL 3902
  46   #define UNICODE_CHARNAME_WORD_SYLLABLE 4978
  47   #define UNICODE_CHARNAME_WORD_CJK 417
  48   #define UNICODE_CHARNAME_WORD_COMPATIBILITY 6107
  49   static const uint16_t unicode_names[68940] = ...;
  50   static const struct { uint16_t code; uint32_t name:24; } unicode_name_to_code[16626] = ...;
  51   static const struct { uint16_t code; uint32_t name:24; } unicode_code_to_name[16626] = ...;
  52   #define UNICODE_CHARNAME_MAX_LENGTH 83
  53   #define UNICODE_CHARNAME_MAX_WORDS 13
  54 */
  55
  56 /* Returns the word with a given index.  */
  57 static const char *
  58 unicode_name_word (unsigned int index, unsigned int *lengthp)
  59 {
  60   unsigned int i1;
  61   unsigned int i2;
  62   unsigned int i;
  63
  64   assert (index < UNICODE_CHARNAME_NUM_WORDS);
  65
  66   /* Binary search for i with
  67        unicode_name_by_length[i].ind_offset <= index
  68      and
  69        index < unicode_name_by_length[i+1].ind_offset
  70    */
  71
  72   i1 = 0;
  73   i2 = SIZEOF (unicode_name_by_length) - 1;
  74   while (i2 - i1 > 1)
  75     {
  76       unsigned int i = (i1 + i2) >> 1;
  77       if (unicode_name_by_length[i].ind_offset <= index)
  78         i1 = i;
  79       else
  80         i2 = i;
  81     }
  82   i = i1;
  83   assert (unicode_name_by_length[i].ind_offset <= index
  84           && index < unicode_name_by_length[i+1].ind_offset);
  85   *lengthp = i;
  86   return &unicode_name_words[unicode_name_by_length[i].extra_offset
  87                              + (index-unicode_name_by_length[i].ind_offset)*i];
  88 }
  89
  90 /* Looks up the index of a word.  */
  91 static int
  92 unicode_name_word_lookup (const char *word, unsigned int length)
  93 {
  94   if (length > 0 && length < SIZEOF (unicode_name_by_length) - 1)
  95     {
  96       /* Binary search among the words of given length.  */
  97       unsigned int extra_offset = unicode_name_by_length[length].extra_offset;
  98       unsigned int i0 = unicode_name_by_length[length].ind_offset;
  99       unsigned int i1 = i0;
 100       unsigned int i2 = unicode_name_by_length[length+1].ind_offset;
 101       while (i2 - i1 > 0)
 102         {
 103           unsigned int i = (i1 + i2) >> 1;
 104           const char *p = &unicode_name_words[extra_offset + (i-i0)*length];
 105           const char *w = word;
 106           unsigned int n = length;
 107           for (;;)
 108             {
 109               if (*p < *w)
 110                 {
 111                   if (i1 == i)
 112                     return -1;
 113                   /* Note here: i1 < i < i2.  */
 114                   i1 = i;
 115                   break;
 116                 }
 117               if (*p > *w)
 118                 {
 119                   /* Note here: i1 <= i < i2.  */
 120                   i2 = i;
 121                   break;
 122                 }
 123               p++; w++; n--;
 124               if (n == 0)
 125                 return i;
 126             }
 127         }
 128     }
 129   return -1;
 130 }
 131
 132 /* Auxiliary tables for Hangul syllable names, see the Unicode 3.0 book,
 133    sections 3.11 and 4.4.  */
 134 static const char jamo_initial_short_name[19][3] =
 135 {
 136   "G", "GG", "N", "D", "DD", "R", "M", "B", "BB", "S", "SS", "", "J", "JJ",
 137   "C", "K", "T", "P", "H"
 138 };
 139 static const char jamo_medial_short_name[21][4] =
 140 {
 141   "A", "AE", "YA", "YAE", "EO", "E", "YEO", "YE", "O", "WA", "WAE", "OE", "YO",
 142   "U", "WEO", "WE", "WI", "YU", "EU", "YI", "I"
 143 };
 144 static const char jamo_final_short_name[28][3] =
 145 {
 146   "", "G", "GG", "GS", "N", "NI", "NH", "D", "L", "LG", "LM", "LB", "LS", "LT",
 147   "LP", "LH", "M", "B", "BS", "S", "SS", "NG", "J", "C", "K", "T", "P", "H"
 148 };
 149
 150 /* Looks up the name of a Unicode character, in uppercase ASCII.
 151    Returns the filled buf, or NULL if the character does not have a name.  */
 152 char *
 153 unicode_character_name (ucs4_t c, char *buf)
 154 {
 155   if (c >= 0xAC00 && c <= 0xD7A3)
 156     {
 157       /* Special case for Hangul syllables. Keeps the tables small.  */
 158       char *ptr;
 159       unsigned int tmp;
 160       unsigned int index1;
 161       unsigned int index2;
 162       unsigned int index3;
 163       const char *q;
 164
 165       /* buf needs to have at least 16 + 7 bytes here.  */
 166       memcpy (buf, "HANGUL SYLLABLE ", 16);
 167       ptr = buf + 16;
 168
 169       tmp = c - 0xAC00;
 170       index3 = tmp % 28; tmp = tmp / 28;
 171       index2 = tmp % 21; tmp = tmp / 21;
 172       index1 = tmp;
 173
 174       q = jamo_initial_short_name[index1];
 175       while (*q != '\0')
 176         *ptr++ = *q++;
 177       q = jamo_medial_short_name[index2];
 178       while (*q != '\0')
 179         *ptr++ = *q++;
 180       q = jamo_final_short_name[index3];
 181       while (*q != '\0')
 182         *ptr++ = *q++;
 183       *ptr = '\0';
 184       return buf;
 185     }
 186   else if ((c >= 0xF900 && c <= 0xFA2D) || (c >= 0xFA30 && c <= 0xFA6A)
 187            || (c >= 0xFA70 && c <= 0xFAD9) || (c >= 0x2F800 && c <= 0x2FA1D))
 188     {
 189       /* Special case for CJK compatibility ideographs. Keeps the tables
 190          small.  */
 191       char *ptr;
 192       int i;
 193
 194       /* buf needs to have at least 28 + 5 bytes here.  */
 195       memcpy (buf, "CJK COMPATIBILITY IDEOGRAPH-", 28);
 196       ptr = buf + 28;
 197
 198       for (i = (c < 0x10000 ? 12 : 16); i >= 0; i -= 4)
 199         {
 200           unsigned int x = (c >> i) & 0xf;
 201           *ptr++ = (x < 10 ? '0' : 'A' - 10) + x;
 202         }
 203       *ptr = '\0';
 204       return buf;
 205     }
 206   else
 207     {
 208       const uint16_t *words;
 209
 210       /* Transform the code so that it fits in 16 bits.  */
 211       switch (c >> 12)
 212         {
 213         case 0x00: case 0x01: case 0x02: case 0x03: case 0x04:
 214           break;
 215         case 0x0A:
 216           c -= 0x05000;
 217           break;
 218         case 0x0F:
 219           c -= 0x09000;
 220           break;
 221         case 0x10:
 222           c -= 0x09000;
 223           break;
 224         case 0x12:
 225           c -= 0x0A000;
 226           break;
 227         case 0x1D:
 228           c -= 0x14000;
 229           break;
 230         case 0x2F:
 231           c -= 0x25000;
 232           break;
 233         case 0xE0:
 234           c -= 0xD5000;
 235           break;
 236         default:
 237           return NULL;
 238         }
 239
 240       {
 241         /* Binary search in unicode_code_to_name.  */
 242         unsigned int i1 = 0;
 243         unsigned int i2 = SIZEOF (unicode_code_to_name);
 244         for (;;)
 245           {
 246             unsigned int i = (i1 + i2) >> 1;
 247             if (unicode_code_to_name[i].code == c)
 248               {
 249                 words = &unicode_names[unicode_code_to_name[i].name];
 250                 break;
 251               }
 252             else if (unicode_code_to_name[i].code < c)
 253               {
 254                 if (i1 == i)
 255                   {
 256                     words = NULL;
 257                     break;
 258                   }
 259                 /* Note here: i1 < i < i2.  */
 260                 i1 = i;
 261               }
 262             else if (unicode_code_to_name[i].code > c)
 263               {
 264                 if (i2 == i)
 265                   {
 266                     words = NULL;
 267                     break;
 268                   }
 269                 /* Note here: i1 <= i < i2.  */
 270                 i2 = i;
 271               }
 272           }
 273       }
 274       if (words != NULL)
 275         {
 276           /* Found it in unicode_code_to_name. Now concatenate the words.  */
 277           /* buf needs to have at least UNICODE_CHARNAME_MAX_LENGTH bytes.  */
 278           char *ptr = buf;
 279           for (;;)
 280             {
 281               unsigned int wordlen;
 282               const char *word = unicode_name_word (*words>>1, &wordlen);
 283               do
 284                 *ptr++ = *word++;
 285               while (--wordlen > 0);
 286               if ((*words & 1) == 0)
 287                 break;
 288               *ptr++ = ' ';
 289               words++;
 290             }
 291           *ptr = '\0';
 292           return buf;
 293         }
 294       return NULL;
 295     }
 296 }
 297
 298 /* Looks up the Unicode character with a given name, in upper- or lowercase
 299    ASCII.  Returns the character if found, or UNINAME_INVALID if not found.  */
 300 ucs4_t
 301 unicode_name_character (const char *name)
 302 {
 303   unsigned int len = strlen (name);
 304   if (len > 1 && len <= UNICODE_CHARNAME_MAX_LENGTH)
 305     {
 306       /* Test for "word1 word2 ..." syntax.  */
 307       char buf[UNICODE_CHARNAME_MAX_LENGTH];
 308       char *ptr = buf;
 309       for (;;)
 310         {
 311           char c = *name++;
 312           if (!(c >= ' ' && c <= '~'))
 313             break;
 314           *ptr++ = (c >= 'a' && c <= 'z' ? c - 'a' + 'A' : c);
 315           if (--len == 0)
 316             goto filled_buf;
 317         }
 318       if (false)
 319       filled_buf:
 320         {
 321           /* Convert the constituents to uint16_t words.  */
 322           uint16_t words[UNICODE_CHARNAME_MAX_WORDS];
 323           uint16_t *wordptr = words;
 324           {
 325             const char *p1 = buf;
 326             for (;;)
 327               {
 328                 {
 329                   int word;
 330                   const char *p2 = p1;
 331                   while (p2 < ptr && *p2 != ' ')
 332                     p2++;
 333                   word = unicode_name_word_lookup (p1, p2 - p1);
 334                   if (word < 0)
 335                     break;
 336                   if (wordptr == &words[UNICODE_CHARNAME_MAX_WORDS])
 337                     break;
 338                   *wordptr++ = word;
 339                   if (p2 == ptr)
 340                     goto filled_words;
 341                   p1 = p2 + 1;
 342                 }
 343                 /* Special case for Hangul syllables. Keeps the tables small. */
 344                 if (wordptr == &words[2]
 345                     && words[0] == UNICODE_CHARNAME_WORD_HANGUL
 346                     && words[1] == UNICODE_CHARNAME_WORD_SYLLABLE)
 347                   {
 348                     /* Split the last word [p1..ptr) into three parts:
 349                          1) [BCDGHJKMNPRST]
 350                          2) [AEIOUWY]
 351                          3) [BCDGHIJKLMNPST]
 352                      */
 353                     const char *p2;
 354                     const char *p3;
 355                     const char *p4;
 356
 357                     p2 = p1;
 358                     while (p2 < ptr
 359                            && (*p2 == 'B' || *p2 == 'C' || *p2 == 'D'
 360                                || *p2 == 'G' || *p2 == 'H' || *p2 == 'J'
 361                                || *p2 == 'K' || *p2 == 'M' || *p2 == 'N'
 362                                || *p2 == 'P' || *p2 == 'R' || *p2 == 'S'
 363                                || *p2 == 'T'))
 364                       p2++;
 365                     p3 = p2;
 366                     while (p3 < ptr
 367                            && (*p3 == 'A' || *p3 == 'E' || *p3 == 'I'
 368                                || *p3 == 'O' || *p3 == 'U' || *p3 == 'W'
 369                                || *p3 == 'Y'))
 370                       p3++;
 371                     p4 = p3;
 372                     while (p4 < ptr
 373                            && (*p4 == 'B' || *p4 == 'C' || *p4 == 'D'
 374                                || *p4 == 'G' || *p4 == 'H' || *p4 == 'I'
 375                                || *p4 == 'J' || *p4 == 'K' || *p4 == 'L'
 376                                || *p4 == 'M' || *p4 == 'N' || *p4 == 'P'
 377                                || *p4 == 'S' || *p4 == 'T'))
 378                       p4++;
 379                     if (p4 == ptr)
 380                       {
 381                         unsigned int n1 = p2 - p1;
 382                         unsigned int n2 = p3 - p2;
 383                         unsigned int n3 = p4 - p3;
 384
 385                         if (n1 <= 2 && (n2 >= 1 && n2 <= 3) && n3 <= 2)
 386                           {
 387                             unsigned int index1;
 388
 389                             for (index1 = 0; index1 < 19; index1++)
 390                               if (memcmp(jamo_initial_short_name[index1], p1, n1) == 0
 391                                   && jamo_initial_short_name[index1][n1] == '\0')
 392                                 {
 393                                   unsigned int index2;
 394
 395                                   for (index2 = 0; index2 < 21; index2++)
 396                                     if (memcmp(jamo_medial_short_name[index2], p2, n2) == 0
 397                                         && jamo_medial_short_name[index2][n2] == '\0')
 398                                       {
 399                                         unsigned int index3;
 400
 401                                         for (index3 = 0; index3 < 28; index3++)
 402                                           if (memcmp(jamo_final_short_name[index3], p3, n3) == 0
 403                                               && jamo_final_short_name[index3][n3] == '\0')
 404                                             {
 405                                               return 0xAC00 + (index1 * 21 + index2) * 28 + index3;
 406                                             }
 407                                         break;
 408                                       }
 409                                   break;
 410                                 }
 411                           }
 412                       }
 413                   }
 414                 /* Special case for CJK compatibility ideographs. Keeps the
 415                    tables small.  */
 416                 if (wordptr == &words[2]
 417                     && words[0] == UNICODE_CHARNAME_WORD_CJK
 418                     && words[1] == UNICODE_CHARNAME_WORD_COMPATIBILITY
 419                     && p1 + 14 <= ptr
 420                     && p1 + 15 >= ptr
 421                     && memcmp (p1, "IDEOGRAPH-", 10) == 0)
 422                   {
 423                     const char *p2 = p1 + 10;
 424
 425                     if (*p2 != '0')
 426                       {
 427                         unsigned int c = 0;
 428
 429                         for (;;)
 430                           {
 431                             if (*p2 >= '0' && *p2 <= '9')
 432                               c += (*p2 - '0');
 433                             else if (*p2 >= 'A' && *p2 <= 'F')
 434                               c += (*p2 - 'A' + 10);
 435                             else
 436                               break;
 437                             p2++;
 438                             if (p2 == ptr)
 439                               {
 440                                 if ((c >= 0xF900 && c <= 0xFA2D)
 441                                     || (c >= 0xFA30 && c <= 0xFA6A)
 442                                     || (c >= 0xFA70 && c <= 0xFAD9)
 443                                     || (c >= 0x2F800 && c <= 0x2FA1D))
 444                                   return c;
 445                                 else
 446                                   break;
 447                               }
 448                             c = c << 4;
 449                           }
 450                       }
 451                   }
 452               }
 453           }
 454           if (false)
 455           filled_words:
 456             {
 457               /* Multiply by 2, to simplify later comparisons.  */
 458               unsigned int words_length = wordptr - words;
 459               {
 460                 int i = words_length - 1;
 461                 words[i] = 2 * words[i];
 462                 for (; --i >= 0; )
 463                   words[i] = 2 * words[i] + 1;
 464               }
 465               /* Binary search in unicode_name_to_code.  */
 466               {
 467                 unsigned int i1 = 0;
 468                 unsigned int i2 = SIZEOF (unicode_name_to_code);
 469                 for (;;)
 470                   {
 471                     unsigned int i = (i1 + i2) >> 1;
 472                     const uint16_t *w = words;
 473                     const uint16_t *p = &unicode_names[unicode_name_to_code[i].name];
 474                     unsigned int n = words_length;
 475                     for (;;)
 476                       {
 477                         if (*p < *w)
 478                           {
 479                             if (i1 == i)
 480                               goto name_not_found;
 481                             /* Note here: i1 < i < i2.  */
 482                             i1 = i;
 483                             break;
 484                           }
 485                         else if (*p > *w)
 486                           {
 487                             if (i2 == i)
 488                               goto name_not_found;
 489                             /* Note here: i1 <= i < i2.  */
 490                             i2 = i;
 491                             break;
 492                           }
 493                         p++; w++; n--;
 494                         if (n == 0)
 495                           {
 496                             unsigned int c = unicode_name_to_code[i].code;
 497
 498                             /* Undo the transformation to 16-bit space.  */
 499                             static const unsigned int offset[12] =
 500                               {
 501                                 0x00000, 0x00000, 0x00000, 0x00000, 0x00000,
 502                                 0x05000, 0x09000, 0x09000, 0x0A000, 0x14000,
 503                                 0x25000, 0xD5000
 504                               };
 505                             return c + offset[c >> 12];
 506                           }
 507                       }
 508                   }
 509               }
 510             name_not_found: ;
 511             }
 512         }
 513     }
 514   return UNINAME_INVALID;
 515 }