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
  31
  32 #define CC_PART1(Page, Char) \
  33   ((combining_class_table_part1[Page] >= G_UNICODE_MAX_TABLE_INDEX) \
  34    ? (combining_class_table_part1[Page] - G_UNICODE_MAX_TABLE_INDEX) \
  35    : (cclass_data[combining_class_table_part1[Page]][Char]))
  36
  37 #define CC_PART2(Page, Char) \
  38   ((combining_class_table_part2[Page] >= G_UNICODE_MAX_TABLE_INDEX) \
  39    ? (combining_class_table_part2[Page] - G_UNICODE_MAX_TABLE_INDEX) \
  40    : (cclass_data[combining_class_table_part2[Page]][Char]))
  41
  42 #define COMBINING_CLASS(Char) \
  43   (((Char) <= G_UNICODE_LAST_CHAR_PART1) \
  44    ? CC_PART1 ((Char) >> 8, (Char) & 0xff) \
  45    : (((Char) >= 0xe0000 && (Char) <= G_UNICODE_LAST_CHAR) \
  46       ? CC_PART2 (((Char) - 0xe0000) >> 8, (Char) & 0xff) \
  47       : 0))
  48
  49 gint
  50 _g_unichar_combining_class (gunichar uc)
  51 {
  52   return COMBINING_CLASS (uc);
  53 }
  54
  55 /**
  56  * g_unicode_canonical_ordering:
  57  * @string: a UCS-4 encoded string.
  58  * @len: the maximum length of @string to use.
  59  *
  60  * Computes the canonical ordering of a string in-place.
  61  * This rearranges decomposed characters in the string
  62  * according to their combining classes.  See the Unicode
  63  * manual for more information.
  64  **/
  65 void
  66 g_unicode_canonical_ordering (gunichar *string,
  67                               gsize     len)
  68 {
  69   gsize i;
  70   int swap = 1;
  71
  72   while (swap)
  73     {
  74       int last;
  75       swap = 0;
  76       last = COMBINING_CLASS (string[0]);
  77       for (i = 0; i < len - 1; ++i)
  78         {
  79           int next = COMBINING_CLASS (string[i + 1]);
  80           if (next != 0 && last > next)
  81             {
  82               gsize j;
  83               /* Percolate item leftward through string.  */
  84               for (j = i + 1; j > 0; --j)
  85                 {
  86                   gunichar t;
  87                   if (COMBINING_CLASS (string[j - 1]) <= next)
  88                     break;
  89                   t = string[j];
  90                   string[j] = string[j - 1];
  91                   string[j - 1] = t;
  92                   swap = 1;
  93                 }
  94               /* We're re-entering the loop looking at the old
  95                  character again.  */
  96               next = last;
  97             }
  98           last = next;
  99         }
 100     }
 101 }
 102
 103 /* returns a pointer to a null-terminated UTF-8 string */
 104 static const gchar *
 105 find_decomposition (gunichar ch,
 106                     gboolean compat)
 107 {
 108   int start = 0;
 109   int end = G_N_ELEMENTS (decomp_table);
 110
 111   if (ch >= decomp_table[start].ch &&
 112       ch <= decomp_table[end - 1].ch)
 113     {
 114       while (TRUE)
 115         {
 116           int half = (start + end) / 2;
 117           if (ch == decomp_table[half].ch)
 118             {
 119               int offset;
 120
 121               if (compat)
 122                 {
 123                   offset = decomp_table[half].compat_offset;
 124                   if (offset == G_UNICODE_NOT_PRESENT_OFFSET)
 125                     offset = decomp_table[half].canon_offset;
 126                 }
 127               else
 128                 {
 129                   offset = decomp_table[half].canon_offset;
 130                   if (offset == G_UNICODE_NOT_PRESENT_OFFSET)
 131                     return NULL;
 132                 }
 133
 134               return &(decomp_expansion_string[offset]);
 135             }
 136           else if (half == start)
 137             break;
 138           else if (ch > decomp_table[half].ch)
 139             start = half;
 140           else
 141             end = half;
 142         }
 143     }
 144
 145   return NULL;
 146 }
 147
 148 /**
 149  * g_unicode_canonical_decomposition:
 150  * @ch: a Unicode character.
 151  * @result_len: location to store the length of the return value.
 152  *
 153  * Computes the canonical decomposition of a Unicode character.
 154  *
 155  * Return value: a newly allocated string of Unicode characters.
 156  *   @result_len is set to the resulting length of the string.
 157  **/
 158 gunichar *
 159 g_unicode_canonical_decomposition (gunichar ch,
 160                                    gsize   *result_len)
 161 {
 162   const gchar *decomp = find_decomposition (ch, FALSE);
 163   const gchar *p;
 164   gunichar *r;
 165
 166   if (decomp)
 167     {
 168       /* Found it.  */
 169       int i;
 170
 171       *result_len = g_utf8_strlen (decomp, -1);
 172       r = g_malloc (*result_len * sizeof (gunichar));
 173
 174       for (p = decomp, i = 0; *p != '\0'; p = g_utf8_next_char (p), i++)
 175         r[i] = g_utf8_get_char (p);
 176     }
 177   else
 178     {
 179       /* Not in our table.  */
 180       r = g_malloc (sizeof (gunichar));
 181       *r = ch;
 182       *result_len = 1;
 183     }
 184
 185   /* Supposedly following the Unicode 2.1.9 table means that the
 186      decompositions come out in canonical order.  I haven't tested
 187      this, but we rely on it here.  */
 188   return r;
 189 }
 190
 191 #define CI(Page, Char) \
 192   ((compose_table[Page] >= G_UNICODE_MAX_TABLE_INDEX) \
 193    ? (compose_table[Page] - G_UNICODE_MAX_TABLE_INDEX) \
 194    : (compose_data[compose_table[Page]][Char]))
 195
 196 #define COMPOSE_INDEX(Char) \
 197      (((Char) > (G_UNICODE_LAST_CHAR)) ? 0 : CI((Char) >> 8, (Char) & 0xff))
 198
 199 static gboolean
 200 combine (gunichar  a,
 201          gunichar  b,
 202          gunichar *result)
 203 {
 204   gushort index_a, index_b;
 205
 206   index_a = COMPOSE_INDEX(a);
 207
 208   if (index_a >= COMPOSE_FIRST_SINGLE_START && index_a < COMPOSE_SECOND_START)
 209     {
 210       if (b == compose_first_single[index_a - COMPOSE_FIRST_SINGLE_START][0])
 211         {
 212           *result = compose_first_single[index_a - COMPOSE_FIRST_SINGLE_START][1];
 213           return TRUE;
 214         }
 215       else
 216         return FALSE;
 217     }
 218
 219   index_b = COMPOSE_INDEX(b);
 220
 221   if (index_b >= COMPOSE_SECOND_SINGLE_START)
 222     {
 223       if (a == compose_second_single[index_b - COMPOSE_SECOND_SINGLE_START][0])
 224         {
 225           *result = compose_second_single[index_b - COMPOSE_SECOND_SINGLE_START][1];
 226           return TRUE;
 227         }
 228       else
 229         return FALSE;
 230     }
 231
 232   if (index_a >= COMPOSE_FIRST_START && index_a < COMPOSE_FIRST_SINGLE_START &&
 233       index_b >= COMPOSE_SECOND_START && index_b < COMPOSE_SECOND_SINGLE_START)
 234     {
 235       gunichar res = compose_array[index_a - COMPOSE_FIRST_START][index_b - COMPOSE_SECOND_START];
 236
 237       if (res)
 238         {
 239           *result = res;
 240           return TRUE;
 241         }
 242     }
 243
 244   return FALSE;
 245 }
 246
 247 gunichar *
 248 _g_utf8_normalize_wc (const gchar    *str,
 249                       gssize          max_len,
 250                       GNormalizeMode  mode)
 251 {
 252   gsize n_wc;
 253   gunichar *wc_buffer;
 254   const char *p;
 255   gsize last_start;
 256   gboolean do_compat = (mode == G_NORMALIZE_NFKC ||
 257                         mode == G_NORMALIZE_NFKD);
 258   gboolean do_compose = (mode == G_NORMALIZE_NFC ||
 259                          mode == G_NORMALIZE_NFKC);
 260
 261   n_wc = 0;
 262   p = str;
 263   while ((max_len < 0 || p < str + max_len) && *p)
 264     {
 265       gunichar wc = g_utf8_get_char (p);
 266
 267       const gchar *decomp = find_decomposition (wc, do_compat);
 268
 269       if (decomp)
 270         n_wc += g_utf8_strlen (decomp, -1);
 271       else
 272         n_wc++;
 273
 274       p = g_utf8_next_char (p);
 275     }
 276
 277   wc_buffer = g_new (gunichar, n_wc + 1);
 278
 279   last_start = 0;
 280   n_wc = 0;
 281   p = str;
 282   while ((max_len < 0 || p < str + max_len) && *p)
 283     {
 284       gunichar wc = g_utf8_get_char (p);
 285       const gchar *decomp;
 286       int cc;
 287       gsize old_n_wc = n_wc;
 288
 289       decomp = find_decomposition (wc, do_compat);
 290
 291       if (decomp)
 292         {
 293           const char *pd;
 294           for (pd = decomp; *pd != '\0'; pd = g_utf8_next_char (pd))
 295             wc_buffer[n_wc++] = g_utf8_get_char (pd);
 296         }
 297       else
 298         wc_buffer[n_wc++] = wc;
 299
 300       if (n_wc > 0)
 301         {
 302           cc = COMBINING_CLASS (wc_buffer[old_n_wc]);
 303
 304           if (cc == 0)
 305             {
 306               g_unicode_canonical_ordering (wc_buffer + last_start, n_wc - last_start);
 307               last_start = old_n_wc;
 308             }
 309         }
 310
 311       p = g_utf8_next_char (p);
 312     }
 313
 314   if (n_wc > 0)
 315     {
 316       g_unicode_canonical_ordering (wc_buffer + last_start, n_wc - last_start);
 317       last_start = n_wc;
 318     }
 319
 320   wc_buffer[n_wc] = 0;
 321
 322   /* All decomposed and reordered */
 323
 324   if (do_compose && n_wc > 0)
 325     {
 326       gsize i, j;
 327       int last_cc = 0;
 328       last_start = 0;
 329
 330       for (i = 0; i < n_wc; i++)
 331         {
 332           int cc = COMBINING_CLASS (wc_buffer[i]);
 333
 334           if (i > 0 &&
 335               (last_cc == 0 || last_cc != cc) &&
 336               combine (wc_buffer[last_start], wc_buffer[i],
 337                        &wc_buffer[last_start]))
 338             {
 339               for (j = i + 1; j < n_wc; j++)
 340                 wc_buffer[j-1] = wc_buffer[j];
 341               n_wc--;
 342               i--;
 343
 344               if (i == last_start)
 345                 last_cc = 0;
 346               else
 347                 last_cc = COMBINING_CLASS (wc_buffer[i-1]);
 348
 349               continue;
 350             }
 351
 352           if (cc == 0)
 353             last_start = i;
 354
 355           last_cc = cc;
 356         }
 357     }
 358
 359   wc_buffer[n_wc] = 0;
 360
 361   return wc_buffer;
 362 }
 363
 364 /**
 365  * g_utf8_normalize:
 366  * @str: a UTF-8 encoded string.
 367  * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
 368  * @mode: the type of normalization to perform.
 369  *
 370  * Converts a string into canonical form, standardizing
 371  * such issues as whether a character with an accent
 372  * is represented as a base character and combining
 373  * accent or as a single precomposed character. You
 374  * should generally call g_utf8_normalize() before
 375  * comparing two Unicode strings.
 376  *
 377  * The normalization mode %G_NORMALIZE_DEFAULT only
 378  * standardizes differences that do not affect the
 379  * text content, such as the above-mentioned accent
 380  * representation. %G_NORMALIZE_ALL also standardizes
 381  * the "compatibility" characters in Unicode, such
 382  * as SUPERSCRIPT THREE to the standard forms
 383  * (in this case DIGIT THREE). Formatting information
 384  * may be lost but for most text operations such
 385  * characters should be considered the same.
 386  * For example, g_utf8_collate() normalizes
 387  * with %G_NORMALIZE_ALL as its first step.
 388  *
 389  * %G_NORMALIZE_DEFAULT_COMPOSE and %G_NORMALIZE_ALL_COMPOSE
 390  * are like %G_NORMALIZE_DEFAULT and %G_NORMALIZE_ALL,
 391  * but returned a result with composed forms rather
 392  * than a maximally decomposed form. This is often
 393  * useful if you intend to convert the string to
 394  * a legacy encoding or pass it to a system with
 395  * less capable Unicode handling.
 396  *
 397  * Return value: a newly allocated string, that is the
 398  *   normalized form of @str.
 399  **/
 400 gchar *
 401 g_utf8_normalize (const gchar    *str,
 402                   gssize          len,
 403                   GNormalizeMode  mode)
 404 {
 405   gunichar *result_wc = _g_utf8_normalize_wc (str, len, mode);
 406   gchar *result;
 407
 408   result = g_ucs4_to_utf8 (result_wc, -1, NULL, NULL, NULL);
 409   g_free (result_wc);
 410
 411   return result;
 412 }