Re: [PATCH v2 1/5] lib/base64: Replace strchr() for better performance

[David Laight <david.laight.linux@gmail.com>]

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
> 
>