595 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*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 several25 * bytes. This table gives the ranges that can be held and how they'd26 * be represented.27 *28 * 0x00000000 0x0000007F: 0xxxxxxx29 * 0x00000000 0x000007FF: 110xxxxx 10xxxxxx30 * 0x00000000 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx31 * 0x00000000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx32 * 0x00000000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx33 * 0x00000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx34 *35 * There is an additional requirement on UTF-8, in that only the36 * shortest representation of a 32bit value is to be used. A decoder37 * must not decode sequences that do not satisfy this requirement.38 * Thus the allowed ranges have a lower bound.39 *40 * 0x00000000 0x0000007F: 0xxxxxxx41 * 0x00000080 0x000007FF: 110xxxxx 10xxxxxx42 * 0x00000800 0x0000FFFF: 1110xxxx 10xxxxxx 10xxxxxx43 * 0x00010000 0x001FFFFF: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx44 * 0x00200000 0x03FFFFFF: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx45 * 0x04000000 0x7FFFFFFF: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx46 *47 * Actual unicode characters are limited to the range 0x0 - 0x10FFFF,48 * 17 planes of 65536 values. This limits the sequences actually seen49 * even more, to just the following.50 *51 * 0 - 0x7F: 0 - 0x7F52 * 0x80 - 0x7FF: 0xC2 0x80 - 0xDF 0xBF53 * 0x800 - 0xFFFF: 0xE0 0xA0 0x80 - 0xEF 0xBF 0xBF54 * 0x10000 - 0x10FFFF: 0xF0 0x90 0x80 0x80 - 0xF4 0x8F 0xBF 0xBF55 *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-860 * representation of Unicode strictly smaller than UTF-32.61 *62 * The shortest sequence requirement was introduced by:63 * Corrigendum #1: UTF-8 Shortest Form64 * It can be found here:65 * http://www.unicode.org/versions/corrigendum1.html66 *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-872 * 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 int85utf8decode3(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 int102utf8encode3(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_t115 *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 three119 * bytes for an offset into the tree. The first byte contains the120 * following information:121 * NEXTBYTE - flag - advance to next byte if set122 * BITNUM - 3 bit field - the bit number to tested123 * OFFLEN - 2 bit field - number of bytes in the offset124 * if offlen == 0 (non-branching node)125 * RIGHTPATH - 1 bit field - set if the following node is for the126 * right-hand path (tested bit is set)127 * TRIENODE - 1 bit field - set if the following node is an internal128 * node, otherwise it is a leaf node129 * if offlen != 0 (branching node)130 * LEFTNODE - 1 bit field - set if the left-hand node is internal131 * RIGHTNODE - 1 bit field - set if the right-hand node is internal132 *133 * Due to the way utf8 works, there cannot be branching nodes with134 * NEXTBYTE set, and moreover those nodes always have a righthand135 * descendant.136 */137typedef const unsigned char utf8trie_t;138#define BITNUM 0x07139#define NEXTBYTE 0x08140#define OFFLEN 0x30141#define OFFLEN_SHIFT 4142#define RIGHTPATH 0x40143#define TRIENODE 0x80144#define RIGHTNODE 0x40145#define LEFTNODE 0x80146 147/*148 * utf8leaf_t149 *150 * The leaves of the trie are embedded in the trie, and so the same151 * underlying datatype: unsigned char.152 *153 * leaf[0]: The unicode version, stored as a generation number that is154 * an index into ->utf8agetab[]. With this we can filter code155 * points based on the unicode version in which they were156 * defined. The CCC of a non-defined code point is 0.157 * leaf[1]: Canonical Combining Class. During normalization, we need158 * to do a stable sort into ascending order of all characters159 * with a non-zero CCC that occur between two characters with160 * a CCC of 0, or at the begin or end of a string.161 * The unicode standard guarantees that all CCC values are162 * between 0 and 254 inclusive, which leaves 255 available as163 * 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 the166 * start of a NUL-terminated string that is the decomposition167 * of the character.168 * The CCC of a decomposable character is the same as the CCC169 * of the first character of its decomposition.170 * Some characters decompose as the empty string: these are171 * 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 the175 * 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 all180 * UTF-8 sequences that match the criteria from the "UTF-8 valid181 * ranges" comment above, and only for those sequences. Therefore a182 * 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 = 0xAC00207 * LBase = 0x1100208 * VBase = 0x1161209 * TBase = 0x11A7210 * LCount = 19211 * VCount = 21212 * TCount = 28213 * NCount = 588 (VCount * TCount)214 * SCount = 11172 (LCount * NCount)215 *216 * Decomposition:217 * SIndex = s - SBase218 *219 * LV (Canonical/Full)220 * LIndex = SIndex / NCount221 * VIndex = (Sindex % NCount) / TCount222 * LPart = LBase + LIndex223 * VPart = VBase + VIndex224 *225 * LVT (Canonical)226 * LVIndex = (SIndex / TCount) * TCount227 * TIndex = (Sindex % TCount)228 * LVPart = SBase + LVIndex229 * TPart = TBase + TIndex230 *231 * LVT (Full)232 * LIndex = SIndex / NCount233 * VIndex = (Sindex % NCount) / TCount234 * TIndex = (Sindex % TCount)235 * LPart = LBase + LIndex236 * VPart = VBase + VIndex237 * if (TIndex == 0) {238 * d = <LPart, VPart>239 * } else {240 * TPart = TBase + TIndex241 * 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 s299 * is well-formed and corresponds to a known unicode code point. The300 * 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 the361 * codepoints >= 0xAC00 and <= 0xD7A3. Their UTF-8 encoding is362 * always 3 bytes long, so s has been advanced twice, and the363 * 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 else403 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 in451 * u8c->p, and u8c->s is set to the start of the decomposition. Note452 * 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. The459 * values of u8c->s and u8c->p are stored in u8c->ss and u8c->sp at460 * the start of the scan. The first pass finds the lowest CCC to be461 * emitted and stores it in u8c->nccc, the second pass emits the462 * characters with this CCC and finds the next lowest CCC. This limits463 * the number of passes to 1 + the number of different CCCs in the464 * 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 updates535 * 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 current542 * 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 class555 * to be emitted. Save the position from556 * 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_MODULE590EXPORT_SYMBOL_GPL(utf8version_is_supported);591EXPORT_SYMBOL_GPL(utf8nlen);592EXPORT_SYMBOL_GPL(utf8ncursor);593EXPORT_SYMBOL_GPL(utf8byte);594#endif595