use crate::{
CborError, CborValue, MAX_DAG_CBOR_CONTAINER_ENTRIES, MAX_DAG_CBOR_INPUT_LEN,
MAX_DAG_CBOR_NODES, MAX_NESTING_DEPTH,
};
use zeroize::Zeroizing;
const MT_UINT: u8 = 0;
const MT_NEGINT: u8 = 1;
const MT_BYTES: u8 = 2;
const MT_STRING: u8 = 3;
const MT_ARRAY: u8 = 4;
const MT_MAP: u8 = 5;
pub fn encode_dag_cbor(value: &CborValue) -> Result<Vec<u8>, CborError> {
let mut length = 0_usize;
let mut nodes = 0_usize;
encode_value(value, &mut length, 0, &mut nodes)?;
let mut out = Zeroizing::new(Vec::with_capacity(length));
nodes = 0;
encode_value(value, &mut *out, 0, &mut nodes)?;
Ok(core::mem::take(&mut *out))
}
fn encode_value(
v: &CborValue,
out: &mut impl EncodingSink,
depth: usize,
nodes: &mut usize,
) -> Result<(), CborError> {
encode_value_with(v, out, depth, nodes, encode_value)
}
fn encode_value_with<S: EncodingSink>(
v: &CborValue,
out: &mut S,
depth: usize,
nodes: &mut usize,
mut encode_child: impl FnMut(&CborValue, &mut S, usize, &mut usize) -> Result<(), CborError>,
) -> Result<(), CborError> {
count_node(nodes)?;
match v {
CborValue::Null => push_byte(out, 0xf6)?,
CborValue::Bool(bit) => encode_bool(*bit, out)?,
CborValue::Int(n) => {
if *n >= 0 {
write_header(MT_UINT, n.unsigned_abs(), out)?;
} else {
write_header(MT_NEGINT, n.unsigned_abs() - 1, out)?;
}
}
CborValue::Bytes(b) => {
write_header(MT_BYTES, len_as_u64(b.len())?, out)?;
extend_bytes(out, b)?;
}
CborValue::String(s) => {
let bytes = s.as_bytes();
write_header(MT_STRING, len_as_u64(bytes.len())?, out)?;
extend_bytes(out, bytes)?;
}
CborValue::Array(arr) => {
let child_depth = descend(depth)?;
if arr.len() > MAX_DAG_CBOR_CONTAINER_ENTRIES {
return Err(CborError::ContainerEntriesExceeded);
}
ensure_minimum_encoded_len(arr.len(), 1)?;
write_header(MT_ARRAY, len_as_u64(arr.len())?, out)?;
for v in arr {
encode_child(v, out, child_depth, nodes)?;
}
}
CborValue::Map(entries) => {
let child_depth = descend(depth)?;
if entries.len() > MAX_DAG_CBOR_CONTAINER_ENTRIES {
return Err(CborError::ContainerEntriesExceeded);
}
*nodes = nodes
.checked_add(entries.len())
.ok_or(CborError::NodeLimitExceeded)?;
if *nodes > MAX_DAG_CBOR_NODES {
return Err(CborError::NodeLimitExceeded);
}
ensure_minimum_encoded_len(entries.len(), 2)?;
let sorted = sort_map_entries(entries)?;
write_map_entries(&sorted, out, child_depth, nodes, encode_child)?;
}
}
Ok(())
}
fn sort_map_entries(
entries: &[(String, CborValue)],
) -> Result<Vec<(&String, &CborValue)>, CborError> {
let mut sorted: Vec<(&String, &CborValue)> =
entries.iter().map(|(key, value)| (key, value)).collect();
sorted.sort_by(|(left, _), (right, _)| {
left.len()
.cmp(&right.len())
.then_with(|| left.as_bytes().cmp(right.as_bytes()))
});
if sorted
.windows(2)
.any(|pair| pair[0].0.as_bytes() == pair[1].0.as_bytes())
{
return Err(CborError::DuplicateMapKey);
}
Ok(sorted)
}
fn write_map_entries<S: EncodingSink>(
sorted: &[(&String, &CborValue)],
out: &mut S,
child_depth: usize,
nodes: &mut usize,
mut encode_child: impl FnMut(&CborValue, &mut S, usize, &mut usize) -> Result<(), CborError>,
) -> Result<(), CborError> {
write_header(MT_MAP, len_as_u64(sorted.len())?, out)?;
for &(key, value) in sorted {
let bytes = key.as_bytes();
write_header(MT_STRING, len_as_u64(bytes.len())?, out)?;
extend_bytes(out, bytes)?;
encode_child(value, out, child_depth, nodes)?;
}
Ok(())
}
fn count_node(nodes: &mut usize) -> Result<(), CborError> {
*nodes = nodes.checked_add(1).ok_or(CborError::NodeLimitExceeded)?;
if *nodes > MAX_DAG_CBOR_NODES {
return Err(CborError::NodeLimitExceeded);
}
Ok(())
}
fn encode_bool(bit: bool, out: &mut impl EncodingSink) -> Result<(), CborError> {
push_byte(out, if bit { 0xf5 } else { 0xf4 })
}
fn len_as_u64(len: usize) -> Result<u64, CborError> {
u64::try_from(len).map_err(|_| CborError::LengthTooLarge)
}
fn write_header(mt: u8, value: u64, out: &mut impl EncodingSink) -> Result<(), CborError> {
let be = value.to_be_bytes();
let head = mt << 5;
if value < 24 {
push_byte(out, head | be[7])?;
} else if value < 0x100 {
push_byte(out, head | 24)?;
extend_bytes(out, &be[7..8])?;
} else if value < 0x1_0000 {
push_byte(out, head | 25)?;
extend_bytes(out, &be[6..8])?;
} else if value < 0x1_0000_0000 {
push_byte(out, head | 26)?;
extend_bytes(out, &be[4..8])?;
} else {
push_byte(out, head | 27)?;
extend_bytes(out, &be)?;
}
Ok(())
}
trait EncodingSink {
fn append(&mut self, bytes: &[u8]) -> Result<(), CborError>;
}
impl EncodingSink for usize {
fn append(&mut self, bytes: &[u8]) -> Result<(), CborError> {
*self = checked_output_length(*self, bytes.len())?;
Ok(())
}
}
impl EncodingSink for Vec<u8> {
fn append(&mut self, bytes: &[u8]) -> Result<(), CborError> {
checked_output_length(self.len(), bytes.len())?;
self.extend_from_slice(bytes);
Ok(())
}
}
fn checked_output_length(length: usize, additional: usize) -> Result<usize, CborError> {
let next = length
.checked_add(additional)
.ok_or(CborError::OffsetOverflow)?;
if next > MAX_DAG_CBOR_INPUT_LEN {
return Err(CborError::OutputTooLarge);
}
Ok(next)
}
fn push_byte(out: &mut impl EncodingSink, byte: u8) -> Result<(), CborError> {
out.append(&[byte])
}
fn extend_bytes(out: &mut impl EncodingSink, bytes: &[u8]) -> Result<(), CborError> {
out.append(bytes)
}
fn descend(depth: usize) -> Result<usize, CborError> {
let next = depth.checked_add(1).ok_or(CborError::OffsetOverflow)?;
if next > MAX_NESTING_DEPTH {
return Err(CborError::DepthExceeded);
}
Ok(next)
}
fn ensure_minimum_encoded_len(count: usize, min_element_len: usize) -> Result<(), CborError> {
let minimum = count
.checked_mul(min_element_len)
.ok_or(CborError::OffsetOverflow)?;
if minimum > MAX_DAG_CBOR_INPUT_LEN {
return Err(CborError::OutputTooLarge);
}
Ok(())
}
#[cfg(kani)]
#[path = "encode_dag_cbor_proof_tests.rs"]
mod proofs;