CFBinaryPList.c

   1 /*
   2  * Copyright (c) 2015 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 /*      CFBinaryPList.c
  25         Copyright (c) 2000-2014, 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 uint64_t __check_uint64_add_unsigned_unsigned(uint64_t x, uint64_t y, int32_t* err) {
  65    if((ULLONG_MAX - y) < x)
  66         *err = *err | CF_OVERFLOW_ERROR;
  67    return x + y;
  68 };
  69
  70 CF_INLINE uint64_t __check_uint64_mul_unsigned_unsigned(uint64_t x, uint64_t y, int32_t* err) {
  71   if(x == 0) return 0;
  72   if(ULLONG_MAX/x < y)
  73      *err = *err | CF_OVERFLOW_ERROR;
  74   return x * y;
  75 };
  76
  77 #if __LP64__
  78 #define check_ptr_add(p, a, err)        (const uint8_t *)__check_uint64_add_unsigned_unsigned((uintptr_t)p, (uintptr_t)a, err)
  79 #define check_size_t_mul(b, a, err)     (size_t)__check_uint64_mul_unsigned_unsigned((size_t)b, (size_t)a, err)
  80 #else
  81
  82 CF_INLINE uint32_t __check_uint32_add_unsigned_unsigned(uint32_t x, uint32_t y, int32_t* err) {
  83     if((UINT_MAX - y) < x)
  84     *err = *err | CF_OVERFLOW_ERROR;
  85     return x + y;
  86 };
  87
  88 CF_INLINE uint32_t __check_uint32_mul_unsigned_unsigned(uint32_t x, uint32_t y, int32_t* err) {
  89     uint64_t tmp = (uint64_t) x * (uint64_t) y;
  90     /* If any of the upper 32 bits touched, overflow */
  91     if(tmp & 0xffffffff00000000ULL)
  92     *err = *err | CF_OVERFLOW_ERROR;
  93     return (uint32_t) tmp;
  94 };
  95
  96 #define check_ptr_add(p, a, err)        (const uint8_t *)__check_uint32_add_unsigned_unsigned((uintptr_t)p, (uintptr_t)a, err)
  97 #define check_size_t_mul(b, a, err)     (size_t)__check_uint32_mul_unsigned_unsigned((size_t)b, (size_t)a, err)
  98 #endif
  99
 100 #pragma mark -
 101 #pragma mark Keyed Archiver UID
 102
 103 struct __CFKeyedArchiverUID {
 104     CFRuntimeBase _base;
 105     uint32_t _value;
 106 };
 107
 108 static CFStringRef __CFKeyedArchiverUIDCopyDescription(CFTypeRef cf) {
 109     CFKeyedArchiverUIDRef uid = (CFKeyedArchiverUIDRef)cf;
 110     return CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<CFKeyedArchiverUID %p [%p]>{value = %u}"), cf, CFGetAllocator(cf), uid->_value);
 111 }
 112
 113 static CFStringRef __CFKeyedArchiverUIDCopyFormattingDescription(CFTypeRef cf, CFDictionaryRef formatOptions) {
 114     CFKeyedArchiverUIDRef uid = (CFKeyedArchiverUIDRef)cf;
 115     return CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("@%u@"), uid->_value);
 116 }
 117
 118 static CFTypeID __kCFKeyedArchiverUIDTypeID = _kCFRuntimeNotATypeID;
 119
 120 static const CFRuntimeClass __CFKeyedArchiverUIDClass = {
 121     0,
 122     "CFKeyedArchiverUID",
 123     NULL,       // init
 124     NULL,       // copy
 125     NULL,       // finalize
 126     NULL,       // equal -- pointer equality only
 127     NULL,       // hash -- pointer hashing only
 128     __CFKeyedArchiverUIDCopyFormattingDescription,
 129     __CFKeyedArchiverUIDCopyDescription
 130 };
 131
 132 CFTypeID _CFKeyedArchiverUIDGetTypeID(void) {
 133     static dispatch_once_t initOnce;
 134     dispatch_once(&initOnce, ^{ __kCFKeyedArchiverUIDTypeID = _CFRuntimeRegisterClass(&__CFKeyedArchiverUIDClass); });
 135     return __kCFKeyedArchiverUIDTypeID;
 136 }
 137
 138 CFKeyedArchiverUIDRef _CFKeyedArchiverUIDCreate(CFAllocatorRef allocator, uint32_t value) {
 139     CFKeyedArchiverUIDRef uid;
 140     uid = (CFKeyedArchiverUIDRef)_CFRuntimeCreateInstance(allocator, _CFKeyedArchiverUIDGetTypeID(), sizeof(struct __CFKeyedArchiverUID) - sizeof(CFRuntimeBase), NULL);
 141     if (NULL == uid) {
 142         return NULL;
 143     }
 144     ((struct __CFKeyedArchiverUID *)uid)->_value = value;
 145     return uid;
 146 }
 147
 148
 149 uint32_t _CFKeyedArchiverUIDGetValue(CFKeyedArchiverUIDRef uid) {
 150     return uid->_value;
 151 }
 152
 153 #pragma mark -
 154 #pragma mark Writing
 155
 156 CF_PRIVATE CFErrorRef __CFPropertyListCreateError(CFIndex code, CFStringRef debugString, ...);
 157
 158 typedef struct {
 159     CFTypeRef stream;
 160     void *databytes;
 161     uint64_t datalen;
 162     CFErrorRef error;
 163     uint64_t written;
 164     int32_t used;
 165     bool streamIsData;
 166     uint8_t buffer[8192 - 32];
 167 } __CFBinaryPlistWriteBuffer;
 168
 169 static void writeBytes(__CFBinaryPlistWriteBuffer *buf, const UInt8 *bytes, CFIndex length) {
 170     if (length <= 0) return;
 171     if (buf->error) return;
 172     if (buf->databytes) {
 173         int32_t err = CF_NO_ERROR;
 174         uint64_t tmpSum = __check_uint64_add_unsigned_unsigned(buf->written, (uint64_t)length, &err);
 175         if ((CF_NO_ERROR != err) || buf->datalen < tmpSum) {
 176             buf->error = __CFPropertyListCreateError(kCFPropertyListWriteStreamError, CFSTR("Binary property list writing could not be completed because databytes is full."));
 177             return;
 178         }
 179         memmove((char *)buf->databytes + buf->written, bytes, length);
 180     }
 181     if (buf->streamIsData) {
 182         if (buf->stream) CFDataAppendBytes((CFMutableDataRef)buf->stream, bytes, length);
 183         buf->written += length;
 184     } else {
 185 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_WINDOWS
 186         while (0 < length) {
 187             CFIndex ret = buf->stream ? CFWriteStreamWrite((CFWriteStreamRef)buf->stream, bytes, length) : length;
 188             if (ret == 0) {
 189                 buf->error = __CFPropertyListCreateError(kCFPropertyListWriteStreamError, CFSTR("Binary property list writing could not be completed because stream is full."));
 190                 return;
 191             }
 192             if (ret < 0) {
 193                 CFErrorRef err = buf->stream ? CFWriteStreamCopyError((CFWriteStreamRef)buf->stream) : NULL;
 194                 buf->error = err ? err : __CFPropertyListCreateError(kCFPropertyListWriteStreamError, CFSTR("Binary property list writing could not be completed because the stream had an unknown error."));
 195                 return;
 196             }
 197             buf->written += ret;
 198             length -= ret;
 199             bytes += ret;
 200         }
 201 #else
 202         CFAssert(false, __kCFLogAssertion, "Streams are not supported on this platform");
 203 #endif
 204     }
 205 }
 206
 207 static void bufferFlush(__CFBinaryPlistWriteBuffer *buf) {
 208     writeBytes(buf, buf->buffer, buf->used);
 209     buf->used = 0;
 210 }
 211
 212 static void bufferWrite(__CFBinaryPlistWriteBuffer *buf, const uint8_t *buffer, CFIndex count) {
 213     if (0 == count) return;
 214     if ((CFIndex)sizeof(buf->buffer) <= count) {
 215         bufferFlush(buf);
 216         writeBytes(buf, buffer, count);
 217         return;
 218     }
 219     CFIndex copyLen = __CFMin(count, (CFIndex)sizeof(buf->buffer) - buf->used);
 220     if (buf->stream || buf->databytes) {
 221         switch (copyLen) {
 222         case 4: buf->buffer[buf->used + 3] = buffer[3]; /* FALLTHROUGH */
 223         case 3: buf->buffer[buf->used + 2] = buffer[2]; /* FALLTHROUGH */
 224         case 2: buf->buffer[buf->used + 1] = buffer[1]; /* FALLTHROUGH */
 225         case 1: buf->buffer[buf->used] = buffer[0]; break;
 226         default: memmove(buf->buffer + buf->used, buffer, copyLen);
 227         }
 228     }
 229     buf->used += copyLen;
 230     if (sizeof(buf->buffer) == buf->used) {
 231         writeBytes(buf, buf->buffer, sizeof(buf->buffer));
 232         if (buf->stream || buf->databytes) {
 233             memmove(buf->buffer, buffer + copyLen, count - copyLen);
 234         }
 235         buf->used = count - copyLen;
 236     }
 237 }
 238
 239 /*
 240 HEADER
 241         magic number ("bplist")
 242         file format version (currently "0?")
 243
 244 OBJECT TABLE
 245         variable-sized objects
 246
 247         Object Formats (marker byte followed by additional info in some cases)
 248         null    0000 0000                       // null object [v"1?"+ only]
 249         bool    0000 1000                       // false
 250         bool    0000 1001                       // true
 251         url     0000 1100       string          // URL with no base URL, recursive encoding of URL string [v"1?"+ only]
 252         url     0000 1101       base string     // URL with base URL, recursive encoding of base URL, then recursive encoding of URL string [v"1?"+ only]
 253         uuid    0000 1110                       // 16-byte UUID [v"1?"+ only]
 254         fill    0000 1111                       // fill byte
 255         int     0001 0nnn       ...             // # of bytes is 2^nnn, big-endian bytes
 256         real    0010 0nnn       ...             // # of bytes is 2^nnn, big-endian bytes
 257         date    0011 0011       ...             // 8 byte float follows, big-endian bytes
 258         data    0100 nnnn       [int]   ...     // nnnn is number of bytes unless 1111 then int count follows, followed by bytes
 259         string  0101 nnnn       [int]   ...     // ASCII string, nnnn is # of chars, else 1111 then int count, then bytes
 260         string  0110 nnnn       [int]   ...     // Unicode string, nnnn is # of chars, else 1111 then int count, then big-endian 2-byte uint16_t
 261         string  0111 nnnn       [int]   ...     // UTF8 string, nnnn is # of chars, else 1111 then int count, then bytes [v"1?"+ only]
 262         uid     1000 nnnn       ...             // nnnn+1 is # of bytes
 263                 1001 xxxx                       // unused
 264         array   1010 nnnn       [int]   objref* // nnnn is count, unless '1111', then int count follows
 265         ordset  1011 nnnn       [int]   objref* // nnnn is count, unless '1111', then int count follows [v"1?"+ only]
 266         set     1100 nnnn       [int]   objref* // nnnn is count, unless '1111', then int count follows [v"1?"+ only]
 267         dict    1101 nnnn       [int]   keyref* objref* // nnnn is count, unless '1111', then int count follows
 268                 1110 xxxx                       // unused
 269                 1111 xxxx                       // unused
 270
 271 OFFSET TABLE
 272         list of ints, byte size of which is given in trailer
 273         -- these are the byte offsets into the file
 274         -- number of these is in the trailer
 275
 276 TRAILER
 277         byte size of offset ints in offset table
 278         byte size of object refs in arrays and dicts
 279         number of offsets in offset table (also is number of objects)
 280         element # in offset table which is top level object
 281         offset table offset
 282
 283 */
 284
 285
 286 static CFTypeID stringtype = -1, datatype = -1, numbertype = -1, datetype = -1;
 287 static CFTypeID booltype = -1, nulltype = -1, dicttype = -1, arraytype = -1;
 288 static CFTypeID uuidtype = -1, urltype = -1, osettype = -1, settype = -1;
 289
 290 static void initStatics() {
 291     if ((CFTypeID)-1 == stringtype) {
 292         stringtype = CFStringGetTypeID();
 293     }
 294     if ((CFTypeID)-1 == datatype) {
 295         datatype = CFDataGetTypeID();
 296     }
 297     if ((CFTypeID)-1 == numbertype) {
 298         numbertype = CFNumberGetTypeID();
 299     }
 300     if ((CFTypeID)-1 == booltype) {
 301         booltype = CFBooleanGetTypeID();
 302     }
 303     if ((CFTypeID)-1 == datetype) {
 304         datetype = CFDateGetTypeID();
 305     }
 306     if ((CFTypeID)-1 == dicttype) {
 307         dicttype = CFDictionaryGetTypeID();
 308     }
 309     if ((CFTypeID)-1 == arraytype) {
 310         arraytype = CFArrayGetTypeID();
 311     }
 312     if ((CFTypeID)-1 == settype) {
 313         settype = CFSetGetTypeID();
 314     }
 315     if ((CFTypeID)-1 == nulltype) {
 316         nulltype = CFNullGetTypeID();
 317     }
 318     if ((CFTypeID)-1 == uuidtype) {
 319         uuidtype = CFUUIDGetTypeID();
 320     }
 321     if ((CFTypeID)-1 == urltype) {
 322         urltype = CFURLGetTypeID();
 323     }
 324     if ((CFTypeID)-1 == osettype) {
 325         osettype = -1;
 326     }
 327 }
 328
 329 static void _appendInt(__CFBinaryPlistWriteBuffer *buf, uint64_t bigint) {
 330     uint8_t marker;
 331     uint8_t *bytes;
 332     CFIndex nbytes;
 333     if (bigint <= (uint64_t)0xff) {
 334         nbytes = 1;
 335         marker = kCFBinaryPlistMarkerInt | 0;
 336     } else if (bigint <= (uint64_t)0xffff) {
 337         nbytes = 2;
 338         marker = kCFBinaryPlistMarkerInt | 1;
 339     } else if (bigint <= (uint64_t)0xffffffff) {
 340         nbytes = 4;
 341         marker = kCFBinaryPlistMarkerInt | 2;
 342     } else {
 343         nbytes = 8;
 344         marker = kCFBinaryPlistMarkerInt | 3;
 345     }
 346     bigint = CFSwapInt64HostToBig(bigint);
 347     bytes = (uint8_t *)&bigint + sizeof(bigint) - nbytes;
 348     bufferWrite(buf, &marker, 1);
 349     bufferWrite(buf, bytes, nbytes);
 350 }
 351
 352 static void _appendUID(__CFBinaryPlistWriteBuffer *buf, CFKeyedArchiverUIDRef uid) {
 353     uint8_t marker;
 354     uint8_t *bytes;
 355     CFIndex nbytes;
 356     uint64_t bigint = _CFKeyedArchiverUIDGetValue(uid);
 357     if (bigint <= (uint64_t)0xff) {
 358         nbytes = 1;
 359     } else if (bigint <= (uint64_t)0xffff) {
 360         nbytes = 2;
 361     } else if (bigint <= (uint64_t)0xffffffff) {
 362         nbytes = 4;
 363     } else {
 364         nbytes = 8;
 365     }
 366     marker = kCFBinaryPlistMarkerUID | (uint8_t)(nbytes - 1);
 367     bigint = CFSwapInt64HostToBig(bigint);
 368     bytes = (uint8_t *)&bigint + sizeof(bigint) - nbytes;
 369     bufferWrite(buf, &marker, 1);
 370     bufferWrite(buf, bytes, nbytes);
 371 }
 372
 373 static void _appendString(__CFBinaryPlistWriteBuffer *buf, CFStringRef str) {
 374     CFIndex ret, count = CFStringGetLength(str);
 375     CFIndex needed, idx2;
 376     uint8_t *bytes, buffer[1024];
 377     bytes = (count <= 1024) ? buffer : (uint8_t *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count, 0);
 378     // presumption, believed to be true, is that ASCII encoding may need
 379     // less bytes, but will not need greater, than the # of unichars
 380     ret = CFStringGetBytes(str, CFRangeMake(0, count), kCFStringEncodingASCII, 0, false, bytes, count, &needed);
 381     if (ret == count) {
 382         uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerASCIIString | (needed < 15 ? needed : 0xf));
 383         bufferWrite(buf, &marker, 1);
 384         if (15 <= needed) {
 385             _appendInt(buf, (uint64_t)needed);
 386         }
 387         bufferWrite(buf, bytes, needed);
 388     } else {
 389         UniChar *chars;
 390         uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerUnicode16String | (count < 15 ? count : 0xf));
 391         bufferWrite(buf, &marker, 1);
 392         if (15 <= count) {
 393             _appendInt(buf, (uint64_t)count);
 394         }
 395         chars = (UniChar *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(UniChar), 0);
 396         CFStringGetCharacters(str, CFRangeMake(0, count), chars);
 397         for (idx2 = 0; idx2 < count; idx2++) {
 398             chars[idx2] = CFSwapInt16HostToBig(chars[idx2]);
 399         }
 400         bufferWrite(buf, (uint8_t *)chars, count * sizeof(UniChar));
 401         CFAllocatorDeallocate(kCFAllocatorSystemDefault, chars);
 402     }
 403     if (bytes != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, bytes);
 404 }
 405
 406 CF_EXPORT CFNumberType _CFNumberGetType2(CFNumberRef number);
 407
 408 static void _appendNumber(__CFBinaryPlistWriteBuffer *buf, CFNumberRef num) {
 409     uint8_t marker;
 410     uint64_t bigint;
 411     uint8_t *bytes;
 412     CFIndex nbytes;
 413     if (CFNumberIsFloatType(num)) {
 414         CFSwappedFloat64 swapped64;
 415         CFSwappedFloat32 swapped32;
 416         if (CFNumberGetByteSize(num) <= (CFIndex)sizeof(float)) {
 417             float v;
 418             CFNumberGetValue(num, kCFNumberFloat32Type, &v);
 419             swapped32 = CFConvertFloat32HostToSwapped(v);
 420             bytes = (uint8_t *)&swapped32;
 421             nbytes = sizeof(float);
 422             marker = kCFBinaryPlistMarkerReal | 2;
 423         } else {
 424             double v;
 425             CFNumberGetValue(num, kCFNumberFloat64Type, &v);
 426             swapped64 = CFConvertFloat64HostToSwapped(v);
 427             bytes = (uint8_t *)&swapped64;
 428             nbytes = sizeof(double);
 429             marker = kCFBinaryPlistMarkerReal | 3;
 430         }
 431         bufferWrite(buf, &marker, 1);
 432         bufferWrite(buf, bytes, nbytes);
 433     } else {
 434         CFNumberType type = _CFNumberGetType2(num);
 435         if (kCFNumberSInt128Type == type) {
 436             CFSInt128Struct s;
 437             CFNumberGetValue(num, kCFNumberSInt128Type, &s);
 438             struct {
 439                 int64_t high;
 440                 uint64_t low;
 441             } storage;
 442             storage.high = CFSwapInt64HostToBig(s.high);
 443             storage.low = CFSwapInt64HostToBig(s.low);
 444             uint8_t *bytes = (uint8_t *)&storage;
 445             uint8_t marker = kCFBinaryPlistMarkerInt | 4;
 446             CFIndex nbytes = 16;
 447             bufferWrite(buf, &marker, 1);
 448             bufferWrite(buf, bytes, nbytes);
 449         } else {
 450             CFNumberGetValue(num, kCFNumberSInt64Type, &bigint);
 451             _appendInt(buf, bigint);
 452         }
 453     }
 454 }
 455
 456 static Boolean _appendObject(__CFBinaryPlistWriteBuffer *buf, CFTypeRef obj, CFDictionaryRef objtable, uint32_t objRefSize) {
 457     uint64_t refnum;
 458     CFIndex idx2;
 459     CFTypeID type = CFGetTypeID(obj);
 460         if (stringtype == type) {
 461             _appendString(buf, (CFStringRef)obj);
 462         } else if (numbertype == type) {
 463             _appendNumber(buf, (CFNumberRef)obj);
 464         } else if (booltype == type) {
 465             uint8_t marker = CFBooleanGetValue((CFBooleanRef)obj) ? kCFBinaryPlistMarkerTrue : kCFBinaryPlistMarkerFalse;
 466             bufferWrite(buf, &marker, 1);
 467         } else if (datatype == type) {
 468             CFIndex count = CFDataGetLength((CFDataRef)obj);
 469             uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerData | (count < 15 ? count : 0xf));
 470             bufferWrite(buf, &marker, 1);
 471             if (15 <= count) {
 472                 _appendInt(buf, (uint64_t)count);
 473             }
 474             bufferWrite(buf, CFDataGetBytePtr((CFDataRef)obj), count);
 475         } else if (datetype == type) {
 476             CFSwappedFloat64 swapped;
 477             uint8_t marker = kCFBinaryPlistMarkerDate;
 478             bufferWrite(buf, &marker, 1);
 479             swapped = CFConvertFloat64HostToSwapped(CFDateGetAbsoluteTime((CFDateRef)obj));
 480             bufferWrite(buf, (uint8_t *)&swapped, sizeof(swapped));
 481         } else if (dicttype == type) {
 482             CFIndex count = CFDictionaryGetCount((CFDictionaryRef)obj);
 483             uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerDict | (count < 15 ? count : 0xf));
 484             bufferWrite(buf, &marker, 1);
 485             if (15 <= count) {
 486                 _appendInt(buf, (uint64_t)count);
 487             }
 488             CFPropertyListRef *list, buffer[512];
 489             list = (count <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * count * sizeof(CFTypeRef), __kCFAllocatorGCScannedMemory);
 490             CFDictionaryGetKeysAndValues((CFDictionaryRef)obj, list, list + count);
 491             for (idx2 = 0; idx2 < 2 * count; idx2++) {
 492                 CFPropertyListRef value = list[idx2];
 493                 if (objtable) {
 494                     uint32_t swapped = 0;
 495                     uint8_t *source = (uint8_t *)&swapped;
 496                     refnum = (uint32_t)(uintptr_t)CFDictionaryGetValue(objtable, value);
 497                     swapped = CFSwapInt32HostToBig((uint32_t)refnum);
 498                     bufferWrite(buf, source + sizeof(swapped) - objRefSize, objRefSize);
 499                 } else {
 500                     Boolean ret = _appendObject(buf, value, objtable, objRefSize);
 501                     if (!ret) {
 502                         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 503                         return false;
 504                     }
 505                 }
 506             }
 507             if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 508         } else if (arraytype == type) {
 509             CFIndex count = CFArrayGetCount((CFArrayRef)obj);
 510             CFPropertyListRef *list, buffer[256];
 511             uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerArray | (count < 15 ? count : 0xf));
 512             bufferWrite(buf, &marker, 1);
 513             if (15 <= count) {
 514                 _appendInt(buf, (uint64_t)count);
 515             }
 516             list = (count <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(CFTypeRef), __kCFAllocatorGCScannedMemory);
 517             CFArrayGetValues((CFArrayRef)obj, CFRangeMake(0, count), list);
 518             for (idx2 = 0; idx2 < count; idx2++) {
 519                 CFPropertyListRef value = list[idx2];
 520                 if (objtable) {
 521                     uint32_t swapped = 0;
 522                     uint8_t *source = (uint8_t *)&swapped;
 523                     refnum = (uint32_t)(uintptr_t)CFDictionaryGetValue(objtable, value);
 524                     swapped = CFSwapInt32HostToBig((uint32_t)refnum);
 525                     bufferWrite(buf, source + sizeof(swapped) - objRefSize, objRefSize);
 526                 } else {
 527                     Boolean ret = _appendObject(buf, value, objtable, objRefSize);
 528                     if (!ret) {
 529                         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 530                         return false;
 531                     }
 532                 }
 533             }
 534             if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 535         } else if (_CFKeyedArchiverUIDGetTypeID() == type) {
 536             _appendUID(buf, (CFKeyedArchiverUIDRef)obj);
 537         } else {
 538             return false;
 539         }
 540     return true;
 541 }
 542
 543 static void _flattenPlist(CFPropertyListRef plist, CFMutableArrayRef objlist, CFMutableDictionaryRef objtable, CFMutableSetRef uniquingset) {
 544     uint32_t refnum;
 545     CFTypeID type = CFGetTypeID(plist);
 546
 547     // Do not unique dictionaries or arrays, because: they
 548     // are slow to compare, and have poor hash codes.
 549     // Uniquing bools is unnecessary.
 550     if (stringtype == type || numbertype == type || datetype == type || datatype == type) {
 551         CFIndex before = CFSetGetCount(uniquingset);
 552         CFSetAddValue(uniquingset, plist);
 553         CFIndex after = CFSetGetCount(uniquingset);
 554         if (after == before) {  // already in set
 555             CFPropertyListRef unique = CFSetGetValue(uniquingset, plist);
 556             if (unique != plist) {
 557                 refnum = (uint32_t)(uintptr_t)CFDictionaryGetValue(objtable, unique);
 558                 CFDictionaryAddValue(objtable, plist, (const void *)(uintptr_t)refnum);
 559             }
 560             return;
 561         }
 562     }
 563     refnum = CFArrayGetCount(objlist);
 564     CFArrayAppendValue(objlist, plist);
 565     CFDictionaryAddValue(objtable, plist, (const void *)(uintptr_t)refnum);
 566     if (dicttype == type) {
 567         CFIndex count = CFDictionaryGetCount((CFDictionaryRef)plist);
 568         STACK_BUFFER_DECL(CFPropertyListRef, buffer, count <= 128 ? count * 2 : 1);
 569         CFPropertyListRef *list = (count <= 128) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * count * sizeof(CFTypeRef), __kCFAllocatorGCScannedMemory);
 570         CFDictionaryGetKeysAndValues((CFDictionaryRef)plist, list, list + count);
 571         for (CFIndex idx = 0; idx < 2 * count; idx++) {
 572             _flattenPlist(list[idx], objlist, objtable, uniquingset);
 573         }
 574         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 575     } else if (arraytype == type) {
 576         CFIndex count = CFArrayGetCount((CFArrayRef)plist);
 577         STACK_BUFFER_DECL(CFPropertyListRef, buffer, count <= 256 ? count : 1);
 578         CFPropertyListRef *list = (count <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(CFTypeRef), __kCFAllocatorGCScannedMemory);
 579         CFArrayGetValues((CFArrayRef)plist, CFRangeMake(0, count), list);
 580         for (CFIndex 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;
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         STACK_BUFFER_DECL(CFPropertyListRef, buffer, arrayCount <= 256 ? arrayCount : 1);
1320         list = (arrayCount <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, byte_cnt, __kCFAllocatorGCScannedMemory);
1321         if (!list) FAIL_FALSE;
1322         Boolean madeSet = false;
1323         if (!set && 15 < curDepth) {
1324             set = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, NULL);
1325             madeSet = set ? true : false;
1326         }
1327
1328         if (set) CFSetAddValue(set, (const void *)(uintptr_t)startOffset);
1329         if ((marker & 0xf0) == kCFBinaryPlistMarkerArray && keyPaths) {
1330             // Only get a subset of this array
1331             CFSetRef theseKeys, nextKeys;
1332             __CFPropertyListCreateSplitKeypaths(kCFAllocatorSystemDefault, keyPaths, &theseKeys, &nextKeys);
1333
1334             Boolean success = true;
1335             CFMutableArrayRef array = CFArrayCreateMutable(allocator, CFSetGetCount(theseKeys), &kCFTypeArrayCallBacks);
1336             if (theseKeys) {
1337                 CFTypeRef *keys = (CFTypeRef *)malloc(CFSetGetCount(theseKeys) * sizeof(CFTypeRef));
1338                 CFSetGetValues(theseKeys, keys);
1339                 for (CFIndex i = 0; i < CFSetGetCount(theseKeys); i++) {
1340                     CFStringRef key = (CFStringRef)keys[i];
1341                     SInt32 intValue = CFStringGetIntValue(key);
1342                     if ((intValue == 0 && CFStringCompare(CFSTR("0"), key, 0) != kCFCompareEqualTo) || intValue == INT_MAX || intValue == INT_MIN || intValue < 0) {
1343                         // skip, doesn't appear to be a proper integer
1344                     } else {
1345                         uint64_t valueOffset;
1346                         Boolean found = __CFBinaryPlistGetOffsetForValueFromArray2(databytes, datalen, startOffset, trailer, (CFIndex)intValue, &valueOffset, objects);
1347                         if (found) {
1348                             CFPropertyListRef result;
1349                             success = __CFBinaryPlistCreateObjectFiltered(databytes, datalen, valueOffset, trailer, allocator, mutabilityOption, objects, set, curDepth + 1, nextKeys, &result);
1350                             if (success) {
1351                                 CFArrayAppendValue(array, result);
1352                                 CFRelease(result);
1353                             } else {
1354                                 break;
1355                             }
1356                         }
1357                     }
1358                 }
1359
1360                 free(keys);
1361                 CFRelease(theseKeys);
1362             }
1363             if (nextKeys) CFRelease(nextKeys);
1364
1365             if (success) {
1366                 if (!(mutabilityOption == kCFPropertyListMutableContainers || mutabilityOption == kCFPropertyListMutableContainersAndLeaves)) {
1367                     // make immutable
1368                     *plist = CFArrayCreateCopy(allocator, array);
1369                     CFRelease(array);
1370                 } else {
1371                     *plist = array;
1372                 }
1373             } else if (array) {
1374                 CFRelease(array);
1375             }
1376         } else {
1377             for (CFIndex idx = 0; idx < arrayCount; idx++) {
1378                 CFPropertyListRef pl;
1379                 off = _getOffsetOfRefAt(databytes, ptr, trailer);
1380                 if (!__CFBinaryPlistCreateObjectFiltered(databytes, datalen, off, trailer, allocator, mutabilityOption, objects, set, curDepth + 1, NULL, &pl)) {
1381                     while (idx--) {
1382                         CFRelease(list[idx]);
1383                     }
1384                     if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1385                     FAIL_FALSE;
1386                 }
1387                 __CFAssignWithWriteBarrier((void **)list + idx, (void *)pl);
1388                 ptr += trailer->_objectRefSize;
1389             }
1390             if ((marker & 0xf0) == kCFBinaryPlistMarkerArray) {
1391                 if (mutabilityOption != kCFPropertyListImmutable) {
1392                     *plist = CFArrayCreateMutable(allocator, 0, &kCFTypeArrayCallBacks);
1393                     CFArrayReplaceValues((CFMutableArrayRef)*plist, CFRangeMake(0, 0), list, arrayCount);
1394                     for (CFIndex idx = 0; idx < arrayCount; idx++) {
1395                         CFRelease(list[idx]);
1396                     }
1397                 } else {
1398                     if (!kCFUseCollectableAllocator) {
1399                         *plist = __CFArrayCreateTransfer(allocator, list, arrayCount);
1400                     } else {
1401                         *plist = CFArrayCreate(allocator, list, arrayCount, &kCFTypeArrayCallBacks);
1402                         for (CFIndex idx = 0; idx < arrayCount; idx++) {
1403                             CFRelease(list[idx]);
1404                         }
1405                     }
1406                 }
1407             } else {
1408                 if (mutabilityOption != kCFPropertyListImmutable) {
1409                     *plist = CFSetCreateMutable(allocator, 0, &kCFTypeSetCallBacks);
1410                     for (CFIndex idx = 0; idx < arrayCount; idx++) {
1411                         CFSetAddValue((CFMutableSetRef)*plist, list[idx]);
1412                     }
1413                     for (CFIndex idx = 0; idx < arrayCount; idx++) {
1414                         CFRelease(list[idx]);
1415                     }
1416                 } else {
1417                     if (!kCFUseCollectableAllocator) {
1418                         *plist = __CFSetCreateTransfer(allocator, list, arrayCount);
1419                     } else {
1420                         *plist = CFSetCreate(allocator, list, arrayCount, &kCFTypeSetCallBacks);
1421                         for (CFIndex idx = 0; idx < arrayCount; idx++) {
1422                             CFRelease(list[idx]);
1423                         }
1424                     }
1425                 }
1426             }
1427         }
1428         if (set) CFSetRemoveValue(set, (const void *)(uintptr_t)startOffset);
1429         if (madeSet) {
1430             CFRelease(set);
1431             set = NULL;
1432         }
1433         if (objects && *plist && (mutabilityOption == kCFPropertyListImmutable)) {
1434             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1435         }
1436         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1437         return (*plist) ? true : false;
1438         }
1439     case kCFBinaryPlistMarkerDict: {
1440         const uint8_t *ptr = databytes + startOffset;
1441         int32_t err = CF_NO_ERROR;
1442         ptr = check_ptr_add(ptr, 1, &err);
1443         if (CF_NO_ERROR != err) FAIL_FALSE;
1444         CFIndex dictionaryCount = marker & 0x0f;
1445         if (0xf == dictionaryCount) {
1446             uint64_t bigint = 0;
1447             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1448             if (LONG_MAX < bigint) FAIL_FALSE;
1449             dictionaryCount = (CFIndex)bigint;
1450         }
1451         dictionaryCount = check_size_t_mul(dictionaryCount, 2, &err);
1452         if (CF_NO_ERROR != err) FAIL_FALSE;
1453         size_t byte_cnt = check_size_t_mul(dictionaryCount, trailer->_objectRefSize, &err);
1454         if (CF_NO_ERROR != err) FAIL_FALSE;
1455         const uint8_t *extent = check_ptr_add(ptr, byte_cnt, &err) - 1;
1456         if (CF_NO_ERROR != err) FAIL_FALSE;
1457         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1458         byte_cnt = check_size_t_mul(dictionaryCount, sizeof(CFPropertyListRef), &err);
1459         if (CF_NO_ERROR != err) FAIL_FALSE;
1460         STACK_BUFFER_DECL(CFPropertyListRef, buffer, dictionaryCount <= 256 ? dictionaryCount : 1);
1461         list = (dictionaryCount <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, byte_cnt, __kCFAllocatorGCScannedMemory);
1462         if (!list) FAIL_FALSE;
1463         Boolean madeSet = false;
1464         if (!set && 15 < curDepth) {
1465             set = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, NULL);
1466             madeSet = set ? true : false;
1467         }
1468
1469         if (set) CFSetAddValue(set, (const void *)(uintptr_t)startOffset);
1470         if (keyPaths) {
1471             // Only get a subset of this dictionary
1472             CFSetRef theseKeys, nextKeys;
1473             __CFPropertyListCreateSplitKeypaths(kCFAllocatorSystemDefault, keyPaths, &theseKeys, &nextKeys);
1474
1475             Boolean success = true;
1476             CFMutableDictionaryRef dict = CFDictionaryCreateMutable(allocator, CFSetGetCount(theseKeys), &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
1477             if (theseKeys) {
1478                 CFTypeRef *keys = (CFTypeRef *)malloc(CFSetGetCount(theseKeys) * sizeof(CFTypeRef));
1479                 CFSetGetValues(theseKeys, keys);
1480                 for (CFIndex i = 0; i < CFSetGetCount(theseKeys); i++) {
1481                     CFStringRef key = (CFStringRef)keys[i];
1482                     uint64_t keyOffset, valueOffset;
1483                     Boolean found = __CFBinaryPlistGetOffsetForValueFromDictionary3(databytes, datalen, startOffset, trailer, key, &keyOffset, &valueOffset, false, objects);
1484                     if (found) {
1485                         CFPropertyListRef result;
1486                         success = __CFBinaryPlistCreateObjectFiltered(databytes, datalen, valueOffset, trailer, allocator, mutabilityOption, objects, set, curDepth + 1, nextKeys, &result);
1487                         if (success) {
1488                             CFDictionarySetValue(dict, key, result);
1489                             CFRelease(result);
1490                         } else {
1491                             break;
1492                         }
1493                     }
1494                 }
1495
1496                 free(keys);
1497                 CFRelease(theseKeys);
1498             }
1499             if (nextKeys) CFRelease(nextKeys);
1500
1501             if (success) {
1502                 if (!(mutabilityOption == kCFPropertyListMutableContainers || mutabilityOption == kCFPropertyListMutableContainersAndLeaves)) {
1503                     // make immutable
1504                     *plist = CFDictionaryCreateCopy(allocator, dict);
1505                     CFRelease(dict);
1506                 } else {
1507                     *plist = dict;
1508                 }
1509             } else if (dict) {
1510                 CFRelease(dict);
1511             }
1512         } else {
1513             for (CFIndex idx = 0; idx < dictionaryCount; idx++) {
1514                 CFPropertyListRef pl = NULL;
1515                 off = _getOffsetOfRefAt(databytes, ptr, trailer);
1516                 if (!__CFBinaryPlistCreateObjectFiltered(databytes, datalen, off, trailer, allocator, mutabilityOption, objects, set, curDepth + 1, NULL, &pl) || (idx < dictionaryCount / 2 && !_plistIsPrimitive(pl))) {
1517                     if (pl && !(0)) CFRelease(pl);
1518                     while (idx--) {
1519                         CFRelease(list[idx]);
1520                     }
1521                     if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1522                     FAIL_FALSE;
1523                 }
1524                 __CFAssignWithWriteBarrier((void **)list + idx, (void *)pl);
1525                 ptr += trailer->_objectRefSize;
1526             }
1527             if (mutabilityOption != kCFPropertyListImmutable) {
1528                 *plist = CFDictionaryCreateMutable(allocator, 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
1529                 for (CFIndex idx = 0; idx < dictionaryCount / 2; idx++) {
1530                     CFDictionaryAddValue((CFMutableDictionaryRef)*plist, list[idx], list[idx + dictionaryCount / 2]);
1531                 }
1532                 for (CFIndex idx = 0; idx < dictionaryCount; idx++) {
1533                     CFRelease(list[idx]);
1534                 }
1535             } else {
1536                 if (!kCFUseCollectableAllocator) {
1537                     *plist = __CFDictionaryCreateTransfer(allocator, list, list + dictionaryCount / 2, dictionaryCount / 2);
1538                 } else {
1539                     *plist = CFDictionaryCreate(allocator, list, list + dictionaryCount / 2, dictionaryCount / 2, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
1540                     for (CFIndex idx = 0; idx < dictionaryCount; idx++) {
1541                         CFRelease(list[idx]);
1542                     }
1543                 }
1544             }
1545         }
1546         if (set) CFSetRemoveValue(set, (const void *)(uintptr_t)startOffset);
1547         if (madeSet) {
1548             CFRelease(set);
1549             set = NULL;
1550         }
1551         if (objects && *plist && (mutabilityOption == kCFPropertyListImmutable)) {
1552             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1553         }
1554         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1555         return (*plist) ? true : false;
1556         }
1557     }
1558     FAIL_FALSE;
1559 }
1560
1561 bool __CFBinaryPlistCreateObject(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFAllocatorRef allocator, CFOptionFlags mutabilityOption, CFMutableDictionaryRef objects, CFPropertyListRef *plist) {
1562         // for compatibility with Foundation's use, need to leave this here
1563     return __CFBinaryPlistCreateObjectFiltered(databytes, datalen, startOffset, trailer, allocator, mutabilityOption, objects, NULL, 0, NULL, plist);
1564 }
1565
1566 CF_PRIVATE bool __CFTryParseBinaryPlist(CFAllocatorRef allocator, CFDataRef data, CFOptionFlags option, CFPropertyListRef *plist, CFStringRef *errorString) {
1567     uint8_t marker;
1568     CFBinaryPlistTrailer trailer;
1569     uint64_t offset;
1570     const uint8_t *databytes = CFDataGetBytePtr(data);
1571     uint64_t datalen = CFDataGetLength(data);
1572
1573     if (8 <= datalen && __CFBinaryPlistGetTopLevelInfo(databytes, datalen, &marker, &offset, &trailer)) {
1574         // FALSE: We know for binary plist parsing that the result objects will be retained
1575         // by their containing collections as the parsing proceeds, so we do not need
1576         // to use retaining callbacks for the objects map in this case. WHY: the file might
1577         // be malformed and contain hash-equal keys for the same dictionary (for example)
1578         // and the later key will cause the previous one to be released when we set the second
1579         // in the dictionary.
1580         CFMutableDictionaryRef objects = CFDictionaryCreateMutable(kCFAllocatorSystemDefault, 0, NULL, &kCFTypeDictionaryValueCallBacks);
1581         _CFDictionarySetCapacity(objects, trailer._numObjects);
1582         CFPropertyListRef pl = NULL;
1583         bool result = true;
1584         if (__CFBinaryPlistCreateObjectFiltered(databytes, datalen, offset, &trailer, allocator, option, objects, NULL, 0, NULL, &pl)) {
1585             if (plist) *plist = pl;
1586 #if 0
1587 // code to check the 1.5 version code against any binary plist successfully parsed above
1588 extern size_t __CFBinaryPlistWrite15(CFPropertyListRef plist, CFMutableDataRef data, CFErrorRef *error);
1589 extern CFPropertyListRef __CFBinaryPlistCreate15(const uint8_t *databytes, uint64_t datalen, CFErrorRef *error);
1590
1591 CFMutableDataRef mdata = CFDataCreateMutable(0, 0);
1592 size_t s = __CFBinaryPlistWrite15(pl, mdata, NULL);
1593 //double ratio = (double)s / (double)datalen;
1594 //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);
1595 if (s != CFDataGetLength(mdata)) CFLog(3, CFSTR("### error: returned length not equal to data length (%ld != %ld)"), s, CFDataGetLength(mdata));
1596 CFPropertyListRef pl2 = __CFBinaryPlistCreate15((const uint8_t *)CFDataGetBytePtr(mdata), CFDataGetLength(mdata), NULL);
1597 if (!CFEqual(pl, pl2)) CFLog(3, CFSTR("*** error: plists before and after are not equal\n--------\n%@\n--------\n%@\n--------"), pl, pl2);
1598 #endif
1599         } else {
1600             if (plist) *plist = NULL;
1601             if (errorString) *errorString = (CFStringRef)CFRetain(CFSTR("binary data is corrupt"));
1602             result = false;
1603         }
1604         CFRelease(objects);
1605         return result;
1606     }
1607     FAIL_FALSE;
1608 }
1609