From nobody Thu Dec 18 03:29:41 2025 Received: from mail-pj1-f51.google.com (mail-pj1-f51.google.com [209.85.216.51]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 76B282DAFA5 for ; Fri, 14 Nov 2025 06:01:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.51 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763100102; cv=none; b=iRySjjxlNSyAbGY7W8T8cYSHbu1kyWykvGv8wcdWbY+EMfXkjmdR4u6ADNROExWkZphbXuGiJIlHpbaWgxDOdXsRibDlmSNYJpC1azFrPJQvgH5ez2RZpvwHyRVe27y9BoOGamOMLuHQ1+/9/BWlCEHT5tK7CPCEBLJcmfV7e8s= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763100102; c=relaxed/simple; bh=iA2hBVRXx0YemEHPsh/s0OtYYJaZyVmkN06w/iID+7o=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=nrzuWv6sgsdqLhGI1iceh6LUPKWKZEdQj0p8w3VsYp8FCSTtNa49SAXnfuD9fQvy8GblqvGWvU/li79uw5rffUXhthU+we8Qj1wvg71WC7jrGU67zHU7rZe/pS5lV1WKjUvCzyIau1+5nYxMGG9qLGT+L6R8q8BJRe8v5OrQ/Ho= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=gms.tku.edu.tw; spf=pass smtp.mailfrom=gms.tku.edu.tw; dkim=pass (2048-bit key) header.d=gms-tku-edu-tw.20230601.gappssmtp.com header.i=@gms-tku-edu-tw.20230601.gappssmtp.com header.b=wX58QEpg; arc=none smtp.client-ip=209.85.216.51 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=gms.tku.edu.tw Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gms.tku.edu.tw Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gms-tku-edu-tw.20230601.gappssmtp.com header.i=@gms-tku-edu-tw.20230601.gappssmtp.com header.b="wX58QEpg" Received: by mail-pj1-f51.google.com with SMTP id 98e67ed59e1d1-3437ea05540so1641415a91.0 for ; Thu, 13 Nov 2025 22:01:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gms-tku-edu-tw.20230601.gappssmtp.com; s=20230601; t=1763100100; x=1763704900; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Q1IGQOBRzs6BjZdUR3pYUPttP+jjYEqCfWUHv2cldxw=; b=wX58QEpg7f1aY5M0lu5SBt44yNLnb40/gCOEIdgMqbpCPJGFtCYK+To/agDuQcqKlz xxoH/Y0FMmFpDTi53SkNCbUoD07QK+09VMpAGI3hNz3iUanCMVAP+8CRvu7aFb74x4GD 26fK3uhsryfDX9bV5BY42J3su/1po5juWRY1XHH1uEbAdJQi0BF9KxjjU2eSBSoBdyPl k1NjFg2MwXvsiz8yg9Iccw61ivsu/Lu6wF4Zbn6/OFcWM/XIG9qEuFNd+vm1pnolpraw IWKXIU8YMX8TV8rAdYM1NnPN04Kp1Y/ClzZUS1ceeqxEzLZzN0aFkG+9OWhpbZiyLXkJ B86A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763100100; x=1763704900; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=Q1IGQOBRzs6BjZdUR3pYUPttP+jjYEqCfWUHv2cldxw=; b=Eh4kgiFSVxjidUcstkiJP9Wnpkd/MO0+93HCSmKAmHj0OPKjfdJADs8kknevFObAWn T7d6IUkXJyVLTG3Tv04Uv6lH7SaJ2yEQ69UKC/SobnndZCCtO4dkJ24yaKKqT34dJg2o bf67XIlCr2o5IpK5QzE+oyHO+CUk6uTzU8XKYjQrc/+dSHcVW6UcasDxlxU1vWDLOBWu qqxBCwAdvSVTUdieuiGbCeGBx37pF4x0ix9wovFYWvPY7pU9OAKBj7GmLIoFJGJp6tqm AbuShEY3fTtNa6fbtA7ME3y2HEPqAF97UaAXVcnDzNP9HwXnw6o2OL/s66G6oD+EQirq XPUw== X-Forwarded-Encrypted: i=1; AJvYcCUaYGSumApgXYtGg7O8wHqIEEaDAO4d/EeS5Vh/8arWQw6q3mQhGF3TSp/AxgLgynEqcZyyYXAcWMwdlQk=@vger.kernel.org X-Gm-Message-State: AOJu0YzbQolE8SrCuxPN1YCN7NMeMOTL7X42f10pDyGseC46rXCjQc41 ckWQ3G9YXRKQREjy0oy/gPja41Fq9szsM1rwmWhZROxMJ8cLm2D60q6jT+7lbOu+hfs= X-Gm-Gg: ASbGnctni74C+2RD6FMHTJvYCLogc0wenzfW91XgsSHHYJNVzgdPlFcsebJ9F+jGyuE mmHltAvZB14W0lh35rIdBcm8EvkjP6T3ziDG8ujqLkfrVCojMFCAR97OURXZC4qUqEZbwSyU2C+ X/P7AcvihLAlfZEZu24mG0MxnkbfFbiz8E0U/j0JoTyJMoDAb1+28lSrWBppeskJOKlKcu16MVq jgwoI95IEr/ospdtK2IK9Gtff/q82ESKyXLRptAz+qw0kJR99UFA+beLfLqlSOUo1ZtR2liCAvi XLXpIsRxP4ZvsjRi8cbrHLerECDHp76VHtrsh37Va0d1HcJdSWxdlsUsvdlOvfxYsCmzn+x0/4d 2Y3eYp138UWNyLVyeBh6q28akG63SkQwAqiOW7dIfwUdLLCH5DjJWejQxhd2GLGZ5j+cDl3hk39 j5avRMhVtZ9Gi8S0SolFxiXF5T X-Google-Smtp-Source: AGHT+IGm/DcFCjii9Cj0HeKdnayirMai9hbtcC7DKvoxz9MTk6adf+dWGrkM2fl+VogccyRz+p4CTA== X-Received: by 2002:a17:90b:3b4b:b0:343:a631:28a8 with SMTP id 98e67ed59e1d1-343fa754b6emr2387408a91.37.1763100098951; Thu, 13 Nov 2025 22:01:38 -0800 (PST) Received: from wu-Pro-E500-G6-WS720T.. ([2001:288:7001:2703:22d2:323c:497d:adbd]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-343ed55564dsm4354199a91.13.2025.11.13.22.01.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 13 Nov 2025 22:01:38 -0800 (PST) From: Guan-Chun Wu <409411716@gms.tku.edu.tw> To: 409411716@gms.tku.edu.tw Cc: akpm@linux-foundation.org, andriy.shevchenko@intel.com, axboe@kernel.dk, ceph-devel@vger.kernel.org, david.laight.linux@gmail.com, ebiggers@kernel.org, hch@lst.de, home7438072@gmail.com, idryomov@gmail.com, jaegeuk@kernel.org, kbusch@kernel.org, linux-fscrypt@vger.kernel.org, linux-kernel@vger.kernel.org, linux-nvme@lists.infradead.org, sagi@grimberg.me, tytso@mit.edu, visitorckw@gmail.com, xiubli@redhat.com Subject: [PATCH v5 3/6] lib/base64: rework encode/decode for speed and stricter validation Date: Fri, 14 Nov 2025 14:01:32 +0800 Message-Id: <20251114060132.89279-1-409411716@gms.tku.edu.tw> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20251114055829.87814-1-409411716@gms.tku.edu.tw> References: <20251114055829.87814-1-409411716@gms.tku.edu.tw> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The old base64 implementation relied on a bit-accumulator loop, which was slow for larger inputs and too permissive in validation. It would accept extra '=3D', missing '=3D', or even '=3D' appearing in the middle of the in= put, allowing malformed strings to pass. This patch reworks the internals to improve performance and enforce stricter validation. Changes: - Encoder: * Process input in 3-byte blocks, mapping 24 bits into four 6-bit symbols, avoiding bit-by-bit shifting and reducing loop iterations. * Handle the final 1-2 leftover bytes explicitly and emit '=3D' only when requested. - Decoder: * Based on the reverse lookup tables from the previous patch, decode input in 4-character groups. * Each group is looked up directly, converted into numeric values, and combined into 3 output bytes. * Explicitly handle padded and unpadded forms: - With padding: input length must be a multiple of 4, and '=3D' is allowed only in the last two positions. Reject stray or early '=3D'. - Without padding: validate tail lengths (2 or 3 chars) and require unused low bits to be zero. * Removed the bit-accumulator style loop to reduce loop iterations. Performance (x86_64, Intel Core i7-10700 @ 2.90GHz, avg over 1000 runs, KUnit): Encode: 64B ~90ns -> ~32ns (~2.8x) 1KB ~1332ns -> ~510ns (~2.6x) Decode: 64B ~1530ns -> ~35ns (~43.7x) 1KB ~27726ns -> ~530ns (~52.3x) Co-developed-by: Kuan-Wei Chiu Signed-off-by: Kuan-Wei Chiu Co-developed-by: Yu-Sheng Huang Signed-off-by: Yu-Sheng Huang Signed-off-by: Guan-Chun Wu <409411716@gms.tku.edu.tw> Reviewed-by: David Laight --- lib/base64.c | 109 ++++++++++++++++++++++++++++++++------------------- 1 file changed, 68 insertions(+), 41 deletions(-) diff --git a/lib/base64.c b/lib/base64.c index 9d1074bb821c..1a6d8fe37eda 100644 --- a/lib/base64.c +++ b/lib/base64.c @@ -79,28 +79,38 @@ static const s8 base64_rev_maps[][256] =3D { int base64_encode(const u8 *src, int srclen, char *dst, bool padding, enum= base64_variant variant) { u32 ac =3D 0; - int bits =3D 0; - int i; char *cp =3D dst; const char *base64_table =3D base64_tables[variant]; =20 - for (i =3D 0; i < srclen; i++) { - ac =3D (ac << 8) | src[i]; - bits +=3D 8; - do { - bits -=3D 6; - *cp++ =3D base64_table[(ac >> bits) & 0x3f]; - } while (bits >=3D 6); - } - if (bits) { - *cp++ =3D base64_table[(ac << (6 - bits)) & 0x3f]; - bits -=3D 6; + while (srclen >=3D 3) { + ac =3D (u32)src[0] << 16 | (u32)src[1] << 8 | (u32)src[2]; + *cp++ =3D base64_table[ac >> 18]; + *cp++ =3D base64_table[(ac >> 12) & 0x3f]; + *cp++ =3D base64_table[(ac >> 6) & 0x3f]; + *cp++ =3D base64_table[ac & 0x3f]; + + src +=3D 3; + srclen -=3D 3; } - if (padding) { - while (bits < 0) { + + switch (srclen) { + case 2: + ac =3D (u32)src[0] << 16 | (u32)src[1] << 8; + *cp++ =3D base64_table[ac >> 18]; + *cp++ =3D base64_table[(ac >> 12) & 0x3f]; + *cp++ =3D base64_table[(ac >> 6) & 0x3f]; + if (padding) + *cp++ =3D '=3D'; + break; + case 1: + ac =3D (u32)src[0] << 16; + *cp++ =3D base64_table[ac >> 18]; + *cp++ =3D base64_table[(ac >> 12) & 0x3f]; + if (padding) { + *cp++ =3D '=3D'; *cp++ =3D '=3D'; - bits +=3D 2; } + break; } return cp - dst; } @@ -116,41 +126,58 @@ EXPORT_SYMBOL_GPL(base64_encode); * * Decodes a string using the selected Base64 variant. * - * This implementation hasn't been optimized for performance. - * * Return: the length of the resulting decoded binary data in bytes, * or -1 if the string isn't a valid Base64 string. */ int base64_decode(const char *src, int srclen, u8 *dst, bool padding, enum= base64_variant variant) { - u32 ac =3D 0; - int bits =3D 0; - int i; u8 *bp =3D dst; - s8 ch; + s8 input[4]; + s32 val; + const u8 *s =3D (const u8 *)src; + const s8 *base64_rev_tables =3D base64_rev_maps[variant]; =20 - for (i =3D 0; i < srclen; i++) { - if (padding) { - if (src[i] =3D=3D '=3D') { - ac =3D (ac << 6); - bits +=3D 6; - if (bits >=3D 8) - bits -=3D 8; - continue; - } - } - ch =3D base64_rev_maps[variant][(u8)src[i]]; - if (ch =3D=3D -1) - return -1; - ac =3D (ac << 6) | ch; - bits +=3D 6; - if (bits >=3D 8) { - bits -=3D 8; - *bp++ =3D (u8)(ac >> bits); + while (srclen >=3D 4) { + input[0] =3D base64_rev_tables[s[0]]; + input[1] =3D base64_rev_tables[s[1]]; + input[2] =3D base64_rev_tables[s[2]]; + input[3] =3D base64_rev_tables[s[3]]; + + val =3D input[0] << 18 | input[1] << 12 | input[2] << 6 | input[3]; + + if (unlikely(val < 0)) { + if (!padding || srclen !=3D 4 || s[3] !=3D '=3D') + return -1; + padding =3D 0; + srclen =3D s[2] =3D=3D '=3D' ? 2 : 3; + break; } + + *bp++ =3D val >> 16; + *bp++ =3D val >> 8; + *bp++ =3D val; + + s +=3D 4; + srclen -=3D 4; } - if (ac & ((1 << bits) - 1)) + + if (likely(!srclen)) + return bp - dst; + if (padding || srclen =3D=3D 1) return -1; + + val =3D (base64_rev_tables[s[0]] << 12) | (base64_rev_tables[s[1]] << 6); + *bp++ =3D val >> 10; + + if (srclen =3D=3D 2) { + if (val & 0x800003ff) + return -1; + } else { + val |=3D base64_rev_tables[s[2]]; + if (val & 0x80000003) + return -1; + *bp++ =3D val >> 2; + } return bp - dst; } EXPORT_SYMBOL_GPL(base64_decode); --=20 2.34.1