Skip to main content

rypipe_core/
block_masks.rs

1//! BlockMasks: one AVX2/SSE2 load per 64-byte block, cached bitmasks.
2//!
3//! 36.5% of parse is memchr on ~50-100 byte spans per field (5-7 separate
4//! searches). Computing delimiter positions once per 64-byte block and
5//! answering queries via bit operations removes per-search prologue.
6//!
7//! Two things make this beat a sequence of `memchr` calls:
8//!
9//! 1. **Single-pass multi-delimiter masks.** Every delimiter in the set is
10//!    masked from the *same* 64-byte load (one load, N `cmpeq`), instead of
11//!    one full load per delimiter (simdxml's structural classifier shape).
12//! 2. **Quote-aware scanning.** `next_unquoted` derives an "inside a quoted
13//!    region" bitmask from the quote bitmask with a SWAR prefix-XOR
14//!    (simdjson/simdxml trick), so delimiters inside attribute values are
15//!    skipped in the same pass with no per-byte state machine.
16
17use std::sync::OnceLock;
18
19const MAX_DELIMS: usize = 8;
20
21static HAS_AVX2: OnceLock<bool> = OnceLock::new();
22
23#[inline]
24fn has_avx2() -> bool {
25    #[cfg(target_arch = "x86_64")]
26    {
27        *HAS_AVX2.get_or_init(|| is_x86_feature_detected!("avx2"))
28    }
29    #[cfg(not(target_arch = "x86_64"))]
30    {
31        false
32    }
33}
34
35/// Inclusive prefix-XOR (scan) of a 64-bit mask.
36///
37/// Bit `i` of the result is the parity of bits `0..=i`. Applied to a quote
38/// bitmask this yields the "inside a quoted region" bitmask: a delimiter bit
39/// ANDed with the complement of this is outside quotes.
40#[inline]
41pub fn prefix_xor(mut m: u64) -> u64 {
42    m ^= m << 1;
43    m ^= m << 2;
44    m ^= m << 4;
45    m ^= m << 8;
46    m ^= m << 16;
47    m ^= m << 32;
48    m
49}
50
51/// 64-byte block masks.
52///
53/// Single-delimiter queries ([`next`](Self::next)) compute only the mask they
54/// need (one load, one `cmpeq`). Multi-delimiter entry points
55/// ([`next_any`](Self::next_any), [`next_unquoted`](Self::next_unquoted))
56/// compute every delimiter from the *same* load in one pass.
57pub struct BlockMasks<'a> {
58    buf: &'a [u8],
59    base: usize,
60    loaded: bool,
61    /// Bit `i` set => `masks[i]` valid for the current block.
62    computed: u8,
63    masks: [u64; MAX_DELIMS],
64    /// Active quote character for `next_unquoted`: 0 = outside a quote,
65    /// otherwise the quote byte (one of `quotes`) whose region we are inside.
66    /// Only a matching quote byte closes it; the other quote byte is literal.
67    in_quote: u8,
68    /// Absolute buffer position through which `in_quote` has been advanced.
69    /// A call with `from == quote_pos` continues; anything else resets.
70    quote_pos: usize,
71    delims: &'static [u8],
72    /// Delimiters treated as quote characters by `next_unquoted` (⊆ delims).
73    quotes: &'static [u8],
74}
75
76impl<'a> BlockMasks<'a> {
77    /// Create for `buf` with `delims` (static, ≤8, e.g. crxml: [b'<',b'>',b'"',b'\'',b'=']).
78    pub fn new(buf: &'a [u8], delims: &'static [u8]) -> Self {
79        Self::build(buf, delims, &[])
80    }
81
82    /// Like [`new`](Self::new) but enables [`next_unquoted`](Self::next_unquoted)
83    /// with the given quote characters. Each quote char must be in `delims`.
84    pub fn with_quotes(buf: &'a [u8], delims: &'static [u8], quotes: &'static [u8]) -> Self {
85        Self::build(buf, delims, quotes)
86    }
87
88    fn build(buf: &'a [u8], delims: &'static [u8], quotes: &'static [u8]) -> Self {
89        assert!(delims.len() <= MAX_DELIMS, "MAX_DELIMS=8");
90        for &q in quotes {
91            assert!(delims.contains(&q), "quote char must be in delims");
92        }
93        Self {
94            buf,
95            base: usize::MAX, // sentinel: first seek will set
96            loaded: false,
97            computed: 0,
98            masks: [0; MAX_DELIMS],
99            in_quote: 0,
100            quote_pos: 0,
101            delims,
102            quotes,
103        }
104    }
105
106    #[inline]
107    fn delim_index(&self, d: u8) -> Option<usize> {
108        self.delims.iter().position(|&x| x == d)
109    }
110
111    /// Bitmask of "all current delimiters computed".
112    #[inline]
113    fn full_mask(&self) -> u8 {
114        let n = self.delims.len();
115        if n >= 8 {
116            u8::MAX
117        } else {
118            (1u8 << n) - 1
119        }
120    }
121
122    /// Fill `out[..delims.len()]` with masks for the 64-byte block at `base`.
123    #[inline]
124    fn fill(&self, base: usize, delims: &[u8], out: &mut [u64]) {
125        let n = delims.len();
126        if n == 0 {
127            return;
128        }
129        if base + 64 <= self.buf.len() {
130            // SAFETY: the guard proves 64 readable bytes start at `base`.
131            unsafe { masks64(self.buf.as_ptr().add(base), delims, out, n) };
132        } else {
133            // Tail: copy remainder into stack array, compute, mask off beyond len.
134            let rem = self.buf.len().saturating_sub(base);
135            if rem == 0 {
136                return;
137            }
138            let mut tmp = [0u8; 64];
139            tmp[..rem].copy_from_slice(&self.buf[base..base + rem]);
140            // SAFETY: `tmp` is a 64-byte array (the remainder, zero-padded).
141            unsafe { masks64(tmp.as_ptr(), delims, out, n) };
142            let keep = (1u64 << rem) - 1;
143            for m in out.iter_mut().take(n) {
144                *m &= keep;
145            }
146        }
147    }
148
149    /// Load (or reload) the block at `base`; masks become stale.
150    #[inline]
151    fn load_at(&mut self, base: usize) {
152        self.base = base;
153        self.loaded = true;
154        self.computed = 0;
155    }
156
157    /// Select the block containing `from`, reloading only if it changed.
158    #[inline]
159    fn select_block(&mut self, from: usize) {
160        let new_base = from & !63;
161        if new_base != self.base || !self.loaded {
162            self.load_at(new_base);
163        }
164    }
165
166    #[inline]
167    fn advance_block(&mut self) -> bool {
168        let nb = self.base.wrapping_add(64);
169        if nb >= self.buf.len() {
170            return false;
171        }
172        self.load_at(nb);
173        true
174    }
175
176    /// Mask for `d`, computed alone (single load, one compare) if not cached.
177    #[inline]
178    fn mask_for(&mut self, d: u8) -> u64 {
179        let idx = self.delim_index(d).expect("delim not in set");
180        if (self.computed >> idx) & 1 == 0 {
181            self.masks[idx] = self.compute_one(d);
182            self.computed |= 1 << idx;
183        }
184        self.masks[idx]
185    }
186
187    /// Compute a single delimiter's mask for the current block (tail-safe).
188    #[inline]
189    fn compute_one(&self, d: u8) -> u64 {
190        let base = self.base;
191        if base + 64 <= self.buf.len() {
192            // SAFETY: the guard proves 64 readable bytes start at `base`.
193            unsafe { mask64(self.buf.as_ptr().add(base), d) }
194        } else {
195            let rem = self.buf.len().saturating_sub(base);
196            if rem == 0 {
197                return 0;
198            }
199            let mut tmp = [0u8; 64];
200            tmp[..rem].copy_from_slice(&self.buf[base..base + rem]);
201            // SAFETY: `tmp` is a 64-byte array; the mask is trimmed to `rem`.
202            (unsafe { mask64(tmp.as_ptr(), d) }) & ((1u64 << rem) - 1)
203        }
204    }
205
206    /// Compute every delimiter mask for the current block in one pass.
207    #[inline]
208    fn ensure_all(&mut self) {
209        if self.computed != self.full_mask() {
210            let mut out = [0u64; MAX_DELIMS];
211            self.fill(self.base, self.delims, &mut out);
212            self.masks = out;
213            self.computed = self.full_mask();
214        }
215    }
216
217    /// Bit positions `>= pos` as a mask (`0` once `pos >= 64`).
218    #[inline]
219    fn from_mask(pos: usize) -> u64 {
220        if pos >= 64 {
221            0
222        } else {
223            !0u64 << pos
224        }
225    }
226
227    /// Next occurrence of `d` at or after `from`.
228    #[inline]
229    pub fn next(&mut self, from: usize, d: u8) -> Option<usize> {
230        if from >= self.buf.len() {
231            return None;
232        }
233        let mut cur = from;
234        loop {
235            if cur < self.base || cur >= self.base + 64 {
236                self.select_block(cur);
237            }
238            let offset = cur - self.base;
239            // mask off bits before offset
240            let m = self.mask_for(d) & (!0u64 << offset);
241            if m != 0 {
242                return Some(self.base + m.trailing_zeros() as usize);
243            }
244            if !self.advance_block() {
245                return None;
246            }
247            cur = self.base;
248        }
249    }
250
251    /// Next occurrence of any of `ds` at or after `from`, returns (pos, delim).
252    #[inline]
253    pub fn next_any(&mut self, from: usize, ds: &[u8]) -> Option<(usize, u8)> {
254        if from >= self.buf.len() {
255            return None;
256        }
257        let mut cur = from;
258        loop {
259            if cur < self.base || cur >= self.base + 64 {
260                self.select_block(cur);
261            }
262            self.ensure_all();
263            let offset = cur - self.base;
264            let mut combined = 0u64;
265            for &d in ds {
266                combined |= self.masks[self.delim_index(d).expect("delim not in set")];
267            }
268            let masked = combined & (!0u64 << offset);
269            if masked != 0 {
270                let pos = self.base + masked.trailing_zeros() as usize;
271                // Identify which delim matches at pos
272                for &d in ds {
273                    let m = self.masks[self.delim_index(d).expect("delim not in set")];
274                    if (m >> (pos - self.base)) & 1 == 1 {
275                        return Some((pos, d));
276                    }
277                }
278                // Should not reach: combined had bit but no individual? Fallback
279                return Some((pos, ds[0]));
280            }
281            if !self.advance_block() {
282                return None;
283            }
284            cur = self.base;
285        }
286    }
287
288    /// Next occurrence of `d` at or after `from` that lies **outside** any
289    /// quoted region (per the quote chars given to [`with_quotes`](Self::with_quotes)).
290    ///
291    /// Quote regions follow XML attribute-value rules: a value opened by `"` is
292    /// closed only by the next `"`, and vice versa for `'`. A quote byte of the
293    /// other type inside a value is literal.
294    ///
295    /// This is a **forward cursor**: quote state is accumulated as the scan
296    /// advances, so each call's `from` must be ≥ the previously returned
297    /// position (the natural `from = last_found + 1` loop). Querying a position
298    /// behind the cursor resets the quote state, which is only correct if that
299    /// earlier prefix has no unbalanced quote.
300    #[inline]
301    pub fn next_unquoted(&mut self, from: usize, d: u8) -> Option<usize> {
302        if self.quotes.is_empty() {
303            return self.next(from, d);
304        }
305        if from >= self.buf.len() {
306            return None;
307        }
308        let di = self.delim_index(d).expect("delim not in set");
309        let mut cur = from;
310        // Continue only when `from` is exactly where the cursor left off;
311        // any other position is a fresh scan (unknown quote state).
312        if !self.loaded || from != self.quote_pos {
313            self.in_quote = 0;
314            self.quote_pos = from;
315            self.load_at(from & !63);
316        }
317        loop {
318            self.ensure_all();
319            if let Some(p) = self.scan_block_unquoted(cur - self.base, di) {
320                self.quote_pos = self.base + p + 1;
321                return Some(self.base + p);
322            }
323            if !self.advance_block() {
324                self.quote_pos = self.base.wrapping_add(64);
325                return None;
326            }
327            cur = self.base;
328            self.quote_pos = cur;
329        }
330    }
331
332    /// Within the loaded block, from byte `offset`, return the offset of the
333    /// next `delims[di]` that is outside quotes, updating `in_quote`. `None` if
334    /// the block ends first.
335    fn scan_block_unquoted(&mut self, offset: usize, di: usize) -> Option<usize> {
336        let mut pos = offset;
337        if self.in_quote == 0 {
338            // Fast path: if only one quote type remains, "inside" is a plain
339            // prefix-XOR of that quote's mask (simdjson/simdxml trick).
340            let q_single = self.single_quote_remaining(pos);
341            if let Some(qi) = q_single {
342                let qmask = self.masks[qi] & Self::from_mask(pos);
343                let inside = prefix_xor(qmask);
344                let hits = self.masks[di] & Self::from_mask(pos) & !inside;
345                if hits != 0 {
346                    // We return outside, so `in_quote` stays 0 for the cursor.
347                    return Some(hits.trailing_zeros() as usize);
348                }
349                // No delimiter before block end; carry the parity to the next block.
350                if qmask.count_ones() & 1 == 1 {
351                    self.in_quote = self.delims[qi];
352                }
353                return None;
354            }
355        }
356        // General path: walk quote events (only the active type closes).
357        loop {
358            if self.in_quote == 0 {
359                let mut qbits = 0u64;
360                for &q in self.quotes {
361                    qbits |= self.masks[self.delim_index(q).expect("quote in delims")];
362                }
363                let g = self.masks[di] & Self::from_mask(pos);
364                let q = qbits & Self::from_mask(pos);
365                let ghas = g != 0;
366                let qhas = q != 0;
367                let gpos = g.trailing_zeros();
368                let qpos = q.trailing_zeros();
369                if ghas && (!qhas || gpos < qpos) {
370                    return Some(gpos as usize);
371                }
372                if !qhas {
373                    return None;
374                }
375                self.in_quote = self.delims[self.quote_index_at(qpos as usize)];
376                pos = qpos as usize + 1;
377            } else {
378                let qi = self.delim_index(self.in_quote).expect("quote in delims");
379                let c = self.masks[qi] & Self::from_mask(pos);
380                if c == 0 {
381                    return None;
382                }
383                self.in_quote = 0;
384                pos = c.trailing_zeros() as usize + 1;
385            }
386        }
387    }
388
389    /// If exactly one quote type occurs at or after block offset `pos`, return
390    /// its delimiter index.
391    #[inline]
392    fn single_quote_remaining(&self, pos: usize) -> Option<usize> {
393        let m = Self::from_mask(pos);
394        let mut found = None;
395        for &q in self.quotes {
396            let qi = self.delim_index(q).expect("quote in delims");
397            if self.masks[qi] & m != 0 {
398                if found.is_some() {
399                    return None;
400                }
401                found = Some(qi);
402            }
403        }
404        found
405    }
406
407    /// Delimiter index of the quote byte at block offset `pos`.
408    #[inline]
409    fn quote_index_at(&self, pos: usize) -> usize {
410        for &q in self.quotes {
411            let qi = self.delim_index(q).expect("quote in delims");
412            if (self.masks[qi] >> pos) & 1 == 1 {
413                return qi;
414            }
415        }
416        unreachable!("quote_index_at: no quote byte at position");
417    }
418
419    /// Long-span fallback: if hint >256 use memchr, else BlockMasks.
420    #[inline]
421    pub fn next_far(&mut self, from: usize, d: u8, hint: usize) -> Option<usize> {
422        if hint > 256 {
423            memchr::memchr(d, &self.buf[from..]).map(|i| from + i)
424        } else {
425            self.next(from, d)
426        }
427    }
428}
429
430// SAFETY: `p` must point to at least 64 readable bytes.
431#[inline]
432unsafe fn mask64(p: *const u8, needle: u8) -> u64 {
433    #[cfg(target_arch = "x86_64")]
434    {
435        if has_avx2() {
436            // SAFETY: the function contract guarantees 64 readable bytes; AVX2
437            // is available (checked).
438            return unsafe { mask64_avx2(p, needle) };
439        }
440        // SAFETY: the contract guarantees 64 readable bytes; SSE2 is baseline.
441        unsafe { mask64_sse2(p, needle) }
442    }
443    #[cfg(not(target_arch = "x86_64"))]
444    {
445        let _ = has_avx2();
446        // SAFETY: the contract guarantees 64 readable bytes.
447        unsafe { mask64_scalar(p, needle) }
448    }
449}
450
451#[cfg(target_arch = "x86_64")]
452#[target_feature(enable = "avx2")]
453/// # Safety
454///
455/// `p` must point to at least 64 readable bytes.
456unsafe fn mask64_avx2(p: *const u8, needle: u8) -> u64 {
457    use std::arch::x86_64::*;
458    let n = _mm256_set1_epi8(needle as i8);
459    let lo = _mm256_loadu_si256(p as *const __m256i);
460    let hi = _mm256_loadu_si256(p.add(32) as *const __m256i);
461    let m0 = _mm256_movemask_epi8(_mm256_cmpeq_epi8(lo, n)) as u32 as u64;
462    let m1 = _mm256_movemask_epi8(_mm256_cmpeq_epi8(hi, n)) as u32 as u64;
463    m0 | (m1 << 32)
464}
465
466#[cfg(target_arch = "x86_64")]
467#[target_feature(enable = "sse2")]
468/// # Safety
469///
470/// `p` must point to at least 64 readable bytes.
471unsafe fn mask64_sse2(p: *const u8, needle: u8) -> u64 {
472    use std::arch::x86_64::*;
473    let n = _mm_set1_epi8(needle as i8);
474    let mut mask = 0u64;
475    for i in 0..4 {
476        let v = _mm_loadu_si128(p.add(i * 16) as *const __m128i);
477        let m = _mm_movemask_epi8(_mm_cmpeq_epi8(v, n)) as u64;
478        mask |= m << (i * 16);
479    }
480    mask
481}
482
483#[cfg(any(not(target_arch = "x86_64"), test))]
484/// # Safety
485///
486/// `p` must point to at least 64 readable bytes.
487unsafe fn mask64_scalar(p: *const u8, needle: u8) -> u64 {
488    let mut mask = 0u64;
489    for i in 0..64 {
490        if *p.add(i) == needle {
491            mask |= 1u64 << i;
492        }
493    }
494    mask
495}
496
497// SAFETY: `p` must point to at least 64 readable bytes; writes `out[..n]`.
498#[inline]
499unsafe fn masks64(p: *const u8, delims: &[u8], out: &mut [u64], n: usize) {
500    #[cfg(target_arch = "x86_64")]
501    {
502        if has_avx2() {
503            // SAFETY: the function contract guarantees 64 readable bytes and
504            // `out[..n]` writable; AVX2 is available (checked).
505            unsafe { masks64_avx2(p, delims, out, n) };
506            return;
507        }
508        // SAFETY: the contract guarantees 64 readable bytes and out[..n]; SSE2
509        // is baseline.
510        unsafe { masks64_sse2(p, delims, out, n) };
511    }
512    #[cfg(not(target_arch = "x86_64"))]
513    {
514        let _ = has_avx2();
515        // SAFETY: the contract guarantees 64 readable bytes and out[..n].
516        unsafe { masks64_scalar(p, delims, out, n) };
517    }
518}
519
520#[cfg(target_arch = "x86_64")]
521#[target_feature(enable = "avx2")]
522/// # Safety
523///
524/// `p` must point to at least 64 readable bytes.
525unsafe fn masks64_avx2(p: *const u8, delims: &[u8], out: &mut [u64], n: usize) {
526    use std::arch::x86_64::*;
527    let lo = _mm256_loadu_si256(p as *const __m256i);
528    let hi = _mm256_loadu_si256(p.add(32) as *const __m256i);
529    for i in 0..n {
530        let v = _mm256_set1_epi8(delims[i] as i8);
531        let m0 = _mm256_movemask_epi8(_mm256_cmpeq_epi8(lo, v)) as u32 as u64;
532        let m1 = _mm256_movemask_epi8(_mm256_cmpeq_epi8(hi, v)) as u32 as u64;
533        out[i] = m0 | (m1 << 32);
534    }
535}
536
537#[cfg(target_arch = "x86_64")]
538#[target_feature(enable = "sse2")]
539/// # Safety
540///
541/// `p` must point to at least 64 readable bytes.
542unsafe fn masks64_sse2(p: *const u8, delims: &[u8], out: &mut [u64], n: usize) {
543    use std::arch::x86_64::*;
544    let v0 = _mm_loadu_si128(p as *const __m128i);
545    let v1 = _mm_loadu_si128(p.add(16) as *const __m128i);
546    let v2 = _mm_loadu_si128(p.add(32) as *const __m128i);
547    let v3 = _mm_loadu_si128(p.add(48) as *const __m128i);
548    for i in 0..n {
549        let d = _mm_set1_epi8(delims[i] as i8);
550        let m0 = _mm_movemask_epi8(_mm_cmpeq_epi8(v0, d)) as u64;
551        let m1 = _mm_movemask_epi8(_mm_cmpeq_epi8(v1, d)) as u64;
552        let m2 = _mm_movemask_epi8(_mm_cmpeq_epi8(v2, d)) as u64;
553        let m3 = _mm_movemask_epi8(_mm_cmpeq_epi8(v3, d)) as u64;
554        out[i] = m0 | (m1 << 16) | (m2 << 32) | (m3 << 48);
555    }
556}
557
558#[cfg(any(not(target_arch = "x86_64"), test))]
559/// # Safety
560///
561/// `p` must point to at least 64 readable bytes.
562unsafe fn masks64_scalar(p: *const u8, delims: &[u8], out: &mut [u64], n: usize) {
563    out[..n].fill(0);
564    for j in 0..64 {
565        let b = *p.add(j);
566        for i in 0..n {
567            if delims[i] == b {
568                out[i] |= 1u64 << j;
569            }
570        }
571    }
572}
573
574#[cfg(test)]
575mod tests {
576    use super::*;
577    use memchr::memchr;
578
579    fn check_next(buf: &[u8], delims: &'static [u8]) {
580        let mut bm = BlockMasks::new(buf, delims);
581        for &d in delims {
582            for pos in 0..buf.len() {
583                let a = bm.next(pos, d);
584                let b = memchr(d, &buf[pos..]).map(|i| pos + i);
585                assert_eq!(
586                    a,
587                    b,
588                    "next mismatch at pos {pos} delim {d:?} buf len {}",
589                    buf.len()
590                );
591            }
592        }
593    }
594
595    /// Reference: scalar quote-aware scan from `from`, with XML matching-quote
596    /// semantics (a quote byte is closed only by the same byte).
597    fn scan_unquoted(buf: &[u8], from: usize, d: u8, quotes: &[u8]) -> Option<usize> {
598        let mut active: u8 = 0;
599        for &b in &buf[..from] {
600            if active == 0 {
601                if quotes.contains(&b) {
602                    active = b;
603                }
604            } else if b == active {
605                active = 0;
606            }
607        }
608        for (i, &b) in buf.iter().enumerate().skip(from) {
609            if active == 0 {
610                if quotes.contains(&b) {
611                    active = b;
612                } else if b == d {
613                    return Some(i);
614                }
615            } else if b == active {
616                active = 0;
617            }
618        }
619        None
620    }
621
622    #[test]
623    fn block_boundaries() {
624        let delims: &'static [u8] = b"<>";
625        // delimiter at byte 63 and 64
626        let mut buf = vec![b'x'; 128];
627        buf[63] = b'<';
628        buf[64] = b'>';
629        buf[127] = b'<';
630        check_next(&buf, delims);
631        // field spanning three blocks
632        let mut buf2 = vec![b'x'; 200];
633        buf2[10] = b'<';
634        buf2[70] = b'>';
635        buf2[130] = b'<';
636        check_next(&buf2, delims);
637    }
638
639    #[test]
640    fn straddling() {
641        let delims: &'static [u8] = b"<";
642        // needle straddling will be tested via raw_text_until candidate+verify,
643        // but check next still works across boundary
644        let mut buf = vec![b'a'; 128];
645        // place "</FormattedValue>" straddling 64
646        let needle = b"</FormattedValue>";
647        buf[60..(needle.len() + 60)].copy_from_slice(&needle[..]);
648        let mut bm = BlockMasks::new(&buf, delims);
649        assert_eq!(bm.next(0, b'<'), Some(60));
650        assert_eq!(bm.next(61, b'<'), None);
651    }
652
653    #[test]
654    fn tail_lengths() {
655        let delims: &'static [u8] = b"<>\"'=";
656        for len in [1, 63, 64, 65, 127, 128, 129] {
657            let mut buf = vec![b'x'; len];
658            if len > 0 {
659                buf[len - 1] = b'"';
660            }
661            if len > 1 {
662                buf[0] = b'<';
663            }
664            check_next(&buf, delims);
665        }
666    }
667
668    #[test]
669    fn empty_and_single() {
670        let delims: &'static [u8] = b"<";
671        check_next(b"", delims);
672        check_next(b"<", delims);
673        check_next(b"x", delims);
674    }
675
676    #[test]
677    fn equivalence_random() {
678        let delims: &'static [u8] = b"<>\"'=";
679        let mut rng = 0u64;
680        let mut next_rng = || {
681            rng = rng.wrapping_mul(6364136223846793005).wrapping_add(1);
682            (rng >> 33) as u8
683        };
684        for _ in 0..100 {
685            let len = (next_rng() as usize % 200) + 1;
686            let mut buf = vec![0u8; len];
687            for b in &mut buf {
688                *b = next_rng();
689            }
690            check_next(&buf, delims);
691            // next_any
692            let mut bm = BlockMasks::new(&buf, delims);
693            for pos in 0..len {
694                let a = bm.next_any(pos, delims);
695                let mut exp: Option<(usize, u8)> = None;
696                for &d in delims {
697                    if let Some(p) = memchr(d, &buf[pos..]).map(|i| pos + i) {
698                        if exp.is_none() || p < exp.unwrap().0 {
699                            exp = Some((p, d));
700                        }
701                    }
702                }
703                assert_eq!(a, exp, "next_any mismatch at pos {pos}");
704            }
705        }
706    }
707
708    #[test]
709    fn next_any_correct() {
710        let delims: &'static [u8] = b"\"'>";
711        let buf = br#"a"b'c>d"#;
712        let mut bm = BlockMasks::new(buf, delims);
713        assert_eq!(bm.next_any(0, delims), Some((1, b'"')));
714        assert_eq!(bm.next_any(2, delims), Some((3, b'\'')));
715        assert_eq!(bm.next_any(4, delims), Some((5, b'>')));
716    }
717
718    #[test]
719    fn next_far_fallback() {
720        let delims: &'static [u8] = b"<";
721        let buf = vec![b'x'; 1000];
722        let mut bm = BlockMasks::new(&buf, delims);
723        // hint >256 should use memchr path, but still correct
724        assert_eq!(bm.next_far(0, b'<', 500), None);
725        let mut buf2 = vec![b'x'; 1000];
726        buf2[900] = b'<';
727        let mut bm2 = BlockMasks::new(&buf2, delims);
728        assert_eq!(bm2.next_far(0, b'<', 500), Some(900));
729        assert_eq!(bm2.next_far(0, b'<', 10), Some(900));
730    }
731
732    #[test]
733    fn prefix_xor_basic() {
734        assert_eq!(prefix_xor(0), 0);
735        assert_eq!(prefix_xor(1), u64::MAX); // bit 0 set => bits 0..=63 set
736        assert_eq!(prefix_xor(1 << 3), !0u64 << 3);
737        // two bits toggle parity twice
738        assert_eq!(
739            prefix_xor((1 << 3) | (1 << 5)),
740            (!0u64 << 3) & !(!0u64 << 5)
741        );
742    }
743
744    #[test]
745    fn next_unquoted_matches_reference() {
746        let delims: &'static [u8] = b"<>\"'";
747        let quotes: &'static [u8] = b"\"'";
748        let cases: &[&[u8]] = &[
749            br#"a<b c="x<y>z">d<e>"#,
750            br#"<attr value='has " and < inside'>tail"#,
751            br#"<tag attr="it's">next<gt>"#,
752            br#"<tag a='say "hi"'>next<gt>"#,
753            b"no quotes < > < >",
754            br#"quote="alone'd?"t<"#,
755            b"",
756            b"<",
757            b"\">",
758        ];
759        for buf in cases {
760            let mut bm = BlockMasks::with_quotes(buf, delims, quotes);
761            for d in *b"<>" {
762                let mut from = 0;
763                loop {
764                    let a = bm.next_unquoted(from, d);
765                    let b = scan_unquoted(buf, from, d, quotes);
766                    assert_eq!(a, b, "unquoted mismatch d={d} from={from} buf={buf:?}");
767                    match a {
768                        Some(p) => from = p + 1,
769                        None => break,
770                    }
771                }
772            }
773        }
774    }
775
776    #[test]
777    fn next_unquoted_across_blocks() {
778        let delims: &'static [u8] = b"<>\"";
779        let quotes: &'static [u8] = b"\"";
780        // Quote opens in block 0 and closes in block 1, hiding a '<' at 100 and 200.
781        let mut buf = vec![b'x'; 300];
782        buf[10] = b'"';
783        buf[100] = b'<'; // inside quote
784        buf[150] = b'"'; // close
785        buf[200] = b'<'; // outside
786        let mut bm = BlockMasks::with_quotes(&buf, delims, quotes);
787        assert_eq!(bm.next_unquoted(0, b'<'), Some(200));
788        // Full forward-cursor walk must match the scalar reference at each step.
789        let mut from = 0;
790        loop {
791            let a = bm.next_unquoted(from, b'<');
792            let b = scan_unquoted(&buf, from, b'<', quotes);
793            assert_eq!(a, b, "from {from}");
794            match a {
795                Some(p) => from = p + 1,
796                None => break,
797            }
798        }
799    }
800
801    #[test]
802    fn next_unquoted_random() {
803        let delims: &'static [u8] = b"<>\"'";
804        let quotes: &'static [u8] = b"\"'";
805        let mut rng = 0x1234_5678_9abc_def0u64;
806        let mut next_rng = || {
807            rng = rng.wrapping_mul(6364136223846793005).wrapping_add(1);
808            (rng >> 33) as u8
809        };
810        let alphabet = b"ab <>\"'";
811        for _ in 0..200 {
812            let len = (next_rng() as usize % 300) + 1;
813            let mut buf = vec![0u8; len];
814            for b in &mut buf {
815                *b = alphabet[(next_rng() as usize) % alphabet.len()];
816            }
817            let mut bm = BlockMasks::with_quotes(&buf, delims, quotes);
818            for d in *b"<>" {
819                let mut from = 0;
820                loop {
821                    let a = bm.next_unquoted(from, d);
822                    let b = scan_unquoted(&buf, from, d, quotes);
823                    assert_eq!(a, b, "d={d} from={from} buf={buf:?}");
824                    match a {
825                        Some(p) => from = p + 1,
826                        None => break,
827                    }
828                }
829            }
830        }
831    }
832
833    #[test]
834    fn masks_parity_avx2_sse2_scalar() {
835        let delims: &'static [u8] = b"<>\"'=x";
836        let mut bytes = [0u8; 128];
837        for (i, byte) in bytes.iter_mut().enumerate() {
838            *byte = (i % 17) as u8;
839        }
840        for offset in 0..64 {
841            // SAFETY: `bytes` is 128 bytes, so `offset..offset+64` is in bounds.
842            unsafe {
843                let ptr = bytes.as_ptr().add(offset);
844                let mut expected = [0u64; MAX_DELIMS];
845                masks64_scalar(ptr, delims, &mut expected, delims.len());
846                let mut got = [0u64; MAX_DELIMS];
847                masks64(ptr, delims, &mut got, delims.len());
848                assert_eq!(got, expected);
849                // Single-delimiter path must agree with the multi pass.
850                for (i, &d) in delims.iter().enumerate() {
851                    assert_eq!(mask64(ptr, d), expected[i]);
852                }
853                assert_eq!(mask64_scalar(ptr, delims[0]), expected[0]);
854                #[cfg(target_arch = "x86_64")]
855                {
856                    let mut sse = [0u64; MAX_DELIMS];
857                    masks64_sse2(ptr, delims, &mut sse, delims.len());
858                    assert_eq!(sse, expected);
859                    if has_avx2() {
860                        let mut avx = [0u64; MAX_DELIMS];
861                        masks64_avx2(ptr, delims, &mut avx, delims.len());
862                        assert_eq!(avx, expected);
863                    }
864                }
865            }
866        }
867    }
868}