crates/oxy-core/src/cbor.rs at 206c76cad4bf · andymccall/oxygen

# 206c76cad4bf 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

ff0af1ee unknown 1 month ago	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> {
75167672 Andy McCall 1 month ago	42	if let Value::Uint(n) = self {
	43	Some(*n)
	44	} else {
	45	None
	46	}
ff0af1ee unknown 1 month ago	47	}
ff0af1ee unknown 1 month ago	48	pub fn as_bytes(&self) -> Option<&[u8]> {
75167672 Andy McCall 1 month ago	49	if let Value::Bytes(b) = self {
	50	Some(b)
	51	} else {
	52	None
	53	}
ff0af1ee unknown 1 month ago	54	}
ff0af1ee unknown 1 month ago	55	pub fn as_text(&self) -> Option<&str> {
75167672 Andy McCall 1 month ago	56	if let Value::Text(t) = self {
	57	Some(t)
	58	} else {
	59	None
	60	}
ff0af1ee unknown 1 month ago	61	}
ff0af1ee unknown 1 month ago	62	pub fn as_array(&self) -> Option<&[Value]> {
75167672 Andy McCall 1 month ago	63	if let Value::Array(a) = self {
	64	Some(a)
	65	} else {
	66	None
	67	}
ff0af1ee unknown 1 month ago	68	}
ff0af1ee unknown 1 month ago	69	pub fn as_map(&self) -> Option<&BTreeMap<u64, Value>> {
75167672 Andy McCall 1 month ago	70	if let Value::Map(m) = self {
	71	Some(m)
	72	} else {
	73	None
	74	}
ff0af1ee unknown 1 month ago	75	}
ff0af1ee unknown 1 month ago	76	pub fn as_bool(&self) -> Option<bool> {
75167672 Andy McCall 1 month ago	77	if let Value::Bool(b) = self {
	78	Some(*b)
	79	} else {
	80	None
	81	}
ff0af1ee unknown 1 month ago	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
6f8aeb99 Andy McCall 1 month ago ↶	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
ff0af1ee unknown 1 month ago	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> {
75167672 Andy McCall 1 month ago	175	let mut d = Decoder {
	176	b: bytes,
	177	pos: 0,
	178	depth: 0,
	179	};
ff0af1ee unknown 1 month ago	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 {
75167672 Andy McCall 1 month ago	220	return Err(CborError::Unsupported(
	221	"simple value or float where a length or integer was expected",
	222	));
ff0af1ee unknown 1 month ago	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,
75167672 Andy McCall 1 month ago	272	_ => {
	273	return Err(CborError::Unsupported(
	274	"simple value, float, undefined, or break",
	275	))
	276	}
ff0af1ee unknown 1 month ago	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() {
75167672 Andy McCall 1 month ago	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	);
ff0af1ee unknown 1 month ago	363	}
	364
	365	#[test]
	366	fn rejects_unsupported_items() {
	367	assert!(matches!(decode(&[0x20]), Err(CborError::Unsupported(_)))); // -1
75167672 Andy McCall 1 month ago	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
ff0af1ee unknown 1 month ago	380	assert!(matches!(decode(&[0xf7]), Err(CborError::Unsupported(_)))); // undefined
	381	}
	382
	383	#[test]
	384	fn maps_are_sorted_and_unique() {
75167672 Andy McCall 1 month ago	385	let v = Value::map([
	386	(2, Value::Uint(1)),
	387	(0, Value::Null),
	388	(1, Value::Bool(true)),
	389	]);
ff0af1ee unknown 1 month ago	390	let b = rt(v);
ff0af1ee unknown 1 month ago	391	assert_eq!(b, [0xa3, 0x00, 0xf6, 0x01, 0xf5, 0x02, 0x01]);
75167672 Andy McCall 1 month ago	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
ff0af1ee unknown 1 month ago	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()));
75167672 Andy McCall 1 month ago	408	rt(Value::Array(vec![
	409	Value::Uint(1),
	410	Value::Text("x".into()),
	411	Value::Array(vec![]),
	412	]));
ff0af1ee unknown 1 month ago	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() {
75167672 Andy McCall 1 month ago	420	assert_eq!(
	421	decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
	422	Err(CborError::LengthOverflow)
	423	);
ff0af1ee unknown 1 month ago	424	assert!(decode(&[0x9b, 0x00, 0x00, 0x00, 0x01, 0, 0, 0, 0]).is_err());
ff0af1ee unknown 1 month ago	425	}
2b872d07 Andy McCall 1 month ago ↶	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;
75167672 Andy McCall 1 month ago	450	Value::Text(
	451	(0..n)
	452	.map(\|_\| char::from_u32((xorshift(seed) % 0x24f) as u32 + 1).unwrap_or('x'))
	453	.collect(),
	454	)
2b872d07 Andy McCall 1 month ago ↶	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) {
75167672 Andy McCall 1 month ago	493	assert_eq!(
	494	encode(&v),
	495	bytes,
	496	"accepted input must be canonical: {bytes:02x?}"
	497	);
2b872d07 Andy McCall 1 month ago ↶	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.
75167672 Andy McCall 1 month ago	529	assert!(matches!(
	530	decode(&[0x5b, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff]),
	531	Err(CborError::LengthOverflow) \| Err(CborError::UnexpectedEnd)
	532	));
2b872d07 Andy McCall 1 month ago ↶	533	}
ff0af1ee unknown 1 month ago	534	}

Keyboard