]> git.saurik.com Git - apple/security.git/blob - Security/sec/SOSCircle/SecureObjectSync/SOSDigestVector.c
Security-57031.1.35.tar.gz
[apple/security.git] / Security / sec / SOSCircle / SecureObjectSync / SOSDigestVector.c
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
32 CFStringRef kSOSDigestVectorErrorDomain = CFSTR("com.apple.security.sos.digestvector.error");
33
34 /* SOSDigestVector code. */
35
36 #define VECTOR_GROW(vector, count, capacity) \
37 do { \
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
46 static void SOSDigestVectorEnsureCapacity(struct SOSDigestVector *dv, size_t count) {
47 VECTOR_GROW(dv->digest, count, dv->capacity);
48 }
49
50 void 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
57 static 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
63 void SOSDigestVectorAppend(struct SOSDigestVector *dv, const uint8_t *digest)
64 {
65 SOSDigestVectorAppendOrdered(dv, digest);
66 dv->unsorted = true;
67 }
68
69 static int SOSDigestCompare(const void *a, const void *b)
70 {
71 return memcmp(a, b, SOSDigestSize);
72 }
73
74 void 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
82 void 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
102 void SOSDigestVectorSwap(struct SOSDigestVector *dva, struct SOSDigestVector *dvb)
103 {
104 struct SOSDigestVector dv;
105 dv = *dva;
106 *dva = *dvb;
107 *dvb = dv;
108 }
109
110 bool SOSDigestVectorContainsSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
111 {
112 return SOSDigestVectorIndexOfSorted(dv, digest) != (size_t)-1;
113 }
114
115 bool SOSDigestVectorContains(struct SOSDigestVector *dv, const uint8_t *digest)
116 {
117 if (dv->unsorted)
118 SOSDigestVectorSort(dv);
119 return SOSDigestVectorContainsSorted(dv, digest);
120 }
121
122 size_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
128 size_t SOSDigestVectorIndexOf(struct SOSDigestVector *dv, const uint8_t *digest)
129 {
130 if (dv->unsorted)
131 SOSDigestVectorSort(dv);
132 return SOSDigestVectorIndexOfSorted(dv, digest);
133 }
134
135 void 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
144 void 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
152 void 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
169 static 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
182 void 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
199 void 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
219 void 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
243 void 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
268 void 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
284 static 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
304 void 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 */
323 bool 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
371 bool 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 }