1 /* $OpenBSD: utf8.c,v 1.11 2014/04/17 15:37:55 nicm Exp $ */ 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 <stdlib.h> 22 #include <string.h> 23 #include <vis.h> 24 25 #include "tmux.h" 26 27 struct utf8_width_entry { 28 u_int first; 29 u_int last; 30 31 int width; 32 33 struct utf8_width_entry *left; 34 struct utf8_width_entry *right; 35 }; 36 37 /* Random order. Not optimal but it'll do for now... */ 38 struct utf8_width_entry utf8_width_table[] = { 39 { 0x00951, 0x00954, 0, NULL, NULL }, 40 { 0x00ccc, 0x00ccd, 0, NULL, NULL }, 41 { 0x0fff9, 0x0fffb, 0, NULL, NULL }, 42 { 0x20000, 0x2fffd, 2, NULL, NULL }, 43 { 0x00ebb, 0x00ebc, 0, NULL, NULL }, 44 { 0x01932, 0x01932, 0, NULL, NULL }, 45 { 0x0070f, 0x0070f, 0, NULL, NULL }, 46 { 0x00a70, 0x00a71, 0, NULL, NULL }, 47 { 0x02329, 0x02329, 2, NULL, NULL }, 48 { 0x00acd, 0x00acd, 0, NULL, NULL }, 49 { 0x00ac7, 0x00ac8, 0, NULL, NULL }, 50 { 0x00a3c, 0x00a3c, 0, NULL, NULL }, 51 { 0x009cd, 0x009cd, 0, NULL, NULL }, 52 { 0x00591, 0x005bd, 0, NULL, NULL }, 53 { 0x01058, 0x01059, 0, NULL, NULL }, 54 { 0x0ffe0, 0x0ffe6, 2, NULL, NULL }, 55 { 0x01100, 0x0115f, 2, NULL, NULL }, 56 { 0x0fe20, 0x0fe23, 0, NULL, NULL }, 57 { 0x0302a, 0x0302f, 0, NULL, NULL }, 58 { 0x01772, 0x01773, 0, NULL, NULL }, 59 { 0x005bf, 0x005bf, 0, NULL, NULL }, 60 { 0x006ea, 0x006ed, 0, NULL, NULL }, 61 { 0x00bc0, 0x00bc0, 0, NULL, NULL }, 62 { 0x00962, 0x00963, 0, NULL, NULL }, 63 { 0x01732, 0x01734, 0, NULL, NULL }, 64 { 0x00d41, 0x00d43, 0, NULL, NULL }, 65 { 0x01b42, 0x01b42, 0, NULL, NULL }, 66 { 0x00a41, 0x00a42, 0, NULL, NULL }, 67 { 0x00eb4, 0x00eb9, 0, NULL, NULL }, 68 { 0x00b01, 0x00b01, 0, NULL, NULL }, 69 { 0x00e34, 0x00e3a, 0, NULL, NULL }, 70 { 0x03040, 0x03098, 2, NULL, NULL }, 71 { 0x0093c, 0x0093c, 0, NULL, NULL }, 72 { 0x00c4a, 0x00c4d, 0, NULL, NULL }, 73 { 0x01032, 0x01032, 0, NULL, NULL }, 74 { 0x00f37, 0x00f37, 0, NULL, NULL }, 75 { 0x00901, 0x00902, 0, NULL, NULL }, 76 { 0x00cbf, 0x00cbf, 0, NULL, NULL }, 77 { 0x0a806, 0x0a806, 0, NULL, NULL }, 78 { 0x00dd2, 0x00dd4, 0, NULL, NULL }, 79 { 0x00f71, 0x00f7e, 0, NULL, NULL }, 80 { 0x01752, 0x01753, 0, NULL, NULL }, 81 { 0x1d242, 0x1d244, 0, NULL, NULL }, 82 { 0x005c1, 0x005c2, 0, NULL, NULL }, 83 { 0x0309b, 0x0a4cf, 2, NULL, NULL }, 84 { 0xe0100, 0xe01ef, 0, NULL, NULL }, 85 { 0x017dd, 0x017dd, 0, NULL, NULL }, 86 { 0x00600, 0x00603, 0, NULL, NULL }, 87 { 0x009e2, 0x009e3, 0, NULL, NULL }, 88 { 0x00cc6, 0x00cc6, 0, NULL, NULL }, 89 { 0x0a80b, 0x0a80b, 0, NULL, NULL }, 90 { 0x01712, 0x01714, 0, NULL, NULL }, 91 { 0x00b3c, 0x00b3c, 0, NULL, NULL }, 92 { 0x01b00, 0x01b03, 0, NULL, NULL }, 93 { 0x007eb, 0x007f3, 0, NULL, NULL }, 94 { 0xe0001, 0xe0001, 0, NULL, NULL }, 95 { 0x1d185, 0x1d18b, 0, NULL, NULL }, 96 { 0x0feff, 0x0feff, 0, NULL, NULL }, 97 { 0x01b36, 0x01b3a, 0, NULL, NULL }, 98 { 0x01920, 0x01922, 0, NULL, NULL }, 99 { 0x00670, 0x00670, 0, NULL, NULL }, 100 { 0x00f90, 0x00f97, 0, NULL, NULL }, 101 { 0x01927, 0x01928, 0, NULL, NULL }, 102 { 0x0200b, 0x0200f, 0, NULL, NULL }, 103 { 0x0ff00, 0x0ff60, 2, NULL, NULL }, 104 { 0x0f900, 0x0faff, 2, NULL, NULL }, 105 { 0x0fb1e, 0x0fb1e, 0, NULL, NULL }, 106 { 0x00cbc, 0x00cbc, 0, NULL, NULL }, 107 { 0x00eb1, 0x00eb1, 0, NULL, NULL }, 108 { 0x10a38, 0x10a3a, 0, NULL, NULL }, 109 { 0x007a6, 0x007b0, 0, NULL, NULL }, 110 { 0x00f80, 0x00f84, 0, NULL, NULL }, 111 { 0x005c4, 0x005c5, 0, NULL, NULL }, 112 { 0x0ac00, 0x0d7a3, 2, NULL, NULL }, 113 { 0x017c9, 0x017d3, 0, NULL, NULL }, 114 { 0x00d4d, 0x00d4d, 0, NULL, NULL }, 115 { 0x1d167, 0x1d169, 0, NULL, NULL }, 116 { 0x01036, 0x01037, 0, NULL, NULL }, 117 { 0xe0020, 0xe007f, 0, NULL, NULL }, 118 { 0x00f35, 0x00f35, 0, NULL, NULL }, 119 { 0x017b4, 0x017b5, 0, NULL, NULL }, 120 { 0x0206a, 0x0206f, 0, NULL, NULL }, 121 { 0x00c46, 0x00c48, 0, NULL, NULL }, 122 { 0x01939, 0x0193b, 0, NULL, NULL }, 123 { 0x01dc0, 0x01dca, 0, NULL, NULL }, 124 { 0x10a0c, 0x10a0f, 0, NULL, NULL }, 125 { 0x0102d, 0x01030, 0, NULL, NULL }, 126 { 0x017c6, 0x017c6, 0, NULL, NULL }, 127 { 0x00ec8, 0x00ecd, 0, NULL, NULL }, 128 { 0x00b41, 0x00b43, 0, NULL, NULL }, 129 { 0x017b7, 0x017bd, 0, NULL, NULL }, 130 { 0x1d173, 0x1d182, 0, NULL, NULL }, 131 { 0x00a47, 0x00a48, 0, NULL, NULL }, 132 { 0x0232a, 0x0232a, 2, NULL, NULL }, 133 { 0x01b3c, 0x01b3c, 0, NULL, NULL }, 134 { 0x10a01, 0x10a03, 0, NULL, NULL }, 135 { 0x00ae2, 0x00ae3, 0, NULL, NULL }, 136 { 0x00483, 0x00486, 0, NULL, NULL }, 137 { 0x0135f, 0x0135f, 0, NULL, NULL }, 138 { 0x01a17, 0x01a18, 0, NULL, NULL }, 139 { 0x006e7, 0x006e8, 0, NULL, NULL }, 140 { 0x03099, 0x0309a, 0, NULL, NULL }, 141 { 0x00b4d, 0x00b4d, 0, NULL, NULL }, 142 { 0x00ce2, 0x00ce3, 0, NULL, NULL }, 143 { 0x00bcd, 0x00bcd, 0, NULL, NULL }, 144 { 0x00610, 0x00615, 0, NULL, NULL }, 145 { 0x00f99, 0x00fbc, 0, NULL, NULL }, 146 { 0x009c1, 0x009c4, 0, NULL, NULL }, 147 { 0x00730, 0x0074a, 0, NULL, NULL }, 148 { 0x00300, 0x0036f, 0, NULL, NULL }, 149 { 0x03030, 0x0303e, 2, NULL, NULL }, 150 { 0x01b34, 0x01b34, 0, NULL, NULL }, 151 { 0x1d1aa, 0x1d1ad, 0, NULL, NULL }, 152 { 0x00dca, 0x00dca, 0, NULL, NULL }, 153 { 0x006d6, 0x006e4, 0, NULL, NULL }, 154 { 0x00f86, 0x00f87, 0, NULL, NULL }, 155 { 0x00b3f, 0x00b3f, 0, NULL, NULL }, 156 { 0x0fe30, 0x0fe6f, 2, NULL, NULL }, 157 { 0x01039, 0x01039, 0, NULL, NULL }, 158 { 0x0094d, 0x0094d, 0, NULL, NULL }, 159 { 0x00c55, 0x00c56, 0, NULL, NULL }, 160 { 0x00488, 0x00489, 0, NULL, NULL }, 161 { 0x00e47, 0x00e4e, 0, NULL, NULL }, 162 { 0x00a81, 0x00a82, 0, NULL, NULL }, 163 { 0x00ac1, 0x00ac5, 0, NULL, NULL }, 164 { 0x0202a, 0x0202e, 0, NULL, NULL }, 165 { 0x00dd6, 0x00dd6, 0, NULL, NULL }, 166 { 0x018a9, 0x018a9, 0, NULL, NULL }, 167 { 0x0064b, 0x0065e, 0, NULL, NULL }, 168 { 0x00abc, 0x00abc, 0, NULL, NULL }, 169 { 0x00b82, 0x00b82, 0, NULL, NULL }, 170 { 0x00f39, 0x00f39, 0, NULL, NULL }, 171 { 0x020d0, 0x020ef, 0, NULL, NULL }, 172 { 0x01dfe, 0x01dff, 0, NULL, NULL }, 173 { 0x30000, 0x3fffd, 2, NULL, NULL }, 174 { 0x00711, 0x00711, 0, NULL, NULL }, 175 { 0x0fe00, 0x0fe0f, 0, NULL, NULL }, 176 { 0x0180b, 0x0180d, 0, NULL, NULL }, 177 { 0x10a3f, 0x10a3f, 0, NULL, NULL }, 178 { 0x00981, 0x00981, 0, NULL, NULL }, 179 { 0x0a825, 0x0a826, 0, NULL, NULL }, 180 { 0x00941, 0x00948, 0, NULL, NULL }, 181 { 0x01b6b, 0x01b73, 0, NULL, NULL }, 182 { 0x00e31, 0x00e31, 0, NULL, NULL }, 183 { 0x0fe10, 0x0fe19, 2, NULL, NULL }, 184 { 0x00a01, 0x00a02, 0, NULL, NULL }, 185 { 0x00a4b, 0x00a4d, 0, NULL, NULL }, 186 { 0x00f18, 0x00f19, 0, NULL, NULL }, 187 { 0x00fc6, 0x00fc6, 0, NULL, NULL }, 188 { 0x02e80, 0x03029, 2, NULL, NULL }, 189 { 0x00b56, 0x00b56, 0, NULL, NULL }, 190 { 0x009bc, 0x009bc, 0, NULL, NULL }, 191 { 0x005c7, 0x005c7, 0, NULL, NULL }, 192 { 0x02060, 0x02063, 0, NULL, NULL }, 193 { 0x00c3e, 0x00c40, 0, NULL, NULL }, 194 { 0x10a05, 0x10a06, 0, NULL, NULL }, 195 }; 196 197 struct utf8_width_entry *utf8_width_root = NULL; 198 199 int utf8_overlap(struct utf8_width_entry *, struct utf8_width_entry *); 200 u_int utf8_combine(const struct utf8_data *); 201 u_int utf8_width(const struct utf8_data *); 202 203 /* Set a single character. */ 204 void 205 utf8_set(struct utf8_data *utf8data, u_char ch) 206 { 207 *utf8data->data = ch; 208 utf8data->size = 1; 209 210 utf8data->width = 1; 211 } 212 213 /* 214 * Open UTF-8 sequence. 215 * 216 * 11000010-11011111 C2-DF start of 2-byte sequence 217 * 11100000-11101111 E0-EF start of 3-byte sequence 218 * 11110000-11110100 F0-F4 start of 4-byte sequence 219 * 220 * Returns 1 if more UTF-8 to come, 0 if not UTF-8. 221 */ 222 int 223 utf8_open(struct utf8_data *utf8data, u_char ch) 224 { 225 memset(utf8data, 0, sizeof *utf8data); 226 if (ch >= 0xc2 && ch <= 0xdf) 227 utf8data->size = 2; 228 else if (ch >= 0xe0 && ch <= 0xef) 229 utf8data->size = 3; 230 else if (ch >= 0xf0 && ch <= 0xf4) 231 utf8data->size = 4; 232 else 233 return (0); 234 utf8_append(utf8data, ch); 235 return (1); 236 } 237 238 /* 239 * Append character to UTF-8, closing if finished. 240 * 241 * Returns 1 if more UTF-8 data to come, 0 if finished. 242 */ 243 int 244 utf8_append(struct utf8_data *utf8data, u_char ch) 245 { 246 if (utf8data->have >= utf8data->size) 247 fatalx("UTF-8 character overflow"); 248 if (utf8data->size > sizeof utf8data->data) 249 fatalx("UTF-8 character size too large"); 250 251 utf8data->data[utf8data->have++] = ch; 252 if (utf8data->have != utf8data->size) 253 return (1); 254 255 utf8data->width = utf8_width(utf8data); 256 return (0); 257 } 258 259 /* Check if two width tree entries overlap. */ 260 int 261 utf8_overlap(struct utf8_width_entry *item1, struct utf8_width_entry *item2) 262 { 263 if (item1->first >= item2->first && item1->first <= item2->last) 264 return (1); 265 if (item1->last >= item2->first && item1->last <= item2->last) 266 return (1); 267 if (item2->first >= item1->first && item2->first <= item1->last) 268 return (1); 269 if (item2->last >= item1->first && item2->last <= item1->last) 270 return (1); 271 return (0); 272 } 273 274 /* Build UTF-8 width tree. */ 275 void 276 utf8_build(void) 277 { 278 struct utf8_width_entry **ptr, *item, *node; 279 u_int i, j; 280 281 for (i = 0; i < nitems(utf8_width_table); i++) { 282 item = &utf8_width_table[i]; 283 284 for (j = 0; j < nitems(utf8_width_table); j++) { 285 if (i != j && utf8_overlap(item, &utf8_width_table[j])) 286 log_fatalx("utf8 overlap: %u %u", i, j); 287 } 288 289 ptr = &utf8_width_root; 290 while (*ptr != NULL) { 291 node = *ptr; 292 if (item->last < node->first) 293 ptr = &(node->left); 294 else if (item->first > node->last) 295 ptr = &(node->right); 296 } 297 *ptr = item; 298 } 299 } 300 301 /* Combine UTF-8 into 32-bit Unicode. */ 302 u_int 303 utf8_combine(const struct utf8_data *utf8data) 304 { 305 u_int value; 306 307 value = 0xff; 308 switch (utf8data->size) { 309 case 1: 310 value = utf8data->data[0]; 311 break; 312 case 2: 313 value = utf8data->data[1] & 0x3f; 314 value |= (utf8data->data[0] & 0x1f) << 6; 315 break; 316 case 3: 317 value = utf8data->data[2] & 0x3f; 318 value |= (utf8data->data[1] & 0x3f) << 6; 319 value |= (utf8data->data[0] & 0x0f) << 12; 320 break; 321 case 4: 322 value = utf8data->data[3] & 0x3f; 323 value |= (utf8data->data[2] & 0x3f) << 6; 324 value |= (utf8data->data[1] & 0x3f) << 12; 325 value |= (utf8data->data[0] & 0x07) << 18; 326 break; 327 } 328 return (value); 329 } 330 331 /* Split a two-byte UTF-8 character. */ 332 u_int 333 utf8_split2(u_int uc, u_char *ptr) 334 { 335 if (uc > 0x7f) { 336 ptr[0] = (uc >> 6) | 0xc0; 337 ptr[1] = (uc & 0x3f) | 0x80; 338 return (2); 339 } 340 ptr[0] = uc; 341 return (1); 342 } 343 344 /* Lookup width of UTF-8 data in tree. */ 345 u_int 346 utf8_width(const struct utf8_data *utf8data) 347 { 348 struct utf8_width_entry *item; 349 u_int value; 350 351 value = utf8_combine(utf8data); 352 353 item = utf8_width_root; 354 while (item != NULL) { 355 if (value < item->first) 356 item = item->left; 357 else if (value > item->last) 358 item = item->right; 359 else 360 return (item->width); 361 } 362 return (1); 363 } 364 365 /* 366 * Encode len characters from src into dst, which is guaranteed to have four 367 * bytes available for each character from src (for \abc or UTF-8) plus space 368 * for \0. 369 */ 370 int 371 utf8_strvis(char *dst, const char *src, size_t len, int flag) 372 { 373 struct utf8_data utf8data; 374 const char *start, *end; 375 int more; 376 size_t i; 377 378 start = dst; 379 end = src + len; 380 381 while (src < end) { 382 if (utf8_open(&utf8data, *src)) { 383 more = 1; 384 while (++src < end && more) 385 more = utf8_append(&utf8data, *src); 386 if (!more) { 387 /* UTF-8 character finished. */ 388 for (i = 0; i < utf8data.size; i++) 389 *dst++ = utf8data.data[i]; 390 continue; 391 } else if (utf8data.have > 0) { 392 /* Not a complete UTF-8 character. */ 393 src -= utf8data.have; 394 } 395 } 396 if (src < end - 1) 397 dst = vis(dst, src[0], flag, src[1]); 398 else if (src < end) 399 dst = vis(dst, src[0], flag, '\0'); 400 src++; 401 } 402 403 *dst = '\0'; 404 return (dst - start); 405 } 406 407 /* 408 * Convert a string into a buffer of UTF-8 characters. Terminated by size == 0. 409 * Caller frees. 410 */ 411 struct utf8_data * 412 utf8_fromcstr(const char *src) 413 { 414 struct utf8_data *dst; 415 size_t n; 416 int more; 417 418 dst = NULL; 419 420 n = 0; 421 while (*src != '\0') { 422 dst = xrealloc(dst, n + 1, sizeof *dst); 423 if (utf8_open(&dst[n], *src)) { 424 more = 1; 425 while (*++src != '\0' && more) 426 more = utf8_append(&dst[n], *src); 427 if (!more) { 428 n++; 429 continue; 430 } 431 src -= dst[n].have; 432 } 433 utf8_set(&dst[n], *src); 434 src++; 435 436 n++; 437 } 438 439 dst = xrealloc(dst, n + 1, sizeof *dst); 440 dst[n].size = 0; 441 return (dst); 442 } 443 444 /* Convert from a buffer of UTF-8 characters into a string. Caller frees. */ 445 char * 446 utf8_tocstr(struct utf8_data *src) 447 { 448 char *dst; 449 size_t n; 450 451 dst = NULL; 452 453 n = 0; 454 for(; src->size != 0; src++) { 455 dst = xrealloc(dst, n + src->size, 1); 456 memcpy(dst + n, src->data, src->size); 457 n += src->size; 458 } 459 460 dst = xrealloc(dst, n + 1, 1); 461 dst[n] = '\0'; 462 return (dst); 463 } 464 465 /* Get width of UTF-8 string. */ 466 u_int 467 utf8_cstrwidth(const char *s) 468 { 469 struct utf8_data tmp; 470 u_int width; 471 int more; 472 473 width = 0; 474 while (*s != '\0') { 475 if (utf8_open(&tmp, *s)) { 476 more = 1; 477 while (*++s != '\0' && more) 478 more = utf8_append(&tmp, *s); 479 if (!more) { 480 width += tmp.width; 481 continue; 482 } 483 s -= tmp.have; 484 } 485 width++; 486 s++; 487 } 488 return (width); 489 } 490 491 /* Trim UTF-8 string to width. Caller frees. */ 492 char * 493 utf8_trimcstr(const char *s, u_int width) 494 { 495 struct utf8_data *tmp, *next; 496 char *out; 497 u_int at; 498 499 tmp = utf8_fromcstr(s); 500 501 at = 0; 502 for (next = tmp; next->size != 0; next++) { 503 if (at + next->width > width) { 504 next->size = 0; 505 break; 506 } 507 at += next->width; 508 } 509 510 out = utf8_tocstr(tmp); 511 free(tmp); 512 return (out); 513 } 514