From nobody Thu Dec 18 03:29:51 2025 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) (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 16CC723C50F for ; Fri, 14 Nov 2025 06:01:14 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763100077; cv=none; b=s8jEMbqrgaONUGNuTs2DukCgc/o1rxqd0vmjKzEI/IwM8Z2yKN3LOuOBRayulYUK6yApvh6dGIQfmlg1IxIJj8VRGdg3eLrqXbQusUnuFyfwRFfApQhHHhe83vlZP7xMQTfM2+SlB0YS8hrjvsmHncHZgMYx6Ps3xxGxjFPtk1M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763100077; c=relaxed/simple; bh=ebfhLZNEl5pO72lYrO9Xn1y4JHTAnC4DTnDbTXJruzM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=TU6G/lqljzsI1FIy942W3MKBCcXrhVf6cuKEa3hgKUy7nUIIgWuWwbhCQvyhMaLZsLz1NPVKpJaESkoAvkqoBd2fmYJjxD9uyPx3J4D5QZq5Kqtn/Z8kTmx9dbzvC/WZRdcl4Bj0NcbQQyNnXpQQdaJAUbFoRhfBw61bXfmet5Q= 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=cMVPcvCX; arc=none smtp.client-ip=209.85.210.181 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="cMVPcvCX" Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-7aae5f2633dso1888428b3a.3 for ; Thu, 13 Nov 2025 22:01:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gms-tku-edu-tw.20230601.gappssmtp.com; s=20230601; t=1763100074; x=1763704874; 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=lWS11xsgkFrNsAXlptIvYpGHMFNUcuv3AuLz0xI70Ao=; b=cMVPcvCXnMM511FrlzdK+cADV1Q9BS4r9uxsnAa1VKlsZ21c/NSk+17XzgOaPoEmy/ PwWmkqlJ4R5NOGUqUjjgam5heJ3tsMz5JvYrlQDpmVP3tleLwZ1/qa5rx1A04Q8iT4bD RbVEt8of6EtSRmz4ZXXtU+BAuBoSYw9GenaPfggwKN7qV/tzknII4JIYRuo6c053WDyn IP1/zaIilFE25RErv6XQ9SZh1VOoz11WT5QKXQUjwc4835r/qmSh63+o5FyRaNqAUx6o /ZTIElouDRm3r3SNr0ydUGzkqK5Y2L4yj2du4ET5XJVYEfYa3Xdf5xDgXa7t9U8/T/xL bUcw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763100074; x=1763704874; 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=lWS11xsgkFrNsAXlptIvYpGHMFNUcuv3AuLz0xI70Ao=; b=Zx1YC5G+AR+jt16FMWfbKpD+YVi7fOxQ8NgRjUDoUseJCQmB0hMbE9yWKgV+VrPd4B 04W85clawNDGKIC46MmXJssTPffBZ8qUykOjqr65X+Lpnop7zmPJM3J2CHnOIk4szQWK VwvXJLFsflWigtYG/0BYhvgaClXzvJ+hgzogahOshKD/SOxZ+NhJ49cp2XOo+qbMzDzL HNHIy4TpGugXkm9AcNSts7D/Y7rOMcYSbJKFfgRW1gRQ4pzjPPP7YplJ6xt09VIh5Fo5 LyW29wbjCi5dyYXuzAAue2ketmY9nIhBqtRI14PQMPYFTTM6dEvjNSwGyWQDaJ091YQs OXNg== X-Forwarded-Encrypted: i=1; AJvYcCV/TwpZmEHxqIoSyKjCPs6756kMDBzOWkqkxxs5AKW1z83SDS37ujKFI9zsHHPDvYWExDUFZAzBNXIHajM=@vger.kernel.org X-Gm-Message-State: AOJu0YwE/pspFee2ggABeMLlHO3ImY4czmJ22rPj/2NhI961Iip+rgx8 E+iiLRcWQTc2Kq/p0Tp04fZ/26WC8QzoZqB2CDfEbcOkYU2DIGb4qK6Ti5fkr4WdezU= X-Gm-Gg: ASbGncux0bFivZO4lyRXTzSH+VmjLX/0kZVUJYsXyZBtyCifqq81Iw1fMMcVXQ5gjwP 6mQNkBG6HLWabqWWzj1Qzt1a0MK3V3Kb3X6CVQvD0yDdt0yWzd+CkS/199r1Tr4SDOm1uYFPt89 phQkTx+ClUzEutAbXT0FKQLSgVFeik9gvynPKJfYbdzP6Y3cLboo2JKziMGiNnPrMxd4E+FW7w4 MwXR1YphQ++BFlquq7S1ZS+tItRp/YBQYeTYgE7Lct5IVQLvXUMhvuwyOmWLNC3OmXNibARMsva 8x84uJvKF+ifDJlOFxwRnD8mEg1jsoUGv9nNXnt06wIIQZs5nBDXmz2qDi8hKeAnVoan1K32ytX 4xCcS8rZ+53YjuIJFATHqqBMyIRoeLrL9F0JhA0PizZ/qflSDuiy+R/EkyKN0a4qTjI2k2lRJ1m GLcY+4/ESkhlvi0y32iSwKX3m/cFo/lXa5+KQ= X-Google-Smtp-Source: AGHT+IH5zqaJvOCHGyW2FJR2JlFHMBKlTKF05FN81/22NWKlZaSd+Pgu/afzXFlbWF1Pxh5Ir24tyA== X-Received: by 2002:a05:6a00:198d:b0:7b8:9d86:6d44 with SMTP id d2e1a72fcca58-7ba3a0be249mr2401481b3a.9.1763100074344; Thu, 13 Nov 2025 22:01:14 -0800 (PST) Received: from wu-Pro-E500-G6-WS720T.. ([2001:288:7001:2703:22d2:323c:497d:adbd]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7b924be368bsm4075198b3a.9.2025.11.13.22.01.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 13 Nov 2025 22:01:14 -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 2/6] lib/base64: Optimize base64_decode() with reverse lookup tables Date: Fri, 14 Nov 2025 14:01:07 +0800 Message-Id: <20251114060107.89026-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" 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] =3D { [BASE64_IMAP] =3D "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01= 23456789+,", }; =20 +/** + * 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] =3D (v) >=3D 'A' && (v) <=3D 'Z' ? (v) - 'A' \ + : (v) >=3D 'a' && (v) <=3D 'z' ? (v) - 'a' + 26 \ + : (v) >=3D '0' && (v) <=3D '9' ? (v) - '0' + 52 \ + : (v) =3D=3D (ch_62) ? 62 : (v) =3D=3D (ch_63) ? 63 : -1 +/** + * Recursive macros to generate multiple Base64 reverse mapping table entr= ies. + * 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_AR= GS__) + +#define BASE64_REV_INIT(ch_62, ch_63) { \ + [0 ... 0x1f] =3D -1, \ + INIT_32(0x20, ch_62, ch_63), \ + INIT_32(0x40, ch_62, ch_63), \ + INIT_32(0x60, ch_62, ch_63), \ + [0x80 ... 0xff] =3D -1 } + +static const s8 base64_rev_maps[][256] =3D { + [BASE64_STD] =3D BASE64_REV_INIT('+', '/'), + [BASE64_URLSAFE] =3D BASE64_REV_INIT('-', '_'), + [BASE64_IMAP] =3D 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 =3D 0; int i; u8 *bp =3D dst; - const char *base64_table =3D base64_tables[variant]; + s8 ch; =20 for (i =3D 0; i < srclen; i++) { - const char *p =3D strchr(base64_table, src[i]); if (padding) { if (src[i] =3D=3D '=3D') { ac =3D (ac << 6); @@ -97,9 +139,10 @@ int base64_decode(const char *src, int srclen, u8 *dst,= bool padding, enum base6 continue; } } - if (p =3D=3D NULL || src[i] =3D=3D 0) + ch =3D base64_rev_maps[variant][(u8)src[i]]; + if (ch =3D=3D -1) return -1; - ac =3D (ac << 6) | (p - base64_table); + ac =3D (ac << 6) | ch; bits +=3D 6; if (bits >=3D 8) { bits -=3D 8; --=20 2.34.1