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        if boundary.first() == Some(&b'\'') {
92            // `boundary='abc'` is the boundary `'abc'` to RFC 2046 readers and
93            // `abc` to readers that take single quotes as quoting; the same
94            // reasoning as D-114 for part names (D-136).
95            return Err(invalid(0));
96        }
97        if boundary.last() == Some(&b'\'') {
98            return Err(invalid(boundary.len().wrapping_sub(1)));
99        }
100        let mut delimiter = [0u8; MAX_DELIMITER_LEN];
101        let len = boundary.len().wrapping_add(4);
102        if let Some(head) = delimiter.get_mut(..4) {
103            head.copy_from_slice(b"\r\n--");
104        }
105        if let Some(rest) = delimiter.get_mut(4..len) {
106            rest.copy_from_slice(boundary);
107        }
108        let fail = failure_table(&delimiter, len);
109        Ok(Boundary {
110            delimiter,
111            fail,
112            len: len as u8,
113        })
114    }
115
116    /// A fresh boundary: `form-net-` and 32 lowercase hex characters from 16
117    /// bytes of the OS random source (41 bytes, all `bchars`).
118    ///
119    /// # Errors
120    ///
121    /// `Random` when the OS random source fails (fail closed).
122    ///
123    /// # Examples
124    ///
125    /// ```
126    /// let b = form_net::Boundary::generate()?;
127    /// assert_eq!(b.as_bytes().len(), 41);
128    /// assert!(b.as_bytes().starts_with(b"form-net-"));
129    /// assert_ne!(b, form_net::Boundary::generate()?);
130    /// # Ok::<(), form_net::FormError>(())
131    /// ```
132    #[cfg(feature = "random")]
133    #[cfg_attr(docsrs, doc(cfg(feature = "random")))]
134    pub fn generate() -> Result<Boundary, FormError> {
135        let hex = crate::random::random_hex()?;
136        let mut name = [0u8; 41];
137        if let Some(head) = name.get_mut(..9) {
138            head.copy_from_slice(b"form-net-");
139        }
140        if let Some(tail) = name.get_mut(9..) {
141            tail.copy_from_slice(&hex);
142        }
143        Boundary::new(&name)
144    }
145
146    /// Reads the boundary from a whole `multipart/form-data` `Content-Type`
147    /// value.
148    ///
149    /// # Errors
150    ///
151    /// `UnsupportedMediaType` for any other media type;
152    /// `Syntax { InvalidContentType | MissingBoundary | DuplicateBoundary | InvalidBoundary }`.
153    ///
154    /// # Examples
155    ///
156    /// ```
157    /// let b = form_net::Boundary::parse(b"multipart/form-data; boundary=----x")?;
158    /// assert_eq!(b.as_bytes(), b"----x");
159    /// assert!(form_net::Boundary::parse(b"text/plain").is_err());
160    /// # Ok::<(), form_net::FormError>(())
161    /// ```
162    pub fn parse(content_type: &[u8]) -> Result<Boundary, FormError> {
163        match crate::kind::FormKind::detect(content_type)? {
164            crate::kind::FormKind::Multipart(b) => Ok(b),
165            crate::kind::FormKind::Urlencoded => Err(FormError::UnsupportedMediaType),
166        }
167    }
168
169    /// The boundary, without `--`.
170    ///
171    /// # Examples
172    ///
173    /// ```
174    /// assert_eq!(form_net::Boundary::new(b"abc")?.as_bytes(), b"abc");
175    /// # Ok::<(), form_net::FormError>(())
176    /// ```
177    #[must_use]
178    pub fn as_bytes(&self) -> &[u8] {
179        self.delimiter.get(4..usize::from(self.len)).unwrap_or(&[])
180    }
181
182    /// The full delimiter: CRLF, `--`, and the boundary.
183    ///
184    /// # Examples
185    ///
186    /// ```
187    /// assert_eq!(form_net::Boundary::new(b"abc")?.delimiter(), b"\r\n--abc");
188    /// # Ok::<(), form_net::FormError>(())
189    /// ```
190    #[must_use]
191    pub fn delimiter(&self) -> &[u8] {
192        self.delimiter.get(..usize::from(self.len)).unwrap_or(&[])
193    }
194
195    /// One step of the matcher: the new state after byte `c` from state `k`
196    /// (the number of delimiter bytes matched so far, below the length).
197    #[inline]
198    pub(crate) fn step(&self, mut k: usize, c: u8) -> usize {
199        #[cfg(test)]
200        tests::count_visits(1);
201        loop {
202            if self.delimiter.get(k) == Some(&c) {
203                return k.wrapping_add(1);
204            }
205            if k == 0 {
206                return 0;
207            }
208            k = usize::from(*self.fail.get(k.wrapping_sub(1)).unwrap_or(&0));
209        }
210    }
211
212    pub(crate) fn len(&self) -> usize {
213        usize::from(self.len)
214    }
215
216    /// One step of the bare-break matcher: the new state after byte `c`
217    /// from state `m`. It matches a lone CR or LF followed by `--boundary`,
218    /// the delimiter with its first byte made a choice of CR or LF and its
219    /// LF dropped. The boundary holds neither, so the only restart point is
220    /// the line break itself and no failure table is needed (D-113).
221    #[inline]
222    pub(crate) fn bare_step(&self, m: usize, c: u8) -> usize {
223        if m > 0 && self.delimiter.get(m.wrapping_add(1)) == Some(&c) {
224            m.wrapping_add(1)
225        } else {
226            usize::from(crate::scan::is_break(c))
227        }
228    }
229
230    /// Runs both matchers over `hay` from states `k` (the delimiter) and
231    /// `m` (a line break followed by `--boundary`). Returns the final
232    /// states and what completed first; a completed delimiter wins over
233    /// the bare-break match that ends at the same byte inside it.
234    ///
235    /// From states 0 a match can only start at a CR or LF followed by `-`:
236    /// the delimiter's LF is followed by `--`, and the boundary holds no
237    /// line break. So the search skips to the next such pair 32 positions
238    /// at a time and compares `--boundary` after it whole; the byte before
239    /// tells a delimiter (CR LF) from a bare break. A miss resumes at the
240    /// byte that differed: the bytes before it are boundary, which holds no
241    /// line break. A match that spans chunks is compared too, against the bytes it
242    /// still needs at the start of `hay` and the bytes `hay` still has at
243    /// its end: with no line break in the boundary, at most one match is
244    /// live past a lone CR, and the moment it fails nothing else is. So the
245    /// states returned are exactly the automata's, at a compare per chunk
246    /// (D-102, D-113, D-117). The same fact keeps the compares linear: a
247    /// candidate can never start inside the bytes the one before it matched.
248    pub(crate) fn run(&self, mut k: usize, mut m: usize, hay: &[u8]) -> (usize, usize, Hit) {
249        let len = self.len();
250        let bare = len.wrapping_sub(1);
251        let delimiter = self.delimiter();
252        let dashes = delimiter.get(2..).unwrap_or(&[]);
253        let mut i = 0usize;
254        if k == 1 {
255            // A CR carried in is the one state with two futures: the next
256            // byte makes it a delimiter, a bare break, or nothing.
257            let Some(&c) = hay.first() else {
258                return (k, m, Hit::None);
259            };
260            k = self.step(k, c);
261            m = self.bare_step(m, c);
262            i = 1;
263            if k == 1 {
264                // Another CR: the search below starts at it.
265                (i, k, m) = (0, 0, 0);
266            }
267        }
268        if m > 0 {
269            // One match carried in, delimiter or bare: compare what it
270            // still needs.
271            let need = delimiter.get(m.wrapping_add(1)..).unwrap_or(&[]);
272            let rest = hay.get(i..).unwrap_or(&[]);
273            let same = shared(need, rest);
274            if same == need.len() {
275                let end = i.wrapping_add(same);
276                return if k > 0 {
277                    (len, 0, Hit::Delimiter(end))
278                } else {
279                    (0, bare, Hit::BareBreak(end))
280                };
281            }
282            if same == rest.len() {
283                // All of `hay` extended the match.
284                let k = if k > 0 { k.wrapping_add(same) } else { 0 };
285                return (k, m.wrapping_add(same), Hit::None);
286            }
287            i = i.wrapping_add(same);
288        }
289        while i < hay.len() {
290            let at = crate::scan::find_break_dash(hay, i);
291            if at >= hay.len() {
292                break;
293            }
294            let start = at.wrapping_add(1);
295            let after_cr = hay.get(at) == Some(&b'\n')
296                && at > 0
297                && hay.get(at.wrapping_sub(1)) == Some(&b'\r');
298            let rest = hay.get(start..).unwrap_or(&[]);
299            let same = shared(dashes, rest);
300            if same == dashes.len() {
301                let end = start.wrapping_add(same);
302                return if after_cr {
303                    (len, 0, Hit::Delimiter(end))
304                } else {
305                    (0, bare, Hit::BareBreak(end))
306                };
307            }
308            if same == rest.len() {
309                // All of `hay` is the start of a match, which goes on in
310                // the next chunk.
311                let k = if after_cr {
312                    same.wrapping_add(2)
313                } else {
314                    usize::from(same == 0 && hay.get(at) == Some(&b'\r'))
315                };
316                return (k, same.wrapping_add(1), Hit::None);
317            }
318            i = start.wrapping_add(same);
319        }
320        (0, 0, Hit::None)
321    }
322}
323
324/// How many leading bytes `a` and `b` share.
325#[inline]
326pub(crate) fn shared(a: &[u8], b: &[u8]) -> usize {
327    let n = crate::scan::common_prefix(a, b);
328    #[cfg(test)]
329    tests::count_visits(n.wrapping_add(1));
330    n
331}
332
333/// What a run of the matchers found.
334#[derive(Clone, Copy, Debug, PartialEq, Eq)]
335pub(crate) enum Hit {
336    /// Nothing: all of `hay` was consumed.
337    None,
338    /// The delimiter, ending just before this index.
339    Delimiter(usize),
340    /// `--boundary` after a lone CR or LF, ending just before this index
341    /// (D-113).
342    BareBreak(usize),
343}
344
345/// The Knuth-Morris-Pratt failure table: `fail[i]` is the length of the
346/// longest proper prefix of `d[..=i]` that is also its suffix.
347fn failure_table(d: &[u8; MAX_DELIMITER_LEN], len: usize) -> [u8; MAX_DELIMITER_LEN] {
348    let mut fail = [0u8; MAX_DELIMITER_LEN];
349    let mut k = 0usize;
350    for i in 1..len {
351        let c = *d.get(i).unwrap_or(&0);
352        while k > 0 && d.get(k) != Some(&c) {
353            k = usize::from(*fail.get(k.wrapping_sub(1)).unwrap_or(&0));
354        }
355        if d.get(k) == Some(&c) {
356            k = k.wrapping_add(1);
357        }
358        if let Some(slot) = fail.get_mut(i) {
359            *slot = k as u8;
360        }
361    }
362    fail
363}
364
365impl fmt::Debug for Boundary {
366    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
367        // bchars are printable ASCII, so this is always valid text.
368        let text = core::str::from_utf8(self.as_bytes()).unwrap_or("");
369        f.debug_tuple("Boundary").field(&text).finish()
370    }
371}
372
373#[cfg(test)]
374pub(crate) mod tests {
375    use super::*;
376    use alloc::vec::Vec;
377    use core::cell::Cell;
378
379    std::thread_local! {
380        static VISITS: Cell<u64> = const { Cell::new(0) };
381    }
382
383    /// Counts bytes the matcher compares: one call to `step`, which may
384    /// follow the failure table several times (KMP bounds those by the
385    /// bytes seen), or the bytes of one whole compare.
386    pub(crate) fn count_visits(n: usize) {
387        VISITS.with(|v| v.set(v.get() + n as u64));
388    }
389
390    #[cfg(feature = "alloc")]
391    pub(crate) fn visits() -> u64 {
392        VISITS.with(Cell::get)
393    }
394
395    /// Runs `body` through a parser in `chunk`-byte pieces and returns the
396    /// matcher's byte visits.
397    #[cfg(feature = "alloc")]
398    fn visits_for(body: &[u8], chunk: usize) -> u64 {
399        use crate::{Event, Limits, MultipartParser, Policy};
400        let limits = Limits::DEFAULT
401            .with_max_body_bytes(64 << 20)
402            .with_max_file_bytes(64 << 20);
403        let mut p = MultipartParser::new(
404            Boundary::new(b"boundary").unwrap(),
405            &limits,
406            &Policy::DEFAULT,
407        )
408        .unwrap();
409        let before = visits();
410        let chunks: Vec<&[u8]> = body.chunks(chunk).collect();
411        for (i, c) in chunks.iter().enumerate() {
412            let mut rest: &[u8] = c;
413            loop {
414                let step = p.parse(rest, i + 1 == chunks.len()).unwrap();
415                rest = &rest[step.consumed..];
416                if matches!(step.event, Event::NeedInput | Event::End) {
417                    break;
418                }
419            }
420        }
421        visits() - before
422    }
423
424    #[cfg(feature = "alloc")]
425    #[test]
426    fn test_matcher_visits_are_linear_for_adversarial_bodies() {
427        let head = b"--boundary\r\nContent-Disposition: form-data; name=f; filename=a\r\n\r\n";
428        let shapes: [&[u8]; 4] = [b"\r", b"\r\n--boundar", b"\r\n-", b"-"];
429        for shape in shapes {
430            for chunk in [1usize, 7, 4096] {
431                let mut body = head.to_vec();
432                while body.len() < head.len() + 64 * 1024 {
433                    body.extend_from_slice(shape);
434                }
435                let data = (body.len() - head.len()) as u64;
436                body.extend_from_slice(b"\r\n--boundary--");
437                let v = visits_for(&body, chunk);
438                // Each data byte is examined a bounded number of times
439                // (KMP), plus at most a delimiter's length rescanned per
440                // chunk boundary.
441                let bound = 2 * data + (body.len() / chunk + 1) as u64 * 16 + 64;
442                assert!(
443                    v <= bound,
444                    "{shape:?} chunk {chunk}: {v} visits for {data} bytes"
445                );
446            }
447        }
448    }
449
450    #[test]
451    fn test_boundary_every_byte_value() {
452        for b in 0u8..=255 {
453            let r = Boundary::new(&[b'a', b, b'z']);
454            assert_eq!(r.is_ok(), is_bchar(b), "byte {b:#x}");
455        }
456    }
457
458    #[test]
459    fn test_boundary_lengths_and_trailing_space() {
460        assert!(Boundary::new(b"").is_err());
461        assert!(Boundary::new(b"a").is_ok());
462        assert!(Boundary::new(&[b'a'; 69]).is_ok());
463        assert!(Boundary::new(&[b'a'; 70]).is_ok());
464        assert!(Boundary::new(&[b'a'; 71]).is_err());
465        assert!(Boundary::new(b"a ").is_err());
466        assert!(Boundary::new(b"a b").is_ok());
467        assert!(Boundary::new(b" ").is_err());
468    }
469
470    #[test]
471    fn test_failure_table_matches_definition() {
472        for raw in [&b"a"[..], b"aaaa", b"-", b"--", b"-a-", b"---", b"a-b--a"] {
473            let b = Boundary::new(raw).unwrap();
474            let d = b.delimiter();
475            for i in 0..d.len() {
476                let best = (0..=i)
477                    .rev()
478                    .find(|&l| l <= i && d[..l] == d[i + 1 - l..=i])
479                    .unwrap();
480                assert_eq!(usize::from(b.fail[i]), best, "{raw:?} at {i}");
481            }
482        }
483    }
484
485    /// The first match in `hay` by a plain search: the delimiter, or a
486    /// lone CR or LF followed by `--boundary`, by where it ends.
487    fn naive_hit(b: &Boundary, hay: &[u8]) -> Hit {
488        let d = b.delimiter();
489        let dashes = &d[2..];
490        for end in 0..=hay.len() {
491            if end >= d.len() && &hay[end - d.len()..end] == d {
492                return Hit::Delimiter(end);
493            }
494            if end > dashes.len() && &hay[end - dashes.len()..end] == dashes {
495                let p = end - dashes.len() - 1;
496                if hay[p] == b'\r' || hay[p] == b'\n' {
497                    return Hit::BareBreak(end);
498                }
499            }
500        }
501        Hit::None
502    }
503
504    /// Runs the matchers over `chunks` in turn, carrying the states, and
505    /// returns the first hit with its index in the whole.
506    fn chunked_hit(b: &Boundary, chunks: &[&[u8]]) -> Hit {
507        let (mut k, mut m, mut base) = (0, 0, 0);
508        for chunk in chunks {
509            let (k2, m2, hit) = b.run(k, m, chunk);
510            match hit {
511                Hit::Delimiter(e) => return Hit::Delimiter(base + e),
512                Hit::BareBreak(e) => return Hit::BareBreak(base + e),
513                Hit::None => (k, m, base) = (k2, m2, base + chunk.len()),
514            }
515        }
516        Hit::None
517    }
518
519    #[test]
520    fn test_run_finds_like_naive_and_carries_state() {
521        let b = Boundary::new(b"-ab").unwrap();
522        let d = b.delimiter().to_vec();
523        let mut hay = Vec::new();
524        hay.extend_from_slice(b"x\r\n--a\r\n\r\n--\r\n--");
525        hay.extend_from_slice(&d);
526        hay.extend_from_slice(b"tail");
527        let expected = naive_hit(&b, &hay);
528        assert!(matches!(expected, Hit::Delimiter(_)));
529        assert_eq!(chunked_hit(&b, &[&hay]), expected);
530        for split in 0..hay.len() {
531            let (x, y) = hay.split_at(split);
532            assert_eq!(chunked_hit(&b, &[x, y]), expected, "split {split}");
533        }
534    }
535
536    /// D-113: the delimiter and bare breaks against the plain search, on
537    /// hays dense in CR, LF, and dashes, whole, at every split, and byte
538    /// by byte, for boundaries with and without dashes of their own.
539    #[test]
540    fn test_bare_breaks_and_delimiters_match_naive_at_every_split() {
541        let mut seed = 11u64;
542        for boundary in [&b"-ab"[..], b"--", b"x", b"ab-"] {
543            let b = Boundary::new(boundary).unwrap();
544            for len in 0..40 {
545                for _ in 0..60 {
546                    let hay: Vec<u8> = (0..len)
547                        .map(|_| {
548                            seed ^= seed << 13;
549                            seed ^= seed >> 7;
550                            seed ^= seed << 17;
551                            b"\r\n--abx"[(seed % 7) as usize]
552                        })
553                        .collect();
554                    let expected = naive_hit(&b, &hay);
555                    assert_eq!(chunked_hit(&b, &[&hay]), expected, "{hay:?}");
556                    for split in 0..=hay.len() {
557                        let (x, y) = hay.split_at(split);
558                        assert_eq!(chunked_hit(&b, &[x, y]), expected, "{hay:?} at {split}");
559                    }
560                    let bytes: Vec<&[u8]> = hay.chunks(1).collect();
561                    assert_eq!(chunked_hit(&b, &bytes), expected, "{hay:?} bytewise");
562                }
563            }
564        }
565    }
566
567    /// D-117: `run` compares where the automata step, and the states it
568    /// leaves are exactly theirs, so a match carries across any split.
569    #[test]
570    fn test_run_leaves_the_automata_states_at_every_split() {
571        let mut seed = 5u64;
572        for boundary in [&b"-ab"[..], b"--", b"x", b"ab-", b"abcdefghijklmnop"] {
573            let b = Boundary::new(boundary).unwrap();
574            let bare = b.len() - 1;
575            let hay_bytes: &[u8] = &[b'\r', b'\n', b'-', b'-', boundary[0], b'x'];
576            for len in 0..48 {
577                for _ in 0..40 {
578                    let mut hay: Vec<u8> = (0..len)
579                        .map(|_| {
580                            seed ^= seed << 13;
581                            seed ^= seed >> 7;
582                            seed ^= seed << 17;
583                            hay_bytes[(seed % 6) as usize]
584                        })
585                        .collect();
586                    // A partial match at the end, of every length.
587                    let d = b.delimiter();
588                    hay.extend_from_slice(&d[..len % d.len()]);
589                    if !matches!(naive_hit(&b, &hay), Hit::None) {
590                        continue;
591                    }
592                    let (mut k, mut m) = (0, 0);
593                    for &c in &hay {
594                        k = b.step(k, c);
595                        m = b.bare_step(m, c);
596                        assert!(k < b.len() && m < bare);
597                    }
598                    assert_eq!(&b.run(0, 0, &hay), &(k, m, Hit::None), "{hay:?}");
599                    for split in 0..=hay.len() {
600                        let (x, y) = hay.split_at(split);
601                        let (k1, m1, _) = b.run(0, 0, x);
602                        assert_eq!(&b.run(k1, m1, y), &(k, m, Hit::None), "{hay:?} at {split}");
603                    }
604                }
605            }
606        }
607    }
608
609    #[test]
610    fn test_parse_reports_unsupported_for_urlencoded() {
611        assert_eq!(
612            Boundary::parse(b"application/x-www-form-urlencoded"),
613            Err(FormError::UnsupportedMediaType)
614        );
615    }
616}
form_net/multipart/boundary.rs

form_net/multipart/
boundary.rs
