* + lib-base64-optimize-base64_decode-with-reverse-lookup-tables.patch added to mm-nonmm-unstable branch
@ 2025-11-01 4:10 Andrew Morton
0 siblings, 0 replies; 2+ messages in thread
From: Andrew Morton @ 2025-11-01 4:10 UTC (permalink / raw)
To: mm-commits, xiubli, tytso, sagi, kbusch, jaegeuk, idryomov,
home7438072, hch, ebiggers, axboe, 409411716, visitorckw, akpm
The patch titled
Subject: lib/base64: optimize base64_decode() with reverse lookup tables
has been added to the -mm mm-nonmm-unstable branch. Its filename is
lib-base64-optimize-base64_decode-with-reverse-lookup-tables.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-base64-optimize-base64_decode-with-reverse-lookup-tables.patch
This patch will later appear in the mm-nonmm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Kuan-Wei Chiu <visitorckw@gmail.com>
Subject: lib/base64: optimize base64_decode() with reverse lookup tables
Date: Wed, 29 Oct 2025 18:20:36 +0800
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)
Link: https://lkml.kernel.org/r/20251029102036.543227-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>
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: Ted Ts'o <tytso@mit.edu>
Cc: Xiubo Li <xiubli@redhat.com>
Cc: Yu-Sheng Huang <home7438072@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
lib/base64.c | 23 +++++++++++++++++++----
1 file changed, 19 insertions(+), 4 deletions(-)
--- a/lib/base64.c~lib-base64-optimize-base64_decode-with-reverse-lookup-tables
+++ a/lib/base64.c
@@ -21,6 +21,21 @@ static const char base64_tables[][65] =
[BASE64_IMAP] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+,",
};
+#define BASE64_REV_INIT(ch_62, ch_63) { \
+ [0 ... 255] = -1, \
+ ['A'] = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, \
+ 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, \
+ ['a'] = 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, \
+ 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, \
+ ['0'] = 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, \
+ [ch_62] = 62, [ch_63] = 63, \
+}
+
+static const s8 base64_rev_maps[][256] = {
+ [BASE64_STD] = BASE64_REV_INIT('+', '/'),
+ [BASE64_URLSAFE] = BASE64_REV_INIT('-', '_'),
+ [BASE64_IMAP] = BASE64_REV_INIT('+', ',')
+};
/**
* base64_encode() - Base64-encode some binary data
* @src: the binary data to encode
@@ -84,10 +99,9 @@ int base64_decode(const char *src, int s
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 +111,10 @@ int base64_decode(const char *src, int s
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;
_
Patches currently in -mm which might be from visitorckw@gmail.com are
lib-base64-add-support-for-multiple-variants.patch
lib-base64-optimize-base64_decode-with-reverse-lookup-tables.patch
^ permalink raw reply [flat|nested] 2+ messages in thread* + lib-base64-optimize-base64_decode-with-reverse-lookup-tables.patch added to mm-nonmm-unstable branch
@ 2025-11-14 22:58 Andrew Morton
0 siblings, 0 replies; 2+ messages in thread
From: Andrew Morton @ 2025-11-14 22:58 UTC (permalink / raw)
To: mm-commits, xiubli, tytso, Slava.Dubeyko, sagi, kbusch, jaegeuk,
idryomov, home7438072, hch, ebiggers, david.laight.linux, axboe,
409411716, visitorckw, akpm
The patch titled
Subject: lib/base64: optimize base64_decode() with reverse lookup tables
has been added to the -mm mm-nonmm-unstable branch. Its filename is
lib-base64-optimize-base64_decode-with-reverse-lookup-tables.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-base64-optimize-base64_decode-with-reverse-lookup-tables.patch
This patch will later appear in the mm-nonmm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Kuan-Wei Chiu <visitorckw@gmail.com>
Subject: lib/base64: optimize base64_decode() with reverse lookup tables
Date: Fri, 14 Nov 2025 14:01:07 +0800
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)
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>
---
lib/base64.c | 51 +++++++++++++++++++++++++++++++++++++++++++++----
1 file changed, 47 insertions(+), 4 deletions(-)
--- a/lib/base64.c~lib-base64-optimize-base64_decode-with-reverse-lookup-tables
+++ a/lib/base64.c
@@ -22,6 +22,49 @@ static const char base64_tables[][65] =
};
/**
+ * 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
* @srclen: the length of @src in bytes
@@ -84,10 +127,9 @@ int base64_decode(const char *src, int s
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 s
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;
_
Patches currently in -mm which might be from visitorckw@gmail.com are
revert-lib-plistc-enforce-memory-ordering-in-plist_check_list.patch
lib-base64-add-support-for-multiple-variants.patch
lib-base64-optimize-base64_decode-with-reverse-lookup-tables.patch
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2025-11-14 22:58 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-11-01 4:10 + lib-base64-optimize-base64_decode-with-reverse-lookup-tables.patch added to mm-nonmm-unstable branch Andrew Morton
-- strict thread matches above, loose matches on Subject: below --
2025-11-14 22:58 Andrew Morton
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.