simd_tokenizer/lib.rs
1//! SIMD-style token counting without unsafe code.
2//!
3//! Provides a pure-Rust, SWAR-boosted token estimator — extracted from
4//! [clawdius](https://github.com/WyattAu/clawdius) — for environments where
5//! `tiktoken-rs` is unavailable (WASM builds, minimal builds, or when the
6//! C/C++/Python tokenizer runtimes cannot be linked), or where a fast
7//! *estimate* beats a slow *exact* count.
8//!
9//! # Architecture
10//!
11//! | Type | Description |
12//! | --- | --- |
13//! | [`TokenCounter`] | Trait abstracting token counting backends. |
14//! | [`SimdWhitespaceTokenizer`] | SWAR byte-scan for whitespace boundaries. |
15//! | [`TokenEstimator`] | Enum dispatching to the best available backend. |
16//! | [`TiktokenCounter`] | Exact `cl100k_base` / `o200k_base` counting (feature `tiktoken`). |
17//!
18//! # The "SIMD" in the name, honestly
19//!
20//! clawdius's original scanner used `std::arch` SSE2/NEON intrinsics behind
21//! `unsafe`. This port replaces it with **SWAR** ("SIMD Within A Register"):
22//! 8 bytes are loaded per iteration into a `u64` and classified with
23//! branch-free bit tricks, then run boundaries are counted with `popcount`.
24//! It is fully portable (no `cfg(target_feature)`, no runtime detection) and
25//! lets the whole crate declare `#![forbid(unsafe_code)]` while staying on
26//! stable Rust.
27//!
28//! Performance characteristics, measured honestly:
29//!
30//! - Several times faster than a naive branchy per-byte loop on large inputs,
31//! and much faster than `str::split_whitespace().count()` (which allocates
32//! UTF-8-boundary-aware iterators).
33//! - Not as fast as hand-written SSE2/AVX2 for huge buffers; SWAR moves 8
34//! bytes per instruction-stream step vs 16-32 for vector ISAs.
35//! - For token *estimation* granularity (the result feeds a heuristic blend,
36//! not an exact invoice) this trade is usually invisible end-to-end.
37//!
38//! # Estimate semantics
39//!
40//! [`SimdWhitespaceTokenizer`] splits on any byte ≤ `0x20` (space, tab,
41//! newline, CR, and other C0 controls), then blends the word count with a
42//! ~4 chars/token heuristic and a punctuation overhead term — see
43//! [`estimate_from_whitespace_splits`]. It approximates BPE behavior for
44//! budgeting and rate-limit decisions; it is **not** a tokenizer table.
45//!
46//! # Feature flags
47//!
48//! - `tiktoken` (default **off**) — adds [`TiktokenCounter`] for exact
49//! `cl100k_base` and `o200k_base` counts ([`TiktokenCounter::new`] and
50//! [`TiktokenCounter::o200k`]) and makes [`TokenEstimator::new`] prefer
51//! tiktoken (`cl100k_base`).
52//!
53//! # Guarantees
54//!
55//! - `#![forbid(unsafe_code)]` — including the SIMD-style scan.
56//! - `#![deny(missing_docs)]` — the entire public API is documented.
57//! - Counting is deterministic, allocation-free, and never panics on any
58//! input (verified by property tests over arbitrary byte strings,
59//! including non-UTF-8 and truncated UTF-8 sequences).
60
61#![forbid(unsafe_code)]
62#![deny(missing_docs)]
63#![cfg_attr(not(feature = "std"), no_std)]
64
65mod swar;
66
67#[cfg(all(not(target_arch = "wasm32"), feature = "tiktoken"))]
68mod tiktoken_backend;
69
70pub use swar::{scalar_count_splits, SimdWhitespaceTokenizer};
71#[cfg(all(not(target_arch = "wasm32"), feature = "tiktoken"))]
72pub use tiktoken_backend::{TiktokenCounter, TiktokenError};
73
74/// Abstraction over token counting backends.
75pub trait TokenCounter: Send + Sync {
76 /// Return an estimated (or exact) token count for `text`.
77 fn count(&self, text: &str) -> usize;
78
79 /// Return a human-readable name for this backend.
80 fn backend_name(&self) -> &'static str;
81}
82
83/// Estimate a BPE-approximate token count from whitespace split statistics.
84///
85/// Deliberately kept simple: split on whitespace, add a small overhead for
86/// punctuation that would normally become separate tokens in BPE, and apply
87/// a ~4 chars/token heuristic for whitespace-dense text. The blend trusts
88/// word count when there are clear word boundaries and falls back to the
89/// character-based estimate for dense text.
90pub fn estimate_from_whitespace_splits(splits: usize, byte_len: usize) -> usize {
91 if splits == 0 {
92 return 0;
93 }
94 let word_tokens = splits;
95 let punct_overhead = (byte_len / 40).max(1);
96 let char_based = byte_len.div_ceil(4);
97 // Weighted blend of both estimates.
98 let blended = (word_tokens + punct_overhead + char_based) / 2;
99 blended.max(1)
100}
101
102/// Enum that dispatches to the best available token counter.
103///
104/// With the `tiktoken` feature enabled (on non-WASM targets) this wraps a
105/// [`TiktokenCounter`]; otherwise it uses [`SimdWhitespaceTokenizer`].
106// `SimdWhitespaceTokenizer` is a zero-sized type, so the tiktoken variant is
107// inherently ~200+ bytes larger (CoreBPE's tables state). Boxing would
108// allocate on every construction for no real benefit; the size is bounded and
109// known.
110#[allow(clippy::large_enum_variant)]
111#[derive(Debug)]
112pub enum TokenEstimator {
113 /// Exact counting via tiktoken-rs (cl100k_base).
114 #[cfg(all(not(target_arch = "wasm32"), feature = "tiktoken"))]
115 Tiktoken(TiktokenCounter),
116 /// Fast SWAR-accelerated approximation.
117 Simd(SimdWhitespaceTokenizer),
118}
119
120impl TokenEstimator {
121 /// Create the best estimator available for the current configuration.
122 ///
123 /// # Panics
124 ///
125 /// With the `tiktoken` feature enabled, panics if the `cl100k_base`
126 /// encoding fails to load. Use [`TokenEstimator::try_new_tiktoken`] for
127 /// fallible construction.
128 pub fn new() -> Self {
129 #[cfg(all(not(target_arch = "wasm32"), feature = "tiktoken"))]
130 {
131 // Documented panic: `new()` is the infallible-by-contract
132 // constructor; fallible callers use `try_new_tiktoken`.
133 #[allow(clippy::expect_used)]
134 Self::Tiktoken(
135 TiktokenCounter::new().expect("failed to initialise cl100k_base tokenizer"),
136 )
137 }
138 #[cfg(not(all(not(target_arch = "wasm32"), feature = "tiktoken")))]
139 {
140 Self::Simd(SimdWhitespaceTokenizer::new())
141 }
142 }
143
144 /// Fallibly construct the tiktoken-backed estimator (only available with
145 /// the `tiktoken` feature on non-WASM targets).
146 #[cfg(all(not(target_arch = "wasm32"), feature = "tiktoken"))]
147 pub fn try_new_tiktoken() -> Result<Self, TiktokenError> {
148 Ok(Self::Tiktoken(TiktokenCounter::new()?))
149 }
150
151 /// Fallibly construct an o200k_base-backed estimator (only available with
152 /// the `tiktoken` feature on non-WASM targets).
153 #[cfg(all(not(target_arch = "wasm32"), feature = "tiktoken"))]
154 pub fn try_new_tiktoken_o200k() -> Result<Self, TiktokenError> {
155 Ok(Self::Tiktoken(TiktokenCounter::o200k()?))
156 }
157}
158
159impl Default for TokenEstimator {
160 fn default() -> Self {
161 Self::new()
162 }
163}
164
165impl TokenCounter for TokenEstimator {
166 fn count(&self, text: &str) -> usize {
167 match self {
168 #[cfg(all(not(target_arch = "wasm32"), feature = "tiktoken"))]
169 Self::Tiktoken(t) => t.count(text),
170 Self::Simd(s) => s.count(text),
171 }
172 }
173
174 fn backend_name(&self) -> &'static str {
175 match self {
176 #[cfg(all(not(target_arch = "wasm32"), feature = "tiktoken"))]
177 Self::Tiktoken(t) => t.backend_name(),
178 Self::Simd(s) => s.backend_name(),
179 }
180 }
181}