1/*
2 * Created by Michael Brouwer on 2/14/12.
3 * Copyright 2012 Apple Inc. All Rights Reserved.
4 */
5
6/*
7 * SOSTransport.c -  Implementation of the secure object syncing transport
8 */
9
10#include <SecureObjectSync/SOSTransport.h>
11#include <utilities/SecCFError.h>
12#include <utilities/SecCFWrappers.h>
13#include <dispatch/dispatch.h>
14#include <stdlib.h>
15
16static CFStringRef sErrorDomain = CFSTR("com.apple.security.sos.transport.error");
17
18/* SOSDigestVector code. */
19
20#define VECTOR_GROW(vector, count, capacity) \
21    do { \
22    if ((count) > capacity) { \
23        capacity = ((capacity) + 16) * 3 / 2; \
24        if (capacity < (count)) \
25            capacity = (count); \
26        vector = realloc((vector), sizeof(*(vector)) * capacity); \
27    } \
28} while (0)
29
30static void SOSDigestVectorEnsureCapacity(struct SOSDigestVector *dv, size_t count) {
31	VECTOR_GROW(dv->digest, count, dv->capacity);
32}
33
34void SOSDigestVectorReplaceAtIndex(struct SOSDigestVector *dv, size_t ix, const uint8_t *digest)
35{
36	SOSDigestVectorEnsureCapacity(dv, ix + 1);
37	memcpy(dv->digest[ix], digest, SOSDigestSize);
38	dv->is_sorted = false;
39}
40
41static void SOSDigestVectorAppendOrdered(struct SOSDigestVector *dv, const uint8_t *digest)
42{
43	SOSDigestVectorEnsureCapacity(dv, dv->count + 1);
44	memcpy(dv->digest[dv->count++], digest, SOSDigestSize);
45}
46
47void SOSDigestVectorAppend(struct SOSDigestVector *dv, const uint8_t *digest)
48{
49    SOSDigestVectorAppendOrdered(dv, digest);
50	dv->is_sorted = false;
51}
52
53static int SOSDigestCompare(const void *a, const void *b)
54{
55	return memcmp(a, b, SOSDigestSize);
56}
57
58void SOSDigestVectorSort(struct SOSDigestVector *dv)
59{
60	qsort(dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
61	dv->is_sorted = true;
62}
63
64bool SOSDigestVectorContains(struct SOSDigestVector *dv, const uint8_t *digest)
65{
66    return SOSDigestVectorIndexOf(dv, digest) != (size_t)-1;
67}
68
69size_t SOSDigestVectorIndexOf(struct SOSDigestVector *dv, const uint8_t *digest)
70{
71	if (!dv->is_sorted)
72		SOSDigestVectorSort(dv);
73    const void *pos = bsearch(digest, dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
74    return pos ? ((size_t)(pos - (void *)dv->digest)) / SOSDigestSize : ((size_t)-1);
75}
76
77void SOSDigestVectorFree(struct SOSDigestVector *dv)
78{
79	free(dv->digest);
80	dv->digest = NULL;
81	dv->count = 0;
82	dv->capacity = 0;
83	dv->is_sorted = false;
84}
85
86void SOSDigestVectorApply(struct SOSDigestVector *dv,
87                          void *context, SOSDigestVectorApplyFunc func)
88{
89	if (!dv->is_sorted)
90		SOSDigestVectorSort(dv);
91
92	for (size_t ix = 0; ix < dv->count; ++ix) {
93		func(context, dv->digest[ix]);
94	}
95}
96
97static void SOSDigestVectorAppendMultiple(struct SOSDigestVector *dv,
98                                          size_t count, const uint8_t *digests) {
99    if (count) {
100        SOSDigestVectorEnsureCapacity(dv, dv->count + count);
101        memcpy(dv->digest[dv->count], digests, count * SOSDigestSize);
102        dv->count += count;
103    }
104}
105
106void SOSDigestVectorDiff(struct SOSDigestVector *dv1, struct SOSDigestVector *dv2,
107                         struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
108{
109    /* dv1_2 and dv2_1 should be empty to start. */
110    assert(dv1_2->count == 0);
111    assert(dv2_1->count == 0);
112
113	if (!dv1->is_sorted)
114		SOSDigestVectorSort(dv1);
115	if (!dv2->is_sorted)
116		SOSDigestVectorSort(dv2);
117
118    size_t i1 = 0, i2 = 0;
119    while (i1 < dv1->count && i2 < dv2->count) {
120        int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
121        if (delta == 0) {
122            ++i1, ++i2;
123        } else if (delta < 0) {
124            SOSDigestVectorAppendOrdered(dv1_2, dv1->digest[i1++]);
125        } else {
126            SOSDigestVectorAppendOrdered(dv2_1, dv2->digest[i2++]);
127        }
128    }
129    SOSDigestVectorAppendMultiple(dv1_2, dv1->count - i1, dv1->digest[i1]);
130    SOSDigestVectorAppendMultiple(dv2_1, dv2->count - i2, dv2->digest[i2]);
131
132    dv1_2->is_sorted = true;
133    dv2_1->is_sorted = true;
134}
135
136bool SOSDigestVectorPatch(struct SOSDigestVector *base, struct SOSDigestVector *removals,
137                          struct SOSDigestVector *additions, struct SOSDigestVector *dv,
138                          CFErrorRef *error)
139{
140    size_t base_ix = 0, removals_ix = 0, additions_ix = 0;
141	if (!base->is_sorted)
142		SOSDigestVectorSort(base);
143	if (!removals->is_sorted)
144		SOSDigestVectorSort(removals);
145	if (!additions->is_sorted)
146		SOSDigestVectorSort(additions);
147
148    assert(dv->count == 0);
149    SOSDigestVectorEnsureCapacity(dv, base->count - removals->count + additions->count);
150    dv->is_sorted = true;
151
152    while (base_ix < base->count) {
153        const uint8_t *d = base->digest[base_ix];
154        if (additions_ix < additions->count && SOSDigestCompare(d, additions->digest[additions_ix]) > 0) {
155            SOSDigestVectorAppendOrdered(dv, additions->digest[additions_ix++]);
156        } else if (removals_ix < removals->count && SOSDigestCompare(d, removals->digest[removals_ix]) == 0) {
157            base_ix++;
158            removals_ix++;
159        } else {
160            SOSDigestVectorAppendOrdered(dv, base->digest[base_ix++]);
161        }
162    }
163
164    if (removals_ix != removals->count) {
165        SecCFCreateErrorWithFormat(1, sErrorDomain, NULL, error, NULL, CFSTR("%lu extra removals left"), removals->count - removals_ix);
166        goto errOut;
167    }
168
169    while (additions_ix < additions->count) {
170        if (dv->count > 0 && SOSDigestCompare(dv->digest[dv->count - 1], additions->digest[additions_ix]) >= 0) {
171            SecCFCreateErrorWithFormat(1, sErrorDomain, NULL, error, NULL, CFSTR("unordered addition (%lu left)"), additions->count - additions_ix);
172            goto errOut;
173        }
174        SOSDigestVectorAppendOrdered(dv, additions->digest[additions_ix++]);
175    }
176
177    return true;
178errOut:
179    return false;
180}
181
182
183
184/* SOSManifest implementation. */
185struct __OpaqueSOSManifest {
186};
187
188SOSManifestRef SOSManifestCreateWithBytes(const uint8_t *bytes, size_t len,
189                                          CFErrorRef *error) {
190    SOSManifestRef manifest = (SOSManifestRef)CFDataCreate(NULL, bytes, (CFIndex)len);
191    if (!manifest)
192        SecCFCreateErrorWithFormat(kSOSManifestCreateError, sErrorDomain, NULL, error, NULL, CFSTR("Failed to create manifest"));
193
194    return manifest;
195}
196
197SOSManifestRef SOSManifestCreateWithData(CFDataRef data, CFErrorRef *error)
198{
199    SOSManifestRef manifest = NULL;
200
201    if (data)
202        manifest = (SOSManifestRef)CFDataCreateCopy(kCFAllocatorDefault, data);
203    else
204        manifest = (SOSManifestRef)CFDataCreate(kCFAllocatorDefault, NULL, 0);
205
206    if (!manifest)
207        SecCFCreateErrorWithFormat(kSOSManifestCreateError, sErrorDomain, NULL, error, NULL, CFSTR("Failed to create manifest"));
208
209    return manifest;
210}
211
212void SOSManifestDispose(SOSManifestRef m) {
213    CFRelease(m);
214}
215
216size_t SOSManifestGetSize(SOSManifestRef m) {
217    return (size_t)CFDataGetLength((CFDataRef)m);
218}
219
220size_t SOSManifestGetCount(SOSManifestRef m) {
221    return SOSManifestGetSize(m) / SOSDigestSize;
222}
223
224const uint8_t *SOSManifestGetBytePtr(SOSManifestRef m) {
225    return CFDataGetBytePtr((CFDataRef)m);
226}
227
228CFDataRef SOSManifestGetData(SOSManifestRef m) {
229    return (CFDataRef)m;
230}
231
232
233bool SOSManifestDiff(SOSManifestRef a, SOSManifestRef b,
234                     SOSManifestRef *a_minus_b, SOSManifestRef *b_minus_a,
235                     CFErrorRef *error) {
236    bool result = true;
237    struct SOSDigestVector dva = SOSDigestVectorInit,
238                           dvb = SOSDigestVectorInit,
239                           dvab = SOSDigestVectorInit,
240                           dvba = SOSDigestVectorInit;
241    SOSDigestVectorAppendMultiple(&dva, SOSManifestGetCount(a), SOSManifestGetBytePtr(a));
242    SOSDigestVectorAppendMultiple(&dvb, SOSManifestGetCount(b), SOSManifestGetBytePtr(b));
243    SOSDigestVectorDiff(&dva, &dvb, &dvab, &dvba);
244    SOSDigestVectorFree(&dva);
245    SOSDigestVectorFree(&dvb);
246
247    if (a_minus_b) {
248        *a_minus_b = SOSManifestCreateWithBytes((const uint8_t *)dvab.digest, dvab.count * SOSDigestSize, error);
249        if (!*a_minus_b)
250            result = false;
251    }
252
253    if (b_minus_a) {
254        *b_minus_a = SOSManifestCreateWithBytes((const uint8_t *)dvba.digest, dvba.count * SOSDigestSize, error);
255        if (!*b_minus_a)
256            result = false;
257    }
258
259    SOSDigestVectorFree(&dvab);
260    SOSDigestVectorFree(&dvba);
261
262    return result;
263}
264
265SOSManifestRef SOSManifestCreateWithPatch(SOSManifestRef base,
266                                          SOSManifestRef removals,
267                                          SOSManifestRef additions,
268                                          CFErrorRef *error) {
269    struct SOSDigestVector dvbase = SOSDigestVectorInit,
270                           dvresult = SOSDigestVectorInit,
271                           dvremovals = SOSDigestVectorInit,
272                           dvadditions = SOSDigestVectorInit;
273    dvbase.is_sorted = dvresult.is_sorted = dvremovals.is_sorted = dvadditions.is_sorted = true;
274    SOSDigestVectorAppendMultiple(&dvbase, SOSManifestGetCount(base), SOSManifestGetBytePtr(base));
275    SOSDigestVectorAppendMultiple(&dvremovals, SOSManifestGetCount(removals), SOSManifestGetBytePtr(removals));
276    SOSDigestVectorAppendMultiple(&dvadditions, SOSManifestGetCount(additions), SOSManifestGetBytePtr(additions));
277    SOSManifestRef result;
278    if (SOSDigestVectorPatch(&dvbase, &dvremovals, &dvadditions, &dvresult, error)) {
279        result = SOSManifestCreateWithBytes((const uint8_t *)dvresult.digest, dvresult.count * SOSDigestSize, error);
280    } else {
281        result = NULL;
282    }
283    SOSDigestVectorFree(&dvbase);
284    SOSDigestVectorFree(&dvresult);
285    SOSDigestVectorFree(&dvremovals);
286    SOSDigestVectorFree(&dvadditions);
287    return result;
288}
289
290void SOSManifestForEach(SOSManifestRef m, void(^block)(CFDataRef e)) {
291    CFDataRef e;
292    const uint8_t *p, *q;
293    for (p = SOSManifestGetBytePtr(m), q = p + SOSManifestGetSize(m);
294         p + SOSDigestSize <= q; p += SOSDigestSize) {
295        e = CFDataCreateWithBytesNoCopy(0, p, SOSDigestSize, kCFAllocatorNull);
296        if (e) {
297            block(e);
298            CFRelease(e);
299        }
300    }
301}
302
303CFStringRef SOSManifestCopyDescription(SOSManifestRef m) {
304    CFMutableStringRef desc = CFStringCreateMutable(0, 0);
305    CFStringAppend(desc, CFSTR("<Manifest"));
306    SOSManifestForEach(m, ^(CFDataRef e) {
307        CFStringAppend(desc, CFSTR(" "));
308        const uint8_t *d = CFDataGetBytePtr(e);
309        CFStringAppendFormat(desc, 0, CFSTR("%02X%02X%02X%02X"), d[0], d[1], d[2], d[3]);
310    });
311    CFStringAppend(desc, CFSTR(">"));
312
313    return desc;
314}
315
316#if 0
317SOSObjectRef SOSManifestGetObject(SOSManifestRef m, SOSObjectID k) {
318    return NULL;
319}
320
321void SOSManifestPutObject(SOSManifestRef m, SOSObjectID k, SOSObjectRef v) {
322
323}
324
325
326SOSManifestRef SOSManifestCreateSparse(void *get_ctx, SOSManifestGetF get_f) {
327    return NULL;
328}
329#endif
330