fs/unicode/utf8-norm.c

   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
   9 int 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  */
  74 static 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  */
  84 static unsigned int
  85 utf8decode3(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  */
 101 static int
 102 utf8encode3(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  */
 137 typedef 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  */
 184 typedef 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. */
 257 static utf8leaf_t *
 258 utf8hangul(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  */
 302 static 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  */
 376 static 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  */
 386 ssize_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  */
 420 int 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  */
 471 int 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. */
 551 ccc_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
 590 EXPORT_SYMBOL_GPL(utf8version_is_supported);
 591 EXPORT_SYMBOL_GPL(utf8nlen);
 592 EXPORT_SYMBOL_GPL(utf8ncursor);
 593 EXPORT_SYMBOL_GPL(utf8byte);
 594 #endif