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@xxxxxxxxx>
> >
> > 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@xxxxxxxxx>
> > Co-developed-by: Guan-Chun Wu <409411716@xxxxxxxxxxxxxx>
> > Signed-off-by: Guan-Chun Wu <409411716@xxxxxxxxxxxxxx>
> > ---
> > 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
