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

David Laight
2025-11-14T09:14:58Z

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;