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}