Expand description
Incremental FNV-1a 64-bit checksum maintenance for the buffer’s rope.
The persisted buffer_edits.checksum_after column carries the FNV-1a
64-bit hash of the rope’s bytes at each revision. Recovery replays the
edit log and halts the first time the replayed rope’s hash diverges
from the stored checksum (see continuity-persist’s recovery path).
Computing that hash by walking the entire rope on every persisted edit costs O(rope_bytes) per edit; on a ~711 KB buffer this is ~1 ms p99 — about 3 % of the keystroke budget at the time of writing, and linear in buffer size.
FNV-1a’s per-byte step is state = (state ^ byte) * FNV_PRIME. The
prime is odd, so it is invertible modulo 2^64, and a single mix
step can be peeled off the tail of the running state with
state = (state * FNV_PRIME_INV) ^ byte. We exploit this to update
the running hash for an edit in O(suffix_bytes + edit_bytes) instead
of O(rope_bytes): unmix the bytes after the edit point, mix in the
new (and unmix the removed) bytes, then re-mix the suffix.
For an append-at-the-end edit the suffix is empty and the cost is O(edit_bytes); mid-rope edits in large buffers still touch the suffix but never the prefix.
A periodic full-walk verification (every CHECKSUM_VERIFY_INTERVAL
edits or at snapshot boundary, driven by the core thread) bounds
damage from any algebraic mistake to that interval and surfaces it
through event:checksum_drift.
Constants§
- CHECKSUM_
VERIFY_ INTERVAL - Periodic verification cadence — the core thread runs a full-walk cross-check every this-many persisted edits per buffer (and at snapshot boundaries). Bounds drift damage to one interval.
- FNV_
OFFSET_ BASIS - FNV-1a 64-bit offset basis. Same constant used by
[
continuity_persist::fnv1a_64]; the running state for an empty rope is exactly this value. - FNV_
PRIME - FNV-1a 64-bit prime.
- FNV_
PRIME_ INV - Multiplicative inverse of
FNV_PRIMEmodulo2^64. Computed at compile time from the Newton–Raphson recurrencex_{k+1} = x_k * (2 - a * x_k)(mod2^64), which doubles the number of correct low bits each iteration; six iterations fromx_0 = 1(correct mod 2) take us past 64 bits.
Functions§
- full_
walk_ rope - Full FNV-1a hash of
rope’s bytes. The verification-path fallback and the initial running state for newly constructed buffers both route through here. - mix_
byte - One forward FNV-1a step. Pure.
- unmix_
byte - One inverse FNV-1a step — peels the last
byteoff the running state. Correct only whenbytewas the most recently mixed byte; to unmix a sequence, call this back-to-front. Pure. - update_
for_ edit - Update
old_state(the running FNV-1a hash ofrope_afterbeforeopwas applied) to the new running hash afterophas applied to the rope.rope_aftermust be the post-apply rope;removed_textis the substringopremoved (empty forEditOp::Insert).