Loading...
1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright (c) 2014 SGI.
4 * All rights reserved.
5 */
6
7#include "utf8n.h"
8
9int utf8version_is_supported(const struct unicode_map *um, unsigned int version)
10{
11 int i = um->tables->utf8agetab_size - 1;
12
13 while (i >= 0 && um->tables->utf8agetab[i] != 0) {
14 if (version == um->tables->utf8agetab[i])
15 return 1;
16 i--;
17 }
18 return 0;
19}
20
21/*
22 * UTF-8 valid ranges.
23 *
24 * The UTF-8 encoding spreads the bits of a 32bit word over several
25 * bytes. This table gives the ranges that can be held and how they'd
26 * be represented.
27 *
28 * 0x00000000 0x0000007F: 0xxxxxxx
29 * 0x00000000 0x000007FF: 110xxxxx 10xxxxxx
30 * 0x00000000 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx
31 * 0x00000000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
32 * 0x00000000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
33 * 0x00000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
34 *
35 * There is an additional requirement on UTF-8, in that only the
36 * shortest representation of a 32bit value is to be used. A decoder
37 * must not decode sequences that do not satisfy this requirement.
38 * Thus the allowed ranges have a lower bound.
39 *
40 * 0x00000000 0x0000007F: 0xxxxxxx
41 * 0x00000080 0x000007FF: 110xxxxx 10xxxxxx
42 * 0x00000800 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx
43 * 0x00010000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
44 * 0x00200000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
45 * 0x04000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
46 *
47 * Actual unicode characters are limited to the range 0x0 - 0x10FFFF,
48 * 17 planes of 65536 values. This limits the sequences actually seen
49 * even more, to just the following.
50 *
51 * 0 - 0x7F: 0 - 0x7F
52 * 0x80 - 0x7FF: 0xC2 0x80 - 0xDF 0xBF
53 * 0x800 - 0xFFFF: 0xE0 0xA0 0x80 - 0xEF 0xBF 0xBF
54 * 0x10000 - 0x10FFFF: 0xF0 0x90 0x80 0x80 - 0xF4 0x8F 0xBF 0xBF
55 *
56 * Within those ranges the surrogates 0xD800 - 0xDFFF are not allowed.
57 *
58 * Note that the longest sequence seen with valid usage is 4 bytes,
59 * the same a single UTF-32 character. This makes the UTF-8
60 * representation of Unicode strictly smaller than UTF-32.
61 *
62 * The shortest sequence requirement was introduced by:
63 * Corrigendum #1: UTF-8 Shortest Form
64 * It can be found here:
65 * http://www.unicode.org/versions/corrigendum1.html
66 *
67 */
68
69/*
70 * Return the number of bytes used by the current UTF-8 sequence.
71 * Assumes the input points to the first byte of a valid UTF-8
72 * sequence.
73 */
74static inline int utf8clen(const char *s)
75{
76 unsigned char c = *s;
77
78 return 1 + (c >= 0xC0) + (c >= 0xE0) + (c >= 0xF0);
79}
80
81/*
82 * Decode a 3-byte UTF-8 sequence.
83 */
84static unsigned int
85utf8decode3(const char *str)
86{
87 unsigned int uc;
88
89 uc = *str++ & 0x0F;
90 uc <<= 6;
91 uc |= *str++ & 0x3F;
92 uc <<= 6;
93 uc |= *str++ & 0x3F;
94
95 return uc;
96}
97
98/*
99 * Encode a 3-byte UTF-8 sequence.
100 */
101static int
102utf8encode3(char *str, unsigned int val)
103{
104 str[2] = (val & 0x3F) | 0x80;
105 val >>= 6;
106 str[1] = (val & 0x3F) | 0x80;
107 val >>= 6;
108 str[0] = val | 0xE0;
109
110 return 3;
111}
112
113/*
114 * utf8trie_t
115 *
116 * A compact binary tree, used to decode UTF-8 characters.
117 *
118 * Internal nodes are one byte for the node itself, and up to three
119 * bytes for an offset into the tree. The first byte contains the
120 * following information:
121 * NEXTBYTE - flag - advance to next byte if set
122 * BITNUM - 3 bit field - the bit number to tested
123 * OFFLEN - 2 bit field - number of bytes in the offset
124 * if offlen == 0 (non-branching node)
125 * RIGHTPATH - 1 bit field - set if the following node is for the
126 * right-hand path (tested bit is set)
127 * TRIENODE - 1 bit field - set if the following node is an internal
128 * node, otherwise it is a leaf node
129 * if offlen != 0 (branching node)
130 * LEFTNODE - 1 bit field - set if the left-hand node is internal
131 * RIGHTNODE - 1 bit field - set if the right-hand node is internal
132 *
133 * Due to the way utf8 works, there cannot be branching nodes with
134 * NEXTBYTE set, and moreover those nodes always have a righthand
135 * descendant.
136 */
137typedef const unsigned char utf8trie_t;
138#define BITNUM 0x07
139#define NEXTBYTE 0x08
140#define OFFLEN 0x30
141#define OFFLEN_SHIFT 4
142#define RIGHTPATH 0x40
143#define TRIENODE 0x80
144#define RIGHTNODE 0x40
145#define LEFTNODE 0x80
146
147/*
148 * utf8leaf_t
149 *
150 * The leaves of the trie are embedded in the trie, and so the same
151 * underlying datatype: unsigned char.
152 *
153 * leaf[0]: The unicode version, stored as a generation number that is
154 * an index into ->utf8agetab[]. With this we can filter code
155 * points based on the unicode version in which they were
156 * defined. The CCC of a non-defined code point is 0.
157 * leaf[1]: Canonical Combining Class. During normalization, we need
158 * to do a stable sort into ascending order of all characters
159 * with a non-zero CCC that occur between two characters with
160 * a CCC of 0, or at the begin or end of a string.
161 * The unicode standard guarantees that all CCC values are
162 * between 0 and 254 inclusive, which leaves 255 available as
163 * a special value.
164 * Code points with CCC 0 are known as stoppers.
165 * leaf[2]: Decomposition. If leaf[1] == 255, then leaf[2] is the
166 * start of a NUL-terminated string that is the decomposition
167 * of the character.
168 * The CCC of a decomposable character is the same as the CCC
169 * of the first character of its decomposition.
170 * Some characters decompose as the empty string: these are
171 * characters with the Default_Ignorable_Code_Point property.
172 * These do affect normalization, as they all have CCC 0.
173 *
174 * The decompositions in the trie have been fully expanded, with the
175 * exception of Hangul syllables, which are decomposed algorithmically.
176 *
177 * Casefolding, if applicable, is also done using decompositions.
178 *
179 * The trie is constructed in such a way that leaves exist for all
180 * UTF-8 sequences that match the criteria from the "UTF-8 valid
181 * ranges" comment above, and only for those sequences. Therefore a
182 * lookup in the trie can be used to validate the UTF-8 input.
183 */
184typedef const unsigned char utf8leaf_t;
185
186#define LEAF_GEN(LEAF) ((LEAF)[0])
187#define LEAF_CCC(LEAF) ((LEAF)[1])
188#define LEAF_STR(LEAF) ((const char *)((LEAF) + 2))
189
190#define MINCCC (0)
191#define MAXCCC (254)
192#define STOPPER (0)
193#define DECOMPOSE (255)
194
195/* Marker for hangul syllable decomposition. */
196#define HANGUL ((char)(255))
197/* Size of the synthesized leaf used for Hangul syllable decomposition. */
198#define UTF8HANGULLEAF (12)
199
200/*
201 * Hangul decomposition (algorithm from Section 3.12 of Unicode 6.3.0)
202 *
203 * AC00;<Hangul Syllable, First>;Lo;0;L;;;;;N;;;;;
204 * D7A3;<Hangul Syllable, Last>;Lo;0;L;;;;;N;;;;;
205 *
206 * SBase = 0xAC00
207 * LBase = 0x1100
208 * VBase = 0x1161
209 * TBase = 0x11A7
210 * LCount = 19
211 * VCount = 21
212 * TCount = 28
213 * NCount = 588 (VCount * TCount)
214 * SCount = 11172 (LCount * NCount)
215 *
216 * Decomposition:
217 * SIndex = s - SBase
218 *
219 * LV (Canonical/Full)
220 * LIndex = SIndex / NCount
221 * VIndex = (Sindex % NCount) / TCount
222 * LPart = LBase + LIndex
223 * VPart = VBase + VIndex
224 *
225 * LVT (Canonical)
226 * LVIndex = (SIndex / TCount) * TCount
227 * TIndex = (Sindex % TCount)
228 * LVPart = SBase + LVIndex
229 * TPart = TBase + TIndex
230 *
231 * LVT (Full)
232 * LIndex = SIndex / NCount
233 * VIndex = (Sindex % NCount) / TCount
234 * TIndex = (Sindex % TCount)
235 * LPart = LBase + LIndex
236 * VPart = VBase + VIndex
237 * if (TIndex == 0) {
238 * d = <LPart, VPart>
239 * } else {
240 * TPart = TBase + TIndex
241 * d = <LPart, TPart, VPart>
242 * }
243 */
244
245/* Constants */
246#define SB (0xAC00)
247#define LB (0x1100)
248#define VB (0x1161)
249#define TB (0x11A7)
250#define LC (19)
251#define VC (21)
252#define TC (28)
253#define NC (VC * TC)
254#define SC (LC * NC)
255
256/* Algorithmic decomposition of hangul syllable. */
257static utf8leaf_t *
258utf8hangul(const char *str, unsigned char *hangul)
259{
260 unsigned int si;
261 unsigned int li;
262 unsigned int vi;
263 unsigned int ti;
264 unsigned char *h;
265
266 /* Calculate the SI, LI, VI, and TI values. */
267 si = utf8decode3(str) - SB;
268 li = si / NC;
269 vi = (si % NC) / TC;
270 ti = si % TC;
271
272 /* Fill in base of leaf. */
273 h = hangul;
274 LEAF_GEN(h) = 2;
275 LEAF_CCC(h) = DECOMPOSE;
276 h += 2;
277
278 /* Add LPart, a 3-byte UTF-8 sequence. */
279 h += utf8encode3((char *)h, li + LB);
280
281 /* Add VPart, a 3-byte UTF-8 sequence. */
282 h += utf8encode3((char *)h, vi + VB);
283
284 /* Add TPart if required, also a 3-byte UTF-8 sequence. */
285 if (ti)
286 h += utf8encode3((char *)h, ti + TB);
287
288 /* Terminate string. */
289 h[0] = '\0';
290
291 return hangul;
292}
293
294/*
295 * Use trie to scan s, touching at most len bytes.
296 * Returns the leaf if one exists, NULL otherwise.
297 *
298 * A non-NULL return guarantees that the UTF-8 sequence starting at s
299 * is well-formed and corresponds to a known unicode code point. The
300 * shorthand for this will be "is valid UTF-8 unicode".
301 */
302static utf8leaf_t *utf8nlookup(const struct unicode_map *um,
303 enum utf8_normalization n, unsigned char *hangul, const char *s,
304 size_t len)
305{
306 utf8trie_t *trie = um->tables->utf8data + um->ntab[n]->offset;
307 int offlen;
308 int offset;
309 int mask;
310 int node;
311
312 if (len == 0)
313 return NULL;
314
315 node = 1;
316 while (node) {
317 offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT;
318 if (*trie & NEXTBYTE) {
319 if (--len == 0)
320 return NULL;
321 s++;
322 }
323 mask = 1 << (*trie & BITNUM);
324 if (*s & mask) {
325 /* Right leg */
326 if (offlen) {
327 /* Right node at offset of trie */
328 node = (*trie & RIGHTNODE);
329 offset = trie[offlen];
330 while (--offlen) {
331 offset <<= 8;
332 offset |= trie[offlen];
333 }
334 trie += offset;
335 } else if (*trie & RIGHTPATH) {
336 /* Right node after this node */
337 node = (*trie & TRIENODE);
338 trie++;
339 } else {
340 /* No right node. */
341 return NULL;
342 }
343 } else {
344 /* Left leg */
345 if (offlen) {
346 /* Left node after this node. */
347 node = (*trie & LEFTNODE);
348 trie += offlen + 1;
349 } else if (*trie & RIGHTPATH) {
350 /* No left node. */
351 return NULL;
352 } else {
353 /* Left node after this node */
354 node = (*trie & TRIENODE);
355 trie++;
356 }
357 }
358 }
359 /*
360 * Hangul decomposition is done algorithmically. These are the
361 * codepoints >= 0xAC00 and <= 0xD7A3. Their UTF-8 encoding is
362 * always 3 bytes long, so s has been advanced twice, and the
363 * start of the sequence is at s-2.
364 */
365 if (LEAF_CCC(trie) == DECOMPOSE && LEAF_STR(trie)[0] == HANGUL)
366 trie = utf8hangul(s - 2, hangul);
367 return trie;
368}
369
370/*
371 * Use trie to scan s.
372 * Returns the leaf if one exists, NULL otherwise.
373 *
374 * Forwards to utf8nlookup().
375 */
376static utf8leaf_t *utf8lookup(const struct unicode_map *um,
377 enum utf8_normalization n, unsigned char *hangul, const char *s)
378{
379 return utf8nlookup(um, n, hangul, s, (size_t)-1);
380}
381
382/*
383 * Length of the normalization of s, touch at most len bytes.
384 * Return -1 if s is not valid UTF-8 unicode.
385 */
386ssize_t utf8nlen(const struct unicode_map *um, enum utf8_normalization n,
387 const char *s, size_t len)
388{
389 utf8leaf_t *leaf;
390 size_t ret = 0;
391 unsigned char hangul[UTF8HANGULLEAF];
392
393 while (len && *s) {
394 leaf = utf8nlookup(um, n, hangul, s, len);
395 if (!leaf)
396 return -1;
397 if (um->tables->utf8agetab[LEAF_GEN(leaf)] >
398 um->ntab[n]->maxage)
399 ret += utf8clen(s);
400 else if (LEAF_CCC(leaf) == DECOMPOSE)
401 ret += strlen(LEAF_STR(leaf));
402 else
403 ret += utf8clen(s);
404 len -= utf8clen(s);
405 s += utf8clen(s);
406 }
407 return ret;
408}
409
410/*
411 * Set up an utf8cursor for use by utf8byte().
412 *
413 * u8c : pointer to cursor.
414 * data : const struct utf8data to use for normalization.
415 * s : string.
416 * len : length of s.
417 *
418 * Returns -1 on error, 0 on success.
419 */
420int utf8ncursor(struct utf8cursor *u8c, const struct unicode_map *um,
421 enum utf8_normalization n, const char *s, size_t len)
422{
423 if (!s)
424 return -1;
425 u8c->um = um;
426 u8c->n = n;
427 u8c->s = s;
428 u8c->p = NULL;
429 u8c->ss = NULL;
430 u8c->sp = NULL;
431 u8c->len = len;
432 u8c->slen = 0;
433 u8c->ccc = STOPPER;
434 u8c->nccc = STOPPER;
435 /* Check we didn't clobber the maximum length. */
436 if (u8c->len != len)
437 return -1;
438 /* The first byte of s may not be an utf8 continuation. */
439 if (len > 0 && (*s & 0xC0) == 0x80)
440 return -1;
441 return 0;
442}
443
444/*
445 * Get one byte from the normalized form of the string described by u8c.
446 *
447 * Returns the byte cast to an unsigned char on succes, and -1 on failure.
448 *
449 * The cursor keeps track of the location in the string in u8c->s.
450 * When a character is decomposed, the current location is stored in
451 * u8c->p, and u8c->s is set to the start of the decomposition. Note
452 * that bytes from a decomposition do not count against u8c->len.
453 *
454 * Characters are emitted if they match the current CCC in u8c->ccc.
455 * Hitting end-of-string while u8c->ccc == STOPPER means we're done,
456 * and the function returns 0 in that case.
457 *
458 * Sorting by CCC is done by repeatedly scanning the string. The
459 * values of u8c->s and u8c->p are stored in u8c->ss and u8c->sp at
460 * the start of the scan. The first pass finds the lowest CCC to be
461 * emitted and stores it in u8c->nccc, the second pass emits the
462 * characters with this CCC and finds the next lowest CCC. This limits
463 * the number of passes to 1 + the number of different CCCs in the
464 * sequence being scanned.
465 *
466 * Therefore:
467 * u8c->p != NULL -> a decomposition is being scanned.
468 * u8c->ss != NULL -> this is a repeating scan.
469 * u8c->ccc == -1 -> this is the first scan of a repeating scan.
470 */
471int utf8byte(struct utf8cursor *u8c)
472{
473 utf8leaf_t *leaf;
474 int ccc;
475
476 for (;;) {
477 /* Check for the end of a decomposed character. */
478 if (u8c->p && *u8c->s == '\0') {
479 u8c->s = u8c->p;
480 u8c->p = NULL;
481 }
482
483 /* Check for end-of-string. */
484 if (!u8c->p && (u8c->len == 0 || *u8c->s == '\0')) {
485 /* There is no next byte. */
486 if (u8c->ccc == STOPPER)
487 return 0;
488 /* End-of-string during a scan counts as a stopper. */
489 ccc = STOPPER;
490 goto ccc_mismatch;
491 } else if ((*u8c->s & 0xC0) == 0x80) {
492 /* This is a continuation of the current character. */
493 if (!u8c->p)
494 u8c->len--;
495 return (unsigned char)*u8c->s++;
496 }
497
498 /* Look up the data for the current character. */
499 if (u8c->p) {
500 leaf = utf8lookup(u8c->um, u8c->n, u8c->hangul, u8c->s);
501 } else {
502 leaf = utf8nlookup(u8c->um, u8c->n, u8c->hangul,
503 u8c->s, u8c->len);
504 }
505
506 /* No leaf found implies that the input is a binary blob. */
507 if (!leaf)
508 return -1;
509
510 ccc = LEAF_CCC(leaf);
511 /* Characters that are too new have CCC 0. */
512 if (u8c->um->tables->utf8agetab[LEAF_GEN(leaf)] >
513 u8c->um->ntab[u8c->n]->maxage) {
514 ccc = STOPPER;
515 } else if (ccc == DECOMPOSE) {
516 u8c->len -= utf8clen(u8c->s);
517 u8c->p = u8c->s + utf8clen(u8c->s);
518 u8c->s = LEAF_STR(leaf);
519 /* Empty decomposition implies CCC 0. */
520 if (*u8c->s == '\0') {
521 if (u8c->ccc == STOPPER)
522 continue;
523 ccc = STOPPER;
524 goto ccc_mismatch;
525 }
526
527 leaf = utf8lookup(u8c->um, u8c->n, u8c->hangul, u8c->s);
528 if (!leaf)
529 return -1;
530 ccc = LEAF_CCC(leaf);
531 }
532
533 /*
534 * If this is not a stopper, then see if it updates
535 * the next canonical class to be emitted.
536 */
537 if (ccc != STOPPER && u8c->ccc < ccc && ccc < u8c->nccc)
538 u8c->nccc = ccc;
539
540 /*
541 * Return the current byte if this is the current
542 * combining class.
543 */
544 if (ccc == u8c->ccc) {
545 if (!u8c->p)
546 u8c->len--;
547 return (unsigned char)*u8c->s++;
548 }
549
550 /* Current combining class mismatch. */
551ccc_mismatch:
552 if (u8c->nccc == STOPPER) {
553 /*
554 * Scan forward for the first canonical class
555 * to be emitted. Save the position from
556 * which to restart.
557 */
558 u8c->ccc = MINCCC - 1;
559 u8c->nccc = ccc;
560 u8c->sp = u8c->p;
561 u8c->ss = u8c->s;
562 u8c->slen = u8c->len;
563 if (!u8c->p)
564 u8c->len -= utf8clen(u8c->s);
565 u8c->s += utf8clen(u8c->s);
566 } else if (ccc != STOPPER) {
567 /* Not a stopper, and not the ccc we're emitting. */
568 if (!u8c->p)
569 u8c->len -= utf8clen(u8c->s);
570 u8c->s += utf8clen(u8c->s);
571 } else if (u8c->nccc != MAXCCC + 1) {
572 /* At a stopper, restart for next ccc. */
573 u8c->ccc = u8c->nccc;
574 u8c->nccc = MAXCCC + 1;
575 u8c->s = u8c->ss;
576 u8c->p = u8c->sp;
577 u8c->len = u8c->slen;
578 } else {
579 /* All done, proceed from here. */
580 u8c->ccc = STOPPER;
581 u8c->nccc = STOPPER;
582 u8c->sp = NULL;
583 u8c->ss = NULL;
584 u8c->slen = 0;
585 }
586 }
587}
588
589#ifdef CONFIG_UNICODE_NORMALIZATION_SELFTEST_MODULE
590EXPORT_SYMBOL_GPL(utf8version_is_supported);
591EXPORT_SYMBOL_GPL(utf8nlen);
592EXPORT_SYMBOL_GPL(utf8ncursor);
593EXPORT_SYMBOL_GPL(utf8byte);
594#endif
1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright (c) 2014 SGI.
4 * All rights reserved.
5 */
6
7#include "utf8n.h"
8
9struct utf8data {
10 unsigned int maxage;
11 unsigned int offset;
12};
13
14#define __INCLUDED_FROM_UTF8NORM_C__
15#include "utf8data.h"
16#undef __INCLUDED_FROM_UTF8NORM_C__
17
18int utf8version_is_supported(u8 maj, u8 min, u8 rev)
19{
20 int i = ARRAY_SIZE(utf8agetab) - 1;
21 unsigned int sb_utf8version = UNICODE_AGE(maj, min, rev);
22
23 while (i >= 0 && utf8agetab[i] != 0) {
24 if (sb_utf8version == utf8agetab[i])
25 return 1;
26 i--;
27 }
28 return 0;
29}
30EXPORT_SYMBOL(utf8version_is_supported);
31
32int utf8version_latest(void)
33{
34 return utf8vers;
35}
36EXPORT_SYMBOL(utf8version_latest);
37
38/*
39 * UTF-8 valid ranges.
40 *
41 * The UTF-8 encoding spreads the bits of a 32bit word over several
42 * bytes. This table gives the ranges that can be held and how they'd
43 * be represented.
44 *
45 * 0x00000000 0x0000007F: 0xxxxxxx
46 * 0x00000000 0x000007FF: 110xxxxx 10xxxxxx
47 * 0x00000000 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx
48 * 0x00000000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
49 * 0x00000000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
50 * 0x00000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
51 *
52 * There is an additional requirement on UTF-8, in that only the
53 * shortest representation of a 32bit value is to be used. A decoder
54 * must not decode sequences that do not satisfy this requirement.
55 * Thus the allowed ranges have a lower bound.
56 *
57 * 0x00000000 0x0000007F: 0xxxxxxx
58 * 0x00000080 0x000007FF: 110xxxxx 10xxxxxx
59 * 0x00000800 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx
60 * 0x00010000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
61 * 0x00200000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
62 * 0x04000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
63 *
64 * Actual unicode characters are limited to the range 0x0 - 0x10FFFF,
65 * 17 planes of 65536 values. This limits the sequences actually seen
66 * even more, to just the following.
67 *
68 * 0 - 0x7F: 0 - 0x7F
69 * 0x80 - 0x7FF: 0xC2 0x80 - 0xDF 0xBF
70 * 0x800 - 0xFFFF: 0xE0 0xA0 0x80 - 0xEF 0xBF 0xBF
71 * 0x10000 - 0x10FFFF: 0xF0 0x90 0x80 0x80 - 0xF4 0x8F 0xBF 0xBF
72 *
73 * Within those ranges the surrogates 0xD800 - 0xDFFF are not allowed.
74 *
75 * Note that the longest sequence seen with valid usage is 4 bytes,
76 * the same a single UTF-32 character. This makes the UTF-8
77 * representation of Unicode strictly smaller than UTF-32.
78 *
79 * The shortest sequence requirement was introduced by:
80 * Corrigendum #1: UTF-8 Shortest Form
81 * It can be found here:
82 * http://www.unicode.org/versions/corrigendum1.html
83 *
84 */
85
86/*
87 * Return the number of bytes used by the current UTF-8 sequence.
88 * Assumes the input points to the first byte of a valid UTF-8
89 * sequence.
90 */
91static inline int utf8clen(const char *s)
92{
93 unsigned char c = *s;
94
95 return 1 + (c >= 0xC0) + (c >= 0xE0) + (c >= 0xF0);
96}
97
98/*
99 * Decode a 3-byte UTF-8 sequence.
100 */
101static unsigned int
102utf8decode3(const char *str)
103{
104 unsigned int uc;
105
106 uc = *str++ & 0x0F;
107 uc <<= 6;
108 uc |= *str++ & 0x3F;
109 uc <<= 6;
110 uc |= *str++ & 0x3F;
111
112 return uc;
113}
114
115/*
116 * Encode a 3-byte UTF-8 sequence.
117 */
118static int
119utf8encode3(char *str, unsigned int val)
120{
121 str[2] = (val & 0x3F) | 0x80;
122 val >>= 6;
123 str[1] = (val & 0x3F) | 0x80;
124 val >>= 6;
125 str[0] = val | 0xE0;
126
127 return 3;
128}
129
130/*
131 * utf8trie_t
132 *
133 * A compact binary tree, used to decode UTF-8 characters.
134 *
135 * Internal nodes are one byte for the node itself, and up to three
136 * bytes for an offset into the tree. The first byte contains the
137 * following information:
138 * NEXTBYTE - flag - advance to next byte if set
139 * BITNUM - 3 bit field - the bit number to tested
140 * OFFLEN - 2 bit field - number of bytes in the offset
141 * if offlen == 0 (non-branching node)
142 * RIGHTPATH - 1 bit field - set if the following node is for the
143 * right-hand path (tested bit is set)
144 * TRIENODE - 1 bit field - set if the following node is an internal
145 * node, otherwise it is a leaf node
146 * if offlen != 0 (branching node)
147 * LEFTNODE - 1 bit field - set if the left-hand node is internal
148 * RIGHTNODE - 1 bit field - set if the right-hand node is internal
149 *
150 * Due to the way utf8 works, there cannot be branching nodes with
151 * NEXTBYTE set, and moreover those nodes always have a righthand
152 * descendant.
153 */
154typedef const unsigned char utf8trie_t;
155#define BITNUM 0x07
156#define NEXTBYTE 0x08
157#define OFFLEN 0x30
158#define OFFLEN_SHIFT 4
159#define RIGHTPATH 0x40
160#define TRIENODE 0x80
161#define RIGHTNODE 0x40
162#define LEFTNODE 0x80
163
164/*
165 * utf8leaf_t
166 *
167 * The leaves of the trie are embedded in the trie, and so the same
168 * underlying datatype: unsigned char.
169 *
170 * leaf[0]: The unicode version, stored as a generation number that is
171 * an index into utf8agetab[]. With this we can filter code
172 * points based on the unicode version in which they were
173 * defined. The CCC of a non-defined code point is 0.
174 * leaf[1]: Canonical Combining Class. During normalization, we need
175 * to do a stable sort into ascending order of all characters
176 * with a non-zero CCC that occur between two characters with
177 * a CCC of 0, or at the begin or end of a string.
178 * The unicode standard guarantees that all CCC values are
179 * between 0 and 254 inclusive, which leaves 255 available as
180 * a special value.
181 * Code points with CCC 0 are known as stoppers.
182 * leaf[2]: Decomposition. If leaf[1] == 255, then leaf[2] is the
183 * start of a NUL-terminated string that is the decomposition
184 * of the character.
185 * The CCC of a decomposable character is the same as the CCC
186 * of the first character of its decomposition.
187 * Some characters decompose as the empty string: these are
188 * characters with the Default_Ignorable_Code_Point property.
189 * These do affect normalization, as they all have CCC 0.
190 *
191 * The decompositions in the trie have been fully expanded, with the
192 * exception of Hangul syllables, which are decomposed algorithmically.
193 *
194 * Casefolding, if applicable, is also done using decompositions.
195 *
196 * The trie is constructed in such a way that leaves exist for all
197 * UTF-8 sequences that match the criteria from the "UTF-8 valid
198 * ranges" comment above, and only for those sequences. Therefore a
199 * lookup in the trie can be used to validate the UTF-8 input.
200 */
201typedef const unsigned char utf8leaf_t;
202
203#define LEAF_GEN(LEAF) ((LEAF)[0])
204#define LEAF_CCC(LEAF) ((LEAF)[1])
205#define LEAF_STR(LEAF) ((const char *)((LEAF) + 2))
206
207#define MINCCC (0)
208#define MAXCCC (254)
209#define STOPPER (0)
210#define DECOMPOSE (255)
211
212/* Marker for hangul syllable decomposition. */
213#define HANGUL ((char)(255))
214/* Size of the synthesized leaf used for Hangul syllable decomposition. */
215#define UTF8HANGULLEAF (12)
216
217/*
218 * Hangul decomposition (algorithm from Section 3.12 of Unicode 6.3.0)
219 *
220 * AC00;<Hangul Syllable, First>;Lo;0;L;;;;;N;;;;;
221 * D7A3;<Hangul Syllable, Last>;Lo;0;L;;;;;N;;;;;
222 *
223 * SBase = 0xAC00
224 * LBase = 0x1100
225 * VBase = 0x1161
226 * TBase = 0x11A7
227 * LCount = 19
228 * VCount = 21
229 * TCount = 28
230 * NCount = 588 (VCount * TCount)
231 * SCount = 11172 (LCount * NCount)
232 *
233 * Decomposition:
234 * SIndex = s - SBase
235 *
236 * LV (Canonical/Full)
237 * LIndex = SIndex / NCount
238 * VIndex = (Sindex % NCount) / TCount
239 * LPart = LBase + LIndex
240 * VPart = VBase + VIndex
241 *
242 * LVT (Canonical)
243 * LVIndex = (SIndex / TCount) * TCount
244 * TIndex = (Sindex % TCount)
245 * LVPart = SBase + LVIndex
246 * TPart = TBase + TIndex
247 *
248 * LVT (Full)
249 * LIndex = SIndex / NCount
250 * VIndex = (Sindex % NCount) / TCount
251 * TIndex = (Sindex % TCount)
252 * LPart = LBase + LIndex
253 * VPart = VBase + VIndex
254 * if (TIndex == 0) {
255 * d = <LPart, VPart>
256 * } else {
257 * TPart = TBase + TIndex
258 * d = <LPart, TPart, VPart>
259 * }
260 */
261
262/* Constants */
263#define SB (0xAC00)
264#define LB (0x1100)
265#define VB (0x1161)
266#define TB (0x11A7)
267#define LC (19)
268#define VC (21)
269#define TC (28)
270#define NC (VC * TC)
271#define SC (LC * NC)
272
273/* Algorithmic decomposition of hangul syllable. */
274static utf8leaf_t *
275utf8hangul(const char *str, unsigned char *hangul)
276{
277 unsigned int si;
278 unsigned int li;
279 unsigned int vi;
280 unsigned int ti;
281 unsigned char *h;
282
283 /* Calculate the SI, LI, VI, and TI values. */
284 si = utf8decode3(str) - SB;
285 li = si / NC;
286 vi = (si % NC) / TC;
287 ti = si % TC;
288
289 /* Fill in base of leaf. */
290 h = hangul;
291 LEAF_GEN(h) = 2;
292 LEAF_CCC(h) = DECOMPOSE;
293 h += 2;
294
295 /* Add LPart, a 3-byte UTF-8 sequence. */
296 h += utf8encode3((char *)h, li + LB);
297
298 /* Add VPart, a 3-byte UTF-8 sequence. */
299 h += utf8encode3((char *)h, vi + VB);
300
301 /* Add TPart if required, also a 3-byte UTF-8 sequence. */
302 if (ti)
303 h += utf8encode3((char *)h, ti + TB);
304
305 /* Terminate string. */
306 h[0] = '\0';
307
308 return hangul;
309}
310
311/*
312 * Use trie to scan s, touching at most len bytes.
313 * Returns the leaf if one exists, NULL otherwise.
314 *
315 * A non-NULL return guarantees that the UTF-8 sequence starting at s
316 * is well-formed and corresponds to a known unicode code point. The
317 * shorthand for this will be "is valid UTF-8 unicode".
318 */
319static utf8leaf_t *utf8nlookup(const struct utf8data *data,
320 unsigned char *hangul, const char *s, size_t len)
321{
322 utf8trie_t *trie = NULL;
323 int offlen;
324 int offset;
325 int mask;
326 int node;
327
328 if (!data)
329 return NULL;
330 if (len == 0)
331 return NULL;
332
333 trie = utf8data + data->offset;
334 node = 1;
335 while (node) {
336 offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT;
337 if (*trie & NEXTBYTE) {
338 if (--len == 0)
339 return NULL;
340 s++;
341 }
342 mask = 1 << (*trie & BITNUM);
343 if (*s & mask) {
344 /* Right leg */
345 if (offlen) {
346 /* Right node at offset of trie */
347 node = (*trie & RIGHTNODE);
348 offset = trie[offlen];
349 while (--offlen) {
350 offset <<= 8;
351 offset |= trie[offlen];
352 }
353 trie += offset;
354 } else if (*trie & RIGHTPATH) {
355 /* Right node after this node */
356 node = (*trie & TRIENODE);
357 trie++;
358 } else {
359 /* No right node. */
360 return NULL;
361 }
362 } else {
363 /* Left leg */
364 if (offlen) {
365 /* Left node after this node. */
366 node = (*trie & LEFTNODE);
367 trie += offlen + 1;
368 } else if (*trie & RIGHTPATH) {
369 /* No left node. */
370 return NULL;
371 } else {
372 /* Left node after this node */
373 node = (*trie & TRIENODE);
374 trie++;
375 }
376 }
377 }
378 /*
379 * Hangul decomposition is done algorithmically. These are the
380 * codepoints >= 0xAC00 and <= 0xD7A3. Their UTF-8 encoding is
381 * always 3 bytes long, so s has been advanced twice, and the
382 * start of the sequence is at s-2.
383 */
384 if (LEAF_CCC(trie) == DECOMPOSE && LEAF_STR(trie)[0] == HANGUL)
385 trie = utf8hangul(s - 2, hangul);
386 return trie;
387}
388
389/*
390 * Use trie to scan s.
391 * Returns the leaf if one exists, NULL otherwise.
392 *
393 * Forwards to utf8nlookup().
394 */
395static utf8leaf_t *utf8lookup(const struct utf8data *data,
396 unsigned char *hangul, const char *s)
397{
398 return utf8nlookup(data, hangul, s, (size_t)-1);
399}
400
401/*
402 * Maximum age of any character in s.
403 * Return -1 if s is not valid UTF-8 unicode.
404 * Return 0 if only non-assigned code points are used.
405 */
406int utf8agemax(const struct utf8data *data, const char *s)
407{
408 utf8leaf_t *leaf;
409 int age = 0;
410 int leaf_age;
411 unsigned char hangul[UTF8HANGULLEAF];
412
413 if (!data)
414 return -1;
415
416 while (*s) {
417 leaf = utf8lookup(data, hangul, s);
418 if (!leaf)
419 return -1;
420
421 leaf_age = utf8agetab[LEAF_GEN(leaf)];
422 if (leaf_age <= data->maxage && leaf_age > age)
423 age = leaf_age;
424 s += utf8clen(s);
425 }
426 return age;
427}
428EXPORT_SYMBOL(utf8agemax);
429
430/*
431 * Minimum age of any character in s.
432 * Return -1 if s is not valid UTF-8 unicode.
433 * Return 0 if non-assigned code points are used.
434 */
435int utf8agemin(const struct utf8data *data, const char *s)
436{
437 utf8leaf_t *leaf;
438 int age;
439 int leaf_age;
440 unsigned char hangul[UTF8HANGULLEAF];
441
442 if (!data)
443 return -1;
444 age = data->maxage;
445 while (*s) {
446 leaf = utf8lookup(data, hangul, s);
447 if (!leaf)
448 return -1;
449 leaf_age = utf8agetab[LEAF_GEN(leaf)];
450 if (leaf_age <= data->maxage && leaf_age < age)
451 age = leaf_age;
452 s += utf8clen(s);
453 }
454 return age;
455}
456EXPORT_SYMBOL(utf8agemin);
457
458/*
459 * Maximum age of any character in s, touch at most len bytes.
460 * Return -1 if s is not valid UTF-8 unicode.
461 */
462int utf8nagemax(const struct utf8data *data, const char *s, size_t len)
463{
464 utf8leaf_t *leaf;
465 int age = 0;
466 int leaf_age;
467 unsigned char hangul[UTF8HANGULLEAF];
468
469 if (!data)
470 return -1;
471
472 while (len && *s) {
473 leaf = utf8nlookup(data, hangul, s, len);
474 if (!leaf)
475 return -1;
476 leaf_age = utf8agetab[LEAF_GEN(leaf)];
477 if (leaf_age <= data->maxage && leaf_age > age)
478 age = leaf_age;
479 len -= utf8clen(s);
480 s += utf8clen(s);
481 }
482 return age;
483}
484EXPORT_SYMBOL(utf8nagemax);
485
486/*
487 * Maximum age of any character in s, touch at most len bytes.
488 * Return -1 if s is not valid UTF-8 unicode.
489 */
490int utf8nagemin(const struct utf8data *data, const char *s, size_t len)
491{
492 utf8leaf_t *leaf;
493 int leaf_age;
494 int age;
495 unsigned char hangul[UTF8HANGULLEAF];
496
497 if (!data)
498 return -1;
499 age = data->maxage;
500 while (len && *s) {
501 leaf = utf8nlookup(data, hangul, s, len);
502 if (!leaf)
503 return -1;
504 leaf_age = utf8agetab[LEAF_GEN(leaf)];
505 if (leaf_age <= data->maxage && leaf_age < age)
506 age = leaf_age;
507 len -= utf8clen(s);
508 s += utf8clen(s);
509 }
510 return age;
511}
512EXPORT_SYMBOL(utf8nagemin);
513
514/*
515 * Length of the normalization of s.
516 * Return -1 if s is not valid UTF-8 unicode.
517 *
518 * A string of Default_Ignorable_Code_Point has length 0.
519 */
520ssize_t utf8len(const struct utf8data *data, const char *s)
521{
522 utf8leaf_t *leaf;
523 size_t ret = 0;
524 unsigned char hangul[UTF8HANGULLEAF];
525
526 if (!data)
527 return -1;
528 while (*s) {
529 leaf = utf8lookup(data, hangul, s);
530 if (!leaf)
531 return -1;
532 if (utf8agetab[LEAF_GEN(leaf)] > data->maxage)
533 ret += utf8clen(s);
534 else if (LEAF_CCC(leaf) == DECOMPOSE)
535 ret += strlen(LEAF_STR(leaf));
536 else
537 ret += utf8clen(s);
538 s += utf8clen(s);
539 }
540 return ret;
541}
542EXPORT_SYMBOL(utf8len);
543
544/*
545 * Length of the normalization of s, touch at most len bytes.
546 * Return -1 if s is not valid UTF-8 unicode.
547 */
548ssize_t utf8nlen(const struct utf8data *data, const char *s, size_t len)
549{
550 utf8leaf_t *leaf;
551 size_t ret = 0;
552 unsigned char hangul[UTF8HANGULLEAF];
553
554 if (!data)
555 return -1;
556 while (len && *s) {
557 leaf = utf8nlookup(data, hangul, s, len);
558 if (!leaf)
559 return -1;
560 if (utf8agetab[LEAF_GEN(leaf)] > data->maxage)
561 ret += utf8clen(s);
562 else if (LEAF_CCC(leaf) == DECOMPOSE)
563 ret += strlen(LEAF_STR(leaf));
564 else
565 ret += utf8clen(s);
566 len -= utf8clen(s);
567 s += utf8clen(s);
568 }
569 return ret;
570}
571EXPORT_SYMBOL(utf8nlen);
572
573/*
574 * Set up an utf8cursor for use by utf8byte().
575 *
576 * u8c : pointer to cursor.
577 * data : const struct utf8data to use for normalization.
578 * s : string.
579 * len : length of s.
580 *
581 * Returns -1 on error, 0 on success.
582 */
583int utf8ncursor(struct utf8cursor *u8c, const struct utf8data *data,
584 const char *s, size_t len)
585{
586 if (!data)
587 return -1;
588 if (!s)
589 return -1;
590 u8c->data = data;
591 u8c->s = s;
592 u8c->p = NULL;
593 u8c->ss = NULL;
594 u8c->sp = NULL;
595 u8c->len = len;
596 u8c->slen = 0;
597 u8c->ccc = STOPPER;
598 u8c->nccc = STOPPER;
599 /* Check we didn't clobber the maximum length. */
600 if (u8c->len != len)
601 return -1;
602 /* The first byte of s may not be an utf8 continuation. */
603 if (len > 0 && (*s & 0xC0) == 0x80)
604 return -1;
605 return 0;
606}
607EXPORT_SYMBOL(utf8ncursor);
608
609/*
610 * Set up an utf8cursor for use by utf8byte().
611 *
612 * u8c : pointer to cursor.
613 * data : const struct utf8data to use for normalization.
614 * s : NUL-terminated string.
615 *
616 * Returns -1 on error, 0 on success.
617 */
618int utf8cursor(struct utf8cursor *u8c, const struct utf8data *data,
619 const char *s)
620{
621 return utf8ncursor(u8c, data, s, (unsigned int)-1);
622}
623EXPORT_SYMBOL(utf8cursor);
624
625/*
626 * Get one byte from the normalized form of the string described by u8c.
627 *
628 * Returns the byte cast to an unsigned char on succes, and -1 on failure.
629 *
630 * The cursor keeps track of the location in the string in u8c->s.
631 * When a character is decomposed, the current location is stored in
632 * u8c->p, and u8c->s is set to the start of the decomposition. Note
633 * that bytes from a decomposition do not count against u8c->len.
634 *
635 * Characters are emitted if they match the current CCC in u8c->ccc.
636 * Hitting end-of-string while u8c->ccc == STOPPER means we're done,
637 * and the function returns 0 in that case.
638 *
639 * Sorting by CCC is done by repeatedly scanning the string. The
640 * values of u8c->s and u8c->p are stored in u8c->ss and u8c->sp at
641 * the start of the scan. The first pass finds the lowest CCC to be
642 * emitted and stores it in u8c->nccc, the second pass emits the
643 * characters with this CCC and finds the next lowest CCC. This limits
644 * the number of passes to 1 + the number of different CCCs in the
645 * sequence being scanned.
646 *
647 * Therefore:
648 * u8c->p != NULL -> a decomposition is being scanned.
649 * u8c->ss != NULL -> this is a repeating scan.
650 * u8c->ccc == -1 -> this is the first scan of a repeating scan.
651 */
652int utf8byte(struct utf8cursor *u8c)
653{
654 utf8leaf_t *leaf;
655 int ccc;
656
657 for (;;) {
658 /* Check for the end of a decomposed character. */
659 if (u8c->p && *u8c->s == '\0') {
660 u8c->s = u8c->p;
661 u8c->p = NULL;
662 }
663
664 /* Check for end-of-string. */
665 if (!u8c->p && (u8c->len == 0 || *u8c->s == '\0')) {
666 /* There is no next byte. */
667 if (u8c->ccc == STOPPER)
668 return 0;
669 /* End-of-string during a scan counts as a stopper. */
670 ccc = STOPPER;
671 goto ccc_mismatch;
672 } else if ((*u8c->s & 0xC0) == 0x80) {
673 /* This is a continuation of the current character. */
674 if (!u8c->p)
675 u8c->len--;
676 return (unsigned char)*u8c->s++;
677 }
678
679 /* Look up the data for the current character. */
680 if (u8c->p) {
681 leaf = utf8lookup(u8c->data, u8c->hangul, u8c->s);
682 } else {
683 leaf = utf8nlookup(u8c->data, u8c->hangul,
684 u8c->s, u8c->len);
685 }
686
687 /* No leaf found implies that the input is a binary blob. */
688 if (!leaf)
689 return -1;
690
691 ccc = LEAF_CCC(leaf);
692 /* Characters that are too new have CCC 0. */
693 if (utf8agetab[LEAF_GEN(leaf)] > u8c->data->maxage) {
694 ccc = STOPPER;
695 } else if (ccc == DECOMPOSE) {
696 u8c->len -= utf8clen(u8c->s);
697 u8c->p = u8c->s + utf8clen(u8c->s);
698 u8c->s = LEAF_STR(leaf);
699 /* Empty decomposition implies CCC 0. */
700 if (*u8c->s == '\0') {
701 if (u8c->ccc == STOPPER)
702 continue;
703 ccc = STOPPER;
704 goto ccc_mismatch;
705 }
706
707 leaf = utf8lookup(u8c->data, u8c->hangul, u8c->s);
708 if (!leaf)
709 return -1;
710 ccc = LEAF_CCC(leaf);
711 }
712
713 /*
714 * If this is not a stopper, then see if it updates
715 * the next canonical class to be emitted.
716 */
717 if (ccc != STOPPER && u8c->ccc < ccc && ccc < u8c->nccc)
718 u8c->nccc = ccc;
719
720 /*
721 * Return the current byte if this is the current
722 * combining class.
723 */
724 if (ccc == u8c->ccc) {
725 if (!u8c->p)
726 u8c->len--;
727 return (unsigned char)*u8c->s++;
728 }
729
730 /* Current combining class mismatch. */
731ccc_mismatch:
732 if (u8c->nccc == STOPPER) {
733 /*
734 * Scan forward for the first canonical class
735 * to be emitted. Save the position from
736 * which to restart.
737 */
738 u8c->ccc = MINCCC - 1;
739 u8c->nccc = ccc;
740 u8c->sp = u8c->p;
741 u8c->ss = u8c->s;
742 u8c->slen = u8c->len;
743 if (!u8c->p)
744 u8c->len -= utf8clen(u8c->s);
745 u8c->s += utf8clen(u8c->s);
746 } else if (ccc != STOPPER) {
747 /* Not a stopper, and not the ccc we're emitting. */
748 if (!u8c->p)
749 u8c->len -= utf8clen(u8c->s);
750 u8c->s += utf8clen(u8c->s);
751 } else if (u8c->nccc != MAXCCC + 1) {
752 /* At a stopper, restart for next ccc. */
753 u8c->ccc = u8c->nccc;
754 u8c->nccc = MAXCCC + 1;
755 u8c->s = u8c->ss;
756 u8c->p = u8c->sp;
757 u8c->len = u8c->slen;
758 } else {
759 /* All done, proceed from here. */
760 u8c->ccc = STOPPER;
761 u8c->nccc = STOPPER;
762 u8c->sp = NULL;
763 u8c->ss = NULL;
764 u8c->slen = 0;
765 }
766 }
767}
768EXPORT_SYMBOL(utf8byte);
769
770const struct utf8data *utf8nfdi(unsigned int maxage)
771{
772 int i = ARRAY_SIZE(utf8nfdidata) - 1;
773
774 while (maxage < utf8nfdidata[i].maxage)
775 i--;
776 if (maxage > utf8nfdidata[i].maxage)
777 return NULL;
778 return &utf8nfdidata[i];
779}
780EXPORT_SYMBOL(utf8nfdi);
781
782const struct utf8data *utf8nfdicf(unsigned int maxage)
783{
784 int i = ARRAY_SIZE(utf8nfdicfdata) - 1;
785
786 while (maxage < utf8nfdicfdata[i].maxage)
787 i--;
788 if (maxage > utf8nfdicfdata[i].maxage)
789 return NULL;
790 return &utf8nfdicfdata[i];
791}
792EXPORT_SYMBOL(utf8nfdicf);