codec_cbor/
encode_deterministic_cbor.rs

1// SPDX-FileCopyrightText: Copyright © 2026 ReallyMe LLC. All rights reserved
2//
3// SPDX-License-Identifier: 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::node(1),
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) => {
136            let child_depth = descend(depth)?;
137            ensure_container_entries(entries.len())?;
138            let mut stats = Preflight::node(header_len(len_as_u64(entries.len())?)?)?;
139            for entry in entries {
140                stats.add(preflight_key(entry.key())?)?;
141                stats.add(preflight_value(entry.value(), child_depth)?)?;
142            }
143
144            // Establish the aggregate tree budgets before copying any map key
145            // into a sortable owner. Bounding each key independently is not
146            // enough: a caller can otherwise supply many individually valid,
147            // large keys and force substantial temporary allocation before
148            // the aggregate text/output limit rejects the map.
149            let mut decorated = decorated_map_entries(entries)?;
150            decorated.sort_by(compare_decorated_keys);
151            reject_duplicate_decorated_keys(&decorated)?;
152            Ok(stats)
153        }
154    }
155}
156
157fn preflight_key(key: &DeterministicCborMapKey) -> Result<Preflight, DeterministicCborError> {
158    match key {
159        DeterministicCborMapKey::Integer(integer) => preflight_integer(integer),
160        DeterministicCborMapKey::Text(text) => {
161            let byte_len = text.len();
162            Preflight::text(
163                checked_add(header_len(len_as_u64(byte_len)?)?, byte_len)?,
164                byte_len,
165            )
166        }
167    }
168}
169
170fn preflight_integer(
171    integer: &DeterministicCborInteger,
172) -> Result<Preflight, DeterministicCborError> {
173    match integer {
174        DeterministicCborInteger::Unsigned(value) => Preflight::node(header_len(*value)?),
175        DeterministicCborInteger::Negative(value) => {
176            let encoded = negative_argument(value.value())?;
177            Preflight::node(header_len(encoded)?)
178        }
179    }
180}
181
182struct DecoratedMapEntry<'a> {
183    encoded_key: Zeroizing<Vec<u8>>,
184    entry: &'a DeterministicCborMapEntry,
185}
186
187fn decorated_map_entries(
188    entries: &[DeterministicCborMapEntry],
189) -> Result<Vec<DecoratedMapEntry<'_>>, DeterministicCborError> {
190    let mut decorated = try_vec_with_capacity(entries.len())?;
191    for entry in entries {
192        // Pre-size every sensitive temporary from the same semantic preflight
193        // used by the encoder. A growing Vec can leave superseded key bytes in
194        // freed allocator blocks that the final Zeroizing owner cannot wipe.
195        let key_stats = preflight_key(entry.key())?;
196        let mut encoded_key = Zeroizing::new(try_vec_with_capacity(key_stats.encoded_len)?);
197        encode_key(entry.key(), &mut encoded_key)?;
198        if encoded_key.len() != key_stats.encoded_len {
199            return Err(DeterministicCborError::PreflightLengthMismatch);
200        }
201        decorated.push(DecoratedMapEntry { encoded_key, entry });
202    }
203    Ok(decorated)
204}
205
206fn compare_decorated_keys(left: &DecoratedMapEntry<'_>, right: &DecoratedMapEntry<'_>) -> Ordering {
207    compare_encoded_keys(&left.encoded_key, &right.encoded_key)
208}
209
210fn compare_encoded_keys(left: &[u8], right: &[u8]) -> Ordering {
211    match left.len().cmp(&right.len()) {
212        Ordering::Equal => left.cmp(right),
213        ordering => ordering,
214    }
215}
216
217fn reject_duplicate_decorated_keys(
218    decorated: &[DecoratedMapEntry<'_>],
219) -> Result<(), DeterministicCborError> {
220    for pair in decorated.windows(2) {
221        if pair[0].encoded_key.as_slice() == pair[1].encoded_key.as_slice() {
222            return Err(DeterministicCborError::DuplicateMapKey);
223        }
224    }
225    Ok(())
226}
227
228fn encode_value(
229    value: &DeterministicCborValue,
230    output: &mut Vec<u8>,
231    depth: usize,
232) -> Result<(), DeterministicCborError> {
233    match value {
234        DeterministicCborValue::Null => push_byte(output, 0xf6),
235        DeterministicCborValue::Bool(false) => push_byte(output, 0xf4),
236        DeterministicCborValue::Bool(true) => push_byte(output, 0xf5),
237        DeterministicCborValue::Integer(integer) => encode_integer(integer, output),
238        DeterministicCborValue::Text(text) => encode_text(text, output),
239        DeterministicCborValue::Bytes(bytes) => encode_bytes(bytes, output),
240        DeterministicCborValue::Array(values) => {
241            let child_depth = descend(depth)?;
242            ensure_container_entries(values.len())?;
243            write_header(MT_ARRAY, len_as_u64(values.len())?, output)?;
244            for child in values {
245                encode_value(child, output, child_depth)?;
246            }
247            Ok(())
248        }
249        DeterministicCborValue::Map(entries) => {
250            let child_depth = descend(depth)?;
251            ensure_container_entries(entries.len())?;
252            let mut decorated = decorated_map_entries(entries)?;
253            decorated.sort_by(compare_decorated_keys);
254            reject_duplicate_decorated_keys(&decorated)?;
255
256            write_header(MT_MAP, len_as_u64(decorated.len())?, output)?;
257            for decorated_entry in decorated {
258                extend_bytes(output, &decorated_entry.encoded_key)?;
259                encode_value(decorated_entry.entry.value(), output, child_depth)?;
260            }
261            Ok(())
262        }
263    }
264}
265
266fn encode_key(
267    key: &DeterministicCborMapKey,
268    output: &mut Vec<u8>,
269) -> Result<(), DeterministicCborError> {
270    match key {
271        DeterministicCborMapKey::Integer(integer) => encode_integer(integer, output),
272        DeterministicCborMapKey::Text(text) => encode_text(text, output),
273    }
274}
275
276fn encode_integer(
277    integer: &DeterministicCborInteger,
278    output: &mut Vec<u8>,
279) -> Result<(), DeterministicCborError> {
280    match integer {
281        DeterministicCborInteger::Unsigned(value) => write_header(MT_UINT, *value, output),
282        DeterministicCborInteger::Negative(value) => {
283            write_header(MT_NEGINT, negative_argument(value.value())?, output)
284        }
285    }
286}
287
288fn encode_text(text: &str, output: &mut Vec<u8>) -> Result<(), DeterministicCborError> {
289    let bytes = text.as_bytes();
290    write_header(MT_STRING, len_as_u64(bytes.len())?, output)?;
291    extend_bytes(output, bytes)
292}
293
294fn encode_bytes(bytes: &[u8], output: &mut Vec<u8>) -> Result<(), DeterministicCborError> {
295    write_header(MT_BYTES, len_as_u64(bytes.len())?, output)?;
296    extend_bytes(output, bytes)
297}
298
299fn negative_argument(value: i64) -> Result<u64, DeterministicCborError> {
300    let argument = (-1_i128)
301        .checked_sub(i128::from(value))
302        .ok_or(DeterministicCborError::OffsetOverflow)?;
303    u64::try_from(argument).map_err(|_| DeterministicCborError::NegativeIntegerOutOfRange)
304}
305
306fn len_as_u64(len: usize) -> Result<u64, DeterministicCborError> {
307    u64::try_from(len).map_err(|_| DeterministicCborError::LengthTooLarge)
308}
309
310fn header_len(value: u64) -> Result<usize, DeterministicCborError> {
311    if value < 24 {
312        Ok(1)
313    } else if value < 0x100 {
314        Ok(2)
315    } else if value < 0x1_0000 {
316        Ok(3)
317    } else if value < 0x1_0000_0000 {
318        Ok(5)
319    } else {
320        Ok(9)
321    }
322}
323
324fn write_header(
325    major_type: u8,
326    value: u64,
327    output: &mut Vec<u8>,
328) -> Result<(), DeterministicCborError> {
329    let be = value.to_be_bytes();
330    let head = major_type << 5;
331    if value < 24 {
332        push_byte(output, head | be[7])
333    } else if value < 0x100 {
334        push_byte(output, head | 24)?;
335        extend_bytes(output, &be[7..8])
336    } else if value < 0x1_0000 {
337        push_byte(output, head | 25)?;
338        extend_bytes(output, &be[6..8])
339    } else if value < 0x1_0000_0000 {
340        push_byte(output, head | 26)?;
341        extend_bytes(output, &be[4..8])
342    } else {
343        push_byte(output, head | 27)?;
344        extend_bytes(output, &be)
345    }
346}
347
348fn push_byte(output: &mut Vec<u8>, byte: u8) -> Result<(), DeterministicCborError> {
349    let next_len = checked_add(output.len(), 1)?;
350    if next_len > MAX_DETERMINISTIC_CBOR_OUTPUT_LEN {
351        return Err(DeterministicCborError::OutputTooLarge);
352    }
353    output.push(byte);
354    Ok(())
355}
356
357fn extend_bytes(output: &mut Vec<u8>, bytes: &[u8]) -> Result<(), DeterministicCborError> {
358    let next_len = checked_add(output.len(), bytes.len())?;
359    if next_len > MAX_DETERMINISTIC_CBOR_OUTPUT_LEN {
360        return Err(DeterministicCborError::OutputTooLarge);
361    }
362    output.extend_from_slice(bytes);
363    Ok(())
364}
365
366fn descend(depth: usize) -> Result<usize, DeterministicCborError> {
367    let next = checked_add(depth, 1)?;
368    if next > MAX_DETERMINISTIC_CBOR_NESTING_DEPTH {
369        return Err(DeterministicCborError::DepthExceeded);
370    }
371    Ok(next)
372}
373
374fn ensure_container_entries(entries: usize) -> Result<(), DeterministicCborError> {
375    if entries > MAX_DETERMINISTIC_CBOR_CONTAINER_ENTRIES {
376        return Err(DeterministicCborError::ContainerEntriesExceeded);
377    }
378    Ok(())
379}
380
381fn checked_add(left: usize, right: usize) -> Result<usize, DeterministicCborError> {
382    left.checked_add(right)
383        .ok_or(DeterministicCborError::OffsetOverflow)
384}
385
386impl Drop for DecoratedMapEntry<'_> {
387    fn drop(&mut self) {
388        self.encoded_key.zeroize();
389    }
390}
codec_cbor/encode_deterministic_cbor.rs

codec_cbor/
encode_deterministic_cbor.rs
