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        // `chunks_exact(8)` guarantees every chunk is exactly 8 bytes, so
78        // the conversion cannot fail.
79        #[allow(clippy::expect_used)]
80        let word = u64::from_le_bytes(chunk.try_into().expect("chunks_exact yields 8 bytes"));
81        let nonws = nonwhitespace_mask(word); // 0x80 per non-whitespace byte
82        let ws = !nonws & HIGH; // 0x80 per whitespace byte
83
84        // Run-start lanes: non-whitespace byte whose predecessor lane is
85        // whitespace. `ws << 8` moves each lane's flag to its successor;
86        // lane 0 uses the incoming carry.
87        let starts = nonws & ((ws << 8) | if prev_ws { 0x80 } else { 0 });
88        count += (starts >> 7).count_ones() as usize;
89
90        // Carry: whitespace-ness of the chunk's last byte (lane 7).
91        prev_ws = ws & (0x80 << 56) != 0;
92    }
93
94    // Scalar tail (fewer than 8 bytes remain).
95    for &b in chunks.remainder() {
96        let is_ws = b <= 0x20;
97        if !is_ws && prev_ws {
98            count += 1;
99        }
100        prev_ws = is_ws;
101    }
102
103    count
104}
105
106/// Portable scalar reference implementation of [`SimdWhitespaceTokenizer::
107/// count_splits`]. Public so callers (and tests) can cross-verify the SWAR
108/// path byte-for-byte.
109pub fn scalar_count_splits(data: &[u8]) -> usize {
110    let mut in_word = false;
111    let mut count = 0;
112    for &b in data {
113        let is_ws = b <= 0x20;
114        if is_ws {
115            if in_word {
116                count += 1;
117                in_word = false;
118            }
119        } else {
120            in_word = true;
121        }
122    }
123    if in_word {
124        count += 1;
125    }
126    count
127}
128
129#[cfg(test)]
130mod tests {
131    use super::*;
132
133    // --- ported from clawdius simd_tokenizer.rs (scalar) -------------------
134
135    #[test]
136    fn test_scalar_empty() {
137        assert_eq!(scalar_count_splits(b""), 0);
138    }
139
140    #[test]
141    fn test_scalar_single_word() {
142        assert_eq!(scalar_count_splits(b"hello"), 1);
143    }
144
145    #[test]
146    fn test_scalar_two_words() {
147        assert_eq!(scalar_count_splits(b"hello world"), 2);
148    }
149
150    #[test]
151    fn test_scalar_whitespace_only() {
152        assert_eq!(scalar_count_splits(b"   \t\n"), 0);
153    }
154
155    #[test]
156    fn test_scalar_mixed_whitespace() {
157        assert_eq!(scalar_count_splits(b"a b\tc\nd"), 4);
158    }
159
160    #[test]
161    fn test_scalar_leading_trailing_ws() {
162        assert_eq!(scalar_count_splits(b"  hello world  "), 2);
163    }
164
165    #[test]
166    fn test_scalar_c0_controls() {
167        assert_eq!(scalar_count_splits(b"a\x00b\x01c"), 3);
168    }
169
170    // --- ported from clawdius simd_tokenizer.rs (tokenizer) -----------------
171
172    #[test]
173    fn test_simd_tokenizer_empty() {
174        let t = SimdWhitespaceTokenizer::new();
175        assert_eq!(t.count(""), 0);
176    }
177
178    #[test]
179    fn test_simd_tokenizer_single() {
180        let t = SimdWhitespaceTokenizer::new();
181        assert!(t.count("hello") >= 1);
182    }
183
184    #[test]
185    fn test_simd_tokenizer_sentence() {
186        let t = SimdWhitespaceTokenizer::new();
187        let c = t.count("The quick brown fox jumps over the lazy dog.");
188        assert!(c >= 5);
189    }
190
191    #[test]
192    fn test_simd_tokenizer_code() {
193        let t = SimdWhitespaceTokenizer::new();
194        let code = "fn main() { let x = 42; }";
195        let c = t.count(code);
196        assert!(c >= 4);
197    }
198
199    #[test]
200    fn test_simd_tokenizer_unicode() {
201        let t = SimdWhitespaceTokenizer::new();
202        let c = t.count("こんにちは 世界 hello");
203        assert!(c >= 2);
204    }
205
206    // --- ported: SWAR-vs-scalar equivalence incl. alignment edges -----------
207
208    #[test]
209    fn test_simd_matches_scalar() {
210        let t = SimdWhitespaceTokenizer::new();
211        let cases: &[&str] = &[
212            "",
213            "a",
214            "hello world",
215            "  leading and trailing  ",
216            "tabs\there\ttoo",
217            "new\nlines\nhere",
218        ];
219        let long = "The quick brown fox jumps over the lazy dog. ".repeat(10);
220        for case in cases.iter().copied().chain(core::iter::once(long.as_str())) {
221            assert_eq!(
222                t.count_splits(case.as_bytes()),
223                scalar_count_splits(case.as_bytes()),
224                "mismatch for input of {} bytes",
225                case.len()
226            );
227        }
228    }
229
230    #[test]
231    fn test_17_byte_alignment() {
232        let data = b"12345678901234567";
233        let t = SimdWhitespaceTokenizer::new();
234        assert_eq!(t.count_splits(data), scalar_count_splits(data));
235    }
236
237    #[test]
238    fn test_33_byte_alignment() {
239        let data = b"123456789012345678901234567890123";
240        let t = SimdWhitespaceTokenizer::new();
241        assert_eq!(t.count_splits(data), scalar_count_splits(data));
242    }
243
244    #[test]
245    fn test_exact_16_bytes() {
246        let data = b"1234567890123456";
247        let t = SimdWhitespaceTokenizer::new();
248        assert_eq!(t.count_splits(data), scalar_count_splits(data));
249    }
250
251    #[test]
252    fn test_exact_32_bytes() {
253        let data = b"12345678901234567890123456789012";
254        let t = SimdWhitespaceTokenizer::new();
255        assert_eq!(t.count_splits(data), scalar_count_splits(data));
256    }
257
258    // --- ported from clawdius tokenizer/mod.rs -------------------------------
259
260    #[test]
261    fn test_empty_string() {
262        let t = SimdWhitespaceTokenizer::new();
263        assert_eq!(t.count(""), 0);
264    }
265
266    #[test]
267    fn test_single_word() {
268        let t = SimdWhitespaceTokenizer::new();
269        let c = t.count("hello");
270        assert!(c >= 1, "single word should yield >= 1 token, got {c}");
271    }
272
273    #[test]
274    fn test_simple_sentence() {
275        let t = SimdWhitespaceTokenizer::new();
276        let c = t.count("The quick brown fox jumps over the lazy dog.");
277        assert!(c >= 5, "sentence should yield >= 5 tokens, got {c}");
278    }
279
280    #[test]
281    fn test_long_text() {
282        let t = SimdWhitespaceTokenizer::new();
283        let text = "The quick brown fox jumps over the lazy dog. ".repeat(100);
284        let c = t.count(&text);
285        assert!(c >= 100, "long text should yield >= 100 tokens, got {c}");
286    }
287
288    #[test]
289    fn test_unicode_text() {
290        let t = SimdWhitespaceTokenizer::new();
291        let c = t.count("こんにちは世界 Hello 世界 this is unicode 🌍");
292        assert!(c >= 3, "unicode text should yield >= 3 tokens, got {c}");
293    }
294
295    #[test]
296    fn test_code_with_symbols() {
297        let t = SimdWhitespaceTokenizer::new();
298        let code = r#"fn main() {
299    let x = 42;
300    println!("Hello, world!");
301    if x > 0 {
302        println!("positive");
303    }
304}"#;
305        let c = t.count(code);
306        assert!(c >= 8, "code should yield >= 8 tokens, got {c}");
307    }
308
309    #[test]
310    fn test_whitespace_only() {
311        let t = SimdWhitespaceTokenizer::new();
312        assert_eq!(t.count("   \t\n\r  "), 0);
313    }
314
315    #[test]
316    fn test_single_character() {
317        let t = SimdWhitespaceTokenizer::new();
318        assert_eq!(t.count("a"), 1);
319    }
320
321    #[test]
322    fn test_repeated_spaces() {
323        let t = SimdWhitespaceTokenizer::new();
324        let c = t.count("hello   world");
325        assert_eq!(t.count("hello world"), c);
326    }
327
328    #[test]
329    fn test_newlines_and_tabs() {
330        let t = SimdWhitespaceTokenizer::new();
331        let c1 = t.count("hello\nworld");
332        let c2 = t.count("hello\tworld");
333        let c3 = t.count("hello world");
334        assert_eq!(c1, c2);
335        assert_eq!(c2, c3);
336    }
337
338    #[test]
339    fn test_backend_name() {
340        let t = SimdWhitespaceTokenizer::new();
341        assert_eq!(t.backend_name(), "simd-whitespace");
342    }
343
344    #[test]
345    fn test_estimate_from_splits_empty() {
346        assert_eq!(estimate_from_whitespace_splits(0, 0), 0);
347    }
348
349    #[test]
350    fn test_estimate_from_splits_single() {
351        let est = estimate_from_whitespace_splits(1, 5);
352        assert!(est >= 1);
353    }
354
355    #[test]
356    fn test_large_input_no_panic() {
357        let t = SimdWhitespaceTokenizer::new();
358        let text = "word ".repeat(100_000);
359        let _ = t.count(&text);
360    }
361
362    #[test]
363    fn test_emoji_heavy() {
364        let t = SimdWhitespaceTokenizer::new();
365        let c = t.count("😀😂🤣😃😄😁😆😅🤪😊😎");
366        assert!(c >= 1);
367    }
368}