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