Base64 Sequence Encoding
(utilities/base64.hpp)

• View this file on GitHub
• Last update: 2026-08-11 14:01:29+09:00
• Include: #include "utilities/base64.hpp"

Overview

This header packs a sequence of fixed-width nonnegative integers into a compact Base64 string. It is intended for embedding precomputed tables, test data, or other numeric constants directly in competitive-programming source code.

#include "utilities/base64.hpp"

All names are in m1une::utilities. The alphabet is the RFC 4648 alphabet A-Z, a-z, 0-9, +, /, exposed as base64_alphabet. Bits are written most-significant first. The final Base64 digit is padded with zero bits, but = characters are omitted to keep the result short. Consequently, encoding bytes with bit_width = 8 produces ordinary unpadded Base64.

Interface

template <class Sequence>
std::string to_base64(const Sequence& values, int bit_width);

template <std::integral Integer>
std::optional<std::vector<Integer>> checked_from_base64(
    std::string_view encoded,
    std::size_t count,
    int bit_width);

template <std::integral Integer>
std::vector<Integer> from_base64(
    std::string_view encoded,
    std::size_t count,
    int bit_width);

The sequence value type and Integer may be any standard integral type except bool. Values must be nonnegative and fit in bit_width bits. The width must be between 1 and the number of non-sign bits in the integer type.

Function	Description	Complexity
to_base64(values, bit_width)	Packs all values and returns the unpadded Base64 text.	$O(N\lceil B/6\rceil)$ time and $O(\lceil NB / 6\rceil)$ output memory.
checked_from_base64<Integer>(text, count, bit_width)	Decodes exactly count values, or returns nullopt if the text has an invalid character, wrong length, or nonzero padding bits.	$O(N\lceil B/6\rceil)$ time and $O(N)$ output memory.
from_base64<Integer>(text, count, bit_width)	Decodes a known-valid embedded string; validity is asserted.	$O(N\lceil B/6\rceil)$ time and $O(N)$ output memory.

Here $N$ is the sequence length and $B$ is bit_width. The implementation processes up to six bits per inner-loop iteration, so its running time is also linear in the encoded size.

The decoder needs count because an unpadded final character does not uniquely identify how many data bits it contains. For example, both a one-value sequence with width 5 and one with width 6 occupy one Base64 character.

Example

For values below 64, use six bits per value. Each number then occupies exactly one character:

#include "utilities/base64.hpp"

#include <iostream>
#include <vector>

int main() {
    std::vector<int> original = {3, 1, 4, 1, 5, 9};
    std::string embedded = m1une::utilities::to_base64(original, 6);
    // embedded is "DBEBFJ"; paste that string into the submitted program.

    std::vector<int> restored =
        m1une::utilities::from_base64<int>("DBEBFJ", 6, 6);
    for (int value : restored) std::cout << value << ' ';
}

Choose the smallest fixed width that contains every value. For example, values in [0, 1024) need 10 bits each, so every three values occupy exactly five Base64 characters.

Verified with

• verify/utilities/base64.test.cpp

Code

#ifndef M1UNE_UTILITIES_BASE64_HPP
#define M1UNE_UTILITIES_BASE64_HPP 1

#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#include <optional>
#include <ranges>
#include <string>
#include <string_view>
#include <type_traits>
#include <vector>

namespace m1une {
namespace utilities {

inline constexpr std::string_view base64_alphabet =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

namespace detail {

inline int base64_digit(char character) noexcept {
    if ('A' <= character && character <= 'Z') return character - 'A';
    if ('a' <= character && character <= 'z') return character - 'a' + 26;
    if ('0' <= character && character <= '9') return character - '0' + 52;
    if (character == '+') return 62;
    if (character == '/') return 63;
    return -1;
}

template <class Integer>
concept Base64Integer =
    std::integral<Integer> &&
    (!std::same_as<std::remove_cv_t<Integer>, bool>);

}  // namespace detail

// Packs fixed-width nonnegative integers, most-significant bit first. The last
// Base64 digit is zero-padded on the right; '=' padding is intentionally omitted.
template <class Sequence>
requires std::ranges::input_range<const Sequence&> &&
         detail::Base64Integer<std::ranges::range_value_t<Sequence>>
std::string to_base64(const Sequence& values, int bit_width) {
    using Integer = std::ranges::range_value_t<Sequence>;
    using Unsigned = std::make_unsigned_t<Integer>;
    constexpr int digits = std::numeric_limits<Integer>::digits;

    assert(1 <= bit_width && bit_width <= digits);
    if (bit_width < 1 || bit_width > digits) return {};

    std::string encoded;
    if constexpr (std::ranges::sized_range<const Sequence&>) {
        std::size_t count = static_cast<std::size_t>(std::ranges::size(values));
        constexpr std::size_t size_limit =
            std::numeric_limits<std::size_t>::max();
        if (count <= (size_limit - 5) / static_cast<unsigned>(bit_width)) {
            encoded.reserve((count * static_cast<unsigned>(bit_width) + 5) / 6);
        }
    }
    unsigned buffer = 0;
    int buffered_bits = 0;

    for (Integer value : values) {
        if constexpr (std::signed_integral<Integer>) {
            assert(value >= 0);
            if (value < 0) return {};
        }
        Unsigned unsigned_value = static_cast<Unsigned>(value);
        if (bit_width < digits) {
            assert((unsigned_value >> bit_width) == 0);
            if ((unsigned_value >> bit_width) != 0) return {};
        }

        int remaining_bits = bit_width;
        while (remaining_bits > 0) {
            int take = std::min(6 - buffered_bits, remaining_bits);
            int shift = remaining_bits - take;
            unsigned mask = (1U << take) - 1;
            unsigned part = static_cast<unsigned>((unsigned_value >> shift) & mask);
            buffer = (buffer << take) | part;
            buffered_bits += take;
            remaining_bits -= take;

            if (buffered_bits == 6) {
                encoded.push_back(base64_alphabet[buffer]);
                buffer = 0;
                buffered_bits = 0;
            }
        }
    }

    if (buffered_bits != 0) {
        encoded.push_back(base64_alphabet[buffer << (6 - buffered_bits)]);
    }
    return encoded;
}

// Returns nullopt unless encoded is the canonical encoding of exactly count
// values with the requested bit width.
template <detail::Base64Integer Integer>
std::optional<std::vector<Integer>> checked_from_base64(
    std::string_view encoded, std::size_t count, int bit_width) {
    constexpr int digits = std::numeric_limits<Integer>::digits;
    if (bit_width < 1 || bit_width > digits) return std::nullopt;

    constexpr std::size_t size_limit = std::numeric_limits<std::size_t>::max();
    if (count > (size_limit - 5) / static_cast<unsigned>(bit_width)) {
        return std::nullopt;
    }
    std::size_t total_bits = count * static_cast<unsigned>(bit_width);
    if (encoded.size() != (total_bits + 5) / 6) return std::nullopt;

    using Unsigned = std::make_unsigned_t<Integer>;
    std::vector<Integer> values;
    values.reserve(count);
    std::size_t position = 0;
    unsigned buffer = 0;
    int buffered_bits = 0;

    for (std::size_t index = 0; index < count; ++index) {
        Unsigned value = 0;
        int remaining_bits = bit_width;
        while (remaining_bits > 0) {
            if (buffered_bits == 0) {
                int digit = detail::base64_digit(encoded[position++]);
                if (digit < 0) return std::nullopt;
                buffer = static_cast<unsigned>(digit);
                buffered_bits = 6;
            }

            int take = std::min(buffered_bits, remaining_bits);
            int shift = buffered_bits - take;
            unsigned mask = (1U << take) - 1;
            unsigned part = (buffer >> shift) & mask;
            value = static_cast<Unsigned>((value << take) | part);
            buffered_bits -= take;
            remaining_bits -= take;
        }
        values.push_back(static_cast<Integer>(value));
    }

    if (buffered_bits != 0) {
        unsigned mask = (1U << buffered_bits) - 1;
        if ((buffer & mask) != 0) return std::nullopt;
    }
    return values;
}

template <detail::Base64Integer Integer>
std::vector<Integer> from_base64(std::string_view encoded, std::size_t count,
                                 int bit_width) {
    std::optional<std::vector<Integer>> result =
        checked_from_base64<Integer>(encoded, count, bit_width);
    assert(result.has_value());
    return result.value_or(std::vector<Integer>());
}

}  // namespace utilities
}  // namespace m1une

#endif  // M1UNE_UTILITIES_BASE64_HPP

#line 1 "utilities/base64.hpp"



#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#include <optional>
#include <ranges>
#include <string>
#include <string_view>
#include <type_traits>
#include <vector>

namespace m1une {
namespace utilities {

inline constexpr std::string_view base64_alphabet =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

namespace detail {

inline int base64_digit(char character) noexcept {
    if ('A' <= character && character <= 'Z') return character - 'A';
    if ('a' <= character && character <= 'z') return character - 'a' + 26;
    if ('0' <= character && character <= '9') return character - '0' + 52;
    if (character == '+') return 62;
    if (character == '/') return 63;
    return -1;
}

template <class Integer>
concept Base64Integer =
    std::integral<Integer> &&
    (!std::same_as<std::remove_cv_t<Integer>, bool>);

}  // namespace detail

// Packs fixed-width nonnegative integers, most-significant bit first. The last
// Base64 digit is zero-padded on the right; '=' padding is intentionally omitted.
template <class Sequence>
requires std::ranges::input_range<const Sequence&> &&
         detail::Base64Integer<std::ranges::range_value_t<Sequence>>
std::string to_base64(const Sequence& values, int bit_width) {
    using Integer = std::ranges::range_value_t<Sequence>;
    using Unsigned = std::make_unsigned_t<Integer>;
    constexpr int digits = std::numeric_limits<Integer>::digits;

    assert(1 <= bit_width && bit_width <= digits);
    if (bit_width < 1 || bit_width > digits) return {};

    std::string encoded;
    if constexpr (std::ranges::sized_range<const Sequence&>) {
        std::size_t count = static_cast<std::size_t>(std::ranges::size(values));
        constexpr std::size_t size_limit =
            std::numeric_limits<std::size_t>::max();
        if (count <= (size_limit - 5) / static_cast<unsigned>(bit_width)) {
            encoded.reserve((count * static_cast<unsigned>(bit_width) + 5) / 6);
        }
    }
    unsigned buffer = 0;
    int buffered_bits = 0;

    for (Integer value : values) {
        if constexpr (std::signed_integral<Integer>) {
            assert(value >= 0);
            if (value < 0) return {};
        }
        Unsigned unsigned_value = static_cast<Unsigned>(value);
        if (bit_width < digits) {
            assert((unsigned_value >> bit_width) == 0);
            if ((unsigned_value >> bit_width) != 0) return {};
        }

        int remaining_bits = bit_width;
        while (remaining_bits > 0) {
            int take = std::min(6 - buffered_bits, remaining_bits);
            int shift = remaining_bits - take;
            unsigned mask = (1U << take) - 1;
            unsigned part = static_cast<unsigned>((unsigned_value >> shift) & mask);
            buffer = (buffer << take) | part;
            buffered_bits += take;
            remaining_bits -= take;

            if (buffered_bits == 6) {
                encoded.push_back(base64_alphabet[buffer]);
                buffer = 0;
                buffered_bits = 0;
            }
        }
    }

    if (buffered_bits != 0) {
        encoded.push_back(base64_alphabet[buffer << (6 - buffered_bits)]);
    }
    return encoded;
}

// Returns nullopt unless encoded is the canonical encoding of exactly count
// values with the requested bit width.
template <detail::Base64Integer Integer>
std::optional<std::vector<Integer>> checked_from_base64(
    std::string_view encoded, std::size_t count, int bit_width) {
    constexpr int digits = std::numeric_limits<Integer>::digits;
    if (bit_width < 1 || bit_width > digits) return std::nullopt;

    constexpr std::size_t size_limit = std::numeric_limits<std::size_t>::max();
    if (count > (size_limit - 5) / static_cast<unsigned>(bit_width)) {
        return std::nullopt;
    }
    std::size_t total_bits = count * static_cast<unsigned>(bit_width);
    if (encoded.size() != (total_bits + 5) / 6) return std::nullopt;

    using Unsigned = std::make_unsigned_t<Integer>;
    std::vector<Integer> values;
    values.reserve(count);
    std::size_t position = 0;
    unsigned buffer = 0;
    int buffered_bits = 0;

    for (std::size_t index = 0; index < count; ++index) {
        Unsigned value = 0;
        int remaining_bits = bit_width;
        while (remaining_bits > 0) {
            if (buffered_bits == 0) {
                int digit = detail::base64_digit(encoded[position++]);
                if (digit < 0) return std::nullopt;
                buffer = static_cast<unsigned>(digit);
                buffered_bits = 6;
            }

            int take = std::min(buffered_bits, remaining_bits);
            int shift = buffered_bits - take;
            unsigned mask = (1U << take) - 1;
            unsigned part = (buffer >> shift) & mask;
            value = static_cast<Unsigned>((value << take) | part);
            buffered_bits -= take;
            remaining_bits -= take;
        }
        values.push_back(static_cast<Integer>(value));
    }

    if (buffered_bits != 0) {
        unsigned mask = (1U << buffered_bits) - 1;
        if ((buffer & mask) != 0) return std::nullopt;
    }
    return values;
}

template <detail::Base64Integer Integer>
std::vector<Integer> from_base64(std::string_view encoded, std::size_t count,
                                 int bit_width) {
    std::optional<std::vector<Integer>> result =
        checked_from_base64<Integer>(encoded, count, bit_width);
    assert(result.has_value());
    return result.value_or(std::vector<Integer>());
}

}  // namespace utilities
}  // namespace m1une

Back to top page