tetrees/Plugins/Wwise/Source/AkAudio/Classes/GTE/Mathematics/UIntegerALU32.h

// David Eberly, Geometric Tools, Redmond WA 98052
// Copyright (c) 1998-2020
// Distributed under the Boost Software License, Version 1.0.
// https://www.boost.org/LICENSE_1_0.txt
// https://www.geometrictools.com/License/Boost/LICENSE_1_0.txt
// Version: 4.0.2019.09.03

#pragma once

#include <Mathematics/BitHacks.h>
#include <algorithm>

// Support for unsigned integer arithmetic in BSNumber and BSRational.  The
// Curiously Recurring Template Paradigm is used to allow the UInteger
// types to share code without introducing virtual functions.

namespace WwiseGTE
{
    template <typename UInteger>
    class UIntegerALU32
    {
    public:
        // Comparisons.  These are not generic.  They rely on their being
        // called when the two BSNumber arguments to BSNumber::operatorX()
        // are of the form 1.u*2^p and 1.v*2^p.  The comparisons apply to
        // 1.u and 1.v as unsigned integers with their leading 1-bits aligned.
        bool operator==(UInteger const& number) const
        {
            UInteger const& self = *(UInteger const*)this;
            int32_t numBits = self.GetNumBits();
            if (numBits != number.GetNumBits())
            {
                return false;
            }

            if (numBits > 0)
            {
                auto const& bits = self.GetBits();
                auto const& nBits = number.GetBits();
                int32_t const last = self.GetSize() - 1;
                for (int32_t i = last; i >= 0; --i)
                {
                    if (bits[i] != nBits[i])
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        bool operator!=(UInteger const& number) const
        {
            return !operator==(number);
        }

        bool operator< (UInteger const& number) const
        {
            UInteger const& self = *(UInteger const*)this;
            int32_t nNumBits = number.GetNumBits();
            auto const& nBits = number.GetBits();

            int32_t numBits = self.GetNumBits();
            if (numBits > 0 && nNumBits > 0)
            {
                // The numbers must be compared as if they are left-aligned
                // with each other.  We got here because we had
                // self = 1.u * 2^p and number = 1.v * 2^p.  Although they
                // have the same exponent, it is possible that
                // 'self < number' but 'numBits(1u) > numBits(1v)'.  Compare
                // the bits one 32-bit block at a time.
                auto const& bits = self.GetBits();
                int bitIndex0 = numBits - 1;
                int bitIndex1 = nNumBits - 1;
                int block0 = bitIndex0 / 32;
                int block1 = bitIndex1 / 32;
                int numBlockBits0 = 1 + (bitIndex0 % 32);
                int numBlockBits1 = 1 + (bitIndex1 % 32);
                uint64_t n0shift = bits[block0];
                uint64_t n1shift = nBits[block1];
                while (block0 >= 0 && block1 >= 0)
                {
                    // Shift the bits in the leading blocks to the high-order bit.
                    uint32_t value0 = (uint32_t)((n0shift << (32 - numBlockBits0)) & 0x00000000FFFFFFFFull);
                    uint32_t value1 = (uint32_t)((n1shift << (32 - numBlockBits1)) & 0x00000000FFFFFFFFull);

                    // Shift bits in the next block (if any) to fill the current
                    // block.
                    if (--block0 >= 0)
                    {
                        n0shift = bits[block0];
                        value0 |= (uint32_t)((n0shift >> numBlockBits0) & 0x00000000FFFFFFFFull);
                    }
                    if (--block1 >= 0)
                    {
                        n1shift = nBits[block1];
                        value1 |= (uint32_t)((n1shift >> numBlockBits1) & 0x00000000FFFFFFFFull);
                    }
                    if (value0 < value1)
                    {
                        return true;
                    }
                    if (value0 > value1)
                    {
                        return false;
                    }
                }
                return block0 < block1;
            }
            else
            {
                // One or both numbers are negative.  The only time 'less than' is
                // 'true' is when 'number' is positive.
                return nNumBits > 0;
            }
        }

        bool operator<=(UInteger const& number) const
        {
            return operator<(number) || operator==(number);
        }

        bool operator> (UInteger const& number) const
        {
            return !operator<=(number);
        }

        bool operator>=(UInteger const& number) const
        {
            return !operator<(number);
        }

        // Arithmetic operations.  These are performed in-place; that is, the
        // result is stored in 'this' object.  The goal is to reduce the
        // number of object copies, much like the goal is for std::move.  The
        // Sub function requires the inputs to satisfy n0 > n1.
        void Add(UInteger const& n0, UInteger const& n1)
        {
            UInteger& self = *(UInteger*)this;
            int32_t n0NumBits = n0.GetNumBits();
            int32_t n1NumBits = n1.GetNumBits();

            // Add the numbers considered as positive integers.  Set the last
            // block to zero in case no carry-out occurs.
            int numBits = std::max(n0NumBits, n1NumBits) + 1;
            self.SetNumBits(numBits);
            self.SetBack(0);

            // Get the input array sizes.
            int32_t numElements0 = n0.GetSize();
            int32_t numElements1 = n1.GetSize();

            // Order the inputs so that the first has the most blocks.
            auto const& u0 = (numElements0 >= numElements1 ? n0.GetBits() : n1.GetBits());
            auto const& u1 = (numElements0 >= numElements1 ? n1.GetBits() : n0.GetBits());
            auto numElements = std::minmax(numElements0, numElements1);

            // Add the u1-blocks to u0-blocks.
            auto& bits = self.GetBits();
            uint64_t carry = 0, sum;
            int32_t i;
            for (i = 0; i < numElements.first; ++i)
            {
                sum = u0[i] + (u1[i] + carry);
                bits[i] = (uint32_t)(sum & 0x00000000FFFFFFFFull);
                carry = (sum >> 32);
            }

            // We have no more u1-blocks. Propagate the carry-out, if there is
            // one, or copy the remaining blocks if there is not.
            if (carry > 0)
            {
                for (/**/; i < numElements.second; ++i)
                {
                    sum = u0[i] + carry;
                    bits[i] = (uint32_t)(sum & 0x00000000FFFFFFFFull);
                    carry = (sum >> 32);
                }
                if (carry > 0)
                {
                    bits[i] = (uint32_t)(carry & 0x00000000FFFFFFFFull);
                }
            }
            else
            {
                for (/**/; i < numElements.second; ++i)
                {
                    bits[i] = u0[i];
                }
            }

            // Reduce the number of bits if there was not a carry-out.
            uint32_t firstBitIndex = (numBits - 1) % 32;
            uint32_t mask = (1 << firstBitIndex);
            if ((mask & self.GetBack()) == 0)
            {
                self.SetNumBits(--numBits);
            }
        }

        void Sub(UInteger const& n0, UInteger const& n1)
        {
            UInteger& self = *(UInteger*)this;
            int32_t n0NumBits = n0.GetNumBits();
            auto const& n0Bits = n0.GetBits();
            auto const& n1Bits = n1.GetBits();

            // Subtract the numbers considered as positive integers.  We know
            // that n0 > n1, so create a number n2 that has the same number of
            // bits as n0 and use two's-complement to generate -n2, and then
            // add n0 and -n2.  The result is nonnegative, so we do not need
            // to apply two's complement to a negative result to extract the
            // sign and absolute value.

            // Get the input array sizes.  We know
            // numElements0 >= numElements1.
            int32_t numElements0 = n0.GetSize();
            int32_t numElements1 = n1.GetSize();

            // Create the two's-complement number n2.  We know
            // n2.GetNumElements() is the same as numElements0.
            UInteger n2;
            n2.SetNumBits(n0NumBits);
            auto& n2Bits = n2.GetBits();
            int32_t i;
            for (i = 0; i < numElements1; ++i)
            {
                n2Bits[i] = ~n1Bits[i];
            }
            for (/**/; i < numElements0; ++i)
            {
                n2Bits[i] = ~0u;
            }

            // Now add 1 to the bit-negated result to obtain -n1.
            uint64_t carry = 1, sum;
            for (i = 0; i < numElements0; ++i)
            {
                sum = n2Bits[i] + carry;
                n2Bits[i] = (uint32_t)(sum & 0x00000000FFFFFFFFull);
                carry = (sum >> 32);
            }

            // Add the numbers as positive integers.  Set the last block to
            // zero in case no carry-out occurs.
            self.SetNumBits(n0NumBits + 1);
            self.SetBack(0);

            // Add the n0-blocks to n2-blocks.
            auto & bits = self.GetBits();
            for (i = 0, carry = 0; i < numElements0; ++i)
            {
                sum = n2Bits[i] + (n0Bits[i] + carry);
                bits[i] = (uint32_t)(sum & 0x00000000FFFFFFFFull);
                carry = (sum >> 32);
            }

            // Strip off the bits introduced by two's-complement.
            int32_t block;
            for (block = numElements0 - 1; block >= 0; --block)
            {
                if (bits[block] > 0)
                {
                    break;
                }
            }

            if (block >= 0)
            {
                self.SetNumBits(32 * block + BitHacks::GetLeadingBit(bits[block]) + 1);
            }
            else
            {
                self.SetNumBits(0);
            }
        }

        void Mul(UInteger const& n0, UInteger const& n1)
        {
            UInteger& self = *(UInteger*)this;
            int32_t n0NumBits = n0.GetNumBits();
            int32_t n1NumBits = n1.GetNumBits();
            auto const& n0Bits = n0.GetBits();
            auto const& n1Bits = n1.GetBits();

            // The number of bits is at most this, possibly one bit smaller.
            int numBits = n0NumBits + n1NumBits;
            self.SetNumBits(numBits);
            auto& bits = self.GetBits();

            // Product of a single-block number with a multiple-block number.
            UInteger product;
            product.SetNumBits(numBits);
            auto& pBits = product.GetBits();

            // Get the array sizes.
            int32_t const numElements0 = n0.GetSize();
            int32_t const numElements1 = n1.GetSize();
            int32_t const numElements = self.GetSize();

            // Compute the product v = u0*u1.
            int32_t i0, i1, i2;
            uint64_t term, sum;

            // The case i0 == 0 is handled separately to initialize the
            // accumulator with u0[0]*v.  This avoids having to fill the bytes
            // of 'bits' with zeros outside the double loop, something that
            // can be a performance issue when 'numBits' is large.
            uint64_t block0 = n0Bits[0];
            uint64_t carry = 0;
            for (i1 = 0; i1 < numElements1; ++i1)
            {
                term = block0 * n1Bits[i1] + carry;
                bits[i1] = (uint32_t)(term & 0x00000000FFFFFFFFull);
                carry = (term >> 32);
            }
            if (i1 < numElements)
            {
                bits[i1] = (uint32_t)(carry & 0x00000000FFFFFFFFull);
            }

            for (i0 = 1; i0 < numElements0; ++i0)
            {
                // Compute the product p = u0[i0]*u1.
                block0 = n0Bits[i0];
                carry = 0;
                for (i1 = 0, i2 = i0; i1 < numElements1; ++i1, ++i2)
                {
                    term = block0 * n1Bits[i1] + carry;
                    pBits[i2] = (uint32_t)(term & 0x00000000FFFFFFFFull);
                    carry = (term >> 32);
                }
                if (i2 < numElements)
                {
                    pBits[i2] = (uint32_t)(carry & 0x00000000FFFFFFFFull);
                }

                // Add p to the accumulator v.
                carry = 0;
                for (i1 = 0, i2 = i0; i1 < numElements1; ++i1, ++i2)
                {
                    sum = pBits[i2] + (bits[i2] + carry);
                    bits[i2] = (uint32_t)(sum & 0x00000000FFFFFFFFull);
                    carry = (sum >> 32);
                }
                if (i2 < numElements)
                {
                    sum = pBits[i2] + carry;
                    bits[i2] = (uint32_t)(sum & 0x00000000FFFFFFFFull);
                }
            }

            // Reduce the number of bits if there was not a carry-out.
            uint32_t firstBitIndex = (numBits - 1) % 32;
            uint32_t mask = (1 << firstBitIndex);
            if ((mask & self.GetBack()) == 0)
            {
                self.SetNumBits(--numBits);
            }
        }

        // The shift is performed in-place; that is, the result is stored in
        // 'this' object.
        void ShiftLeft(UInteger const& number, int32_t shift)
        {
            UInteger& self = *(UInteger*)this;
            int32_t nNumBits = number.GetNumBits();
            auto const& nBits = number.GetBits();

            // Shift the 'number' considered as an odd positive integer.
            self.SetNumBits(nNumBits + shift);

            // Set the low-order bits to zero.
            auto& bits = self.GetBits();
            int32_t const shiftBlock = shift / 32;
            for (int32_t i = 0; i < shiftBlock; ++i)
            {
                bits[i] = 0;
            }

            // Get the location of the low-order 1-bit within the result.
            int32_t const numInElements = number.GetSize();
            int32_t const lshift = shift % 32;
            int32_t i, j;
            if (lshift > 0)
            {
                // The trailing 1-bits for source and target are at different
                // relative indices.  Each shifted source block straddles a
                // boundary between two target blocks, so we must extract the
                // subblocks and copy accordingly.
                int32_t const rshift = 32 - lshift;
                uint32_t prev = 0, curr;
                for (i = shiftBlock, j = 0; j < numInElements; ++i, ++j)
                {
                    curr = nBits[j];
                    bits[i] = (curr << lshift) | (prev >> rshift);
                    prev = curr;
                }
                if (i < self.GetSize())
                {
                    // The leading 1-bit of the source is at a relative index
                    // such that when you add the shift amount, that bit
                    // occurs in a new block.
                    bits[i] = (prev >> rshift);
                }
            }
            else
            {
                // The trailing 1-bits for source and target are at the same
                // relative index.  The shift reduces to a block copy.
                for (i = shiftBlock, j = 0; j < numInElements; ++i, ++j)
                {
                    bits[i] = nBits[j];
                }
            }
        }

        // The 'number' is even and positive.  It is shifted right to become
        // an odd number and the return value is the amount shifted.  The
        // operation is performed in-place; that is, the result is stored in
        // 'this' object.
        int32_t ShiftRightToOdd(UInteger const& number)
        {
            UInteger& self = *(UInteger*)this;
            auto const& nBits = number.GetBits();

            // Get the leading 1-bit.
            int32_t const numElements = number.GetSize();
            int32_t const numM1 = numElements - 1;
            int32_t firstBitIndex = 32 * numM1 + BitHacks::GetLeadingBit(nBits[numM1]);

            // Get the trailing 1-bit.
            int32_t lastBitIndex = -1;
            for (int32_t block = 0; block < numElements; ++block)
            {
                uint32_t value = nBits[block];
                if (value > 0)
                {
                    lastBitIndex = 32 * block + BitHacks::GetTrailingBit(value);
                    break;
                }
            }

            // The right-shifted result.
            self.SetNumBits(firstBitIndex - lastBitIndex + 1);
            auto& bits = self.GetBits();
            int32_t const numBlocks = self.GetSize();

            // Get the location of the low-order 1-bit within the result.
            int32_t const shiftBlock = lastBitIndex / 32;
            int32_t rshift = lastBitIndex % 32;
            if (rshift > 0)
            {
                int32_t const lshift = 32 - rshift;
                int32_t i, j = shiftBlock;
                uint32_t curr = nBits[j++];
                for (i = 0; j < numElements; ++i, ++j)
                {
                    uint32_t next = nBits[j];
                    bits[i] = (curr >> rshift) | (next << lshift);
                    curr = next;
                }
                if (i < numBlocks)
                {
                    bits[i] = (curr >> rshift);
                }
            }
            else
            {
                for (int32_t i = 0, j = shiftBlock; i < numBlocks; ++i, ++j)
                {
                    bits[i] = nBits[j];
                }
            }

            return rshift + 32 * shiftBlock;
        }

        // Add 1 to 'this', useful for rounding modes in conversions of
        // BSNumber and BSRational. The operation is performed in-place;
        // that is, the result is stored in 'this' object. The return value
        // is the amount shifted after the addition in order to obtain an
        // odd integer.
        int32_t RoundUp()
        {
            UInteger const& self = *(UInteger const*)this;
            UInteger rounded;
            rounded.Add(self, UInteger(1u));
            return ShiftRightToOdd(rounded);
        }

        // Get a block of numRequested bits starting with the leading 1-bit of
        // the nonzero number.  The returned number has the prefix stored in
        // the high-order bits.  Additional bits are copied and used by the
        // caller for rounding.  This function supports conversions from
        // 'float' and 'double'.  The input 'numRequested' is smaller than 64.
        uint64_t GetPrefix(int32_t numRequested) const
        {
            UInteger const& self = *(UInteger const*)this;
            auto const& bits = self.GetBits();

            // Copy to 'prefix' the leading 32-bit block that is nonzero.
            int32_t bitIndex = self.GetNumBits() - 1;
            int32_t blockIndex = bitIndex / 32;
            uint64_t prefix = bits[blockIndex];

            // Get the number of bits in the block starting with the leading
            // 1-bit.
            int32_t firstBitIndex = bitIndex % 32;
            int32_t numBlockBits = firstBitIndex + 1;

            // Shift the leading 1-bit to bit-63 of prefix.  We have consumed
            // numBlockBits, which might not be the entire budget.
            int32_t targetIndex = 63;
            prefix <<= targetIndex - firstBitIndex;
            numRequested -= numBlockBits;
            targetIndex -= numBlockBits;

            if (numRequested > 0 && --blockIndex >= 0)
            {
                // More bits are available.  Copy and shift the entire 32-bit
                // next block and OR it into the 'prefix'.  For 'float', we
                // will have consumed the entire budget.  For 'double', we
                // might have to get bits from a third block.
                uint64_t nextBlock = bits[blockIndex];
                nextBlock <<= targetIndex - 31;  // Shift amount is positive.
                prefix |= nextBlock;
                numRequested -= 32;
                targetIndex -= 32;

                if (numRequested > 0 && --blockIndex >= 0)
                {
                    // We know that targetIndex > 0; only 'double' allows us
                    // to get here, so numRequested is at most 53.  We also
                    // know that targetIndex < 32 because we started with 63
                    // and subtracted at least 32 from it.  Thus, the shift
                    // amount is positive.
                    nextBlock = bits[blockIndex];
                    nextBlock >>= 31 - targetIndex;
                    prefix |= nextBlock;
                }
            }

            return prefix;
        }
    };
}