From f1e2ca801c54dfc09d6a5540207cec25e8d43f6f Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 14 Nov 2025 14:00:45 +0800 Subject: lib/base64: add support for multiple variants Patch series " lib/base64: add generic encoder/decoder, migrate users", v5. This series introduces a generic Base64 encoder/decoder to the kernel library, eliminating duplicated implementations and delivering significant performance improvements. The Base64 API has been extended to support multiple variants (Standard, URL-safe, and IMAP) as defined in RFC 4648 and RFC 3501. The API now takes a variant parameter and an option to control padding. As part of this series, users are migrated to the new interface while preserving their specific formats: fscrypt now uses BASE64_URLSAFE, Ceph uses BASE64_IMAP, and NVMe is updated to BASE64_STD. On the encoder side, the implementation processes input in 3-byte blocks, mapping 24 bits directly to 4 output symbols. This avoids bit-by-bit streaming and reduces loop overhead, achieving about a 2.7x speedup compared to previous implementations. On the decoder side, replace strchr() lookups with per-variant reverse tables and process input in 4-character groups. Each group is mapped to numeric values and combined into 3 bytes. Padded and unpadded forms are validated explicitly, rejecting invalid '=' usage and enforcing tail rules. This improves throughput by ~43-52x. This patch (of 6): Extend the base64 API to support multiple variants (standard, URL-safe, and IMAP) as defined in RFC 4648 and RFC 3501. The API now takes a variant parameter and an option to control padding. Update NVMe auth code to use the new interface with BASE64_STD. Link: https://lkml.kernel.org/r/20251114055829.87814-1-409411716@gms.tku.edu.tw Link: https://lkml.kernel.org/r/20251114060045.88792-1-409411716@gms.tku.edu.tw Signed-off-by: Kuan-Wei Chiu 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 Cc: Christoph Hellwig Cc: Eric Biggers Cc: Ilya Dryomov Cc: Jaegeuk Kim Cc: Jens Axboe Cc: Keith Busch Cc: Sagi Grimberg Cc: "Theodore Y. Ts'o" Cc: Viacheslav Dubeyko Cc: Xiubo Li Cc: Yu-Sheng Huang Signed-off-by: Andrew Morton --- lib/base64.c | 62 +++++++++++++++++++++++++++++++++++------------------------- 1 file changed, 36 insertions(+), 26 deletions(-) (limited to 'lib/base64.c') diff --git a/lib/base64.c b/lib/base64.c index b736a7a431c5..a7c20a8e8e98 100644 --- a/lib/base64.c +++ b/lib/base64.c @@ -1,12 +1,12 @@ // SPDX-License-Identifier: GPL-2.0 /* - * base64.c - RFC4648-compliant base64 encoding + * base64.c - Base64 with support for multiple variants * * Copyright (c) 2020 Hannes Reinecke, SUSE * * Based on the base64url routines from fs/crypto/fname.c - * (which are using the URL-safe base64 encoding), - * modified to use the standard coding table from RFC4648 section 4. + * (which are using the URL-safe Base64 encoding), + * modified to support multiple Base64 variants. */ #include @@ -15,26 +15,31 @@ #include #include -static const char base64_table[65] = - "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; +static const char base64_tables[][65] = { + [BASE64_STD] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/", + [BASE64_URLSAFE] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_", + [BASE64_IMAP] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+,", +}; /** - * base64_encode() - base64-encode some binary data + * base64_encode() - Base64-encode some binary data * @src: the binary data to encode * @srclen: the length of @src in bytes - * @dst: (output) the base64-encoded string. Not NUL-terminated. + * @dst: (output) the Base64-encoded string. Not NUL-terminated. + * @padding: whether to append '=' padding characters + * @variant: which base64 variant to use * - * Encodes data using base64 encoding, i.e. the "Base 64 Encoding" specified - * by RFC 4648, including the '='-padding. + * Encodes data using the selected Base64 variant. * - * Return: the length of the resulting base64-encoded string in bytes. + * Return: the length of the resulting Base64-encoded string in bytes. */ -int base64_encode(const u8 *src, int srclen, char *dst) +int base64_encode(const u8 *src, int srclen, char *dst, bool padding, enum base64_variant variant) { u32 ac = 0; int bits = 0; int i; char *cp = dst; + const char *base64_table = base64_tables[variant]; for (i = 0; i < srclen; i++) { ac = (ac << 8) | src[i]; @@ -48,44 +53,49 @@ int base64_encode(const u8 *src, int srclen, char *dst) *cp++ = base64_table[(ac << (6 - bits)) & 0x3f]; bits -= 6; } - while (bits < 0) { - *cp++ = '='; - bits += 2; + if (padding) { + while (bits < 0) { + *cp++ = '='; + bits += 2; + } } return cp - dst; } EXPORT_SYMBOL_GPL(base64_encode); /** - * base64_decode() - base64-decode a string + * base64_decode() - Base64-decode a string * @src: the string to decode. Doesn't need to be NUL-terminated. * @srclen: the length of @src in bytes * @dst: (output) the decoded binary data + * @padding: whether to append '=' padding characters + * @variant: which base64 variant to use * - * Decodes a string using base64 encoding, i.e. the "Base 64 Encoding" - * specified by RFC 4648, including the '='-padding. + * Decodes a string using the selected Base64 variant. * * This implementation hasn't been optimized for performance. * * Return: the length of the resulting decoded binary data in bytes, - * or -1 if the string isn't a valid base64 string. + * or -1 if the string isn't a valid Base64 string. */ -int base64_decode(const char *src, int srclen, u8 *dst) +int base64_decode(const char *src, int srclen, u8 *dst, bool padding, enum base64_variant variant) { u32 ac = 0; int bits = 0; int i; u8 *bp = dst; + const char *base64_table = base64_tables[variant]; for (i = 0; i < srclen; i++) { const char *p = strchr(base64_table, src[i]); - - if (src[i] == '=') { - ac = (ac << 6); - bits += 6; - if (bits >= 8) - bits -= 8; - continue; + if (padding) { + if (src[i] == '=') { + ac = (ac << 6); + bits += 6; + if (bits >= 8) + bits -= 8; + continue; + } } if (p == NULL || src[i] == 0) return -1; -- cgit v1.2.3 From c4eb7ad32eab13ba64cc452c6f43d518b63f5e03 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 14 Nov 2025 14:01:07 +0800 Subject: 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 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 Cc: Christoph Hellwig Cc: Eric Biggers Cc: Ilya Dryomov Cc: Jaegeuk Kim Cc: Jens Axboe Cc: Keith Busch Cc: Sagi Grimberg Cc: "Theodore Y. Ts'o" Cc: Viacheslav Dubeyko Cc: Xiubo Li Cc: Yu-Sheng Huang Signed-off-by: Andrew Morton --- lib/base64.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 48 insertions(+), 4 deletions(-) (limited to 'lib/base64.c') diff --git a/lib/base64.c b/lib/base64.c index a7c20a8e8e98..2d0b775def64 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; -- cgit v1.2.3 From 9c7d3cf94d33927b6e4e576e7090a929e7162d05 Mon Sep 17 00:00:00 2001 From: Guan-Chun Wu <409411716@gms.tku.edu.tw> Date: Fri, 14 Nov 2025 14:01:32 +0800 Subject: lib/base64: rework encode/decode for speed and stricter validation The old base64 implementation relied on a bit-accumulator loop, which was slow for larger inputs and too permissive in validation. It would accept extra '=', missing '=', or even '=' appearing in the middle of the input, allowing malformed strings to pass. This patch reworks the internals to improve performance and enforce stricter validation. Changes: - Encoder: * Process input in 3-byte blocks, mapping 24 bits into four 6-bit symbols, avoiding bit-by-bit shifting and reducing loop iterations. * Handle the final 1-2 leftover bytes explicitly and emit '=' only when requested. - Decoder: * Based on the reverse lookup tables from the previous patch, decode input in 4-character groups. * Each group is looked up directly, converted into numeric values, and combined into 3 output bytes. * Explicitly handle padded and unpadded forms: - With padding: input length must be a multiple of 4, and '=' is allowed only in the last two positions. Reject stray or early '='. - Without padding: validate tail lengths (2 or 3 chars) and require unused low bits to be zero. * Removed the bit-accumulator style loop to reduce loop iterations. Performance (x86_64, Intel Core i7-10700 @ 2.90GHz, avg over 1000 runs, KUnit): Encode: 64B ~90ns -> ~32ns (~2.8x) 1KB ~1332ns -> ~510ns (~2.6x) Decode: 64B ~1530ns -> ~35ns (~43.7x) 1KB ~27726ns -> ~530ns (~52.3x) [akpm@linux-foundation.org: remove u32 casts, per David and Guan-Chun] Link: https://lkml.kernel.org/r/20251114060132.89279-1-409411716@gms.tku.edu.tw Co-developed-by: Kuan-Wei Chiu Signed-off-by: Kuan-Wei Chiu Co-developed-by: Yu-Sheng Huang Signed-off-by: Yu-Sheng Huang Signed-off-by: Guan-Chun Wu <409411716@gms.tku.edu.tw> Reviewed-by: David Laight Cc: Christoph Hellwig Cc: Eric Biggers Cc: Ilya Dryomov Cc: Jaegeuk Kim Cc: Jens Axboe Cc: Keith Busch Cc: Sagi Grimberg Cc: "Theodore Y. Ts'o" Cc: Viacheslav Dubeyko Cc: Xiubo Li Signed-off-by: Andrew Morton --- lib/base64.c | 109 +++++++++++++++++++++++++++++++++++++---------------------- 1 file changed, 68 insertions(+), 41 deletions(-) (limited to 'lib/base64.c') diff --git a/lib/base64.c b/lib/base64.c index 2d0b775def64..41961a444028 100644 --- a/lib/base64.c +++ b/lib/base64.c @@ -80,28 +80,38 @@ static const s8 base64_rev_maps[][256] = { int base64_encode(const u8 *src, int srclen, char *dst, bool padding, enum base64_variant variant) { u32 ac = 0; - int bits = 0; - int i; char *cp = dst; const char *base64_table = base64_tables[variant]; - for (i = 0; i < srclen; i++) { - ac = (ac << 8) | src[i]; - bits += 8; - do { - bits -= 6; - *cp++ = base64_table[(ac >> bits) & 0x3f]; - } while (bits >= 6); - } - if (bits) { - *cp++ = base64_table[(ac << (6 - bits)) & 0x3f]; - bits -= 6; + while (srclen >= 3) { + ac = src[0] << 16 | src[1] << 8 | src[2]; + *cp++ = base64_table[ac >> 18]; + *cp++ = base64_table[(ac >> 12) & 0x3f]; + *cp++ = base64_table[(ac >> 6) & 0x3f]; + *cp++ = base64_table[ac & 0x3f]; + + src += 3; + srclen -= 3; } - if (padding) { - while (bits < 0) { + + switch (srclen) { + case 2: + ac = src[0] << 16 | src[1] << 8; + *cp++ = base64_table[ac >> 18]; + *cp++ = base64_table[(ac >> 12) & 0x3f]; + *cp++ = base64_table[(ac >> 6) & 0x3f]; + if (padding) + *cp++ = '='; + break; + case 1: + ac = src[0] << 16; + *cp++ = base64_table[ac >> 18]; + *cp++ = base64_table[(ac >> 12) & 0x3f]; + if (padding) { + *cp++ = '='; *cp++ = '='; - bits += 2; } + break; } return cp - dst; } @@ -117,41 +127,58 @@ EXPORT_SYMBOL_GPL(base64_encode); * * Decodes a string using the selected Base64 variant. * - * This implementation hasn't been optimized for performance. - * * Return: the length of the resulting decoded binary data in bytes, * or -1 if the string isn't a valid Base64 string. */ int base64_decode(const char *src, int srclen, u8 *dst, bool padding, enum base64_variant variant) { - u32 ac = 0; - int bits = 0; - int i; u8 *bp = dst; - s8 ch; + s8 input[4]; + s32 val; + const u8 *s = (const u8 *)src; + const s8 *base64_rev_tables = base64_rev_maps[variant]; - for (i = 0; i < srclen; i++) { - if (padding) { - if (src[i] == '=') { - ac = (ac << 6); - bits += 6; - if (bits >= 8) - bits -= 8; - continue; - } - } - ch = base64_rev_maps[variant][(u8)src[i]]; - if (ch == -1) - return -1; - ac = (ac << 6) | ch; - bits += 6; - if (bits >= 8) { - bits -= 8; - *bp++ = (u8)(ac >> bits); + while (srclen >= 4) { + input[0] = base64_rev_tables[s[0]]; + input[1] = base64_rev_tables[s[1]]; + input[2] = base64_rev_tables[s[2]]; + input[3] = base64_rev_tables[s[3]]; + + val = input[0] << 18 | input[1] << 12 | input[2] << 6 | input[3]; + + if (unlikely(val < 0)) { + if (!padding || srclen != 4 || s[3] != '=') + return -1; + padding = 0; + srclen = s[2] == '=' ? 2 : 3; + break; } + + *bp++ = val >> 16; + *bp++ = val >> 8; + *bp++ = val; + + s += 4; + srclen -= 4; } - if (ac & ((1 << bits) - 1)) + + if (likely(!srclen)) + return bp - dst; + if (padding || srclen == 1) return -1; + + val = (base64_rev_tables[s[0]] << 12) | (base64_rev_tables[s[1]] << 6); + *bp++ = val >> 10; + + if (srclen == 2) { + if (val & 0x800003ff) + return -1; + } else { + val |= base64_rev_tables[s[2]]; + if (val & 0x80000003) + return -1; + *bp++ = val >> 2; + } return bp - dst; } EXPORT_SYMBOL_GPL(base64_decode); -- cgit v1.2.3