unsigned_word.h

Go to the documentation of this file.

#pragma once
// SPDX-FileCopyrightText: 2025 Nessan Fitzmaurice <nzznfitz+gh@icloud.com>
// SPDX-License-Identifier: MIT

 
#include <gf2/assert.h>
 
#include <bit>
#include <concepts>
#include <cstdint>
#include <format>
#include <optional>
#include <utility>
#include <type_traits>
 
namespace gf2 {
 
// Our `unsigned_word` concept is the same as `std::unsigned_integral`
template<typename T>
concept unsigned_word = std::unsigned_integral<T>;


using u8 = std::uint8_t;

using u16 = std::uint16_t;

using u32 = std::uint32_t;

using u64 = std::uint64_t;

using usize = std::size_t;


template<unsigned_word Word>
constexpr u8 BITS = std::numeric_limits<Word>::digits;

template<unsigned_word Word>
constexpr Word ZERO = Word{0};

template<unsigned_word Word>
constexpr Word ONE = Word{1};

template<unsigned_word Word>
constexpr Word MAX = std::numeric_limits<Word>::max();

template<unsigned_word Word>
constexpr Word ALTERNATING = MAX<Word> / 3;


template<unsigned_word Word>
constexpr Word
with_set_bits(u8 begin, u8 end) {
    gf2_debug_assert(end <= BITS<Word>, "End of range `{}` should be at most `{}`.", end, BITS<Word>);
    gf2_debug_assert(begin <= end, "Mis-ordered range: [{}, {})", begin, end);
    return (MAX<Word> << begin) & (MAX<Word> >> (BITS<Word> - end));
}

template<unsigned_word Word>
constexpr Word
with_unset_bits(u8 begin, u8 end) {
    gf2_debug_assert(end <= BITS<Word>, "End of range `{}` should be at most `{}`.", end, BITS<Word>);
    gf2_debug_assert(begin <= end, "Mis-ordered range: [{}, {})", begin, end);
    auto result = with_set_bits<Word>(begin, end);
    return static_cast<Word>(~result);
}


template<unsigned_word Word>
constexpr void
set_bits(Word& word, u8 begin, u8 end) {
    gf2_debug_assert(end <= BITS<Word>, "End of range `{}` should be at most `{}`.", end, BITS<Word>);
    gf2_debug_assert(begin <= end, "Mis-ordered range: [{}, {})", begin, end);
    if (begin != end) word |= with_set_bits<Word>(begin, end);
}

template<unsigned_word Word>
constexpr void
reset_bits(Word& word, u8 begin, u8 end) {
    gf2_debug_assert(end <= BITS<Word>, "End of range `{}` should be at most `{}`.", end, BITS<Word>);
    gf2_debug_assert(begin <= end, "Mis-ordered range: [{}, {})", begin, end);
    if (begin != end) {
        auto mask = with_set_bits<Word>(begin, end);
        mask = static_cast<Word>(~mask);
        word &= mask;
    }
}

template<unsigned_word Word>
constexpr void
set_except_bits(Word& word, u8 begin, u8 end) {
    gf2_debug_assert(end <= BITS<Word>, "End of range `{}` should be at most `{}`.", end, BITS<Word>);
    gf2_debug_assert(begin <= end, "Mis-ordered range: [{}, {})", begin, end);
    if (begin != end) {
        auto mask = with_set_bits<Word>(begin, end);
        mask = static_cast<Word>(~mask);
        word |= mask;
    }
}

template<unsigned_word Word>
constexpr void
reset_except_bits(Word& word, u8 begin, u8 end) {
    gf2_debug_assert(end <= BITS<Word>, "End of range `{}` should be at most `{}`.", end, BITS<Word>);
    gf2_debug_assert(begin <= end, "Mis-ordered range: [{}, {})", begin, end);
    if (begin != end) {
        auto mask = with_set_bits<Word>(begin, end);
        word &= mask;
    }
}

template<unsigned_word Word>
constexpr Word
reverse_bits(Word word) {
    Word result = 0;
    for (u8 i = 0; i < BITS<Word>; ++i, word >>= 1) { result = static_cast<Word>((result << 1) | (word & 1)); }
    return result;
}

template<unsigned_word Word, typename Other>
constexpr void
replace_bits(Word& word, u8 begin, u8 end, Other other)
    requires std::convertible_to<Other, Word>
{
    gf2_debug_assert(end <= BITS<Word>, "End of range `{}` should be at most `{}`.", end, BITS<Word>);
    gf2_debug_assert(begin <= end, "Mis-ordered range: [{}, {})", begin, end);
    if (begin != end) {
        auto other_mask = with_set_bits<Word>(begin, end);
        auto word_mask = static_cast<Word>(~other_mask);
        word = (word & word_mask) | (static_cast<Word>(other) & other_mask);
    }
}


template<unsigned_word Word>
constexpr std::pair<Word, Word>
riffle(Word word) {
    auto half_bits = BITS<Word> / 2;
    Word lo = word & (MAX<Word> >> half_bits);
    Word hi = word >> half_bits;
 
    // Some magic to interleave the respective halves with zeros starting with half the bits in each half.
    Word one = 1;
    auto shift = BITS<Word> / 4;
    while (shift > 0) {
        Word div = Word(one << shift) | one;
        Word mask = MAX<Word> / div;
        lo = (lo ^ (lo << shift)) & mask;
        hi = (hi ^ (hi << shift)) & mask;
        shift /= 2;
    }
    return std::pair{lo, hi};
}


template<unsigned_word Word>
constexpr u8
count_ones(Word word) {
    return static_cast<u8>(std::popcount(word));
}

template<unsigned_word Word>
constexpr u8
count_zeros(Word word) {
    return BITS<Word> - count_ones(word);
}

template<unsigned_word Word>
constexpr u8
trailing_zeros(Word word) {
    return static_cast<u8>(std::countr_zero(word));
}

template<unsigned_word Word>
constexpr u8
leading_zeros(Word word) {
    return static_cast<u8>(std::countl_zero(word));
}

template<unsigned_word Word>
constexpr u8
trailing_ones(Word word) {
    return static_cast<u8>(std::countr_one(word));
}

template<unsigned_word Word>
constexpr u8
leading_ones(Word word) {
    return static_cast<u8>(std::countl_one(word));
}

template<unsigned_word Word>
constexpr std::optional<u8>
lowest_set_bit(Word word) {
    if (word != 0) return trailing_zeros(word);
    return {};
}


template<unsigned_word Word>
constexpr std::optional<u8>
highest_set_bit(Word word) {
    if (word != 0) return BITS<Word> - leading_zeros(word) - 1;
    return {};
}

template<unsigned_word Word>
constexpr std::optional<u8>
lowest_unset_bit(Word word) {
    if (word != MAX<Word>) return trailing_ones(word);
    return {};
}

template<unsigned_word Word>
constexpr std::optional<u8>
highest_unset_bit(Word word) {
    if (word != MAX<Word>) return BITS<Word> - leading_ones(word) - 1;
    return {};
}


template<unsigned_word Word>
static inline std::string
to_binary_string(Word word) {
    return std::format("{:0{}b}", word, BITS<Word>);
}

template<unsigned_word Word>
static inline std::string
to_hex_string(Word word) {
    return std::format("{:0{}X}", word, BITS<Word> / 4);
}


template<unsigned_word Word>
constexpr usize
words_needed(usize n_bits) {
    // Usually divide returns *both* the quotient & remainder & the compiler will optimise the next line.
    return n_bits / BITS<Word> + (n_bits % BITS<Word> != 0);
}

template<unsigned_word Word>
constexpr usize
word_index(usize i) {
    return i / BITS<Word>;
}

template<unsigned_word Word>
constexpr u8
bit_offset(usize i) {
    return i % BITS<Word>;
}

template<unsigned_word Word>
constexpr std::pair<usize, u8>
index_and_offset(usize i) {
    return std::pair{word_index<Word>(i), bit_offset<Word>(i)};
}

template<unsigned_word Word>
constexpr std::pair<usize, Word>
index_and_mask(usize i) {
    return std::pair{word_index<Word>(i), static_cast<Word>(ONE<Word> << bit_offset<Word>(i))};
}

 
} // namespace gf2