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