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

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

[Guan-Chun Wu]

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

static int encode_v1(const u8 *src, int srclen, char *dst)
{
	u32 ac = 0;
	int bits = 0;
	int i;
	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);
	}
	if (bits)
		*cp++ = base64url_table[(ac << (6 - bits)) & 0x3f];
	return cp - dst;
}

static int encode_v2(const u8 *src, int srclen, char *dst)
{
	u32 ac = 0;
	int i = 0;
	char *cp = dst;

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

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

static void run_test(const char *label, const u8 *data, int len)
{
    char *dst1, *dst2;
    int n1, n2;
    u64 start, end;

    dst1 = kmalloc(len * 2, GFP_KERNEL);
    dst2 = kmalloc(len * 2, GFP_KERNEL);

    if (!dst1 || !dst2) {
        pr_err("%s: Failed to allocate dst buffers\n", label);
        goto out;
    }

    pr_info("[%s] input size = %d bytes\n", label, len);

    start = ktime_get_ns();
    n1 = encode_v1(data, len, dst1);
    end = ktime_get_ns();
    pr_info("[%s] encode_v1 time: %lld ns\n", label, end - start);

    start = ktime_get_ns();
    n2 = encode_v2(data, len, dst2);
    end = ktime_get_ns();
    pr_info("[%s] encode_v2 time: %lld ns\n", label, end - start);

    if (n1 != n2 || memcmp(dst1, dst2, n1) != 0)
        pr_err("[%s] Mismatch detected between encode_v1 and encode_v2!\n", label);
    else
        pr_info("[%s] Outputs are identical.\n", label);

out:
    kfree(dst1);
    kfree(dst2);
}

static int __init base64_perf_init(void)
{
    u8 *data1k;

    pr_info("Module init - running multi-size tests\n");

    {
        static u8 test64[64];
        get_random_bytes(test64, sizeof(test64));
        run_test("64B", test64, sizeof(test64));
    }

    data1k = kmalloc(1024, GFP_KERNEL);
    if (data1k) {
        get_random_bytes(data1k, 1024);
        run_test("1KB", data1k, 1024);
        kfree(data1k);
    } else {
        pr_err("Failed to allocate 1KB test buffer\n");
    }

    return 0;
}
---
 fs/crypto/fname.c | 33 ++++++++++++++++++++++-----------
 1 file changed, 22 insertions(+), 11 deletions(-)

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;
+	}
+
+	switch (srclen - i) {
+	case 2:
+		ac = ((u32)src[i] << 16) | ((u32)src[i + 1] << 8);
+		*cp++ = base64url_table[(ac >> 18) & 0x3f];
+		*cp++ = base64url_table[(ac >> 12) & 0x3f];
+		*cp++ = base64url_table[(ac >> 6) & 0x3f];
+		break;
+	case 1:
+		ac = ((u32)src[i] << 16);
+		*cp++ = base64url_table[(ac >> 18) & 0x3f];
+		*cp++ = base64url_table[(ac >> 12) & 0x3f];
+		break;
 	}
-	if (bits)
-		*cp++ = base64url_table[(ac << (6 - bits)) & 0x3f];
 	return cp - dst;
 }
 
-- 
2.34.1

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

[Eric Biggers]

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

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

[Thomas Weißschuh]

On 2025-08-30 21:28:32+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.

Can't the custom base64 implementations in fs/ not pass a custom table
and padding to the generic algorithm in lib/? Then we only need to maintain
this code once.


Thomas

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

[Guan-Chun Wu]

Hi Eric,

>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()?

I’m interested in adding a KUnit test as a separate patch
to cover both fscrypt_base64url_encode() and fscrypt_base64url_decode().

Per Thomas’s suggestion, I’d also like to explore a generic Base64 helper in lib/
(with encoding table and optional padding), with tests in lib/test/
covering both the standard and URL-safe variants.

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

Thanks, Eric. I'll update the loop condition to use 'srclen >= 3' for
better readability, and drop the redundant '& 0x3f' when shifting the
24-bit accumulator.

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

[Guan-Chun Wu]

Hi Thomas,

>On 2025-08-30 21:28:32+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.
>
>Can't the custom base64 implementations in fs/ not pass a custom table
>and padding to the generic algorithm in lib/? Then we only need to maintain
>this code once.
>
>
>Thomas

Thanks, that makes sense.

For v2, I’m considering extending the lib/base64 API to support a custom
encoding table and optional padding. That way, the fs/ code can just use
the generic implementation directly, and we only need to maintain the
logic in one place.