fs/crypto/fname.c | 33 ++++++++++++++++++++++----------- 1 file changed, 22 insertions(+), 11 deletions(-)
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.1On 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
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.
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
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.
© 2016 - 2025 Red Hat, Inc.