base58/
lib.rs

1//! Base58-to-text encoding
2//!
3//! Based on https://github.com/trezor/trezor-crypto/blob/master/base58.c
4//! commit hash: c6e7d37
5//! works only up to 128 bytes
6#![no_std]
7
8#[macro_use]
9extern crate alloc;
10
11use alloc::vec::Vec;
12use alloc::string::String;
13
14const ALPHABET: &'static [u8] = b"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
15
16const B58_DIGITS_MAP: &'static [i8] = &[
17	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
18	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
19	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
20	-1, 0, 1, 2, 3, 4, 5, 6, 7, 8,-1,-1,-1,-1,-1,-1,
21	-1, 9,10,11,12,13,14,15,16,-1,17,18,19,20,21,-1,
22	22,23,24,25,26,27,28,29,30,31,32,-1,-1,-1,-1,-1,
23	-1,33,34,35,36,37,38,39,40,41,42,43,-1,44,45,46,
24	47,48,49,50,51,52,53,54,55,56,57,-1,-1,-1,-1,-1,
25];
26
27/// Errors that can occur when decoding base58 encoded string.
28#[derive(Debug, PartialEq)]
29pub enum FromBase58Error {
30	/// The input contained a character which is not a part of the base58 format.
31	InvalidBase58Character(char, usize),
32	/// The input had invalid length.
33	InvalidBase58Length,
34}
35
36/// A trait for converting a value to base58 encoded string.
37pub trait ToBase58 {
38	/// Converts a value of `self` to a base58 value, returning the owned string.
39	fn to_base58(&self) -> String;
40}
41
42/// A trait for converting base58 encoded values.
43pub trait FromBase58 {
44	/// Convert a value of `self`, interpreted as base58 encoded data, into an owned vector of bytes, returning a vector.
45	fn from_base58(&self) -> Result<Vec<u8>, FromBase58Error>;
46}
47
48impl ToBase58 for [u8] {
49	fn to_base58(&self) -> String {
50		let zcount = self.iter().take_while(|x| **x == 0).count();
51		let size = (self.len() - zcount) * 138 / 100 + 1;
52		let mut buffer = vec![0u8; size];
53
54		let mut i = zcount;
55		let mut high = size - 1;
56
57		while i < self.len() {
58			let mut carry = self[i] as u32;
59			let mut j = size - 1;
60
61			while j > high || carry != 0 {
62				carry += 256 * buffer[j] as u32;
63				buffer[j] = (carry % 58) as u8;
64				carry /= 58;
65
66				// in original trezor implementation it was underflowing
67				if j  > 0 {
68					j -= 1;
69				}
70			}
71
72			i += 1;
73			high = j;
74		}
75
76		let mut j = buffer.iter().take_while(|x| **x == 0).count();
77
78		let mut result = String::new();
79		for _ in 0..zcount {
80			result.push('1');
81		}
82
83		while j < size {
84			result.push(ALPHABET[buffer[j] as usize] as char);
85			j += 1;
86		}
87
88		result
89	}
90}
91
92impl FromBase58 for str {
93	fn from_base58(&self) -> Result<Vec<u8>, FromBase58Error> {
94		let mut bin = [0u8; 132];
95		let mut out = [0u32; (132 + 3) / 4];
96		let bytesleft = (bin.len() % 4) as u8;
97		let zeromask = match bytesleft {
98			0 => 0u32,
99			_ => 0xffffffff << (bytesleft * 8),
100		};
101
102		let zcount = self.chars().take_while(|x| *x == '1').count();
103		let mut i = zcount;
104		let b58: Vec<u8> = self.bytes().collect();
105
106		while i < self.len() {
107			if (b58[i] & 0x80) != 0 {
108				// High-bit set on invalid digit
109				return Err(FromBase58Error::InvalidBase58Character(b58[i] as char, i));
110			}
111
112			if B58_DIGITS_MAP[b58[i] as usize] == -1 {
113				// // Invalid base58 digit
114				return Err(FromBase58Error::InvalidBase58Character(b58[i] as char, i));
115			}
116
117			let mut c = B58_DIGITS_MAP[b58[i] as usize] as u64;
118			let mut j = out.len();
119			while j != 0 {
120				j -= 1;
121				let t = out[j] as u64 * 58 + c;
122				c = (t & 0x3f00000000) >> 32;
123				out[j] = (t & 0xffffffff) as u32;
124			}
125
126			if c != 0 {
127				// Output number too big (carry to the next int32)
128				return Err(FromBase58Error::InvalidBase58Length);
129			}
130
131			if (out[0] & zeromask) != 0 {
132				// Output number too big (last int32 filled too far)
133				return Err(FromBase58Error::InvalidBase58Length);
134			}
135
136			i += 1;
137		}
138
139		let mut i = 1;
140		let mut j = 0;
141
142		bin[0] = match bytesleft {
143			3 => ((out[0] & 0xff0000) >> 16) as u8,
144			2 => ((out[0] & 0xff00) >> 8) as u8,
145			1 => {
146				j = 1;
147				(out[0] & 0xff) as u8
148			},
149			_ => {
150				i = 0;
151				bin[0]
152			}
153		};
154
155		while j < out.len() {
156			bin[i] = ((out[j] >> 0x18) & 0xff) as u8;
157			bin[i + 1] = ((out[j] >> 0x10) & 0xff) as u8;
158			bin[i + 2] = ((out[j] >> 8) & 0xff) as u8;
159			bin[i + 3] = ((out[j] >> 0) & 0xff) as u8;
160			i += 4;
161			j += 1;
162		}
163
164		let leading_zeros = bin.iter().take_while(|x| **x == 0).count();
165		Ok(bin[leading_zeros - zcount..].to_vec())
166	}
167}
168
169#[cfg(test)]
170mod tests {
171	use super::{ToBase58, FromBase58};
172
173	#[test]
174	fn test_from_base58_basic() {
175		assert_eq!("".from_base58().unwrap(), b"");
176		assert_eq!("Z".from_base58().unwrap(), &[32]);
177		assert_eq!("n".from_base58().unwrap(), &[45]);
178		assert_eq!("q".from_base58().unwrap(), &[48]);
179		assert_eq!("r".from_base58().unwrap(), &[49]);
180		assert_eq!("z".from_base58().unwrap(), &[57]);
181		assert_eq!("4SU".from_base58().unwrap(), &[45, 49]);
182		assert_eq!("4k8".from_base58().unwrap(), &[49, 49]);
183		assert_eq!("ZiCa".from_base58().unwrap(), &[97, 98, 99]);
184		assert_eq!("3mJr7AoUXx2Wqd".from_base58().unwrap(), b"1234598760");
185		assert_eq!("3yxU3u1igY8WkgtjK92fbJQCd4BZiiT1v25f".from_base58().unwrap(), b"abcdefghijklmnopqrstuvwxyz");
186	}
187
188	#[test]
189	fn test_from_base58_invalid_char() {
190		assert!("0".from_base58().is_err());
191		assert!("O".from_base58().is_err());
192		assert!("I".from_base58().is_err());
193		assert!("l".from_base58().is_err());
194		assert!("3mJr0".from_base58().is_err());
195		assert!("O3yxU".from_base58().is_err());
196		assert!("3sNI".from_base58().is_err());
197		assert!("4kl8".from_base58().is_err());
198		assert!("s!5<".from_base58().is_err());
199		assert!("t$@mX<*".from_base58().is_err());
200	}
201
202	#[test]
203	fn test_from_base58_initial_zeros() {
204		assert_eq!("1ZiCa".from_base58().unwrap(), b"\0abc");
205		assert_eq!("11ZiCa".from_base58().unwrap(), b"\0\0abc");
206		assert_eq!("111ZiCa".from_base58().unwrap(), b"\0\0\0abc");
207		assert_eq!("1111ZiCa".from_base58().unwrap(), b"\0\0\0\0abc");
208	}
209
210	#[test]
211	fn test_to_base58_basic() {
212		assert_eq!(b"".to_base58(), "");
213		assert_eq!(&[32].to_base58(), "Z");
214		assert_eq!(&[45].to_base58(), "n");
215		assert_eq!(&[48].to_base58(), "q");
216		assert_eq!(&[49].to_base58(), "r");
217		assert_eq!(&[57].to_base58(), "z");
218		assert_eq!(&[45, 49].to_base58(), "4SU");
219		assert_eq!(&[49, 49].to_base58(), "4k8");
220		assert_eq!(b"abc".to_base58(), "ZiCa");
221		assert_eq!(b"1234598760".to_base58(), "3mJr7AoUXx2Wqd");
222		assert_eq!(b"abcdefghijklmnopqrstuvwxyz".to_base58(), "3yxU3u1igY8WkgtjK92fbJQCd4BZiiT1v25f");
223	}
224
225	#[test]
226	fn test_to_base58_initial_zeros() {
227		assert_eq!(b"\0abc".to_base58(), "1ZiCa");
228		assert_eq!(b"\0\0abc".to_base58(), "11ZiCa");
229		assert_eq!(b"\0\0\0abc".to_base58(), "111ZiCa");
230		assert_eq!(b"\0\0\0\0abc".to_base58(), "1111ZiCa");
231	}
232}
base58/lib.rs

base58/
lib.rs
