unicode.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * linux/fs/hfsplus/unicode.c
  4. *
  5. * Copyright (C) 2001
  6. * Brad Boyer (flar@allandria.com)
  7. * (C) 2003 Ardis Technologies <roman@ardistech.com>
  8. *
  9. * Handler routines for unicode strings
  10. */
  11. #include <linux/types.h>
  12. #include <linux/nls.h>
  13. #include "hfsplus_fs.h"
  14. #include "hfsplus_raw.h"
  15. /* Fold the case of a unicode char, given the 16 bit value */
  16. /* Returns folded char, or 0 if ignorable */
  17. static inline u16 case_fold(u16 c)
  18. {
  19. u16 tmp;
  20. tmp = hfsplus_case_fold_table[c >> 8];
  21. if (tmp)
  22. tmp = hfsplus_case_fold_table[tmp + (c & 0xff)];
  23. else
  24. tmp = c;
  25. return tmp;
  26. }
  27. /* Compare unicode strings, return values like normal strcmp */
  28. int hfsplus_strcasecmp(const struct hfsplus_unistr *s1,
  29. const struct hfsplus_unistr *s2)
  30. {
  31. u16 len1, len2, c1, c2;
  32. const hfsplus_unichr *p1, *p2;
  33. len1 = be16_to_cpu(s1->length);
  34. len2 = be16_to_cpu(s2->length);
  35. p1 = s1->unicode;
  36. p2 = s2->unicode;
  37. while (1) {
  38. c1 = c2 = 0;
  39. while (len1 && !c1) {
  40. c1 = case_fold(be16_to_cpu(*p1));
  41. p1++;
  42. len1--;
  43. }
  44. while (len2 && !c2) {
  45. c2 = case_fold(be16_to_cpu(*p2));
  46. p2++;
  47. len2--;
  48. }
  49. if (c1 != c2)
  50. return (c1 < c2) ? -1 : 1;
  51. if (!c1 && !c2)
  52. return 0;
  53. }
  54. }
  55. /* Compare names as a sequence of 16-bit unsigned integers */
  56. int hfsplus_strcmp(const struct hfsplus_unistr *s1,
  57. const struct hfsplus_unistr *s2)
  58. {
  59. u16 len1, len2, c1, c2;
  60. const hfsplus_unichr *p1, *p2;
  61. int len;
  62. len1 = be16_to_cpu(s1->length);
  63. len2 = be16_to_cpu(s2->length);
  64. p1 = s1->unicode;
  65. p2 = s2->unicode;
  66. for (len = min(len1, len2); len > 0; len--) {
  67. c1 = be16_to_cpu(*p1);
  68. c2 = be16_to_cpu(*p2);
  69. if (c1 != c2)
  70. return c1 < c2 ? -1 : 1;
  71. p1++;
  72. p2++;
  73. }
  74. return len1 < len2 ? -1 :
  75. len1 > len2 ? 1 : 0;
  76. }
  77. #define Hangul_SBase 0xac00
  78. #define Hangul_LBase 0x1100
  79. #define Hangul_VBase 0x1161
  80. #define Hangul_TBase 0x11a7
  81. #define Hangul_SCount 11172
  82. #define Hangul_LCount 19
  83. #define Hangul_VCount 21
  84. #define Hangul_TCount 28
  85. #define Hangul_NCount (Hangul_VCount * Hangul_TCount)
  86. static u16 *hfsplus_compose_lookup(u16 *p, u16 cc)
  87. {
  88. int i, s, e;
  89. s = 1;
  90. e = p[1];
  91. if (!e || cc < p[s * 2] || cc > p[e * 2])
  92. return NULL;
  93. do {
  94. i = (s + e) / 2;
  95. if (cc > p[i * 2])
  96. s = i + 1;
  97. else if (cc < p[i * 2])
  98. e = i - 1;
  99. else
  100. return hfsplus_compose_table + p[i * 2 + 1];
  101. } while (s <= e);
  102. return NULL;
  103. }
  104. int hfsplus_uni2asc(struct super_block *sb,
  105. const struct hfsplus_unistr *ustr,
  106. char *astr, int *len_p)
  107. {
  108. const hfsplus_unichr *ip;
  109. struct nls_table *nls = HFSPLUS_SB(sb)->nls;
  110. u8 *op;
  111. u16 cc, c0, c1;
  112. u16 *ce1, *ce2;
  113. int i, len, ustrlen, res, compose;
  114. op = astr;
  115. ip = ustr->unicode;
  116. ustrlen = be16_to_cpu(ustr->length);
  117. len = *len_p;
  118. ce1 = NULL;
  119. compose = !test_bit(HFSPLUS_SB_NODECOMPOSE, &HFSPLUS_SB(sb)->flags);
  120. while (ustrlen > 0) {
  121. c0 = be16_to_cpu(*ip++);
  122. ustrlen--;
  123. /* search for single decomposed char */
  124. if (likely(compose))
  125. ce1 = hfsplus_compose_lookup(hfsplus_compose_table, c0);
  126. if (ce1)
  127. cc = ce1[0];
  128. else
  129. cc = 0;
  130. if (cc) {
  131. /* start of a possibly decomposed Hangul char */
  132. if (cc != 0xffff)
  133. goto done;
  134. if (!ustrlen)
  135. goto same;
  136. c1 = be16_to_cpu(*ip) - Hangul_VBase;
  137. if (c1 < Hangul_VCount) {
  138. /* compose the Hangul char */
  139. cc = (c0 - Hangul_LBase) * Hangul_VCount;
  140. cc = (cc + c1) * Hangul_TCount;
  141. cc += Hangul_SBase;
  142. ip++;
  143. ustrlen--;
  144. if (!ustrlen)
  145. goto done;
  146. c1 = be16_to_cpu(*ip) - Hangul_TBase;
  147. if (c1 > 0 && c1 < Hangul_TCount) {
  148. cc += c1;
  149. ip++;
  150. ustrlen--;
  151. }
  152. goto done;
  153. }
  154. }
  155. while (1) {
  156. /* main loop for common case of not composed chars */
  157. if (!ustrlen)
  158. goto same;
  159. c1 = be16_to_cpu(*ip);
  160. if (likely(compose))
  161. ce1 = hfsplus_compose_lookup(
  162. hfsplus_compose_table, c1);
  163. if (ce1)
  164. break;
  165. switch (c0) {
  166. case 0:
  167. c0 = 0x2400;
  168. break;
  169. case '/':
  170. c0 = ':';
  171. break;
  172. }
  173. res = nls->uni2char(c0, op, len);
  174. if (res < 0) {
  175. if (res == -ENAMETOOLONG)
  176. goto out;
  177. *op = '?';
  178. res = 1;
  179. }
  180. op += res;
  181. len -= res;
  182. c0 = c1;
  183. ip++;
  184. ustrlen--;
  185. }
  186. ce2 = hfsplus_compose_lookup(ce1, c0);
  187. if (ce2) {
  188. i = 1;
  189. while (i < ustrlen) {
  190. ce1 = hfsplus_compose_lookup(ce2,
  191. be16_to_cpu(ip[i]));
  192. if (!ce1)
  193. break;
  194. i++;
  195. ce2 = ce1;
  196. }
  197. cc = ce2[0];
  198. if (cc) {
  199. ip += i;
  200. ustrlen -= i;
  201. goto done;
  202. }
  203. }
  204. same:
  205. switch (c0) {
  206. case 0:
  207. cc = 0x2400;
  208. break;
  209. case '/':
  210. cc = ':';
  211. break;
  212. default:
  213. cc = c0;
  214. }
  215. done:
  216. res = nls->uni2char(cc, op, len);
  217. if (res < 0) {
  218. if (res == -ENAMETOOLONG)
  219. goto out;
  220. *op = '?';
  221. res = 1;
  222. }
  223. op += res;
  224. len -= res;
  225. }
  226. res = 0;
  227. out:
  228. *len_p = (char *)op - astr;
  229. return res;
  230. }
  231. /*
  232. * Convert one or more ASCII characters into a single unicode character.
  233. * Returns the number of ASCII characters corresponding to the unicode char.
  234. */
  235. static inline int asc2unichar(struct super_block *sb, const char *astr, int len,
  236. wchar_t *uc)
  237. {
  238. int size = HFSPLUS_SB(sb)->nls->char2uni(astr, len, uc);
  239. if (size <= 0) {
  240. *uc = '?';
  241. size = 1;
  242. }
  243. switch (*uc) {
  244. case 0x2400:
  245. *uc = 0;
  246. break;
  247. case ':':
  248. *uc = '/';
  249. break;
  250. }
  251. return size;
  252. }
  253. /* Decomposes a non-Hangul unicode character. */
  254. static u16 *hfsplus_decompose_nonhangul(wchar_t uc, int *size)
  255. {
  256. int off;
  257. off = hfsplus_decompose_table[(uc >> 12) & 0xf];
  258. if (off == 0 || off == 0xffff)
  259. return NULL;
  260. off = hfsplus_decompose_table[off + ((uc >> 8) & 0xf)];
  261. if (!off)
  262. return NULL;
  263. off = hfsplus_decompose_table[off + ((uc >> 4) & 0xf)];
  264. if (!off)
  265. return NULL;
  266. off = hfsplus_decompose_table[off + (uc & 0xf)];
  267. *size = off & 3;
  268. if (*size == 0)
  269. return NULL;
  270. return hfsplus_decompose_table + (off / 4);
  271. }
  272. /*
  273. * Try to decompose a unicode character as Hangul. Return 0 if @uc is not
  274. * precomposed Hangul, otherwise return the length of the decomposition.
  275. *
  276. * This function was adapted from sample code from the Unicode Standard
  277. * Annex #15: Unicode Normalization Forms, version 3.2.0.
  278. *
  279. * Copyright (C) 1991-2018 Unicode, Inc. All rights reserved. Distributed
  280. * under the Terms of Use in http://www.unicode.org/copyright.html.
  281. */
  282. static int hfsplus_try_decompose_hangul(wchar_t uc, u16 *result)
  283. {
  284. int index;
  285. int l, v, t;
  286. index = uc - Hangul_SBase;
  287. if (index < 0 || index >= Hangul_SCount)
  288. return 0;
  289. l = Hangul_LBase + index / Hangul_NCount;
  290. v = Hangul_VBase + (index % Hangul_NCount) / Hangul_TCount;
  291. t = Hangul_TBase + index % Hangul_TCount;
  292. result[0] = l;
  293. result[1] = v;
  294. if (t != Hangul_TBase) {
  295. result[2] = t;
  296. return 3;
  297. }
  298. return 2;
  299. }
  300. /* Decomposes a single unicode character. */
  301. static u16 *decompose_unichar(wchar_t uc, int *size, u16 *hangul_buffer)
  302. {
  303. u16 *result;
  304. /* Hangul is handled separately */
  305. result = hangul_buffer;
  306. *size = hfsplus_try_decompose_hangul(uc, result);
  307. if (*size == 0)
  308. result = hfsplus_decompose_nonhangul(uc, size);
  309. return result;
  310. }
  311. int hfsplus_asc2uni(struct super_block *sb,
  312. struct hfsplus_unistr *ustr, int max_unistr_len,
  313. const char *astr, int len)
  314. {
  315. int size, dsize, decompose;
  316. u16 *dstr, outlen = 0;
  317. wchar_t c;
  318. u16 dhangul[3];
  319. decompose = !test_bit(HFSPLUS_SB_NODECOMPOSE, &HFSPLUS_SB(sb)->flags);
  320. while (outlen < max_unistr_len && len > 0) {
  321. size = asc2unichar(sb, astr, len, &c);
  322. if (decompose)
  323. dstr = decompose_unichar(c, &dsize, dhangul);
  324. else
  325. dstr = NULL;
  326. if (dstr) {
  327. if (outlen + dsize > max_unistr_len)
  328. break;
  329. do {
  330. ustr->unicode[outlen++] = cpu_to_be16(*dstr++);
  331. } while (--dsize > 0);
  332. } else
  333. ustr->unicode[outlen++] = cpu_to_be16(c);
  334. astr += size;
  335. len -= size;
  336. }
  337. ustr->length = cpu_to_be16(outlen);
  338. if (len > 0)
  339. return -ENAMETOOLONG;
  340. return 0;
  341. }
  342. /*
  343. * Hash a string to an integer as appropriate for the HFS+ filesystem.
  344. * Composed unicode characters are decomposed and case-folding is performed
  345. * if the appropriate bits are (un)set on the superblock.
  346. */
  347. int hfsplus_hash_dentry(const struct dentry *dentry, struct qstr *str)
  348. {
  349. struct super_block *sb = dentry->d_sb;
  350. const char *astr;
  351. const u16 *dstr;
  352. int casefold, decompose, size, len;
  353. unsigned long hash;
  354. wchar_t c;
  355. u16 c2;
  356. u16 dhangul[3];
  357. casefold = test_bit(HFSPLUS_SB_CASEFOLD, &HFSPLUS_SB(sb)->flags);
  358. decompose = !test_bit(HFSPLUS_SB_NODECOMPOSE, &HFSPLUS_SB(sb)->flags);
  359. hash = init_name_hash(dentry);
  360. astr = str->name;
  361. len = str->len;
  362. while (len > 0) {
  363. int dsize;
  364. size = asc2unichar(sb, astr, len, &c);
  365. astr += size;
  366. len -= size;
  367. if (decompose)
  368. dstr = decompose_unichar(c, &dsize, dhangul);
  369. else
  370. dstr = NULL;
  371. if (dstr) {
  372. do {
  373. c2 = *dstr++;
  374. if (casefold)
  375. c2 = case_fold(c2);
  376. if (!casefold || c2)
  377. hash = partial_name_hash(c2, hash);
  378. } while (--dsize > 0);
  379. } else {
  380. c2 = c;
  381. if (casefold)
  382. c2 = case_fold(c2);
  383. if (!casefold || c2)
  384. hash = partial_name_hash(c2, hash);
  385. }
  386. }
  387. str->hash = end_name_hash(hash);
  388. return 0;
  389. }
  390. /*
  391. * Compare strings with HFS+ filename ordering.
  392. * Composed unicode characters are decomposed and case-folding is performed
  393. * if the appropriate bits are (un)set on the superblock.
  394. */
  395. int hfsplus_compare_dentry(const struct dentry *dentry,
  396. unsigned int len, const char *str, const struct qstr *name)
  397. {
  398. struct super_block *sb = dentry->d_sb;
  399. int casefold, decompose, size;
  400. int dsize1, dsize2, len1, len2;
  401. const u16 *dstr1, *dstr2;
  402. const char *astr1, *astr2;
  403. u16 c1, c2;
  404. wchar_t c;
  405. u16 dhangul_1[3], dhangul_2[3];
  406. casefold = test_bit(HFSPLUS_SB_CASEFOLD, &HFSPLUS_SB(sb)->flags);
  407. decompose = !test_bit(HFSPLUS_SB_NODECOMPOSE, &HFSPLUS_SB(sb)->flags);
  408. astr1 = str;
  409. len1 = len;
  410. astr2 = name->name;
  411. len2 = name->len;
  412. dsize1 = dsize2 = 0;
  413. dstr1 = dstr2 = NULL;
  414. while (len1 > 0 && len2 > 0) {
  415. if (!dsize1) {
  416. size = asc2unichar(sb, astr1, len1, &c);
  417. astr1 += size;
  418. len1 -= size;
  419. if (decompose)
  420. dstr1 = decompose_unichar(c, &dsize1,
  421. dhangul_1);
  422. if (!decompose || !dstr1) {
  423. c1 = c;
  424. dstr1 = &c1;
  425. dsize1 = 1;
  426. }
  427. }
  428. if (!dsize2) {
  429. size = asc2unichar(sb, astr2, len2, &c);
  430. astr2 += size;
  431. len2 -= size;
  432. if (decompose)
  433. dstr2 = decompose_unichar(c, &dsize2,
  434. dhangul_2);
  435. if (!decompose || !dstr2) {
  436. c2 = c;
  437. dstr2 = &c2;
  438. dsize2 = 1;
  439. }
  440. }
  441. c1 = *dstr1;
  442. c2 = *dstr2;
  443. if (casefold) {
  444. c1 = case_fold(c1);
  445. if (!c1) {
  446. dstr1++;
  447. dsize1--;
  448. continue;
  449. }
  450. c2 = case_fold(c2);
  451. if (!c2) {
  452. dstr2++;
  453. dsize2--;
  454. continue;
  455. }
  456. }
  457. if (c1 < c2)
  458. return -1;
  459. else if (c1 > c2)
  460. return 1;
  461. dstr1++;
  462. dsize1--;
  463. dstr2++;
  464. dsize2--;
  465. }
  466. if (len1 < len2)
  467. return -1;
  468. if (len1 > len2)
  469. return 1;
  470. return 0;
  471. }