volt
7378f65189
The module's docstring claims 'results match the C reference' and no cell
graded it: _MULT ...1757->...1751 and the md5 hi^lo fold -> hi both passed
7/7 while remapping 99.0% and 99.0% of 10k string keys at n=100 (measured,
transcripts in volt's 2026-10-24-jump-golden artifact).
- jump_ref.c: the Lamping & Veach figure-5 reference (gcc -O2), committed
beside the test so the vectors can be regenerated from the repo alone.
Measured against the Python module on 630,910 (key, n) pairs: 0 mismatch.
- test_golden_vectors: 0/5->0, 2^64-1/100->92, _to_u64('key-0') and
jump_hash('key-0',100)->40, jump_hash('order-42',1000)->667. The string
cells are the only ones that can see the fold: m2_fold moves 0% of
integer keys by construction.
- test_minimal_movement: lower bound at 0.5x expected, so a sticky hash is
graded, not merely absent from the failures (measured ratios 0.974-1.047).
- test_uniformity_other_bucket_count: n=97 prime, +/-10%, observed -5.28/+4.57.
Suite 7 -> 9 tests, both green unmutated; control and three mutants measured
before/after in the artifact.
41 lines
1.4 KiB
C
41 lines
1.4 KiB
C
/* ref.c -- Lamping & Veach (2014), the reference form: 64-bit wrapping
|
|
* multiply, and the jump computed with a double, exactly as published in
|
|
* "A Fast, Minimal Memory, Consistent Hash Algorithm", figure 5.
|
|
*
|
|
* This file exists so the Python module's docstring claim ("results match the
|
|
* C reference") can be graded against an implementation the Python module did
|
|
* not write, rather than against itself. Nothing here mirrors the Python
|
|
* control flow: the loop, the multiply and the double division are the
|
|
* paper's, and the key comes from stdin, not from a hash fold.
|
|
*
|
|
* stdin: one "<u64> <n>" pair per line, n <= 2^31-1
|
|
* stdout: "<u64> <n> <bucket>"
|
|
*/
|
|
#include <stdio.h>
|
|
#include <stdint.h>
|
|
#include <stdlib.h>
|
|
|
|
static int32_t jump_ref(uint64_t key, int32_t num_buckets) {
|
|
int64_t b = -1, j = 0;
|
|
while (j < num_buckets) {
|
|
b = j;
|
|
key = key * 2862933555777941757ULL + 1;
|
|
j = (int64_t)((double)(b + 1) * (double)(1LL << 31) /
|
|
(double)((key >> 33) + 1));
|
|
}
|
|
return (int32_t)b;
|
|
}
|
|
|
|
int main(void) {
|
|
unsigned long long k;
|
|
long n;
|
|
while (scanf("%llu %ld", &k, &n) == 2) {
|
|
if (n < 1 || n > 2147483647L) {
|
|
fprintf(stderr, "ref: n out of range: %ld\n", n);
|
|
return 2;
|
|
}
|
|
printf("%llu %ld %d\n", k, n, jump_ref((uint64_t)k, (int32_t)n));
|
|
}
|
|
return 0;
|
|
}
|