sark_http/field/scan/
mod.rs

1//! Allocation-free scans over immutable wire bytes.
2
3use core::{mem, num::NonZero};
4
5const LANE: usize = 16;
6
7mod raw;
8
9/// One actual forward-search match retained on its exact immutable source.
10#[derive(Clone, Copy)]
11pub struct Match<'a> {
12    bytes: &'a [u8],
13    end: NonZero<usize>,
14}
15
16impl<'a> Match<'a> {
17    pub fn find(byte: u8, bytes: &'a [u8]) -> Option<Self> {
18        let index = memchr::memchr(byte, bytes)?;
19        // SAFETY: memchr returned this byte's position inside the exact retained source.
20        Some(unsafe { raw::found(bytes, index) })
21    }
22
23    pub fn find2(first: u8, second: u8, bytes: &'a [u8]) -> Option<Self> {
24        let index = memchr::memchr2(first, second, bytes)?;
25        // SAFETY: memchr2 returned a matched position inside the exact retained source.
26        Some(unsafe { raw::found(bytes, index) })
27    }
28
29    pub(crate) fn find_by(bytes: &'a [u8], mut matches: impl FnMut(u8) -> bool) -> Option<Self> {
30        let index = bytes.iter().position(|byte| matches(*byte))?;
31        // SAFETY: the iterator returned this position inside the exact retained source.
32        Some(unsafe { raw::found(bytes, index) })
33    }
34
35    pub const fn start(self) -> usize {
36        self.end.get() - 1
37    }
38
39    pub const fn end(self) -> NonZero<usize> {
40        self.end
41    }
42
43    pub fn byte(self) -> u8 {
44        raw::byte(self)
45    }
46
47    pub fn prefix(self) -> &'a [u8] {
48        raw::before::<false>(self)
49    }
50
51    pub fn through(self) -> &'a [u8] {
52        raw::before::<true>(self)
53    }
54
55    pub fn tail(self) -> &'a [u8] {
56        raw::after::<true>(self)
57    }
58
59    pub fn suffix(self) -> &'a [u8] {
60        raw::after::<false>(self)
61    }
62}
63
64#[derive(PartialEq, Eq)]
65pub enum Outcome<T> {
66    Found(T),
67    Invalid { offset: usize, actual: u8 },
68    Partial,
69}
70
71/// A pointer-sized view over bytes scanned as HTTP/1 field syntax.
72#[repr(transparent)]
73pub struct Bytes<'a>(&'a [u8]);
74
75impl<'a> Bytes<'a> {
76    pub const fn new(bytes: &'a [u8]) -> Self {
77        Self(bytes)
78    }
79
80    pub fn name(&self, start: usize) -> Outcome<(usize, u8)> {
81        let Some(rest) = self.0.get(start..) else {
82            return Outcome::Partial;
83        };
84        let (prefix, rest) = rest.split_at(rest.len().min(LANE));
85        let outcome = name_tail(prefix, start);
86        if !matches!(outcome, Outcome::Partial) {
87            return outcome;
88        }
89        if rest.is_empty() {
90            return Outcome::Partial;
91        }
92        let index = start + prefix.len();
93        if rest.len() < LANE {
94            return name_tail(rest, index);
95        }
96        name_simd(rest, index)
97    }
98
99    pub fn value(&self, start: usize) -> Outcome<usize> {
100        let Some(rest) = self.0.get(start..) else {
101            return Outcome::Partial;
102        };
103        value_simd(rest, start)
104    }
105}
106
107fn name_simd(bytes: &[u8], mut index: usize) -> Outcome<(usize, u8)> {
108    let (lanes, tail) = bytes.as_chunks::<LANE>();
109    let (groups, lanes) = lanes.as_chunks::<4>();
110    for group in groups {
111        let [a, b, c, d] = group;
112        let masks = [
113            mask::<true>(*a),
114            mask::<true>(*b),
115            mask::<true>(*c),
116            mask::<true>(*d),
117        ];
118        let Some(found) = NonZero::new(packed(masks)) else {
119            index += 4 * LANE;
120            continue;
121        };
122        let (offset, byte) = first(group, found);
123        return name_at(index + offset, byte);
124    }
125    for lane in lanes {
126        let bits = mask::<true>(*lane);
127        if bits != 0 {
128            let (offset, byte) = in_lane(lane, bits);
129            return name_at(index + offset, byte);
130        }
131        index += LANE;
132    }
133    if tail.is_empty() {
134        Outcome::Partial
135    } else {
136        name_tail(tail, index)
137    }
138}
139
140fn value_simd(bytes: &[u8], mut index: usize) -> Outcome<usize> {
141    let Some((lane, rest)) = bytes.split_first_chunk::<LANE>() else {
142        return value_tail(bytes, index);
143    };
144    let bits = mask::<false>(*lane);
145    if bits != 0 {
146        let (offset, byte) = in_lane(lane, bits);
147        return value_at(bytes, offset, index + offset, byte);
148    }
149    index += LANE;
150    let (lanes, tail) = rest.as_chunks::<LANE>();
151    let (groups, lanes) = lanes.as_chunks::<4>();
152    let mut consumed = LANE;
153    for group in groups {
154        let [a, b, c, d] = group;
155        let masks = [
156            mask::<false>(*a),
157            mask::<false>(*b),
158            mask::<false>(*c),
159            mask::<false>(*d),
160        ];
161        let Some(found) = NonZero::new(packed(masks)) else {
162            index += 4 * LANE;
163            consumed += 4 * LANE;
164            continue;
165        };
166        let (offset, byte) = first(group, found);
167        return value_at(bytes, consumed + offset, index + offset, byte);
168    }
169    for lane in lanes {
170        let bits = mask::<false>(*lane);
171        if bits != 0 {
172            let (offset, byte) = in_lane(lane, bits);
173            return value_at(bytes, consumed + offset, index + offset, byte);
174        }
175        index += LANE;
176        consumed += LANE;
177    }
178    if tail.is_empty() {
179        Outcome::Partial
180    } else {
181        value_tail(tail, index)
182    }
183}
184
185fn name_tail(bytes: &[u8], index: usize) -> Outcome<(usize, u8)> {
186    for (offset, &byte) in bytes.iter().enumerate() {
187        let pos = index + offset;
188        if byte == b':' || byte == b'\r' {
189            return Outcome::Found((pos, byte));
190        }
191        if !crate::field::Error::is_name_byte(byte) {
192            return Outcome::Invalid {
193                offset: pos,
194                actual: byte,
195            };
196        }
197    }
198    Outcome::Partial
199}
200
201fn value_tail(bytes: &[u8], index: usize) -> Outcome<usize> {
202    for (offset, &byte) in bytes.iter().enumerate() {
203        if byte == b'\r' {
204            return value_at(bytes, offset, index + offset, byte);
205        }
206        if !crate::field::Error::is_text(byte) {
207            return Outcome::Invalid {
208                offset: index + offset,
209                actual: byte,
210            };
211        }
212    }
213    Outcome::Partial
214}
215
216/// Lowest byte one nonzero lane mask selects inside that lane.
217///
218/// A lane mask carries exactly `LANE` bits, so its lowest set bit already names
219/// an in-lane index: the byte needs no second range check and no panic path.
220fn in_lane(lane: &[u8; LANE], bits: u16) -> (usize, u8) {
221    let offset = bits.trailing_zeros() as usize & (LANE - 1);
222    (offset, lane[offset])
223}
224
225/// Byte-ordered bits of the four lane masks of one group.
226fn packed(masks: [u16; 4]) -> u64 {
227    let mut bits = 0;
228    for (lane, mask) in masks.into_iter().enumerate() {
229        bits |= u64::from(mask) << (lane * LANE);
230    }
231    bits
232}
233
234/// Lowest byte one nonzero group mask selects.
235///
236/// The mask carries one bit per byte, so its lowest set bit names the byte
237/// without a second search or a panic path.
238fn first(group: &[[u8; LANE]; 4], found: NonZero<u64>) -> (usize, u8) {
239    let ordinal = found.get().trailing_zeros() as usize;
240    (ordinal, group[ordinal / LANE][ordinal % LANE])
241}
242
243fn mask<const NAME: bool>(lane: [u8; LANE]) -> u16 {
244    let flags = lane.map(|byte| {
245        let invalid = if NAME {
246            !crate::field::Error::is_name_byte(byte)
247        } else {
248            !crate::field::Error::is_text(byte)
249        };
250        u8::from(invalid) << 7
251    });
252    let mut bits = 0;
253    // Each byte is 0 or 0x80; packing preserves byte order without cross-byte carries.
254    for (index, chunk) in flags.as_chunks::<8>().0.iter().enumerate() {
255        let word = u64::from_le_bytes(*chunk);
256        bits |= ((word.wrapping_mul(0x0002_0408_1020_4081) >> 56) as u16) << (index * 8);
257    }
258    bits
259}
260
261fn name_at(pos: usize, byte: u8) -> Outcome<(usize, u8)> {
262    if byte == b':' || byte == b'\r' {
263        Outcome::Found((pos, byte))
264    } else {
265        Outcome::Invalid {
266            offset: pos,
267            actual: byte,
268        }
269    }
270}
271
272fn value_at(bytes: &[u8], offset: usize, pos: usize, byte: u8) -> Outcome<usize> {
273    if byte != b'\r' {
274        return Outcome::Invalid {
275            offset: pos,
276            actual: byte,
277        };
278    }
279    let Some(next) = bytes.get(offset + 1) else {
280        return Outcome::Partial;
281    };
282    if *next == b'\n' {
283        Outcome::Found(pos)
284    } else {
285        Outcome::Invalid {
286            offset: pos + 1,
287            actual: *next,
288        }
289    }
290}
291
292const _: () = {
293    let word = mem::size_of::<usize>();
294    assert!(mem::size_of::<Bytes<'_>>() == 2 * word);
295    assert!(mem::size_of::<Outcome<usize>>() == 2 * word);
296    assert!(mem::size_of::<Outcome<(usize, u8)>>() == 3 * word);
297    assert!(mem::size_of::<Match<'_>>() == 3 * word);
298    assert!(mem::size_of::<Option<Match<'_>>>() == 3 * word);
299};
sark_http/field/scan/mod.rs

sark_http/field/scan/
mod.rs
