glib/gunidecomp.c

   1 /* decomp.c - Character decomposition.
   2  *
   3  *  Copyright (C) 1999, 2000 Tom Tromey
   4  *  Copyright 2000 Red Hat, Inc.
   5  *
   6  * The Gnome Library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public License as
   8  * published by the Free Software Foundation; either version 2 of the
   9  * License, or (at your option) any later version.
  10  *
  11  * The Gnome Library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with the Gnome Library; see the file COPYING.LIB.  If not,
  18  * write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19  *   Boston, MA 02111-1307, USA.
  20  */
  21
  22 #include "config.h"
  23
  24 #include <stdlib.h>
  25
  26 #include "glib.h"
  27 #include "gunidecomp.h"
  28 #include "gunicomp.h"
  29 #include "gunicodeprivate.h"
  30 #include "galias.h"
  31
  32
  33 #define CC_PART1(Page, Char) \
  34   ((combining_class_table_part1[Page] >= G_UNICODE_MAX_TABLE_INDEX) \
  35    ? (combining_class_table_part1[Page] - G_UNICODE_MAX_TABLE_INDEX) \
  36    : (cclass_data[combining_class_table_part1[Page]][Char]))
  37
  38 #define CC_PART2(Page, Char) \
  39   ((combining_class_table_part2[Page] >= G_UNICODE_MAX_TABLE_INDEX) \
  40    ? (combining_class_table_part2[Page] - G_UNICODE_MAX_TABLE_INDEX) \
  41    : (cclass_data[combining_class_table_part2[Page]][Char]))
  42
  43 #define COMBINING_CLASS(Char) \
  44   (((Char) <= G_UNICODE_LAST_CHAR_PART1) \
  45    ? CC_PART1 ((Char) >> 8, (Char) & 0xff) \
  46    : (((Char) >= 0xe0000 && (Char) <= G_UNICODE_LAST_CHAR) \
  47       ? CC_PART2 (((Char) - 0xe0000) >> 8, (Char) & 0xff) \
  48       : 0))
  49
  50 gint
  51 _g_unichar_combining_class (gunichar uc)
  52 {
  53   return COMBINING_CLASS (uc);
  54 }
  55
  56 /* constants for hangul syllable [de]composition */
  57 #define SBase 0xAC00
  58 #define LBase 0x1100
  59 #define VBase 0x1161
  60 #define TBase 0x11A7
  61 #define LCount 19
  62 #define VCount 21
  63 #define TCount 28
  64 #define NCount (VCount * TCount)
  65 #define SCount (LCount * NCount)
  66
  67 /**
  68  * g_unicode_canonical_ordering:
  69  * @string: a UCS-4 encoded string.
  70  * @len: the maximum length of @string to use.
  71  *
  72  * Computes the canonical ordering of a string in-place.
  73  * This rearranges decomposed characters in the string
  74  * according to their combining classes.  See the Unicode
  75  * manual for more information.
  76  **/
  77 void
  78 g_unicode_canonical_ordering (gunichar *string,
  79                               gsize     len)
  80 {
  81   gsize i;
  82   int swap = 1;
  83
  84   while (swap)
  85     {
  86       int last;
  87       swap = 0;
  88       last = COMBINING_CLASS (string[0]);
  89       for (i = 0; i < len - 1; ++i)
  90         {
  91           int next = COMBINING_CLASS (string[i + 1]);
  92           if (next != 0 && last > next)
  93             {
  94               gsize j;
  95               /* Percolate item leftward through string.  */
  96               for (j = i + 1; j > 0; --j)
  97                 {
  98                   gunichar t;
  99                   if (COMBINING_CLASS (string[j - 1]) <= next)
 100                     break;
 101                   t = string[j];
 102                   string[j] = string[j - 1];
 103                   string[j - 1] = t;
 104                   swap = 1;
 105                 }
 106               /* We're re-entering the loop looking at the old
 107                  character again.  */
 108               next = last;
 109             }
 110           last = next;
 111         }
 112     }
 113 }
 114
 115 /* http://www.unicode.org/unicode/reports/tr15/#Hangul
 116  * r should be null or have sufficient space. Calling with r == NULL will
 117  * only calculate the result_len; however, a buffer with space for three
 118  * characters will always be big enough. */
 119 static void
 120 decompose_hangul (gunichar s,
 121                   gunichar *r,
 122                   gsize *result_len)
 123 {
 124   gint SIndex = s - SBase;
 125
 126   /* not a hangul syllable */
 127   if (SIndex < 0 || SIndex >= SCount)
 128     {
 129       if (r)
 130         r[0] = s;
 131       *result_len = 1;
 132     }
 133   else
 134     {
 135       gunichar L = LBase + SIndex / NCount;
 136       gunichar V = VBase + (SIndex % NCount) / TCount;
 137       gunichar T = TBase + SIndex % TCount;
 138
 139       if (r)
 140         {
 141           r[0] = L;
 142           r[1] = V;
 143         }
 144
 145       if (T != TBase)
 146         {
 147           if (r)
 148             r[2] = T;
 149           *result_len = 3;
 150         }
 151       else
 152         *result_len = 2;
 153     }
 154 }
 155
 156 /* returns a pointer to a null-terminated UTF-8 string */
 157 static const gchar *
 158 find_decomposition (gunichar ch,
 159                     gboolean compat)
 160 {
 161   int start = 0;
 162   int end = G_N_ELEMENTS (decomp_table);
 163
 164   if (ch >= decomp_table[start].ch &&
 165       ch <= decomp_table[end - 1].ch)
 166     {
 167       while (TRUE)
 168         {
 169           int half = (start + end) / 2;
 170           if (ch == decomp_table[half].ch)
 171             {
 172               int offset;
 173
 174               if (compat)
 175                 {
 176                   offset = decomp_table[half].compat_offset;
 177                   if (offset == G_UNICODE_NOT_PRESENT_OFFSET)
 178                     offset = decomp_table[half].canon_offset;
 179                 }
 180               else
 181                 {
 182                   offset = decomp_table[half].canon_offset;
 183                   if (offset == G_UNICODE_NOT_PRESENT_OFFSET)
 184                     return NULL;
 185                 }
 186
 187               return &(decomp_expansion_string[offset]);
 188             }
 189           else if (half == start)
 190             break;
 191           else if (ch > decomp_table[half].ch)
 192             start = half;
 193           else
 194             end = half;
 195         }
 196     }
 197
 198   return NULL;
 199 }
 200
 201 /**
 202  * g_unicode_canonical_decomposition:
 203  * @ch: a Unicode character.
 204  * @result_len: location to store the length of the return value.
 205  *
 206  * Computes the canonical decomposition of a Unicode character.
 207  *
 208  * Return value: a newly allocated string of Unicode characters.
 209  *   @result_len is set to the resulting length of the string.
 210  **/
 211 gunichar *
 212 g_unicode_canonical_decomposition (gunichar ch,
 213                                    gsize   *result_len)
 214 {
 215   const gchar *decomp;
 216   const gchar *p;
 217   gunichar *r;
 218
 219   /* Hangul syllable */
 220   if (ch >= 0xac00 && ch <= 0xd7a3)
 221     {
 222       decompose_hangul (ch, NULL, result_len);
 223       r = g_malloc (*result_len * sizeof (gunichar));
 224       decompose_hangul (ch, r, result_len);
 225     }
 226   else if ((decomp = find_decomposition (ch, FALSE)) != NULL)
 227     {
 228       /* Found it.  */
 229       int i;
 230
 231       *result_len = g_utf8_strlen (decomp, -1);
 232       r = g_malloc (*result_len * sizeof (gunichar));
 233
 234       for (p = decomp, i = 0; *p != '\0'; p = g_utf8_next_char (p), i++)
 235         r[i] = g_utf8_get_char (p);
 236     }
 237   else
 238     {
 239       /* Not in our table.  */
 240       r = g_malloc (sizeof (gunichar));
 241       *r = ch;
 242       *result_len = 1;
 243     }
 244
 245   /* Supposedly following the Unicode 2.1.9 table means that the
 246      decompositions come out in canonical order.  I haven't tested
 247      this, but we rely on it here.  */
 248   return r;
 249 }
 250
 251 /* L,V => LV and LV,T => LVT  */
 252 static gboolean
 253 combine_hangul (gunichar a,
 254                 gunichar b,
 255                 gunichar *result)
 256 {
 257   gint LIndex = a - LBase;
 258   gint SIndex = a - SBase;
 259
 260   gint VIndex = b - VBase;
 261   gint TIndex = b - TBase;
 262
 263   if (0 <= LIndex && LIndex < LCount
 264       && 0 <= VIndex && VIndex < VCount)
 265     {
 266       *result = SBase + (LIndex * VCount + VIndex) * TCount;
 267       return TRUE;
 268     }
 269   else if (0 <= SIndex && SIndex < SCount && (SIndex % TCount) == 0
 270            && 0 <= TIndex && TIndex <= TCount)
 271     {
 272       *result = a + TIndex;
 273       return TRUE;
 274     }
 275
 276   return FALSE;
 277 }
 278
 279 #define CI(Page, Char) \
 280   ((compose_table[Page] >= G_UNICODE_MAX_TABLE_INDEX) \
 281    ? (compose_table[Page] - G_UNICODE_MAX_TABLE_INDEX) \
 282    : (compose_data[compose_table[Page]][Char]))
 283
 284 #define COMPOSE_INDEX(Char) \
 285      (((Char >> 8) > (COMPOSE_TABLE_LAST)) ? 0 : CI((Char) >> 8, (Char) & 0xff))
 286
 287 static gboolean
 288 combine (gunichar  a,
 289          gunichar  b,
 290          gunichar *result)
 291 {
 292   gushort index_a, index_b;
 293
 294   if (combine_hangul (a, b, result))
 295     return TRUE;
 296
 297   index_a = COMPOSE_INDEX(a);
 298
 299   if (index_a >= COMPOSE_FIRST_SINGLE_START && index_a < COMPOSE_SECOND_START)
 300     {
 301       if (b == compose_first_single[index_a - COMPOSE_FIRST_SINGLE_START][0])
 302         {
 303           *result = compose_first_single[index_a - COMPOSE_FIRST_SINGLE_START][1];
 304           return TRUE;
 305         }
 306       else
 307         return FALSE;
 308     }
 309
 310   index_b = COMPOSE_INDEX(b);
 311
 312   if (index_b >= COMPOSE_SECOND_SINGLE_START)
 313     {
 314       if (a == compose_second_single[index_b - COMPOSE_SECOND_SINGLE_START][0])
 315         {
 316           *result = compose_second_single[index_b - COMPOSE_SECOND_SINGLE_START][1];
 317           return TRUE;
 318         }
 319       else
 320         return FALSE;
 321     }
 322
 323   if (index_a >= COMPOSE_FIRST_START && index_a < COMPOSE_FIRST_SINGLE_START &&
 324       index_b >= COMPOSE_SECOND_START && index_b < COMPOSE_SECOND_SINGLE_START)
 325     {
 326       gunichar res = compose_array[index_a - COMPOSE_FIRST_START][index_b - COMPOSE_SECOND_START];
 327
 328       if (res)
 329         {
 330           *result = res;
 331           return TRUE;
 332         }
 333     }
 334
 335   return FALSE;
 336 }
 337
 338 gunichar *
 339 _g_utf8_normalize_wc (const gchar    *str,
 340                       gssize          max_len,
 341                       GNormalizeMode  mode)
 342 {
 343   gsize n_wc;
 344   gunichar *wc_buffer;
 345   const char *p;
 346   gsize last_start;
 347   gboolean do_compat = (mode == G_NORMALIZE_NFKC ||
 348                         mode == G_NORMALIZE_NFKD);
 349   gboolean do_compose = (mode == G_NORMALIZE_NFC ||
 350                          mode == G_NORMALIZE_NFKC);
 351
 352   n_wc = 0;
 353   p = str;
 354   while ((max_len < 0 || p < str + max_len) && *p)
 355     {
 356       const gchar *decomp;
 357       gunichar wc = g_utf8_get_char (p);
 358
 359       if (wc >= 0xac00 && wc <= 0xd7a3)
 360         {
 361           gsize result_len;
 362           decompose_hangul (wc, NULL, &result_len);
 363           n_wc += result_len;
 364         }
 365       else
 366         {
 367           decomp = find_decomposition (wc, do_compat);
 368
 369           if (decomp)
 370             n_wc += g_utf8_strlen (decomp, -1);
 371           else
 372             n_wc++;
 373         }
 374
 375       p = g_utf8_next_char (p);
 376     }
 377
 378   wc_buffer = g_new (gunichar, n_wc + 1);
 379
 380   last_start = 0;
 381   n_wc = 0;
 382   p = str;
 383   while ((max_len < 0 || p < str + max_len) && *p)
 384     {
 385       gunichar wc = g_utf8_get_char (p);
 386       const gchar *decomp;
 387       int cc;
 388       gsize old_n_wc = n_wc;
 389
 390       if (wc >= 0xac00 && wc <= 0xd7a3)
 391         {
 392           gsize result_len;
 393           decompose_hangul (wc, wc_buffer + n_wc, &result_len);
 394           n_wc += result_len;
 395         }
 396       else
 397         {
 398           decomp = find_decomposition (wc, do_compat);
 399
 400           if (decomp)
 401             {
 402               const char *pd;
 403               for (pd = decomp; *pd != '\0'; pd = g_utf8_next_char (pd))
 404                 wc_buffer[n_wc++] = g_utf8_get_char (pd);
 405             }
 406           else
 407             wc_buffer[n_wc++] = wc;
 408         }
 409
 410       if (n_wc > 0)
 411         {
 412           cc = COMBINING_CLASS (wc_buffer[old_n_wc]);
 413
 414           if (cc == 0)
 415             {
 416               g_unicode_canonical_ordering (wc_buffer + last_start, n_wc - last_start);
 417               last_start = old_n_wc;
 418             }
 419         }
 420
 421       p = g_utf8_next_char (p);
 422     }
 423
 424   if (n_wc > 0)
 425     {
 426       g_unicode_canonical_ordering (wc_buffer + last_start, n_wc - last_start);
 427       last_start = n_wc;
 428     }
 429
 430   wc_buffer[n_wc] = 0;
 431
 432   /* All decomposed and reordered */
 433
 434   if (do_compose && n_wc > 0)
 435     {
 436       gsize i, j;
 437       int last_cc = 0;
 438       last_start = 0;
 439
 440       for (i = 0; i < n_wc; i++)
 441         {
 442           int cc = COMBINING_CLASS (wc_buffer[i]);
 443
 444           if (i > 0 &&
 445               (last_cc == 0 || last_cc != cc) &&
 446               combine (wc_buffer[last_start], wc_buffer[i],
 447                        &wc_buffer[last_start]))
 448             {
 449               for (j = i + 1; j < n_wc; j++)
 450                 wc_buffer[j-1] = wc_buffer[j];
 451               n_wc--;
 452               i--;
 453
 454               if (i == last_start)
 455                 last_cc = 0;
 456               else
 457                 last_cc = COMBINING_CLASS (wc_buffer[i-1]);
 458
 459               continue;
 460             }
 461
 462           if (cc == 0)
 463             last_start = i;
 464
 465           last_cc = cc;
 466         }
 467     }
 468
 469   wc_buffer[n_wc] = 0;
 470
 471   return wc_buffer;
 472 }
 473
 474 /**
 475  * g_utf8_normalize:
 476  * @str: a UTF-8 encoded string.
 477  * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
 478  * @mode: the type of normalization to perform.
 479  *
 480  * Converts a string into canonical form, standardizing
 481  * such issues as whether a character with an accent
 482  * is represented as a base character and combining
 483  * accent or as a single precomposed character. You
 484  * should generally call g_utf8_normalize() before
 485  * comparing two Unicode strings.
 486  *
 487  * The normalization mode %G_NORMALIZE_DEFAULT only
 488  * standardizes differences that do not affect the
 489  * text content, such as the above-mentioned accent
 490  * representation. %G_NORMALIZE_ALL also standardizes
 491  * the "compatibility" characters in Unicode, such
 492  * as SUPERSCRIPT THREE to the standard forms
 493  * (in this case DIGIT THREE). Formatting information
 494  * may be lost but for most text operations such
 495  * characters should be considered the same.
 496  * For example, g_utf8_collate() normalizes
 497  * with %G_NORMALIZE_ALL as its first step.
 498  *
 499  * %G_NORMALIZE_DEFAULT_COMPOSE and %G_NORMALIZE_ALL_COMPOSE
 500  * are like %G_NORMALIZE_DEFAULT and %G_NORMALIZE_ALL,
 501  * but returned a result with composed forms rather
 502  * than a maximally decomposed form. This is often
 503  * useful if you intend to convert the string to
 504  * a legacy encoding or pass it to a system with
 505  * less capable Unicode handling.
 506  *
 507  * Return value: a newly allocated string, that is the
 508  *   normalized form of @str.
 509  **/
 510 gchar *
 511 g_utf8_normalize (const gchar    *str,
 512                   gssize          len,
 513                   GNormalizeMode  mode)
 514 {
 515   gunichar *result_wc = _g_utf8_normalize_wc (str, len, mode);
 516   gchar *result;
 517
 518   result = g_ucs4_to_utf8 (result_wc, -1, NULL, NULL, NULL);
 519   g_free (result_wc);
 520
 521   return result;
 522 }
 523
 524 #define __G_UNIDECOMP_C__
 525 #include "galiasdef.c"