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 }