From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 8B152CAC5B5 for ; Sun, 28 Sep 2025 06:37:29 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender:List-Subscribe:List-Help :List-Post:List-Archive:List-Unsubscribe:List-Id:In-Reply-To: Content-Transfer-Encoding:Content-Type:MIME-Version:References:Message-ID: Subject:Cc:To:From:Date:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=ubpMuP7II5ikdJvb/5K0JndDDuxFjf1Jocs0VnGSPuA=; b=WBvDC0FavhuvSQTRpxIXHF7RpO 5q/hmBPX3O5pXFxjOKOOulj/87FjoYuIwdqqeEC7JaRHGBXPrOUUc/1ERiPA4suu6pfou67CGSqG7 v45HeB+1mrKcnWHHvymzdUrg/ruUHYoZH+gnNlERzokID8xNQoCIPjFX1rG+DKTQTA+XuaO4opbUZ WFLpOy7FdA0x/I7GBw1Euj/pvb/eugLYGA/iBpoZNYJ1XV4CIILrkKEHMxaIqzVk20/JyQOSl6jlL 4nWLOsqhGlG73gA1cb4qIa06Xqmyua2NopBl2wv3pWQNT7lVIE1sCXNQdA4azpDMFSinUJr3588xd 8AggWPrA==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.98.2 #2 (Red Hat Linux)) id 1v2l2E-0000000E0J3-2f6B; Sun, 28 Sep 2025 06:37:26 +0000 Received: from mail-pl1-x629.google.com ([2607:f8b0:4864:20::629]) by bombadil.infradead.org with esmtps (Exim 4.98.2 #2 (Red Hat Linux)) id 1v2l2B-0000000E0IT-39L9 for linux-nvme@lists.infradead.org; Sun, 28 Sep 2025 06:37:24 +0000 Received: by mail-pl1-x629.google.com with SMTP id d9443c01a7336-28832ad6f64so1098275ad.1 for ; Sat, 27 Sep 2025 23:37:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1759041442; x=1759646242; darn=lists.infradead.org; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:from:to :cc:subject:date:message-id:reply-to; bh=ubpMuP7II5ikdJvb/5K0JndDDuxFjf1Jocs0VnGSPuA=; b=ErM4GzaDBaPi/2S3PmecDPI2wBV0EUbdKi22ECVQHvKqs3Gid3T/rrCjaBB+SzE7VB KiD45tkekpCqMgtkceDj1W93JGYjqbhj/w44xMTUn0Qj9pDWAaypGvgmrMjHE7Lqdws8 IydesNVwnNK5zSJ4lCu//lx+Nu1KnPmvA4IpL4AjqiX9GwjQdHPEtwALEnM5KnLlaT4Y ypwsoLrjb6eOsTUk7+FgKdrl14jzRmKSU2i1Vk3y0UVkQ+pNUnjmXPjmPIb66fSfGnv8 lsCihmBdO07/9NWuw4plnGSPSc+xSYDY3S82LlKY7B225OTrel0RgVJX2AFVoBuMXAlO k3CA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1759041442; x=1759646242; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=ubpMuP7II5ikdJvb/5K0JndDDuxFjf1Jocs0VnGSPuA=; b=VmAunT6eOoO0zLKaHplGzLySq/ZZSsa+jW9NjHaBncUoS/8CKeAkmtNwq//biEv2X7 13EiNOBCI+btiaQqRVOg1MlR6/51Gj86gBEW0gpit0zgMhuD/BSG50F5bfi8ujyCQndM j3lvUmhxMyYyKf+OzHkvfw2ZbCVZUwMR81AspPAmtau6K7qUg6CuRldExdvmxKdVogiD YESh/BOc74OuqqkPk7HstDN8w/4/eP2peM/g2nyhQobpe+oxO+pzTkdtJUe+PvH2LJU9 Jwh0DtVp+wHPu91CnhtNIOUBxmTXIKwSbvP8vJ9YctvTqSgXZyNMlBoQCgC0zK/B6/3t EHoQ== X-Forwarded-Encrypted: i=1; AJvYcCVqoA0TLCriZlDOrJHMyuLAeK1bopE5XtzP6sLAi74HySeIyLypHh23NHZlmHJ+kmwwRkxqPdWp0NI9@lists.infradead.org X-Gm-Message-State: AOJu0YyGRQCoacIVlLE4DiCZLpMCmIYd/w5fsHgDOYuVsqgYbv/c/ueo bKuW/VmRevOnIsTVTYMweIAtNBQ0hAzYXFWilzucBkUWm/kkLfnCA0qz X-Gm-Gg: ASbGnct7JA8Y5JPbd1ZP/glw/TAuj5enho44Thhgp6K4BsrJzdyMQxAEUtRbKdVQOIC 7GRCS02UeFcmNq7nj44DjUCr+P0omzGg6EBY1NYBn6c4P0Xh7KZIQ8jVrp2sdAN4+0YcWGxyqwQ 9i0NNC7EKFox61TQsikKoO6uKht0V8a2pEmqR2rUUuCyPOhSKipZK3QPuG0EdYBPEhkLMV9ItEO 250MDmiRvoQHHpsk89PkE+2h6RzH3Ptpmtb9NvIv9wtk4FRZ2KodTw//R98UkR5vNuYMuOrSXqe +YCvt4/lSKPxupcTuOoEZByxOkv9/3+3jw/lQfsU9GQYy55wSwnmqJD9a6QQXGpWMxehY+QPvKd uFZJTZT3yBzhhM0RUzxf7yPqijcWqfHE1/nay0reTFEtDZYj6H3KpG4apUS3YHjGXoJ+tkBU= X-Google-Smtp-Source: AGHT+IHkOtF5578eCGnpU9nMgKsLzoxz/q9Ij/omuAZkxTc208StOe4e409+y8TjhW4sjjzmHwt/2w== X-Received: by 2002:a17:902:e54a:b0:270:b6d5:f001 with SMTP id d9443c01a7336-27ed4a0d542mr138016595ad.23.1759041442474; Sat, 27 Sep 2025 23:37:22 -0700 (PDT) Received: from visitorckw-System-Product-Name ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-27ed66cf9d3sm97700695ad.15.2025.09.27.23.37.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 27 Sep 2025 23:37:22 -0700 (PDT) Date: Sun, 28 Sep 2025 14:37:17 +0800 From: Kuan-Wei Chiu To: Caleb Sander Mateos Cc: Guan-Chun Wu <409411716@gms.tku.edu.tw>, akpm@linux-foundation.org, 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, xiubli@redhat.com Subject: Re: [PATCH v3 2/6] lib/base64: Optimize base64_decode() with reverse lookup tables Message-ID: References: <20250926065235.13623-1-409411716@gms.tku.edu.tw> <20250926065556.14250-1-409411716@gms.tku.edu.tw> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20250927_233723_793951_DACB049A X-CRM114-Status: GOOD ( 25.21 ) X-BeenThere: linux-nvme@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "Linux-nvme" Errors-To: linux-nvme-bounces+linux-nvme=archiver.kernel.org@lists.infradead.org On Fri, Sep 26, 2025 at 04:33:12PM -0700, Caleb Sander Mateos wrote: > On Thu, Sep 25, 2025 at 11:59 PM 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 -> ~75ns (~20.4x) > > 1KB ~27726ns -> ~1165ns (~23.8x) > > > > 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> > > --- > > lib/base64.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++---- > > 1 file changed, 61 insertions(+), 5 deletions(-) > > > > diff --git a/lib/base64.c b/lib/base64.c > > index 1af557785..b20fdf168 100644 > > --- a/lib/base64.c > > +++ b/lib/base64.c > > @@ -21,6 +21,63 @@ static const char base64_tables[][65] = { > > [BASE64_IMAP] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+,", > > }; > > > > +static const s8 base64_rev_tables[][256] = { > > + [BASE64_STD] = { > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 62, -1, -1, -1, 63, > > + 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, -1, -1, -1, -1, -1, -1, > > + -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, > > + 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1, > > + -1, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, > > + 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + }, > > + [BASE64_URLSAFE] = { > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 62, -1, -1, > > + 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, -1, -1, -1, -1, -1, -1, > > + -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, > > + 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, 63, > > + -1, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, > > + 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + }, > > + [BASE64_IMAP] = { > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 62, 63, -1, -1, -1, > > + 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, -1, -1, -1, -1, -1, -1, > > + -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, > > + 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1, > > + -1, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, > > + 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, > > + }, > > Do we actually need 3 separate lookup tables? It looks like all 3 > variants agree on the value of any characters they have in common. So > we could combine them into a single lookup table that would work for a > valid base64 string of any variant. The only downside I can see is > that base64 strings which are invalid in some variants might no longer > be rejected by base64_decode(). Ah, David also mentioned this earlier, but I forgot about it while writing the code. Sorry for that. I'll rectify it. Regards, Kuan-Wei > > > +}; > > + > > /** > > * base64_encode() - Base64-encode some binary data > > * @src: the binary data to encode > > @@ -82,11 +139,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 (src[i] == '=') { > > ac = (ac << 6); > > bits += 6; > > @@ -94,9 +149,10 @@ int base64_decode(const char *src, int srclen, u8 *dst, bool padding, enum base6 > > bits -= 8; > > continue; > > } > > - if (p == NULL || src[i] == 0) > > + ch = base64_rev_tables[variant][(u8)src[i]]; > > + if (ch == -1) > > Checking for < 0 can save an additional comparison here. > > Best, > Caleb > > > return -1; > > - ac = (ac << 6) | (p - base64_table); > > + ac = (ac << 6) | ch; > > bits += 6; > > if (bits >= 8) { > > bits -= 8; > > -- > > 2.34.1 > > > >