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
  25 #include <config.h>
  26
  27 #include <stdlib.h>
  28
  29 /* We cheat a bit and cast type values to (char *).  We detect these
  30    using the &0xff trick.  */
  31 #define CC(Page, Char) \
  32   (((((int) (combining_class_table[Page])) & 0xff) \
  33     == ((int) combining_class_table[Page])) \
  34    ? ((int) combining_class_table[Page]) \
  35    : (combining_class_table[Page][Char]))
  36
  37 #define COMBINING_CLASS(Char) \
  38      (((Char) > (UNICODE_LAST_CHAR)) ? 0 : CC((Char) >> 8, (Char) & 0xff))
  39
  40 /* Compute the canonical ordering of a string in-place.  */
  41 void
  42 g_unicode_canonical_ordering (gunichar *string,
  43                               size_t len)
  44 {
  45   size_t i;
  46   int swap = 1;
  47
  48   while (swap)
  49     {
  50       int last;
  51       swap = 0;
  52       last = COMBINING_CLASS (string[0]);
  53       for (i = 0; i < len - 1; ++i)
  54         {
  55           int next = COMBINING_CLASS (string[i + 1]);
  56           if (next != 0 && last > next)
  57             {
  58               size_t j;
  59               /* Percolate item leftward through string.  */
  60               for (j = i; j > 0; --j)
  61                 {
  62                   gunichar t;
  63                   if (COMBINING_CLASS (string[j]) <= next)
  64                     break;
  65                   t = string[j + 1];
  66                   string[j + 1] = string[j];
  67                   string[j] = t;
  68                   swap = 1;
  69                 }
  70               /* We're re-entering the loop looking at the old
  71                  character again.  */
  72               next = last;
  73             }
  74           last = next;
  75         }
  76     }
  77 }
  78
  79 gunichar *
  80 g_unicode_canonical_decomposition (gunichar ch,
  81                                    size_t *result_len)
  82 {
  83   gunichar *r = NULL;
  84
  85   if (ch <= 0xffff)
  86     {
  87       int start = 0;
  88       int end = G_N_ELEMENTS (decomp_table);
  89       while (start != end)
  90         {
  91           int half = (start + end) / 2;
  92           if (ch == decomp_table[half].ch)
  93             {
  94               /* Found it.  */
  95               int i, len;
  96               /* We store as a double-nul terminated string.  */
  97               for (len = 0; (decomp_table[half].expansion[len]
  98                              || decomp_table[half].expansion[len + 1]);
  99                    len += 2)
 100                 ;
 101
 102               /* We've counted twice as many bytes as there are
 103                  characters.  */
 104               *result_len = len / 2;
 105               r = malloc (len / 2 * sizeof (gunichar));
 106
 107               for (i = 0; i < len; i += 2)
 108                 {
 109                   r[i / 2] = (decomp_table[half].expansion[i] << 8
 110                               | decomp_table[half].expansion[i + 1]);
 111                 }
 112               break;
 113             }
 114           else if (ch > decomp_table[half].ch)
 115             start = half;
 116           else
 117             end = half;
 118         }
 119     }
 120
 121   if (r == NULL)
 122     {
 123       /* Not in our table.  */
 124       r = malloc (sizeof (gunichar));
 125       *r = ch;
 126       *result_len = 1;
 127     }
 128
 129   /* Supposedly following the Unicode 2.1.9 table means that the
 130      decompositions come out in canonical order.  I haven't tested
 131      this, but we rely on it here.  */
 132   return r;
 133 }