2 * Copyright (c) 2014 SGI.
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.
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
23 #define __INCLUDED_FROM_UTF8NORM_C__
25 #undef __INCLUDED_FROM_UTF8NORM_C__
27 int utf8version_is_supported(u8 maj, u8 min, u8 rev)
29 int i = ARRAY_SIZE(utf8agetab) - 1;
30 unsigned int sb_utf8version = UNICODE_AGE(maj, min, rev);
32 while (i >= 0 && utf8agetab[i] != 0) {
33 if (sb_utf8version == utf8agetab[i])
39 EXPORT_SYMBOL(utf8version_is_supported);
41 int utf8version_latest(void)
45 EXPORT_SYMBOL(utf8version_latest);
50 * The UTF-8 encoding spreads the bits of a 32bit word over several
51 * bytes. This table gives the ranges that can be held and how they'd
54 * 0x00000000 0x0000007F: 0xxxxxxx
55 * 0x00000000 0x000007FF: 110xxxxx 10xxxxxx
56 * 0x00000000 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx
57 * 0x00000000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
58 * 0x00000000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
59 * 0x00000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
61 * There is an additional requirement on UTF-8, in that only the
62 * shortest representation of a 32bit value is to be used. A decoder
63 * must not decode sequences that do not satisfy this requirement.
64 * Thus the allowed ranges have a lower bound.
66 * 0x00000000 0x0000007F: 0xxxxxxx
67 * 0x00000080 0x000007FF: 110xxxxx 10xxxxxx
68 * 0x00000800 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx
69 * 0x00010000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
70 * 0x00200000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
71 * 0x04000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
73 * Actual unicode characters are limited to the range 0x0 - 0x10FFFF,
74 * 17 planes of 65536 values. This limits the sequences actually seen
75 * even more, to just the following.
78 * 0x80 - 0x7FF: 0xC2 0x80 - 0xDF 0xBF
79 * 0x800 - 0xFFFF: 0xE0 0xA0 0x80 - 0xEF 0xBF 0xBF
80 * 0x10000 - 0x10FFFF: 0xF0 0x90 0x80 0x80 - 0xF4 0x8F 0xBF 0xBF
82 * Within those ranges the surrogates 0xD800 - 0xDFFF are not allowed.
84 * Note that the longest sequence seen with valid usage is 4 bytes,
85 * the same a single UTF-32 character. This makes the UTF-8
86 * representation of Unicode strictly smaller than UTF-32.
88 * The shortest sequence requirement was introduced by:
89 * Corrigendum #1: UTF-8 Shortest Form
90 * It can be found here:
91 * http://www.unicode.org/versions/corrigendum1.html
96 * Return the number of bytes used by the current UTF-8 sequence.
97 * Assumes the input points to the first byte of a valid UTF-8
100 static inline int utf8clen(const char *s)
102 unsigned char c = *s;
104 return 1 + (c >= 0xC0) + (c >= 0xE0) + (c >= 0xF0);
108 * Decode a 3-byte UTF-8 sequence.
111 utf8decode3(const char *str)
125 * Encode a 3-byte UTF-8 sequence.
128 utf8encode3(char *str, unsigned int val)
130 str[2] = (val & 0x3F) | 0x80;
132 str[1] = (val & 0x3F) | 0x80;
142 * A compact binary tree, used to decode UTF-8 characters.
144 * Internal nodes are one byte for the node itself, and up to three
145 * bytes for an offset into the tree. The first byte contains the
146 * following information:
147 * NEXTBYTE - flag - advance to next byte if set
148 * BITNUM - 3 bit field - the bit number to tested
149 * OFFLEN - 2 bit field - number of bytes in the offset
150 * if offlen == 0 (non-branching node)
151 * RIGHTPATH - 1 bit field - set if the following node is for the
152 * right-hand path (tested bit is set)
153 * TRIENODE - 1 bit field - set if the following node is an internal
154 * node, otherwise it is a leaf node
155 * if offlen != 0 (branching node)
156 * LEFTNODE - 1 bit field - set if the left-hand node is internal
157 * RIGHTNODE - 1 bit field - set if the right-hand node is internal
159 * Due to the way utf8 works, there cannot be branching nodes with
160 * NEXTBYTE set, and moreover those nodes always have a righthand
163 typedef const unsigned char utf8trie_t;
165 #define NEXTBYTE 0x08
167 #define OFFLEN_SHIFT 4
168 #define RIGHTPATH 0x40
169 #define TRIENODE 0x80
170 #define RIGHTNODE 0x40
171 #define LEFTNODE 0x80
176 * The leaves of the trie are embedded in the trie, and so the same
177 * underlying datatype: unsigned char.
179 * leaf[0]: The unicode version, stored as a generation number that is
180 * an index into utf8agetab[]. With this we can filter code
181 * points based on the unicode version in which they were
182 * defined. The CCC of a non-defined code point is 0.
183 * leaf[1]: Canonical Combining Class. During normalization, we need
184 * to do a stable sort into ascending order of all characters
185 * with a non-zero CCC that occur between two characters with
186 * a CCC of 0, or at the begin or end of a string.
187 * The unicode standard guarantees that all CCC values are
188 * between 0 and 254 inclusive, which leaves 255 available as
190 * Code points with CCC 0 are known as stoppers.
191 * leaf[2]: Decomposition. If leaf[1] == 255, then leaf[2] is the
192 * start of a NUL-terminated string that is the decomposition
194 * The CCC of a decomposable character is the same as the CCC
195 * of the first character of its decomposition.
196 * Some characters decompose as the empty string: these are
197 * characters with the Default_Ignorable_Code_Point property.
198 * These do affect normalization, as they all have CCC 0.
200 * The decompositions in the trie have been fully expanded, with the
201 * exception of Hangul syllables, which are decomposed algorithmically.
203 * Casefolding, if applicable, is also done using decompositions.
205 * The trie is constructed in such a way that leaves exist for all
206 * UTF-8 sequences that match the criteria from the "UTF-8 valid
207 * ranges" comment above, and only for those sequences. Therefore a
208 * lookup in the trie can be used to validate the UTF-8 input.
210 typedef const unsigned char utf8leaf_t;
212 #define LEAF_GEN(LEAF) ((LEAF)[0])
213 #define LEAF_CCC(LEAF) ((LEAF)[1])
214 #define LEAF_STR(LEAF) ((const char *)((LEAF) + 2))
219 #define DECOMPOSE (255)
221 /* Marker for hangul syllable decomposition. */
222 #define HANGUL ((char)(255))
223 /* Size of the synthesized leaf used for Hangul syllable decomposition. */
224 #define UTF8HANGULLEAF (12)
227 * Hangul decomposition (algorithm from Section 3.12 of Unicode 6.3.0)
229 * AC00;<Hangul Syllable, First>;Lo;0;L;;;;;N;;;;;
230 * D7A3;<Hangul Syllable, Last>;Lo;0;L;;;;;N;;;;;
239 * NCount = 588 (VCount * TCount)
240 * SCount = 11172 (LCount * NCount)
245 * LV (Canonical/Full)
246 * LIndex = SIndex / NCount
247 * VIndex = (Sindex % NCount) / TCount
248 * LPart = LBase + LIndex
249 * VPart = VBase + VIndex
252 * LVIndex = (SIndex / TCount) * TCount
253 * TIndex = (Sindex % TCount)
254 * LVPart = SBase + LVIndex
255 * TPart = TBase + TIndex
258 * LIndex = SIndex / NCount
259 * VIndex = (Sindex % NCount) / TCount
260 * TIndex = (Sindex % TCount)
261 * LPart = LBase + LIndex
262 * VPart = VBase + VIndex
266 * TPart = TBase + TIndex
267 * d = <LPart, TPart, VPart>
282 /* Algorithmic decomposition of hangul syllable. */
284 utf8hangul(const char *str, unsigned char *hangul)
292 /* Calculate the SI, LI, VI, and TI values. */
293 si = utf8decode3(str) - SB;
298 /* Fill in base of leaf. */
301 LEAF_CCC(h) = DECOMPOSE;
304 /* Add LPart, a 3-byte UTF-8 sequence. */
305 h += utf8encode3((char *)h, li + LB);
307 /* Add VPart, a 3-byte UTF-8 sequence. */
308 h += utf8encode3((char *)h, vi + VB);
310 /* Add TPart if required, also a 3-byte UTF-8 sequence. */
312 h += utf8encode3((char *)h, ti + TB);
314 /* Terminate string. */
321 * Use trie to scan s, touching at most len bytes.
322 * Returns the leaf if one exists, NULL otherwise.
324 * A non-NULL return guarantees that the UTF-8 sequence starting at s
325 * is well-formed and corresponds to a known unicode code point. The
326 * shorthand for this will be "is valid UTF-8 unicode".
328 static utf8leaf_t *utf8nlookup(const struct utf8data *data,
329 unsigned char *hangul, const char *s, size_t len)
331 utf8trie_t *trie = NULL;
342 trie = utf8data + data->offset;
345 offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT;
346 if (*trie & NEXTBYTE) {
351 mask = 1 << (*trie & BITNUM);
355 /* Right node at offset of trie */
356 node = (*trie & RIGHTNODE);
357 offset = trie[offlen];
360 offset |= trie[offlen];
363 } else if (*trie & RIGHTPATH) {
364 /* Right node after this node */
365 node = (*trie & TRIENODE);
374 /* Left node after this node. */
375 node = (*trie & LEFTNODE);
377 } else if (*trie & RIGHTPATH) {
381 /* Left node after this node */
382 node = (*trie & TRIENODE);
388 * Hangul decomposition is done algorithmically. These are the
389 * codepoints >= 0xAC00 and <= 0xD7A3. Their UTF-8 encoding is
390 * always 3 bytes long, so s has been advanced twice, and the
391 * start of the sequence is at s-2.
393 if (LEAF_CCC(trie) == DECOMPOSE && LEAF_STR(trie)[0] == HANGUL)
394 trie = utf8hangul(s - 2, hangul);
399 * Use trie to scan s.
400 * Returns the leaf if one exists, NULL otherwise.
402 * Forwards to utf8nlookup().
404 static utf8leaf_t *utf8lookup(const struct utf8data *data,
405 unsigned char *hangul, const char *s)
407 return utf8nlookup(data, hangul, s, (size_t)-1);
411 * Maximum age of any character in s.
412 * Return -1 if s is not valid UTF-8 unicode.
413 * Return 0 if only non-assigned code points are used.
415 int utf8agemax(const struct utf8data *data, const char *s)
420 unsigned char hangul[UTF8HANGULLEAF];
426 leaf = utf8lookup(data, hangul, s);
430 leaf_age = utf8agetab[LEAF_GEN(leaf)];
431 if (leaf_age <= data->maxage && leaf_age > age)
437 EXPORT_SYMBOL(utf8agemax);
440 * Minimum age of any character in s.
441 * Return -1 if s is not valid UTF-8 unicode.
442 * Return 0 if non-assigned code points are used.
444 int utf8agemin(const struct utf8data *data, const char *s)
449 unsigned char hangul[UTF8HANGULLEAF];
455 leaf = utf8lookup(data, hangul, s);
458 leaf_age = utf8agetab[LEAF_GEN(leaf)];
459 if (leaf_age <= data->maxage && leaf_age < age)
465 EXPORT_SYMBOL(utf8agemin);
468 * Maximum age of any character in s, touch at most len bytes.
469 * Return -1 if s is not valid UTF-8 unicode.
471 int utf8nagemax(const struct utf8data *data, const char *s, size_t len)
476 unsigned char hangul[UTF8HANGULLEAF];
482 leaf = utf8nlookup(data, hangul, s, len);
485 leaf_age = utf8agetab[LEAF_GEN(leaf)];
486 if (leaf_age <= data->maxage && leaf_age > age)
493 EXPORT_SYMBOL(utf8nagemax);
496 * Maximum age of any character in s, touch at most len bytes.
497 * Return -1 if s is not valid UTF-8 unicode.
499 int utf8nagemin(const struct utf8data *data, const char *s, size_t len)
504 unsigned char hangul[UTF8HANGULLEAF];
510 leaf = utf8nlookup(data, hangul, s, len);
513 leaf_age = utf8agetab[LEAF_GEN(leaf)];
514 if (leaf_age <= data->maxage && leaf_age < age)
521 EXPORT_SYMBOL(utf8nagemin);
524 * Length of the normalization of s.
525 * Return -1 if s is not valid UTF-8 unicode.
527 * A string of Default_Ignorable_Code_Point has length 0.
529 ssize_t utf8len(const struct utf8data *data, const char *s)
533 unsigned char hangul[UTF8HANGULLEAF];
538 leaf = utf8lookup(data, hangul, s);
541 if (utf8agetab[LEAF_GEN(leaf)] > data->maxage)
543 else if (LEAF_CCC(leaf) == DECOMPOSE)
544 ret += strlen(LEAF_STR(leaf));
551 EXPORT_SYMBOL(utf8len);
554 * Length of the normalization of s, touch at most len bytes.
555 * Return -1 if s is not valid UTF-8 unicode.
557 ssize_t utf8nlen(const struct utf8data *data, const char *s, size_t len)
561 unsigned char hangul[UTF8HANGULLEAF];
566 leaf = utf8nlookup(data, hangul, s, len);
569 if (utf8agetab[LEAF_GEN(leaf)] > data->maxage)
571 else if (LEAF_CCC(leaf) == DECOMPOSE)
572 ret += strlen(LEAF_STR(leaf));
580 EXPORT_SYMBOL(utf8nlen);
583 * Set up an utf8cursor for use by utf8byte().
585 * u8c : pointer to cursor.
586 * data : const struct utf8data to use for normalization.
590 * Returns -1 on error, 0 on success.
592 int utf8ncursor(struct utf8cursor *u8c, const struct utf8data *data,
593 const char *s, size_t len)
608 /* Check we didn't clobber the maximum length. */
611 /* The first byte of s may not be an utf8 continuation. */
612 if (len > 0 && (*s & 0xC0) == 0x80)
616 EXPORT_SYMBOL(utf8ncursor);
619 * Set up an utf8cursor for use by utf8byte().
621 * u8c : pointer to cursor.
622 * data : const struct utf8data to use for normalization.
623 * s : NUL-terminated string.
625 * Returns -1 on error, 0 on success.
627 int utf8cursor(struct utf8cursor *u8c, const struct utf8data *data,
630 return utf8ncursor(u8c, data, s, (unsigned int)-1);
632 EXPORT_SYMBOL(utf8cursor);
635 * Get one byte from the normalized form of the string described by u8c.
637 * Returns the byte cast to an unsigned char on succes, and -1 on failure.
639 * The cursor keeps track of the location in the string in u8c->s.
640 * When a character is decomposed, the current location is stored in
641 * u8c->p, and u8c->s is set to the start of the decomposition. Note
642 * that bytes from a decomposition do not count against u8c->len.
644 * Characters are emitted if they match the current CCC in u8c->ccc.
645 * Hitting end-of-string while u8c->ccc == STOPPER means we're done,
646 * and the function returns 0 in that case.
648 * Sorting by CCC is done by repeatedly scanning the string. The
649 * values of u8c->s and u8c->p are stored in u8c->ss and u8c->sp at
650 * the start of the scan. The first pass finds the lowest CCC to be
651 * emitted and stores it in u8c->nccc, the second pass emits the
652 * characters with this CCC and finds the next lowest CCC. This limits
653 * the number of passes to 1 + the number of different CCCs in the
654 * sequence being scanned.
657 * u8c->p != NULL -> a decomposition is being scanned.
658 * u8c->ss != NULL -> this is a repeating scan.
659 * u8c->ccc == -1 -> this is the first scan of a repeating scan.
661 int utf8byte(struct utf8cursor *u8c)
667 /* Check for the end of a decomposed character. */
668 if (u8c->p && *u8c->s == '\0') {
673 /* Check for end-of-string. */
674 if (!u8c->p && (u8c->len == 0 || *u8c->s == '\0')) {
675 /* There is no next byte. */
676 if (u8c->ccc == STOPPER)
678 /* End-of-string during a scan counts as a stopper. */
681 } else if ((*u8c->s & 0xC0) == 0x80) {
682 /* This is a continuation of the current character. */
685 return (unsigned char)*u8c->s++;
688 /* Look up the data for the current character. */
690 leaf = utf8lookup(u8c->data, u8c->hangul, u8c->s);
692 leaf = utf8nlookup(u8c->data, u8c->hangul,
696 /* No leaf found implies that the input is a binary blob. */
700 ccc = LEAF_CCC(leaf);
701 /* Characters that are too new have CCC 0. */
702 if (utf8agetab[LEAF_GEN(leaf)] > u8c->data->maxage) {
704 } else if (ccc == DECOMPOSE) {
705 u8c->len -= utf8clen(u8c->s);
706 u8c->p = u8c->s + utf8clen(u8c->s);
707 u8c->s = LEAF_STR(leaf);
708 /* Empty decomposition implies CCC 0. */
709 if (*u8c->s == '\0') {
710 if (u8c->ccc == STOPPER)
716 leaf = utf8lookup(u8c->data, u8c->hangul, u8c->s);
717 ccc = LEAF_CCC(leaf);
721 * If this is not a stopper, then see if it updates
722 * the next canonical class to be emitted.
724 if (ccc != STOPPER && u8c->ccc < ccc && ccc < u8c->nccc)
728 * Return the current byte if this is the current
731 if (ccc == u8c->ccc) {
734 return (unsigned char)*u8c->s++;
737 /* Current combining class mismatch. */
739 if (u8c->nccc == STOPPER) {
741 * Scan forward for the first canonical class
742 * to be emitted. Save the position from
745 u8c->ccc = MINCCC - 1;
749 u8c->slen = u8c->len;
751 u8c->len -= utf8clen(u8c->s);
752 u8c->s += utf8clen(u8c->s);
753 } else if (ccc != STOPPER) {
754 /* Not a stopper, and not the ccc we're emitting. */
756 u8c->len -= utf8clen(u8c->s);
757 u8c->s += utf8clen(u8c->s);
758 } else if (u8c->nccc != MAXCCC + 1) {
759 /* At a stopper, restart for next ccc. */
760 u8c->ccc = u8c->nccc;
761 u8c->nccc = MAXCCC + 1;
764 u8c->len = u8c->slen;
766 /* All done, proceed from here. */
775 EXPORT_SYMBOL(utf8byte);
777 const struct utf8data *utf8nfdi(unsigned int maxage)
779 int i = ARRAY_SIZE(utf8nfdidata) - 1;
781 while (maxage < utf8nfdidata[i].maxage)
783 if (maxage > utf8nfdidata[i].maxage)
785 return &utf8nfdidata[i];
787 EXPORT_SYMBOL(utf8nfdi);
789 const struct utf8data *utf8nfdicf(unsigned int maxage)
791 int i = ARRAY_SIZE(utf8nfdicfdata) - 1;
793 while (maxage < utf8nfdicfdata[i].maxage)
795 if (maxage > utf8nfdicfdata[i].maxage)
797 return &utf8nfdicfdata[i];
799 EXPORT_SYMBOL(utf8nfdicf);