Skip to main content

Module checksum

Module checksum 

Source
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_PRIME modulo 2^64. Computed at compile time from the Newton–Raphson recurrence x_{k+1} = x_k * (2 - a * x_k) (mod 2^64), which doubles the number of correct low bits each iteration; six iterations from x_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 byte off the running state. Correct only when byte was 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 of rope_after before op was applied) to the new running hash after op has applied to the rope. rope_after must be the post-apply rope; removed_text is the substring op removed (empty for EditOp::Insert).