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        let mut all_cases: Vec<&str> = cases.to_vec();
218        all_cases.push(&long);
219        for &case in &all_cases {
220            assert_eq!(
221                t.count_splits(case.as_bytes()),
222                scalar_count_splits(case.as_bytes()),
223                "mismatch for input of {} bytes",
224                case.len()
225            );
226        }
227    }
228
229    #[test]
230    fn test_17_byte_alignment() {
231        let data = b"12345678901234567";
232        let t = SimdWhitespaceTokenizer::new();
233        assert_eq!(t.count_splits(data), scalar_count_splits(data));
234    }
235
236    #[test]
237    fn test_33_byte_alignment() {
238        let data = b"123456789012345678901234567890123";
239        let t = SimdWhitespaceTokenizer::new();
240        assert_eq!(t.count_splits(data), scalar_count_splits(data));
241    }
242
243    #[test]
244    fn test_exact_16_bytes() {
245        let data = b"1234567890123456";
246        let t = SimdWhitespaceTokenizer::new();
247        assert_eq!(t.count_splits(data), scalar_count_splits(data));
248    }
249
250    #[test]
251    fn test_exact_32_bytes() {
252        let data = b"12345678901234567890123456789012";
253        let t = SimdWhitespaceTokenizer::new();
254        assert_eq!(t.count_splits(data), scalar_count_splits(data));
255    }
256
257    // --- ported from clawdius tokenizer/mod.rs -------------------------------
258
259    #[test]
260    fn test_empty_string() {
261        let t = SimdWhitespaceTokenizer::new();
262        assert_eq!(t.count(""), 0);
263    }
264
265    #[test]
266    fn test_single_word() {
267        let t = SimdWhitespaceTokenizer::new();
268        let c = t.count("hello");
269        assert!(c >= 1, "single word should yield >= 1 token, got {c}");
270    }
271
272    #[test]
273    fn test_simple_sentence() {
274        let t = SimdWhitespaceTokenizer::new();
275        let c = t.count("The quick brown fox jumps over the lazy dog.");
276        assert!(c >= 5, "sentence should yield >= 5 tokens, got {c}");
277    }
278
279    #[test]
280    fn test_long_text() {
281        let t = SimdWhitespaceTokenizer::new();
282        let text = "The quick brown fox jumps over the lazy dog. ".repeat(100);
283        let c = t.count(&text);
284        assert!(c >= 100, "long text should yield >= 100 tokens, got {c}");
285    }
286
287    #[test]
288    fn test_unicode_text() {
289        let t = SimdWhitespaceTokenizer::new();
290        let c = t.count("こんにちは世界 Hello 世界 this is unicode 🌍");
291        assert!(c >= 3, "unicode text should yield >= 3 tokens, got {c}");
292    }
293
294    #[test]
295    fn test_code_with_symbols() {
296        let t = SimdWhitespaceTokenizer::new();
297        let code = r#"fn main() {
298    let x = 42;
299    println!("Hello, world!");
300    if x > 0 {
301        println!("positive");
302    }
303}"#;
304        let c = t.count(code);
305        assert!(c >= 8, "code should yield >= 8 tokens, got {c}");
306    }
307
308    #[test]
309    fn test_whitespace_only() {
310        let t = SimdWhitespaceTokenizer::new();
311        assert_eq!(t.count("   \t\n\r  "), 0);
312    }
313
314    #[test]
315    fn test_single_character() {
316        let t = SimdWhitespaceTokenizer::new();
317        assert_eq!(t.count("a"), 1);
318    }
319
320    #[test]
321    fn test_repeated_spaces() {
322        let t = SimdWhitespaceTokenizer::new();
323        let c = t.count("hello   world");
324        assert_eq!(t.count("hello world"), c);
325    }
326
327    #[test]
328    fn test_newlines_and_tabs() {
329        let t = SimdWhitespaceTokenizer::new();
330        let c1 = t.count("hello\nworld");
331        let c2 = t.count("hello\tworld");
332        let c3 = t.count("hello world");
333        assert_eq!(c1, c2);
334        assert_eq!(c2, c3);
335    }
336
337    #[test]
338    fn test_backend_name() {
339        let t = SimdWhitespaceTokenizer::new();
340        assert_eq!(t.backend_name(), "simd-whitespace");
341    }
342
343    #[test]
344    fn test_estimate_from_splits_empty() {
345        assert_eq!(estimate_from_whitespace_splits(0, 0), 0);
346    }
347
348    #[test]
349    fn test_estimate_from_splits_single() {
350        let est = estimate_from_whitespace_splits(1, 5);
351        assert!(est >= 1);
352    }
353
354    #[test]
355    fn test_large_input_no_panic() {
356        let t = SimdWhitespaceTokenizer::new();
357        let text = "word ".repeat(100_000);
358        let _ = t.count(&text);
359    }
360
361    #[test]
362    fn test_emoji_heavy() {
363        let t = SimdWhitespaceTokenizer::new();
364        let c = t.count("😀😂🤣😃😄😁😆😅🤪😊😎");
365        assert!(c >= 1);
366    }
367}