crates/oxy-core/src/cbor.rs at 8457a6cc6984 · andymccall/oxygen

# 8457a6cc6984 oxygen / crates / oxy-core / src / cbor.rs

16.6 KiB · Rust · last changed Store large inserts as text blobs (change format 2) 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),
    }
}

/// 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: &[Vec<u8>]) -> Vec<u8> {
    let mut out = Vec::with_capacity(byte_strings_len(items));
    head(&mut out, 4, items.len() as u64);
    for b in items {
        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: &[Vec<u8>]) -> 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;

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

Keyboard