base32.rs (7835B)
1 /* 2 This file is part of TALER 3 Copyright (C) 2024, 2025, 2026 Taler Systems SA 4 5 TALER is free software; you can redistribute it and/or modify it under the 6 terms of the GNU Affero General Public License as published by the Free Software 7 Foundation; either version 3, or (at your option) any later version. 8 9 TALER is distributed in the hope that it will be useful, but WITHOUT ANY 10 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR 11 A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details. 12 13 You should have received a copy of the GNU Affero General Public License along with 14 TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/> 15 */ 16 17 use std::fmt::Display; 18 19 pub const CROCKFORD_ALPHABET: &[u8] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ"; 20 21 /** Encoded bytes len of Crockford's base32 */ 22 #[inline] 23 const fn encoded_len(len: usize) -> usize { 24 (len * 8).div_ceil(5) 25 } 26 27 /** Buffer bytes len of Crockford's base32 using a batch of 8 chars */ 28 #[inline] 29 pub(crate) const fn encoded_buf_len(len: usize) -> usize { 30 (len / 5 + 1) * 8 31 } 32 33 /** Encode bytes using Crockford's base32 */ 34 pub fn encode(bytes: impl AsRef<[u8]>) -> String { 35 let bytes = bytes.as_ref(); 36 let mut buf = vec![0u8; encoded_buf_len(bytes.len())]; 37 // Batch encoded 38 encode_batch(bytes, &mut buf); 39 40 // Truncate incomplete ending chunk 41 buf.truncate(encoded_len(bytes.len())); 42 43 // SAFETY: only contains valid ASCII characters from CROCKFORD_ALPHABET 44 unsafe { std::string::String::from_utf8_unchecked(buf) } 45 } 46 47 /** Format bytes using Crockford's base32 */ 48 pub fn fmt(bytes: impl AsRef<[u8]>) -> impl Display { 49 std::fmt::from_fn(move |f| { 50 for chunk in bytes.as_ref().chunks(5) { 51 let mut out_buf = [0u8; 8]; 52 encode_chunk(chunk, &mut out_buf); 53 54 let n = encoded_len(chunk.len()); 55 // SAFETY: encode_chunk populates out_buf using CROCKFORD_ALPHABET, 56 // which consists of valid ASCII characters. 57 let s = unsafe { std::str::from_utf8_unchecked(&out_buf[..n]) }; 58 f.write_str(s)?; 59 } 60 Ok(()) 61 }) 62 } 63 64 /** Encode a chunk using Crockford's base32 */ 65 #[inline(always)] 66 pub(crate) fn encode_chunk(chunk: &[u8], encoded: &mut [u8; 8]) { 67 let mut buf = [0u8; 5]; 68 for (i, &b) in chunk.iter().enumerate() { 69 buf[i] = b; 70 } 71 encoded[0] = CROCKFORD_ALPHABET[((buf[0] & 0xF8) >> 3) as usize]; 72 encoded[1] = CROCKFORD_ALPHABET[(((buf[0] & 0x07) << 2) | ((buf[1] & 0xC0) >> 6)) as usize]; 73 encoded[2] = CROCKFORD_ALPHABET[((buf[1] & 0x3E) >> 1) as usize]; 74 encoded[3] = CROCKFORD_ALPHABET[(((buf[1] & 0x01) << 4) | ((buf[2] & 0xF0) >> 4)) as usize]; 75 encoded[4] = CROCKFORD_ALPHABET[(((buf[2] & 0x0F) << 1) | (buf[3] >> 7)) as usize]; 76 encoded[5] = CROCKFORD_ALPHABET[((buf[3] & 0x7C) >> 2) as usize]; 77 encoded[6] = CROCKFORD_ALPHABET[(((buf[3] & 0x03) << 3) | ((buf[4] & 0xE0) >> 5)) as usize]; 78 encoded[7] = CROCKFORD_ALPHABET[(buf[4] & 0x1F) as usize]; 79 } 80 81 /** Batch encode bytes using Crockford's base32 */ 82 #[inline] 83 fn encode_batch(bytes: &[u8], encoded: &mut [u8]) { 84 // Check buffer len 85 assert!(encoded.len() >= encoded_buf_len(bytes.len())); 86 87 // Encode chunks of 5B for 8 chars 88 for (chunk, encoded) in bytes.chunks(5).zip(encoded.as_chunks_mut().0) { 89 encode_chunk(chunk, encoded); 90 } 91 } 92 93 #[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)] 94 pub enum Base32Error<const N: usize> { 95 #[error("invalid Crockford's base32 format")] 96 Format, 97 #[error("invalid length expected {N} bytes got {0}")] 98 Length(usize), 99 } 100 101 /** Crockford's base32 inverse table, case insentitive and with substitution */ 102 const CROCKFORD_INV: [u8; 256] = { 103 let mut table = [255; 256]; 104 105 // Fill the canonical alphabet 106 let mut i = 0; 107 while i < CROCKFORD_ALPHABET.len() { 108 let b = CROCKFORD_ALPHABET[i]; 109 table[b as usize] = i as u8; 110 i += 1; 111 } 112 113 // Add substitution 114 table[b'O' as usize] = table[b'0' as usize]; 115 table[b'I' as usize] = table[b'1' as usize]; 116 table[b'L' as usize] = table[b'1' as usize]; 117 table[b'U' as usize] = table[b'V' as usize]; 118 119 // Make the table case insensitive 120 let mut i = 0; 121 while i < CROCKFORD_ALPHABET.len() { 122 let b = CROCKFORD_ALPHABET[i]; 123 table[b.to_ascii_lowercase() as usize] = table[b as usize]; 124 i += 1; 125 } 126 127 // Add substitution 128 table[b'o' as usize] = table[b'0' as usize]; 129 table[b'i' as usize] = table[b'1' as usize]; 130 table[b'l' as usize] = table[b'1' as usize]; 131 table[b'u' as usize] = table[b'v' as usize]; 132 133 table 134 }; 135 136 /** Decoded bytes len of Crockford's base32 */ 137 #[inline] 138 const fn decoded_len(len: usize) -> usize { 139 len * 5 / 8 140 } 141 142 /** Buffer bytes len of Crockford's base32 using a batch of 5 bytes */ 143 #[inline] 144 pub(crate) const fn decoded_buf_len(len: usize) -> usize { 145 (len / 8 + 1) * 5 146 } 147 148 /** Decode N bytes from a Crockford's base32 string */ 149 pub fn decode_static<const N: usize>(encoded: &[u8]) -> Result<[u8; N], Base32Error<N>> { 150 // Check decode length 151 let output_length = decoded_len(encoded.len()); 152 if output_length != N { 153 return Err(Base32Error::Length(output_length)); 154 } 155 156 let mut decoded = vec![0u8; decoded_buf_len(encoded.len())]; // TODO use a stack allocated buffer when supported 157 158 if !decode_batch(encoded, &mut decoded) { 159 return Err(Base32Error::Format); 160 } 161 Ok(decoded[..N].try_into().unwrap()) 162 } 163 164 /** Decode bytes from a Crockford's base32 string */ 165 pub fn decode(encoded: impl AsRef<[u8]>) -> Result<Vec<u8>, Base32Error<0>> { 166 let encoded = encoded.as_ref(); 167 let mut decoded = vec![0u8; decoded_buf_len(encoded.len())]; 168 169 if !decode_batch(encoded, &mut decoded) { 170 return Err(Base32Error::Format); 171 } 172 decoded.truncate(decoded_len(encoded.len())); 173 Ok(decoded) 174 } 175 176 /** Batch decode bytes using Crockford's base32 */ 177 #[inline] 178 fn decode_batch(encoded: &[u8], decoded: &mut [u8]) -> bool { 179 let mut invalid = false; 180 181 // Encode chunks of 8 chars for 5B 182 for (chunk, decoded) in encoded.chunks(8).zip(decoded.as_chunks_mut::<5>().0) { 183 let mut buf = [0; 8]; 184 185 // Lookup chunk 186 for (i, &b) in chunk.iter().enumerate() { 187 buf[i] = CROCKFORD_INV[b as usize]; 188 } 189 190 // Check chunk validity 191 invalid |= buf.contains(&255); 192 193 // Decode chunk 194 decoded[0] = (buf[0] << 3) | (buf[1] >> 2); 195 decoded[1] = (buf[1] << 6) | (buf[2] << 1) | (buf[3] >> 4); 196 decoded[2] = (buf[3] << 4) | (buf[4] >> 1); 197 decoded[3] = (buf[4] << 7) | (buf[5] << 2) | (buf[6] >> 3); 198 decoded[4] = (buf[6] << 5) | buf[7]; 199 } 200 201 !invalid 202 } 203 204 #[cfg(test)] 205 mod test { 206 use crate::encoding::base32::{Base32Error, decode, encode, fmt}; 207 208 #[test] 209 fn base32() { 210 // RFC test vectors 211 for (decoded, encoded) in [ 212 ("", ""), 213 ("f", "CR"), 214 ("fo", "CSQG"), 215 ("foo", "CSQPY"), 216 ("foob", "CSQPYRG"), 217 ("fooba", "CSQPYRK1"), 218 ("foobar", "CSQPYRK1E8"), 219 ] { 220 assert_eq!(encode(decoded.as_bytes()), encoded); 221 assert_eq!(fmt(decoded).to_string(), encoded); 222 assert_eq!(decode(encoded.as_bytes()).unwrap(), decoded.as_bytes()); 223 } 224 225 // Crockford allows case-insensitive decoding 226 assert_eq!(decode(b"oilu").unwrap(), decode(b"OILU").unwrap()); 227 228 // Crockford remaps ambiguous characters on decode 229 assert_eq!(decode(b"OILU").unwrap(), decode(b"011V").unwrap()); 230 231 // Invalid characters 232 assert_eq!(decode(b"C!"), Err(Base32Error::Format)); 233 assert_eq!(decode(b"C\x00R"), Err(Base32Error::Format)); 234 } 235 }