Support File, for use with BigIntX.cs
using System;
using System.Collections.Generic;
using System.Text;
public class DigitsArray
{
public static readonly uint AllBits;
public static readonly uint HiBitSet;
public uint[] Data;
static DigitsArray()
{
unchecked
{
AllBits = ~(uint) 0;
HiBitSet = (uint) 1 << (DataSizeBits - 1);
}
}
public DigitsArray(int size)
{
Allocate(size, 0);
}
public DigitsArray(int size, int used)
{
Allocate(size, used);
}
public DigitsArray(uint[] copyFrom)
{
Allocate(copyFrom.Length);
CopyFrom(copyFrom, 0, 0, copyFrom.Length);
ResetDataUsed();
}
public DigitsArray(DigitsArray copyFrom)
{
Allocate(copyFrom.Count - 1, copyFrom.DataUsed);
Array.Copy(copyFrom.Data, 0, Data, 0, copyFrom.Count);
}
public static int DataSizeOf => sizeof(uint);
public static int DataSizeBits => sizeof(uint) * 8;
public uint this[int index]
{
get
{
if (index < Data.Length)
return Data[index];
return IsNegative ? AllBits : 0;
}
set => Data[index] = value;
}
public int DataUsed
{
get;
set;
}
public int Count => Data.Length;
public bool IsZero => DataUsed == 0 || DataUsed == 1 && Data[0] == 0;
public bool IsNegative => (Data[Data.Length - 1] & HiBitSet) == HiBitSet;
public int Sign
{
get
{
if (Data[0] == 0)
return 0;
if (IsNegative)
return -1;
return 1;
}
}
public void Allocate(int size)
{
Allocate(size, 0);
}
public void Allocate(int size, int used)
{
Data = new uint[size + 1];
DataUsed = used;
}
public void CopyFrom(uint[] source, int sourceOffset, int offset, int length)
{
Array.Copy(source, sourceOffset, Data, 0, length);
}
public void CopyTo(uint[] array, int offset, int length)
{
Array.Copy(Data, 0, array, offset, length);
}
public string GetDataAsString()
{
var result = new StringBuilder();
foreach (var data in Data)
result.Append(data + " ");
return result.ToString();
}
public byte[] ToByteArray()
{
if (Data == null && Sign == 0)
return new byte[1];
uint[] dwords;
byte highByte;
if (Data == null)
{
dwords = new uint[1] {(uint) Sign};
highByte = Sign < 0 ? byte.MaxValue : (byte) 0;
}
else if (Sign == -1)
{
dwords = (uint[]) Data.Clone();
dwords = TwosComplement(dwords);
highByte = byte.MaxValue;
}
else
{
dwords = Data;
highByte = 0;
}
var bytes = new byte[checked(4 * dwords.Length)];
var curByte = 0;
for (var i = 0; i < dwords.Length; ++i)
{
var dword = dwords[i];
for (var j = 0; j < 4; ++j)
{
bytes[curByte++] = (byte) (dword & byte.MaxValue);
dword >>= 8;
}
}
var msb = bytes.Length - 1;
while (msb > 0 && bytes[msb] == highByte)
--msb;
var needExtraByte = (bytes[msb] & 128) != (highByte & 128);
var timmedBytes = new byte[msb + 1 + (needExtraByte ? 1 : 0)];
Array.Copy(bytes, timmedBytes, msb + 1);
if (needExtraByte)
timmedBytes[timmedBytes.Length - 1] = highByte;
return timmedBytes;
}
public uint[] ToUIn32Array()
{
var value = ToByteArray();
var al = value.Length >> 2;
if (al << 2 != value.Length)
al++;
var arr = new uint[al];
Buffer.BlockCopy(value, 0, arr, 0, value.Length);
return arr;
}
public ulong[] ToUIn64Array()
{
var value = ToByteArray();
var al = value.Length >> 3;
if (al << 3 != value.Length)
al++;
var arr = new ulong[al];
Buffer.BlockCopy(value, 0, arr, 0, value.Length);
return arr;
}
private static uint[] TwosComplement(uint[] d)
{
var i = 0;
uint v = 0;
for (; i < d.Length; i++)
{
v = ~d[i] + 1;
d[i] = v;
if (v != 0)
{
i++;
break;
}
}
if (v != 0)
{
for (; i < d.Length; i++)
d[i] = ~d[i];
}
else
{
Array.Resize(ref d, d.Length + 1);
d[d.Length - 1] = 1;
}
return d;
}
public void ResetDataUsed()
{
DataUsed = Data.Length;
if (IsNegative)
{
while (DataUsed > 1 && Data[DataUsed - 1] == AllBits)
--DataUsed;
DataUsed++;
}
else
{
while (DataUsed > 1 && Data[DataUsed - 1] == 0)
--DataUsed;
if (DataUsed == 0)
DataUsed = 1;
}
}
public int ShiftRight(int shiftCount)
{
return ShiftRight(Data, shiftCount);
}
public static int ShiftRight(uint[] buffer, int shiftCount)
{
var shiftAmount = DataSizeBits;
var invShift = 0;
var bufLen = buffer.Length;
while (bufLen > 1 && buffer[bufLen - 1] == 0)
bufLen--;
for (var count = shiftCount; count > 0; count -= shiftAmount)
{
if (count < shiftAmount)
{
shiftAmount = count;
invShift = DataSizeBits - shiftAmount;
}
ulong carry = 0;
for (var i = bufLen - 1; i >= 0; i--)
{
var val = (ulong) buffer[i] >> shiftAmount;
val |= carry;
carry = (ulong) buffer[i] << invShift;
buffer[i] = (uint) val;
}
}
while (bufLen > 1 && buffer[bufLen - 1] == 0)
bufLen--;
return bufLen;
}
public int ShiftLeft(int shiftCount)
{
return ShiftLeft(Data, shiftCount);
}
public static int ShiftLeft(uint[] buffer, int shiftCount)
{
var shiftAmount = DataSizeBits;
var bufLen = buffer.Length;
while (bufLen > 1 && buffer[bufLen - 1] == 0)
bufLen--;
for (var count = shiftCount; count > 0; count -= shiftAmount)
{
if (count < shiftAmount)
shiftAmount = count;
ulong carry = 0;
for (var i = 0; i < bufLen; i++)
{
var val = (ulong) buffer[i] << shiftAmount;
val |= carry;
buffer[i] = (uint) (val & AllBits);
carry = val >> DataSizeBits;
}
if (carry != 0)
{
if (bufLen + 1 <= buffer.Length)
{
buffer[bufLen] = (uint) carry;
bufLen++;
carry = 0;
}
else
{
throw new OverflowException();
}
}
}
return bufLen;
}
public int ShiftLeftWithoutOverflow(int shiftCount)
{
if (shiftCount == 0) return Data.Length;
var temporary = new List<uint>(Data);
var shiftAmount = DataSizeBits;
for (var count = shiftCount; count > 0; count -= shiftAmount)
{
if (count < shiftAmount)
shiftAmount = count;
ulong carry = 0;
for (var i = 0; i < temporary.Count; i++)
{
var val = (ulong) temporary[i] << shiftAmount;
val |= carry;
temporary[i] = (uint) (val & AllBits);
carry = val >> DataSizeBits;
}
if (carry != 0)
{
var lastNum = (uint) carry;
if (IsNegative)
{
var byteCount = (int) Math.Floor(Math.Log(carry, 2));
lastNum = (0xffffffff << byteCount) | (uint) carry;
}
temporary.Add(lastNum);
}
}
Data = new uint[temporary.Count];
temporary.CopyTo(Data);
return Data.Length;
}
}