1 /*
2 * Copyright 2008-2013 Various Authors
3 * Copyright 2004-2005 Timo Hirvonen
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation; either version 2 of the
8 * License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include "uchar.h"
20 #include "compiler.h"
21 #include "gbuf.h"
22 #include "utils.h" /* N_ELEMENTS */
23 #include "ui_curses.h" /* using_utf8, charset */
24 #include "convert.h"
25
26 #include <stdlib.h>
27 #include <string.h>
28 #include <wchar.h>
29 #include <wctype.h>
30 #include <ctype.h>
31
32 #include "unidecomp.h"
33
34 const char hex_tab[16] = "0123456789abcdef";
35
36 /*
37 * Byte Sequence Min Min Max
38 * ----------------------------------------------------------------------------------
39 * 0xxxxxxx 0000000 0x00000 0x00007f
40 * 110xxxxx 10xxxxxx 000 10000000 0x00080 0x0007ff
41 * 1110xxxx 10xxxxxx 10xxxxxx 00001000 00000000 0x00800 0x00ffff
42 * 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 00001 00000000 00000000 0x10000 0x10ffff (not 0x1fffff)
43 *
44 * max: 100 001111 111111 111111 (0x10ffff)
45 */
46
47 /* Length of UTF-8 byte sequence.
48 * Table index is the first byte of UTF-8 sequence.
49 */
50 static const signed char len_tab[256] = {
51 /* 0-127 0xxxxxxx */
52 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
53 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
54 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
55 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
56 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
57 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
58 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
59 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
60
61 /* 128-191 10xxxxxx (invalid first byte) */
62 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
63 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
64 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
65 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
66
67 /* 192-223 110xxxxx */
68 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
69 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
70
71 /* 224-239 1110xxxx */
72 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
73
74 /* 240-244 11110xxx (000 - 100) */
75 4, 4, 4, 4, 4,
76
77 /* 11110xxx (101 - 111) (always invalid) */
78 -1, -1, -1,
79
80 /* 11111xxx (always invalid) */
81 -1, -1, -1, -1, -1, -1, -1, -1
82 };
83
84 /* fault-tolerant equivalent to len_tab, from glib */
85 static const char utf8_skip_data[256] = {
86 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
87 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
88 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
89 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
90 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
91 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
92 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
93 3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,6,6,1,1
94 };
95 const char * const utf8_skip = utf8_skip_data;
96
97 /* index is length of the UTF-8 sequence - 1 */
98 static int min_val[4] = { 0x000000, 0x000080, 0x000800, 0x010000 };
99 static int max_val[4] = { 0x00007f, 0x0007ff, 0x00ffff, 0x10ffff };
100
101 /* get value bits from the first UTF-8 sequence byte */
102 static unsigned int first_byte_mask[4] = { 0x7f, 0x1f, 0x0f, 0x07 };
103
u_is_valid(const char * str)104 int u_is_valid(const char *str)
105 {
106 const unsigned char *s = (const unsigned char *)str;
107 int i = 0;
108
109 while (s[i]) {
110 unsigned char ch = s[i++];
111 int len = len_tab[ch];
112
113 if (len <= 0)
114 return 0;
115
116 if (len > 1) {
117 /* len - 1 10xxxxxx bytes */
118 uchar u;
119 int c;
120
121 len--;
122 u = ch & first_byte_mask[len];
123 c = len;
124 do {
125 ch = s[i++];
126 if (len_tab[ch] != 0)
127 return 0;
128 u = (u << 6) | (ch & 0x3f);
129 } while (--c);
130
131 if (u < min_val[len] || u > max_val[len])
132 return 0;
133 }
134 }
135 return 1;
136 }
137
u_strlen(const char * str)138 size_t u_strlen(const char *str)
139 {
140 size_t len;
141 for (len = 0; *str; len++)
142 str = u_next_char(str);
143 return len;
144 }
145
u_strlen_safe(const char * str)146 size_t u_strlen_safe(const char *str)
147 {
148 const unsigned char *s = (const unsigned char *)str;
149 size_t len = 0;
150
151 while (*s) {
152 int l = len_tab[*s];
153
154 if (unlikely(l > 1)) {
155 /* next l - 1 bytes must be 0x10xxxxxx */
156 int c = 1;
157 do {
158 if (len_tab[s[c]] != 0) {
159 /* invalid sequence */
160 goto single_char;
161 }
162 c++;
163 } while (c < l);
164
165 /* valid sequence */
166 s += l;
167 len++;
168 continue;
169 }
170 single_char:
171 /* l is -1, 0 or 1
172 * invalid chars counted as single characters */
173 s++;
174 len++;
175 }
176 return len;
177 }
178
u_char_width(uchar u)179 int u_char_width(uchar u)
180 {
181 if (unlikely(u < 0x20))
182 goto control;
183
184 /* Combining Diacritical Marks */
185 if (u >= 0x300U && u <= 0x36fU)
186 goto zero;
187
188 if (u < 0x1100U)
189 goto narrow;
190
191 /* Hangul Jamo init. consonants */
192 if (u <= 0x115fU)
193 goto wide;
194
195 /* Zero-width characters */
196 if (u == 0x200bU || u == 0x200cU || u == 0x200dU)
197 goto zero;
198
199 /* angle brackets */
200 if (u == 0x2329U || u == 0x232aU)
201 goto wide;
202
203 if (u < 0x2e80U)
204 goto narrow;
205 /* CJK ... Yi */
206 if (u < 0x302aU)
207 goto wide;
208 if (u <= 0x302fU)
209 goto narrow;
210 if (u == 0x303fU)
211 goto narrow;
212 if (u == 0x3099U)
213 goto narrow;
214 if (u == 0x309aU)
215 goto narrow;
216 /* CJK ... Yi */
217 if (u <= 0xa4cfU)
218 goto wide;
219
220 /* Hangul Syllables */
221 if (u >= 0xac00U && u <= 0xd7a3U)
222 goto wide;
223
224 /* CJK Compatibility Ideographs */
225 if (u >= 0xf900U && u <= 0xfaffU)
226 goto wide;
227
228 /* CJK Compatibility Forms */
229 if (u >= 0xfe30U && u <= 0xfe6fU)
230 goto wide;
231
232 /* Fullwidth Forms */
233 if (u >= 0xff00U && u <= 0xff60U)
234 goto wide;
235
236 /* Halfwidth Forms */
237 if (u >= 0xff61U && u <= 0xffdfU)
238 goto narrow;
239
240 /* Fullwidth Forms */
241 if (u >= 0xffe0U && u <= 0xffe6U)
242 goto wide;
243
244 /* Halfwidth Forms */
245 if (u >= 0xffe8U && u <= 0xffeeU)
246 goto narrow;
247
248 /* CJK extra stuff */
249 if (u >= 0x20000U && u <= 0x2fffdU)
250 goto wide;
251
252 /* ? */
253 if (u >= 0x30000U && u <= 0x3fffdU)
254 goto wide;
255
256 /* invalid bytes in unicode stream are rendered "<xx>" */
257 if (u & U_INVALID_MASK)
258 goto invalid;
259 zero:
260 return 0;
261 narrow:
262 return 1;
263 wide:
264 return 2;
265 control:
266 /* special case */
267 if (u == 0)
268 return 1;
269
270 /* print control chars as <xx> */
271 invalid:
272 return 4;
273 }
274
u_str_width(const char * str)275 int u_str_width(const char *str)
276 {
277 int idx = 0, w = 0;
278
279 while (str[idx]) {
280 uchar u = u_get_char(str, &idx);
281 w += u_char_width(u);
282 }
283 return w;
284 }
285
u_str_nwidth(const char * str,int len)286 int u_str_nwidth(const char *str, int len)
287 {
288 int idx = 0;
289 int w = 0;
290
291 while (len > 0) {
292 uchar u = u_get_char(str, &idx);
293 if (u == 0)
294 break;
295 w += u_char_width(u);
296 len--;
297 }
298 return w;
299 }
300
u_strchr(const char * str,uchar uch)301 char *u_strchr(const char *str, uchar uch)
302 {
303 int idx = 0;
304
305 while (str[idx]) {
306 uchar u = u_get_char(str, &idx);
307 if (uch == u)
308 return (char *) (str + idx);
309 }
310 return NULL;
311 }
312
u_prev_char_pos(const char * str,int * idx)313 void u_prev_char_pos(const char *str, int *idx)
314 {
315 const unsigned char *s = (const unsigned char *)str;
316 int c, len, i = *idx;
317 uchar ch;
318
319 ch = s[--i];
320 len = len_tab[ch];
321 if (len != 0) {
322 /* start of byte sequence or invalid uchar */
323 goto one;
324 }
325
326 c = 1;
327 while (1) {
328 if (i == 0) {
329 /* first byte of the sequence is missing */
330 break;
331 }
332
333 ch = s[--i];
334 len = len_tab[ch];
335 c++;
336
337 if (len == 0) {
338 if (c < 4)
339 continue;
340
341 /* too long sequence */
342 break;
343 }
344 if (len != c) {
345 /* incorrect length */
346 break;
347 }
348
349 /* ok */
350 *idx = i;
351 return;
352 }
353 one:
354 *idx = *idx - 1;
355 return;
356 }
357
u_get_char(const char * str,int * idx)358 uchar u_get_char(const char *str, int *idx)
359 {
360 const unsigned char *s = (const unsigned char *)str;
361 int len, i, x = 0;
362 uchar ch, u;
363
364 if (idx)
365 s += *idx;
366 else
367 idx = &x;
368 ch = s[0];
369
370 /* ASCII optimization */
371 if (ch < 128) {
372 *idx += 1;
373 return ch;
374 }
375
376 len = len_tab[ch];
377 if (unlikely(len < 1))
378 goto invalid;
379
380 u = ch & first_byte_mask[len - 1];
381 for (i = 1; i < len; i++) {
382 ch = s[i];
383 if (unlikely(len_tab[ch] != 0))
384 goto invalid;
385 u = (u << 6) | (ch & 0x3f);
386 }
387 *idx += len;
388 return u;
389 invalid:
390 *idx += 1;
391 u = s[0];
392 return u | U_INVALID_MASK;
393 }
394
u_set_char_raw(char * str,int * idx,uchar uch)395 void u_set_char_raw(char *str, int *idx, uchar uch)
396 {
397 int i = *idx;
398
399 if (uch <= 0x0000007fU) {
400 str[i++] = uch;
401 *idx = i;
402 } else if (uch <= 0x000007ffU) {
403 str[i + 1] = (uch & 63) | 0x80; uch >>= 6;
404 str[i + 0] = uch | 0x000000c0U;
405 i += 2;
406 *idx = i;
407 } else if (uch <= 0x0000ffffU) {
408 str[i + 2] = (uch & 63) | 0x80; uch >>= 6;
409 str[i + 1] = (uch & 63) | 0x80; uch >>= 6;
410 str[i + 0] = uch | 0x000000e0U;
411 i += 3;
412 *idx = i;
413 } else if (uch <= 0x0010ffffU) {
414 str[i + 3] = (uch & 63) | 0x80; uch >>= 6;
415 str[i + 2] = (uch & 63) | 0x80; uch >>= 6;
416 str[i + 1] = (uch & 63) | 0x80; uch >>= 6;
417 str[i + 0] = uch | 0x000000f0U;
418 i += 4;
419 *idx = i;
420 } else {
421 /* must be an invalid uchar */
422 str[i++] = uch & 0xff;
423 *idx = i;
424 }
425 }
426
427 /*
428 * Printing functions, these lose information
429 */
430
u_set_char(char * str,size_t * idx,uchar uch)431 void u_set_char(char *str, size_t *idx, uchar uch)
432 {
433 int i = *idx;
434
435 if (unlikely(uch <= 0x0000001fU))
436 goto invalid;
437
438 if (uch <= 0x0000007fU) {
439 str[i++] = uch;
440 *idx = i;
441 return;
442 } else if (uch <= 0x000007ffU) {
443 str[i + 1] = (uch & 63) | 0x80; uch >>= 6;
444 str[i + 0] = uch | 0x000000c0U;
445 i += 2;
446 *idx = i;
447 return;
448 } else if (uch <= 0x0000ffffU) {
449 str[i + 2] = (uch & 63) | 0x80; uch >>= 6;
450 str[i + 1] = (uch & 63) | 0x80; uch >>= 6;
451 str[i + 0] = uch | 0x000000e0U;
452 i += 3;
453 *idx = i;
454 return;
455 } else if (uch <= 0x0010ffffU) {
456 str[i + 3] = (uch & 63) | 0x80; uch >>= 6;
457 str[i + 2] = (uch & 63) | 0x80; uch >>= 6;
458 str[i + 1] = (uch & 63) | 0x80; uch >>= 6;
459 str[i + 0] = uch | 0x000000f0U;
460 i += 4;
461 *idx = i;
462 return;
463 }
464 invalid:
465 /* control character or invalid unicode */
466 if (uch == 0) {
467 /* handle this special case here to make the common case fast */
468 str[i++] = 0;
469 *idx = i;
470 } else {
471 str[i++] = '<';
472 str[i++] = hex_tab[(uch >> 4) & 0xf];
473 str[i++] = hex_tab[uch & 0xf];
474 str[i++] = '>';
475 *idx = i;
476 }
477 }
478
u_copy_chars(char * dst,const char * src,int * width)479 size_t u_copy_chars(char *dst, const char *src, int *width)
480 {
481 int w = *width;
482 int si = 0;
483 size_t di = 0;
484 int cw;
485 uchar u;
486
487 while (w > 0) {
488 u = u_get_char(src, &si);
489 if (u == 0)
490 break;
491
492 cw = u_char_width(u);
493 w -= cw;
494
495 if (unlikely(w < 0)) {
496 if (cw == 2)
497 dst[di++] = ' ';
498 if (cw == 4) {
499 dst[di++] = '<';
500 if (w >= -2)
501 dst[di++] = hex_tab[(u >> 4) & 0xf];
502 if (w >= -1)
503 dst[di++] = hex_tab[u & 0xf];
504 }
505 w = 0;
506 break;
507 }
508 u_set_char(dst, &di, u);
509 }
510 *width -= w;
511 return di;
512 }
513
u_to_ascii(char * dst,const char * src,int len)514 int u_to_ascii(char *dst, const char *src, int len)
515 {
516 int i, idx = 0;
517 for (i = 0; i < len && src[idx]; i++) {
518 uchar u = u_get_char(src, &idx);
519 dst[i] = (u < 128) ? u : '?';
520 }
521 return i;
522 }
523
u_to_utf8(char * dst,const char * src)524 void u_to_utf8(char *dst, const char *src)
525 {
526 int s = 0;
527 size_t d = 0;
528 uchar u;
529 do {
530 u = u_get_char(src, &s);
531 u_set_char(dst, &d, u);
532 } while (u!=0);
533 }
534
u_print_size(uchar uch)535 int u_print_size(uchar uch)
536 {
537 int s = u_char_size(uch);
538 /* control characters and invalid unicode set as <XX> */
539 if (uch < 0x0000001fU && uch != 0){
540 return 4;
541 }
542 return s;
543 }
544
u_str_print_size(const char * str)545 int u_str_print_size(const char *str)
546 {
547 int l = 0;
548 int idx = 0;
549 uchar u;
550 do {
551 u = u_get_char(str, &idx);
552 l += u_print_size(u);
553 } while (u!=0);
554 return l;
555 }
556
u_skip_chars(const char * str,int * width)557 int u_skip_chars(const char *str, int *width)
558 {
559 int w = *width;
560 int idx = 0;
561
562 while (w > 0) {
563 uchar u = u_get_char(str, &idx);
564 w -= u_char_width(u);
565 }
566 /* add 1..3 if skipped 'too much' (the last char was double width or invalid (<xx>)) */
567 *width -= w;
568 return idx;
569 }
570
571 /*
572 * Case-folding functions
573 */
574
u_casefold_char(uchar ch)575 static inline uchar u_casefold_char(uchar ch)
576 {
577 /* faster lookup for for A-Z, rest of ASCII unaffected */
578 if (ch < 0x0041)
579 return ch;
580 if (ch <= 0x005A)
581 return ch + 0x20;
582 #if defined(_WIN32) || defined(__STDC_ISO_10646__) || defined(__APPLE__)
583 if (ch < 128)
584 return ch;
585 ch = towlower(ch);
586 #endif
587 return ch;
588 }
589
u_casefold(const char * str)590 char *u_casefold(const char *str)
591 {
592 GBUF(out);
593 int i = 0;
594
595 while (str[i]) {
596 char buf[4];
597 int buflen = 0;
598 uchar ch = u_get_char(str, &i);
599
600 ch = u_casefold_char(ch);
601 u_set_char_raw(buf, &buflen, ch);
602 gbuf_add_bytes(&out, buf, buflen);
603 }
604
605 return gbuf_steal(&out);
606 }
607
608 /*
609 * Comparison functions
610 */
611
u_strcase_equal(const char * a,const char * b)612 int u_strcase_equal(const char *a, const char *b)
613 {
614 int ai = 0, bi = 0;
615
616 while (a[ai]) {
617 uchar au, bu;
618
619 au = u_get_char(a, &ai);
620 bu = u_get_char(b, &bi);
621
622 if (u_casefold_char(au) != u_casefold_char(bu))
623 return 0;
624 }
625
626 return b[bi] ? 0 : 1;
627 }
628
get_base_from_composed(uchar ch)629 static uchar get_base_from_composed(uchar ch)
630 {
631 int begin = 0;
632 int end = N_ELEMENTS(unidecomp_map);
633
634 if (ch < unidecomp_map[begin].composed || ch > unidecomp_map[end - 1].composed)
635 return ch;
636
637 /* binary search */
638 while (1) {
639 int half = (begin + end) / 2;
640 if (ch == unidecomp_map[half].composed)
641 return unidecomp_map[half].base;
642 else if (half == begin)
643 break;
644 else if (ch > unidecomp_map[half].composed)
645 begin = half;
646 else
647 end = half;
648 }
649 return ch;
650 }
651
do_u_strncase_equal(const char * a,const char * b,size_t len,int only_base_chars)652 static inline int do_u_strncase_equal(const char *a, const char *b, size_t len, int only_base_chars)
653 {
654 int ai = 0, bi = 0;
655 size_t i;
656
657 for (i = 0; i < len; i++) {
658 uchar au, bu;
659
660 au = u_get_char(a, &ai);
661 bu = u_get_char(b, &bi);
662
663 if (only_base_chars) {
664 au = get_base_from_composed(au);
665 bu = get_base_from_composed(bu);
666 }
667
668 if (u_casefold_char(au) != u_casefold_char(bu))
669 return 0;
670 }
671
672 return 1;
673 }
674
u_strncase_equal(const char * a,const char * b,size_t len)675 int u_strncase_equal(const char *a, const char *b, size_t len)
676 {
677 return do_u_strncase_equal(a, b, len, 0);
678 }
679
u_strncase_equal_base(const char * a,const char * b,size_t len)680 int u_strncase_equal_base(const char *a, const char *b, size_t len)
681 {
682 return do_u_strncase_equal(a, b, len, 1);
683 }
684
do_u_strcasestr(const char * haystack,const char * needle,int only_base_chars)685 static inline char *do_u_strcasestr(const char *haystack, const char *needle, int only_base_chars)
686 {
687 /* strlen is faster and works here */
688 int haystack_len = strlen(haystack);
689 int needle_len = u_strlen(needle);
690
691 do {
692 int idx;
693
694 if (haystack_len < needle_len)
695 return NULL;
696 if (do_u_strncase_equal(needle, haystack, needle_len, only_base_chars))
697 return (char *)haystack;
698
699 /* skip one char */
700 idx = 0;
701 u_get_char(haystack, &idx);
702 haystack += idx;
703 haystack_len -= idx;
704 } while (1);
705 }
706
u_strcasestr(const char * haystack,const char * needle)707 char *u_strcasestr(const char *haystack, const char *needle)
708 {
709 return do_u_strcasestr(haystack, needle, 0);
710 }
711
u_strcasestr_base(const char * haystack,const char * needle)712 char *u_strcasestr_base(const char *haystack, const char *needle)
713 {
714 return do_u_strcasestr(haystack, needle, 1);
715 }
716
u_strcasestr_filename(const char * haystack,const char * needle)717 char *u_strcasestr_filename(const char *haystack, const char *needle)
718 {
719 char *r = NULL, *ustr = NULL;
720 if (!using_utf8 && utf8_encode(haystack, charset, &ustr) == 0)
721 haystack = ustr;
722 r = u_strcasestr_base(haystack, needle);
723 free(ustr);
724 return r;
725 }
726