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
 136   /* not a hangul syllable */
 137   if (SIndex < 0 || SIndex >= SCount)
 138     {
 139       if (r)
 140         r[0] = s;
 141       *result_len = 1;
 142     }
 143   else
 144     {
 145       gunichar L = LBase + SIndex / NCount;
 146       gunichar V = VBase + (SIndex % NCount) / TCount;
 147       gunichar T = TBase + SIndex % TCount;
 148
 149       if (r)
 150         {
 151           r[0] = L;
 152           r[1] = V;
 153         }
 154
 155       if (T != TBase)
 156         {
 157           if (r)
 158             r[2] = T;
 159           *result_len = 3;
 160         }
 161       else
 162         *result_len = 2;
 163     }
 164 }
 165
 166 /* returns a pointer to a null-terminated UTF-8 string */
 167 static const gchar *
 168 find_decomposition (gunichar ch,
 169                     gboolean compat)
 170 {
 171   int start = 0;
 172   int end = G_N_ELEMENTS (decomp_table);
 173
 174   if (ch >= decomp_table[start].ch &&
 175       ch <= decomp_table[end - 1].ch)
 176     {
 177       while (TRUE)
 178         {
 179           int half = (start + end) / 2;
 180           if (ch == decomp_table[half].ch)
 181             {
 182               int offset;
 183
 184               if (compat)
 185                 {
 186                   offset = decomp_table[half].compat_offset;
 187                   if (offset == G_UNICODE_NOT_PRESENT_OFFSET)
 188                     offset = decomp_table[half].canon_offset;
 189                 }
 190               else
 191                 {
 192                   offset = decomp_table[half].canon_offset;
 193                   if (offset == G_UNICODE_NOT_PRESENT_OFFSET)
 194                     return NULL;
 195                 }
 196
 197               return &(decomp_expansion_string[offset]);
 198             }
 199           else if (half == start)
 200             break;
 201           else if (ch > decomp_table[half].ch)
 202             start = half;
 203           else
 204             end = half;
 205         }
 206     }
 207
 208   return NULL;
 209 }
 210
 211 /**
 212  * g_unicode_canonical_decomposition:
 213  * @ch: a Unicode character.
 214  * @result_len: location to store the length of the return value.
 215  *
 216  * Computes the canonical decomposition of a Unicode character.
 217  *
 218  * Return value: a newly allocated string of Unicode characters.
 219  *   @result_len is set to the resulting length of the string.
 220  **/
 221 gunichar *
 222 g_unicode_canonical_decomposition (gunichar ch,
 223                                    gsize   *result_len)
 224 {
 225   const gchar *decomp;
 226   const gchar *p;
 227   gunichar *r;
 228
 229   /* Hangul syllable */
 230   if (ch >= 0xac00 && ch <= 0xd7a3)
 231     {
 232       decompose_hangul (ch, NULL, result_len);
 233       r = g_malloc (*result_len * sizeof (gunichar));
 234       decompose_hangul (ch, r, result_len);
 235     }
 236   else if ((decomp = find_decomposition (ch, FALSE)) != NULL)
 237     {
 238       /* Found it.  */
 239       int i;
 240
 241       *result_len = g_utf8_strlen (decomp, -1);
 242       r = g_malloc (*result_len * sizeof (gunichar));
 243
 244       for (p = decomp, i = 0; *p != '\0'; p = g_utf8_next_char (p), i++)
 245         r[i] = g_utf8_get_char (p);
 246     }
 247   else
 248     {
 249       /* Not in our table.  */
 250       r = g_malloc (sizeof (gunichar));
 251       *r = ch;
 252       *result_len = 1;
 253     }
 254
 255   return r;
 256 }
 257
 258 /* L,V => LV and LV,T => LVT  */
 259 static gboolean
 260 combine_hangul (gunichar a,
 261                 gunichar b,
 262                 gunichar *result)
 263 {
 264   gint LIndex = a - LBase;
 265   gint SIndex = a - SBase;
 266
 267   gint VIndex = b - VBase;
 268   gint TIndex = b - TBase;
 269
 270   if (0 <= LIndex && LIndex < LCount
 271       && 0 <= VIndex && VIndex < VCount)
 272     {
 273       *result = SBase + (LIndex * VCount + VIndex) * TCount;
 274       return TRUE;
 275     }
 276   else if (0 <= SIndex && SIndex < SCount && (SIndex % TCount) == 0
 277            && 0 < TIndex && TIndex < TCount)
 278     {
 279       *result = a + TIndex;
 280       return TRUE;
 281     }
 282
 283   return FALSE;
 284 }
 285
 286 #define CI(Page, Char) \
 287   ((compose_table[Page] >= G_UNICODE_MAX_TABLE_INDEX) \
 288    ? (compose_table[Page] - G_UNICODE_MAX_TABLE_INDEX) \
 289    : (compose_data[compose_table[Page]][Char]))
 290
 291 #define COMPOSE_INDEX(Char) \
 292      (((Char >> 8) > (COMPOSE_TABLE_LAST)) ? 0 : CI((Char) >> 8, (Char) & 0xff))
 293
 294 static gboolean
 295 combine (gunichar  a,
 296          gunichar  b,
 297          gunichar *result)
 298 {
 299   gushort index_a, index_b;
 300
 301   if (combine_hangul (a, b, result))
 302     return TRUE;
 303
 304   index_a = COMPOSE_INDEX(a);
 305
 306   if (index_a >= COMPOSE_FIRST_SINGLE_START && index_a < COMPOSE_SECOND_START)
 307     {
 308       if (b == compose_first_single[index_a - COMPOSE_FIRST_SINGLE_START][0])
 309         {
 310           *result = compose_first_single[index_a - COMPOSE_FIRST_SINGLE_START][1];
 311           return TRUE;
 312         }
 313       else
 314         return FALSE;
 315     }
 316
 317   index_b = COMPOSE_INDEX(b);
 318
 319   if (index_b >= COMPOSE_SECOND_SINGLE_START)
 320     {
 321       if (a == compose_second_single[index_b - COMPOSE_SECOND_SINGLE_START][0])
 322         {
 323           *result = compose_second_single[index_b - COMPOSE_SECOND_SINGLE_START][1];
 324           return TRUE;
 325         }
 326       else
 327         return FALSE;
 328     }
 329
 330   if (index_a >= COMPOSE_FIRST_START && index_a < COMPOSE_FIRST_SINGLE_START &&
 331       index_b >= COMPOSE_SECOND_START && index_b < COMPOSE_SECOND_SINGLE_START)
 332     {
 333       gunichar res = compose_array[index_a - COMPOSE_FIRST_START][index_b - COMPOSE_SECOND_START];
 334
 335       if (res)
 336         {
 337           *result = res;
 338           return TRUE;
 339         }
 340     }
 341
 342   return FALSE;
 343 }
 344
 345 gunichar *
 346 _g_utf8_normalize_wc (const gchar    *str,
 347                       gssize          max_len,
 348                       GNormalizeMode  mode)
 349 {
 350   gsize n_wc;
 351   gunichar *wc_buffer;
 352   const char *p;
 353   gsize last_start;
 354   gboolean do_compat = (mode == G_NORMALIZE_NFKC ||
 355                         mode == G_NORMALIZE_NFKD);
 356   gboolean do_compose = (mode == G_NORMALIZE_NFC ||
 357                          mode == G_NORMALIZE_NFKC);
 358
 359   n_wc = 0;
 360   p = str;
 361   while ((max_len < 0 || p < str + max_len) && *p)
 362     {
 363       const gchar *decomp;
 364       gunichar wc = g_utf8_get_char (p);
 365
 366       if (wc >= 0xac00 && wc <= 0xd7a3)
 367         {
 368           gsize result_len;
 369           decompose_hangul (wc, NULL, &result_len);
 370           n_wc += result_len;
 371         }
 372       else
 373         {
 374           decomp = find_decomposition (wc, do_compat);
 375
 376           if (decomp)
 377             n_wc += g_utf8_strlen (decomp, -1);
 378           else
 379             n_wc++;
 380         }
 381
 382       p = g_utf8_next_char (p);
 383     }
 384
 385   wc_buffer = g_new (gunichar, n_wc + 1);
 386
 387   last_start = 0;
 388   n_wc = 0;
 389   p = str;
 390   while ((max_len < 0 || p < str + max_len) && *p)
 391     {
 392       gunichar wc = g_utf8_get_char (p);
 393       const gchar *decomp;
 394       int cc;
 395       gsize old_n_wc = n_wc;
 396
 397       if (wc >= 0xac00 && wc <= 0xd7a3)
 398         {
 399           gsize result_len;
 400           decompose_hangul (wc, wc_buffer + n_wc, &result_len);
 401           n_wc += result_len;
 402         }
 403       else
 404         {
 405           decomp = find_decomposition (wc, do_compat);
 406
 407           if (decomp)
 408             {
 409               const char *pd;
 410               for (pd = decomp; *pd != '\0'; pd = g_utf8_next_char (pd))
 411                 wc_buffer[n_wc++] = g_utf8_get_char (pd);
 412             }
 413           else
 414             wc_buffer[n_wc++] = wc;
 415         }
 416
 417       if (n_wc > 0)
 418         {
 419           cc = COMBINING_CLASS (wc_buffer[old_n_wc]);
 420
 421           if (cc == 0)
 422             {
 423               g_unicode_canonical_ordering (wc_buffer + last_start, n_wc - last_start);
 424               last_start = old_n_wc;
 425             }
 426         }
 427
 428       p = g_utf8_next_char (p);
 429     }
 430
 431   if (n_wc > 0)
 432     {
 433       g_unicode_canonical_ordering (wc_buffer + last_start, n_wc - last_start);
 434       last_start = n_wc;
 435     }
 436
 437   wc_buffer[n_wc] = 0;
 438
 439   /* All decomposed and reordered */
 440
 441   if (do_compose && n_wc > 0)
 442     {
 443       gsize i, j;
 444       int last_cc = 0;
 445       last_start = 0;
 446
 447       for (i = 0; i < n_wc; i++)
 448         {
 449           int cc = COMBINING_CLASS (wc_buffer[i]);
 450
 451           if (i > 0 &&
 452               (last_cc == 0 || last_cc < cc) &&
 453               combine (wc_buffer[last_start], wc_buffer[i],
 454                        &wc_buffer[last_start]))
 455             {
 456               for (j = i + 1; j < n_wc; j++)
 457                 wc_buffer[j-1] = wc_buffer[j];
 458               n_wc--;
 459               i--;
 460
 461               if (i == last_start)
 462                 last_cc = 0;
 463               else
 464                 last_cc = COMBINING_CLASS (wc_buffer[i-1]);
 465
 466               continue;
 467             }
 468
 469           if (cc == 0)
 470             last_start = i;
 471
 472           last_cc = cc;
 473         }
 474     }
 475
 476   wc_buffer[n_wc] = 0;
 477
 478   return wc_buffer;
 479 }
 480
 481 /**
 482  * g_utf8_normalize:
 483  * @str: a UTF-8 encoded string.
 484  * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
 485  * @mode: the type of normalization to perform.
 486  *
 487  * Converts a string into canonical form, standardizing
 488  * such issues as whether a character with an accent
 489  * is represented as a base character and combining
 490  * accent or as a single precomposed character. The
 491  * string has to be valid UTF-8, otherwise %NULL is
 492  * returned. You should generally call g_utf8_normalize()
 493  * before comparing two Unicode strings.
 494  *
 495  * The normalization mode %G_NORMALIZE_DEFAULT only
 496  * standardizes differences that do not affect the
 497  * text content, such as the above-mentioned accent
 498  * representation. %G_NORMALIZE_ALL also standardizes
 499  * the "compatibility" characters in Unicode, such
 500  * as SUPERSCRIPT THREE to the standard forms
 501  * (in this case DIGIT THREE). Formatting information
 502  * may be lost but for most text operations such
 503  * characters should be considered the same.
 504  *
 505  * %G_NORMALIZE_DEFAULT_COMPOSE and %G_NORMALIZE_ALL_COMPOSE
 506  * are like %G_NORMALIZE_DEFAULT and %G_NORMALIZE_ALL,
 507  * but returned a result with composed forms rather
 508  * than a maximally decomposed form. This is often
 509  * useful if you intend to convert the string to
 510  * a legacy encoding or pass it to a system with
 511  * less capable Unicode handling.
 512  *
 513  * Return value: a newly allocated string, that is the
 514  *   normalized form of @str, or %NULL if @str is not
 515  *   valid UTF-8.
 516  **/
 517 gchar *
 518 g_utf8_normalize (const gchar    *str,
 519                   gssize          len,
 520                   GNormalizeMode  mode)
 521 {
 522   gunichar *result_wc = _g_utf8_normalize_wc (str, len, mode);
 523   gchar *result;
 524
 525   result = g_ucs4_to_utf8 (result_wc, -1, NULL, NULL, NULL);
 526   g_free (result_wc);
 527
 528   return result;
 529 }
 530
 531 static gboolean
 532 decompose_hangul_step (gunichar  ch,
 533                        gunichar *a,
 534                        gunichar *b)
 535 {
 536   gint SIndex;
 537   gunichar L, V, T;
 538
 539   SIndex = ch - SBase;
 540
 541   if (SIndex < 0 || SIndex >= SCount)
 542     return FALSE;  /* not a hangul syllable */
 543
 544   L = LBase + SIndex / NCount;
 545   V = VBase + (SIndex % NCount) / TCount;
 546   T = TBase + SIndex % TCount;
 547
 548   if (T != TBase)
 549     {
 550       gint LIndex, VIndex;
 551       gunichar LV;
 552
 553       /* split LVT -> LV,T */
 554       LIndex = L - LBase;
 555       VIndex = V - VBase;
 556       LV = SBase + (LIndex * VCount + VIndex) * TCount;
 557
 558       *a = LV;
 559       *b = T;
 560     }
 561   else
 562     {
 563       /* split LV -> L,V */
 564       *a = L;
 565       *b = V;
 566     }
 567
 568   return TRUE;
 569 }
 570
 571 static gboolean
 572 compose_hangul_step (gunichar a,
 573                      gunichar b,
 574                      gunichar *ch)
 575 {
 576   gint LIndex, SIndex;
 577
 578   /* first try L,V -> LV */
 579   LIndex = a - LBase;
 580   if (0 <= LIndex && LIndex < LCount)
 581     {
 582       gint VIndex;
 583
 584       VIndex = b - VBase;
 585       if (0 <= VIndex && VIndex < VCount)
 586         {
 587           *ch = SBase + (LIndex * VCount + VIndex) * TCount;
 588           return TRUE;
 589         }
 590     }
 591
 592   /* next try LV,T -> LVT */
 593   SIndex = a - SBase;
 594   if (0 <= SIndex && SIndex < SCount && (SIndex % TCount) == 0)
 595     {
 596       gint TIndex;
 597
 598       TIndex = b - TBase;
 599       if (0 < TIndex && TIndex < TCount)
 600         {
 601           *ch = a + TIndex;
 602           return TRUE;
 603         }
 604     }
 605
 606   return FALSE;
 607 }
 608
 609 /**
 610  * g_unichar_decompose:
 611  * @ch: a Unicode character
 612  * @a: return location for the first component of @ch
 613  * @b: return location for the second component of @ch
 614  *
 615  * Performs a single decomposition step of the
 616  * Unicode canonical decomposition algorithm.
 617  *
 618  * This function does not include compatibility
 619  * decompositions. It does, however, include algorithmic
 620  * Hangul Jamo decomposition, as well as 'singleton'
 621  * decompositions which replace a character by a single
 622  * other character. In the case of singletons *@b will
 623  * be set to zero.
 624  *
 625  * If @ch is not decomposable, *@a is set to @ch and *@b
 626  * is set to zero.
 627  *
 628  * See <ulink url="http://unicode.org/reports/tr15/">UAX#15</ulink>
 629  * for details.
 630  *
 631  * Returns: %TRUE if the character could be decomposed
 632  *
 633  * Since: 2.30
 634  */
 635 gboolean
 636 g_unichar_decompose (gunichar  ch,
 637                      gunichar *a,
 638                      gunichar *b)
 639 {
 640   gint start = 0;
 641   gint end = G_N_ELEMENTS (decomp_step_table);
 642
 643   if (decompose_hangul_step (ch, a, b))
 644     return TRUE;
 645
 646   if (ch >= decomp_step_table[start].ch &&
 647       ch <= decomp_step_table[end - 1].ch)
 648     {
 649       while (TRUE)
 650         {
 651           gint half = (start + end) / 2;
 652           const decomposition_step *p = &(decomp_step_table[half]);
 653           if (ch == p->ch)
 654             {
 655               *a = p->a;
 656               *b = p->b;
 657               return TRUE;
 658             }
 659           else if (half == start)
 660             break;
 661           else if (ch > p->ch)
 662             start = half;
 663           else
 664             end = half;
 665         }
 666     }
 667
 668   *a = ch;
 669   *b = 0;
 670
 671   return FALSE;
 672 }
 673
 674 /**
 675  * g_unichar_compose:
 676  * @a: a Unicode character
 677  * @b: a Unicode character
 678  * @ch: return location for the composed character
 679  *
 680  * Performs a single composition step of the
 681  * Unicode canonical composition algorithm.
 682  *
 683  * This function does not perform algorithmic composition
 684  * for Hangul characters, and does not include compatibility
 685  * compositions. It does, however, include 'singleton'
 686  * compositions which replace a character by a single
 687  * other character. To obtain these, pass zero for @b.
 688  *
 689  * This function includes algorithmic Hangul Jamo composition.
 690  *
 691  * If @a and @b do not compose a new character, @ch is set to zero.
 692  *
 693  * See <ulink url="http://unicode.org/reports/tr15/">UAX#15</ulink>
 694  * for details.
 695  *
 696  * Returns: %TRUE if the characters could be composed
 697  *
 698  * Since: 2.30
 699  */
 700 gboolean
 701 g_unichar_compose (gunichar  a,
 702                    gunichar  b,
 703                    gunichar *ch)
 704 {
 705   gint start = 0;
 706   gint end = G_N_ELEMENTS (comp_step_table);
 707
 708   if (compose_hangul_step (a, b, ch))
 709     return TRUE;
 710
 711   if (a >= comp_step_table[start].a &&
 712       a <= comp_step_table[end - 1].a)
 713     {
 714       while (TRUE)
 715         {
 716           gint half = (start + end) / 2;
 717           const decomposition_step *p = &(comp_step_table[half]);
 718           if (a == p->a && b == p->b)
 719             {
 720               *ch = p->ch;
 721               return TRUE;
 722             }
 723           else if (half == start)
 724             break;
 725           else if (a > p->a || (a == p->a && b > p->b))
 726             start = half;
 727           else
 728             end = half;
 729         }
 730     }
 731
 732   *ch = 0;
 733
 734   return FALSE;
 735 }