reifydb_type/util/
base58.rs

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

reifydb_type/util/
base58.rs
