CFBinaryPList.c

   1 /*
   2  * Copyright (c) 2009 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /*      CFBinaryPList.c
  24         Copyright (c) 2000-2009, Apple Inc. All rights reserved.
  25         Responsibility: Tony Parker
  26 */
  27
  28
  29 #include <CoreFoundation/CFString.h>
  30 #include <CoreFoundation/CFNumber.h>
  31 #include <CoreFoundation/CFDate.h>
  32 #include <CoreFoundation/CFData.h>
  33 #include <CoreFoundation/CFError.h>
  34 #include <CoreFoundation/CFArray.h>
  35 #include <CoreFoundation/CFDictionary.h>
  36 #include <CoreFoundation/CFSet.h>
  37 #include <CoreFoundation/CFPropertyList.h>
  38 #include <CoreFoundation/CFByteOrder.h>
  39 #include <CoreFoundation/CFRuntime.h>
  40 #include <stdio.h>
  41 #include <limits.h>
  42 #include <string.h>
  43 #include "CFInternal.h"
  44
  45 typedef struct {
  46     int64_t high;
  47     uint64_t low;
  48 } CFSInt128Struct;
  49
  50 enum {
  51     kCFNumberSInt128Type = 17
  52 };
  53
  54 CF_EXPORT CFNumberType _CFNumberGetType2(CFNumberRef number);
  55 __private_extern__ CFErrorRef __CFPropertyListCreateError(CFAllocatorRef allocator, CFIndex code, CFStringRef debugString, ...);
  56
  57 enum {
  58         CF_NO_ERROR = 0,
  59         CF_OVERFLOW_ERROR = (1 << 0),
  60 };
  61
  62 CF_INLINE uint32_t __check_uint32_add_unsigned_unsigned(uint32_t x, uint32_t y, int32_t* err) {
  63    if((UINT_MAX - y) < x)
  64         *err = *err | CF_OVERFLOW_ERROR;
  65    return x + y;
  66 };
  67
  68 CF_INLINE uint64_t __check_uint64_add_unsigned_unsigned(uint64_t x, uint64_t y, int32_t* err) {
  69    if((ULLONG_MAX - y) < x)
  70         *err = *err | CF_OVERFLOW_ERROR;
  71    return x + y;
  72 };
  73
  74 CF_INLINE uint32_t __check_uint32_mul_unsigned_unsigned(uint32_t x, uint32_t y, int32_t* err) {
  75    uint64_t tmp = (uint64_t) x * (uint64_t) y;
  76    /* If any of the upper 32 bits touched, overflow */
  77    if(tmp & 0xffffffff00000000ULL)
  78         *err = *err | CF_OVERFLOW_ERROR;
  79    return (uint32_t) tmp;
  80 };
  81
  82 CF_INLINE uint64_t __check_uint64_mul_unsigned_unsigned(uint64_t x, uint64_t y, int32_t* err) {
  83   if(x == 0) return 0;
  84   if(ULLONG_MAX/x < y)
  85      *err = *err | CF_OVERFLOW_ERROR;
  86   return x * y;
  87 };
  88
  89 #if __LP64__
  90 #define check_ptr_add(p, a, err)        (const uint8_t *)__check_uint64_add_unsigned_unsigned((uintptr_t)p, (uintptr_t)a, err)
  91 #define check_size_t_mul(b, a, err)     (size_t)__check_uint64_mul_unsigned_unsigned((size_t)b, (size_t)a, err)
  92 #else
  93 #define check_ptr_add(p, a, err)        (const uint8_t *)__check_uint32_add_unsigned_unsigned((uintptr_t)p, (uintptr_t)a, err)
  94 #define check_size_t_mul(b, a, err)     (size_t)__check_uint32_mul_unsigned_unsigned((size_t)b, (size_t)a, err)
  95 #endif
  96
  97
  98 CF_INLINE CFTypeID __CFGenericTypeID_genericobj_inline(const void *cf) {
  99     CFTypeID typeID = (*(uint32_t *)(((CFRuntimeBase *)cf)->_cfinfo) >> 8) & 0xFFFF;
 100     return CF_IS_OBJC(typeID, cf) ? CFGetTypeID(cf) : typeID;
 101 }
 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 __private_extern__ void __CFKeyedArchiverUIDInitialize(void) {
 133     __kCFKeyedArchiverUIDTypeID = _CFRuntimeRegisterClass(&__CFKeyedArchiverUIDClass);
 134 }
 135
 136 CFTypeID _CFKeyedArchiverUIDGetTypeID(void) {
 137     return __kCFKeyedArchiverUIDTypeID;
 138 }
 139
 140 CFKeyedArchiverUIDRef _CFKeyedArchiverUIDCreate(CFAllocatorRef allocator, uint32_t value) {
 141     CFKeyedArchiverUIDRef uid;
 142     uid = (CFKeyedArchiverUIDRef)_CFRuntimeCreateInstance(allocator, __kCFKeyedArchiverUIDTypeID, sizeof(struct __CFKeyedArchiverUID) - sizeof(CFRuntimeBase), NULL);
 143     if (NULL == uid) {
 144         return NULL;
 145     }
 146     ((struct __CFKeyedArchiverUID *)uid)->_value = value;
 147     return uid;
 148 }
 149
 150
 151 uint32_t _CFKeyedArchiverUIDGetValue(CFKeyedArchiverUIDRef uid) {
 152     return uid->_value;
 153 }
 154
 155
 156 typedef struct {
 157     CFTypeRef stream;
 158     CFErrorRef error;
 159     uint64_t written;
 160     int32_t used;
 161     bool streamIsData;
 162     uint8_t buffer[8192 - 32];
 163 } __CFBinaryPlistWriteBuffer;
 164
 165 static void writeBytes(__CFBinaryPlistWriteBuffer *buf, const UInt8 *bytes, CFIndex length) {
 166     if (0 == length) return;
 167     if (buf->error) return;
 168     if (buf->streamIsData) {
 169         CFDataAppendBytes((CFMutableDataRef)buf->stream, bytes, length);
 170         buf->written += length;
 171     } else {
 172         CFAssert(false, __kCFLogAssertion, "Streams are not supported on this platform");
 173     }
 174 }
 175
 176 static void bufferWrite(__CFBinaryPlistWriteBuffer *buf, const uint8_t *buffer, CFIndex count) {
 177     if (0 == count) return;
 178     if ((CFIndex)sizeof(buf->buffer) <= count) {
 179         writeBytes(buf, buf->buffer, buf->used);
 180         buf->used = 0;
 181         writeBytes(buf, buffer, count);
 182         return;
 183     }
 184     CFIndex copyLen = __CFMin(count, (CFIndex)sizeof(buf->buffer) - buf->used);
 185     memmove(buf->buffer + buf->used, buffer, copyLen);
 186     buf->used += copyLen;
 187     if (sizeof(buf->buffer) == buf->used) {
 188         writeBytes(buf, buf->buffer, sizeof(buf->buffer));
 189         memmove(buf->buffer, buffer + copyLen, count - copyLen);
 190         buf->used = count - copyLen;
 191     }
 192 }
 193
 194 static void bufferFlush(__CFBinaryPlistWriteBuffer *buf) {
 195     writeBytes(buf, buf->buffer, buf->used);
 196     buf->used = 0;
 197 }
 198
 199 /*
 200 HEADER
 201         magic number ("bplist")
 202         file format version
 203
 204 OBJECT TABLE
 205         variable-sized objects
 206
 207         Object Formats (marker byte followed by additional info in some cases)
 208         null    0000 0000
 209         bool    0000 1000                       // false
 210         bool    0000 1001                       // true
 211         fill    0000 1111                       // fill byte
 212         int     0001 nnnn       ...             // # of bytes is 2^nnnn, big-endian bytes
 213         real    0010 nnnn       ...             // # of bytes is 2^nnnn, big-endian bytes
 214         date    0011 0011       ...             // 8 byte float follows, big-endian bytes
 215         data    0100 nnnn       [int]   ...     // nnnn is number of bytes unless 1111 then int count follows, followed by bytes
 216         string  0101 nnnn       [int]   ...     // ASCII string, nnnn is # of chars, else 1111 then int count, then bytes
 217         string  0110 nnnn       [int]   ...     // Unicode string, nnnn is # of chars, else 1111 then int count, then big-endian 2-byte uint16_t
 218                 0111 xxxx                       // unused
 219         uid     1000 nnnn       ...             // nnnn+1 is # of bytes
 220                 1001 xxxx                       // unused
 221         array   1010 nnnn       [int]   objref* // nnnn is count, unless '1111', then int count follows
 222                 1011 xxxx                       // unused
 223         set     1100 nnnn       [int]   objref* // nnnn is count, unless '1111', then int count follows
 224         dict    1101 nnnn       [int]   keyref* objref* // nnnn is count, unless '1111', then int count follows
 225                 1110 xxxx                       // unused
 226                 1111 xxxx                       // unused
 227
 228 OFFSET TABLE
 229         list of ints, byte size of which is given in trailer
 230         -- these are the byte offsets into the file
 231         -- number of these is in the trailer
 232
 233 TRAILER
 234         byte size of offset ints in offset table
 235         byte size of object refs in arrays and dicts
 236         number of offsets in offset table (also is number of objects)
 237         element # in offset table which is top level object
 238         offset table offset
 239
 240 */
 241
 242
 243 static CFTypeID stringtype = -1, datatype = -1, numbertype = -1, datetype = -1;
 244 static CFTypeID booltype = -1, nulltype = -1, dicttype = -1, arraytype = -1, settype = -1;
 245
 246 static void initStatics() {
 247     if ((CFTypeID)-1 == stringtype) {
 248         stringtype = CFStringGetTypeID();
 249     }
 250     if ((CFTypeID)-1 == datatype) {
 251         datatype = CFDataGetTypeID();
 252     }
 253     if ((CFTypeID)-1 == numbertype) {
 254         numbertype = CFNumberGetTypeID();
 255     }
 256     if ((CFTypeID)-1 == booltype) {
 257         booltype = CFBooleanGetTypeID();
 258     }
 259     if ((CFTypeID)-1 == datetype) {
 260         datetype = CFDateGetTypeID();
 261     }
 262     if ((CFTypeID)-1 == dicttype) {
 263         dicttype = CFDictionaryGetTypeID();
 264     }
 265     if ((CFTypeID)-1 == arraytype) {
 266         arraytype = CFArrayGetTypeID();
 267     }
 268     if ((CFTypeID)-1 == settype) {
 269         settype = CFSetGetTypeID();
 270     }
 271     if ((CFTypeID)-1 == nulltype) {
 272         nulltype = CFNullGetTypeID();
 273     }
 274 }
 275
 276 static void _appendInt(__CFBinaryPlistWriteBuffer *buf, uint64_t bigint) {
 277     uint8_t marker;
 278     uint8_t *bytes;
 279     CFIndex nbytes;
 280     if (bigint <= (uint64_t)0xff) {
 281         nbytes = 1;
 282         marker = kCFBinaryPlistMarkerInt | 0;
 283     } else if (bigint <= (uint64_t)0xffff) {
 284         nbytes = 2;
 285         marker = kCFBinaryPlistMarkerInt | 1;
 286     } else if (bigint <= (uint64_t)0xffffffff) {
 287         nbytes = 4;
 288         marker = kCFBinaryPlistMarkerInt | 2;
 289     } else {
 290         nbytes = 8;
 291         marker = kCFBinaryPlistMarkerInt | 3;
 292     }
 293     bigint = CFSwapInt64HostToBig(bigint);
 294     bytes = (uint8_t *)&bigint + sizeof(bigint) - nbytes;
 295     bufferWrite(buf, &marker, 1);
 296     bufferWrite(buf, bytes, nbytes);
 297 }
 298
 299 static void _appendUID(__CFBinaryPlistWriteBuffer *buf, CFKeyedArchiverUIDRef uid) {
 300     uint8_t marker;
 301     uint8_t *bytes;
 302     CFIndex nbytes;
 303     uint64_t bigint = _CFKeyedArchiverUIDGetValue(uid);
 304     if (bigint <= (uint64_t)0xff) {
 305         nbytes = 1;
 306     } else if (bigint <= (uint64_t)0xffff) {
 307         nbytes = 2;
 308     } else if (bigint <= (uint64_t)0xffffffff) {
 309         nbytes = 4;
 310     } else {
 311         nbytes = 8;
 312     }
 313     marker = kCFBinaryPlistMarkerUID | (uint8_t)(nbytes - 1);
 314     bigint = CFSwapInt64HostToBig(bigint);
 315     bytes = (uint8_t *)&bigint + sizeof(bigint) - nbytes;
 316     bufferWrite(buf, &marker, 1);
 317     bufferWrite(buf, bytes, nbytes);
 318 }
 319
 320 static void _flattenPlist(CFPropertyListRef plist, CFMutableArrayRef objlist, CFMutableDictionaryRef objtable, CFMutableSetRef uniquingset) {
 321     CFPropertyListRef unique;
 322     uint32_t refnum;
 323     CFTypeID type = __CFGenericTypeID_genericobj_inline(plist);
 324     CFIndex idx;
 325     CFPropertyListRef *list, buffer[256];
 326
 327     // Do not unique dictionaries or arrays, because: they
 328     // are slow to compare, and have poor hash codes.
 329     // Uniquing bools is unnecessary.
 330     if (stringtype == type || numbertype == type || datetype == type || datatype == type) {
 331         CFIndex before = CFSetGetCount(uniquingset);
 332         CFSetAddValue(uniquingset, plist);
 333         CFIndex after = CFSetGetCount(uniquingset);
 334         if (after == before) {  // already in set
 335             unique = CFSetGetValue(uniquingset, plist);
 336             if (unique != plist) {
 337                 refnum = (uint32_t)(uintptr_t)CFDictionaryGetValue(objtable, unique);
 338                 CFDictionaryAddValue(objtable, plist, (const void *)(uintptr_t)refnum);
 339             }
 340             return;
 341         }
 342     }
 343     refnum = CFArrayGetCount(objlist);
 344     CFArrayAppendValue(objlist, plist);
 345     CFDictionaryAddValue(objtable, plist, (const void *)(uintptr_t)refnum);
 346     if (dicttype == type) {
 347         CFIndex count = CFDictionaryGetCount((CFDictionaryRef)plist);
 348         list = (count <= 128) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * count * sizeof(CFTypeRef), 0);
 349         CFDictionaryGetKeysAndValues((CFDictionaryRef)plist, list, list + count);
 350         for (idx = 0; idx < 2 * count; idx++) {
 351             _flattenPlist(list[idx], objlist, objtable, uniquingset);
 352         }
 353         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 354     } else if (arraytype == type) {
 355         CFIndex count = CFArrayGetCount((CFArrayRef)plist);
 356         list = (count <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(CFTypeRef), 0);
 357         CFArrayGetValues((CFArrayRef)plist, CFRangeMake(0, count), list);
 358         for (idx = 0; idx < count; idx++) {
 359             _flattenPlist(list[idx], objlist, objtable, uniquingset);
 360         }
 361         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 362     }
 363 }
 364
 365 /* Get the number of bytes required to hold the value in 'count'. Will return a power of 2 value big enough to hold 'count'.
 366  */
 367 CF_INLINE uint8_t _byteCount(uint64_t count) {
 368     uint64_t mask = ~(uint64_t)0;
 369     uint8_t size = 0;
 370
 371     // Find something big enough to hold 'count'
 372     while (count & mask) {
 373         size++;
 374         mask = mask << 8;
 375     }
 376
 377     // Ensure that 'count' is a power of 2
 378     // For sizes bigger than 8, just use the required count
 379     while ((size != 1 && size != 2 && size != 4 && size != 8) && size <= 8) {
 380         size++;
 381     }
 382
 383     return size;
 384 }
 385
 386
 387 // stream must be a CFMutableDataRef
 388 /* 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. */
 389 CFIndex __CFBinaryPlistWrite(CFPropertyListRef plist, CFTypeRef stream, uint64_t estimate, CFOptionFlags options, CFErrorRef *error) {
 390     CFMutableDictionaryRef objtable;
 391     CFMutableArrayRef objlist;
 392     CFMutableSetRef uniquingset;
 393     CFBinaryPlistTrailer trailer;
 394     uint64_t *offsets, length_so_far;
 395     uint64_t refnum;
 396     int64_t idx, idx2, cnt;
 397     __CFBinaryPlistWriteBuffer *buf;
 398
 399     initStatics();
 400
 401     objtable = CFDictionaryCreateMutable(kCFAllocatorSystemDefault, 0, NULL, NULL);
 402     objlist = CFArrayCreateMutable(kCFAllocatorSystemDefault, 0, NULL);
 403     uniquingset = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, NULL);
 404 #if DEPLOYMENT_TARGET_MACOSX
 405     _CFDictionarySetCapacity(objtable, estimate ? estimate : 650);
 406     _CFArraySetCapacity(objlist, estimate ? estimate : 650);
 407     _CFSetSetCapacity(uniquingset, estimate ? estimate : 1000);
 408 #endif
 409
 410     _flattenPlist(plist, objlist, objtable, uniquingset);
 411
 412     CFRelease(uniquingset);
 413
 414     cnt = CFArrayGetCount(objlist);
 415     offsets = (uint64_t *)CFAllocatorAllocate(kCFAllocatorSystemDefault, (CFIndex)(cnt * sizeof(*offsets)), 0);
 416
 417     buf = (__CFBinaryPlistWriteBuffer *)CFAllocatorAllocate(kCFAllocatorSystemDefault, sizeof(__CFBinaryPlistWriteBuffer), 0);
 418     buf->stream = stream;
 419     buf->error = NULL;
 420     buf->streamIsData = (CFGetTypeID(stream) == CFDataGetTypeID());
 421     buf->written = 0;
 422     buf->used = 0;
 423     bufferWrite(buf, (uint8_t *)"bplist00", 8); // header
 424
 425     memset(&trailer, 0, sizeof(trailer));
 426     trailer._numObjects = CFSwapInt64HostToBig(cnt);
 427     trailer._topObject = 0;     // true for this implementation
 428     trailer._objectRefSize = _byteCount(cnt);
 429     for (idx = 0; idx < cnt; idx++) {
 430         CFPropertyListRef obj = CFArrayGetValueAtIndex(objlist, (CFIndex)idx);
 431         CFTypeID type = __CFGenericTypeID_genericobj_inline(obj);
 432         offsets[idx] = buf->written + buf->used;
 433         if (stringtype == type) {
 434             CFIndex ret, count = CFStringGetLength((CFStringRef)obj);
 435             CFIndex needed;
 436             uint8_t *bytes, buffer[1024];
 437             bytes = (count <= 1024) ? buffer : (uint8_t *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count, 0);
 438             // presumption, believed to be true, is that ASCII encoding may need
 439             // less bytes, but will not need greater, than the # of unichars
 440             ret = CFStringGetBytes((CFStringRef)obj, CFRangeMake(0, count), kCFStringEncodingASCII, 0, false, bytes, count, &needed);
 441             if (ret == count) {
 442                 uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerASCIIString | (needed < 15 ? needed : 0xf));
 443                 bufferWrite(buf, &marker, 1);
 444                 if (15 <= needed) {
 445                     _appendInt(buf, (uint64_t)needed);
 446                 }
 447                 bufferWrite(buf, bytes, needed);
 448             } else {
 449                 UniChar *chars;
 450                 uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerUnicode16String | (count < 15 ? count : 0xf));
 451                 bufferWrite(buf, &marker, 1);
 452                 if (15 <= count) {
 453                     _appendInt(buf, (uint64_t)count);
 454                 }
 455                 chars = (UniChar *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(UniChar), 0);
 456                 CFStringGetCharacters((CFStringRef)obj, CFRangeMake(0, count), chars);
 457                 for (idx2 = 0; idx2 < count; idx2++) {
 458                     chars[idx2] = CFSwapInt16HostToBig(chars[idx2]);
 459                 }
 460                 bufferWrite(buf, (uint8_t *)chars, count * sizeof(UniChar));
 461                 CFAllocatorDeallocate(kCFAllocatorSystemDefault, chars);
 462             }
 463             if (bytes != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, bytes);
 464         } else if (numbertype == type) {
 465             uint8_t marker;
 466             uint64_t bigint;
 467             uint8_t *bytes;
 468             CFIndex nbytes;
 469             if (CFNumberIsFloatType((CFNumberRef)obj)) {
 470                 CFSwappedFloat64 swapped64;
 471                 CFSwappedFloat32 swapped32;
 472                 if (CFNumberGetByteSize((CFNumberRef)obj) <= (CFIndex)sizeof(float)) {
 473                     float v;
 474                     CFNumberGetValue((CFNumberRef)obj, kCFNumberFloat32Type, &v);
 475                     swapped32 = CFConvertFloat32HostToSwapped(v);
 476                     bytes = (uint8_t *)&swapped32;
 477                     nbytes = sizeof(float);
 478                     marker = kCFBinaryPlistMarkerReal | 2;
 479                 } else {
 480                     double v;
 481                     CFNumberGetValue((CFNumberRef)obj, kCFNumberFloat64Type, &v);
 482                     swapped64 = CFConvertFloat64HostToSwapped(v);
 483                     bytes = (uint8_t *)&swapped64;
 484                     nbytes = sizeof(double);
 485                     marker = kCFBinaryPlistMarkerReal | 3;
 486                 }
 487                 bufferWrite(buf, &marker, 1);
 488                 bufferWrite(buf, bytes, nbytes);
 489             } else {
 490                 CFNumberType type = _CFNumberGetType2((CFNumberRef)obj);
 491                 if (kCFNumberSInt128Type == type) {
 492                     CFSInt128Struct s;
 493                     CFNumberGetValue((CFNumberRef)obj, kCFNumberSInt128Type, &s);
 494                     struct {
 495                         int64_t high;
 496                         uint64_t low;
 497                     } storage;
 498                     storage.high = CFSwapInt64HostToBig(s.high);
 499                     storage.low = CFSwapInt64HostToBig(s.low);
 500                     uint8_t *bytes = (uint8_t *)&storage;
 501                     uint8_t marker = kCFBinaryPlistMarkerInt | 4;
 502                     CFIndex nbytes = 16;
 503                     bufferWrite(buf, &marker, 1);
 504                     bufferWrite(buf, bytes, nbytes);
 505                 } else {
 506                     CFNumberGetValue((CFNumberRef)obj, kCFNumberSInt64Type, &bigint);
 507                     _appendInt(buf, bigint);
 508                 }
 509             }
 510         } else if (_CFKeyedArchiverUIDGetTypeID() == type) {
 511             _appendUID(buf, (CFKeyedArchiverUIDRef)obj);
 512         } else if (booltype == type) {
 513             uint8_t marker = CFBooleanGetValue((CFBooleanRef)obj) ? kCFBinaryPlistMarkerTrue : kCFBinaryPlistMarkerFalse;
 514             bufferWrite(buf, &marker, 1);
 515         } else if (datatype == type) {
 516             CFIndex count = CFDataGetLength((CFDataRef)obj);
 517             uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerData | (count < 15 ? count : 0xf));
 518             bufferWrite(buf, &marker, 1);
 519             if (15 <= count) {
 520                 _appendInt(buf, (uint64_t)count);
 521             }
 522             bufferWrite(buf, CFDataGetBytePtr((CFDataRef)obj), count);
 523         } else if (datetype == type) {
 524             CFSwappedFloat64 swapped;
 525             uint8_t marker = kCFBinaryPlistMarkerDate;
 526             bufferWrite(buf, &marker, 1);
 527             swapped = CFConvertFloat64HostToSwapped(CFDateGetAbsoluteTime((CFDateRef)obj));
 528             bufferWrite(buf, (uint8_t *)&swapped, sizeof(swapped));
 529         } else if (dicttype == type) {
 530             CFIndex count = CFDictionaryGetCount((CFDictionaryRef)obj);
 531
 532             uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerDict | (count < 15 ? count : 0xf));
 533             bufferWrite(buf, &marker, 1);
 534             if (15 <= count) {
 535                 _appendInt(buf, (uint64_t)count);
 536             }
 537
 538             CFPropertyListRef *list, buffer[512];
 539
 540             list = (count <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * count * sizeof(CFTypeRef), 0);
 541             CFDictionaryGetKeysAndValues((CFDictionaryRef)obj, list, list + count);
 542             for (idx2 = 0; idx2 < 2 * count; idx2++) {
 543                 CFPropertyListRef value = list[idx2];
 544                 uint32_t swapped = 0;
 545                 uint8_t *source = (uint8_t *)&swapped;
 546                 refnum = (uint32_t)(uintptr_t)CFDictionaryGetValue(objtable, value);
 547                 swapped = CFSwapInt32HostToBig((uint32_t)refnum);
 548                 bufferWrite(buf, source + sizeof(swapped) - trailer._objectRefSize, trailer._objectRefSize);
 549             }
 550             if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 551         } else if (arraytype == type) {
 552             CFIndex count = CFArrayGetCount((CFArrayRef)obj);
 553             CFPropertyListRef *list, buffer[256];
 554             uint8_t marker = (uint8_t)(kCFBinaryPlistMarkerArray | (count < 15 ? count : 0xf));
 555             bufferWrite(buf, &marker, 1);
 556             if (15 <= count) {
 557                 _appendInt(buf, (uint64_t)count);
 558             }
 559             list = (count <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(CFTypeRef), 0);
 560             CFArrayGetValues((CFArrayRef)obj, CFRangeMake(0, count), list);
 561             for (idx2 = 0; idx2 < count; idx2++) {
 562                 CFPropertyListRef value = list[idx2];
 563                 uint32_t swapped = 0;
 564                 uint8_t *source = (uint8_t *)&swapped;
 565                 refnum = (uint32_t)(uintptr_t)CFDictionaryGetValue(objtable, value);
 566                 swapped = CFSwapInt32HostToBig((uint32_t)refnum);
 567                 bufferWrite(buf, source + sizeof(swapped) - trailer._objectRefSize, trailer._objectRefSize);
 568             }
 569             if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 570         } else {
 571             CFRelease(objtable);
 572             CFRelease(objlist);
 573             if (error && buf->error) {
 574                 // caller will release error
 575                 *error = buf->error;
 576             } else if (buf->error) {
 577                 // caller is not interested in error, release it here
 578                 CFRelease(buf->error);
 579             }
 580             CFAllocatorDeallocate(kCFAllocatorSystemDefault, buf);
 581             CFAllocatorDeallocate(kCFAllocatorSystemDefault, offsets);
 582             return 0;
 583         }
 584     }
 585     CFRelease(objtable);
 586     CFRelease(objlist);
 587
 588     length_so_far = buf->written + buf->used;
 589     trailer._offsetTableOffset = CFSwapInt64HostToBig(length_so_far);
 590     trailer._offsetIntSize = _byteCount(length_so_far);
 591
 592     for (idx = 0; idx < cnt; idx++) {
 593         uint64_t swapped = CFSwapInt64HostToBig(offsets[idx]);
 594         uint8_t *source = (uint8_t *)&swapped;
 595         bufferWrite(buf, source + sizeof(*offsets) - trailer._offsetIntSize, trailer._offsetIntSize);
 596     }
 597     length_so_far += cnt * trailer._offsetIntSize;
 598
 599     bufferWrite(buf, (uint8_t *)&trailer, sizeof(trailer));
 600     bufferFlush(buf);
 601     length_so_far += sizeof(trailer);
 602     if (buf->error) {
 603         if (error) {
 604             // caller will release error
 605             *error = buf->error;
 606         } else {
 607             CFRelease(buf->error);
 608         }
 609         return 0;
 610     }
 611     CFAllocatorDeallocate(kCFAllocatorSystemDefault, buf);
 612     CFAllocatorDeallocate(kCFAllocatorSystemDefault, offsets);
 613     return (CFIndex)length_so_far;
 614 }
 615
 616
 617 CFIndex __CFBinaryPlistWriteToStream(CFPropertyListRef plist, CFTypeRef stream) {
 618     return __CFBinaryPlistWrite(plist, stream, 0, 0, NULL);
 619 }
 620
 621 // to be removed soon
 622 CFIndex __CFBinaryPlistWriteToStreamWithEstimate(CFPropertyListRef plist, CFTypeRef stream, uint64_t estimate) {
 623     return __CFBinaryPlistWrite(plist, stream, estimate, 0, NULL);
 624 }
 625
 626 // to be removed soon
 627 CFIndex __CFBinaryPlistWriteToStreamWithOptions(CFPropertyListRef plist, CFTypeRef stream, uint64_t estimate, CFOptionFlags options) {
 628     return __CFBinaryPlistWrite(plist, stream, estimate, options, NULL);
 629 }
 630
 631 #define FAIL_FALSE      do { return false; } while (0)
 632 #define FAIL_MAXOFFSET  do { return UINT64_MAX; } while (0)
 633
 634 /* Grab a valSize-bytes integer out of the buffer pointed at by data and return it.
 635  */
 636 CF_INLINE uint64_t _getSizedInt(const uint8_t *data, uint8_t valSize) {
 637     if (valSize == 1) {
 638         return (uint64_t)*data;
 639     } else if (valSize == 2) {
 640         uint16_t val = *(uint16_t *)data;
 641         return (uint64_t)CFSwapInt16BigToHost(val);
 642     } else if (valSize == 4) {
 643         uint32_t val = *(uint32_t *)data;
 644         return (uint64_t)CFSwapInt32BigToHost(val);
 645     } else if (valSize == 8) {
 646         uint64_t val = *(uint64_t *)data;
 647         return CFSwapInt64BigToHost(val);
 648     } else {
 649         // Compatability with existing archives, including anything with a non-power-of-2 size and 16-byte values
 650         uint64_t res = 0;
 651         for (CFIndex idx = 0; idx < valSize; idx++) {
 652             res = (res << 8) + data[idx];
 653         }
 654         return res;
 655     }
 656     // shouldn't get here
 657     return 0;
 658 }
 659
 660 bool __CFBinaryPlistGetTopLevelInfo(const uint8_t *databytes, uint64_t datalen, uint8_t *marker, uint64_t *offset, CFBinaryPlistTrailer *trailer) {
 661     CFBinaryPlistTrailer trail;
 662
 663     initStatics();
 664
 665     if (!databytes || datalen < sizeof(trail) + 8 + 1) FAIL_FALSE;
 666     // Tiger and earlier will parse "bplist00"
 667     // Leopard will parse "bplist00" or "bplist01"
 668     // SnowLeopard will parse "bplist0?" where ? is any one character
 669     if (0 != memcmp("bplist0", databytes, 7)) {
 670         return false;
 671     }
 672     memmove(&trail, databytes + datalen - sizeof(trail), sizeof(trail));
 673     // In Leopard, the unused bytes in the trailer must be 0 or the parse will fail
 674     // This check is not present in Tiger and earlier or after Leopard
 675     trail._numObjects = CFSwapInt64BigToHost(trail._numObjects);
 676     trail._topObject = CFSwapInt64BigToHost(trail._topObject);
 677     trail._offsetTableOffset = CFSwapInt64BigToHost(trail._offsetTableOffset);
 678     if (LONG_MAX < trail._numObjects) FAIL_FALSE;
 679     if (LONG_MAX < trail._offsetTableOffset) FAIL_FALSE;
 680     if (trail._numObjects < 1) FAIL_FALSE;
 681     if (trail._numObjects <= trail._topObject) FAIL_FALSE;
 682     if (trail._offsetTableOffset < 9) FAIL_FALSE;
 683     if (datalen - sizeof(trail) <= trail._offsetTableOffset) FAIL_FALSE;
 684     if (trail._offsetIntSize < 1) FAIL_FALSE;
 685     if (trail._objectRefSize < 1) FAIL_FALSE;
 686     int32_t err = CF_NO_ERROR;
 687     uint64_t offsetIntSize = trail._offsetIntSize;
 688     uint64_t offsetTableSize = __check_uint64_mul_unsigned_unsigned(trail._numObjects, offsetIntSize, &err);
 689     if (CF_NO_ERROR!= err) FAIL_FALSE;
 690     if (offsetTableSize < 1) FAIL_FALSE;
 691     uint64_t objectDataSize = trail._offsetTableOffset - 8;
 692     uint64_t tmpSum = __check_uint64_add_unsigned_unsigned(8, objectDataSize, &err);
 693     tmpSum = __check_uint64_add_unsigned_unsigned(tmpSum, offsetTableSize, &err);
 694     tmpSum = __check_uint64_add_unsigned_unsigned(tmpSum, sizeof(trail), &err);
 695     if (CF_NO_ERROR != err) FAIL_FALSE;
 696     if (datalen != tmpSum) FAIL_FALSE;
 697     if (trail._objectRefSize < 8 && (1ULL << (8 * trail._objectRefSize)) <= trail._numObjects) FAIL_FALSE;
 698     if (trail._offsetIntSize < 8 && (1ULL << (8 * trail._offsetIntSize)) <= trail._offsetTableOffset) FAIL_FALSE;
 699     const uint8_t *objectsFirstByte;
 700     objectsFirstByte = check_ptr_add(databytes, 8, &err);
 701     if (CF_NO_ERROR != err) FAIL_FALSE;
 702     const uint8_t *offsetsFirstByte = check_ptr_add(databytes, trail._offsetTableOffset, &err);
 703     if (CF_NO_ERROR != err) FAIL_FALSE;
 704     const uint8_t *offsetsLastByte;
 705     offsetsLastByte = check_ptr_add(offsetsFirstByte, offsetTableSize - 1, &err);
 706     if (CF_NO_ERROR != err) FAIL_FALSE;
 707
 708     const uint8_t *bytesptr = databytes + trail._offsetTableOffset;
 709     uint64_t maxOffset = trail._offsetTableOffset - 1;
 710     for (CFIndex idx = 0; idx < trail._numObjects; idx++) {
 711         uint64_t off = _getSizedInt(bytesptr, trail._offsetIntSize);
 712         if (maxOffset < off) FAIL_FALSE;
 713         bytesptr += trail._offsetIntSize;
 714     }
 715
 716     bytesptr = databytes + trail._offsetTableOffset + trail._topObject * trail._offsetIntSize;
 717     uint64_t off = _getSizedInt(bytesptr, trail._offsetIntSize);
 718     if (off < 8 || trail._offsetTableOffset <= off) FAIL_FALSE;
 719     if (trailer) *trailer = trail;
 720     if (offset) *offset = off;
 721     if (marker) *marker = *(databytes + off);
 722     return true;
 723 }
 724
 725 CF_INLINE Boolean _plistIsPrimitive(CFPropertyListRef pl) {
 726     CFTypeID type = __CFGenericTypeID_genericobj_inline(pl);
 727     if (dicttype == type || arraytype == type || settype == type) FAIL_FALSE;
 728     return true;
 729 }
 730
 731 CF_INLINE bool _readInt(const uint8_t *ptr, const uint8_t *end_byte_ptr, uint64_t *bigint, const uint8_t **newptr) {
 732     if (end_byte_ptr < ptr) FAIL_FALSE;
 733     uint8_t marker = *ptr++;
 734     if ((marker & 0xf0) != kCFBinaryPlistMarkerInt) FAIL_FALSE;
 735     uint64_t cnt = 1 << (marker & 0x0f);
 736     int32_t err = CF_NO_ERROR;
 737     const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
 738     if (CF_NO_ERROR != err) FAIL_FALSE;
 739     if (end_byte_ptr < extent) FAIL_FALSE;
 740     // integers are not required to be in the most compact possible representation, but only the last 64 bits are significant currently
 741     *bigint = _getSizedInt(ptr, cnt);
 742     ptr += cnt;
 743     if (newptr) *newptr = ptr;
 744     return true;
 745 }
 746
 747 // bytesptr points at a ref
 748 CF_INLINE uint64_t _getOffsetOfRefAt(const uint8_t *databytes, const uint8_t *bytesptr, const CFBinaryPlistTrailer *trailer) {
 749     // *trailer contents are trusted, even for overflows -- was checked when the trailer was parsed;
 750     // this pointer arithmetic and the multiplication was also already done once and checked,
 751     // and the offsetTable was already validated.
 752     const uint8_t *objectsFirstByte = databytes + 8;
 753     const uint8_t *offsetsFirstByte = databytes + trailer->_offsetTableOffset;
 754     if (bytesptr < objectsFirstByte || offsetsFirstByte - trailer->_objectRefSize < bytesptr) FAIL_MAXOFFSET;
 755
 756     uint64_t ref = _getSizedInt(bytesptr, trailer->_objectRefSize);
 757     if (trailer->_numObjects <= ref) FAIL_MAXOFFSET;
 758
 759     bytesptr = databytes + trailer->_offsetTableOffset + ref * trailer->_offsetIntSize;
 760     uint64_t off = _getSizedInt(bytesptr, trailer->_offsetIntSize);
 761     return off;
 762 }
 763
 764 bool __CFBinaryPlistGetOffsetForValueFromArray2(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFIndex idx, uint64_t *offset, CFMutableDictionaryRef objects) {
 765     uint64_t objectsRangeStart = 8, objectsRangeEnd = trailer->_offsetTableOffset - 1;
 766     if (startOffset < objectsRangeStart || objectsRangeEnd < startOffset) FAIL_FALSE;
 767     const uint8_t *ptr = databytes + startOffset;
 768     uint8_t marker = *ptr;
 769     if ((marker & 0xf0) != kCFBinaryPlistMarkerArray) FAIL_FALSE;
 770     int32_t err = CF_NO_ERROR;
 771     ptr = check_ptr_add(ptr, 1, &err);
 772     if (CF_NO_ERROR != err) FAIL_FALSE;
 773     uint64_t cnt = (marker & 0x0f);
 774     if (0xf == cnt) {
 775         uint64_t bigint;
 776         if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
 777         if (LONG_MAX < bigint) FAIL_FALSE;
 778         cnt = bigint;
 779     }
 780     if (cnt <= idx) FAIL_FALSE;
 781     size_t byte_cnt = check_size_t_mul(cnt, trailer->_objectRefSize, &err);
 782     if (CF_NO_ERROR != err) FAIL_FALSE;
 783     const uint8_t *extent = check_ptr_add(ptr, byte_cnt, &err) - 1;
 784     if (CF_NO_ERROR != err) FAIL_FALSE;
 785     if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
 786     uint64_t off = _getOffsetOfRefAt(databytes, ptr + idx * trailer->_objectRefSize, trailer);
 787     if (offset) *offset = off;
 788     return true;
 789 }
 790
 791 // Compatibility method, to be removed soon
 792 CF_EXPORT bool __CFBinaryPlistGetOffsetForValueFromDictionary2(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFTypeRef key, uint64_t *koffset, uint64_t *voffset, CFMutableDictionaryRef objects) {
 793     return __CFBinaryPlistGetOffsetForValueFromDictionary3(databytes, datalen, startOffset, trailer, key, koffset, voffset, false, objects);
 794 }
 795
 796 /* Get the offset for a value in a dictionary in a binary property list.
 797  @param databytes A pointer to the start of the binary property list data.
 798  @param datalen The length of the data.
 799  @param startOffset The offset at which the dictionary starts.
 800  @param trailer A pointer to a filled out trailer structure (use __CFBinaryPlistGetTopLevelInfo).
 801  @param key A string key in the dictionary that should be searched for.
 802  @param koffset Will be filled out with the offset to the key in the data bytes.
 803  @param voffset Will be filled out with the offset to the value in the data bytes.
 804  @param unused Unused parameter.
 805  @param objects Used for caching objects. Should be a valid CFMutableDictionaryRef.
 806  @return True if the key was found, false otherwise.
 807 */
 808 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) {
 809
 810     // Require a key that is a plist primitive
 811     if (!key || !_plistIsPrimitive(key)) FAIL_FALSE;
 812
 813     // Require that startOffset is in the range of the object table
 814     uint64_t objectsRangeStart = 8, objectsRangeEnd = trailer->_offsetTableOffset - 1;
 815     if (startOffset < objectsRangeStart || objectsRangeEnd < startOffset) FAIL_FALSE;
 816
 817     // ptr is the start of the dictionary we are reading
 818     const uint8_t *ptr = databytes + startOffset;
 819
 820     // Check that the data pointer actually points to a dictionary
 821     uint8_t marker = *ptr;
 822     if ((marker & 0xf0) != kCFBinaryPlistMarkerDict) FAIL_FALSE;
 823
 824     // Get the number of objects in this dictionary
 825     int32_t err = CF_NO_ERROR;
 826     ptr = check_ptr_add(ptr, 1, &err);
 827     if (CF_NO_ERROR != err) FAIL_FALSE;
 828     uint64_t cnt = (marker & 0x0f);
 829     if (0xf == cnt) {
 830         uint64_t bigint = 0;
 831         if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
 832         if (LONG_MAX < bigint) FAIL_FALSE;
 833         cnt = bigint;
 834     }
 835
 836     // Total number of objects (keys + values) is cnt * 2
 837     cnt = check_size_t_mul(cnt, 2, &err);
 838     if (CF_NO_ERROR != err) FAIL_FALSE;
 839     size_t byte_cnt = check_size_t_mul(cnt, trailer->_objectRefSize, &err);
 840     if (CF_NO_ERROR != err) FAIL_FALSE;
 841
 842     // Find the end of the dictionary
 843     const uint8_t *extent = check_ptr_add(ptr, byte_cnt, &err) - 1;
 844     if (CF_NO_ERROR != err) FAIL_FALSE;
 845
 846     // Check that we didn't overflow the size of the dictionary
 847     if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
 848
 849     // For short keys (15 bytes or less) in ASCII form, we can do a quick comparison check
 850     // We get the pointer or copy the buffer here, outside of the loop
 851     CFIndex stringKeyLen = -1;
 852     if (__CFGenericTypeID_genericobj_inline(key) == stringtype) {
 853         stringKeyLen = CFStringGetLength((CFStringRef)key);
 854     }
 855
 856     // Find the object in the dictionary with this key
 857     cnt = cnt / 2;
 858     uint64_t totalKeySize = cnt * trailer->_objectRefSize;
 859     uint64_t off;
 860     Boolean match = false;
 861     CFPropertyListRef keyInData = NULL;
 862
 863     char keyBuffer[16];
 864     const char *keyBufferPtr = keyBuffer;
 865
 866     if (stringKeyLen < 0xf) {
 867         // Since we will only be comparing ASCII strings, we can attempt to get a pointer using MacRoman encoding
 868         // (this is cheaper than a copy)
 869         if (!(keyBufferPtr = CFStringGetCStringPtr((CFStringRef)key, kCFStringEncodingMacRoman))) {
 870             CFStringGetCString((CFStringRef)key, keyBuffer, 16, kCFStringEncodingMacRoman);
 871             // The pointer should now point to our keyBuffer instead of the original string buffer, since we've copied it
 872             keyBufferPtr = keyBuffer;
 873         }
 874     }
 875
 876     // Perform linear search of the keys
 877     for (CFIndex idx = 0; idx < cnt; idx++) {
 878         off = _getOffsetOfRefAt(databytes, ptr, trailer);
 879         marker = *(databytes + off);
 880         CFIndex len = marker & 0x0f;
 881         // if it is a short ascii string in the data, and the key is a string
 882         if (stringKeyLen != -1 && len < 0xf && (marker & 0xf0) == kCFBinaryPlistMarkerASCIIString) {
 883             if (len == stringKeyLen) {
 884                 err = CF_NO_ERROR;
 885                 const uint8_t *ptr2 = databytes + off;
 886                 extent = check_ptr_add(ptr2, len, &err);
 887                 if (CF_NO_ERROR != err) FAIL_FALSE;
 888
 889                 if (databytes + trailer->_offsetTableOffset <= extent) FAIL_FALSE;
 890
 891                 // Compare the key to this potential match (ptr2 + 1 moves past the marker)
 892                 if (memcmp(ptr2 + 1, keyBufferPtr, stringKeyLen) == 0) {
 893                     match = true;
 894                 }
 895             }
 896         } else {
 897             keyInData = NULL;
 898             if (!__CFBinaryPlistCreateObject2(databytes, datalen, off, trailer, kCFAllocatorSystemDefault, kCFPropertyListImmutable, objects, NULL, 0, &keyInData) || !_plistIsPrimitive(keyInData)) {
 899                 if (keyInData) CFRelease(keyInData);
 900                 return false;
 901             }
 902
 903             match = CFEqual(key, keyInData);
 904             CFRelease(keyInData);
 905         }
 906
 907         if (match) {
 908             if (koffset) *koffset = off;
 909             if (voffset) *voffset = _getOffsetOfRefAt(databytes, ptr + totalKeySize, trailer);
 910             return true;
 911         }
 912
 913         ptr += trailer->_objectRefSize;
 914     }
 915
 916     return false;
 917 }
 918
 919 CF_EXPORT bool __CFBinaryPlistCreateObject2(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFAllocatorRef allocator, CFOptionFlags mutabilityOption, CFMutableDictionaryRef objects, CFMutableSetRef set, CFIndex curDepth, CFPropertyListRef *plist) {
 920
 921     if (objects) {
 922         *plist = CFDictionaryGetValue(objects, (const void *)(uintptr_t)startOffset);
 923         if (*plist) {
 924             CFRetain(*plist);
 925             return true;
 926         }
 927     }
 928
 929     // at any one invocation of this function, set should contain the offsets in the "path" down to this object
 930     if (set && CFSetContainsValue(set, (const void *)(uintptr_t)startOffset)) return false;
 931
 932     // databytes is trusted to be at least datalen bytes long
 933     // *trailer contents are trusted, even for overflows -- was checked when the trailer was parsed
 934     uint64_t objectsRangeStart = 8, objectsRangeEnd = trailer->_offsetTableOffset - 1;
 935     if (startOffset < objectsRangeStart || objectsRangeEnd < startOffset) FAIL_FALSE;
 936
 937     uint64_t off;
 938     CFPropertyListRef *list, buffer[256];
 939     CFAllocatorRef listAllocator;
 940
 941     uint8_t marker = *(databytes + startOffset);
 942     switch (marker & 0xf0) {
 943     case kCFBinaryPlistMarkerNull:
 944         switch (marker) {
 945         case kCFBinaryPlistMarkerNull:
 946             *plist = kCFNull;
 947             return true;
 948         case kCFBinaryPlistMarkerFalse:
 949             *plist = CFRetain(kCFBooleanFalse);
 950             return true;
 951         case kCFBinaryPlistMarkerTrue:
 952             *plist = CFRetain(kCFBooleanTrue);
 953             return true;
 954         }
 955         FAIL_FALSE;
 956     case kCFBinaryPlistMarkerInt:
 957     {
 958         const uint8_t *ptr = (databytes + startOffset);
 959         int32_t err = CF_NO_ERROR;
 960         ptr = check_ptr_add(ptr, 1, &err);
 961         if (CF_NO_ERROR != err) FAIL_FALSE;
 962         uint64_t cnt = 1 << (marker & 0x0f);
 963         const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
 964         if (CF_NO_ERROR != err) FAIL_FALSE;
 965         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
 966         if (16 < cnt) FAIL_FALSE;
 967         // in format version '00', 1, 2, and 4-byte integers have to be interpreted as unsigned,
 968         // whereas 8-byte integers are signed (and 16-byte when available)
 969         // negative 1, 2, 4-byte integers are always emitted as 8 bytes in format '00'
 970         // integers are not required to be in the most compact possible representation, but only the last 64 bits are significant currently
 971         uint64_t bigint = _getSizedInt(ptr, cnt);
 972         ptr += cnt;
 973         if (8 < cnt) {
 974             CFSInt128Struct val;
 975             val.high = 0;
 976             val.low = bigint;
 977             *plist = CFNumberCreate(allocator, kCFNumberSInt128Type, &val);
 978         } else {
 979             *plist = CFNumberCreate(allocator, kCFNumberSInt64Type, &bigint);
 980         }
 981         // these are always immutable
 982         if (objects && *plist) {
 983             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
 984         }
 985         return (*plist) ? true : false;
 986     }
 987     case kCFBinaryPlistMarkerReal:
 988         switch (marker & 0x0f) {
 989         case 2: {
 990             const uint8_t *ptr = (databytes + startOffset);
 991             int32_t err = CF_NO_ERROR;
 992             ptr = check_ptr_add(ptr, 1, &err);
 993             if (CF_NO_ERROR != err) FAIL_FALSE;
 994             const uint8_t *extent = check_ptr_add(ptr, 4, &err) - 1;
 995             if (CF_NO_ERROR != err) FAIL_FALSE;
 996             if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
 997             CFSwappedFloat32 swapped32;
 998             memmove(&swapped32, ptr, 4);
 999             float f = CFConvertFloat32SwappedToHost(swapped32);
1000             *plist = CFNumberCreate(allocator, kCFNumberFloat32Type, &f);
1001             // these are always immutable
1002             if (objects && *plist) {
1003                 CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1004             }
1005             return (*plist) ? true : false;
1006         }
1007         case 3: {
1008             const uint8_t *ptr = (databytes + startOffset);
1009             int32_t err = CF_NO_ERROR;
1010             ptr = check_ptr_add(ptr, 1, &err);
1011             if (CF_NO_ERROR != err) FAIL_FALSE;
1012             const uint8_t *extent = check_ptr_add(ptr, 8, &err) - 1;
1013             if (CF_NO_ERROR != err) FAIL_FALSE;
1014             if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1015             CFSwappedFloat64 swapped64;
1016             memmove(&swapped64, ptr, 8);
1017             double d = CFConvertFloat64SwappedToHost(swapped64);
1018             *plist = CFNumberCreate(allocator, kCFNumberFloat64Type, &d);
1019             // these are always immutable
1020             if (objects && *plist) {
1021                 CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1022             }
1023             return (*plist) ? true : false;
1024         }
1025         }
1026         FAIL_FALSE;
1027     case kCFBinaryPlistMarkerDate & 0xf0:
1028         switch (marker) {
1029         case kCFBinaryPlistMarkerDate: {
1030             const uint8_t *ptr = (databytes + startOffset);
1031             int32_t err = CF_NO_ERROR;
1032             ptr = check_ptr_add(ptr, 1, &err);
1033             if (CF_NO_ERROR != err) FAIL_FALSE;
1034             const uint8_t *extent = check_ptr_add(ptr, 8, &err) - 1;
1035             if (CF_NO_ERROR != err) FAIL_FALSE;
1036             if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1037             CFSwappedFloat64 swapped64;
1038             memmove(&swapped64, ptr, 8);
1039             double d = CFConvertFloat64SwappedToHost(swapped64);
1040             *plist = CFDateCreate(allocator, d);
1041             // these are always immutable
1042             if (objects && *plist) {
1043                 CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1044             }
1045             return (*plist) ? true : false;
1046         }
1047         }
1048         FAIL_FALSE;
1049     case kCFBinaryPlistMarkerData: {
1050         const uint8_t *ptr = databytes + startOffset;
1051         int32_t err = CF_NO_ERROR;
1052         ptr = check_ptr_add(ptr, 1, &err);
1053         if (CF_NO_ERROR != err) FAIL_FALSE;
1054         CFIndex cnt = marker & 0x0f;
1055         if (0xf == cnt) {
1056             uint64_t bigint = 0;
1057             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1058             if (LONG_MAX < bigint) FAIL_FALSE;
1059             cnt = (CFIndex)bigint;
1060         }
1061         const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
1062         if (CF_NO_ERROR != err) FAIL_FALSE;
1063         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1064         if (mutabilityOption == kCFPropertyListMutableContainersAndLeaves) {
1065             *plist = CFDataCreateMutable(allocator, 0);
1066             if (*plist) CFDataAppendBytes((CFMutableDataRef)*plist, ptr, cnt);
1067         } else {
1068             *plist = CFDataCreate(allocator, ptr, cnt);
1069         }
1070         if (objects && *plist && (mutabilityOption != kCFPropertyListMutableContainersAndLeaves)) {
1071             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1072         }
1073         return (*plist) ? true : false;
1074         }
1075     case kCFBinaryPlistMarkerASCIIString: {
1076         const uint8_t *ptr = databytes + startOffset;
1077         int32_t err = CF_NO_ERROR;
1078         ptr = check_ptr_add(ptr, 1, &err);
1079         if (CF_NO_ERROR != err) FAIL_FALSE;
1080         CFIndex cnt = marker & 0x0f;
1081         if (0xf == cnt) {
1082             uint64_t bigint = 0;
1083             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1084             if (LONG_MAX < bigint) FAIL_FALSE;
1085             cnt = (CFIndex)bigint;
1086         }
1087         const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
1088         if (CF_NO_ERROR != err) FAIL_FALSE;
1089         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1090         if (mutabilityOption == kCFPropertyListMutableContainersAndLeaves) {
1091             CFStringRef str = CFStringCreateWithBytes(allocator, ptr, cnt, kCFStringEncodingASCII, false);
1092             *plist = str ? CFStringCreateMutableCopy(allocator, 0, str) : NULL;
1093             if (str) CFRelease(str);
1094         } else {
1095             *plist = CFStringCreateWithBytes(allocator, ptr, cnt, kCFStringEncodingASCII, false);
1096         }
1097         if (objects && *plist && (mutabilityOption != kCFPropertyListMutableContainersAndLeaves)) {
1098             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1099         }
1100         return (*plist) ? true : false;
1101         }
1102     case kCFBinaryPlistMarkerUnicode16String: {
1103         const uint8_t *ptr = databytes + startOffset;
1104         int32_t err = CF_NO_ERROR;
1105         ptr = check_ptr_add(ptr, 1, &err);
1106         if (CF_NO_ERROR != err) FAIL_FALSE;
1107         CFIndex cnt = marker & 0x0f;
1108         if (0xf == cnt) {
1109             uint64_t bigint = 0;
1110             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1111             if (LONG_MAX < bigint) FAIL_FALSE;
1112             cnt = (CFIndex)bigint;
1113         }
1114         const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
1115         extent = check_ptr_add(extent, cnt, &err);      // 2 bytes per character
1116         if (CF_NO_ERROR != err) FAIL_FALSE;
1117         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1118         size_t byte_cnt = check_size_t_mul(cnt, sizeof(UniChar), &err);
1119         if (CF_NO_ERROR != err) FAIL_FALSE;
1120         UniChar *chars = (UniChar *)CFAllocatorAllocate(allocator, byte_cnt, 0);
1121         if (!chars) FAIL_FALSE;
1122         memmove(chars, ptr, byte_cnt);
1123         for (CFIndex idx = 0; idx < cnt; idx++) {
1124             chars[idx] = CFSwapInt16BigToHost(chars[idx]);
1125         }
1126         if (mutabilityOption == kCFPropertyListMutableContainersAndLeaves) {
1127             CFStringRef str = CFStringCreateWithCharactersNoCopy(allocator, chars, cnt, allocator);
1128             *plist = str ? CFStringCreateMutableCopy(allocator, 0, str) : NULL;
1129             if (str) CFRelease(str);
1130         } else {
1131             *plist = CFStringCreateWithCharactersNoCopy(allocator, chars, cnt, allocator);
1132         }
1133         if (objects && *plist && (mutabilityOption != kCFPropertyListMutableContainersAndLeaves)) {
1134             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1135         }
1136         return (*plist) ? true : false;
1137         }
1138     case kCFBinaryPlistMarkerUID: {
1139         const uint8_t *ptr = databytes + startOffset;
1140         int32_t err = CF_NO_ERROR;
1141         ptr = check_ptr_add(ptr, 1, &err);
1142         if (CF_NO_ERROR != err) FAIL_FALSE;
1143         CFIndex cnt = (marker & 0x0f) + 1;
1144         const uint8_t *extent = check_ptr_add(ptr, cnt, &err) - 1;
1145         if (CF_NO_ERROR != err) FAIL_FALSE;
1146         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1147         // uids are not required to be in the most compact possible representation, but only the last 64 bits are significant currently
1148         uint64_t bigint = _getSizedInt(ptr, cnt);
1149         ptr += cnt;
1150         if (UINT32_MAX < bigint) FAIL_FALSE;
1151         *plist = _CFKeyedArchiverUIDCreate(allocator, (uint32_t)bigint);
1152         // these are always immutable
1153         if (objects && *plist) {
1154             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1155         }
1156         return (*plist) ? true : false;
1157         }
1158     case kCFBinaryPlistMarkerArray:
1159     case kCFBinaryPlistMarkerSet: {
1160         const uint8_t *ptr = databytes + startOffset;
1161         int32_t err = CF_NO_ERROR;
1162         ptr = check_ptr_add(ptr, 1, &err);
1163         if (CF_NO_ERROR != err) FAIL_FALSE;
1164         CFIndex cnt = marker & 0x0f;
1165         if (0xf == cnt) {
1166             uint64_t bigint = 0;
1167             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1168             if (LONG_MAX < bigint) FAIL_FALSE;
1169             cnt = (CFIndex)bigint;
1170         }
1171         size_t byte_cnt = check_size_t_mul(cnt, trailer->_objectRefSize, &err);
1172         if (CF_NO_ERROR != err) FAIL_FALSE;
1173         const uint8_t *extent = check_ptr_add(ptr, byte_cnt, &err) - 1;
1174         if (CF_NO_ERROR != err) FAIL_FALSE;
1175         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1176         byte_cnt = check_size_t_mul(cnt, sizeof(CFPropertyListRef), &err);
1177         if (CF_NO_ERROR != err) FAIL_FALSE;
1178         list = (cnt <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, byte_cnt, 0);
1179         listAllocator = (list == buffer ? kCFAllocatorNull : kCFAllocatorSystemDefault);
1180         if (!list) FAIL_FALSE;
1181         Boolean madeSet = false;
1182         if (!set && 15 < curDepth) {
1183             set = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, NULL);
1184             madeSet = set ? true : false;
1185         }
1186         if (set) CFSetAddValue(set, (const void *)(uintptr_t)startOffset);
1187         for (CFIndex idx = 0; idx < cnt; idx++) {
1188             CFPropertyListRef pl;
1189             off = _getOffsetOfRefAt(databytes, ptr, trailer);
1190             if (!__CFBinaryPlistCreateObject2(databytes, datalen, off, trailer, allocator, mutabilityOption, objects, set, curDepth + 1, &pl)) {
1191                 while (idx--) {
1192                     CFRelease(list[idx]);
1193                 }
1194                 if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1195                 FAIL_FALSE;
1196             }
1197             list[idx] = pl;
1198             ptr += trailer->_objectRefSize;
1199         }
1200         if (set) CFSetRemoveValue(set, (const void *)(uintptr_t)startOffset);
1201         if (madeSet) {
1202             CFRelease(set);
1203             set = NULL;
1204         }
1205         if ((marker & 0xf0) == kCFBinaryPlistMarkerArray) {
1206             if (mutabilityOption != kCFPropertyListImmutable) {
1207                 *plist = CFArrayCreateMutable(allocator, 0, &kCFTypeArrayCallBacks);
1208                 CFArrayReplaceValues((CFMutableArrayRef)*plist, CFRangeMake(0, 0), list, cnt);
1209             } else {
1210                 *plist = CFArrayCreate(allocator, list, cnt, &kCFTypeArrayCallBacks);
1211             }
1212         } else {
1213             if (mutabilityOption != kCFPropertyListImmutable) {
1214                 *plist = CFSetCreateMutable(allocator, 0, &kCFTypeSetCallBacks);
1215                 for (CFIndex idx = 0; idx < cnt; idx++) {
1216                     CFSetAddValue((CFMutableSetRef)*plist, list[idx]);
1217                 }
1218             } else {
1219                 *plist = CFSetCreate(allocator, list, cnt, &kCFTypeSetCallBacks);
1220             }
1221         }
1222         for (CFIndex idx = 0; idx < cnt; idx++) {
1223             CFRelease(list[idx]);
1224         }
1225         if (objects && *plist && (mutabilityOption == kCFPropertyListImmutable)) {
1226             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1227         }
1228         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1229         return (*plist) ? true : false;
1230         }
1231     case kCFBinaryPlistMarkerDict: {
1232         const uint8_t *ptr = databytes + startOffset;
1233         int32_t err = CF_NO_ERROR;
1234         ptr = check_ptr_add(ptr, 1, &err);
1235         if (CF_NO_ERROR != err) FAIL_FALSE;
1236         CFIndex cnt = marker & 0x0f;
1237         if (0xf == cnt) {
1238             uint64_t bigint = 0;
1239             if (!_readInt(ptr, databytes + objectsRangeEnd, &bigint, &ptr)) FAIL_FALSE;
1240             if (LONG_MAX < bigint) FAIL_FALSE;
1241             cnt = (CFIndex)bigint;
1242         }
1243         cnt = check_size_t_mul(cnt, 2, &err);
1244         if (CF_NO_ERROR != err) FAIL_FALSE;
1245         size_t byte_cnt = check_size_t_mul(cnt, trailer->_objectRefSize, &err);
1246         if (CF_NO_ERROR != err) FAIL_FALSE;
1247         const uint8_t *extent = check_ptr_add(ptr, byte_cnt, &err) - 1;
1248         if (CF_NO_ERROR != err) FAIL_FALSE;
1249         if (databytes + objectsRangeEnd < extent) FAIL_FALSE;
1250         byte_cnt = check_size_t_mul(cnt, sizeof(CFPropertyListRef), &err);
1251         if (CF_NO_ERROR != err) FAIL_FALSE;
1252         list = (cnt <= 256) ? buffer : (CFPropertyListRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, byte_cnt, 0);
1253         listAllocator = (list == buffer ? kCFAllocatorNull : kCFAllocatorSystemDefault);
1254         if (!list) FAIL_FALSE;
1255         Boolean madeSet = false;
1256         if (!set && 15 < curDepth) {
1257             set = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, NULL);
1258             madeSet = set ? true : false;
1259         }
1260         if (set) CFSetAddValue(set, (const void *)(uintptr_t)startOffset);
1261         for (CFIndex idx = 0; idx < cnt; idx++) {
1262             CFPropertyListRef pl = NULL;
1263             off = _getOffsetOfRefAt(databytes, ptr, trailer);
1264             if (!__CFBinaryPlistCreateObject2(databytes, datalen, off, trailer, allocator, mutabilityOption, objects, set, curDepth + 1, &pl) || (idx < cnt / 2 && !_plistIsPrimitive(pl))) {
1265                 if (pl) CFRelease(pl);
1266                 while (idx--) {
1267                     CFRelease(list[idx]);
1268                 }
1269                 if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1270                 FAIL_FALSE;
1271             }
1272             list[idx] = pl;
1273             ptr += trailer->_objectRefSize;
1274         }
1275         if (set) CFSetRemoveValue(set, (const void *)(uintptr_t)startOffset);
1276         if (madeSet) {
1277             CFRelease(set);
1278             set = NULL;
1279         }
1280         if (mutabilityOption != kCFPropertyListImmutable) {
1281             *plist = CFDictionaryCreateMutable(allocator, 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
1282             for (CFIndex idx = 0; idx < cnt / 2; idx++) {
1283                 CFDictionaryAddValue((CFMutableDictionaryRef)*plist, list[idx], list[idx + cnt / 2]);
1284             }
1285         } else {
1286             *plist = CFDictionaryCreate(allocator, list, list + cnt / 2, cnt / 2, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
1287         }
1288         for (CFIndex idx = 0; idx < cnt; idx++) {
1289                 CFRelease(list[idx]);
1290         }
1291         if (objects && *plist && (mutabilityOption == kCFPropertyListImmutable)) {
1292             CFDictionarySetValue(objects, (const void *)(uintptr_t)startOffset, *plist);
1293         }
1294         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
1295         return (*plist) ? true : false;
1296         }
1297     }
1298     FAIL_FALSE;
1299 }
1300
1301 bool __CFBinaryPlistCreateObject(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFAllocatorRef allocator, CFOptionFlags mutabilityOption, CFMutableDictionaryRef objects, CFPropertyListRef *plist) {
1302         // for compatibility with Foundation's use, need to leave this here
1303     return __CFBinaryPlistCreateObject2(databytes, datalen, startOffset, trailer, allocator, mutabilityOption, objects, NULL, 0, plist);
1304 }
1305
1306 __private_extern__ bool __CFTryParseBinaryPlist(CFAllocatorRef allocator, CFDataRef data, CFOptionFlags option, CFPropertyListRef *plist, CFStringRef *errorString) {
1307     uint8_t marker;
1308     CFBinaryPlistTrailer trailer;
1309     uint64_t offset;
1310     const uint8_t *databytes = CFDataGetBytePtr(data);
1311     uint64_t datalen = CFDataGetLength(data);
1312
1313     if (8 <= datalen && __CFBinaryPlistGetTopLevelInfo(databytes, datalen, &marker, &offset, &trailer)) {
1314         // FALSE: We know for binary plist parsing that the result objects will be retained
1315         // by their containing collections as the parsing proceeds, so we do not need
1316         // to use retaining callbacks for the objects map in this case. WHY: the file might
1317         // be malformed and contain hash-equal keys for the same dictionary (for example)
1318         // and the later key will cause the previous one to be released when we set the second
1319         // in the dictionary.
1320         CFMutableDictionaryRef objects = CFDictionaryCreateMutable(kCFAllocatorSystemDefault, 0, NULL, &kCFTypeDictionaryValueCallBacks);
1321         _CFDictionarySetCapacity(objects, trailer._numObjects);
1322         CFPropertyListRef pl = NULL;
1323         if (__CFBinaryPlistCreateObject2(databytes, datalen, offset, &trailer, allocator, option, objects, NULL, 0, &pl)) {
1324             if (plist) *plist = pl;
1325         } else {
1326             if (plist) *plist = NULL;
1327             if (errorString) *errorString = (CFStringRef)CFRetain(CFSTR("binary data is corrupt"));
1328         }
1329         CFRelease(objects);
1330         return true;
1331     }
1332     return false;
1333 }