Skip to main content

serde_json/
swar.rs

1//! Exact SWAR byte primitives: test eight bytes with one integer operation.
2//!
3//! SWAR ("SIMD within a register") treats a `u64` as eight lanes and finds the
4//! interesting lane with ordinary integer arithmetic. No target feature, no
5//! runtime dispatch, no `unsafe`, and identical results on every platform --
6//! which is why the house reaches for it before it reaches for an intrinsic.
7//!
8//! # The trap this module exists to avoid
9//!
10//! The famous zero-byte test is
11//!
12//! ```text
13//! (x - 0x0101..01) & !x & 0x8080..80
14//! ```
15//!
16//! and it is **wrong**. The subtraction borrows across lane boundaries, so a
17//! byte is reported as zero because its NEIGHBOUR was. It is right often
18//! enough to pass a careless test and wrong often enough to corrupt output on
19//! real data. Brick B1s in this crate was measured with the buggy form
20//! deliberately substituted in, to prove the twin tests could actually tell
21//! the difference: three of four failed, which is what a gate is for.
22//!
23//! The form below is exact. Masking off the high bits before the add means the
24//! carry out of lane *n* cannot reach lane *n + 1*:
25//!
26//! ```text
27//! !(((x & !HIGHS) + !HIGHS) | x) & HIGHS
28//! ```
29//!
30//! Every predicate here is built from that one function, so the subtlety is
31//! paid for once, in one place, with tests, rather than re-derived per brick.
32//!
33//! # Reading a mask
34//!
35//! Each predicate returns a `u64` with the high bit of lane *i* set when lane
36//! *i* matched, and every other bit clear. `mask.trailing_zeros() >> 3` is the
37//! index of the first matching byte, which is what makes these usable for
38//! "find the next interesting byte" rather than only "is one present".
39//! Little-endian lane order is assumed throughout, so callers must load with
40//! [`u64::from_le_bytes`].
41
42/// `0x0101_0101_0101_0101` -- one in every lane.
43pub(crate) const ONES: u64 = 0x0101_0101_0101_0101;
44/// `0x8080_8080_8080_8080` -- the high bit of every lane.
45pub(crate) const HIGHS: u64 = 0x8080_8080_8080_8080;
46
47/// High bit set in each lane that is zero.
48///
49/// Exact: no carry crosses a lane boundary. See the module docs for the
50/// popular version of this function that is not exact.
51#[inline(always)]
52pub(crate) fn zero_bytes(x: u64) -> u64 {
53    !(((x & !HIGHS).wrapping_add(!HIGHS)) | x) & HIGHS
54}
55
56/// High bit set in each lane equal to `c`.
57#[inline(always)]
58pub(crate) fn eq_bytes(x: u64, c: u8) -> u64 {
59    zero_bytes(x ^ (c as u64).wrapping_mul(ONES))
60}
61
62/// High bit set in each lane whose bits under `mask` are all clear.
63///
64/// The building block for a range test that needs no comparison. `b < 0x20`
65/// is exactly `b & 0xE0 == 0`, because 0x20 is a single bit and everything
66/// below it has the top three bits clear -- so a control-character test is
67/// this function with `mask = 0xE0`, and it is exact rather than approximate.
68#[inline(always)]
69pub(crate) fn masked_zero_bytes(x: u64, mask: u8) -> u64 {
70    zero_bytes(x & (mask as u64).wrapping_mul(ONES))
71}
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76    use alloc::vec::Vec;
77
78    /// The scalar truth for `zero_bytes`, written independently.
79    fn zero_bytes_scalar(x: u64) -> u64 {
80        let mut out = 0u64;
81        for i in 0..8 {
82            if (x >> (i * 8)) as u8 == 0 {
83                out |= 0x80 << (i * 8);
84            }
85        }
86        out
87    }
88
89    fn eq_bytes_scalar(x: u64, c: u8) -> u64 {
90        let mut out = 0u64;
91        for i in 0..8 {
92            if (x >> (i * 8)) as u8 == c {
93                out |= 0x80 << (i * 8);
94            }
95        }
96        out
97    }
98
99    fn masked_zero_scalar(x: u64, mask: u8) -> u64 {
100        let mut out = 0u64;
101        for i in 0..8 {
102            if ((x >> (i * 8)) as u8) & mask == 0 {
103                out |= 0x80 << (i * 8);
104            }
105        }
106        out
107    }
108
109    /// A deterministic spread of words, including every single-byte case in
110    /// every lane -- which is where a cross-lane borrow bug shows up.
111    fn words() -> Vec<u64> {
112        let mut v = Vec::new();
113        for b in 0..=255u8 {
114            for lane in 0..8 {
115                // The byte alone in one lane.
116                v.push((b as u64) << (lane * 8));
117                // The byte in one lane with 0x01 everywhere else: the case the
118                // borrowing form of the zero test gets wrong.
119                let mut w = ONES;
120                w &= !(0xFFu64 << (lane * 8));
121                w |= (b as u64) << (lane * 8);
122                v.push(w);
123                // And with 0xFF everywhere else.
124                let mut w = u64::MAX;
125                w &= !(0xFFu64 << (lane * 8));
126                w |= (b as u64) << (lane * 8);
127                v.push(w);
128            }
129        }
130        v.push(0);
131        v.push(u64::MAX);
132        v.push(ONES);
133        v.push(HIGHS);
134        // A cheap deterministic PRNG, so the spread is not only structured.
135        let mut s = 0x243F_6A88_85A3_08D3u64;
136        for _ in 0..4096 {
137            s ^= s << 13;
138            s ^= s >> 7;
139            s ^= s << 17;
140            v.push(s);
141        }
142        v
143    }
144
145    #[test]
146    fn zero_bytes_matches_scalar() {
147        for x in words() {
148            assert_eq!(
149                zero_bytes(x),
150                zero_bytes_scalar(x),
151                "zero_bytes disagreed on {x:#018x}"
152            );
153        }
154    }
155
156    #[test]
157    fn eq_bytes_matches_scalar() {
158        // Every byte value as the needle, against the structured spread.
159        for c in [0u8, 1, 0x1F, 0x20, 0x22, 0x5C, 0x7F, 0x80, 0xFE, 0xFF] {
160            for x in words() {
161                assert_eq!(
162                    eq_bytes(x, c),
163                    eq_bytes_scalar(x, c),
164                    "eq_bytes({x:#018x}, {c:#04x}) disagreed"
165                );
166            }
167        }
168    }
169
170    #[test]
171    fn masked_zero_bytes_matches_scalar() {
172        for mask in [0xE0u8, 0xF0, 0x80, 0xFF, 0x01] {
173            for x in words() {
174                assert_eq!(
175                    masked_zero_bytes(x, mask),
176                    masked_zero_scalar(x, mask),
177                    "masked_zero_bytes({x:#018x}, {mask:#04x}) disagreed"
178                );
179            }
180        }
181    }
182
183    /// `b & 0xE0 == 0` must be exactly `b < 0x20`, for every byte. This is the
184    /// identity the escape and whitespace scanners both rely on, so it is
185    /// asserted rather than assumed.
186    #[test]
187    fn masked_zero_is_a_less_than_test() {
188        for b in 0..=255u8 {
189            assert_eq!(b & 0xE0 == 0, b < 0x20, "0xE0 mask wrong for {b:#04x}");
190        }
191    }
192
193    /// The borrowing form really is wrong, so the tests above are load-bearing
194    /// rather than decorative. If this test ever fails, the exact form and the
195    /// buggy form agree everywhere tested and the gate has stopped
196    /// discriminating -- which would mean the spread in `words()` got weaker.
197    #[test]
198    fn the_classic_zero_test_is_wrong_somewhere() {
199        fn buggy(x: u64) -> u64 {
200            x.wrapping_sub(ONES) & !x & HIGHS
201        }
202        let disagreements = words()
203            .into_iter()
204            .filter(|&x| buggy(x) != zero_bytes(x))
205            .count();
206        assert!(
207            disagreements > 0,
208            "the buggy zero-byte test agreed with the exact one everywhere \
209             tested -- the test spread has stopped discriminating"
210        );
211    }
212}