Skip to content

Instantly share code, notes, and snippets.

@binarycow
Last active June 26, 2022 17:56
Show Gist options
  • Save binarycow/a1a617e05b5e61096ec53939b93ae8d3 to your computer and use it in GitHub Desktop.
Save binarycow/a1a617e05b5e61096ec53939b93ae8d3 to your computer and use it in GitHub Desktop.
Generic BitVector
using System.Diagnostics.CodeAnalysis;
public struct BitVector<T>
: IBitVector<BitVector<T>, T>,
IEquatable<T>, IEqualityOperators<BitVector<T>, T>
where T : IEquatable<T>,
IBitwiseOperators<T, T, T>,
IShiftOperators<T, T>,
IMinMaxValue<T>,
IBinaryInteger<T>,
IConvertible,
IUnsignedNumber<T>
{
private const string ArgumentInvalidValueTooSmall = @"Argument {0} should be larger than {1}.";
private const string BitVectorFull = @"Bit vector is full.";
public T Data { get; private set; }
public BitVector(T data) => this.Data = data;
public BitVector(BitVector<T> value) => this.Data = value.Data;
public bool this[int bit]
{
get => (this.Data & (T.One << bit)) != T.Zero;
set => this.Data = value
? this.Data | (T.One << bit)
: this.Data & ~(T.One << bit);
}
public T this[Section section]
{
get => (this.Data & (section.Mask << section.Offset)) >> section.Offset;
set
{
value <<= section.Offset;
var offsetMask = section.Mask << section.Offset;
this.Data = (this.Data & ~offsetMask) | (value & offsetMask);
}
}
private static int PopCountInt(T value) => T.PopCount(value).ToInt32(null);
private static T CreateMask(int bitWidth) => (T.One << bitWidth) - T.One;
public static Section CreateSectionWithWidth(int bitWidth, Section previous = default)
{
return CreateSectionFromMask(CreateMask(ValidateBitWidth(bitWidth)), previous);
static int ValidateBitWidth(int bitWidth) => bitWidth >= 1
? bitWidth
: throw new ArgumentOutOfRangeException(
nameof(bitWidth),
bitWidth,
string.Format(ArgumentInvalidValueTooSmall, nameof(bitWidth), 0)
);
}
// TODO: Once we reference .NET 7, we can remove this method in favor of IBinaryInteger<TSelf>.GetShortestBitLength
// https://docs.microsoft.com/en-us/dotnet/api/system.numerics.ibinaryinteger-1.getshortestbitlength?view=net-7.0
private static int GetShortestBitLength(T value) => BitLength - T.LeadingZeroCount(value).ToInt32(null);
public static Section CreateSectionWithMaxValue(T maxValue, Section previous = default)
=> CreateSectionWithWidth(GetShortestBitLength(maxValue), previous);
private static Section CreateSectionFromMask(T mask, Section previous)
{
var offset = PopCountInt(mask) + previous.Offset;
return offset > BitLength
? throw new InvalidOperationException(BitVectorFull)
: new(mask, offset);
}
public bool Equals(T? other) => this.Data.Equals(other);
public override bool Equals([NotNullWhen(true)] object? o) => o switch
{
BitVector<T> other => this.Equals(other),
T other => this.Equals(other),
_ => false,
};
public bool Equals(BitVector<T> other) => this.Data == other.Data;
public override int GetHashCode() => this.Data.GetHashCode();
private static int BitLength => PopCountInt(T.MaxValue);
private static T MaxMaskBit => T.One << (BitLength - 1);
public override string ToString() => Formatter.ToString(this);
public static BitVector<T> operator &(BitVector<T> left, T right) => new(left.Data & right);
public static BitVector<T> operator |(BitVector<T> left, T right) => new(left.Data | right);
public static BitVector<T> operator ^(BitVector<T> left, T right) => new(left.Data ^ right);
public static BitVector<T> operator ~(BitVector<T> value) => new(~value.Data);
public static bool operator ==(BitVector<T> left, T right) => left.Equals(right);
public static bool operator !=(BitVector<T> left, T right) => left.Equals(right) is false;
public static bool operator ==(BitVector<T> left, BitVector<T> right) => left.Equals(right);
public static bool operator !=(BitVector<T> left, BitVector<T> right) => left.Equals(right) is false;
private static class Formatter
{
// For a BitVector<byte>, with a value of 0x55, the .ToString() output would be in the format:
// BitVector<byte>{01010101}
private static int CalculateToStringLength()
{
var tLength = displayTName.Length;
return nameof(BitVector<T>).Length - 2 /* BitVector< (10) */
+ tLength /* byte (4) */
+ 1 /* > (1) */
+ 1 /* { (1) */
+ BitLength /* 01010101 (8) */
+ 1 /* } (1) */
; /* Total: 25 */
}
// ReSharper disable once StaticMemberInGenericType
private static readonly string displayTName = GetDisplayTName(typeof(T));
// ReSharper disable once StaticMemberInGenericType
private static readonly int toStringLength = CalculateToStringLength();
private static string GetDisplayTName(Type type)
{
var typeName = type.FullName ?? type.Name;
return typeName switch
{
"System.SByte" => "sbyte",
"System.Byte" => "byte",
"System.Int16" => "short",
"System.UInt16" => "ushort",
"System.Int32" => "int",
"System.UInt32" => "uint",
"System.Int64" => "long",
"System.UInt64" => "ulong",
_ => typeName,
};
}
private static ReadOnlySpan<char> Prefix => nameof(BitVector<T>)[..^2];
private static bool TryCopyAndIncrementBuffer(
ref Span<char> buffer,
ReadOnlySpan<char> text
)
{
if (!text.TryCopyTo(buffer)) return false;
buffer = buffer[text.Length..];
return true;
}
private static bool TryCopyAndIncrementBuffer(
ref Span<char> buffer,
char text
)
{
if (buffer.IsEmpty) return false;
buffer[0] = text;
buffer = buffer[1..];
return true;
}
private static bool WriteBit(
BitVector<T> vector,
ref Span<char> buffer,
ref T maskBit
)
{
var isSet = (vector & maskBit) != T.Zero;
return TryCopyAndIncrementBuffer(ref buffer, isSet ? '1' : '0')
&& ShiftBit(ref maskBit);
}
private static bool WriteBits(
BitVector<T> vector,
ref Span<char> buffer
)
{
var mask = MaxMaskBit;
while (WriteBit(vector, ref buffer, ref mask))
{
// Empty loop
}
return buffer.IsEmpty is false;
}
private static bool ShiftBit(ref T maskBit)
{
maskBit >>= 1;
return maskBit != T.One;
}
public static string ToString(BitVector<T> value) => string.Create(
length: toStringLength,
state: value,
action: static (destination, vector)
=> _ = TryCopyAndIncrementBuffer(ref destination, Prefix)
&& TryCopyAndIncrementBuffer(ref destination, displayTName)
&& TryCopyAndIncrementBuffer(ref destination, ">{")
&& WriteBits(vector, ref destination)
&& TryCopyAndIncrementBuffer(ref destination, '}')
);
}
public readonly struct Section : IEquatable<Section>
{
internal Section(T mask, int offset)
{
this.Mask = mask;
this.Offset = offset;
}
public T Mask { get; }
public int Offset { get; }
public override bool Equals([NotNullWhen(true)] object? o) => o is Section other && this.Equals(other);
public bool Equals(Section obj) => obj.Mask == this.Mask && obj.Offset == this.Offset;
public static bool operator ==(Section a, Section b) => a.Equals(b);
public static bool operator !=(Section a, Section b) => a.Equals(b) is false;
public override int GetHashCode() => HashCode.Combine(this.Mask, this.Offset);
public static string ToString(Section value) => $"Section{{0x{value.Mask:x}, 0x{value.Offset:x}}}";
public override string ToString() => ToString(this);
}
}
/*
NES Status Flags
https://www.nesdev.org/wiki/Status_flags
7 bit 0
---- ----
NVss DIZC
|||| ||||
|||| |||+- Carry
|||| ||+-- Zero
|||| |+--- Interrupt Disable
|||| +---- Decimal
||++------ No CPU effect, see: the B flag
|+-------- Overflow
+--------- Negative
*/
var nesFlags = new BitVector<byte>(0x34);
var carry = BitVector<byte>.CreateSectionWithWidth(1);
var zero = BitVector<byte>.CreateSectionWithWidth(1, carry);
var interruptDisable = BitVector<byte>.CreateSectionWithWidth(1, zero);
var decimalMode = BitVector<byte>.CreateSectionWithWidth(1, interruptDisable);
var breakFlags = BitVector<byte>.CreateSectionWithWidth(2, decimalMode);
var overflow = BitVector<byte>.CreateSectionWithWidth(1, breakFlags);
var negative = BitVector<byte>.CreateSectionWithWidth(1, overflow);
Console.Write(nesFlags[negative] == 1 ? 'N' : '-');
Console.Write(nesFlags[overflow] == 1 ? 'V' : '-');
Console.Write("--");
Console.Write(nesFlags[decimalMode] == 1 ? 'D' : '-');
Console.Write(nesFlags[interruptDisable] == 1 ? 'I' : '-');
Console.Write(nesFlags[zero] == 1 ? 'Z' : '-');
Console.Write(nesFlags[carry] == 1 ? 'C' : '-');
Console.WriteLine();
Console.WriteLine(nesFlags.ToString());
public interface IBitVector<TSelf, T>
: IBitwiseOperators<TSelf, T, TSelf>,
IEquatable<TSelf>, IEqualityOperators<TSelf, TSelf>
where TSelf : IBitVector<TSelf, T>
where T : IEquatable<T>,
IBitwiseOperators<T, T, T>,
IShiftOperators<T, T>,
IMinMaxValue<T>,
IBinaryInteger<T>,
IConvertible,
IUnsignedNumber<T>
{
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment