A fast base58 implementation for Rust, built for Solana's public keys and
signatures. It's no_std, has no dependencies, and only touches the heap for
input longer than one Solana packet.
58 isn't a power of two, so base58 can't split input into bit groups the way
base64 does. The textbook method, which bs58 uses, treats the input as one
big number and divides all of it by 58 for every character it writes.
Most Solana data is a 32-byte key or a 64-byte signature, and at a known size that work can be precomputed. Following Firedancer, each 32-bit word of input is multiplied by a fixed table of its value in base 58^5. The sum is a set of limbs holding five digits each, which only need carrying and splitting. There's no long division. The vector code then carries every limb at once instead of one after another:
| target | encode | decode |
|---|---|---|
| aarch64 | the alphabet through one four-register table lookup | characters through the same lookup, inverted |
| x86-64 with AVX-512 VBMI | keys and signatures entirely in registers | the AVX2 kernels, which were never slower |
| x86-64 with AVX2 | keys and signatures entirely in registers, the alphabet as a compare chain | characters through a per-window shuffle |
| anything else | portable | portable |
The path is picked at runtime by asking the processor, because Agave builds
with x86-64-v2, which has no AVX2, so a crate that picks SIMD at compile time
runs scalar in a validator. The routing comes from measurements: Zen 4 runs
AVX-512 in two halves, so it gets the AVX2 key encoder, which is 15% faster
there.
On x86 under Agave's flags, that's 2 to 5x faster than five8. On chain there
are no vectors, and the portable code still uses 40 to 50% fewer compute units
than five8, which the Solana SDK uses to print addresses: 744 CU per
msg!("{}", pubkey) instead of 1,231. BENCHMARKS.md has the
numbers, how to reproduce them, and four ways a benchmark of this crate can
mislead you.
[dependencies]
tape-base58 = "0.2"
# in an on-chain program:
# tape-base58 = { version = "0.2", default-features = false }// Fixed widths, no allocation.
encode_32(&[u8; 32], &mut [u8; MAX_ENCODED_32]) -> usize
encode_64(&[u8; 64], &mut [u8; MAX_ENCODED_64]) -> usize
decode_32(&[u8], &mut [u8; 32]) -> Result<(), DecodeError>
decode_64(&[u8], &mut [u8; 64]) -> Result<(), DecodeError>
// Any length up to MAX_ACCEPTED_LEN, past which a call is refused.
encode(&[u8], &mut [u8]) -> Result<usize, EncodeError>
decode(&[u8], &mut [u8]) -> Result<usize, DecodeError>
encoded_len(usize) -> usize
decoded_len(usize) -> usize
// Four inputs at a time, sharing one walk of the table.
encode_32_batch(&[[u8; 32]], &mut [u8], &mut [usize]) -> Result<(), EncodeError>
encode_64_batch(&[[u8; 64]], &mut [u8], &mut [usize]) -> Result<(), EncodeError>
decode_32_batch(&[&[u8]], &mut [[u8; 32]]) -> Result<(), BatchError>
decode_64_batch(&[&[u8]], &mut [[u8; 64]]) -> Result<(), BatchError>Everything that isn't a key or a signature goes through encode and decode,
which fold in a whole 64-byte block at a time. The value is reduced once per
block instead of once per word, and the multiply that does the rest has no
serial chain. The fold works in place inside a small window, which keeps the
stack frame small enough for SBF. Below 128 bytes there's no whole block, and
dividing the value down is cheaper anyway. On an M4, a 1232-byte transaction
encodes in 7.3 µs, against 1.41 ms for bs58.
The conversion is still quadratic, so input is capped at MAX_ACCEPTED_LEN,
which stops one call from being made arbitrarily expensive by its length. With
the default alloc feature the cap is 4096 bytes, with heap scratch past one
packet. Without it the cap is one packet (1232 bytes) and nothing allocates,
which is what an on-chain program wants.
The conversion algorithm, base 58^5 limbs with fixed tables, comes from
Firedancer's fd_base58 (Apache-2.0). No Firedancer code is included. The
tables are generated by tools/gen_tables.py. Kevin Heavey's five8 informed
the shape of the fixed-size functions. See NOTICE.