lib/wind/normalize.c

   1 /*
   2  * Copyright (c) 2004 Kungliga Tekniska Högskolan
   3  * (Royal Institute of Technology, Stockholm, Sweden).
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * 3. Neither the name of the Institute nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 #ifdef HAVE_CONFIG_H
  35 #include <config.h>
  36 #endif
  37 #include "windlocl.h"
  38
  39 #include <assert.h>
  40 #include <stdlib.h>
  41 #include <errno.h>
  42 #include <stdio.h>
  43
  44 #include "roken.h"
  45
  46 #include "normalize_table.h"
  47
  48 static int
  49 translation_cmp(const void *key, const void *data)
  50 {
  51     const struct translation *t1 = (const struct translation *)key;
  52     const struct translation *t2 = (const struct translation *)data;
  53
  54     return t1->key - t2->key;
  55 }
  56
  57 enum { s_base  = 0xAC00};
  58 enum { s_count = 11172};
  59 enum { l_base  = 0x1100};
  60 enum { l_count = 19};
  61 enum { v_base  = 0x1161};
  62 enum { v_count = 21};
  63 enum { t_base  = 0x11A7};
  64 enum { t_count = 28};
  65 enum { n_count = v_count * t_count};
  66
  67 static int
  68 hangul_decomp(const uint32_t *in, size_t in_len,
  69               uint32_t *out, size_t *out_len)
  70 {
  71     uint32_t u = *in;
  72     unsigned s_index;
  73     unsigned l, v, t;
  74     unsigned o;
  75
  76     if (u < s_base || u >= s_base + s_count)
  77         return 0;
  78     s_index = u - s_base;
  79     l = l_base + s_index / n_count;
  80     v = v_base + (s_index % n_count) / t_count;
  81     t = t_base + s_index % t_count;
  82     o = 2;
  83     if (t != t_base)
  84         ++o;
  85     if (*out_len < o)
  86         return WIND_ERR_OVERRUN;
  87     out[0] = l;
  88     out[1] = v;
  89     if (t != t_base)
  90         out[2] = t;
  91     *out_len = o;
  92     return 1;
  93 }
  94
  95 static uint32_t
  96 hangul_composition(const uint32_t *in, size_t in_len)
  97 {
  98     if (in_len < 2)
  99         return 0;
 100     if (in[0] >= l_base && in[0] < l_base + l_count) {
 101         unsigned l_index = in[0] - l_base;
 102         unsigned v_index;
 103
 104         if (in[1] < v_base || in[1] >= v_base + v_count)
 105             return 0;
 106         v_index = in[1] - v_base;
 107         return (l_index * v_count + v_index) * t_count + s_base;
 108     } else if (in[0] >= s_base && in[0] < s_base + s_count) {
 109         unsigned s_index = in[0] - s_base;
 110         unsigned t_index;
 111
 112         if (s_index % t_count != 0)
 113             return 0;
 114         if (in[1] < t_base || in[1] >= t_base + t_count)
 115             return 0;
 116         t_index = in[1] - t_base;
 117         return in[0] + t_index;
 118     }
 119     return 0;
 120 }
 121
 122 static int
 123 compat_decomp(const uint32_t *in, size_t in_len,
 124               uint32_t *out, size_t *out_len)
 125 {
 126     unsigned i;
 127     unsigned o = 0;
 128
 129     for (i = 0; i < in_len; ++i) {
 130         struct translation ts = {in[i]};
 131         size_t sub_len = *out_len - o;
 132         int ret;
 133
 134         ret = hangul_decomp(in + i, in_len - i,
 135                             out + o, &sub_len);
 136         if (ret) {
 137             if (ret == WIND_ERR_OVERRUN)
 138                 return ret;
 139             o += sub_len;
 140         } else {
 141             void *s = bsearch(&ts,
 142                               _wind_normalize_table,
 143                               _wind_normalize_table_size,
 144                               sizeof(_wind_normalize_table[0]),
 145                               translation_cmp);
 146             if (s != NULL) {
 147                 const struct translation *t = (const struct translation *)s;
 148
 149                 ret = compat_decomp(_wind_normalize_val_table + t->val_offset,
 150                                     t->val_len,
 151                                     out + o, &sub_len);
 152                 if (ret)
 153                     return ret;
 154                 o += sub_len;
 155             } else {
 156                 if (o >= *out_len)
 157                     return WIND_ERR_OVERRUN;
 158                 out[o++] = in[i];
 159
 160             }
 161         }
 162     }
 163     *out_len = o;
 164     return 0;
 165 }
 166
 167 static int
 168 cc_cmp(const void *a, const void *b)
 169 {
 170     const uint32_t *ua = (const uint32_t *)a;
 171     const uint32_t *ub = (const uint32_t *)b;
 172
 173     return _wind_combining_class(*ua) - _wind_combining_class(*ub);
 174 }
 175
 176 static void
 177 canonical_reorder(uint32_t *tmp, size_t tmp_len)
 178 {
 179     size_t i;
 180
 181     for (i = 0; i < tmp_len; ++i) {
 182         int cc = _wind_combining_class(tmp[i]);
 183         if (cc) {
 184             size_t j;
 185             for (j = i + 1;
 186                  j < tmp_len && _wind_combining_class(tmp[j]);
 187                  ++j)
 188                 ;
 189             qsort(&tmp[i], j - i, sizeof(tmp[0]), cc_cmp);
 190             i = j;
 191         }
 192     }
 193 }
 194
 195 static uint32_t
 196 find_composition(const uint32_t *in, unsigned in_len)
 197 {
 198     unsigned short canon_index = 0;
 199     uint32_t cur;
 200     unsigned n = 0;
 201
 202     cur = hangul_composition(in, in_len);
 203     if (cur)
 204         return cur;
 205
 206     do {
 207         const struct canon_node *c = &_wind_canon_table[canon_index];
 208         unsigned i;
 209
 210         if (n % 5 == 0) {
 211             cur = *in++;
 212             if (in_len-- == 0)
 213                 return c->val;
 214         }
 215
 216         i = cur >> 16;
 217         if (i < c->next_start || i >= c->next_end)
 218             canon_index = 0;
 219         else
 220             canon_index =
 221                 _wind_canon_next_table[c->next_offset + i - c->next_start];
 222         if (canon_index != 0) {
 223             cur = (cur << 4) & 0xFFFFF;
 224             ++n;
 225         }
 226     } while (canon_index != 0);
 227     return 0;
 228 }
 229
 230 static int
 231 combine(const uint32_t *in, size_t in_len,
 232         uint32_t *out, size_t *out_len)
 233 {
 234     unsigned i;
 235     int ostarter;
 236     unsigned o = 0;
 237     int old_cc;
 238
 239     for (i = 0; i < in_len;) {
 240         while (i < in_len && _wind_combining_class(in[i]) != 0) {
 241             out[o++] = in[i++];
 242         }
 243         if (i < in_len) {
 244             if (o >= *out_len)
 245                 return WIND_ERR_OVERRUN;
 246             ostarter = o;
 247             out[o++] = in[i++];
 248             old_cc   = -1;
 249
 250             while (i < in_len) {
 251                 uint32_t comb;
 252                 uint32_t v[2];
 253                 int cc;
 254
 255                 v[0] = out[ostarter];
 256                 v[1] = in[i];
 257
 258                 cc = _wind_combining_class(in[i]);
 259                 if (old_cc != cc && (comb = find_composition(v, 2))) {
 260                     out[ostarter] = comb;
 261                 } else if (cc == 0) {
 262                     break;
 263                 } else {
 264                     if (o >= *out_len)
 265                         return WIND_ERR_OVERRUN;
 266                     out[o++] = in[i];
 267                     old_cc   = cc;
 268                 }
 269                 ++i;
 270             }
 271         }
 272     }
 273     *out_len = o;
 274     return 0;
 275 }
 276
 277 int
 278 _wind_stringprep_normalize(const uint32_t *in, size_t in_len,
 279                            uint32_t *out, size_t *out_len)
 280 {
 281     size_t tmp_len;
 282     uint32_t *tmp;
 283     int ret;
 284
 285     if (in_len == 0) {
 286         *out_len = 0;
 287         return 0;
 288     }
 289
 290     tmp_len = in_len * 4;
 291     if (tmp_len < MAX_LENGTH_CANON)
 292         tmp_len = MAX_LENGTH_CANON;
 293     tmp = malloc(tmp_len * sizeof(uint32_t));
 294     if (tmp == NULL)
 295         return ENOMEM;
 296
 297     ret = compat_decomp(in, in_len, tmp, &tmp_len);
 298     if (ret) {
 299         free(tmp);
 300         return ret;
 301     }
 302     canonical_reorder(tmp, tmp_len);
 303     ret = combine(tmp, tmp_len, out, out_len);
 304     free(tmp);
 305     return ret;
 306 }