From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wr1-f43.google.com (mail-wr1-f43.google.com [209.85.221.43]) (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 3BCB630216B for ; Fri, 14 Nov 2025 09:14:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.43 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763111700; cv=none; b=oYfg5LPVlt8PTYWiSDr7BibFkPh9RIzZndqpMRbehihm2JXhRBCBqsFxFLd7dxPi5HFB2hlvwRZfHXJdY/mtissw/mnzn6LLn581ZAPqB+91XYSfUL7tS0uyUPGLeN/TO1kUgBJAAR8thKDV+u2n2J2lJK4LmtTHAAzqer3Bw0Y= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763111700; c=relaxed/simple; bh=2E/wk4ll31VAFKwMa9GhOn8TIMH7sn15E5LQUU4V2ho=; h=Date:From:To:Cc:Subject:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=fSeXudXzZJiT94rH81blauo9wkWknTfJr1vdpq+bU+tgjgnJ0xLlDNhnRnFsAkhgGUbulcnN8FH8zCsL3ImLgX0PMDmDrN3/hydKz3p9JB303URFgyi7LPVqbo3RCReMaQAKnbtOlAWNLaMIDhnSUAANt0KC4FhN32o7oBzdcU0= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=e4oLwIsy; arc=none smtp.client-ip=209.85.221.43 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="e4oLwIsy" Received: by mail-wr1-f43.google.com with SMTP id ffacd0b85a97d-42b32900c8bso1005822f8f.0 for ; Fri, 14 Nov 2025 01:14:58 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1763111696; x=1763716496; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:subject:cc:to:from:date:from:to:cc:subject:date :message-id:reply-to; bh=RmGL71As4NC9Ari9wD9SqERFZR+6bEtc3Jb/BauBhYM=; b=e4oLwIsyIxIifQNdUiFTGWaCnu0ZzKbY5Hve7EfEs9fj3xNm+r6WBVeAlJJ4cp4Rfd x41d4jMiUfKKGuq0HwmobjPJbH/yS8R5EjNbf9OjQoFIAEfu2KFfE5NN90KCBrsRQCjD QB8mQ+XtVkL9Sw6QyBJ9ABlyLKtsbHn1KulRYtMlvuuT0gFlCp1C40NoKQIlffA7xK9f x3IFmt+4wmeDv72S/Xj8JVmpk9M7r9L964Fm/2c5LLoplvDWVzQFg50Y2WdoGFnI9qec KJDH49N+4E8mz9jGO1SV4w8VBCR/+JTq5hEKf6/A5ldUyMM9k654riRUUFVklF7p9YAG q/4Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763111696; x=1763716496; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:subject:cc:to:from:date:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=RmGL71As4NC9Ari9wD9SqERFZR+6bEtc3Jb/BauBhYM=; b=RDmtmb/cTNqhjG2NJKLFPrKUzqnOifAH7tLJMMrZv+a4+1SHyPSINSs9vlcH/gnEg2 htOr+cl3xBJZ3wtjj1EGh/FAMm9ye9J3n+OGa55p2Ram7IiodyT8hmDZ546AgMiKK8zu s6EOggcn2lr39lM9N//akioDbTvEIJ5s1DPfXtliq5wz8CWEg6obfvIiyW6q/RmUIbTK CEge40HqC8ukk6XFMc7/X9oywwmAK8AckDDC5DuvTFs0cLa2BH9+yDt9FauQRuEdorQS +kEiue0m7i+Wvq4nvBNZufFIYaTyeKx9SnRox6GPGLMlrtw2t/7t+LLju6OSRH4qZm+9 8dSg== X-Forwarded-Encrypted: i=1; AJvYcCVbQBu1hoI8Af6Jq8rTL+oY5jg7NEcHwMLys6J6PzEWgZnlVxoQ8F+LJu+Tr2REwvedHgMuMxkq7+ra@vger.kernel.org X-Gm-Message-State: AOJu0YwNghYL/RK4Gavuu1mg+wB0d5qOtmAwACr/iI8ZcXAcz4yRl6rL 2CgCNZ72QOLAJ7ZZAl2CirFCMSjSpMANIH01PT9s5YUbS3jwFSqXZiNf X-Gm-Gg: ASbGncsOyIOZHDIZtehStz+RZy3z3sl+VPlt17KGp2EveV8+ofiEr/E7ktrjqhpksJ4 oDI4CEIPP1fHRjEw4ZmlNuJY7q2AqHzZ2lLRF97YaoF+Ea9Kip7LlqJlWB89ggv/EK2TuE2KNxv Zy/Npdx0/+BY412aIma+uJ3WRZJ/c2axHn9xeRWkWrHI67J5liHQ+AHCDrRfr+Ho9cMegSUZRGU i4gNXT0EPiNH4196G+ap/64K2gQjD0CMpNPiL3G3xBoYXvmaxIDFIPRIPKJN3BLz0Q2QIw7NPfE yzO3zCyAeaMiCVfsrPa+7a3phFF26PS0PbPp8k3P7f6o3RfGmesJ7Stt/q/TExi3BMXIJz+1Dcn 8Q575B2lEgSYCrkmzb6z//30WWQDEedNua30Q0Izt+sOy4WzqfQGsufHW3uao09YnbuoicubCJw NHc9GFnyg1vqaWK8LDhQNviE1zDyjqPbg86ksG9Zh4TXq3mXKyS3Sn X-Google-Smtp-Source: AGHT+IG6vU2bsOEFY2Pt3/YgVdDI6hItqo1MmD515aomBXXZ72CDnKNh3ehpPfNQLQSjE0uqgfo72w== X-Received: by 2002:a05:6000:1a8d:b0:42b:3746:3b86 with SMTP id ffacd0b85a97d-42b5938aab5mr2239624f8f.54.1763111696455; Fri, 14 Nov 2025 01:14:56 -0800 (PST) Received: from pumpkin (82-69-66-36.dsl.in-addr.zen.co.uk. [82.69.66.36]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-42b53f0b8d6sm9102852f8f.28.2025.11.14.01.14.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 14 Nov 2025 01:14:56 -0800 (PST) Date: Fri, 14 Nov 2025 09:14:54 +0000 From: David Laight To: Guan-Chun Wu <409411716@gms.tku.edu.tw> Cc: akpm@linux-foundation.org, andriy.shevchenko@intel.com, axboe@kernel.dk, ceph-devel@vger.kernel.org, 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: Re: [PATCH v5 2/6] lib/base64: Optimize base64_decode() with reverse lookup tables Message-ID: <20251114091454.5a5dbfc7@pumpkin> In-Reply-To: <20251114060107.89026-1-409411716@gms.tku.edu.tw> References: <20251114055829.87814-1-409411716@gms.tku.edu.tw> <20251114060107.89026-1-409411716@gms.tku.edu.tw> X-Mailer: Claws Mail 4.1.1 (GTK 3.24.38; arm-unknown-linux-gnueabihf) Precedence: bulk X-Mailing-List: ceph-devel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit On Fri, 14 Nov 2025 14:01:07 +0800 Guan-Chun Wu <409411716@gms.tku.edu.tw> wrote: > From: Kuan-Wei Chiu > > Replace the use of strchr() in base64_decode() with precomputed reverse > lookup tables for each variant. This avoids repeated string scans and > improves performance. Use -1 in the tables to mark invalid characters. > > Decode: > 64B ~1530ns -> ~80ns (~19.1x) > 1KB ~27726ns -> ~1239ns (~22.4x) > > Signed-off-by: Kuan-Wei Chiu > Co-developed-by: Guan-Chun Wu <409411716@gms.tku.edu.tw> > Signed-off-by: Guan-Chun Wu <409411716@gms.tku.edu.tw> Reviewed-by: David Laight > --- > lib/base64.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++---- > 1 file changed, 47 insertions(+), 4 deletions(-) > > diff --git a/lib/base64.c b/lib/base64.c > index a7c20a8e8e98..9d1074bb821c 100644 > --- a/lib/base64.c > +++ b/lib/base64.c > @@ -21,6 +21,49 @@ static const char base64_tables[][65] = { > [BASE64_IMAP] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+,", > }; > > +/** > + * Initialize the base64 reverse mapping for a single character > + * This macro maps a character to its corresponding base64 value, > + * returning -1 if the character is invalid. > + * char 'A'-'Z' maps to 0-25, 'a'-'z' maps to 26-51, '0'-'9' maps to 52-61, > + * ch_62 maps to 62, ch_63 maps to 63, and other characters return -1 > + */ > +#define INIT_1(v, ch_62, ch_63) \ > + [v] = (v) >= 'A' && (v) <= 'Z' ? (v) - 'A' \ > + : (v) >= 'a' && (v) <= 'z' ? (v) - 'a' + 26 \ > + : (v) >= '0' && (v) <= '9' ? (v) - '0' + 52 \ > + : (v) == (ch_62) ? 62 : (v) == (ch_63) ? 63 : -1 > +/** > + * Recursive macros to generate multiple Base64 reverse mapping table entries. > + * Each macro generates a sequence of entries in the lookup table: > + * INIT_2 generates 2 entries, INIT_4 generates 4, INIT_8 generates 8, and so on up to INIT_32. > + */ > +#define INIT_2(v, ...) INIT_1(v, __VA_ARGS__), INIT_1((v) + 1, __VA_ARGS__) > +#define INIT_4(v, ...) INIT_2(v, __VA_ARGS__), INIT_2((v) + 2, __VA_ARGS__) > +#define INIT_8(v, ...) INIT_4(v, __VA_ARGS__), INIT_4((v) + 4, __VA_ARGS__) > +#define INIT_16(v, ...) INIT_8(v, __VA_ARGS__), INIT_8((v) + 8, __VA_ARGS__) > +#define INIT_32(v, ...) INIT_16(v, __VA_ARGS__), INIT_16((v) + 16, __VA_ARGS__) > + > +#define BASE64_REV_INIT(ch_62, ch_63) { \ > + [0 ... 0x1f] = -1, \ > + INIT_32(0x20, ch_62, ch_63), \ > + INIT_32(0x40, ch_62, ch_63), \ > + INIT_32(0x60, ch_62, ch_63), \ > + [0x80 ... 0xff] = -1 } > + > +static const s8 base64_rev_maps[][256] = { > + [BASE64_STD] = BASE64_REV_INIT('+', '/'), > + [BASE64_URLSAFE] = BASE64_REV_INIT('-', '_'), > + [BASE64_IMAP] = BASE64_REV_INIT('+', ',') > +}; > + > +#undef BASE64_REV_INIT > +#undef INIT_32 > +#undef INIT_16 > +#undef INIT_8 > +#undef INIT_4 > +#undef INIT_2 > +#undef INIT_1 > /** > * base64_encode() - Base64-encode some binary data > * @src: the binary data to encode > @@ -84,10 +127,9 @@ int base64_decode(const char *src, int srclen, u8 *dst, bool padding, enum base6 > int bits = 0; > int i; > u8 *bp = dst; > - const char *base64_table = base64_tables[variant]; > + s8 ch; > > for (i = 0; i < srclen; i++) { > - const char *p = strchr(base64_table, src[i]); > if (padding) { > if (src[i] == '=') { > ac = (ac << 6); > @@ -97,9 +139,10 @@ int base64_decode(const char *src, int srclen, u8 *dst, bool padding, enum base6 > continue; > } > } > - if (p == NULL || src[i] == 0) > + ch = base64_rev_maps[variant][(u8)src[i]]; > + if (ch == -1) > return -1; > - ac = (ac << 6) | (p - base64_table); > + ac = (ac << 6) | ch; > bits += 6; > if (bits >= 8) { > bits -= 8;