//
// System.Numerics.BigInteger
//
// Authors:
// Rodrigo Kumpera (rkumpera@novell.com)
// Marek Safar  <marek.safar@gmail.com>
//
// Copyright (C) 2010 Novell, Inc (http://www.novell.com)
// Copyright (C) 2014 Xamarin Inc (http://www.xamarin.com)
//
// Permission is hereby granted, free of charge, to any person obtaining
// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
// 
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
// 
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
// A big chuck of code comes the DLR (as hosted in http://ironpython.codeplex.com), 
// which has the following License:
//
/* ****************************************************************************
*
* Copyright (c) Microsoft Corporation.
*
* This source code is subject to terms and conditions of the Microsoft Public License. A
* copy of the license can be found in the License.html file at the root of this distribution. If
* you cannot locate the Microsoft Public License, please send an email to
* dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
* by the terms of the Microsoft Public License.
*
* You must not remove this notice, or any other, from this software.
*
*
* ***************************************************************************/

using System;
using System.Collections.Generic;
using System.Globalization;

using Renci.SshNet.Abstractions;

/*
 * Optimization:
 * - Have proper popcount function for IsPowerOfTwo
 * - Use unsafe ops to avoid bounds check
 * - CoreAdd could avoid some resizes by checking for equal sized array that top overflow
 * - For bitwise operators, hoist the conditionals out of their main loop
 * - Optimize BitScanBackward
 * - Use a carry variable to make shift opts do half the number of array ops.
 * -Schoolbook multiply is O(n^2), use Karatsuba /Toom-3 for large numbers
 */
namespace Renci.SshNet.Common
{
    /// <summary>
    /// Represents an arbitrarily large signed integer.
    /// </summary>
    public struct BigInteger : IComparable, IFormattable, IComparable<BigInteger>, IEquatable<BigInteger>
    {
        private const ulong Base = 0x100000000;
        private const int Bias = 1075;
        private const int DecimalSignMask = unchecked((int)0x80000000);

        private static readonly BigInteger ZeroSingleton = new BigInteger(0);
        private static readonly BigInteger OneSingleton = new BigInteger(1);
        private static readonly BigInteger MinusOneSingleton = new BigInteger(-1);

        // LSB on [0]
        private readonly uint[] _data;
        private readonly short _sign;

        #region SSH.NET additions

        /// <summary>
        /// Gets number of bits used by the number.
        /// </summary>
        /// <value>
        /// The number of the bit used.
        /// </value>
        public readonly int BitLength
        {
            get
            {
                if (_sign == 0)
                {
                    return 0;
                }

                var msbIndex = _data.Length - 1;

                while (_data[msbIndex] == 0)
                {
                    msbIndex--;
                }

                var msbBitCount = BitScanBackward(_data[msbIndex]) + 1;

                return msbIndex * 4 * 8 + msbBitCount + ((_sign > 0) ? 0 : 1);
            }
        }

        /// <summary>
        /// Mods the inverse.
        /// </summary>
        /// <param name="bi">The bi.</param>
        /// <param name="modulus">The modulus.</param>
        /// <returns>
        /// Modulus inverted number.
        /// </returns>
        public static BigInteger ModInverse(BigInteger bi, BigInteger modulus)
        {
            BigInteger a = modulus, b = bi % modulus;
            BigInteger p0 = 0, p1 = 1;

            while (!b.IsZero)
            {
                if (b.IsOne)
                {
                    return p1;
                }

                p0 += (a / b) * p1;
                a %= b;

                if (a.IsZero)
                {
                    break;
                }

                if (a.IsOne)
                {
                    return modulus - p0;
                }

                p1 += (b / a) * p0;
                b %= a;

            }
            return 0;
        }

        /// <summary>
        /// Returns positive remainder that results from division with two specified <see cref="BigInteger"/> values.
        /// </summary>
        /// <param name="dividend">The value to be divided.</param>
        /// <param name="divisor">The value to divide by.</param>
        /// <returns>
        /// Positive remainder that results from the division.
        /// </returns>
        public static BigInteger PositiveMod(BigInteger dividend, BigInteger divisor)
        {
            var result = dividend % divisor;

            if (result < 0)
            {
                result += divisor;
            }

            return result;
        }

        /// <summary>
        /// Generates a new, random <see cref="BigInteger"/> of the specified length.
        /// </summary>
        /// <param name="bitLength">The number of bits for the new number.</param>
        /// <returns>A random number of the specified length.</returns>
        public static BigInteger Random(int bitLength)
        {
            var bytesArray = new byte[(bitLength / 8) + (((bitLength % 8) > 0) ? 1 : 0)];
            CryptoAbstraction.GenerateRandom(bytesArray);
            bytesArray[bytesArray.Length - 1] = (byte) (bytesArray[bytesArray.Length - 1] & 0x7F); // Ensure not a negative value
            return new BigInteger(bytesArray);
        }

        #endregion SSH.NET additions

        private BigInteger(short sign, uint[] data)
        {
            _sign = sign;
            _data = data;
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BigInteger"/> structure using a 32-bit signed integer value.
        /// </summary>
        /// <param name="value">A 32-bit signed integer.</param>
        public BigInteger(int value)
        {
            if (value == 0)
            {
                _sign = 0;
                _data = null;
            }
            else if (value > 0)
            {
                _sign = 1;
                _data = new[] { (uint) value };
            }
            else
            {
                _sign = -1;
                _data = new[] { (uint) -value };
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BigInteger"/> structure using an unsigned 32-bit integer value.
        /// </summary>
        /// <param name="value">An unsigned 32-bit integer value.</param>
        [CLSCompliant(false)]
        public BigInteger(uint value)
        {
            if (value == 0)
            {
                _sign = 0;
                _data = null;
            }
            else
            {
                _sign = 1;
                _data = new[] { value };
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BigInteger"/> structure using a 64-bit signed integer value.
        /// </summary>
        /// <param name="value">A 64-bit signed integer.</param>
        public BigInteger(long value)
        {
            if (value == 0)
            {
                _sign = 0;
                _data = null;
            }
            else if (value > 0)
            {
                _sign = 1;
                var low = (uint)value;
                var high = (uint)(value >> 32);

                _data = new uint[high != 0 ? 2 : 1];
                _data[0] = low;
                if (high != 0)
                {
                    _data[1] = high;
                }
            }
            else
            {
                _sign = -1;
                value = -value;
                var low = (uint)value;
                var high = (uint)((ulong)value >> 32);

                _data = new uint[high != 0 ? 2 : 1];
                _data[0] = low;
                if (high != 0)
                {
                    _data[1] = high;
                }
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BigInteger"/> structure with an unsigned 64-bit integer value.
        /// </summary>
        /// <param name="value">An unsigned 64-bit integer.</param>
        [CLSCompliant(false)]
        public BigInteger(ulong value)
        {
            if (value == 0)
            {
                _sign = 0;
                _data = null;
            }
            else
            {
                _sign = 1;
                var low = (uint) value;
                var high = (uint) (value >> 32);

                _data = new uint[high != 0 ? 2 : 1];
                _data[0] = low;
                if (high != 0)
                {
                    _data[1] = high;
                }
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BigInteger"/> structure using a double-precision floating-point value.
        /// </summary>
        /// <param name="value">A double-precision floating-point value.</param>
        public BigInteger(double value)
        {
            if (double.IsNaN(value) || double.IsInfinity(value))
            {
                throw new OverflowException();
            }

            var bytes = BitConverter.GetBytes(value);
            var mantissa = Mantissa(bytes);
            if (mantissa == 0)
            {
                // 1.0 * 2**exp, we have a power of 2
                int exponent = Exponent(bytes);
                if (exponent == 0)
                {
                    _sign = 0;
                    _data = null;
                    return;
                }

                var res = Negative(bytes) ? MinusOne : One;
                res <<= exponent - 0x3ff;
                _sign = res._sign;
                _data = res._data;
            }
            else
            {
                // 1.mantissa * 2**exp
                int exponent = Exponent(bytes);
                mantissa |= 0x10000000000000ul;
                BigInteger res = mantissa;
                res = exponent > Bias ? res << (exponent - Bias) : res >> (Bias - exponent);

                _sign = (short) (Negative(bytes) ? -1 : 1);
                _data = res._data;
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BigInteger"/> structure using a single-precision floating-point value.
        /// </summary>
        /// <param name="value">A single-precision floating-point value.</param>
        public BigInteger(float value)
            : this((double) value)
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BigInteger"/> structure using a <see cref="decimal"/> value.
        /// </summary>
        /// <param name="value">A decimal number.</param>
        public BigInteger(decimal value)
        {
            // First truncate to get scale to 0 and extract bits
            var bits = decimal.GetBits(decimal.Truncate(value));

            var size = 3;
            while (size > 0 && bits[size - 1] == 0)
            {
                size--;
            }

            if (size == 0)
            {
                _sign = 0;
                _data = null;
                return;
            }

            _sign = (short) ((bits[3] & DecimalSignMask) != 0 ? -1 : 1);

            _data = new uint[size];
            _data[0] = (uint) bits[0];
            if (size > 1)
            {
                _data[1] = (uint) bits[1];
            }

            if (size > 2)
            {
                _data[2] = (uint) bits[2];
            }
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BigInteger"/> structure using the values in a byte array.
        /// </summary>
        /// <param name="value">An array of <see cref="byte"/> values in little-endian order.</param>
        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <c>null</c>.</exception>
        [CLSCompliant(false)]
        public BigInteger(byte[] value)
        {
            if (value is null)
            {
                throw new ArgumentNullException(nameof(value));
            }

            var len = value.Length;

            if (len == 0 || (len == 1 && value[0] == 0))
            {
                _sign = 0;
                _data = null;
                return;
            }

            if ((value[len - 1] & 0x80) != 0)
            {
                _sign = -1;
            }
            else
            {
                _sign = 1;
            }

            if (_sign == 1)
            {
                while (value[len - 1] == 0)
                {
                    if (--len == 0)
                    {
                        _sign = 0;
                        _data = null;
                        return;
                    }
                }

                int size;
                var fullWords = size = len / 4;
                if ((len & 0x3) != 0)
                {
                    ++size;
                }

                _data = new uint[size];
                var j = 0;
                for (var i = 0; i < fullWords; ++i)
                {
                    _data[i] = (uint) value[j++] |
                               (uint) (value[j++] << 8) |
                               (uint) (value[j++] << 16) |
                               (uint) (value[j++] << 24);
                }

                size = len & 0x3;
                if (size > 0)
                {
                    var idx = _data.Length - 1;
                    for (var i = 0; i < size; ++i)
                    {
                        _data[idx] |= (uint) (value[j++] << (i * 8));
                    }
                }
            }
            else
            {
                int size;
                var fullWords = size = len / 4;
                if ((len & 0x3) != 0)
                {
                    ++size;
                }

                _data = new uint[size];

                uint word, borrow = 1;
                ulong sub;
                var j = 0;

                for (var i = 0; i < fullWords; ++i)
                {
                    word = (uint) value[j++] |
                           (uint) (value[j++] << 8) |
                           (uint) (value[j++] << 16) |
                           (uint) (value[j++] << 24);

                    sub = (ulong) word - borrow;
                    word = (uint) sub;
                    borrow = (uint) (sub >> 32) & 0x1u;
                    _data[i] = ~word;
                }

                size = len & 0x3;

                if (size > 0)
                {
                    word = 0;
                    uint storeMask = 0;
                    for (var i = 0; i < size; ++i)
                    {
                        word |= (uint) (value[j++] << (i * 8));
                        storeMask = (storeMask << 8) | 0xFF;
                    }

                    sub = word - borrow;
                    word = (uint) sub;
                    borrow = (uint) (sub >> 32) & 0x1u;

                    if ((~word & storeMask) == 0)
                    {
                        Array.Resize(ref _data, _data.Length - 1);
                    }
                    else
                    {
                        _data[_data.Length - 1] = ~word & storeMask;
                    }
                }

                if (borrow != 0)
                {
                    // FIXME I believe this can't happen, can someone write a test for it?
                    throw new Exception("non zero final carry");
                }
            }
        }

        private static bool Negative(byte[] v)
        {
            return (v[7] & 0x80) != 0;
        }

        private static ushort Exponent(byte[] v)
        {
            return (ushort)((((ushort)(v[7] & 0x7F)) << (ushort)4) | (((ushort)(v[6] & 0xF0)) >> 4));
        }

        private static ulong Mantissa(byte[] v)
        {
            var i1 = (uint)v[0] | ((uint)v[1] << 8) | ((uint)v[2] << 16) | ((uint)v[3] << 24);
            var i2 = (uint)v[4] | ((uint)v[5] << 8) | ((uint)(v[6] & 0xF) << 16);

            return ((ulong) i1 | ((ulong) i2 << 32));
        }

        /// <summary>
        /// Gets a value indicating whether the value of the current <see cref="BigInteger"/> object is an even number.
        /// </summary>
        /// <value>
        /// <c>true</c> if the value of the BigInteger object is an even number; otherwise, <c>false</c>.
        /// </value>
        public readonly bool IsEven
        {
            get { return _sign == 0 || (_data[0] & 0x1) == 0; }
        }

        /// <summary>
        /// Gets a value indicating whether the value of the current <see cref="BigInteger"/> object is <see cref="One"/>.
        /// </summary>
        /// <value>
        /// <c>true</c> if the value of the <see cref="BigInteger"/> object is <see cref="One"/>;
        /// otherwise, <c>false</c>.
        /// </value>
        public readonly bool IsOne
        {
            get { return _sign == 1 && _data.Length == 1 && _data[0] == 1; }
        }

        // Gem from Hacker's Delight
        // Returns the number of bits set in @x
        private static int PopulationCount(uint x)
        {
            x -= (x >> 1) & 0x55555555;
            x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
            x = (x + (x >> 4)) & 0x0F0F0F0F;
            x += x >> 8;
            x += x >> 16;
            return (int) (x & 0x0000003F);
        }

        /// <summary>
        /// Returns the number of bits set in <paramref name="x"/>.
        /// </summary>
        /// <returns>
        /// The number of bits set in <paramref name="x"/>.
        /// </returns>
        /// <remarks>
        /// Based on code by Zilong Tan on Ulib released under MIT license.
        /// </remarks>
        private static int PopulationCount(ulong x)
        {
            x -= (x >> 1) & 0x5555555555555555UL;
            x = (x & 0x3333333333333333UL) + ((x >> 2) & 0x3333333333333333UL);
            x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fUL;
            return (int)((x * 0x0101010101010101UL) >> 56);
        }

        private static int LeadingZeroCount(uint value)
        {
            value |= value >> 1;
            value |= value >> 2;
            value |= value >> 4;
            value |= value >> 8;
            value |= value >> 16;
            return 32 - PopulationCount(value); // 32 = bits in uint
        }

        private static int LeadingZeroCount(ulong value)
        {
            value |= value >> 1;
            value |= value >> 2;
            value |= value >> 4;
            value |= value >> 8;
            value |= value >> 16;
            value |= value >> 32;
            return 64 - PopulationCount(value); // 64 = bits in ulong
        }

        private static double BuildDouble(int sign, ulong mantissa, int exponent)
        {
            const int exponentBias = 1023;
            const int mantissaLength = 52;
            const int exponentLength = 11;
            const int maxExponent = 2046;
            const long mantissaMask = 0xfffffffffffffL;
            const long exponentMask = 0x7ffL;
            const ulong negativeMark = 0x8000000000000000uL;

            if (sign == 0 || mantissa == 0)
            {
                return 0.0;
            }

            exponent += exponentBias + mantissaLength;
            var offset = LeadingZeroCount(mantissa) - exponentLength;
            if (exponent - offset > maxExponent)
            {
                return sign > 0 ? double.PositiveInfinity : double.NegativeInfinity;
            }

            if (offset < 0)
            {
                mantissa >>= -offset;
                exponent += -offset;
            }
            else if (offset >= exponent)
            {
                mantissa <<= exponent - 1;
                exponent = 0;
            }
            else
            {
                mantissa <<= offset;
                exponent -= offset;
            }

            mantissa &= mantissaMask;

            if ((exponent & exponentMask) == exponent)
            {
                unchecked
                {
                    var bits = mantissa | ((ulong)exponent << mantissaLength);
                    if (sign < 0)
                    {
                        bits |= negativeMark;
                    }

                    return BitConverter.Int64BitsToDouble((long)bits);
                }
            }

            return sign > 0 ? double.PositiveInfinity : double.NegativeInfinity;
        }

        /// <summary>
        /// Gets a value Indicating whether the value of the current <see cref="BigInteger"/> object is a power of two.
        /// </summary>
        /// <value>
        /// <c>true</c> if the value of the <see cref="BigInteger"/> object is a power of two;
        /// otherwise, <c>false</c>.
        /// </value>
        public readonly bool IsPowerOfTwo
        {
            get
            {
                if (_sign != 1)
                {
                    return false;
                }

                var foundBit = false;

                // This function is pop count == 1 for positive numbers
                foreach (var bit in _data)
                {
                    var p = PopulationCount(bit);
                    if (p > 0)
                    {
                        if (p > 1 || foundBit)
                        {
                            return false;
                        }

                        foundBit = true;
                    }
                }

                return foundBit;
            }
        }

        /// <summary>
        /// Gets a value indicating whether the value of the current <see cref="BigInteger"/> object is <see cref="Zero"/>.
        /// </summary>
        /// <value>
        /// <c>true</c> if the value of the <see cref="BigInteger"/> object is <see cref="Zero"/>;
        /// otherwise, <c>false</c>.
        /// </value>
        public readonly bool IsZero
        {
            get { return _sign == 0; }
        }

        /// <summary>
        /// Gets a number that indicates the sign (negative, positive, or zero) of the current <see cref="BigInteger"/> object.
        /// </summary>
        /// <value>
        /// A number that indicates the sign of the <see cref="BigInteger"/> object.
        /// </value>
        public readonly int Sign
        {
            get { return _sign; }
        }

        /// <summary>
        /// Gets a value that represents the number negative one (-1).
        /// </summary>
        /// <value>
        /// An integer whose value is negative one (-1).
        /// </value>
        public static BigInteger MinusOne
        {
            get { return MinusOneSingleton; }
        }

        /// <summary>
        /// Gets a value that represents the number one (1).
        /// </summary>
        /// <value>
        /// An object whose value is one (1).
        /// </value>
        public static BigInteger One
        {
            get { return OneSingleton; }
        }

        /// <summary>
        /// Gets a value that represents the number 0 (zero).
        /// </summary>
        /// <value>
        /// An integer whose value is 0 (zero).
        /// </value>
        public static BigInteger Zero
        {
            get { return ZeroSingleton; }
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a 32-bit signed integer value.
        /// </summary>
        /// <param name="value">The value to convert to a 32-bit signed integer.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static explicit operator int(BigInteger value)
        {
            if (value._data is null)
            {
                return 0;
            }

            if (value._data.Length > 1)
            {
                throw new OverflowException();
            }

            var data = value._data[0];

            if (value._sign == 1)
            {
                if (data > (uint) int.MaxValue)
                {
                    throw new OverflowException();
                }

                return (int)data;
            }

            if (value._sign == -1)
            {
                if (data > 0x80000000u)
                {
                    throw new OverflowException();
                }

                return -(int)data;
            }

            return 0;
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to an unsigned 32-bit integer value.
        /// </summary>
        /// <param name="value">The value to convert to an unsigned 32-bit integer.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        [CLSCompliant(false)]
        public static explicit operator uint(BigInteger value)
        {
            if (value._data is null)
            {
                return 0;
            }

            if (value._data.Length > 1 || value._sign == -1)
            {
                throw new OverflowException();
            }

            return value._data[0];
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a 16-bit signed integer value.
        /// </summary>
        /// <param name="value">The value to convert to a 16-bit signed integer.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static explicit operator short(BigInteger value)
        {
            var val = (int) value;
            if (val is < short.MinValue or > short.MaxValue)
            {
                throw new OverflowException();
            }

            return (short) val;
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a 16-bit unsigned integer value.
        /// </summary>
        /// <param name="value">The value to convert to a 16-bit unsigned integer.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        [CLSCompliant(false)]
        public static explicit operator ushort(BigInteger value)
        {
            var val = (uint) value;
            if (val > ushort.MaxValue)
            {
                throw new OverflowException();
            }

            return (ushort) val;
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to an unsigned byte value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="byte"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static explicit operator byte(BigInteger value)
        {
            var val = (uint) value;
            if (val > byte.MaxValue)
            {
                throw new OverflowException();
            }

            return (byte) val;
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a signed 8-bit value.
        /// </summary>
        /// <param name="value">The value to convert to a signed 8-bit value.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        [CLSCompliant(false)]
        public static explicit operator sbyte(BigInteger value)
        {
            var val = (int) value;
            if (val is < sbyte.MinValue or > sbyte.MaxValue)
            {
                throw new OverflowException();
            }

            return (sbyte) val;
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a 64-bit signed integer value.
        /// </summary>
        /// <param name="value">The value to convert to a 64-bit signed integer.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static explicit operator long(BigInteger value)
        {
            if (value._data is null)
            {
                return 0;
            }

            if (value._data.Length > 2)
            {
                throw new OverflowException();
            }

            var low = value._data[0];

            if (value._data.Length == 1)
            {
                if (value._sign == 1)
                {
                    return (long) low;
                }

                var res = (long)low;
                return -res;
            }

            var high = value._data[1];

            if (value._sign == 1)
            {
                if (high >= 0x80000000u)
                {
                    throw new OverflowException();
                }

                return (((long)high) << 32) | low;
            }

            /*
            We cannot represent negative numbers smaller than long.MinValue.
            Those values are encoded into what look negative numbers, so negating
            them produces a positive value, that's why it's safe to check for that
            condition.

            long.MinValue works fine since it's bigint encoding looks like a negative
            number, but since long.MinValue == -long.MinValue, we're good.
            */

            var result = -((((long)high) << 32) | (long)low);
            if (result > 0)
            {
                throw new OverflowException();
            }

            return result;
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to an unsigned 64-bit integer value.
        /// </summary>
        /// <param name="value">The value to convert to an unsigned 64-bit integer.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        [CLSCompliant(false)]
        public static explicit operator ulong(BigInteger value)
        {
            if (value._data is null)
            {
                return 0;
            }

            if (value._data.Length > 2 || value._sign == -1)
            {
                throw new OverflowException();
            }

            var low = value._data[0];
            if (value._data.Length == 1)
            {
                return low;
            }

            var high = value._data[1];
            return (((ulong)high) << 32) | low;
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a <see cref="double"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="double"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static explicit operator double(BigInteger value)
        {
            if (value._data is null)
            {
                return 0.0;
            }

            switch (value._data.Length)
            {
                case 1:
                    return BuildDouble(value._sign, value._data[0], 0);
                case 2:
                    return BuildDouble(value._sign, (ulong) value._data[1] << 32 | (ulong) value._data[0], 0);
                default:
                    var index = value._data.Length - 1;
                    var word = value._data[index];
                    var mantissa = ((ulong)word << 32) | value._data[index - 1];
                    var missing = LeadingZeroCount(word) - 11; // 11 = bits in exponent
                    if (missing > 0)
                    {
                        // add the missing bits from the next word
                        mantissa = (mantissa << missing) | (value._data[index - 2] >> (32 - missing));
                    }
                    else
                    {
                        mantissa >>= -missing;
                    }

                    return BuildDouble(value._sign, mantissa, ((value._data.Length - 2) * 32) - missing);
            }
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a single-precision floating-point value.
        /// </summary>
        /// <param name="value">The value to convert to a single-precision floating-point value.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static explicit operator float(BigInteger value)
        {
            return (float) (double) value;
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="BigInteger"/> object to a <see cref="decimal"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="decimal"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static explicit operator decimal(BigInteger value)
        {
            if (value._data is null)
            {
                return decimal.Zero;
            }

            var data = value._data;
            if (data.Length > 3)
            {
                throw new OverflowException();
            }

            int lo = 0, mi = 0, hi = 0;
            if (data.Length > 2)
            {
                hi = (int) data[2];
            }

            if (data.Length > 1)
            {
                mi = (int) data[1];
            }

            if (data.Length > 0)
            {
                lo = (int) data[0];
            }

            return new decimal(lo, mi, hi, value._sign < 0, 0);
        }

        /// <summary>
        /// Defines an implicit conversion of a signed 32-bit integer to a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static implicit operator BigInteger(int value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// Defines an implicit conversion of a 32-bit unsigned integer to a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        [CLSCompliant(false)]
        public static implicit operator BigInteger(uint value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// Defines an implicit conversion of a signed 16-bit integer to a BigInteger value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static implicit operator BigInteger(short value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// Defines an implicit conversion of a 16-bit unsigned integer to a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        [CLSCompliant(false)]
        public static implicit operator BigInteger(ushort value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// Defines an implicit conversion of an unsigned byte to a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static implicit operator BigInteger(byte value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        [CLSCompliant(false)]
        public static implicit operator BigInteger(sbyte value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// Defines an implicit conversion of a signed 64-bit integer to a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static implicit operator BigInteger(long value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// Defines an implicit conversion of a 64-bit unsigned integer to a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        [CLSCompliant(false)]
        public static implicit operator BigInteger(ulong value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="double"/> value to a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static explicit operator BigInteger(double value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="float"/> object to a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static explicit operator BigInteger(float value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// Defines an explicit conversion of a <see cref="decimal"/> object to a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to convert to a <see cref="BigInteger"/>.</param>
        /// <returns>
        /// An object that contains the value of the <paramref name="value"/> parameter.
        /// </returns>
        public static explicit operator BigInteger(decimal value)
        {
            return new BigInteger(value);
        }

        /// <summary>
        /// Adds the values of two specified <see cref="BigInteger"/> objects.
        /// </summary>
        /// <param name="left">The first value to add.</param>
        /// <param name="right">The second value to add.</param>
        /// <returns>
        /// The sum of <paramref name="left"/> and <paramref name="right"/>.
        /// </returns>
        public static BigInteger operator +(BigInteger left, BigInteger right)
        {
            if (left._sign == 0)
            {
                return right;
            }

            if (right._sign == 0)
            {
                return left;
            }

            if (left._sign == right._sign)
            {
                return new BigInteger(left._sign, CoreAdd(left._data, right._data));
            }

            var r = CoreCompare(left._data, right._data);

            if (r == 0)
            {
                return Zero;
            }

            if (r > 0)
            {
                //left > right
                return new BigInteger(left._sign, CoreSub(left._data, right._data));
            }

            return new BigInteger(right._sign, CoreSub(right._data, left._data));
        }

        /// <summary>
        /// Subtracts a <see cref="BigInteger"/> value from another <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The value to subtract from (the minuend).</param>
        /// <param name="right">The value to subtract (the subtrahend).</param>
        /// <returns>
        /// The result of subtracting <paramref name="right"/> from <paramref name="left"/>.
        /// </returns>
        public static BigInteger operator -(BigInteger left, BigInteger right)
        {
            if (right._sign == 0)
            {
                return left;
            }

            if (left._sign == 0)
            {
                return new BigInteger((short) -right._sign, right._data);
            }

            if (left._sign == right._sign)
            {
                var r = CoreCompare(left._data, right._data);

                if (r == 0)
                {
                    return Zero;
                }

                if (r > 0)
                {
                    // left > right
                    return new BigInteger(left._sign, CoreSub(left._data, right._data));
                }

                return new BigInteger((short)-right._sign, CoreSub(right._data, left._data));
            }

            return new BigInteger(left._sign, CoreAdd(left._data, right._data));
        }

        /// <summary>
        /// Multiplies two specified <see cref="BigInteger"/> values.
        /// </summary>
        /// <param name="left">The first value to multiply.</param>
        /// <param name="right">The second value to multiply.</param>
        /// <returns>
        /// The product of left and right.
        /// </returns>
        public static BigInteger operator *(BigInteger left, BigInteger right)
        {
            if (left._sign == 0 || right._sign == 0)
            {
                return Zero;
            }

            if (left._data[0] == 1 && left._data.Length == 1)
            {
                if (left._sign == 1)
                {
                    return right;
                }

                return new BigInteger((short)-right._sign, right._data);
            }

            if (right._data[0] == 1 && right._data.Length == 1)
            {
                if (right._sign == 1)
                {
                    return left;
                }

                return new BigInteger((short)-left._sign, left._data);
            }

            var a = left._data;
            var b = right._data;

            var res = new uint[a.Length + b.Length];

            for (var i = 0; i < a.Length; ++i)
            {
                var ai = a[i];
                var k = i;

                ulong carry = 0;
                for (var j = 0; j < b.Length; ++j)
                {
                    carry = carry + ((ulong) ai) * b[j] + res[k];
                    res[k++] = (uint)carry;
                    carry >>= 32;
                }

                while (carry != 0)
                {
                    carry += res[k];
                    res[k++] = (uint)carry;
                    carry >>= 32;
                }
            }

            int m;
            for (m = res.Length - 1; m >= 0 && res[m] == 0; --m)
            {
                // Intentionally empty block
            }

            if (m < res.Length - 1)
            {
                Array.Resize(ref res, m + 1);
            }

            return new BigInteger((short) (left._sign*right._sign), res);
        }

        /// <summary>
        /// Divides a specified <see cref="BigInteger"/> value by another specified <see cref="BigInteger"/> value by using
        /// integer division.
        /// </summary>
        /// <param name="dividend">The value to be divided.</param>
        /// <param name="divisor">The value to divide by.</param>
        /// <returns>
        /// The integral result of the division.
        /// </returns>
        public static BigInteger operator /(BigInteger dividend, BigInteger divisor)
        {
            if (divisor._sign == 0)
            {
                throw new DivideByZeroException();
            }

            if (dividend._sign == 0)
            {
                return dividend;
            }

            DivModUnsigned(dividend._data, divisor._data, out var quotient, out _);

            int i;
            for (i = quotient.Length - 1; i >= 0 && quotient[i] == 0; --i)
            {
                // Intentionally empty block
            }

            if (i == -1)
            {
                return Zero;
            }

            if (i < quotient.Length - 1)
            {
                Array.Resize(ref quotient, i + 1);
            }

            return new BigInteger((short)(dividend._sign * divisor._sign), quotient);
        }

        /// <summary>
        /// Returns the remainder that results from division with two specified <see cref="BigInteger"/> values.
        /// </summary>
        /// <param name="dividend">The value to be divided.</param>
        /// <param name="divisor">The value to divide by.</param>
        /// <returns>
        /// The remainder that results from the division.
        /// </returns>
        public static BigInteger operator %(BigInteger dividend, BigInteger divisor)
        {
            if (divisor._sign == 0)
            {
                throw new DivideByZeroException();
            }

            if (dividend._sign == 0)
            {
                return dividend;
            }

            DivModUnsigned(dividend._data, divisor._data, out _, out var remainderValue);

            int i;
            for (i = remainderValue.Length - 1; i >= 0 && remainderValue[i] == 0; --i)
            {
                // Intentionally empty block
            }

            if (i == -1)
            {
                return Zero;
            }

            if (i < remainderValue.Length - 1)
            {
                Array.Resize(ref remainderValue, i + 1);
            }

            return new BigInteger(dividend._sign, remainderValue);
        }

        /// <summary>
        /// Negates a specified <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to negate.</param>
        /// <returns>
        /// The result of the <paramref name="value"/> parameter multiplied by negative one (-1).
        /// </returns>
        public static BigInteger operator -(BigInteger value)
        {
            if (value._data is null)
            {
                return value;
            }

            return new BigInteger((short) -value._sign, value._data);
        }

        /// <summary>
        /// Returns the value of the <see cref="BigInteger"/> operand.
        /// </summary>
        /// <param name="value">An integer value.</param>
        /// <returns>
        /// The value of the <paramref name="value"/> operand.
        /// </returns>
        /// <remarks>
        /// The sign of the operand is unchanged.
        /// </remarks>
        public static BigInteger operator +(BigInteger value)
        {
            return value;
        }

        /// <summary>
        /// Increments a <see cref="BigInteger"/> value by 1.
        /// </summary>
        /// <param name="value">The value to increment.</param>
        /// <returns>
        /// The value of the <paramref name="value"/> parameter incremented by 1.
        /// </returns>
        public static BigInteger operator ++(BigInteger value)
        {
            if (value._data is null)
            {
                return One;
            }

            var sign = value._sign;
            var data = value._data;
            if (data.Length == 1)
            {
                if (sign == -1 && data[0] == 1)
                {
                    return Zero;
                }

                if (sign == 0)
                {
                    return One;
                }
            }

            data = sign == -1 ? CoreSub(data, 1) : CoreAdd(data, 1);

            return new BigInteger(sign, data);
        }

        /// <summary>
        /// Decrements a <see cref="BigInteger"/> value by 1.
        /// </summary>
        /// <param name="value">The value to decrement.</param>
        /// <returns>
        /// The value of the <paramref name="value"/> parameter decremented by 1.
        /// </returns>
        public static BigInteger operator --(BigInteger value)
        {
            if (value._data is null)
            {
                return MinusOne;
            }

            var sign = value._sign;
            var data = value._data;
            if (data.Length == 1)
            {
                if (sign == 1 && data[0] == 1)
                {
                    return Zero;
                }

                if (sign == 0)
                {
                    return MinusOne;
                }
            }

            data = sign == -1 ? CoreAdd(data, 1) : CoreSub(data, 1);

            return new BigInteger(sign, data);
        }

        /// <summary>
        /// Performs a bitwise <c>And</c> operation on two <see cref="BigInteger"/> values.
        /// </summary>
        /// <param name="left">The first value.</param>
        /// <param name="right">The second value.</param>
        /// <returns>
        /// The result of the bitwise <c>And</c> operation.
        /// </returns>
        public static BigInteger operator &(BigInteger left, BigInteger right)
        {
            if (left._sign == 0)
            {
                return left;
            }

            if (right._sign == 0)
            {
                return right;
            }

            var a = left._data;
            var b = right._data;
            int ls = left._sign;
            int rs = right._sign;

            var negRes = (ls == rs) && (ls == -1);

            var result = new uint[Math.Max(a.Length, b.Length)];

            ulong ac = 1, bc = 1, borrow = 1;

            int i;
            for (i = 0; i < result.Length; ++i)
            {
                uint va = 0;
                if (i < a.Length)
                {
                    va = a[i];
                }

                if (ls == -1)
                {
                    ac = ~va + ac;
                    va = (uint)ac;
                    ac = (uint)(ac >> 32);
                }

                uint vb = 0;
                if (i < b.Length)
                {
                    vb = b[i];
                }

                if (rs == -1)
                {
                    bc = ~vb + bc;
                    vb = (uint)bc;
                    bc = (uint)(bc >> 32);
                }

                var word = va & vb;

                if (negRes)
                {
                    borrow = word - borrow;
                    word = ~(uint)borrow;
                    borrow = (uint)(borrow >> 32) & 0x1u;
                }

                result[i] = word;
            }

            for (i = result.Length - 1; i >= 0 && result[i] == 0; --i)
            {
                // Intentionally empty block
            }

            if (i == -1)
            {
                return Zero;
            }

            if (i < result.Length - 1)
            {
                Array.Resize(ref result, i + 1);
            }

            return new BigInteger(negRes ? (short)-1 : (short)1, result);
        }

        /// <summary>
        /// Performs a bitwise <c>Or</c> operation on two <see cref="BigInteger"/> values.
        /// </summary>
        /// <param name="left">The first value.</param>
        /// <param name="right">The second value.</param>
        /// <returns>
        /// The result of the bitwise <c>Or</c> operation.
        /// </returns>
        public static BigInteger operator |(BigInteger left, BigInteger right)
        {
            if (left._sign == 0)
            {
                return right;
            }

            if (right._sign == 0)
            {
                return left;
            }

            var a = left._data;
            var b = right._data;
            int ls = left._sign;
            int rs = right._sign;

            var negRes = (ls == -1) || (rs == -1);

            var result = new uint[Math.Max(a.Length, b.Length)];

            ulong ac = 1, bc = 1, borrow = 1;

            int i;
            for (i = 0; i < result.Length; ++i)
            {
                uint va = 0;
                if (i < a.Length)
                {
                    va = a[i];
                }

                if (ls == -1)
                {
                    ac = ~va + ac;
                    va = (uint)ac;
                    ac = (uint)(ac >> 32);
                }

                uint vb = 0;
                if (i < b.Length)
                {
                    vb = b[i];
                }

                if (rs == -1)
                {
                    bc = ~vb + bc;
                    vb = (uint)bc;
                    bc = (uint)(bc >> 32);
                }

                var word = va | vb;

                if (negRes)
                {
                    borrow = word - borrow;
                    word = ~(uint)borrow;
                    borrow = (uint)(borrow >> 32) & 0x1u;
                }

                result[i] = word;
            }

            for (i = result.Length - 1; i >= 0 && result[i] == 0; --i)
            {
                // Intentionally empty block
            }

            if (i == -1)
            {
                return Zero;
            }

            if (i < result.Length - 1)
            {
                Array.Resize(ref result, i + 1);
            }

            return new BigInteger(negRes ? (short)-1 : (short)1, result);
        }

        /// <summary>
        /// Performs a bitwise exclusive <c>Or</c> (<c>XOr</c>) operation on two <see cref="BigInteger"/> values.
        /// </summary>
        /// <param name="left">The first value.</param>
        /// <param name="right">The second value.</param>
        /// <returns>
        /// The result of the bitwise <c>Or</c> operation.
        /// </returns>
        public static BigInteger operator ^(BigInteger left, BigInteger right)
        {
            if (left._sign == 0)
            {
                return right;
            }

            if (right._sign == 0)
            {
                return left;
            }

            var a = left._data;
            var b = right._data;
            int ls = left._sign;
            int rs = right._sign;

            var negRes = (ls == -1) ^ (rs == -1);

            var result = new uint[Math.Max(a.Length, b.Length)];

            ulong ac = 1, bc = 1, borrow = 1;

            int i;
            for (i = 0; i < result.Length; ++i)
            {
                uint va = 0;
                if (i < a.Length)
                {
                    va = a[i];
                }

                if (ls == -1)
                {
                    ac = ~va + ac;
                    va = (uint)ac;
                    ac = (uint)(ac >> 32);
                }

                uint vb = 0;
                if (i < b.Length)
                {
                    vb = b[i];
                }

                if (rs == -1)
                {
                    bc = ~vb + bc;
                    vb = (uint)bc;
                    bc = (uint)(bc >> 32);
                }

                var word = va ^ vb;

                if (negRes)
                {
                    borrow = word - borrow;
                    word = ~(uint)borrow;
                    borrow = (uint)(borrow >> 32) & 0x1u;
                }

                result[i] = word;
            }

            for (i = result.Length - 1; i >= 0 && result[i] == 0; --i)
            {
                // Intentionally empty block
            }

            if (i == -1)
            {
                return Zero;
            }

            if (i < result.Length - 1)
            {
                Array.Resize(ref result, i + 1);
            }

            return new BigInteger(negRes ? (short)-1 : (short)1, result);
        }

        /// <summary>
        /// Returns the bitwise one's complement of a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">An integer value.</param>
        /// <returns>
        /// The bitwise one's complement of <paramref name="value"/>.
        /// </returns>
        public static BigInteger operator ~(BigInteger value)
        {
            if (value._data is null)
            {
                return MinusOne;
            }

            var data = value._data;
            int sign = value._sign;

            var negRes = sign == 1;

            var result = new uint[data.Length];

            ulong carry = 1, borrow = 1;

            int i;
            for (i = 0; i < result.Length; ++i)
            {
                var word = data[i];
                if (sign == -1)
                {
                    carry = ~word + carry;
                    word = (uint)carry;
                    carry = (uint)(carry >> 32);
                }

                word = ~word;

                if (negRes)
                {
                    borrow = word - borrow;
                    word = ~(uint)borrow;
                    borrow = (uint)(borrow >> 32) & 0x1u;
                }

                result[i] = word;
            }

            for (i = result.Length - 1; i >= 0 && result[i] == 0; --i)
            {
                // Intentionally empty block
            }

            if (i == -1)
            {
                return Zero;
            }

            if (i < result.Length - 1)
            {
                Array.Resize(ref result, i + 1);
            }

            return new BigInteger(negRes ? (short)-1 : (short)1, result);
        }

        //returns the 0-based index of the most significant set bit
        //returns 0 if no bit is set, so extra care when using it
        static int BitScanBackward(uint word)
        {
            for (var i = 31; i >= 0; --i)
            {
                var mask = 1u << i;
                if ((word & mask) == mask)
                {
                    return i;
                }
            }

            return 0;
        }

        /// <summary>
        /// Shifts a <see cref="BigInteger"/> value a specified number of bits to the left.
        /// </summary>
        /// <param name="value">The value whose bits are to be shifted.</param>
        /// <param name="shift">The number of bits to shift value to the left.</param>
        /// <returns>
        /// A value that has been shifted to the left by the specified number of bits.
        /// </returns>
        public static BigInteger operator <<(BigInteger value, int shift)
        {
            if (shift == 0 || value._data is null)
            {
                return value;
            }

            if (shift < 0)
            {
                return value >> -shift;
            }

            var data = value._data;
            int sign = value._sign;

            var topMostIdx = BitScanBackward(data[data.Length - 1]);
            var bits = shift - (31 - topMostIdx);
            var extraWords = (bits >> 5) + ((bits & 0x1F) != 0 ? 1 : 0);

            var res = new uint[data.Length + extraWords];

            var idxShift = shift >> 5;
            var bitShift = shift & 0x1F;
            var carryShift = 32 - bitShift;

            if (carryShift == 32)
            {
                for (var i = 0; i < data.Length; ++i)
                {
                    var word = data[i];
                    res[i + idxShift] |= word << bitShift;
                }
            }
            else
            {
                for (var i = 0; i < data.Length; ++i)
                {
                    var word = data[i];
                    res[i + idxShift] |= word << bitShift;
                    if (i + idxShift + 1 < res.Length)
                    {
                        res[i + idxShift + 1] = word >> carryShift;
                    }
                }
            }

            return new BigInteger((short)sign, res);
        }

        /// <summary>
        /// Shifts a <see cref="BigInteger"/> value a specified number of bits to the right.
        /// </summary>
        /// <param name="value">The value whose bits are to be shifted.</param>
        /// <param name="shift">The number of bits to shift value to the right.</param>
        /// <returns>
        /// A value that has been shifted to the right by the specified number of bits.
        /// </returns>
        public static BigInteger operator >>(BigInteger value, int shift)
        {
            if (shift == 0 || value._sign == 0)
            {
                return value;
            }

            if (shift < 0)
            {
                return value << -shift;
            }

            var data = value._data;
            int sign = value._sign;

            var topMostIdx = BitScanBackward(data[data.Length - 1]);
            var idxShift = shift >> 5;
            var bitShift = shift & 0x1F;

            var extraWords = idxShift;
            if (bitShift > topMostIdx)
            {
                ++extraWords;
            }

            var size = data.Length - extraWords;

            if (size <= 0)
            {
                return sign == 1 ? Zero : MinusOne;
            }

            var res = new uint[size];
            var carryShift = 32 - bitShift;

            if (carryShift == 32)
            {
                for (var i = data.Length - 1; i >= idxShift; --i)
                {
                    var word = data[i];

                    if (i - idxShift < res.Length)
                    {
                        res[i - idxShift] |= word >> bitShift;
                    }
                }
            }
            else
            {
                for (var i = data.Length - 1; i >= idxShift; --i)
                {
                    var word = data[i];

                    if (i - idxShift < res.Length)
                    {
                        res[i - idxShift] |= word >> bitShift;
                    }

                    if (i - idxShift - 1 >= 0)
                    {
                        res[i - idxShift - 1] = word << carryShift;
                    }
                }
            }

            // Round down instead of toward zero
            if (sign == -1)
            {
                for (var i = 0; i < idxShift; i++)
                {
                    if (data[i] != 0u)
                    {
                        var tmp = new BigInteger((short)sign, res);
                        --tmp;
                        return tmp;
                    }
                }

                if (bitShift > 0 && (data[idxShift] << carryShift) != 0u)
                {
                    var tmp = new BigInteger((short)sign, res);
                    --tmp;
                    return tmp;
                }
            }

            return new BigInteger((short)sign, res);
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is less than another
        /// <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is less than <paramref name="right"/>; otherwise, <c>false</c>.
        /// </returns>
        public static bool operator <(BigInteger left, BigInteger right)
        {
            return Compare(left, right) < 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is less than a 64-bit signed integer.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if left is <paramref name="left"/> than <paramref name="right"/>; otherwise, <c>false</c>.
        /// </returns>
        public static bool operator <(BigInteger left, long right)
        {
            return left.CompareTo(right) < 0;
        }


        /// <summary>
        /// Returns a value that indicates whether a 64-bit signed integer is less than a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is less than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator <(long left, BigInteger right)
        {
            return right.CompareTo(left) > 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a 64-bit signed integer is less than a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is less than <paramref name="right"/>; otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator <(BigInteger left, ulong right)
        {
            return left.CompareTo(right) < 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a 64-bit unsigned integer is less than a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is less than <paramref name="right"/>; otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator <(ulong left, BigInteger right)
        {
            return right.CompareTo(left) > 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is less than or equal
        /// to another <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is less than or equal to <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator <=(BigInteger left, BigInteger right)
        {
            return Compare(left, right) <= 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is less than or equal
        /// to a 64-bit signed integer.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is less than or equal to <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator <=(BigInteger left, long right)
        {
            return left.CompareTo(right) <= 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a 64-bit signed integer is less than or equal to a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is less than or equal to <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator <=(long left, BigInteger right)
        {
            return right.CompareTo(left) >= 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is less than or equal to
        /// a 64-bit unsigned integer.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is less than or equal to <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator <=(BigInteger left, ulong right)
        {
            return left.CompareTo(right) <= 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a 64-bit unsigned integer is less than or equal to a
        /// <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is less than or equal to <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator <=(ulong left, BigInteger right)
        {
            return right.CompareTo(left) >= 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is greater than another
        /// <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is greater than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator >(BigInteger left, BigInteger right)
        {
            return Compare(left, right) > 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> is greater than a 64-bit signed integer value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is greater than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator >(BigInteger left, long right)
        {
            return left.CompareTo(right) > 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a 64-bit signed integer is greater than a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is greater than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator >(long left, BigInteger right)
        {
            return right.CompareTo(left) < 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is greater than a 64-bit unsigned integer.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is greater than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator >(BigInteger left, ulong right)
        {
            return left.CompareTo(right) > 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a 64-bit unsigned integer is greater than a <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is greater than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator >(ulong left, BigInteger right)
        {
            return right.CompareTo(left) < 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is greater than or equal
        /// to another <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is greater than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator >=(BigInteger left, BigInteger right)
        {
            return Compare(left, right) >= 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is greater than or equal
        /// to a 64-bit signed integer value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is greater than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator >=(BigInteger left, long right)
        {
            return left.CompareTo(right) >= 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a 64-bit signed integer is greater than or equal to a
        /// <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is greater than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator >=(long left, BigInteger right)
        {
            return right.CompareTo(left) <= 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value is greater than or equal to a
        /// 64-bit unsigned integer value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is greater than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator >=(BigInteger left, ulong right)
        {
            return left.CompareTo(right) >= 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a 64-bit unsigned integer is greater than or equal to a
        /// <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> is greater than <paramref name="right"/>;
        /// otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator >=(ulong left, BigInteger right)
        {
            return right.CompareTo(left) <= 0;
        }

        /// <summary>
        /// Returns a value that indicates whether the values of two <see cref="BigInteger"/> objects are equal.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if the <paramref name="left"/> and <paramref name="right"/> parameters have the same value;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator ==(BigInteger left, BigInteger right)
        {
            return Compare(left, right) == 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value and a signed long integer value are equal.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if the <paramref name="left"/> and <paramref name="right"/> parameters have the same value;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator ==(BigInteger left, long right)
        {
            return left.CompareTo(right) == 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a signed long integer value and a <see cref="BigInteger"/> value are equal.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if the <paramref name="left"/> and <paramref name="right"/> parameters have the same value;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator ==(long left, BigInteger right)
        {
            return right.CompareTo(left) == 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value and an unsigned long integer value are equal.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if the <paramref name="left"/> and <paramref name="right"/> parameters have the same value;
        /// otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator ==(BigInteger left, ulong right)
        {
            return left.CompareTo(right) == 0;
        }

        /// <summary>
        /// Returns a value that indicates whether an unsigned long integer value and a <see cref="BigInteger"/> value are equal.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if the <paramref name="left"/> and <paramref name="right"/> parameters have the same value;
        /// otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator ==(ulong left, BigInteger right)
        {
            return right.CompareTo(left) == 0;
        }

        /// <summary>
        /// Returns a value that indicates whether two <see cref="BigInteger"/> objects have different values.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> and <paramref name="right"/> are not equal;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator !=(BigInteger left, BigInteger right)
        {
            return Compare(left, right) != 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value and a 64-bit signed integer are not equal.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> and <paramref name="right"/> are not equal;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator !=(BigInteger left, long right)
        {
            return left.CompareTo(right) != 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a 64-bit signed integer and a <see cref="BigInteger"/> value are not equal.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> and <paramref name="right"/> are not equal;
        /// otherwise, <c>false</c>.
        /// </returns>
        public static bool operator !=(long left, BigInteger right)
        {
            return right.CompareTo(left) != 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a <see cref="BigInteger"/> value and a 64-bit unsigned integer are not equal.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> and <paramref name="right"/> are not equal;
        /// otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator !=(BigInteger left, ulong right)
        {
            return left.CompareTo(right) != 0;
        }

        /// <summary>
        /// Returns a value that indicates whether a 64-bit unsigned integer and a <see cref="BigInteger"/> value are not equal.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="left"/> and <paramref name="right"/> are not equal;
        /// otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public static bool operator !=(ulong left, BigInteger right)
        {
            return right.CompareTo(left) != 0;
        }

        /// <summary>
        /// Returns a value that indicates whether the current instance and a specified object have the same value.
        /// </summary>
        /// <param name="obj">The object to compare.</param>
        /// <returns>
        /// <c>true</c> if the <paramref name="obj"/> parameter is a <see cref="BigInteger"/> object or a type capable
        /// of implicit conversion to a <see cref="BigInteger"/> value, and its value is equal to the value of the
        /// current <see cref="BigInteger"/> object; otherwise, <c>false</c>.
        /// </returns>
        public override readonly bool Equals(object obj)
        {
            if (obj is not BigInteger other)
            {
                return false;
            }

            return Equals(other);
        }

        /// <summary>
        /// Returns a value that indicates whether the current instance and a specified <see cref="BigInteger"/> object
        /// have the same value.
        /// </summary>
        /// <param name="other">The object to compare.</param>
        /// <returns>
        /// <c>true</c> if this <see cref="BigInteger"/> object and <paramref name="other"/> have the same value;
        /// otherwise, <c>false</c>.
        /// </returns>
        public readonly bool Equals(BigInteger other)
        {
            if (_sign != other._sign)
            {
                return false;
            }

            var alen = _data != null ? _data.Length : 0;
            var blen = other._data != null ? other._data.Length : 0;

            if (alen != blen)
            {
                return false;
            }

            for (var i = 0; i < alen; ++i)
            {
                if (_data[i] != other._data[i])
                {
                    return false;
                }
            }

            return true;
        }

        /// <summary>
        /// Returns a value that indicates whether the current instance and a signed 64-bit integer have the same value.
        /// </summary>
        /// <param name="other">The signed 64-bit integer value to compare.</param>
        /// <returns>
        /// <c>true</c> if the signed 64-bit integer and the current instance have the same value; otherwise, <c>false</c>.
        /// </returns>
        public readonly bool Equals(long other)
        {
            return CompareTo(other) == 0;
        }

        /// <summary>
        /// Returns a value that indicates whether the current instance and an unsigned 64-bit integer have the same value.
        /// </summary>
        /// <param name="other">The unsigned 64-bit integer to compare.</param>
        /// <returns>
        /// <c>true</c> if the current instance and the unsigned 64-bit integer have the same value; otherwise, <c>false</c>.
        /// </returns>
        [CLSCompliant(false)]
        public readonly bool Equals(ulong other)
        {
            return CompareTo(other) == 0;
        }

        /// <summary>
        /// Converts the numeric value of the current <see cref="BigInteger"/> object to its equivalent string representation.
        /// </summary>
        /// <returns>
        /// The string representation of the current <see cref="BigInteger"/> value.
        /// </returns>
        public override readonly string ToString()
        {
            return ToString(10, provider: null);
        }

        /// <summary>
        /// Converts the numeric value of the current <see cref="BigInteger"/> object to its equivalent string representation
        /// by using the specified format.
        /// </summary>
        /// <param name="format">A standard or custom numeric format string.</param>
        /// <returns>
        /// The string representation of the current <see cref="BigInteger"/> value in the format specified by the
        /// <paramref name="format"/> parameter.
        /// </returns>
        /// <exception cref="FormatException"><paramref name="format"/> is not a valid format string.</exception>
        public readonly string ToString(string format)
        {
            return ToString(format, formatProvider: null);
        }

        /// <summary>
        /// Converts the numeric value of the current <see cref="BigInteger"/> object to its equivalent string representation
        /// by using the specified culture-specific formatting information.
        /// </summary>
        /// <param name="provider">An object that supplies culture-specific formatting information.</param>
        /// <returns>
        /// The string representation of the current <see cref="BigInteger"/> value in the format specified by the
        /// <paramref name="provider"/> parameter.
        /// </returns>
        public readonly string ToString(IFormatProvider provider)
        {
            return ToString(format: null, provider);
        }

        /// <summary>
        /// Converts the numeric value of the current <see cref="BigInteger"/> object to its equivalent string representation
        /// by using the specified format and culture-specific format information.
        /// </summary>
        /// <param name="format">A standard or custom numeric format string.</param>
        /// <param name="formatProvider">An object that supplies culture-specific formatting information.</param>
        /// <returns>
        /// The string representation of the current <see cref="BigInteger"/> value as specified by the <paramref name="format"/>
        /// and <paramref name="formatProvider"/> parameters.
        /// </returns>
        public readonly string ToString(string format, IFormatProvider formatProvider)
        {
            if (string.IsNullOrEmpty(format))
            {
                return ToString(10, formatProvider);
            }

            switch (format[0])
            {
                case 'd':
                case 'D':
                case 'g':
                case 'G':
                case 'r':
                case 'R':
                    return ToStringWithPadding(format, 10, formatProvider);
                case 'x':
                case 'X':
                    return ToStringWithPadding(format, 16, provider: null);
                default:
                    throw new FormatException(string.Format("format '{0}' not implemented", format));
            }
        }

        private readonly string ToStringWithPadding(string format, uint radix, IFormatProvider provider)
        {
            if (format.Length > 1)
            {
                var precision = Convert.ToInt32(format.Substring(1), CultureInfo.InvariantCulture.NumberFormat);
                var baseStr = ToString(radix, provider);
                if (baseStr.Length < precision)
                {
                    var additional = new string('0', precision - baseStr.Length);
                    if (baseStr[0] != '-')
                    {
                        return additional + baseStr;
                    }

                    return "-" + additional + baseStr.Substring(1);
                }

                return baseStr;
            }

            return ToString(radix, provider);
        }

        private static uint[] MakeTwoComplement(uint[] v)
        {
            var res = new uint[v.Length];

            ulong carry = 1;
            for (var i = 0; i < v.Length; ++i)
            {
                var word = v[i];
                carry = (ulong)~word + carry;
                word = (uint)carry;
                carry = (uint)(carry >> 32);
                res[i] = word;
            }

            var last = res[res.Length - 1];
            var idx = FirstNonFfByte(last);
            uint mask = 0xFF;
            for (var i = 1; i < idx; ++i)
            {
                mask = (mask << 8) | 0xFF;
            }

            res[res.Length - 1] = last & mask;
            return res;
        }

        private readonly string ToString(uint radix, IFormatProvider provider)
        {
            const string characterSet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

            if (characterSet.Length < radix)
            {
                throw new ArgumentException("charSet length less than radix", "characterSet");
            }

            if (radix == 1)
            {
                throw new ArgumentException("There is no such thing as radix one notation", nameof(radix));
            }

            if (_sign == 0)
            {
                return "0";
            }

            if (_data.Length == 1 && _data[0] == 1)
            {
                return _sign == 1 ? "1" : "-1";
            }

            var digits = new List<char>(1 + _data.Length * 3 / 10);

            BigInteger a;
            if (_sign == 1)
            {
                a = this;
            }
            else
            {
                var dt = _data;
                if (radix > 10)
                {
                    dt = MakeTwoComplement(dt);
                }

                a = new BigInteger(1, dt);
            }

            while (a != 0)
            {
                a = DivRem(a, radix, out var rem);
                digits.Add(characterSet[(int) rem]);
            }

            if (_sign == -1 && radix == 10)
            {
                NumberFormatInfo info = null;
                if (provider != null)
                {
                    info = provider.GetFormat(typeof(NumberFormatInfo)) as NumberFormatInfo;
                }

                if (info != null)
                {
                    var str = info.NegativeSign;
                    for (var i = str.Length - 1; i >= 0; --i)
                    {
                        digits.Add(str[i]);
                    }
                }
                else
                {
                    digits.Add('-');
                }
            }

            var last = digits[digits.Count - 1];
            if (_sign == 1 && radix > 10 && (last < '0' || last > '9'))
            {
                digits.Add('0');
            }

            digits.Reverse();

            return new string(digits.ToArray());
        }

        /// <summary>
        /// Converts the string representation of a number to its <see cref="BigInteger"/> equivalent.
        /// </summary>
        /// <param name="value">A string that contains the number to convert.</param>
        /// <returns>
        /// A value that is equivalent to the number specified in the <paramref name="value"/> parameter.
        /// </returns>
        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <c>null</c>.</exception>
        /// <exception cref="FormatException"><paramref name="value"/> is not in the correct format.</exception>
        public static BigInteger Parse(string value)
        {
            if (!Parse(value, tryParse: false, out var result, out var ex))
            {
                throw ex;
            }

            return result;
        }

        /// <summary>
        /// Converts the string representation of a number in a specified style to its <see cref="BigInteger"/> equivalent.
        /// </summary>
        /// <param name="value">A string that contains a number to convert.</param>
        /// <param name="style">A bitwise combination of the enumeration values that specify the permitted format of <paramref name="value"/>.</param>
        /// <returns>
        /// A value that is equivalent to the number specified in the <paramref name="value"/> parameter.
        /// </returns>
        /// <exception cref="ArgumentException">
        /// <para><paramref name="style"/> is not a <see cref="NumberStyles"/> value.</para>
        /// <para>-or-</para>
        /// <para><paramref name="style"/> includes the <see cref="NumberStyles.AllowHexSpecifier"/> or <see cref="NumberStyles.HexNumber"/> flag along with another value.</para>
        /// </exception>
        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <c>null</c>.</exception>
        /// <exception cref="FormatException"><paramref name="value"/> does not comply with the input pattern specified by <see cref="NumberStyles"/>.</exception>
        public static BigInteger Parse(string value, NumberStyles style)
        {
            return Parse(value, style, provider: null);
        }

        /// <summary>
        /// Converts the string representation of a number in a specified style to its <see cref="BigInteger"/> equivalent.
        /// </summary>
        /// <param name="value">A string that contains a number to convert.</param>
        /// <param name="provider">An object that provides culture-specific formatting information about <paramref name="value"/>.</param>
        /// <returns>
        /// A value that is equivalent to the number specified in the <paramref name="value"/> parameter.
        /// </returns>
        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <c>null</c>.</exception>
        /// <exception cref="FormatException"><paramref name="value"/> is not in the correct format.</exception>
        public static BigInteger Parse(string value, IFormatProvider provider)
        {
            return Parse(value, NumberStyles.Integer, provider);
        }

        /// <summary>
        /// Converts the string representation of a number in a specified style and culture-specific format to its <see cref="BigInteger"/> equivalent.
        /// </summary>
        /// <param name="value">A string that contains a number to convert.</param>
        /// <param name="style">A bitwise combination of the enumeration values that specify the permitted format of <paramref name="value"/>.</param>
        /// <param name="provider">An object that provides culture-specific formatting information about <paramref name="value"/>.</param>
        /// <returns>
        /// A value that is equivalent to the number specified in the <paramref name="value"/> parameter.
        /// </returns>
        /// <exception cref="ArgumentException">
        /// <para><paramref name="style"/> is not a <see cref="NumberStyles"/> value.</para>
        /// <para>-or-</para>
        /// <para><paramref name="style"/> includes the <see cref="NumberStyles.AllowHexSpecifier"/> or <see cref="NumberStyles.HexNumber"/> flag along with another value.</para>
        /// </exception>
        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <c>null</c>.</exception>
        /// <exception cref="FormatException"><paramref name="value"/> does not comply with the input pattern specified by <see cref="NumberStyles"/>.</exception>
        public static BigInteger Parse(string value, NumberStyles style, IFormatProvider provider)
        {
            if (!Parse(value, style, provider, tryParse: false, out var res, out var exc))
            {
                throw exc;
            }

            return res;
        }

        /// <summary>
        /// Tries to convert the string representation of a number to its <see cref="BigInteger"/> equivalent, and
        /// returns a value that indicates whether the conversion succeeded.
        /// </summary>
        /// <param name="value">The string representation of a number.</param>
        /// <param name="result">When this method returns, contains the <see cref="BigInteger"/> equivalent to the number that is contained in value, or zero (0) if the conversion fails. The conversion fails if the <paramref name="value"/> parameter is <c>null</c> or is not of the correct format. This parameter is passed uninitialized.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="value"/> was converted successfully; otherwise, <c>false</c>.
        /// </returns>
        /// <exception cref="ArgumentNullException"><paramref name="value"/> is <c>null</c>.</exception>
        public static bool TryParse(string value, out BigInteger result)
        {
            return Parse(value, tryParse: true, out result, out _);
        }

        /// <summary>
        /// Tries to convert the string representation of a number in a specified style and culture-specific format to its
        /// <see cref="BigInteger"/> equivalent, and returns a value that indicates whether the conversion succeeded.
        /// </summary>
        /// <param name="value">The string representation of a number.</param>
        /// <param name="style">A bitwise combination of enumeration values that indicates the style elements that can be present in <paramref name="value"/>.</param>
        /// <param name="provider">An object that supplies culture-specific formatting information about <paramref name="value"/>.</param>
        /// <param name="result">When this method returns, contains the <see cref="BigInteger"/> equivalent to the number that is contained in value, or <see cref="Zero"/> if the conversion fails. The conversion fails if the <paramref name="value"/> parameter is <c>null</c> or is not of the correct format. This parameter is passed uninitialized.</param>
        /// <returns>
        /// <c>true</c> if <paramref name="value"/> was converted successfully; otherwise, <c>false</c>.
        /// </returns>
        /// <exception cref="ArgumentException">
        /// <para><paramref name="style"/> is not a <see cref="NumberStyles"/> value.</para>
        /// <para>-or-</para>
        /// <para><paramref name="style"/> includes the <see cref="NumberStyles.AllowHexSpecifier"/> or <see cref="NumberStyles.HexNumber"/> flag along with another value.</para>
        /// </exception>
        public static bool TryParse(string value, NumberStyles style, IFormatProvider provider, out BigInteger result)
        {
            if (!Parse(value, style, provider, tryParse: true, out result, out _))
            {
                result = Zero;
                return false;
            }

            return true;
        }

        private static bool Parse(string value, NumberStyles style, IFormatProvider fp, bool tryParse, out BigInteger result, out Exception exc)
        {
            result = Zero;
            exc = null;

            if (value is null)
            {
                if (!tryParse)
                {
                    exc = new ArgumentNullException(nameof(value));
                }

                return false;
            }

            if (value.Length == 0)
            {
                if (!tryParse)
                {
                    exc = GetFormatException();
                }

                return false;
            }

            NumberFormatInfo nfi = null;
            if (fp != null)
            {
                var typeNfi = typeof(NumberFormatInfo);
                nfi = (NumberFormatInfo) fp.GetFormat(typeNfi);
            }

            nfi ??= NumberFormatInfo.CurrentInfo;

            if (!CheckStyle(style, tryParse, ref exc))
            {
                return false;
            }

            var allowCurrencySymbol = (style & NumberStyles.AllowCurrencySymbol) != 0;
            var allowHexSpecifier = (style & NumberStyles.AllowHexSpecifier) != 0;
            var allowThousands = (style & NumberStyles.AllowThousands) != 0;
            var allowDecimalPoint = (style & NumberStyles.AllowDecimalPoint) != 0;
            var allowParentheses = (style & NumberStyles.AllowParentheses) != 0;
            var allowTrailingSign = (style & NumberStyles.AllowTrailingSign) != 0;
            var allowLeadingSign = (style & NumberStyles.AllowLeadingSign) != 0;
            var allowTrailingWhite = (style & NumberStyles.AllowTrailingWhite) != 0;
            var allowLeadingWhite = (style & NumberStyles.AllowLeadingWhite) != 0;
            var allowExponent = (style & NumberStyles.AllowExponent) != 0;

            var pos = 0;

            if (allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
            {
                return false;
            }

            var foundOpenParentheses = false;
            var negative = false;
            var foundSign = false;
            var foundCurrency = false;

            // Pre-number stuff
            if (allowParentheses && value[pos] == '(')
            {
                foundOpenParentheses = true;
                foundSign = true;
                negative = true; // MS always make the number negative when there parentheses, even when NumberFormatInfo.NumberNegativePattern != 0
                pos++;

                if (allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
                {
                    return false;
                }

                if (value.Substring(pos, nfi.NegativeSign.Length) == nfi.NegativeSign)
                {
                    if (!tryParse)
                    {
                        exc = GetFormatException();
                    }

                    return false;
                }

                if (value.Substring(pos, nfi.PositiveSign.Length) == nfi.PositiveSign)
                {
                    if (!tryParse)
                    {
                        exc = GetFormatException();
                    }

                    return false;
                }
            }

            if (allowLeadingSign && !foundSign)
            {
                // Sign + Currency
                FindSign(ref pos, value, nfi, ref foundSign, ref negative);
                if (foundSign)
                {
                    if (allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
                    {
                        return false;
                    }

                    if (allowCurrencySymbol)
                    {
                        FindCurrency(ref pos, value, nfi, ref foundCurrency);
                        if (foundCurrency && allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
                        {
                            return false;
                        }
                    }
                }
            }

            if (allowCurrencySymbol && !foundCurrency)
            {
                // Currency + sign
                FindCurrency(ref pos, value, nfi, ref foundCurrency);
                if (foundCurrency)
                {
                    if (allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
                    {
                        return false;
                    }

                    if (foundCurrency)
                    {
                        if (!foundSign && allowLeadingSign)
                        {
                            FindSign(ref pos, value, nfi, ref foundSign, ref negative);
                            if (foundSign && allowLeadingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
                            {
                                return false;
                            }
                        }
                    }
                }
            }

            var number = Zero;
            var nDigits = 0;
            var decimalPointPos = -1;
            var firstHexDigit = true;

            // Number stuff
            while (pos < value.Length)
            {
                if (!ValidDigit(value[pos], allowHexSpecifier))
                {
                    if (allowThousands &&
                        (FindOther(ref pos, value, nfi.NumberGroupSeparator)
                        || FindOther(ref pos, value, nfi.CurrencyGroupSeparator)))
                    {
                        continue;
                    }

                    if (allowDecimalPoint && decimalPointPos < 0 &&
                        (FindOther(ref pos, value, nfi.NumberDecimalSeparator)
                        || FindOther(ref pos, value, nfi.CurrencyDecimalSeparator)))
                    {
                        decimalPointPos = nDigits;
                        continue;
                    }

                    break;
                }

                nDigits++;

                if (allowHexSpecifier)
                {
                    var hexDigit = value[pos++];
                    byte digitValue;
                    if (char.IsDigit(hexDigit))
                    {
                        digitValue = (byte) (hexDigit - '0');
                    }
                    else if (char.IsLower(hexDigit))
                    {
                        digitValue = (byte) (hexDigit - 'a' + 10);
                    }
                    else
                    {
                        digitValue = (byte) (hexDigit - 'A' + 10);
                    }

                    if (firstHexDigit && digitValue >= 8)
                    {
                        negative = true;
                    }

                    number = (number * 16) + digitValue;
                    firstHexDigit = false;
                    continue;
                }

                number = (number * 10) + (byte)(value[pos++] - '0');
            }

            // Post number stuff
            if (nDigits == 0)
            {
                if (!tryParse)
                {
                    exc = GetFormatException();
                }

                return false;
            }

            // Signed hex value (Two's Complement)
            if (allowHexSpecifier && negative)
            {
                var mask = Pow(16, nDigits) - 1;
                number = (number ^ mask) + 1;
            }

            var exponent = 0;
            if (allowExponent)
            {
                if (FindExponent(ref pos, value, ref exponent, tryParse, ref exc) && exc != null)
                {
                    return false;
                }
            }

            if (allowTrailingSign && !foundSign)
            {
                // Sign + Currency
                FindSign(ref pos, value, nfi, ref foundSign, ref negative);
                if (foundSign && pos < value.Length)
                {
                    if (allowTrailingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
                    {
                        return false;
                    }
                }
            }

            if (allowCurrencySymbol && !foundCurrency)
            {
                if (allowTrailingWhite && pos < value.Length && !JumpOverWhitespace(ref pos, value, reportError: false, tryParse, ref exc))
                {
                    return false;
                }

                // Currency + sign
                FindCurrency(ref pos, value, nfi, ref foundCurrency);
                if (foundCurrency && pos < value.Length)
                {
                    if (allowTrailingWhite && !JumpOverWhitespace(ref pos, value, reportError: true, tryParse, ref exc))
                    {
                        return false;
                    }

                    if (!foundSign && allowTrailingSign)
                    {
                        FindSign(ref pos, value, nfi, ref foundSign, ref negative);
                    }
                }
            }

            if (allowTrailingWhite && pos < value.Length && !JumpOverWhitespace(ref pos, value, reportError: false, tryParse, ref exc))
            {
                return false;
            }

            if (foundOpenParentheses)
            {
                if (pos >= value.Length || value[pos++] != ')')
                {
                    if (!tryParse)
                    {
                        exc = GetFormatException();
                    }

                    return false;
                }

                if (allowTrailingWhite && pos < value.Length && !JumpOverWhitespace(ref pos, value, reportError: false, tryParse, ref exc))
                {
                    return false;
                }
            }

            if (pos < value.Length && value[pos] != '\u0000')
            {
                if (!tryParse)
                {
                    exc = GetFormatException();
                }

                return false;
            }

            if (decimalPointPos >= 0)
            {
                exponent = exponent - nDigits + decimalPointPos;
            }

            if (exponent < 0)
            {
                // Any non-zero values after decimal point are not allowed
                number = DivRem(number, Pow(10, -exponent), out var remainder);

                if (!remainder.IsZero)
                {
                    if (!tryParse)
                    {
                        exc = new OverflowException("Value too large or too small. exp=" + exponent + " rem = " + remainder + " pow = " + Pow(10, -exponent));
                    }

                    return false;
                }
            }
            else if (exponent > 0)
            {
                number = Pow(10, exponent) * number;
            }

            if (number._sign == 0)
            {
                result = number;
            }
            else if (negative)
            {
                result = new BigInteger(-1, number._data);
            }
            else
            {
                result = new BigInteger(1, number._data);
            }

            return true;
        }

        private static bool CheckStyle(NumberStyles style, bool tryParse, ref Exception exc)
        {
            if ((style & NumberStyles.AllowHexSpecifier) != 0)
            {
                var ne = style ^ NumberStyles.AllowHexSpecifier;
                if ((ne & NumberStyles.AllowLeadingWhite) != 0)
                {
                    ne ^= NumberStyles.AllowLeadingWhite;
                }

                if ((ne & NumberStyles.AllowTrailingWhite) != 0)
                {
                    ne ^= NumberStyles.AllowTrailingWhite;
                }

                if (ne != 0)
                {
                    if (!tryParse)
                    {
                        exc = new ArgumentException("With AllowHexSpecifier only " +
                                                    "AllowLeadingWhite and AllowTrailingWhite " +
                                                    "are permitted.");
                    }

                    return false;
                }
            }
            else if ((uint)style > (uint)NumberStyles.Any)
            {
                if (!tryParse)
                {
                    exc = new ArgumentException("Not a valid number style");
                }

                return false;
            }

            return true;
        }

        private static bool JumpOverWhitespace(ref int pos, string s, bool reportError, bool tryParse, ref Exception exc)
        {
            while (pos < s.Length && char.IsWhiteSpace(s[pos]))
            {
                pos++;
            }

            if (reportError && pos >= s.Length)
            {
                if (!tryParse)
                {
                    exc = GetFormatException();
                }

                return false;
            }

            return true;
        }

        private static void FindSign(ref int pos, string s, NumberFormatInfo nfi, ref bool foundSign, ref bool negative)
        {
            if ((pos + nfi.NegativeSign.Length) <= s.Length &&
                string.CompareOrdinal(s, pos, nfi.NegativeSign, 0, nfi.NegativeSign.Length) == 0)
            {
                negative = true;
                foundSign = true;
                pos += nfi.NegativeSign.Length;
            }
            else if ((pos + nfi.PositiveSign.Length) <= s.Length &&
              string.CompareOrdinal(s, pos, nfi.PositiveSign, 0, nfi.PositiveSign.Length) == 0)
            {
                negative = false;
                pos += nfi.PositiveSign.Length;
                foundSign = true;
            }
        }

        private static void FindCurrency(ref int pos, string s, NumberFormatInfo nfi, ref bool foundCurrency)
        {
            if ((pos + nfi.CurrencySymbol.Length) <= s.Length &&
                 s.Substring(pos, nfi.CurrencySymbol.Length) == nfi.CurrencySymbol)
            {
                foundCurrency = true;
                pos += nfi.CurrencySymbol.Length;
            }
        }

        private static bool FindExponent(ref int pos, string s, ref int exponent, bool tryParse, ref Exception exc)
        {
            exponent = 0;

            if (pos >= s.Length || (s[pos] != 'e' && s[pos] != 'E'))
            {
                exc = null;
                return false;
            }

            var i = pos + 1;
            if (i == s.Length)
            {
                exc = tryParse ? null : GetFormatException();
                return true;
            }

            var negative = false;
            if (s[i] == '-')
            {
                negative = true;
                if (++i == s.Length)
                {
                    exc = tryParse ? null : GetFormatException();
                    return true;
                }
            }

            if (s[i] == '+' && ++i == s.Length)
            {
                exc = tryParse ? null : GetFormatException();
                return true;
            }

            long exp = 0; // temp long value
            for (; i < s.Length; i++)
            {
                if (!char.IsDigit(s[i]))
                {
                    exc = tryParse ? null : GetFormatException();
                    return true;
                }

                // Reduce the risk of throwing an overflow exc
                exp = checked((exp * 10) - (s[i] - '0'));
                if (exp is < int.MinValue or > int.MaxValue)
                {
                    exc = tryParse ? null : new OverflowException("Value too large or too small.");
                    return true;
                }
            }

            // exp value saved as negative
            if (!negative)
            {
                exp = -exp;
            }

            exc = null;
            exponent = (int) exp;
            pos = i;
            return true;
        }

        private static bool FindOther(ref int pos, string s, string other)
        {
            if ((pos + other.Length) <= s.Length &&
                 s.Substring(pos, other.Length) == other)
            {
                pos += other.Length;
                return true;
            }

            return false;
        }

        private static bool ValidDigit(char e, bool allowHex)
        {
            if (allowHex)
            {
                return char.IsDigit(e) || (e >= 'A' && e <= 'F') || (e >= 'a' && e <= 'f');
            }

            return char.IsDigit(e);
        }

        private static Exception GetFormatException()
        {
            return new FormatException("Input string was not in the correct format");
        }

        private static bool ProcessTrailingWhitespace(bool tryParse, string s, int position, ref Exception exc)
        {
            var len = s.Length;

            for (var i = position; i < len; i++)
            {
                var c = s[i];

                if (c != 0 && !char.IsWhiteSpace(c))
                {
                    if (!tryParse)
                    {
                        exc = GetFormatException();
                    }

                    return false;
                }
            }

            return true;
        }

        private static bool Parse(string value, bool tryParse, out BigInteger result, out Exception exc)
        {
            int i, sign = 1;
            var digitsSeen = false;

            result = Zero;
            exc = null;

            if (value is null)
            {
                if (!tryParse)
                {
                    exc = new ArgumentNullException(nameof(value));
                }

                return false;
            }

            var len = value.Length;

            char c;
            for (i = 0; i < len; i++)
            {
                c = value[i];
                if (!char.IsWhiteSpace(c))
                {
                    break;
                }
            }

            if (i == len)
            {
                if (!tryParse)
                {
                    exc = GetFormatException();
                }

                return false;
            }

            var info = NumberFormatInfo.CurrentInfo;

            var negative = info.NegativeSign;
            var positive = info.PositiveSign;

            if (string.CompareOrdinal(value, i, positive, 0, positive.Length) == 0)
            {
                i += positive.Length;
            }
            else if (string.CompareOrdinal(value, i, negative, 0, negative.Length) == 0)
            {
                sign = -1;
                i += negative.Length;
            }

            var val = Zero;
            for (; i < len; i++)
            {
                c = value[i];

                if (c == '\0')
                {
                    i = len;
                    continue;
                }

                if (c is >= '0' and <= '9')
                {
                    var d = (byte) (c - '0');

                    val = (val * 10) + d;

                    digitsSeen = true;
                }
                else if (!ProcessTrailingWhitespace(tryParse, value, i, ref exc))
                {
                    return false;
                }
            }

            if (!digitsSeen)
            {
                if (!tryParse)
                {
                    exc = GetFormatException();
                }

                return false;
            }

            if (val._sign == 0)
            {
                result = val;
            }
            else if (sign == -1)
            {
                result = new BigInteger(-1, val._data);
            }
            else
            {
                result = new BigInteger(1, val._data);
            }

            return true;
        }

        /// <summary>
        /// Returns the smaller of two <see cref="BigInteger"/> values.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// The <paramref name="left"/> or <paramref name="right"/> parameter, whichever is smaller.
        /// </returns>
        public static BigInteger Min(BigInteger left, BigInteger right)
        {
            int ls = left._sign;
            int rs = right._sign;

            if (ls < rs)
            {
                return left;
            }

            if (rs < ls)
            {
                return right;
            }

            var r = CoreCompare(left._data, right._data);
            if (ls == -1)
            {
                r = -r;
            }

            if (r <= 0)
            {
                return left;
            }

            return right;
        }

        /// <summary>
        /// Returns the larger of two <see cref="BigInteger"/> values.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// The <paramref name="left"/> or <paramref name="right"/> parameter, whichever is larger.
        /// </returns>
        public static BigInteger Max(BigInteger left, BigInteger right)
        {
            int ls = left._sign;
            int rs = right._sign;

            if (ls > rs)
            {
                return left;
            }

            if (rs > ls)
            {
                return right;
            }

            var r = CoreCompare(left._data, right._data);
            if (ls == -1)
            {
                r = -r;
            }

            if (r >= 0)
            {
                return left;
            }

            return right;
        }

        /// <summary>
        /// Gets the absolute value of a <see cref="BigInteger"/> object.
        /// </summary>
        /// <param name="value">A number.</param>
        /// <returns>
        /// The absolute value of <paramref name="value"/>.
        /// </returns>
        public static BigInteger Abs(BigInteger value)
        {
            return new BigInteger(Math.Abs(value._sign), value._data);
        }

        /// <summary>
        /// Divides one <see cref="BigInteger"/> value by another, returns the result, and returns the remainder in
        /// an output parameter.
        /// </summary>
        /// <param name="dividend">The value to be divided.</param>
        /// <param name="divisor">The value to divide by.</param>
        /// <param name="remainder">When this method returns, contains a <see cref="BigInteger"/> value that represents the remainder from the division. This parameter is passed uninitialized.</param>
        /// <returns>
        /// The quotient of the division.
        /// </returns>
        public static BigInteger DivRem(BigInteger dividend, BigInteger divisor, out BigInteger remainder)
        {
            if (divisor._sign == 0)
            {
                throw new DivideByZeroException();
            }

            if (dividend._sign == 0)
            {
                remainder = dividend;
                return dividend;
            }

            DivModUnsigned(dividend._data, divisor._data, out var quotient, out var remainderValue);

            int i;
            for (i = remainderValue.Length - 1; i >= 0 && remainderValue[i] == 0; --i)
            {
                // Intentionally empty block
            }

            if (i == -1)
            {
                remainder = Zero;
            }
            else
            {
                if (i < remainderValue.Length - 1)
                {
                    Array.Resize(ref remainderValue, i + 1);
                }

                remainder = new BigInteger(dividend._sign, remainderValue);
            }

            for (i = quotient.Length - 1; i >= 0 && quotient[i] == 0; --i)
            {
                // Intentionally empty block
            }

            if (i == -1)
            {
                return Zero;
            }

            if (i < quotient.Length - 1)
            {
                Array.Resize(ref quotient, i + 1);
            }

            return new BigInteger((short)(dividend._sign * divisor._sign), quotient);
        }

        /// <summary>
        /// Raises a <see cref="BigInteger"/> value to the power of a specified value.
        /// </summary>
        /// <param name="value">The number to raise to the <paramref name="exponent"/> power.</param>
        /// <param name="exponent">The exponent to raise <paramref name="value"/> by.</param>
        /// <returns>
        /// The result of raising <paramref name="value"/> to the <paramref name="exponent"/> power.
        /// </returns>
        public static BigInteger Pow(BigInteger value, int exponent)
        {
            if (exponent < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(exponent), "exp must be >= 0");
            }

            if (exponent == 0)
            {
                return One;
            }

            if (exponent == 1)
            {
                return value;
            }

            var result = One;
            while (exponent != 0)
            {
                if ((exponent & 1) != 0)
                {
                    result *= value;
                }

                if (exponent == 1)
                {
                    break;
                }

                value *= value;
                exponent >>= 1;
            }

            return result;
        }

        /// <summary>
        /// Performs modulus division on a number raised to the power of another number.
        /// </summary>
        /// <param name="value">The number to raise to the <paramref name="exponent"/> power.</param>
        /// <param name="exponent">The exponent to raise <paramref name="value"/> by.</param>
        /// <param name="modulus">The number by which to divide <paramref name="value"/> raised to the <paramref name="exponent"/> power.</param>
        /// <returns>
        /// The remainder after dividing <paramref name="value"/> raised by <paramref name="exponent"/> by
        /// <paramref name="modulus"/>.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException"><paramref name="exponent"/> is negative.</exception>
        public static BigInteger ModPow(BigInteger value, BigInteger exponent, BigInteger modulus)
        {
            if (exponent._sign == -1)
            {
                throw new ArgumentOutOfRangeException(nameof(exponent), "power must be >= 0");
            }

            if (modulus._sign == 0)
            {
                throw new DivideByZeroException();
            }

            var result = One % modulus;
            while (exponent._sign != 0)
            {
                if (!exponent.IsEven)
                {
                    result *= value;
                    result %= modulus;
                }

                if (exponent.IsOne)
                {
                    break;
                }

                value *= value;
                value %= modulus;
                exponent >>= 1;
            }

            return result;
        }

        /// <summary>
        /// Finds the greatest common divisor of two <see cref="BigInteger"/> values.
        /// </summary>
        /// <param name="left">The first value.</param>
        /// <param name="right">The second value.</param>
        /// <returns>
        /// The greatest common divisor of <paramref name="left"/> and <paramref name="right"/>.
        /// </returns>
        public static BigInteger GreatestCommonDivisor(BigInteger left, BigInteger right)
        {
            if (left._sign != 0 && left._data.Length == 1 && left._data[0] == 1)
            {
                return One;
            }

            if (right._sign != 0 && right._data.Length == 1 && right._data[0] == 1)
            {
                return One;
            }

            if (left.IsZero)
            {
                return Abs(right);
            }

            if (right.IsZero)
            {
                return Abs(left);
            }

            var x = new BigInteger(1, left._data);
            var y = new BigInteger(1, right._data);

            var g = y;

            while (x._data.Length > 1)
            {
                g = x;
                x = y % x;
                y = g;

            }

            if (x.IsZero)
            {
                return g;
            }

            // TODO: should we have something here if we can convert to long?

            /*
             * Now we can just do it with single precision. I am using the binary gcd method,
             * as it should be faster.
             */

            var yy = x._data[0];
            var xx = (uint)(y % yy);

            var t = 0;

            while (((xx | yy) & 1) == 0)
            {
                xx >>= 1;
                yy >>= 1;
                t++;
            }

            while (xx != 0)
            {
                while ((xx & 1) == 0)
                {
                    xx >>= 1;
                }

                while ((yy & 1) == 0)
                {
                    yy >>= 1;
                }

                if (xx >= yy)
                {
                    xx = (xx - yy) >> 1;
                }
                else
                {
                    yy = (yy - xx) >> 1;
                }
            }

            return yy << t;
        }

        /*
         * LAMESPEC Log doesn't specify to how many ulp is has to be precise
         * We are equilavent to MS with about 2 ULP
         */

        /// <summary>
        /// Returns the logarithm of a specified number in a specified base.
        /// </summary>
        /// <param name="value">A number whose logarithm is to be found.</param>
        /// <param name="baseValue">The base of the logarithm.</param>
        /// <returns>
        /// The base <paramref name="baseValue"/> logarithm of value.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException">The log of <paramref name="value"/> is out of range of the <see cref="double"/> data type.</exception>
        public static double Log(BigInteger value, double baseValue)
        {
            if (value._sign == -1 || baseValue == 1.0d || baseValue == -1.0d ||
                    baseValue == double.NegativeInfinity || double.IsNaN(baseValue))
            {
                return double.NaN;
            }

            if (baseValue is 0.0d or double.PositiveInfinity)
            {
                return value.IsOne ? 0 : double.NaN;
            }

            if (value._data is null)
            {
                return double.NegativeInfinity;
            }

            var length = value._data.Length - 1;
            var bitCount = -1;
            for (var curBit = 31; curBit >= 0; curBit--)
            {
                if ((value._data[length] & (1 << curBit)) != 0)
                {
                    bitCount = curBit + length * 32;
                    break;
                }
            }

            long bitlen = bitCount;
            double c = 0, d = 1;

            var testBit = One;
            var tempBitlen = bitlen;
            while (tempBitlen > int.MaxValue)
            {
                testBit <<= int.MaxValue;
                tempBitlen -= int.MaxValue;
            }

            testBit <<= (int)tempBitlen;

            for (var curbit = bitlen; curbit >= 0; --curbit)
            {
                if ((value & testBit)._sign != 0)
                {
                    c += d;
                }

                d *= 0.5;
                testBit >>= 1;
            }

            return (Math.Log(c) + (Math.Log(2) * bitlen)) / Math.Log(baseValue);
        }

        /// <summary>
        /// Returns the natural (base <c>e</c>) logarithm of a specified number.
        /// </summary>
        /// <param name="value">The number whose logarithm is to be found.</param>
        /// <returns>
        /// The natural (base <c>e</c>) logarithm of <paramref name="value"/>.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException">The base 10 log of value is out of range of the <see cref="double"/> data type.</exception>
        public static double Log(BigInteger value)
        {
            return Log(value, Math.E);
        }

        /// <summary>
        /// Returns the base 10 logarithm of a specified number.
        /// </summary>
        /// <param name="value">A number whose logarithm is to be found.</param>
        /// <returns>
        /// The base 10 logarithm of <paramref name="value"/>.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException">The base 10 log of value is out of range of the <see cref="double"/> data type.</exception>
        public static double Log10(BigInteger value)
        {
            return Log(value, 10);
        }

        /// <summary>
        /// Returns the hash code for the current <see cref="BigInteger"/> object.
        /// </summary>
        /// <returns>
        /// A 32-bit signed integer hash code.
        /// </returns>
        public override readonly int GetHashCode()
        {
            var hash = (uint) (_sign * 0x01010101u);
            if (_data != null)
            {
                foreach (var bit in _data)
                {
                    hash ^= bit;
                }
            }

            return (int) hash;
        }

        /// <summary>
        /// Adds two <see cref="BigInteger"/> values and returns the result.
        /// </summary>
        /// <param name="left">The first value to add.</param>
        /// <param name="right">The second value to add.</param>
        /// <returns>
        /// The sum of <paramref name="left"/> and <paramref name="right"/>.
        /// </returns>
        public static BigInteger Add(BigInteger left, BigInteger right)
        {
            return left + right;
        }

        /// <summary>
        /// Subtracts one <see cref="BigInteger"/> value from another and returns the result.
        /// </summary>
        /// <param name="left">The value to subtract from (the minuend).</param>
        /// <param name="right">The value to subtract (the subtrahend).</param>
        /// <returns>
        /// The result of subtracting <paramref name="right"/> from <paramref name="left"/>.
        /// </returns>
        public static BigInteger Subtract(BigInteger left, BigInteger right)
        {
            return left - right;
        }

        /// <summary>
        /// Returns the product of two <see cref="BigInteger"/> values.
        /// </summary>
        /// <param name="left">The first number to multiply.</param>
        /// <param name="right">The second number to multiply.</param>
        /// <returns>
        /// The product of the <paramref name="left"/> and <paramref name="right"/> parameters.
        /// </returns>
        public static BigInteger Multiply(BigInteger left, BigInteger right)
        {
            return left * right;
        }

        /// <summary>
        /// Divides one <see cref="BigInteger"/> value by another and returns the result.
        /// </summary>
        /// <param name="dividend">The value to be divided.</param>
        /// <param name="divisor">The value to divide by.</param>
        /// <returns>
        /// The quotient of the division.
        /// </returns>
        public static BigInteger Divide(BigInteger dividend, BigInteger divisor)
        {
            return dividend / divisor;
        }

        /// <summary>
        /// Performs integer division on two <see cref="BigInteger"/> values and returns the remainder.
        /// </summary>
        /// <param name="dividend">The value to be divided.</param>
        /// <param name="divisor">The value to divide by.</param>
        /// <returns>
        /// The remainder after dividing <paramref name="dividend"/> by <paramref name="divisor"/>.
        /// </returns>
        public static BigInteger Remainder(BigInteger dividend, BigInteger divisor)
        {
            return dividend % divisor;
        }

        /// <summary>
        /// Negates a specified <see cref="BigInteger"/> value.
        /// </summary>
        /// <param name="value">The value to negate.</param>
        /// <returns>
        /// The result of the <paramref name="value"/> parameter multiplied by negative one (-1).
        /// </returns>
        public static BigInteger Negate(BigInteger value)
        {
            return -value;
        }

        /// <summary>
        /// Compares this instance to a specified object and returns an integer that indicates whether the value of
        /// this instance is less than, equal to, or greater than the value of the specified object.
        /// </summary>
        /// <param name="obj">The object to compare.</param>
        /// <returns>
        /// A signed integer that indicates the relationship of the current instance to the <paramref name="obj"/> parameter,
        /// as shown in the following table.
        /// <list type="table">
        ///     <listheader>
        ///         <term>Value</term>
        ///         <description>Condition</description>
        ///     </listheader>
        ///     <item>
        ///         <term>Less than zero</term>
        ///         <description>The current instance is less than <paramref name="obj"/>.</description>
        ///     </item>
        ///     <item>
        ///         <term>Zero</term>
        ///         <description>The current instance equals <paramref name="obj"/>.</description>
        ///     </item>
        ///     <item>
        ///         <term>Greater than zero</term>
        ///         <description>The current instance is greater than <paramref name="obj"/>.</description>
        ///     </item>
        /// </list>
        /// </returns>
        /// <exception cref="ArgumentException"><paramref name="obj"/> is not a <see cref="BigInteger"/>.</exception>
        public readonly int CompareTo(object obj)
        {
            if (obj is null)
            {
                return 1;
            }

            if (obj is not BigInteger other)
            {
                return -1;
            }

            return Compare(this, other);
        }

        /// <summary>
        /// Compares this instance to a second <see cref="BigInteger"/> and returns an integer that indicates whether the
        /// value of this instance is less than, equal to, or greater than the value of the specified object.
        /// </summary>
        /// <param name="other">The object to compare.</param>
        /// <returns>
        /// A signed integer value that indicates the relationship of this instance to <paramref name="other"/>, as
        /// shown in the following table.
        /// <list type="table">
        ///     <listheader>
        ///         <term>Value</term>
        ///         <description>Condition</description>
        ///     </listheader>
        ///     <item>
        ///         <term>Less than zero</term>
        ///         <description>The current instance is less than <paramref name="other"/>.</description>
        ///     </item>
        ///     <item>
        ///         <term>Zero</term>
        ///         <description>The current instance equals <paramref name="other"/>.</description>
        ///     </item>
        ///     <item>
        ///         <term>Greater than zero</term>
        ///         <description>The current instance is greater than <paramref name="other"/>.</description>
        ///     </item>
        /// </list>
        /// </returns>
        public readonly int CompareTo(BigInteger other)
        {
            return Compare(this, other);
        }

        /// <summary>
        /// Compares this instance to an unsigned 64-bit integer and returns an integer that indicates whether the value of this
        /// instance is less than, equal to, or greater than the value of the unsigned 64-bit integer.
        /// </summary>
        /// <param name="other">The unsigned 64-bit integer to compare.</param>
        /// <returns>
        /// A signed integer that indicates the relative value of this instance and <paramref name="other"/>, as shown
        /// in the following table.
        /// <list type="table">
        ///     <listheader>
        ///         <term>Value</term>
        ///         <description>Condition</description>
        ///     </listheader>
        ///     <item>
        ///         <term>Less than zero</term>
        ///         <description>The current instance is less than <paramref name="other"/>.</description>
        ///     </item>
        ///     <item>
        ///         <term>Zero</term>
        ///         <description>The current instance equals <paramref name="other"/>.</description>
        ///     </item>
        ///     <item>
        ///         <term>Greater than zero</term>
        ///         <description>The current instance is greater than <paramref name="other"/>.</description>
        ///     </item>
        /// </list>
        /// </returns>
        [CLSCompliant(false)]
        public readonly int CompareTo(ulong other)
        {
            if (_sign < 0)
            {
                return -1;
            }

            if (_sign == 0)
            {
                return other == 0 ? 0 : -1;
            }

            if (_data.Length > 2)
            {
                return 1;
            }

            var high = (uint)(other >> 32);
            var low = (uint)other;

            return LongCompare(low, high);
        }

        /// <summary>
        /// Compares this instance to a signed 64-bit integer and returns an integer that indicates whether the value of this
        /// instance is less than, equal to, or greater than the value of the signed 64-bit integer.
        /// </summary>
        /// <param name="other">The signed 64-bit integer to compare.</param>
        /// <returns>
        /// A signed integer that indicates the relative value of this instance and <paramref name="other"/>, as shown
        /// in the following table.
        /// <list type="table">
        ///     <listheader>
        ///         <term>Value</term>
        ///         <description>Condition</description>
        ///     </listheader>
        ///     <item>
        ///         <term>Less than zero</term>
        ///         <description>The current instance is less than <paramref name="other"/>.</description>
        ///     </item>
        ///     <item>
        ///         <term>Zero</term>
        ///         <description>The current instance equals <paramref name="other"/>.</description>
        ///     </item>
        ///     <item>
        ///         <term>Greater than zero</term>
        ///         <description>The current instance is greater than <paramref name="other"/>.</description>
        ///     </item>
        /// </list>
        /// </returns>
        public readonly int CompareTo(long other)
        {
            int ls = _sign;
            var rs = Math.Sign(other);

            if (ls != rs)
            {
                return ls > rs ? 1 : -1;
            }

            if (ls == 0)
            {
                return 0;
            }

            if (_data.Length > 2)
            {
                return _sign;
            }

            if (other < 0)
            {
                other = -other;
            }

            var low = (uint) other;
            var high = (uint) ((ulong) other >> 32);

            var r = LongCompare(low, high);
            if (ls == -1)
            {
                r = -r;
            }

            return r;
        }

        private readonly int LongCompare(uint low, uint high)
        {
            uint h = 0;

            if (_data.Length > 1)
            {
                h = _data[1];
            }

            if (h > high)
            {
                return 1;
            }

            if (h < high)
            {
                return -1;
            }

            var l = _data[0];

            if (l > low)
            {
                return 1;
            }

            if (l < low)
            {
                return -1;
            }

            return 0;
        }

        /// <summary>
        /// Compares two <see cref="BigInteger"/> values and returns an integer that indicates whether the first value is less than, equal to, or greater than the second value.
        /// </summary>
        /// <param name="left">The first value to compare.</param>
        /// <param name="right">The second value to compare.</param>
        /// <returns>
        /// A signed integer that indicates the relative values of left and right, as shown in the following table.
        /// <list type="table">
        ///     <listheader>
        ///         <term>Value</term>
        ///         <description>Condition</description>
        ///     </listheader>
        ///     <item>
        ///         <term>Less than zero</term>
        ///         <description><paramref name="left"/> is less than <paramref name="right"/>.</description>
        ///     </item>
        ///     <item>
        ///         <term>Zero</term>
        ///         <description><paramref name="left"/> equals <paramref name="right"/>.</description>
        ///     </item>
        ///     <item>
        ///         <term>Greater than zero</term>
        ///         <description><paramref name="left"/> is greater than <paramref name="right"/>.</description>
        ///     </item>
        /// </list>
        /// </returns>
        public static int Compare(BigInteger left, BigInteger right)
        {
            int ls = left._sign;
            int rs = right._sign;

            if (ls != rs)
            {
                return ls > rs ? 1 : -1;
            }

            var r = CoreCompare(left._data, right._data);
            if (ls < 0)
            {
                r = -r;
            }

            return r;
        }

        private static int TopByte(uint x)
        {
            if ((x & 0xFFFF0000u) != 0)
            {
                if ((x & 0xFF000000u) != 0)
                {
                    return 4;
                }

                return 3;
            }

            if ((x & 0xFF00u) != 0)
            {
                return 2;
            }

            return 1;
        }

        private static int FirstNonFfByte(uint word)
        {
            if ((word & 0xFF000000u) != 0xFF000000u)
            {
                return 4;
            }

            if ((word & 0xFF0000u) != 0xFF0000u)
            {
                return 3;
            }

            if ((word & 0xFF00u) != 0xFF00u)
            {
                return 2;
            }

            return 1;
        }

        /// <summary>
        /// Converts a <see cref="BigInteger"/> value to a byte array.
        /// </summary>
        /// <returns>
        /// The value of the current <see cref="BigInteger"/> object converted to an array of bytes.
        /// </returns>
        public readonly byte[] ToByteArray()
        {
            if (_sign == 0)
            {
                return new byte[1];
            }

            // number of bytes not counting upper word
            var bytes = (_data.Length - 1) * 4;
            var needExtraZero = false;

            var topWord = _data[_data.Length - 1];
            int extra;

            // if the topmost bit is set we need an extra
            if (_sign == 1)
            {
                extra = TopByte(topWord);
                var mask = 0x80u << ((extra - 1) * 8);
                if ((topWord & mask) != 0)
                {
                    needExtraZero = true;
                }
            }
            else
            {
                extra = TopByte(topWord);
            }

            var res = new byte[bytes + extra + (needExtraZero ? 1 : 0)];
            if (_sign == 1)
            {
                var j = 0;
                var end = _data.Length - 1;
                for (var i = 0; i < end; ++i)
                {
                    var word = _data[i];

                    res[j++] = (byte)word;
                    res[j++] = (byte)(word >> 8);
                    res[j++] = (byte)(word >> 16);
                    res[j++] = (byte)(word >> 24);
                }

                while (extra-- > 0)
                {
                    res[j++] = (byte)topWord;
                    topWord >>= 8;
                }
            }
            else
            {
                var j = 0;
                var end = _data.Length - 1;

                uint carry = 1, word;
                ulong add;
                for (var i = 0; i < end; ++i)
                {
                    word = _data[i];
                    add = (ulong)~word + carry;
                    word = (uint)add;
                    carry = (uint)(add >> 32);

                    res[j++] = (byte)word;
                    res[j++] = (byte)(word >> 8);
                    res[j++] = (byte)(word >> 16);
                    res[j++] = (byte)(word >> 24);
                }

                add = (ulong)~topWord + carry;
                word = (uint)add;
                carry = (uint)(add >> 32);
                if (carry == 0)
                {
                    var ex = FirstNonFfByte(word);
                    var needExtra = (word & (1 << (ex * 8 - 1))) == 0;
                    var to = ex + (needExtra ? 1 : 0);

                    if (to != extra)
                    {
                        Array.Resize(ref res, bytes + to);
                    }

                    while (ex-- > 0)
                    {
                        res[j++] = (byte)word;
                        word >>= 8;
                    }

                    if (needExtra)
                    {
                        res[j++] = 0xFF;
                    }
                }
                else
                {
                    Array.Resize(ref res, bytes + 5);
                    res[j++] = (byte)word;
                    res[j++] = (byte)(word >> 8);
                    res[j++] = (byte)(word >> 16);
                    res[j++] = (byte)(word >> 24);
                    res[j++] = 0xFF;
                }
            }

            return res;
        }

        private static uint[] CoreAdd(uint[] a, uint[] b)
        {
            if (a.Length < b.Length)
            {
                var tmp = a;
                a = b;
                b = tmp;
            }

            var bl = a.Length;
            var sl = b.Length;

            var res = new uint[bl];

            ulong sum = 0;

            var i = 0;
            for (; i < sl; i++)
            {
                sum = sum + a[i] + b[i];
                res[i] = (uint)sum;
                sum >>= 32;
            }

            for (; i < bl; i++)
            {
                sum += a[i];
                res[i] = (uint)sum;
                sum >>= 32;
            }

            if (sum != 0)
            {
                Array.Resize(ref res, bl + 1);
                res[i] = (uint)sum;
            }

            return res;
        }

        private static uint[] CoreAdd(uint[] a, uint b)
        {
            var len = a.Length;
            var res = new uint[len];

            ulong sum = b;
            int i;
            for (i = 0; i < len; i++)
            {
                sum += a[i];
                res[i] = (uint) sum;
                sum >>= 32;
            }

            if (sum != 0)
            {
                Array.Resize(ref res, len + 1);
                res[i] = (uint) sum;
            }

            return res;
        }

        /*invariant a > b*/
        private static uint[] CoreSub(uint[] a, uint[] b)
        {
            var bl = a.Length;
            var sl = b.Length;

            var res = new uint[bl];

            ulong borrow = 0;
            int i;
            for (i = 0; i < sl; ++i)
            {
                borrow = (ulong)a[i] - b[i] - borrow;

                res[i] = (uint)borrow;
                borrow = (borrow >> 32) & 0x1;
            }

            for (; i < bl; i++)
            {
                borrow = (ulong)a[i] - borrow;
                res[i] = (uint)borrow;
                borrow = (borrow >> 32) & 0x1;
            }

            // remove extra zeroes
            for (i = bl - 1; i >= 0 && res[i] == 0; --i)
            {
                // Intentionally empty block
            }

            if (i < bl - 1)
            {
                Array.Resize(ref res, i + 1);
            }

            return res;
        }

        private static uint[] CoreSub(uint[] a, uint b)
        {
            var len = a.Length;
            var res = new uint[len];

            ulong borrow = b;
            int i;
            for (i = 0; i < len; i++)
            {
                borrow = (ulong)a[i] - borrow;
                res[i] = (uint)borrow;
                borrow = (borrow >> 32) & 0x1;
            }

            // Remove extra zeroes
            for (i = len - 1; i >= 0 && res[i] == 0; --i)
            {
                // Intentionally empty block
            }

            if (i < len - 1)
            {
                Array.Resize(ref res, i + 1);
            }

            return res;
        }

        private static int CoreCompare(uint[] a, uint[] b)
        {
            var al = a != null ? a.Length : 0;
            var bl = b != null ? b.Length : 0;

            if (al > bl)
            {
                return 1;
            }

            if (bl > al)
            {
                return -1;
            }

            for (var i = al - 1; i >= 0; --i)
            {
                var ai = a[i];
                var bi = b[i];
                if (ai > bi)
                {
                    return 1;
                }

                if (ai < bi)
                {
                    return -1;
                }
            }

            return 0;
        }

        private static int GetNormalizeShift(uint value)
        {
            var shift = 0;

            if ((value & 0xFFFF0000) == 0)
            {
                value <<= 16;
                shift += 16;
            }

            if ((value & 0xFF000000) == 0)
            {
                value <<= 8;
                shift += 8;
            }

            if ((value & 0xF0000000) == 0)
            {
                value <<= 4;
                shift += 4;
            }

            if ((value & 0xC0000000) == 0)
            {
                value <<= 2;
                shift += 2;
            }

            if ((value & 0x80000000) == 0)
            {
#pragma warning disable IDE0059 // Unnecessary assignment of a value
                value <<= 1;
#pragma warning restore IDE0059 // Unnecessary assignment of a value
                shift += 1;
            }

            return shift;
        }

        private static void Normalize(uint[] u, int l, uint[] un, int shift)
        {
            uint carry = 0;
            int i;
            if (shift > 0)
            {
                var rshift = 32 - shift;
                for (i = 0; i < l; i++)
                {
                    var ui = u[i];
                    un[i] = (ui << shift) | carry;
                    carry = ui >> rshift;
                }
            }
            else
            {
                for (i = 0; i < l; i++)
                {
                    un[i] = u[i];
                }
            }

            while (i < un.Length)
            {
                un[i++] = 0;
            }

            if (carry != 0)
            {
                un[l] = carry;
            }
        }

        private static void Unnormalize(uint[] un, out uint[] r, int shift)
        {
            var length = un.Length;
            r = new uint[length];

            if (shift > 0)
            {
                var lshift = 32 - shift;
                uint carry = 0;
                for (var i = length - 1; i >= 0; i--)
                {
                    var uni = un[i];
                    r[i] = (uni >> shift) | carry;
                    carry = uni << lshift;
                }
            }
            else
            {
                for (var i = 0; i < length; i++)
                {
                    r[i] = un[i];
                }
            }
        }

        private static void DivModUnsigned(uint[] u, uint[] v, out uint[] q, out uint[] r)
        {
            var m = u.Length;
            var n = v.Length;

            if (n <= 1)
            {
                // Divide by single digit
                ulong rem = 0;
                var v0 = v[0];
                q = new uint[m];
                r = new uint[1];

                for (var j = m - 1; j >= 0; j--)
                {
                    rem *= Base;
                    rem += u[j];

                    var div = rem / v0;
                    rem -= div * v0;
                    q[j] = (uint)div;
                }

                r[0] = (uint) rem;
            }
            else if (m >= n)
            {
                var shift = GetNormalizeShift(v[n - 1]);

                var un = new uint[m + 1];
                var vn = new uint[n];

                Normalize(u, m, un, shift);
                Normalize(v, n, vn, shift);

                q = new uint[m - n + 1];

                // Main division loop
                for (var j = m - n; j >= 0; j--)
                {
                    int i;

                    var rr = Base * un[j + n] + un[j + n - 1];
                    var qq = rr / vn[n - 1];
                    rr -= qq * vn[n - 1];

                    for (;;)
                    {
                        // Estimate too big ?
                        if ((qq >= Base) || (qq * vn[n - 2] > (rr * Base + un[j + n - 2])))
                        {
                            qq--;
                            rr += (ulong)vn[n - 1];
                            if (rr < Base)
                            {
                                continue;
                            }
                        }

                        break;
                    }


                    // Multiply and subtract
                    long b = 0;
                    long t;
                    for (i = 0; i < n; i++)
                    {
                        var p = vn[i] * qq;
                        t = (long)un[i + j] - (long)(uint)p - b;
                        un[i + j] = (uint)t;
                        p >>= 32;
                        t >>= 32;
                        b = (long)p - t;
                    }

                    t = (long)un[j + n] - b;
                    un[j + n] = (uint)t;

                    // Store the calculated value
                    q[j] = (uint)qq;

                    // Add back vn[0..n] to un[j..j+n]
                    if (t < 0)
                    {
                        q[j]--;
                        ulong c = 0;
                        for (i = 0; i < n; i++)
                        {
                            c = (ulong)vn[i] + un[j + i] + c;
                            un[j + i] = (uint)c;
                            c >>= 32;
                        }

                        c += (ulong)un[j + n];
                        un[j + n] = (uint)c;
                    }
                }

                Unnormalize(un, out r, shift);
            }
            else
            {
                q = new uint[] { 0 };
                r = u;
            }
        }
    }
}