Re: [PATCH] fscrypt: optimize fscrypt_base64url_encode() with block processing

[Eric Biggers <ebiggers@kernel.org>]

On Sat, Aug 30, 2025 at 09:28:32PM +0800, Guan-Chun Wu wrote:
> Previously, fscrypt_base64url_encode() processed input one byte at a
> time, using a bitstream, accumulating bits and emitting characters when
> 6 bits were available. This was correct but added extra computation.
> 
> This patch processes input in 3-byte blocks, mapping directly to 4 output
> characters. Any remaining 1 or 2 bytes are handled according to Base64 URL
> rules. This reduces computation and improves performance.
> 
> Performance test (5 runs) for fscrypt_base64url_encode():
> 
> 64B input:
> -------------------------------------------------------
> | Old method | 131 | 108 | 114 | 122 | 123 | avg ~120 ns |
> -------------------------------------------------------
> | New method |  84 |  81 |  84 |  82 |  84 | avg ~83 ns  |
> -------------------------------------------------------
> 
> 1KB input:
> --------------------------------------------------------
> | Old method | 1152 | 1121 | 1142 | 1147 | 1148 | avg ~1142 ns |
> --------------------------------------------------------
> | New method |  767 |  752 |  765 |  771 |  776 | avg ~766 ns  |
> --------------------------------------------------------
> 
> Signed-off-by: Guan-Chun Wu <409411716@gms.tku.edu.tw>

Thanks!

> Tested on Linux 6.8.0-64-generic x86_64
> with Intel Core i7-10700 @ 2.90GHz
> 
> Test is executed in the form of kernel module.
> 
> Test script:

Is there any chance you'd be interested in creating an fscrypt KUnit
test (in a separate patch) which tests fscrypt_base64url_encode() and
fscrypt_base64url_decode()?

> diff --git a/fs/crypto/fname.c b/fs/crypto/fname.c
> index 010f9c0a4c2f..adaa16905498 100644
> --- a/fs/crypto/fname.c
> +++ b/fs/crypto/fname.c
> @@ -204,20 +204,31 @@ static const char base64url_table[65] =
>  static int fscrypt_base64url_encode(const u8 *src, int srclen, char *dst)
>  {
>  	u32 ac = 0;
> -	int bits = 0;
> -	int i;
> +	int i = 0;
>  	char *cp = dst;
>  
> -	for (i = 0; i < srclen; i++) {
> -		ac = (ac << 8) | src[i];
> -		bits += 8;
> -		do {
> -			bits -= 6;
> -			*cp++ = base64url_table[(ac >> bits) & 0x3f];
> -		} while (bits >= 6);
> +	while (i + 2 < srclen) {
> +		ac = ((u32)src[i] << 16) | ((u32)src[i + 1] << 8) | (u32)src[i + 2];
> +		*cp++ = base64url_table[(ac >> 18) & 0x3f];
> +		*cp++ = base64url_table[(ac >> 12) & 0x3f];
> +		*cp++ = base64url_table[(ac >> 6) & 0x3f];
> +		*cp++ = base64url_table[ac & 0x3f];
> +		i += 3;
> +	}

To make it a bit easier to understand, how about updating src and srclen
as we go along?

	while (srclen >= 3) {
		ac = ((u32)src[0] << 16) | ((u32)src[1] << 8) | (u32)src[2];
		*cp++ = base64url_table[ac >> 18];
		*cp++ = base64url_table[(ac >> 12) & 0x3f];
		*cp++ = base64url_table[(ac >> 6) & 0x3f];
		*cp++ = base64url_table[ac & 0x3f];
		src += 3;
		srclen -= 3;
	}

	switch (srclen) {
	case 2:
		ac = ((u32)src[0] << 16) | ((u32)src[1] << 8);
		*cp++ = base64url_table[ac >> 18];
		*cp++ = base64url_table[(ac >> 12) & 0x3f];
		*cp++ = base64url_table[(ac >> 6) & 0x3f];
		break;
	case 1:
		ac = ((u32)src[0] << 16);
		*cp++ = base64url_table[ac >> 18];
		*cp++ = base64url_table[(ac >> 12) & 0x3f];
		break;
	}

'srclen >= 3' is much more readable than 'i + 2 < srclen', IMO.

Also, instead of '(ac >> 18) & 0x3f', we can just use 'ac >> 18', since
'ac' is a 24-bit value.

- Eric