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: <aMkQSIw4eHoDAED/@visitorckw-System-Product-Name>
Date: Tue, 16 Sep 2025 15:22:48 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: David Laight <david.laight.linux@...il.com>
Cc: Caleb Sander Mateos <csander@...estorage.com>,
	Guan-Chun Wu <409411716@....tku.edu.tw>, akpm@...ux-foundation.org,
	axboe@...nel.dk, ceph-devel@...r.kernel.org, ebiggers@...nel.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 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@...il.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@...il.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