From: Kuan-Wei Chiu <visitorckw@gmail.com>
The base64 decoder previously relied on strchr() to locate each
character in the base64 table. In the worst case, this requires
scanning all 64 entries, and even with bitwise tricks or word-sized
comparisons, still needs up to 8 checks.
Introduce a small helper function that maps input characters directly
to their position in the base64 table. This reduces the maximum number
of comparisons to 5, improving decoding efficiency while keeping the
logic straightforward.
Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
over 1000 runs, tested with KUnit):
Decode:
- 64B input: avg ~1530ns -> ~126ns (~12x faster)
- 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
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>
---
lib/base64.c | 17 ++++++++++++++++-
1 file changed, 16 insertions(+), 1 deletion(-)
diff --git a/lib/base64.c b/lib/base64.c
index b736a7a43..9416bded2 100644
--- a/lib/base64.c
+++ b/lib/base64.c
@@ -18,6 +18,21 @@
static const char base64_table[65] =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+static inline const char *find_chr(const char *base64_table, char ch)
+{
+ if ('A' <= ch && ch <= 'Z')
+ return base64_table + ch - 'A';
+ if ('a' <= ch && ch <= 'z')
+ return base64_table + 26 + ch - 'a';
+ if ('0' <= ch && ch <= '9')
+ return base64_table + 26 * 2 + ch - '0';
+ if (ch == base64_table[26 * 2 + 10])
+ return base64_table + 26 * 2 + 10;
+ if (ch == base64_table[26 * 2 + 10 + 1])
+ return base64_table + 26 * 2 + 10 + 1;
+ return NULL;
+}
+
/**
* base64_encode() - base64-encode some binary data
* @src: the binary data to encode
@@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
u8 *bp = dst;
for (i = 0; i < srclen; i++) {
- const char *p = strchr(base64_table, src[i]);
+ const char *p = find_chr(base64_table, src[i]);
if (src[i] == '=') {
ac = (ac << 6);
--
2.34.1On Thu, 11 Sep 2025 15:32:04 +0800
Guan-Chun Wu <409411716@gms.tku.edu.tw> wrote:
> From: Kuan-Wei Chiu <visitorckw@gmail.com>
>
> The base64 decoder previously relied on strchr() to locate each
> character in the base64 table. In the worst case, this requires
> scanning all 64 entries, and even with bitwise tricks or word-sized
> comparisons, still needs up to 8 checks.
>
> Introduce a small helper function that maps input characters directly
> to their position in the base64 table. This reduces the maximum number
> of comparisons to 5, improving decoding efficiency while keeping the
> logic straightforward.
>
> Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
> over 1000 runs, tested with KUnit):
>
> Decode:
> - 64B input: avg ~1530ns -> ~126ns (~12x faster)
> - 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
>
> 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>
> ---
> lib/base64.c | 17 ++++++++++++++++-
> 1 file changed, 16 insertions(+), 1 deletion(-)
>
> diff --git a/lib/base64.c b/lib/base64.c
> index b736a7a43..9416bded2 100644
> --- a/lib/base64.c
> +++ b/lib/base64.c
> @@ -18,6 +18,21 @@
> static const char base64_table[65] =
> "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
>
> +static inline const char *find_chr(const char *base64_table, char ch)
> +{
> + if ('A' <= ch && ch <= 'Z')
> + return base64_table + ch - 'A';
> + if ('a' <= ch && ch <= 'z')
> + return base64_table + 26 + ch - 'a';
> + if ('0' <= ch && ch <= '9')
> + return base64_table + 26 * 2 + ch - '0';
> + if (ch == base64_table[26 * 2 + 10])
> + return base64_table + 26 * 2 + 10;
> + if (ch == base64_table[26 * 2 + 10 + 1])
> + return base64_table + 26 * 2 + 10 + 1;
> + return NULL;
> +}
That's still going to be really horrible with random data.
You'll get a lot of mispredicted branch penalties.
I think they are about 20 clocks each on my Zen-5.
A 256 byte lookup table might be better.
However if you assume ascii then 'ch' can be split 3:5 bits and
the top three used to determine the valid values for the low bits
(probably using shifts of constants rather than actual arrays).
So apart from the outlying '+' and '/' (and IIRC there is a variant
that uses different characters) which can be picked up in the error
path; it ought to be possible to code with no conditionals at all.
To late at night to write (and test) an implementation.
David
> +
> /**
> * base64_encode() - base64-encode some binary data
> * @src: the binary data to encode
> @@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
> u8 *bp = dst;
>
> for (i = 0; i < srclen; i++) {
> - const char *p = strchr(base64_table, src[i]);
> + const char *p = find_chr(base64_table, src[i]);
>
> if (src[i] == '=') {
> ac = (ac << 6);
On Thu, Sep 11, 2025 at 03:32:04PM +0800, Guan-Chun Wu wrote:
> From: Kuan-Wei Chiu <visitorckw@gmail.com>
>
> The base64 decoder previously relied on strchr() to locate each
> character in the base64 table. In the worst case, this requires
> scanning all 64 entries, and even with bitwise tricks or word-sized
> comparisons, still needs up to 8 checks.
>
> Introduce a small helper function that maps input characters directly
> to their position in the base64 table. This reduces the maximum number
> of comparisons to 5, improving decoding efficiency while keeping the
> logic straightforward.
>
> Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
> over 1000 runs, tested with KUnit):
>
> Decode:
> - 64B input: avg ~1530ns -> ~126ns (~12x faster)
> - 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
>
> 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>
> ---
> lib/base64.c | 17 ++++++++++++++++-
> 1 file changed, 16 insertions(+), 1 deletion(-)
>
> diff --git a/lib/base64.c b/lib/base64.c
> index b736a7a43..9416bded2 100644
> --- a/lib/base64.c
> +++ b/lib/base64.c
> @@ -18,6 +18,21 @@
> static const char base64_table[65] =
> "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
>
> +static inline const char *find_chr(const char *base64_table, char ch)
> +{
> + if ('A' <= ch && ch <= 'Z')
> + return base64_table + ch - 'A';
> + if ('a' <= ch && ch <= 'z')
> + return base64_table + 26 + ch - 'a';
> + if ('0' <= ch && ch <= '9')
> + return base64_table + 26 * 2 + ch - '0';
> + if (ch == base64_table[26 * 2 + 10])
> + return base64_table + 26 * 2 + 10;
> + if (ch == base64_table[26 * 2 + 10 + 1])
> + return base64_table + 26 * 2 + 10 + 1;
> + return NULL;
> +}
> +
> /**
> * base64_encode() - base64-encode some binary data
> * @src: the binary data to encode
> @@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
> u8 *bp = dst;
>
> for (i = 0; i < srclen; i++) {
> - const char *p = strchr(base64_table, src[i]);
> + const char *p = find_chr(base64_table, src[i]);
>
> if (src[i] == '=') {
> ac = (ac << 6);
But this makes the contents of base64_table no longer be used, except
for entries 62 and 63. So this patch doesn't make sense. Either we
should actually use base64_table, or we should remove base64_table and
do the mapping entirely in code.
- Eric
Hi Eric,
On Thu, Sep 11, 2025 at 11:14:18AM -0700, Eric Biggers wrote:
> On Thu, Sep 11, 2025 at 03:32:04PM +0800, Guan-Chun Wu wrote:
> > From: Kuan-Wei Chiu <visitorckw@gmail.com>
> >
> > The base64 decoder previously relied on strchr() to locate each
> > character in the base64 table. In the worst case, this requires
> > scanning all 64 entries, and even with bitwise tricks or word-sized
> > comparisons, still needs up to 8 checks.
> >
> > Introduce a small helper function that maps input characters directly
> > to their position in the base64 table. This reduces the maximum number
> > of comparisons to 5, improving decoding efficiency while keeping the
> > logic straightforward.
> >
> > Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
> > over 1000 runs, tested with KUnit):
> >
> > Decode:
> > - 64B input: avg ~1530ns -> ~126ns (~12x faster)
> > - 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
> >
> > 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>
> > ---
> > lib/base64.c | 17 ++++++++++++++++-
> > 1 file changed, 16 insertions(+), 1 deletion(-)
> >
> > diff --git a/lib/base64.c b/lib/base64.c
> > index b736a7a43..9416bded2 100644
> > --- a/lib/base64.c
> > +++ b/lib/base64.c
> > @@ -18,6 +18,21 @@
> > static const char base64_table[65] =
> > "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
> >
> > +static inline const char *find_chr(const char *base64_table, char ch)
> > +{
> > + if ('A' <= ch && ch <= 'Z')
> > + return base64_table + ch - 'A';
> > + if ('a' <= ch && ch <= 'z')
> > + return base64_table + 26 + ch - 'a';
> > + if ('0' <= ch && ch <= '9')
> > + return base64_table + 26 * 2 + ch - '0';
> > + if (ch == base64_table[26 * 2 + 10])
> > + return base64_table + 26 * 2 + 10;
> > + if (ch == base64_table[26 * 2 + 10 + 1])
> > + return base64_table + 26 * 2 + 10 + 1;
> > + return NULL;
> > +}
> > +
> > /**
> > * base64_encode() - base64-encode some binary data
> > * @src: the binary data to encode
> > @@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
> > u8 *bp = dst;
> >
> > for (i = 0; i < srclen; i++) {
> > - const char *p = strchr(base64_table, src[i]);
> > + const char *p = find_chr(base64_table, src[i]);
> >
> > if (src[i] == '=') {
> > ac = (ac << 6);
>
> But this makes the contents of base64_table no longer be used, except
> for entries 62 and 63. So this patch doesn't make sense. Either we
> should actually use base64_table, or we should remove base64_table and
> do the mapping entirely in code.
>
For base64_decode(), you're right. After this patch it only uses the last
two entries of base64_table. However, base64_encode() still makes use of
the entire table.
I'm a bit unsure why it would be unacceptable if only one of the two
functions relies on the full base64 table.
Regards,
Kuan-Wei
On Fri, 12 Sep 2025 02:44:41 +0800
Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
> Hi Eric,
>
> On Thu, Sep 11, 2025 at 11:14:18AM -0700, Eric Biggers wrote:
> > On Thu, Sep 11, 2025 at 03:32:04PM +0800, Guan-Chun Wu wrote:
> > > From: Kuan-Wei Chiu <visitorckw@gmail.com>
> > >
> > > The base64 decoder previously relied on strchr() to locate each
> > > character in the base64 table. In the worst case, this requires
> > > scanning all 64 entries, and even with bitwise tricks or word-sized
> > > comparisons, still needs up to 8 checks.
> > >
> > > Introduce a small helper function that maps input characters directly
> > > to their position in the base64 table. This reduces the maximum number
> > > of comparisons to 5, improving decoding efficiency while keeping the
> > > logic straightforward.
> > >
> > > Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
> > > over 1000 runs, tested with KUnit):
> > >
> > > Decode:
> > > - 64B input: avg ~1530ns -> ~126ns (~12x faster)
> > > - 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
> > >
> > > 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>
> > > ---
> > > lib/base64.c | 17 ++++++++++++++++-
> > > 1 file changed, 16 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/lib/base64.c b/lib/base64.c
> > > index b736a7a43..9416bded2 100644
> > > --- a/lib/base64.c
> > > +++ b/lib/base64.c
> > > @@ -18,6 +18,21 @@
> > > static const char base64_table[65] =
> > > "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
> > >
> > > +static inline const char *find_chr(const char *base64_table, char ch)
> > > +{
> > > + if ('A' <= ch && ch <= 'Z')
> > > + return base64_table + ch - 'A';
> > > + if ('a' <= ch && ch <= 'z')
> > > + return base64_table + 26 + ch - 'a';
> > > + if ('0' <= ch && ch <= '9')
> > > + return base64_table + 26 * 2 + ch - '0';
> > > + if (ch == base64_table[26 * 2 + 10])
> > > + return base64_table + 26 * 2 + 10;
> > > + if (ch == base64_table[26 * 2 + 10 + 1])
> > > + return base64_table + 26 * 2 + 10 + 1;
> > > + return NULL;
> > > +}
> > > +
> > > /**
> > > * base64_encode() - base64-encode some binary data
> > > * @src: the binary data to encode
> > > @@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
> > > u8 *bp = dst;
> > >
> > > for (i = 0; i < srclen; i++) {
> > > - const char *p = strchr(base64_table, src[i]);
> > > + const char *p = find_chr(base64_table, src[i]);
> > >
> > > if (src[i] == '=') {
> > > ac = (ac << 6);
> >
> > But this makes the contents of base64_table no longer be used, except
> > for entries 62 and 63. So this patch doesn't make sense. Either we
> > should actually use base64_table, or we should remove base64_table and
> > do the mapping entirely in code.
> >
> For base64_decode(), you're right. After this patch it only uses the last
> two entries of base64_table. However, base64_encode() still makes use of
> the entire table.
>
> I'm a bit unsure why it would be unacceptable if only one of the two
> functions relies on the full base64 table.
I think the point is that that first 62 entries are fixed, only the last two
change.
Passing the full table might make someone think they can an arbitrary table.
Clearly this isn't true.
Having the full table is convenient for the encoder (although the memory
lookups may be slower than other algorithms).
This might be ok if you could guarantee the compiler would use conditional moves:
if (val > 26)
val += 'a' - 'Z' - 1;
if (val > 52)
val += '0' - 'z' - 1;
if (val > 62)
val = val == 62 ? ch_62 : ch_63;
else
val += 'A';
This test code seems to do the decode.
The only conditional is in the path for 62 and 53 (and errors).
int main(int argc, char **argv)
{
char *cp = argv[1];
unsigned char ch;
unsigned int bank, val;
unsigned int ch_62 = '+', ch_63 = '/';
if (!cp)
return 1;
while ((ch = *cp++)) {
bank = (ch >> 5) * 4;
val = ch & 0x1f;
// Need to subtract 1 or 16, variants using 'conditional move'
// are probably better - but not all cpu have sane ones.
val -= ((0xf << 4) >> bank) + 1;
if (val >= (((10u << 4 | 26u << 8 | 26u << 12) >> bank) & 0x1e)) {
if (ch == ch_62)
val = 62;
else if (ch == ch_63)
val = 63;
else
val = 255;
} else {
val += ((52u << 8 | 0u << 16 | 26u << 24) >> (bank * 2)) & 63;
}
printf("%c => %u\n", ch, val);
}
return 0;
}
David
>
> Regards,
> Kuan-Wei
>
>
On Fri, Sep 12, 2025 at 02:44:41AM +0800, Kuan-Wei Chiu wrote:
> Hi Eric,
>
> On Thu, Sep 11, 2025 at 11:14:18AM -0700, Eric Biggers wrote:
> > On Thu, Sep 11, 2025 at 03:32:04PM +0800, Guan-Chun Wu wrote:
> > > From: Kuan-Wei Chiu <visitorckw@gmail.com>
> > >
> > > The base64 decoder previously relied on strchr() to locate each
> > > character in the base64 table. In the worst case, this requires
> > > scanning all 64 entries, and even with bitwise tricks or word-sized
> > > comparisons, still needs up to 8 checks.
> > >
> > > Introduce a small helper function that maps input characters directly
> > > to their position in the base64 table. This reduces the maximum number
> > > of comparisons to 5, improving decoding efficiency while keeping the
> > > logic straightforward.
> > >
> > > Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
> > > over 1000 runs, tested with KUnit):
> > >
> > > Decode:
> > > - 64B input: avg ~1530ns -> ~126ns (~12x faster)
> > > - 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
> > >
> > > 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>
> > > ---
> > > lib/base64.c | 17 ++++++++++++++++-
> > > 1 file changed, 16 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/lib/base64.c b/lib/base64.c
> > > index b736a7a43..9416bded2 100644
> > > --- a/lib/base64.c
> > > +++ b/lib/base64.c
> > > @@ -18,6 +18,21 @@
> > > static const char base64_table[65] =
> > > "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
> > >
> > > +static inline const char *find_chr(const char *base64_table, char ch)
> > > +{
> > > + if ('A' <= ch && ch <= 'Z')
> > > + return base64_table + ch - 'A';
> > > + if ('a' <= ch && ch <= 'z')
> > > + return base64_table + 26 + ch - 'a';
> > > + if ('0' <= ch && ch <= '9')
> > > + return base64_table + 26 * 2 + ch - '0';
> > > + if (ch == base64_table[26 * 2 + 10])
> > > + return base64_table + 26 * 2 + 10;
> > > + if (ch == base64_table[26 * 2 + 10 + 1])
> > > + return base64_table + 26 * 2 + 10 + 1;
> > > + return NULL;
> > > +}
> > > +
> > > /**
> > > * base64_encode() - base64-encode some binary data
> > > * @src: the binary data to encode
> > > @@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
> > > u8 *bp = dst;
> > >
> > > for (i = 0; i < srclen; i++) {
> > > - const char *p = strchr(base64_table, src[i]);
> > > + const char *p = find_chr(base64_table, src[i]);
> > >
> > > if (src[i] == '=') {
> > > ac = (ac << 6);
> >
> > But this makes the contents of base64_table no longer be used, except
> > for entries 62 and 63. So this patch doesn't make sense. Either we
> > should actually use base64_table, or we should remove base64_table and
> > do the mapping entirely in code.
> >
> For base64_decode(), you're right. After this patch it only uses the last
> two entries of base64_table. However, base64_encode() still makes use of
> the entire table.
>
> I'm a bit unsure why it would be unacceptable if only one of the two
> functions relies on the full base64 table.
Well, don't remove the table then. But please don't calculate pointers
into it, only to take the offset from the beginning and never actually
dereference them. You should just generate the offset directly.
- Eric
On Thu, Sep 11, 2025 at 11:49:35AM -0700, Eric Biggers wrote:
> On Fri, Sep 12, 2025 at 02:44:41AM +0800, Kuan-Wei Chiu wrote:
> > Hi Eric,
> >
> > On Thu, Sep 11, 2025 at 11:14:18AM -0700, Eric Biggers wrote:
> > > On Thu, Sep 11, 2025 at 03:32:04PM +0800, Guan-Chun Wu wrote:
> > > > From: Kuan-Wei Chiu <visitorckw@gmail.com>
> > > >
> > > > The base64 decoder previously relied on strchr() to locate each
> > > > character in the base64 table. In the worst case, this requires
> > > > scanning all 64 entries, and even with bitwise tricks or word-sized
> > > > comparisons, still needs up to 8 checks.
> > > >
> > > > Introduce a small helper function that maps input characters directly
> > > > to their position in the base64 table. This reduces the maximum number
> > > > of comparisons to 5, improving decoding efficiency while keeping the
> > > > logic straightforward.
> > > >
> > > > Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
> > > > over 1000 runs, tested with KUnit):
> > > >
> > > > Decode:
> > > > - 64B input: avg ~1530ns -> ~126ns (~12x faster)
> > > > - 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
> > > >
> > > > 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>
> > > > ---
> > > > lib/base64.c | 17 ++++++++++++++++-
> > > > 1 file changed, 16 insertions(+), 1 deletion(-)
> > > >
> > > > diff --git a/lib/base64.c b/lib/base64.c
> > > > index b736a7a43..9416bded2 100644
> > > > --- a/lib/base64.c
> > > > +++ b/lib/base64.c
> > > > @@ -18,6 +18,21 @@
> > > > static const char base64_table[65] =
> > > > "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
> > > >
> > > > +static inline const char *find_chr(const char *base64_table, char ch)
> > > > +{
> > > > + if ('A' <= ch && ch <= 'Z')
> > > > + return base64_table + ch - 'A';
> > > > + if ('a' <= ch && ch <= 'z')
> > > > + return base64_table + 26 + ch - 'a';
> > > > + if ('0' <= ch && ch <= '9')
> > > > + return base64_table + 26 * 2 + ch - '0';
> > > > + if (ch == base64_table[26 * 2 + 10])
> > > > + return base64_table + 26 * 2 + 10;
> > > > + if (ch == base64_table[26 * 2 + 10 + 1])
> > > > + return base64_table + 26 * 2 + 10 + 1;
> > > > + return NULL;
> > > > +}
> > > > +
> > > > /**
> > > > * base64_encode() - base64-encode some binary data
> > > > * @src: the binary data to encode
> > > > @@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
> > > > u8 *bp = dst;
> > > >
> > > > for (i = 0; i < srclen; i++) {
> > > > - const char *p = strchr(base64_table, src[i]);
> > > > + const char *p = find_chr(base64_table, src[i]);
> > > >
> > > > if (src[i] == '=') {
> > > > ac = (ac << 6);
> > >
> > > But this makes the contents of base64_table no longer be used, except
> > > for entries 62 and 63. So this patch doesn't make sense. Either we
> > > should actually use base64_table, or we should remove base64_table and
> > > do the mapping entirely in code.
> > >
> > For base64_decode(), you're right. After this patch it only uses the last
> > two entries of base64_table. However, base64_encode() still makes use of
> > the entire table.
> >
> > I'm a bit unsure why it would be unacceptable if only one of the two
> > functions relies on the full base64 table.
>
> Well, don't remove the table then. But please don't calculate pointers
> into it, only to take the offset from the beginning and never actually
> dereference them. You should just generate the offset directly.
>
Agreed. Thanks for the review.
I'll make that change in the next version.
Regards,
Kuan-Wei
On Thu, Sep 11, 2025 at 12:33 AM Guan-Chun Wu <409411716@gms.tku.edu.tw> wrote:
>
> From: Kuan-Wei Chiu <visitorckw@gmail.com>
>
> The base64 decoder previously relied on strchr() to locate each
> character in the base64 table. In the worst case, this requires
> scanning all 64 entries, and even with bitwise tricks or word-sized
> comparisons, still needs up to 8 checks.
>
> Introduce a small helper function that maps input characters directly
> to their position in the base64 table. This reduces the maximum number
> of comparisons to 5, improving decoding efficiency while keeping the
> logic straightforward.
>
> Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
> over 1000 runs, tested with KUnit):
>
> Decode:
> - 64B input: avg ~1530ns -> ~126ns (~12x faster)
> - 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
>
> 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>
> ---
> lib/base64.c | 17 ++++++++++++++++-
> 1 file changed, 16 insertions(+), 1 deletion(-)
>
> diff --git a/lib/base64.c b/lib/base64.c
> index b736a7a43..9416bded2 100644
> --- a/lib/base64.c
> +++ b/lib/base64.c
> @@ -18,6 +18,21 @@
> static const char base64_table[65] =
> "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
Does base64_table still need to be NUL-terminated?
>
> +static inline const char *find_chr(const char *base64_table, char ch)
Don't see a need to pass in base64_table, the function could just
access the global variable directly.
> +{
> + if ('A' <= ch && ch <= 'Z')
> + return base64_table + ch - 'A';
> + if ('a' <= ch && ch <= 'z')
> + return base64_table + 26 + ch - 'a';
> + if ('0' <= ch && ch <= '9')
> + return base64_table + 26 * 2 + ch - '0';
> + if (ch == base64_table[26 * 2 + 10])
> + return base64_table + 26 * 2 + 10;
> + if (ch == base64_table[26 * 2 + 10 + 1])
> + return base64_table + 26 * 2 + 10 + 1;
> + return NULL;
This is still pretty branchy. One way to avoid the branches would be
to define a reverse lookup table mapping base64 chars to their values
(or a sentinel value for invalid chars). Have you benchmarked that
approach?
Best,
Caleb
> +}
> +
> /**
> * base64_encode() - base64-encode some binary data
> * @src: the binary data to encode
> @@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
> u8 *bp = dst;
>
> for (i = 0; i < srclen; i++) {
> - const char *p = strchr(base64_table, src[i]);
> + const char *p = find_chr(base64_table, src[i]);
>
> if (src[i] == '=') {
> ac = (ac << 6);
> --
> 2.34.1
>
>
Hi Caleb,
On Thu, Sep 11, 2025 at 08:50:12AM -0700, Caleb Sander Mateos wrote:
> On Thu, Sep 11, 2025 at 12:33 AM Guan-Chun Wu <409411716@gms.tku.edu.tw> wrote:
> >
> > From: Kuan-Wei Chiu <visitorckw@gmail.com>
> >
> > The base64 decoder previously relied on strchr() to locate each
> > character in the base64 table. In the worst case, this requires
> > scanning all 64 entries, and even with bitwise tricks or word-sized
> > comparisons, still needs up to 8 checks.
> >
> > Introduce a small helper function that maps input characters directly
> > to their position in the base64 table. This reduces the maximum number
> > of comparisons to 5, improving decoding efficiency while keeping the
> > logic straightforward.
> >
> > Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
> > over 1000 runs, tested with KUnit):
> >
> > Decode:
> > - 64B input: avg ~1530ns -> ~126ns (~12x faster)
> > - 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
> >
> > 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>
> > ---
> > lib/base64.c | 17 ++++++++++++++++-
> > 1 file changed, 16 insertions(+), 1 deletion(-)
> >
> > diff --git a/lib/base64.c b/lib/base64.c
> > index b736a7a43..9416bded2 100644
> > --- a/lib/base64.c
> > +++ b/lib/base64.c
> > @@ -18,6 +18,21 @@
> > static const char base64_table[65] =
> > "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
>
> Does base64_table still need to be NUL-terminated?
>
Right, it doesn't need to be nul-terminated.
> >
> > +static inline const char *find_chr(const char *base64_table, char ch)
>
> Don't see a need to pass in base64_table, the function could just
> access the global variable directly.
>
> > +{
> > + if ('A' <= ch && ch <= 'Z')
> > + return base64_table + ch - 'A';
> > + if ('a' <= ch && ch <= 'z')
> > + return base64_table + 26 + ch - 'a';
> > + if ('0' <= ch && ch <= '9')
> > + return base64_table + 26 * 2 + ch - '0';
> > + if (ch == base64_table[26 * 2 + 10])
> > + return base64_table + 26 * 2 + 10;
> > + if (ch == base64_table[26 * 2 + 10 + 1])
> > + return base64_table + 26 * 2 + 10 + 1;
> > + return NULL;
>
> This is still pretty branchy. One way to avoid the branches would be
> to define a reverse lookup table mapping base64 chars to their values
> (or a sentinel value for invalid chars). Have you benchmarked that
> approach?
>
We've considered that approach and agree it could very likely be faster.
However, since a later patch in this series will add support for users to
provide their own base64 table, adopting a reverse lookup table would also
require each user to supply a corresponding reverse table. We're not sure
whether the extra memory overhead in exchange for runtime speed would be
an acceptable tradeoff for everyone, and it might also cause confusion on
the API side as to why it's mandatory to pass in a reverse table.
By contrast, the simple inline function gives us a clear performance
improvement without additional memory cost or complicating the API. That
said, if there's consensus that a reverse lookup table is worthwhile, we
can certainly revisit the idea.
Regards,
Kuan-Wei
>
> > +}
> > +
> > /**
> > * base64_encode() - base64-encode some binary data
> > * @src: the binary data to encode
> > @@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
> > u8 *bp = dst;
> >
> > for (i = 0; i < srclen; i++) {
> > - const char *p = strchr(base64_table, src[i]);
> > + const char *p = find_chr(base64_table, src[i]);
> >
> > if (src[i] == '=') {
> > ac = (ac << 6);
> > --
> > 2.34.1
> >
> >
On Fri, Sep 12, 2025 at 12:26:02AM +0800, Kuan-Wei Chiu wrote:
> Hi Caleb,
>
> On Thu, Sep 11, 2025 at 08:50:12AM -0700, Caleb Sander Mateos wrote:
> > On Thu, Sep 11, 2025 at 12:33 AM Guan-Chun Wu <409411716@gms.tku.edu.tw> wrote:
> > >
> > > From: Kuan-Wei Chiu <visitorckw@gmail.com>
> > >
> > > The base64 decoder previously relied on strchr() to locate each
> > > character in the base64 table. In the worst case, this requires
> > > scanning all 64 entries, and even with bitwise tricks or word-sized
> > > comparisons, still needs up to 8 checks.
> > >
> > > Introduce a small helper function that maps input characters directly
> > > to their position in the base64 table. This reduces the maximum number
> > > of comparisons to 5, improving decoding efficiency while keeping the
> > > logic straightforward.
> > >
> > > Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged
> > > over 1000 runs, tested with KUnit):
> > >
> > > Decode:
> > > - 64B input: avg ~1530ns -> ~126ns (~12x faster)
> > > - 1KB input: avg ~27726ns -> ~2003ns (~14x faster)
> > >
> > > 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>
> > > ---
> > > lib/base64.c | 17 ++++++++++++++++-
> > > 1 file changed, 16 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/lib/base64.c b/lib/base64.c
> > > index b736a7a43..9416bded2 100644
> > > --- a/lib/base64.c
> > > +++ b/lib/base64.c
> > > @@ -18,6 +18,21 @@
> > > static const char base64_table[65] =
> > > "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
> >
> > Does base64_table still need to be NUL-terminated?
> >
> Right, it doesn't need to be nul-terminated.
>
> > >
> > > +static inline const char *find_chr(const char *base64_table, char ch)
> >
> > Don't see a need to pass in base64_table, the function could just
> > access the global variable directly.
> >
> > > +{
> > > + if ('A' <= ch && ch <= 'Z')
> > > + return base64_table + ch - 'A';
> > > + if ('a' <= ch && ch <= 'z')
> > > + return base64_table + 26 + ch - 'a';
> > > + if ('0' <= ch && ch <= '9')
> > > + return base64_table + 26 * 2 + ch - '0';
> > > + if (ch == base64_table[26 * 2 + 10])
> > > + return base64_table + 26 * 2 + 10;
> > > + if (ch == base64_table[26 * 2 + 10 + 1])
> > > + return base64_table + 26 * 2 + 10 + 1;
> > > + return NULL;
> >
> > This is still pretty branchy. One way to avoid the branches would be
> > to define a reverse lookup table mapping base64 chars to their values
> > (or a sentinel value for invalid chars). Have you benchmarked that
> > approach?
> >
> We've considered that approach and agree it could very likely be faster.
> However, since a later patch in this series will add support for users to
> provide their own base64 table, adopting a reverse lookup table would also
> require each user to supply a corresponding reverse table. We're not sure
> whether the extra memory overhead in exchange for runtime speed would be
> an acceptable tradeoff for everyone, and it might also cause confusion on
> the API side as to why it's mandatory to pass in a reverse table.
>
> By contrast, the simple inline function gives us a clear performance
> improvement without additional memory cost or complicating the API. That
> said, if there's consensus that a reverse lookup table is worthwhile, we
> can certainly revisit the idea.
>
Or I just realized that since different base64 tables only differ in the
last two characters, we could allocate a 256 entry reverse table inside
the base64 function and set the mapping for those two characters. That
way, users wouldn't need to pass in a reverse table. The downside is that
this would significantly increase the function's stack size.
Regards,
Kuan-Wei
>
> >
> > > +}
> > > +
> > > /**
> > > * base64_encode() - base64-encode some binary data
> > > * @src: the binary data to encode
> > > @@ -78,7 +93,7 @@ int base64_decode(const char *src, int srclen, u8 *dst)
> > > u8 *bp = dst;
> > >
> > > for (i = 0; i < srclen; i++) {
> > > - const char *p = strchr(base64_table, src[i]);
> > > + const char *p = find_chr(base64_table, src[i]);
> > >
> > > if (src[i] == '=') {
> > > ac = (ac << 6);
> > > --
> > > 2.34.1
> > >
> > >
On Fri, 12 Sep 2025 00:38:20 +0800 Kuan-Wei Chiu <visitorckw@gmail.com> wrote: ... > Or I just realized that since different base64 tables only differ in the > last two characters, we could allocate a 256 entry reverse table inside > the base64 function and set the mapping for those two characters. That > way, users wouldn't need to pass in a reverse table. The downside is that > this would significantly increase the function's stack size. How many different variants are there? IIRC there are only are two common ones. (and it might not matter is the decoder accepted both sets since I'm pretty sure the issue is that '/' can't be used because it has already been treated as a separator.) Since the code only has to handle in-kernel users - which presumably use a fixed table for each call site, they only need to pass in an identifier for the table. That would mean they can use the same identifier for encode and decode, and the tables themselves wouldn't be replicated and would be part of the implementation. David
On Sun, Sep 14, 2025 at 09:12:43PM +0100, David Laight wrote:
> On Fri, 12 Sep 2025 00:38:20 +0800
> Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
>
> ...
> > Or I just realized that since different base64 tables only differ in the
> > last two characters, we could allocate a 256 entry reverse table inside
> > the base64 function and set the mapping for those two characters. That
> > way, users wouldn't need to pass in a reverse table. The downside is that
> > this would significantly increase the function's stack size.
>
> How many different variants are there?
Currently there are 3 variants:
RFC 4648 (standard), RFC 4648 (base64url), and RFC 3501.
They use "+/", "-_", and "+," respectively for the last two characters.
> IIRC there are only are two common ones.
> (and it might not matter is the decoder accepted both sets since I'm
> pretty sure the issue is that '/' can't be used because it has already
> been treated as a separator.)
>
> Since the code only has to handle in-kernel users - which presumably
> use a fixed table for each call site, they only need to pass in
> an identifier for the table.
> That would mean they can use the same identifier for encode and decode,
> and the tables themselves wouldn't be replicated and would be part of
> the implementation.
>
So maybe we can define an enum in the header like this:
enum base64_variant {
BASE64_STD, /* RFC 4648 (standard) */
BASE64_URLSAFE, /* RFC 4648 (base64url) */
BASE64_IMAP, /* RFC 3501 */
};
Then the enum value can be passed as a parameter to base64_encode/decode,
and in base64.c we can define the tables and reverse tables like this:
static const char base64_tables[][64] = {
[BASE64_STD] = "ABC...+/",
[BASE64_URLSAFE] = "ABC...-_",
[BASE64_IMAP] = "ABC...+,",
};
What do you think about this approach?
Regards,
Kuan-Wei
On Mon, 15 Sep 2025 15:50:18 +0800
Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
> On Sun, Sep 14, 2025 at 09:12:43PM +0100, David Laight wrote:
> > On Fri, 12 Sep 2025 00:38:20 +0800
> > Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
> >
> > ...
> > > Or I just realized that since different base64 tables only differ in the
> > > last two characters, we could allocate a 256 entry reverse table inside
> > > the base64 function and set the mapping for those two characters. That
> > > way, users wouldn't need to pass in a reverse table. The downside is that
> > > this would significantly increase the function's stack size.
> >
> > How many different variants are there?
>
> Currently there are 3 variants:
> RFC 4648 (standard), RFC 4648 (base64url), and RFC 3501.
> They use "+/", "-_", and "+," respectively for the last two characters.
So always decoding "+-" to 62 and "/_," to 63 would just miss a few error
cases - which may not matter.
>
> > IIRC there are only are two common ones.
> > (and it might not matter is the decoder accepted both sets since I'm
> > pretty sure the issue is that '/' can't be used because it has already
> > been treated as a separator.)
> >
> > Since the code only has to handle in-kernel users - which presumably
> > use a fixed table for each call site, they only need to pass in
> > an identifier for the table.
> > That would mean they can use the same identifier for encode and decode,
> > and the tables themselves wouldn't be replicated and would be part of
> > the implementation.
> >
> So maybe we can define an enum in the header like this:
>
> enum base64_variant {
> BASE64_STD, /* RFC 4648 (standard) */
> BASE64_URLSAFE, /* RFC 4648 (base64url) */
> BASE64_IMAP, /* RFC 3501 */
> };
>
> Then the enum value can be passed as a parameter to base64_encode/decode,
> and in base64.c we can define the tables and reverse tables like this:
>
> static const char base64_tables[][64] = {
> [BASE64_STD] = "ABC...+/",
> [BASE64_URLSAFE] = "ABC...-_",
> [BASE64_IMAP] = "ABC...+,",
> };
>
> What do you think about this approach?
That is the sort of thing I was thinking about.
It even lets you change the implementation without changing the callers.
For instance BASE64_STD could actually be a pointer to an incomplete
struct that contains the lookup tables.
Initialising the decode table is going to be a PITA.
You probably want 'signed char' with -1 for the invalid characters.
Then if any of the four characters for a 24bit output are invalid
the 24bit value will be negative.
David
>
> Regards,
> Kuan-Wei
>
On Mon, Sep 15, 2025 at 12:02:20PM +0100, David Laight wrote:
> On Mon, 15 Sep 2025 15:50:18 +0800
> Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
>
> > On Sun, Sep 14, 2025 at 09:12:43PM +0100, David Laight wrote:
> > > On Fri, 12 Sep 2025 00:38:20 +0800
> > > Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
> > >
> > > ...
> > > > Or I just realized that since different base64 tables only differ in the
> > > > last two characters, we could allocate a 256 entry reverse table inside
> > > > the base64 function and set the mapping for those two characters. That
> > > > way, users wouldn't need to pass in a reverse table. The downside is that
> > > > this would significantly increase the function's stack size.
> > >
> > > How many different variants are there?
> >
> > Currently there are 3 variants:
> > RFC 4648 (standard), RFC 4648 (base64url), and RFC 3501.
> > They use "+/", "-_", and "+," respectively for the last two characters.
>
> So always decoding "+-" to 62 and "/_," to 63 would just miss a few error
> cases - which may not matter.
>
> >
> > > IIRC there are only are two common ones.
> > > (and it might not matter is the decoder accepted both sets since I'm
> > > pretty sure the issue is that '/' can't be used because it has already
> > > been treated as a separator.)
> > >
> > > Since the code only has to handle in-kernel users - which presumably
> > > use a fixed table for each call site, they only need to pass in
> > > an identifier for the table.
> > > That would mean they can use the same identifier for encode and decode,
> > > and the tables themselves wouldn't be replicated and would be part of
> > > the implementation.
> > >
> > So maybe we can define an enum in the header like this:
> >
> > enum base64_variant {
> > BASE64_STD, /* RFC 4648 (standard) */
> > BASE64_URLSAFE, /* RFC 4648 (base64url) */
> > BASE64_IMAP, /* RFC 3501 */
> > };
> >
> > Then the enum value can be passed as a parameter to base64_encode/decode,
> > and in base64.c we can define the tables and reverse tables like this:
> >
> > static const char base64_tables[][64] = {
> > [BASE64_STD] = "ABC...+/",
> > [BASE64_URLSAFE] = "ABC...-_",
> > [BASE64_IMAP] = "ABC...+,",
> > };
> >
> > What do you think about this approach?
>
> That is the sort of thing I was thinking about.
>
> It even lets you change the implementation without changing the callers.
> For instance BASE64_STD could actually be a pointer to an incomplete
> struct that contains the lookup tables.
>
> Initialising the decode table is going to be a PITA.
> You probably want 'signed char' with -1 for the invalid characters.
> Then if any of the four characters for a 24bit output are invalid
> the 24bit value will be negative.
>
Thanks for the feedback.
so for the next version of the patch, I plan to use a 3×64 encode
table and a 3×256 reverse table.
Does this approach sound good to everyone?
Regards,
Kuan-Wei
On Thu, Sep 11, 2025 at 8:50 AM Caleb Sander Mateos <csander@purestorage.com> wrote: > > On Thu, Sep 11, 2025 at 12:33 AM Guan-Chun Wu <409411716@gms.tku.edu.tw> wrote: > > > > From: Kuan-Wei Chiu <visitorckw@gmail.com> > > > > The base64 decoder previously relied on strchr() to locate each > > character in the base64 table. In the worst case, this requires > > scanning all 64 entries, and even with bitwise tricks or word-sized > > comparisons, still needs up to 8 checks. > > > > Introduce a small helper function that maps input characters directly > > to their position in the base64 table. This reduces the maximum number > > of comparisons to 5, improving decoding efficiency while keeping the > > logic straightforward. > > > > Benchmarks on x86_64 (Intel Core i7-10700 @ 2.90GHz, averaged > > over 1000 runs, tested with KUnit): > > > > Decode: > > - 64B input: avg ~1530ns -> ~126ns (~12x faster) > > - 1KB input: avg ~27726ns -> ~2003ns (~14x faster) > > > > 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> > > --- > > lib/base64.c | 17 ++++++++++++++++- > > 1 file changed, 16 insertions(+), 1 deletion(-) > > > > diff --git a/lib/base64.c b/lib/base64.c > > index b736a7a43..9416bded2 100644 > > --- a/lib/base64.c > > +++ b/lib/base64.c > > @@ -18,6 +18,21 @@ > > static const char base64_table[65] = > > "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; > > Does base64_table still need to be NUL-terminated? > > > > > +static inline const char *find_chr(const char *base64_table, char ch) > > Don't see a need to pass in base64_table, the function could just > access the global variable directly. Never mind, I see the following patches pass in different base64_table values.
© 2016 - 2025 Red Hat, Inc.