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