base_x/
encoder.rs

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

base_x/
encoder.rs
