xref: /netbsd-src/external/bsd/tmux/dist/utf8.c (revision 4d12bfcd155352508213ace5ccc59ce930ea2974) 
1 /* $Id: utf8.c,v 1.1.1.2 2011/08/17 18:40:05 jmmv 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 <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 }
354