source4/heimdal/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
  43 #include "normalize_table.h"
  44
  45 static int
  46 translation_cmp(const void *key, const void *data)
  47 {
  48     const struct translation *t1 = (const struct translation *)key;
  49     const struct translation *t2 = (const struct translation *)data;
  50
  51     return t1->key - t2->key;
  52 }
  53
  54 enum { s_base  = 0xAC00};
  55 enum { s_count = 11172};
  56 enum { l_base  = 0x1100};
  57 enum { l_count = 19};
  58 enum { v_base  = 0x1161};
  59 enum { v_count = 21};
  60 enum { t_base  = 0x11A7};
  61 enum { t_count = 28};
  62 enum { n_count = v_count * t_count};
  63
  64 static int
  65 hangul_decomp(const uint32_t *in, size_t in_len,
  66               uint32_t *out, size_t *out_len)
  67 {
  68     uint32_t u = *in;
  69     unsigned s_index;
  70     unsigned l, v, t;
  71     unsigned o;
  72
  73     if (u < s_base || u >= s_base + s_count)
  74         return 0;
  75     s_index = u - s_base;
  76     l = l_base + s_index / n_count;
  77     v = v_base + (s_index % n_count) / t_count;
  78     t = t_base + s_index % t_count;
  79     o = 2;
  80     if (t != t_base)
  81         ++o;
  82     if (*out_len < o)
  83         return WIND_ERR_OVERRUN;
  84     out[0] = l;
  85     out[1] = v;
  86     if (t != t_base)
  87         out[2] = t;
  88     *out_len = o;
  89     return 1;
  90 }
  91
  92 static uint32_t
  93 hangul_composition(const uint32_t *in, size_t in_len)
  94 {
  95     if (in_len < 2)
  96         return 0;
  97     if (in[0] >= l_base && in[0] < l_base + l_count) {
  98         unsigned l_index = in[0] - l_base;
  99         unsigned v_index;
 100
 101         if (in[1] < v_base || in[1] >= v_base + v_count)
 102             return 0;
 103         v_index = in[1] - v_base;
 104         return (l_index * v_count + v_index) * t_count + s_base;
 105     } else if (in[0] >= s_base && in[0] < s_base + s_count) {
 106         unsigned s_index = in[0] - s_base;
 107         unsigned t_index;
 108
 109         if (s_index % t_count != 0)
 110             return 0;
 111         if (in[1] < t_base || in[1] >= t_base + t_count)
 112             return 0;
 113         t_index = in[1] - t_base;
 114         return in[0] + t_index;
 115     }
 116     return 0;
 117 }
 118
 119 static int
 120 compat_decomp(const uint32_t *in, size_t in_len,
 121               uint32_t *out, size_t *out_len)
 122 {
 123     unsigned i;
 124     unsigned o = 0;
 125
 126     for (i = 0; i < in_len; ++i) {
 127         struct translation ts = {in[i]};
 128         size_t sub_len = *out_len - o;
 129         int ret;
 130
 131         ret = hangul_decomp(in + i, in_len - i,
 132                             out + o, &sub_len);
 133         if (ret) {
 134             if (ret == WIND_ERR_OVERRUN)
 135                 return ret;
 136             o += sub_len;
 137         } else {
 138             void *s = bsearch(&ts,
 139                               _wind_normalize_table,
 140                               _wind_normalize_table_size,
 141                               sizeof(_wind_normalize_table[0]),
 142                               translation_cmp);
 143             if (s != NULL) {
 144                 const struct translation *t = (const struct translation *)s;
 145
 146                 ret = compat_decomp(_wind_normalize_val_table + t->val_offset,
 147                                     t->val_len,
 148                                     out + o, &sub_len);
 149                 if (ret)
 150                     return ret;
 151                 o += sub_len;
 152             } else {
 153                 if (o >= *out_len)
 154                     return WIND_ERR_OVERRUN;
 155                 out[o++] = in[i];
 156
 157             }
 158         }
 159     }
 160     *out_len = o;
 161     return 0;
 162 }
 163
 164 static int
 165 cc_cmp(const void *a, const void *b)
 166 {
 167     const uint32_t *ua = (const uint32_t *)a;
 168     const uint32_t *ub = (const uint32_t *)b;
 169
 170     return _wind_combining_class(*ua) - _wind_combining_class(*ub);
 171 }
 172
 173 static void
 174 canonical_reorder(uint32_t *tmp, size_t tmp_len)
 175 {
 176     unsigned i;
 177
 178     for (i = 0; i < tmp_len; ++i) {
 179         int cc = _wind_combining_class(tmp[i]);
 180         if (cc) {
 181             size_t j;
 182             for (j = i + 1;
 183                  j < tmp_len && _wind_combining_class(tmp[j]);
 184                  ++j)
 185                 ;
 186             qsort(&tmp[i], j - i, sizeof(unsigned),
 187                   cc_cmp);
 188             i = j;
 189         }
 190     }
 191 }
 192
 193 static uint32_t
 194 find_composition(const uint32_t *in, unsigned in_len)
 195 {
 196     unsigned short canon_index = 0;
 197     uint32_t cur;
 198     unsigned n = 0;
 199
 200     cur = hangul_composition(in, in_len);
 201     if (cur)
 202         return cur;
 203
 204     do {
 205         const struct canon_node *c = &_wind_canon_table[canon_index];
 206         unsigned i;
 207
 208         if (n % 5 == 0) {
 209             cur = *in++;
 210             if (in_len-- == 0)
 211                 return c->val;
 212         }
 213
 214         i = cur >> 16;
 215         if (i < c->next_start || i >= c->next_end)
 216             canon_index = 0;
 217         else
 218             canon_index =
 219                 _wind_canon_next_table[c->next_offset + i - c->next_start];
 220         if (canon_index != 0) {
 221             cur = (cur << 4) & 0xFFFFF;
 222             ++n;
 223         }
 224     } while (canon_index != 0);
 225     return 0;
 226 }
 227
 228 static int
 229 combine(const uint32_t *in, size_t in_len,
 230         uint32_t *out, size_t *out_len)
 231 {
 232     unsigned i;
 233     int ostarter;
 234     unsigned o = 0;
 235     int old_cc;
 236
 237     for (i = 0; i < in_len;) {
 238         while (i < in_len && _wind_combining_class(in[i]) != 0) {
 239             out[o++] = in[i++];
 240         }
 241         if (i < in_len) {
 242             if (o >= *out_len)
 243                 return WIND_ERR_OVERRUN;
 244             ostarter = o;
 245             out[o++] = in[i++];
 246             old_cc   = -1;
 247
 248             while (i < in_len) {
 249                 uint32_t comb;
 250                 uint32_t v[2];
 251                 int cc;
 252
 253                 v[0] = out[ostarter];
 254                 v[1] = in[i];
 255
 256                 cc = _wind_combining_class(in[i]);
 257                 if (old_cc != cc && (comb = find_composition(v, 2))) {
 258                     out[ostarter] = comb;
 259                 } else if (cc == 0) {
 260                     break;
 261                 } else {
 262                     if (o >= *out_len)
 263                         return WIND_ERR_OVERRUN;
 264                     out[o++] = in[i];
 265                     old_cc   = cc;
 266                 }
 267                 ++i;
 268             }
 269         }
 270     }
 271     *out_len = o;
 272     return 0;
 273 }
 274
 275 int
 276 _wind_stringprep_normalize(const uint32_t *in, size_t in_len,
 277                            uint32_t *out, size_t *out_len)
 278 {
 279     size_t tmp_len;
 280     uint32_t *tmp;
 281     int ret;
 282
 283     tmp_len = in_len * 4;
 284     if (tmp_len < MAX_LENGTH_CANON)
 285         tmp_len = MAX_LENGTH_CANON;
 286     tmp = malloc(tmp_len * sizeof(uint32_t));
 287     if (tmp == NULL)
 288         return ENOMEM;
 289
 290     ret = compat_decomp(in, in_len, tmp, &tmp_len);
 291     if (ret) {
 292         free(tmp);
 293         return ret;
 294     }
 295     canonical_reorder(tmp, tmp_len);
 296     ret = combine(tmp, tmp_len, out, out_len);
 297     free(tmp);
 298     return ret;
 299 }