didbot_data/
encoding.rs

1//! Base32 and base64, in the two exact dialects atproto uses.
2//!
3//! Both are strict, because the one property this whole crate exists to hold
4//! is that a value has exactly one encoding. Each refuses padding, and each
5//! refuses a final character whose unused low bits are set, which would
6//! decode to the same bytes and re-encode to a different string.
7//!
8//! * base32, lowercase, no padding, RFC 4648 alphabet. This is multibase `b`,
9//!   which is the only string form atproto permits for a CID.
10//! * base64, standard alphabet (`+` and `/`, not the URL-safe pair), no
11//!   padding. This is the `$bytes` representation in the JSON form of the
12//!   data model, and the `base64` crate's `STANDARD_NO_PAD` engine, which
13//!   refuses both.
14
15use base64::engine::general_purpose::STANDARD_NO_PAD;
16use base64::Engine as _;
17
18/// Why a string is not valid lowercase unpadded base32.
19#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
20pub enum DecodeError {
21    /// A character outside the alphabet, including `=`: padding is refused
22    /// rather than tolerated, because the protocol specifies unpadded and a
23    /// padded string is a second encoding of the same bytes.
24    #[error("invalid character {0:?}")]
25    InvalidCharacter(char),
26    /// A length that no whole number of bytes can produce, such as a single
27    /// leftover character. The value is how many bits were left over.
28    #[error("truncated: {0} leftover bits encode no whole byte")]
29    Truncated(u32),
30    /// The final character carries bits that the decoded bytes do not use.
31    /// Decoding would silently discard them and re-encoding would produce a
32    /// different string, so it is refused.
33    #[error("the final character has {0} non-zero unused bits")]
34    UnusedBits(u32),
35}
36
37/// The lowercase RFC 4648 base32 alphabet, which is multibase `b`.
38const BASE32: &[u8; 32] = b"abcdefghijklmnopqrstuvwxyz234567";
39
40/// Decodes a bit-packed string in `alphabet`, `bits` bits per character,
41/// under both strictness rules: no padding, and no set bits beyond the last
42/// whole byte.
43fn decode(text: &str, alphabet: &[u8], bits: u32) -> Result<Vec<u8>, DecodeError> {
44    let mut out = Vec::with_capacity(text.len() * bits as usize / 8);
45    let mut buffer: u32 = 0;
46    let mut held: u32 = 0;
47    for ch in text.chars() {
48        let value = alphabet
49            .iter()
50            .position(|c| char::from(*c) == ch)
51            .ok_or(DecodeError::InvalidCharacter(ch))?;
52        buffer = (buffer << bits) | value as u32;
53        held += bits;
54        if held >= 8 {
55            held -= 8;
56            out.push((buffer >> held) as u8);
57        }
58    }
59    // What is left in `buffer` is the tail of the last character. It must be
60    // zero, and there must not be enough of it to have been a whole byte.
61    if held >= bits {
62        return Err(DecodeError::Truncated(held));
63    }
64    let leftover = buffer & ((1 << held) - 1);
65    if leftover != 0 {
66        return Err(DecodeError::UnusedBits(leftover.count_ones()));
67    }
68    Ok(out)
69}
70
71/// Encodes bytes bit-packed into `alphabet`, `bits` bits per character.
72fn encode(bytes: &[u8], alphabet: &[u8], bits: u32) -> String {
73    let mut out = String::with_capacity(bytes.len() * 8 / bits as usize + 1);
74    let mut buffer: u32 = 0;
75    let mut held: u32 = 0;
76    for byte in bytes {
77        buffer = (buffer << 8) | u32::from(*byte);
78        held += 8;
79        while held >= bits {
80            held -= bits;
81            out.push(alphabet[((buffer >> held) & ((1 << bits) - 1)) as usize] as char);
82        }
83    }
84    if held > 0 {
85        let index = (buffer << (bits - held)) & ((1 << bits) - 1);
86        out.push(alphabet[index as usize] as char);
87    }
88    out
89}
90
91/// Decodes lowercase unpadded base32.
92pub fn base32_decode(text: &str) -> Result<Vec<u8>, DecodeError> {
93    decode(text, BASE32, 5)
94}
95
96/// Encodes lowercase unpadded base32.
97pub fn base32_encode(bytes: &[u8]) -> String {
98    encode(bytes, BASE32, 5)
99}
100
101/// Decodes standard unpadded base64.
102pub fn base64_decode(text: &str) -> Result<Vec<u8>, base64::DecodeError> {
103    STANDARD_NO_PAD.decode(text)
104}
105
106/// Encodes standard unpadded base64.
107pub fn base64_encode(bytes: &[u8]) -> String {
108    STANDARD_NO_PAD.encode(bytes)
109}
110
111#[cfg(test)]
112mod tests {
113    use super::*;
114
115    #[test]
116    fn base64_round_trips_every_tail_length() {
117        for len in 0..8usize {
118            let bytes: Vec<u8> = (0..len)
119                .map(|i| (i as u8).wrapping_mul(37).wrapping_add(9))
120                .collect();
121            let text = base64_encode(&bytes);
122            assert!(!text.contains('='), "{text:?} is padded");
123            assert_eq!(base64_decode(&text), Ok(bytes));
124        }
125    }
126
127    #[test]
128    fn base32_round_trips_every_tail_length() {
129        for len in 0..8usize {
130            let bytes: Vec<u8> = (0..len)
131                .map(|i| (i as u8).wrapping_mul(53).wrapping_add(3))
132                .collect();
133            let text = base32_encode(&bytes);
134            assert_eq!(base32_decode(&text), Ok(bytes));
135        }
136    }
137
138    #[test]
139    fn padding_is_refused() {
140        assert_eq!(
141            base64_decode("YWJjZA=="),
142            Err(base64::DecodeError::InvalidPadding)
143        );
144    }
145
146    #[test]
147    fn a_set_bit_beyond_the_last_byte_is_refused() {
148        // "QQ" decodes to one byte and leaves four bits; "QR" sets one of
149        // them. A lenient decoder returns the same byte for both, which is
150        // two strings for one value.
151        assert_eq!(base64_decode("QQ"), Ok(vec![0x41]));
152        assert_eq!(
153            base64_decode("QR"),
154            Err(base64::DecodeError::InvalidLastSymbol(1, b'R'))
155        );
156    }
157
158    #[test]
159    fn a_lone_trailing_character_encodes_no_byte() {
160        assert_eq!(
161            base64_decode("QQQQQ"),
162            Err(base64::DecodeError::InvalidLength(5))
163        );
164    }
165
166    #[test]
167    fn the_url_safe_alphabet_is_not_the_one_atproto_uses() {
168        assert_eq!(
169            base64_decode("-_"),
170            Err(base64::DecodeError::InvalidByte(0, b'-'))
171        );
172    }
173
174    /// The base32 half of the same rules, which this file decodes itself.
175    #[test]
176    fn base32_refuses_padding_and_set_unused_bits() {
177        assert_eq!(
178            base32_decode("mfrgg==="),
179            Err(DecodeError::InvalidCharacter('='))
180        );
181        // "ae" decodes to one byte and leaves two bits; "af" sets one.
182        assert_eq!(base32_decode("ae"), Ok(vec![0x01]));
183        assert_eq!(base32_decode("af"), Err(DecodeError::UnusedBits(1)));
184        assert_eq!(base32_decode("a"), Err(DecodeError::Truncated(5)));
185    }
186
187    #[test]
188    fn uppercase_base32_is_a_different_multibase() {
189        assert_eq!(
190            base32_decode("MFRGG"),
191            Err(DecodeError::InvalidCharacter('M'))
192        );
193    }
194}
didbot_data/encoding.rs

didbot_data/
encoding.rs
