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