Skip to main content

simd_tokenizer/
swar.rs

1//! SWAR-accelerated whitespace tokenizer.
2//!
3//! SWAR ("SIMD Within A Register") scans 8 bytes per iteration inside a
4//! `u64`: bytes are classified with branch-free bit arithmetic and word
5//! boundaries are counted with `popcount`. Fully safe and portable — no
6//! `std::arch`, no runtime feature detection, identical results on every
7//! platform (see the `simd_matches_scalar` tests and property tests).
8
9use crate::{estimate_from_whitespace_splits, TokenCounter};
10
11const HIGH: u64 = 0x8080_8080_8080_8080;
12const SEVENS: u64 = 0x7F7F_7F7F_7F7F_7F7F;
13const ADD_5F: u64 = 0x5F5F_5F5F_5F5F_5F5F;
14
15/// Per-byte non-whitespace mask: `0x80` in each byte lane whose byte is
16/// **not** ≤ `0x20`.
17///
18/// Byte `c` is non-whitespace iff `c >= 0x80` (its high bit is set — this
19/// covers all UTF-8 non-ASCII bytes) or `(c & 0x7F) >= 0x21`. The 7-bit
20/// addition never carries across lanes (`0x7F + 0x5F = 0xDE`), so the
21/// per-byte predicate is exact — no SWAR borrow artifacts.
22#[inline(always)]
23fn nonwhitespace_mask(word: u64) -> u64 {
24    (word | ((word & SEVENS) + ADD_5F)) & HIGH
25}
26
27/// SIMD-style (SWAR) whitespace-split token estimator.
28///
29/// Splits on any byte ≤ `0x20` (covers space, tab, newline, CR, and other C0
30/// controls) using 8-byte SWAR loads, then blends word count + character
31/// based heuristics via [`estimate_from_whitespace_splits`] for a
32/// BPE-approximate token count.
33#[derive(Debug, Clone, Default)]
34pub struct SimdWhitespaceTokenizer {
35    _priv: (), // prevent direct construction — use ::new()
36}
37
38impl SimdWhitespaceTokenizer {
39    /// Create a new tokenizer.
40    pub fn new() -> Self {
41        Self { _priv: () }
42    }
43
44    /// Count whitespace-delimited segments (maximal runs of non-whitespace
45    /// bytes).
46    ///
47    /// Uses the SWAR path (8 bytes per step); the portable scalar reference
48    /// is available as [`scalar_count_splits`]. Both produce identical
49    /// results for every input.
50    pub fn count_splits(&self, bytes: &[u8]) -> usize {
51        count_splits_swar(bytes)
52    }
53}
54
55impl TokenCounter for SimdWhitespaceTokenizer {
56    fn count(&self, text: &str) -> usize {
57        let bytes = text.as_bytes();
58        let splits = count_splits_swar(bytes);
59        estimate_from_whitespace_splits(splits, bytes.len())
60    }
61
62    fn backend_name(&self) -> &'static str {
63        "simd-whitespace"
64    }
65}
66
67/// SWAR whitespace-split counter: counts the first byte of every non-
68/// whitespace run. A run's first byte is a non-whitespace byte whose
69/// predecessor is whitespace (or start-of-input, modeled by seeding the
70/// carry as "previous was whitespace").
71fn count_splits_swar(data: &[u8]) -> usize {
72    let mut count = 0usize;
73    let mut prev_ws = true;
74
75    let mut chunks = data.chunks_exact(8);
76    for chunk in &mut chunks {
77        let word = u64::from_le_bytes(chunk.try_into().expect("chunks_exact yields 8 bytes"));
78        let nonws = nonwhitespace_mask(word); // 0x80 per non-whitespace byte
79        let ws = !nonws & HIGH; // 0x80 per whitespace byte
80
81        // Run-start lanes: non-whitespace byte whose predecessor lane is
82        // whitespace. `ws << 8` moves each lane's flag to its successor;
83        // lane 0 uses the incoming carry.
84        let starts = nonws & ((ws << 8) | if prev_ws { 0x80 } else { 0 });
85        count += (starts >> 7).count_ones() as usize;
86
87        // Carry: whitespace-ness of the chunk's last byte (lane 7).
88        prev_ws = ws & (0x80 << 56) != 0;
89    }
90
91    // Scalar tail (fewer than 8 bytes remain).
92    for &b in chunks.remainder() {
93        let is_ws = b <= 0x20;
94        if !is_ws && prev_ws {
95            count += 1;
96        }
97        prev_ws = is_ws;
98    }
99
100    count
101}
102
103/// Portable scalar reference implementation of [`SimdWhitespaceTokenizer::
104/// count_splits`]. Public so callers (and tests) can cross-verify the SWAR
105/// path byte-for-byte.
106pub fn scalar_count_splits(data: &[u8]) -> usize {
107    let mut in_word = false;
108    let mut count = 0;
109    for &b in data {
110        let is_ws = b <= 0x20;
111        if is_ws {
112            if in_word {
113                count += 1;
114                in_word = false;
115            }
116        } else {
117            in_word = true;
118        }
119    }
120    if in_word {
121        count += 1;
122    }
123    count
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129
130    // --- ported from clawdius simd_tokenizer.rs (scalar) -------------------
131
132    #[test]
133    fn test_scalar_empty() {
134        assert_eq!(scalar_count_splits(b""), 0);
135    }
136
137    #[test]
138    fn test_scalar_single_word() {
139        assert_eq!(scalar_count_splits(b"hello"), 1);
140    }
141
142    #[test]
143    fn test_scalar_two_words() {
144        assert_eq!(scalar_count_splits(b"hello world"), 2);
145    }
146
147    #[test]
148    fn test_scalar_whitespace_only() {
149        assert_eq!(scalar_count_splits(b"   \t\n"), 0);
150    }
151
152    #[test]
153    fn test_scalar_mixed_whitespace() {
154        assert_eq!(scalar_count_splits(b"a b\tc\nd"), 4);
155    }
156
157    #[test]
158    fn test_scalar_leading_trailing_ws() {
159        assert_eq!(scalar_count_splits(b"  hello world  "), 2);
160    }
161
162    #[test]
163    fn test_scalar_c0_controls() {
164        assert_eq!(scalar_count_splits(b"a\x00b\x01c"), 3);
165    }
166
167    // --- ported from clawdius simd_tokenizer.rs (tokenizer) -----------------
168
169    #[test]
170    fn test_simd_tokenizer_empty() {
171        let t = SimdWhitespaceTokenizer::new();
172        assert_eq!(t.count(""), 0);
173    }
174
175    #[test]
176    fn test_simd_tokenizer_single() {
177        let t = SimdWhitespaceTokenizer::new();
178        assert!(t.count("hello") >= 1);
179    }
180
181    #[test]
182    fn test_simd_tokenizer_sentence() {
183        let t = SimdWhitespaceTokenizer::new();
184        let c = t.count("The quick brown fox jumps over the lazy dog.");
185        assert!(c >= 5);
186    }
187
188    #[test]
189    fn test_simd_tokenizer_code() {
190        let t = SimdWhitespaceTokenizer::new();
191        let code = "fn main() { let x = 42; }";
192        let c = t.count(code);
193        assert!(c >= 4);
194    }
195
196    #[test]
197    fn test_simd_tokenizer_unicode() {
198        let t = SimdWhitespaceTokenizer::new();
199        let c = t.count("こんにちは 世界 hello");
200        assert!(c >= 2);
201    }
202
203    // --- ported: SWAR-vs-scalar equivalence incl. alignment edges -----------
204
205    #[test]
206    fn test_simd_matches_scalar() {
207        let t = SimdWhitespaceTokenizer::new();
208        let cases: &[&str] = &[
209            "",
210            "a",
211            "hello world",
212            "  leading and trailing  ",
213            "tabs\there\ttoo",
214            "new\nlines\nhere",
215        ];
216        let long = "The quick brown fox jumps over the lazy dog. ".repeat(10);
217        for case in cases.iter().copied().chain(core::iter::once(long.as_str())) {
218            assert_eq!(
219                t.count_splits(case.as_bytes()),
220                scalar_count_splits(case.as_bytes()),
221                "mismatch for input of {} bytes",
222                case.len()
223            );
224        }
225    }
226
227    #[test]
228    fn test_17_byte_alignment() {
229        let data = b"12345678901234567";
230        let t = SimdWhitespaceTokenizer::new();
231        assert_eq!(t.count_splits(data), scalar_count_splits(data));
232    }
233
234    #[test]
235    fn test_33_byte_alignment() {
236        let data = b"123456789012345678901234567890123";
237        let t = SimdWhitespaceTokenizer::new();
238        assert_eq!(t.count_splits(data), scalar_count_splits(data));
239    }
240
241    #[test]
242    fn test_exact_16_bytes() {
243        let data = b"1234567890123456";
244        let t = SimdWhitespaceTokenizer::new();
245        assert_eq!(t.count_splits(data), scalar_count_splits(data));
246    }
247
248    #[test]
249    fn test_exact_32_bytes() {
250        let data = b"12345678901234567890123456789012";
251        let t = SimdWhitespaceTokenizer::new();
252        assert_eq!(t.count_splits(data), scalar_count_splits(data));
253    }
254
255    // --- ported from clawdius tokenizer/mod.rs -------------------------------
256
257    #[test]
258    fn test_empty_string() {
259        let t = SimdWhitespaceTokenizer::new();
260        assert_eq!(t.count(""), 0);
261    }
262
263    #[test]
264    fn test_single_word() {
265        let t = SimdWhitespaceTokenizer::new();
266        let c = t.count("hello");
267        assert!(c >= 1, "single word should yield >= 1 token, got {c}");
268    }
269
270    #[test]
271    fn test_simple_sentence() {
272        let t = SimdWhitespaceTokenizer::new();
273        let c = t.count("The quick brown fox jumps over the lazy dog.");
274        assert!(c >= 5, "sentence should yield >= 5 tokens, got {c}");
275    }
276
277    #[test]
278    fn test_long_text() {
279        let t = SimdWhitespaceTokenizer::new();
280        let text = "The quick brown fox jumps over the lazy dog. ".repeat(100);
281        let c = t.count(&text);
282        assert!(c >= 100, "long text should yield >= 100 tokens, got {c}");
283    }
284
285    #[test]
286    fn test_unicode_text() {
287        let t = SimdWhitespaceTokenizer::new();
288        let c = t.count("こんにちは世界 Hello 世界 this is unicode 🌍");
289        assert!(c >= 3, "unicode text should yield >= 3 tokens, got {c}");
290    }
291
292    #[test]
293    fn test_code_with_symbols() {
294        let t = SimdWhitespaceTokenizer::new();
295        let code = r#"fn main() {
296    let x = 42;
297    println!("Hello, world!");
298    if x > 0 {
299        println!("positive");
300    }
301}"#;
302        let c = t.count(code);
303        assert!(c >= 8, "code should yield >= 8 tokens, got {c}");
304    }
305
306    #[test]
307    fn test_whitespace_only() {
308        let t = SimdWhitespaceTokenizer::new();
309        assert_eq!(t.count("   \t\n\r  "), 0);
310    }
311
312    #[test]
313    fn test_single_character() {
314        let t = SimdWhitespaceTokenizer::new();
315        assert_eq!(t.count("a"), 1);
316    }
317
318    #[test]
319    fn test_repeated_spaces() {
320        let t = SimdWhitespaceTokenizer::new();
321        let c = t.count("hello   world");
322        assert_eq!(t.count("hello world"), c);
323    }
324
325    #[test]
326    fn test_newlines_and_tabs() {
327        let t = SimdWhitespaceTokenizer::new();
328        let c1 = t.count("hello\nworld");
329        let c2 = t.count("hello\tworld");
330        let c3 = t.count("hello world");
331        assert_eq!(c1, c2);
332        assert_eq!(c2, c3);
333    }
334
335    #[test]
336    fn test_backend_name() {
337        let t = SimdWhitespaceTokenizer::new();
338        assert_eq!(t.backend_name(), "simd-whitespace");
339    }
340
341    #[test]
342    fn test_estimate_from_splits_empty() {
343        assert_eq!(estimate_from_whitespace_splits(0, 0), 0);
344    }
345
346    #[test]
347    fn test_estimate_from_splits_single() {
348        let est = estimate_from_whitespace_splits(1, 5);
349        assert!(est >= 1);
350    }
351
352    #[test]
353    fn test_large_input_no_panic() {
354        let t = SimdWhitespaceTokenizer::new();
355        let text = "word ".repeat(100_000);
356        let _ = t.count(&text);
357    }
358
359    #[test]
360    fn test_emoji_heavy() {
361        let t = SimdWhitespaceTokenizer::new();
362        let c = t.count("😀😂🤣😃😄😁😆😅🤪😊😎");
363        assert!(c >= 1);
364    }
365}