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