1use crate::{
6 deterministic::try_vec_with_capacity, DeterministicCborError, DeterministicCborInteger,
7 DeterministicCborMapEntry, DeterministicCborMapKey, DeterministicCborValue,
8 MAX_DETERMINISTIC_CBOR_AGGREGATE_BYTE_STRING_BYTES,
9 MAX_DETERMINISTIC_CBOR_AGGREGATE_TEXT_BYTES, MAX_DETERMINISTIC_CBOR_CONTAINER_ENTRIES,
10 MAX_DETERMINISTIC_CBOR_NESTING_DEPTH, MAX_DETERMINISTIC_CBOR_NODES,
11 MAX_DETERMINISTIC_CBOR_OUTPUT_LEN,
12};
13use std::cmp::Ordering;
14use zeroize::{Zeroize, Zeroizing};
15
16const MT_UINT: u8 = 0;
17const MT_NEGINT: u8 = 1;
18const MT_BYTES: u8 = 2;
19const MT_STRING: u8 = 3;
20const MT_ARRAY: u8 = 4;
21const MT_MAP: u8 = 5;
22
23pub fn encode_deterministic_cbor(
29 value: &DeterministicCborValue,
30) -> Result<Zeroizing<Vec<u8>>, DeterministicCborError> {
31 let preflight = preflight_value(value, 0)?;
32 if preflight.encoded_len > MAX_DETERMINISTIC_CBOR_OUTPUT_LEN {
33 return Err(DeterministicCborError::OutputTooLarge);
34 }
35
36 let mut output = Zeroizing::new(try_vec_with_capacity(preflight.encoded_len)?);
37 encode_value(value, &mut output, 0)?;
38 if output.len() != preflight.encoded_len {
39 return Err(DeterministicCborError::PreflightLengthMismatch);
40 }
41 Ok(output)
42}
43
44#[derive(Clone, Copy, Default)]
45struct Preflight {
46 encoded_len: usize,
47 nodes: usize,
48 aggregate_text_bytes: usize,
49 aggregate_byte_string_bytes: usize,
50}
51
52impl Preflight {
53 fn node(encoded_len: usize) -> Result<Self, DeterministicCborError> {
54 Ok(Self {
55 encoded_len,
56 nodes: 1,
57 aggregate_text_bytes: 0,
58 aggregate_byte_string_bytes: 0,
59 })
60 }
61
62 fn text(encoded_len: usize, byte_len: usize) -> Result<Self, DeterministicCborError> {
63 let mut stats = Self::node(encoded_len)?;
64 stats.aggregate_text_bytes = byte_len;
65 stats.ensure_limits()?;
66 Ok(stats)
67 }
68
69 fn bytes(encoded_len: usize, byte_len: usize) -> Result<Self, DeterministicCborError> {
70 let mut stats = Self::node(encoded_len)?;
71 stats.aggregate_byte_string_bytes = byte_len;
72 stats.ensure_limits()?;
73 Ok(stats)
74 }
75
76 fn add(&mut self, other: Self) -> Result<(), DeterministicCborError> {
77 self.encoded_len = checked_add(self.encoded_len, other.encoded_len)?;
78 self.nodes = checked_add(self.nodes, other.nodes)?;
79 self.aggregate_text_bytes =
80 checked_add(self.aggregate_text_bytes, other.aggregate_text_bytes)?;
81 self.aggregate_byte_string_bytes = checked_add(
82 self.aggregate_byte_string_bytes,
83 other.aggregate_byte_string_bytes,
84 )?;
85 self.ensure_limits()
86 }
87
88 fn ensure_limits(&self) -> Result<(), DeterministicCborError> {
89 if self.encoded_len > MAX_DETERMINISTIC_CBOR_OUTPUT_LEN {
90 return Err(DeterministicCborError::OutputTooLarge);
91 }
92 if self.nodes > MAX_DETERMINISTIC_CBOR_NODES {
93 return Err(DeterministicCborError::NodeLimitExceeded);
94 }
95 if self.aggregate_text_bytes > MAX_DETERMINISTIC_CBOR_AGGREGATE_TEXT_BYTES {
96 return Err(DeterministicCborError::AggregateTextBytesExceeded);
97 }
98 if self.aggregate_byte_string_bytes > MAX_DETERMINISTIC_CBOR_AGGREGATE_BYTE_STRING_BYTES {
99 return Err(DeterministicCborError::AggregateByteStringBytesExceeded);
100 }
101 Ok(())
102 }
103}
104
105fn preflight_value(
106 value: &DeterministicCborValue,
107 depth: usize,
108) -> Result<Preflight, DeterministicCborError> {
109 match value {
110 DeterministicCborValue::Null | DeterministicCborValue::Bool(_) => preflight_simple(),
111 DeterministicCborValue::Integer(integer) => preflight_integer(integer),
112 DeterministicCborValue::Text(text) => {
113 let byte_len = text.len();
114 Preflight::text(
115 checked_add(header_len(len_as_u64(byte_len)?)?, byte_len)?,
116 byte_len,
117 )
118 }
119 DeterministicCborValue::Bytes(bytes) => {
120 let byte_len = bytes.len();
121 Preflight::bytes(
122 checked_add(header_len(len_as_u64(byte_len)?)?, byte_len)?,
123 byte_len,
124 )
125 }
126 DeterministicCborValue::Array(values) => {
127 let child_depth = descend(depth)?;
128 ensure_container_entries(values.len())?;
129 let mut stats = Preflight::node(header_len(len_as_u64(values.len())?)?)?;
130 for child in values {
131 stats.add(preflight_value(child, child_depth)?)?;
132 }
133 Ok(stats)
134 }
135 DeterministicCborValue::Map(entries) => preflight_map(entries, depth, preflight_value),
136 }
137}
138
139fn preflight_simple() -> Result<Preflight, DeterministicCborError> {
140 Preflight::node(1)
141}
142
143fn preflight_map(
144 entries: &[DeterministicCborMapEntry],
145 depth: usize,
146 mut preflight_child: impl FnMut(
147 &DeterministicCborValue,
148 usize,
149 ) -> Result<Preflight, DeterministicCborError>,
150) -> Result<Preflight, DeterministicCborError> {
151 let child_depth = descend(depth)?;
152 ensure_container_entries(entries.len())?;
153 let mut stats = Preflight::node(header_len(len_as_u64(entries.len())?)?)?;
154 for entry in entries {
155 stats.add(preflight_key(entry.key())?)?;
156 stats.add(preflight_child(entry.value(), child_depth)?)?;
157 }
158
159 let mut decorated = decorated_map_entries(entries)?;
165 sort_map_entries(&mut decorated)?;
166 Ok(stats)
167}
168
169fn preflight_key(key: &DeterministicCborMapKey) -> Result<Preflight, DeterministicCborError> {
170 match key {
171 DeterministicCborMapKey::Integer(integer) => preflight_integer(integer),
172 DeterministicCborMapKey::Text(text) => {
173 let byte_len = text.len();
174 Preflight::text(
175 checked_add(header_len(len_as_u64(byte_len)?)?, byte_len)?,
176 byte_len,
177 )
178 }
179 }
180}
181
182fn preflight_integer(
183 integer: &DeterministicCborInteger,
184) -> Result<Preflight, DeterministicCborError> {
185 match integer {
186 DeterministicCborInteger::Unsigned(value) => Preflight::node(header_len(*value)?),
187 DeterministicCborInteger::Negative(value) => {
188 let encoded = negative_argument(value.value())?;
189 Preflight::node(header_len(encoded)?)
190 }
191 }
192}
193
194struct DecoratedMapEntry<'a> {
195 encoded_key: Zeroizing<Vec<u8>>,
196 entry: &'a DeterministicCborMapEntry,
197}
198
199fn decorated_map_entries(
200 entries: &[DeterministicCborMapEntry],
201) -> Result<Vec<DecoratedMapEntry<'_>>, DeterministicCborError> {
202 collect_map_entries(entries, |key| encode_map_key(key, encode_key))
203}
204
205fn collect_map_entries<'a>(
206 entries: &'a [DeterministicCborMapEntry],
207 mut prepare_key: impl FnMut(
208 &DeterministicCborMapKey,
209 ) -> Result<Zeroizing<Vec<u8>>, DeterministicCborError>,
210) -> Result<Vec<DecoratedMapEntry<'a>>, DeterministicCborError> {
211 let mut decorated = try_vec_with_capacity(entries.len())?;
212 for entry in entries {
213 let encoded_key = prepare_key(entry.key())?;
214 decorated.push(DecoratedMapEntry { encoded_key, entry });
215 }
216 Ok(decorated)
217}
218
219fn encode_map_key(
220 key: &DeterministicCborMapKey,
221 write_key: impl FnOnce(&DeterministicCborMapKey, &mut Vec<u8>) -> Result<(), DeterministicCborError>,
222) -> Result<Zeroizing<Vec<u8>>, DeterministicCborError> {
223 let key_stats = preflight_key(key)?;
226 let mut encoded_key = Zeroizing::new(try_vec_with_capacity(key_stats.encoded_len)?);
227 write_key(key, &mut encoded_key)?;
228 if encoded_key.len() != key_stats.encoded_len {
229 return Err(DeterministicCborError::PreflightLengthMismatch);
230 }
231 Ok(encoded_key)
232}
233
234fn compare_decorated_keys(left: &DecoratedMapEntry<'_>, right: &DecoratedMapEntry<'_>) -> Ordering {
235 compare_encoded_keys(&left.encoded_key, &right.encoded_key)
236}
237
238fn compare_encoded_keys(left: &[u8], right: &[u8]) -> Ordering {
239 match left.len().cmp(&right.len()) {
240 Ordering::Equal => left.cmp(right),
241 ordering => ordering,
242 }
243}
244
245fn reject_duplicate_decorated_keys(
246 decorated: &[DecoratedMapEntry<'_>],
247) -> Result<(), DeterministicCborError> {
248 for pair in decorated.windows(2) {
249 if pair[0].encoded_key.as_slice() == pair[1].encoded_key.as_slice() {
250 return Err(DeterministicCborError::DuplicateMapKey);
251 }
252 }
253 Ok(())
254}
255
256fn sort_map_entries(decorated: &mut [DecoratedMapEntry<'_>]) -> Result<(), DeterministicCborError> {
257 decorated.sort_by(compare_decorated_keys);
258 reject_duplicate_decorated_keys(decorated)
259}
260
261fn encode_value(
262 value: &DeterministicCborValue,
263 output: &mut Vec<u8>,
264 depth: usize,
265) -> Result<(), DeterministicCborError> {
266 match value {
267 DeterministicCborValue::Null => push_byte(output, 0xf6),
268 DeterministicCborValue::Bool(bit) => encode_bool(*bit, output),
269 DeterministicCborValue::Integer(integer) => encode_integer(integer, output),
270 DeterministicCborValue::Text(text) => encode_text(text, output),
271 DeterministicCborValue::Bytes(bytes) => encode_bytes(bytes, output),
272 DeterministicCborValue::Array(values) => {
273 let child_depth = descend(depth)?;
274 ensure_container_entries(values.len())?;
275 write_header(MT_ARRAY, len_as_u64(values.len())?, output)?;
276 for child in values {
277 encode_value(child, output, child_depth)?;
278 }
279 Ok(())
280 }
281 DeterministicCborValue::Map(entries) => encode_map(entries, output, depth, encode_value),
282 }
283}
284
285fn encode_map(
286 entries: &[DeterministicCborMapEntry],
287 output: &mut Vec<u8>,
288 depth: usize,
289 encode_child: impl FnMut(
290 &DeterministicCborValue,
291 &mut Vec<u8>,
292 usize,
293 ) -> Result<(), DeterministicCborError>,
294) -> Result<(), DeterministicCborError> {
295 let child_depth = descend(depth)?;
296 ensure_container_entries(entries.len())?;
297 let mut decorated = decorated_map_entries(entries)?;
298 sort_map_entries(&mut decorated)?;
299 write_map_entries(decorated, output, child_depth, encode_child)
300}
301
302fn write_map_entries(
303 decorated: Vec<DecoratedMapEntry<'_>>,
304 output: &mut Vec<u8>,
305 child_depth: usize,
306 mut encode_child: impl FnMut(
307 &DeterministicCborValue,
308 &mut Vec<u8>,
309 usize,
310 ) -> Result<(), DeterministicCborError>,
311) -> Result<(), DeterministicCborError> {
312 write_header(MT_MAP, len_as_u64(decorated.len())?, output)?;
313 for decorated_entry in decorated {
314 extend_bytes(output, &decorated_entry.encoded_key)?;
317 encode_child(decorated_entry.entry.value(), output, child_depth)?;
318 }
319 Ok(())
320}
321
322fn encode_bool(bit: bool, output: &mut Vec<u8>) -> Result<(), DeterministicCborError> {
323 push_byte(output, if bit { 0xf5 } else { 0xf4 })
324}
325
326fn encode_key(
327 key: &DeterministicCborMapKey,
328 output: &mut Vec<u8>,
329) -> Result<(), DeterministicCborError> {
330 match key {
331 DeterministicCborMapKey::Integer(integer) => encode_integer(integer, output),
332 DeterministicCborMapKey::Text(text) => encode_text(text, output),
333 }
334}
335
336fn encode_integer(
337 integer: &DeterministicCborInteger,
338 output: &mut Vec<u8>,
339) -> Result<(), DeterministicCborError> {
340 match integer {
341 DeterministicCborInteger::Unsigned(value) => write_header(MT_UINT, *value, output),
342 DeterministicCborInteger::Negative(value) => {
343 write_header(MT_NEGINT, negative_argument(value.value())?, output)
344 }
345 }
346}
347
348fn encode_text(text: &str, output: &mut Vec<u8>) -> Result<(), DeterministicCborError> {
349 let bytes = text.as_bytes();
350 write_header(MT_STRING, len_as_u64(bytes.len())?, output)?;
351 extend_bytes(output, bytes)
352}
353
354fn encode_bytes(bytes: &[u8], output: &mut Vec<u8>) -> Result<(), DeterministicCborError> {
355 write_header(MT_BYTES, len_as_u64(bytes.len())?, output)?;
356 extend_bytes(output, bytes)
357}
358
359fn negative_argument(value: i64) -> Result<u64, DeterministicCborError> {
360 let argument = (-1_i128)
361 .checked_sub(i128::from(value))
362 .ok_or(DeterministicCborError::OffsetOverflow)?;
363 u64::try_from(argument).map_err(|_| DeterministicCborError::NegativeIntegerOutOfRange)
364}
365
366fn len_as_u64(len: usize) -> Result<u64, DeterministicCborError> {
367 u64::try_from(len).map_err(|_| DeterministicCborError::LengthTooLarge)
368}
369
370fn header_len(value: u64) -> Result<usize, DeterministicCborError> {
371 if value < 24 {
372 Ok(1)
373 } else if value < 0x100 {
374 Ok(2)
375 } else if value < 0x1_0000 {
376 Ok(3)
377 } else if value < 0x1_0000_0000 {
378 Ok(5)
379 } else {
380 Ok(9)
381 }
382}
383
384fn write_header(
385 major_type: u8,
386 value: u64,
387 output: &mut Vec<u8>,
388) -> Result<(), DeterministicCborError> {
389 let be = value.to_be_bytes();
390 let head = major_type << 5;
391 if value < 24 {
392 push_byte(output, head | be[7])
393 } else if value < 0x100 {
394 push_byte(output, head | 24)?;
395 extend_bytes(output, &be[7..8])
396 } else if value < 0x1_0000 {
397 push_byte(output, head | 25)?;
398 extend_bytes(output, &be[6..8])
399 } else if value < 0x1_0000_0000 {
400 push_byte(output, head | 26)?;
401 extend_bytes(output, &be[4..8])
402 } else {
403 push_byte(output, head | 27)?;
404 extend_bytes(output, &be)
405 }
406}
407
408fn push_byte(output: &mut Vec<u8>, byte: u8) -> Result<(), DeterministicCborError> {
409 let next_len = checked_add(output.len(), 1)?;
410 if next_len > MAX_DETERMINISTIC_CBOR_OUTPUT_LEN {
411 return Err(DeterministicCborError::OutputTooLarge);
412 }
413 output.push(byte);
414 Ok(())
415}
416
417fn extend_bytes(output: &mut Vec<u8>, bytes: &[u8]) -> Result<(), DeterministicCborError> {
418 let next_len = checked_add(output.len(), bytes.len())?;
419 if next_len > MAX_DETERMINISTIC_CBOR_OUTPUT_LEN {
420 return Err(DeterministicCborError::OutputTooLarge);
421 }
422 output.extend_from_slice(bytes);
423 Ok(())
424}
425
426fn descend(depth: usize) -> Result<usize, DeterministicCborError> {
427 let next = checked_add(depth, 1)?;
428 if next > MAX_DETERMINISTIC_CBOR_NESTING_DEPTH {
429 return Err(DeterministicCborError::DepthExceeded);
430 }
431 Ok(next)
432}
433
434fn ensure_container_entries(entries: usize) -> Result<(), DeterministicCborError> {
435 if entries > MAX_DETERMINISTIC_CBOR_CONTAINER_ENTRIES {
436 return Err(DeterministicCborError::ContainerEntriesExceeded);
437 }
438 Ok(())
439}
440
441fn checked_add(left: usize, right: usize) -> Result<usize, DeterministicCborError> {
442 left.checked_add(right)
443 .ok_or(DeterministicCborError::OffsetOverflow)
444}
445
446impl Drop for DecoratedMapEntry<'_> {
447 fn drop(&mut self) {
448 self.encoded_key.zeroize();
449 }
450}
451
452#[cfg(kani)]
453#[path = "encode_deterministic_cbor_proof_tests.rs"]
454mod proofs;
455
456#[cfg(test)]
457#[path = "encode_deterministic_cbor_tests.rs"]
458mod preflight_limit_tests;