On Fri, 26 Sep 2025 14:55:56 +0800 Guan-Chun Wu <[email protected]> wrote:
> From: Kuan-Wei Chiu <[email protected]> > > 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 <[email protected]> > Co-developed-by: Guan-Chun Wu <[email protected]> > Signed-off-by: Guan-Chun Wu <[email protected]> > --- > 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, > + }, Using: [BASE64_STD] = { [0 ... 255] = -1, ['A'] = 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, ['a'] = 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 48, 50, 51, ['0'] = 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, ['+'] = 62, ['/'] = 63}; would be more readable. (Assuming no one has turned on a warning that stops you defaulting the entries to -1.) The is also definitely scope for a #define to common things up. Even if it has to have the values for all the 5 special characters (-1 if not used) rather than the characters for 62 and 63. David > + [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, > + }, > +}; > + > /** > * 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) > return -1; > - ac = (ac << 6) | (p - base64_table); > + ac = (ac << 6) | ch; > bits += 6; > if (bits >= 8) { > bits -= 8;
