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