codec_cbor/
decode_deterministic_cbor.rs

1// SPDX-FileCopyrightText: 2026 ReallyMe LLC
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5use crate::{
6    deterministic::{try_string_copy, try_vec_with_capacity},
7    DeterministicCborError, DeterministicCborInteger, DeterministicCborMapEntry,
8    DeterministicCborMapKey, DeterministicCborValue,
9    MAX_DETERMINISTIC_CBOR_AGGREGATE_BYTE_STRING_BYTES,
10    MAX_DETERMINISTIC_CBOR_AGGREGATE_TEXT_BYTES, MAX_DETERMINISTIC_CBOR_CONTAINER_ENTRIES,
11    MAX_DETERMINISTIC_CBOR_INPUT_LEN, MAX_DETERMINISTIC_CBOR_NESTING_DEPTH,
12    MAX_DETERMINISTIC_CBOR_NODES,
13};
14use std::cmp::Ordering;
15use std::str;
16
17const MT_UINT: u8 = 0;
18const MT_NEGINT: u8 = 1;
19const MT_BYTES: u8 = 2;
20const MT_STRING: u8 = 3;
21const MT_ARRAY: u8 = 4;
22const MT_MAP: u8 = 5;
23const MT_TAG: u8 = 6;
24const MT_SIMPLE: u8 = 7;
25const SIMPLE_FALSE: u64 = 20;
26const SIMPLE_TRUE: u64 = 21;
27const SIMPLE_NULL: u64 = 22;
28const MIN_ELEMENT_ENCODED_LEN: usize = 1;
29
30/// Decode deterministic generic-CBOR bytes into the supported semantic value.
31///
32/// The decoder is strict: non-minimal integer/length encodings, indefinite
33/// lengths, unsupported major types, duplicate keys, out-of-order keys, invalid
34/// UTF-8, trailing bytes, and limit violations all fail closed.
35pub fn decode_deterministic_cbor(
36    bytes: &[u8],
37) -> Result<DeterministicCborValue, DeterministicCborError> {
38    if bytes.len() > MAX_DETERMINISTIC_CBOR_INPUT_LEN {
39        return Err(DeterministicCborError::InputTooLarge);
40    }
41    let mut limits = DecodeLimits::default();
42    let (value, offset) = decode_value(bytes, 0, 0, &mut limits)?;
43    if offset != bytes.len() {
44        return Err(DeterministicCborError::TrailingBytes);
45    }
46    Ok(value)
47}
48
49#[derive(Default)]
50struct DecodeLimits {
51    nodes: usize,
52    pending_nodes: usize,
53    aggregate_text_bytes: usize,
54    aggregate_byte_string_bytes: usize,
55}
56
57impl DecodeLimits {
58    fn add_node(&mut self) -> Result<(), DeterministicCborError> {
59        if self.nodes != 0 {
60            self.pending_nodes = self
61                .pending_nodes
62                .checked_sub(1)
63                .ok_or(DeterministicCborError::NodeLimitExceeded)?;
64        }
65        self.nodes = checked_add(self.nodes, 1)?;
66        if self.nodes > MAX_DETERMINISTIC_CBOR_NODES {
67            return Err(DeterministicCborError::NodeLimitExceeded);
68        }
69        Ok(())
70    }
71
72    fn reserve_children(&mut self, count: usize) -> Result<(), DeterministicCborError> {
73        let pending = checked_add(self.pending_nodes, count)?;
74        let declared_total = checked_add(self.nodes, pending)?;
75        if declared_total > MAX_DETERMINISTIC_CBOR_NODES {
76            return Err(DeterministicCborError::NodeLimitExceeded);
77        }
78        self.pending_nodes = pending;
79        Ok(())
80    }
81
82    fn add_text_bytes(&mut self, len: usize) -> Result<(), DeterministicCborError> {
83        self.aggregate_text_bytes = checked_add(self.aggregate_text_bytes, len)?;
84        if self.aggregate_text_bytes > MAX_DETERMINISTIC_CBOR_AGGREGATE_TEXT_BYTES {
85            return Err(DeterministicCborError::AggregateTextBytesExceeded);
86        }
87        Ok(())
88    }
89
90    fn add_byte_string_bytes(&mut self, len: usize) -> Result<(), DeterministicCborError> {
91        self.aggregate_byte_string_bytes = checked_add(self.aggregate_byte_string_bytes, len)?;
92        if self.aggregate_byte_string_bytes > MAX_DETERMINISTIC_CBOR_AGGREGATE_BYTE_STRING_BYTES {
93            return Err(DeterministicCborError::AggregateByteStringBytesExceeded);
94        }
95        Ok(())
96    }
97}
98
99fn decode_value(
100    bytes: &[u8],
101    offset: usize,
102    depth: usize,
103    limits: &mut DecodeLimits,
104) -> Result<(DeterministicCborValue, usize), DeterministicCborError> {
105    limits.add_node()?;
106    let (major, argument, mut offset) = read_head(bytes, offset)?;
107
108    match major {
109        MT_UINT => Ok((
110            DeterministicCborValue::Integer(DeterministicCborInteger::unsigned(argument)),
111            offset,
112        )),
113        MT_NEGINT => Ok((
114            DeterministicCborValue::Integer(DeterministicCborInteger::negative(negative_value(
115                argument,
116            )?)?),
117            offset,
118        )),
119        MT_BYTES => {
120            let (value, next) = extract_bytes(bytes, offset, argument, limits)?;
121            Ok((DeterministicCborValue::Bytes(value), next))
122        }
123        MT_STRING => {
124            let (value, next) = extract_string(bytes, offset, argument, limits)?;
125            Ok((DeterministicCborValue::Text(value), next))
126        }
127        MT_ARRAY => {
128            let child_depth = descend(depth)?;
129            let item_count = container_count(argument)?;
130            bounded_capacity(item_count, bytes.len(), offset, MIN_ELEMENT_ENCODED_LEN)?;
131            limits.reserve_children(item_count)?;
132            // The declared count has already been bounded both semantically
133            // and against the remaining input. Exact allocation prevents Vec
134            // growth from abandoning earlier identity-bearing owners in
135            // allocator blocks that the final owner cannot wipe.
136            let mut values = try_vec_with_capacity(item_count)?;
137            for _ in 0..item_count {
138                let (value, next) = decode_value(bytes, offset, child_depth, limits)?;
139                values.push(value);
140                offset = next;
141            }
142            Ok((DeterministicCborValue::Array(values), offset))
143        }
144        MT_MAP => {
145            let child_depth = descend(depth)?;
146            let entry_count = container_count(argument)?;
147            let min_entry_len = checked_mul(MIN_ELEMENT_ENCODED_LEN, 2)?;
148            bounded_capacity(entry_count, bytes.len(), offset, min_entry_len)?;
149            limits.reserve_children(checked_mul(entry_count, 2)?)?;
150            let mut entries = try_vec_with_capacity(entry_count)?;
151            let mut previous_key_range: Option<(usize, usize)> = None;
152
153            for _ in 0..entry_count {
154                let key_start = offset;
155                let (key, key_end) = decode_key(bytes, offset, limits)?;
156                if let Some((previous_start, previous_end)) = previous_key_range {
157                    let previous_key = checked_slice(bytes, previous_start, previous_end)?;
158                    let current_key = checked_slice(bytes, key_start, key_end)?;
159                    match compare_encoded_keys(previous_key, current_key) {
160                        Ordering::Less => {}
161                        Ordering::Equal => return Err(DeterministicCborError::DuplicateMapKey),
162                        Ordering::Greater => {
163                            return Err(DeterministicCborError::MapKeysOutOfOrder);
164                        }
165                    }
166                }
167                previous_key_range = Some((key_start, key_end));
168                offset = key_end;
169
170                let (value, next) = decode_value(bytes, offset, child_depth, limits)?;
171                entries.push(DeterministicCborMapEntry::new(key, value));
172                offset = next;
173            }
174            Ok((DeterministicCborValue::Map(entries), offset))
175        }
176        MT_SIMPLE => match argument {
177            SIMPLE_FALSE => Ok((DeterministicCborValue::Bool(false), offset)),
178            SIMPLE_TRUE => Ok((DeterministicCborValue::Bool(true), offset)),
179            SIMPLE_NULL => Ok((DeterministicCborValue::Null, offset)),
180            _ => Err(DeterministicCborError::UnsupportedSimpleValue),
181        },
182        _ => Err(DeterministicCborError::UnsupportedMajorType),
183    }
184}
185
186fn decode_key(
187    bytes: &[u8],
188    offset: usize,
189    limits: &mut DecodeLimits,
190) -> Result<(DeterministicCborMapKey, usize), DeterministicCborError> {
191    limits.add_node()?;
192    let (major, argument, offset) = read_head(bytes, offset)?;
193    match major {
194        MT_UINT => Ok((
195            DeterministicCborMapKey::Integer(DeterministicCborInteger::unsigned(argument)),
196            offset,
197        )),
198        MT_NEGINT => Ok((
199            DeterministicCborMapKey::Integer(DeterministicCborInteger::negative(negative_value(
200                argument,
201            )?)?),
202            offset,
203        )),
204        MT_STRING => {
205            let (value, next) = extract_string(bytes, offset, argument, limits)?;
206            Ok((DeterministicCborMapKey::text(value), next))
207        }
208        _ => Err(DeterministicCborError::UnsupportedMapKeyType),
209    }
210}
211
212fn read_head(bytes: &[u8], offset: usize) -> Result<(u8, u64, usize), DeterministicCborError> {
213    if offset >= bytes.len() {
214        return Err(DeterministicCborError::UnexpectedEnd);
215    }
216    let first = *bytes
217        .get(offset)
218        .ok_or(DeterministicCborError::UnexpectedEnd)?;
219    let next_offset = checked_add(offset, 1)?;
220    let major = first >> 5;
221    let additional = first & 0x1f;
222    // Tags and floating-point/simple extensions are outside this closed
223    // profile. Reject them from the initial byte alone so float payload bits
224    // are never misinterpreted as an integer argument and misclassified as a
225    // canonical-integer failure.
226    if major == MT_TAG {
227        return Err(DeterministicCborError::UnsupportedMajorType);
228    }
229    if major == MT_SIMPLE && additional >= 24 {
230        return match additional {
231            24..=27 => Err(DeterministicCborError::UnsupportedSimpleValue),
232            _ => Err(DeterministicCborError::UnsupportedAdditionalInfo),
233        };
234    }
235    let (argument, after_argument) = read_argument(bytes, next_offset, additional)?;
236    Ok((major, argument, after_argument))
237}
238
239fn read_argument(
240    bytes: &[u8],
241    offset: usize,
242    additional: u8,
243) -> Result<(u64, usize), DeterministicCborError> {
244    match additional {
245        value @ 0..=23 => Ok((u64::from(value), offset)),
246        24 => {
247            let end = checked_end(offset, 1)?;
248            let value = u64::from(
249                *bytes
250                    .get(offset)
251                    .ok_or(DeterministicCborError::TruncatedArgument)?,
252            );
253            if value < 24 {
254                return Err(DeterministicCborError::NonCanonicalInteger);
255            }
256            Ok((value, end))
257        }
258        25 => {
259            let end = checked_end(offset, 2)?;
260            let encoded = checked_argument_slice(bytes, offset, end)?;
261            let value = u16::from_be_bytes(
262                <[u8; 2]>::try_from(encoded)
263                    .map_err(|_| DeterministicCborError::TruncatedArgument)?,
264            );
265            if value < 0x100 {
266                return Err(DeterministicCborError::NonCanonicalInteger);
267            }
268            Ok((u64::from(value), end))
269        }
270        26 => {
271            let end = checked_end(offset, 4)?;
272            let encoded = checked_argument_slice(bytes, offset, end)?;
273            let value = u32::from_be_bytes(
274                <[u8; 4]>::try_from(encoded)
275                    .map_err(|_| DeterministicCborError::TruncatedArgument)?,
276            );
277            if value < 0x1_0000 {
278                return Err(DeterministicCborError::NonCanonicalInteger);
279            }
280            Ok((u64::from(value), end))
281        }
282        27 => {
283            let end = checked_end(offset, 8)?;
284            let encoded = checked_argument_slice(bytes, offset, end)?;
285            let value = u64::from_be_bytes(
286                <[u8; 8]>::try_from(encoded)
287                    .map_err(|_| DeterministicCborError::TruncatedArgument)?,
288            );
289            if value < 0x1_0000_0000 {
290                return Err(DeterministicCborError::NonCanonicalInteger);
291            }
292            Ok((value, end))
293        }
294        _ => Err(DeterministicCborError::UnsupportedAdditionalInfo),
295    }
296}
297
298fn extract_bytes(
299    bytes: &[u8],
300    offset: usize,
301    len: u64,
302    limits: &mut DecodeLimits,
303) -> Result<(Vec<u8>, usize), DeterministicCborError> {
304    let len = usize::try_from(len).map_err(|_| DeterministicCborError::LengthTooLarge)?;
305    limits.add_byte_string_bytes(len)?;
306    let end = checked_end(offset, len)?;
307    let encoded =
308        checked_slice(bytes, offset, end).map_err(|_| DeterministicCborError::TruncatedBytes)?;
309    let mut value = try_vec_with_capacity(len)?;
310    value.extend_from_slice(encoded);
311    Ok((value, end))
312}
313
314fn extract_string(
315    bytes: &[u8],
316    offset: usize,
317    len: u64,
318    limits: &mut DecodeLimits,
319) -> Result<(String, usize), DeterministicCborError> {
320    let len = usize::try_from(len).map_err(|_| DeterministicCborError::LengthTooLarge)?;
321    limits.add_text_bytes(len)?;
322    let end = checked_end(offset, len)?;
323    let encoded =
324        checked_slice(bytes, offset, end).map_err(|_| DeterministicCborError::TruncatedBytes)?;
325    let text =
326        try_string_copy(str::from_utf8(encoded).map_err(|_| DeterministicCborError::InvalidUtf8)?)?;
327    Ok((text, end))
328}
329
330fn negative_value(argument: u64) -> Result<i64, DeterministicCborError> {
331    let value = (-1_i128)
332        .checked_sub(i128::from(argument))
333        .ok_or(DeterministicCborError::NegativeIntegerOutOfRange)?;
334    i64::try_from(value).map_err(|_| DeterministicCborError::NegativeIntegerOutOfRange)
335}
336
337fn container_count(argument: u64) -> Result<usize, DeterministicCborError> {
338    let count = usize::try_from(argument).map_err(|_| DeterministicCborError::LengthTooLarge)?;
339    if count > MAX_DETERMINISTIC_CBOR_CONTAINER_ENTRIES {
340        return Err(DeterministicCborError::ContainerEntriesExceeded);
341    }
342    Ok(count)
343}
344
345fn bounded_capacity(
346    count: usize,
347    total_len: usize,
348    offset: usize,
349    min_element_len: usize,
350) -> Result<(), DeterministicCborError> {
351    let remaining = checked_sub(total_len, offset)?;
352    let max_possible = remaining / min_element_len.max(1);
353    if count > max_possible {
354        return Err(DeterministicCborError::ContainerLengthExceedsInput);
355    }
356    Ok(())
357}
358
359fn compare_encoded_keys(left: &[u8], right: &[u8]) -> Ordering {
360    match left.len().cmp(&right.len()) {
361        Ordering::Equal => left.cmp(right),
362        ordering => ordering,
363    }
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 checked_end(offset: usize, len: usize) -> Result<usize, DeterministicCborError> {
375    checked_add(offset, len)
376}
377
378fn checked_argument_slice(
379    bytes: &[u8],
380    start: usize,
381    end: usize,
382) -> Result<&[u8], DeterministicCborError> {
383    checked_slice(bytes, start, end).map_err(|_| DeterministicCborError::TruncatedArgument)
384}
385
386fn checked_slice(bytes: &[u8], start: usize, end: usize) -> Result<&[u8], DeterministicCborError> {
387    bytes
388        .get(start..end)
389        .ok_or(DeterministicCborError::OffsetOverflow)
390}
391
392fn checked_add(left: usize, right: usize) -> Result<usize, DeterministicCborError> {
393    left.checked_add(right)
394        .ok_or(DeterministicCborError::OffsetOverflow)
395}
396
397fn checked_sub(left: usize, right: usize) -> Result<usize, DeterministicCborError> {
398    left.checked_sub(right)
399        .ok_or(DeterministicCborError::OffsetOverflow)
400}
401
402fn checked_mul(left: usize, right: usize) -> Result<usize, DeterministicCborError> {
403    left.checked_mul(right)
404        .ok_or(DeterministicCborError::OffsetOverflow)
405}
406
407#[cfg(test)]
408mod node_limit_tests {
409    use super::{DecodeLimits, MAX_DETERMINISTIC_CBOR_NODES};
410    use crate::DeterministicCborError;
411
412    #[test]
413    fn decoder_node_guards_accept_exact_limit_and_reject_one_more() {
414        // Keep the two accounting guards independently observable. Normal
415        // decoding reserves descendants before visiting them, so an earlier
416        // reservation failure can mask a later add-node regression.
417        let mut reservation = DecodeLimits {
418            nodes: 1,
419            pending_nodes: MAX_DETERMINISTIC_CBOR_NODES - 2,
420            ..DecodeLimits::default()
421        };
422        assert!(reservation.reserve_children(1).is_ok());
423        assert_eq!(
424            reservation.reserve_children(1),
425            Err(DeterministicCborError::NodeLimitExceeded)
426        );
427
428        let mut visits = DecodeLimits {
429            nodes: MAX_DETERMINISTIC_CBOR_NODES - 1,
430            pending_nodes: 2,
431            ..DecodeLimits::default()
432        };
433        assert!(visits.add_node().is_ok());
434        assert_eq!(
435            visits.add_node(),
436            Err(DeterministicCborError::NodeLimitExceeded)
437        );
438    }
439}
codec_cbor/decode_deterministic_cbor.rs

codec_cbor/
decode_deterministic_cbor.rs
