On Thu, 11 Sep 2025 15:32:04 +0800
Guan-Chun Wu <409411716@xxxxxxxxxxxxxx> wrote:
> From: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
>
> The base64 decoder previously relied on strchr() to locate each
> character in the base64 table. In the worst case, this requires
> scanning all 64 entries, and even with bitwise tricks or word-sized
> comparisons, still needs up to 8 checks.
>
> Introduce a small helper function that maps input characters directly
> to their position in the base64 table. This reduces the maximum number
> of comparisons to 5, improving decoding efficiency while keeping the
> logic straightforward.
>
> Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
> over 1000 runs, tested with KUnit):
>
> Decode:
> - 64B input: avg ~1530ns -> ~126ns (~12x faster)
> - 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
>
> Signed-off-by: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
> Co-developed-by: Guan-Chun Wu <409411716@xxxxxxxxxxxxxx>
> Signed-off-by: Guan-Chun Wu <409411716@xxxxxxxxxxxxxx>
> ---
> lib/base64.c | 17 ++++++++++++++++-
> 1 file changed, 16 insertions(+), 1 deletion(-)
>
> diff --git a/lib/base64.c b/lib/base64.c
> index b736a7a43..9416bded2 100644
> --- a/lib/base64.c
> +++ b/lib/base64.c
> @@ -18,6 +18,21 @@
> static const char base64_table[65] =
> "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
>
> +static inline const char *find_chr(const char *base64_table, char ch)
> +{
> + if ('A' <= ch && ch <= 'Z')
> + return base64_table + ch - 'A';
> + if ('a' <= ch && ch <= 'z')
> + return base64_table + 26 + ch - 'a';
> + if ('0' <= ch && ch <= '9')
> + return base64_table + 26 * 2 + ch - '0';
> + if (ch == base64_table[26 * 2 + 10])
> + return base64_table + 26 * 2 + 10;
> + if (ch == base64_table[26 * 2 + 10 + 1])
> + return base64_table + 26 * 2 + 10 + 1;
> + return NULL;
> +}
That's still going to be really horrible with random data.
You'll get a lot of mispredicted branch penalties.
I think they are about 20 clocks each on my Zen-5.
A 256 byte lookup table might be better.
However if you assume ascii then 'ch' can be split 3:5 bits and
the top three used to determine the valid values for the low bits
(probably using shifts of constants rather than actual arrays).
So apart from the outlying '+' and '/' (and IIRC there is a variant
that uses different characters) which can be picked up in the error
path; it ought to be possible to code with no conditionals at all.
To late at night to write (and test) an implementation.
David
> +
> /**
> * base64_encode() - base64-encode some binary data
> * @src: the binary data to encode
> @@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
> u8 *bp = dst;
>
> for (i = 0; i < srclen; i++) {
> - const char *p = strchr(base64_table, src[i]);
> + const char *p = find_chr(base64_table, src[i]);
>
> if (src[i] == '=') {
> ac = (ac << 6);
