reifydb_type/util/
base58.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright (c) 2025 ReifyDB
3
4use std::{error, fmt, iter};
5const BASE58_CHARS: &[u8] = b"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
6
7/// Encode bytes to base58 string
8pub fn encode(input: &[u8]) -> String {
9	if input.is_empty() {
10		return String::new();
11	}
12
13	// Count leading zeros
14	let leading_zeros = input.iter().take_while(|&&b| b == 0).count();
15
16	// Convert to base58 using big-integer arithmetic
17	// We work with a mutable copy of the input as a big-endian number
18	let mut bytes = input.to_vec();
19	let mut result = Vec::new();
20
21	while !bytes.iter().all(|&b| b == 0) {
22		let mut remainder = 0u32;
23		for byte in bytes.iter_mut() {
24			let value = (remainder << 8) | (*byte as u32);
25			*byte = (value / 58) as u8;
26			remainder = value % 58;
27		}
28		result.push(BASE58_CHARS[remainder as usize]);
29	}
30
31	// Add leading '1's for each leading zero byte
32	result.extend(iter::repeat_n(b'1', leading_zeros));
33
34	// Reverse and convert to string
35	result.reverse();
36	String::from_utf8(result).unwrap()
37}
38
39/// Decode base58 string to bytes
40pub fn decode(input: &str) -> Result<Vec<u8>, DecodeError> {
41	if input.is_empty() {
42		return Ok(Vec::new());
43	}
44
45	// Count leading '1's (they represent leading zero bytes)
46	let leading_ones = input.chars().take_while(|&c| c == '1').count();
47
48	// Convert from base58 to bytes
49	let mut bytes: Vec<u8> = Vec::new();
50
51	for ch in input.chars() {
52		let value = char_to_value(ch)?;
53
54		// Multiply existing bytes by 58 and add the new value
55		let mut carry = value as u32;
56		for byte in bytes.iter_mut().rev() {
57			let val = (*byte as u32) * 58 + carry;
58			*byte = (val & 0xFF) as u8;
59			carry = val >> 8;
60		}
61
62		while carry > 0 {
63			bytes.insert(0, (carry & 0xFF) as u8);
64			carry >>= 8;
65		}
66	}
67
68	// Prepend leading zero bytes
69	let mut result = vec![0u8; leading_ones];
70	result.extend(bytes);
71
72	Ok(result)
73}
74
75fn char_to_value(ch: char) -> Result<u8, DecodeError> {
76	let byte = ch as u8;
77	BASE58_CHARS.iter().position(|&b| b == byte).map(|pos| pos as u8).ok_or(DecodeError::InvalidCharacter(ch))
78}
79
80#[derive(Debug)]
81pub enum DecodeError {
82	InvalidCharacter(char),
83}
84
85impl fmt::Display for DecodeError {
86	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
87		match self {
88			DecodeError::InvalidCharacter(ch) => {
89				write!(f, "Invalid base58 character: '{}'", ch)
90			}
91		}
92	}
93}
94
95impl error::Error for DecodeError {}
96
97#[cfg(test)]
98pub mod tests {
99	use super::*;
100
101	#[test]
102	fn test_encode_empty() {
103		assert_eq!(encode(b""), "");
104	}
105
106	#[test]
107	fn test_encode_hello() {
108		// "Hello" -> "9Ajdvzr"
109		assert_eq!(encode(b"Hello"), "9Ajdvzr");
110	}
111
112	#[test]
113	fn test_encode_hello_world() {
114		// "Hello, World!" -> "72k1xXWG59fYdzSNoA"
115		assert_eq!(encode(b"Hello, World!"), "72k1xXWG59fYdzSNoA");
116	}
117
118	#[test]
119	fn test_encode_leading_zeros() {
120		// Leading zero bytes become leading '1's
121		assert_eq!(encode(&[0, 0, 1]), "112");
122		assert_eq!(encode(&[0, 0, 0]), "111");
123	}
124
125	#[test]
126	fn test_decode_empty() {
127		assert_eq!(decode("").unwrap(), b"");
128	}
129
130	#[test]
131	fn test_decode_hello() {
132		assert_eq!(decode("9Ajdvzr").unwrap(), b"Hello");
133	}
134
135	#[test]
136	fn test_decode_hello_world() {
137		assert_eq!(decode("72k1xXWG59fYdzSNoA").unwrap(), b"Hello, World!");
138	}
139
140	#[test]
141	fn test_decode_leading_ones() {
142		assert_eq!(decode("112").unwrap(), &[0, 0, 1]);
143		assert_eq!(decode("111").unwrap(), &[0, 0, 0]);
144	}
145
146	#[test]
147	fn test_roundtrip() {
148		let data = b"Hello, World! \x00\x01\x02\xFF";
149		let encoded = encode(data);
150		let decoded = decode(&encoded).unwrap();
151		assert_eq!(decoded, data);
152	}
153
154	#[test]
155	fn test_roundtrip_binary() {
156		let data = &[0xde, 0xad, 0xbe, 0xef];
157		let encoded = encode(data);
158		let decoded = decode(&encoded).unwrap();
159		assert_eq!(decoded, data);
160	}
161
162	#[test]
163	fn test_invalid_character() {
164		// '0', 'O', 'I', 'l' are not in base58 alphabet
165		assert!(decode("0").is_err());
166		assert!(decode("O").is_err());
167		assert!(decode("I").is_err());
168		assert!(decode("l").is_err());
169		assert!(decode("invalid!").is_err());
170	}
171}
reifydb_type/util/base58.rs

reifydb_type/util/
base58.rs
