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    /// A fresh boundary: `form-net-` and 32 lowercase hex characters from 16
108    /// bytes of the OS random source (41 bytes, all `bchars`).
109    ///
110    /// # Errors
111    ///
112    /// `Random` when the OS random source fails (fail closed).
113    ///
114    /// # Examples
115    ///
116    /// ```
117    /// let b = form_net::Boundary::generate()?;
118    /// assert_eq!(b.as_bytes().len(), 41);
119    /// assert!(b.as_bytes().starts_with(b"form-net-"));
120    /// assert_ne!(b, form_net::Boundary::generate()?);
121    /// # Ok::<(), form_net::FormError>(())
122    /// ```
123    #[cfg(feature = "random")]
124    #[cfg_attr(docsrs, doc(cfg(feature = "random")))]
125    pub fn generate() -> Result<Boundary, FormError> {
126        let hex = crate::random::random_hex()?;
127        let mut name = [0u8; 41];
128        if let Some(head) = name.get_mut(..9) {
129            head.copy_from_slice(b"form-net-");
130        }
131        if let Some(tail) = name.get_mut(9..) {
132            tail.copy_from_slice(&hex);
133        }
134        Boundary::new(&name)
135    }
136
137    /// Reads the boundary from a whole `multipart/form-data` `Content-Type`
138    /// value.
139    ///
140    /// # Errors
141    ///
142    /// `UnsupportedMediaType` for any other media type;
143    /// `Syntax { InvalidContentType | MissingBoundary | DuplicateBoundary | InvalidBoundary }`.
144    ///
145    /// # Examples
146    ///
147    /// ```
148    /// let b = form_net::Boundary::parse(b"multipart/form-data; boundary=----x")?;
149    /// assert_eq!(b.as_bytes(), b"----x");
150    /// assert!(form_net::Boundary::parse(b"text/plain").is_err());
151    /// # Ok::<(), form_net::FormError>(())
152    /// ```
153    pub fn parse(content_type: &[u8]) -> Result<Boundary, FormError> {
154        match crate::kind::FormKind::detect(content_type)? {
155            crate::kind::FormKind::Multipart(b) => Ok(b),
156            crate::kind::FormKind::Urlencoded => Err(FormError::UnsupportedMediaType),
157        }
158    }
159
160    /// The boundary, without `--`.
161    ///
162    /// # Examples
163    ///
164    /// ```
165    /// assert_eq!(form_net::Boundary::new(b"abc")?.as_bytes(), b"abc");
166    /// # Ok::<(), form_net::FormError>(())
167    /// ```
168    #[must_use]
169    pub fn as_bytes(&self) -> &[u8] {
170        self.delimiter.get(4..usize::from(self.len)).unwrap_or(&[])
171    }
172
173    /// The full delimiter: CRLF, `--`, and the boundary.
174    ///
175    /// # Examples
176    ///
177    /// ```
178    /// assert_eq!(form_net::Boundary::new(b"abc")?.delimiter(), b"\r\n--abc");
179    /// # Ok::<(), form_net::FormError>(())
180    /// ```
181    #[must_use]
182    pub fn delimiter(&self) -> &[u8] {
183        self.delimiter.get(..usize::from(self.len)).unwrap_or(&[])
184    }
185
186    /// One step of the matcher: the new state after byte `c` from state `k`
187    /// (the number of delimiter bytes matched so far, below the length).
188    #[inline]
189    pub(crate) fn step(&self, mut k: usize, c: u8) -> usize {
190        #[cfg(test)]
191        tests::count_visit();
192        loop {
193            if self.delimiter.get(k) == Some(&c) {
194                return k.wrapping_add(1);
195            }
196            if k == 0 {
197                return 0;
198            }
199            k = usize::from(*self.fail.get(k.wrapping_sub(1)).unwrap_or(&0));
200        }
201    }
202
203    pub(crate) fn len(&self) -> usize {
204        usize::from(self.len)
205    }
206
207    /// Runs the matcher over `hay` from state `k`. Returns the final state
208    /// and, when the delimiter completed, the index just after it.
209    ///
210    /// From state 0 a match can only start at a CR followed by LF: the
211    /// delimiter starts with CRLF, and the boundary cannot hold a CR. So the
212    /// search skips to the next CRLF eight positions at a time and compares
213    /// the delimiter there whole; a miss resumes two bytes on, past the LF.
214    /// Only near the end of `hay`, where the delimiter may continue into
215    /// the next chunk, does it step the automaton byte by byte, so the state
216    /// it returns is exactly the automaton's (D-102).
217    pub(crate) fn run(&self, mut k: usize, hay: &[u8]) -> (usize, Option<usize>) {
218        let len = self.len();
219        let delimiter = self.delimiter();
220        let mut i = 0usize;
221        while i < hay.len() {
222            if k == 0 {
223                i = crate::scan::find_pair(hay, i, b'\r', b'\n');
224                if i >= hay.len() {
225                    break;
226                }
227                if let Some(candidate) = hay.get(i..i.wrapping_add(len)) {
228                    // The last byte first: a near miss usually differs there.
229                    if candidate.last() == delimiter.last() && candidate == delimiter {
230                        return (len, Some(i.wrapping_add(len)));
231                    }
232                    i = i.wrapping_add(2);
233                    continue;
234                }
235            }
236            let c = *hay.get(i).unwrap_or(&0);
237            k = self.step(k, c);
238            i = i.wrapping_add(1);
239            if k == len {
240                return (k, Some(i));
241            }
242        }
243        (k, None)
244    }
245}
246
247/// The Knuth-Morris-Pratt failure table: `fail[i]` is the length of the
248/// longest proper prefix of `d[..=i]` that is also its suffix.
249fn failure_table(d: &[u8; MAX_DELIMITER_LEN], len: usize) -> [u8; MAX_DELIMITER_LEN] {
250    let mut fail = [0u8; MAX_DELIMITER_LEN];
251    let mut k = 0usize;
252    for i in 1..len {
253        let c = *d.get(i).unwrap_or(&0);
254        while k > 0 && d.get(k) != Some(&c) {
255            k = usize::from(*fail.get(k.wrapping_sub(1)).unwrap_or(&0));
256        }
257        if d.get(k) == Some(&c) {
258            k = k.wrapping_add(1);
259        }
260        if let Some(slot) = fail.get_mut(i) {
261            *slot = k as u8;
262        }
263    }
264    fail
265}
266
267impl fmt::Debug for Boundary {
268    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
269        // bchars are printable ASCII, so this is always valid text.
270        let text = core::str::from_utf8(self.as_bytes()).unwrap_or("");
271        f.debug_tuple("Boundary").field(&text).finish()
272    }
273}
274
275#[cfg(test)]
276pub(crate) mod tests {
277    use super::*;
278    use alloc::vec::Vec;
279    use core::cell::Cell;
280
281    std::thread_local! {
282        static VISITS: Cell<u64> = const { Cell::new(0) };
283    }
284
285    /// Counts one byte the matcher compares (one call to `step`, which may
286    /// follow the failure table several times: KMP bounds those by the
287    /// bytes seen).
288    pub(crate) fn count_visit() {
289        VISITS.with(|v| v.set(v.get() + 1));
290    }
291
292    #[cfg(feature = "alloc")]
293    pub(crate) fn visits() -> u64 {
294        VISITS.with(Cell::get)
295    }
296
297    /// Runs `body` through a parser in `chunk`-byte pieces and returns the
298    /// matcher's byte visits.
299    #[cfg(feature = "alloc")]
300    fn visits_for(body: &[u8], chunk: usize) -> u64 {
301        use crate::{Event, Limits, MultipartParser, Policy};
302        let limits = Limits::DEFAULT
303            .with_max_body_bytes(64 << 20)
304            .with_max_file_bytes(64 << 20);
305        let mut p = MultipartParser::new(
306            Boundary::new(b"boundary").unwrap(),
307            &limits,
308            &Policy::DEFAULT,
309        )
310        .unwrap();
311        let before = visits();
312        let chunks: Vec<&[u8]> = body.chunks(chunk).collect();
313        for (i, c) in chunks.iter().enumerate() {
314            let mut rest: &[u8] = c;
315            loop {
316                let step = p.parse(rest, i + 1 == chunks.len()).unwrap();
317                rest = &rest[step.consumed..];
318                if matches!(step.event, Event::NeedInput | Event::End) {
319                    break;
320                }
321            }
322        }
323        visits() - before
324    }
325
326    #[cfg(feature = "alloc")]
327    #[test]
328    fn test_matcher_visits_are_linear_for_adversarial_bodies() {
329        let head = b"--boundary\r\nContent-Disposition: form-data; name=f; filename=a\r\n\r\n";
330        let shapes: [&[u8]; 4] = [b"\r", b"\r\n--boundar", b"\r\n-", b"-"];
331        for shape in shapes {
332            for chunk in [1usize, 7, 4096] {
333                let mut body = head.to_vec();
334                while body.len() < head.len() + 64 * 1024 {
335                    body.extend_from_slice(shape);
336                }
337                let data = (body.len() - head.len()) as u64;
338                body.extend_from_slice(b"\r\n--boundary--");
339                let v = visits_for(&body, chunk);
340                // Each data byte is examined a bounded number of times
341                // (KMP), plus at most a delimiter's length rescanned per
342                // chunk boundary.
343                let bound = 2 * data + (body.len() / chunk + 1) as u64 * 16 + 64;
344                assert!(
345                    v <= bound,
346                    "{shape:?} chunk {chunk}: {v} visits for {data} bytes"
347                );
348            }
349        }
350    }
351
352    fn naive_find(hay: &[u8], needle: &[u8]) -> Option<usize> {
353        hay.windows(needle.len())
354            .position(|w| w == needle)
355            .map(|p| p + needle.len())
356    }
357
358    #[test]
359    fn test_boundary_every_byte_value() {
360        for b in 0u8..=255 {
361            let r = Boundary::new(&[b'a', b, b'z']);
362            assert_eq!(r.is_ok(), is_bchar(b), "byte {b:#x}");
363        }
364    }
365
366    #[test]
367    fn test_boundary_lengths_and_trailing_space() {
368        assert!(Boundary::new(b"").is_err());
369        assert!(Boundary::new(b"a").is_ok());
370        assert!(Boundary::new(&[b'a'; 69]).is_ok());
371        assert!(Boundary::new(&[b'a'; 70]).is_ok());
372        assert!(Boundary::new(&[b'a'; 71]).is_err());
373        assert!(Boundary::new(b"a ").is_err());
374        assert!(Boundary::new(b"a b").is_ok());
375        assert!(Boundary::new(b" ").is_err());
376    }
377
378    #[test]
379    fn test_failure_table_matches_definition() {
380        for raw in [&b"a"[..], b"aaaa", b"-", b"--", b"-a-", b"---", b"a-b--a"] {
381            let b = Boundary::new(raw).unwrap();
382            let d = b.delimiter();
383            for i in 0..d.len() {
384                let best = (0..=i)
385                    .rev()
386                    .find(|&l| l <= i && d[..l] == d[i + 1 - l..=i])
387                    .unwrap();
388                assert_eq!(usize::from(b.fail[i]), best, "{raw:?} at {i}");
389            }
390        }
391    }
392
393    #[test]
394    fn test_run_finds_like_naive_and_carries_state() {
395        let b = Boundary::new(b"-ab").unwrap();
396        let d = b.delimiter().to_vec();
397        let mut hay = Vec::new();
398        hay.extend_from_slice(b"x\r\n--a\r\n\r\n--\r\n--");
399        hay.extend_from_slice(&d);
400        hay.extend_from_slice(b"tail");
401        let expected = naive_find(&hay, &d);
402        assert_eq!(b.run(0, &hay).1, expected);
403        // Split at every byte: the state carries across.
404        for split in 0..hay.len() {
405            let (k, found) = b.run(0, &hay[..split]);
406            let total = match found {
407                Some(i) => Some(i),
408                None => b.run(k, &hay[split..]).1.map(|i| i + split),
409            };
410            assert_eq!(total, expected, "split {split}");
411        }
412    }
413
414    #[test]
415    fn test_parse_reports_unsupported_for_urlencoded() {
416        assert_eq!(
417            Boundary::parse(b"application/x-www-form-urlencoded"),
418            Err(FormError::UnsupportedMediaType)
419        );
420    }
421}
form_net/multipart/boundary.rs

form_net/multipart/
boundary.rs
