crates/spectra-core/src/cbor.rs at c7161ec1a607 · andymccall/spectra

# c7161ec1a607 spectra / crates / spectra-core / src / cbor.rs

8.3 KiB · Rust · last changed Spectra stands alone: its own identities, signatures and CBOR; projects of any kind of work (#26, #27) 1 day ago source blame history raw

//! Deterministic CBOR (RFC 8949 §4.2), as much of it as Spectra encodes:
//! unsigned integers, byte and text strings, arrays, maps with integer
//! keys, null and booleans. Shortest forms, definite lengths, map keys in
//! ascending order; the decoder refuses anything else, so one value has
//! exactly one encoding and hashing it is meaningful (spec §9.5).

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,
}

impl Value {
    pub fn map<const N: usize>(entries: [(u64, Value); N]) -> Value {
        Value::Map(entries.into_iter().collect())
    }
    pub fn as_uint(&self) -> Option<u64> {
        match self {
            Value::Uint(u) => Some(*u),
            _ => None,
        }
    }
    pub fn as_bytes(&self) -> Option<&[u8]> {
        match self {
            Value::Bytes(b) => Some(b),
            _ => None,
        }
    }
    pub fn as_text(&self) -> Option<&str> {
        match self {
            Value::Text(t) => Some(t),
            _ => None,
        }
    }
    pub fn as_array(&self) -> Option<&[Value]> {
        match self {
            Value::Array(a) => Some(a),
            _ => None,
        }
    }
    pub fn as_map(&self) -> Option<&BTreeMap<u64, Value>> {
        match self {
            Value::Map(m) => Some(m),
            _ => None,
        }
    }
    pub fn is_null(&self) -> bool {
        matches!(self, Value::Null)
    }
}

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

fn put(out: &mut Vec<u8>, v: &Value) {
    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 {
                put(out, x);
            }
        }
        // BTreeMap iterates keys ascending, which for unsigned integers is
        // the order of their shortest encodings.
        Value::Map(m) => {
            head(out, 5, m.len() as u64);
            for (k, x) in m {
                head(out, 0, *k);
                put(out, x);
            }
        }
        Value::Bool(false) => out.push(0xf4),
        Value::Bool(true) => out.push(0xf5),
        Value::Null => out.push(0xf6),
    }
}

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

/// Why bytes are not a value Spectra encodes.
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
#[error("malformed CBOR: {0}")]
pub struct Error(pub String);

struct Reader<'a> {
    b: &'a [u8],
    at: usize,
    depth: usize,
}

const MAX_DEPTH: usize = 32;

impl<'a> Reader<'a> {
    fn take(&mut self, n: usize) -> Result<&'a [u8], Error> {
        let end = self.at.checked_add(n).filter(|e| *e <= self.b.len()).ok_or_else(|| Error("truncated".into()))?;
        let s = &self.b[self.at..end];
        self.at = end;
        Ok(s)
    }

    fn head(&mut self) -> Result<(u8, u64), Error> {
        let first = self.take(1)?[0];
        let (major, info) = (first >> 5, first & 0x1f);
        let n = match info {
            0..=23 => info as u64,
            24 => self.take(1)?[0] as u64,
            25 => u16::from_be_bytes(self.take(2)?.try_into().unwrap()) as u64,
            26 => u32::from_be_bytes(self.take(4)?.try_into().unwrap()) as u64,
            27 => u64::from_be_bytes(self.take(8)?.try_into().unwrap()),
            _ if major == 7 => return Ok((7, info as u64)),
            _ => return Err(Error("an indefinite length or a reserved form".into())),
        };
        let minimal = match info {
            24 => n >= 24,
            25 => n > 0xff,
            26 => n > 0xffff,
            27 => n > 0xffff_ffff,
            _ => true,
        };
        if !minimal && major != 7 {
            return Err(Error("a length or number not in its shortest form".into()));
        }
        Ok((major, n))
    }

    fn len(&mut self, n: u64) -> Result<usize, Error> {
        let n = usize::try_from(n).map_err(|_| Error("too long".into()))?;
        if n > self.b.len() - self.at {
            return Err(Error("truncated".into()));
        }
        Ok(n)
    }

    fn value(&mut self) -> Result<Value, Error> {
        self.depth += 1;
        if self.depth > MAX_DEPTH {
            return Err(Error("nested too deeply".into()));
        }
        let (major, n) = self.head()?;
        let v = match major {
            0 => Value::Uint(n),
            2 => {
                let l = self.len(n)?;
                Value::Bytes(self.take(l)?.to_vec())
            }
            3 => {
                let l = self.len(n)?;
                Value::Text(String::from_utf8(self.take(l)?.to_vec()).map_err(|_| Error("text that is not UTF-8".into()))?)
            }
            4 => {
                let l = self.len(n)?;
                let mut a = Vec::with_capacity(l);
                for _ in 0..l {
                    a.push(self.value()?);
                }
                Value::Array(a)
            }
            5 => {
                let l = self.len(n)?;
                let mut m = BTreeMap::new();
                let mut last: Option<u64> = None;
                for _ in 0..l {
                    let (km, k) = self.head()?;
                    if km != 0 {
                        return Err(Error("a map key that is not an unsigned integer".into()));
                    }
                    if last.is_some_and(|p| k <= p) {
                        return Err(Error("map keys out of order or repeated".into()));
                    }
                    last = Some(k);
                    m.insert(k, self.value()?);
                }
                Value::Map(m)
            }
            7 => match n {
                20 => Value::Bool(false),
                21 => Value::Bool(true),
                22 => Value::Null,
                _ => return Err(Error("an unsupported simple value or float".into())),
            },
            _ => return Err(Error("a negative integer or a tag".into())),
        };
        self.depth -= 1;
        Ok(v)
    }
}

/// Decode exactly one value, refusing any non-canonical encoding.
pub fn decode(b: &[u8]) -> Result<Value, Error> {
    let mut r = Reader { b, at: 0, depth: 0 };
    let v = r.value()?;
    if r.at != b.len() {
        return Err(Error("bytes after the value".into()));
    }
    Ok(v)
}

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

    #[test]
    fn round_trips_and_known_encodings() {
        let v = Value::map([
            (0, Value::Uint(1)),
            (1, Value::Text("é".into())),
            (2, Value::Bytes(vec![1, 2])),
            (3, Value::Array(vec![Value::Null, Value::Bool(true), Value::Uint(500)])),
            (24, Value::Uint(u64::MAX)),
        ]);
        let b = encode(&v);
        assert_eq!(decode(&b).unwrap(), v);
        assert_eq!(encode(&Value::Uint(23)), [0x17]);
        assert_eq!(encode(&Value::Uint(24)), [0x18, 24]);
        assert_eq!(encode(&Value::Uint(1000)), [0x19, 0x03, 0xe8]);
        assert_eq!(encode(&Value::Text("a".into())), [0x61, b'a']);
    }

    #[test]
    fn refuses_what_is_not_canonical() {
        assert!(decode(&[0x18, 5]).is_err(), "5 in two bytes");
        assert!(decode(&[0xa2, 0x01, 0x00, 0x00, 0x00]).is_err(), "keys out of order");
        assert!(decode(&[0x5f]).is_err(), "indefinite length");
        assert!(decode(&[0x01, 0x02]).is_err(), "trailing bytes");
        assert!(decode(&[0x5a, 0xff, 0xff, 0xff, 0xff]).is_err(), "truncated");
        assert!(decode(&[0x20]).is_err(), "negative");
        let deep = [0x81u8; 64];
        assert!(decode(&deep).is_err(), "too deep");
    }
}

`/`	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), as much of it as Spectra encodes:
2	//! unsigned integers, byte and text strings, arrays, maps with integer
3	//! keys, null and booleans. Shortest forms, definite lengths, map keys in
4	//! ascending order; the decoder refuses anything else, so one value has
5	//! exactly one encoding and hashing it is meaningful (spec §9.5).
6
7	use std::collections::BTreeMap;
8
9	#[derive(Clone, Debug, PartialEq, Eq)]
10	pub enum Value {
11	Uint(u64),
12	Bytes(Vec<u8>),
13	Text(String),
14	Array(Vec<Value>),
15	Map(BTreeMap<u64, Value>),
16	Bool(bool),
17	Null,
18	}
19
20	impl Value {
21	pub fn map<const N: usize>(entries: [(u64, Value); N]) -> Value {
22	Value::Map(entries.into_iter().collect())
23	}
24	pub fn as_uint(&self) -> Option<u64> {
25	match self {
26	Value::Uint(u) => Some(*u),
27	_ => None,
28	}
29	}
30	pub fn as_bytes(&self) -> Option<&[u8]> {
31	match self {
32	Value::Bytes(b) => Some(b),
33	_ => None,
34	}
35	}
36	pub fn as_text(&self) -> Option<&str> {
37	match self {
38	Value::Text(t) => Some(t),
39	_ => None,
40	}
41	}
42	pub fn as_array(&self) -> Option<&[Value]> {
43	match self {
44	Value::Array(a) => Some(a),
45	_ => None,
46	}
47	}
48	pub fn as_map(&self) -> Option<&BTreeMap<u64, Value>> {
49	match self {
50	Value::Map(m) => Some(m),
51	_ => None,
52	}
53	}
54	pub fn is_null(&self) -> bool {
55	matches!(self, Value::Null)
56	}
57	}
58
59	fn head(out: &mut Vec<u8>, major: u8, n: u64) {
60	let m = major << 5;
61	match n {
62	0..=23 => out.push(m \| n as u8),
63	24..=0xff => out.extend_from_slice(&[m \| 24, n as u8]),
64	0x100..=0xffff => {
65	out.push(m \| 25);
66	out.extend_from_slice(&(n as u16).to_be_bytes());
67	}
68	0x1_0000..=0xffff_ffff => {
69	out.push(m \| 26);
70	out.extend_from_slice(&(n as u32).to_be_bytes());
71	}
72	_ => {
73	out.push(m \| 27);
74	out.extend_from_slice(&n.to_be_bytes());
75	}
76	}
77	}
78
79	fn put(out: &mut Vec<u8>, v: &Value) {
80	match v {
81	Value::Uint(n) => head(out, 0, *n),
82	Value::Bytes(b) => {
83	head(out, 2, b.len() as u64);
84	out.extend_from_slice(b);
85	}
86	Value::Text(t) => {
87	head(out, 3, t.len() as u64);
88	out.extend_from_slice(t.as_bytes());
89	}
90	Value::Array(a) => {
91	head(out, 4, a.len() as u64);
92	for x in a {
93	put(out, x);
94	}
95	}
96	// BTreeMap iterates keys ascending, which for unsigned integers is
97	// the order of their shortest encodings.
98	Value::Map(m) => {
99	head(out, 5, m.len() as u64);
100	for (k, x) in m {
101	head(out, 0, *k);
102	put(out, x);
103	}
104	}
105	Value::Bool(false) => out.push(0xf4),
106	Value::Bool(true) => out.push(0xf5),
107	Value::Null => out.push(0xf6),
108	}
109	}
110
111	pub fn encode(v: &Value) -> Vec<u8> {
112	let mut out = Vec::new();
113	put(&mut out, v);
114	out
115	}
116
117	/// Why bytes are not a value Spectra encodes.
118	#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
119	#[error("malformed CBOR: {0}")]
120	pub struct Error(pub String);
121
122	struct Reader<'a> {
123	b: &'a [u8],
124	at: usize,
125	depth: usize,
126	}
127
128	const MAX_DEPTH: usize = 32;
129
130	impl<'a> Reader<'a> {
131	fn take(&mut self, n: usize) -> Result<&'a [u8], Error> {
132	let end = self.at.checked_add(n).filter(\|e\| *e <= self.b.len()).ok_or_else(\|\| Error("truncated".into()))?;
133	let s = &self.b[self.at..end];
134	self.at = end;
135	Ok(s)
136	}
137
138	fn head(&mut self) -> Result<(u8, u64), Error> {
139	let first = self.take(1)?[0];
140	let (major, info) = (first >> 5, first & 0x1f);
141	let n = match info {
142	0..=23 => info as u64,
143	24 => self.take(1)?[0] as u64,
144	25 => u16::from_be_bytes(self.take(2)?.try_into().unwrap()) as u64,
145	26 => u32::from_be_bytes(self.take(4)?.try_into().unwrap()) as u64,
146	27 => u64::from_be_bytes(self.take(8)?.try_into().unwrap()),
147	_ if major == 7 => return Ok((7, info as u64)),
148	_ => return Err(Error("an indefinite length or a reserved form".into())),
149	};
150	let minimal = match info {
151	24 => n >= 24,
152	25 => n > 0xff,
153	26 => n > 0xffff,
154	27 => n > 0xffff_ffff,
155	_ => true,
156	};
157	if !minimal && major != 7 {
158	return Err(Error("a length or number not in its shortest form".into()));
159	}
160	Ok((major, n))
161	}
162
163	fn len(&mut self, n: u64) -> Result<usize, Error> {
164	let n = usize::try_from(n).map_err(\|_\| Error("too long".into()))?;
165	if n > self.b.len() - self.at {
166	return Err(Error("truncated".into()));
167	}
168	Ok(n)
169	}
170
171	fn value(&mut self) -> Result<Value, Error> {
172	self.depth += 1;
173	if self.depth > MAX_DEPTH {
174	return Err(Error("nested too deeply".into()));
175	}
176	let (major, n) = self.head()?;
177	let v = match major {
178	0 => Value::Uint(n),
179	2 => {
180	let l = self.len(n)?;
181	Value::Bytes(self.take(l)?.to_vec())
182	}
183	3 => {
184	let l = self.len(n)?;
185	Value::Text(String::from_utf8(self.take(l)?.to_vec()).map_err(\|_\| Error("text that is not UTF-8".into()))?)
186	}
187	4 => {
188	let l = self.len(n)?;
189	let mut a = Vec::with_capacity(l);
190	for _ in 0..l {
191	a.push(self.value()?);
192	}
193	Value::Array(a)
194	}
195	5 => {
196	let l = self.len(n)?;
197	let mut m = BTreeMap::new();
198	let mut last: Option<u64> = None;
199	for _ in 0..l {
200	let (km, k) = self.head()?;
201	if km != 0 {
202	return Err(Error("a map key that is not an unsigned integer".into()));
203	}
204	if last.is_some_and(\|p\| k <= p) {
205	return Err(Error("map keys out of order or repeated".into()));
206	}
207	last = Some(k);
208	m.insert(k, self.value()?);
209	}
210	Value::Map(m)
211	}
212	7 => match n {
213	20 => Value::Bool(false),
214	21 => Value::Bool(true),
215	22 => Value::Null,
216	_ => return Err(Error("an unsupported simple value or float".into())),
217	},
218	_ => return Err(Error("a negative integer or a tag".into())),
219	};
220	self.depth -= 1;
221	Ok(v)
222	}
223	}
224
225	/// Decode exactly one value, refusing any non-canonical encoding.
226	pub fn decode(b: &[u8]) -> Result<Value, Error> {
227	let mut r = Reader { b, at: 0, depth: 0 };
228	let v = r.value()?;
229	if r.at != b.len() {
230	return Err(Error("bytes after the value".into()));
231	}
232	Ok(v)
233	}
234
235	#[cfg(test)]
236	mod tests {
237	use super::*;
238
239	#[test]
240	fn round_trips_and_known_encodings() {
241	let v = Value::map([
242	(0, Value::Uint(1)),
243	(1, Value::Text("é".into())),
244	(2, Value::Bytes(vec![1, 2])),
245	(3, Value::Array(vec![Value::Null, Value::Bool(true), Value::Uint(500)])),
246	(24, Value::Uint(u64::MAX)),
247	]);
248	let b = encode(&v);
249	assert_eq!(decode(&b).unwrap(), v);
250	assert_eq!(encode(&Value::Uint(23)), [0x17]);
251	assert_eq!(encode(&Value::Uint(24)), [0x18, 24]);
252	assert_eq!(encode(&Value::Uint(1000)), [0x19, 0x03, 0xe8]);
253	assert_eq!(encode(&Value::Text("a".into())), [0x61, b'a']);
254	}
255
256	#[test]
257	fn refuses_what_is_not_canonical() {
258	assert!(decode(&[0x18, 5]).is_err(), "5 in two bytes");
259	assert!(decode(&[0xa2, 0x01, 0x00, 0x00, 0x00]).is_err(), "keys out of order");
260	assert!(decode(&[0x5f]).is_err(), "indefinite length");
261	assert!(decode(&[0x01, 0x02]).is_err(), "trailing bytes");
262	assert!(decode(&[0x5a, 0xff, 0xff, 0xff, 0xff]).is_err(), "truncated");
263	assert!(decode(&[0x20]).is_err(), "negative");
264	let deep = [0x81u8; 64];
265	assert!(decode(&deep).is_err(), "too deep");
266	}
267	}

Keyboard