Skip to main content

hyprstream_pds/
cid.rs

1//! CIDv1 (Content IDentifier) for DAG-CBOR blocks.
2//!
3//! A CID is a self-describing content address. This crate uses **CIDv1** with
4//! the `dag-cbor` codec (0x71) and `sha2-256` multihash (0x12) — the atproto /
5//! IPLD default for repo blocks (commits, MST nodes, records).
6//!
7//! # Wire format (CIDv1)
8//!
9//! ```text
10//! <version:u8=0x01><codec:varint><multihash>
11//! ```
12//! where `<multihash> = <hash-code:varint><digest-len:varint><digest-bytes>`.
13//!
14//! # DAG-CBOR link encoding (tag 42)
15//!
16//! Inside DAG-CBOR, a CID is carried as a byte string tagged with CBOR tag 42,
17//! whose payload is a "CID specifier": a leading 0x00 (identity-multibase
18//! marker, per the [DAG-CBOR spec](https://github.com/ipld/specs/blob/master/block-layer/codecs/dag-cbor.md))
19//! followed by the raw CID bytes (version+codec+multihash). The 0x00 prefix
20//! exists so a CID can never collide with a legitimate CBOR byte string.
21
22use std::fmt;
23
24use anyhow::{anyhow, bail, Result};
25
26/// Codec code for `dag-cbor` (0x71) — used for atproto repo blocks.
27pub const CODEC_DAG_CBOR: u64 = 0x71;
28/// Codec code for `raw` (0x55) — opaque byte blocks.
29pub const CODEC_RAW: u64 = 0x55;
30
31/// Multihash code for SHA-256 (0x12) — the atproto / IPLD default.
32const MH_SHA2_256: u64 = 0x12;
33const SHA256_LEN: usize = 32;
34
35/// A CIDv1 content identifier.
36///
37/// Internally stored as a fixed-size byte buffer holding the full CID bytes
38/// (`0x01 <codec> <multihash>`), plus a length. CIDv1 with a single-byte codec
39/// varint and SHA-256 multihash is exactly 38 bytes, so a 40-byte inline buffer
40/// covers all realistic multihashes without a heap allocation. This makes
41/// [`Cid`] [`Copy`] (38-ish bytes is cheaper to copy than to refcount), which
42/// matters because CIDs flow through tree node fields, map keys, and proof
43/// steps that would otherwise drown in `.clone()` noise.
44#[derive(Clone, Copy, Eq, PartialEq, Hash)]
45pub struct Cid {
46    /// Raw CID bytes: `0x01 <codec-varint> <multihash>`.
47    bytes: [u8; Self::CAP],
48    /// Number of valid bytes in `bytes`.
49    len: u8,
50}
51
52impl Cid {
53    /// Maximum CID byte length supported (CIDv1 + dag-cbor codec + sha2-256
54    /// multihash = 38 bytes; the slack covers longer multihashes).
55    const CAP: usize = 40;
56
57    /// Compute the CIDv1 `dag-cbor` CID over `block_bytes` (SHA-256 multihash).
58    ///
59    /// This is the canonical way to address a DAG-CBOR block in atproto: the
60    /// caller hands in the already-canonical DAG-CBOR bytes (see [`crate::dag_cbor`])
61    /// and gets back the CID that identifies them.
62    pub fn from_dag_cbor(block_bytes: &[u8]) -> Self {
63        let mut bytes = Vec::with_capacity(38);
64        bytes.push(0x01); // CIDv1
65        write_uvarint(CODEC_DAG_CBOR, &mut bytes);
66        // multihash: sha2-256 code + length + digest
67        write_uvarint(MH_SHA2_256, &mut bytes);
68        write_uvarint(SHA256_LEN as u64, &mut bytes);
69        use sha2::{Digest, Sha256};
70        let digest = Sha256::digest(block_bytes);
71        bytes.extend_from_slice(&digest);
72        Cid::from_vec(bytes)
73    }
74
75    /// CIDv1 `raw` codec over arbitrary bytes (used for external git OIDs
76    /// referenced by `currentOid` when the caller has the raw blob handy).
77    pub fn from_raw(blob_bytes: &[u8]) -> Self {
78        let mut bytes = Vec::with_capacity(38);
79        bytes.push(0x01);
80        write_uvarint(CODEC_RAW, &mut bytes);
81        write_uvarint(MH_SHA2_256, &mut bytes);
82        write_uvarint(SHA256_LEN as u64, &mut bytes);
83        use sha2::{Digest, Sha256};
84        let digest = Sha256::digest(blob_bytes);
85        bytes.extend_from_slice(&digest);
86        Cid::from_vec(bytes)
87    }
88
89    /// Pack a `Vec<u8>` of CID bytes into the fixed-size inline buffer.
90    fn from_vec(bytes: Vec<u8>) -> Self {
91        let len = bytes.len();
92        assert!(
93            len <= Self::CAP,
94            "CID exceeds inline buffer: {len} > {}",
95            Self::CAP
96        );
97        let mut buf = [0u8; Self::CAP];
98        buf[..len].copy_from_slice(&bytes);
99        Cid {
100            bytes: buf,
101            len: len as u8,
102        }
103    }
104
105    /// Raw CID bytes (version + codec + multihash).
106    pub fn as_bytes(&self) -> &[u8] {
107        &self.bytes[..self.len as usize]
108    }
109
110    /// Encode as a DAG-CBOR link: the CBOR-tag-42 payload, i.e. a leading
111    /// `0x00` identity-multibase marker followed by the raw CID bytes.
112    ///
113    /// Returns the bytes that go *inside* the tag-42 byte string (the marker
114    /// plus the CID). Used by [`crate::dag_cbor`] when emitting link values.
115    pub fn to_link_bytes(&self) -> Vec<u8> {
116        let bytes = self.as_bytes();
117        let mut out = Vec::with_capacity(1 + bytes.len());
118        out.push(0x00);
119        out.extend_from_slice(bytes);
120        out
121    }
122
123    /// Parse a DAG-CBOR tag-42 payload (leading 0x00 marker + CID) back into a [`Cid`].
124    pub fn from_link_bytes(link: &[u8]) -> Result<Self> {
125        if link.is_empty() {
126            bail!("empty DAG-CBOR link payload");
127        }
128        // The first byte is the multibase identity marker (0x00); strip it.
129        if link[0] != 0x00 {
130            bail!(
131                "DAG-CBOR link payload must start with 0x00 identity marker, got 0x{:02x}",
132                link[0]
133            );
134        }
135        Self::from_bytes(&link[1..])
136    }
137
138    /// Parse raw CID bytes (version + codec + multihash).
139    pub fn from_bytes(raw: &[u8]) -> Result<Self> {
140        if raw.is_empty() {
141            bail!("empty CID bytes");
142        }
143        if raw[0] != 0x01 {
144            bail!(
145                "only CIDv1 is supported (got version byte 0x{:02x})",
146                raw[0]
147            );
148        }
149        // Validate the varints parse and the digest length matches.
150        let rest = &raw[1..];
151        let (_codec, rest) = read_uvarint(rest).ok_or_else(|| anyhow!("truncated codec varint"))?;
152        let (code, rest) = read_uvarint(rest).ok_or_else(|| anyhow!("truncated multihash code"))?;
153        let (len, rest) =
154            read_uvarint(rest).ok_or_else(|| anyhow!("truncated multihash length"))?;
155        let len = usize::try_from(len).map_err(|_| anyhow!("multihash length overflow"))?;
156        if rest.len() != len {
157            bail!(
158                "multihash length {len} does not match remaining {} bytes",
159                rest.len()
160            );
161        }
162        if code != MH_SHA2_256 {
163            bail!("only sha2-256 multihash is supported (got code {code})");
164        }
165        if raw.len() > Self::CAP {
166            bail!("CID exceeds inline buffer: {} > {}", raw.len(), Self::CAP);
167        }
168        Ok(Cid::from_vec(raw.to_vec()))
169    }
170
171    /// Base32 (lowercase, no padding) `bafy...`/`bafk...`-style encoding — the
172    /// canonical string form of a CIDv1.
173    ///
174    /// Named `encode` rather than `to_string` to avoid shadowing the
175    /// `ToString` blanket impl that `Display` would otherwise recurse through.
176    ///
177    /// This is the [CIDv1 string format](https://github.com/multiformats/multibase):
178    /// multibase prefix `b` (base32lower-nopad) followed by the base32 of the
179    /// raw CID bytes.
180    pub fn encode(&self) -> String {
181        let bytes = self.as_bytes();
182        let mut out = String::with_capacity(1 + bytes.len() * 2);
183        out.push('b');
184        out.push_str(&base32_nopad_lower(bytes));
185        out
186    }
187}
188
189impl fmt::Debug for Cid {
190    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
191        write!(f, "Cid({})", self.encode())
192    }
193}
194
195impl fmt::Display for Cid {
196    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
197        f.write_str(&self.encode())
198    }
199}
200
201impl PartialOrd for Cid {
202    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
203        Some(self.cmp(other))
204    }
205}
206impl Ord for Cid {
207    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
208        self.bytes.cmp(&other.bytes)
209    }
210}
211
212// ── varint helpers (LEB128 unsigned, RFC 7541 / multiformats) ────────────────
213
214/// Write a multiformats unsigned varint (7 bits/byte, MSB continuation).
215pub(crate) fn write_uvarint(mut val: u64, out: &mut Vec<u8>) {
216    while val >= 0x80 {
217        out.push(((val & 0x7f) as u8) | 0x80);
218        val >>= 7;
219    }
220    out.push(val as u8);
221}
222
223/// Read a multiformats unsigned varint. Returns `(value, remaining_slice)`.
224pub(crate) fn read_uvarint(input: &[u8]) -> Option<(u64, &[u8])> {
225    let mut val: u64 = 0;
226    let mut shift = 0u32;
227    for (i, &b) in input.iter().enumerate() {
228        if shift >= 64 {
229            return None; // varint too long
230        }
231        // The tenth byte contributes only the top bit of a u64. Reject
232        // payload bits which would overflow before shifting them in.
233        if shift == 63 && b & 0x7e != 0 {
234            return None;
235        }
236        val |= ((b & 0x7f) as u64) << shift;
237        if b & 0x80 == 0 {
238            // A terminating zero group after the first byte is an overlong
239            // representation (for example, `f1 00` for 0x71).
240            if i > 0 && b == 0 {
241                return None;
242            }
243            return Some((val, &input[i + 1..]));
244        }
245        shift += 7;
246    }
247    None // truncated
248}
249
250/// RFC 4648 base32, lowercase, no padding.
251fn base32_nopad_lower(bytes: &[u8]) -> String {
252    const ALPHA: &[u8; 32] = b"abcdefghijklmnopqrstuvwxyz234567";
253    let mut out = String::with_capacity((bytes.len() * 8).div_ceil(5));
254    let mut buffer: u64 = 0;
255    let mut bits: u32 = 0;
256    for &b in bytes {
257        buffer = (buffer << 8) | (b as u64);
258        bits += 8;
259        while bits >= 5 {
260            bits -= 5;
261            let idx = ((buffer >> bits) & 0x1f) as usize;
262            out.push(ALPHA[idx] as char);
263        }
264    }
265    if bits > 0 {
266        let idx = ((buffer << (5 - bits)) & 0x1f) as usize;
267        out.push(ALPHA[idx] as char);
268    }
269    out
270}
271
272#[cfg(test)]
273mod tests {
274    #![allow(
275        clippy::unwrap_used,
276        clippy::expect_used,
277        clippy::indexing_slicing,
278        clippy::panic
279    )]
280    use super::*;
281
282    #[test]
283    fn cid_is_deterministic() {
284        // Same bytes → same CID (load-bearing for MST + commit sig).
285        let a = Cid::from_dag_cbor(b"hello world");
286        let b = Cid::from_dag_cbor(b"hello world");
287        assert_eq!(a, b);
288        assert_eq!(a.as_bytes(), b.as_bytes());
289        assert_ne!(
290            Cid::from_dag_cbor(b"hello world"),
291            Cid::from_dag_cbor(b"hello earth")
292        );
293    }
294
295    #[test]
296    fn cid_round_trip_link_bytes() {
297        let cid = Cid::from_dag_cbor(b"some dag-cbor block");
298        let link = cid.to_link_bytes();
299        assert_eq!(link[0], 0x00);
300        let parsed = Cid::from_link_bytes(&link).expect("round-trip");
301        assert_eq!(cid, parsed);
302    }
303
304    #[test]
305    fn cid_round_trip_from_bytes() {
306        let cid = Cid::from_dag_cbor(b"x");
307        let parsed = Cid::from_bytes(cid.as_bytes()).expect("round-trip");
308        assert_eq!(cid, parsed);
309    }
310
311    #[test]
312    fn cid_string_starts_with_b() {
313        let cid = Cid::from_dag_cbor(b"");
314        let s = cid.encode();
315        assert!(s.starts_with('b'), "CIDv1 base32 must start with 'b': {s}");
316    }
317
318    #[test]
319    fn varint_round_trip() {
320        for val in [
321            0u64,
322            1,
323            0x7f,
324            0x80,
325            0xff,
326            0x71,
327            0x12,
328            0x4000,
329            u32::MAX as u64,
330        ] {
331            let mut buf = Vec::new();
332            write_uvarint(val, &mut buf);
333            let (parsed, rest) = read_uvarint(&buf).expect("round-trip");
334            assert_eq!(parsed, val, "varint {val}");
335            assert!(rest.is_empty(), "varint {val} had trailing bytes");
336        }
337    }
338
339    #[test]
340    fn varint_rejects_overlong_and_overflow_encodings() {
341        assert!(read_uvarint(&[0xf1, 0x00]).is_none());
342        assert!(read_uvarint(&[0x80, 0x00]).is_none());
343
344        let mut overflow = vec![0xff; 9];
345        overflow.push(0x02);
346        assert!(read_uvarint(&overflow).is_none());
347    }
348}