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 }