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