reifydb_type/util/
base58.rs

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

reifydb_type/util/
base58.rs
