Open Bouska opened 3 years ago
Yes, it exactly needs a decode_table to improve its performance, try this to calculate decode_table in compile-time instead of manually.
static constexpr std::string_view encode_table = {
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz"
"0123456789"
"+/" };
static constexpr std::string_view encode_table_url = {
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz"
"0123456789"
"-_" };
static constexpr size_t max_encode_char = static_cast<size_t>('z') + 1;
static constexpr size_t decode_placeholder = 0xff;
static constexpr std::array<size_t, max_encode_char> generate_decode_table(std::string_view str)
{
std::array<size_t, max_encode_char> ret{};
ret.fill(decode_placeholder);
std::for_each(str.begin(), str.end(), [&ret, offset = 0](const char& ch) mutable constexpr
{ ret.at(static_cast<size_t>(ch)) = offset++; });
return ret;
}
static constexpr std::array<size_t, max_encode_char> decode_table = generate_decode_table(encode_table);
static size_t pos_of_char(const char chr)
{
//
// Return the position of chr within base64_encode()
//
if (static_cast<size_t>(chr) >= max_encode_char)
throw std::runtime_error("Input is not valid base64-encoded data.");
else if (auto val = decode_table.at(static_cast<size_t>(chr)); val == decode_placeholder)
throw std::runtime_error("Input is not valid base64-encoded data.");
else
return val;
}
Incorporated lookup table in https://github.com/heifner/base64
According to "measure_time.cpp" benchmark, decoding is 2.65 (g++ -O0) / 2.55 (g++ -O2) times slower than encoding. One of the bottleneck of decoding comes from doing several comparisons and calculating the value for each decoded character (
pos_of_char()
function). Replacing the comparison + calculation by a lookup table (like in the encoding) improves the decoding speed, making it only 2.22 (g++ -O0) / 1.36 (g++ -O2) times slower than encoding.