Parsing.subproj/CFBinaryPList.c

   1 /*
   2  * Copyright (c) 2005 Apple Computer, 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 2000-2002, Apple, Inc. All rights reserved.
  25         Responsibility: Christopher Kane
  26 */
  27
  28 #include <CoreFoundation/CFBase.h>
  29 #include <CoreFoundation/CFString.h>
  30 #include <CoreFoundation/CFNumber.h>
  31 #include <CoreFoundation/CFDate.h>
  32 #include <CoreFoundation/CFData.h>
  33 #include <CoreFoundation/CFArray.h>
  34 #include <CoreFoundation/CFDictionary.h>
  35 #include <CoreFoundation/CFSet.h>
  36 #include <CoreFoundation/CFPropertyList.h>
  37 #include <CoreFoundation/CFByteOrder.h>
  38 #include <CoreFoundation/CFRuntime.h>
  39 #include <CoreFoundation/CFStream.h>
  40 #include <stdio.h>
  41 #include <limits.h>
  42 #include <string.h>
  43 #include "CFInternal.h"
  44
  45
  46 CF_INLINE CFTypeID __CFGenericTypeID_genericobj_inline(const void *cf) {
  47     CFTypeID typeID = __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_info, 15, 8);
  48     return CF_IS_OBJC(typeID, cf) ? CFGetTypeID(cf) : typeID;
  49 }
  50
  51 struct __CFKeyedArchiverUID {
  52     CFRuntimeBase _base;
  53     uint32_t _value;
  54 };
  55
  56 static CFStringRef __CFKeyedArchiverUIDCopyDescription(CFTypeRef cf) {
  57     CFKeyedArchiverUIDRef uid = (CFKeyedArchiverUIDRef)cf;
  58     return CFStringCreateWithFormat(kCFAllocatorDefault, NULL, CFSTR("<CFKeyedArchiverUID %p [%p]>{value = %u}"), cf, CFGetAllocator(cf), uid->_value);
  59 }
  60
  61 static CFStringRef __CFKeyedArchiverUIDCopyFormattingDescription(CFTypeRef cf, CFDictionaryRef formatOptions) {
  62     CFKeyedArchiverUIDRef uid = (CFKeyedArchiverUIDRef)cf;
  63     return CFStringCreateWithFormat(kCFAllocatorDefault, NULL, CFSTR("@%u@"), uid->_value);
  64 }
  65
  66 static CFTypeID __kCFKeyedArchiverUIDTypeID = _kCFRuntimeNotATypeID;
  67
  68 static const CFRuntimeClass __CFKeyedArchiverUIDClass = {
  69     0,
  70     "CFKeyedArchiverUID",
  71     NULL,       // init
  72     NULL,       // copy
  73     NULL,       // finalize
  74     NULL,       // equal -- pointer equality only
  75     NULL,       // hash -- pointer hashing only
  76     __CFKeyedArchiverUIDCopyFormattingDescription,
  77     __CFKeyedArchiverUIDCopyDescription
  78 };
  79
  80 __private_extern__ void __CFKeyedArchiverUIDInitialize(void) {
  81     __kCFKeyedArchiverUIDTypeID = _CFRuntimeRegisterClass(&__CFKeyedArchiverUIDClass);
  82 }
  83
  84 CFTypeID _CFKeyedArchiverUIDGetTypeID(void) {
  85     return __kCFKeyedArchiverUIDTypeID;
  86 }
  87
  88 CFKeyedArchiverUIDRef _CFKeyedArchiverUIDCreate(CFAllocatorRef allocator, uint32_t value) {
  89     CFKeyedArchiverUIDRef uid;
  90     uid = (CFKeyedArchiverUIDRef)_CFRuntimeCreateInstance(allocator, __kCFKeyedArchiverUIDTypeID, sizeof(struct __CFKeyedArchiverUID) - sizeof(CFRuntimeBase), NULL);
  91     if (NULL == uid) {
  92         return NULL;
  93     }
  94     ((struct __CFKeyedArchiverUID *)uid)->_value = value;
  95     return uid;
  96 }
  97
  98
  99 uint32_t _CFKeyedArchiverUIDGetValue(CFKeyedArchiverUIDRef uid) {
 100     return uid->_value;
 101 }
 102
 103
 104 typedef struct {
 105     CFTypeRef stream;
 106     bool streamIsData;
 107     uint64_t written;
 108     int32_t used;
 109     uint8_t buffer[8192 - 16];
 110 } __CFBinaryPlistWriteBuffer;
 111
 112 CF_INLINE void writeBytes(__CFBinaryPlistWriteBuffer *buf, const UInt8 *bytes, CFIndex length) {
 113     if (buf->streamIsData) {
 114         CFDataAppendBytes((CFMutableDataRef)buf->stream, bytes, length);
 115     } else {
 116         CFWriteStreamWrite((CFWriteStreamRef)buf->stream, bytes, length);
 117     }
 118 }
 119
 120 static void bufferWrite(__CFBinaryPlistWriteBuffer *buf, const uint8_t *buffer, CFIndex count) {
 121     CFIndex copyLen;
 122     if ((CFIndex)sizeof(buf->buffer) <= count) {
 123         writeBytes(buf, buf->buffer, buf->used);
 124         buf->written += buf->used;
 125         buf->used = 0;
 126         writeBytes(buf, buffer, count);
 127         buf->written += count;
 128         return;
 129     }
 130     copyLen = __CFMin(count, (CFIndex)sizeof(buf->buffer) - buf->used);
 131     memmove(buf->buffer + buf->used, buffer, copyLen);
 132     buf->used += copyLen;
 133     if (sizeof(buf->buffer) == buf->used) {
 134         writeBytes(buf, buf->buffer, sizeof(buf->buffer));
 135         buf->written += sizeof(buf->buffer);
 136         memmove(buf->buffer, buffer + copyLen, count - copyLen);
 137         buf->used = count - copyLen;
 138     }
 139 }
 140
 141 static void bufferFlush(__CFBinaryPlistWriteBuffer *buf) {
 142     writeBytes(buf, buf->buffer, buf->used);
 143     buf->written += buf->used;
 144     buf->used = 0;
 145 }
 146
 147 /*
 148 HEADER
 149         magic number ("bplist")
 150         file format version
 151
 152 OBJECT TABLE
 153         variable-sized objects
 154
 155         Object Formats (marker byte followed by additional info in some cases)
 156         null    0000 0000
 157         bool    0000 1000                       // false
 158         bool    0000 1001                       // true
 159         fill    0000 1111                       // fill byte
 160         int     0001 nnnn       ...             // # of bytes is 2^nnnn, big-endian bytes
 161         real    0010 nnnn       ...             // # of bytes is 2^nnnn, big-endian bytes
 162         date    0011 0011       ...             // 8 byte float follows, big-endian bytes
 163         data    0100 nnnn       [int]   ...     // nnnn is number of bytes unless 1111 then int count follows, followed by bytes
 164         string  0101 nnnn       [int]   ...     // ASCII string, nnnn is # of chars, else 1111 then int count, then bytes
 165         string  0110 nnnn       [int]   ...     // Unicode string, nnnn is # of chars, else 1111 then int count, then big-endian 2-byte uint16_t
 166                 0111 xxxx                       // unused
 167         uid     1000 nnnn       ...             // nnnn+1 is # of bytes
 168                 1001 xxxx                       // unused
 169         array   1010 nnnn       [int]   objref* // nnnn is count, unless '1111', then int count follows
 170                 1011 xxxx                       // unused
 171                 1100 xxxx                       // unused
 172         dict    1101 nnnn       [int]   keyref* objref* // nnnn is count, unless '1111', then int count follows
 173                 1110 xxxx                       // unused
 174                 1111 xxxx                       // unused
 175
 176 OFFSET TABLE
 177         list of ints, byte size of which is given in trailer
 178         -- these are the byte offsets into the file
 179         -- number of these is in the trailer
 180
 181 TRAILER
 182         byte size of offset ints in offset table
 183         byte size of object refs in arrays and dicts
 184         number of offsets in offset table (also is number of objects)
 185         element # in offset table which is top level object
 186
 187 */
 188
 189
 190 static CFTypeID stringtype = -1, datatype = -1, numbertype = -1, datetype = -1;
 191 static CFTypeID booltype = -1, dicttype = -1, arraytype = -1;
 192
 193 static void _appendInt(__CFBinaryPlistWriteBuffer *buf, uint64_t bigint) {
 194     uint8_t marker;
 195     uint8_t *bytes;
 196     CFIndex nbytes;
 197     if (bigint <= (uint64_t)0xff) {
 198         nbytes = 1;
 199         marker = kCFBinaryPlistMarkerInt | 0;
 200     } else if (bigint <= (uint64_t)0xffff) {
 201         nbytes = 2;
 202         marker = kCFBinaryPlistMarkerInt | 1;
 203     } else if (bigint <= (uint64_t)0xffffffff) {
 204         nbytes = 4;
 205         marker = kCFBinaryPlistMarkerInt | 2;
 206     } else {
 207         nbytes = 8;
 208         marker = kCFBinaryPlistMarkerInt | 3;
 209     }
 210     bigint = CFSwapInt64HostToBig(bigint);
 211     bytes = (uint8_t *)&bigint + sizeof(bigint) - nbytes;
 212     bufferWrite(buf, &marker, 1);
 213     bufferWrite(buf, bytes, nbytes);
 214 }
 215
 216 static void _appendUID(__CFBinaryPlistWriteBuffer *buf, CFKeyedArchiverUIDRef uid) {
 217     uint8_t marker;
 218     uint8_t *bytes;
 219     CFIndex nbytes;
 220     uint64_t bigint = _CFKeyedArchiverUIDGetValue(uid);
 221     if (bigint <= (uint64_t)0xff) {
 222         nbytes = 1;
 223     } else if (bigint <= (uint64_t)0xffff) {
 224         nbytes = 2;
 225     } else if (bigint <= (uint64_t)0xffffffff) {
 226         nbytes = 4;
 227     } else {
 228         nbytes = 8;
 229     }
 230     marker = kCFBinaryPlistMarkerUID | (nbytes - 1);
 231     bigint = CFSwapInt64HostToBig(bigint);
 232     bytes = (uint8_t *)&bigint + sizeof(bigint) - nbytes;
 233     bufferWrite(buf, &marker, 1);
 234     bufferWrite(buf, bytes, nbytes);
 235 }
 236
 237 static Boolean __plistUniquingEqual(CFTypeRef cf1, CFTypeRef cf2) {
 238     // As long as this equals function is more restrictive than the
 239     // existing one, for any given type, the hash function need not
 240     // also be provided for the uniquing set.
 241     if (__CFGenericTypeID_genericobj_inline(cf1) != __CFGenericTypeID_genericobj_inline(cf2)) return false;
 242     if (__CFGenericTypeID_genericobj_inline(cf1) == numbertype) {
 243         if (CFNumberIsFloatType(cf1) != CFNumberIsFloatType(cf2)) return false;
 244         return CFEqual(cf1, cf2);
 245     }
 246     return CFEqual(cf1, cf2);
 247 }
 248
 249 static void _flattenPlist(CFPropertyListRef plist, CFMutableArrayRef objlist, CFMutableDictionaryRef objtable, CFMutableSetRef uniquingsets[]) {
 250     CFPropertyListRef unique;
 251     uint32_t refnum;
 252     CFTypeID type = __CFGenericTypeID_genericobj_inline(plist);
 253     CFIndex idx;
 254     CFPropertyListRef *list, buffer[256];
 255
 256     // Do not unique dictionaries or arrays, because: they
 257     // are slow to compare, and have poor hash codes.
 258     // Uniquing bools is unnecessary.
 259     int which = -1;
 260     if (stringtype == type) {
 261         which = 0;
 262     } else if (numbertype == type) {
 263         which = 1;
 264     } else if (datatype == type) {
 265         which = 2;
 266     } else if (datetype == type) {
 267         which = 3;
 268     }
 269     if (1 && -1 != which) {
 270         CFMutableSetRef uniquingset = uniquingsets[which];
 271         CFIndex before = CFSetGetCount(uniquingset);
 272         CFSetAddValue(uniquingset, plist);
 273         CFIndex after = CFSetGetCount(uniquingset);
 274         if (after == before) {  // already in set
 275             unique = CFSetGetValue(uniquingset, plist);
 276             if (unique != plist) {
 277                 refnum = (uint32_t)CFDictionaryGetValue(objtable, unique);
 278                 CFDictionaryAddValue(objtable, plist, (const void *)refnum);
 279             }
 280             return;
 281         }
 282     }
 283     refnum = CFArrayGetCount(objlist);
 284     CFArrayAppendValue(objlist, plist);
 285     CFDictionaryAddValue(objtable, plist, (const void *)refnum);
 286     if (dicttype == type) {
 287         CFIndex count = CFDictionaryGetCount(plist);
 288         list = (count <= 128) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * count * sizeof(CFTypeRef), 0);
 289         CFDictionaryGetKeysAndValues(plist, list, list + count);
 290         for (idx = 0; idx < 2 * count; idx++) {
 291             _flattenPlist(list[idx], objlist, objtable, uniquingsets);
 292         }
 293         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 294     } else if (arraytype == type) {
 295         CFIndex count = CFArrayGetCount(plist);
 296         list = (count <= 256) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(CFTypeRef), 0);
 297         CFArrayGetValues(plist, CFRangeMake(0, count), list);
 298         for (idx = 0; idx < count; idx++) {
 299             _flattenPlist(list[idx], objlist, objtable, uniquingsets);
 300         }
 301         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 302     }
 303 }
 304
 305 // stream can be a CFWriteStreamRef or a CFMutableDataRef
 306 CFIndex __CFBinaryPlistWriteToStream(CFPropertyListRef plist, CFTypeRef stream) {
 307     CFMutableDictionaryRef objtable;
 308     CFMutableArrayRef objlist;
 309     CFBinaryPlistTrailer trailer;
 310     uint64_t *offsets, length_so_far;
 311     uint64_t mask, refnum;
 312     int64_t idx, idx2, cnt;
 313     __CFBinaryPlistWriteBuffer *buf;
 314     CFSetCallBacks cb = kCFTypeSetCallBacks;
 315
 316     if ((CFTypeID)-1 == stringtype) {
 317         stringtype = CFStringGetTypeID();
 318         datatype = CFDataGetTypeID();
 319         numbertype = CFNumberGetTypeID();
 320         booltype = CFBooleanGetTypeID();
 321         datetype = CFDateGetTypeID();
 322         dicttype = CFDictionaryGetTypeID();
 323         arraytype = CFArrayGetTypeID();
 324     }
 325     objtable = CFDictionaryCreateMutable(kCFAllocatorSystemDefault, 0, NULL, NULL);
 326     _CFDictionarySetCapacity(objtable, 640);
 327     objlist = CFArrayCreateMutable(kCFAllocatorSystemDefault, 0, NULL);
 328     _CFArraySetCapacity(objlist, 640);
 329     cb.equal = __plistUniquingEqual;
 330     CFMutableSetRef uniquingsets[4];
 331     uniquingsets[0] = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, &cb);
 332     _CFSetSetCapacity(uniquingsets[0], 1000);
 333     uniquingsets[1] = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, &cb);
 334     _CFSetSetCapacity(uniquingsets[1], 500);
 335     uniquingsets[2] = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, &cb);
 336     _CFSetSetCapacity(uniquingsets[2], 250);
 337     uniquingsets[3] = CFSetCreateMutable(kCFAllocatorSystemDefault, 0, &cb);
 338     _CFSetSetCapacity(uniquingsets[3], 250);
 339
 340     _flattenPlist(plist, objlist, objtable, uniquingsets);
 341
 342     CFRelease(uniquingsets[0]);
 343     CFRelease(uniquingsets[1]);
 344     CFRelease(uniquingsets[2]);
 345     CFRelease(uniquingsets[3]);
 346
 347     cnt = CFArrayGetCount(objlist);
 348     offsets = CFAllocatorAllocate(kCFAllocatorSystemDefault, cnt * sizeof(*offsets), 0);
 349
 350     buf = CFAllocatorAllocate(kCFAllocatorSystemDefault, sizeof(__CFBinaryPlistWriteBuffer), 0);
 351     buf->stream = stream;
 352     buf->streamIsData = (CFGetTypeID(stream) == CFDataGetTypeID());
 353     buf->written = 0;
 354     buf->used = 0;
 355     bufferWrite(buf, "bplist00", 8);    // header
 356
 357     memset(&trailer, 0, sizeof(trailer));
 358     trailer._numObjects = CFSwapInt64HostToBig(cnt);
 359     trailer._topObject = 0;     // true for this implementation
 360     mask = ~(uint64_t)0;
 361     while (cnt & mask) {
 362         trailer._objectRefSize++;
 363         mask = mask << 8;
 364     }
 365
 366     for (idx = 0; idx < cnt; idx++) {
 367         CFPropertyListRef obj = CFArrayGetValueAtIndex(objlist, idx);
 368         CFTypeID type = CFGetTypeID(obj);
 369         offsets[idx] = buf->written + buf->used;
 370         if (stringtype == type) {
 371             CFIndex ret, count = CFStringGetLength(obj);
 372             CFIndex needed;
 373             uint8_t *bytes, buffer[1024];
 374             bytes = (count <= 1024) ? buffer : CFAllocatorAllocate(kCFAllocatorDefault, count, 0);
 375             // presumption, believed to be true, is that ASCII encoding may need
 376             // less bytes, but will not need greater, than the # of unichars
 377             ret = CFStringGetBytes(obj, CFRangeMake(0, count), kCFStringEncodingASCII, 0, false, bytes, count, &needed);
 378             if (ret == count) {
 379                 uint8_t marker = kCFBinaryPlistMarkerASCIIString | (needed < 15 ? needed : 0xf);
 380                 bufferWrite(buf, &marker, 1);
 381                 if (15 <= needed) {
 382                     _appendInt(buf, (uint64_t)needed);
 383                 }
 384                 bufferWrite(buf, bytes, needed);
 385             } else {
 386                 UniChar *chars;
 387                 uint8_t marker = kCFBinaryPlistMarkerUnicode16String | (count < 15 ? count : 0xf);
 388                 bufferWrite(buf, &marker, 1);
 389                 if (15 <= count) {
 390                     _appendInt(buf, (uint64_t)count);
 391                 }
 392                 chars = CFAllocatorAllocate(kCFAllocatorDefault, count * sizeof(UniChar), 0);
 393                 CFStringGetCharacters(obj, CFRangeMake(0, count), chars);
 394                 for (idx2 = 0; idx2 < count; idx2++) {
 395                     chars[idx2] = CFSwapInt16HostToBig(chars[idx2]);
 396                 }
 397                 bufferWrite(buf, (uint8_t *)chars, count * sizeof(UniChar));
 398                 CFAllocatorDeallocate(kCFAllocatorDefault, chars);
 399             }
 400             if (bytes != buffer) CFAllocatorDeallocate(kCFAllocatorDefault, bytes);
 401         } else if (numbertype == type) {
 402             uint8_t marker;
 403             CFSwappedFloat64 swapped64;
 404             CFSwappedFloat32 swapped32;
 405             uint64_t bigint;
 406             uint8_t *bytes;
 407             CFIndex nbytes;
 408             if (CFNumberIsFloatType(obj)) {
 409                 if (CFNumberGetByteSize(obj) <= (CFIndex)sizeof(float)) {
 410                     float v;
 411                     CFNumberGetValue(obj, kCFNumberFloat32Type, &v);
 412                     swapped32 = CFConvertFloat32HostToSwapped(v);
 413                     bytes = (uint8_t *)&swapped32;
 414                     nbytes = sizeof(float);
 415                     marker = kCFBinaryPlistMarkerReal | 2;
 416                 } else {
 417                     double v;
 418                     CFNumberGetValue(obj, kCFNumberFloat64Type, &v);
 419                     swapped64 = CFConvertFloat64HostToSwapped(v);
 420                     bytes = (uint8_t *)&swapped64;
 421                     nbytes = sizeof(double);
 422                     marker = kCFBinaryPlistMarkerReal | 3;
 423                 }
 424                 bufferWrite(buf, &marker, 1);
 425                 bufferWrite(buf, bytes, nbytes);
 426             } else {
 427                 CFNumberGetValue(obj, kCFNumberSInt64Type, &bigint);
 428                 _appendInt(buf, bigint);
 429             }
 430         } else if (_CFKeyedArchiverUIDGetTypeID() == type) {
 431             _appendUID(buf, (CFKeyedArchiverUIDRef)obj);
 432         } else if (booltype == type) {
 433             uint8_t marker = CFBooleanGetValue(obj) ? kCFBinaryPlistMarkerTrue : kCFBinaryPlistMarkerFalse;
 434             bufferWrite(buf, &marker, 1);
 435         } else if (datatype == type) {
 436             CFIndex count = CFDataGetLength(obj);
 437             uint8_t marker = kCFBinaryPlistMarkerData | (count < 15 ? count : 0xf);
 438             bufferWrite(buf, &marker, 1);
 439             if (15 <= count) {
 440                 _appendInt(buf, (uint64_t)count);
 441             }
 442             bufferWrite(buf, CFDataGetBytePtr(obj), count);
 443         } else if (datetype == type) {
 444             CFSwappedFloat64 swapped;
 445             uint8_t marker = kCFBinaryPlistMarkerDate;
 446             bufferWrite(buf, &marker, 1);
 447             swapped = CFConvertFloat64HostToSwapped(CFDateGetAbsoluteTime(obj));
 448             bufferWrite(buf, (uint8_t *)&swapped, sizeof(swapped));
 449         } else if (dicttype == type) {
 450             CFIndex count = CFDictionaryGetCount(obj);
 451             CFPropertyListRef *list, buffer[512];
 452             uint8_t marker = kCFBinaryPlistMarkerDict | (count < 15 ? count : 0xf);
 453             bufferWrite(buf, &marker, 1);
 454             if (15 <= count) {
 455                 _appendInt(buf, (uint64_t)count);
 456             }
 457             list = (count <= 256) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * count * sizeof(CFTypeRef), 0);
 458             CFDictionaryGetKeysAndValues(obj, list, list + count);
 459             for (idx2 = 0; idx2 < 2 * count; idx2++) {
 460                 CFPropertyListRef value = list[idx2];
 461                 uint32_t swapped = 0;
 462                 uint8_t *source = (uint8_t *)&swapped;
 463                 refnum = (uint32_t)CFDictionaryGetValue(objtable, value);
 464                 swapped = CFSwapInt32HostToBig(refnum);
 465                 bufferWrite(buf, source + sizeof(swapped) - trailer._objectRefSize, trailer._objectRefSize);
 466             }
 467             if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 468         } else if (arraytype == type) {
 469             CFIndex count = CFArrayGetCount(obj);
 470             CFPropertyListRef *list, buffer[256];
 471             uint8_t marker = kCFBinaryPlistMarkerArray | (count < 15 ? count : 0xf);
 472             bufferWrite(buf, &marker, 1);
 473             if (15 <= count) {
 474                 _appendInt(buf, (uint64_t)count);
 475             }
 476             list = (count <= 256) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, count * sizeof(CFTypeRef), 0);
 477             CFArrayGetValues(obj, CFRangeMake(0, count), list);
 478             for (idx2 = 0; idx2 < count; idx2++) {
 479                 CFPropertyListRef value = list[idx2];
 480                 uint32_t swapped = 0;
 481                 uint8_t *source = (uint8_t *)&swapped;
 482                 refnum = (uint32_t)CFDictionaryGetValue(objtable, value);
 483                 swapped = CFSwapInt32HostToBig(refnum);
 484                 bufferWrite(buf, source + sizeof(swapped) - trailer._objectRefSize, trailer._objectRefSize);
 485             }
 486             if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 487         } else {
 488             CFRelease(objtable);
 489             CFRelease(objlist);
 490             CFAllocatorDeallocate(kCFAllocatorSystemDefault, buf);
 491             CFAllocatorDeallocate(kCFAllocatorSystemDefault, offsets);
 492             return 0;
 493         }
 494     }
 495     CFRelease(objtable);
 496     CFRelease(objlist);
 497
 498     length_so_far = buf->written + buf->used;
 499     trailer._offsetTableOffset = CFSwapInt64HostToBig(length_so_far);
 500     trailer._offsetIntSize = 0;
 501     mask = ~(uint64_t)0;
 502     while (length_so_far & mask) {
 503         trailer._offsetIntSize++;
 504         mask = mask << 8;
 505     }
 506
 507     for (idx = 0; idx < cnt; idx++) {
 508         uint64_t swapped = CFSwapInt64HostToBig(offsets[idx]);
 509         uint8_t *source = (uint8_t *)&swapped;
 510         bufferWrite(buf, source + sizeof(*offsets) - trailer._offsetIntSize, trailer._offsetIntSize);
 511     }
 512     length_so_far += cnt * trailer._offsetIntSize;
 513
 514     bufferWrite(buf, (uint8_t *)&trailer, sizeof(trailer));
 515     bufferFlush(buf);
 516     length_so_far += sizeof(trailer);
 517     CFAllocatorDeallocate(kCFAllocatorSystemDefault, buf);
 518     CFAllocatorDeallocate(kCFAllocatorSystemDefault, offsets);
 519     return (CFIndex)length_so_far;
 520 }
 521
 522 bool __CFBinaryPlistGetTopLevelInfo(const uint8_t *databytes, uint64_t datalen, uint8_t *marker, uint64_t *offset, CFBinaryPlistTrailer *trailer) {
 523     const uint8_t *bytesptr;
 524     CFBinaryPlistTrailer trail;
 525     uint64_t off;
 526     CFIndex idx;
 527
 528     if ((CFTypeID)-1 == stringtype) {
 529         stringtype = CFStringGetTypeID();
 530         datatype = CFDataGetTypeID();
 531         numbertype = CFNumberGetTypeID();
 532         booltype = CFBooleanGetTypeID();
 533         datetype = CFDateGetTypeID();
 534         dicttype = CFDictionaryGetTypeID();
 535         arraytype = CFArrayGetTypeID();
 536     }
 537     if (!databytes || datalen < 8 || 0 != memcmp("bplist00", databytes, 8)) return false;
 538     if (datalen < sizeof(trail) + 8 + 1) return false;
 539     memmove(&trail, databytes + datalen - sizeof(trail), sizeof(trail));
 540     trail._numObjects = CFSwapInt64BigToHost(trail._numObjects);
 541     trail._topObject = CFSwapInt64BigToHost(trail._topObject);
 542     if (trail._numObjects < trail._topObject) return false;
 543     trail._offsetTableOffset = CFSwapInt64BigToHost(trail._offsetTableOffset);
 544     if (datalen < trail._offsetTableOffset + trail._numObjects * trail._offsetIntSize + sizeof(trail)) return false;
 545     bytesptr = databytes + trail._offsetTableOffset + trail._topObject * trail._offsetIntSize;
 546     off = 0;
 547     for (idx = 0; idx < trail._offsetIntSize; idx++) {
 548         off = (off << 8) + bytesptr[idx];
 549     }
 550     if (trail._offsetTableOffset <= off) return false;
 551     if (trailer) *trailer = trail;
 552     if (offset) *offset = off;
 553     if (marker) *marker = *(databytes + off);
 554     return true;
 555 }
 556
 557 static bool _readInt(const uint8_t *ptr, uint64_t *bigint, const uint8_t **newptr) {
 558     uint8_t marker;
 559     CFIndex idx, cnt;
 560     marker = *ptr++;
 561     if ((marker & 0xf0) != kCFBinaryPlistMarkerInt) return false;
 562     cnt = 1 << (marker & 0xf);
 563     *bigint = 0;
 564     for (idx = 0; idx < cnt; idx++) {
 565         *bigint = (*bigint << 8) + *ptr++;
 566     }
 567     if (newptr) *newptr = ptr;
 568     return true;
 569 }
 570
 571 static uint64_t _getOffsetOfRefAt(const uint8_t *databytes, const uint8_t *bytesptr, const CFBinaryPlistTrailer *trailer) {
 572     uint64_t ref = 0, off = 0;
 573     CFIndex idx;
 574     for (idx = 0; idx < trailer->_objectRefSize; idx++) {
 575         ref = (ref << 8) + bytesptr[idx];
 576     }
 577     bytesptr = databytes + trailer->_offsetTableOffset + ref * trailer->_offsetIntSize;
 578     for (idx = 0; idx < trailer->_offsetIntSize; idx++) {
 579         off = (off << 8) + bytesptr[idx];
 580     }
 581     return off;
 582 }
 583
 584 bool __CFBinaryPlistGetOffsetForValueFromArray(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFIndex idx, uint64_t *offset) {
 585     const uint8_t *bytesptr;
 586     uint8_t marker;
 587     CFIndex cnt;
 588     uint64_t off;
 589
 590     marker = *(databytes + startOffset);
 591     if ((marker & 0xf0) != kCFBinaryPlistMarkerArray) return false;
 592     cnt = (marker & 0x0f);
 593     if (cnt < 15 && cnt <= idx) return false;
 594     bytesptr = databytes + startOffset + 1;
 595     if (0xf == cnt) {
 596         uint64_t bigint;
 597         if (!_readInt(bytesptr, &bigint, &bytesptr)) return false;
 598         if (INT_MAX < bigint) return false;
 599         cnt = (CFIndex)bigint;
 600     }
 601     if (cnt <= idx) return false;
 602     off = _getOffsetOfRefAt(databytes, bytesptr + idx * trailer->_objectRefSize, trailer);
 603     if (datalen <= off) return false;
 604     if (offset) *offset = off;
 605     return true;
 606 }
 607
 608 bool __CFBinaryPlistGetOffsetForValueFromDictionary(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFTypeRef key, uint64_t *koffset, uint64_t *voffset) {
 609     const uint8_t *refsptr, *bytesptr;
 610     uint64_t off;
 611     uint8_t marker;
 612     CFTypeID keytype = CFGetTypeID(key);
 613     CFIndex idx, keyn, cnt, cnt2;
 614
 615     marker = *(databytes + startOffset);
 616     if ((marker & 0xf0) != kCFBinaryPlistMarkerDict) return false;
 617     cnt = (marker & 0x0f);
 618     refsptr = databytes + startOffset + 1 + 0;
 619     if (0xf == cnt) {
 620         uint64_t bigint;
 621         if (!_readInt(refsptr, &bigint, &refsptr)) return false;
 622         if (INT_MAX < bigint) return false;
 623         cnt = (CFIndex)bigint;
 624     }
 625     for (keyn = 0; keyn < cnt; keyn++) {
 626         off = _getOffsetOfRefAt(databytes, refsptr, trailer);
 627         if (datalen <= off) return false;
 628         refsptr += trailer->_objectRefSize;
 629         bytesptr = databytes + off;
 630         marker = *bytesptr & 0xf0;
 631         cnt2 = *bytesptr & 0x0f;
 632         if (kCFBinaryPlistMarkerASCIIString == marker || kCFBinaryPlistMarkerUnicode16String == marker) {
 633             CFStringInlineBuffer strbuf;
 634             UniChar uchar;
 635             if (keytype != stringtype) goto miss;
 636             if (0xf == cnt2 && CFStringGetLength(key) < 15) goto miss;
 637             bytesptr++;
 638             if (0xf == cnt2) {
 639                 uint64_t bigint;
 640                 if (!_readInt(bytesptr, &bigint, &bytesptr)) return false;
 641                 if (INT_MAX < bigint) return false;
 642                 cnt2 = (CFIndex)bigint;
 643             }
 644             if (cnt2 != CFStringGetLength(key)) goto miss;
 645             uchar = (kCFBinaryPlistMarkerASCIIString == marker) ? (UniChar)bytesptr[0] : (UniChar)(bytesptr[0] * 256 + bytesptr[1]);
 646             if (uchar != CFStringGetCharacterAtIndex(key, 0)) goto miss;
 647             bytesptr += (kCFBinaryPlistMarkerASCIIString == marker) ? 1 : 2;
 648             CFStringInitInlineBuffer(key, &strbuf, CFRangeMake(0, cnt2));
 649             for (idx = 1; idx < cnt2; idx++) {
 650                 uchar = (kCFBinaryPlistMarkerASCIIString == marker) ? (UniChar)bytesptr[0] : (UniChar)(bytesptr[0] * 256 + bytesptr[1]);
 651                 if (uchar != __CFStringGetCharacterFromInlineBufferQuick(&strbuf, idx)) goto miss;
 652                 bytesptr += (kCFBinaryPlistMarkerASCIIString == marker) ? 1 : 2;
 653             }
 654             if (koffset) *koffset = off;
 655             off = _getOffsetOfRefAt(databytes, refsptr + (cnt - 1) * trailer->_objectRefSize, trailer);
 656             if (datalen <= off) return false;
 657             if (voffset) *voffset = off;
 658             return true;
 659         } else {
 660 //#warning the other primitive types should be allowed as keys in a binary plist dictionary, I think
 661             return false;
 662         }
 663         miss: ;
 664     }
 665     return false;
 666 }
 667
 668 extern CFArrayRef _CFArrayCreate_ex(CFAllocatorRef allocator, bool mutable, const void **values, CFIndex numValues);
 669
 670 extern CFDictionaryRef _CFDictionaryCreate_ex(CFAllocatorRef allocator, bool mutable, const void **keys, const void **values, CFIndex numValues);
 671
 672 #if 0
 673 static bool _getUIDFromData(const uint8_t *datap, uint64_t *vp) {
 674     int32_t idx, cnt;
 675     uint8_t marker = *datap;
 676     uint64_t bigint;
 677     if ((marker & 0xf0) != kCFBinaryPlistMarkerUID) return false;
 678     cnt = (marker & 0x0f) + 1;
 679     datap++;
 680     bigint = 0;
 681     for (idx = 0; idx < cnt; idx++) {
 682         bigint = (bigint << 8) + *datap++;
 683     }
 684     *vp = bigint;
 685     return true;
 686 }
 687 #endif
 688
 689 static bool _getFloatFromData(const uint8_t *datap, float *vp) {
 690     CFSwappedFloat32 swapped32;
 691     if (*datap != (kCFBinaryPlistMarkerReal | 2)) return false;
 692     datap++;
 693     memmove(&swapped32, datap, sizeof(swapped32));
 694     *vp = CFConvertFloat32SwappedToHost(swapped32);
 695     return true;
 696 }
 697
 698 static bool _getDoubleFromData(const uint8_t *datap, double *vp) {
 699     CFSwappedFloat64 swapped64;
 700     if (*datap != (kCFBinaryPlistMarkerReal | 3)) return false;
 701     datap++;
 702     memmove(&swapped64, datap, sizeof(swapped64));
 703     *vp = CFConvertFloat64SwappedToHost(swapped64);
 704     return true;
 705 }
 706
 707 bool __CFBinaryPlistCreateObject(const uint8_t *databytes, uint64_t datalen, uint64_t startOffset, const CFBinaryPlistTrailer *trailer, CFAllocatorRef allocator, CFOptionFlags mutabilityOption, CFMutableDictionaryRef objects, CFPropertyListRef *plist) {
 708     const uint8_t *bytesptr;
 709     uint64_t off;
 710     uint8_t marker;
 711     CFIndex idx, cnt;
 712     uint64_t bigint;
 713     UniChar *chars;
 714     CFPropertyListRef *list, buffer[256];
 715     CFAllocatorRef listAllocator;
 716
 717     if (objects) {
 718         *plist = CFDictionaryGetValue(objects, (const void *)(intptr_t)startOffset);
 719         if (*plist) {
 720             CFRetain(*plist);
 721             return true;
 722         }
 723     }
 724
 725     marker = *(databytes + startOffset);
 726     switch (marker & 0xf0) {
 727     case kCFBinaryPlistMarkerNull:
 728         switch (marker) {
 729         case kCFBinaryPlistMarkerNull:
 730             *plist = NULL;
 731             return true;
 732         case kCFBinaryPlistMarkerFalse:
 733             *plist = CFRetain(kCFBooleanFalse);
 734             return true;
 735         case kCFBinaryPlistMarkerTrue:
 736             *plist = CFRetain(kCFBooleanTrue);
 737             return true;
 738         }
 739         return false;
 740     case kCFBinaryPlistMarkerInt:
 741         if (!_readInt(databytes + startOffset, &bigint, NULL)) return false;
 742         *plist = CFNumberCreate(allocator, kCFNumberSInt64Type, &bigint);
 743         if (objects) CFDictionarySetValue(objects, (const void *)(intptr_t)startOffset, *plist);
 744         return (*plist) ? true : false;
 745     case kCFBinaryPlistMarkerReal:
 746         cnt = marker & 0x0f;
 747         if (2 == cnt) {
 748             float f;
 749             _getFloatFromData(databytes + startOffset, &f);
 750             *plist = CFNumberCreate(allocator, kCFNumberFloat32Type, &f);
 751             if (objects) CFDictionarySetValue(objects, (const void *)(intptr_t)startOffset, *plist);
 752             return (*plist) ? true : false;
 753         } else if (3 == cnt) {
 754             double d;
 755             _getDoubleFromData(databytes + startOffset, &d);
 756             *plist = CFNumberCreate(allocator, kCFNumberFloat64Type, &d);
 757             if (objects) CFDictionarySetValue(objects, (const void *)(intptr_t)startOffset, *plist);
 758             return (*plist) ? true : false;
 759         }
 760         return false;
 761     case kCFBinaryPlistMarkerDate & 0xf0: {
 762         CFSwappedFloat64 swapped64;
 763         double d;
 764         cnt = marker & 0x0f;
 765         if (3 != cnt) return false;
 766         memmove(&swapped64, databytes + startOffset + 1, sizeof(swapped64));
 767         d = CFConvertFloat64SwappedToHost(swapped64);
 768         *plist = CFDateCreate(allocator, d);
 769         if (objects) CFDictionarySetValue(objects, (const void *)(intptr_t)startOffset, *plist);
 770         return (*plist) ? true : false;
 771         }
 772     case kCFBinaryPlistMarkerData:
 773         cnt = marker & 0x0f;
 774         bytesptr = databytes + startOffset + 1;
 775         if (0xf == cnt) {
 776             if (!_readInt(bytesptr, &bigint, &bytesptr)) return false;
 777             if (INT_MAX < bigint) return false;
 778             cnt = (CFIndex)bigint;
 779         }
 780         if (mutabilityOption == kCFPropertyListMutableContainersAndLeaves) {
 781             *plist = CFDataCreateMutable(allocator, 0);
 782             CFDataAppendBytes((CFMutableDataRef)*plist, bytesptr, cnt);
 783         } else {
 784             *plist = CFDataCreate(allocator, bytesptr, cnt);
 785         }
 786         if (objects) CFDictionarySetValue(objects, (const void *)(intptr_t)startOffset, *plist);
 787         return (*plist) ? true : false;
 788     case kCFBinaryPlistMarkerASCIIString:
 789         cnt = marker & 0x0f;
 790         bytesptr = databytes + startOffset + 1;
 791         if (0xf == cnt) {
 792             if (!_readInt(bytesptr, &bigint, &bytesptr)) return false;
 793             if (INT_MAX < bigint) return false;
 794             cnt = (CFIndex)bigint;
 795         }
 796         if (mutabilityOption == kCFPropertyListMutableContainersAndLeaves) {
 797             CFStringRef str = CFStringCreateWithBytes(allocator, bytesptr, cnt, kCFStringEncodingASCII, false);
 798             *plist = CFStringCreateMutableCopy(allocator, 0, str);
 799             CFRelease(str);
 800         } else {
 801             *plist = CFStringCreateWithBytes(allocator, bytesptr, cnt, kCFStringEncodingASCII, false);
 802         }
 803         if (objects) CFDictionarySetValue(objects, (const void *)(intptr_t)startOffset, *plist);
 804         return (*plist) ? true : false;
 805     case kCFBinaryPlistMarkerUnicode16String:
 806         cnt = marker & 0x0f;
 807         bytesptr = databytes + startOffset + 1;
 808         if (0xf == cnt) {
 809             if (!_readInt(bytesptr, &bigint, &bytesptr)) return false;
 810             if (INT_MAX < bigint) return false;
 811             cnt = (CFIndex)bigint;
 812         }
 813         chars = CFAllocatorAllocate(allocator, cnt * sizeof(UniChar), 0);
 814         memmove(chars, bytesptr, cnt * sizeof(UniChar));
 815         for (idx = 0; idx < cnt; idx++) {
 816             chars[idx] = CFSwapInt16BigToHost(chars[idx]);
 817         }
 818         if (mutabilityOption == kCFPropertyListMutableContainersAndLeaves) {
 819             CFStringRef str = CFStringCreateWithCharactersNoCopy(allocator, chars, cnt, allocator);
 820             *plist = CFStringCreateMutableCopy(allocator, 0, str);
 821             CFRelease(str);
 822         } else {
 823             *plist = CFStringCreateWithCharactersNoCopy(allocator, chars, cnt, allocator);
 824         }
 825         if (objects) CFDictionarySetValue(objects, (const void *)(intptr_t)startOffset, *plist);
 826         return (*plist) ? true : false;
 827     case kCFBinaryPlistMarkerUID:
 828         cnt = (marker & 0x0f) + 1;
 829         bytesptr = databytes + startOffset + 1;
 830         bigint = 0;
 831         for (idx = 0; idx < cnt; idx++) {
 832             bigint = (bigint << 8) + *bytesptr++;
 833         }
 834         if (UINT_MAX < bigint) return false;
 835         *plist = _CFKeyedArchiverUIDCreate(allocator, (uint32_t)bigint);
 836         if (objects) CFDictionarySetValue(objects, (const void *)(intptr_t)startOffset, *plist);
 837         return (*plist) ? true : false;
 838     case kCFBinaryPlistMarkerArray:
 839         cnt = marker & 0x0f;
 840         bytesptr = databytes + startOffset + 1;
 841         if (0xf == cnt) {
 842             if (!_readInt(bytesptr, &bigint, &bytesptr)) return false;
 843             if (INT_MAX < bigint) return false;
 844             cnt = (CFIndex)bigint;
 845         }
 846         list = (cnt <= 256) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, sizeof(CFPropertyListRef) * cnt, 0);
 847         listAllocator = (list == buffer ? kCFAllocatorNull : kCFAllocatorSystemDefault);
 848         for (idx = 0; idx < cnt; idx++) {
 849             CFPropertyListRef pl;
 850             off = _getOffsetOfRefAt(databytes, bytesptr, trailer);
 851             if (datalen <= off) return false;
 852             if (!__CFBinaryPlistCreateObject(databytes, datalen, off, trailer, allocator, mutabilityOption, objects, &pl)) {
 853                 if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 854                     while (idx--) {
 855                         CFRelease(list[idx]);
 856                     }
 857                 }
 858                 if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 859                 return false;
 860             }
 861             if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 862                 CF_WRITE_BARRIER_BASE_ASSIGN(listAllocator, list, list[idx], CFMakeCollectable(pl));
 863             } else {
 864                 list[idx] = pl;
 865             }
 866             bytesptr += trailer->_objectRefSize;
 867         }
 868         *plist = _CFArrayCreate_ex(allocator, (mutabilityOption != kCFPropertyListImmutable), list, cnt);
 869         if (objects) CFDictionarySetValue(objects, (const void *)(intptr_t)startOffset, *plist);
 870         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 871         return (*plist) ? true : false;
 872     case kCFBinaryPlistMarkerDict:
 873         cnt = marker & 0x0f;
 874         bytesptr = databytes + startOffset + 1;
 875         if (0xf == cnt) {
 876             if (!_readInt(bytesptr, &bigint, &bytesptr)) return false;
 877             if (INT_MAX < bigint) return false;
 878             cnt = (CFIndex)bigint;
 879         }
 880         cnt *= 2;
 881         list = (cnt <= 256) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, sizeof(CFPropertyListRef) * cnt, 0);
 882         listAllocator = (list == buffer ? kCFAllocatorNull : kCFAllocatorSystemDefault);
 883         for (idx = 0; idx < cnt; idx++) {
 884             CFPropertyListRef pl;
 885             off = _getOffsetOfRefAt(databytes, bytesptr, trailer);
 886             if (datalen <= off) return false;
 887             if (!__CFBinaryPlistCreateObject(databytes, datalen, off, trailer, allocator, mutabilityOption, objects, &pl)) {
 888                 if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 889                     while (idx--) {
 890                         CFRelease(list[idx]);
 891                     }
 892                 }
 893                 if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 894                 return false;
 895             }
 896             if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 897                 CF_WRITE_BARRIER_BASE_ASSIGN(listAllocator, list, list[idx], CFMakeCollectable(pl));
 898             } else {
 899                 list[idx] = pl;
 900             }
 901             bytesptr += trailer->_objectRefSize;
 902         }
 903         *plist = _CFDictionaryCreate_ex(allocator, (mutabilityOption != kCFPropertyListImmutable), list, list + cnt / 2, cnt / 2);
 904         if (objects) CFDictionarySetValue(objects, (const void *)(intptr_t)startOffset, *plist);
 905         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list);
 906         return (*plist) ? true : false;
 907     }
 908     return false;
 909 }
 910
 911 __private_extern__ bool __CFTryParseBinaryPlist(CFAllocatorRef allocator, CFDataRef data, CFOptionFlags option, CFPropertyListRef *plist, CFStringRef *errorString) {
 912     uint8_t marker;
 913     CFBinaryPlistTrailer trailer;
 914     uint64_t offset;
 915     CFPropertyListRef pl;
 916     const uint8_t *databytes = CFDataGetBytePtr(data);
 917     uint64_t datalen = CFDataGetLength(data);
 918
 919     if (8 <= datalen && __CFBinaryPlistGetTopLevelInfo(databytes, datalen, &marker, &offset, &trailer)) {
 920         if (__CFBinaryPlistCreateObject(databytes, datalen, offset, &trailer, allocator, option, NULL, &pl)) {
 921             if (plist) *plist = pl;
 922         } else {
 923             if (plist) *plist = NULL;
 924             if (errorString) *errorString = CFRetain(CFSTR("binary data is corrupt"));
 925         }
 926         return true;
 927     }
 928     return false;
 929 }
 930