diff options
| author | Kuan-Wei Chiu <visitorckw@gmail.com> | 2025-11-14 14:01:07 +0800 |
|---|---|---|
| committer | Andrew Morton <akpm@linux-foundation.org> | 2025-11-20 14:03:44 -0800 |
| commit | c4eb7ad32eab13ba64cc452c6f43d518b63f5e03 (patch) | |
| tree | 3f7b0ab394c72fc7e425156f48e63d3fc1b6fcb9 /lib/base64.c | |
| parent | f1e2ca801c54dfc09d6a5540207cec25e8d43f6f (diff) | |
| download | tip-c4eb7ad32eab13ba64cc452c6f43d518b63f5e03.tar.gz | |
lib/base64: optimize base64_decode() with reverse lookup tables
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)
[akpm@linux-foundation.org: fix kernedoc]
Link: https://lkml.kernel.org/r/20251114060107.89026-1-409411716@gms.tku.edu.tw
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>
Cc: Christoph Hellwig <hch@lst.de>
Cc: Eric Biggers <ebiggers@kernel.org>
Cc: Ilya Dryomov <idryomov@gmail.com>
Cc: Jaegeuk Kim <jaegeuk@kernel.org>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: Keith Busch <kbusch@kernel.org>
Cc: Sagi Grimberg <sagi@grimberg.me>
Cc: "Theodore Y. Ts'o" <tytso@mit.edu>
Cc: Viacheslav Dubeyko <Slava.Dubeyko@ibm.com>
Cc: Xiubo Li <xiubli@redhat.com>
Cc: Yu-Sheng Huang <home7438072@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Diffstat (limited to 'lib/base64.c')
| -rw-r--r-- | lib/base64.c | 52 |
1 files changed, 48 insertions, 4 deletions
diff --git a/lib/base64.c b/lib/base64.c index a7c20a8e8e9874..2d0b775def64b7 100644 --- a/lib/base64.c +++ b/lib/base64.c @@ -21,6 +21,50 @@ 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 +128,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 +140,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; |