utf8-norm.c 20 KB

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