1/*
2 * Copyright (c) 2014 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/*	CFUUID.c
25	Copyright (c) 1999-2013, Apple Inc.  All rights reserved.
26	Responsibility: David Smith
27*/
28
29#include <CoreFoundation/CFUUID.h>
30#include "CFInternal.h"
31
32#if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_WINDOWS
33#include <dispatch/dispatch.h>
34
35static CFMutableDictionaryRef _uniquedUUIDs = NULL;
36CF_INLINE void LOCKED(dispatch_block_t work) {
37    static dispatch_once_t guard;
38    static dispatch_queue_t CFUUIDGlobalDataLock;
39    dispatch_once(&guard, ^{ CFUUIDGlobalDataLock = dispatch_queue_create("CFUUID global uniquing table lock", 0); });
40    dispatch_sync(CFUUIDGlobalDataLock, work);
41}
42
43#else
44// Platforms without dispatch
45
46static CFMutableDictionaryRef _uniquedUUIDs = NULL;
47static CFSpinLock_t _uniquedUUIDsLock = CFSpinLockInit;
48
49CF_INLINE void LOCKED(void (^work)(void)) {
50    __CFSpinLock(&_uniquedUUIDsLock);
51    work();
52    __CFSpinUnlock(&_uniquedUUIDsLock);
53}
54
55#endif
56
57struct __CFUUID {
58    CFRuntimeBase _base;
59    CFUUIDBytes _bytes;
60};
61
62typedef struct __CFUUID __CFUUID_t;
63
64static Boolean __CFisEqualUUIDBytes(const void *ptr1, const void *ptr2) {
65    CFUUIDBytes *p1 = (CFUUIDBytes *)ptr1;
66    CFUUIDBytes *p2 = (CFUUIDBytes *)ptr2;
67
68    return (((p1->byte0 == p2->byte0) && (p1->byte1 == p2->byte1) && (p1->byte2 == p2->byte2) && (p1->byte3 == p2->byte3) && (p1->byte4 == p2->byte4) && (p1->byte5 == p2->byte5) && (p1->byte6 == p2->byte6) && (p1->byte7 == p2->byte7) && (p1->byte8 == p2->byte8) && (p1->byte9 == p2->byte9) && (p1->byte10 == p2->byte10) && (p1->byte11 == p2->byte11) && (p1->byte12 == p2->byte12) && (p1->byte13 == p2->byte13) && (p1->byte14 == p2->byte14) && (p1->byte15 == p2->byte15)) ? true : false);
69}
70
71static CFHashCode __CFhashUUIDBytes(const void *ptr) {
72    return CFHashBytes((uint8_t *)ptr, 16);
73}
74
75/*
76 * GC implementation of a weak set specifically designed for UUID
77 */
78
79#define MALLOC(x) CFAllocatorAllocate(kCFAllocatorSystemDefault, x, 0)
80#define FREE(x) CFAllocatorDeallocate(kCFAllocatorSystemDefault, x)
81#define HASH(x) CFHashBytes((uint8_t *)x, 16)
82
83#define READWEAK(location) objc_read_weak((id *)location)
84#define WRITEWEAK(location, value) objc_assign_weak((id)value, (id *)location)
85
86typedef struct {
87    unsigned long count, size;
88    __CFUUID_t **weakPtrs;
89} _UUIDWeakSet_t;
90
91static _UUIDWeakSet_t _UUIDWeakSet;
92
93static void grow_has_lock(void);
94
95// enter if not already present
96static void enter_has_lock(__CFUUID_t *candidate) {
97    if (!candidate) return;
98    _UUIDWeakSet_t *table = &_UUIDWeakSet;
99    if (!table->size) grow_has_lock();
100    unsigned long int hashValue = HASH(&candidate->_bytes) & (table->size-1);
101    __CFUUID_t *result = table->weakPtrs[hashValue];
102    while (1) {
103        if (result == (void *)0x1 || result == NULL) {
104            table->weakPtrs[hashValue] = NULL;  // so that we don't try to unregister 0x1
105            WRITEWEAK(&table->weakPtrs[hashValue], (void *)candidate);
106            ++table->count;
107            break;
108        }
109        if (result) result = (__CFUUID_t *)READWEAK(&table->weakPtrs[hashValue]);
110        if (result) {
111            // see if it is equal to candidate
112            if (__CFisEqualUUIDBytes(&result->_bytes, &candidate->_bytes)) {
113                // keep first one.  There is a race if two threads both fail to find
114                // a candidate uuid then both try decide to create and enter one.
115                // Under non-GC one of them simply leaks.
116                break;
117            }
118        } else {
119            // was zeroed by collector.  Use this slot.
120            continue;
121        }
122        // move on
123        if (++hashValue >= table->size) hashValue = 0;
124        result = table->weakPtrs[hashValue];
125    }
126}
127
128static void *find_has_lock(const CFUUIDBytes *bytes) {
129    if (!bytes) return NULL;
130    _UUIDWeakSet_t *table = &_UUIDWeakSet;
131    if (!table->size) return NULL;  // no entries
132    unsigned long int hashValue = HASH(bytes) & (table->size-1);
133    __CFUUID_t *result = table->weakPtrs[hashValue];
134    while (1) {
135        if (result == (void *)0x1) break;
136        if (result) result = (__CFUUID_t *)READWEAK(&table->weakPtrs[hashValue]);
137        if (result) {
138            // see if it is equal to bytes
139            if (__CFisEqualUUIDBytes(&result->_bytes, bytes)) return result;
140        }
141        // move on
142        if (++hashValue >= table->size) hashValue = 0;
143        result = table->weakPtrs[hashValue];
144    }
145    return NULL;
146}
147
148
149static void grow_has_lock() {
150    _UUIDWeakSet_t *table = &_UUIDWeakSet;
151    if (table->size == 0) {
152        table->size = 16;
153        table->weakPtrs = (__CFUUID_t **)MALLOC(sizeof(__CFUUID_t *)*table->size);
154        for (int i = 0; i < table->size; ++i) table->weakPtrs[i] = (__CFUUID_t *)0x1;
155        table->count = 0;
156        return;
157    }
158    table->count = 0;
159    table->size = table->size*2;
160    __CFUUID_t **oldPtrs = table->weakPtrs;
161    table->weakPtrs = (__CFUUID_t **)MALLOC(sizeof(__CFUUID_t *)*table->size);
162    for (int i = 0; i < table->size; ++i) table->weakPtrs[i] = (__CFUUID_t *)0x1;
163    for (int i = 0; i < table->size / 2; ++i) {
164        if (oldPtrs[i] == (__CFUUID_t *)0x1) continue; // available field, ignore
165        if (oldPtrs[i] == NULL) continue;  // zero'ed by collector, ignore
166        enter_has_lock((__CFUUID_t *)READWEAK(&oldPtrs[i]));  // read, then enter (but enter must check for NULL)
167        WRITEWEAK(&oldPtrs[i], NULL);  // unregister
168    }
169    FREE(oldPtrs);
170}
171
172/***** end of weak set */
173
174static void __CFUUIDAddUniqueUUIDHasLock(CFUUIDRef uuid) {
175    CFDictionaryKeyCallBacks __CFUUIDBytesDictionaryKeyCallBacks = {0, NULL, NULL, NULL, __CFisEqualUUIDBytes, __CFhashUUIDBytes};
176    CFDictionaryValueCallBacks __CFnonRetainedUUIDDictionaryValueCallBacks = {0, NULL, NULL, CFCopyDescription, CFEqual};
177
178    if (kCFUseCollectableAllocator) {
179        enter_has_lock((__CFUUID_t *)uuid);
180        if (_UUIDWeakSet.count > (3 * _UUIDWeakSet.size / 4)) grow_has_lock();
181    } else {
182        if (!_uniquedUUIDs) _uniquedUUIDs = CFDictionaryCreateMutable(kCFAllocatorSystemDefault, 0, &__CFUUIDBytesDictionaryKeyCallBacks, &__CFnonRetainedUUIDDictionaryValueCallBacks);
183        CFDictionarySetValue(_uniquedUUIDs, &(uuid->_bytes), uuid);
184    }
185}
186
187static void __CFUUIDRemoveUniqueUUIDHasLock(CFUUIDRef uuid) {
188    if (_uniquedUUIDs) CFDictionaryRemoveValue(_uniquedUUIDs, &(uuid->_bytes));
189}
190
191static CFUUIDRef __CFUUIDGetUniquedUUIDHasLock(const CFUUIDBytes *bytes) {
192    CFUUIDRef uuid = NULL;
193    if (kCFUseCollectableAllocator) {
194        uuid = (CFUUIDRef)find_has_lock(bytes);
195    } else if (_uniquedUUIDs) {
196        uuid = (CFUUIDRef)CFDictionaryGetValue(_uniquedUUIDs, bytes);
197    }
198    return uuid;
199}
200
201static void __CFUUIDDeallocate(CFTypeRef cf) {
202    if (kCFUseCollectableAllocator) return;
203
204    __CFUUID_t *uuid = (__CFUUID_t *)cf;
205    LOCKED(^{
206    __CFUUIDRemoveUniqueUUIDHasLock(uuid);
207    });
208}
209
210static CFStringRef __CFUUIDCopyDescription(CFTypeRef cf) {
211    CFStringRef uuidStr = CFUUIDCreateString(CFGetAllocator(cf), (CFUUIDRef)cf);
212    CFStringRef desc = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<CFUUID %p> %@"), cf, uuidStr);
213    CFRelease(uuidStr);
214    return desc;
215}
216
217static CFStringRef __CFUUIDCopyFormattingDescription(CFTypeRef cf, CFDictionaryRef formatOptions) {
218    return CFUUIDCreateString(CFGetAllocator(cf), (CFUUIDRef)cf);
219}
220
221static CFTypeID __kCFUUIDTypeID = _kCFRuntimeNotATypeID;
222
223static const CFRuntimeClass __CFUUIDClass = {
224    0,
225    "CFUUID",
226    NULL,	// init
227    NULL,	// copy
228    __CFUUIDDeallocate,
229    NULL,	// equal
230    NULL,	// hash
231    __CFUUIDCopyFormattingDescription,
232    __CFUUIDCopyDescription
233};
234
235CF_PRIVATE void __CFUUIDInitialize(void) {
236    __kCFUUIDTypeID = _CFRuntimeRegisterClass(&__CFUUIDClass);
237}
238
239CFTypeID CFUUIDGetTypeID(void) {
240    return __kCFUUIDTypeID;
241}
242
243static CFUUIDRef __CFUUIDCreateWithBytesPrimitive(CFAllocatorRef allocator, CFUUIDBytes bytes, Boolean isConst) {
244    __block __CFUUID_t *uuid = NULL;
245    LOCKED(^{
246        uuid = (__CFUUID_t *)__CFUUIDGetUniquedUUIDHasLock(&bytes);
247        if (!uuid) {
248            size_t size;
249            size = sizeof(__CFUUID_t) - sizeof(CFRuntimeBase);
250            uuid = (__CFUUID_t *)_CFRuntimeCreateInstance(kCFUseCollectableAllocator ? kCFAllocatorSystemDefault : allocator, __kCFUUIDTypeID, size, NULL);
251
252            if (!uuid) return;
253
254            uuid->_bytes = bytes;
255            __CFUUIDAddUniqueUUIDHasLock(uuid);
256        } else if (!isConst) {
257            CFRetain(uuid);
258        }
259    });
260
261    return (CFUUIDRef)uuid;
262}
263
264#if DEPLOYMENT_TARGET_WINDOWS
265#include <Rpc.h>
266#elif DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED
267#include <uuid/uuid.h>
268#endif
269
270CFUUIDRef CFUUIDCreate(CFAllocatorRef alloc) {
271    /* Create a new bytes struct and then call the primitive. */
272    __block CFUUIDBytes bytes;
273    __block uint32_t retval = 0;
274
275    LOCKED(^{
276#if DEPLOYMENT_TARGET_WINDOWS
277        UUID u;
278        long rStatus = UuidCreate(&u);
279        if (RPC_S_OK != rStatus && RPC_S_UUID_LOCAL_ONLY != rStatus) retval = 1;
280        memmove(&bytes, &u, sizeof(bytes));
281#elif DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED
282        static Boolean useV1UUIDs = false, checked = false;
283        uuid_t uuid;
284        if (!checked) {
285            const char *value = __CFgetenv("CFUUIDVersionNumber");
286            if (value) {
287                if (1 == strtoul_l(value, NULL, 0, NULL)) useV1UUIDs = true;
288            }
289            checked = true;
290        }
291        if (useV1UUIDs) uuid_generate_time(uuid); else uuid_generate_random(uuid);
292        memcpy((void *)&bytes, uuid, sizeof(uuid));
293#else
294        retval = 1;
295#endif
296    });
297
298    return (retval == 0) ? __CFUUIDCreateWithBytesPrimitive(alloc, bytes, false) : NULL;
299}
300
301CFUUIDRef CFUUIDCreateWithBytes(CFAllocatorRef alloc, uint8_t byte0, uint8_t byte1, uint8_t byte2, uint8_t byte3, uint8_t byte4, uint8_t byte5, uint8_t byte6, uint8_t byte7, uint8_t byte8, uint8_t byte9, uint8_t byte10, uint8_t byte11, uint8_t byte12, uint8_t byte13, uint8_t byte14, uint8_t byte15) {
302    CFUUIDBytes bytes;
303    // CodeWarrior can't handle the structure assignment of bytes, so we must explode this - REW, 10/8/99
304    bytes.byte0 = byte0;
305    bytes.byte1 = byte1;
306    bytes.byte2 = byte2;
307    bytes.byte3 = byte3;
308    bytes.byte4 = byte4;
309    bytes.byte5 = byte5;
310    bytes.byte6 = byte6;
311    bytes.byte7 = byte7;
312    bytes.byte8 = byte8;
313    bytes.byte9 = byte9;
314    bytes.byte10 = byte10;
315    bytes.byte11 = byte11;
316    bytes.byte12 = byte12;
317    bytes.byte13 = byte13;
318    bytes.byte14 = byte14;
319    bytes.byte15 = byte15;
320
321    return __CFUUIDCreateWithBytesPrimitive(alloc, bytes, false);
322}
323
324static void _intToHexChars(UInt32 in, UniChar *out, int digits) {
325    int shift;
326    UInt32 d;
327
328    while (--digits >= 0) {
329        shift = digits << 2;
330        d = 0x0FL & (in >> shift);
331        if (d <= 9) {
332            *out++ = (UniChar)'0' + d;
333        } else {
334            *out++ = (UniChar)'A' + (d - 10);
335        }
336    }
337}
338
339static uint8_t _byteFromHexChars(UniChar *in) {
340    uint8_t result = 0;
341    UniChar c;
342    uint8_t d;
343    CFIndex i;
344
345    for (i=0; i<2; i++) {
346        c = in[i];
347        if ((c >= (UniChar)'0') && (c <= (UniChar)'9')) {
348            d = c - (UniChar)'0';
349        } else if ((c >= (UniChar)'a') && (c <= (UniChar)'f')) {
350            d = c - ((UniChar)'a' - 10);
351        } else if ((c >= (UniChar)'A') && (c <= (UniChar)'F')) {
352            d = c - ((UniChar)'A' - 10);
353        } else {
354            return 0;
355        }
356        result = (result << 4) | d;
357    }
358
359    return result;
360}
361
362CF_INLINE Boolean _isHexChar(UniChar c) {
363    return ((((c >= (UniChar)'0') && (c <= (UniChar)'9')) || ((c >= (UniChar)'a') && (c <= (UniChar)'f')) || ((c >= (UniChar)'A') && (c <= (UniChar)'F'))) ? true : false);
364}
365
366#define READ_A_BYTE(into) if (i+1 < len) { \
367    (into) = _byteFromHexChars(&(chars[i])); \
368        i+=2; \
369}
370
371CFUUIDRef CFUUIDCreateFromString(CFAllocatorRef alloc, CFStringRef uuidStr) {
372    /* Parse the string into a bytes struct and then call the primitive. */
373    CFUUIDBytes bytes;
374    UniChar chars[100];
375    CFIndex len;
376    CFIndex i = 0;
377
378    if (uuidStr == NULL) return NULL;
379
380    len = CFStringGetLength(uuidStr);
381    if (len > 100) {
382        len = 100;
383    } else if (len == 0) {
384        return NULL;
385    }
386    CFStringGetCharacters(uuidStr, CFRangeMake(0, len), chars);
387    memset((void *)&bytes, 0, sizeof(bytes));
388
389    /* Skip initial random stuff */
390    while (!_isHexChar(chars[i]) && i < len) i++;
391
392    READ_A_BYTE(bytes.byte0);
393    READ_A_BYTE(bytes.byte1);
394    READ_A_BYTE(bytes.byte2);
395    READ_A_BYTE(bytes.byte3);
396    i++;
397
398    READ_A_BYTE(bytes.byte4);
399    READ_A_BYTE(bytes.byte5);
400    i++;
401
402    READ_A_BYTE(bytes.byte6);
403    READ_A_BYTE(bytes.byte7);
404    i++;
405
406    READ_A_BYTE(bytes.byte8);
407    READ_A_BYTE(bytes.byte9);
408    i++;
409
410    READ_A_BYTE(bytes.byte10);
411    READ_A_BYTE(bytes.byte11);
412    READ_A_BYTE(bytes.byte12);
413    READ_A_BYTE(bytes.byte13);
414    READ_A_BYTE(bytes.byte14);
415    READ_A_BYTE(bytes.byte15);
416
417    return __CFUUIDCreateWithBytesPrimitive(alloc, bytes, false);
418}
419
420CFStringRef CFUUIDCreateString(CFAllocatorRef alloc, CFUUIDRef uuid) {
421    CFMutableStringRef str = CFStringCreateMutable(alloc, 0);
422    UniChar buff[12];
423
424    // First segment (4 bytes, 8 digits + 1 dash)
425    _intToHexChars(uuid->_bytes.byte0, buff, 2);
426    _intToHexChars(uuid->_bytes.byte1, &(buff[2]), 2);
427    _intToHexChars(uuid->_bytes.byte2, &(buff[4]), 2);
428    _intToHexChars(uuid->_bytes.byte3, &(buff[6]), 2);
429    buff[8] = (UniChar)'-';
430    CFStringAppendCharacters(str, buff, 9);
431
432    // Second segment (2 bytes, 4 digits + 1 dash)
433    _intToHexChars(uuid->_bytes.byte4, buff, 2);
434    _intToHexChars(uuid->_bytes.byte5, &(buff[2]), 2);
435    buff[4] = (UniChar)'-';
436    CFStringAppendCharacters(str, buff, 5);
437
438    // Third segment (2 bytes, 4 digits + 1 dash)
439    _intToHexChars(uuid->_bytes.byte6, buff, 2);
440    _intToHexChars(uuid->_bytes.byte7, &(buff[2]), 2);
441    buff[4] = (UniChar)'-';
442    CFStringAppendCharacters(str, buff, 5);
443
444    // Fourth segment (2 bytes, 4 digits + 1 dash)
445    _intToHexChars(uuid->_bytes.byte8, buff, 2);
446    _intToHexChars(uuid->_bytes.byte9, &(buff[2]), 2);
447    buff[4] = (UniChar)'-';
448    CFStringAppendCharacters(str, buff, 5);
449
450    // Fifth segment (6 bytes, 12 digits)
451    _intToHexChars(uuid->_bytes.byte10, buff, 2);
452    _intToHexChars(uuid->_bytes.byte11, &(buff[2]), 2);
453    _intToHexChars(uuid->_bytes.byte12, &(buff[4]), 2);
454    _intToHexChars(uuid->_bytes.byte13, &(buff[6]), 2);
455    _intToHexChars(uuid->_bytes.byte14, &(buff[8]), 2);
456    _intToHexChars(uuid->_bytes.byte15, &(buff[10]), 2);
457    CFStringAppendCharacters(str, buff, 12);
458
459    return str;
460}
461
462CFUUIDRef CFUUIDGetConstantUUIDWithBytes(CFAllocatorRef alloc, uint8_t byte0, uint8_t byte1, uint8_t byte2, uint8_t byte3, uint8_t byte4, uint8_t byte5, uint8_t byte6, uint8_t byte7, uint8_t byte8, uint8_t byte9, uint8_t byte10, uint8_t byte11, uint8_t byte12, uint8_t byte13, uint8_t byte14, uint8_t byte15) {
463    CFUUIDBytes bytes;
464    // CodeWarrior can't handle the structure assignment of bytes, so we must explode this - REW, 10/8/99
465    bytes.byte0 = byte0;
466    bytes.byte1 = byte1;
467    bytes.byte2 = byte2;
468    bytes.byte3 = byte3;
469    bytes.byte4 = byte4;
470    bytes.byte5 = byte5;
471    bytes.byte6 = byte6;
472    bytes.byte7 = byte7;
473    bytes.byte8 = byte8;
474    bytes.byte9 = byte9;
475    bytes.byte10 = byte10;
476    bytes.byte11 = byte11;
477    bytes.byte12 = byte12;
478    bytes.byte13 = byte13;
479    bytes.byte14 = byte14;
480    bytes.byte15 = byte15;
481
482    return __CFUUIDCreateWithBytesPrimitive(alloc, bytes, true);
483}
484
485CFUUIDBytes CFUUIDGetUUIDBytes(CFUUIDRef uuid) {
486    return uuid->_bytes;
487}
488
489CF_EXPORT CFUUIDRef CFUUIDCreateFromUUIDBytes(CFAllocatorRef alloc, CFUUIDBytes bytes) {
490    return __CFUUIDCreateWithBytesPrimitive(alloc, bytes, false);
491}
492
493#undef READ_A_BYTE
494
495