base_x/
encoder.rs

1#[cfg(not(feature = "std"))]
2use alloc::vec::Vec;
3use crate::bigint::BigUint;
4
5pub(crate) fn encode<T>(alpha: &[T], input: &[u8]) -> Vec<T>
6where
7    T: Copy,
8{
9    if input.is_empty() {
10        return Vec::new();
11    }
12
13    let base = alpha.len() as u32;
14
15    assert!(base >= 2, "Alphabet must have at least 2 characters");
16
17    // Convert the input byte array to a BigUint
18    let mut big = BigUint::from_bytes_be(input);
19    let mut out = Vec::with_capacity(input.len());
20
21    // Find the highest power of `base` that fits in `u32`
22    let big_pow = 32 / (32 - base.leading_zeros());
23    let big_base = base.pow(big_pow);
24
25    'fast: loop {
26        // Instead of diving by `base`, we divide by the `big_base`,
27        // giving us a bigger remainder that we can further subdivide
28        // by the original `base`. This greatly (in case of base58 it's
29        // a factor of 5) reduces the amount of divisions that need to
30        // be done on BigUint, delegating the hard work to regular `u32`
31        // operations, which are blazing fast.
32        let mut big_rem = big.div_mod(big_base);
33
34        if big.is_zero() {
35            loop {
36                let (result, remainder) = (big_rem / base, big_rem % base);
37                out.push(alpha[remainder as usize]);
38                big_rem = result;
39
40                if big_rem == 0 {
41                    break 'fast; // teehee
42                }
43            }
44        } else {
45            for _ in 0..big_pow {
46                let (result, remainder) = (big_rem / base, big_rem % base);
47                out.push(alpha[remainder as usize]);
48                big_rem = result;
49            }
50        }
51    }
52
53    let leaders = input
54        .iter()
55        .take(input.len() - 1)
56        .take_while(|i| **i == 0)
57        .map(|_| alpha[0]);
58
59    out.extend(leaders);
60    out
61}
base_x/encoder.rs

base_x/
encoder.rs
