BitFields

BitField128.cs

using System;

// A structure for performing bitwise operations collections of flags that are larger than the bit depth of an integer.
// The structure is backed by an array of unsigned 32 bit integers which represent "words" in the larger bit array.
// All standard bitwise operators are implemented, as well as methods that mutate the struct directly.
// The array of uints is implemented as a `fixed-size buffer` to force allocation of the uints inside this structure.
// The struct is therefore marked as `unsafe` 
// The struct implements IEquatable to improve performance in hash tables and dictionaries.
// Method params are marked with the `in` keyword where appropriate to minimise copying of the supplied arguments.
public unsafe struct BitField128 : IEquatable<BitField128>
{
    // PROPERTIES AND FIELDS
    
    #region PROPERTIES_AND_FIELDS
    
    private fixed uint words[wordCount];
    
    private const int wordCount = 4;
    private const int wordLength = 32;
    private const int bitCount = 128;

    public static int WordCount => wordCount;
    public static int WordLength => wordLength;
    public static int BitCount => bitCount;
    
    public static BitField128 none => new BitField128();
    public static BitField128 all => new BitField128(true);
    
    #endregion
    
    // CONSTRUCTORS
    
    #region CONSTRUCTORS

    public BitField128(in BitField128 bits)
    {
        for (var i = 0; i < wordCount; i++) words[i] = bits.words[i];
    }

    public BitField128(params int[] bits)
    {
        foreach (var bit in bits) SetBit(bit);
    }

    private BitField128(bool _) => Not();

    #endregion
    
    // BIT MANIPULATION

    #region BIT_MANIPULATION
    
    public void SetBit(int index)
    {
        IndexInBounds(index);
        GetMask(index, out var wordIndex, out var mask);
        words[wordIndex] |= mask;
    }
    
    public void UnsetBit(int index)
    {
        IndexInBounds(index);
        GetMask(index, out var wordIndex, out var mask);
        words[wordIndex] &= ~mask;
    }

    public void ToggleBit(int index)
    {
        if (GetBit(index)) UnsetBit(index);
        else SetBit(index);
    }

    public void SetBits(in BitField128 mask) => Or(in mask);
    
    public void UnsetBits(in BitField128 mask) => AndNot(in mask);

    public void ToggleBits(in BitField128 mask) => XOr(in mask);
    
    #endregion
    
    // QUERIES
    
    #region QUERIES

    public bool GetBit(int index)
    {
        IndexInBounds(index);
        GetMask(index, out var wordIndex, out var mask);
        return (words[wordIndex] & mask) == mask;
    }

    public bool IsEmpty()
    {
        for (var i = 0; i < wordCount; i++)
            if (words[i] != 0)
                return false;

        return true;
    }

    public bool AllOf(in BitField128 mask) => (this & mask) == mask;

    public bool AnyOf(in BitField128 mask) => !(this & mask).IsEmpty();

    public bool NoneOf(in BitField128 mask) => (this & mask).IsEmpty();

    #endregion
    
    // BOOLEAN OPERATORS
    
    #region BOOLEAN_OPERATIONS
    
    // And, Not, Or and XOr are the same operations performed element-by-element on the underlying uints

    public void And(in BitField128 mask)
    {
        for (var i = 0; i < wordCount; i++) 
            words[i] &= mask.words[i];
    }

    public void AndNot(in BitField128 mask)
    {
        for (var i = 0; i < wordCount; i++)
            words[i] &= ~mask.words[i];
    }

    public void Nand(in BitField128 mask)
    {
        for (var i = 0; i < wordCount; i++)
            words[i] = ~(words[i] & mask.words[i]);
    }

    public void Or(in BitField128 mask)
    {
        for (var i = 0; i < wordCount; i++) 
            words[i] |= mask.words[i];
    }

    public void OrNot(in BitField128 mask)
    {
        for (var i = 0; i < wordCount; i++) 
            words[i] |= ~mask.words[i];
    }

    public void Nor(in BitField128 mask)
    {
        for (var i = 0; i < wordCount; i++) 
            words[i] = ~(words[i] | mask.words[i]);
    }

    public void XOr(in BitField128 mask)
    {
        for (var i = 0; i < wordCount; i++) 
            words[i] ^= mask.words[i];
    }

    public void XOrNot(in BitField128 mask)
    {
        for (var i = 0; i < wordCount; i++) 
            words[i] ^= ~mask.words[i];
    }

    public void NotXOr(in BitField128 mask)
    {
        for (var i = 0; i < wordCount; i++) 
            words[i] = ~(words[i] ^ mask.words[i]);
    }

    public void Not()
    {
        for (var i = 0; i < wordCount; i++) 
            words[i] = ~words[i];
    }
    
    // The shift operation is more complicated because it pushes bits from one word into another
    // we must "carry" the bits that are shifted out of one word into the adjacent word
    // for shift amounts that are greater than the word length, we can decompose the operation
    // into two parts, shifting by an amount smaller than the word length and then copying words 
    // in whole steps from one array element to another.
    // Right and left shift require traversing the underlying array in the opposite orders.

    public void Shift(int count)
    {
        // if shifting by 0 do nothing
        if (count == 0) return;
         
        // if shifting by more than the total number of bits stored,
        // set every bit to zero
        if (Abs(count) >= bitCount)
        {
            for (var i = 0; i < wordCount; i++) words[i] = 0;
            return;
        }
        
        // This operation can be split into two simpler operations:
        // (1) shift the bits by an amount smaller than the word length (using bitwise math)
        // (2) shift the result by a whole number of words (by shifting the positions of words in the array)
        
        // find the the quotient and remainder of the shift amount over the word length
        // the quotient is the number of whole words to shift
        var wholeWordCount = Abs(count / wordLength);
        // the remainder is the number of bits to shift within each word
        var shiftAmount = Abs(count % wordLength);
        // get the direction of the shift
        var rightShift = count > 0;

        // (1): shift by the remainder after division by word length
        if (shiftAmount != 0)
        {
            // find the carry bits that overflow from one word to the next
            // this is the same as shifting the word in the opposite direction by wordLength - shiftAmount
            var overflowAmount = wordLength - shiftAmount;
            // the first word will be filled in with zeros from the trailing side, so the the carry bits are zero
            var carryBits = 0u;
            
            // no need to process elements that are with wordCount of the opposite edge of the array
            // these will be pushed out of the bitfield
            if (rightShift) // RIGHT-SHIFT
            {
                // work backwards through the array pushing bits right
                for (var i = wordCount - 1; i >= wholeWordCount; i--)
                {
                    // get the current word
                    var word = words[i];
                    // the first term is the [current word] shifted in the target direction by the [shift amount]
                    // the second term is the bits carried over from the previous word (0 if this is the first word)
                    // [carry bits] are the previous word's bits shifted in the opposite direction by the [overflow amount]
                    // [term1] OR [term2] gives the resulting word 
                    words[i] = word >> shiftAmount | carryBits;
                    // store the [carry bits] for the next word 
                    carryBits = word << overflowAmount;
                }
            }
            else // LEFT-SHIFT
            {
                // work forwards through the array pushing bits left
                for (var i = 0; i < wordCount - wholeWordCount; i++)
                {
                    // get the current word
                    var word = words[i];
                    // the first term is the [current word] shifted in the target direction by the [shift amount]
                    // the second term is the bits carried over from the previous word (0 if this is the first word)
                    // [carry bits] are the previous word's bits shifted in the opposite direction by the [overflow amount]
                    // [term1] OR [term2] gives the resulting word 
                    words[i] = word << shiftAmount | carryBits;
                    // store the carry bits for the next word
                    carryBits = word >> overflowAmount;
                }
            }
        }

        // (2): shift whole words by the quotient of the division
        if (rightShift)
        {
            // work forwards through the array
            for (var i = 0; i < wordCount; i++)
            {
                // if possible, replace the entry at the current index with the entry at (index + wholeWordCount)
                if (i + wholeWordCount < wordCount) words[i] = words[i + wholeWordCount];
                // otherwise fill in with zeros
                else words[i] = 0;
            }
        }
        else
        {
            // work backwards through the array
            for (var i = wordCount-1; i >= 0; i--)
            {
                // if possible, replace the entry at the current index with the entry at (index - wholeWordCount)
                if (i - wholeWordCount >= 0) words[i] = words[i - wholeWordCount];
                // otherwise fill in with zeros
                else words[i] = 0;
            }
        }
    }

    #endregion

    // OPERATORS
    
    #region OPERATORS
    
    public static BitField128 operator &(BitField128 a, BitField128 b)
    {
        var c = new BitField128(in a);
        c.And(in b);
        return c;
    }    
    
    public static BitField128 operator |(BitField128 a, BitField128 b)
    {
        var c = new BitField128(in a);
        c.Or(in b);
        return c;
    }  
    
    public static BitField128 operator ^(BitField128 a, BitField128 b)
    {
        var c = new BitField128(in a);
        c.XOr(in b);
        return c;
    }
    
    public static BitField128 operator ~(BitField128 a)
    {
        var c = new BitField128(in a);
        c.Not();
        return c;
    }
    
    public static BitField128 operator <<(BitField128 a, int d)
    {
        var c = new BitField128(in a);
        c.Shift(-d);
        return c;
    }
    
    public static BitField128 operator >>(BitField128 a, int d)
    {
        var c = new BitField128(in a);
        c.Shift(d);
        return c;
    }
    
    public static bool operator ==(BitField128 a, BitField128 b) => a.Equals(b);
    
    public static bool operator !=(BitField128 a, BitField128 b) => !a.Equals(b);
    
    #endregion

    // UTILITY
    
    #region UTILITY

    private int Abs(int i)
    {
        if (i >= 0) return i;
        return -i;
    }

    private void GetMask(int index, out int wordIndex, out uint mask)
    {
        wordIndex = index / wordLength;
        mask = 1u << index % wordLength;
    }

    private void IndexInBounds(int index)
    {
        if (index < 0 || index >= bitCount) throw new IndexOutOfRangeException();
    }
    
    public override string ToString()
    {
        const string header = "BitField ( ";
        const int headerLen = 11; 
        var chars = new char[headerLen + bitCount + wordCount + 2];
        var i = 0;
        for (; i < headerLen; ++i) chars[i] = header[i];

        for (var word = wordCount - 1; word >= 0; word--, ++i)
        {
            for (var digit = wordLength - 1; digit >= 0; digit--, ++i)
            {
                var mask = 1u << digit;
                chars[i] = (words[word] & mask) == mask ? '1' : '0';
            }
            chars[i] = ' ';
        }
        chars[i] = ')';
        return new string(chars);
    }
    
    #endregion
    
    // EQUATABLE
    
    #region EQUATABLE

    public bool Equals(BitField128 other)
    {
        for (var i = 0; i < wordCount; i++)
            if (words[i] != other.words[i])
                return false;

        return true;
    }

    public override bool Equals(object obj) => obj is BitField128 other && Equals(other);

    public override int GetHashCode()
    {
        var hash = 17;
        for(var i = 0; i < wordCount; i++) hash = 31 * hash + words[i].GetHashCode();
        return hash;
    }
    
    #endregion
}