bitvector.hpp

Go to the documentation of this file.

 
#ifndef CCSDS124_BITVECTOR_HPP
#define CCSDS124_BITVECTOR_HPP
 
#include <array>
#include <cstring>
 
#include "config.hpp"
 
namespace ccsds124 {
 
namespace detail {
 
inline int extract_msb(std::uint32_t& word) noexcept {
    if (word == 0) {
        return -1;
    }
    int clz = __builtin_clz(word);
    word &= ~(1U << (31U - static_cast<std::uint32_t>(clz)));
    return clz;
}
 
inline int extract_lsb(std::uint32_t& word) noexcept {
    if (word == 0) {
        return -1;
    }
    int ctz = __builtin_ctz(word);
    word &= word - 1; // Clear LSB (standard idiom)
    return 31 - ctz;  // Convert to position from MSB
}
 
} // namespace detail
 
template <std::size_t N> class BitVector {
public:
    static constexpr std::size_t NUM_WORDS = (N + 31) / 32;
 
    static constexpr std::size_t NUM_BYTES = (N + 7) / 8;
 
    constexpr BitVector() noexcept : data_{} {}
 
    [[nodiscard]] constexpr std::size_t length() const noexcept {
        return N;
    }
 
    [[nodiscard]] constexpr std::size_t num_words() const noexcept {
        return NUM_WORDS;
    }
 
    void zero() noexcept {
        data_.fill(0);
    }
 
    [[nodiscard]] inline int get_bit(std::size_t pos) const noexcept {
        if (pos >= N) [[unlikely]]
            return 0;
        return get_bit_unchecked(pos);
    }
 
    [[nodiscard]] inline int get_bit_unchecked(std::size_t pos) const noexcept {
        std::size_t word_idx = pos >> 5;
        std::size_t bit_in_word = 31U - (pos & 31U);
        return static_cast<int>((data_[word_idx] >> bit_in_word) & 1U);
    }
 
    inline void set_bit(std::size_t pos, int value) noexcept {
        if (pos >= N) [[unlikely]]
            return;
        set_bit_unchecked(pos, value);
    }
 
    inline void set_bit_unchecked(std::size_t pos, int value) noexcept {
        std::size_t word_idx = pos >> 5;
        std::size_t bit_in_word = 31U - (pos & 31U);
 
        if (value) {
            data_[word_idx] |= (1U << bit_in_word);
        } else {
            data_[word_idx] &= ~(1U << bit_in_word);
        }
    }
 
    void copy_from(const BitVector& src) noexcept {
        data_ = src.data_;
    }
 
    void xor_of(const BitVector& a, const BitVector& b) noexcept {
        for (std::size_t i = 0; i < NUM_WORDS; ++i) {
            data_[i] = a.data_[i] ^ b.data_[i];
        }
    }
 
    void or_of(const BitVector& a, const BitVector& b) noexcept {
        for (std::size_t i = 0; i < NUM_WORDS; ++i) {
            data_[i] = a.data_[i] | b.data_[i];
        }
    }
 
    void and_of(const BitVector& a, const BitVector& b) noexcept {
        for (std::size_t i = 0; i < NUM_WORDS; ++i) {
            data_[i] = a.data_[i] & b.data_[i];
        }
    }
 
    void not_of(const BitVector& a) noexcept {
        for (std::size_t i = 0; i < NUM_WORDS; ++i) {
            data_[i] = ~a.data_[i];
        }
        mask_unused_bits();
    }
 
    void left_shift_of(const BitVector& a) noexcept {
        if constexpr (NUM_WORDS > 0) {
            for (std::size_t i = 0; i < NUM_WORDS - 1; ++i) {
                data_[i] = (a.data_[i] << 1) | (a.data_[i + 1] >> 31);
            }
            data_[NUM_WORDS - 1] = a.data_[NUM_WORDS - 1] << 1;
        }
    }
 
    void reverse_of(const BitVector& a) noexcept {
        // Reverse word order and reverse bits within each word
        for (std::size_t i = 0; i < NUM_WORDS; ++i) {
            std::uint32_t word = a.data_[NUM_WORDS - 1 - i];
            // Reverse bits within word using efficient swaps
            word = ((word & 0x55555555U) << 1) | ((word >> 1) & 0x55555555U);
            word = ((word & 0x33333333U) << 2) | ((word >> 2) & 0x33333333U);
            word = ((word & 0x0F0F0F0FU) << 4) | ((word >> 4) & 0x0F0F0F0FU);
            word = __builtin_bswap32(word); // Reverse bytes
            data_[i] = word;
        }
 
        // Handle non-32-bit-aligned size: shift to account for unused bits
        constexpr std::size_t extra_bits = (NUM_WORDS * 32) - N;
        if constexpr (extra_bits > 0) {
            // Shift entire array left by extra_bits to align
            for (std::size_t i = 0; i < NUM_WORDS - 1; ++i) {
                data_[i] = (data_[i] << extra_bits) | (data_[i + 1] >> (32 - extra_bits));
            }
            data_[NUM_WORDS - 1] <<= extra_bits;
        }
    }
 
    void xor_with(const BitVector& other) noexcept {
        for (std::size_t i = 0; i < NUM_WORDS; ++i) {
            data_[i] ^= other.data_[i];
        }
    }
 
    void xor_with(const BitVector& a, const BitVector& b) noexcept {
        xor_of(a, b);
    }
 
    void or_with(const BitVector& other) noexcept {
        for (std::size_t i = 0; i < NUM_WORDS; ++i) {
            data_[i] |= other.data_[i];
        }
    }
 
    void or_with(const BitVector& a, const BitVector& b) noexcept {
        or_of(a, b);
    }
 
    void or_in_place(const BitVector& other) noexcept {
        or_with(other);
    }
 
    void and_with(const BitVector& other) noexcept {
        for (std::size_t i = 0; i < NUM_WORDS; ++i) {
            data_[i] &= other.data_[i];
        }
    }
 
    void invert() noexcept {
        for (std::size_t i = 0; i < NUM_WORDS; ++i) {
            data_[i] = ~data_[i];
        }
        mask_unused_bits();
    }
 
    void left_shift() noexcept {
        if constexpr (NUM_WORDS > 0) {
            for (std::size_t i = 0; i < NUM_WORDS - 1; ++i) {
                data_[i] = (data_[i] << 1) | (data_[i + 1] >> 31);
            }
            data_[NUM_WORDS - 1] <<= 1;
        }
    }
 
    void left_shift(const BitVector& src) noexcept {
        left_shift_of(src);
    }
 
    [[nodiscard]] std::size_t hamming_weight() const noexcept {
        std::size_t count = 0;
        for (std::size_t i = 0; i < NUM_WORDS; ++i) {
            count += static_cast<std::size_t>(__builtin_popcount(data_[i]));
        }
 
        // Adjust for unused bits in last word
        constexpr std::size_t extra_bits = (NUM_WORDS * 32) - N;
        if constexpr (extra_bits > 0) {
            word_t last_word = data_[NUM_WORDS - 1];
            word_t mask = (1U << extra_bits) - 1U;
            count -= static_cast<std::size_t>(__builtin_popcount(last_word & mask));
        }
 
        return count;
    }
 
    [[nodiscard]] bool operator==(const BitVector& other) const noexcept {
        return data_ == other.data_;
    }
 
    [[nodiscard]] bool operator!=(const BitVector& other) const noexcept {
        return data_ != other.data_;
    }
 
    void from_bytes(const std::uint8_t* bytes, std::size_t num_bytes) noexcept {
        zero();
 
        std::size_t max_bytes = (num_bytes < NUM_BYTES) ? num_bytes : NUM_BYTES;
        std::size_t word_idx = 0;
        int byte_in_word = 4;
        word_t word_acc = 0;
 
        for (std::size_t i = 0; i < max_bytes; ++i) {
            --byte_in_word;
            word_acc |= static_cast<word_t>(bytes[i]) << (byte_in_word * 8);
 
            if (byte_in_word == 0) {
                data_[word_idx] = word_acc;
                ++word_idx;
                word_acc = 0;
                byte_in_word = 4;
            }
        }
 
        // Handle incomplete final word
        if (byte_in_word < 4) {
            data_[word_idx] = word_acc;
        }
    }
 
    void to_bytes(std::uint8_t* bytes, std::size_t num_bytes) const noexcept {
        std::size_t max_bytes = (num_bytes < NUM_BYTES) ? num_bytes : NUM_BYTES;
        std::size_t byte_idx = 0;
 
        for (std::size_t word_idx = 0; word_idx < NUM_WORDS && byte_idx < max_bytes; ++word_idx) {
            word_t word = data_[word_idx];
 
            for (int j = 3; j >= 0 && byte_idx < max_bytes; --j) {
                bytes[byte_idx] = static_cast<std::uint8_t>((word >> (j * 8)) & 0xFFU);
                ++byte_idx;
            }
        }
    }
 
    [[nodiscard]] word_t* data() noexcept {
        return data_.data();
    }
 
    [[nodiscard]] const word_t* data() const noexcept {
        return data_.data();
    }
 
private:
    std::array<word_t, NUM_WORDS> data_;
 
    void mask_unused_bits() noexcept {
        constexpr std::size_t extra_bits = (NUM_WORDS * 32) - N;
        if constexpr (extra_bits > 0 && NUM_WORDS > 0) {
            word_t mask = ~((1U << extra_bits) - 1U);
            data_[NUM_WORDS - 1] &= mask;
        }
    }
};
 
} // namespace ccsds124
 
#endif // CCSDS124_BITVECTOR_HPP