--- /dev/null
+/*
+ * Copyright (c) 2013-2015 Apple Inc. All Rights Reserved.
+ *
+ * @APPLE_LICENSE_HEADER_START@
+ *
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this
+ * file.
+ *
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
+ * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.
+ *
+ * @APPLE_LICENSE_HEADER_END@
+ */
+
+
+#include <Security/SecureObjectSync/SOSDigestVector.h>
+#include <utilities/SecCFError.h>
+#include <utilities/SecCFWrappers.h>
+#include <utilities/comparison.h>
+#include <dispatch/dispatch.h>
+#include <stdlib.h>
+
+CFStringRef kSOSDigestVectorErrorDomain = CFSTR("com.apple.security.sos.digestvector.error");
+
+/* SOSDigestVector code. */
+
+#define VECTOR_GROW(vector, count, capacity) \
+do { \
+ if ((count) > capacity) { \
+ capacity = ((capacity) + 16) * 3 / 2; \
+ if (capacity < (count)) \
+ capacity = (count); \
+ vector = reallocf((vector), sizeof(*(vector)) * capacity); \
+ } \
+} while (0)
+
+static void SOSDigestVectorEnsureCapacity(struct SOSDigestVector *dv, size_t count) {
+ VECTOR_GROW(dv->digest, count, dv->capacity);
+}
+
+void SOSDigestVectorReplaceAtIndex(struct SOSDigestVector *dv, size_t ix, const uint8_t *digest)
+{
+ SOSDigestVectorEnsureCapacity(dv, ix + 1);
+ memcpy(dv->digest[ix], digest, SOSDigestSize);
+ dv->unsorted = true;
+}
+
+static void SOSDigestVectorAppendOrdered(struct SOSDigestVector *dv, const uint8_t *digest)
+{
+ SOSDigestVectorEnsureCapacity(dv, dv->count + 1);
+ memcpy(dv->digest[dv->count++], digest, SOSDigestSize);
+}
+
+void SOSDigestVectorAppend(struct SOSDigestVector *dv, const uint8_t *digest)
+{
+ SOSDigestVectorAppendOrdered(dv, digest);
+ dv->unsorted = true;
+}
+
+static int SOSDigestCompare(const void *a, const void *b)
+{
+ return memcmp(a, b, SOSDigestSize);
+}
+
+// Remove duplicates from sorted manifest using minimal memcpy() calls
+static __unused void SOSDigestVectorUnique(struct SOSDigestVector *dv) {
+ if (dv->count < 2)
+ return;
+
+ const uint8_t *prev = dv->digest[0];
+ uint8_t *dest = dv->digest[1];
+ const uint8_t *end = dv->digest[dv->count];
+ const uint8_t *source = dest;
+ for (const uint8_t *cur = source; cur < end; cur += SOSDigestSize) {
+ int delta = SOSDigestCompare(prev, cur);
+ if (delta < 0) {
+ // Found a properly sorted element
+ // 1) Extend the current region (prev is end of region pointer)
+ // 2) Reset prev
+ prev = cur;
+ } else if (delta > 0) {
+ // DigestVector wasn't sorted!
+ assert(delta <= 0);
+ } else {
+ // Found a duplicate element
+ // 1) Finish copy for current region up to previous element
+ prev += SOSDigestSize;
+ if (dest != source)
+ memcpy(dest, source, prev - source);
+ dest += prev - source;
+ // 2) Skip remaining dupes
+ if (cur < end) {
+ while (cur += SOSDigestSize, cur < end) {
+ int delta = SOSDigestCompare(prev, cur);
+ assert(delta <= 0);
+ if (delta != 0)
+ break;
+ }
+ }
+ // cur now points to the first new element that hasn't yet been copied
+ // 3) Set start of next region
+ prev = cur;
+ source = cur;
+ }
+ }
+
+ // Copy remainder of final region
+ if (source < end) {
+ prev += SOSDigestSize;
+ if (dest != source)
+ memcpy(dest, source, prev - source);
+ dest += prev - source;
+ }
+ dv->count = (dest - dv->digest[0]) / SOSDigestSize;
+}
+
+
+void SOSDigestVectorSort(struct SOSDigestVector *dv)
+{
+ if (dv->unsorted) {
+ qsort(dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
+ dv->unsorted = false;
+ SOSDigestVectorUnique(dv);
+ }
+}
+
+void SOSDigestVectorUniqueSorted(struct SOSDigestVector *dv)
+{
+ // Uniqify in place (sort does this now for safety)
+ if (dv->unsorted)
+ SOSDigestVectorSort(dv);
+}
+
+void SOSDigestVectorSwap(struct SOSDigestVector *dva, struct SOSDigestVector *dvb)
+{
+ struct SOSDigestVector dv;
+ dv = *dva;
+ *dva = *dvb;
+ *dvb = dv;
+}
+
+bool SOSDigestVectorContainsSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
+{
+ return SOSDigestVectorIndexOfSorted(dv, digest) != (size_t)-1;
+}
+
+bool SOSDigestVectorContains(struct SOSDigestVector *dv, const uint8_t *digest)
+{
+ if (dv->unsorted)
+ SOSDigestVectorSort(dv);
+ return SOSDigestVectorContainsSorted(dv, digest);
+}
+
+size_t SOSDigestVectorIndexOfSorted(const struct SOSDigestVector *dv, const uint8_t *digest)
+{
+ const void *pos = bsearch(digest, dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
+ return pos ? ((size_t)(pos - (void *)dv->digest)) / SOSDigestSize : ((size_t)-1);
+}
+
+size_t SOSDigestVectorIndexOf(struct SOSDigestVector *dv, const uint8_t *digest)
+{
+ if (dv->unsorted)
+ SOSDigestVectorSort(dv);
+ return SOSDigestVectorIndexOfSorted(dv, digest);
+}
+
+void SOSDigestVectorFree(struct SOSDigestVector *dv)
+{
+ free(dv->digest);
+ dv->digest = NULL;
+ dv->count = 0;
+ dv->capacity = 0;
+ dv->unsorted = false;
+}
+
+void SOSDigestVectorApplySorted(const struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
+{
+ bool stop = false;
+ for (size_t ix = 0; !stop && ix < dv->count; ++ix) {
+ with(dv->digest[ix], &stop);
+ }
+}
+
+void SOSDigestVectorApply(struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
+{
+ if (dv->unsorted)
+ SOSDigestVectorSort(dv);
+ SOSDigestVectorApplySorted(dv, with);
+}
+
+// TODO: Check for NDEBUG to disable skip dupes are release time.
+//#define SOSDVSKIPDUPES 0
+#define SOSDVSKIPDUPES 1
+
+#if SOSDVSKIPDUPES
+#define SOSDVINCRIX(dv,ix) (SOSDigestVectorIncrementAndSkipDupes(dv,ix))
+
+static size_t SOSIncrementAndSkipDupes(const uint8_t *digests, size_t count, const size_t ix) {
+ size_t new_ix = ix;
+ if (new_ix < count) {
+ while (++new_ix < count) {
+ int delta = SOSDigestCompare(digests + ix * SOSDigestSize, digests + new_ix * SOSDigestSize);
+ assert(delta <= 0);
+ if (delta != 0)
+ break;
+ }
+ }
+ return new_ix;
+}
+
+static size_t SOSDigestVectorIncrementAndSkipDupes(const struct SOSDigestVector *dv, const size_t ix) {
+ return SOSIncrementAndSkipDupes((const uint8_t *)dv->digest, dv->count, ix);
+}
+
+void SOSDigestVectorAppendMultipleOrdered(struct SOSDigestVector *dv,
+ size_t count, const uint8_t *digests) {
+ size_t ix = 0;
+ while (ix < count) {
+ SOSDigestVectorAppendOrdered(dv, digests + (ix * SOSDigestSize));
+ ix = SOSIncrementAndSkipDupes(digests, count, ix);
+ }
+}
+
+#else /* !SOSDVSKIPDUPES */
+
+#define SOSDVINCRIX(dv,ix) (ix + 1)
+
+void SOSDigestVectorAppendMultipleOrdered(struct SOSDigestVector *dv,
+ size_t count, const uint8_t *digests) {
+ if (count) {
+ SOSDigestVectorEnsureCapacity(dv, dv->count + count);
+ memcpy(dv->digest[dv->count], digests, count * SOSDigestSize);
+ dv->count += count;
+ }
+}
+
+#endif /* !SOSDVSKIPDUPES */
+
+void SOSDigestVectorIntersectSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
+ struct SOSDigestVector *dvintersect)
+{
+ /* dvintersect should be empty to start. */
+ assert(dvintersect->count == 0);
+ size_t i1 = 0, i2 = 0;
+ while (i1 < dv1->count && i2 < dv2->count) {
+ int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
+ if (delta == 0) {
+ SOSDigestVectorAppendOrdered(dvintersect, dv1->digest[i1]);
+ i1 = SOSDVINCRIX(dv1, i1);
+ i2 = SOSDVINCRIX(dv2, i2);
+ } else if (delta < 0) {
+ i1 = SOSDVINCRIX(dv1, i1);
+ } else {
+ i2 = SOSDVINCRIX(dv2, i2);
+ }
+ }
+}
+
+void SOSDigestVectorUnionSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
+ struct SOSDigestVector *dvunion)
+{
+ /* dvunion should be empty to start. */
+ assert(dvunion->count == 0);
+ size_t i1 = 0, i2 = 0;
+ while (i1 < dv1->count && i2 < dv2->count) {
+ int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
+ if (delta == 0) {
+ SOSDigestVectorAppendOrdered(dvunion, dv1->digest[i1]);
+ i1 = SOSDVINCRIX(dv1, i1);
+ i2 = SOSDVINCRIX(dv2, i2);
+ } else if (delta < 0) {
+ SOSDigestVectorAppendOrdered(dvunion, dv1->digest[i1]);
+ i1 = SOSDVINCRIX(dv1, i1);
+ } else {
+ SOSDigestVectorAppendOrdered(dvunion, dv2->digest[i2]);
+ i2 = SOSDVINCRIX(dv2, i2);
+ }
+ }
+ SOSDigestVectorAppendMultipleOrdered(dvunion, dv1->count - i1, dv1->digest[i1]);
+ SOSDigestVectorAppendMultipleOrdered(dvunion, dv2->count - i2, dv2->digest[i2]);
+}
+
+void SOSDigestVectorDiffSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
+ struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
+{
+ /* dv1_2 and dv2_1 should be empty to start. */
+ assert(dv1_2->count == 0);
+ assert(dv2_1->count == 0);
+
+ size_t i1 = 0, i2 = 0;
+ while (i1 < dv1->count && i2 < dv2->count) {
+ int delta = SOSDigestCompare(dv1->digest[i1], dv2->digest[i2]);
+ if (delta == 0) {
+ i1 = SOSDVINCRIX(dv1, i1);
+ i2 = SOSDVINCRIX(dv2, i2);
+ } else if (delta < 0) {
+ SOSDigestVectorAppendOrdered(dv1_2, dv1->digest[i1]);
+ i1 = SOSDVINCRIX(dv1, i1);
+ } else {
+ SOSDigestVectorAppendOrdered(dv2_1, dv2->digest[i2]);
+ i2 = SOSDVINCRIX(dv2, i2);
+ }
+ }
+ SOSDigestVectorAppendMultipleOrdered(dv1_2, dv1->count - i1, dv1->digest[i1]);
+ SOSDigestVectorAppendMultipleOrdered(dv2_1, dv2->count - i2, dv2->digest[i2]);
+}
+
+void SOSDigestVectorDiff(struct SOSDigestVector *dv1, struct SOSDigestVector *dv2,
+ struct SOSDigestVector *dv1_2, struct SOSDigestVector *dv2_1)
+{
+ if (dv1->unsorted) SOSDigestVectorSort(dv1);
+ if (dv2->unsorted) SOSDigestVectorSort(dv2);
+ SOSDigestVectorDiffSorted(dv1, dv2, dv1_2, dv2_1);
+}
+
+/*
+ If A and B are sets, then the relative complement of A in B, also termed the set-theoretic difference of B and A,
+ 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
+ sometimes written B − A
+
+ The common case for us will be Removals\Additions
+ */
+
+static void SOSDigestVectorAppendComplementAtIndex(size_t a_ix, const struct SOSDigestVector *dvA, size_t b_ix, const struct SOSDigestVector *dvB,
+ struct SOSDigestVector *dvcomplement)
+{
+ assert(a_ix <= dvA->count && b_ix <= dvB->count);
+ while (a_ix < dvA->count && b_ix < dvB->count) {
+ int delta = SOSDigestCompare(dvA->digest[a_ix], dvB->digest[b_ix]);
+ if (delta == 0) {
+ a_ix = SOSDVINCRIX(dvA, a_ix);
+ b_ix = SOSDVINCRIX(dvB, b_ix);
+ } else if (delta < 0) {
+ a_ix = SOSDVINCRIX(dvA, a_ix);
+ } else {
+ SOSDigestVectorAppendOrdered(dvcomplement, dvB->digest[b_ix]);
+ b_ix = SOSDVINCRIX(dvB, b_ix);
+ }
+ }
+ SOSDigestVectorAppendMultipleOrdered(dvcomplement, dvB->count - b_ix, dvB->digest[b_ix]);
+}
+
+
+void SOSDigestVectorComplementSorted(const struct SOSDigestVector *dvA, const struct SOSDigestVector *dvB,
+ struct SOSDigestVector *dvcomplement)
+{
+ /* dvcomplement should be empty to start. */
+ assert(dvcomplement->count == 0);
+ assert(!dvA->unsorted);
+ assert(!dvB->unsorted);
+
+ SOSDigestVectorAppendComplementAtIndex(0, dvA, 0, dvB, dvcomplement);
+}
+
+
+/*
+ For each item in base
+
+ one way to do would be to define SOSDigestVectorComplementSorted
+
+ For removals, if removal value is less than base, increment until GEQ
+ */
+bool SOSDigestVectorPatchSorted(const struct SOSDigestVector *base, const struct SOSDigestVector *removals,
+ const struct SOSDigestVector *additions, struct SOSDigestVector *dv,
+ CFErrorRef *error)
+{
+ /* dv should be empty to start. */
+ assert(dv->count == 0);
+ assert(!base->unsorted);
+ assert(!removals->unsorted);
+ assert(!additions->unsorted);
+
+ size_t i1 = 0, i2 = 0, i3 = 0;
+ while (i1 < base->count && i2 < additions->count) {
+ // Pick the smaller of base->digest[i1] and additions->digest[i2] as a
+ // candidate to be put into the output vector. If udelta positive, addition is smaller
+ int udelta = SOSDigestCompare(base->digest[i1], additions->digest[i2]);
+ const uint8_t *candidate = udelta < 0 ? base->digest[i1] : additions->digest[i2];
+
+ // ddelta > 0 means rem > candidate
+ int ddelta = 1;
+ while (i3 < removals->count) {
+ ddelta = SOSDigestCompare(removals->digest[i3], candidate);
+ if (ddelta < 0) {
+ i3 = SOSDVINCRIX(removals, i3);
+ } else {
+ if (ddelta == 0)
+ i3 = SOSDVINCRIX(removals, i3);
+ break;
+ }
+ }
+ if (ddelta > 0)
+ SOSDigestVectorAppendOrdered(dv, candidate);
+
+ // Point to next (different) candidate
+ if (udelta == 0) {
+ i1 = SOSDVINCRIX(base, i1);
+ i2 = SOSDVINCRIX(additions, i2);
+ } else if (udelta < 0) {
+ i1 = SOSDVINCRIX(base, i1);
+ } else {
+ i2 = SOSDVINCRIX(additions, i2);
+ }
+ }
+ SOSDigestVectorAppendComplementAtIndex(i3, removals, i1, base, dv);
+ SOSDigestVectorAppendComplementAtIndex(i3, removals, i2, additions, dv);
+
+ return true;
+}
+
+bool SOSDigestVectorPatch(struct SOSDigestVector *base, struct SOSDigestVector *removals,
+ struct SOSDigestVector *additions, struct SOSDigestVector *dv,
+ CFErrorRef *error)
+{
+ if (base->unsorted) SOSDigestVectorSort(base);
+ if (removals->unsorted) SOSDigestVectorSort(removals);
+ if (additions->unsorted) SOSDigestVectorSort(additions);
+ return SOSDigestVectorPatchSorted(base, removals, additions, dv, error);
+}
projects / apple / security.git / blobdiff