crates/oxy-core/src/cbor.rs at 9935d490ddfb · andymccall/oxygen

# 9935d490ddfb oxygen / crates / oxy-core / src / cbor.rs

18.3 KiB · Rust · last changed Keep an insert's lines in one shared buffer 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: &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	}
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: &crate::lines::Lines) -> 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.iter() {
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: &crate::lines::Lines) -> 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	/// A cursor over canonical CBOR, for decoders that read part of an item
190	/// and skip or defer the rest (history-only loads of large changes).
191	pub struct Cursor<'a> {
192	d: Decoder<'a>,
193	}
194
195	impl<'a> Cursor<'a> {
196	pub fn new(bytes: &'a [u8]) -> Cursor<'a> {
197	Cursor {
198	d: Decoder {
199	b: bytes,
200	pos: 0,
201	depth: 0,
202	},
203	}
204	}
205
206	/// The offset of the next item.
207	pub fn pos(&self) -> usize {
208	self.d.pos
209	}
210
211	/// Whether every byte was read.
212	pub fn at_end(&self) -> bool {
213	self.d.pos == self.d.b.len()
214	}
215
216	/// The next head: (major type, argument).
217	pub fn head(&mut self) -> Result<(u8, u64), CborError> {
218	self.d.head()
219	}
220
221	/// The next item, decoded.
222	pub fn value(&mut self) -> Result<Value, CborError> {
223	self.d.value()
224	}
225
226	/// Step over the next item, checking only its structure.
227	pub fn skip(&mut self) -> Result<(), CborError> {
228	let ib = *self.d.b.get(self.d.pos).ok_or(CborError::UnexpectedEnd)?;
229	if ib >> 5 == 7 {
230	self.d.pos += 1;
231	return Ok(());
232	}
233	let (major, n) = self.d.head()?;
234	match major {
235	0 => {}
236	2 \| 3 => {
237	self.d.take(n)?;
238	}
239	4 => {
240	for _ in 0..n {
241	self.skip()?;
242	}
243	}
244	5 => {
245	for _ in 0..n.saturating_mul(2) {
246	self.skip()?;
247	}
248	}
249	_ => return Err(CborError::Unsupported("negative integer or tag")),
250	}
251	Ok(())
252	}
253	}
254
255	struct Decoder<'a> {
256	b: &'a [u8],
257	pos: usize,
258	depth: u32,
259	}
260
261	impl<'a> Decoder<'a> {
262	fn byte(&mut self) -> Result<u8, CborError> {
263	let x = *self.b.get(self.pos).ok_or(CborError::UnexpectedEnd)?;
264	self.pos += 1;
265	Ok(x)
266	}
267
268	fn take(&mut self, n: u64) -> Result<&'a [u8], CborError> {
269	let n = usize::try_from(n).map_err(\|_\| CborError::LengthOverflow)?;
270	let end = self.pos.checked_add(n).ok_or(CborError::LengthOverflow)?;
271	if end > self.b.len() {
272	return Err(CborError::UnexpectedEnd);
273	}
274	let s = &self.b[self.pos..end];
275	self.pos = end;
276	Ok(s)
277	}
278
279	/// Reads a head for majors 0..=5 and returns (major, argument), enforcing
280	/// shortest-form arguments.
281	fn head(&mut self) -> Result<(u8, u64), CborError> {
282	let ib = self.byte()?;
283	let major = ib >> 5;
284	let ai = ib & 0x1f;
285	if major == 7 {
286	return Err(CborError::Unsupported(
287	"simple value or float where a length or integer was expected",
288	));
289	}
290	let n = match ai {
291	0..=23 => ai as u64,
292	24 => {
293	let n = self.byte()? as u64;
294	if n < 24 {
295	return Err(CborError::NonCanonical("argument fits in the initial byte"));
296	}
297	n
298	}
299	25 => {
300	let n = u16::from_be_bytes(self.take(2)?.try_into().unwrap()) as u64;
301	if n <= 0xff {
302	return Err(CborError::NonCanonical("argument fits in one byte"));
303	}
304	n
305	}
306	26 => {
307	let n = u32::from_be_bytes(self.take(4)?.try_into().unwrap()) as u64;
308	if n <= 0xffff {
309	return Err(CborError::NonCanonical("argument fits in two bytes"));
310	}
311	n
312	}
313	27 => {
314	let n = u64::from_be_bytes(self.take(8)?.try_into().unwrap());
315	if n <= 0xffff_ffff {
316	return Err(CborError::NonCanonical("argument fits in four bytes"));
317	}
318	n
319	}
320	28..=30 => return Err(CborError::Unsupported("reserved additional information")),
321	_ => return Err(CborError::Unsupported("indefinite-length item")),
322	};
323	Ok((major, n))
324	}
325
326	fn value(&mut self) -> Result<Value, CborError> {
327	self.depth += 1;
328	if self.depth > MAX_DEPTH {
329	return Err(CborError::Unsupported("nesting deeper than 256"));
330	}
331	let ib = *self.b.get(self.pos).ok_or(CborError::UnexpectedEnd)?;
332	let v = if ib >> 5 == 7 {
333	self.pos += 1;
334	match ib {
335	0xf4 => Value::Bool(false),
336	0xf5 => Value::Bool(true),
337	0xf6 => Value::Null,
338	_ => {
339	return Err(CborError::Unsupported(
340	"simple value, float, undefined, or break",
341	))
342	}
343	}
344	} else {
345	let (major, n) = self.head()?;
346	match major {
347	0 => Value::Uint(n),
348	1 => return Err(CborError::Unsupported("negative integer")),
349	2 => Value::Bytes(self.take(n)?.to_vec()),
350	3 => Value::Text(
351	std::str::from_utf8(self.take(n)?)
352	.map_err(\|_\| CborError::InvalidUtf8)?
353	.to_owned(),
354	),
355	4 => {
356	let mut a = Vec::new();
357	for _ in 0..n {
358	a.push(self.value()?);
359	}
360	Value::Array(a)
361	}
362	5 => {
363	let mut m = BTreeMap::new();
364	let mut last: Option<u64> = None;
365	for _ in 0..n {
366	let (km, k) = self.head()?;
367	if km != 0 {
368	return Err(CborError::BadMapKey);
369	}
370	if let Some(l) = last {
371	if k <= l {
372	return Err(CborError::BadMapKey);
373	}
374	}
375	last = Some(k);
376	let v = self.value()?;
377	m.insert(k, v);
378	}
379	Value::Map(m)
380	}
381	_ => return Err(CborError::Unsupported("tag")),
382	}
383	};
384	self.depth -= 1;
385	Ok(v)
386	}
387	}
388
389	#[cfg(test)]
390	mod tests {
391	use super::*;
392
393	fn rt(v: Value) -> Vec<u8> {
394	let b = encode(&v);
395	assert_eq!(decode(&b).unwrap(), v);
396	b
397	}
398
399	#[test]
400	fn integers_use_shortest_form() {
401	assert_eq!(rt(Value::Uint(0)), [0x00]);
402	assert_eq!(rt(Value::Uint(23)), [0x17]);
403	assert_eq!(rt(Value::Uint(24)), [0x18, 24]);
404	assert_eq!(rt(Value::Uint(255)), [0x18, 255]);
405	assert_eq!(rt(Value::Uint(256)), [0x19, 1, 0]);
406	assert_eq!(rt(Value::Uint(65536)), [0x1a, 0, 1, 0, 0]);
407	assert_eq!(rt(Value::Uint(1 << 32)), [0x1b, 0, 0, 0, 1, 0, 0, 0, 0]);
408	assert_eq!(rt(Value::Uint(u64::MAX)).len(), 9);
409	}
410
411	#[test]
412	fn rejects_non_shortest_integers() {
413	assert_eq!(
414	decode(&[0x18, 5]),
415	Err(CborError::NonCanonical("argument fits in the initial byte"))
416	);
417	assert_eq!(
418	decode(&[0x19, 0, 5]),
419	Err(CborError::NonCanonical("argument fits in one byte"))
420	);
421	assert_eq!(
422	decode(&[0x1a, 0, 0, 0, 5]),
423	Err(CborError::NonCanonical("argument fits in two bytes"))
424	);
425	assert_eq!(
426	decode(&[0x1b, 0, 0, 0, 0, 0, 0, 0, 5]),
427	Err(CborError::NonCanonical("argument fits in four bytes"))
428	);
429	}
430
431	#[test]
432	fn rejects_unsupported_items() {
433	assert!(matches!(decode(&[0x20]), Err(CborError::Unsupported(_)))); // -1
434	assert!(matches!(
435	decode(&[0xc0, 0x00]),
436	Err(CborError::Unsupported(_))
437	)); // tag
438	assert!(matches!(
439	decode(&[0xf9, 0, 0]),
440	Err(CborError::Unsupported(_))
441	)); // float16
442	assert!(matches!(
443	decode(&[0x9f, 0xff]),
444	Err(CborError::Unsupported(_))
445	)); // indefinite array
446	assert!(matches!(decode(&[0xf7]), Err(CborError::Unsupported(_)))); // undefined
447	}
448
449	#[test]
450	fn maps_are_sorted_and_unique() {
451	let v = Value::map([
452	(2, Value::Uint(1)),
453	(0, Value::Null),
454	(1, Value::Bool(true)),
455	]);
456	let b = rt(v);
457	assert_eq!(b, [0xa3, 0x00, 0xf6, 0x01, 0xf5, 0x02, 0x01]);
458	assert_eq!(
459	decode(&[0xa2, 0x01, 0x00, 0x00, 0x00]),
460	Err(CborError::BadMapKey)
461	);
462	assert_eq!(
463	decode(&[0xa2, 0x01, 0x00, 0x01, 0x00]),
464	Err(CborError::BadMapKey)
465	);
466	assert_eq!(decode(&[0xa1, 0x61, 0x61, 0x00]), Err(CborError::BadMapKey));
467	// text key
468	}
469
470	#[test]
471	fn strings_arrays_and_trailing() {
472	rt(Value::Bytes(vec![1, 2, 3]));
473	rt(Value::Text("héllo".into()));
474	rt(Value::Array(vec![
475	Value::Uint(1),
476	Value::Text("x".into()),
477	Value::Array(vec![]),
478	]));
479	assert_eq!(decode(&[0x00, 0x00]), Err(CborError::TrailingBytes));
480	assert_eq!(decode(&[0x62, 0xff, 0xfe]), Err(CborError::InvalidUtf8));
481	assert_eq!(decode(&[0x43, 1, 2]), Err(CborError::UnexpectedEnd));
482	}
483
484	#[test]
485	fn huge_length_does_not_allocate() {
486	assert_eq!(
487	decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
488	Err(CborError::LengthOverflow)
489	);
490	assert!(decode(&[0x9b, 0x00, 0x00, 0x00, 0x01, 0, 0, 0, 0]).is_err());
491	}
492
493	fn xorshift(state: &mut u64) -> u64 {
494	state ^= state << 13;
495	state ^= state >> 7;
496	state ^= state << 17;
497	*state
498	}
499
500	fn random_value(seed: &mut u64, depth: u32) -> Value {
501	match xorshift(seed) % if depth > 4 { 5 } else { 7 } {
502	0 => Value::Uint(match xorshift(seed) % 4 {
503	0 => xorshift(seed) % 24,
504	1 => xorshift(seed) % 256,
505	2 => xorshift(seed) % 65536,
506	_ => xorshift(seed),
507	}),
508	1 => Value::Bool(xorshift(seed).is_multiple_of(2)),
509	2 => Value::Null,
510	3 => {
511	let n = (xorshift(seed) % 40) as usize;
512	Value::Bytes((0..n).map(\|_\| (xorshift(seed) & 0xff) as u8).collect())
513	}
514	4 => {
515	let n = (xorshift(seed) % 12) as usize;
516	Value::Text(
517	(0..n)
518	.map(\|_\| char::from_u32((xorshift(seed) % 0x24f) as u32 + 1).unwrap_or('x'))
519	.collect(),
520	)
521	}
522	5 => {
523	let n = (xorshift(seed) % 5) as usize;
524	Value::Array((0..n).map(\|_\| random_value(seed, depth + 1)).collect())
525	}
526	_ => {
527	let n = (xorshift(seed) % 5) as usize;
528	let mut m = std::collections::BTreeMap::new();
529	for _ in 0..n {
530	m.insert(xorshift(seed) % 300, random_value(seed, depth + 1));
531	}
532	Value::Map(m)
533	}
534	}
535	}
536
537	/// Random values round-trip and re-encode identically (canonical form).
538	#[test]
539	fn random_values_round_trip() {
540	let mut seed = 0x2545f4914f6cdd1du64;
541	for _ in 0..2000 {
542	let v = random_value(&mut seed, 0);
543	let b = encode(&v);
544	let back = decode(&b).unwrap();
545	assert_eq!(back, v);
546	assert_eq!(encode(&back), b);
547	}
548	}
549
550	/// Random bytes and mutated encodings never panic; whatever decodes is
551	/// canonical, so re-encoding it reproduces the input exactly.
552	#[test]
553	fn random_and_mutated_input_never_panics() {
554	let mut seed = 0xdeadbeefcafef00du64;
555	for _ in 0..3000 {
556	let n = (xorshift(&mut seed) % 64) as usize;
557	let bytes: Vec<u8> = (0..n).map(\|_\| (xorshift(&mut seed) & 0xff) as u8).collect();
558	if let Ok(v) = decode(&bytes) {
559	assert_eq!(
560	encode(&v),
561	bytes,
562	"accepted input must be canonical: {bytes:02x?}"
563	);
564	}
565	}
566	for _ in 0..3000 {
567	let v = random_value(&mut seed, 0);
568	let mut b = encode(&v);
569	if b.is_empty() {
570	continue;
571	}
572	match xorshift(&mut seed) % 3 {
573	0 => {
574	let at = (xorshift(&mut seed) as usize) % b.len();
575	b[at] ^= 1 << (xorshift(&mut seed) % 8);
576	}
577	1 => {
578	let keep = (xorshift(&mut seed) as usize) % b.len();
579	b.truncate(keep);
580	}
581	_ => {
582	let at = (xorshift(&mut seed) as usize) % b.len();
583	b.insert(at, (xorshift(&mut seed) & 0xff) as u8);
584	}
585	}
586	if let Ok(v2) = decode(&b) {
587	assert_eq!(encode(&v2), b, "accepted mutation must be canonical");
588	}
589	}
590	// Deep nesting is refused rather than overflowing the stack.
591	let mut deep = vec![0x81u8; 100_000];
592	deep.push(0x00);
593	assert!(matches!(decode(&deep), Err(CborError::Unsupported(_))));
594	// Lengths beyond the input are refused without allocating them.
595	assert!(matches!(
596	decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
597	Err(CborError::LengthOverflow) \| Err(CborError::UnexpectedEnd)
598	));
599	}
600	}

Keyboard