Crate bitcannon 

bitcannon — GPT-family pre-tokenization as a bitstream program, replacing the scalar FSMs.

Follows Interleaved Bitstream Execution for Multi-Pattern Regex Matching on GPUs (MICRO’25, doi 10.1145/3725843.3756052). The paper’s two ideas that carry over to a CPU:

1. Bit-parallel regex. Compile the grammar into character-class bitstreams (one bit per input byte) plus boolean ops and carry-propagating adds. 64 input bytes are decided per 64-bit register op, branchlessly — the FSM’s per-token unpredictable branch disappears.
2. Interleaved execution. Do NOT run one loop per bitstream instruction over the whole input (that is the “sequential” baseline the paper beats: every intermediate stream is materialised and re-read). Instead fuse all instructions into ONE block-wise loop, so an intermediate stream lives in a register for the ~100 ops it is needed and dies there. The only thing that reaches memory is the final starts bitmap (n/8 bytes).

The paper’s third contribution (dependency-aware thread-data mapping) is a GPU concern — it resolves cross-block dependencies by recomputing them on other SMs. On one core the blocks are visited in order, so those dependencies are carried in a handful of scalar registers and, for the one genuinely backward-in-time rule, patched into the already-written bitmap.

We do not re-derive character classes: classify already emits one Atom tag per byte. The builder folds those 16 atoms into a grammar-specific dense 3-bit code and extracts 3 bit-planes of it; every class stream is then a 2–3 op boolean function of the planes.

Grammars: bitcannon_deepseek, bitcannon_byte_level (GPT-2), bitcannon_cl100k. All three byte-exact with the oniguruma oracle over a block-phase sweep — see tests/parity.rs.

Re-exports

pub use models::cl100k::bitcannon_cl100k;

pub use models::cl100k::bitcannon_qwen;

pub use models::deepseek::bitcannon_deepseek;

pub use models::gpt2::bitcannon_byte_level;

pub use models::kimi::bitcannon_kimi;

pub use models::o200k::bitcannon_o200k;

pub use models::tekken::bitcannon_tekken;

Modules

classes

The class-run family: \w+|[^\w\s]+, BERT’s basic split, digit runs, punctuation isolation. Not regex-shaped – these cut where the atom class changes, so one shape (class_runs_into<DROP, ISOLATE, KEEP_A>) covers all of them. Plus CharDelimiterSplit, the only one that keys on a literal char rather than an atom class.

classify

SIMD Unicode classification: one pass mapping every codepoint to a tiny “atom” alphabet, which is what every grammar in models/ consumes. The per-arch kernels are siblings; atom_tables.rs is generated (cargo run -p bitmap_gen) and tables.rs is the layout it bakes into.

literal

Splitting on an exact string — the Metaspace ▁ delimiter (llama2 / gemma), CharDelimiterSplit, and any Split whose pattern is a plain string rather than a regex.

models

One module per pre-tokenization regex, each unrolled against the primitives in crate. Models that ship the same regex share a module — o200k covers Llama-4, gpt-oss and MiniMax-M2; cl100k covers Llama-3, GLM-4.6 and (at digit cap 1) Qwen.

regexes

Canonical GPT pre-tokenization regexes — the specification each fsm reproduces byte-for-byte under an Isolated split. This is the single source of truth: the parity oracle (tests/parity.rs) and tk-encode’s runtime recognizer both reference these consts, so the pattern a tokenizer ships, the pattern the FSM is tested against, and the pattern the pipeline recognizes can never drift apart. bitcannon never runs these at runtime — it works off the tag stream; the consts only document (and gate the tests of) the contract the FSMs implement.

Structs

Span

A token span: byte offsets [start, end) into the input. #[repr(C)] so the output buffer has a stable [start, end] layout — the pipeline reuses it with zero conversion, and it can be reinterpreted as bytes / handed across the crate boundary.

Functions

fast_builder

Whether this target builds its bitstreams with SIMD. Without it the builder is the portable byte-at-a-time reference, which is slower than the FSM this replaces – so a caller should keep its FSM path rather than route here. On x86 the kernel needs SSSE3, so this is a runtime check.

pre_tokenize

Convenience wrapper: classify + deepseek bitcannon over caller-owned scratch.