CFBinaryPList.c

   1 /*
   2  * Copyright (c) 2013 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 /*      CFBinaryPList.c
  25         Copyright (c) 2000-2013, Apple Inc. All rights reserved.
  26         Responsibility: Tony Parker
  27 */
  28
  29
  30 #include <CoreFoundation/CFString.h>
  31 #include <CoreFoundation/CFNumber.h>
  32 #include <CoreFoundation/CFDate.h>
  33 #include <CoreFoundation/CFData.h>
  34 #include <CoreFoundation/CFError.h>
  35 #include <CoreFoundation/CFArray.h>
  36 #include <CoreFoundation/CFDictionary.h>
  37 #include <CoreFoundation/CFSet.h>
  38 #include <CoreFoundation/CFPropertyList.h>
  39 #include <CoreFoundation/CFByteOrder.h>
  40 #include <CoreFoundation/CFRuntime.h>
  41 #include <CoreFoundation/CFUUID.h>
  42 #include <stdio.h>
  43 #include <limits.h>
  44 #include <string.h>
  45 #include "CFInternal.h"
  46 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_WINDOWS
  47 #include <CoreFoundation/CFStream.h>
  48 #endif
  49
  50 typedef struct {
  51     int64_t high;
  52     uint64_t low;
  53 } CFSInt128Struct;
  54
  55 enum {
  56     kCFNumberSInt128Type = 17
  57 };
  58
  59 enum {
  60         CF_NO_ERROR = 0,
  61         CF_OVERFLOW_ERROR = (1 << 0),
  62 };
  63
  64 CF_INLINE uint32_t __check_uint32_add_unsigned_unsigned(uint32_t x, uint32_t y, int32_t* err) {
  65    if((UINT_MAX - y) < x)
  66         *err = *err | CF_OVERFLOW_ERROR;
  67    return x + y;
  68 };
  69
  70 CF_INLINE uint64_t __check_uint64_add_unsigned_unsigned(uint64_t x, uint64_t y, int32_t* err) {
  71    if((ULLONG_MAX - y) < x)
  72         *err = *err | CF_OVERFLOW_ERROR;
  73    return x + y;
  74 };
  75
  76 CF_INLINE uint32_t __check_uint32_mul_unsigned_unsigned(uint32_t x, uint32_t y, int32_t* err) {
  77    uint64_t tmp = (uint64_t) x * (uint64_t) y;
  78    /* If any of the upper 32 bits touched, overflow */
  79    if(tmp & 0xffffffff00000000ULL)
  80         *err = *err | CF_OVERFLOW_ERROR;
  81    return (uint32_t) tmp;
  82 };
  83
  84 CF_INLINE uint64_t __check_uint64_mul_unsigned_unsigned(uint64_t x, uint64_t y, int32_t* err) {
  85   if(x == 0) return 0;
  86   if(ULLONG_MAX/x < y)
  87      *err = *err | CF_OVERFLOW_ERROR;
  88   return x * y;
  89 };
  90
  91 #if __LP64__
  92 #define check_ptr_add(p, a, err)        (const uint8_t *)__check_uint64_add_unsigned_unsigned((uintptr_t)p, (uintptr_t)a, err)
  93 #define check_size_t_mul(b, a, err)     (size_t)__check_uint64_mul_unsigned_unsigned((size_t)b, (size_t)a, err)
  94 #else
  95 #define check_ptr_add(p, a, err)        (const uint8_t *)__check_uint32_add_unsigned_unsigned((uintptr_t)p, (uintptr_t)a, err)
  96 #define check_size_t_mul(b, a, err)     (size_t)__check_uint32_mul_unsigned_unsigned((size_t)b, (size_t)a, err)
  97 #endif
  98
  99 #pragma mark -
 100 #pragma mark Keyed Archiver UID
 101
 102 struct __CFKeyedArchiverUID {
 103     CFRuntimeBase _base;
 104     uint32_t _value;
 105 };
 106
 107 static CFStringRef __CFKeyedArchiverUIDCopyDescription(CFTypeRef cf) {
 108     CFKeyedArchiverUIDRef uid = (CFKeyedArchiverUIDRef)cf;
 109     return CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<CFKeyedArchiverUID %p [%p]>{value = %u}"), cf, CFGetAllocator(cf), uid->_value);
 110 }
 111
 112 static CFStringRef __CFKeyedArchiverUIDCopyFormattingDescription(CFTypeRef cf, CFDictionaryRef formatOptions) {
 113     CFKeyedArchiverUIDRef uid = (CFKeyedArchiverUIDRef)cf;
 114     return CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("@%u@"), uid->_value);
 115 }
 116
 117 static CFTypeID __kCFKeyedArchiverUIDTypeID = _kCFRuntimeNotATypeID;
 118
 119 static const CFRuntimeClass __CFKeyedArchiverUIDClass = {
 120     0,
 121     "CFKeyedArchiverUID",
 122     NULL,       // init
 123     NULL,       // copy
 124     NULL,       // finalize
 125     NULL,       // equal -- pointer equality only
 126     NULL,       // hash -- pointer hashing only
 127     __CFKeyedArchiverUIDCopyFormattingDescription,
 128     __CFKeyedArchiverUIDCopyDescription
 129 };
 130
 131 CF_PRIVATE void __CFKeyedArchiverUIDInitialize(void) {
 132     __kCFKeyedArchiverUIDTypeID = _CFRuntimeRegisterClass(&__CFKeyedArchiverUIDClass);
 133 }
 134
 135 CFTypeID _CFKeyedArchiverUIDGetTypeID(void) {
 136     return __kCFKeyedArchiverUIDTypeID;
 137 }
 138
 139 CFKeyedArchiverUIDRef _CFKeyedArchiverUIDCreate(CFAllocatorRef allocator, uint32_t value) {
 140     CFKeyedArchiverUIDRef uid;
 141     uid = (CFKeyedArchiverUIDRef)_CFRuntimeCreateInstance(allocator, __kCFKeyedArchiverUIDTypeID, sizeof(struct __CFKeyedArchiverUID) - sizeof(CFRuntimeBase), NULL);
 142     if (NULL == uid) {
 143         return NULL;
 144     }
 145     ((struct __CFKeyedArchiverUID *)uid)->_value = value;
 146     return uid;
 147 }
 148
 149
 150 uint32_t _CFKeyedArchiverUIDGetValue(CFKeyedArchiverUIDRef uid) {
 151     return uid->_value;
 152 }
 153
 154 #pragma mark -
 155 #pragma mark Writing
 156
 157 CF_PRIVATE CFErrorRef __CFPropertyListCreateError(CFIndex code, CFStringRef debugString, ...);
 158
 159 typedef struct {
 160     CFTypeRef stream;
 161     void *databytes;
 162     uint64_t datalen;
 163     CFErrorRef error;
 164     uint64_t written;
 165     int32_t used;
 166     bool streamIsData;
 167     uint8_t buffer[8192 - 32];
 168 } __CFBinaryPlistWriteBuffer;
 169
 170 static void writeBytes(__CFBinaryPlistWriteBuffer *buf, const UInt8 *bytes, CFIndex length) {
 171     if (0 == length) return;
 172     if (buf->error) return;
 173     if (buf->databytes) {
 174         if (buf->datalen < buf->written + length) {
 175             buf->error = __CFPropertyListCreateError(kCFPropertyListWriteStreamError, CFSTR("Binary property list writing could not be completed because databytes is full."));
 176             return;
 177         }
 178         memmove((char *)buf->databytes + buf->written, bytes, length);
 179     }
 180     if (buf->streamIsData) {
 181         if (buf->stream) CFDataAppendBytes((CFMutableDataRef)buf->stream, bytes, length);
 182         buf->written += length;
 183     } else {
 184 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_WINDOWS
 185         while (0 < length) {
 186             CFIndex ret = buf->stream ? CFWriteStreamWrite((CFWriteStreamRef)buf->stream, bytes, length) : length;
 187             if (ret == 0) {
 188                 buf->error = __CFPropertyListCreateError(kCFPropertyListWriteStreamError, CFSTR("Binary property list writing could not be completed because stream is full."));
 189                 return;
 190             }
 191             if (ret < 0) {
 192                 CFErrorRef err = buf->stream ? CFWriteStreamCopyError((CFWriteStreamRef)buf->stream) : NULL;
 193                 buf->error = err ? err : __CFPropertyListCreateError(kCFPropertyListWriteStreamError, CFSTR("Binary property list writing could not be completed because the stream had an unknown error."));
 194                 return;
 195             }
 196             buf->written += ret;
 197             length -= ret;
 198             bytes += ret;
 199         }
 200 #else
 201         CFAssert(false, __kCFLogAssertion, "Streams are not supported on this platform");
 202 #endif
 203     }
 204 }
 205
 206 static void bufferFlush(__CFBinaryPlistWriteBuffer *buf) {
 207     writeBytes(buf, buf->buffer, buf->used);
 208     buf->used = 0;
 209 }
 210
 211 static void bufferWrite(__CFBinaryPlistWriteBuffer *buf, const uint8_t *buffer, CFIndex count) {
 212     if (0 == count) return;
 213     if ((CFIndex)sizeof(buf->buffer) <= count) {
 214         bufferFlush(buf);
 215         writeBytes(buf, buffer, count);
 216         return;
 217     }
 218     CFIndex copyLen = __CFMin(count, (CFIndex)sizeof(buf->buffer) - buf->used);
 219     if (buf->stream || buf->databytes) {
 220         switch (copyLen) {
 221         case 4: buf->buffer[buf->used + 3] = buffer[3]; /* FALLTHROUGH */
 222         case 3: buf->buffer[buf->used + 2] = buffer[2]; /* FALLTHROUGH */
 223         case 2: buf->buffer[buf->used + 1] = buffer[1]; /* FALLTHROUGH */
 224         case 1: buf->buffer[buf->used] = buffer[0]; break;
 225         default: memmove(buf->buffer + buf->used, buffer, copyLen);
 226         }
 227     }
 228     buf->used += copyLen;
 229     if (sizeof(buf->buffer) == buf->used) {
 230         writeBytes(buf, buf->buffer, sizeof(buf->buffer));
 231         if (buf->stream || buf->databytes) {
 232             memmove(buf->buffer, buffer + copyLen, count - copyLen);
 233         }
 234         buf->used = count - copyLen;
 235     }
 236 }
 237
 238 /*
 239 HEADER
 240         magic number ("bplist")
 241         file format version (currently "0?")
 242
 243 OBJECT TABLE
 244         variable-sized objects
 245
 246         Object Formats (marker byte followed by additional info in some cases)
 247         null    0000 0000                       // null object [v"1?"+ only]
 248         bool    0000 1000                       // false
 249         bool    0000 1001                       // true
 250         url     0000 1100       string          // URL with no base URL, recursive encoding of URL string [v"1?"+ only]
 251         url     0000 1101       base string     // URL with base URL, recursive encoding of base URL, then recursive encoding of URL string [v"1?"+ only]
 252         uuid    0000 1110                       // 16-byte UUID [v"1?"+ only]
 253         fill    0000 1111                       // fill byte
 254         int     0001 0nnn       ...             // # of bytes is 2^nnn, big-endian bytes
 255         real    0010 0nnn       ...             // # of bytes is 2^nnn, big-endian bytes
 256         date    0011 0011       ...             // 8 byte float follows, big-endian bytes
 257         data    0100 nnnn       [int]   ...     // nnnn is number of bytes unless 1111 then int count follows, followed by bytes
 258         string  0101 nnnn       [int]   ...     // ASCII string, nnnn is # of chars, else 1111 then int count, then bytes
 259         string  0110 nnnn       [int]   ...     // Unicode string, nnnn is # of chars, else 1111 then int count, then big-endian 2-byte uint16_t
 260         string  0111 nnnn       [int]   ...     // UTF8 string, nnnn is # of chars, else 1111 then int count, then bytes [v"1?"+ only]
 261         uid     1000 nnnn       ...             // nnnn+1 is # of bytes
 262                 1001 xxxx                       // unused
 263         array   1010 nnnn       [int]   objref* // nnnn is count, unless '1111', then int count follows
 264         ordset  1011 nnnn       [int]   objref* // nnnn is count, unless '1111', then int count follows [v"1?"+ only]
 265         set     1100 nnnn       [int]   objref* // nnnn is count, unless '1111', then int count follows [v"1?"+ only]
 266         dict    1101 nnnn       [int]   keyref* objref* // nnnn is count, unless '1111', then int count follows
 267                 1110 xxxx                       // unused
 268                 1111 xxxx                       // unused
 269
 270 OFFSET TABLE
 271         list of ints, byte size of which is given in trailer
 272         -- these are the byte offsets into the file
 273         -- number of these is in the trailer
 274
 275 TRAILER
 276         byte size of offset ints in offset table
 277         byte size of object refs in arrays and dicts
 278         number of offsets in offset table (also is number of objects)
 279         element # in offset table which is top level object
 280         offset table offset
 281
 282 */
 283
 284
 285 static CFTypeID stringtype = -1, datatype = -1, numbertype = -1, datetype = -1;
 286 static CFTypeID booltype = -1, nulltype = -1, dicttype = -1, arraytype = -1;
 287 static CFTypeID uuidtype = -1, urltype = -1, osettype = -1, settype = -1;
 288
 289 static void initStatics() {
 290     if ((CFTypeID)-1 == stringtype) {
 291         stringtype = CFStringGetTypeID();
 292     }
 293     if ((CFTypeID)-1 == datatype) {
 294         datatype = CFDataGetTypeID();
 295     }
 296     if ((CFTypeID)-1 == numbertype) {
 297         numbertype = CFNumberGetTypeID();
 298     }
 299     if ((CFTypeID)-1 == booltype) {
 300         booltype = CFBooleanGetTypeID();
 301     }
 302     if ((CFTypeID)-1 == datetype) {
 303         datetype = CFDateGetTypeID();
 304     }
 305     if ((CFTypeID)-1 == dicttype) {
 306         dicttype = CFDictionaryGetTypeID();
 307     }
 308     if ((CFTypeID)-1 == arraytype) {
 309         arraytype = CFArrayGetTypeID();
 310     }
 311     if ((CFTypeID)-1 == settype) {
 312         settype = CFSetGetTypeID();
 313     }
 314     if ((CFTypeID)-1 == nulltype) {
 315         nulltype = CFNullGetTypeID();
 316     }
 317     if ((CFTypeID)-1 == uuidtype) {
 318         uuidtype = CFUUIDGetTypeID();
 319     }
 320     if ((CFTypeID)-1 == urltype) {
 321         urltype = CFURLGetTypeID();
 322     }
 323     if ((CFTypeID)-1 == osettype) {
 324         osettype = -1;
 325     }
 326 }
 327
 328 static void _appendInt(__CFBinaryPlistWriteBuffer *buf, uint64_t bigint) {
 329     uint8_t marker;
 330     uint8_t *bytes;
 331     CFIndex nbytes;
 332     if (bigint <= (uint64_t)0xff) {
 333         nbytes = 1;
 334         marker = kCFBinaryPlistMarkerInt | 0;
 335     } else if (bigint <= (uint64_t)0xffff) {
 336         nbytes = 2;
 337         marker = kCFBinaryPlistMarkerInt | 1;
 338     } else if (bigint <= (uint64_t)0xffffffff) {
 339         nbytes = 4;
 340         marker = kCFBinaryPlistMarkerInt | 2;
 341     } else {
 342         nbytes = 8;
 343         marker = kCFBinaryPlistMarkerInt | 3;
 344     }
 345     bigint = CFSwapInt64HostToBig(bigint);
 346     bytes = (uint8_t *)&bigint + sizeof(bigint) - nbytes;
 347     bufferWrite(buf, &marker, 1);
 348     bufferWrite(buf, bytes, nbytes);
 349 }
 350
 351 static void _appendUID(__CFBinaryPlistWriteBuffer *buf, CFKeyedArchiverUIDRef uid) {
 352     uint8_t marker;
 353     uint8_t *bytes;
 354     CFIndex nbytes;
 355     uint64_t bigint = _CFKeyedArchiverUIDGetValue(uid);
 356     if (bigint <= (uint64_t)0xff) {
 357         nbytes = 1;
 358     } else if (bigint <= (uint64_t)0xffff) {
 359         nbytes = 2;
 360     } else if (bigint <= (uint64_t)0xffffffff) {
 361         nbytes = 4;
 362     } else {
 363         nbytes = 8;
 364     }
 365     marker = kCFBinaryPlistMarkerUID | (uint8_t)(nbytes - 1);
 366     bigint = CFSwapInt64HostToBig(bigint);
 367     bytes = (uint8_t *)&bigint + sizeof(bigint) - nbytes;
 368     bufferWrite(buf, &marker, 1);
 369     bufferWrite(buf, bytes, nbytes);
 370 }
 371
 372 static void _appendString(__CFBinaryPlistWriteBuffer *buf, CFStringRef str) {
 373     CFIndex ret, count = CFStringGetLength(str);
 374     CFIndex needed, idx2;
 375     uint8_t *bytes, buffer[1024];
 376     bytes = (count <= 1024) ? buffer : (uint8_t *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count, 0);
 377     // presumption, believed to be true, is that ASCII encoding may need
 378     // less bytes, but will not need greater, than the # of unichars
 379     ret = CFStringGetBytes(str, CFRangeMake(0, count), kCFStringEncodingASCII, 0, false, bytes, count, &needed);
 380     if (ret == count) {
 381         uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerASCIIString | (needed < 15 ? needed : 0xf));
 382         bufferWrite(buf, &marker, 1);
 383         if (15 <= needed) {
 384             _appendInt(buf, (uint64_t)needed);
 385         }
 386         bufferWrite(buf, bytes, needed);
 387     } else {
 388         UniChar *chars;
 389         uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerUnicode16String | (count < 15 ? count : 0xf));
 390         bufferWrite(buf, &marker, 1);
 391         if (15 <= count) {
 392             _appendInt(buf, (uint64_t)count);
 393         }
 394         chars = (UniChar *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(UniChar), 0);
 395         CFStringGetCharacters(str, CFRangeMake(0, count), chars);
 396         for (idx2 = 0; idx2 < count; idx2++) {
 397             chars[idx2] = CFSwapInt16HostToBig(chars[idx2]);
 398         }
 399         bufferWrite(buf, (uint8_t *)chars, count * sizeof(UniChar));
 400         CFAllocatorDeallocate(kCFAllocatorSystemDefault, chars);
 401     }
 402     if (bytes != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, bytes);
 403 }
 404
 405 CF_EXPORT CFNumberType _CFNumberGetType2(CFNumberRef number);
 406
 407 static void _appendNumber(__CFBinaryPlistWriteBuffer *buf, CFNumberRef num) {
 408     uint8_t marker;
 409     uint64_t bigint;
 410     uint8_t *bytes;
 411     CFIndex nbytes;
 412     if (CFNumberIsFloatType(num)) {
 413         CFSwappedFloat64 swapped64;
 414         CFSwappedFloat32 swapped32;
 415         if (CFNumberGetByteSize(num) <= (CFIndex)sizeof(float)) {
 416             float v;
 417             CFNumberGetValue(num, kCFNumberFloat32Type, &v);
 418             swapped32 = CFConvertFloat32HostToSwapped(v);
 419             bytes = (uint8_t *)&swapped32;
 420             nbytes = sizeof(float);
 421             marker = kCFBinaryPlistMarkerReal | 2;
 422         } else {
 423             double v;
 424             CFNumberGetValue(num, kCFNumberFloat64Type, &v);
 425             swapped64 = CFConvertFloat64HostToSwapped(v);
 426             bytes = (uint8_t *)&swapped64;
 427             nbytes = sizeof(double);
 428             marker = kCFBinaryPlistMarkerReal | 3;
 429         }
 430         bufferWrite(buf, &marker, 1);
 431         bufferWrite(buf, bytes, nbytes);
 432     } else {
 433         CFNumberType type = _CFNumberGetType2(num);
 434         if (kCFNumberSInt128Type == type) {
 435             CFSInt128Struct s;
 436             CFNumberGetValue(num, kCFNumberSInt128Type, &s);
 437             struct {
 438                 int64_t high;
 439                 uint64_t low;
 440             } storage;
 441             storage.high = CFSwapInt64HostToBig(s.high);
 442             storage.low = CFSwapInt64HostToBig(s.low);
 443             uint8_t *bytes = (uint8_t *)&storage;
 444             uint8_t marker = kCFBinaryPlistMarkerInt | 4;
 445             CFIndex nbytes = 16;
 446             bufferWrite(buf, &marker, 1);
 447             bufferWrite(buf, bytes, nbytes);
 448         } else {
 449             CFNumberGetValue(num, kCFNumberSInt64Type, &bigint);
 450             _appendInt(buf, bigint);
 451         }
 452     }
 453 }
 454
 455 static Boolean _appendObject(__CFBinaryPlistWriteBuffer *buf, CFTypeRef obj, CFDictionaryRef objtable, uint32_t objRefSize) {
 456     uint64_t refnum;
 457     CFIndex idx2;
 458     CFTypeID type = CFGetTypeID(obj);
 459         if (stringtype == type) {
 460             _appendString(buf, (CFStringRef)obj);
 461         } else if (numbertype == type) {
 462             _appendNumber(buf, (CFNumberRef)obj);
 463         } else if (booltype == type) {
 464             uint8_t marker = CFBooleanGetValue((CFBooleanRef)obj) ? kCFBinaryPlistMarkerTrue : kCFBinaryPlistMarkerFalse;
 465             bufferWrite(buf, &marker, 1);
 466         } else if (datatype == type) {
 467             CFIndex count = CFDataGetLength((CFDataRef)obj);
 468             uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerData | (count < 15 ? count : 0xf));
 469             bufferWrite(buf, &marker, 1);
 470             if (15 <= count) {
 471                 _appendInt(buf, (uint64_t)count);
 472             }
 473             bufferWrite(buf, CFDataGetBytePtr((CFDataRef)obj), count);
 474         } else if (datetype == type) {
 475             CFSwappedFloat64 swapped;
 476             uint8_t marker = kCFBinaryPlistMarkerDate;
 477             bufferWrite(buf, &marker, 1);
 478             swapped = CFConvertFloat64HostToSwapped(CFDateGetAbsoluteTime((CFDateRef)obj));
 479             bufferWrite(buf, (uint8_t *)&swapped, sizeof(swapped));
 480         } else if (dicttype == type) {
 481             CFIndex count = CFDictionaryGetCount((CFDictionaryRef)obj);
 482             uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerDict | (count < 15 ? count : 0xf));
 483             bufferWrite(buf, &marker, 1);
 484             if (15 <= count) {
 485                 _appendInt(buf, (uint64_t)count);
 486             }
 487             CFPropertyListRef *list, buffer[512];
 488             list = (count <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * count * sizeof(CFTypeRef), __kCFAllocatorGCScannedMemory);
 489             CFDictionaryGetKeysAndValues((CFDictionaryRef)obj, list, list + count);
 490             for (idx2 = 0; idx2 < 2 * count; idx2++) {
 491                 CFPropertyListRef value = list[idx2];
 492                 if (objtable) {
 493                     uint32_t swapped = 0;
 494                     uint8_t *source = (uint8_t *)&swapped;
 495                     refnum = (uint32_t)(uintptr_t)CFDictionaryGetValue(objtable, value);
 496                     swapped = CFSwapInt32HostToBig((uint32_t)refnum);
 497                     bufferWrite(buf, source + sizeof(swapped) - objRefSize, objRefSize);
 498                 } else {
 499                     Boolean ret = _appendObject(buf, value, objtable, objRefSize);
 500                     if (!ret) {
 501                         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 502                         return false;
 503                     }
 504                 }
 505             }
 506             if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 507         } else if (arraytype == type) {
 508             CFIndex count = CFArrayGetCount((CFArrayRef)obj);
 509             CFPropertyListRef *list, buffer[256];
 510             uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerArray | (count < 15 ? count : 0xf));
 511             bufferWrite(buf, &marker, 1);
 512             if (15 <= count) {
 513                 _appendInt(buf, (uint64_t)count);
 514             }
 515             list = (count <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(CFTypeRef), __kCFAllocatorGCScannedMemory);
 516             CFArrayGetValues((CFArrayRef)obj, CFRangeMake(0, count), list);
 517             for (idx2 = 0; idx2 < count; idx2++) {
 518                 CFPropertyListRef value = list[idx2];
 519                 if (objtable) {
 520                     uint32_t swapped = 0;
 521                     uint8_t *source = (uint8_t *)&swapped;
 522                     refnum = (uint32_t)(uintptr_t)CFDictionaryGetValue(objtable, value);
 523                     swapped = CFSwapInt32HostToBig((uint32_t)refnum);
 524                     bufferWrite(buf, source + sizeof(swapped) - objRefSize, objRefSize);
 525                 } else {
 526                     Boolean ret = _appendObject(buf, value, objtable, objRefSize);
 527                     if (!ret) {
 528                         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 529                         return false;
 530                     }
 531                 }
 532             }
 533             if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 534         } else if (_CFKeyedArchiverUIDGetTypeID() == type) {
 535             _appendUID(buf, (CFKeyedArchiverUIDRef)obj);
 536         } else {
 537             return false;
 538         }
 539     return true;
 540 }
 541
 542 static void _flattenPlist(CFPropertyListRef plist, CFMutableArrayRef objlist, CFMutableDictionaryRef objtable, CFMutableSetRef uniquingset) {
 543     CFPropertyListRef unique;
 544     uint32_t refnum;
 545     CFTypeID type = CFGetTypeID(plist);
 546     CFIndex idx;
 547     CFPropertyListRef *list, buffer[256];
 548
 549     // Do not unique dictionaries or arrays, because: they
 550     // are slow to compare, and have poor hash codes.
 551     // Uniquing bools is unnecessary.
 552     if (stringtype == type || numbertype == type || datetype == type || datatype == type) {
 553         CFIndex before = CFSetGetCount(uniquingset);
 554         CFSetAddValue(uniquingset, plist);
 555         CFIndex after = CFSetGetCount(uniquingset);
 556         if (after == before) {  // already in set
 557             unique = CFSetGetValue(uniquingset, plist);
 558             if (unique != plist) {
 559                 refnum = (uint32_t)(uintptr_t)CFDictionaryGetValue(objtable, unique);
 560                 CFDictionaryAddValue(objtable, plist, (const void *)(uintptr_t)refnum);
 561             }
 562             return;
 563         }
 564     }
 565     refnum = CFArrayGetCount(objlist);
 566     CFArrayAppendValue(objlist, plist);
 567     CFDictionaryAddValue(objtable, plist, (const void *)(uintptr_t)refnum);
 568     if (dicttype == type) {
 569         CFIndex count = CFDictionaryGetCount((CFDictionaryRef)plist);
 570         list = (count <= 128) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * count * sizeof(CFTypeRef), __kCFAllocatorGCScannedMemory);
 571         CFDictionaryGetKeysAndValues((CFDictionaryRef)plist, list, list + count);
 572         for (idx = 0; idx < 2 * count; idx++) {
 573             _flattenPlist(list[idx], objlist, objtable, uniquingset);
 574         }
 575         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 576     } else if (arraytype == type) {
 577         CFIndex count = CFArrayGetCount((CFArrayRef)plist);
 578         list = (count <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(CFTypeRef), __kCFAllocatorGCScannedMemory);
 579         CFArrayGetValues((CFArrayRef)plist, CFRangeMake(0, count), list);
 580         for (idx = 0; idx < count; idx++) {
 581             _flattenPlist(list[idx], objlist, objtable, uniquingset);
 582         }
 583         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 584     }
 585 }
 586
 587 /* Get the number of bytes required to hold the value in 'count'. Will return a power of 2 value big enough to hold 'count'.
 588  */
 589 CF_INLINE uint8_t _byteCount(uint64_t count) {
 590     uint64_t mask = ~(uint64_t)0;
 591     uint8_t size = 0;
 592
 593     // Find something big enough to hold 'count'
 594     while (count & mask) {
 595         size++;
 596         mask = mask << 8;
 597     }
 598
 599     // Ensure that 'count' is a power of 2
 600     // For sizes bigger than 8, just use the required count
 601     while ((size != 1 && size != 2 && size != 4 && size != 8) && size <= 8) {
 602         size++;
 603     }
 604
 605     return size;
 606 }
 607
 608 // stream can be a CFWriteStreamRef (on supported platforms) or a CFMutableDataRef
 609 /* Write a property list to a stream, in binary format. plist is the property list to write (one of the basic property list types), stream is the destination of the property list, and estimate is a best-guess at the total number of objects in the property list. The estimate parameter is for efficiency in pre-allocating memory for the uniquing step. Pass in a 0 if no estimate is available. The options flag specifies sort options. If the error parameter is non-NULL and an error occurs, it will be used to return a CFError explaining the problem. It is the callers responsibility to release the error. */
 610 CFIndex __CFBinaryPlistWrite(CFPropertyListRef plist, CFTypeRef stream, uint64_t estimate, CFOptionFlags options, CFErrorRef *error) {
 611     CFMutableDictionaryRef objtable = NULL;
 612     CFMutableArrayRef objlist = NULL;
 613     CFMutableSetRef uniquingset = NULL;
 614     CFBinaryPlistTrailer trailer;
 615     uint64_t *offsets, length_so_far;
 616     int64_t idx, cnt;
 617     __CFBinaryPlistWriteBuffer *buf;
 618
 619     initStatics();
 620
 621     const CFDictionaryKeyCallBacks dictKeyCallbacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, 0, 0, 0};
 622     objtable = CFDictionaryCreateMutable(kCFAllocatorSystemDefault, 0, &dictKeyCallbacks, NULL);
 623
 624     const CFArrayCallBacks arrayCallbacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, 0, 0};
 625     objlist = CFArrayCreateMutable(kCFAllocatorSystemDefault, 0, &arrayCallbacks);
 626
 627
 628     const CFSetCallBacks setCallbacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, 0, 0, 0};
 629     uniquingset = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, &setCallbacks);
 630
 631 #if DEPLOYMENT_TARGET_MACOSX
 632     _CFDictionarySetCapacity(objtable, estimate ? estimate : 650);
 633     _CFArraySetCapacity(objlist, estimate ? estimate : 650);
 634     _CFSetSetCapacity(uniquingset, estimate ? estimate : 1000);
 635 #endif
 636
 637     _flattenPlist(plist, objlist, objtable, uniquingset);
 638
 639     CFRelease(uniquingset);
 640
 641     cnt = CFArrayGetCount(objlist);
 642     offsets = (uint64_t *)CFAllocatorAllocate(kCFAllocatorSystemDefault, (CFIndex)(cnt * sizeof(*offsets)), 0);
 643
 644     buf = (__CFBinaryPlistWriteBuffer *)CFAllocatorAllocate(kCFAllocatorSystemDefault, sizeof(__CFBinaryPlistWriteBuffer), 0);
 645     buf->stream = stream;
 646     buf->databytes = NULL;
 647     buf->datalen = 0;
 648     buf->error = NULL;
 649     buf->streamIsData = (CFGetTypeID(stream) == CFDataGetTypeID());
 650     buf->written = 0;
 651     buf->used = 0;
 652     bufferWrite(buf, (uint8_t *)"bplist00", 8); // header
 653
 654     memset(&trailer, 0, sizeof(trailer));
 655     trailer._numObjects = CFSwapInt64HostToBig(cnt);
 656     trailer._topObject = 0;     // true for this implementation
 657     trailer._objectRefSize = _byteCount(cnt);
 658     for (idx = 0; idx < cnt; idx++) {
 659         offsets[idx] = buf->written + buf->used;
 660         CFPropertyListRef obj = CFArrayGetValueAtIndex(objlist, (CFIndex)idx);
 661         Boolean success = _appendObject(buf, obj, objtable, trailer._objectRefSize);
 662         if (!success) {
 663             CFRelease(objtable);
 664             CFRelease(objlist);
 665             if (error && buf->error) {
 666                 // caller will release error
 667                 *error = buf->error;
 668             } else if (buf->error) {
 669                 // caller is not interested in error, release it here
 670                 CFRelease(buf->error);
 671             }
 672             CFAllocatorDeallocate(kCFAllocatorSystemDefault, buf);
 673             CFAllocatorDeallocate(kCFAllocatorSystemDefault, offsets);
 674             return 0;
 675         }
 676     }
 677     CFRelease(objtable);
 678     CFRelease(objlist);
 679
 680     length_so_far = buf->written + buf->used;
 681     trailer._offsetTableOffset = CFSwapInt64HostToBig(length_so_far);
 682     trailer._offsetIntSize = _byteCount(length_so_far);
 683
 684     for (idx = 0; idx < cnt; idx++) {
 685         uint64_t swapped = CFSwapInt64HostToBig(offsets[idx]);
 686         uint8_t *source = (uint8_t *)&swapped;
 687         bufferWrite(buf, source + sizeof(*offsets) - trailer._offsetIntSize, trailer._offsetIntSize);
 688     }
 689     length_so_far += cnt * trailer._offsetIntSize;
 690     CFAllocatorDeallocate(kCFAllocatorSystemDefault, offsets);
 691
 692     bufferWrite(buf, (uint8_t *)&trailer, sizeof(trailer));
 693     bufferFlush(buf);
 694     length_so_far += sizeof(trailer);
 695     if (buf->error) {
 696         if (error) {
 697             // caller will release error
 698             *error = buf->error;
 699         } else {
 700             CFRelease(buf->error);
 701         }
 702         CFAllocatorDeallocate(kCFAllocatorSystemDefault, buf);
 703         return 0;
 704     }
 705     CFAllocatorDeallocate(kCFAllocatorSystemDefault, buf);
 706     return (CFIndex)length_so_far;
 707 }
 708
 709
 710 CFIndex __CFBinaryPlistWriteToStream(CFPropertyListRef plist, CFTypeRef stream) {
 711     return __CFBinaryPlistWrite(plist, stream, 0, 0, NULL);
 712 }
 713
 714 // to be removed soon
 715 CFIndex __CFBinaryPlistWriteToStreamWithEstimate(CFPropertyListRef plist, CFTypeRef stream, uint64_t estimate) {
 716     return __CFBinaryPlistWrite(plist, stream, estimate, 0, NULL);
 717 }
 718
 719 // to be removed soon
 720 CFIndex __CFBinaryPlistWriteToStreamWithOptions(CFPropertyListRef plist, CFTypeRef stream, uint64_t estimate, CFOptionFlags options) {
 721     return __CFBinaryPlistWrite(plist, stream, estimate, options, NULL);
 722 }
 723
 724
 725 #pragma mark -
 726 #pragma mark Reading
 727
 728 #define FAIL_FALSE      do { return false; } while (0)
 729 #define FAIL_MAXOFFSET  do { return UINT64_MAX; } while (0)
 730
 731 CF_PRIVATE bool __CFBinaryPlistCreateObjectFiltered(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFAllocatorRef allocator, CFOptionFlags mutabilityOption, CFMutableDictionaryRef objects, CFMutableSetRef set, CFIndex curDepth, CFSetRef keyPaths, CFPropertyListRef *plist);
 732
 733 /* Grab a valSize-bytes integer out of the buffer pointed at by data and return it.
 734  */
 735 CF_INLINE uint64_t _getSizedInt(const uint8_t *data, uint8_t valSize) {
 736 #if defined(__i386__) || defined(__x86_64__)
 737     if (valSize == 1) {
 738         return (uint64_t)*data;
 739     } else if (valSize == 2) {
 740         uint16_t val = *(uint16_t *)data;
 741         return (uint64_t)CFSwapInt16BigToHost(val);
 742     } else if (valSize == 4) {
 743         uint32_t val = *(uint32_t *)data;
 744         return (uint64_t)CFSwapInt32BigToHost(val);
 745     } else if (valSize == 8) {
 746         uint64_t val = *(uint64_t *)data;
 747         return CFSwapInt64BigToHost(val);
 748     }
 749 #endif
 750     // Compatability with existing archives, including anything with a non-power-of-2
 751     // size and 16-byte values, and architectures that don't support unaligned access
 752     uint64_t res = 0;
 753     for (CFIndex idx = 0; idx < valSize; idx++) {
 754         res = (res << 8) + data[idx];
 755     }
 756     return res;
 757 }
 758
 759 bool __CFBinaryPlistGetTopLevelInfo(const uint8_t *databytes, uint64_t datalen, uint8_t *marker, uint64_t *offset, CFBinaryPlistTrailer *trailer) {
 760     CFBinaryPlistTrailer trail;
 761
 762     initStatics();
 763
 764     if (!databytes || datalen < sizeof(trail) + 8 + 1) FAIL_FALSE;
 765     // Tiger and earlier will parse "bplist00"
 766     // Leopard will parse "bplist00" or "bplist01"
 767     // SnowLeopard will parse "bplist0?" where ? is any one character
 768     if (0 != memcmp("bplist0", databytes, 7)) {
 769         FAIL_FALSE;
 770     }
 771     memmove(&trail, databytes + datalen - sizeof(trail), sizeof(trail));
 772     // In Leopard, the unused bytes in the trailer must be 0 or the parse will fail
 773     // This check is not present in Tiger and earlier or after Leopard
 774     trail._numObjects = CFSwapInt64BigToHost(trail._numObjects);
 775     trail._topObject = CFSwapInt64BigToHost(trail._topObject);
 776     trail._offsetTableOffset = CFSwapInt64BigToHost(trail._offsetTableOffset);
 777
 778     // Don't overflow on the number of objects or offset of the table
 779     if (LONG_MAX < trail._numObjects) FAIL_FALSE;
 780     if (LONG_MAX < trail._offsetTableOffset) FAIL_FALSE;
 781
 782     //  Must be a minimum of 1 object
 783     if (trail._numObjects < 1) FAIL_FALSE;
 784
 785     // The ref to the top object must be a value in the range of 1 to the total number of objects
 786     if (trail._numObjects <= trail._topObject) FAIL_FALSE;
 787
 788     // The offset table must be after at least 9 bytes of other data ('bplist??' + 1 byte of object table data).
 789     if (trail._offsetTableOffset < 9) FAIL_FALSE;
 790
 791     // The trailer must point to a value before itself in the data.
 792     if (datalen - sizeof(trail) <= trail._offsetTableOffset) FAIL_FALSE;
 793
 794     // Minimum of 1 byte for the size of integers and references in the data
 795     if (trail._offsetIntSize < 1) FAIL_FALSE;
 796     if (trail._objectRefSize < 1) FAIL_FALSE;
 797
 798     int32_t err = CF_NO_ERROR;
 799
 800     // The total size of the offset table (number of objects * size of each int in the table) must not overflow
 801     uint64_t offsetIntSize = trail._offsetIntSize;
 802     uint64_t offsetTableSize = __check_uint64_mul_unsigned_unsigned(trail._numObjects, offsetIntSize, &err);
 803     if (CF_NO_ERROR!= err) FAIL_FALSE;
 804
 805     // The offset table must have at least 1 entry
 806     if (offsetTableSize < 1) FAIL_FALSE;
 807
 808     // Make sure the size of the offset table and data sections do not overflow
 809     uint64_t objectDataSize = trail._offsetTableOffset - 8;
 810     uint64_t tmpSum = __check_uint64_add_unsigned_unsigned(8, objectDataSize, &err);
 811     tmpSum = __check_uint64_add_unsigned_unsigned(tmpSum, offsetTableSize, &err);
 812     tmpSum = __check_uint64_add_unsigned_unsigned(tmpSum, sizeof(trail), &err);
 813     if (CF_NO_ERROR != err) FAIL_FALSE;
 814
 815     // The total size of the data should be equal to the sum of offsetTableOffset + sizeof(trailer)
 816     if (datalen != tmpSum) FAIL_FALSE;
 817
 818     // The object refs must be the right size to point into the offset table. That is, if the count of objects is 260, but only 1 byte is used to store references (max value 255), something is wrong.
 819     if (trail._objectRefSize < 8 && (1ULL << (8 * trail._objectRefSize)) <= trail._numObjects) FAIL_FALSE;
 820
 821     // The integers used for pointers in the offset table must be able to reach as far as the start of the offset table.
 822     if (trail._offsetIntSize < 8 && (1ULL << (8 * trail._offsetIntSize)) <= trail._offsetTableOffset) FAIL_FALSE;
 823
 824
 825     (void)check_ptr_add(databytes, 8, &err);
 826     if (CF_NO_ERROR != err) FAIL_FALSE;
 827     const uint8_t *offsetsFirstByte = check_ptr_add(databytes, trail._offsetTableOffset, &err);
 828     if (CF_NO_ERROR != err) FAIL_FALSE;
 829     (void)check_ptr_add(offsetsFirstByte, offsetTableSize - 1, &err);
 830     if (CF_NO_ERROR != err) FAIL_FALSE;
 831
 832     const uint8_t *bytesptr = databytes + trail._offsetTableOffset;
 833     uint64_t maxOffset = trail._offsetTableOffset - 1;
 834     for (CFIndex idx = 0; idx < trail._numObjects; idx++) {
 835         uint64_t off = _getSizedInt(bytesptr, trail._offsetIntSize);
 836         if (maxOffset < off) FAIL_FALSE;
 837         bytesptr += trail._offsetIntSize;
 838     }
 839
 840     bytesptr = databytes + trail._offsetTableOffset + trail._topObject * trail._offsetIntSize;
 841     uint64_t off = _getSizedInt(bytesptr, trail._offsetIntSize);
 842     if (off < 8 || trail._offsetTableOffset <= off) FAIL_FALSE;
 843     if (trailer) *trailer = trail;
 844     if (offset) *offset = off;
 845     if (marker) *marker = *(databytes + off);
 846     return true;
 847 }
 848
 849 CF_INLINE Boolean _plistIsPrimitive(CFPropertyListRef pl) {
 850     CFTypeID type = CFGetTypeID(pl);
 851     if (dicttype == type || arraytype == type || settype == type || osettype == type) FAIL_FALSE;
 852     return true;
 853 }
 854
 855 CF_INLINE bool _readInt(const uint8_t *ptr, const uint8_t *end_byte_ptr, uint64_t *bigint, const uint8_t **newptr) {
 856     if (end_byte_ptr < ptr) FAIL_FALSE;
 857     uint8_t marker = *ptr++;
 858     if ((marker & 0xf0) != kCFBinaryPlistMarkerInt) FAIL_FALSE;
 859     uint64_t cnt = 1 << (marker & 0x0f);
 860     int32_t err = CF_NO_ERROR;
 861     const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
 862     if (CF_NO_ERROR != err) FAIL_FALSE;
 863     if (end_byte_ptr < extent) FAIL_FALSE;
 864     // integers are not required to be in the most compact possible representation, but only the last 64 bits are significant currently
 865     *bigint = _getSizedInt(ptr, cnt);
 866     ptr += cnt;
 867     if (newptr) *newptr = ptr;
 868     return true;
 869 }
 870
 871 // bytesptr points at a ref
 872 CF_INLINE uint64_t _getOffsetOfRefAt(const uint8_t *databytes, const uint8_t *bytesptr, const CFBinaryPlistTrailer *trailer) {
 873     // *trailer contents are trusted, even for overflows -- was checked when the trailer was parsed;
 874     // this pointer arithmetic and the multiplication was also already done once and checked,
 875     // and the offsetTable was already validated.
 876     const uint8_t *objectsFirstByte = databytes + 8;
 877     const uint8_t *offsetsFirstByte = databytes + trailer->_offsetTableOffset;
 878     if (bytesptr < objectsFirstByte || offsetsFirstByte - trailer->_objectRefSize < bytesptr) FAIL_MAXOFFSET;
 879
 880     uint64_t ref = _getSizedInt(bytesptr, trailer->_objectRefSize);
 881     if (trailer->_numObjects <= ref) FAIL_MAXOFFSET;
 882
 883     bytesptr = databytes + trailer->_offsetTableOffset + ref * trailer->_offsetIntSize;
 884     uint64_t off = _getSizedInt(bytesptr, trailer->_offsetIntSize);
 885     return off;
 886 }
 887
 888 bool __CFBinaryPlistGetOffsetForValueFromArray2(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFIndex idx, uint64_t *offset, CFMutableDictionaryRef objects) {
 889     uint64_t objectsRangeStart = 8, objectsRangeEnd = trailer->_offsetTableOffset - 1;
 890     if (startOffset < objectsRangeStart || objectsRangeEnd < startOffset) FAIL_FALSE;
 891     const uint8_t *ptr = databytes + startOffset;
 892     uint8_t marker = *ptr;
 893     if ((marker & 0xf0) != kCFBinaryPlistMarkerArray) FAIL_FALSE;
 894     int32_t err = CF_NO_ERROR;
 895     ptr = check_ptr_add(ptr, 1, &err);
 896     if (CF_NO_ERROR != err) FAIL_FALSE;
 897     uint64_t cnt = (marker & 0x0f);
 898     if (0xf == cnt) {
 899         uint64_t bigint;
 900         if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
 901         if (LONG_MAX < bigint) FAIL_FALSE;
 902         cnt = bigint;
 903     }
 904     if (cnt <= idx) FAIL_FALSE;
 905     size_t byte_cnt = check_size_t_mul(cnt, trailer->_objectRefSize, &err);
 906     if (CF_NO_ERROR != err) FAIL_FALSE;
 907     const uint8_t *extent = check_ptr_add(ptr, byte_cnt, &err) - 1;
 908     if (CF_NO_ERROR != err) FAIL_FALSE;
 909     if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
 910     uint64_t off = _getOffsetOfRefAt(databytes, ptr + idx * trailer->_objectRefSize, trailer);
 911     if (offset) *offset = off;
 912     return true;
 913 }
 914
 915 /* Get the offset for a value in a dictionary in a binary property list.
 916  @param databytes A pointer to the start of the binary property list data.
 917  @param datalen The length of the data.
 918  @param startOffset The offset at which the dictionary starts.
 919  @param trailer A pointer to a filled out trailer structure (use __CFBinaryPlistGetTopLevelInfo).
 920  @param key A string key in the dictionary that should be searched for.
 921  @param koffset Will be filled out with the offset to the key in the data bytes.
 922  @param voffset Will be filled out with the offset to the value in the data bytes.
 923  @param unused Unused parameter.
 924  @param objects Used for caching objects. Should be a valid CFMutableDictionaryRef.
 925  @return True if the key was found, false otherwise.
 926 */
 927 bool __CFBinaryPlistGetOffsetForValueFromDictionary3(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFTypeRef key, uint64_t *koffset, uint64_t *voffset, Boolean unused, CFMutableDictionaryRef objects) {
 928
 929     // Require a key that is a plist primitive
 930     if (!key || !_plistIsPrimitive(key)) FAIL_FALSE;
 931
 932     // Require that startOffset is in the range of the object table
 933     uint64_t objectsRangeStart = 8, objectsRangeEnd = trailer->_offsetTableOffset - 1;
 934     if (startOffset < objectsRangeStart || objectsRangeEnd < startOffset) FAIL_FALSE;
 935
 936     // ptr is the start of the dictionary we are reading
 937     const uint8_t *ptr = databytes + startOffset;
 938
 939     // Check that the data pointer actually points to a dictionary
 940     uint8_t marker = *ptr;
 941     if ((marker & 0xf0) != kCFBinaryPlistMarkerDict) FAIL_FALSE;
 942
 943     // Get the number of objects in this dictionary
 944     int32_t err = CF_NO_ERROR;
 945     ptr = check_ptr_add(ptr, 1, &err);
 946     if (CF_NO_ERROR != err) FAIL_FALSE;
 947     uint64_t cnt = (marker & 0x0f);
 948     if (0xf == cnt) {
 949         uint64_t bigint = 0;
 950         if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
 951         if (LONG_MAX < bigint) FAIL_FALSE;
 952         cnt = bigint;
 953     }
 954
 955     // Total number of objects (keys + values) is cnt * 2
 956     cnt = check_size_t_mul(cnt, 2, &err);
 957     if (CF_NO_ERROR != err) FAIL_FALSE;
 958     size_t byte_cnt = check_size_t_mul(cnt, trailer->_objectRefSize, &err);
 959     if (CF_NO_ERROR != err) FAIL_FALSE;
 960
 961     // Find the end of the dictionary
 962     const uint8_t *extent = check_ptr_add(ptr, byte_cnt, &err) - 1;
 963     if (CF_NO_ERROR != err) FAIL_FALSE;
 964
 965     // Check that we didn't overflow the size of the dictionary
 966     if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
 967
 968     // For short keys (15 bytes or less) in ASCII form, we can do a quick comparison check
 969     // We get the pointer or copy the buffer here, outside of the loop
 970     CFIndex stringKeyLen = -1;
 971     if (CFGetTypeID(key) == stringtype) {
 972         stringKeyLen = CFStringGetLength((CFStringRef)key);
 973     }
 974
 975     // Find the object in the dictionary with this key
 976     cnt = cnt / 2;
 977     uint64_t totalKeySize = cnt * trailer->_objectRefSize;
 978     uint64_t off;
 979     Boolean match = false;
 980     CFPropertyListRef keyInData = NULL;
 981
 982 #define KEY_BUFF_SIZE 16
 983     char keyBuffer[KEY_BUFF_SIZE];
 984     const char *keyBufferPtr = NULL;
 985
 986     // If we have a string for the key, then we will grab the ASCII encoded version of it, if possible, and do a memcmp on it
 987     if (stringKeyLen != -1) {
 988         // Since we will only be comparing ASCII strings, we can attempt to get a pointer using MacRoman encoding
 989         // (this is cheaper than a copy)
 990         if (!(keyBufferPtr = CFStringGetCStringPtr((CFStringRef)key, kCFStringEncodingMacRoman)) && stringKeyLen < KEY_BUFF_SIZE) {
 991             CFStringGetCString((CFStringRef)key, keyBuffer, KEY_BUFF_SIZE, kCFStringEncodingMacRoman);
 992             // The pointer should now point to our keyBuffer instead of the original string buffer, since we've copied it
 993             keyBufferPtr = keyBuffer;
 994         }
 995     }
 996
 997     // Perform linear search of the keys
 998     for (CFIndex idx = 0; idx < cnt; idx++) {
 999         off = _getOffsetOfRefAt(databytes, ptr, trailer);
1000         marker = *(databytes + off);
1001         // if it is an ASCII string in the data, then we do a memcmp. If the key isn't ASCII, then it won't pass the compare, unless it hits some odd edge case of the ASCII string actually containing the unicode escape sequence.
1002         if (keyBufferPtr && (marker & 0xf0) == kCFBinaryPlistMarkerASCIIString) {
1003             CFIndex len = marker & 0x0f;
1004             // move past the marker
1005             const uint8_t *ptr2 = databytes + off;
1006             err = CF_NO_ERROR;
1007             ptr2 = check_ptr_add(ptr2, 1, &err);
1008             if (CF_NO_ERROR != err) FAIL_FALSE;
1009
1010             // If the key's length is large, and the length we are querying is also large, then we have to read it in. If stringKeyLen is less than 0xf, then len will never be equal to it if it was encoded as large.
1011             if (0xf == len && stringKeyLen >= 0xf) {
1012                 uint64_t bigint = 0;
1013                 if (!_readInt(ptr2, databytes + objectsRangeEnd, &bigint, &ptr2)) FAIL_FALSE;
1014                 if (LONG_MAX < bigint) FAIL_FALSE;
1015                 len = (CFIndex)bigint;
1016             }
1017
1018             if (len == stringKeyLen) {
1019                 err = CF_NO_ERROR;
1020                 extent = check_ptr_add(ptr2, len, &err);
1021                 if (CF_NO_ERROR != err) FAIL_FALSE;
1022
1023                 if (databytes + trailer->_offsetTableOffset <= extent) FAIL_FALSE;
1024
1025                 // Compare the key to this potential match
1026                 if (memcmp(ptr2, keyBufferPtr, stringKeyLen) == 0) {
1027                     match = true;
1028                 }
1029             }
1030         } else {
1031             // temp object not saved in 'objects', because we don't know what allocator to use
1032             // (what allocator __CFBinaryPlistCreateObjectFiltered() or __CFBinaryPlistCreateObject()
1033             //  will eventually be called with which results in that object)
1034             keyInData = NULL;
1035             if (!__CFBinaryPlistCreateObjectFiltered(databytes, datalen, off, trailer, kCFAllocatorSystemDefault, kCFPropertyListImmutable, NULL /*objects*/, NULL, 0, NULL, &keyInData) || !_plistIsPrimitive(keyInData)) {
1036                 if (keyInData) CFRelease(keyInData);
1037                 FAIL_FALSE;
1038             }
1039
1040             match = CFEqual(key, keyInData);
1041             CFRelease(keyInData);
1042         }
1043
1044         if (match) {
1045             if (koffset) *koffset = off;
1046             if (voffset) *voffset = _getOffsetOfRefAt(databytes, ptr + totalKeySize, trailer);
1047             return true;
1048         }
1049
1050         ptr += trailer->_objectRefSize;
1051     }
1052
1053     FAIL_FALSE;
1054 }
1055
1056 extern CFDictionaryRef __CFDictionaryCreateTransfer(CFAllocatorRef allocator, const void * *klist, const void * *vlist, CFIndex numValues);
1057 extern CFSetRef __CFSetCreateTransfer(CFAllocatorRef allocator, const void * *klist, CFIndex numValues);
1058 extern CFArrayRef __CFArrayCreateTransfer(CFAllocatorRef allocator, const void * *klist, CFIndex numValues);
1059 CF_PRIVATE void __CFPropertyListCreateSplitKeypaths(CFAllocatorRef allocator, CFSetRef currentKeys, CFSetRef *theseKeys, CFSetRef *nextKeys);
1060
1061 CF_PRIVATE bool __CFBinaryPlistCreateObjectFiltered(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFAllocatorRef allocator, CFOptionFlags mutabilityOption, CFMutableDictionaryRef objects, CFMutableSetRef set, CFIndex curDepth, CFSetRef keyPaths, CFPropertyListRef *plist) {
1062
1063     if (objects) {
1064         *plist = CFDictionaryGetValue(objects, (const void *)(uintptr_t)startOffset);
1065         if (*plist) {
1066             // have to assume that '*plist' was previously created with same allocator that is now being passed in
1067             CFRetain(*plist);
1068             return true;
1069         }
1070     }
1071
1072     // at any one invocation of this function, set should contain the offsets in the "path" down to this object
1073     if (set && CFSetContainsValue(set, (const void *)(uintptr_t)startOffset)) FAIL_FALSE;
1074
1075     // databytes is trusted to be at least datalen bytes long
1076     // *trailer contents are trusted, even for overflows -- was checked when the trailer was parsed
1077     uint64_t objectsRangeStart = 8, objectsRangeEnd = trailer->_offsetTableOffset - 1;
1078     if (startOffset < objectsRangeStart || objectsRangeEnd < startOffset) FAIL_FALSE;
1079
1080     uint64_t off;
1081     CFPropertyListRef *list, buffer[256];
1082
1083     uint8_t marker = *(databytes + startOffset);
1084     switch (marker & 0xf0) {
1085     case kCFBinaryPlistMarkerNull:
1086         switch (marker) {
1087         case kCFBinaryPlistMarkerNull:
1088             *plist = kCFNull;
1089             return true;
1090         case kCFBinaryPlistMarkerFalse:
1091             *plist = !(0) ? CFRetain(kCFBooleanFalse) : kCFBooleanFalse;
1092             return true;
1093         case kCFBinaryPlistMarkerTrue:
1094             *plist = !(0) ? CFRetain(kCFBooleanTrue) : kCFBooleanTrue;
1095             return true;
1096         }
1097         FAIL_FALSE;
1098     case kCFBinaryPlistMarkerInt:
1099     {
1100         const uint8_t *ptr = (databytes + startOffset);
1101         int32_t err = CF_NO_ERROR;
1102         ptr = check_ptr_add(ptr, 1, &err);
1103         if (CF_NO_ERROR != err) FAIL_FALSE;
1104         uint64_t cnt = 1 << (marker & 0x0f);
1105         const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
1106         if (CF_NO_ERROR != err) FAIL_FALSE;
1107         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1108         if (16 < cnt) FAIL_FALSE;
1109         // in format version '00', 1, 2, and 4-byte integers have to be interpreted as unsigned,
1110         // whereas 8-byte integers are signed (and 16-byte when available)
1111         // negative 1, 2, 4-byte integers are always emitted as 8 bytes in format '00'
1112         // integers are not required to be in the most compact possible representation, but only the last 64 bits are significant currently
1113         uint64_t bigint = _getSizedInt(ptr, cnt);
1114         if (8 < cnt) {
1115             CFSInt128Struct val;
1116             val.high = 0;
1117             val.low = bigint;
1118             *plist = CFNumberCreate(allocator, kCFNumberSInt128Type, &val);
1119         } else {
1120             *plist = CFNumberCreate(allocator, kCFNumberSInt64Type, &bigint);
1121         }
1122         // these are always immutable
1123         if (objects && *plist) {
1124             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1125         }
1126         return (*plist) ? true : false;
1127     }
1128     case kCFBinaryPlistMarkerReal:
1129         switch (marker & 0x0f) {
1130         case 2: {
1131             const uint8_t *ptr = (databytes + startOffset);
1132             int32_t err = CF_NO_ERROR;
1133             ptr = check_ptr_add(ptr, 1, &err);
1134             if (CF_NO_ERROR != err) FAIL_FALSE;
1135             const uint8_t *extent = check_ptr_add(ptr, 4, &err) - 1;
1136             if (CF_NO_ERROR != err) FAIL_FALSE;
1137             if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1138             CFSwappedFloat32 swapped32;
1139             memmove(&swapped32, ptr, 4);
1140             float f = CFConvertFloat32SwappedToHost(swapped32);
1141             *plist = CFNumberCreate(allocator, kCFNumberFloat32Type, &f);
1142             // these are always immutable
1143             if (objects && *plist) {
1144                 CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1145             }
1146             return (*plist) ? true : false;
1147         }
1148         case 3: {
1149             const uint8_t *ptr = (databytes + startOffset);
1150             int32_t err = CF_NO_ERROR;
1151             ptr = check_ptr_add(ptr, 1, &err);
1152             if (CF_NO_ERROR != err) FAIL_FALSE;
1153             const uint8_t *extent = check_ptr_add(ptr, 8, &err) - 1;
1154             if (CF_NO_ERROR != err) FAIL_FALSE;
1155             if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1156             CFSwappedFloat64 swapped64;
1157             memmove(&swapped64, ptr, 8);
1158             double d = CFConvertFloat64SwappedToHost(swapped64);
1159             *plist = CFNumberCreate(allocator, kCFNumberFloat64Type, &d);
1160             // these are always immutable
1161             if (objects && *plist) {
1162                 CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1163             }
1164             return (*plist) ? true : false;
1165         }
1166         }
1167         FAIL_FALSE;
1168     case kCFBinaryPlistMarkerDate & 0xf0:
1169         switch (marker) {
1170         case kCFBinaryPlistMarkerDate: {
1171             const uint8_t *ptr = (databytes + startOffset);
1172             int32_t err = CF_NO_ERROR;
1173             ptr = check_ptr_add(ptr, 1, &err);
1174             if (CF_NO_ERROR != err) FAIL_FALSE;
1175             const uint8_t *extent = check_ptr_add(ptr, 8, &err) - 1;
1176             if (CF_NO_ERROR != err) FAIL_FALSE;
1177             if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1178             CFSwappedFloat64 swapped64;
1179             memmove(&swapped64, ptr, 8);
1180             double d = CFConvertFloat64SwappedToHost(swapped64);
1181             *plist = CFDateCreate(allocator, d);
1182             // these are always immutable
1183             if (objects && *plist) {
1184                 CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1185             }
1186             return (*plist) ? true : false;
1187         }
1188         }
1189         FAIL_FALSE;
1190     case kCFBinaryPlistMarkerData: {
1191         const uint8_t *ptr = databytes + startOffset;
1192         int32_t err = CF_NO_ERROR;
1193         ptr = check_ptr_add(ptr, 1, &err);
1194         if (CF_NO_ERROR != err) FAIL_FALSE;
1195         CFIndex cnt = marker & 0x0f;
1196         if (0xf == cnt) {
1197             uint64_t bigint = 0;
1198             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1199             if (LONG_MAX < bigint) FAIL_FALSE;
1200             cnt = (CFIndex)bigint;
1201         }
1202         const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
1203         if (CF_NO_ERROR != err) FAIL_FALSE;
1204         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1205         if (mutabilityOption == kCFPropertyListMutableContainersAndLeaves) {
1206             *plist = CFDataCreateMutable(allocator, 0);
1207             if (*plist) CFDataAppendBytes((CFMutableDataRef)*plist, ptr, cnt);
1208         } else {
1209             *plist = CFDataCreate(allocator, ptr, cnt);
1210         }
1211         if (objects && *plist && (mutabilityOption != kCFPropertyListMutableContainersAndLeaves)) {
1212             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1213         }
1214         return (*plist) ? true : false;
1215         }
1216     case kCFBinaryPlistMarkerASCIIString: {
1217         const uint8_t *ptr = databytes + startOffset;
1218         int32_t err = CF_NO_ERROR;
1219         ptr = check_ptr_add(ptr, 1, &err);
1220         if (CF_NO_ERROR != err) FAIL_FALSE;
1221         CFIndex cnt = marker & 0x0f;
1222         if (0xf == cnt) {
1223             uint64_t bigint = 0;
1224             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1225             if (LONG_MAX < bigint) FAIL_FALSE;
1226             cnt = (CFIndex)bigint;
1227         }
1228         const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
1229         if (CF_NO_ERROR != err) FAIL_FALSE;
1230         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1231         if (mutabilityOption == kCFPropertyListMutableContainersAndLeaves) {
1232             CFStringRef str = CFStringCreateWithBytes(allocator, ptr, cnt, kCFStringEncodingASCII, false);
1233             *plist = str ? CFStringCreateMutableCopy(allocator, 0, str) : NULL;
1234             if (str) CFRelease(str);
1235         } else {
1236             *plist = CFStringCreateWithBytes(allocator, ptr, cnt, kCFStringEncodingASCII, false);
1237         }
1238         if (objects && *plist && (mutabilityOption != kCFPropertyListMutableContainersAndLeaves)) {
1239             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1240         }
1241         return (*plist) ? true : false;
1242         }
1243     case kCFBinaryPlistMarkerUnicode16String: {
1244         const uint8_t *ptr = databytes + startOffset;
1245         int32_t err = CF_NO_ERROR;
1246         ptr = check_ptr_add(ptr, 1, &err);
1247         if (CF_NO_ERROR != err) FAIL_FALSE;
1248         CFIndex cnt = marker & 0x0f;
1249         if (0xf == cnt) {
1250             uint64_t bigint = 0;
1251             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1252             if (LONG_MAX < bigint) FAIL_FALSE;
1253             cnt = (CFIndex)bigint;
1254         }
1255         const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
1256         extent = check_ptr_add(extent, cnt, &err);      // 2 bytes per character
1257         if (CF_NO_ERROR != err) FAIL_FALSE;
1258         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1259         size_t byte_cnt = check_size_t_mul(cnt, sizeof(UniChar), &err);
1260         if (CF_NO_ERROR != err) FAIL_FALSE;
1261         UniChar *chars = (UniChar *)CFAllocatorAllocate(kCFAllocatorSystemDefault, byte_cnt, 0);
1262         if (!chars) FAIL_FALSE;
1263         memmove(chars, ptr, byte_cnt);
1264         for (CFIndex idx = 0; idx < cnt; idx++) {
1265             chars[idx] = CFSwapInt16BigToHost(chars[idx]);
1266         }
1267         if (mutabilityOption == kCFPropertyListMutableContainersAndLeaves) {
1268             CFStringRef str = CFStringCreateWithCharacters(allocator, chars, cnt);
1269             *plist = str ? CFStringCreateMutableCopy(allocator, 0, str) : NULL;
1270             if (str) CFRelease(str);
1271         } else {
1272             *plist = CFStringCreateWithCharacters(allocator, chars, cnt);
1273         }
1274         CFAllocatorDeallocate(kCFAllocatorSystemDefault, chars);
1275         if (objects && *plist && (mutabilityOption != kCFPropertyListMutableContainersAndLeaves)) {
1276             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1277         }
1278         return (*plist) ? true : false;
1279         }
1280     case kCFBinaryPlistMarkerUID: {
1281         const uint8_t *ptr = databytes + startOffset;
1282         int32_t err = CF_NO_ERROR;
1283         ptr = check_ptr_add(ptr, 1, &err);
1284         if (CF_NO_ERROR != err) FAIL_FALSE;
1285         CFIndex cnt = (marker & 0x0f) + 1;
1286         const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
1287         if (CF_NO_ERROR != err) FAIL_FALSE;
1288         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1289         // uids are not required to be in the most compact possible representation, but only the last 64 bits are significant currently
1290         uint64_t bigint = _getSizedInt(ptr, cnt);
1291         if (UINT32_MAX < bigint) FAIL_FALSE;
1292         *plist = _CFKeyedArchiverUIDCreate(allocator, (uint32_t)bigint);
1293         // these are always immutable
1294         if (objects && *plist) {
1295             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1296         }
1297         return (*plist) ? true : false;
1298         }
1299     case kCFBinaryPlistMarkerArray:
1300     case kCFBinaryPlistMarkerSet: {
1301         const uint8_t *ptr = databytes + startOffset;
1302         int32_t err = CF_NO_ERROR;
1303         ptr = check_ptr_add(ptr, 1, &err);
1304         if (CF_NO_ERROR != err) FAIL_FALSE;
1305         CFIndex arrayCount = marker & 0x0f;
1306         if (0xf == arrayCount) {
1307             uint64_t bigint = 0;
1308             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1309             if (LONG_MAX < bigint) FAIL_FALSE;
1310             arrayCount = (CFIndex)bigint;
1311         }
1312         size_t byte_cnt = check_size_t_mul(arrayCount, trailer->_objectRefSize, &err);
1313         if (CF_NO_ERROR != err) FAIL_FALSE;
1314         const uint8_t *extent = check_ptr_add(ptr, byte_cnt, &err) - 1;
1315         if (CF_NO_ERROR != err) FAIL_FALSE;
1316         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1317         byte_cnt = check_size_t_mul(arrayCount, sizeof(CFPropertyListRef), &err);
1318         if (CF_NO_ERROR != err) FAIL_FALSE;
1319         list = (arrayCount <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, byte_cnt, __kCFAllocatorGCScannedMemory);
1320         if (!list) FAIL_FALSE;
1321         Boolean madeSet = false;
1322         if (!set && 15 < curDepth) {
1323             set = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, NULL);
1324             madeSet = set ? true : false;
1325         }
1326
1327         if (set) CFSetAddValue(set, (const void *)(uintptr_t)startOffset);
1328         if ((marker & 0xf0) == kCFBinaryPlistMarkerArray && keyPaths) {
1329             // Only get a subset of this array
1330             CFSetRef theseKeys, nextKeys;
1331             __CFPropertyListCreateSplitKeypaths(kCFAllocatorSystemDefault, keyPaths, &theseKeys, &nextKeys);
1332
1333             Boolean success = true;
1334             CFMutableArrayRef array = CFArrayCreateMutable(allocator, CFSetGetCount(theseKeys), &kCFTypeArrayCallBacks);
1335             if (theseKeys) {
1336                 CFTypeRef *keys = (CFTypeRef *)malloc(CFSetGetCount(theseKeys) * sizeof(CFTypeRef));
1337                 CFSetGetValues(theseKeys, keys);
1338                 for (CFIndex i = 0; i < CFSetGetCount(theseKeys); i++) {
1339                     CFStringRef key = (CFStringRef)keys[i];
1340                     SInt32 intValue = CFStringGetIntValue(key);
1341                     if ((intValue == 0 && CFStringCompare(CFSTR("0"), key, 0) != kCFCompareEqualTo) || intValue == INT_MAX || intValue == INT_MIN || intValue < 0) {
1342                         // skip, doesn't appear to be a proper integer
1343                     } else {
1344                         uint64_t valueOffset;
1345                         Boolean found = __CFBinaryPlistGetOffsetForValueFromArray2(databytes, datalen, startOffset, trailer, (CFIndex)intValue, &valueOffset, objects);
1346                         if (found) {
1347                             CFPropertyListRef result;
1348                             success = __CFBinaryPlistCreateObjectFiltered(databytes, datalen, valueOffset, trailer, allocator, mutabilityOption, objects, set, curDepth + 1, nextKeys, &result);
1349                             if (success) {
1350                                 CFArrayAppendValue(array, result);
1351                                 CFRelease(result);
1352                             } else {
1353                                 break;
1354                             }
1355                         }
1356                     }
1357                 }
1358
1359                 free(keys);
1360                 CFRelease(theseKeys);
1361             }
1362             if (nextKeys) CFRelease(nextKeys);
1363
1364             if (success) {
1365                 if (!(mutabilityOption == kCFPropertyListMutableContainers || mutabilityOption == kCFPropertyListMutableContainersAndLeaves)) {
1366                     // make immutable
1367                     *plist = CFArrayCreateCopy(allocator, array);
1368                     CFRelease(array);
1369                 } else {
1370                     *plist = array;
1371                 }
1372             } else if (array) {
1373                 CFRelease(array);
1374             }
1375         } else {
1376             for (CFIndex idx = 0; idx < arrayCount; idx++) {
1377                 CFPropertyListRef pl;
1378                 off = _getOffsetOfRefAt(databytes, ptr, trailer);
1379                 if (!__CFBinaryPlistCreateObjectFiltered(databytes, datalen, off, trailer, allocator, mutabilityOption, objects, set, curDepth + 1, NULL, &pl)) {
1380                     while (idx--) {
1381                         CFRelease(list[idx]);
1382                     }
1383                     if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1384                     FAIL_FALSE;
1385                 }
1386                 __CFAssignWithWriteBarrier((void **)list + idx, (void *)pl);
1387                 ptr += trailer->_objectRefSize;
1388             }
1389             if ((marker & 0xf0) == kCFBinaryPlistMarkerArray) {
1390                 if (mutabilityOption != kCFPropertyListImmutable) {
1391                     *plist = CFArrayCreateMutable(allocator, 0, &kCFTypeArrayCallBacks);
1392                     CFArrayReplaceValues((CFMutableArrayRef)*plist, CFRangeMake(0, 0), list, arrayCount);
1393                     for (CFIndex idx = 0; idx < arrayCount; idx++) {
1394                         CFRelease(list[idx]);
1395                     }
1396                 } else {
1397                     if (!kCFUseCollectableAllocator) {
1398                         *plist = __CFArrayCreateTransfer(allocator, list, arrayCount);
1399                     } else {
1400                         *plist = CFArrayCreate(allocator, list, arrayCount, &kCFTypeArrayCallBacks);
1401                         for (CFIndex idx = 0; idx < arrayCount; idx++) {
1402                             CFRelease(list[idx]);
1403                         }
1404                     }
1405                 }
1406             } else {
1407                 if (mutabilityOption != kCFPropertyListImmutable) {
1408                     *plist = CFSetCreateMutable(allocator, 0, &kCFTypeSetCallBacks);
1409                     for (CFIndex idx = 0; idx < arrayCount; idx++) {
1410                         CFSetAddValue((CFMutableSetRef)*plist, list[idx]);
1411                     }
1412                     for (CFIndex idx = 0; idx < arrayCount; idx++) {
1413                         CFRelease(list[idx]);
1414                     }
1415                 } else {
1416                     if (!kCFUseCollectableAllocator) {
1417                         *plist = __CFSetCreateTransfer(allocator, list, arrayCount);
1418                     } else {
1419                         *plist = CFSetCreate(allocator, list, arrayCount, &kCFTypeSetCallBacks);
1420                         for (CFIndex idx = 0; idx < arrayCount; idx++) {
1421                             CFRelease(list[idx]);
1422                         }
1423                     }
1424                 }
1425             }
1426         }
1427         if (set) CFSetRemoveValue(set, (const void *)(uintptr_t)startOffset);
1428         if (madeSet) {
1429             CFRelease(set);
1430             set = NULL;
1431         }
1432         if (objects && *plist && (mutabilityOption == kCFPropertyListImmutable)) {
1433             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1434         }
1435         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1436         return (*plist) ? true : false;
1437         }
1438     case kCFBinaryPlistMarkerDict: {
1439         const uint8_t *ptr = databytes + startOffset;
1440         int32_t err = CF_NO_ERROR;
1441         ptr = check_ptr_add(ptr, 1, &err);
1442         if (CF_NO_ERROR != err) FAIL_FALSE;
1443         CFIndex dictionaryCount = marker & 0x0f;
1444         if (0xf == dictionaryCount) {
1445             uint64_t bigint = 0;
1446             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1447             if (LONG_MAX < bigint) FAIL_FALSE;
1448             dictionaryCount = (CFIndex)bigint;
1449         }
1450         dictionaryCount = check_size_t_mul(dictionaryCount, 2, &err);
1451         if (CF_NO_ERROR != err) FAIL_FALSE;
1452         size_t byte_cnt = check_size_t_mul(dictionaryCount, trailer->_objectRefSize, &err);
1453         if (CF_NO_ERROR != err) FAIL_FALSE;
1454         const uint8_t *extent = check_ptr_add(ptr, byte_cnt, &err) - 1;
1455         if (CF_NO_ERROR != err) FAIL_FALSE;
1456         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1457         byte_cnt = check_size_t_mul(dictionaryCount, sizeof(CFPropertyListRef), &err);
1458         if (CF_NO_ERROR != err) FAIL_FALSE;
1459         list = (dictionaryCount <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, byte_cnt, __kCFAllocatorGCScannedMemory);
1460         if (!list) FAIL_FALSE;
1461         Boolean madeSet = false;
1462         if (!set && 15 < curDepth) {
1463             set = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, NULL);
1464             madeSet = set ? true : false;
1465         }
1466
1467         if (set) CFSetAddValue(set, (const void *)(uintptr_t)startOffset);
1468         if (keyPaths) {
1469             // Only get a subset of this dictionary
1470             CFSetRef theseKeys, nextKeys;
1471             __CFPropertyListCreateSplitKeypaths(kCFAllocatorSystemDefault, keyPaths, &theseKeys, &nextKeys);
1472
1473             Boolean success = true;
1474             CFMutableDictionaryRef dict = CFDictionaryCreateMutable(allocator, CFSetGetCount(theseKeys), &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
1475             if (theseKeys) {
1476                 CFTypeRef *keys = (CFTypeRef *)malloc(CFSetGetCount(theseKeys) * sizeof(CFTypeRef));
1477                 CFSetGetValues(theseKeys, keys);
1478                 for (CFIndex i = 0; i < CFSetGetCount(theseKeys); i++) {
1479                     CFStringRef key = (CFStringRef)keys[i];
1480                     uint64_t keyOffset, valueOffset;
1481                     Boolean found = __CFBinaryPlistGetOffsetForValueFromDictionary3(databytes, datalen, startOffset, trailer, key, &keyOffset, &valueOffset, false, objects);
1482                     if (found) {
1483                         CFPropertyListRef result;
1484                         success = __CFBinaryPlistCreateObjectFiltered(databytes, datalen, valueOffset, trailer, allocator, mutabilityOption, objects, set, curDepth + 1, nextKeys, &result);
1485                         if (success) {
1486                             CFDictionarySetValue(dict, key, result);
1487                             CFRelease(result);
1488                         } else {
1489                             break;
1490                         }
1491                     }
1492                 }
1493
1494                 free(keys);
1495                 CFRelease(theseKeys);
1496             }
1497             if (nextKeys) CFRelease(nextKeys);
1498
1499             if (success) {
1500                 if (!(mutabilityOption == kCFPropertyListMutableContainers || mutabilityOption == kCFPropertyListMutableContainersAndLeaves)) {
1501                     // make immutable
1502                     *plist = CFDictionaryCreateCopy(allocator, dict);
1503                     CFRelease(dict);
1504                 } else {
1505                     *plist = dict;
1506                 }
1507             } else if (dict) {
1508                 CFRelease(dict);
1509             }
1510         } else {
1511             for (CFIndex idx = 0; idx < dictionaryCount; idx++) {
1512                 CFPropertyListRef pl = NULL;
1513                 off = _getOffsetOfRefAt(databytes, ptr, trailer);
1514                 if (!__CFBinaryPlistCreateObjectFiltered(databytes, datalen, off, trailer, allocator, mutabilityOption, objects, set, curDepth + 1, NULL, &pl) || (idx < dictionaryCount / 2 && !_plistIsPrimitive(pl))) {
1515                     if (pl && !(0)) CFRelease(pl);
1516                     while (idx--) {
1517                         CFRelease(list[idx]);
1518                     }
1519                     if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1520                     FAIL_FALSE;
1521                 }
1522                 __CFAssignWithWriteBarrier((void **)list + idx, (void *)pl);
1523                 ptr += trailer->_objectRefSize;
1524             }
1525             if (mutabilityOption != kCFPropertyListImmutable) {
1526                 *plist = CFDictionaryCreateMutable(allocator, 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
1527                 for (CFIndex idx = 0; idx < dictionaryCount / 2; idx++) {
1528                     CFDictionaryAddValue((CFMutableDictionaryRef)*plist, list[idx], list[idx + dictionaryCount / 2]);
1529                 }
1530                 for (CFIndex idx = 0; idx < dictionaryCount; idx++) {
1531                     CFRelease(list[idx]);
1532                 }
1533             } else {
1534                 if (!kCFUseCollectableAllocator) {
1535                     *plist = __CFDictionaryCreateTransfer(allocator, list, list + dictionaryCount / 2, dictionaryCount / 2);
1536                 } else {
1537                     *plist = CFDictionaryCreate(allocator, list, list + dictionaryCount / 2, dictionaryCount / 2, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
1538                     for (CFIndex idx = 0; idx < dictionaryCount; idx++) {
1539                         CFRelease(list[idx]);
1540                     }
1541                 }
1542             }
1543         }
1544         if (set) CFSetRemoveValue(set, (const void *)(uintptr_t)startOffset);
1545         if (madeSet) {
1546             CFRelease(set);
1547             set = NULL;
1548         }
1549         if (objects && *plist && (mutabilityOption == kCFPropertyListImmutable)) {
1550             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1551         }
1552         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1553         return (*plist) ? true : false;
1554         }
1555     }
1556     FAIL_FALSE;
1557 }
1558
1559 bool __CFBinaryPlistCreateObject(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFAllocatorRef allocator, CFOptionFlags mutabilityOption, CFMutableDictionaryRef objects, CFPropertyListRef *plist) {
1560         // for compatibility with Foundation's use, need to leave this here
1561     return __CFBinaryPlistCreateObjectFiltered(databytes, datalen, startOffset, trailer, allocator, mutabilityOption, objects, NULL, 0, NULL, plist);
1562 }
1563
1564 CF_PRIVATE bool __CFTryParseBinaryPlist(CFAllocatorRef allocator, CFDataRef data, CFOptionFlags option, CFPropertyListRef *plist, CFStringRef *errorString) {
1565     uint8_t marker;
1566     CFBinaryPlistTrailer trailer;
1567     uint64_t offset;
1568     const uint8_t *databytes = CFDataGetBytePtr(data);
1569     uint64_t datalen = CFDataGetLength(data);
1570
1571     if (8 <= datalen && __CFBinaryPlistGetTopLevelInfo(databytes, datalen, &marker, &offset, &trailer)) {
1572         // FALSE: We know for binary plist parsing that the result objects will be retained
1573         // by their containing collections as the parsing proceeds, so we do not need
1574         // to use retaining callbacks for the objects map in this case. WHY: the file might
1575         // be malformed and contain hash-equal keys for the same dictionary (for example)
1576         // and the later key will cause the previous one to be released when we set the second
1577         // in the dictionary.
1578         CFMutableDictionaryRef objects = CFDictionaryCreateMutable(kCFAllocatorSystemDefault, 0, NULL, &kCFTypeDictionaryValueCallBacks);
1579         _CFDictionarySetCapacity(objects, trailer._numObjects);
1580         CFPropertyListRef pl = NULL;
1581         bool result = true;
1582         if (__CFBinaryPlistCreateObjectFiltered(databytes, datalen, offset, &trailer, allocator, option, objects, NULL, 0, NULL, &pl)) {
1583             if (plist) *plist = pl;
1584 #if 0
1585 // code to check the 1.5 version code against any binary plist successfully parsed above
1586 extern size_t __CFBinaryPlistWrite15(CFPropertyListRef plist, CFMutableDataRef data, CFErrorRef *error);
1587 extern CFPropertyListRef __CFBinaryPlistCreate15(const uint8_t *databytes, uint64_t datalen, CFErrorRef *error);
1588
1589 CFMutableDataRef mdata = CFDataCreateMutable(0, 0);
1590 size_t s = __CFBinaryPlistWrite15(pl, mdata, NULL);
1591 //double ratio = (double)s / (double)datalen;
1592 //if (ratio < 0.75 || ratio > 4.0) CFLog(4, CFSTR("@@@ note: Binary plist of %ld bytes is %ld bytes (%f) in version 1.5"), datalen, s, ratio);
1593 if (s != CFDataGetLength(mdata)) CFLog(3, CFSTR("### error: returned length not equal to data length (%ld != %ld)"), s, CFDataGetLength(mdata));
1594 CFPropertyListRef pl2 = __CFBinaryPlistCreate15((const uint8_t *)CFDataGetBytePtr(mdata), CFDataGetLength(mdata), NULL);
1595 if (!CFEqual(pl, pl2)) CFLog(3, CFSTR("*** error: plists before and after are not equal\n--------\n%@\n--------\n%@\n--------"), pl, pl2);
1596 #endif
1597         } else {
1598             if (plist) *plist = NULL;
1599             if (errorString) *errorString = (CFStringRef)CFRetain(CFSTR("binary data is corrupt"));
1600             result = false;
1601         }
1602         CFRelease(objects);
1603         return result;
1604     }
1605     FAIL_FALSE;
1606 }
1607