cbor.rs 98.0%

396 of 404 lines run, 86 of 87 functions · run #309 on main · run missed

//! Deterministic CBOR (RFC 8949 §4.2.1) restricted to the profile of spec §5.1:
//! unsigned integers, byte strings, text strings, arrays, maps with unsigned
//! integer keys in increasing order, booleans, and null. Everything else is
//! rejected on decode and cannot be expressed on encode.

use std::collections::BTreeMap;

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Value {
    Uint(u64),
    Bytes(Vec<u8>),
    Text(String),
    Array(Vec<Value>),
    Map(BTreeMap<u64, Value>),
    Bool(bool),
    Null,
    /// An item already in its canonical encoding, written out as it is.
    /// Only built for encoding (never decoded): a large change's inline
    /// lines then cost their bytes, not a value per line.
    Encoded(Vec<u8>),
}

#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum CborError {
    #[error("unexpected end of input")]
    UnexpectedEnd,
    #[error("non-canonical encoding: {0}")]
    NonCanonical(&'static str),
    #[error("unsupported CBOR item: {0}")]
    Unsupported(&'static str),
    #[error("trailing bytes after value")]
    TrailingBytes,
    #[error("invalid UTF-8 in text string")]
    InvalidUtf8,
    #[error("map keys must be strictly increasing unsigned integers")]
    BadMapKey,
    #[error("length exceeds input")]
    LengthOverflow,
}

impl Value {
    pub fn map(pairs: impl IntoIterator<Item = (u64, Value)>) -> Value {
        Value::Map(pairs.into_iter().collect())
    }
    pub fn as_uint(&self) -> Option<u64> {
        if let Value::Uint(n) = self {
            Some(*n)
        } else {
            None
        }
    }
    pub fn as_bytes(&self) -> Option<&[u8]> {
        if let Value::Bytes(b) = self {
            Some(b)
        } else {
            None
        }
    }
    pub fn as_text(&self) -> Option<&str> {
        if let Value::Text(t) = self {
            Some(t)
        } else {
            None
        }
    }
    pub fn as_array(&self) -> Option<&[Value]> {
        if let Value::Array(a) = self {
            Some(a)
        } else {
            None
        }
    }
    pub fn as_map(&self) -> Option<&BTreeMap<u64, Value>> {
        if let Value::Map(m) = self {
            Some(m)
        } else {
            None
        }
    }
    pub fn as_bool(&self) -> Option<bool> {
        if let Value::Bool(b) = self {
            Some(*b)
        } else {
            None
        }
    }
    pub fn is_null(&self) -> bool {
        matches!(self, Value::Null)
    }
}

pub fn encode(v: &Value) -> Vec<u8> {
    let mut out = Vec::new();
    encode_into(v, &mut out);
    out
}

pub fn encode_into(v: &Value, out: &mut Vec<u8>) {
    match v {
        Value::Uint(n) => head(out, 0, *n),
        Value::Bytes(b) => {
            head(out, 2, b.len() as u64);
            out.extend_from_slice(b);
        }
        Value::Text(t) => {
            head(out, 3, t.len() as u64);
            out.extend_from_slice(t.as_bytes());
        }
        Value::Array(a) => {
            head(out, 4, a.len() as u64);
            for x in a {
                encode_into(x, out);
            }
        }
        Value::Map(m) => {
            head(out, 5, m.len() as u64);
            for (k, x) in m {
                head(out, 0, *k);
                encode_into(x, out);
            }
        }
        Value::Bool(false) => out.push(0xf4),
        Value::Bool(true) => out.push(0xf5),
        Value::Null => out.push(0xf6),
        Value::Encoded(b) => out.extend_from_slice(b),
    }
}

/// The canonical encoding of an array of byte strings, written without
/// building a [`Value`] (large inserts stored as text blobs, spec §6.1).
pub fn encode_byte_strings(items: &crate::lines::Lines) -> Vec<u8> {
    let mut out = Vec::with_capacity(byte_strings_len(items));
    head(&mut out, 4, items.len() as u64);
    for b in items.iter() {
        head(&mut out, 2, b.len() as u64);
        out.extend_from_slice(b);
    }
    out
}

/// The length of [`encode_byte_strings`]' output, without encoding.
pub fn byte_strings_len(items: &crate::lines::Lines) -> usize {
    head_len(items.len() as u64)
        + items
            .iter()
            .map(|b| head_len(b.len() as u64) + b.len())
            .sum::<usize>()
}

fn head_len(n: u64) -> usize {
    match n {
        0..=23 => 1,
        24..=0xff => 2,
        0x100..=0xffff => 3,
        0x1_0000..=0xffff_ffff => 5,
        _ => 9,
    }
}

fn head(out: &mut Vec<u8>, major: u8, n: u64) {
    let m = major << 5;
    if n < 24 {
        out.push(m | n as u8);
    } else if n <= 0xff {
        out.push(m | 24);
        out.push(n as u8);
    } else if n <= 0xffff {
        out.push(m | 25);
        out.extend_from_slice(&(n as u16).to_be_bytes());
    } else if n <= 0xffff_ffff {
        out.push(m | 26);
        out.extend_from_slice(&(n as u32).to_be_bytes());
    } else {
        out.push(m | 27);
        out.extend_from_slice(&n.to_be_bytes());
    }
}

pub fn decode(bytes: &[u8]) -> Result<Value, CborError> {
    let mut d = Decoder {
        b: bytes,
        pos: 0,
        depth: 0,
    };
    let v = d.value()?;
    if d.pos != bytes.len() {
        return Err(CborError::TrailingBytes);
    }
    Ok(v)
}

const MAX_DEPTH: u32 = 256;

/// A cursor over canonical CBOR, for decoders that read part of an item
/// and skip or defer the rest (history-only loads of large changes).
pub struct Cursor<'a> {
    d: Decoder<'a>,
}

impl<'a> Cursor<'a> {
    pub fn new(bytes: &'a [u8]) -> Cursor<'a> {
        Cursor {
            d: Decoder {
                b: bytes,
                pos: 0,
                depth: 0,
            },
        }
    }

    /// The offset of the next item.
    pub fn pos(&self) -> usize {
        self.d.pos
    }

    /// Whether every byte was read.
    pub fn at_end(&self) -> bool {
        self.d.pos == self.d.b.len()
    }

    /// The next head: (major type, argument).
    pub fn head(&mut self) -> Result<(u8, u64), CborError> {
        self.d.head()
    }

    /// The next item, decoded.
    pub fn value(&mut self) -> Result<Value, CborError> {
        self.d.value()
    }

    /// Step over the next item, checking only its structure.
    pub fn skip(&mut self) -> Result<(), CborError> {
        let ib = *self.d.b.get(self.d.pos).ok_or(CborError::UnexpectedEnd)?;
        if ib >> 5 == 7 {
            self.d.pos += 1;
            return Ok(());
        }
        let (major, n) = self.d.head()?;
        match major {
            0 => {}
            2 | 3 => {
                self.d.take(n)?;
            }
            4 => {
                for _ in 0..n {
                    self.skip()?;
                }
            }
            5 => {
                for _ in 0..n.saturating_mul(2) {
                    self.skip()?;
                }
            }
            _ => return Err(CborError::Unsupported("negative integer or tag")),
        }
        Ok(())
    }
}

struct Decoder<'a> {
    b: &'a [u8],
    pos: usize,
    depth: u32,
}

impl<'a> Decoder<'a> {
    fn byte(&mut self) -> Result<u8, CborError> {
        let x = *self.b.get(self.pos).ok_or(CborError::UnexpectedEnd)?;
        self.pos += 1;
        Ok(x)
    }

    fn take(&mut self, n: u64) -> Result<&'a [u8], CborError> {
        let n = usize::try_from(n).map_err(|_| CborError::LengthOverflow)?;
        let end = self.pos.checked_add(n).ok_or(CborError::LengthOverflow)?;
        if end > self.b.len() {
            return Err(CborError::UnexpectedEnd);
        }
        let s = &self.b[self.pos..end];
        self.pos = end;
        Ok(s)
    }

    /// Reads a head for majors 0..=5 and returns (major, argument), enforcing
    /// shortest-form arguments.
    fn head(&mut self) -> Result<(u8, u64), CborError> {
        let ib = self.byte()?;
        let major = ib >> 5;
        let ai = ib & 0x1f;
        if major == 7 {
            return Err(CborError::Unsupported(
                "simple value or float where a length or integer was expected",
            ));
        }
        let n = match ai {
            0..=23 => ai as u64,
            24 => {
                let n = self.byte()? as u64;
                if n < 24 {
                    return Err(CborError::NonCanonical("argument fits in the initial byte"));
                }
                n
            }
            25 => {
                let n = u16::from_be_bytes(self.take(2)?.try_into().unwrap()) as u64;
                if n <= 0xff {
                    return Err(CborError::NonCanonical("argument fits in one byte"));
                }
                n
            }
            26 => {
                let n = u32::from_be_bytes(self.take(4)?.try_into().unwrap()) as u64;
                if n <= 0xffff {
                    return Err(CborError::NonCanonical("argument fits in two bytes"));
                }
                n
            }
            27 => {
                let n = u64::from_be_bytes(self.take(8)?.try_into().unwrap());
                if n <= 0xffff_ffff {
                    return Err(CborError::NonCanonical("argument fits in four bytes"));
                }
                n
            }
            28..=30 => return Err(CborError::Unsupported("reserved additional information")),
            _ => return Err(CborError::Unsupported("indefinite-length item")),
        };
        Ok((major, n))
    }

    fn value(&mut self) -> Result<Value, CborError> {
        self.depth += 1;
        if self.depth > MAX_DEPTH {
            return Err(CborError::Unsupported("nesting deeper than 256"));
        }
        let ib = *self.b.get(self.pos).ok_or(CborError::UnexpectedEnd)?;
        let v = if ib >> 5 == 7 {
            self.pos += 1;
            match ib {
                0xf4 => Value::Bool(false),
                0xf5 => Value::Bool(true),
                0xf6 => Value::Null,
                _ => {
                    return Err(CborError::Unsupported(
                        "simple value, float, undefined, or break",
                    ))
                }
            }
        } else {
            let (major, n) = self.head()?;
            match major {
                0 => Value::Uint(n),
                1 => return Err(CborError::Unsupported("negative integer")),
                2 => Value::Bytes(self.take(n)?.to_vec()),
                3 => Value::Text(
                    std::str::from_utf8(self.take(n)?)
                        .map_err(|_| CborError::InvalidUtf8)?
                        .to_owned(),
                ),
                4 => {
                    let mut a = Vec::new();
                    for _ in 0..n {
                        a.push(self.value()?);
                    }
                    Value::Array(a)
                }
                5 => {
                    let mut m = BTreeMap::new();
                    let mut last: Option<u64> = None;
                    for _ in 0..n {
                        let (km, k) = self.head()?;
                        if km != 0 {
                            return Err(CborError::BadMapKey);
                        }
                        if let Some(l) = last {
                            if k <= l {
                                return Err(CborError::BadMapKey);
                            }
                        }
                        last = Some(k);
                        let v = self.value()?;
                        m.insert(k, v);
                    }
                    Value::Map(m)
                }
                _ => return Err(CborError::Unsupported("tag")),
            }
        };
        self.depth -= 1;
        Ok(v)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn rt(v: Value) -> Vec<u8> {
        let b = encode(&v);
        assert_eq!(decode(&b).unwrap(), v);
        b
    }

    #[test]
    fn integers_use_shortest_form() {
        assert_eq!(rt(Value::Uint(0)), [0x00]);
        assert_eq!(rt(Value::Uint(23)), [0x17]);
        assert_eq!(rt(Value::Uint(24)), [0x18, 24]);
        assert_eq!(rt(Value::Uint(255)), [0x18, 255]);
        assert_eq!(rt(Value::Uint(256)), [0x19, 1, 0]);
        assert_eq!(rt(Value::Uint(65536)), [0x1a, 0, 1, 0, 0]);
        assert_eq!(rt(Value::Uint(1 << 32)), [0x1b, 0, 0, 0, 1, 0, 0, 0, 0]);
        assert_eq!(rt(Value::Uint(u64::MAX)).len(), 9);
    }

    #[test]
    fn rejects_non_shortest_integers() {
        assert_eq!(
            decode(&[0x18, 5]),
            Err(CborError::NonCanonical("argument fits in the initial byte"))
        );
        assert_eq!(
            decode(&[0x19, 0, 5]),
            Err(CborError::NonCanonical("argument fits in one byte"))
        );
        assert_eq!(
            decode(&[0x1a, 0, 0, 0, 5]),
            Err(CborError::NonCanonical("argument fits in two bytes"))
        );
        assert_eq!(
            decode(&[0x1b, 0, 0, 0, 0, 0, 0, 0, 5]),
            Err(CborError::NonCanonical("argument fits in four bytes"))
        );
    }

    #[test]
    fn rejects_unsupported_items() {
        assert!(matches!(decode(&[0x20]), Err(CborError::Unsupported(_)))); // -1
        assert!(matches!(
            decode(&[0xc0, 0x00]),
            Err(CborError::Unsupported(_))
        )); // tag
        assert!(matches!(
            decode(&[0xf9, 0, 0]),
            Err(CborError::Unsupported(_))
        )); // float16
        assert!(matches!(
            decode(&[0x9f, 0xff]),
            Err(CborError::Unsupported(_))
        )); // indefinite array
        assert!(matches!(decode(&[0xf7]), Err(CborError::Unsupported(_)))); // undefined
    }

    #[test]
    fn maps_are_sorted_and_unique() {
        let v = Value::map([
            (2, Value::Uint(1)),
            (0, Value::Null),
            (1, Value::Bool(true)),
        ]);
        let b = rt(v);
        assert_eq!(b, [0xa3, 0x00, 0xf6, 0x01, 0xf5, 0x02, 0x01]);
        assert_eq!(
            decode(&[0xa2, 0x01, 0x00, 0x00, 0x00]),
            Err(CborError::BadMapKey)
        );
        assert_eq!(
            decode(&[0xa2, 0x01, 0x00, 0x01, 0x00]),
            Err(CborError::BadMapKey)
        );
        assert_eq!(decode(&[0xa1, 0x61, 0x61, 0x00]), Err(CborError::BadMapKey));
        // text key
    }

    #[test]
    fn strings_arrays_and_trailing() {
        rt(Value::Bytes(vec![1, 2, 3]));
        rt(Value::Text("héllo".into()));
        rt(Value::Array(vec![
            Value::Uint(1),
            Value::Text("x".into()),
            Value::Array(vec![]),
        ]));
        assert_eq!(decode(&[0x00, 0x00]), Err(CborError::TrailingBytes));
        assert_eq!(decode(&[0x62, 0xff, 0xfe]), Err(CborError::InvalidUtf8));
        assert_eq!(decode(&[0x43, 1, 2]), Err(CborError::UnexpectedEnd));
    }

    #[test]
    fn huge_length_does_not_allocate() {
        assert_eq!(
            decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
            Err(CborError::LengthOverflow)
        );
        assert!(decode(&[0x9b, 0x00, 0x00, 0x00, 0x01, 0, 0, 0, 0]).is_err());
    }

    fn xorshift(state: &mut u64) -> u64 {
        *state ^= *state << 13;
        *state ^= *state >> 7;
        *state ^= *state << 17;
        *state
    }

    fn random_value(seed: &mut u64, depth: u32) -> Value {
        match xorshift(seed) % if depth > 4 { 5 } else { 7 } {
            0 => Value::Uint(match xorshift(seed) % 4 {
                0 => xorshift(seed) % 24,
                1 => xorshift(seed) % 256,
                2 => xorshift(seed) % 65536,
                _ => xorshift(seed),
            }),
            1 => Value::Bool(xorshift(seed).is_multiple_of(2)),
            2 => Value::Null,
            3 => {
                let n = (xorshift(seed) % 40) as usize;
                Value::Bytes((0..n).map(|_| (xorshift(seed) & 0xff) as u8).collect())
            }
            4 => {
                let n = (xorshift(seed) % 12) as usize;
                Value::Text(
                    (0..n)
                        .map(|_| char::from_u32((xorshift(seed) % 0x24f) as u32 + 1).unwrap_or('x'))
                        .collect(),
                )
            }
            5 => {
                let n = (xorshift(seed) % 5) as usize;
                Value::Array((0..n).map(|_| random_value(seed, depth + 1)).collect())
            }
            _ => {
                let n = (xorshift(seed) % 5) as usize;
                let mut m = std::collections::BTreeMap::new();
                for _ in 0..n {
                    m.insert(xorshift(seed) % 300, random_value(seed, depth + 1));
                }
                Value::Map(m)
            }
        }
    }

    /// Random values round-trip and re-encode identically (canonical form).
    #[test]
    fn random_values_round_trip() {
        let mut seed = 0x2545f4914f6cdd1du64;
        for _ in 0..2000 {
            let v = random_value(&mut seed, 0);
            let b = encode(&v);
            let back = decode(&b).unwrap();
            assert_eq!(back, v);
            assert_eq!(encode(&back), b);
        }
    }

    /// Random bytes and mutated encodings never panic; whatever decodes is
    /// canonical, so re-encoding it reproduces the input exactly.
    #[test]
    fn random_and_mutated_input_never_panics() {
        let mut seed = 0xdeadbeefcafef00du64;
        for _ in 0..3000 {
            let n = (xorshift(&mut seed) % 64) as usize;
            let bytes: Vec<u8> = (0..n).map(|_| (xorshift(&mut seed) & 0xff) as u8).collect();
            if let Ok(v) = decode(&bytes) {
                assert_eq!(
                    encode(&v),
                    bytes,
                    "accepted input must be canonical: {bytes:02x?}"
                );
            }
        }
        for _ in 0..3000 {
            let v = random_value(&mut seed, 0);
            let mut b = encode(&v);
            if b.is_empty() {
                continue;
            }
            match xorshift(&mut seed) % 3 {
                0 => {
                    let at = (xorshift(&mut seed) as usize) % b.len();
                    b[at] ^= 1 << (xorshift(&mut seed) % 8);
                }
                1 => {
                    let keep = (xorshift(&mut seed) as usize) % b.len();
                    b.truncate(keep);
                }
                _ => {
                    let at = (xorshift(&mut seed) as usize) % b.len();
                    b.insert(at, (xorshift(&mut seed) & 0xff) as u8);
                }
            }
            if let Ok(v2) = decode(&b) {
                assert_eq!(encode(&v2), b, "accepted mutation must be canonical");
            }
        }
        // Deep nesting is refused rather than overflowing the stack.
        let mut deep = vec![0x81u8; 100_000];
        deep.push(0x00);
        assert!(matches!(decode(&deep), Err(CborError::Unsupported(_))));
        // Lengths beyond the input are refused without allocating them.
        assert!(matches!(
            decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
            Err(CborError::LengthOverflow) | Err(CborError::UnexpectedEnd)
        ));
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1		//! Deterministic CBOR (RFC 8949 §4.2.1) restricted to the profile of spec §5.1:
2		//! unsigned integers, byte strings, text strings, arrays, maps with unsigned
3		//! integer keys in increasing order, booleans, and null. Everything else is
4		//! rejected on decode and cannot be expressed on encode.
5
6		use std::collections::BTreeMap;
7
8		#[derive(Clone, Debug, PartialEq, Eq)]
9		pub enum Value {
10		Uint(u64),
11		Bytes(Vec<u8>),
12		Text(String),
13		Array(Vec<Value>),
14		Map(BTreeMap<u64, Value>),
15		Bool(bool),
16		Null,
17		/// An item already in its canonical encoding, written out as it is.
18		/// Only built for encoding (never decoded): a large change's inline
19		/// lines then cost their bytes, not a value per line.
20		Encoded(Vec<u8>),
21		}
22
23		#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
24		pub enum CborError {
25		#[error("unexpected end of input")]
26		UnexpectedEnd,
27		#[error("non-canonical encoding: {0}")]
28		NonCanonical(&'static str),
29		#[error("unsupported CBOR item: {0}")]
30		Unsupported(&'static str),
31		#[error("trailing bytes after value")]
32		TrailingBytes,
33		#[error("invalid UTF-8 in text string")]
34		InvalidUtf8,
35		#[error("map keys must be strictly increasing unsigned integers")]
36		BadMapKey,
37		#[error("length exceeds input")]
38		LengthOverflow,
39		}
40
41		impl Value {
42	53256×	pub fn map(pairs: impl IntoIterator<Item = (u64, Value)>) -> Value {
43	53256×	Value::Map(pairs.into_iter().collect())
44	53256×	}
45	375711×	pub fn as_uint(&self) -> Option<u64> {
46	375711×	if let Value::Uint(n) = self {
47	375711×	Some(*n)
48		} else {
49	0×	None
50		}
51	375711×	}
52	408742×	pub fn as_bytes(&self) -> Option<&[u8]> {
53	408742×	if let Value::Bytes(b) = self {
54	408741×	Some(b)
55		} else {
56	1×	None
57		}
58	408742×	}
59	123958×	pub fn as_text(&self) -> Option<&str> {
60	123958×	if let Value::Text(t) = self {
61	123958×	Some(t)
62		} else {
63	0×	None
64		}
65	123958×	}
66	277208×	pub fn as_array(&self) -> Option<&[Value]> {
67	277208×	if let Value::Array(a) = self {
68	277208×	Some(a)
69		} else {
70	0×	None
71		}
72	277208×	}
73	173972×	pub fn as_map(&self) -> Option<&BTreeMap<u64, Value>> {
74	173972×	if let Value::Map(m) = self {
75	173972×	Some(m)
76		} else {
77	0×	None
78		}
79	173972×	}
80	487×	pub fn as_bool(&self) -> Option<bool> {
81	487×	if let Value::Bool(b) = self {
82	487×	Some(*b)
83		} else {
84	0×	None
85		}
86	487×	}
87	32396×	pub fn is_null(&self) -> bool {
88	32396×	matches!(self, Value::Null)
89	32396×	}
90		}
91
92	26627×	pub fn encode(v: &Value) -> Vec<u8> {
93	26627×	let mut out = Vec::new();
94	26627×	encode_into(v, &mut out);
95	26627×	out
96	26627×	}
97
98	625336×	pub fn encode_into(v: &Value, out: &mut Vec<u8>) {
99	625336×	match v {
100	167396×	Value::Uint(n) => head(out, 0, *n),
101	172130×	Value::Bytes(b) => {
102	172130×	head(out, 2, b.len() as u64);
103	172130×	out.extend_from_slice(b);
104	172130×	}
105	37181×	Value::Text(t) => {
106	37181×	head(out, 3, t.len() as u64);
107	37181×	out.extend_from_slice(t.as_bytes());
108	37181×	}
109	165457×	Value::Array(a) => {
110	165457×	head(out, 4, a.len() as u64);
111	330661×	for x in a {
112	330661×	encode_into(x, out);
113	330661×	}
114		}
115	63446×	Value::Map(m) => {
116	63446×	head(out, 5, m.len() as u64);
117	268048×	for (k, x) in m {
118	268048×	head(out, 0, *k);
119	268048×	encode_into(x, out);
120	268048×	}
121		}
122	1309×	Value::Bool(false) => out.push(0xf4),
123	1425×	Value::Bool(true) => out.push(0xf5),
124	9477×	Value::Null => out.push(0xf6),
125	7515×	Value::Encoded(b) => out.extend_from_slice(b),
126		}
127	625336×	}
128
129		/// The canonical encoding of an array of byte strings, written without
130		/// building a [`Value`] (large inserts stored as text blobs, spec §6.1).
131	7521×	pub fn encode_byte_strings(items: &crate::lines::Lines) -> Vec<u8> {
132	7521×	let mut out = Vec::with_capacity(byte_strings_len(items));
133	7521×	head(&mut out, 4, items.len() as u64);
134	17693×	for b in items.iter() {
135	17693×	head(&mut out, 2, b.len() as u64);
136	17693×	out.extend_from_slice(b);
137	17693×	}
138	7521×	out
139	7521×	}
140
141		/// The length of [`encode_byte_strings`]' output, without encoding.
142	19021×	pub fn byte_strings_len(items: &crate::lines::Lines) -> usize {
143	19021×	head_len(items.len() as u64)
144	19021×	+ items
145	19021×	.iter()
146	229709×	.map(\|b\| head_len(b.len() as u64) + b.len())
147	19021×	.sum::<usize>()
148	19021×	}
149
150	248730×	fn head_len(n: u64) -> usize {
151	248730×	match n {
152	248730×	0..=23 => 1,
153	16171×	24..=0xff => 2,
154	229×	0x100..=0xffff => 3,
155	128×	0x1_0000..=0xffff_ffff => 5,
156	0×	_ => 9,
157		}
158	248730×	}
159
160	898872×	fn head(out: &mut Vec<u8>, major: u8, n: u64) {
161	898872×	let m = major << 5;
162	898872×	if n < 24 {
163	739531×	out.push(m \| n as u8);
164	739531×	} else if n <= 0xff {
165	135424×	out.push(m \| 24);
166	135424×	out.push(n as u8);
167	135424×	} else if n <= 0xffff {
168	9306×	out.push(m \| 25);
169	9306×	out.extend_from_slice(&(n as u16).to_be_bytes());
170	14611×	} else if n <= 0xffff_ffff {
171	194×	out.push(m \| 26);
172	194×	out.extend_from_slice(&(n as u32).to_be_bytes());
173	14417×	} else {
174	14417×	out.push(m \| 27);
175	14417×	out.extend_from_slice(&n.to_be_bytes());
176	14417×	}
177	898872×	}
178
179	74025×	pub fn decode(bytes: &[u8]) -> Result<Value, CborError> {
180	74025×	let mut d = Decoder {
181	74025×	b: bytes,
182	74025×	pos: 0,
183	74025×	depth: 0,
184	74025×	};
185	74025×	let v = d.value()?;
186	69452×	if d.pos != bytes.len() {
187	955×	return Err(CborError::TrailingBytes);
188	68497×	}
189	68497×	Ok(v)
190	74025×	}
191
192		const MAX_DEPTH: u32 = 256;
193
194		/// A cursor over canonical CBOR, for decoders that read part of an item
195		/// and skip or defer the rest (history-only loads of large changes).
196		pub struct Cursor<'a> {
197		d: Decoder<'a>,
198		}
199
200		impl<'a> Cursor<'a> {
201	11280×	pub fn new(bytes: &'a [u8]) -> Cursor<'a> {
202	11280×	Cursor {
203	11280×	d: Decoder {
204	11280×	b: bytes,
205	11280×	pos: 0,
206	11280×	depth: 0,
207	11280×	},
208	11280×	}
209	11280×	}
210
211		/// The offset of the next item.
212	92472×	pub fn pos(&self) -> usize {
213	92472×	self.d.pos
214	92472×	}
215
216		/// Whether every byte was read.
217	11279×	pub fn at_end(&self) -> bool {
218	11279×	self.d.pos == self.d.b.len()
219	11279×	}
220
221		/// The next head: (major type, argument).
222	469134×	pub fn head(&mut self) -> Result<(u8, u64), CborError> {
223	469134×	self.d.head()
224	469134×	}
225
226		/// The next item, decoded.
227	293567×	pub fn value(&mut self) -> Result<Value, CborError> {
228	293567×	self.d.value()
229	293567×	}
230
231		/// Step over the next item, checking only its structure.
232	273667×	pub fn skip(&mut self) -> Result<(), CborError> {
233	273667×	let ib = *self.d.b.get(self.d.pos).ok_or(CborError::UnexpectedEnd)?;
234	273667×	if ib >> 5 == 7 {
235	236×	self.d.pos += 1;
236	236×	return Ok(());
237	273431×	}
238	273431×	let (major, n) = self.d.head()?;
239	273431×	match major {
240	135441×	0 => {}
241		2 \| 3 => {
242	105000×	self.d.take(n)?;
243		}
244		4 => {
245	16720×	for _ in 0..n {
246	31486×	self.skip()?;
247		}
248		}
249		5 => {
250	16270×	for _ in 0..n.saturating_mul(2) {
251	174180×	self.skip()?;
252		}
253		}
254	0×	_ => return Err(CborError::Unsupported("negative integer or tag")),
255		}
256	273431×	Ok(())
257	273667×	}
258		}
259
260		struct Decoder<'a> {
261		b: &'a [u8],
262		pos: usize,
263		depth: u32,
264		}
265
266		impl<'a> Decoder<'a> {
267	3057761×	fn byte(&mut self) -> Result<u8, CborError> {
268	3057761×	let x = *self.b.get(self.pos).ok_or(CborError::UnexpectedEnd)?;
269	3057636×	self.pos += 1;
270	3057636×	Ok(x)
271	3057761×	}
272
273	693759×	fn take(&mut self, n: u64) -> Result<&'a [u8], CborError> {
274	693759×	let n = usize::try_from(n).map_err(\|_\| CborError::LengthOverflow)?;
275	693759×	let end = self.pos.checked_add(n).ok_or(CborError::LengthOverflow)?;
276	693757×	if end > self.b.len() {
277	903×	return Err(CborError::UnexpectedEnd);
278	692854×	}
279	692854×	let s = &self.b[self.pos..end];
280	692854×	self.pos = end;
281	692854×	Ok(s)
282	693759×	}
283
284		/// Reads a head for majors 0..=5 and returns (major, argument), enforcing
285		/// shortest-form arguments.
286	2886422×	fn head(&mut self) -> Result<(u8, u64), CborError> {
287	2886422×	let ib = self.byte()?;
288	2886340×	let major = ib >> 5;
289	2886340×	let ai = ib & 0x1f;
290	2886340×	if major == 7 {
291	71×	return Err(CborError::Unsupported(
292	71×	"simple value or float where a length or integer was expected",
293	71×	));
294	2886269×	}
295	2886269×	let n = match ai {
296	2886269×	0..=23 => ai as u64,
297		24 => {
298	171339×	let n = self.byte()? as u64;
299	171296×	if n < 24 {
300	20×	return Err(CborError::NonCanonical("argument fits in the initial byte"));
301	171276×	}
302	171276×	n
303		}
304		25 => {
305	7827×	let n = u16::from_be_bytes(self.take(2)?.try_into().unwrap()) as u64;
306	7781×	if n <= 0xff {
307	1×	return Err(CborError::NonCanonical("argument fits in one byte"));
308	7780×	}
309	7780×	n
310		}
311		26 => {
312	323×	let n = u32::from_be_bytes(self.take(4)?.try_into().unwrap()) as u64;
313	300×	if n <= 0xffff {
314	1×	return Err(CborError::NonCanonical("argument fits in two bytes"));
315	299×	}
316	299×	n
317		}
318		27 => {
319	38585×	let n = u64::from_be_bytes(self.take(8)?.try_into().unwrap());
320	38523×	if n <= 0xffff_ffff {
321	1×	return Err(CborError::NonCanonical("argument fits in four bytes"));
322	38522×	}
323	38522×	n
324		}
325	473×	28..=30 => return Err(CborError::Unsupported("reserved additional information")),
326	114×	_ => return Err(CborError::Unsupported("indefinite-length item")),
327		};
328	2885599×	Ok((major, n))
329	2886422×	}
330
331	1483858×	fn value(&mut self) -> Result<Value, CborError> {
332	1483858×	self.depth += 1;
333	1483858×	if self.depth > MAX_DEPTH {
334	1×	return Err(CborError::Unsupported("nesting deeper than 256"));
335	1483857×	}
336	1483857×	let ib = *self.b.get(self.pos).ok_or(CborError::UnexpectedEnd)?;
337	1483186×	let v = if ib >> 5 == 7 {
338	24859×	self.pos += 1;
339	24859×	match ib {
340	591×	0xf4 => Value::Bool(false),
341	985×	0xf5 => Value::Bool(true),
342	22656×	0xf6 => Value::Null,
343		_ => {
344	627×	return Err(CborError::Unsupported(
345	627×	"simple value, float, undefined, or break",
346	627×	))
347		}
348		}
349		} else {
350	1458327×	let (major, n) = self.head()?;
351	1457733×	match major {
352	467473×	0 => Value::Uint(n),
353	446×	1 => return Err(CborError::Unsupported("negative integer")),
354	415860×	2 => Value::Bytes(self.take(n)?.to_vec()),
355		3 => Value::Text(
356	126164×	std::str::from_utf8(self.take(n)?)
357	125774×	.map_err(\|_\| CborError::InvalidUtf8)?
358	125358×	.to_owned(),
359		),
360		4 => {
361	285663×	let mut a = Vec::new();
362	285663×	for _ in 0..n {
363	431270×	a.push(self.value()?);
364		}
365	284676×	Value::Array(a)
366		}
367		5 => {
368	161617×	let mut m = BTreeMap::new();
369	161617×	let mut last: Option<u64> = None;
370	161617×	for _ in 0..n {
371	685530×	let (km, k) = self.head()?;
372	685301×	if km != 0 {
373	291×	return Err(CborError::BadMapKey);
374	685010×	}
375	685010×	if let Some(l) = last {
376	540551×	if k <= l {
377	14×	return Err(CborError::BadMapKey);
378	540537×	}
379	144459×	}
380	684996×	last = Some(k);
381	684996×	let v = self.value()?;
382	684713×	m.insert(k, v);
383		}
384	160800×	Value::Map(m)
385		}
386	510×	_ => return Err(CborError::Unsupported("tag")),
387		}
388		};
389	1478015×	self.depth -= 1;
390	1478015×	Ok(v)
391	1483858×	}
392		}
393
394		#[cfg(test)]
395		mod tests {
396		use super::*;
397
398	12×	fn rt(v: Value) -> Vec<u8> {
399	12×	let b = encode(&v);
400	12×	assert_eq!(decode(&b).unwrap(), v);
401	12×	b
402	12×	}
403
404		#[test]
405	1×	fn integers_use_shortest_form() {
406	1×	assert_eq!(rt(Value::Uint(0)), [0x00]);
407	1×	assert_eq!(rt(Value::Uint(23)), [0x17]);
408	1×	assert_eq!(rt(Value::Uint(24)), [0x18, 24]);
409	1×	assert_eq!(rt(Value::Uint(255)), [0x18, 255]);
410	1×	assert_eq!(rt(Value::Uint(256)), [0x19, 1, 0]);
411	1×	assert_eq!(rt(Value::Uint(65536)), [0x1a, 0, 1, 0, 0]);
412	1×	assert_eq!(rt(Value::Uint(1 << 32)), [0x1b, 0, 0, 0, 1, 0, 0, 0, 0]);
413	1×	assert_eq!(rt(Value::Uint(u64::MAX)).len(), 9);
414	1×	}
415
416		#[test]
417	1×	fn rejects_non_shortest_integers() {
418	1×	assert_eq!(
419	1×	decode(&[0x18, 5]),
420		Err(CborError::NonCanonical("argument fits in the initial byte"))
421		);
422	1×	assert_eq!(
423	1×	decode(&[0x19, 0, 5]),
424		Err(CborError::NonCanonical("argument fits in one byte"))
425		);
426	1×	assert_eq!(
427	1×	decode(&[0x1a, 0, 0, 0, 5]),
428		Err(CborError::NonCanonical("argument fits in two bytes"))
429		);
430	1×	assert_eq!(
431	1×	decode(&[0x1b, 0, 0, 0, 0, 0, 0, 0, 5]),
432		Err(CborError::NonCanonical("argument fits in four bytes"))
433		);
434	1×	}
435
436		#[test]
437	1×	fn rejects_unsupported_items() {
438	1×	assert!(matches!(decode(&[0x20]), Err(CborError::Unsupported(_)))); // -1
439	1×	assert!(matches!(
440	1×	decode(&[0xc0, 0x00]),
441		Err(CborError::Unsupported(_))
442		)); // tag
443	1×	assert!(matches!(
444	1×	decode(&[0xf9, 0, 0]),
445		Err(CborError::Unsupported(_))
446		)); // float16
447	1×	assert!(matches!(
448	1×	decode(&[0x9f, 0xff]),
449		Err(CborError::Unsupported(_))
450		)); // indefinite array
451	1×	assert!(matches!(decode(&[0xf7]), Err(CborError::Unsupported(_)))); // undefined
452	1×	}
453
454		#[test]
455	1×	fn maps_are_sorted_and_unique() {
456	1×	let v = Value::map([
457	1×	(2, Value::Uint(1)),
458	1×	(0, Value::Null),
459	1×	(1, Value::Bool(true)),
460	1×	]);
461	1×	let b = rt(v);
462	1×	assert_eq!(b, [0xa3, 0x00, 0xf6, 0x01, 0xf5, 0x02, 0x01]);
463	1×	assert_eq!(
464	1×	decode(&[0xa2, 0x01, 0x00, 0x00, 0x00]),
465		Err(CborError::BadMapKey)
466		);
467	1×	assert_eq!(
468	1×	decode(&[0xa2, 0x01, 0x00, 0x01, 0x00]),
469		Err(CborError::BadMapKey)
470		);
471	1×	assert_eq!(decode(&[0xa1, 0x61, 0x61, 0x00]), Err(CborError::BadMapKey));
472		// text key
473	1×	}
474
475		#[test]
476	1×	fn strings_arrays_and_trailing() {
477	1×	rt(Value::Bytes(vec![1, 2, 3]));
478	1×	rt(Value::Text("héllo".into()));
479	1×	rt(Value::Array(vec![
480	1×	Value::Uint(1),
481	1×	Value::Text("x".into()),
482	1×	Value::Array(vec![]),
483	1×	]));
484	1×	assert_eq!(decode(&[0x00, 0x00]), Err(CborError::TrailingBytes));
485	1×	assert_eq!(decode(&[0x62, 0xff, 0xfe]), Err(CborError::InvalidUtf8));
486	1×	assert_eq!(decode(&[0x43, 1, 2]), Err(CborError::UnexpectedEnd));
487	1×	}
488
489		#[test]
490	1×	fn huge_length_does_not_allocate() {
491	1×	assert_eq!(
492	1×	decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
493		Err(CborError::LengthOverflow)
494		);
495	1×	assert!(decode(&[0x9b, 0x00, 0x00, 0x00, 0x01, 0, 0, 0, 0]).is_err());
496	1×	}
497
498	171472×	fn xorshift(state: &mut u64) -> u64 {
499	171472×	state ^= state << 13;
500	171472×	state ^= state >> 7;
501	171472×	state ^= state << 17;
502	171472×	*state
503	171472×	}
504
505	11210×	fn random_value(seed: &mut u64, depth: u32) -> Value {
506	11210×	match xorshift(seed) % if depth > 4 { 5 } else { 7 } {
507	1585×	0 => Value::Uint(match xorshift(seed) % 4 {
508	381×	0 => xorshift(seed) % 24,
509	410×	1 => xorshift(seed) % 256,
510	395×	2 => xorshift(seed) % 65536,
511	399×	_ => xorshift(seed),
512		}),
513	1657×	1 => Value::Bool(xorshift(seed).is_multiple_of(2)),
514	1603×	2 => Value::Null,
515		3 => {
516	1584×	let n = (xorshift(seed) % 40) as usize;
517	30661×	Value::Bytes((0..n).map(\|_\| (xorshift(seed) & 0xff) as u8).collect())
518		}
519		4 => {
520	1657×	let n = (xorshift(seed) % 12) as usize;
521		Value::Text(
522	1657×	(0..n)
523	9255×	.map(\|_\| char::from_u32((xorshift(seed) % 0x24f) as u32 + 1).unwrap_or('x'))
524	1657×	.collect(),
525		)
526		}
527		5 => {
528	1592×	let n = (xorshift(seed) % 5) as usize;
529	3115×	Value::Array((0..n).map(\|_\| random_value(seed, depth + 1)).collect())
530		}
531		_ => {
532	1532×	let n = (xorshift(seed) % 5) as usize;
533	1532×	let mut m = std::collections::BTreeMap::new();
534	3095×	for _ in 0..n {
535	3095×	m.insert(xorshift(seed) % 300, random_value(seed, depth + 1));
536	3095×	}
537	1532×	Value::Map(m)
538		}
539		}
540	11210×	}
541
542		/// Random values round-trip and re-encode identically (canonical form).
543		#[test]
544	1×	fn random_values_round_trip() {
545	1×	let mut seed = 0x2545f4914f6cdd1du64;
546	1×	for _ in 0..2000 {
547	2000×	let v = random_value(&mut seed, 0);
548	2000×	let b = encode(&v);
549	2000×	let back = decode(&b).unwrap();
550	2000×	assert_eq!(back, v);
551	2000×	assert_eq!(encode(&back), b);
552		}
553	1×	}
554
555		/// Random bytes and mutated encodings never panic; whatever decodes is
556		/// canonical, so re-encoding it reproduces the input exactly.
557		#[test]
558	1×	fn random_and_mutated_input_never_panics() {
559	1×	let mut seed = 0xdeadbeefcafef00du64;
560	1×	for _ in 0..3000 {
561	3000×	let n = (xorshift(&mut seed) % 64) as usize;
562	95063×	let bytes: Vec<u8> = (0..n).map(\|_\| (xorshift(&mut seed) & 0xff) as u8).collect();
563	3000×	if let Ok(v) = decode(&bytes) {
564	13×	assert_eq!(
565	13×	encode(&v),
566		bytes,
567		"accepted input must be canonical: {bytes:02x?}"
568		);
569	2987×	}
570		}
571	1×	for _ in 0..3000 {
572	3000×	let v = random_value(&mut seed, 0);
573	3000×	let mut b = encode(&v);
574	3000×	if b.is_empty() {
575	0×	continue;
576	3000×	}
577	3000×	match xorshift(&mut seed) % 3 {
578	1003×	0 => {
579	1003×	let at = (xorshift(&mut seed) as usize) % b.len();
580	1003×	b[at] ^= 1 << (xorshift(&mut seed) % 8);
581	1003×	}
582	1004×	1 => {
583	1004×	let keep = (xorshift(&mut seed) as usize) % b.len();
584	1004×	b.truncate(keep);
585	1004×	}
586	993×	_ => {
587	993×	let at = (xorshift(&mut seed) as usize) % b.len();
588	993×	b.insert(at, (xorshift(&mut seed) & 0xff) as u8);
589	993×	}
590		}
591	3000×	if let Ok(v2) = decode(&b) {
592	479×	assert_eq!(encode(&v2), b, "accepted mutation must be canonical");
593	2521×	}
594		}
595		// Deep nesting is refused rather than overflowing the stack.
596	1×	let mut deep = vec![0x81u8; 100_000];
597	1×	deep.push(0x00);
598	1×	assert!(matches!(decode(&deep), Err(CborError::Unsupported(_))));
599		// Lengths beyond the input are refused without allocating them.
600	1×	assert!(matches!(
601	1×	decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
602		Err(CborError::LengthOverflow) \| Err(CborError::UnexpectedEnd)
603		));
604	1×	}
605		}

Coverage / crates/oxy-core/src/cbor.rs 98.0%

Keyboard