Skip to main content

codec_cbor/
encode_deterministic_cbor.rs

1// SPDX-FileCopyrightText: 2026 ReallyMe Technologies Limited
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5use 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
23/// Encode a value using the deterministic generic-CBOR profile.
24///
25/// The encoder validates limits and computes the exact output length before
26/// allocating the result. Temporary encoded map-key buffers are zeroized after
27/// sorting and duplicate detection.
28pub 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    // Establish the aggregate tree budgets before copying any map key
160    // into a sortable owner. Bounding each key independently is not
161    // enough: a caller can otherwise supply many individually valid,
162    // large keys and force substantial temporary allocation before
163    // the aggregate text/output limit rejects the map.
164    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    // Pre-size the key buffer so a reallocation cannot leave earlier key
224    // bytes in a freed block that the final owner cannot wipe.
225    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        // Write each key from the sorted entry, then visit that same entry's
315        // value. The child shares the output and its preflighted capacity.
316        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;