bitcannon/

lib.rs

//! `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`.

/// Declares a grammar's block-local class streams, and with them the two carried shifts every
/// rule needs: `back` — what held one position earlier, carrying in the previous block's last
/// bit — and `fwd`, one position later, carrying in the next block's first bit.
///
/// This is the whole cross-block story. Keeping the carry in the *stream* instead of passing it at
/// every call site is what lets a rule read as plain stream algebra: "a run starts where this class
/// holds and the position before it did not" is `x & lead & !bk.x`, exact at a block edge. Before
/// this, each grammar rebuilt the edge byte's class into a `u16` mask (`code_bits`/`bits_at`) and
/// threaded it through every shift by hand — so the boundary byte got classified twice, once by the
/// builder and again scalar-side.
macro_rules! streams {
    ($(#[$m:meta])* $name:ident { $($f:ident),+ $(,)? }) => {
        $(#[$m])*
        #[derive(Clone, Copy, Default)]
        pub(crate) struct $name { $(pub(crate) $f: u64,)+ }

        impl $name {
            /// Every stream shifted one position later, carrying in `p`'s last bit.
            #[inline]
            pub(crate) fn back(&self, p: &Self) -> Self {
                Self { $($f: (self.$f << 1) | (p.$f >> 63),)+ }
            }

            /// Every stream shifted one position earlier, carrying in `n`'s first bit.
            #[inline]
            pub(crate) fn fwd(&self, n: &Self) -> Self {
                Self { $($f: (self.$f >> 1) | (n.$f << 63),)+ }
            }
        }

        impl crate::Streams for $name {
            #[inline]
            fn back(&self, p: &Self) -> Self { $name::back(self, p) }
            #[inline]
            fn fwd(&self, n: &Self) -> Self { $name::fwd(self, n) }
            #[inline]
            fn lead(&self) -> u64 { self.lead }
        }
    };
}

/// A grammar's class-stream set, as generated by [`streams!`]. Every grammar declares `lead` and
/// `cont`, because the driver needs them for the char-boundary geometry.
pub(crate) trait Streams: Copy + Default {
    fn back(&self, p: &Self) -> Self;
    fn fwd(&self, n: &Self) -> Self;
    fn lead(&self) -> u64;
}

/// Everything a rule needs about one block, prepared once by [`blocks`] instead of re-derived by
/// every grammar: the previous / current / next blocks, both carried shifts, and the geometry.
pub(crate) struct Ctx<C> {
    /// the previous block's streams (all-zero before the first)
    pub pv: C,
    pub cur: C,
    /// the next block's streams (all-zero past the last)
    pub nx: C,
    /// `cur` one position later, carrying in `pv`'s last bit — "what held just before here"
    pub bk: C,
    /// `cur` one position earlier, carrying in `nx`'s first bit — "what holds just after here"
    pub fw: C,
    pub bi: usize,
    pub base: usize,
    pub len: usize,
    /// bits inside this block (`!0` for a full one)
    pub valid: u64,
    pub last_blk: bool,
    /// this position is the LAST byte of its char (the input's final byte counts)
    pub lb: u64,
    /// the input's final byte as a bit, else 0
    pub eof: u64,
}

/// What a rule returns for its block: the token-start bitmap, a patch OR-ed into the *previous*
/// block (a char straddling the edge lands its lead in the word already written), and a mask
/// AND-ed with the FINISHED starts to fill the `flag` bitmap. Returning the mask rather than
/// writing `flag` keeps `& lead` and the "position 0 always opens a token" rule in one place —
/// three grammars were redoing both just to see the final `st`.
pub(crate) struct Out {
    pub st: u64,
    pub patch: u64,
    pub flag: u64,
}

/// The edge bits of a carried stream: `was` is the previous block's last, `will` the next block's
/// first. Every grammar defined these as local closures.
#[inline]
pub(crate) fn was(v: u64) -> bool {
    v >> 63 != 0
}

#[inline]
pub(crate) fn will(v: u64) -> bool {
    v & 1 != 0
}

/// Drive a grammar block by block with one block of lookahead.
///
/// This owns everything that is *not* grammar — block geometry, the fill-seed threading (inside
/// `build`'s captures), the previous/current/next rotation, both carried shifts, `lb`, the eof bit,
/// and the starts assembly, plus the fill seed. A grammar supplies its atom table, its plane decode
/// and its rules; nothing else. `rule` also gets `starts` because one rule (deepseek's `anl`) retracts a
/// start it committed in an earlier block.
#[inline]
pub(crate) fn blocks<C, S, B, R>(
    ntext: usize,
    starts: &mut [u64],
    mut flag: Option<&mut [u64]>,
    seed0: S,
    mut build: B,
    mut rule: R,
) where
    C: Streams,
    B: FnMut(usize, usize, S) -> (C, S),
    R: FnMut(&Ctx<C>, &mut [u64]) -> Out,
{
    // The fill seed — the class of the byte before a block, so one opening mid-char keeps
    // inheriting its lead's. Threaded here rather than through a mutable capture in every grammar.
    let mut seed = seed0;
    let nblk = ntext.div_ceil(64);
    let blen = |bi: usize| (ntext - bi * 64).min(64);
    let mut pv = C::default();
    let (mut cur, s) = build(0, blen(0), seed);
    seed = s;

    for bi in 0..nblk {
        let base = bi * 64;
        let len = blen(bi);
        let last_blk = base + len == ntext;
        // built BEFORE this block is processed, which is what makes `fw` a real carry
        let nx = if last_blk {
            C::default()
        } else {
            let (c, s) = build(base + 64, blen(bi + 1), seed);
            seed = s;
            c
        };
        let valid = if len == 64 { !0u64 } else { (1u64 << len) - 1 };
        let eof = if last_blk { 1u64 << (len - 1) } else { 0 };
        let bk = cur.back(&pv);
        let fw = cur.fwd(&nx);
        let ctx = Ctx {
            pv,
            cur,
            nx,
            bk,
            fw,
            bi,
            base,
            len,
            valid,
            last_blk,
            lb: (fw.lead() & valid) | eof,
            eof,
        };
        let o = rule(&ctx, starts);
        let mut st = o.st & cur.lead();
        if bi == 0 {
            st |= 1; // position 0 always opens a token
        }
        starts[bi] = st;
        if let Some(f) = flag.as_deref_mut() {
            f[bi] = st & o.flag;
        }
        if bi > 0 {
            starts[bi - 1] |= o.patch;
        }
        pv = cur;
        cur = nx;
    }
}

pub mod classes;
pub mod classify;
pub mod literal;
pub mod models;
pub mod regexes;
mod simd;

pub use models::cl100k::{bitcannon_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;

/// 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.
#[repr(C)]
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default, Hash, PartialOrd, Ord)]
pub struct Span {
    pub start: u32,
    pub end: u32,
}

impl Span {
    #[inline]
    #[must_use]
    pub const fn new(start: u32, end: u32) -> Self {
        Self { start, end }
    }

    /// `[start, end)` as a `usize` range — for slicing the input text.
    #[inline]
    #[must_use]
    pub fn range(self) -> core::ops::Range<usize> {
        self.start as usize..self.end as usize
    }
}

impl PartialEq<(u32, u32)> for Span {
    fn eq(&self, other: &(u32, u32)) -> bool {
        self.start == other.0 && self.end == other.1
    }
}

/// 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.
#[must_use]
pub fn fast_builder() -> bool {
    #[cfg(target_arch = "aarch64")]
    {
        true
    }
    #[cfg(target_arch = "x86_64")]
    {
        has_ssse3()
    }
    #[cfg(not(any(target_arch = "aarch64", target_arch = "x86_64")))]
    {
        false
    }
}

#[cfg(target_arch = "x86_64")]
pub(crate) fn has_ssse3() -> bool {
    use std::sync::atomic::{AtomicU8, Ordering};
    static CACHED: AtomicU8 = AtomicU8::new(0);
    match CACHED.load(Ordering::Relaxed) {
        0 => {
            let yes = std::arch::is_x86_feature_detected!("ssse3");
            CACHED.store(1 + u8::from(yes), Ordering::Relaxed);
            yes
        }
        n => n == 2,
    }
}

pub(crate) const CONT: u8 = 15; // Atom::Cont
pub(crate) const CODE_CONT: u8 = 7; // every grammar's dense code for a continuation byte

/// What a grammar wants in the text-derived `Blk::aux` stream. Tag-derived classes go through the
/// LUT; these three need the raw bytes, so they are the one thing the builder reads `text` for.
pub(crate) const AUX_NONE: u8 = 0;
pub(crate) const AUX_CJK: u8 = 1; // deepseek Split-2: Han U+4E00..9FA5 ∪ kana U+3040..30FF
pub(crate) const AUX_SLASH: u8 = 2; // o200k rule 4's `[\r\n/]*` tail

/// The bitstreams for one 64-byte block. `p0`..`p3` are the bit-planes of the **filled** dense
/// code — filled meaning a multi-byte char sets its bits on *all* of its bytes, so "previous char's
/// class" is a plain `<< 1` and no rule does char-width arithmetic. `cont` is the one un-filled
/// stream (it defines the fill); `aux` is text-derived and only built when a grammar asks for it.
///
/// `p3` exists because o200k needs 9 tag classes (U/L/C/N/NL/SP/WSO/OTHER + cont) and code 7 is
/// reserved — the SIMD kernels find continuation lanes by testing `lut[tag] == 7`, so "other"
/// cannot be the leftover code. It is const-gated off for the 3-plane grammars.
#[derive(Default, Clone, Copy)]
pub(crate) struct Blk {
    pub cont: u64,
    pub p0: u64,
    pub p1: u64,
    pub p2: u64,
    pub p3: u64,
    pub aux: u64,
}

/// deepseek Split-2's isolated range: Han U+4E00..9FA5 ∪ Hiragana/Katakana U+3040..30FF (all
/// 3-byte, leads E3..E9). Same predicate as `fsm_deepseek`'s `ds_is_cjk_at`.
#[inline]
pub(crate) fn is_cjk_at(text: &[u8], p: usize) -> bool {
    let b = text[p];
    if !(0xE3..=0xE9).contains(&b) || p + 2 >= text.len() {
        return false;
    }
    let cp = ((b as u32 & 0x0F) << 12)
        | ((text[p + 1] as u32 & 0x3F) << 6)
        | (text[p + 2] as u32 & 0x3F);
    (0x4E00..=0x9FA5).contains(&cp) || (0x3040..=0x30FF).contains(&cp)
}

/// The `AUX` predicate at a lead byte.
#[inline]
pub(crate) fn aux_at<const AUX: u8>(text: &[u8], p: usize) -> bool {
    match AUX {
        AUX_CJK => is_cjk_at(text, p),
        AUX_SLASH => text[p] == b'/',
        _ => false,
    }
}

/// Build one block. Full blocks go through the NEON kernel; the ragged tail (and every other
/// target) uses the portable byte-at-a-time reference. Both produce the identical `Blk`.
/// `lut` is the grammar's tag → dense code table.
#[inline]
pub(crate) fn build_block<const AUX: u8, const P3: bool>(
    text: &[u8],
    tags: &[u8],
    base: usize,
    len: usize,
    lut: &[u8; 64],
    cur_code: u8,
    cur_aux: bool,
) -> (Blk, u8) {
    #[cfg(target_arch = "aarch64")]
    if len == 64 {
        // SAFETY: `len == 64` means `base + 64 <= text.len() == tags.len()`.
        return unsafe {
            crate::simd::neon::build64::<AUX, P3>(text, tags, base, lut, cur_code, cur_aux)
        };
    }
    #[cfg(target_arch = "x86_64")]
    if len == 64 && has_ssse3() {
        // SAFETY: `len == 64` bounds both reads, and SSSE3 is checked above.
        return unsafe {
            crate::simd::x86::build64::<AUX, P3>(text, tags, base, lut, cur_code, cur_aux)
        };
    }
    build_block_scalar::<AUX, P3>(text, tags, base, len, lut, cur_code, cur_aux)
}

/// Portable reference builder: one byte at a time.
pub(crate) fn build_block_scalar<const AUX: u8, const P3: bool>(
    text: &[u8],
    tags: &[u8],
    base: usize,
    len: usize,
    lut: &[u8; 64],
    mut cur_code: u8,
    mut cur_aux: bool,
) -> (Blk, u8) {
    let mut b = Blk::default();
    for i in 0..len {
        let p = base + i;
        let bit = 1u64 << i;
        if tags[p] == CONT {
            b.cont |= bit;
        } else {
            cur_code = lut[tags[p] as usize];
            cur_aux = AUX != AUX_NONE && aux_at::<AUX>(text, p);
        }
        b.p0 |= bit * u64::from(cur_code & 1 != 0);
        b.p1 |= bit * u64::from(cur_code & 2 != 0);
        b.p2 |= bit * u64::from(cur_code & 4 != 0);
        if P3 {
            b.p3 |= bit * u64::from(cur_code & 8 != 0);
        }
        b.aux |= bit * u64::from(cur_aux);
    }
    (b, cur_code)
}

// ── bitstream primitives ────────────────────────────────────────────────────────────────────────

/// `ScanThru`: move every marker in `m` forward past the run of `c` it sits in, landing on the
/// first position not in `c`. The classic Parabix carry-propagation trick — one add. Done in `u128`
/// so a run reaching bit 63 puts its landing bit at 64 instead of vanishing: that bit *is* the
/// block's carry-out, and `e - m` still yields the right in-block span.
#[inline]
pub(crate) const fn scanthru(m: u128, c: u128) -> u128 {
    m.wrapping_add(c) & !c
}

/// Advance markers by ONE CHAR: shift one byte, then scan through the continuation bytes. Markers
/// that leave the block are dropped — their state is reconstructed from the scalar carry instead.
#[inline]
pub(crate) const fn adv(m: u64, cont: u64) -> u64 {
    scanthru((m as u128) << 1, cont as u128) as u64
}

/// Move each bit back to the lead byte of its char. Rules that look at the *next* char are stated
/// at a char's last byte; token starts must sit on leads. ≤3 steps (UTF-8 chars are ≤4 bytes).
/// Returns `(in-block, patch for the previous word)` — a char straddling the block boundary lands
/// its lead in the word we already wrote.
#[inline]
pub(crate) fn to_lead(x: u64, cont: u64, prev_cont: u64) -> (u64, u64) {
    let c = ((cont as u128) << 64) | prev_cont as u128;
    let mut y = (x as u128) << 64;
    for _ in 0..3 {
        let m = y & c;
        if m == 0 {
            break;
        }
        y = (y & !c) | (m >> 1);
    }
    ((y >> 64) as u64, y as u64)
}

/// The span from each marker of `m` forward to the END of the run of `c` it sits in, landing
/// EXCLUDED. `c` may be any combination of class streams — it is just a bitmask.
///
/// This is the closure operator, and the one the spec called `MatchStar`. Its doc used to have the
/// direction backwards ("fill from the run start through the LAST marker"), which is why callers
/// reached for it through `reverse_bits` pairs and hand-rolled their smears instead of calling it.
/// Reversed, "forward to the end of the run" reads as "is there a marker at or after me, still
/// inside this run?" — that is [`later_in_run`].
///
/// Parabix's `MatchStar` includes the position the run stops on. No rule here wants that: a rule
/// needs either the span without the landing (this) or the landing alone ([`scanthru`]). Should one
/// ever need both, it is `fill_to_last(m, c) | scanthru(m, c) as u64`.
#[inline]
pub(crate) fn fill_to_last(m: u64, c: u64) -> u64 {
    if m == 0 {
        return 0;
    }
    let (m128, c128) = (m as u128, c as u128);
    (scanthru(m128, c128).wrapping_sub(m128) | m128) as u64
}

/// **Backward.** For every position, is there a marker of `m` at or after it, inside the same run of
/// `c`? [`fill_to_last`] spans forward from a marker, so reversed it answers exactly this. All three
/// grammars spelled it out as a `reverse_bits` triple.
#[inline]
pub(crate) fn later_in_run(m: u64, c: u64) -> u64 {
    fill_to_last(m.reverse_bits(), c.reverse_bits()).reverse_bits()
}

/// Absolute position of the highest set bit of `x`, for a block starting at `base` (`x != 0`).
#[inline]
pub(crate) fn last_pos(base: usize, x: u64) -> usize {
    base + 63 - x.leading_zeros() as usize
}

/// `\p{N}{1,cap}` across a block edge: how many digits of the current group the run has consumed by
/// the time it leaves this block. `groups` are this block's group starts, `tn` its trailing digit
/// run. Identical in cl100k and the o200k family, so it lives here.
#[inline]
fn digits_since(groups: u64, tn: u64, n: u64, lead: u64, since: u32, cap: usize) -> u32 {
    let g = groups & tn;
    let counted = if g == 0 {
        since + (n & lead & tn).count_ones()
    } else {
        (n & lead & tn & !((1u64 << (63 - g.leading_zeros())) - 1)).count_ones()
    };
    if cap == 0 || cap >= 64 {
        counted
    } else {
        counted % cap as u32
    }
}

/// `\p{N}{1,cap}` across block edges: whether a digit run is still open at the edge, and how far
/// into its current group it got. All three grammars kept exactly this pair, recomputed it with the
/// same `trail_run`, and two of them spelled the counter out identically.
#[derive(Default)]
pub(crate) struct Digits {
    open: bool,
    since: u32,
}

impl Digits {
    /// This block's group starts: a boundary every `cap` chars from the run start.
    pub(crate) fn starts(
        &self,
        cap: usize,
        n: u64,
        lead: u64,
        cont: u64,
        prev_is_digit: bool,
    ) -> u64 {
        digit_groups(cap, n, lead, cont, prev_is_digit, self.open, self.since)
    }

    /// Carry the run into the next block. `next_is_digit` is that block's first byte.
    // Every one of these is a live bitstream register at the call site; bundling them into a
    // struct would only put an indirection between the driver and the carry it just computed.
    #[allow(clippy::too_many_arguments)]
    pub(crate) fn commit(
        &mut self,
        cap: usize,
        groups: u64,
        n: u64,
        lead: u64,
        valid: u64,
        len: usize,
        next_is_digit: bool,
    ) {
        let tn = trail_run(n, valid, len);
        self.open = tn != 0 && next_is_digit;
        self.since = if self.open {
            digits_since(groups, tn, n, lead, self.since, cap)
        } else {
            0
        };
    }
}

/// `\s*[\r\n]+` versus `\s+(?!\S)`: the one backward-in-time rule these grammars have. `\s*[\r\n]+`
/// runs through a whitespace run's LAST newline, so a token opens right after it — but a newline
/// arriving in a LATER block moves which newline is last, retracting a start already written. All
/// three grammars carried this verbatim, comments included; it lives here instead.
#[derive(Default)]
pub(crate) struct Anl(Option<usize>);

impl Anl {
    /// Top of a block: a newline has arrived inside the run that was open at the edge, so the start
    /// committed for it is no longer after the last newline.
    pub(crate) fn retract(
        &mut self,
        starts: &mut [u64],
        prev_ws: bool,
        ws: u64,
        nl: u64,
        valid: u64,
    ) {
        if let Some(p) = self.0
            && prev_ws
            && ws & 1 != 0
            && nl & lead_run(ws, valid) != 0
        {
            starts[p / 64] &= !(1u64 << (p % 64));
            self.0 = None;
        }
    }

    /// Bottom of a block: remember the start a later newline could still retract. `absorbed` is what
    /// a punct run's `[\r\n]*` tail already claimed — a bit that tail made a run start cannot be
    /// reached back past, because the absorption cut the whitespace run.
    pub(crate) fn commit(
        &mut self,
        base: usize,
        after_nl: u64,
        tws: u64,
        absorbed: u64,
        ws_next: bool,
        prev_ws: bool,
    ) {
        if tws != 0 && ws_next {
            let a = after_nl & tws & !absorbed;
            if a != 0 {
                self.0 = Some(last_pos(base, a));
            } else if !(tws & 1 != 0 && prev_ws) {
                self.0 = None; // a fresh run with no newline yet — nothing left to retract
            }
        } else {
            self.0 = None;
        }
    }
}

/// Run of `x` that starts at bit 0.
#[inline]
pub(crate) fn lead_run(x: u64, valid: u64) -> u64 {
    let z = !x & valid;
    if z == 0 {
        valid
    } else {
        (z & z.wrapping_neg()) - 1
    }
}

/// Run of `x` that ends at bit `len - 1` (0 if that bit is clear).
#[inline]
pub(crate) fn trail_run(x: u64, valid: u64, len: usize) -> u64 {
    if x & (1u64 << (len - 1)) == 0 {
        return 0;
    }
    let z = !x & valid;
    if z == 0 {
        valid
    } else {
        valid & !((1u64 << (64 - z.leading_zeros())) - 1)
    }
}

/// `\p{N}{1,cap}` — a group boundary every `cap` chars from the run start. The one non-local rule
/// in every tiktoken-family grammar, so it lives here rather than three times over.
///
/// `cap == 0` or `>= 64` means an unbounded `\p{N}+`: the run is one token and there is nothing to
/// do (and the shifts below would be UB). `dig_since` resumes a run that crossed the block edge —
/// re-masking with `n` at every hop matters, because the carry only says the byte *at* the edge was
/// a digit, not that the run survived it.
#[inline]
fn digit_groups(
    cap: usize,
    n: u64,
    lead: u64,
    cont: u64,
    prev_is_digit: bool,
    dig_run: bool,
    dig_since: u32,
) -> u64 {
    let mut m = n & lead & !((n << 1) | u64::from(prev_is_digit));
    if cap == 0 || cap >= 64 {
        return m; // an unbounded `\p{N}+`: the run is one token
    }
    let capu = cap as u32;
    if dig_run && prev_is_digit {
        let mut s = lead & lead.wrapping_neg() & n; // first lead of the block
        for _ in 0..((capu - dig_since % capu) % capu) {
            s = adv(s, cont) & n & lead;
        }
        m |= s;
    }
    let mut groups = m;
    if n & cont == 0 {
        // Fast path: every digit here is single-byte, so "CAP chars on" is a plain shift against a
        // mask asking that the skipped positions were digits too — what the `adv` chain checks.
        let mut nk = n;
        let mut k = 1;
        while k < cap {
            nk &= n << k;
            k += 1;
        }
        while m != 0 {
            m = (m << cap) & nk;
            groups |= m;
        }
    } else {
        while m != 0 {
            let mut e = m;
            for _ in 0..cap {
                e = adv(e, cont) & n & lead;
            }
            if e == 0 {
                break;
            }
            groups |= e;
            m = e;
        }
    }
    groups
}

// ── emit ────────────────────────────────────────────────────────────────────────────────────────

/// `starts` bitmap → spans. Each set bit closes the previous token and opens the next; `tzcnt`
/// walks them at ~3 ops per token. A bit also set in `fake` closes but opens nothing — that is how
/// the class-run family expresses a *dropped* run: it is a boundary, not a token. Pass `&[]` when
/// every start is a real one.
pub(crate) fn emit(starts: &[u64], fake: &[u64], nblk: usize, n: usize, out: &mut [Span]) -> usize {
    let (mut w, mut open) = (0usize, u32::MAX);
    for (bi, &word) in starts.iter().enumerate().take(nblk) {
        let mut m = word;
        while m != 0 {
            let t = m.trailing_zeros() as usize;
            let pos = (bi * 64 + t) as u32;
            if open != u32::MAX {
                out[w] = Span::new(open, pos);
                w += 1;
            }
            open = if fake.get(bi).is_some_and(|f| f >> t & 1 != 0) {
                u32::MAX
            } else {
                pos
            };
            m &= m - 1;
        }
    }
    if open != u32::MAX {
        out[w] = Span::new(open, n as u32);
        w += 1;
    }
    w
}

/// Byte length of the contraction at `i` (2 or 3), or 0. `ci` picks cl100k/o200k's `(?i:)` form
/// over GPT-2's case-sensitive one.
#[inline]
pub(crate) fn contr_len(text: &[u8], i: usize, ci: bool) -> usize {
    let n = text.len();
    if i + 1 >= n || text[i] != b'\'' || text[i + 1] >= 0x80 {
        return 0;
    }
    let c1 = if ci { text[i + 1] | 0x20 } else { text[i + 1] };
    match c1 {
        b's' | b't' | b'm' | b'd' => 2,
        b'r' | b'v' | b'l' if i + 2 < n && text[i + 2] < 0x80 => {
            let c2 = if ci { text[i + 2] | 0x20 } else { text[i + 2] };
            usize::from((matches!(c1, b'r' | b'v') && c2 == b'e') || (c1 == b'l' && c2 == b'l')) * 3
        }
        _ => 0,
    }
}

/// Builder-only cost probe: runs just the byte→bitstream transpose over every block and folds the
/// streams so nothing is optimised away. The difference against a full grammar is what the
/// bitstream program itself costs.
#[doc(hidden)]
#[must_use]
pub fn build_only(text: &[u8], tags: &[u8]) -> u64 {
    let (mut acc, mut code, mut cjk) = (0u64, CODE_CONT, false);
    for base in (0..text.len()).step_by(64) {
        let len = (text.len() - base).min(64);
        let (b, c) = build_block::<{ AUX_CJK }, false>(
            text,
            tags,
            base,
            len,
            &models::deepseek::LUT,
            code,
            cjk,
        );
        code = c;
        cjk = b.aux >> (len - 1) & 1 != 0;
        acc ^= b.cont ^ b.p0 ^ b.p1 ^ b.p2 ^ b.aux;
    }
    acc
}

/// Convenience wrapper: classify + deepseek bitcannon over caller-owned scratch.
#[must_use]
pub fn pre_tokenize(text: &[u8], tags: &mut [u8], starts: &mut [u64], out: &mut [Span]) -> usize {
    classify::classify(text, tags);
    bitcannon_deepseek(text, tags, starts, out)
}

#[cfg(test)]
mod op_tests {
    use super::{fill_to_last, scanthru};

    /// Brute force: from every marker, walk forward while `c` holds, marking what we cross.
    fn star_ref(m: u64, c: u64) -> u64 {
        let mut out = 0u64;
        for p in 0..64 {
            if m >> p & 1 == 0 {
                continue;
            }
            out |= 1 << p;
            let mut q = p;
            while q < 63 && c >> (q + 1) & 1 != 0 {
                q += 1;
                out |= 1 << q;
            }
        }
        out
    }

    /// The smear shape the grammars use: step into the run, span to its end, add the marker back.
    #[test]
    fn fill_to_last_is_the_closure() {
        for &(m, c) in &[
            (0b0001u64, 0b1110u64),
            (0b0010, 0b1110),
            (0b0001, 0b0000),
            (1, !0u64 >> 1),
            (0x0000_0001_0000_0100, 0x0000_00FE_0000_FE00),
            (0xAAAA_AAAA_AAAA_AAAA, 0x5555_5555_5555_5555),
        ] {
            let stepped = (m << 1) & c;
            let got = fill_to_last(stepped, c) | m;
            assert_eq!(got, star_ref(m, c), "m={m:#018x} c={c:#018x}");
        }
    }

    /// The two operators against each other, so the distinction stays pinned.
    #[test]
    fn scanthru_lands_and_fill_to_last_spans() {
        let (m, c) = (0b0010u64, 0b1110u64);
        assert_eq!(
            scanthru(m as u128, c as u128) as u64,
            0b10000,
            "landing only"
        );
        assert_eq!(fill_to_last(m, c), 0b01110, "span, landing excluded");
    }
}