It turns out I can greatly improve the performance further!
Before:
$ time yes | head -c65535 | src/basenc --base58 -w0 >file.enc
real 0m1.533s
After:
$ time yes | head -c65535 | src/basenc --base58 -w0 >file.enc
real 0m0.018s
I was reading the GMP source out of interest (go open source),
and noticed that it supported base conversion internally,
which we could just call and then map the alternate character set after.
A prelim patch to do that is attached.
cheers,
Padraig
From de2352a99b1a220fb768d2cab9cbafd153ade520 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?P=C3=A1draig=20Brady?= <p...@draigbrady.com>
Date: Fri, 8 Aug 2025 17:52:55 +0100
Subject: [PATCH] basenc: base58: do base conversion within gmp
Before:
$ time yes | head -c65535 | src/basenc --base58 -w0 >file.enc
real 0m1.533s
After:
$ time yes | head -c65535 | src/basenc --base58 -w0 >file.enc
real 0m0.018s
* src/basenc.c (do_encode): Base convert with mpz_get_str(),
and then map from the GMP character set.
---
src/basenc.c | 58 ++++++++++++++++++++++++++++++----------------------
1 file changed, 34 insertions(+), 24 deletions(-)
diff --git a/src/basenc.c b/src/basenc.c
index cb2dbdb93..f823fe703 100644
--- a/src/basenc.c
+++ b/src/basenc.c
@@ -1067,8 +1067,28 @@ base2msbf_decode_ctx (struct base_decode_context *ctx,
return true;
}
-static char const base58_alphabet[58] _GL_ATTRIBUTE_NONSTRING =
- "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
+/* Map from GMP base (62):
+ "0123456789 ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuv";
+ to Base 58:
+ "123456789A BCDEFGHJKLMNPQRSTUVWXYZabc defghijkmnopqrstuvwxyz"; */
+static signed char const gmp_to_base58[256] = {
+ -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','2','3','4','5','6','7','8','9','A',-1, -1, -1, -1, -1, -1,
+ -1, 'B','C','D','E','F','G','H','J','K','L','M','N','P','Q','R',
+ 'S','T','U','V','W','X','Y','Z','a','b','c',-1, -1, -1, -1, -1,
+ -1, 'd','e','f','g','h','i','j','k','m','n','o','p','q','r','s',
+ 'y','u','v','w','x','y','z',-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, -1, -1, -1, -1
+};
static signed char const base58_to_int[256] = {
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
@@ -1148,36 +1168,26 @@ base58_encode (char const* data, size_t data_len,
while (leading_zeros < data_len && data[leading_zeros] == 0)
leading_zeros++;
- /* Init GMP integer from binary (base 256) data. */
+ memset (out, '1', leading_zeros);
+ char *p = out + leading_zeros;
+
+ /* Use GMP to convert from base 256 to base 58. */
mpz_t num;
mpz_init (num);
mpz_import (num, data_len, 1, 1, 0, 0, data);
- char *ptr = out + *outlen; /* Start just beyond end. */
-
- /* Convert to base 58 by repeatedly dividing by 58. */
- mpz_t quotient, remainder;
- mpz_init (quotient);
- mpz_init (remainder);
- while (mpz_cmp_ui (num, 0) > 0)
+ if (mpz_cmp_ui (num, 0) > 0)
{
- mpz_fdiv_qr_ui (quotient, remainder, num, 58);
- unsigned long rem_val = mpz_get_ui (remainder);
- *(--ptr) = base58_alphabet[rem_val];
- mpz_set (num, quotient);
+ char *gmp_b58 = mpz_get_str (NULL, 58, num);
+ char *g = gmp_b58;
+ while (*g)
+ *p++ = gmp_to_base58[to_uchar (*g++)];
+ free (gmp_b58); /* TODO translate in place. */
}
- /* Account for leading zeros. */
- ptr -= leading_zeros;
- memset (ptr, '1', leading_zeros);
-
- /* Prepare return. */
- *outlen -= (ptr - out);
- memmove (out, ptr, *outlen);
-
mpz_clear (num);
- mpz_clear (quotient);
- mpz_clear (remainder);
+
+ *outlen = p - out;
return;
}
--
2.50.0
