{"id":449,"date":"2021-06-12T03:17:35","date_gmt":"2021-06-12T03:17:35","guid":{"rendered":"https:\/\/michaeljohnsteiner.com\/?p=449"},"modified":"2021-06-12T03:17:35","modified_gmt":"2021-06-12T03:17:35","slug":"digitsarray-cs","status":"publish","type":"post","link":"https:\/\/michaeljohnsteiner.com\/index.php\/2021\/06\/12\/digitsarray-cs\/","title":{"rendered":"DigitsArray.cs"},"content":{"rendered":"\n<p>Support File, for use with <a href=\"https:\/\/michaeljohnsteiner.com\/index.php\/2021\/06\/11\/bigintx-cs\/\" data-type=\"post\" data-id=\"435\">BigIntX.cs<\/a><\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"csharp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">using System;\nusing System.Collections.Generic;\nusing System.Text;\npublic class DigitsArray\n{\n    public static readonly uint   AllBits;\n    public static readonly uint   HiBitSet;\n    public                 uint[] Data;\n    static DigitsArray()\n    {\n        unchecked\n        {\n            AllBits  = ~(uint) 0;\n            HiBitSet = (uint) 1 &lt;&lt; (DataSizeBits - 1);\n        }\n    }\n    public DigitsArray(int size)\n    {\n        Allocate(size, 0);\n    }\n    public DigitsArray(int size, int used)\n    {\n        Allocate(size, used);\n    }\n    public DigitsArray(uint[] copyFrom)\n    {\n        Allocate(copyFrom.Length);\n        CopyFrom(copyFrom, 0, 0, copyFrom.Length);\n        ResetDataUsed();\n    }\n    public DigitsArray(DigitsArray copyFrom)\n    {\n        Allocate(copyFrom.Count - 1, copyFrom.DataUsed);\n        Array.Copy(copyFrom.Data, 0, Data, 0, copyFrom.Count);\n    }\n    public static int DataSizeOf   => sizeof(uint);\n    public static int DataSizeBits => sizeof(uint) * 8;\n    public uint this[int index]\n    {\n        get\n        {\n            if (index &lt; Data.Length)\n                return Data[index];\n            return IsNegative ? AllBits : 0;\n        }\n        set => Data[index] = value;\n    }\n    public int DataUsed\n    {\n        get;\n        set;\n    }\n    public int  Count      => Data.Length;\n    public bool IsZero     => DataUsed == 0 || DataUsed == 1 &amp;&amp; Data[0] == 0;\n    public bool IsNegative => (Data[Data.Length - 1] &amp; HiBitSet) == HiBitSet;\n    public int Sign\n    {\n        get\n        {\n            if (Data[0] == 0)\n                return 0;\n            if (IsNegative)\n                return -1;\n            return 1;\n        }\n    }\n    public void Allocate(int size)\n    {\n        Allocate(size, 0);\n    }\n    public void Allocate(int size, int used)\n    {\n        Data     = new uint[size + 1];\n        DataUsed = used;\n    }\n    public void CopyFrom(uint[] source, int sourceOffset, int offset, int length)\n    {\n        Array.Copy(source, sourceOffset, Data, 0, length);\n    }\n    public void CopyTo(uint[] array, int offset, int length)\n    {\n        Array.Copy(Data, 0, array, offset, length);\n    }\n    public string GetDataAsString()\n    {\n        var result = new StringBuilder();\n        foreach (var data in Data)\n            result.Append(data + \" \");\n        return result.ToString();\n    }\n    public byte[] ToByteArray()\n    {\n        if (Data == null &amp;&amp; Sign == 0)\n            return new byte[1];\n        uint[] dwords;\n        byte   highByte;\n        if (Data == null)\n        {\n            dwords   = new uint[1] {(uint) Sign};\n            highByte = Sign &lt; 0 ? byte.MaxValue : (byte) 0;\n        }\n        else if (Sign == -1)\n        {\n            dwords   = (uint[]) Data.Clone();\n            dwords   = TwosComplement(dwords);\n            highByte = byte.MaxValue;\n        }\n        else\n        {\n            dwords   = Data;\n            highByte = 0;\n        }\n        var bytes   = new byte[checked(4 * dwords.Length)];\n        var curByte = 0;\n        for (var i = 0; i &lt; dwords.Length; ++i)\n        {\n            var dword = dwords[i];\n            for (var j = 0; j &lt; 4; ++j)\n            {\n                bytes[curByte++] =   (byte) (dword &amp; byte.MaxValue);\n                dword            >>= 8;\n            }\n        }\n        var msb = bytes.Length - 1;\n        while (msb > 0 &amp;&amp; bytes[msb] == highByte)\n            --msb;\n        var needExtraByte = (bytes[msb] &amp; 128) != (highByte &amp; 128);\n        var timmedBytes   = new byte[msb + 1 + (needExtraByte ? 1 : 0)];\n        Array.Copy(bytes, timmedBytes, msb + 1);\n        if (needExtraByte)\n            timmedBytes[timmedBytes.Length - 1] = highByte;\n        return timmedBytes;\n    }\n    public uint[] ToUIn32Array()\n    {\n        var value = ToByteArray();\n        var al    = value.Length >> 2;\n        if (al &lt;&lt; 2 != value.Length)\n            al++;\n        var arr = new uint[al];\n        Buffer.BlockCopy(value, 0, arr, 0, value.Length);\n        return arr;\n    }\n    public ulong[] ToUIn64Array()\n    {\n        var value = ToByteArray();\n        var al    = value.Length >> 3;\n        if (al &lt;&lt; 3 != value.Length)\n            al++;\n        var arr = new ulong[al];\n        Buffer.BlockCopy(value, 0, arr, 0, value.Length);\n        return arr;\n    }\n    private static uint[] TwosComplement(uint[] d)\n    {\n        var  i = 0;\n        uint v = 0;\n        for (; i &lt; d.Length; i++)\n        {\n            v    = ~d[i] + 1;\n            d[i] = v;\n            if (v != 0)\n            {\n                i++;\n                break;\n            }\n        }\n        if (v != 0)\n        {\n            for (; i &lt; d.Length; i++)\n                d[i] = ~d[i];\n        }\n        else\n        {\n            Array.Resize(ref d, d.Length + 1);\n            d[d.Length - 1] = 1;\n        }\n        return d;\n    }\n    public void ResetDataUsed()\n    {\n        DataUsed = Data.Length;\n        if (IsNegative)\n        {\n            while (DataUsed > 1 &amp;&amp; Data[DataUsed - 1] == AllBits)\n                --DataUsed;\n            DataUsed++;\n        }\n        else\n        {\n            while (DataUsed > 1 &amp;&amp; Data[DataUsed - 1] == 0)\n                --DataUsed;\n            if (DataUsed == 0)\n                DataUsed = 1;\n        }\n    }\n    public int ShiftRight(int shiftCount)\n    {\n        return ShiftRight(Data, shiftCount);\n    }\n    public static int ShiftRight(uint[] buffer, int shiftCount)\n    {\n        var shiftAmount = DataSizeBits;\n        var invShift    = 0;\n        var bufLen      = buffer.Length;\n        while (bufLen > 1 &amp;&amp; buffer[bufLen - 1] == 0)\n            bufLen--;\n        for (var count = shiftCount; count > 0; count -= shiftAmount)\n        {\n            if (count &lt; shiftAmount)\n            {\n                shiftAmount = count;\n                invShift    = DataSizeBits - shiftAmount;\n            }\n            ulong carry = 0;\n            for (var i = bufLen - 1; i >= 0; i--)\n            {\n                var val = (ulong) buffer[i] >> shiftAmount;\n                val       |= carry;\n                carry     =  (ulong) buffer[i] &lt;&lt; invShift;\n                buffer[i] =  (uint) val;\n            }\n        }\n        while (bufLen > 1 &amp;&amp; buffer[bufLen - 1] == 0)\n            bufLen--;\n        return bufLen;\n    }\n    public int ShiftLeft(int shiftCount)\n    {\n        return ShiftLeft(Data, shiftCount);\n    }\n    public static int ShiftLeft(uint[] buffer, int shiftCount)\n    {\n        var shiftAmount = DataSizeBits;\n        var bufLen      = buffer.Length;\n        while (bufLen > 1 &amp;&amp; buffer[bufLen - 1] == 0)\n            bufLen--;\n        for (var count = shiftCount; count > 0; count -= shiftAmount)\n        {\n            if (count &lt; shiftAmount)\n                shiftAmount = count;\n            ulong carry = 0;\n            for (var i = 0; i &lt; bufLen; i++)\n            {\n                var val = (ulong) buffer[i] &lt;&lt; shiftAmount;\n                val       |= carry;\n                buffer[i] =  (uint) (val &amp; AllBits);\n                carry     =  val >> DataSizeBits;\n            }\n            if (carry != 0)\n            {\n                if (bufLen + 1 &lt;= buffer.Length)\n                {\n                    buffer[bufLen] = (uint) carry;\n                    bufLen++;\n                    carry = 0;\n                }\n                else\n                {\n                    throw new OverflowException();\n                }\n            }\n        }\n        return bufLen;\n    }\n    public int ShiftLeftWithoutOverflow(int shiftCount)\n    {\n        if (shiftCount == 0) return Data.Length;\n        var temporary   = new List&lt;uint>(Data);\n        var shiftAmount = DataSizeBits;\n        for (var count = shiftCount; count > 0; count -= shiftAmount)\n        {\n            if (count &lt; shiftAmount)\n                shiftAmount = count;\n            ulong carry = 0;\n            for (var i = 0; i &lt; temporary.Count; i++)\n            {\n                var val = (ulong) temporary[i] &lt;&lt; shiftAmount;\n                val          |= carry;\n                temporary[i] =  (uint) (val &amp; AllBits);\n                carry        =  val >> DataSizeBits;\n            }\n            if (carry != 0)\n            {\n                var lastNum = (uint) carry;\n                if (IsNegative)\n                {\n                    var byteCount = (int) Math.Floor(Math.Log(carry, 2));\n                    lastNum = (0xffffffff &lt;&lt; byteCount) | (uint) carry;\n                }\n                temporary.Add(lastNum);\n            }\n        }\n        Data = new uint[temporary.Count];\n        temporary.CopyTo(Data);\n        return Data.Length;\n    }\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Support File, for use with BigIntX.cs<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[186],"_links":{"self":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/449"}],"collection":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/comments?post=449"}],"version-history":[{"count":1,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/449\/revisions"}],"predecessor-version":[{"id":450,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/449\/revisions\/450"}],"wp:attachment":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/media?parent=449"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/categories?post=449"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/tags?post=449"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}