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