5
\$\begingroup\$

I have always been amazed at the number of things you can do in a constexpr function, yet I have not thought much about them until recently when I found out that c++20 added the ability to pass user-defined types as a template parameter. Meaning there is a way to pass strings as a template parameter which made me think couldn't you make a compile-time base64 encoder. As a result, I decided to make a compile-time base 64 encoder.

Here is the code: base64.cc

#include <iostream>
#include <cstring>
namespace base64
{
template <std::size_t N>
struct FixedString
{
    char buf[N + 1] {};
    constexpr FixedString() = default;
    constexpr FixedString(char const *s)
    {
        for (std::size_t i = 0; i != N; ++i)
            buf[i] = s[i];
    }
    template <std::size_t S>
    constexpr FixedString(FixedString<S> const &other)
    {
        for (std::size_t i = (S > N ? N : S); i--;)
            buf[i] = other.buf[i];
    }
    auto constexpr operator == (FixedString const &other) const
    {
        for(std::size_t i = 0; i < N; ++i)
        {
            if(buf[i]!=other[i])
                return false;
        }
        return true;
    }
    constexpr operator char const *() const { return buf; }
    constexpr operator char *() { return buf; }
    std::size_t constexpr size() const { return N; }
};

template <std::size_t N>
FixedString(char const (&)[N]) -> FixedString < N - 1 >;

template <FixedString string>
auto constexpr decode()
{
    std::size_t constexpr string_size = string.size();
    auto constexpr find_padding = [string_size]() {
        std::size_t i;
        for (i = 0; i < string_size; ++i)
            if (string[i] == '=')
                break;
        return i;
    };
    FixedString <find_padding() * 3 / 4 > result;
    auto constexpr convert_char = [](auto const & ch) {
        if (ch >= 'A' && ch <= 'Z')
            return ch - 65;
        else if (ch >= 'a' && ch <= 'z')
            return ch - 71;
        else if (ch >= '0')
            return ch + 4;
        else
            return ch == '+' ? 62 : 63;
    };
    for (std::size_t i = 0, j = 0; i < string_size; i += 4, j += 3)
    {
        char bytes[3] = {
            static_cast<char>(convert_char(string[i]) << 2
            | convert_char(string[i + 1]) >> 4),
            static_cast<char>(convert_char(string[i + 1]) << 4
            | convert_char(string[i + 2]) >> 2),
            static_cast<char>(convert_char(string[i + 2]) << 6
            | convert_char(string[i + 3])),
        };
        result[j] = bytes[0];
        result[j + 1] = bytes[1];
        if (string[i + 3] != '=')
            result[j + 2] = bytes[2];
    }
    return result;
}

template <FixedString string>
auto constexpr encode()
{
    std::size_t constexpr string_size = string.size();
    std::size_t constexpr result_size_no_padding = (string_size * 4 + 2) / 3;
    std::size_t constexpr result_size = (result_size_no_padding + 3) & (-4);
    std::size_t constexpr padding_size = result_size - result_size_no_padding;
    FixedString <(string_size + 2) / 3 * 3> constexpr string_with_padding = string;
    FixedString<result_size> result;
    auto constexpr convert_num = [](auto const & num) {
        if (num < 26)
            return static_cast<char>(num + 65);
        else if (num > 25 && num < 52)
            return static_cast<char>(num + 71);
        else if (num > 51)
            return static_cast<char>(num - 4);
        else
            return num == 62 ? '+' : '/';
    };
    for (std::size_t i = 0, j = 0; i < string_size; i += 3, j += 4)
    {
        /* convert every 3 bytes to 4 6 bit numbers
         * 8 * 3 = 24
         * 6 * 4 = 24
         */
        char bytes[4] = {
            static_cast<char>(string_with_padding[i] >> 2),
            static_cast<char>((string_with_padding[i]
            & 3) << 4
            | string_with_padding[i + 1] >> 4),
            static_cast<char>((string_with_padding[i + 1] & 15) << 2
            | string_with_padding[i + 2] >> 6),
            static_cast<char>(string_with_padding[i + 2] & 63)
        };
        result[j] = convert_num(bytes[0]);
        result[j + 1] = convert_num(bytes[1]);
        result[j + 2] = convert_num(bytes[2]);
        result[j + 3] = convert_num(bytes[3]);
    }
    for (std::size_t i = 0; i < padding_size; ++i)
        result[result_size_no_padding + i] = '=';
    return result;
}
} // namespace base64

/* here is a test */
int main()
{

    auto constexpr input_text = base64::FixedString { "Man is distinguished, not only by his reason, but by this singular passion from other animals, \
which is a lust of the mind, that by a perseverance of delight in the continued and indefatigable \
generation of knowledge, exceeds the short vehemence of any carnal pleasure."};
    auto constexpr encoded = base64::encode<input_text>();
    auto constexpr decoded = base64::decode<encoded>();
    static_assert(decoded == input_text);
    std::cout << encoded << '\n';
}
\$\endgroup\$
3
\$\begingroup\$

Overall the code is quite well written, and it's an interesting program.

  1. The biggest improvement that I think can be made is avoiding all the raw loops. From c++20, many of the algorithms are constexpr, which means the following member functions could be one liners:
constexpr FixedString(char const* s)
{
    std::copy(s, s + N, buf);
}

template <std::size_t S>
constexpr FixedString(FixedString<S> const& other)
{
    std::copy(other.buf, other.buf + std::min(S, N), buf);
}

auto constexpr operator==(FixedString const& other) const
{
    return std::equal(buf, buf + N, other.buf);
}

There is a similar example in the decode function, where the find_padding lambda could be:

auto constexpr find_padding = [string_size]() {
    return std::distance(string.buf, 
               std::find(string.buf, string.buf + string_size, '='));
};

and in the encode function, this code:

result[j] = convert_num(bytes[0]);
result[j + 1] = convert_num(bytes[1]);
result[j + 2] = convert_num(bytes[2]);
result[j + 3] = convert_num(bytes[3]);

could be replaced by the shorter:

std::transform(bytes, bytes + 4, result.buf + j, convert_num);

and this loop:

for (std::size_t i = 0; i < padding_size; ++i)
    result[result_size_no_padding + i] = '=';

could be replaced by:

std::fill_n(result.buf + result_size_no_padding, padding_size, '=');
  1. You have used clear names for all your variables, and functions, but snippets like the following:
if (ch >= 'A' && ch <= 'Z')

should be named as well (even if it's used in only one place). Ideally, you would use std::isupper, but it's not constexpr, so that's not possible. However, it's trivial to write your own named function that is constexpr. In particular, it would be much more readable to have names for snippets like:

if (num > 25 && num < 52)

for example, something like reverse_is_upper would make sense?

  1. As it stands, I find the encode and decode functions a little long (though this is reduced by removing the raw loops). Still, the lambda expressions could be moved out of the *code functions and used as needed.

  2. This is a relatively minor point, but I'm not a fan of the implicit conversions to char* from FixedString. The primary advantage seems to be that you avoid having to write .buf everywhere, but the negative impacts of implicit conversions outweigh this benefit (as the code increases, it becomes increasingly easy to make a subtle mistake because of this). Also, it's being used in main to allow streaming like this:

std::cout << encoded << '\n';

but this is better solved by overloading operator<< for FixedString instead.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.