unicode.c

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