| 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
| ||
|
Message-Id: <20250830132805.7727-1-409411716@gms.tku.edu.tw>
Date: Sat, 30 Aug 2025 21:28:05 +0800
From: Guan-Chun Wu <409411716@....tku.edu.tw>
To: akpm@...ux-foundation.org
Cc: linux-kernel@...r.kernel.org,
Guan-Chun Wu <409411716@....tku.edu.tw>
Subject: [PATCH] lib/base64: optimize base64_encode() with block processing
Previously, base64_encode() processed one input byte at a time using a
bitstream approach, accumulating bits and emitting characters when 6
bits were available. This caused extra bit operations and loop overhead.
This patch processes 3-byte blocks at a time, mapping them directly to 4
output characters. Remaining 1 or 2 bytes are handled with standard Base64
padding. This reduces computation and improves performance.
Performance test (5 runs) for base64_encode():
64B input:
-------------------------------------------------------
| Old method | 129 | 135 | 125 | 126 | 131 | avg ~129 ns |
-------------------------------------------------------
| New method | 87 | 86 | 85 | 85 | 86 | avg ~86 ns |
-------------------------------------------------------
1KB input:
--------------------------------------------------------
| Old method | 1296 | 1286 | 1291 | 1290 | 1290 | avg ~1291 ns |
--------------------------------------------------------
| New method | 771 | 771 | 769 | 772 | 771 | avg ~771 ns |
--------------------------------------------------------
Signed-off-by: Guan-Chun Wu <409411716@....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++ = base64_table[(ac >> bits) & 0x3f];
} while (bits >= 6);
}
if (bits) {
*cp++ = base64_table[(ac << (6 - bits)) & 0x3f];
bits -= 6;
}
while (bits < 0) {
*cp++ = '=';
bits += 2;
}
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++ = base64_table[(ac >> 18) & 0x3f];
*cp++ = base64_table[(ac >> 12) & 0x3f];
*cp++ = base64_table[(ac >> 6) & 0x3f];
*cp++ = base64_table[ac & 0x3f];
i += 3;
}
switch (srclen - i) {
case 2:
ac = ((u32)src[i] << 16) | ((u32)src[i + 1] << 8);
*cp++ = base64_table[(ac >> 18) & 0x3f];
*cp++ = base64_table[(ac >> 12) & 0x3f];
*cp++ = base64_table[(ac >> 6) & 0x3f];
*cp++ = '=';
break;
case 1:
ac = ((u32)src[i] << 16);
*cp++ = base64_table[(ac >> 18) & 0x3f];
*cp++ = base64_table[(ac >> 12) & 0x3f];
*cp++ = '=';
*cp++ = '=';
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;
}
---
lib/base64.c | 38 +++++++++++++++++++++++---------------
1 file changed, 23 insertions(+), 15 deletions(-)
diff --git a/lib/base64.c b/lib/base64.c
index b736a7a431c5..a8f7b0e8b6ac 100644
--- a/lib/base64.c
+++ b/lib/base64.c
@@ -32,25 +32,33 @@ static const char base64_table[65] =
int base64_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++ = base64_table[(ac >> bits) & 0x3f];
- } while (bits >= 6);
- }
- if (bits) {
- *cp++ = base64_table[(ac << (6 - bits)) & 0x3f];
- bits -= 6;
+ while (i + 2 < srclen) {
+ ac = ((u32)src[i] << 16) | ((u32)src[i + 1] << 8) | (u32)src[i + 2];
+ *cp++ = base64_table[(ac >> 18) & 0x3f];
+ *cp++ = base64_table[(ac >> 12) & 0x3f];
+ *cp++ = base64_table[(ac >> 6) & 0x3f];
+ *cp++ = base64_table[ac & 0x3f];
+ i += 3;
}
- while (bits < 0) {
+
+ switch (srclen - i) {
+ case 2:
+ ac = ((u32)src[i] << 16) | ((u32)src[i + 1] << 8);
+ *cp++ = base64_table[(ac >> 18) & 0x3f];
+ *cp++ = base64_table[(ac >> 12) & 0x3f];
+ *cp++ = base64_table[(ac >> 6) & 0x3f];
+ *cp++ = '=';
+ break;
+ case 1:
+ ac = ((u32)src[i] << 16);
+ *cp++ = base64_table[(ac >> 18) & 0x3f];
+ *cp++ = base64_table[(ac >> 12) & 0x3f];
+ *cp++ = '=';
*cp++ = '=';
- bits += 2;
+ break;
}
return cp - dst;
}
--
2.34.1
Powered by blists - more mailing lists