crates/oxy-core/src/cbor.rs at 098227d48b1a · andymccall/oxygen

# 098227d48b1a oxygen / crates / oxy-core / src / cbor.rs

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

Keyboard