CFData.c

   1 /*
   2  * Copyright (c) 2015 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 /*      CFData.c
  25         Copyright (c) 1998-2014, Apple Inc. All rights reserved.
  26         Responsibility: Kevin Perry
  27 */
  28
  29 #include <CoreFoundation/CFData.h>
  30 #include <CoreFoundation/CFPriv.h>
  31 #include "CFInternal.h"
  32 #include <string.h>
  33
  34
  35
  36 #if __LP64__
  37 #define CFDATA_MAX_SIZE     ((1ULL << 42) - 1)
  38 #else
  39 #define CFDATA_MAX_SIZE     ((1ULL << 31) - 1)
  40 #endif
  41
  42 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_EMBEDDED_MINI
  43 #import <mach/mach.h>
  44 CF_INLINE unsigned long __CFPageSize() { return vm_page_size; }
  45 #elif DEPLOYMENT_TARGET_WINDOWS
  46 CF_INLINE unsigned long __CFPageSize() {
  47     SYSTEM_INFO sysInfo;
  48     GetSystemInfo(&sysInfo);
  49     return sysInfo.dwPageSize;
  50 }
  51 #elif DEPLOYMENT_TARGET_LINUX
  52 #include <unistd.h>
  53 CF_INLINE unsigned long __CFPageSize() {
  54     return (unsigned long)getpagesize();
  55 }
  56 #endif
  57
  58 #define INLINE_BYTES_THRESHOLD ((4 * __CFPageSize()) - sizeof(struct __CFData) - 15)
  59
  60 struct __CFData {
  61     CFRuntimeBase _base;
  62     CFIndex _length;    /* number of bytes */
  63     CFIndex _capacity;  /* maximum number of bytes */
  64     CFAllocatorRef _bytesDeallocator;   /* used only for immutable; if NULL, no deallocation */
  65     uint8_t *_bytes;    /* compaction: direct access to _bytes is only valid when data is not inline */
  66 };
  67
  68 /*
  69  Bit 0 = is mutable
  70  Bit 1 = growable
  71  Bit 2 = bytes inline
  72  Bit 3 = use given CFAllocator
  73  Bit 5 = allocate collectable memory
  74
  75  Bits 1-0 are used for mutability variation
  76
  77  Bit 6 = not all bytes have been zeroed yet (mutable)
  78  */
  79
  80 enum {
  81     __kCFMutable = 0x01,
  82     __kCFGrowable = 0x02,
  83     __kCFMutableVarietyMask = 0x03,
  84     __kCFBytesInline = 0x04,
  85     __kCFUseAllocator = 0x08,
  86     __kCFAllocatesCollectable = 0x20,
  87 };
  88
  89 enum {
  90     kCFImmutable = 0x0,         /* unchangable and fixed capacity; default */
  91     kCFFixedMutable = 0x1,      /* changeable and fixed capacity */
  92     kCFMutable = 0x3            /* changeable and variable capacity */
  93 };
  94
  95 CF_INLINE void __CFDataSetInfoBits(CFDataRef data, UInt32 v) {__CFBitfieldSetValue(((CFRuntimeBase *)data)->_cfinfo[CF_INFO_BITS], 5, 0, v);}
  96 CF_INLINE Boolean __CFDataGetInfoBit(CFDataRef data, UInt32 b) {return ((((const CFRuntimeBase *)data)->_cfinfo[CF_INFO_BITS] & b) != 0);}
  97 CF_INLINE Boolean __CFDataIsMutable(CFDataRef data) {return __CFDataGetInfoBit(data, __kCFMutable);}
  98 CF_INLINE Boolean __CFDataIsGrowable(CFDataRef data) {return __CFDataGetInfoBit(data, __kCFGrowable);}
  99 CF_INLINE Boolean __CFDataBytesInline(CFDataRef data) {return __CFDataGetInfoBit(data, __kCFBytesInline);}
 100 CF_INLINE Boolean __CFDataUseAllocator(CFDataRef data) {return __CFDataGetInfoBit(data, __kCFUseAllocator);}
 101 CF_INLINE Boolean __CFDataAllocatesCollectable(CFDataRef data) {return __CFDataGetInfoBit(data, __kCFAllocatesCollectable);}
 102
 103 CF_INLINE UInt32 __CFMutableVariety(const void *cf) {
 104     return __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 1, 0);
 105 }
 106
 107 CF_INLINE void __CFSetMutableVariety(void *cf, UInt32 v) {
 108     __CFBitfieldSetValue(((CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 1, 0, v);
 109 }
 110
 111 CF_INLINE UInt32 __CFMutableVarietyFromFlags(UInt32 flags) {
 112     return (flags & __kCFMutableVarietyMask);
 113 }
 114
 115 #define __CFGenericValidateMutabilityFlags(flags) \
 116     CFAssert2(__CFMutableVarietyFromFlags(flags) != 0x2, __kCFLogAssertion, "%s(): flags 0x%x do not correctly specify the mutable variety", __PRETTY_FUNCTION__, flags);
 117
 118 CF_INLINE void __CFDataSetInline(CFDataRef data, Boolean flag) {
 119     __CFBitfieldSetValue(((CFRuntimeBase *)data)->_cfinfo[CF_INFO_BITS], 2, 2, (flag ? 1 : 0));
 120 }
 121
 122 CF_INLINE Boolean __CFDataNeedsToZero(CFDataRef data) {
 123     return __CFBitfieldGetValue(((CFRuntimeBase *)data)->_cfinfo[CF_INFO_BITS], 6, 6);
 124 }
 125
 126 CF_INLINE void __CFDataSetNeedsToZero(CFDataRef data, Boolean zero) {
 127     __CFBitfieldSetValue(((CFRuntimeBase *)data)->_cfinfo[CF_INFO_BITS], 6, 6, (zero ? 1 : 0));
 128 }
 129
 130 CF_INLINE CFIndex __CFDataLength(CFDataRef data) {
 131     return data->_length;
 132 }
 133
 134 CF_INLINE void __CFDataSetLength(CFMutableDataRef data, CFIndex v) {
 135     /* for a CFData, _bytesUsed == _length */
 136 }
 137
 138 CF_INLINE CFIndex __CFDataCapacity(CFDataRef data) {
 139     return data->_capacity;
 140 }
 141
 142 CF_INLINE void __CFDataSetCapacity(CFMutableDataRef data, CFIndex v) {
 143     /* for a CFData, _bytesNum == _capacity */
 144 }
 145
 146 CF_INLINE void __CFDataSetNumBytesUsed(CFMutableDataRef data, CFIndex v) {
 147     data->_length = v;
 148 }
 149
 150 CF_INLINE CFIndex __CFDataNumBytes(CFDataRef data) {
 151     return data->_capacity;
 152 }
 153
 154 CF_INLINE void __CFDataSetNumBytes(CFMutableDataRef data, CFIndex v) {
 155     data->_capacity = v;
 156 }
 157
 158 #if __LP64__
 159 #define CHUNK_SIZE (1ULL << 29)
 160 #define LOW_THRESHOLD (1ULL << 20)
 161 #define HIGH_THRESHOLD (1ULL << 32)
 162 #else
 163 #define CHUNK_SIZE (1ULL << 26)
 164 #define LOW_THRESHOLD (1ULL << 20)
 165 #define HIGH_THRESHOLD (1ULL << 29)
 166 #endif
 167
 168 CF_INLINE CFIndex __CFDataRoundUpCapacity(CFIndex capacity) {
 169     if (capacity < 16) {
 170         return 16;
 171     } else if (capacity < LOW_THRESHOLD) {
 172         /* Up to 4x */
 173         long idx = flsl(capacity);
 174         return (1L << (long)(idx + ((idx % 2 == 0) ? 0 : 1)));
 175     } else if (capacity < HIGH_THRESHOLD) {
 176         /* Up to 2x */
 177         return (1L << (long)flsl(capacity));
 178     } else {
 179         /* Round up to next multiple of CHUNK_SIZE */
 180         unsigned long newCapacity = CHUNK_SIZE * (1+(capacity >> ((long)flsl(CHUNK_SIZE)-1)));
 181         return __CFMin(newCapacity, CFDATA_MAX_SIZE);
 182     }
 183 }
 184
 185 CF_INLINE CFIndex __CFDataNumBytesForCapacity(CFIndex capacity) {
 186     return capacity;
 187 }
 188
 189 static void __CFDataHandleOutOfMemory(CFTypeRef obj, CFIndex numBytes) {
 190     CFStringRef msg;
 191     if(0 < numBytes && numBytes <= CFDATA_MAX_SIZE) {
 192         msg = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("Attempt to allocate %ld bytes for NS/CFData failed"), numBytes);
 193     } else {
 194         msg = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("Attempt to allocate %ld bytes for NS/CFData failed. Maximum size: %lld"), numBytes, CFDATA_MAX_SIZE);
 195     }
 196     {
 197         CFLog(kCFLogLevelCritical, CFSTR("%@"), msg);
 198         HALT;
 199     }
 200     CFRelease(msg);
 201 }
 202
 203 #if defined(DEBUG)
 204 CF_INLINE void __CFDataValidateRange(CFDataRef data, CFRange range, const char *func) {
 205     CFAssert2(0 <= range.location && range.location <= __CFDataLength(data), __kCFLogAssertion, "%s(): range.location index (%d) out of bounds", func, range.location);
 206     CFAssert2(0 <= range.length, __kCFLogAssertion, "%s(): length (%d) cannot be less than zero", func, range.length);
 207     CFAssert2(range.location + range.length <= __CFDataLength(data), __kCFLogAssertion, "%s(): ending index (%d) out of bounds", func, range.location + range.length);
 208 }
 209 #else
 210 #define __CFDataValidateRange(a,r,f)
 211 #endif
 212
 213 static Boolean __CFDataEqual(CFTypeRef cf1, CFTypeRef cf2) {
 214     CFDataRef data1 = (CFDataRef)cf1;
 215     CFDataRef data2 = (CFDataRef)cf2;
 216     CFIndex length;
 217     length = __CFDataLength(data1);
 218     if (length != __CFDataLength(data2)) return false;
 219     const uint8_t *bytePtr1 = CFDataGetBytePtr(data1);
 220     const uint8_t *bytePtr2 = CFDataGetBytePtr(data2);
 221     return 0 == memcmp(bytePtr1, bytePtr2, length);
 222 }
 223
 224 static CFHashCode __CFDataHash(CFTypeRef cf) {
 225     CFDataRef data = (CFDataRef)cf;
 226     return CFHashBytes((uint8_t *)CFDataGetBytePtr(data), __CFMin(__CFDataLength(data), 80));
 227 }
 228
 229 static CFStringRef __CFDataCopyDescription(CFTypeRef cf) {
 230     CFDataRef data = (CFDataRef)cf;
 231     CFMutableStringRef result;
 232     CFIndex idx;
 233     CFIndex len;
 234     const uint8_t *bytes;
 235     len = __CFDataLength(data);
 236     bytes = CFDataGetBytePtr(data);
 237     result = CFStringCreateMutable(CFGetAllocator(data), 0);
 238     CFStringAppendFormat(result, NULL, CFSTR("<CFData %p [%p]>{length = %lu, capacity = %lu, bytes = 0x"), cf, CFGetAllocator(data), (unsigned long)len, (unsigned long)__CFDataCapacity(data));
 239     if (24 < len) {
 240         for (idx = 0; idx < 16; idx += 4) {
 241             CFStringAppendFormat(result, NULL, CFSTR("%02x%02x%02x%02x"), bytes[idx], bytes[idx + 1], bytes[idx + 2], bytes[idx + 3]);
 242         }
 243         CFStringAppend(result, CFSTR(" ... "));
 244         for (idx = len - 8; idx < len; idx += 4) {
 245             CFStringAppendFormat(result, NULL, CFSTR("%02x%02x%02x%02x"), bytes[idx], bytes[idx + 1], bytes[idx + 2], bytes[idx + 3]);
 246         }
 247     } else {
 248         for (idx = 0; idx < len; idx++) {
 249             CFStringAppendFormat(result, NULL, CFSTR("%02x"), bytes[idx]);
 250         }
 251     }
 252     CFStringAppend(result, CFSTR("}"));
 253     return result;
 254 }
 255
 256 static void *__CFDataInlineBytesPtr(CFDataRef data) {
 257     return (void *)((uintptr_t)((int8_t *)data + sizeof(struct __CFData) + 15) & ~0xF); // 16-byte align
 258 }
 259
 260 static Boolean __CFDataShouldAllocateCleared(CFDataRef data, CFIndex size) {
 261     Boolean result;
 262     if (__CFDataUseAllocator(data)) {
 263         result = false;
 264     } else {
 265         if (__CFDataAllocatesCollectable(data)) {
 266 #if __LP64__
 267             result = false;
 268 #else
 269             result = (size > (64 * 1024));
 270 #endif
 271         } else {
 272             result = (size > (128 * 1024));
 273         }
 274     }
 275     return result;
 276 }
 277
 278
 279 // Check __CFDataShouldAllocateCleared before passing true.
 280 static void *__CFDataAllocate(CFDataRef data, CFIndex size, Boolean clear) {
 281     void *bytes = NULL;
 282     if (__CFDataUseAllocator(data)) {
 283         CFAllocatorRef allocator = __CFGetAllocator(data);
 284         bytes = CFAllocatorAllocate(allocator, size, 0);
 285         if (clear) memset((uint8_t *)bytes, 0, size);
 286     } else {
 287         if (__CFDataAllocatesCollectable(data)) {
 288             bytes = auto_zone_allocate_object(objc_collectableZone(), size, AUTO_MEMORY_UNSCANNED, 0, clear);
 289         } else {
 290             if (clear) {
 291                 bytes = calloc(1, size);
 292             } else {
 293                 bytes = malloc(size);
 294             }
 295         }
 296     }
 297     return bytes;
 298 }
 299
 300 static void __CFDataDeallocate(CFTypeRef cf) {
 301     CFMutableDataRef data = (CFMutableDataRef)cf;
 302     if (!__CFDataBytesInline(data)) {
 303         CFAllocatorRef deallocator = data->_bytesDeallocator;
 304         if (deallocator != NULL) {
 305             _CFAllocatorDeallocateGC(deallocator, data->_bytes);
 306             CFRelease(deallocator);
 307             data->_bytes = NULL;
 308         } else {
 309             if (__CFDataUseAllocator(data)) {
 310                 _CFAllocatorDeallocateGC(__CFGetAllocator(data), data->_bytes);
 311             } else if (!__CFDataAllocatesCollectable(data) && data->_bytes) {
 312                 free(data->_bytes);
 313             }
 314             data->_bytes = NULL;
 315         }
 316     }
 317 }
 318
 319 static CFTypeID __kCFDataTypeID = _kCFRuntimeNotATypeID;
 320
 321 static const CFRuntimeClass __CFDataClass = {
 322     _kCFRuntimeScannedObject,
 323     "CFData",
 324     NULL,       // init
 325     NULL,       // copy
 326     __CFDataDeallocate,
 327     __CFDataEqual,
 328     __CFDataHash,
 329     NULL,       //
 330     __CFDataCopyDescription
 331 };
 332
 333 CFTypeID CFDataGetTypeID(void) {
 334     static dispatch_once_t initOnce;
 335     dispatch_once(&initOnce, ^{ __kCFDataTypeID = _CFRuntimeRegisterClass(&__CFDataClass); });
 336     return __kCFDataTypeID;
 337 }
 338
 339
 340 // NULL bytesDeallocator to this function does not mean the default allocator, it means
 341 // that there should be no deallocator, and the bytes should be copied.
 342 static CFMutableDataRef __CFDataInit(CFAllocatorRef allocator, CFOptionFlags flags, CFIndex capacity, const uint8_t *bytes, CFIndex length, CFAllocatorRef bytesDeallocator) {
 343     CFMutableDataRef memory;
 344     __CFGenericValidateMutabilityFlags(flags);
 345     CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
 346     CFAssert3(kCFFixedMutable != __CFMutableVarietyFromFlags(flags) || length <= capacity, __kCFLogAssertion, "%s(): for kCFFixedMutable type, capacity (%d) must be greater than or equal to number of initial elements (%d)", __PRETTY_FUNCTION__, capacity, length);
 347     CFAssert2(0 <= length, __kCFLogAssertion, "%s(): length (%d) cannot be less than zero", __PRETTY_FUNCTION__, length);
 348
 349     Boolean collectableMemory = CF_IS_COLLECTABLE_ALLOCATOR(allocator);
 350     Boolean noCopy = bytesDeallocator != NULL;
 351     Boolean isMutable = ((flags & __kCFMutable) != 0);
 352     Boolean isGrowable = ((flags & __kCFGrowable) != 0);
 353     Boolean allocateInline = !isGrowable && !noCopy && capacity < INLINE_BYTES_THRESHOLD;
 354     allocator = (allocator == NULL) ? __CFGetDefaultAllocator() : allocator;
 355     Boolean useAllocator = (allocator != kCFAllocatorSystemDefault && allocator != kCFAllocatorMalloc && allocator != kCFAllocatorMallocZone);
 356
 357     CFIndex size = sizeof(struct __CFData) - sizeof(CFRuntimeBase);
 358     if (allocateInline) {
 359         size += sizeof(uint8_t) * __CFDataNumBytesForCapacity(capacity) + sizeof(uint8_t) * 15; // for 16-byte alignment fixup
 360     }
 361     memory = (CFMutableDataRef)_CFRuntimeCreateInstance(allocator, CFDataGetTypeID(), size, NULL);
 362     if (NULL == memory) {
 363         return NULL;
 364     }
 365     __CFDataSetNumBytesUsed(memory, 0);
 366     __CFDataSetLength(memory, 0);
 367     __CFDataSetInfoBits(memory,
 368                         (allocateInline ? __kCFBytesInline : 0) |
 369                         (useAllocator ? __kCFUseAllocator : 0) |
 370                         (collectableMemory ? __kCFAllocatesCollectable : 0));
 371
 372     BOOL finalize = YES;
 373     BOOL scan = YES;
 374     if (collectableMemory) {
 375         if (allocateInline) {
 376             // We have no pointer to anything that needs to be reclaimed, so don't scan or finalize.
 377             scan = NO;
 378             finalize = NO;
 379         } else if (noCopy) {
 380             if (CF_IS_COLLECTABLE_ALLOCATOR(bytesDeallocator)) {
 381                 // We're taking responsibility for externally GC-allocated memory, so scan us, but we don't need to finalize.
 382                 finalize = NO;
 383             } else if (bytesDeallocator == kCFAllocatorNull) {
 384                 // We don't have responsibility for these bytes, so there's no need to be scanned and we don't need to finalize.
 385                 scan = NO;
 386                 finalize = NO;
 387             } else {
 388                 // We have a pointer to non-GC-allocated memory, so don't scan, but do finalize.
 389                 scan = NO;
 390             }
 391         }
 392         if (!scan) auto_zone_set_unscanned(objc_collectableZone(), memory);
 393         if (!finalize) auto_zone_set_nofinalize(objc_collectableZone(), memory);
 394     }
 395     if (isMutable && isGrowable) {
 396         __CFDataSetCapacity(memory, __CFDataRoundUpCapacity(1));
 397         __CFDataSetNumBytes(memory, __CFDataNumBytesForCapacity(__CFDataRoundUpCapacity(1)));
 398         __CFSetMutableVariety(memory, kCFMutable);
 399     } else {
 400         /* Don't round up capacity */
 401         __CFDataSetCapacity(memory, capacity);
 402         __CFDataSetNumBytes(memory, __CFDataNumBytesForCapacity(capacity));
 403         __CFSetMutableVariety(memory, kCFFixedMutable);
 404     }
 405     if (noCopy) {
 406         __CFAssignWithWriteBarrier((void **)&memory->_bytes, (uint8_t *)bytes);
 407         if (finalize) {
 408             if ((0)) {
 409                 memory->_bytesDeallocator = bytesDeallocator;
 410             } else {
 411                 memory->_bytesDeallocator = (CFAllocatorRef)CFRetain(bytesDeallocator);
 412             }
 413         }
 414         if (CF_IS_COLLECTABLE_ALLOCATOR(bytesDeallocator) && !(0)) {
 415             // we assume that the no-copy memory is GC-allocated with a retain count of (at least) 1 and we should release it now instead of waiting until __CFDataDeallocate.
 416             auto_zone_release(objc_collectableZone(), memory->_bytes);
 417         }
 418         __CFDataSetNumBytesUsed(memory, length);
 419         __CFDataSetLength(memory, length);
 420         // Mutable no-copy datas are not allowed, so don't bother setting needsToZero flag.
 421     } else {
 422         Boolean cleared = (isMutable && !isGrowable && !_CFExecutableLinkedOnOrAfter(CFSystemVersionSnowLeopard));
 423         if (!allocateInline) {
 424             // assume that allocators give 16-byte aligned memory back -- it is their responsibility
 425             __CFAssignWithWriteBarrier((void **)&memory->_bytes, __CFDataAllocate(memory, __CFDataNumBytes(memory) * sizeof(uint8_t), cleared));
 426             if (__CFOASafe) __CFSetLastAllocationEventName(memory->_bytes, "CFData (store)");
 427             if (NULL == memory->_bytes) {
 428                 CFRelease(memory);
 429                 return NULL;
 430             }
 431         } else {
 432             if (length == 0 && !isMutable) {
 433                 // NSData sets its bytes pointer to NULL when its length is zero. Starting in 10.7 we do the same for CFData.
 434                 memory->_bytes = NULL;
 435                 // It is important to set this data as not inlined, so we do not recalculate a bytes pointer from null.
 436                 __CFDataSetInline(memory, false);
 437             }
 438             cleared = true;
 439         }
 440         __CFDataSetNeedsToZero(memory, !cleared);
 441         memory->_bytesDeallocator = NULL;
 442         CFDataReplaceBytes(memory, CFRangeMake(0, 0), bytes, length);
 443     }
 444     __CFSetMutableVariety(memory, __CFMutableVarietyFromFlags(flags));
 445     return memory;
 446 }
 447
 448 CFDataRef CFDataCreate(CFAllocatorRef allocator, const uint8_t *bytes, CFIndex length) {
 449     return __CFDataInit(allocator, kCFImmutable, length, bytes, length, NULL);
 450 }
 451
 452 CFDataRef CFDataCreateWithBytesNoCopy(CFAllocatorRef allocator, const uint8_t *bytes, CFIndex length, CFAllocatorRef bytesDeallocator) {
 453     CFAssert1((0 == length || bytes != NULL), __kCFLogAssertion, "%s(): bytes pointer cannot be NULL if length is non-zero", __PRETTY_FUNCTION__);
 454     if (NULL == bytesDeallocator) bytesDeallocator = __CFGetDefaultAllocator();
 455     return __CFDataInit(allocator, kCFImmutable, length, bytes, length, bytesDeallocator);
 456 }
 457
 458 CFDataRef CFDataCreateCopy(CFAllocatorRef allocator, CFDataRef data) {
 459     CFIndex length = CFDataGetLength(data);
 460     return __CFDataInit(allocator, kCFImmutable, length, CFDataGetBytePtr(data), length, NULL);
 461 }
 462
 463 CFMutableDataRef CFDataCreateMutable(CFAllocatorRef allocator, CFIndex capacity) {
 464     // Do not allow magic allocator for now for mutable datas, because it
 465     // isn't remembered for proper handling later when growth of the buffer
 466     // has to occur.
 467     Boolean wasMagic = (0);
 468     CFMutableDataRef r = (CFMutableDataRef)__CFDataInit(allocator, (0 == capacity) ? kCFMutable : kCFFixedMutable, capacity, NULL, 0, NULL);
 469     if (wasMagic) CFMakeCollectable(r);
 470     return r;
 471 }
 472
 473 CFMutableDataRef CFDataCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFDataRef data) {
 474     // Do not allow magic allocator for now for mutable datas, because it
 475     // isn't remembered for proper handling later when growth of the buffer
 476     // has to occur.
 477     Boolean wasMagic = (0);
 478     CFMutableDataRef r = (CFMutableDataRef) __CFDataInit(allocator, (0 == capacity) ? kCFMutable : kCFFixedMutable, capacity, CFDataGetBytePtr(data), CFDataGetLength(data), NULL);
 479     if (wasMagic) CFMakeCollectable(r);
 480     return r;
 481 }
 482
 483 CFIndex CFDataGetLength(CFDataRef data) {
 484     CF_OBJC_FUNCDISPATCHV(CFDataGetTypeID(), CFIndex, (NSData *)data, length);
 485     __CFGenericValidateType(data, CFDataGetTypeID());
 486     return __CFDataLength(data);
 487 }
 488
 489 const uint8_t *CFDataGetBytePtr(CFDataRef data) {
 490     CF_OBJC_FUNCDISPATCHV(CFDataGetTypeID(), const uint8_t *, (NSData *)data, bytes);
 491     __CFGenericValidateType(data, CFDataGetTypeID());
 492     // compaction: if inline, always do the computation.
 493     return __CFDataBytesInline(data) ? (uint8_t *)__CFDataInlineBytesPtr(data) : data->_bytes;
 494 }
 495
 496 uint8_t *CFDataGetMutableBytePtr(CFMutableDataRef data) {
 497     CF_OBJC_FUNCDISPATCHV(CFDataGetTypeID(), uint8_t *, (NSMutableData *)data, mutableBytes);
 498     CFAssert1(__CFDataIsMutable(data), __kCFLogAssertion, "%s(): data is immutable", __PRETTY_FUNCTION__);
 499     // compaction: if inline, always do the computation.
 500     return __CFDataBytesInline(data) ? (uint8_t *)__CFDataInlineBytesPtr(data) : data->_bytes;
 501 }
 502
 503 void CFDataGetBytes(CFDataRef data, CFRange range, uint8_t *buffer) {
 504     CF_OBJC_FUNCDISPATCHV(CFDataGetTypeID(), void, (NSData *)data, getBytes:(void *)buffer range:NSMakeRange(range.location, range.length));
 505     __CFDataValidateRange(data, range, __PRETTY_FUNCTION__);
 506     memmove(buffer, CFDataGetBytePtr(data) + range.location, range.length);
 507 }
 508
 509 /* Allocates new block of data with at least numNewValues more bytes than the current length. If clear is true, the new bytes up to at least the new length with be zeroed. */
 510 static void __CFDataGrow(CFMutableDataRef data, CFIndex numNewValues, Boolean clear) {
 511     CFIndex oldLength = __CFDataLength(data);
 512     CFIndex newLength = oldLength + numNewValues;
 513     if (newLength > CFDATA_MAX_SIZE || newLength < 0) __CFDataHandleOutOfMemory(data, newLength * sizeof(uint8_t));
 514     CFIndex capacity = __CFDataRoundUpCapacity(newLength);
 515     CFIndex numBytes = __CFDataNumBytesForCapacity(capacity);
 516     CFAllocatorRef allocator = CFGetAllocator(data);
 517     void *bytes = NULL;
 518     void *oldBytes = data->_bytes;
 519     Boolean allocateCleared = clear && __CFDataShouldAllocateCleared(data, numBytes);
 520     if (allocateCleared && !__CFDataUseAllocator(data) && (oldLength == 0 || (newLength / oldLength) > 4)) {
 521         // If the length that needs to be zeroed is significantly greater than the length of the data, then calloc/memmove is probably more efficient than realloc/memset.
 522         bytes = __CFDataAllocate(data, numBytes * sizeof(uint8_t), true);
 523         if (NULL != bytes) {
 524             memmove(bytes, oldBytes, oldLength);
 525             __CFDataDeallocate(data);
 526         }
 527     }
 528     if (bytes == NULL) {
 529         // If the calloc/memmove approach either failed or was never attempted, then realloc.
 530         allocateCleared = false;
 531         if (__CFDataUseAllocator(data)) {
 532             bytes = CFAllocatorReallocate(allocator, oldBytes, numBytes * sizeof(uint8_t), 0);
 533         } else {
 534             bytes = realloc(oldBytes, numBytes * sizeof(uint8_t));
 535         }
 536     }
 537     if (NULL == bytes) __CFDataHandleOutOfMemory(data, numBytes * sizeof(uint8_t));
 538     __CFDataSetCapacity(data, capacity);
 539     __CFDataSetNumBytes(data, numBytes);
 540     if (clear && !allocateCleared && oldLength < newLength) memset((uint8_t *)bytes + oldLength, 0, newLength - oldLength);
 541     __CFDataSetNeedsToZero(data, !allocateCleared);
 542     __CFAssignWithWriteBarrier((void **)&data->_bytes, bytes);
 543     if (__CFOASafe) __CFSetLastAllocationEventName(data->_bytes, "CFData (store)");
 544 }
 545
 546 void CFDataSetLength(CFMutableDataRef data, CFIndex newLength) {
 547     CFIndex oldLength, capacity;
 548     Boolean isGrowable;
 549     CF_OBJC_FUNCDISPATCHV(CFDataGetTypeID(), void, (NSMutableData *)data, setLength:(NSUInteger)newLength);
 550     CFAssert1(__CFDataIsMutable(data), __kCFLogAssertion, "%s(): data is immutable", __PRETTY_FUNCTION__);
 551     oldLength = __CFDataLength(data);
 552     capacity = __CFDataCapacity(data);
 553     isGrowable = __CFDataIsGrowable(data);
 554     if (__CFDataIsMutable(data)) {
 555         if (newLength < 0) {
 556             if (isGrowable) {
 557                 __CFDataHandleOutOfMemory(data, newLength);
 558             } else {
 559                 HALT;
 560             }
 561         } else if (capacity < newLength) {
 562             if (isGrowable) {
 563                 __CFDataGrow(data, newLength - oldLength, true);
 564             } else {
 565                 CFAssert1(newLength <= __CFDataCapacity(data), __kCFLogAssertion, "%s(): fixed-capacity data is full", __PRETTY_FUNCTION__);
 566             }
 567         } else if (oldLength < newLength && __CFDataNeedsToZero(data)) {
 568             memset(CFDataGetMutableBytePtr(data) + oldLength, 0, newLength - oldLength);
 569         } else if (newLength < oldLength) {
 570             __CFDataSetNeedsToZero(data, true);
 571         }
 572     }
 573     __CFDataSetLength(data, newLength);
 574     __CFDataSetNumBytesUsed(data, newLength);
 575 }
 576
 577 void CFDataIncreaseLength(CFMutableDataRef data, CFIndex extraLength) {
 578     CF_OBJC_FUNCDISPATCHV(CFDataGetTypeID(), void, (NSMutableData *)data, increaseLengthBy:(NSUInteger)extraLength);
 579     CFAssert1(__CFDataIsMutable(data), __kCFLogAssertion, "%s(): data is immutable", __PRETTY_FUNCTION__);
 580     if (extraLength < 0) HALT; // Avoid integer overflow.
 581     CFDataSetLength(data, __CFDataLength(data) + extraLength);
 582 }
 583
 584 void CFDataAppendBytes(CFMutableDataRef data, const uint8_t *bytes, CFIndex length) {
 585     CF_OBJC_FUNCDISPATCHV(CFDataGetTypeID(), void, (NSMutableData *)data, appendBytes:(const void *)bytes length:(NSUInteger)length);
 586     CFAssert1(__CFDataIsMutable(data), __kCFLogAssertion, "%s(): data is immutable", __PRETTY_FUNCTION__);
 587     CFDataReplaceBytes(data, CFRangeMake(__CFDataLength(data), 0), bytes, length);
 588 }
 589
 590 void CFDataDeleteBytes(CFMutableDataRef data, CFRange range) {
 591     CF_OBJC_FUNCDISPATCHV(CFDataGetTypeID(), void, (NSMutableData *)data, replaceBytesInRange:NSMakeRange(range.location, range.length) withBytes:NULL length:0);
 592     CFAssert1(__CFDataIsMutable(data), __kCFLogAssertion, "%s(): data is immutable", __PRETTY_FUNCTION__);
 593     CFDataReplaceBytes(data, range, NULL, 0);
 594 }
 595
 596 void CFDataReplaceBytes(CFMutableDataRef data, CFRange range, const uint8_t *newBytes, CFIndex newLength) {
 597     CF_OBJC_FUNCDISPATCHV(CFDataGetTypeID(), void, (NSMutableData *)data, replaceBytesInRange:NSMakeRange(range.location, range.length) withBytes:(const void *)newBytes length:(NSUInteger)newLength);
 598     __CFGenericValidateType(data, CFDataGetTypeID());
 599     __CFDataValidateRange(data, range, __PRETTY_FUNCTION__);
 600     CFAssert1(__CFDataIsMutable(data), __kCFLogAssertion, "%s(): data is immutable", __PRETTY_FUNCTION__);
 601     CFAssert2(0 <= newLength, __kCFLogAssertion, "%s(): newLength (%d) cannot be less than zero", __PRETTY_FUNCTION__, newLength);
 602
 603     CFIndex len = __CFDataLength(data);
 604     if (len < 0 || range.length < 0 || newLength < 0) HALT;
 605     CFIndex newCount = len - range.length + newLength;
 606     if (newCount < 0) HALT;
 607
 608     uint8_t *bytePtr = (uint8_t *)CFDataGetMutableBytePtr(data);
 609     uint8_t *srcBuf = (uint8_t *)newBytes;
 610     switch (__CFMutableVariety(data)) {
 611     case kCFMutable:
 612         if (__CFDataNumBytes(data) < newCount) {
 613             if (bytePtr && newBytes && newBytes < bytePtr + __CFDataCapacity(data) && bytePtr < newBytes + newLength) {
 614                 srcBuf = (uint8_t *)malloc(newLength * sizeof(uint8_t));
 615                 memmove(srcBuf, newBytes, newLength * sizeof(uint8_t));
 616             }
 617             __CFDataGrow(data, newLength - range.length, false);
 618             bytePtr = (uint8_t *)CFDataGetMutableBytePtr(data);
 619         }
 620         break;
 621     case kCFFixedMutable:
 622         CFAssert1(newCount <= __CFDataCapacity(data), __kCFLogAssertion, "%s(): fixed-capacity data is full", __PRETTY_FUNCTION__);
 623         // Continuing after this could cause buffer overruns.
 624         if (newCount > __CFDataCapacity(data)) HALT;
 625         break;
 626     }
 627     if (newLength != range.length && range.location + range.length < len) {
 628         memmove(bytePtr + range.location + newLength, bytePtr + range.location + range.length, (len - range.location - range.length) * sizeof(uint8_t));
 629     }
 630     if (0 < newLength) {
 631         memmove(bytePtr + range.location, srcBuf, newLength * sizeof(uint8_t));
 632     }
 633     if (srcBuf != newBytes) free(srcBuf);
 634     __CFDataSetNumBytesUsed(data, newCount);
 635     __CFDataSetLength(data, newCount);
 636 }
 637
 638 #define REVERSE_BUFFER(type, buf, len) { \
 639     type tmp; \
 640     for(int i = 0; i < (len)/2; i++) { \
 641         tmp = (buf)[i]; \
 642         (buf)[i] = (buf)[(len) - i - 1]; \
 643         (buf)[(len) - i - 1] = tmp; \
 644     } \
 645 }
 646
 647 static void _computeGoodSubstringShift(const uint8_t *needle, int needleLength, unsigned long shift[], unsigned long suff[]) {
 648     int f, g, i, j;
 649
 650     // Compute suffix lengths
 651
 652     suff[needleLength - 1] = needleLength;
 653     f = g = needleLength - 1;
 654     for (i = needleLength - 2; i >= 0; --i) {
 655         if (i > g && suff[i + needleLength - 1 - f] < i - g)
 656             suff[i] = suff[i + needleLength - 1 - f];
 657         else {
 658             if (i < g)
 659                 g = i;
 660             f = i;
 661             while (g >= 0 && needle[g] == needle[g + needleLength - 1 - f])
 662                 --g;
 663             suff[i] = f - g;
 664         }
 665     }
 666
 667     // Compute shift table
 668
 669     for (i = 0; i < needleLength; ++i)
 670         shift[i] = needleLength;
 671     j = 0;
 672     for (i = needleLength - 1; i >= 0; --i)
 673         if (suff[i] == i + 1)
 674             for (; j < needleLength - 1 - i; ++j)
 675                 if (shift[j] == needleLength)
 676                     shift[j] = needleLength - 1 - i;
 677     // Set the amount of shift necessary to move each of the suffix matches found into a position where it overlaps with the suffix. If there are duplicate matches the latest one is the one that should take effect.
 678     for (i = 0; i <= needleLength - 2; ++i)
 679         shift[needleLength - 1 - suff[i]] = needleLength - 1 - i;
 680     // Since the Boyer-Moore algorithm moves the pointer back while scanning substrings, add the distance to the end of the potential substring.
 681     for (i = 0; i < needleLength - 1; ++i) {
 682         shift[i] += (needleLength - 1 - i);
 683     }
 684 }
 685
 686 static const uint8_t * __CFDataSearchBoyerMoore(const CFDataRef data, const uint8_t *haystack, unsigned long haystackLength, const uint8_t *needle, unsigned long needleLength, Boolean backwards) {
 687     unsigned long badCharacterShift[UCHAR_MAX + 1] = {0};
 688     unsigned long *goodSubstringShift = (unsigned long *)malloc(needleLength * sizeof(unsigned long));
 689     unsigned long *suffixLengths = (unsigned long *)malloc(needleLength * sizeof(unsigned long));
 690     if (!goodSubstringShift || !suffixLengths) {
 691         __CFDataHandleOutOfMemory(data, needleLength * sizeof(unsigned long));
 692     }
 693
 694     if(backwards) {
 695         for (int i = 0; i < sizeof(badCharacterShift) / sizeof(*badCharacterShift); i++)
 696             badCharacterShift[i] = needleLength;
 697
 698         for (int i = needleLength - 1; i >= 0; i--)
 699             badCharacterShift[needle[i]] = i;
 700
 701         // To get the correct shift table for backwards search reverse the needle, compute the forwards shift table, and then reverse the result.
 702         uint8_t *needleCopy = (uint8_t *)malloc(needleLength * sizeof(uint8_t));
 703         if (!needleCopy) {
 704             __CFDataHandleOutOfMemory(data, needleLength * sizeof(uint8_t));
 705         }
 706         memmove(needleCopy, needle, needleLength);
 707         REVERSE_BUFFER(uint8_t, needleCopy, needleLength);
 708         _computeGoodSubstringShift(needleCopy, needleLength, goodSubstringShift, suffixLengths);
 709         REVERSE_BUFFER(unsigned long, goodSubstringShift, needleLength);
 710         free(needleCopy);
 711     } else {
 712         for (int i = 0; i < sizeof(badCharacterShift) / sizeof(*badCharacterShift); i++)
 713             badCharacterShift[i] = needleLength;
 714
 715         for (int i = 0; i < needleLength; i++)
 716             badCharacterShift[needle[i]] = needleLength - i- 1;
 717
 718         _computeGoodSubstringShift(needle, needleLength, goodSubstringShift, suffixLengths);
 719     }
 720
 721     const uint8_t *scan_needle;
 722     const uint8_t *scan_haystack;
 723     const uint8_t *result = NULL;
 724     if(backwards) {
 725         const uint8_t *const end_needle = needle + needleLength;
 726         scan_needle = needle;
 727         scan_haystack = haystack + haystackLength - needleLength;
 728         while (scan_haystack >= haystack && scan_needle < end_needle) {
 729             if (*scan_haystack == *scan_needle) {
 730                 scan_haystack++;
 731                 scan_needle++;
 732             } else {
 733                 scan_haystack -= __CFMax(badCharacterShift[*scan_haystack], goodSubstringShift[scan_needle - needle]);
 734                 scan_needle = needle;
 735             }
 736         }
 737         if (scan_needle == end_needle) {
 738             result = (scan_haystack - needleLength);
 739         }
 740     } else {
 741         const uint8_t *const end_haystack = haystack + haystackLength;
 742         scan_needle = needle + needleLength - 1;
 743         scan_haystack = haystack + needleLength - 1;
 744         while (scan_haystack < end_haystack && scan_needle >= needle) {
 745             if (*scan_haystack == *scan_needle) {
 746                 scan_haystack--;
 747                 scan_needle--;
 748             } else {
 749                 scan_haystack += __CFMax(badCharacterShift[*scan_haystack], goodSubstringShift[scan_needle - needle]);
 750                 scan_needle = needle + needleLength - 1;
 751             }
 752         }
 753         if (scan_needle < needle) {
 754             result = (scan_haystack + 1);
 755         }
 756     }
 757
 758     free(goodSubstringShift);
 759     free(suffixLengths);
 760
 761     return result;
 762 }
 763
 764 CFRange _CFDataFindBytes(CFDataRef data, CFDataRef dataToFind, CFRange searchRange, CFDataSearchFlags compareOptions) {
 765     const uint8_t *fullHaystack = CFDataGetBytePtr(data);
 766     const uint8_t *needle = CFDataGetBytePtr(dataToFind);
 767     unsigned long fullHaystackLength = CFDataGetLength(data);
 768     unsigned long needleLength = CFDataGetLength(dataToFind);
 769
 770     if(compareOptions & kCFDataSearchAnchored) {
 771         if(searchRange.length > needleLength) {
 772             if(compareOptions & kCFDataSearchBackwards) {
 773                 searchRange.location += (searchRange.length - needleLength);
 774             }
 775             searchRange.length = needleLength;
 776         }
 777     }
 778     if(searchRange.length > fullHaystackLength - searchRange.location) {
 779         searchRange.length = fullHaystackLength - searchRange.location;
 780     }
 781
 782     if(searchRange.length < needleLength || fullHaystackLength == 0 || needleLength == 0) {
 783         return CFRangeMake(kCFNotFound, 0);
 784     }
 785
 786     const uint8_t *haystack = fullHaystack + searchRange.location;
 787     const uint8_t *searchResult = __CFDataSearchBoyerMoore(data, haystack, searchRange.length, needle, needleLength, (compareOptions & kCFDataSearchBackwards) != 0);
 788     CFIndex resultLocation = (searchResult == NULL) ? kCFNotFound : searchRange.location + (searchResult - haystack);
 789
 790     return CFRangeMake(resultLocation, resultLocation == kCFNotFound ? 0: needleLength);
 791 }
 792
 793 CFRange CFDataFind(CFDataRef data, CFDataRef dataToFind, CFRange searchRange, CFDataSearchFlags compareOptions) {
 794     // No objc dispatch
 795     __CFGenericValidateType(data, CFDataGetTypeID());
 796     __CFGenericValidateType(dataToFind, CFDataGetTypeID());
 797     __CFDataValidateRange(data, searchRange, __PRETTY_FUNCTION__);
 798
 799     return _CFDataFindBytes(data, dataToFind, searchRange, compareOptions);
 800 }
 801
 802 #undef __CFDataValidateRange
 803 #undef __CFGenericValidateMutabilityFlags
 804 #undef INLINE_BYTES_THRESHOLD
 805 #undef CFDATA_MAX_SIZE
 806 #undef REVERSE_BUFFER