StringEncodings.subproj/CFUnicodeDecomposition.c

   1 /*
   2  * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /*      CFUnicodeDecomposition.c
  26         Copyright 1999-2002, Apple, Inc. All rights reserved.
  27         Responsibility: Aki Inoue
  28 */
  29
  30 #include <string.h>
  31 #if KERNEL
  32 #include <stdlib.h>
  33 #include "CFUnicodeDecomposition.h"
  34 #include "CFUniCharNonBaseData.h"
  35 #include "CFUniCharDecompData.h"
  36 #include "CFUniCharCombiningPriorityData.h"
  37 #else KERNEL
  38 #include <CoreFoundation/CFBase.h>
  39 #include <CoreFoundation/CFCharacterSet.h>
  40 #include "CFUniChar.h"
  41 #include "CFUnicodeDecomposition.h"
  42 #include "CFInternal.h"
  43 #include "CFUniCharPriv.h"
  44 #endif KERNEL
  45
  46 // Canonical Decomposition
  47 #if KERNEL
  48 static const uint32_t __CFUniCharDecompositionTableLength = (sizeof(__CFUniCharDecompositionTable) / (sizeof(uint32_t) * 2));
  49 // The kernel version of __CFUniCharIsDecomposableCharacter doesn't have exception ranges
  50 #define __CFUniCharIsDecomposableCharacterWithFlag(character,isHFSPlus) (__CFUniCharIsDecomposableCharacter(character))
  51
  52 uint8_t **CFUniCharCombiningPriorityTable = __CFUniCharCombiningPriorityTable;
  53 uint8_t **CFUniCharCombiningPriorityExtraTable = __CFUniCharCombiningPriorityExtraTable;
  54 uint8_t CFUniCharNumberOfPlanesForCombiningPriority = sizeof(__CFUniCharCombiningPriorityTable) / sizeof(*__CFUniCharCombiningPriorityTable);
  55 uint8_t **CFUniCharNonBaseBitmap = __CFUniCharNonBaseBitmap;
  56 uint8_t CFUniCharNumberOfPlanesForNonBaseBitmap = sizeof(__CFUniCharNonBaseBitmap) / sizeof(*__CFUniCharNonBaseBitmap);
  57 #else KERNEL
  58 static UTF32Char *__CFUniCharDecompositionTable = NULL;
  59 static uint32_t __CFUniCharDecompositionTableLength = 0;
  60 static UTF32Char *__CFUniCharMultipleDecompositionTable = NULL;
  61
  62 static const uint8_t *__CFUniCharDecomposableBitmapForBMP = NULL;
  63 static const uint8_t *__CFUniCharHFSPlusDecomposableBitmapForBMP = NULL;
  64 static const uint8_t *__CFUniCharNonBaseBitmapForBMP = NULL;
  65
  66 static CFSpinLock_t __CFUniCharDecompositionTableLock = 0;
  67
  68 static const uint8_t **__CFUniCharCombiningPriorityTable = NULL;
  69 static uint8_t __CFUniCharCombiningPriorityTableNumPlane = 0;
  70
  71 static void __CFUniCharLoadDecompositionTable(void) {
  72
  73     __CFSpinLock(&__CFUniCharDecompositionTableLock);
  74
  75     if (NULL == __CFUniCharDecompositionTable) {
  76         const void *bytes = CFUniCharGetMappingData(kCFUniCharCanonicalDecompMapping);
  77
  78         if (NULL == bytes) {
  79             __CFSpinUnlock(&__CFUniCharDecompositionTableLock);
  80             return;
  81         }
  82
  83         __CFUniCharDecompositionTableLength = *(((uint32_t *)bytes)++);
  84         __CFUniCharDecompositionTable = (UTF32Char *)bytes;
  85         __CFUniCharMultipleDecompositionTable = (UTF32Char *)((intptr_t)bytes + __CFUniCharDecompositionTableLength);
  86
  87         __CFUniCharDecompositionTableLength /= (sizeof(uint32_t) * 2);
  88         __CFUniCharDecomposableBitmapForBMP = CFUniCharGetBitmapPtrForPlane(kCFUniCharCanonicalDecomposableCharacterSet, 0);
  89         __CFUniCharHFSPlusDecomposableBitmapForBMP = CFUniCharGetBitmapPtrForPlane(kCFUniCharHFSPlusDecomposableCharacterSet, 0);
  90         __CFUniCharNonBaseBitmapForBMP = CFUniCharGetBitmapPtrForPlane(kCFUniCharNonBaseCharacterSet, 0);
  91     }
  92
  93     __CFSpinUnlock(&__CFUniCharDecompositionTableLock);
  94 }
  95
  96 static CFSpinLock_t __CFUniCharCompatibilityDecompositionTableLock = 0;
  97 static UTF32Char *__CFUniCharCompatibilityDecompositionTable = NULL;
  98 static uint32_t __CFUniCharCompatibilityDecompositionTableLength = 0;
  99 static UTF32Char *__CFUniCharCompatibilityMultipleDecompositionTable = NULL;
 100
 101 static void __CFUniCharLoadCompatibilityDecompositionTable(void) {
 102
 103     __CFSpinLock(&__CFUniCharCompatibilityDecompositionTableLock);
 104
 105     if (NULL == __CFUniCharCompatibilityDecompositionTable) {
 106         const void *bytes = CFUniCharGetMappingData(kCFUniCharCompatibilityDecompMapping);
 107
 108         if (NULL == bytes) {
 109             __CFSpinUnlock(&__CFUniCharCompatibilityDecompositionTableLock);
 110             return;
 111         }
 112
 113         __CFUniCharCompatibilityDecompositionTableLength = *(((uint32_t *)bytes)++);
 114         __CFUniCharCompatibilityDecompositionTable = (UTF32Char *)bytes;
 115         __CFUniCharCompatibilityMultipleDecompositionTable = (UTF32Char *)((intptr_t)bytes + __CFUniCharCompatibilityDecompositionTableLength);
 116
 117         __CFUniCharCompatibilityDecompositionTableLength /= (sizeof(uint32_t) * 2);
 118     }
 119
 120     __CFSpinUnlock(&__CFUniCharCompatibilityDecompositionTableLock);
 121 }
 122
 123 CF_INLINE bool __CFUniCharIsDecomposableCharacterWithFlag(UTF32Char character, bool isHFSPlus) {
 124     return CFUniCharIsMemberOfBitmap(character, (character < 0x10000 ? (isHFSPlus ? __CFUniCharHFSPlusDecomposableBitmapForBMP : __CFUniCharDecomposableBitmapForBMP) : CFUniCharGetBitmapPtrForPlane(kCFUniCharCanonicalDecomposableCharacterSet, ((character >> 16) & 0xFF))));
 125 }
 126
 127 CF_INLINE bool __CFUniCharIsNonBaseCharacter(UTF32Char character) {
 128     return CFUniCharIsMemberOfBitmap(character, (character < 0x10000 ? __CFUniCharNonBaseBitmapForBMP : CFUniCharGetBitmapPtrForPlane(kCFUniCharNonBaseCharacterSet, ((character >> 16) & 0xFF))));
 129 }
 130 #endif KERNEL
 131
 132 typedef struct {
 133     uint32_t _key;
 134     uint32_t _value;
 135 } __CFUniCharDecomposeMappings;
 136
 137 static uint32_t __CFUniCharGetMappedValue(const __CFUniCharDecomposeMappings *theTable, uint32_t numElem, UTF32Char character) {
 138     const __CFUniCharDecomposeMappings *p, *q, *divider;
 139
 140     if ((character < theTable[0]._key) || (character > theTable[numElem-1]._key)) {
 141         return 0;
 142     }
 143     p = theTable;
 144     q = p + (numElem-1);
 145     while (p <= q) {
 146         divider = p + ((q - p) >> 1);   /* divide by 2 */
 147         if (character < divider->_key) { q = divider - 1; }
 148         else if (character > divider->_key) { p = divider + 1; }
 149         else { return divider->_value; }
 150     }
 151     return 0;
 152 }
 153
 154 #if KERNEL
 155 #define __CFUniCharGetCombiningPropertyForCharacter(character) __CFUniCharGetCombiningPriority(character)
 156 #else KERNEL
 157 #define __CFUniCharGetCombiningPropertyForCharacter(character) CFUniCharGetCombiningPropertyForCharacter(character, (((character) >> 16) < __CFUniCharCombiningPriorityTableNumPlane ? __CFUniCharCombiningPriorityTable[(character) >> 16] : NULL))
 158 #endif KERNEL
 159
 160 static void __CFUniCharPrioritySort(UTF32Char *characters, uint32_t length) {
 161     uint32_t p1, p2;
 162     UTF32Char *ch1, *ch2;
 163     bool changes = true;
 164     UTF32Char *end = characters + length;
 165
 166 #if !KERNEL
 167     if (NULL == __CFUniCharCombiningPriorityTable) {
 168         __CFSpinLock(&__CFUniCharDecompositionTableLock);
 169         if (NULL == __CFUniCharCombiningPriorityTable) {
 170             uint32_t numPlanes = CFUniCharGetNumberOfPlanesForUnicodePropertyData(kCFUniCharCombiningProperty);
 171             uint32_t idx;
 172
 173             __CFUniCharCombiningPriorityTable = (const uint8_t **)CFAllocatorAllocate(NULL, sizeof(uint8_t *) * numPlanes, 0);
 174             for (idx = 0;idx < numPlanes;idx++) __CFUniCharCombiningPriorityTable[idx] = CFUniCharGetUnicodePropertyDataForPlane(kCFUniCharCombiningProperty, idx);
 175             __CFUniCharCombiningPriorityTableNumPlane = numPlanes;
 176         }
 177         __CFSpinUnlock(&__CFUniCharDecompositionTableLock);
 178     }
 179 #endif !KERNEL
 180
 181     if (length < 2) return;
 182
 183     do {
 184         changes = false;
 185         ch1 = characters; ch2 = characters + 1;
 186         p2 = __CFUniCharGetCombiningPropertyForCharacter(*ch1);
 187         while (ch2 < end) {
 188             p1 = p2; p2 = __CFUniCharGetCombiningPropertyForCharacter(*ch2);
 189             if (p1 > p2) {
 190                 UTF32Char tmp = *ch1; *ch1 = *ch2; *ch2 = tmp;
 191                 changes = true;
 192             }
 193             ++ch1; ++ch2;
 194         }
 195     } while (changes);
 196 }
 197
 198 static uint32_t __CFUniCharRecursivelyDecomposeCharacter(UTF32Char character, UTF32Char *convertedChars, uint32_t maxBufferLength) {
 199     uint32_t value = __CFUniCharGetMappedValue((const __CFUniCharDecomposeMappings *)__CFUniCharDecompositionTable, __CFUniCharDecompositionTableLength, character);
 200     uint32_t length = CFUniCharConvertFlagToCount(value);
 201     UTF32Char firstChar = value & 0xFFFFFF;
 202 #if KERNEL
 203     const UTF32Char *mappings = (kCFUniCharNonBmpFlag & value ? (length == 1 ? &firstChar : __CFUniCharNonBMPMultipleDecompositionTable + firstChar) : NULL);
 204     UTF16Char theChar = (UTF16Char)firstChar;
 205     const UTF16Char *bmpMappings = (mappings ? NULL : (length == 1 ? &theChar : __CFUniCharMultipleDecompositionTable + firstChar));
 206 #else KERNEL
 207     UTF32Char *mappings = (length > 1 ? __CFUniCharMultipleDecompositionTable + firstChar : &firstChar);
 208 #endif KERNEL
 209     uint32_t usedLength = 0;
 210
 211     if (maxBufferLength < length) return 0;
 212
 213 #if KERNEL
 214     if (bmpMappings) {
 215         if (value & kCFUniCharRecursiveDecompositionFlag) {
 216             usedLength = __CFUniCharRecursivelyDecomposeCharacter((UTF32Char)*bmpMappings, convertedChars, maxBufferLength - length);
 217
 218             --length; // Decrement for the first char
 219             if (!usedLength || usedLength + length > maxBufferLength) return 0;
 220             ++bmpMappings;
 221             convertedChars += usedLength;
 222         }
 223
 224         usedLength += length;
 225
 226         while (length--) *(convertedChars++) = *(bmpMappings++);
 227
 228         return usedLength;
 229     }
 230 #endif KERNEL
 231     if (value & kCFUniCharRecursiveDecompositionFlag) {
 232         usedLength = __CFUniCharRecursivelyDecomposeCharacter(*mappings, convertedChars, maxBufferLength - length);
 233
 234         --length; // Decrement for the first char
 235         if (!usedLength || usedLength + length > maxBufferLength) return 0;
 236         ++mappings;
 237         convertedChars += usedLength;
 238     }
 239
 240     usedLength += length;
 241
 242     while (length--) *(convertedChars++) = *(mappings++);
 243
 244     return usedLength;
 245 }
 246
 247 #define HANGUL_SBASE 0xAC00
 248 #define HANGUL_LBASE 0x1100
 249 #define HANGUL_VBASE 0x1161
 250 #define HANGUL_TBASE 0x11A7
 251 #define HANGUL_SCOUNT 11172
 252 #define HANGUL_LCOUNT 19
 253 #define HANGUL_VCOUNT 21
 254 #define HANGUL_TCOUNT 28
 255 #define HANGUL_NCOUNT (HANGUL_VCOUNT * HANGUL_TCOUNT)
 256
 257 uint32_t CFUniCharDecomposeCharacter(UTF32Char character, UTF32Char *convertedChars, uint32_t maxBufferLength) {
 258 #if !KERNEL
 259     if (NULL == __CFUniCharDecompositionTable) __CFUniCharLoadDecompositionTable();
 260 #endif !KERNEL
 261     if (character >= HANGUL_SBASE && character <= (HANGUL_SBASE + HANGUL_SCOUNT)) {
 262         uint32_t length;
 263
 264         character -= HANGUL_SBASE;
 265
 266         length = (character % HANGUL_TCOUNT ? 3 : 2);
 267
 268         if (maxBufferLength < length) return 0;
 269
 270         *(convertedChars++) = character / HANGUL_NCOUNT + HANGUL_LBASE;
 271         *(convertedChars++) = (character % HANGUL_NCOUNT) / HANGUL_TCOUNT + HANGUL_VBASE;
 272         if (length > 2) *convertedChars = (character % HANGUL_TCOUNT) + HANGUL_TBASE;
 273         return length;
 274     } else {
 275         return __CFUniCharRecursivelyDecomposeCharacter(character, convertedChars, maxBufferLength);
 276     }
 277 }
 278
 279 #if KERNEL
 280 #define CFAllocatorAllocate(a,size,flag)        malloc((size))
 281 #define CFAllocatorDeallocate(a,ptr)            free((ptr))
 282 #endif KERNEL
 283
 284 #define MAX_BUFFER_LENGTH (32)
 285 bool CFUniCharDecompose(const UTF16Char *src, uint32_t length, uint32_t *consumedLength, void *dst, uint32_t maxLength, uint32_t *filledLength, bool needToReorder, uint32_t dstFormat, bool isHFSPlus) {
 286     uint32_t usedLength = 0;
 287     uint32_t originalLength = length;
 288     UTF32Char buffer[MAX_BUFFER_LENGTH];
 289     UTF32Char *decompBuffer = buffer;
 290     uint32_t decompBufferLen = MAX_BUFFER_LENGTH;
 291     UTF32Char currentChar;
 292     uint32_t idx;
 293     bool isDecomp = false;
 294     bool isNonBase = false;
 295
 296 #if !KERNEL
 297     if (NULL == __CFUniCharDecompositionTable) __CFUniCharLoadDecompositionTable();
 298 #endif !KERNEL
 299
 300     while (length > 0) {
 301         currentChar = *(src++);
 302         --length;
 303
 304         if (currentChar < 0x80) {
 305             if (maxLength) {
 306                 if (usedLength < maxLength) {
 307                     switch (dstFormat) {
 308                         case kCFUniCharUTF8Format: *(((uint8_t *)dst)++) = currentChar; break;
 309                         case kCFUniCharUTF16Format: *(((UTF16Char *)dst)++) = currentChar; break;
 310                         case kCFUniCharUTF32Format: *(((UTF32Char *)dst)++) = currentChar; break;
 311                     }
 312                 } else {
 313                     if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 314                     if (consumedLength) *consumedLength = originalLength - length - 1;
 315                     if (filledLength) *filledLength = usedLength;
 316                     return false;
 317                 }
 318             }
 319             ++usedLength;
 320             continue;
 321         }
 322
 323         if (CFUniCharIsSurrogateHighCharacter(currentChar) && (length > 0) && CFUniCharIsSurrogateLowCharacter(*src)) {
 324             currentChar = CFUniCharGetLongCharacterForSurrogatePair(currentChar, *(src++));
 325             --length;
 326         }
 327
 328         isDecomp = __CFUniCharIsDecomposableCharacterWithFlag(currentChar, isHFSPlus);
 329         isNonBase = (needToReorder && __CFUniCharIsNonBaseCharacter(currentChar));
 330
 331         if (!isDecomp || isNonBase) {
 332             if (isNonBase) {
 333                 if (isDecomp) {
 334                     idx = CFUniCharDecomposeCharacter(currentChar, decompBuffer, MAX_BUFFER_LENGTH);
 335                 } else {
 336                     idx = 1;
 337                     *decompBuffer = currentChar;
 338                 }
 339
 340                 while (length > 0) {
 341                     if (CFUniCharIsSurrogateHighCharacter(*src) && ((length + 1) > 0) && CFUniCharIsSurrogateLowCharacter(*(src + 1))) {
 342                         currentChar = CFUniCharGetLongCharacterForSurrogatePair(*src, *(src + 1));
 343                     } else {
 344                         currentChar = *src;
 345                     }
 346                     if (__CFUniCharIsNonBaseCharacter(currentChar)) {
 347                         if (currentChar > 0xFFFF) { // Non-BMP
 348                             length -= 2;
 349                             src += 2;
 350                         } else {
 351                             --length;
 352                             ++src;
 353                         }
 354                         if ((idx + 1) >= decompBufferLen) {
 355                             UTF32Char *newBuffer;
 356
 357                             decompBufferLen += MAX_BUFFER_LENGTH;
 358                             newBuffer = (UTF32Char *)CFAllocatorAllocate(NULL, sizeof(UTF32Char) * decompBufferLen, 0);
 359                             memmove(newBuffer, decompBuffer, (decompBufferLen - MAX_BUFFER_LENGTH) * sizeof(UTF32Char));
 360                             if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 361                             decompBuffer = newBuffer;
 362                         }
 363
 364                         if (__CFUniCharIsDecomposableCharacterWithFlag(currentChar, isHFSPlus)) { // Vietnamese accent, etc.
 365                             idx += CFUniCharDecomposeCharacter(currentChar, decompBuffer + idx, MAX_BUFFER_LENGTH - idx);
 366                         } else {
 367                             decompBuffer[idx++] = currentChar;
 368                         }
 369                     } else {
 370                         break;
 371                     }
 372                 }
 373
 374                 if (idx > 1) { // Need to reorder
 375                     __CFUniCharPrioritySort(decompBuffer, idx);
 376                 }
 377                 if (!CFUniCharFillDestinationBuffer(decompBuffer, idx, &dst, maxLength, &usedLength, dstFormat)) {
 378                     if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 379                     if (consumedLength) *consumedLength = originalLength - length;
 380                     if (filledLength) *filledLength = usedLength;
 381                     return false;
 382                 }
 383             } else {
 384                 if (dstFormat == kCFUniCharUTF32Format) {
 385                     ++usedLength;
 386                     if (maxLength) {
 387                         if (usedLength > maxLength) {
 388                             if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 389                             if (consumedLength) *consumedLength = originalLength - length;
 390                             if (filledLength) *filledLength = usedLength;
 391                             return false;
 392                         }
 393                         *(((UTF32Char *)dst)++) = currentChar;
 394                     }
 395                 } else {
 396                     if (!CFUniCharFillDestinationBuffer(&currentChar, 1, &dst, maxLength, &usedLength, dstFormat)) {
 397                         if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 398                         if (consumedLength) *consumedLength = originalLength - length;
 399                         if (filledLength) *filledLength = usedLength;
 400                         return false;
 401                     }
 402                 }
 403             }
 404         } else {
 405             if (dstFormat == kCFUniCharUTF32Format && maxLength) {
 406                 idx = CFUniCharDecomposeCharacter(currentChar, dst, maxLength - usedLength);
 407
 408                 if (idx == 0) {
 409                     if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 410                     if (consumedLength) *consumedLength = originalLength - length;
 411                     if (filledLength) *filledLength = usedLength;
 412                     return false;
 413                 } else if (needToReorder && (idx > 1)) { // Need to reorder
 414                     bool moreCombiningMarks = false;
 415                     ++((UTF32Char *)dst); --idx; ++usedLength; // Skip the base
 416
 417                     while (length > 0) {
 418                         if (CFUniCharIsSurrogateHighCharacter(*src) && ((length + 1) > 0) && CFUniCharIsSurrogateLowCharacter(*(src + 1))) {
 419                             currentChar = CFUniCharGetLongCharacterForSurrogatePair(*src, *(src + 1));
 420                         } else {
 421                             currentChar = *src;
 422                         }
 423                         if (__CFUniCharIsNonBaseCharacter(currentChar)) {
 424                             if (currentChar > 0xFFFF) { // Non-BMP
 425                                 length -= 2;
 426                                 src += 2;
 427                             } else {
 428                                 --length;
 429                                 ++src;
 430                             }
 431                             if ((idx + usedLength + 1) >= maxLength) {
 432                                 if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 433                                 if (consumedLength) *consumedLength = originalLength - length;
 434                                 if (filledLength) *filledLength = usedLength;
 435                                 return false;
 436                             }
 437                             ((UTF32Char *)dst)[idx++] = currentChar;
 438                             moreCombiningMarks = true;
 439                         } else {
 440                             break;
 441                         }
 442                     }
 443                     if (moreCombiningMarks) __CFUniCharPrioritySort(((UTF32Char *)dst), idx);
 444
 445                 }
 446                 usedLength += idx;
 447                 ((UTF32Char *)dst) += idx;
 448             } else {
 449                 idx = CFUniCharDecomposeCharacter(currentChar, decompBuffer, decompBufferLen);
 450
 451                 if (maxLength && idx + usedLength > maxLength) {
 452                     if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 453                     if (consumedLength) *consumedLength = originalLength - length;
 454                     if (filledLength) *filledLength = usedLength;
 455                     return false;
 456                 } else if (needToReorder && (idx > 1)) { // Need to reorder
 457                     bool moreCombiningMarks = false;
 458
 459                     while (length > 0) {
 460                         if (CFUniCharIsSurrogateHighCharacter(*src) && ((length + 1) > 0) && CFUniCharIsSurrogateLowCharacter(*(src + 1))) {
 461                             currentChar = CFUniCharGetLongCharacterForSurrogatePair(*src, *(src + 1));
 462                         } else {
 463                             currentChar = *src;
 464                         }
 465                         if (__CFUniCharIsNonBaseCharacter(currentChar)) {
 466                             if (currentChar > 0xFFFF) { // Non-BMP
 467                                 length -= 2;
 468                                 src += 2;
 469                             } else {
 470                                 --length;
 471                                 ++src;
 472                             }
 473                             if ((idx + 1) >= decompBufferLen) {
 474                                 UTF32Char *newBuffer;
 475
 476                                 decompBufferLen += MAX_BUFFER_LENGTH;
 477                                 newBuffer = (UTF32Char *)CFAllocatorAllocate(NULL, sizeof(UTF32Char) * decompBufferLen, 0);
 478                                 memmove(newBuffer, decompBuffer, (decompBufferLen - MAX_BUFFER_LENGTH) * sizeof(UTF32Char));
 479                                 if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 480                                 decompBuffer = newBuffer;
 481                             }
 482                             decompBuffer[idx++] = currentChar;
 483                             moreCombiningMarks = true;
 484                         } else {
 485                             break;
 486                         }
 487                     }
 488                     if (moreCombiningMarks) __CFUniCharPrioritySort(decompBuffer + 1, idx - 1);
 489                 }
 490                 if (!CFUniCharFillDestinationBuffer(decompBuffer, idx, &dst, maxLength, &usedLength, dstFormat)) {
 491                     if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 492                     if (consumedLength) *consumedLength = originalLength - length;
 493                     if (filledLength) *filledLength = usedLength;
 494                     return false;
 495                 }
 496             }
 497         }
 498     }
 499     if (decompBuffer != buffer) CFAllocatorDeallocate(NULL, decompBuffer);
 500
 501     if (consumedLength) *consumedLength = originalLength - length;
 502     if (filledLength) *filledLength = usedLength;
 503
 504     return true;
 505 }
 506
 507 #if !KERNEL
 508
 509 #define MAX_COMP_DECOMP_LEN (32)
 510
 511 static uint32_t __CFUniCharRecursivelyCompatibilityDecomposeCharacter(UTF32Char character, UTF32Char *convertedChars) {
 512     uint32_t value = __CFUniCharGetMappedValue((const __CFUniCharDecomposeMappings *)__CFUniCharCompatibilityDecompositionTable, __CFUniCharCompatibilityDecompositionTableLength, character);
 513     uint32_t length = CFUniCharConvertFlagToCount(value);
 514     UTF32Char firstChar = value & 0xFFFFFF;
 515     const UTF32Char *mappings = (length > 1 ? __CFUniCharCompatibilityMultipleDecompositionTable + firstChar : &firstChar);
 516     uint32_t usedLength = length;
 517     UTF32Char currentChar;
 518     uint32_t currentLength;
 519
 520     while (length-- > 0) {
 521         currentChar = *(mappings++);
 522         if (__CFUniCharIsDecomposableCharacterWithFlag(currentChar, false)) {
 523             currentLength = __CFUniCharRecursivelyDecomposeCharacter(currentChar, convertedChars, MAX_COMP_DECOMP_LEN - length);
 524             convertedChars += currentLength;
 525             usedLength += (currentLength - 1);
 526         } else if (CFUniCharIsMemberOf(currentChar, kCFUniCharCompatibilityDecomposableCharacterSet)) {
 527             currentLength = __CFUniCharRecursivelyCompatibilityDecomposeCharacter(currentChar, convertedChars);
 528             convertedChars += currentLength;
 529             usedLength += (currentLength - 1);
 530         } else {
 531             *(convertedChars++) = currentChar;
 532         }
 533     }
 534
 535     return usedLength;
 536 }
 537
 538 CF_INLINE void __CFUniCharMoveBufferFromEnd(UTF32Char *convertedChars, uint32_t length, uint32_t delta) {
 539     const UTF32Char *limit = convertedChars;
 540     UTF32Char *dstP;
 541
 542     convertedChars += length;
 543     dstP = convertedChars + delta;
 544
 545     while (convertedChars > limit) *(--dstP) = *(--convertedChars);
 546 }
 547
 548 __private_extern__ uint32_t CFUniCharCompatibilityDecompose(UTF32Char *convertedChars, uint32_t length, uint32_t maxBufferLength) {
 549     UTF32Char currentChar;
 550     UTF32Char buffer[MAX_COMP_DECOMP_LEN];
 551     const UTF32Char *bufferP;
 552     const UTF32Char *limit = convertedChars + length;
 553     uint32_t filledLength;
 554
 555     if (NULL == __CFUniCharCompatibilityDecompositionTable) __CFUniCharLoadCompatibilityDecompositionTable();
 556
 557     while (convertedChars < limit) {
 558         currentChar = *convertedChars;
 559
 560         if (CFUniCharIsMemberOf(currentChar, kCFUniCharCompatibilityDecomposableCharacterSet)) {
 561             filledLength = __CFUniCharRecursivelyCompatibilityDecomposeCharacter(currentChar, buffer);
 562
 563             if (filledLength + length - 1 > maxBufferLength) return 0;
 564
 565             if (filledLength > 1) __CFUniCharMoveBufferFromEnd(convertedChars + 1, limit - convertedChars - 1, filledLength - 1);
 566
 567             bufferP = buffer;
 568             length += (filledLength - 1);
 569             while (filledLength-- > 0) *(convertedChars++) = *(bufferP++);
 570         } else {
 571             ++convertedChars;
 572         }
 573     }
 574
 575     return length;
 576 }
 577
 578 CF_EXPORT void CFUniCharPrioritySort(UTF32Char *characters, uint32_t length) {
 579     __CFUniCharPrioritySort(characters, length);
 580 }
 581 #endif !KERNEL