FA-72956 / Probabilistic sketches / Open access
HyperLogLog register update: register index taken from low bits · case 01
Registers are indexed by bits that also feed the rank, correlating index and rho and biasing the estimate.
ROOT CAUSE
The register index uses the low p bits instead of the top p bits.
VERIFIED REPAIR
Index registers with the top p bits of the 32-bit hash.
Unsuccessful approach: Shifting by 31-p takes an index window that is off by one bit.
Case contract
Input {p, hashes}. Each hash is reduced to its low 32 bits. The register index is the top p bits; the remaining 32-p bits, left-aligned in a 32-bit word, give rho = leading zeros + 1, and an all-zero remainder gives rho = 32 - p + 1. Each register keeps the maximum rho seen. Return the list of 2^p registers.
Why this case matters
Every HyperLogLog estimate and merge depends on registers being filled with exactly the same index and rank rule on every node.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
p = x['p']
regs = [0] * (1 << p)
for h in x['hashes']:
h = h & 0xFFFFFFFF
idx = h & ((1 << p) - 1)
w = (h << p) & 0xFFFFFFFF
if w == 0:
rho = 32 - p + 1
else:
rho = 32 - w.bit_length() + 1
regs[idx] = max(regs[idx], rho)
return regs
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['random hashes p=4',
{'hashes': [2746290842,
1214636060,
2700365353,
1518964074,
1034755027,
2745697653,
3465139052,
1408437207,
1445057485,
2277921226,
1562942113,
737304231],
'p': 4},
[0, 0, 1, 1, 1, 3, 0, 0, 2, 0, 5, 0, 1, 0, 0, 0]],
['zero suffix',
{'hashes': [268435456, 805306369, 0], 'p': 4},
[29, 29, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 1099645845504, 18446744069414584337], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093697], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3083874711,
1466456804,
1510865127,
1936358424,
4067255089,
3117812620,
1972411353,
44849429,
1601931937,
1985418595,
85937200,
4254039572,
3251348065,
1589126043,
917877929,
579573044,
1961218034,
3335656935,
2901203533,
7772599],
'p': 6},
[4,
2,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
0,
0,
0,
0,
1,
3,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
3,
0,
1,
2,
0,
2,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
2]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4027056128, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9]]],
[['random hashes p=4',
{'hashes': [2171125632,
1561077222,
723602496,
2706691026,
1511209620,
3136040843,
3466769981,
3155411258,
2996841228,
4154669796,
729019621,
4118415819],
'p': 4},
[0, 0, 1, 0, 0, 1, 0, 0, 4, 0, 4, 3, 1, 0, 0, 2]],
['zero suffix',
{'hashes': [536870912, 805306369, 0], 'p': 4},
[29, 0, 29, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 2199157473280, 18446744069414584338], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093698], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3806962188,
1832858908,
3698728279,
3051225488,
175843725,
3689096410,
2768173870,
3616306195,
1627860444,
2174172542,
333719717,
1061042192,
1370242323,
846295865,
2770467623,
3293138441,
465062010,
2842674505,
1381634835,
3297928288],
'p': 6},
[0,
0,
1,
0,
1,
0,
1,
0,
0,
0,
0,
0,
1,
0,
0,
1,
0,
0,
0,
0,
2,
0,
0,
0,
2,
0,
0,
2,
0,
0,
0,
0,
2,
0,
0,
0,
0,
0,
0,
0,
0,
3,
2,
0,
0,
2,
0,
0,
0,
4,
0,
0,
0,
1,
1,
4,
1,
0,
0,
0,
0,
0,
0,
0]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026793984, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10]]],
[['random hashes p=4',
{'hashes': [734289917,
651773559,
1520220667,
3103360296,
825191422,
1621339354,
1335447505,
589878360,
3841155756,
2779542839,
80865712,
176500380],
'p': 4},
[2, 0, 3, 4, 1, 1, 5, 0, 0, 0, 2, 1, 0, 0, 2, 0]],
['zero suffix',
{'hashes': [805306368, 805306369, 0], 'p': 4},
[29, 0, 0, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 3298669101056, 18446744069414584339], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093699], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3384855708,
1812156463,
3005153793,
531394969,
124498482,
3623700348,
147951344,
3199733155,
2393688965,
3187545175,
3855956590,
1988994126,
1804606932,
4141219565,
3126769002,
167275462,
3576137210,
376874430,
4251399446,
3255939649],
'p': 6},
[0,
1,
3,
0,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
9,
0,
1,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
1,
2,
1,
0,
2,
0,
0,
2,
0,
0,
0,
2,
0,
0,
0,
1,
0,
2]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026662912, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11]]],
[['random hashes p=4',
{'hashes': [1988219189,
3536151577,
2451850351,
1576120406,
3460144982,
53140742,
3232271618,
3606811026,
822563767,
216937224,
653771170,
789419942],
'p': 4},
[3, 0, 2, 4, 0, 1, 0, 2, 0, 3, 0, 0, 5, 3, 0, 0]],
['zero suffix',
{'hashes': [1073741824, 805306369, 0], 'p': 4},
[29, 0, 0, 28, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 4398180728832, 18446744069414584340], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093700], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3203024958,
1607094823,
2953651490,
2154876315,
2643026601,
3395013983,
4210268938,
2481149946,
2344839774,
3486311577,
1288892453,
454290413,
1419530055,
2952556834,
140911276,
3589740878,
3461903868,
1033057716,
1747761605,
1323890633],
'p': 6},
[0,
0,
4,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
2,
0,
0,
0,
3,
0,
3,
0,
1,
0,
0,
5,
0,
0,
0,
0,
0,
4,
0,
1,
0,
1,
0,
0,
2,
0,
0,
0,
1,
7,
0,
0,
1,
0,
0,
1,
1,
0,
2,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026597376, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12]]],
[['random hashes p=4',
{'hashes': [642556483,
1103189711,
3626284107,
1285976915,
1204744135,
1451808050,
3013572557,
2019910678,
1262233268,
2292419534,
3414554249,
2291441069],
'p': 4},
[0, 0, 2, 0, 4, 2, 0, 1, 1, 0, 0, 3, 1, 1, 0, 0]],
['zero suffix',
{'hashes': [1342177280, 805306369, 0], 'p': 4},
[29, 0, 0, 28, 0, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 5497692356608, 18446744069414584341], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093701], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [2768372447,
1504635470,
259812463,
1747374277,
4119487797,
3519348978,
3620444824,
2624272929,
1736966017,
2549283484,
2300450263,
2789031204,
3100346196,
426070303,
3205786177,
3828806182,
3614515608,
1431907283,
4157712463,
2369628851],
'p': 6},
[0,
0,
0,
1,
0,
0,
2,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
2,
2,
0,
0,
1,
5,
0,
0,
0,
0,
0,
0,
0,
2,
2,
0,
1,
0,
4,
0,
2,
0,
0,
0,
0,
3,
1,
0,
0,
0,
0,
2,
1,
0,
0,
0,
5,
0,
0,
0,
2,
0,
0]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026564608, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| random hashes p=4 | [0, 1, 0, 1, 0, 3, 0, 3, 0, 5, 3, 0, 1, 2, 0, 0] | [0, 0, 1, 1, 1, 3, 0, 0, 2, 0, 5, 0, 1, 0, 0, 0] | Failed |
| zero suffix | [29, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [29, 29, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Failed |
| 64-bit input truncated | [28, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 23, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [23, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Failed |
| overwrite smaller rank | [20, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Failed |
| random hashes p=6 | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 0, 0, 0, 0, 0, 0, 2, 1, 0, 1, 1, 2, 0, 1, 0, 0, 0, 0, 0, 2, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 2, 1, 3, 0, 1, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0] | [4, 2, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2] | Failed |
| empty stream | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Passed |
| top index | [9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9] | Failed |
SHA-256 / b918515e0f28a60066934d220b7e352f077f52ccd810331f198cf151cc52eda9
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
p = x['p']
regs = [0] * (1 << p)
for h in x['hashes']:
h = h & 0xFFFFFFFF
idx = (h >> (31 - p)) % (1 << p)
w = (h << p) & 0xFFFFFFFF
if w == 0:
rho = 32 - p + 1
else:
rho = 32 - w.bit_length() + 1
regs[idx] = max(regs[idx], rho)
return regs
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['random hashes p=4',
{'hashes': [2746290842,
1214636060,
2700365353,
1518964074,
1034755027,
2745697653,
3465139052,
1408437207,
1445057485,
2277921226,
1562942113,
737304231],
'p': 4},
[0, 0, 1, 1, 1, 3, 0, 0, 2, 0, 5, 0, 1, 0, 0, 0]],
['zero suffix',
{'hashes': [268435456, 805306369, 0], 'p': 4},
[29, 29, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 1099645845504, 18446744069414584337], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093697], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3083874711,
1466456804,
1510865127,
1936358424,
4067255089,
3117812620,
1972411353,
44849429,
1601931937,
1985418595,
85937200,
4254039572,
3251348065,
1589126043,
917877929,
579573044,
1961218034,
3335656935,
2901203533,
7772599],
'p': 6},
[4,
2,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
0,
0,
0,
0,
1,
3,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
3,
0,
1,
2,
0,
2,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
2]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4027056128, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9]]],
[['random hashes p=4',
{'hashes': [2171125632,
1561077222,
723602496,
2706691026,
1511209620,
3136040843,
3466769981,
3155411258,
2996841228,
4154669796,
729019621,
4118415819],
'p': 4},
[0, 0, 1, 0, 0, 1, 0, 0, 4, 0, 4, 3, 1, 0, 0, 2]],
['zero suffix',
{'hashes': [536870912, 805306369, 0], 'p': 4},
[29, 0, 29, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 2199157473280, 18446744069414584338], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093698], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3806962188,
1832858908,
3698728279,
3051225488,
175843725,
3689096410,
2768173870,
3616306195,
1627860444,
2174172542,
333719717,
1061042192,
1370242323,
846295865,
2770467623,
3293138441,
465062010,
2842674505,
1381634835,
3297928288],
'p': 6},
[0,
0,
1,
0,
1,
0,
1,
0,
0,
0,
0,
0,
1,
0,
0,
1,
0,
0,
0,
0,
2,
0,
0,
0,
2,
0,
0,
2,
0,
0,
0,
0,
2,
0,
0,
0,
0,
0,
0,
0,
0,
3,
2,
0,
0,
2,
0,
0,
0,
4,
0,
0,
0,
1,
1,
4,
1,
0,
0,
0,
0,
0,
0,
0]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026793984, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10]]],
[['random hashes p=4',
{'hashes': [734289917,
651773559,
1520220667,
3103360296,
825191422,
1621339354,
1335447505,
589878360,
3841155756,
2779542839,
80865712,
176500380],
'p': 4},
[2, 0, 3, 4, 1, 1, 5, 0, 0, 0, 2, 1, 0, 0, 2, 0]],
['zero suffix',
{'hashes': [805306368, 805306369, 0], 'p': 4},
[29, 0, 0, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 3298669101056, 18446744069414584339], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093699], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3384855708,
1812156463,
3005153793,
531394969,
124498482,
3623700348,
147951344,
3199733155,
2393688965,
3187545175,
3855956590,
1988994126,
1804606932,
4141219565,
3126769002,
167275462,
3576137210,
376874430,
4251399446,
3255939649],
'p': 6},
[0,
1,
3,
0,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
9,
0,
1,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
1,
2,
1,
0,
2,
0,
0,
2,
0,
0,
0,
2,
0,
0,
0,
1,
0,
2]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026662912, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11]]],
[['random hashes p=4',
{'hashes': [1988219189,
3536151577,
2451850351,
1576120406,
3460144982,
53140742,
3232271618,
3606811026,
822563767,
216937224,
653771170,
789419942],
'p': 4},
[3, 0, 2, 4, 0, 1, 0, 2, 0, 3, 0, 0, 5, 3, 0, 0]],
['zero suffix',
{'hashes': [1073741824, 805306369, 0], 'p': 4},
[29, 0, 0, 28, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 4398180728832, 18446744069414584340], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093700], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3203024958,
1607094823,
2953651490,
2154876315,
2643026601,
3395013983,
4210268938,
2481149946,
2344839774,
3486311577,
1288892453,
454290413,
1419530055,
2952556834,
140911276,
3589740878,
3461903868,
1033057716,
1747761605,
1323890633],
'p': 6},
[0,
0,
4,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
2,
0,
0,
0,
3,
0,
3,
0,
1,
0,
0,
5,
0,
0,
0,
0,
0,
4,
0,
1,
0,
1,
0,
0,
2,
0,
0,
0,
1,
7,
0,
0,
1,
0,
0,
1,
1,
0,
2,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026597376, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12]]],
[['random hashes p=4',
{'hashes': [642556483,
1103189711,
3626284107,
1285976915,
1204744135,
1451808050,
3013572557,
2019910678,
1262233268,
2292419534,
3414554249,
2291441069],
'p': 4},
[0, 0, 2, 0, 4, 2, 0, 1, 1, 0, 0, 3, 1, 1, 0, 0]],
['zero suffix',
{'hashes': [1342177280, 805306369, 0], 'p': 4},
[29, 0, 0, 28, 0, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 5497692356608, 18446744069414584341], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093701], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [2768372447,
1504635470,
259812463,
1747374277,
4119487797,
3519348978,
3620444824,
2624272929,
1736966017,
2549283484,
2300450263,
2789031204,
3100346196,
426070303,
3205786177,
3828806182,
3614515608,
1431907283,
4157712463,
2369628851],
'p': 6},
[0,
0,
0,
1,
0,
0,
2,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
2,
2,
0,
0,
1,
5,
0,
0,
0,
0,
0,
0,
0,
2,
2,
0,
1,
0,
4,
0,
2,
0,
0,
0,
0,
3,
1,
0,
0,
0,
0,
2,
1,
0,
0,
0,
5,
0,
0,
0,
2,
0,
0]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026564608, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| random hashes p=4 | [2, 0, 0, 0, 5, 1, 0, 1, 0, 1, 3, 1, 0, 0, 0, 0] | [0, 0, 1, 1, 1, 3, 0, 0, 2, 0, 5, 0, 1, 0, 0, 0] | Failed |
| zero suffix | [29, 0, 29, 0, 0, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [29, 29, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Failed |
| 64-bit input truncated | [27, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [23, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Failed |
| overwrite smaller rank | [0, 0, 20, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Failed |
| random hashes p=6 | [4, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 0, 0, 0, 1, 2, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 1, 0, 0, 2, 0] | [4, 2, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2] | Failed |
| empty stream | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Passed |
| top index | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 1] | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9] | Failed |
SHA-256 / afb5df5a4232df89deea8ab154dec18559c0bee6e242d4fa89c72d7948941d36
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
p = x['p']
regs = [0] * (1 << p)
for h in x['hashes']:
h = h & 0xFFFFFFFF
idx = h >> (32 - p)
w = (h << p) & 0xFFFFFFFF
if w == 0:
rho = 32 - p + 1
else:
rho = 32 - w.bit_length() + 1
regs[idx] = max(regs[idx], rho)
return regs
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['random hashes p=4',
{'hashes': [2746290842,
1214636060,
2700365353,
1518964074,
1034755027,
2745697653,
3465139052,
1408437207,
1445057485,
2277921226,
1562942113,
737304231],
'p': 4},
[0, 0, 1, 1, 1, 3, 0, 0, 2, 0, 5, 0, 1, 0, 0, 0]],
['zero suffix',
{'hashes': [268435456, 805306369, 0], 'p': 4},
[29, 29, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 1099645845504, 18446744069414584337], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093697], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3083874711,
1466456804,
1510865127,
1936358424,
4067255089,
3117812620,
1972411353,
44849429,
1601931937,
1985418595,
85937200,
4254039572,
3251348065,
1589126043,
917877929,
579573044,
1961218034,
3335656935,
2901203533,
7772599],
'p': 6},
[4,
2,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
1,
1,
1,
0,
0,
0,
0,
1,
3,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
3,
0,
1,
2,
0,
2,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
2]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4027056128, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9]]],
[['random hashes p=4',
{'hashes': [2171125632,
1561077222,
723602496,
2706691026,
1511209620,
3136040843,
3466769981,
3155411258,
2996841228,
4154669796,
729019621,
4118415819],
'p': 4},
[0, 0, 1, 0, 0, 1, 0, 0, 4, 0, 4, 3, 1, 0, 0, 2]],
['zero suffix',
{'hashes': [536870912, 805306369, 0], 'p': 4},
[29, 0, 29, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 2199157473280, 18446744069414584338], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093698], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3806962188,
1832858908,
3698728279,
3051225488,
175843725,
3689096410,
2768173870,
3616306195,
1627860444,
2174172542,
333719717,
1061042192,
1370242323,
846295865,
2770467623,
3293138441,
465062010,
2842674505,
1381634835,
3297928288],
'p': 6},
[0,
0,
1,
0,
1,
0,
1,
0,
0,
0,
0,
0,
1,
0,
0,
1,
0,
0,
0,
0,
2,
0,
0,
0,
2,
0,
0,
2,
0,
0,
0,
0,
2,
0,
0,
0,
0,
0,
0,
0,
0,
3,
2,
0,
0,
2,
0,
0,
0,
4,
0,
0,
0,
1,
1,
4,
1,
0,
0,
0,
0,
0,
0,
0]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026793984, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10]]],
[['random hashes p=4',
{'hashes': [734289917,
651773559,
1520220667,
3103360296,
825191422,
1621339354,
1335447505,
589878360,
3841155756,
2779542839,
80865712,
176500380],
'p': 4},
[2, 0, 3, 4, 1, 1, 5, 0, 0, 0, 2, 1, 0, 0, 2, 0]],
['zero suffix',
{'hashes': [805306368, 805306369, 0], 'p': 4},
[29, 0, 0, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 3298669101056, 18446744069414584339], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093699], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3384855708,
1812156463,
3005153793,
531394969,
124498482,
3623700348,
147951344,
3199733155,
2393688965,
3187545175,
3855956590,
1988994126,
1804606932,
4141219565,
3126769002,
167275462,
3576137210,
376874430,
4251399446,
3255939649],
'p': 6},
[0,
1,
3,
0,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
9,
0,
1,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
1,
2,
1,
0,
2,
0,
0,
2,
0,
0,
0,
2,
0,
0,
0,
1,
0,
2]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026662912, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11]]],
[['random hashes p=4',
{'hashes': [1988219189,
3536151577,
2451850351,
1576120406,
3460144982,
53140742,
3232271618,
3606811026,
822563767,
216937224,
653771170,
789419942],
'p': 4},
[3, 0, 2, 4, 0, 1, 0, 2, 0, 3, 0, 0, 5, 3, 0, 0]],
['zero suffix',
{'hashes': [1073741824, 805306369, 0], 'p': 4},
[29, 0, 0, 28, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 4398180728832, 18446744069414584340], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093700], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [3203024958,
1607094823,
2953651490,
2154876315,
2643026601,
3395013983,
4210268938,
2481149946,
2344839774,
3486311577,
1288892453,
454290413,
1419530055,
2952556834,
140911276,
3589740878,
3461903868,
1033057716,
1747761605,
1323890633],
'p': 6},
[0,
0,
4,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
2,
0,
0,
0,
3,
0,
3,
0,
1,
0,
0,
5,
0,
0,
0,
0,
0,
4,
0,
1,
0,
1,
0,
0,
2,
0,
0,
0,
1,
7,
0,
0,
1,
0,
0,
1,
1,
0,
2,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026597376, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12]]],
[['random hashes p=4',
{'hashes': [642556483,
1103189711,
3626284107,
1285976915,
1204744135,
1451808050,
3013572557,
2019910678,
1262233268,
2292419534,
3414554249,
2291441069],
'p': 4},
[0, 0, 2, 0, 4, 2, 0, 1, 1, 0, 0, 3, 1, 1, 0, 0]],
['zero suffix',
{'hashes': [1342177280, 805306369, 0], 'p': 4},
[29, 0, 0, 28, 0, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['64-bit input truncated',
{'hashes': [188899104129025, 5497692356608, 18446744069414584341], 'p': 5},
[23,
28,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
27,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0]],
['overwrite smaller rank',
{'hashes': [520093696, 268435712, 520093701], 'p': 4},
[0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['random hashes p=6',
{'hashes': [2768372447,
1504635470,
259812463,
1747374277,
4119487797,
3519348978,
3620444824,
2624272929,
1736966017,
2549283484,
2300450263,
2789031204,
3100346196,
426070303,
3205786177,
3828806182,
3614515608,
1431907283,
4157712463,
2369628851],
'p': 6},
[0,
0,
0,
1,
0,
0,
2,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
2,
2,
0,
0,
1,
5,
0,
0,
0,
0,
0,
0,
0,
2,
2,
0,
1,
0,
4,
0,
2,
0,
0,
0,
0,
3,
1,
0,
0,
0,
0,
2,
1,
0,
0,
0,
5,
0,
0,
0,
2,
0,
0]],
['empty stream', {'hashes': [], 'p': 4}, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
['top index',
{'hashes': [4026564608, 4160749568], 'p': 4},
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| random hashes p=4 | [0, 0, 1, 1, 1, 3, 0, 0, 2, 0, 5, 0, 1, 0, 0, 0] | [0, 0, 1, 1, 1, 3, 0, 0, 2, 0, 5, 0, 1, 0, 0, 0] | Passed |
| zero suffix | [29, 29, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [29, 29, 0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Passed |
| 64-bit input truncated | [23, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [23, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Passed |
| overwrite smaller rank | [0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Passed |
| random hashes p=6 | [4, 2, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2] | [4, 2, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2] | Passed |
| empty stream | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] | Passed |
| top index | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9] | [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9] | Passed |
SHA-256 / cbc2a03837e86ac87545f5889359709b8593fa5718c1ad9d0f360b7b38b7052d
Verification & scope
A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:48:43.018117+00:00.
Case digest / 7e7589002e73a88006c67abcb5cc8eec05468fc3a888d77206fc150beb8c6112