CFData.c

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