bsd/vfs/vfs_utfconv.c

   1 /*
   2  * Copyright (c) 2000-2002 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * The contents of this file constitute Original Code as defined in and
   7  * are subject to the Apple Public Source License Version 1.1 (the
   8  * "License").  You may not use this file except in compliance with the
   9  * License.  Please obtain a copy of the License at
  10  * http://www.apple.com/publicsource and read it before using this file.
  11  *
  12  * This Original Code and all software distributed under the License are
  13  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
  17  * License for the specific language governing rights and limitations
  18  * under the License.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22
  23  /*
  24         Includes Unicode 3.2 decomposition code derived from Core Foundation
  25  */
  26
  27 #include <sys/param.h>
  28 #include <sys/utfconv.h>
  29 #include <sys/errno.h>
  30 #include <libkern/OSByteOrder.h>
  31
  32 /*
  33  * UTF-8 (Unicode Transformation Format)
  34  *
  35  * UTF-8 is the Unicode Transformation Format that serializes a Unicode
  36  * character as a sequence of one to four bytes. Only the shortest form
  37  * required to represent the significant Unicode bits is legal.
  38  *
  39  * UTF-8 Multibyte Codes
  40  *
  41  * Bytes   Bits   Unicode Min  Unicode Max   UTF-8 Byte Sequence (binary)
  42  * -----------------------------------------------------------------------------
  43  *   1       7       0x0000        0x007F    0xxxxxxx
  44  *   2      11       0x0080        0x07FF    110xxxxx 10xxxxxx
  45  *   3      16       0x0800        0xFFFF    1110xxxx 10xxxxxx 10xxxxxx
  46  *   4      21      0x10000      0x10FFFF    11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  47  * -----------------------------------------------------------------------------
  48  */
  49
  50
  51 #define UNICODE_TO_UTF8_LEN(c)  \
  52         ((c) < 0x0080 ? 1 : ((c) < 0x0800 ? 2 : (((c) & 0xf800) == 0xd800 ? 2 : 3)))
  53
  54 #define UCS_ALT_NULL    0x2400
  55
  56 /* Surrogate Pair Constants */
  57 #define SP_HALF_SHIFT   10
  58 #define SP_HALF_BASE    0x0010000UL
  59 #define SP_HALF_MASK    0x3FFUL
  60
  61 #define SP_HIGH_FIRST   0xD800UL
  62 #define SP_HIGH_LAST    0xDBFFUL
  63 #define SP_LOW_FIRST    0xDC00UL
  64 #define SP_LOW_LAST     0xDFFFUL
  65
  66
  67 #include "vfs_utfconvdata.h"
  68
  69
  70 /*
  71  * Test for a combining character.
  72  *
  73  * Similar to __CFUniCharIsNonBaseCharacter except that
  74  * unicode_combinable also includes Hangul Jamo characters.
  75  */
  76 static inline int
  77 unicode_combinable(u_int16_t character)
  78 {
  79         const u_int8_t *bitmap = __CFUniCharCombiningBitmap;
  80         u_int8_t value;
  81
  82         if (character < 0x0300)
  83                 return (0);
  84
  85         value = bitmap[(character >> 8) & 0xFF];
  86
  87         if (value == 0xFF) {
  88                 return (1);
  89         } else if (value) {
  90                 bitmap = bitmap + ((value - 1) * 32) + 256;
  91                 return (bitmap[(character & 0xFF) / 8] & (1 << (character % 8)) ? 1 : 0);
  92         }
  93         return (0);
  94 }
  95
  96 /*
  97  * Test for a precomposed character.
  98  *
  99  * Similar to __CFUniCharIsDecomposableCharacter.
 100  */
 101 static inline int
 102 unicode_decomposeable(u_int16_t character) {
 103         const u_int8_t *bitmap = __CFUniCharDecomposableBitmap;
 104         u_int8_t value;
 105
 106         if (character < 0x00C0)
 107                 return (0);
 108
 109         value = bitmap[(character >> 8) & 0xFF];
 110
 111         if (value == 0xFF) {
 112                 return (1);
 113         } else if (value) {
 114                 bitmap = bitmap + ((value - 1) * 32) + 256;
 115                 return (bitmap[(character & 0xFF) / 8] & (1 << (character % 8)) ? 1 : 0);
 116         }
 117         return (0);
 118 }
 119
 120
 121 /*
 122  * Get the combing class.
 123  *
 124  * Similar to CFUniCharGetCombiningPropertyForCharacter.
 125  */
 126 static inline u_int8_t
 127 get_combining_class(u_int16_t character) {
 128         const u_int8_t *bitmap = __CFUniCharCombiningPropertyBitmap;
 129
 130         u_int8_t value = bitmap[(character >> 8)];
 131
 132         if (value) {
 133                 bitmap = bitmap + (value * 256);
 134                 return bitmap[character % 256];
 135         }
 136         return (0);
 137 }
 138
 139
 140 static int unicode_decompose(u_int16_t character, u_int16_t *convertedChars);
 141
 142 static u_int16_t unicode_combine(u_int16_t base, u_int16_t combining);
 143
 144 static void priortysort(u_int16_t* characters, int count);
 145
 146 char utf_extrabytes[32] = {
 147          0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
 148         -1, -1, -1, -1, -1, -1, -1, -1,  1,  1,  1,  1,  2,  2,  3, -1
 149 };
 150
 151
 152 /*
 153  * utf8_encodelen - Calculates the UTF-8 encoding length for a Unicode filename
 154  *
 155  * NOTES:
 156  *    If '/' chars are allowed on disk then an alternate
 157  *    (replacement) char must be provided in altslash.
 158  *
 159  * input flags:
 160  *    UTF_REVERSE_ENDIAN: Unicode byteorder is opposite current runtime
 161  */
 162 size_t
 163 utf8_encodelen(const u_int16_t * ucsp, size_t ucslen, u_int16_t altslash,
 164                int flags)
 165 {
 166         u_int16_t ucs_ch;
 167         int charcnt;
 168         int swapbytes = (flags & UTF_REVERSE_ENDIAN);
 169         size_t len;
 170
 171         charcnt = ucslen / 2;
 172         len = 0;
 173
 174         while (charcnt-- > 0) {
 175                 ucs_ch = *ucsp++;
 176
 177                 if (swapbytes)
 178                         ucs_ch = OSSwapInt16(ucs_ch);
 179                 if (ucs_ch == '/')
 180                         ucs_ch = altslash ? altslash : '_';
 181                 else if (ucs_ch == '\0')
 182                         ucs_ch = UCS_ALT_NULL;
 183
 184                 len += UNICODE_TO_UTF8_LEN(ucs_ch);
 185         }
 186
 187         return (len);
 188 }
 189
 190
 191 /*
 192  * utf8_encodestr - Encodes a Unicode string to UTF-8
 193  *
 194  * NOTES:
 195  *    The resulting UTF-8 string is NULL terminated.
 196  *
 197  *    If '/' chars are allowed on disk then an alternate
 198  *    (replacement) char must be provided in altslash.
 199  *
 200  * input flags:
 201  *    UTF_REVERSE_ENDIAN: Unicode byteorder is opposite current runtime
 202  *    UTF_NO_NULL_TERM:  don't add NULL termination to UTF-8 output
 203  *
 204  * result:
 205  *    ENAMETOOLONG: Name didn't fit; only buflen bytes were encoded
 206  *    EINVAL: Illegal char found; char was replaced by an '_'.
 207  */
 208 int
 209 utf8_encodestr(const u_int16_t * ucsp, size_t ucslen, u_int8_t * utf8p,
 210                size_t * utf8len, size_t buflen, u_int16_t altslash, int flags)
 211 {
 212         u_int8_t * bufstart;
 213         u_int8_t * bufend;
 214         u_int16_t ucs_ch;
 215         u_int16_t * chp = NULL;
 216         u_int16_t sequence[8];
 217         int extra = 0;
 218         int charcnt;
 219         int swapbytes = (flags & UTF_REVERSE_ENDIAN);
 220         int nullterm  = ((flags & UTF_NO_NULL_TERM) == 0);
 221         int decompose = (flags & UTF_DECOMPOSED);
 222         int result = 0;
 223
 224         bufstart = utf8p;
 225         bufend = bufstart + buflen;
 226         if (nullterm)
 227                 --bufend;
 228         charcnt = ucslen / 2;
 229
 230         while (charcnt-- > 0) {
 231                 if (extra > 0) {
 232                         --extra;
 233                         ucs_ch = *chp++;
 234                 } else {
 235                         ucs_ch = swapbytes ? OSSwapInt16(*ucsp++) : *ucsp++;
 236
 237                         if (decompose && unicode_decomposeable(ucs_ch)) {
 238                                 extra = unicode_decompose(ucs_ch, sequence) - 1;
 239                                 charcnt += extra;
 240                                 ucs_ch = sequence[0];
 241                                 chp = &sequence[1];
 242                         }
 243                 }
 244
 245                 /* Slash and NULL are not permitted */
 246                 if (ucs_ch == '/') {
 247                         if (altslash)
 248                                 ucs_ch = altslash;
 249                         else {
 250                                 ucs_ch = '_';
 251                                 result = EINVAL;
 252                         }
 253                 } else if (ucs_ch == '\0') {
 254                         ucs_ch = UCS_ALT_NULL;
 255                 }
 256
 257                 if (ucs_ch < 0x0080) {
 258                         if (utf8p >= bufend) {
 259                                 result = ENAMETOOLONG;
 260                                 break;
 261                         }
 262                         *utf8p++ = ucs_ch;
 263
 264                 } else if (ucs_ch < 0x800) {
 265                         if ((utf8p + 1) >= bufend) {
 266                                 result = ENAMETOOLONG;
 267                                 break;
 268                         }
 269                         *utf8p++ = 0xc0 | (ucs_ch >> 6);
 270                         *utf8p++ = 0x80 | (0x3f & ucs_ch);
 271
 272                 } else {
 273                         /* Combine valid surrogate pairs */
 274                         if (ucs_ch >= SP_HIGH_FIRST && ucs_ch <= SP_HIGH_LAST
 275                                 && charcnt > 0) {
 276                                 u_int16_t ch2;
 277                                 u_int32_t pair;
 278
 279                                 ch2 = swapbytes ? OSSwapInt16(*ucsp) : *ucsp;
 280                                 if (ch2 >= SP_LOW_FIRST && ch2 <= SP_LOW_LAST) {
 281                                         pair = ((ucs_ch - SP_HIGH_FIRST) << SP_HALF_SHIFT)
 282                                                 + (ch2 - SP_LOW_FIRST) + SP_HALF_BASE;
 283                                         if ((utf8p + 3) >= bufend) {
 284                                                 result = ENAMETOOLONG;
 285                                                 break;
 286                                         }
 287                                         --charcnt;
 288                                         ++ucsp;
 289                                         *utf8p++ = 0xf0 | (pair >> 18);
 290                                         *utf8p++ = 0x80 | (0x3f & (pair >> 12));
 291                                         *utf8p++ = 0x80 | (0x3f & (pair >> 6));
 292                                         *utf8p++ = 0x80 | (0x3f & pair);
 293                                         continue;
 294                                 }
 295                         }
 296                         if ((utf8p + 2) >= bufend) {
 297                                 result = ENAMETOOLONG;
 298                                 break;
 299                         }
 300                         *utf8p++ = 0xe0 | (ucs_ch >> 12);
 301                         *utf8p++ = 0x80 | (0x3f & (ucs_ch >> 6));
 302                         *utf8p++ = 0x80 | (0x3f & ucs_ch);
 303                 }
 304         }
 305
 306         *utf8len = utf8p - bufstart;
 307         if (nullterm)
 308                 *utf8p++ = '\0';
 309
 310         return (result);
 311 }
 312
 313
 314 /*
 315  * utf8_decodestr - Decodes a UTF-8 string back to Unicode
 316  *
 317  * NOTES:
 318  *    The input UTF-8 string does not need to be null terminated
 319  *    if utf8len is set.
 320  *
 321  *    If '/' chars are allowed on disk then an alternate
 322  *    (replacement) char must be provided in altslash.
 323  *
 324  * input flags:
 325  *    UTF_REV_ENDIAN:   Unicode byteorder is oposite current runtime
 326  *    UTF_DECOMPOSED:   Unicode output string must be fully decompsed
 327  *
 328  * result:
 329  *    ENAMETOOLONG: Name didn't fit; only ucslen chars were decoded.
 330  *    EINVAL: Illegal UTF-8 sequence found.
 331  */
 332 int
 333 utf8_decodestr(const u_int8_t* utf8p, size_t utf8len, u_int16_t* ucsp,
 334                size_t *ucslen, size_t buflen, u_int16_t altslash, int flags)
 335 {
 336         u_int16_t* bufstart;
 337         u_int16_t* bufend;
 338         unsigned int ucs_ch;
 339         unsigned int byte;
 340         int combcharcnt = 0;
 341         int result = 0;
 342         int decompose, precompose, swapbytes;
 343
 344         decompose =  (flags & UTF_DECOMPOSED);
 345         precompose = (flags & UTF_PRECOMPOSED);
 346         swapbytes =  (flags & UTF_REVERSE_ENDIAN);
 347
 348         bufstart = ucsp;
 349         bufend = (u_int16_t *)((u_int8_t *)ucsp + buflen);
 350
 351         while (utf8len-- > 0 && (byte = *utf8p++) != '\0') {
 352                 if (ucsp >= bufend)
 353                         goto toolong;
 354
 355                 /* check for ascii */
 356                 if (byte < 0x80) {
 357                         ucs_ch = byte;                 /* 1st byte */
 358                 } else {
 359                         u_int32_t ch;
 360                         int extrabytes = utf_extrabytes[byte >> 3];
 361
 362                         if (utf8len < extrabytes)
 363                                 goto invalid;
 364                         utf8len -= extrabytes;
 365
 366                         switch (extrabytes) {
 367                         case 1:
 368                                 ch = byte; ch <<= 6;   /* 1st byte */
 369                                 byte = *utf8p++;       /* 2nd byte */
 370                                 if ((byte >> 6) != 2)
 371                                         goto invalid;
 372                                 ch += byte;
 373                                 ch -= 0x00003080UL;
 374                                 if (ch < 0x0080)
 375                                         goto invalid;
 376                                 ucs_ch = ch;
 377                                 break;
 378                         case 2:
 379                                 ch = byte; ch <<= 6;   /* 1st byte */
 380                                 byte = *utf8p++;       /* 2nd byte */
 381                                 if ((byte >> 6) != 2)
 382                                         goto invalid;
 383                                 ch += byte; ch <<= 6;
 384                                 byte = *utf8p++;       /* 3rd byte */
 385                                 if ((byte >> 6) != 2)
 386                                         goto invalid;
 387                                 ch += byte;
 388                                 ch -= 0x000E2080UL;
 389                                 if (ch < 0x0800)
 390                                         goto invalid;
 391                                 if (ch >= 0xD800) {
 392                                         if (ch <= 0xDFFF)
 393                                                 goto invalid;
 394                                         if (ch == 0xFFFE || ch == 0xFFFF)
 395                                                 goto invalid;
 396                                 }
 397                                 ucs_ch = ch;
 398                                 break;
 399                         case 3:
 400                                 ch = byte; ch <<= 6;   /* 1st byte */
 401                                 byte = *utf8p++;       /* 2nd byte */
 402                                 if ((byte >> 6) != 2)
 403                                         goto invalid;
 404                                 ch += byte; ch <<= 6;
 405                                 byte = *utf8p++;       /* 3rd byte */
 406                                 if ((byte >> 6) != 2)
 407                                         goto invalid;
 408                                 ch += byte; ch <<= 6;
 409                                 byte = *utf8p++;       /* 4th byte */
 410                                 if ((byte >> 6) != 2)
 411                                         goto invalid;
 412                                 ch += byte;
 413                                 ch -= 0x03C82080UL + SP_HALF_BASE;
 414                                 ucs_ch = (ch >> SP_HALF_SHIFT) + SP_HIGH_FIRST;
 415                                 if (ucs_ch < SP_HIGH_FIRST || ucs_ch > SP_HIGH_LAST)
 416                                         goto invalid;
 417                                 *ucsp++ = swapbytes ? OSSwapInt16(ucs_ch) : ucs_ch;
 418                                 if (ucsp >= bufend)
 419                                         goto toolong;
 420                                 ucs_ch = (ch & SP_HALF_MASK) + SP_LOW_FIRST;
 421                                 if (ucs_ch < SP_LOW_FIRST || ucs_ch > SP_LOW_LAST)
 422                                         goto invalid;
 423                                 *ucsp++ = swapbytes ? OSSwapInt16(ucs_ch) : ucs_ch;
 424                                 continue;
 425                         default:
 426                                 goto invalid;
 427                         }
 428                         if (decompose) {
 429                                 if (unicode_decomposeable(ucs_ch)) {
 430                                         u_int16_t sequence[8];
 431                                         int count, i;
 432
 433                                         count = unicode_decompose(ucs_ch, sequence);
 434
 435                                         for (i = 0; i < count; ++i) {
 436                                                 ucs_ch = sequence[i];
 437                                                 *ucsp++ = swapbytes ? OSSwapInt16(ucs_ch) : ucs_ch;
 438                                                 if (ucsp >= bufend)
 439                                                         goto toolong;
 440                                         }
 441                                         combcharcnt += count - 1;
 442                                         continue;
 443                                 }
 444                         } else if (precompose && (ucsp != bufstart)) {
 445                                 u_int16_t composite, base;
 446
 447                                 if (unicode_combinable(ucs_ch)) {
 448                                         base = swapbytes ? OSSwapInt16(*(ucsp - 1)) : *(ucsp - 1);
 449                                         composite = unicode_combine(base, ucs_ch);
 450                                         if (composite) {
 451                                                 --ucsp;
 452                                                 ucs_ch = composite;
 453                                         }
 454                                 }
 455                         }
 456                         if (ucs_ch == UCS_ALT_NULL)
 457                                 ucs_ch = '\0';
 458                 }
 459                 if (ucs_ch == altslash)
 460                         ucs_ch = '/';
 461
 462                 /*
 463                  * Make multiple combining character sequences canonical
 464                  */
 465                 if (unicode_combinable(ucs_ch)) {
 466                         ++combcharcnt;   /* start tracking a run */
 467                 } else if (combcharcnt) {
 468                         if (combcharcnt > 1) {
 469                                 priortysort(ucsp - combcharcnt, combcharcnt);
 470                         }
 471                         combcharcnt = 0;  /* start over */
 472                 }
 473                 *ucsp++ = swapbytes ? OSSwapInt16(ucs_ch) : ucs_ch;
 474         }
 475         /*
 476          * Make a previous combining sequence canonical
 477          */
 478         if (combcharcnt > 1) {
 479                 priortysort(ucsp - combcharcnt, combcharcnt);
 480         }
 481
 482 exit:
 483         *ucslen = (u_int8_t*)ucsp - (u_int8_t*)bufstart;
 484
 485         return (result);
 486
 487 invalid:
 488         result = EINVAL;
 489         goto exit;
 490
 491 toolong:
 492         result = ENAMETOOLONG;
 493         goto exit;
 494 }
 495
 496
 497 /*
 498  * utf8_validatestr - Check for a valid UTF-8 string.
 499  */
 500 int
 501 utf8_validatestr(const u_int8_t* utf8p, size_t utf8len)
 502 {
 503         unsigned int byte;
 504         u_int32_t ch;
 505         unsigned int ucs_ch;
 506         size_t extrabytes;
 507
 508         while (utf8len-- > 0 && (byte = *utf8p++) != '\0') {
 509                 if (byte < 0x80)
 510                         continue;  /* plain ascii */
 511
 512                 extrabytes = utf_extrabytes[byte >> 3];
 513
 514                 if (utf8len < extrabytes)
 515                         goto invalid;
 516                 utf8len -= extrabytes;
 517
 518                 switch (extrabytes) {
 519                 case 1:
 520                         ch = byte; ch <<= 6;   /* 1st byte */
 521                         byte = *utf8p++;       /* 2nd byte */
 522                         if ((byte >> 6) != 2)
 523                                 goto invalid;
 524                         ch += byte;
 525                         ch -= 0x00003080UL;
 526                         if (ch < 0x0080)
 527                                 goto invalid;
 528                         break;
 529                 case 2:
 530                         ch = byte; ch <<= 6;   /* 1st byte */
 531                         byte = *utf8p++;       /* 2nd byte */
 532                         if ((byte >> 6) != 2)
 533                                 goto invalid;
 534                         ch += byte; ch <<= 6;
 535                         byte = *utf8p++;       /* 3rd byte */
 536                         if ((byte >> 6) != 2)
 537                                 goto invalid;
 538                         ch += byte;
 539                         ch -= 0x000E2080UL;
 540                         if (ch < 0x0800)
 541                                 goto invalid;
 542                         if (ch >= 0xD800) {
 543                                 if (ch <= 0xDFFF)
 544                                         goto invalid;
 545                                 if (ch == 0xFFFE || ch == 0xFFFF)
 546                                         goto invalid;
 547                         }
 548                         break;
 549                 case 3:
 550                         ch = byte; ch <<= 6;   /* 1st byte */
 551                         byte = *utf8p++;       /* 2nd byte */
 552                         if ((byte >> 6) != 2)
 553                                 goto invalid;
 554                         ch += byte; ch <<= 6;
 555                         byte = *utf8p++;       /* 3rd byte */
 556                         if ((byte >> 6) != 2)
 557                                 goto invalid;
 558                         ch += byte; ch <<= 6;
 559                         byte = *utf8p++;       /* 4th byte */
 560                         if ((byte >> 6) != 2)
 561                                 goto invalid;
 562                         ch += byte;
 563                         ch -= 0x03C82080UL + SP_HALF_BASE;
 564                         ucs_ch = (ch >> SP_HALF_SHIFT) + SP_HIGH_FIRST;
 565                         if (ucs_ch < SP_HIGH_FIRST || ucs_ch > SP_HIGH_LAST)
 566                                 goto invalid;
 567                         ucs_ch = (ch & SP_HALF_MASK) + SP_LOW_FIRST;
 568                         if (ucs_ch < SP_LOW_FIRST || ucs_ch > SP_LOW_LAST)
 569                                 goto invalid;
 570                         break;
 571                 default:
 572                         goto invalid;
 573                 }
 574
 575         }
 576         return (0);
 577 invalid:
 578         return (EINVAL);
 579 }
 580
 581
 582  /*
 583   * Unicode 3.2 decomposition code (derived from Core Foundation)
 584   */
 585
 586 typedef struct {
 587         u_int32_t _key;
 588         u_int32_t _value;
 589 } unicode_mappings32;
 590
 591 static inline u_int32_t
 592 getmappedvalue32(const unicode_mappings32 *theTable, u_int32_t numElem,
 593                 u_int16_t character)
 594 {
 595         const unicode_mappings32 *p, *q, *divider;
 596
 597         if ((character < theTable[0]._key) || (character > theTable[numElem-1]._key))
 598                 return (0);
 599
 600         p = theTable;
 601         q = p + (numElem-1);
 602         while (p <= q) {
 603                 divider = p + ((q - p) >> 1);   /* divide by 2 */
 604                 if (character < divider->_key) { q = divider - 1; }
 605                 else if (character > divider->_key) { p = divider + 1; }
 606                 else { return (divider->_value); }
 607         }
 608         return (0);
 609 }
 610
 611 #define RECURSIVE_DECOMPOSITION (1 << 15)
 612 #define EXTRACT_COUNT(value)    (((value) >> 12) & 0x0007)
 613
 614 typedef struct {
 615         u_int16_t _key;
 616         u_int16_t _value;
 617 } unicode_mappings16;
 618
 619 static inline u_int16_t
 620 getmappedvalue16(const unicode_mappings16 *theTable, u_int32_t numElem,
 621                 u_int16_t character)
 622 {
 623         const unicode_mappings16 *p, *q, *divider;
 624
 625         if ((character < theTable[0]._key) || (character > theTable[numElem-1]._key))
 626                 return (0);
 627
 628         p = theTable;
 629         q = p + (numElem-1);
 630         while (p <= q) {
 631                 divider = p + ((q - p) >> 1);   /* divide by 2 */
 632                 if (character < divider->_key)
 633                         q = divider - 1;
 634                 else if (character > divider->_key)
 635                         p = divider + 1;
 636                 else
 637                         return (divider->_value);
 638         }
 639         return (0);
 640 }
 641
 642
 643 static u_int32_t
 644 unicode_recursive_decompose(u_int16_t character, u_int16_t *convertedChars)
 645 {
 646         u_int16_t value;
 647         u_int32_t length;
 648         u_int16_t firstChar;
 649         u_int16_t theChar;
 650         const u_int16_t *bmpMappings;
 651         u_int32_t usedLength;
 652
 653         value = getmappedvalue16(
 654                 (const unicode_mappings16 *)__CFUniCharDecompositionTable,
 655                 __UniCharDecompositionTableLength, character);
 656         length = EXTRACT_COUNT(value);
 657         firstChar = value & 0x0FFF;
 658         theChar = firstChar;
 659         bmpMappings = (length == 1 ? &theChar : __CFUniCharMultipleDecompositionTable + firstChar);
 660         usedLength = 0;
 661
 662         if (value & RECURSIVE_DECOMPOSITION) {
 663             usedLength = unicode_recursive_decompose((u_int16_t)*bmpMappings, convertedChars);
 664
 665             --length;   /* Decrement for the first char */
 666             if (!usedLength)
 667                 return 0;
 668             ++bmpMappings;
 669             convertedChars += usedLength;
 670         }
 671
 672         usedLength += length;
 673
 674         while (length--)
 675                 *(convertedChars++) = *(bmpMappings++);
 676
 677         return (usedLength);
 678 }
 679
 680 #define HANGUL_SBASE 0xAC00
 681 #define HANGUL_LBASE 0x1100
 682 #define HANGUL_VBASE 0x1161
 683 #define HANGUL_TBASE 0x11A7
 684
 685 #define HANGUL_SCOUNT 11172
 686 #define HANGUL_LCOUNT 19
 687 #define HANGUL_VCOUNT 21
 688 #define HANGUL_TCOUNT 28
 689 #define HANGUL_NCOUNT (HANGUL_VCOUNT * HANGUL_TCOUNT)
 690
 691 /*
 692  * unicode_decompose - decompose a composed Unicode char
 693  *
 694  * Composed Unicode characters are forbidden on
 695  * HFS Plus volumes. ucs_decompose will convert a
 696  * composed character into its correct decomposed
 697  * sequence.
 698  *
 699  * Similar to CFUniCharDecomposeCharacter
 700  */
 701 static int
 702 unicode_decompose(u_int16_t character, u_int16_t *convertedChars)
 703 {
 704         if ((character >= HANGUL_SBASE) &&
 705             (character <= (HANGUL_SBASE + HANGUL_SCOUNT))) {
 706                 u_int32_t length;
 707
 708                 character -= HANGUL_SBASE;
 709                 length = (character % HANGUL_TCOUNT ? 3 : 2);
 710
 711                 *(convertedChars++) =
 712                         character / HANGUL_NCOUNT + HANGUL_LBASE;
 713                 *(convertedChars++) =
 714                         (character % HANGUL_NCOUNT) / HANGUL_TCOUNT + HANGUL_VBASE;
 715                 if (length > 2)
 716                         *convertedChars = (character % HANGUL_TCOUNT) + HANGUL_TBASE;
 717                 return (length);
 718         } else {
 719                 return (unicode_recursive_decompose(character, convertedChars));
 720         }
 721 }
 722
 723 /*
 724  * unicode_combine - generate a precomposed Unicode char
 725  *
 726  * Precomposed Unicode characters are required for some volume
 727  * formats and network protocols.  unicode_combine will combine
 728  * a decomposed character sequence into a single precomposed
 729  * (composite) character.
 730  *
 731  * Similar toCFUniCharPrecomposeCharacter but unicode_combine
 732  * also handles Hangul Jamo characters.
 733  */
 734 static u_int16_t
 735 unicode_combine(u_int16_t base, u_int16_t combining)
 736 {
 737         u_int32_t value;
 738
 739         /* Check HANGUL */
 740         if ((combining >= HANGUL_VBASE) && (combining < (HANGUL_TBASE + HANGUL_TCOUNT))) {
 741                 /* 2 char Hangul sequences */
 742                 if ((combining < (HANGUL_VBASE + HANGUL_VCOUNT)) &&
 743                     (base >= HANGUL_LBASE && base < (HANGUL_LBASE + HANGUL_LCOUNT))) {
 744                     return (HANGUL_SBASE +
 745                             ((base - HANGUL_LBASE)*(HANGUL_VCOUNT*HANGUL_TCOUNT)) +
 746                             ((combining  - HANGUL_VBASE)*HANGUL_TCOUNT));
 747                 }
 748
 749                 /* 3 char Hangul sequences */
 750                 if ((combining > HANGUL_TBASE) &&
 751                     (base >= HANGUL_SBASE && base < (HANGUL_SBASE + HANGUL_SCOUNT))) {
 752                         if ((base - HANGUL_SBASE) % HANGUL_TCOUNT)
 753                                 return (0);
 754                         else
 755                                 return (base + (combining - HANGUL_TBASE));
 756                 }
 757         }
 758
 759         value = getmappedvalue32(
 760                 (const unicode_mappings32 *)__CFUniCharPrecompSourceTable,
 761                 __CFUniCharPrecompositionTableLength, combining);
 762
 763         if (value) {
 764                 value = getmappedvalue16(
 765                         (const unicode_mappings16 *)
 766                         ((u_int32_t *)__CFUniCharBMPPrecompDestinationTable + (value & 0xFFFF)),
 767                         (value >> 16), base);
 768         }
 769         return (value);
 770 }
 771
 772
 773 /*
 774  * priortysort - order combining chars into canonical order
 775  *
 776  * Similar to CFUniCharPrioritySort
 777  */
 778 static void
 779 priortysort(u_int16_t* characters, int count)
 780 {
 781         u_int32_t p1, p2;
 782         u_int16_t *ch1, *ch2;
 783         u_int16_t *end;
 784         int changes = 1;
 785
 786         end = characters + count;
 787         do {
 788                 changes = 0;
 789                 ch1 = characters;
 790                 ch2 = characters + 1;
 791                 p2 = get_combining_class(*ch1);
 792                 while (ch2 < end) {
 793                         p1 = p2;
 794                         p2 = get_combining_class(*ch2);
 795                         if (p1 > p2) {
 796                                 u_int32_t tmp;
 797
 798                                 tmp = *ch1;
 799                                 *ch1 = *ch2;
 800                                 *ch2 = tmp;
 801                                 changes = 1;
 802                         }
 803                         ++ch1;
 804                         ++ch2;
 805                 }
 806         } while (changes);
 807 }