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