utf8.c

   1 /* $OpenBSD$ */
   2
   3 /*
   4  * Copyright (c) 2008 Nicholas Marriott <nicm@users.sourceforge.net>
   5  *
   6  * Permission to use, copy, modify, and distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF MIND, USE, DATA OR PROFITS, WHETHER
  15  * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
  16  * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18
  19 #include <sys/types.h>
  20
  21 #include <string.h>
  22
  23 #include "tmux.h"
  24
  25 struct utf8_width_entry {
  26         u_int   first;
  27         u_int   last;
  28
  29         int     width;
  30
  31         struct utf8_width_entry *left;
  32         struct utf8_width_entry *right;
  33 };
  34
  35 /* Random order. Not optimal but it'll do for now... */
  36 struct utf8_width_entry utf8_width_table[] = {
  37         { 0x00951, 0x00954, 0, NULL, NULL },
  38         { 0x00ccc, 0x00ccd, 0, NULL, NULL },
  39         { 0x0fff9, 0x0fffb, 0, NULL, NULL },
  40         { 0x20000, 0x2fffd, 2, NULL, NULL },
  41         { 0x00ebb, 0x00ebc, 0, NULL, NULL },
  42         { 0x01932, 0x01932, 0, NULL, NULL },
  43         { 0x0070f, 0x0070f, 0, NULL, NULL },
  44         { 0x00a70, 0x00a71, 0, NULL, NULL },
  45         { 0x02329, 0x02329, 2, NULL, NULL },
  46         { 0x00acd, 0x00acd, 0, NULL, NULL },
  47         { 0x00ac7, 0x00ac8, 0, NULL, NULL },
  48         { 0x00a3c, 0x00a3c, 0, NULL, NULL },
  49         { 0x009cd, 0x009cd, 0, NULL, NULL },
  50         { 0x00591, 0x005bd, 0, NULL, NULL },
  51         { 0x01058, 0x01059, 0, NULL, NULL },
  52         { 0x0ffe0, 0x0ffe6, 2, NULL, NULL },
  53         { 0x01100, 0x0115f, 2, NULL, NULL },
  54         { 0x0fe20, 0x0fe23, 0, NULL, NULL },
  55         { 0x0302a, 0x0302f, 0, NULL, NULL },
  56         { 0x01772, 0x01773, 0, NULL, NULL },
  57         { 0x005bf, 0x005bf, 0, NULL, NULL },
  58         { 0x006ea, 0x006ed, 0, NULL, NULL },
  59         { 0x00bc0, 0x00bc0, 0, NULL, NULL },
  60         { 0x00962, 0x00963, 0, NULL, NULL },
  61         { 0x01732, 0x01734, 0, NULL, NULL },
  62         { 0x00d41, 0x00d43, 0, NULL, NULL },
  63         { 0x01b42, 0x01b42, 0, NULL, NULL },
  64         { 0x00a41, 0x00a42, 0, NULL, NULL },
  65         { 0x00eb4, 0x00eb9, 0, NULL, NULL },
  66         { 0x00b01, 0x00b01, 0, NULL, NULL },
  67         { 0x00e34, 0x00e3a, 0, NULL, NULL },
  68         { 0x03040, 0x03098, 2, NULL, NULL },
  69         { 0x0093c, 0x0093c, 0, NULL, NULL },
  70         { 0x00c4a, 0x00c4d, 0, NULL, NULL },
  71         { 0x01032, 0x01032, 0, NULL, NULL },
  72         { 0x00f37, 0x00f37, 0, NULL, NULL },
  73         { 0x00901, 0x00902, 0, NULL, NULL },
  74         { 0x00cbf, 0x00cbf, 0, NULL, NULL },
  75         { 0x0a806, 0x0a806, 0, NULL, NULL },
  76         { 0x00dd2, 0x00dd4, 0, NULL, NULL },
  77         { 0x00f71, 0x00f7e, 0, NULL, NULL },
  78         { 0x01752, 0x01753, 0, NULL, NULL },
  79         { 0x1d242, 0x1d244, 0, NULL, NULL },
  80         { 0x005c1, 0x005c2, 0, NULL, NULL },
  81         { 0x0309b, 0x0a4cf, 2, NULL, NULL },
  82         { 0xe0100, 0xe01ef, 0, NULL, NULL },
  83         { 0x017dd, 0x017dd, 0, NULL, NULL },
  84         { 0x00600, 0x00603, 0, NULL, NULL },
  85         { 0x009e2, 0x009e3, 0, NULL, NULL },
  86         { 0x00cc6, 0x00cc6, 0, NULL, NULL },
  87         { 0x0a80b, 0x0a80b, 0, NULL, NULL },
  88         { 0x01712, 0x01714, 0, NULL, NULL },
  89         { 0x00b3c, 0x00b3c, 0, NULL, NULL },
  90         { 0x01b00, 0x01b03, 0, NULL, NULL },
  91         { 0x007eb, 0x007f3, 0, NULL, NULL },
  92         { 0xe0001, 0xe0001, 0, NULL, NULL },
  93         { 0x1d185, 0x1d18b, 0, NULL, NULL },
  94         { 0x0feff, 0x0feff, 0, NULL, NULL },
  95         { 0x01b36, 0x01b3a, 0, NULL, NULL },
  96         { 0x01920, 0x01922, 0, NULL, NULL },
  97         { 0x00670, 0x00670, 0, NULL, NULL },
  98         { 0x00f90, 0x00f97, 0, NULL, NULL },
  99         { 0x01927, 0x01928, 0, NULL, NULL },
 100         { 0x0200b, 0x0200f, 0, NULL, NULL },
 101         { 0x0ff00, 0x0ff60, 2, NULL, NULL },
 102         { 0x0f900, 0x0faff, 2, NULL, NULL },
 103         { 0x0fb1e, 0x0fb1e, 0, NULL, NULL },
 104         { 0x00cbc, 0x00cbc, 0, NULL, NULL },
 105         { 0x00eb1, 0x00eb1, 0, NULL, NULL },
 106         { 0x10a38, 0x10a3a, 0, NULL, NULL },
 107         { 0x007a6, 0x007b0, 0, NULL, NULL },
 108         { 0x00f80, 0x00f84, 0, NULL, NULL },
 109         { 0x005c4, 0x005c5, 0, NULL, NULL },
 110         { 0x0ac00, 0x0d7a3, 2, NULL, NULL },
 111         { 0x017c9, 0x017d3, 0, NULL, NULL },
 112         { 0x00d4d, 0x00d4d, 0, NULL, NULL },
 113         { 0x1d167, 0x1d169, 0, NULL, NULL },
 114         { 0x01036, 0x01037, 0, NULL, NULL },
 115         { 0xe0020, 0xe007f, 0, NULL, NULL },
 116         { 0x00f35, 0x00f35, 0, NULL, NULL },
 117         { 0x017b4, 0x017b5, 0, NULL, NULL },
 118         { 0x0206a, 0x0206f, 0, NULL, NULL },
 119         { 0x00c46, 0x00c48, 0, NULL, NULL },
 120         { 0x01939, 0x0193b, 0, NULL, NULL },
 121         { 0x01dc0, 0x01dca, 0, NULL, NULL },
 122         { 0x10a0c, 0x10a0f, 0, NULL, NULL },
 123         { 0x0102d, 0x01030, 0, NULL, NULL },
 124         { 0x017c6, 0x017c6, 0, NULL, NULL },
 125         { 0x00ec8, 0x00ecd, 0, NULL, NULL },
 126         { 0x00b41, 0x00b43, 0, NULL, NULL },
 127         { 0x017b7, 0x017bd, 0, NULL, NULL },
 128         { 0x1d173, 0x1d182, 0, NULL, NULL },
 129         { 0x00a47, 0x00a48, 0, NULL, NULL },
 130         { 0x0232a, 0x0232a, 2, NULL, NULL },
 131         { 0x01b3c, 0x01b3c, 0, NULL, NULL },
 132         { 0x10a01, 0x10a03, 0, NULL, NULL },
 133         { 0x00ae2, 0x00ae3, 0, NULL, NULL },
 134         { 0x00483, 0x00486, 0, NULL, NULL },
 135         { 0x0135f, 0x0135f, 0, NULL, NULL },
 136         { 0x01a17, 0x01a18, 0, NULL, NULL },
 137         { 0x006e7, 0x006e8, 0, NULL, NULL },
 138         { 0x03099, 0x0309a, 0, NULL, NULL },
 139         { 0x00b4d, 0x00b4d, 0, NULL, NULL },
 140         { 0x00ce2, 0x00ce3, 0, NULL, NULL },
 141         { 0x00bcd, 0x00bcd, 0, NULL, NULL },
 142         { 0x00610, 0x00615, 0, NULL, NULL },
 143         { 0x00f99, 0x00fbc, 0, NULL, NULL },
 144         { 0x009c1, 0x009c4, 0, NULL, NULL },
 145         { 0x00730, 0x0074a, 0, NULL, NULL },
 146         { 0x00300, 0x0036f, 0, NULL, NULL },
 147         { 0x03030, 0x0303e, 2, NULL, NULL },
 148         { 0x01b34, 0x01b34, 0, NULL, NULL },
 149         { 0x1d1aa, 0x1d1ad, 0, NULL, NULL },
 150         { 0x00dca, 0x00dca, 0, NULL, NULL },
 151         { 0x006d6, 0x006e4, 0, NULL, NULL },
 152         { 0x00f86, 0x00f87, 0, NULL, NULL },
 153         { 0x00b3f, 0x00b3f, 0, NULL, NULL },
 154         { 0x0fe30, 0x0fe6f, 2, NULL, NULL },
 155         { 0x01039, 0x01039, 0, NULL, NULL },
 156         { 0x0094d, 0x0094d, 0, NULL, NULL },
 157         { 0x00c55, 0x00c56, 0, NULL, NULL },
 158         { 0x00488, 0x00489, 0, NULL, NULL },
 159         { 0x00e47, 0x00e4e, 0, NULL, NULL },
 160         { 0x00a81, 0x00a82, 0, NULL, NULL },
 161         { 0x00ac1, 0x00ac5, 0, NULL, NULL },
 162         { 0x0202a, 0x0202e, 0, NULL, NULL },
 163         { 0x00dd6, 0x00dd6, 0, NULL, NULL },
 164         { 0x018a9, 0x018a9, 0, NULL, NULL },
 165         { 0x0064b, 0x0065e, 0, NULL, NULL },
 166         { 0x00abc, 0x00abc, 0, NULL, NULL },
 167         { 0x00b82, 0x00b82, 0, NULL, NULL },
 168         { 0x00f39, 0x00f39, 0, NULL, NULL },
 169         { 0x020d0, 0x020ef, 0, NULL, NULL },
 170         { 0x01dfe, 0x01dff, 0, NULL, NULL },
 171         { 0x30000, 0x3fffd, 2, NULL, NULL },
 172         { 0x00711, 0x00711, 0, NULL, NULL },
 173         { 0x0fe00, 0x0fe0f, 0, NULL, NULL },
 174         { 0x01160, 0x011ff, 0, NULL, NULL },
 175         { 0x0180b, 0x0180d, 0, NULL, NULL },
 176         { 0x10a3f, 0x10a3f, 0, NULL, NULL },
 177         { 0x00981, 0x00981, 0, NULL, NULL },
 178         { 0x0a825, 0x0a826, 0, NULL, NULL },
 179         { 0x00941, 0x00948, 0, NULL, NULL },
 180         { 0x01b6b, 0x01b73, 0, NULL, NULL },
 181         { 0x00e31, 0x00e31, 0, NULL, NULL },
 182         { 0x0fe10, 0x0fe19, 2, NULL, NULL },
 183         { 0x00a01, 0x00a02, 0, NULL, NULL },
 184         { 0x00a4b, 0x00a4d, 0, NULL, NULL },
 185         { 0x00f18, 0x00f19, 0, NULL, NULL },
 186         { 0x00fc6, 0x00fc6, 0, NULL, NULL },
 187         { 0x02e80, 0x03029, 2, NULL, NULL },
 188         { 0x00b56, 0x00b56, 0, NULL, NULL },
 189         { 0x009bc, 0x009bc, 0, NULL, NULL },
 190         { 0x005c7, 0x005c7, 0, NULL, NULL },
 191         { 0x02060, 0x02063, 0, NULL, NULL },
 192         { 0x00c3e, 0x00c40, 0, NULL, NULL },
 193         { 0x10a05, 0x10a06, 0, NULL, NULL },
 194 };
 195
 196 struct utf8_width_entry *utf8_width_root = NULL;
 197
 198 int     utf8_overlap(struct utf8_width_entry *, struct utf8_width_entry *);
 199 u_int   utf8_combine(const struct utf8_data *);
 200 u_int   utf8_width(const struct utf8_data *);
 201
 202 /*
 203  * Open UTF-8 sequence.
 204  *
 205  * 11000010-11011111 C2-DF start of 2-byte sequence
 206  * 11100000-11101111 E0-EF start of 3-byte sequence
 207  * 11110000-11110100 F0-F4 start of 4-byte sequence
 208  *
 209  * Returns 1 if more UTF-8 to come, 0 if not UTF-8.
 210  */
 211 int
 212 utf8_open(struct utf8_data *utf8data, u_char ch)
 213 {
 214         memset(utf8data, 0, sizeof *utf8data);
 215         if (ch >= 0xc2 && ch <= 0xdf)
 216                 utf8data->size = 2;
 217         else if (ch >= 0xe0 && ch <= 0xef)
 218                 utf8data->size = 3;
 219         else if (ch >= 0xf0 && ch <= 0xf4)
 220                 utf8data->size = 4;
 221         else
 222                 return (0);
 223         utf8_append(utf8data, ch);
 224         return (1);
 225 }
 226
 227 /*
 228  * Append character to UTF-8, closing if finished.
 229  *
 230  * Returns 1 if more UTF-8 data to come, 0 if finished.
 231  */
 232 int
 233 utf8_append(struct utf8_data *utf8data, u_char ch)
 234 {
 235         if (utf8data->have >= utf8data->size)
 236                 fatalx("UTF-8 character overflow");
 237         if (utf8data->size > sizeof utf8data->data)
 238                 fatalx("UTF-8 character size too large");
 239
 240         utf8data->data[utf8data->have++] = ch;
 241         if (utf8data->have != utf8data->size)
 242                 return (1);
 243
 244         utf8data->width = utf8_width(utf8data);
 245         return (0);
 246 }
 247
 248 /* Check if two width tree entries overlap. */
 249 int
 250 utf8_overlap(
 251     struct utf8_width_entry *item1, struct utf8_width_entry *item2)
 252 {
 253         if (item1->first >= item2->first && item1->first <= item2->last)
 254                 return (1);
 255         if (item1->last >= item2->first && item1->last <= item2->last)
 256                 return (1);
 257         if (item2->first >= item1->first && item2->first <= item1->last)
 258                 return (1);
 259         if (item2->last >= item1->first && item2->last <= item1->last)
 260                 return (1);
 261         return (0);
 262 }
 263
 264 /* Build UTF-8 width tree. */
 265 void
 266 utf8_build(void)
 267 {
 268         struct utf8_width_entry **ptr, *item, *node;
 269         u_int                     i, j;
 270
 271         for (i = 0; i < nitems(utf8_width_table); i++) {
 272                 item = &utf8_width_table[i];
 273
 274                 for (j = 0; j < nitems(utf8_width_table); j++) {
 275                         if (i != j && utf8_overlap(item, &utf8_width_table[j]))
 276                                 log_fatalx("utf8 overlap: %u %u", i, j);
 277                 }
 278
 279                 ptr = &utf8_width_root;
 280                 while (*ptr != NULL) {
 281                         node = *ptr;
 282                         if (item->last < node->first)
 283                                 ptr = &(node->left);
 284                         else if (item->first > node->last)
 285                                 ptr = &(node->right);
 286                 }
 287                 *ptr = item;
 288         }
 289 }
 290
 291 /* Combine UTF-8 into 32-bit Unicode. */
 292 u_int
 293 utf8_combine(const struct utf8_data *utf8data)
 294 {
 295         u_int   value;
 296
 297         value = 0xff;
 298         switch (utf8data->size) {
 299         case 1:
 300                 value = utf8data->data[0];
 301                 break;
 302         case 2:
 303                 value = utf8data->data[1] & 0x3f;
 304                 value |= (utf8data->data[0] & 0x1f) << 6;
 305                 break;
 306         case 3:
 307                 value = utf8data->data[2] & 0x3f;
 308                 value |= (utf8data->data[1] & 0x3f) << 6;
 309                 value |= (utf8data->data[0] & 0x0f) << 12;
 310                 break;
 311         case 4:
 312                 value = utf8data->data[3] & 0x3f;
 313                 value |= (utf8data->data[2] & 0x3f) << 6;
 314                 value |= (utf8data->data[1] & 0x3f) << 12;
 315                 value |= (utf8data->data[0] & 0x3f) << 18;
 316                 break;
 317         }
 318         return (value);
 319 }
 320
 321 /* Split a two-byte UTF-8 character. */
 322 u_int
 323 utf8_split2(u_int uc, u_char *ptr)
 324 {
 325         if (uc > 0x7f) {
 326                 ptr[0] = (uc >> 6) | 0xc0;
 327                 ptr[1] = (uc & 0x3f) | 0x80;
 328                 return (2);
 329         }
 330         ptr[0] = uc;
 331         return (1);
 332 }
 333
 334 /* Lookup width of UTF-8 data in tree. */
 335 u_int
 336 utf8_width(const struct utf8_data *utf8data)
 337 {
 338         struct utf8_width_entry *item;
 339         u_int                    value;
 340
 341         value = utf8_combine(utf8data);
 342
 343         item = utf8_width_root;
 344         while (item != NULL) {
 345                 if (value < item->first)
 346                         item = item->left;
 347                 else if (value > item->last)
 348                         item = item->right;
 349                 else
 350                         return (item->width);
 351         }
 352         return (1);
 353 }