crates/oxy-core/src/cbor.rs at 7b9809e67c3d · andymccall/oxygen

# 7b9809e67c3d oxygen / crates / oxy-core / src / cbor.rs

14.7 KiB · Rust · last changed Hardening: CBOR and pack corruption tests, index bounds validation, concurrent HTTP push test, 1 GiB benchmark (spec 0.6q) 1 month ago source blame history raw

//! 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,
}

#[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),
    }
}

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;

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	}
18
19	#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
20	pub enum CborError {
21	#[error("unexpected end of input")]
22	UnexpectedEnd,
23	#[error("non-canonical encoding: {0}")]
24	NonCanonical(&'static str),
25	#[error("unsupported CBOR item: {0}")]
26	Unsupported(&'static str),
27	#[error("trailing bytes after value")]
28	TrailingBytes,
29	#[error("invalid UTF-8 in text string")]
30	InvalidUtf8,
31	#[error("map keys must be strictly increasing unsigned integers")]
32	BadMapKey,
33	#[error("length exceeds input")]
34	LengthOverflow,
35	}
36
37	impl Value {
38	pub fn map(pairs: impl IntoIterator<Item = (u64, Value)>) -> Value {
39	Value::Map(pairs.into_iter().collect())
40	}
41	pub fn as_uint(&self) -> Option<u64> {
42	if let Value::Uint(n) = self { Some(*n) } else { None }
43	}
44	pub fn as_bytes(&self) -> Option<&[u8]> {
45	if let Value::Bytes(b) = self { Some(b) } else { None }
46	}
47	pub fn as_text(&self) -> Option<&str> {
48	if let Value::Text(t) = self { Some(t) } else { None }
49	}
50	pub fn as_array(&self) -> Option<&[Value]> {
51	if let Value::Array(a) = self { Some(a) } else { None }
52	}
53	pub fn as_map(&self) -> Option<&BTreeMap<u64, Value>> {
54	if let Value::Map(m) = self { Some(m) } else { None }
55	}
56	pub fn as_bool(&self) -> Option<bool> {
57	if let Value::Bool(b) = self { Some(*b) } else { None }
58	}
59	pub fn is_null(&self) -> bool {
60	matches!(self, Value::Null)
61	}
62	}
63
64	pub fn encode(v: &Value) -> Vec<u8> {
65	let mut out = Vec::new();
66	encode_into(v, &mut out);
67	out
68	}
69
70	pub fn encode_into(v: &Value, out: &mut Vec<u8>) {
71	match v {
72	Value::Uint(n) => head(out, 0, *n),
73	Value::Bytes(b) => {
74	head(out, 2, b.len() as u64);
75	out.extend_from_slice(b);
76	}
77	Value::Text(t) => {
78	head(out, 3, t.len() as u64);
79	out.extend_from_slice(t.as_bytes());
80	}
81	Value::Array(a) => {
82	head(out, 4, a.len() as u64);
83	for x in a {
84	encode_into(x, out);
85	}
86	}
87	Value::Map(m) => {
88	head(out, 5, m.len() as u64);
89	for (k, x) in m {
90	head(out, 0, *k);
91	encode_into(x, out);
92	}
93	}
94	Value::Bool(false) => out.push(0xf4),
95	Value::Bool(true) => out.push(0xf5),
96	Value::Null => out.push(0xf6),
97	}
98	}
99
100	fn head(out: &mut Vec<u8>, major: u8, n: u64) {
101	let m = major << 5;
102	if n < 24 {
103	out.push(m \| n as u8);
104	} else if n <= 0xff {
105	out.push(m \| 24);
106	out.push(n as u8);
107	} else if n <= 0xffff {
108	out.push(m \| 25);
109	out.extend_from_slice(&(n as u16).to_be_bytes());
110	} else if n <= 0xffff_ffff {
111	out.push(m \| 26);
112	out.extend_from_slice(&(n as u32).to_be_bytes());
113	} else {
114	out.push(m \| 27);
115	out.extend_from_slice(&n.to_be_bytes());
116	}
117	}
118
119	pub fn decode(bytes: &[u8]) -> Result<Value, CborError> {
120	let mut d = Decoder { b: bytes, pos: 0, depth: 0 };
121	let v = d.value()?;
122	if d.pos != bytes.len() {
123	return Err(CborError::TrailingBytes);
124	}
125	Ok(v)
126	}
127
128	const MAX_DEPTH: u32 = 256;
129
130	struct Decoder<'a> {
131	b: &'a [u8],
132	pos: usize,
133	depth: u32,
134	}
135
136	impl<'a> Decoder<'a> {
137	fn byte(&mut self) -> Result<u8, CborError> {
138	let x = *self.b.get(self.pos).ok_or(CborError::UnexpectedEnd)?;
139	self.pos += 1;
140	Ok(x)
141	}
142
143	fn take(&mut self, n: u64) -> Result<&'a [u8], CborError> {
144	let n = usize::try_from(n).map_err(\|_\| CborError::LengthOverflow)?;
145	let end = self.pos.checked_add(n).ok_or(CborError::LengthOverflow)?;
146	if end > self.b.len() {
147	return Err(CborError::UnexpectedEnd);
148	}
149	let s = &self.b[self.pos..end];
150	self.pos = end;
151	Ok(s)
152	}
153
154	/// Reads a head for majors 0..=5 and returns (major, argument), enforcing
155	/// shortest-form arguments.
156	fn head(&mut self) -> Result<(u8, u64), CborError> {
157	let ib = self.byte()?;
158	let major = ib >> 5;
159	let ai = ib & 0x1f;
160	if major == 7 {
161	return Err(CborError::Unsupported("simple value or float where a length or integer was expected"));
162	}
163	let n = match ai {
164	0..=23 => ai as u64,
165	24 => {
166	let n = self.byte()? as u64;
167	if n < 24 {
168	return Err(CborError::NonCanonical("argument fits in the initial byte"));
169	}
170	n
171	}
172	25 => {
173	let n = u16::from_be_bytes(self.take(2)?.try_into().unwrap()) as u64;
174	if n <= 0xff {
175	return Err(CborError::NonCanonical("argument fits in one byte"));
176	}
177	n
178	}
179	26 => {
180	let n = u32::from_be_bytes(self.take(4)?.try_into().unwrap()) as u64;
181	if n <= 0xffff {
182	return Err(CborError::NonCanonical("argument fits in two bytes"));
183	}
184	n
185	}
186	27 => {
187	let n = u64::from_be_bytes(self.take(8)?.try_into().unwrap());
188	if n <= 0xffff_ffff {
189	return Err(CborError::NonCanonical("argument fits in four bytes"));
190	}
191	n
192	}
193	28..=30 => return Err(CborError::Unsupported("reserved additional information")),
194	_ => return Err(CborError::Unsupported("indefinite-length item")),
195	};
196	Ok((major, n))
197	}
198
199	fn value(&mut self) -> Result<Value, CborError> {
200	self.depth += 1;
201	if self.depth > MAX_DEPTH {
202	return Err(CborError::Unsupported("nesting deeper than 256"));
203	}
204	let ib = *self.b.get(self.pos).ok_or(CborError::UnexpectedEnd)?;
205	let v = if ib >> 5 == 7 {
206	self.pos += 1;
207	match ib {
208	0xf4 => Value::Bool(false),
209	0xf5 => Value::Bool(true),
210	0xf6 => Value::Null,
211	_ => return Err(CborError::Unsupported("simple value, float, undefined, or break")),
212	}
213	} else {
214	let (major, n) = self.head()?;
215	match major {
216	0 => Value::Uint(n),
217	1 => return Err(CborError::Unsupported("negative integer")),
218	2 => Value::Bytes(self.take(n)?.to_vec()),
219	3 => Value::Text(
220	std::str::from_utf8(self.take(n)?)
221	.map_err(\|_\| CborError::InvalidUtf8)?
222	.to_owned(),
223	),
224	4 => {
225	let mut a = Vec::new();
226	for _ in 0..n {
227	a.push(self.value()?);
228	}
229	Value::Array(a)
230	}
231	5 => {
232	let mut m = BTreeMap::new();
233	let mut last: Option<u64> = None;
234	for _ in 0..n {
235	let (km, k) = self.head()?;
236	if km != 0 {
237	return Err(CborError::BadMapKey);
238	}
239	if let Some(l) = last {
240	if k <= l {
241	return Err(CborError::BadMapKey);
242	}
243	}
244	last = Some(k);
245	let v = self.value()?;
246	m.insert(k, v);
247	}
248	Value::Map(m)
249	}
250	_ => return Err(CborError::Unsupported("tag")),
251	}
252	};
253	self.depth -= 1;
254	Ok(v)
255	}
256	}
257
258	#[cfg(test)]
259	mod tests {
260	use super::*;
261
262	fn rt(v: Value) -> Vec<u8> {
263	let b = encode(&v);
264	assert_eq!(decode(&b).unwrap(), v);
265	b
266	}
267
268	#[test]
269	fn integers_use_shortest_form() {
270	assert_eq!(rt(Value::Uint(0)), [0x00]);
271	assert_eq!(rt(Value::Uint(23)), [0x17]);
272	assert_eq!(rt(Value::Uint(24)), [0x18, 24]);
273	assert_eq!(rt(Value::Uint(255)), [0x18, 255]);
274	assert_eq!(rt(Value::Uint(256)), [0x19, 1, 0]);
275	assert_eq!(rt(Value::Uint(65536)), [0x1a, 0, 1, 0, 0]);
276	assert_eq!(rt(Value::Uint(1 << 32)), [0x1b, 0, 0, 0, 1, 0, 0, 0, 0]);
277	assert_eq!(rt(Value::Uint(u64::MAX)).len(), 9);
278	}
279
280	#[test]
281	fn rejects_non_shortest_integers() {
282	assert_eq!(decode(&[0x18, 5]), Err(CborError::NonCanonical("argument fits in the initial byte")));
283	assert_eq!(decode(&[0x19, 0, 5]), Err(CborError::NonCanonical("argument fits in one byte")));
284	assert_eq!(decode(&[0x1a, 0, 0, 0, 5]), Err(CborError::NonCanonical("argument fits in two bytes")));
285	assert_eq!(decode(&[0x1b, 0, 0, 0, 0, 0, 0, 0, 5]), Err(CborError::NonCanonical("argument fits in four bytes")));
286	}
287
288	#[test]
289	fn rejects_unsupported_items() {
290	assert!(matches!(decode(&[0x20]), Err(CborError::Unsupported(_)))); // -1
291	assert!(matches!(decode(&[0xc0, 0x00]), Err(CborError::Unsupported(_)))); // tag
292	assert!(matches!(decode(&[0xf9, 0, 0]), Err(CborError::Unsupported(_)))); // float16
293	assert!(matches!(decode(&[0x9f, 0xff]), Err(CborError::Unsupported(_)))); // indefinite array
294	assert!(matches!(decode(&[0xf7]), Err(CborError::Unsupported(_)))); // undefined
295	}
296
297	#[test]
298	fn maps_are_sorted_and_unique() {
299	let v = Value::map([(2, Value::Uint(1)), (0, Value::Null), (1, Value::Bool(true))]);
300	let b = rt(v);
301	assert_eq!(b, [0xa3, 0x00, 0xf6, 0x01, 0xf5, 0x02, 0x01]);
302	assert_eq!(decode(&[0xa2, 0x01, 0x00, 0x00, 0x00]), Err(CborError::BadMapKey));
303	assert_eq!(decode(&[0xa2, 0x01, 0x00, 0x01, 0x00]), Err(CborError::BadMapKey));
304	assert_eq!(decode(&[0xa1, 0x61, 0x61, 0x00]), Err(CborError::BadMapKey)); // text key
305	}
306
307	#[test]
308	fn strings_arrays_and_trailing() {
309	rt(Value::Bytes(vec![1, 2, 3]));
310	rt(Value::Text("héllo".into()));
311	rt(Value::Array(vec![Value::Uint(1), Value::Text("x".into()), Value::Array(vec![])]));
312	assert_eq!(decode(&[0x00, 0x00]), Err(CborError::TrailingBytes));
313	assert_eq!(decode(&[0x62, 0xff, 0xfe]), Err(CborError::InvalidUtf8));
314	assert_eq!(decode(&[0x43, 1, 2]), Err(CborError::UnexpectedEnd));
315	}
316
317	#[test]
318	fn huge_length_does_not_allocate() {
319	assert_eq!(decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]), Err(CborError::LengthOverflow));
320	assert!(decode(&[0x9b, 0x00, 0x00, 0x00, 0x01, 0, 0, 0, 0]).is_err());
321	}
322
323	fn xorshift(state: &mut u64) -> u64 {
324	state ^= state << 13;
325	state ^= state >> 7;
326	state ^= state << 17;
327	*state
328	}
329
330	fn random_value(seed: &mut u64, depth: u32) -> Value {
331	match xorshift(seed) % if depth > 4 { 5 } else { 7 } {
332	0 => Value::Uint(match xorshift(seed) % 4 {
333	0 => xorshift(seed) % 24,
334	1 => xorshift(seed) % 256,
335	2 => xorshift(seed) % 65536,
336	_ => xorshift(seed),
337	}),
338	1 => Value::Bool(xorshift(seed).is_multiple_of(2)),
339	2 => Value::Null,
340	3 => {
341	let n = (xorshift(seed) % 40) as usize;
342	Value::Bytes((0..n).map(\|_\| (xorshift(seed) & 0xff) as u8).collect())
343	}
344	4 => {
345	let n = (xorshift(seed) % 12) as usize;
346	Value::Text((0..n).map(\|_\| char::from_u32((xorshift(seed) % 0x24f) as u32 + 1).unwrap_or('x')).collect())
347	}
348	5 => {
349	let n = (xorshift(seed) % 5) as usize;
350	Value::Array((0..n).map(\|_\| random_value(seed, depth + 1)).collect())
351	}
352	_ => {
353	let n = (xorshift(seed) % 5) as usize;
354	let mut m = std::collections::BTreeMap::new();
355	for _ in 0..n {
356	m.insert(xorshift(seed) % 300, random_value(seed, depth + 1));
357	}
358	Value::Map(m)
359	}
360	}
361	}
362
363	/// Random values round-trip and re-encode identically (canonical form).
364	#[test]
365	fn random_values_round_trip() {
366	let mut seed = 0x2545f4914f6cdd1du64;
367	for _ in 0..2000 {
368	let v = random_value(&mut seed, 0);
369	let b = encode(&v);
370	let back = decode(&b).unwrap();
371	assert_eq!(back, v);
372	assert_eq!(encode(&back), b);
373	}
374	}
375
376	/// Random bytes and mutated encodings never panic; whatever decodes is
377	/// canonical, so re-encoding it reproduces the input exactly.
378	#[test]
379	fn random_and_mutated_input_never_panics() {
380	let mut seed = 0xdeadbeefcafef00du64;
381	for _ in 0..3000 {
382	let n = (xorshift(&mut seed) % 64) as usize;
383	let bytes: Vec<u8> = (0..n).map(\|_\| (xorshift(&mut seed) & 0xff) as u8).collect();
384	if let Ok(v) = decode(&bytes) {
385	assert_eq!(encode(&v), bytes, "accepted input must be canonical: {bytes:02x?}");
386	}
387	}
388	for _ in 0..3000 {
389	let v = random_value(&mut seed, 0);
390	let mut b = encode(&v);
391	if b.is_empty() {
392	continue;
393	}
394	match xorshift(&mut seed) % 3 {
395	0 => {
396	let at = (xorshift(&mut seed) as usize) % b.len();
397	b[at] ^= 1 << (xorshift(&mut seed) % 8);
398	}
399	1 => {
400	let keep = (xorshift(&mut seed) as usize) % b.len();
401	b.truncate(keep);
402	}
403	_ => {
404	let at = (xorshift(&mut seed) as usize) % b.len();
405	b.insert(at, (xorshift(&mut seed) & 0xff) as u8);
406	}
407	}
408	if let Ok(v2) = decode(&b) {
409	assert_eq!(encode(&v2), b, "accepted mutation must be canonical");
410	}
411	}
412	// Deep nesting is refused rather than overflowing the stack.
413	let mut deep = vec![0x81u8; 100_000];
414	deep.push(0x00);
415	assert!(matches!(decode(&deep), Err(CborError::Unsupported(_))));
416	// Lengths beyond the input are refused without allocating them.
417	assert!(matches!(decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]), Err(CborError::LengthOverflow) \| Err(CborError::UnexpectedEnd)));
418	}
419	}

Keyboard