How bitcut finds the difference between two documents without ever indexing either of them.
← → step · space skip to the next event
Drift 0 is always tried first, before anything remembered. The rest are kept most-recent-first.
It holds one position per key, and only the first. A key that occurs several times in the old document keeps its earliest occurrence and drops the rest, so the index never knows all the offsets of anything — it knows one guess per key, which is then verified like any other candidate. The key is a rolling hash of a fixed-width window rather than the bytes themselves, so distinct content can collide onto one entry too. That is the opposite of the windowed search, which enumerates every occurrence inside its window and tries them in order. Building the index costs a full pass over the base, which is exactly why it is the last tier and not the first.
| Name | Default in the crate | What it decides |
|---|---|---|
| MIN_MATCH | 16 | below this, a copy costs more than the literal it replaces |
| ANCHOR | 32 | length of the fragment searched for |
| VERIFY | 64 | how far a match must extend to be believed |
| GAPS | 0, 32, 128, 512, 2048 | offsets the anchor is taken from |
| WINDOW | ±4096 | half-width of the search window in the old document |
| SKIP | = the widest gap | derived, never set on its own |
| SLOTS | 16 | how many drifts are remembered |
The presets scale everything down so the ladder is visible on a document of a few dozen bytes. One rule is not scaled and cannot be: the index is built as soon as one more round of local searching would cost as much as indexing the base outright. On a 70-byte base that is almost immediately — indexing 70 bytes is free — which is why the short presets reach the index quickly and the longer one gets to skip ahead first.