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

[David Laight]

On Mon, 15 Sep 2025 15:50:18 +0800
Kuan-Wei Chiu <visitorckw at 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 at 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
>