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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <aMMcX8jEoBjBUeyj@visitorckw-System-Product-Name>
Date: Fri, 12 Sep 2025 03:00:47 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: Eric Biggers <ebiggers@...nel.org>
Cc: Guan-Chun Wu <409411716@....tku.edu.tw>, akpm@...ux-foundation.org,
	axboe@...nel.dk, ceph-devel@...r.kernel.org, hch@....de,
	home7438072@...il.com, idryomov@...il.com, jaegeuk@...nel.org,
	kbusch@...nel.org, linux-fscrypt@...r.kernel.org,
	linux-kernel@...r.kernel.org, linux-nvme@...ts.infradead.org,
	sagi@...mberg.me, tytso@....edu, xiubli@...hat.com
Subject: Re: [PATCH v2 1/5] lib/base64: Replace strchr() for better
 performance

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@...il.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@...il.com>
> > > > Co-developed-by: Guan-Chun Wu <409411716@....tku.edu.tw>
> > > > Signed-off-by: Guan-Chun Wu <409411716@....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