reifydb_type/util/
base58.rs

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

reifydb_type/util/
base58.rs
