form_net/multipart/
boundary.rs

1//! The multipart boundary: validation, the delimiter bytes, and the failure
2//! table of the streaming matcher.
3
4use core::fmt;
5
6use crate::error::{FormError, Location, SyntaxError};
7
8/// The longest boundary RFC 2046 allows.
9pub const MAX_BOUNDARY_LEN: usize = 70;
10
11/// The longest delimiter: CRLF, `--`, and a 70-byte boundary.
12pub const MAX_DELIMITER_LEN: usize = 74;
13
14/// RFC 2046 `bchars`: digits, letters, `'()+_,-./:=?`, and space.
15const fn is_bchar(b: u8) -> bool {
16    b.is_ascii_alphanumeric()
17        || matches!(
18            b,
19            b'\''
20                | b'('
21                | b')'
22                | b'+'
23                | b'_'
24                | b','
25                | b'-'
26                | b'.'
27                | b'/'
28                | b':'
29                | b'='
30                | b'?'
31                | b' '
32        )
33}
34
35/// A validated boundary with its delimiter (`CRLF "--" boundary`, 5 to 74
36/// bytes) and the failure table of the streaming matcher, built once.
37///
38/// `Debug` prints the boundary: it is not secret.
39///
40/// # Examples
41///
42/// ```
43/// use form_net::Boundary;
44///
45/// let b = Boundary::new(b"----WebKitFormBoundaryx7Y")?;
46/// assert_eq!(b.delimiter(), b"\r\n------WebKitFormBoundaryx7Y");
47/// assert!(Boundary::new(b"").is_err());
48/// assert!(Boundary::new(&[b'a'; 71]).is_err());
49/// assert!(Boundary::new(b"ends with space ").is_err());
50/// assert!(Boundary::new(b"has\"quote").is_err());
51/// assert_eq!(Boundary::parse(b"multipart/form-data; boundary=\"a b\"")?.as_bytes(), b"a b");
52/// # Ok::<(), form_net::FormError>(())
53/// ```
54#[must_use]
55#[derive(Clone, Copy, PartialEq, Eq)]
56pub struct Boundary {
57    delimiter: [u8; MAX_DELIMITER_LEN],
58    fail: [u8; MAX_DELIMITER_LEN],
59    len: u8,
60}
61
62impl Boundary {
63    /// Validates a bare boundary (without `--`): 1 to 70 bytes of RFC 2046
64    /// `bchars`, not ending in a space.
65    ///
66    /// # Errors
67    ///
68    /// `Syntax { InvalidBoundary }`, at the offending byte.
69    ///
70    /// # Examples
71    ///
72    /// ```
73    /// assert_eq!(form_net::Boundary::new(b"X")?.delimiter(), b"\r\n--X");
74    /// # Ok::<(), form_net::FormError>(())
75    /// ```
76    pub fn new(boundary: &[u8]) -> Result<Boundary, FormError> {
77        let invalid =
78            |at: usize| FormError::syntax(SyntaxError::InvalidBoundary, Location::at(at as u64));
79        if boundary.is_empty() {
80            return Err(invalid(0));
81        }
82        if boundary.len() > MAX_BOUNDARY_LEN {
83            return Err(invalid(MAX_BOUNDARY_LEN));
84        }
85        if let Some(at) = boundary.iter().position(|&b| !is_bchar(b)) {
86            return Err(invalid(at));
87        }
88        if boundary.last() == Some(&b' ') {
89            return Err(invalid(boundary.len().wrapping_sub(1)));
90        }
91        let mut delimiter = [0u8; MAX_DELIMITER_LEN];
92        let len = boundary.len().wrapping_add(4);
93        if let Some(head) = delimiter.get_mut(..4) {
94            head.copy_from_slice(b"\r\n--");
95        }
96        if let Some(rest) = delimiter.get_mut(4..len) {
97            rest.copy_from_slice(boundary);
98        }
99        let fail = failure_table(&delimiter, len);
100        Ok(Boundary {
101            delimiter,
102            fail,
103            len: len as u8,
104        })
105    }
106
107    /// Reads the boundary from a whole `multipart/form-data` `Content-Type`
108    /// value.
109    ///
110    /// # Errors
111    ///
112    /// `UnsupportedMediaType` for any other media type;
113    /// `Syntax { InvalidContentType | MissingBoundary | DuplicateBoundary | InvalidBoundary }`.
114    ///
115    /// # Examples
116    ///
117    /// ```
118    /// let b = form_net::Boundary::parse(b"multipart/form-data; boundary=----x")?;
119    /// assert_eq!(b.as_bytes(), b"----x");
120    /// assert!(form_net::Boundary::parse(b"text/plain").is_err());
121    /// # Ok::<(), form_net::FormError>(())
122    /// ```
123    pub fn parse(content_type: &[u8]) -> Result<Boundary, FormError> {
124        match crate::kind::FormKind::detect(content_type)? {
125            crate::kind::FormKind::Multipart(b) => Ok(b),
126            crate::kind::FormKind::Urlencoded => Err(FormError::UnsupportedMediaType),
127        }
128    }
129
130    /// The boundary, without `--`.
131    ///
132    /// # Examples
133    ///
134    /// ```
135    /// assert_eq!(form_net::Boundary::new(b"abc")?.as_bytes(), b"abc");
136    /// # Ok::<(), form_net::FormError>(())
137    /// ```
138    #[must_use]
139    pub fn as_bytes(&self) -> &[u8] {
140        self.delimiter.get(4..usize::from(self.len)).unwrap_or(&[])
141    }
142
143    /// The full delimiter: CRLF, `--`, and the boundary.
144    ///
145    /// # Examples
146    ///
147    /// ```
148    /// assert_eq!(form_net::Boundary::new(b"abc")?.delimiter(), b"\r\n--abc");
149    /// # Ok::<(), form_net::FormError>(())
150    /// ```
151    #[must_use]
152    pub fn delimiter(&self) -> &[u8] {
153        self.delimiter.get(..usize::from(self.len)).unwrap_or(&[])
154    }
155
156    /// One step of the matcher: the new state after byte `c` from state `k`
157    /// (the number of delimiter bytes matched so far, below the length).
158    #[inline]
159    pub(crate) fn step(&self, mut k: usize, c: u8) -> usize {
160        #[cfg(test)]
161        tests::count_visit();
162        loop {
163            if self.delimiter.get(k) == Some(&c) {
164                return k.wrapping_add(1);
165            }
166            if k == 0 {
167                return 0;
168            }
169            k = usize::from(*self.fail.get(k.wrapping_sub(1)).unwrap_or(&0));
170        }
171    }
172
173    pub(crate) fn len(&self) -> usize {
174        usize::from(self.len)
175    }
176
177    /// Runs the matcher over `hay` from state `k`. Returns the final state
178    /// and, when the delimiter completed, the index just after it.
179    ///
180    /// From state 0 nothing before a CR can start a match (the delimiter
181    /// starts with CR), so those bytes are skipped eight at a time.
182    pub(crate) fn run(&self, mut k: usize, hay: &[u8]) -> (usize, Option<usize>) {
183        let len = self.len();
184        let mut i = 0usize;
185        while i < hay.len() {
186            if k == 0 {
187                i = crate::scan::find_byte(hay, i, b'\r');
188                if i >= hay.len() {
189                    break;
190                }
191            }
192            let c = *hay.get(i).unwrap_or(&0);
193            k = self.step(k, c);
194            i = i.wrapping_add(1);
195            if k == len {
196                return (k, Some(i));
197            }
198        }
199        (k, None)
200    }
201}
202
203/// The Knuth-Morris-Pratt failure table: `fail[i]` is the length of the
204/// longest proper prefix of `d[..=i]` that is also its suffix.
205fn failure_table(d: &[u8; MAX_DELIMITER_LEN], len: usize) -> [u8; MAX_DELIMITER_LEN] {
206    let mut fail = [0u8; MAX_DELIMITER_LEN];
207    let mut k = 0usize;
208    for i in 1..len {
209        let c = *d.get(i).unwrap_or(&0);
210        while k > 0 && d.get(k) != Some(&c) {
211            k = usize::from(*fail.get(k.wrapping_sub(1)).unwrap_or(&0));
212        }
213        if d.get(k) == Some(&c) {
214            k = k.wrapping_add(1);
215        }
216        if let Some(slot) = fail.get_mut(i) {
217            *slot = k as u8;
218        }
219    }
220    fail
221}
222
223impl fmt::Debug for Boundary {
224    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
225        // bchars are printable ASCII, so this is always valid text.
226        let text = core::str::from_utf8(self.as_bytes()).unwrap_or("");
227        f.debug_tuple("Boundary").field(&text).finish()
228    }
229}
230
231#[cfg(test)]
232pub(crate) mod tests {
233    use super::*;
234    use alloc::vec::Vec;
235    use core::cell::Cell;
236
237    std::thread_local! {
238        static VISITS: Cell<u64> = const { Cell::new(0) };
239    }
240
241    /// Counts one byte the matcher compares (one call to `step`, which may
242    /// follow the failure table several times: KMP bounds those by the
243    /// bytes seen).
244    pub(crate) fn count_visit() {
245        VISITS.with(|v| v.set(v.get() + 1));
246    }
247
248    #[cfg(feature = "alloc")]
249    pub(crate) fn visits() -> u64 {
250        VISITS.with(Cell::get)
251    }
252
253    /// Runs `body` through a parser in `chunk`-byte pieces and returns the
254    /// matcher's byte visits.
255    #[cfg(feature = "alloc")]
256    fn visits_for(body: &[u8], chunk: usize) -> u64 {
257        use crate::{Event, Limits, MultipartParser, Policy};
258        let limits = Limits::DEFAULT
259            .with_max_body_bytes(64 << 20)
260            .with_max_file_bytes(64 << 20);
261        let mut p = MultipartParser::new(
262            Boundary::new(b"boundary").unwrap(),
263            &limits,
264            &Policy::DEFAULT,
265        )
266        .unwrap();
267        let before = visits();
268        let chunks: Vec<&[u8]> = body.chunks(chunk).collect();
269        for (i, c) in chunks.iter().enumerate() {
270            let mut rest: &[u8] = c;
271            loop {
272                let step = p.parse(rest, i + 1 == chunks.len()).unwrap();
273                rest = &rest[step.consumed..];
274                if matches!(step.event, Event::NeedInput | Event::End) {
275                    break;
276                }
277            }
278        }
279        visits() - before
280    }
281
282    #[cfg(feature = "alloc")]
283    #[test]
284    fn test_matcher_visits_are_linear_for_adversarial_bodies() {
285        let head = b"--boundary\r\nContent-Disposition: form-data; name=f; filename=a\r\n\r\n";
286        let shapes: [&[u8]; 4] = [b"\r", b"\r\n--boundar", b"\r\n-", b"-"];
287        for shape in shapes {
288            for chunk in [1usize, 7, 4096] {
289                let mut body = head.to_vec();
290                while body.len() < head.len() + 64 * 1024 {
291                    body.extend_from_slice(shape);
292                }
293                let data = (body.len() - head.len()) as u64;
294                body.extend_from_slice(b"\r\n--boundary--");
295                let v = visits_for(&body, chunk);
296                // Each data byte is examined a bounded number of times
297                // (KMP), plus at most a delimiter's length rescanned per
298                // chunk boundary.
299                let bound = 2 * data + (body.len() / chunk + 1) as u64 * 16 + 64;
300                assert!(
301                    v <= bound,
302                    "{shape:?} chunk {chunk}: {v} visits for {data} bytes"
303                );
304            }
305        }
306    }
307
308    fn naive_find(hay: &[u8], needle: &[u8]) -> Option<usize> {
309        hay.windows(needle.len())
310            .position(|w| w == needle)
311            .map(|p| p + needle.len())
312    }
313
314    #[test]
315    fn test_boundary_every_byte_value() {
316        for b in 0u8..=255 {
317            let r = Boundary::new(&[b'a', b, b'z']);
318            assert_eq!(r.is_ok(), is_bchar(b), "byte {b:#x}");
319        }
320    }
321
322    #[test]
323    fn test_boundary_lengths_and_trailing_space() {
324        assert!(Boundary::new(b"").is_err());
325        assert!(Boundary::new(b"a").is_ok());
326        assert!(Boundary::new(&[b'a'; 69]).is_ok());
327        assert!(Boundary::new(&[b'a'; 70]).is_ok());
328        assert!(Boundary::new(&[b'a'; 71]).is_err());
329        assert!(Boundary::new(b"a ").is_err());
330        assert!(Boundary::new(b"a b").is_ok());
331        assert!(Boundary::new(b" ").is_err());
332    }
333
334    #[test]
335    fn test_failure_table_matches_definition() {
336        for raw in [&b"a"[..], b"aaaa", b"-", b"--", b"-a-", b"---", b"a-b--a"] {
337            let b = Boundary::new(raw).unwrap();
338            let d = b.delimiter();
339            for i in 0..d.len() {
340                let best = (0..=i)
341                    .rev()
342                    .find(|&l| l <= i && d[..l] == d[i + 1 - l..=i])
343                    .unwrap();
344                assert_eq!(usize::from(b.fail[i]), best, "{raw:?} at {i}");
345            }
346        }
347    }
348
349    #[test]
350    fn test_run_finds_like_naive_and_carries_state() {
351        let b = Boundary::new(b"-ab").unwrap();
352        let d = b.delimiter().to_vec();
353        let mut hay = Vec::new();
354        hay.extend_from_slice(b"x\r\n--a\r\n\r\n--\r\n--");
355        hay.extend_from_slice(&d);
356        hay.extend_from_slice(b"tail");
357        let expected = naive_find(&hay, &d);
358        assert_eq!(b.run(0, &hay).1, expected);
359        // Split at every byte: the state carries across.
360        for split in 0..hay.len() {
361            let (k, found) = b.run(0, &hay[..split]);
362            let total = match found {
363                Some(i) => Some(i),
364                None => b.run(k, &hay[split..]).1.map(|i| i + split),
365            };
366            assert_eq!(total, expected, "split {split}");
367        }
368    }
369
370    #[test]
371    fn test_parse_reports_unsupported_for_urlencoded() {
372        assert_eq!(
373            Boundary::parse(b"application/x-www-form-urlencoded"),
374            Err(FormError::UnsupportedMediaType)
375        );
376    }
377}
form_net/multipart/boundary.rs

form_net/multipart/
boundary.rs
