diff options
Diffstat (limited to 'ARMeilleure/Common')
| -rw-r--r-- | ARMeilleure/Common/BitMap.cs | 138 | ||||
| -rw-r--r-- | ARMeilleure/Common/BitUtils.cs | 109 | ||||
| -rw-r--r-- | ARMeilleure/Common/EnumUtils.cs | 12 |
3 files changed, 259 insertions, 0 deletions
diff --git a/ARMeilleure/Common/BitMap.cs b/ARMeilleure/Common/BitMap.cs new file mode 100644 index 00000000..9dff271b --- /dev/null +++ b/ARMeilleure/Common/BitMap.cs @@ -0,0 +1,138 @@ +using System.Collections; +using System.Collections.Generic; + +namespace ARMeilleure.Common +{ + class BitMap : IEnumerable<int> + { + private const int IntSize = 32; + private const int IntMask = IntSize - 1; + + private List<int> _masks; + + public BitMap(int initialCapacity) + { + int count = (initialCapacity + IntMask) / IntSize; + + _masks = new List<int>(count); + + while (count-- > 0) + { + _masks.Add(0); + } + } + + public bool Set(int bit) + { + EnsureCapacity(bit + 1); + + int wordIndex = bit / IntSize; + int wordBit = bit & IntMask; + + int wordMask = 1 << wordBit; + + if ((_masks[wordIndex] & wordMask) != 0) + { + return false; + } + + _masks[wordIndex] |= wordMask; + + return true; + } + + public void Clear(int bit) + { + EnsureCapacity(bit + 1); + + int wordIndex = bit / IntSize; + int wordBit = bit & IntMask; + + int wordMask = 1 << wordBit; + + _masks[wordIndex] &= ~wordMask; + } + + public bool IsSet(int bit) + { + EnsureCapacity(bit + 1); + + int wordIndex = bit / IntSize; + int wordBit = bit & IntMask; + + return (_masks[wordIndex] & (1 << wordBit)) != 0; + } + + public bool Set(BitMap map) + { + EnsureCapacity(map._masks.Count * IntSize); + + bool modified = false; + + for (int index = 0; index < _masks.Count; index++) + { + int newValue = _masks[index] | map._masks[index]; + + if (_masks[index] != newValue) + { + _masks[index] = newValue; + + modified = true; + } + } + + return modified; + } + + public bool Clear(BitMap map) + { + EnsureCapacity(map._masks.Count * IntSize); + + bool modified = false; + + for (int index = 0; index < _masks.Count; index++) + { + int newValue = _masks[index] & ~map._masks[index]; + + if (_masks[index] != newValue) + { + _masks[index] = newValue; + + modified = true; + } + } + + return modified; + } + + private void EnsureCapacity(int size) + { + while (_masks.Count * IntSize < size) + { + _masks.Add(0); + } + } + + public IEnumerator<int> GetEnumerator() + { + for (int index = 0; index < _masks.Count; index++) + { + int mask = _masks[index]; + + while (mask != 0) + { + int bit = BitUtils.LowestBitSet(mask); + + mask &= ~(1 << bit); + + yield return index * IntSize + bit; + } + } + } + + IEnumerator IEnumerable.GetEnumerator() + { + return GetEnumerator(); + } + } +}
\ No newline at end of file diff --git a/ARMeilleure/Common/BitUtils.cs b/ARMeilleure/Common/BitUtils.cs new file mode 100644 index 00000000..55344608 --- /dev/null +++ b/ARMeilleure/Common/BitUtils.cs @@ -0,0 +1,109 @@ +using System.Runtime.CompilerServices; + +namespace ARMeilleure.Common +{ + static class BitUtils + { + private const int DeBrujinSequence = 0x77cb531; + + private static int[] DeBrujinLbsLut; + + static BitUtils() + { + DeBrujinLbsLut = new int[32]; + + for (int index = 0; index < DeBrujinLbsLut.Length; index++) + { + uint lutIndex = (uint)(DeBrujinSequence * (1 << index)) >> 27; + + DeBrujinLbsLut[lutIndex] = index; + } + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LowestBitSet(int value) + { + if (value == 0) + { + return -1; + } + + int lsb = value & -value; + + return DeBrujinLbsLut[(uint)(DeBrujinSequence * lsb) >> 27]; + } + + public static int HighestBitSet(int value) + { + if (value == 0) + { + return -1; + } + + for (int bit = 31; bit >= 0; bit--) + { + if (((value >> bit) & 1) != 0) + { + return bit; + } + } + + return -1; + } + + private static readonly sbyte[] HbsNibbleLut = { -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3 }; + + public static int HighestBitSetNibble(int value) => HbsNibbleLut[value & 0b1111]; + + public static long Replicate(long bits, int size) + { + long output = 0; + + for (int bit = 0; bit < 64; bit += size) + { + output |= bits << bit; + } + + return output; + } + + public static int CountBits(int value) + { + int count = 0; + + while (value != 0) + { + value &= ~(value & -value); + + count++; + } + + return count; + } + + public static long FillWithOnes(int bits) + { + return bits == 64 ? -1L : (1L << bits) - 1; + } + + public static int RotateRight(int bits, int shift, int size) + { + return (int)RotateRight((uint)bits, shift, size); + } + + public static uint RotateRight(uint bits, int shift, int size) + { + return (bits >> shift) | (bits << (size - shift)); + } + + public static long RotateRight(long bits, int shift, int size) + { + return (long)RotateRight((ulong)bits, shift, size); + } + + public static ulong RotateRight(ulong bits, int shift, int size) + { + return (bits >> shift) | (bits << (size - shift)); + } + } +} diff --git a/ARMeilleure/Common/EnumUtils.cs b/ARMeilleure/Common/EnumUtils.cs new file mode 100644 index 00000000..2a4aa645 --- /dev/null +++ b/ARMeilleure/Common/EnumUtils.cs @@ -0,0 +1,12 @@ +using System; + +namespace ARMeilleure.Common +{ + static class EnumUtils + { + public static int GetCount(Type enumType) + { + return Enum.GetNames(enumType).Length; + } + } +} |