#include "keychain/SecureObjectSync/SOSDigestVector.h"
#include <utilities/SecCFError.h>
#include <utilities/SecCFWrappers.h>
#include <dispatch/dispatch.h>
#include <stdlib.h>
CFStringRef kSOSDigestVectorErrorDomain = CFSTR("com.apple.security.sos.digestvector.error");
const size_t kMaxDVCapacity = (1024*1024L);
static bool SOSDigestVectorEnsureCapacity(struct SOSDigestVector *dv, size_t count) {
if (count <= dv->capacity)
return true;
if (count > kMaxDVCapacity) {
secnotice("manifest", "Requesting too much space for digest vectors: %ld", count);
return false;
}
size_t capacity = MIN(count + 100, kMaxDVCapacity);
dv->digest = reallocf(dv->digest, SOSDigestSize * capacity);
if (dv->digest == NULL) {
dv->count = 0;
dv->capacity = 0;
secnotice("manifest", "reallocf failed requesting space for digest vectors: %ld (bytes)", SOSDigestSize * capacity);
return false;
}
dv->capacity = capacity;
return true;
}
static void SOSDigestVectorAppendOrdered(struct SOSDigestVector *dv, const uint8_t *digest)
{
if (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);
}
static void SOSDigestVectorUnique(struct SOSDigestVector *dv) {
if (dv->count < 2 || dv->digest == NULL)
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) {
prev = cur;
} else if (delta > 0) {
assert(delta <= 0);
} else {
prev += SOSDigestSize;
if (dest != source)
memmove(dest, source, prev - source);
dest += prev - source;
if (cur < end) {
cur += SOSDigestSize;
while (cur < end) {
int delta = SOSDigestCompare(prev, cur);
assert(delta <= 0);
if (delta != 0) {
break;
}
cur += SOSDigestSize;
}
}
prev = cur;
source = cur;
}
}
if (source < end) {
prev += SOSDigestSize;
if (dest != source)
memmove(dest, source, prev - source);
dest += prev - source;
}
dv->count = (dest - dv->digest[0]) / SOSDigestSize;
}
void SOSDigestVectorSort(struct SOSDigestVector *dv)
{
if (dv->unsorted && dv->digest) {
qsort(dv->digest, dv->count, sizeof(*dv->digest), SOSDigestCompare);
dv->unsorted = false;
SOSDigestVectorUnique(dv);
}
}
void SOSDigestVectorUniqueSorted(struct SOSDigestVector *dv)
{
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)
{
if (dv->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);
} else {
return -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 && dv->digest; ++ix) {
with(dv->digest[ix], &stop);
}
}
void SOSDigestVectorApply(struct SOSDigestVector *dv, SOSDigestVectorApplyBlock with)
{
if (dv->unsorted)
SOSDigestVectorSort(dv);
SOSDigestVectorApplySorted(dv, with);
}
#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 (digests && 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
#define SOSDVINCRIX(dv,ix) (ix + 1)
void SOSDigestVectorAppendMultipleOrdered(struct SOSDigestVector *dv,
size_t count, const uint8_t *digests) {
if (count) {
if (SOSDigestVectorEnsureCapacity(dv, dv->count + count))
memcpy(dv->digest[dv->count], digests, count * SOSDigestSize);
dv->count += count;
}
}
#endif
void SOSDigestVectorIntersectSorted(const struct SOSDigestVector *dv1, const struct SOSDigestVector *dv2,
struct SOSDigestVector *dvintersect)
{
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)
{
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)
{
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);
}
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 && dvA->digest && dvB->digest) {
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);
}
}
if (dvB->digest)
SOSDigestVectorAppendMultipleOrdered(dvcomplement, dvB->count - b_ix, dvB->digest[b_ix]);
}
void SOSDigestVectorComplementSorted(const struct SOSDigestVector *dvA, const struct SOSDigestVector *dvB,
struct SOSDigestVector *dvcomplement)
{
assert(dvcomplement->count == 0);
assert(!dvA->unsorted);
assert(!dvB->unsorted);
SOSDigestVectorAppendComplementAtIndex(0, dvA, 0, dvB, dvcomplement);
}
bool SOSDigestVectorPatchSorted(const struct SOSDigestVector *base, const struct SOSDigestVector *removals,
const struct SOSDigestVector *additions, struct SOSDigestVector *dv,
CFErrorRef *error)
{
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) {
int udelta = SOSDigestCompare(base->digest[i1], additions->digest[i2]);
const uint8_t *candidate = udelta < 0 ? base->digest[i1] : additions->digest[i2];
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);
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);
}