#include <stdlib.h>
#include "semq_internal.h"
#include "core/semq_bits.h"
static uint64_t quant_hamming(const uint8_t* a, const uint8_t* b, uint32_t dim,
uint32_t bits) {
const uint32_t mask = (1u << bits) - 1u;
uint64_t count = 0u;
uint64_t bit_pos = 0u;
for (uint32_t unit = 0u; unit < dim; unit++) {
const uint64_t byte = bit_pos >> 3u;
const uint32_t shift = (uint32_t)(bit_pos & 7u);
uint32_t changed = (uint32_t)(a[byte] ^ b[byte]);
if (shift + bits > 8u) {
changed |= (uint32_t)(a[byte + 1u] ^ b[byte + 1u]) << 8u;
}
count += ((changed >> shift) & mask) != 0u;
bit_pos += bits;
}
return count;
}
static uint64_t hamming_of(const semq_encoding_t* a, uint64_t i, const semq_encoding_t* b, uint64_t j,
uint8_t* sa, uint8_t* sb) {
const uint8_t* ar = a->rows + (size_t)i * a->bpv;
const uint8_t* br = b->rows + (size_t)j * b->bpv;
if (a->config.op == SEMQ_QUANT) {
return quant_hamming(ar, br, a->config.dim,
semq_bits_per_symbol_quant(a->config.p1));
}
semqi_unpack_row(&a->config, ar, sa);
semqi_unpack_row(&b->config, br, sb);
uint64_t h = 0u;
for (uint32_t u = 0u; u < a->units; u++) h += (sa[u] != sb[u]) ? 1u : 0u;
return h;
}
static semq_status_t manifest_changes(semq_diff_t* d, semq_error_t* err) {
const semq_encoding_t* a = d->ref;
const semq_encoding_t* b = d->cand;
const uint64_t cap = (uint64_t)a->n_pairs + (uint64_t)b->n_pairs;
d->mchanges = (semq_manifest_change_t*)semqi_alloc(cap * sizeof(semq_manifest_change_t));
if (d->mchanges == NULL) return SEMQI_NOMEM(err);
uint32_t i = 0u, j = 0u, k = 0u;
while (i < a->n_pairs || j < b->n_pairs) {
int c;
if (i >= a->n_pairs) c = 1;
else if (j >= b->n_pairs) c = -1;
else c = semqi_cmp_bytes(a->manifest + a->pairs[i].key_off, a->pairs[i].key_len,
b->manifest + b->pairs[j].key_off, b->pairs[j].key_len);
semq_manifest_change_t* m = &d->mchanges[k];
memset(m, 0, sizeof(*m));
if (c < 0) {
m->key = a->manifest + a->pairs[i].key_off; m->key_len = a->pairs[i].key_len;
m->has_before = 1; m->before = a->manifest + a->pairs[i].value_off; m->before_len = a->pairs[i].value_len;
i++; k++;
} else if (c > 0) {
m->key = b->manifest + b->pairs[j].key_off; m->key_len = b->pairs[j].key_len;
m->has_after = 1; m->after = b->manifest + b->pairs[j].value_off; m->after_len = b->pairs[j].value_len;
j++; k++;
} else {
const int same = a->pairs[i].value_len == b->pairs[j].value_len
&& memcmp(a->manifest + a->pairs[i].value_off, b->manifest + b->pairs[j].value_off,
a->pairs[i].value_len) == 0;
if (!same) {
m->key = a->manifest + a->pairs[i].key_off; m->key_len = a->pairs[i].key_len;
m->has_before = 1; m->before = a->manifest + a->pairs[i].value_off; m->before_len = a->pairs[i].value_len;
m->has_after = 1; m->after = b->manifest + b->pairs[j].value_off; m->after_len = b->pairs[j].value_len;
k++;
}
i++; j++;
}
}
d->n_mchanges = k;
return SEMQ_OK;
}
SEMQ_API semq_status_t semq_encoding_diff(const semq_encoding_t* reference,
const semq_encoding_t* candidate, semq_diff_t** out,
semq_error_t* err) {
if (out == NULL) return SEMQI_INVALID(err, SEMQ_NONE, SEMQ_NONE, "output is NULL");
*out = NULL;
if (reference == NULL || candidate == NULL) return SEMQI_INVALID(err, SEMQ_NONE, SEMQ_NONE, "encoding is NULL");
if (!semq_config_equal(&reference->config, &candidate->config)) {
return semqi_fail(err, SEMQ_ERR_INCOMPATIBLE, SEMQ_NONE, SEMQ_NONE, "encodings have different configs");
}
if (reference->id_kind != candidate->id_kind) {
return semqi_fail(err, SEMQ_ERR_INCOMPATIBLE, SEMQ_NONE, SEMQ_NONE, "encodings have different id kinds");
}
semq_diff_t* d = (semq_diff_t*)semqi_calloc(1u, sizeof(*d));
if (d == NULL) return SEMQI_NOMEM(err);
d->ref = (semq_encoding_t*)reference;
d->cand = (semq_encoding_t*)candidate;
semqi_ref_inc(&d->ref->refs);
semqi_ref_inc(&d->cand->refs);
semq_status_t s = manifest_changes(d, err);
if (s != SEMQ_OK) { semq_diff_free(d); return s; }
if (memcmp(reference->footer, candidate->footer, 32u) == 0) {
d->n_unchanged = reference->n;
*out = d;
semqi_ok(err);
return SEMQ_OK;
}
const uint64_t na = reference->n, nb = candidate->n;
uint64_t cap_added, cap_removed, cap_changed;
if (semqi_mul_ovf(nb, sizeof(uint64_t), &cap_added) || semqi_mul_ovf(na, sizeof(uint64_t), &cap_removed)
|| semqi_mul_ovf(na < nb ? na : nb, sizeof(uint64_t), &cap_changed)) {
semq_diff_free(d);
return SEMQI_NOMEM(err);
}
d->added = (uint64_t*)semqi_alloc(cap_added);
d->removed = (uint64_t*)semqi_alloc(cap_removed);
d->changed_ref = (uint64_t*)semqi_alloc(cap_changed);
d->changed_cand = (uint64_t*)semqi_alloc(cap_changed);
d->hamming = (uint64_t*)semqi_alloc(cap_changed);
uint8_t* sa = NULL;
uint8_t* sb = NULL;
if (reference->config.op != SEMQ_QUANT) {
sa = (uint8_t*)semqi_alloc(reference->units);
sb = (uint8_t*)semqi_alloc(reference->units);
}
if (d->added == NULL || d->removed == NULL || d->changed_ref == NULL || d->changed_cand == NULL
|| d->hamming == NULL || (reference->config.op != SEMQ_QUANT && (sa == NULL || sb == NULL))) {
semqi_free(sa); semqi_free(sb);
semq_diff_free(d);
return SEMQI_NOMEM(err);
}
uint64_t i = 0u, j = 0u;
while (i < na || j < nb) {
int c;
if (i >= na) c = 1;
else if (j >= nb) c = -1;
else c = semqi_id_cmp(reference, i, candidate, j);
if (c < 0) {
d->removed[d->n_removed++] = i++;
} else if (c > 0) {
d->added[d->n_added++] = j++;
} else {
if (memcmp(reference->rows + (size_t)i * reference->bpv,
candidate->rows + (size_t)j * candidate->bpv, reference->bpv) == 0) {
d->n_unchanged++;
} else {
d->changed_ref[d->n_changed] = i;
d->changed_cand[d->n_changed] = j;
d->hamming[d->n_changed] = hamming_of(reference, i, candidate, j, sa, sb);
d->n_changed++;
}
i++; j++;
}
}
semqi_free(sa);
semqi_free(sb);
*out = d;
semqi_ok(err);
return SEMQ_OK;
}
SEMQ_API void semq_diff_free(semq_diff_t* d) {
if (d == NULL) return;
semq_encoding_free(d->ref);
semq_encoding_free(d->cand);
semqi_free(d->added);
semqi_free(d->removed);
semqi_free(d->changed_ref);
semqi_free(d->changed_cand);
semqi_free(d->hamming);
semqi_free(d->mchanges);
memset(d, 0, sizeof(*d));
semqi_free(d);
}
SEMQ_API const semq_config_t* semq_diff_config(const semq_diff_t* d) {
return d == NULL ? NULL : &d->ref->config;
}
SEMQ_API uint32_t semq_diff_id_kind(const semq_diff_t* d) {
return d == NULL ? 0u : d->ref->id_kind;
}
SEMQ_API void semq_diff_reference_id(const semq_diff_t* d, uint8_t out[32]) {
memcpy(out, d->ref->footer + 32, 32u);
}
SEMQ_API void semq_diff_candidate_id(const semq_diff_t* d, uint8_t out[32]) {
memcpy(out, d->cand->footer + 32, 32u);
}
SEMQ_API uint64_t semq_diff_count(const semq_diff_t* d, uint32_t list) {
if (d == NULL) return 0u;
switch (list) {
case SEMQ_LIST_ADDED: return d->n_added;
case SEMQ_LIST_REMOVED: return d->n_removed;
case SEMQ_LIST_CHANGED: return d->n_changed;
default: return 0u;
}
}
SEMQ_API uint64_t semq_diff_n_unchanged(const semq_diff_t* d) {
return d == NULL ? 0u : d->n_unchanged;
}
SEMQ_API semq_status_t semq_diff_id(const semq_diff_t* d, uint32_t list, uint64_t i, uint64_t* u64,
const uint8_t** bytes, uint64_t* len, semq_error_t* err) {
if (d == NULL) return SEMQI_INVALID(err, SEMQ_NONE, SEMQ_NONE, "diff is NULL");
const semq_encoding_t* e;
uint64_t row;
switch (list) {
case SEMQ_LIST_ADDED:
if (i >= d->n_added) return SEMQI_INVALID(err, i, list, "index out of range");
e = d->cand; row = d->added[i]; break;
case SEMQ_LIST_REMOVED:
if (i >= d->n_removed) return SEMQI_INVALID(err, i, list, "index out of range");
e = d->ref; row = d->removed[i]; break;
case SEMQ_LIST_CHANGED:
if (i >= d->n_changed) return SEMQI_INVALID(err, i, list, "index out of range");
e = d->ref; row = d->changed_ref[i]; break;
default:
return SEMQI_INVALID(err, SEMQ_NONE, list, "unknown list");
}
if (e->id_kind == SEMQ_ID_U64) {
if (u64) *u64 = semqi_rd64(e->ids + row * 8u);
if (bytes) *bytes = NULL;
if (len) *len = 0u;
} else {
const uint64_t a = semqi_rd64(e->ids + row * 8u), b = semqi_rd64(e->ids + (row + 1u) * 8u);
if (u64) *u64 = 0u;
if (bytes) *bytes = e->ids + (e->n + 1u) * 8u + a;
if (len) *len = b - a;
}
semqi_ok(err);
return SEMQ_OK;
}
SEMQ_API semq_status_t semq_diff_hamming(const semq_diff_t* d, uint64_t i, uint64_t* out,
semq_error_t* err) {
if (d == NULL || out == NULL) return SEMQI_INVALID(err, SEMQ_NONE, SEMQ_NONE, "NULL argument");
if (i >= d->n_changed) return SEMQI_INVALID(err, i, SEMQ_NONE, "index out of range");
*out = d->hamming[i];
semqi_ok(err);
return SEMQ_OK;
}
SEMQ_API uint32_t semq_diff_manifest_changes(const semq_diff_t* d) {
return d == NULL ? 0u : d->n_mchanges;
}
SEMQ_API semq_status_t semq_diff_manifest_change(const semq_diff_t* d, uint32_t i,
semq_manifest_change_t* out, semq_error_t* err) {
if (d == NULL || out == NULL) return SEMQI_INVALID(err, SEMQ_NONE, SEMQ_NONE, "NULL argument");
if (i >= d->n_mchanges) return SEMQI_INVALID(err, SEMQ_NONE, i, "index out of range");
*out = d->mchanges[i];
semqi_ok(err);
return SEMQ_OK;
}
static semq_status_t units_common(const semq_diff_t* d, uint64_t ri, uint64_t ci, uint32_t* units,
uint8_t* ref_symbols, uint8_t* cand_symbols, uint64_t cap,
uint64_t* count, semq_error_t* err) {
if (ri == SEMQ_NONE || ci == SEMQ_NONE) {
return SEMQI_INVALID(err, SEMQ_NONE, SEMQ_NONE, "id is absent from one side of the diff");
}
uint8_t* sa = (uint8_t*)semqi_alloc(d->ref->units);
uint8_t* sb = (uint8_t*)semqi_alloc(d->ref->units);
if (sa == NULL || sb == NULL) { semqi_free(sa); semqi_free(sb); return SEMQI_NOMEM(err); }
semqi_unpack_row(&d->ref->config, d->ref->rows + (size_t)ri * d->ref->bpv, sa);
semqi_unpack_row(&d->cand->config, d->cand->rows + (size_t)ci * d->cand->bpv, sb);
uint64_t k = 0u;
for (uint32_t u = 0u; u < d->ref->units; u++) {
if (sa[u] == sb[u]) continue;
if (k < cap) {
if (units) units[k] = u;
if (ref_symbols) ref_symbols[k] = sa[u];
if (cand_symbols) cand_symbols[k] = sb[u];
}
k++;
}
semqi_free(sa);
semqi_free(sb);
*count = k;
semqi_ok(err);
return SEMQ_OK;
}
SEMQ_API semq_status_t semq_diff_units_u64(const semq_diff_t* d, uint64_t id, uint32_t* units,
uint8_t* ref_symbols, uint8_t* cand_symbols,
uint64_t cap, uint64_t* count, semq_error_t* err) {
if (d == NULL || count == NULL) return SEMQI_INVALID(err, SEMQ_NONE, SEMQ_NONE, "NULL argument");
if (d->ref->id_kind != SEMQ_ID_U64) return SEMQI_INVALID(err, SEMQ_NONE, SEMQ_NONE, "diff ids are utf8, not u64");
return units_common(d, semqi_find_u64(d->ref, id), semqi_find_u64(d->cand, id), units, ref_symbols,
cand_symbols, cap, count, err);
}
SEMQ_API semq_status_t semq_diff_units_utf8(const semq_diff_t* d, const uint8_t* id, uint64_t len,
uint32_t* units, uint8_t* ref_symbols, uint8_t* cand_symbols,
uint64_t cap, uint64_t* count, semq_error_t* err) {
if (d == NULL || count == NULL || (len > 0u && id == NULL)) {
return SEMQI_INVALID(err, SEMQ_NONE, SEMQ_NONE, "NULL argument");
}
if (d->ref->id_kind != SEMQ_ID_UTF8) return SEMQI_INVALID(err, SEMQ_NONE, SEMQ_NONE, "diff ids are u64, not utf8");
return units_common(d, semqi_find_utf8(d->ref, id, len), semqi_find_utf8(d->cand, id, len), units,
ref_symbols, cand_symbols, cap, count, err);
}