1/*
2 * Copyright (c) 2013-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
25#include <SecureObjectSync/SOSDigestVector.h>
26#include <utilities/SecCFError.h>
27#include <utilities/SecCFWrappers.h>
28#include <utilities/comparison.h>
29#include <dispatch/dispatch.h>
30#include <stdlib.h>
31
32CFStringRef kSOSDigestVectorErrorDomain = CFSTR("com.apple.security.sos.digestvector.error");
33
34/* SOSDigestVector code. */
35
36#define VECTOR_GROW(vector, count, capacity) \
37do { \
38    if ((count) > capacity) { \
39        capacity = ((capacity) + 16) * 3 / 2; \
40        if (capacity < (count)) \
41            capacity = (count); \
42        vector = reallocf((vector), sizeof(*(vector)) * capacity); \
43    } \
44} while (0)
45
46static void SOSDigestVectorEnsureCapacity(struct SOSDigestVector *dv, size_t count) {
47	VECTOR_GROW(dv->digest, count, dv->capacity);
48}
49
50void SOSDigestVectorReplaceAtIndex(struct SOSDigestVector *dv, size_t ix, const uint8_t *digest)
51{
52	SOSDigestVectorEnsureCapacity(dv, ix + 1);
53	memcpy(dv->digest[ix], digest, SOSDigestSize);
54	dv->unsorted = true;
55}
56
57static void SOSDigestVectorAppendOrdered(struct SOSDigestVector *dv, const uint8_t *digest)
58{
59	SOSDigestVectorEnsureCapacity(dv, dv->count + 1);
60	memcpy(dv->digest[dv->count++], digest, SOSDigestSize);
61}
62
63void SOSDigestVectorAppend(struct SOSDigestVector *dv, const uint8_t *digest)
64{
65    SOSDigestVectorAppendOrdered(dv, digest);
66	dv->unsorted = true;
67}
68
69static int SOSDigestCompare(const void *a, const void *b)
70{
71	return memcmp(a, b, SOSDigestSize);
72}
73
74void SOSDigestVectorSort(struct SOSDigestVector *dv)
75{
76    if (dv->unsorted) {
77        qsort(dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
78        dv->unsorted = false;
79    }
80}
81
82void SOSDigestVectorUniqueSorted(struct SOSDigestVector *dv)
83{
84	// Uniqify in place
85    // TODO: This is really inefficient because of all the memcpys
86    if (dv->unsorted)
87		SOSDigestVectorSort(dv);
88
89    int idx = 0, odx = 1;
90    uint8_t *prevDigest = dv->digest[0];
91    for (idx = 1; idx < (int)dv->count; idx++)
92    {
93        if (SOSDigestCompare(prevDigest, dv->digest[idx])) {  // this element is not the same as previous one
94            SOSDigestVectorReplaceAtIndex(dv, odx, dv->digest[idx]);
95            prevDigest = dv->digest[odx];
96            ++odx;
97        }
98    }
99    dv->count = odx;
100}
101
102void SOSDigestVectorSwap(struct SOSDigestVector *dva, struct SOSDigestVector *dvb)
103{
104    struct SOSDigestVector dv;
105      dv = *dva;
106    *dva = *dvb;
107    *dvb = dv;
108}
109
110bool SOSDigestVectorContainsSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
111{
112    return SOSDigestVectorIndexOfSorted(dv, digest) != (size_t)-1;
113}
114
115bool SOSDigestVectorContains(struct SOSDigestVector *dv, const uint8_t *digest)
116{
117    if (dv->unsorted)
118		SOSDigestVectorSort(dv);
119    return SOSDigestVectorContainsSorted(dv, digest);
120}
121
122size_t SOSDigestVectorIndexOfSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
123{
124    const void *pos = bsearch(digest, dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
125    return pos ? ((size_t)(pos - (void *)dv->digest)) / SOSDigestSize : ((size_t)-1);
126}
127
128size_t SOSDigestVectorIndexOf(struct SOSDigestVector *dv, const uint8_t *digest)
129{
130	if (dv->unsorted)
131		SOSDigestVectorSort(dv);
132    return SOSDigestVectorIndexOfSorted(dv, digest);
133}
134
135void SOSDigestVectorFree(struct SOSDigestVector *dv)
136{
137	free(dv->digest);
138	dv->digest = NULL;
139	dv->count = 0;
140	dv->capacity = 0;
141	dv->unsorted = false;
142}
143
144void SOSDigestVectorApplySorted(const struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
145{
146    bool stop = false;
147	for (size_t ix = 0; !stop && ix < dv->count; ++ix) {
148        with(dv->digest[ix], &stop);
149	}
150}
151
152void SOSDigestVectorApply(struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
153{
154	if (dv->unsorted)
155		SOSDigestVectorSort(dv);
156    SOSDigestVectorApplySorted(dv, with);
157}
158
159// TODO: Check for NDEBUG to disable skip dupes are release time.
160//#define SOSDVSKIPDUPES  0
161#define SOSDVSKIPDUPES  1
162
163#if SOSDVSKIPDUPES
164#define SOSDVINCRIX(dv,ix) (SOSDigestVectorIncrementAndSkipDupes(dv,ix))
165#else
166#define SOSDVINCRIX(dv,ix) (ix + 1)
167#endif
168
169static size_t SOSDigestVectorIncrementAndSkipDupes(const struct SOSDigestVector *dv, const size_t ix) {
170    size_t new_ix = ix;
171    if (new_ix < dv->count) {
172        while (++new_ix < dv->count) {
173            int delta = SOSDigestCompare(dv->digest[ix], dv->digest[new_ix]);
174            assert(delta <= 0);
175            if (delta != 0)
176                break;
177        }
178    }
179    return new_ix;
180}
181
182void SOSDigestVectorAppendMultipleOrdered(struct SOSDigestVector *dv,
183                                   size_t count, const uint8_t *digests) {
184#if SOSDVSKIPDUPES
185    size_t ix = 0;
186    while (ix < count) {
187        SOSDigestVectorAppendOrdered(dv, digests + (ix * SOSDigestSize));
188        ix = SOSDVINCRIX(dv, ix);
189    }
190#else
191    if (count) {
192        SOSDigestVectorEnsureCapacity(dv, dv->count + count);
193        memcpy(dv->digest[dv->count], digests, count * SOSDigestSize);
194        dv->count += count;
195    }
196#endif
197}
198
199void SOSDigestVectorIntersectSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
200                                    struct SOSDigestVector *dvintersect)
201{
202    /* dvintersect should be empty to start. */
203    assert(dvintersect->count == 0);
204    size_t i1 = 0, i2 = 0;
205    while (i1 < dv1->count && i2 < dv2->count) {
206        int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
207        if (delta == 0) {
208            SOSDigestVectorAppendOrdered(dvintersect, dv1->digest[i1]);
209            i1 = SOSDVINCRIX(dv1, i1);
210            i2 = SOSDVINCRIX(dv2, i2);
211        } else if (delta < 0) {
212            i1 = SOSDVINCRIX(dv1, i1);
213        } else {
214            i2 = SOSDVINCRIX(dv2, i2);
215        }
216    }
217}
218
219void SOSDigestVectorUnionSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
220                                struct SOSDigestVector *dvunion)
221{
222    /* dvunion should be empty to start. */
223    assert(dvunion->count == 0);
224    size_t i1 = 0, i2 = 0;
225    while (i1 < dv1->count && i2 < dv2->count) {
226        int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
227        if (delta == 0) {
228            SOSDigestVectorAppendOrdered(dvunion, dv1->digest[i1]);
229            i1 = SOSDVINCRIX(dv1, i1);
230            i2 = SOSDVINCRIX(dv2, i2);
231        } else if (delta < 0) {
232            SOSDigestVectorAppendOrdered(dvunion, dv1->digest[i1]);
233            i1 = SOSDVINCRIX(dv1, i1);
234        } else {
235            SOSDigestVectorAppendOrdered(dvunion, dv2->digest[i2]);
236            i2 = SOSDVINCRIX(dv2, i2);
237        }
238    }
239    SOSDigestVectorAppendMultipleOrdered(dvunion, dv1->count - i1, dv1->digest[i1]);
240    SOSDigestVectorAppendMultipleOrdered(dvunion, dv2->count - i2, dv2->digest[i2]);
241}
242
243void SOSDigestVectorDiffSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
244                               struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
245{
246    /* dv1_2 and dv2_1 should be empty to start. */
247    assert(dv1_2->count == 0);
248    assert(dv2_1->count == 0);
249
250    size_t i1 = 0, i2 = 0;
251    while (i1 < dv1->count && i2 < dv2->count) {
252        int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
253        if (delta == 0) {
254            i1 = SOSDVINCRIX(dv1, i1);
255            i2 = SOSDVINCRIX(dv2, i2);
256        } else if (delta < 0) {
257            SOSDigestVectorAppendOrdered(dv1_2, dv1->digest[i1]);
258            i1 = SOSDVINCRIX(dv1, i1);
259        } else {
260            SOSDigestVectorAppendOrdered(dv2_1, dv2->digest[i2]);
261            i2 = SOSDVINCRIX(dv2, i2);
262        }
263    }
264    SOSDigestVectorAppendMultipleOrdered(dv1_2, dv1->count - i1, dv1->digest[i1]);
265    SOSDigestVectorAppendMultipleOrdered(dv2_1, dv2->count - i2, dv2->digest[i2]);
266}
267
268void SOSDigestVectorDiff(struct SOSDigestVector *dv1, struct SOSDigestVector *dv2,
269                         struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
270{
271    if (dv1->unsorted) SOSDigestVectorSort(dv1);
272	if (dv2->unsorted) SOSDigestVectorSort(dv2);
273    SOSDigestVectorDiffSorted(dv1, dv2, dv1_2, dv2_1);
274}
275
276/*
277 If A and B are sets, then the relative complement of A in B, also termed the set-theoretic difference of B and A,
278 is the set of elements in B, but not in A. The relative complement of A in B is denoted B ∖ A according to the ISO 31-11 standard
279 sometimes written B − A
280
281 The common case for us will be Removals\Additions
282 */
283
284static void SOSDigestVectorAppendComplementAtIndex(size_t a_ix, const struct SOSDigestVector *dvA, size_t b_ix, const struct SOSDigestVector *dvB,
285                                     struct SOSDigestVector *dvcomplement)
286{
287    assert(a_ix <= dvA->count && b_ix <= dvB->count);
288    while (a_ix < dvA->count && b_ix < dvB->count) {
289        int delta = SOSDigestCompare(dvA->digest[a_ix], dvB->digest[b_ix]);
290        if (delta == 0) {
291            a_ix = SOSDVINCRIX(dvA, a_ix);
292            b_ix = SOSDVINCRIX(dvB, b_ix);
293        } else if (delta < 0) {
294            a_ix = SOSDVINCRIX(dvA, a_ix);
295        } else {
296            SOSDigestVectorAppendOrdered(dvcomplement, dvB->digest[b_ix]);
297            b_ix = SOSDVINCRIX(dvB, b_ix);
298        }
299    }
300    SOSDigestVectorAppendMultipleOrdered(dvcomplement, dvB->count - b_ix, dvB->digest[b_ix]);
301}
302
303
304void SOSDigestVectorComplementSorted(const struct SOSDigestVector *dvA, const struct SOSDigestVector *dvB,
305                                     struct SOSDigestVector *dvcomplement)
306{
307    /* dvcomplement should be empty to start. */
308    assert(dvcomplement->count == 0);
309    assert(!dvA->unsorted);
310	assert(!dvB->unsorted);
311
312    SOSDigestVectorAppendComplementAtIndex(0, dvA, 0, dvB, dvcomplement);
313}
314
315
316/*
317    For each item in base
318
319 one way to do would be to define SOSDigestVectorComplementSorted
320
321 For removals, if removal value is less than base, increment until GEQ
322 */
323bool SOSDigestVectorPatchSorted(const struct SOSDigestVector *base, const struct SOSDigestVector *removals,
324                                const struct SOSDigestVector *additions, struct SOSDigestVector *dv,
325                                CFErrorRef *error)
326{
327    /* dv should be empty to start. */
328    assert(dv->count == 0);
329    assert(!base->unsorted);
330	assert(!removals->unsorted);
331	assert(!additions->unsorted);
332
333    size_t i1 = 0, i2 = 0, i3 = 0;
334    while (i1 < base->count && i2 < additions->count) {
335        // Pick the smaller of base->digest[i1] and additions->digest[i2] as a
336        // candidate to be put into the output vector. If udelta positive, addition is smaller
337        int udelta = SOSDigestCompare(base->digest[i1], additions->digest[i2]);
338        const uint8_t *candidate = udelta < 0 ? base->digest[i1] : additions->digest[i2];
339
340        // ddelta > 0 means rem > candidate
341        int ddelta = 1;
342        while (i3 < removals->count) {
343            ddelta = SOSDigestCompare(removals->digest[i3], candidate);
344            if (ddelta < 0) {
345                i3 = SOSDVINCRIX(removals, i3);
346            } else {
347                if (ddelta == 0)
348                    i3 = SOSDVINCRIX(removals, i3);
349                break;
350            }
351        }
352        if (ddelta > 0)
353            SOSDigestVectorAppendOrdered(dv, candidate);
354
355        // Point to next (different) candidate
356        if (udelta == 0) {
357            i1 = SOSDVINCRIX(base, i1);
358            i2 = SOSDVINCRIX(additions, i2);
359        } else if (udelta < 0) {
360            i1 = SOSDVINCRIX(base, i1);
361        } else {
362            i2 = SOSDVINCRIX(additions, i2);
363        }
364    }
365    SOSDigestVectorAppendComplementAtIndex(i3, removals, i1, base, dv);
366    SOSDigestVectorAppendComplementAtIndex(i3, removals, i2, additions, dv);
367
368    return true;
369}
370
371bool SOSDigestVectorPatch(struct SOSDigestVector *base, struct SOSDigestVector *removals,
372                          struct SOSDigestVector *additions, struct SOSDigestVector *dv,
373                          CFErrorRef *error)
374{
375	if (base->unsorted) SOSDigestVectorSort(base);
376	if (removals->unsorted) SOSDigestVectorSort(removals);
377	if (additions->unsorted) SOSDigestVectorSort(additions);
378    return SOSDigestVectorPatchSorted(base, removals, additions, dv, error);
379}
380