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 "gunicode.h"
  27 #include "gunidecomp.h"
  28 #include "gmem.h"
  29 #include "gunicomp.h"
  30 #include "gunicodeprivate.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 /**
  51  * g_unichar_combining_class:
  52  * @uc: a Unicode character
  53  *
  54  * Determines the canonical combining class of a Unicode character.
  55  *
  56  * Return value: the combining class of the character
  57  *
  58  * Since: 2.14
  59  **/
  60 gint
  61 g_unichar_combining_class (gunichar uc)
  62 {
  63   return COMBINING_CLASS (uc);
  64 }
  65
  66 /* constants for hangul syllable [de]composition */
  67 #define SBase 0xAC00
  68 #define LBase 0x1100
  69 #define VBase 0x1161
  70 #define TBase 0x11A7
  71 #define LCount 19
  72 #define VCount 21
  73 #define TCount 28
  74 #define NCount (VCount * TCount)
  75 #define SCount (LCount * NCount)
  76
  77 /**
  78  * g_unicode_canonical_ordering:
  79  * @string: a UCS-4 encoded string.
  80  * @len: the maximum length of @string to use.
  81  *
  82  * Computes the canonical ordering of a string in-place.
  83  * This rearranges decomposed characters in the string
  84  * according to their combining classes.  See the Unicode
  85  * manual for more information.
  86  **/
  87 void
  88 g_unicode_canonical_ordering (gunichar *string,
  89                               gsize     len)
  90 {
  91   gsize i;
  92   int swap = 1;
  93
  94   while (swap)
  95     {
  96       int last;
  97       swap = 0;
  98       last = COMBINING_CLASS (string[0]);
  99       for (i = 0; i < len - 1; ++i)
 100         {
 101           int next = COMBINING_CLASS (string[i + 1]);
 102           if (next != 0 && last > next)
 103             {
 104               gsize j;
 105               /* Percolate item leftward through string.  */
 106               for (j = i + 1; j > 0; --j)
 107                 {
 108                   gunichar t;
 109                   if (COMBINING_CLASS (string[j - 1]) <= next)
 110                     break;
 111                   t = string[j];
 112                   string[j] = string[j - 1];
 113                   string[j - 1] = t;
 114                   swap = 1;
 115                 }
 116               /* We're re-entering the loop looking at the old
 117                  character again.  */
 118               next = last;
 119             }
 120           last = next;
 121         }
 122     }
 123 }
 124
 125 /* http://www.unicode.org/unicode/reports/tr15/#Hangul
 126  * r should be null or have sufficient space. Calling with r == NULL will
 127  * only calculate the result_len; however, a buffer with space for three
 128  * characters will always be big enough. */
 129 static void
 130 decompose_hangul (gunichar s,
 131                   gunichar *r,
 132                   gsize *result_len)
 133 {
 134   gint SIndex = s - SBase;
 135   gint TIndex = SIndex % TCount;
 136
 137   if (r)
 138     {
 139       r[0] = LBase + SIndex / NCount;
 140       r[1] = VBase + (SIndex % NCount) / TCount;
 141     }
 142
 143   if (TIndex)
 144     {
 145       if (r)
 146         r[2] = TBase + TIndex;
 147       *result_len = 3;
 148     }
 149   else
 150     *result_len = 2;
 151 }
 152
 153 /* returns a pointer to a null-terminated UTF-8 string */
 154 static const gchar *
 155 find_decomposition (gunichar ch,
 156                     gboolean compat)
 157 {
 158   int start = 0;
 159   int end = G_N_ELEMENTS (decomp_table);
 160
 161   if (ch >= decomp_table[start].ch &&
 162       ch <= decomp_table[end - 1].ch)
 163     {
 164       while (TRUE)
 165         {
 166           int half = (start + end) / 2;
 167           if (ch == decomp_table[half].ch)
 168             {
 169               int offset;
 170
 171               if (compat)
 172                 {
 173                   offset = decomp_table[half].compat_offset;
 174                   if (offset == G_UNICODE_NOT_PRESENT_OFFSET)
 175                     offset = decomp_table[half].canon_offset;
 176                 }
 177               else
 178                 {
 179                   offset = decomp_table[half].canon_offset;
 180                   if (offset == G_UNICODE_NOT_PRESENT_OFFSET)
 181                     return NULL;
 182                 }
 183
 184               return &(decomp_expansion_string[offset]);
 185             }
 186           else if (half == start)
 187             break;
 188           else if (ch > decomp_table[half].ch)
 189             start = half;
 190           else
 191             end = half;
 192         }
 193     }
 194
 195   return NULL;
 196 }
 197
 198 /**
 199  * g_unicode_canonical_decomposition:
 200  * @ch: a Unicode character.
 201  * @result_len: location to store the length of the return value.
 202  *
 203  * Computes the canonical decomposition of a Unicode character.
 204  *
 205  * Return value: a newly allocated string of Unicode characters.
 206  *   @result_len is set to the resulting length of the string.
 207  *
 208  * Deprecated: 2.30: Use the more flexible g_unichar_fully_decompose()
 209  *   instead.
 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 >= SBase && ch < SBase + SCount)
 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   return r;
 246 }
 247
 248 /* L,V => LV and LV,T => LVT  */
 249 static gboolean
 250 combine_hangul (gunichar a,
 251                 gunichar b,
 252                 gunichar *result)
 253 {
 254   gint LIndex = a - LBase;
 255   gint SIndex = a - SBase;
 256
 257   gint VIndex = b - VBase;
 258   gint TIndex = b - TBase;
 259
 260   if (0 <= LIndex && LIndex < LCount
 261       && 0 <= VIndex && VIndex < VCount)
 262     {
 263       *result = SBase + (LIndex * VCount + VIndex) * TCount;
 264       return TRUE;
 265     }
 266   else if (0 <= SIndex && SIndex < SCount && (SIndex % TCount) == 0
 267            && 0 < TIndex && TIndex < TCount)
 268     {
 269       *result = a + TIndex;
 270       return TRUE;
 271     }
 272
 273   return FALSE;
 274 }
 275
 276 #define CI(Page, Char) \
 277   ((compose_table[Page] >= G_UNICODE_MAX_TABLE_INDEX) \
 278    ? (compose_table[Page] - G_UNICODE_MAX_TABLE_INDEX) \
 279    : (compose_data[compose_table[Page]][Char]))
 280
 281 #define COMPOSE_INDEX(Char) \
 282      (((Char >> 8) > (COMPOSE_TABLE_LAST)) ? 0 : CI((Char) >> 8, (Char) & 0xff))
 283
 284 static gboolean
 285 combine (gunichar  a,
 286          gunichar  b,
 287          gunichar *result)
 288 {
 289   gushort index_a, index_b;
 290
 291   if (combine_hangul (a, b, result))
 292     return TRUE;
 293
 294   index_a = COMPOSE_INDEX(a);
 295
 296   if (index_a >= COMPOSE_FIRST_SINGLE_START && index_a < COMPOSE_SECOND_START)
 297     {
 298       if (b == compose_first_single[index_a - COMPOSE_FIRST_SINGLE_START][0])
 299         {
 300           *result = compose_first_single[index_a - COMPOSE_FIRST_SINGLE_START][1];
 301           return TRUE;
 302         }
 303       else
 304         return FALSE;
 305     }
 306
 307   index_b = COMPOSE_INDEX(b);
 308
 309   if (index_b >= COMPOSE_SECOND_SINGLE_START)
 310     {
 311       if (a == compose_second_single[index_b - COMPOSE_SECOND_SINGLE_START][0])
 312         {
 313           *result = compose_second_single[index_b - COMPOSE_SECOND_SINGLE_START][1];
 314           return TRUE;
 315         }
 316       else
 317         return FALSE;
 318     }
 319
 320   if (index_a >= COMPOSE_FIRST_START && index_a < COMPOSE_FIRST_SINGLE_START &&
 321       index_b >= COMPOSE_SECOND_START && index_b < COMPOSE_SECOND_SINGLE_START)
 322     {
 323       gunichar res = compose_array[index_a - COMPOSE_FIRST_START][index_b - COMPOSE_SECOND_START];
 324
 325       if (res)
 326         {
 327           *result = res;
 328           return TRUE;
 329         }
 330     }
 331
 332   return FALSE;
 333 }
 334
 335 gunichar *
 336 _g_utf8_normalize_wc (const gchar    *str,
 337                       gssize          max_len,
 338                       GNormalizeMode  mode)
 339 {
 340   gsize n_wc;
 341   gunichar *wc_buffer;
 342   const char *p;
 343   gsize last_start;
 344   gboolean do_compat = (mode == G_NORMALIZE_NFKC ||
 345                         mode == G_NORMALIZE_NFKD);
 346   gboolean do_compose = (mode == G_NORMALIZE_NFC ||
 347                          mode == G_NORMALIZE_NFKC);
 348
 349   n_wc = 0;
 350   p = str;
 351   while ((max_len < 0 || p < str + max_len) && *p)
 352     {
 353       const gchar *decomp;
 354       gunichar wc = g_utf8_get_char (p);
 355
 356       if (wc >= SBase && wc < SBase + SCount)
 357         {
 358           gsize result_len;
 359           decompose_hangul (wc, NULL, &result_len);
 360           n_wc += result_len;
 361         }
 362       else
 363         {
 364           decomp = find_decomposition (wc, do_compat);
 365
 366           if (decomp)
 367             n_wc += g_utf8_strlen (decomp, -1);
 368           else
 369             n_wc++;
 370         }
 371
 372       p = g_utf8_next_char (p);
 373     }
 374
 375   wc_buffer = g_new (gunichar, n_wc + 1);
 376
 377   last_start = 0;
 378   n_wc = 0;
 379   p = str;
 380   while ((max_len < 0 || p < str + max_len) && *p)
 381     {
 382       gunichar wc = g_utf8_get_char (p);
 383       const gchar *decomp;
 384       int cc;
 385       gsize old_n_wc = n_wc;
 386
 387       if (wc >= SBase && wc < SBase + SCount)
 388         {
 389           gsize result_len;
 390           decompose_hangul (wc, wc_buffer + n_wc, &result_len);
 391           n_wc += result_len;
 392         }
 393       else
 394         {
 395           decomp = find_decomposition (wc, do_compat);
 396
 397           if (decomp)
 398             {
 399               const char *pd;
 400               for (pd = decomp; *pd != '\0'; pd = g_utf8_next_char (pd))
 401                 wc_buffer[n_wc++] = g_utf8_get_char (pd);
 402             }
 403           else
 404             wc_buffer[n_wc++] = wc;
 405         }
 406
 407       if (n_wc > 0)
 408         {
 409           cc = COMBINING_CLASS (wc_buffer[old_n_wc]);
 410
 411           if (cc == 0)
 412             {
 413               g_unicode_canonical_ordering (wc_buffer + last_start, n_wc - last_start);
 414               last_start = old_n_wc;
 415             }
 416         }
 417
 418       p = g_utf8_next_char (p);
 419     }
 420
 421   if (n_wc > 0)
 422     {
 423       g_unicode_canonical_ordering (wc_buffer + last_start, n_wc - last_start);
 424       last_start = n_wc;
 425     }
 426
 427   wc_buffer[n_wc] = 0;
 428
 429   /* All decomposed and reordered */
 430
 431   if (do_compose && n_wc > 0)
 432     {
 433       gsize i, j;
 434       int last_cc = 0;
 435       last_start = 0;
 436
 437       for (i = 0; i < n_wc; i++)
 438         {
 439           int cc = COMBINING_CLASS (wc_buffer[i]);
 440
 441           if (i > 0 &&
 442               (last_cc == 0 || last_cc < cc) &&
 443               combine (wc_buffer[last_start], wc_buffer[i],
 444                        &wc_buffer[last_start]))
 445             {
 446               for (j = i + 1; j < n_wc; j++)
 447                 wc_buffer[j-1] = wc_buffer[j];
 448               n_wc--;
 449               i--;
 450
 451               if (i == last_start)
 452                 last_cc = 0;
 453               else
 454                 last_cc = COMBINING_CLASS (wc_buffer[i-1]);
 455
 456               continue;
 457             }
 458
 459           if (cc == 0)
 460             last_start = i;
 461
 462           last_cc = cc;
 463         }
 464     }
 465
 466   wc_buffer[n_wc] = 0;
 467
 468   return wc_buffer;
 469 }
 470
 471 /**
 472  * g_utf8_normalize:
 473  * @str: a UTF-8 encoded string.
 474  * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
 475  * @mode: the type of normalization to perform.
 476  *
 477  * Converts a string into canonical form, standardizing
 478  * such issues as whether a character with an accent
 479  * is represented as a base character and combining
 480  * accent or as a single precomposed character. The
 481  * string has to be valid UTF-8, otherwise %NULL is
 482  * returned. You should generally call g_utf8_normalize()
 483  * before comparing two Unicode strings.
 484  *
 485  * The normalization mode %G_NORMALIZE_DEFAULT only
 486  * standardizes differences that do not affect the
 487  * text content, such as the above-mentioned accent
 488  * representation. %G_NORMALIZE_ALL also standardizes
 489  * the "compatibility" characters in Unicode, such
 490  * as SUPERSCRIPT THREE to the standard forms
 491  * (in this case DIGIT THREE). Formatting information
 492  * may be lost but for most text operations such
 493  * characters should be considered the same.
 494  *
 495  * %G_NORMALIZE_DEFAULT_COMPOSE and %G_NORMALIZE_ALL_COMPOSE
 496  * are like %G_NORMALIZE_DEFAULT and %G_NORMALIZE_ALL,
 497  * but returned a result with composed forms rather
 498  * than a maximally decomposed form. This is often
 499  * useful if you intend to convert the string to
 500  * a legacy encoding or pass it to a system with
 501  * less capable Unicode handling.
 502  *
 503  * Return value: a newly allocated string, that is the
 504  *   normalized form of @str, or %NULL if @str is not
 505  *   valid UTF-8.
 506  **/
 507 gchar *
 508 g_utf8_normalize (const gchar    *str,
 509                   gssize          len,
 510                   GNormalizeMode  mode)
 511 {
 512   gunichar *result_wc = _g_utf8_normalize_wc (str, len, mode);
 513   gchar *result;
 514
 515   result = g_ucs4_to_utf8 (result_wc, -1, NULL, NULL, NULL);
 516   g_free (result_wc);
 517
 518   return result;
 519 }
 520
 521 static gboolean
 522 decompose_hangul_step (gunichar  ch,
 523                        gunichar *a,
 524                        gunichar *b)
 525 {
 526   gint SIndex, TIndex;
 527
 528   if (ch < SBase || ch >= SBase + SCount)
 529     return FALSE;  /* not a hangul syllable */
 530
 531   SIndex = ch - SBase;
 532   TIndex = SIndex % TCount;
 533
 534   if (TIndex)
 535     {
 536       /* split LVT -> LV,T */
 537       *a = ch - TIndex;
 538       *b = TBase + TIndex;
 539     }
 540   else
 541     {
 542       /* split LV -> L,V */
 543       *a = LBase + SIndex / NCount;
 544       *b = VBase + (SIndex % NCount) / TCount;
 545     }
 546
 547   return TRUE;
 548 }
 549
 550 /**
 551  * g_unichar_decompose:
 552  * @ch: a Unicode character
 553  * @a: return location for the first component of @ch
 554  * @b: return location for the second component of @ch
 555  *
 556  * Performs a single decomposition step of the
 557  * Unicode canonical decomposition algorithm.
 558  *
 559  * This function does not include compatibility
 560  * decompositions. It does, however, include algorithmic
 561  * Hangul Jamo decomposition, as well as 'singleton'
 562  * decompositions which replace a character by a single
 563  * other character. In the case of singletons *@b will
 564  * be set to zero.
 565  *
 566  * If @ch is not decomposable, *@a is set to @ch and *@b
 567  * is set to zero.
 568  *
 569  * Note that the way Unicode decomposition pairs are
 570  * defined, it is guaranteed that @b would not decompose
 571  * further, but @a may itself decompose.  To get the full
 572  * canonical decomposition for @ch, one would need to
 573  * recursively call this function on @a.  Or use
 574  * g_unichar_fully_decompose().
 575  *
 576  * See <ulink url="http://unicode.org/reports/tr15/">UAX#15</ulink>
 577  * for details.
 578  *
 579  * Returns: %TRUE if the character could be decomposed
 580  *
 581  * Since: 2.30
 582  */
 583 gboolean
 584 g_unichar_decompose (gunichar  ch,
 585                      gunichar *a,
 586                      gunichar *b)
 587 {
 588   gint start = 0;
 589   gint end = G_N_ELEMENTS (decomp_step_table);
 590
 591   if (decompose_hangul_step (ch, a, b))
 592     return TRUE;
 593
 594   /* TODO use bsearch() */
 595   if (ch >= decomp_step_table[start].ch &&
 596       ch <= decomp_step_table[end - 1].ch)
 597     {
 598       while (TRUE)
 599         {
 600           gint half = (start + end) / 2;
 601           const decomposition_step *p = &(decomp_step_table[half]);
 602           if (ch == p->ch)
 603             {
 604               *a = p->a;
 605               *b = p->b;
 606               return TRUE;
 607             }
 608           else if (half == start)
 609             break;
 610           else if (ch > p->ch)
 611             start = half;
 612           else
 613             end = half;
 614         }
 615     }
 616
 617   *a = ch;
 618   *b = 0;
 619
 620   return FALSE;
 621 }
 622
 623 /**
 624  * g_unichar_compose:
 625  * @a: a Unicode character
 626  * @b: a Unicode character
 627  * @ch: return location for the composed character
 628  *
 629  * Performs a single composition step of the
 630  * Unicode canonical composition algorithm.
 631  *
 632  * This function does not perform algorithmic composition
 633  * for Hangul characters, and does not include compatibility
 634  * compositions. It does, however, include 'singleton'
 635  * compositions which replace a character by a single
 636  * other character. To obtain these, pass zero for @b.
 637  *
 638  * This function includes algorithmic Hangul Jamo composition.
 639  *
 640  * If @a and @b do not compose a new character, @ch is set to zero.
 641  *
 642  * See <ulink url="http://unicode.org/reports/tr15/">UAX#15</ulink>
 643  * for details.
 644  *
 645  * Returns: %TRUE if the characters could be composed
 646  *
 647  * Since: 2.30
 648  */
 649 gboolean
 650 g_unichar_compose (gunichar  a,
 651                    gunichar  b,
 652                    gunichar *ch)
 653 {
 654   if (combine (a, b, ch))
 655     return TRUE;
 656
 657   *ch = 0;
 658   return FALSE;
 659 }
 660
 661 /**
 662  * g_unichar_fully_decompose:
 663  * @ch: a Unicode character.
 664  * @compat: whether perform canonical or compatibility decomposition
 665  * @result: location to store decomposed result, or %NULL
 666  * @result_len: length of @result
 667  *
 668  * Computes the canonical or compatibility decomposition of a
 669  * Unicode character.  For compatibility decomposition,
 670  * pass %TRUE for @compat; for canonical decomposition
 671  * pass %FALSE for @compat.
 672  *
 673  * The decomposed sequence is placed in @result.  Only up to
 674  * @result_len characters are written into @result.  The length
 675  * of the full decomposition (irrespective of @result_len) is
 676  * returned by the function.  For canonical decomposition, a
 677  * result buffer of length 4 is always enough, whereas for
 678  * compatibility decomposition, a buffer of 18 is enough.
 679  *
 680  * See <ulink url="http://unicode.org/reports/tr15/">UAX#15</ulink>
 681  * for details.
 682  *
 683  * Return value: the length of the full decomposition.
 684  *
 685  * Since: 2.30
 686  **/
 687 gsize
 688 g_unichar_fully_decompose (gunichar  ch,
 689                            gboolean  compat,
 690                            gunichar *result,
 691                            gsize     result_len)
 692 {
 693   const gchar *decomp;
 694   const gchar *p;
 695
 696   /* Hangul syllable */
 697   if (ch >= SBase && ch < SBase + SCount)
 698     {
 699       gsize len, i;
 700       gunichar buffer[3];
 701       decompose_hangul (ch, result ? buffer : NULL, &len);
 702       if (result)
 703         for (i = 0; i < len && i < result_len; i++)
 704           result[i] = buffer[i];
 705       return len;
 706     }
 707   else if ((decomp = find_decomposition (ch, compat)) != NULL)
 708     {
 709       /* Found it.  */
 710       gsize len, i;
 711
 712       len = g_utf8_strlen (decomp, -1);
 713
 714       for (p = decomp, i = 0; i < len && i < result_len; p = g_utf8_next_char (p), i++)
 715         result[i] = g_utf8_get_char (p);
 716
 717       return len;
 718     }
 719
 720   /* Does not decompose */
 721   if (result && result_len >= 1)
 722     *result = ch;
 723   return 1;
 724 }