]> git.saurik.com Git - apple/security.git/blob - OSX/sec/SOSCircle/SecureObjectSync/SOSDigestVector.c
Security-57336.1.9.tar.gz
[apple/security.git] / OSX / sec / SOSCircle / SecureObjectSync / SOSDigestVector.c
1 /*
2 * Copyright (c) 2013-2015 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 <Security/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 // Remove duplicates from sorted manifest using minimal memcpy() calls
75 static __unused void SOSDigestVectorUnique(struct SOSDigestVector *dv) {
76 if (dv->count < 2)
77 return;
78
79 const uint8_t *prev = dv->digest[0];
80 uint8_t *dest = dv->digest[1];
81 const uint8_t *end = dv->digest[dv->count];
82 const uint8_t *source = dest;
83 for (const uint8_t *cur = source; cur < end; cur += SOSDigestSize) {
84 int delta = SOSDigestCompare(prev, cur);
85 if (delta < 0) {
86 // Found a properly sorted element
87 // 1) Extend the current region (prev is end of region pointer)
88 // 2) Reset prev
89 prev = cur;
90 } else if (delta > 0) {
91 // DigestVector wasn't sorted!
92 assert(delta <= 0);
93 } else {
94 // Found a duplicate element
95 // 1) Finish copy for current region up to previous element
96 prev += SOSDigestSize;
97 if (dest != source)
98 memcpy(dest, source, prev - source);
99 dest += prev - source;
100 // 2) Skip remaining dupes
101 if (cur < end) {
102 while (cur += SOSDigestSize, cur < end) {
103 int delta = SOSDigestCompare(prev, cur);
104 assert(delta <= 0);
105 if (delta != 0)
106 break;
107 }
108 }
109 // cur now points to the first new element that hasn't yet been copied
110 // 3) Set start of next region
111 prev = cur;
112 source = cur;
113 }
114 }
115
116 // Copy remainder of final region
117 if (source < end) {
118 prev += SOSDigestSize;
119 if (dest != source)
120 memcpy(dest, source, prev - source);
121 dest += prev - source;
122 }
123 dv->count = (dest - dv->digest[0]) / SOSDigestSize;
124 }
125
126
127 void SOSDigestVectorSort(struct SOSDigestVector *dv)
128 {
129 if (dv->unsorted) {
130 qsort(dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
131 dv->unsorted = false;
132 SOSDigestVectorUnique(dv);
133 }
134 }
135
136 void SOSDigestVectorUniqueSorted(struct SOSDigestVector *dv)
137 {
138 // Uniqify in place (sort does this now for safety)
139 if (dv->unsorted)
140 SOSDigestVectorSort(dv);
141 }
142
143 void SOSDigestVectorSwap(struct SOSDigestVector *dva, struct SOSDigestVector *dvb)
144 {
145 struct SOSDigestVector dv;
146 dv = *dva;
147 *dva = *dvb;
148 *dvb = dv;
149 }
150
151 bool SOSDigestVectorContainsSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
152 {
153 return SOSDigestVectorIndexOfSorted(dv, digest) != (size_t)-1;
154 }
155
156 bool SOSDigestVectorContains(struct SOSDigestVector *dv, const uint8_t *digest)
157 {
158 if (dv->unsorted)
159 SOSDigestVectorSort(dv);
160 return SOSDigestVectorContainsSorted(dv, digest);
161 }
162
163 size_t SOSDigestVectorIndexOfSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
164 {
165 const void *pos = bsearch(digest, dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
166 return pos ? ((size_t)(pos - (void *)dv->digest)) / SOSDigestSize : ((size_t)-1);
167 }
168
169 size_t SOSDigestVectorIndexOf(struct SOSDigestVector *dv, const uint8_t *digest)
170 {
171 if (dv->unsorted)
172 SOSDigestVectorSort(dv);
173 return SOSDigestVectorIndexOfSorted(dv, digest);
174 }
175
176 void SOSDigestVectorFree(struct SOSDigestVector *dv)
177 {
178 free(dv->digest);
179 dv->digest = NULL;
180 dv->count = 0;
181 dv->capacity = 0;
182 dv->unsorted = false;
183 }
184
185 void SOSDigestVectorApplySorted(const struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
186 {
187 bool stop = false;
188 for (size_t ix = 0; !stop && ix < dv->count; ++ix) {
189 with(dv->digest[ix], &stop);
190 }
191 }
192
193 void SOSDigestVectorApply(struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
194 {
195 if (dv->unsorted)
196 SOSDigestVectorSort(dv);
197 SOSDigestVectorApplySorted(dv, with);
198 }
199
200 // TODO: Check for NDEBUG to disable skip dupes are release time.
201 //#define SOSDVSKIPDUPES 0
202 #define SOSDVSKIPDUPES 1
203
204 #if SOSDVSKIPDUPES
205 #define SOSDVINCRIX(dv,ix) (SOSDigestVectorIncrementAndSkipDupes(dv,ix))
206
207 static size_t SOSIncrementAndSkipDupes(const uint8_t *digests, size_t count, const size_t ix) {
208 size_t new_ix = ix;
209 if (new_ix < count) {
210 while (++new_ix < count) {
211 int delta = SOSDigestCompare(digests + ix * SOSDigestSize, digests + new_ix * SOSDigestSize);
212 assert(delta <= 0);
213 if (delta != 0)
214 break;
215 }
216 }
217 return new_ix;
218 }
219
220 static size_t SOSDigestVectorIncrementAndSkipDupes(const struct SOSDigestVector *dv, const size_t ix) {
221 return SOSIncrementAndSkipDupes((const uint8_t *)dv->digest, dv->count, ix);
222 }
223
224 void SOSDigestVectorAppendMultipleOrdered(struct SOSDigestVector *dv,
225 size_t count, const uint8_t *digests) {
226 size_t ix = 0;
227 while (ix < count) {
228 SOSDigestVectorAppendOrdered(dv, digests + (ix * SOSDigestSize));
229 ix = SOSIncrementAndSkipDupes(digests, count, ix);
230 }
231 }
232
233 #else /* !SOSDVSKIPDUPES */
234
235 #define SOSDVINCRIX(dv,ix) (ix + 1)
236
237 void SOSDigestVectorAppendMultipleOrdered(struct SOSDigestVector *dv,
238 size_t count, const uint8_t *digests) {
239 if (count) {
240 SOSDigestVectorEnsureCapacity(dv, dv->count + count);
241 memcpy(dv->digest[dv->count], digests, count * SOSDigestSize);
242 dv->count += count;
243 }
244 }
245
246 #endif /* !SOSDVSKIPDUPES */
247
248 void SOSDigestVectorIntersectSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
249 struct SOSDigestVector *dvintersect)
250 {
251 /* dvintersect should be empty to start. */
252 assert(dvintersect->count == 0);
253 size_t i1 = 0, i2 = 0;
254 while (i1 < dv1->count && i2 < dv2->count) {
255 int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
256 if (delta == 0) {
257 SOSDigestVectorAppendOrdered(dvintersect, dv1->digest[i1]);
258 i1 = SOSDVINCRIX(dv1, i1);
259 i2 = SOSDVINCRIX(dv2, i2);
260 } else if (delta < 0) {
261 i1 = SOSDVINCRIX(dv1, i1);
262 } else {
263 i2 = SOSDVINCRIX(dv2, i2);
264 }
265 }
266 }
267
268 void SOSDigestVectorUnionSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
269 struct SOSDigestVector *dvunion)
270 {
271 /* dvunion should be empty to start. */
272 assert(dvunion->count == 0);
273 size_t i1 = 0, i2 = 0;
274 while (i1 < dv1->count && i2 < dv2->count) {
275 int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
276 if (delta == 0) {
277 SOSDigestVectorAppendOrdered(dvunion, dv1->digest[i1]);
278 i1 = SOSDVINCRIX(dv1, i1);
279 i2 = SOSDVINCRIX(dv2, i2);
280 } else if (delta < 0) {
281 SOSDigestVectorAppendOrdered(dvunion, dv1->digest[i1]);
282 i1 = SOSDVINCRIX(dv1, i1);
283 } else {
284 SOSDigestVectorAppendOrdered(dvunion, dv2->digest[i2]);
285 i2 = SOSDVINCRIX(dv2, i2);
286 }
287 }
288 SOSDigestVectorAppendMultipleOrdered(dvunion, dv1->count - i1, dv1->digest[i1]);
289 SOSDigestVectorAppendMultipleOrdered(dvunion, dv2->count - i2, dv2->digest[i2]);
290 }
291
292 void SOSDigestVectorDiffSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
293 struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
294 {
295 /* dv1_2 and dv2_1 should be empty to start. */
296 assert(dv1_2->count == 0);
297 assert(dv2_1->count == 0);
298
299 size_t i1 = 0, i2 = 0;
300 while (i1 < dv1->count && i2 < dv2->count) {
301 int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
302 if (delta == 0) {
303 i1 = SOSDVINCRIX(dv1, i1);
304 i2 = SOSDVINCRIX(dv2, i2);
305 } else if (delta < 0) {
306 SOSDigestVectorAppendOrdered(dv1_2, dv1->digest[i1]);
307 i1 = SOSDVINCRIX(dv1, i1);
308 } else {
309 SOSDigestVectorAppendOrdered(dv2_1, dv2->digest[i2]);
310 i2 = SOSDVINCRIX(dv2, i2);
311 }
312 }
313 SOSDigestVectorAppendMultipleOrdered(dv1_2, dv1->count - i1, dv1->digest[i1]);
314 SOSDigestVectorAppendMultipleOrdered(dv2_1, dv2->count - i2, dv2->digest[i2]);
315 }
316
317 void SOSDigestVectorDiff(struct SOSDigestVector *dv1, struct SOSDigestVector *dv2,
318 struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
319 {
320 if (dv1->unsorted) SOSDigestVectorSort(dv1);
321 if (dv2->unsorted) SOSDigestVectorSort(dv2);
322 SOSDigestVectorDiffSorted(dv1, dv2, dv1_2, dv2_1);
323 }
324
325 /*
326 If A and B are sets, then the relative complement of A in B, also termed the set-theoretic difference of B and A,
327 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
328 sometimes written B − A
329
330 The common case for us will be Removals\Additions
331 */
332
333 static void SOSDigestVectorAppendComplementAtIndex(size_t a_ix, const struct SOSDigestVector *dvA, size_t b_ix, const struct SOSDigestVector *dvB,
334 struct SOSDigestVector *dvcomplement)
335 {
336 assert(a_ix <= dvA->count && b_ix <= dvB->count);
337 while (a_ix < dvA->count && b_ix < dvB->count) {
338 int delta = SOSDigestCompare(dvA->digest[a_ix], dvB->digest[b_ix]);
339 if (delta == 0) {
340 a_ix = SOSDVINCRIX(dvA, a_ix);
341 b_ix = SOSDVINCRIX(dvB, b_ix);
342 } else if (delta < 0) {
343 a_ix = SOSDVINCRIX(dvA, a_ix);
344 } else {
345 SOSDigestVectorAppendOrdered(dvcomplement, dvB->digest[b_ix]);
346 b_ix = SOSDVINCRIX(dvB, b_ix);
347 }
348 }
349 SOSDigestVectorAppendMultipleOrdered(dvcomplement, dvB->count - b_ix, dvB->digest[b_ix]);
350 }
351
352
353 void SOSDigestVectorComplementSorted(const struct SOSDigestVector *dvA, const struct SOSDigestVector *dvB,
354 struct SOSDigestVector *dvcomplement)
355 {
356 /* dvcomplement should be empty to start. */
357 assert(dvcomplement->count == 0);
358 assert(!dvA->unsorted);
359 assert(!dvB->unsorted);
360
361 SOSDigestVectorAppendComplementAtIndex(0, dvA, 0, dvB, dvcomplement);
362 }
363
364
365 /*
366 For each item in base
367
368 one way to do would be to define SOSDigestVectorComplementSorted
369
370 For removals, if removal value is less than base, increment until GEQ
371 */
372 bool SOSDigestVectorPatchSorted(const struct SOSDigestVector *base, const struct SOSDigestVector *removals,
373 const struct SOSDigestVector *additions, struct SOSDigestVector *dv,
374 CFErrorRef *error)
375 {
376 /* dv should be empty to start. */
377 assert(dv->count == 0);
378 assert(!base->unsorted);
379 assert(!removals->unsorted);
380 assert(!additions->unsorted);
381
382 size_t i1 = 0, i2 = 0, i3 = 0;
383 while (i1 < base->count && i2 < additions->count) {
384 // Pick the smaller of base->digest[i1] and additions->digest[i2] as a
385 // candidate to be put into the output vector. If udelta positive, addition is smaller
386 int udelta = SOSDigestCompare(base->digest[i1], additions->digest[i2]);
387 const uint8_t *candidate = udelta < 0 ? base->digest[i1] : additions->digest[i2];
388
389 // ddelta > 0 means rem > candidate
390 int ddelta = 1;
391 while (i3 < removals->count) {
392 ddelta = SOSDigestCompare(removals->digest[i3], candidate);
393 if (ddelta < 0) {
394 i3 = SOSDVINCRIX(removals, i3);
395 } else {
396 if (ddelta == 0)
397 i3 = SOSDVINCRIX(removals, i3);
398 break;
399 }
400 }
401 if (ddelta > 0)
402 SOSDigestVectorAppendOrdered(dv, candidate);
403
404 // Point to next (different) candidate
405 if (udelta == 0) {
406 i1 = SOSDVINCRIX(base, i1);
407 i2 = SOSDVINCRIX(additions, i2);
408 } else if (udelta < 0) {
409 i1 = SOSDVINCRIX(base, i1);
410 } else {
411 i2 = SOSDVINCRIX(additions, i2);
412 }
413 }
414 SOSDigestVectorAppendComplementAtIndex(i3, removals, i1, base, dv);
415 SOSDigestVectorAppendComplementAtIndex(i3, removals, i2, additions, dv);
416
417 return true;
418 }
419
420 bool SOSDigestVectorPatch(struct SOSDigestVector *base, struct SOSDigestVector *removals,
421 struct SOSDigestVector *additions, struct SOSDigestVector *dv,
422 CFErrorRef *error)
423 {
424 if (base->unsorted) SOSDigestVectorSort(base);
425 if (removals->unsorted) SOSDigestVectorSort(removals);
426 if (additions->unsorted) SOSDigestVectorSort(additions);
427 return SOSDigestVectorPatchSorted(base, removals, additions, dv, error);
428 }