THE FOLD / CHEAT / THE-SPEEDRUN / THE BITAP
THE BITAP
one register that matches in parallel
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Bitap (shift-or) algorithm searches for a pattern in text using nothing but bit-shifts and bitwise-or — the whole matching state for a length-m pattern lives in one machine word. A single register R tracks, in parallel, how far every possible match has progressed: each text character shifts R left and ors in a precomputed mask for that character, and a completed match shows up as a cleared bit at position m−1. Because a CPU word processes all m positions at once, the inner loop is a couple of instructions per character — and the same trick extends to fuzzy (approximate) matching.
LIT verified live: over 5000 random text/pattern pairs, Bitap’s bit-parallel scan reports exactly the same match positions as a brute-force substring search (window.__bitap). FIG no framing; the shift-or state machine and a brute-force check run in-browser (pattern length ≤ word size).
LIT verified live: over 5000 random text/pattern pairs, Bitap’s bit-parallel scan reports exactly the same match positions as a brute-force substring search (window.__bitap). FIG no framing; the shift-or state machine and a brute-force check run in-browser (pattern length ≤ word size).
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-speedrun — one register carries every partial match at once, so the scan clears the text in a couple of instructions per character. AVAN (AI) built the instrument: the per-character masks, the shift-or state update, and the brute-force cross-check.
Credit as content: Bálint Dömölki (1964); popularized by Baeza-Yates & Gonnet (1992). The weave: David names the speedrun; I confirm the one-register bit-parallel scan finds exactly the brute-force matches.
Credit as content: Bálint Dömölki (1964); popularized by Baeza-Yates & Gonnet (1992). The weave: David names the speedrun; I confirm the one-register bit-parallel scan finds exactly the brute-force matches.
3 ONE DIMENSION
The state register as the text is scanned; a cleared bit m−1 flags a completed match at that position.
4 TWO DIMENSIONS · INTERACTIVE
A text and a pattern; Bitap marks every occurrence, and the positions match the brute-force search exactly.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the match positions the scan reports.
AVAN’s addition (the inverse-companion): don’t compare character by character — carry all partial matches in one register. The inverse of ‘test each alignment separately’ is ‘one bitmask advances every possible match in parallel; a cleared bit m−1 is a hit.’ Magenta is a mismatch that resets its bit; green is a completed match. All alignments at once.
LIT Genuine Bitap / shift-or algorithm (Bálint Dömölki, 1964; popularized by Baeza-Yates & Gonnet, 1992). Verified live: over 5000 random text/pattern pairs (pattern length ≤ word size), the one-register shift-or scan reports exactly the same match positions as a brute-force substring search (window.__bitap.matchesBrute).
FIG No framing: the shift-or state machine and a brute-force check run in-browser (pattern length ≤ word size). The AVAN inverse is honest — instead of testing each alignment separately, one register carries every partial match at once: a bitmask advances all possible matches in parallel, and a cleared bit m−1 is a hit. Magenta is a mismatch that resets its bit; green is a completed match. All alignments at once.
FIG No framing: the shift-or state machine and a brute-force check run in-browser (pattern length ≤ word size). The AVAN inverse is honest — instead of testing each alignment separately, one register carries every partial match at once: a bitmask advances all possible matches in parallel, and a cleared bit m−1 is a hit. Magenta is a mismatch that resets its bit; green is a completed match. All alignments at once.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-SPEEDRUN · David Lee Wise (ROOT0), with AVAN