codec_cbor/
encode_dag_cbor.rs

1// SPDX-FileCopyrightText: 2026 ReallyMe LLC
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5use crate::{
6    CborError, CborValue, MAX_DAG_CBOR_CONTAINER_ENTRIES, MAX_DAG_CBOR_INPUT_LEN,
7    MAX_DAG_CBOR_NODES, MAX_NESTING_DEPTH,
8};
9use zeroize::Zeroizing;
10
11const MT_UINT: u8 = 0;
12const MT_NEGINT: u8 = 1;
13const MT_BYTES: u8 = 2;
14const MT_STRING: u8 = 3;
15const MT_ARRAY: u8 = 4;
16const MT_MAP: u8 = 5;
17
18/// Encode a value using canonical DAG-CBOR.
19///
20/// This encoding:
21/// - uses definite-length, shortest-form (canonical) integer headers only
22/// - orders map keys by length-first deterministic rules: shorter encoded
23///   key first, then bytewise lexical order among equal lengths
24/// - contains no floats, tags, or indefinite-length items
25/// - is deterministic and cryptographically stable, so equal values always
26///   encode to identical bytes (a prerequisite for stable content IDs)
27pub fn encode_dag_cbor(value: &CborValue) -> Result<Vec<u8>, CborError> {
28    // Run the same encoder against a counting sink first. This preserves
29    // error precedence, then reserves once so no written document buffer is
30    // ever discarded by Vec growth.
31    let mut length = 0_usize;
32    let mut nodes = 0_usize;
33    encode_value(value, &mut length, 0, &mut nodes)?;
34    let mut out = Zeroizing::new(Vec::with_capacity(length));
35    nodes = 0;
36    encode_value(value, &mut *out, 0, &mut nodes)?;
37    Ok(core::mem::take(&mut *out))
38}
39
40fn encode_value(
41    v: &CborValue,
42    out: &mut impl EncodingSink,
43    depth: usize,
44    nodes: &mut usize,
45) -> Result<(), CborError> {
46    *nodes = nodes.checked_add(1).ok_or(CborError::NodeLimitExceeded)?;
47    if *nodes > MAX_DAG_CBOR_NODES {
48        return Err(CborError::NodeLimitExceeded);
49    }
50    match v {
51        CborValue::Null => push_byte(out, 0xf6)?,
52        CborValue::Bool(false) => push_byte(out, 0xf4)?,
53        CborValue::Bool(true) => push_byte(out, 0xf5)?,
54
55        CborValue::Int(n) => {
56            if *n >= 0 {
57                write_header(MT_UINT, n.unsigned_abs(), out)?;
58            } else {
59                write_header(MT_NEGINT, n.unsigned_abs() - 1, out)?;
60            }
61        }
62
63        CborValue::Bytes(b) => {
64            write_header(MT_BYTES, len_as_u64(b.len())?, out)?;
65            extend_bytes(out, b)?;
66        }
67
68        CborValue::String(s) => {
69            let bytes = s.as_bytes();
70            write_header(MT_STRING, len_as_u64(bytes.len())?, out)?;
71            extend_bytes(out, bytes)?;
72        }
73
74        CborValue::Array(arr) => {
75            let child_depth = descend(depth)?;
76            if arr.len() > MAX_DAG_CBOR_CONTAINER_ENTRIES {
77                return Err(CborError::ContainerEntriesExceeded);
78            }
79            ensure_minimum_encoded_len(arr.len(), 1)?;
80            write_header(MT_ARRAY, len_as_u64(arr.len())?, out)?;
81            for v in arr {
82                encode_value(v, out, child_depth, nodes)?;
83            }
84        }
85
86        CborValue::Map(entries) => {
87            let child_depth = descend(depth)?;
88            if entries.len() > MAX_DAG_CBOR_CONTAINER_ENTRIES {
89                return Err(CborError::ContainerEntriesExceeded);
90            }
91            *nodes = nodes
92                .checked_add(entries.len())
93                .ok_or(CborError::NodeLimitExceeded)?;
94            if *nodes > MAX_DAG_CBOR_NODES {
95                return Err(CborError::NodeLimitExceeded);
96            }
97            ensure_minimum_encoded_len(entries.len(), 2)?;
98            // Length-first deterministic ordering sorts text keys by the
99            // length of their encoded bytes first, then by bytewise lexical
100            // order. did:me vectors rely on this exact order for stable CIDs.
101            let mut sorted: Vec<(&String, &CborValue)> =
102                entries.iter().map(|(key, value)| (key, value)).collect();
103            sorted.sort_by(|(ka, _), (kb, _)| {
104                ka.len()
105                    .cmp(&kb.len())
106                    .then_with(|| ka.as_bytes().cmp(kb.as_bytes()))
107            });
108
109            if sorted
110                .windows(2)
111                .any(|pair| pair[0].0.as_bytes() == pair[1].0.as_bytes())
112            {
113                return Err(CborError::DuplicateMapKey);
114            }
115
116            write_header(MT_MAP, len_as_u64(sorted.len())?, out)?;
117
118            for (k, v) in sorted {
119                let kb = k.as_bytes();
120                write_header(MT_STRING, len_as_u64(kb.len())?, out)?;
121                extend_bytes(out, kb)?;
122                encode_value(v, out, child_depth, nodes)?;
123            }
124        }
125    }
126    Ok(())
127}
128
129/// Widens a container length to the `u64` argument width CBOR headers use.
130///
131/// This is a widening conversion — `usize` is at most 64 bits on every
132/// supported target — so it never loses information on supported platforms,
133/// while still returning a typed error if that assumption is violated.
134fn len_as_u64(len: usize) -> Result<u64, CborError> {
135    u64::try_from(len).map_err(|_| CborError::LengthTooLarge)
136}
137
138/// Writes a CBOR head byte plus the minimal big-endian argument encoding
139/// for `value`, following canonical (shortest-form) integer rules.
140///
141/// Each branch slices the exact low-order bytes of `value.to_be_bytes()`
142/// that its range guarantees are significant, so no narrowing cast or
143/// truncation is involved.
144fn write_header(mt: u8, value: u64, out: &mut impl EncodingSink) -> Result<(), CborError> {
145    let be = value.to_be_bytes();
146    let head = mt << 5;
147    if value < 24 {
148        // The whole argument fits in the low 5 bits of the head byte.
149        push_byte(out, head | be[7])?;
150    } else if value < 0x100 {
151        push_byte(out, head | 24)?;
152        extend_bytes(out, &be[7..8])?;
153    } else if value < 0x1_0000 {
154        push_byte(out, head | 25)?;
155        extend_bytes(out, &be[6..8])?;
156    } else if value < 0x1_0000_0000 {
157        push_byte(out, head | 26)?;
158        extend_bytes(out, &be[4..8])?;
159    } else {
160        push_byte(out, head | 27)?;
161        extend_bytes(out, &be)?;
162    }
163    Ok(())
164}
165
166/// A counting sink and a byte sink share every validation and ordering step.
167/// Only the byte sink copies caller data into an owned allocation.
168trait EncodingSink {
169    fn append(&mut self, bytes: &[u8]) -> Result<(), CborError>;
170}
171
172impl EncodingSink for usize {
173    fn append(&mut self, bytes: &[u8]) -> Result<(), CborError> {
174        *self = checked_output_length(*self, bytes.len())?;
175        Ok(())
176    }
177}
178
179impl EncodingSink for Vec<u8> {
180    fn append(&mut self, bytes: &[u8]) -> Result<(), CborError> {
181        checked_output_length(self.len(), bytes.len())?;
182        self.extend_from_slice(bytes);
183        Ok(())
184    }
185}
186
187fn checked_output_length(length: usize, additional: usize) -> Result<usize, CborError> {
188    let next = length
189        .checked_add(additional)
190        .ok_or(CborError::OffsetOverflow)?;
191    if next > MAX_DAG_CBOR_INPUT_LEN {
192        return Err(CborError::OutputTooLarge);
193    }
194    Ok(next)
195}
196
197fn push_byte(out: &mut impl EncodingSink, byte: u8) -> Result<(), CborError> {
198    out.append(&[byte])
199}
200
201fn extend_bytes(out: &mut impl EncodingSink, bytes: &[u8]) -> Result<(), CborError> {
202    out.append(bytes)
203}
204
205fn descend(depth: usize) -> Result<usize, CborError> {
206    let next = depth.checked_add(1).ok_or(CborError::OffsetOverflow)?;
207    if next > MAX_NESTING_DEPTH {
208        return Err(CborError::DepthExceeded);
209    }
210    Ok(next)
211}
212
213fn ensure_minimum_encoded_len(count: usize, min_element_len: usize) -> Result<(), CborError> {
214    let minimum = count
215        .checked_mul(min_element_len)
216        .ok_or(CborError::OffsetOverflow)?;
217    if minimum > MAX_DAG_CBOR_INPUT_LEN {
218        return Err(CborError::OutputTooLarge);
219    }
220    Ok(())
221}
codec_cbor/encode_dag_cbor.rs

codec_cbor/
encode_dag_cbor.rs
