BitSpan.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 <gf2/BitStore.h>
 
#include <print>
 
namespace gf2 {

template<unsigned_word Word>
class BitSpan : public BitStore<BitSpan<Word>> {
private:
    Word* m_begin;  // A pointer to the first word containing bits in the span (it may be partially occupied).
    u8    m_offset; // The bit-span begins at this bit-offset inside `m_begin[0]`.
    usize m_size;   // The number of bits in the span..
    usize m_words;  // We cache the total number of synthesized words the span generates.
 
public:
    static constexpr usize bits_per_word = std::numeric_limits<Word>::digits;
 
    // The underlying store really has words of this type (where we are remove any `const` qualifier).
    using word_type = std::remove_const_t<Word>;


    BitSpan(Word* begin, u8 offset, usize size) {
 
        // Check that the span is non-empty and that the begin bit is valid.
        gf2_debug_assert(size > 0, "We do not allow empty bit-spans.");
        gf2_debug_assert(offset < bits_per_word, "Span begins at bit-offset {} > bits in a word ({})!", offset,
                         bits_per_word);
 
        // Set the member variables.
        m_begin = begin;
        m_offset = offset;
        m_size = size;
 
        // Cache the total number of synthesized words needed to store all the bits in the span.
        m_words = gf2::words_needed<Word>(m_size);
    }


    constexpr usize size() const { return m_size; }

    constexpr usize words() const { return m_words; }

    constexpr word_type word(usize i) const {
        // Get the recipe for the "word" at index `i` (we may need two real words to synthesise it).
        auto [w0_bits, w1_bits] = recipe_for_word(i);
 
        // Our return value starts with all unset bits.
        word_type result = 0;
 
        // Replace `w0_bits` low-order bits in `result` with the same number of high-order bits from `w0`
        Word w0 = m_begin[i];
        gf2::replace_bits(result, 0, w0_bits, w0 >> m_offset);
 
        // Perhaps our result spans two words.
        if (w1_bits > 0) {
            // Replace `w1_bits` high-order bits in result with the same number of low-order bits from `w1`
            Word w1 = m_begin[i + 1];
            gf2::replace_bits(result, w0_bits, w0_bits + w1_bits, w1 << w0_bits);
        }
        return result;
    }

    constexpr void set_word(usize i, word_type value) {
        if constexpr (std::is_const_v<Word>) {
            // This should never get called for const bit-spans.
            throw std::logic_error("Cannot set a word in a const bit-span.");
        } else {
            // Get the recipe for the "word" at index `i` (it may be a synthesis of two real words).
            auto [w0_bits, w1_bits] = recipe_for_word(i);
 
            // Replace `w0_bits` low-order bits in `w0` with the same number of high-order bits from `value`
            // Shift `value` to the left to align its bits with the start of `w0`.
            gf2::replace_bits(m_begin[i], m_offset, m_offset + w0_bits, value << m_offset);
 
            // Perhaps we also need to overwrite some bits in the second word.
            if (w1_bits > 0) {
                // Replace `w1_bits` low-order bits in `w1` with the same number of high-order bits from `value`
                gf2::replace_bits(m_begin[i + 1], 0, w1_bits, value >> w0_bits);
            }
        }
    }

    constexpr const Word* data() const { return m_begin; }

    constexpr Word* data() { return m_begin; }

    constexpr u8 offset() const { return m_offset; }

 
private:
    constexpr auto recipe_for_word(usize i) const {
        gf2_debug_assert(i < m_words, "Index {} should be less than {}", i, m_words);
 
        // The default recipe (these sum to a whole word of bits).
        u8 w0_bits = bits_per_word - m_offset;
        u8 w1_bits = m_offset;
 
        // The last word in the span may not be fully occupied so we need to adjust the bits accordingly.
        if (i == m_words - 1) {
            auto last_offset = static_cast<u8>((m_offset + m_size - 1) % bits_per_word);
            if (last_offset < m_offset) {
                // Still need to use two words but `w1-bits` may shrink.
                w1_bits = static_cast<u8>(last_offset + 1);
            } else {
                // Only need to use one word so no need for `w1_bits`.
                w0_bits = static_cast<u8>(last_offset - m_offset + 1);
                w1_bits = 0;
            }
        }
        return std::pair{w0_bits, w1_bits};
    }
};
 
} // namespace gf2
 
// --------------------------------------------------------------------------------------------------------------------
// Specialises `std::formatter` for `BitSpan` -- defers to the version for `BitStore` ...
// -------------------------------------------------------------------------------------------------------------------
template<gf2::unsigned_word Word>
struct std::formatter<gf2::BitSpan<Word>> : std::formatter<gf2::BitStore<gf2::BitSpan<Word>>> {
    // Inherits all functionality from `BitStore` formatter
};