Tag: BigIntX

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;
    }
}