Faster Base58 encoding & decoding

[kzorin52]

Instead of using straightforward byte decoding and encoding, I suggest this variant on limbs (uint), which I use for quite long time in my private repos:

using System.Buffers;
using System.Buffers.Binary;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

namespace SharedCrypto.Crypto.Algorithms;

public static class FastBase58
{
    private const int Base = 58;
    private static ReadOnlySpan<char> AlphabetStr => "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
    private static readonly SearchValues<char> ValidityMap = SearchValues.Create(AlphabetStr);
    
    private const int StackAllocThresholdLimbs = 256;
    
    private static ReadOnlySpan<sbyte> Map =>
    [
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1, 0, 1, 2, 3, 4, 5, 6, 7, 8,-1,-1,-1,-1,-1,-1,
        -1, 9,10,11,12,13,14,15,16,-1,17,18,19,20,21,-1,
        22,23,24,25,26,27,28,29,30,31,32,-1,-1,-1,-1,-1,
        -1,33,34,35,36,37,38,39,40,41,42,43,-1,44,45,46,
        47,48,49,50,51,52,53,54,55,56,57,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
    ];
    
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int GetSafeByteCountForDecoding(int zeroCount, int encodedLength)
    {
        return zeroCount + (encodedLength - zeroCount + 1) * 733 / 1000 + 1;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int GetSafeCharCountForEncoding(int zeroCount, int decodedLength)
    {
        return zeroCount + (decodedLength - zeroCount) * 1000 / 733 + 1;
    }

    public static string Encode(ReadOnlySpan<byte> input)
    {
        var zeroCount = 0;
        while (zeroCount < input.Length && input[zeroCount] == 0) zeroCount++;
        
        Span<char> temp = stackalloc char[GetSafeCharCountForEncoding(zeroCount, input.Length)];
        var written = Encode(input, temp);
        
        return new string(temp.Slice(0, written));
    }

    public static byte[]? Decode(ReadOnlySpan<char> encoded)
    {
        var zeroCount = 0;
        while (zeroCount < encoded.Length && encoded[zeroCount] == 0) zeroCount++;
        
        Span<byte> temp = stackalloc byte[GetSafeByteCountForDecoding(zeroCount, encoded.Length)];
        return TryDecode(encoded, temp, out var written) ? temp[..written].ToArray() : null;
    }
    
    [SkipLocalsInit]
    public static unsafe int Encode(ReadOnlySpan<byte> input, Span<char> output)
    {
        if (input.IsEmpty) return 0;
        
        var zeroCount = 0;
        while (zeroCount < input.Length && input[zeroCount] == 0) zeroCount++;
        
        var payload = input[zeroCount..];
        if (payload.IsEmpty)
        {
            output[..zeroCount].Fill('1');
            return zeroCount;
        }
        
        var limbCount = (payload.Length + 3) / 4;
        var alignedByteSize = limbCount * 4;
        
        uint[]? pooledArray = null;
        var limbs = limbCount <= StackAllocThresholdLimbs
            ? stackalloc uint[StackAllocThresholdLimbs]
            : pooledArray = ArrayPool<uint>.Shared.Rent(limbCount);

        limbs = limbs[..limbCount];
        limbs.Clear();
        
        var limbsAsBytes = MemoryMarshal.AsBytes(limbs);
        var padding = alignedByteSize - payload.Length;
        payload.CopyTo(limbsAsBytes[padding..]);
        
        BinaryPrimitives.ReverseEndianness(limbs, limbs);
        
        var maxOutLen = zeroCount + payload.Length * 138 / 100 + 1;
        
        byte[]? pooledIndexBuf = null;
        var indexBuf = maxOutLen <= 512
            ? stackalloc byte[512]
            : pooledIndexBuf = ArrayPool<byte>.Shared.Rent(maxOutLen);

        var indexLen = 0;
        var startLimb = 0;
        
        while (startLimb < limbCount)
        {
            ulong remainder = 0;
            
            if (limbs[startLimb] == 0)
            {
                startLimb++;
                continue;
            }
            
            for (var i = startLimb; i < limbCount; i++)
            {
                var temp = (remainder << 32) | limbs[i];

                limbs[i] = (uint)(temp / Base);
                remainder = temp % Base;
            }

            indexBuf[indexLen++] = (byte)remainder;
        }
        
        if (output.Length < zeroCount + indexLen)
            throw new ArgumentException("Output buffer too small");

        output[..zeroCount].Fill('1');
        var outIdx = zeroCount;
        
        fixed (char* alphabetPtr = AlphabetStr)
        {
            for (var i = indexLen - 1; i >= 0; i--) output[outIdx++] = alphabetPtr[indexBuf[i]];
        }
        
        ReturnPool(pooledArray);
        ReturnPool(pooledIndexBuf);

        return outIdx;
    }
    
    [SkipLocalsInit]
    public static unsafe bool TryDecode(ReadOnlySpan<char> input, Span<byte> output, out int bytesWritten)
    {
        bytesWritten = 0;
        if (input.IsEmpty) return true;
        if (input.ContainsAnyExcept(ValidityMap)) return false;
        
        var zeros = 0;
        while (zeros < input.Length && input[zeros] == '1') zeros++;

        var capacityBytes = (input.Length - zeros) * 733 / 1000 + 1;
        var capacityLimbs = (capacityBytes + 3) / 4;

        uint[]? pooledLimbs = null;
        var limbs = capacityLimbs <= StackAllocThresholdLimbs
            ? stackalloc uint[StackAllocThresholdLimbs]
            : pooledLimbs = ArrayPool<uint>.Shared.Rent(capacityLimbs);
        
        limbs = limbs[..capacityLimbs];
        limbs.Clear();

        fixed (sbyte* mapPtr = Map)
        {
            for (var i = zeros; i < input.Length; i++)
            {
                int val = mapPtr[input[i]];
                
                var carry = (ulong)val;
                
                for (var j = capacityLimbs - 1; j >= 0; j--)
                {
                    var temp = (ulong)limbs[j] * Base + carry;
                    limbs[j] = (uint)temp;
                    carry = temp >> 32;
                }

                if (carry > 0)
                {
                    ReturnPool(pooledLimbs);
                    return false;
                }
            }
        }
        
        BinaryPrimitives.ReverseEndianness(limbs, limbs);
        var resultBytes = MemoryMarshal.AsBytes(limbs);

        var skip = 0;
        while (skip < resultBytes.Length && resultBytes[skip] == 0) skip++;

        var payloadLen = resultBytes.Length - skip;
        var totalLen = zeros + payloadLen;

        if (output.Length < totalLen)
        {
            ReturnPool(pooledLimbs);
            return false;
        }
        
        output[..zeros].Clear();
        
        resultBytes[skip..].CopyTo(output[zeros..]);
        bytesWritten = totalLen;

        ReturnPool(pooledLimbs);
        return true;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static void ReturnPool<T>(T[]? arr)
    {
        if (arr != null) ArrayPool<T>.Shared.Return(arr);
    }
}

This is the code, it may be a little bit dirty, little bit too unsafe, but the algorithm should be clear.
And yes, here is benchmark code:

[MemoryDiagnoser]
[AffinitizedJob(1)]
public class Base58Benchmark
{
    public static readonly byte[] Data;
    private static readonly string DataEncoded;

    static Base58Benchmark()
    {
        Data = RandomNumberGenerator.GetBytes(32);
        Data[0] = 0;
        Data[1] = 1; // to keep zeroPrefix static
        
        DataEncoded = Base58.Bitcoin.Encode(Data);
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    [Benchmark]
    public string SimpleBaseEncode()
    {
        return Base58.Bitcoin.Encode(Data);
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    [Benchmark]
    public string MyEncode()
    {
        return FastBase58.Encode(Data);
    }
    
    [MethodImpl(MethodImplOptions.NoInlining)]
    [Benchmark]
    public byte[] SimpleBaseDecode()
    {
        return Base58.Bitcoin.Decode(DataEncoded);
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    [Benchmark]
    public byte[] MyDecode()
    {
        return FastBase58.Decode(DataEncoded)!;
    }
}

And results on my machine:

BenchmarkDotNet v0.16.0-nightly.20260128.414, Linux CachyOS
AMD Ryzen Threadripper 7980X 64-Cores 2.18GHz, 1 CPU, 128 logical and 64 physical cores                                                                                                                                                                                                                            
.NET SDK 11.0.100-preview.2.26081.104                                                                                                                                                                                                                                                                              
  [Host]     : .NET 11.0.0 (11.0.0-preview.2.26081.104, 11.0.26.8204), X64 RyuJIT x86-64-v4                                                                                                                                                                                                                        
  Job-CLLEZI : .NET 11.0.0 (11.0.0-preview.2.26081.104, 11.0.26.8204), X64 RyuJIT x86-64-v4                                                                                                                                                                                                                        
                                                                                                                                                                                                                                                                                                                   
Affinity=00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001  

Method	Mean	Error	StdDev	Gen0	Allocated
SimpleBaseEncode	1,146.9 ns	7.21 ns	6.39 ns	0.0057	112 B
MyEncode	361.7 ns	3.15 ns	2.95 ns	0.0067	112 B
SimpleBaseDecode	815.2 ns	15.96 ns	14.93 ns	0.0029	56 B
MyDecode	191.7 ns	0.68 ns	0.53 ns	0.0033	56 B

So the speedup is around ~4x. Also, I suggest you using SearchValues: it's SIMDed inside

[ssg]

@kzorin52 Thanks for the suggestion! I'm trying this out to make sure that it doesn't introduce any regressions. I'm mostly concerned about extra memory allocation for "limbs" as non-allocating encoders ideally should not allocate any memory at all. ArrayPool rentals are still implicit allocations, especially with parallel workloads like web services despite that the GC overhead is reduced. Perhaps this can be introduced as a different encoder class (like MoneroBase58), or the API surface can be split into long and short buffer encoders. I'll think about it.

About your suggestion on SearchValues, I don't see a case where it can be used. Validation already happens during reverse table lookups as a side-effect?

[kzorin52]

Yeah, I didn't realize it at first. Thanks for clarifying. I'm pretty sure there is space for improvements, bcz my implementation is just a draft.
I look forward to your thoughts.

[unsafePtr]

@kzorin52 existing implemntation has an issue #83

Try this one implemntation https://github.com/unsafePtr/Base58Encoding. Already optimized