Annotation of src/usr.bin/tmux/utf8.c, Revision 1.11
1.11 ! nicm 1: /* $OpenBSD: utf8.c,v 1.10 2014/04/17 14:45:49 nicm Exp $ */
1.1 nicm 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:
1.11 ! nicm 21: #include <stdlib.h>
1.1 nicm 22: #include <string.h>
1.9 nicm 23: #include <vis.h>
1.1 nicm 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 *);
1.4 nicm 200: u_int utf8_combine(const struct utf8_data *);
201: u_int utf8_width(const struct utf8_data *);
1.1 nicm 202:
1.11 ! nicm 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:
1.4 nicm 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: *
1.5 nicm 241: * Returns 1 if more UTF-8 data to come, 0 if finished.
1.4 nicm 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. */
1.1 nicm 260: int
1.10 nicm 261: utf8_overlap(struct utf8_width_entry *item1, struct utf8_width_entry *item2)
1.1 nicm 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:
1.4 nicm 274: /* Build UTF-8 width tree. */
1.1 nicm 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:
1.4 nicm 301: /* Combine UTF-8 into 32-bit Unicode. */
1.1 nicm 302: u_int
1.4 nicm 303: utf8_combine(const struct utf8_data *utf8data)
1.1 nicm 304: {
1.4 nicm 305: u_int value;
1.1 nicm 306:
1.4 nicm 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;
1.8 nicm 325: value |= (utf8data->data[0] & 0x07) << 18;
1.4 nicm 326: break;
1.1 nicm 327: }
1.4 nicm 328: return (value);
1.6 nicm 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);
1.1 nicm 342: }
343:
1.4 nicm 344: /* Lookup width of UTF-8 data in tree. */
345: u_int
346: utf8_width(const struct utf8_data *utf8data)
1.1 nicm 347: {
348: struct utf8_width_entry *item;
1.4 nicm 349: u_int value;
1.1 nicm 350:
1.4 nicm 351: value = utf8_combine(utf8data);
1.1 nicm 352:
353: item = utf8_width_root;
354: while (item != NULL) {
1.4 nicm 355: if (value < item->first)
1.1 nicm 356: item = item->left;
1.4 nicm 357: else if (value > item->last)
1.1 nicm 358: item = item->right;
359: else
360: return (item->width);
361: }
362: return (1);
1.9 nicm 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);
1.11 ! nicm 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);
1.1 nicm 513: }