masked_value.cpp

#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <limits>
#include <type_traits>

constexpr std::size_t popcount(std::uint8_t value) noexcept
{
    value -= (value >> 1) & 0x55;
    value = (value & 0x33) + ((value >> 2) & 0x33);
    return (value + (value >> 4)) & 0x0F;
}

constexpr std::size_t popcount(std::uint32_t value) noexcept
{
    value -= (value >> 1) & 0x55555555; // reuse input as temporary
    value = (value & 0x33333333) + ((value >> 2) & 0x33333333); // temp
    return ((value + (value >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
}

template <typename T>
struct masked_value {
    T value = T(0);
    T mask = ~T(0);

    constexpr void extend(masked_value other)
    {
        mask &= ~(value ^ other.value) & other.mask;
        value &= mask;
    }

    constexpr bool operator==(masked_value other) const
    {
        return (value == other.value) && (mask == other.mask);
    }

    constexpr bool operator!=(masked_value other) const
    {
        return (value != other.value) || (mask != other.mask);
    }

    // Returns whether a value matches this masked byte
    constexpr bool matches(T value_) const
    {
        return (value_ & mask) == value;
    }

    // Returns whether this will match at least every value other does
    constexpr bool contains(masked_value other) const
    {
        return ((mask & ~other.mask) == 0) && ((mask & other.value) == value);
    }

    // Returns the lowest possible matching value
    constexpr T min_match() const
    {
        return value;
    }

    // Returns the highest possible matching value
    constexpr T max_match() const
    {
        return value | ~mask;
    }

    // Returns the next possible value after current (wraps when reaching the end)
    // Example:
    // for (T x = v.min_match();; x = v.next_match(x))
    // {
    //     // ...
    //     if (x == v.max_match())
    //         break;
    // }
    constexpr T next_match(T current) const
    {
        return value | (((current | mask) + 1) & ~mask);
    }

    // Returns the number of bits with a known value
    constexpr std::size_t known_bit_count() const
    {
        return popcount(mask);
    }

    // Returns the number of bits with a unknown value
    constexpr std::size_t unknown_bit_count() const
    {
        return static_cast<std::size_t>(std::numeric_limits<T>::digits) - known_bit_count();
    }

    // Returns the number of possible matching values
    constexpr std::size_t value_count() const
    {
        return static_cast<std::size_t>(1) << unknown_bit_count();
    }

    // Returns the largest step possible to match every value in range(min_match(), max_match(), value_step())
    constexpr T value_step() const
    {
        return ~mask & (mask + 1);
    }

    // Returns whether all values in range(min_match(), max_match(), value_step()) are possible values
    constexpr bool is_uniform_range() const
    {
        T ones = ~mask + value_step();

        return (ones & (ones - 1)) == 0;
    }

    static constexpr masked_value constant(T value)
    {
        return { value };
    }

    static constexpr masked_value unknown()
    {
        return { T(0), T(0) };
    }

    // Returns the masked byte which matches a range of values, with an optional step
    static constexpr masked_value range(T min, T max, T step = 1)
    {
        // Find the bits which change between min and max
        T mask = min ^ max;

        // Any bits lower than the highest changed bit would also change
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;

        // Convert from a mask of changed bit to a mask of unchanged bits
        mask = ~mask;
        mask |= (step & -static_cast<std::make_signed_t<T>>(step)) - 1;

        return {
            static_cast<T>(min & mask), mask
        };
    }

    // Returns the masked byte which matches a set of values
    static constexpr masked_value from_values(const T* values, std::size_t count)
    {
        // Any bits set in known_ones are set for every value
        T known_ones = ~T(0);

        // Any bits clear in known_zeros are clear for every value
        T known_zeros = T(0);

        for (std::size_t i = 0; i < count; ++i) {
            known_ones &= values[i];
            known_zeros |= values[i];
        }

        // The mask is any bits which are the same in both known_zeros and known_ones:
        //  * If a bit is set in all inputs, it will be set in known_zeros and known_ones
        //  * If a bit is clear in all inputs, it will be clear in known_zeros or known_ones
        //  * If a bit is set in some inputs but not in others, it will be set in known_zeros but not known_ones
        return {
            known_ones, static_cast<T>(~(known_zeros ^ known_ones))
        };
    }

    // Returns the masked byte which matches a set of values
    static constexpr masked_value from_values(std::initializer_list<T> values)
    {
        return from_values(values.begin(), values.size());
    }

    static constexpr masked_value checked(T value, T mask)
    {
        return { value & mask, mask };
    }

    constexpr masked_value operator&(masked_value other) const
    {
        return { value & other.value, (mask & other.mask) | (~value & mask) | (~other.value & other.mask) };
    }

    constexpr masked_value operator|(masked_value other) const
    {
        T v = value | other.value;
        return { v, v | (mask & other.mask) };
    }

    constexpr masked_value operator^(masked_value v) const
    {
        return checked(value ^ v.value, mask & v.mask);
    }

    constexpr masked_value operator<<(std::size_t shift) const
    {
        return { value << shift, ((mask + 1) << shift) - 1 };
    }

    constexpr masked_value operator+(masked_value other) const
    {
        masked_value const a = *this;
        masked_value const b = other;

        masked_value c;
        masked_value d;

        for (std::size_t i = 0; i < std::numeric_limits<T>::digits; ++i) {
            masked_value const mask { T(1) << i };
            d = d | ((a ^ b ^ c) & mask);
            c = (((a & b) | (a & c) | (b & c)) & mask) << 1;
        }

        return d;
    }

    constexpr masked_value operator*(masked_value other) const
    {
        masked_value a = *this;
        masked_value b = other;
        masked_value c;

        for (std::size_t i = 0; i < std::numeric_limits<T>::digits; ++i) {
            if ((b.value >> i) & 1) {
                c = c + (a << i);
            }
        }

        for (std::size_t i = 0; i < std::numeric_limits<T>::digits; ++i) {
            if ((~b.mask >> i) & 1) {
                c.extend(c + (a << i));
            }
        }

        return c;
    }
};

using masked_byte = masked_value<std::uint8_t>;