crates/oxy-core/src/cbor.rs at v0.4.3 · andymccall/oxygen

◆ v0.4.3 oxygen / crates / oxy-core / src / cbor.rs

18.6 KiB · Rust · last changed First commit: 12 s and 2.1 GB on the Linux tree (refs #41) 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,
    /// An item already in its canonical encoding, written out as it is.
    /// Only built for encoding (never decoded): a large change's inline
    /// lines then cost their bytes, not a value per line.
    Encoded(Vec<u8>),
}

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

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

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

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

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

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

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

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

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

const MAX_DEPTH: u32 = 256;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Keyboard