Re: [PATCH v5 2/6] lib/base64: Optimize base64_decode() with reverse lookup tables

[David Laight <david.laight.linux@gmail.com>]

On Fri, 14 Nov 2025 14:01:07 +0800
Guan-Chun Wu <409411716@gms.tku.edu.tw> wrote:

> From: Kuan-Wei Chiu <visitorckw@gmail.com>
> 
> Replace the use of strchr() in base64_decode() with precomputed reverse
> lookup tables for each variant. This avoids repeated string scans and
> improves performance. Use -1 in the tables to mark invalid characters.
> 
> Decode:
>   64B   ~1530ns  ->  ~80ns    (~19.1x)
>   1KB  ~27726ns  -> ~1239ns   (~22.4x)
> 
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> Co-developed-by: Guan-Chun Wu <409411716@gms.tku.edu.tw>
> Signed-off-by: Guan-Chun Wu <409411716@gms.tku.edu.tw>

Reviewed-by: David Laight <david.laight.linux@gmail.com>

> ---
>  lib/base64.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++----
>  1 file changed, 47 insertions(+), 4 deletions(-)
> 
> diff --git a/lib/base64.c b/lib/base64.c
> index a7c20a8e8e98..9d1074bb821c 100644
> --- a/lib/base64.c
> +++ b/lib/base64.c
> @@ -21,6 +21,49 @@ static const char base64_tables[][65] = {
>  	[BASE64_IMAP] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+,",
>  };
>  
> +/**
> + * Initialize the base64 reverse mapping for a single character
> + * This macro maps a character to its corresponding base64 value,
> + * returning -1 if the character is invalid.
> + * char 'A'-'Z' maps to 0-25, 'a'-'z' maps to 26-51, '0'-'9' maps to 52-61,
> + * ch_62 maps to 62, ch_63 maps to 63, and other characters return -1
> + */
> +#define INIT_1(v, ch_62, ch_63) \
> +	[v] = (v) >= 'A' && (v) <= 'Z' ? (v) - 'A' \
> +		: (v) >= 'a' && (v) <= 'z' ? (v) - 'a' + 26 \
> +		: (v) >= '0' && (v) <= '9' ? (v) - '0' + 52 \
> +		: (v) == (ch_62) ? 62 : (v) == (ch_63) ? 63 : -1
> +/**
> + * Recursive macros to generate multiple Base64 reverse mapping table entries.
> + * Each macro generates a sequence of entries in the lookup table:
> + * INIT_2 generates 2 entries, INIT_4 generates 4, INIT_8 generates 8, and so on up to INIT_32.
> + */
> +#define INIT_2(v, ...) INIT_1(v, __VA_ARGS__), INIT_1((v) + 1, __VA_ARGS__)
> +#define INIT_4(v, ...) INIT_2(v, __VA_ARGS__), INIT_2((v) + 2, __VA_ARGS__)
> +#define INIT_8(v, ...) INIT_4(v, __VA_ARGS__), INIT_4((v) + 4, __VA_ARGS__)
> +#define INIT_16(v, ...) INIT_8(v, __VA_ARGS__), INIT_8((v) + 8, __VA_ARGS__)
> +#define INIT_32(v, ...) INIT_16(v, __VA_ARGS__), INIT_16((v) + 16, __VA_ARGS__)
> +
> +#define BASE64_REV_INIT(ch_62, ch_63) { \
> +	[0 ... 0x1f] = -1, \
> +	INIT_32(0x20, ch_62, ch_63), \
> +	INIT_32(0x40, ch_62, ch_63), \
> +	INIT_32(0x60, ch_62, ch_63), \
> +	[0x80 ... 0xff] = -1 }
> +
> +static const s8 base64_rev_maps[][256] = {
> +	[BASE64_STD] = BASE64_REV_INIT('+', '/'),
> +	[BASE64_URLSAFE] = BASE64_REV_INIT('-', '_'),
> +	[BASE64_IMAP] = BASE64_REV_INIT('+', ',')
> +};
> +
> +#undef BASE64_REV_INIT
> +#undef INIT_32
> +#undef INIT_16
> +#undef INIT_8
> +#undef INIT_4
> +#undef INIT_2
> +#undef INIT_1
>  /**
>   * base64_encode() - Base64-encode some binary data
>   * @src: the binary data to encode
> @@ -84,10 +127,9 @@ int base64_decode(const char *src, int srclen, u8 *dst, bool padding, enum base6
>  	int bits = 0;
>  	int i;
>  	u8 *bp = dst;
> -	const char *base64_table = base64_tables[variant];
> +	s8 ch;
>  
>  	for (i = 0; i < srclen; i++) {
> -		const char *p = strchr(base64_table, src[i]);
>  		if (padding) {
>  			if (src[i] == '=') {
>  				ac = (ac << 6);
> @@ -97,9 +139,10 @@ int base64_decode(const char *src, int srclen, u8 *dst, bool padding, enum base6
>  				continue;
>  			}
>  		}
> -		if (p == NULL || src[i] == 0)
> +		ch = base64_rev_maps[variant][(u8)src[i]];
> +		if (ch == -1)
>  			return -1;
> -		ac = (ac << 6) | (p - base64_table);
> +		ac = (ac << 6) | ch;
>  		bits += 6;
>  		if (bits >= 8) {
>  			bits -= 8;