base_n.hpp

// Copyright Take Vos 2020-2021.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt)
 
#include "../byte_string.hpp"
#include "../required.hpp"
#include "../assert.hpp"
#include "../check.hpp"
#include <span>
#include <string>
#include <cstdint>
#include <array>
#include <string>
#include <string_view>
 
#pragma once
 
namespace tt {
namespace detail {
 
struct base_n_alphabet {
    long long radix;
    bool case_insensitive;
    char padding_char;
    std::array<int8_t, 256> int_from_char_table = {};
    std::array<char, 127> char_from_int_table = {};
 
    template<size_t StringLength>
    constexpr base_n_alphabet(
        char const (&str)[StringLength],
        bool case_insensitive = StringLength <= 33,
        char padding_char = '\0') noexcept :
        radix(narrow_cast<long long>(StringLength - 1)), case_insensitive(case_insensitive), padding_char(padding_char)
    {
        static_assert(StringLength < 128);
 
        // Mark the int_from_char_table to have invalid characters.
        for (long long i = 0; i != 256; ++i) {
            int_from_char_table[i] = -2;
        }
 
        // Mark white-space in the int_from_char_table as white-space.
        int_from_char_table[narrow_cast<size_t>(' ')] = -1;
        int_from_char_table[narrow_cast<size_t>('\t')] = -1;
        int_from_char_table[narrow_cast<size_t>('\r')] = -1;
        int_from_char_table[narrow_cast<size_t>('\n')] = -1;
        int_from_char_table[narrow_cast<size_t>('\f')] = -1;
 
        if (padding_char != 0) {
            int_from_char_table[narrow_cast<size_t>(padding_char)] = -1;
        }
 
        for (long long i = 0; i != radix; ++i) {
            auto c = str[i];
            char_from_int_table[i] = c;
 
            int_from_char_table[narrow_cast<size_t>(c)] = narrow_cast<int8_t>(i);
            if constexpr (StringLength <= 33) {
                // Add an extra entry for case folded form.
                if (c >= 'a' && c <= 'z') {
                    int_from_char_table[narrow_cast<size_t>((c - 'a') + 'A')] = narrow_cast<int8_t>(i);
                } else if (c >= 'A' && c <= 'Z') {
                    int_from_char_table[narrow_cast<size_t>((c - 'A') + 'a')] = narrow_cast<int8_t>(i);
                }
            }
        }
    }
 
    constexpr char char_from_int(int8_t x) const noexcept
    {
        tt_axiom(x < radix);
        return char_from_int_table[x];
    }
 
    constexpr int8_t int_from_char(char c) const noexcept
    {
        return int_from_char_table[narrow_cast<size_t>(c)];
    }
};
 
constexpr auto base2_alphabet = base_n_alphabet{"01"};
 
constexpr auto base8_alphabet = base_n_alphabet{"01234567"};
 
constexpr auto base10_alphabet = base_n_alphabet{"0123456789"};
 
constexpr auto base16_alphabet = base_n_alphabet{"0123456789ABCDEF"};
 
constexpr auto base32_rfc4648_alphabet = base_n_alphabet{"ABCDEFGHIJKLMNOPQRSTUVWXYZ234567"};
 
constexpr auto base32hex_rfc4648_alphabet = base_n_alphabet{"0123456789ABCDEFGHIJKLMNOPQRSTUV"};
 
constexpr auto base64_rfc4648_alphabet =
    base_n_alphabet{"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/", false, '='};
 
constexpr auto base64url_rfc4648_alphabet =
    base_n_alphabet{"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_", false, '='};
 
constexpr auto base85_rfc1924_alphabet =
    base_n_alphabet{"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~"};
 
constexpr auto base85_btoa_alphabet =
    base_n_alphabet{"!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstu"};
 
} // namespace detail
 
template<detail::base_n_alphabet Alphabet, int CharsPerBlock, int BytesPerBlock>
class base_n {
public:
    static constexpr detail::base_n_alphabet alphabet = Alphabet;
    static constexpr char padding_char = alphabet.padding_char;
    static constexpr long long radix = alphabet.radix;
    static constexpr long long bytes_per_block = BytesPerBlock;
    static constexpr long long chars_per_block = CharsPerBlock;
    static_assert(bytes_per_block != 0, "radix must be 16, 32, 64 or 85");
    static_assert(chars_per_block != 0, "radix must be 16, 32, 64 or 85");
 
    template<typename T>
    static constexpr T int_from_char(char c) noexcept
    {
        return narrow_cast<T>(alphabet.int_from_char(c));
    }
 
    template<typename T>
    static constexpr char char_from_int(T x) noexcept
    {
        return alphabet.char_from_int(narrow_cast<int8_t>(x));
    }
 
    template<typename ItIn, typename ItOut>
    static constexpr void encode(ItIn ptr, ItIn last, ItOut output)
    {
        long long byte_index_in_block = 0;
        long long block = 0;
 
        while (ptr != last) {
            // Construct a block in big endian.
            ttlet shift = 8 * ((bytes_per_block - 1) - byte_index_in_block);
            block |= static_cast<long long>(*(ptr++)) << shift;
 
            if (++byte_index_in_block == bytes_per_block) {
                encode_block(block, bytes_per_block, output);
                block = 0;
                byte_index_in_block = 0;
            }
        }
 
        if (byte_index_in_block != 0) {
            encode_block(block, byte_index_in_block, output);
        }
    }
 
    template<typename ItIn>
    static constexpr std::string encode(ItIn first, ItIn last) noexcept
    {
        std::string r;
        encode(first, last, std::back_inserter(r));
        return r;
    }
 
    static constexpr std::string encode(std::span<std::byte const> bytes) noexcept
    {
        return encode(begin(bytes), end(bytes));
    }
 
    template<typename ItIn, typename ItOut>
    static constexpr ItIn decode(ItIn ptr, ItIn last, ItOut output) noexcept
    {
        int char_index_in_block = 0;
        long long block = 0;
 
        for (; ptr != last; ++ptr) {
            ttlet digit = int_from_char<long long>(*ptr);
            if (digit == -1) {
                // Whitespace is ignored.
                continue;
 
            } else if (digit == -2) {
                // Other character means end
                return ptr;
 
            } else {
                block *= radix;
                block += digit;
 
                if (++char_index_in_block == chars_per_block) {
                    decode_block(block, chars_per_block, output);
                    block = 0;
                    char_index_in_block = 0;
                }
            }
        }
 
        if (char_index_in_block != 0) {
            // pad the block with zeros.
            for (auto i = char_index_in_block; i != chars_per_block; ++i) {
                block *= radix;
            }
            decode_block(block, char_index_in_block, output);
        }
        return ptr;
    }
 
    static constexpr bstring decode(std::string_view str)
    {
        auto r = bstring{};
        auto i = decode(begin(str), end(str), std::back_inserter(r));
        tt_parse_check(i == end(str));
        return r;
    }
 
private:
    template<typename ItOut>
    static constexpr void encode_block(long long block, long long nr_bytes, ItOut output) noexcept
    {
        ttlet padding = bytes_per_block - nr_bytes;
 
        // Construct a block in little-endian, using easy division/modulo.
        auto char_block = std::string{};
        for (long long i = 0; i != chars_per_block; ++i) {
            ttlet v = block % radix;
            block /= radix;
 
            if (i < padding) {
                tt_assume(v != 0);
                if (padding_char != 0) {
                    char_block += padding_char;
                }
            } else {
                char_block += char_from_int(v);
            }
        }
 
        // A block should be output as a big-endian radix-number.
        std::copy(rbegin(char_block), rend(char_block), output);
    }
 
    template<typename ItOut>
    static constexpr void decode_block(long long block, long long nr_chars, ItOut output) noexcept
    {
        ttlet padding = chars_per_block - nr_chars;
 
        // Construct a block in little-endian, using easy division/modulo.
        for (long long i = 0; i != (bytes_per_block - padding); ++i) {
            ttlet shift = 8 * ((bytes_per_block - 1) - i);
            ttlet byte = static_cast<std::byte>((block >> shift) & 0xff);
 
            *(output++) = byte;
        }
 
        // The output data will not contain the padding.
    }
};
 
// Alphabet, CharsPerBlock, BytesPerBlock
using base2 = base_n<detail::base2_alphabet, 8, 1>;
using base8 = base_n<detail::base8_alphabet, 8, 3>;
using base16 = base_n<detail::base16_alphabet, 2, 1>;
using base32 = base_n<detail::base32_rfc4648_alphabet, 8, 5>;
using base32hex = base_n<detail::base32hex_rfc4648_alphabet, 8, 5>;
using base64 = base_n<detail::base64_rfc4648_alphabet, 4, 3>;
using base64url = base_n<detail::base64url_rfc4648_alphabet, 4, 3>;
using base85 = base_n<detail::base85_rfc1924_alphabet, 5, 4>;
using ascii85 = base_n<detail::base85_btoa_alphabet, 5, 4>;
 
} // namespace tt