Loading...
Searching...
No Matches
juce_BigInteger.cpp
/*
==============================================================================
This file is part of the JUCE library.
Copyright (c) 2022 - Raw Material Software Limited
JUCE is an open source library subject to commercial or open-source
licensing.
The code included in this file is provided under the terms of the ISC license
http://www.isc.org/downloads/software-support-policy/isc-license. Permission
To use, copy, modify, and/or distribute this software for any purpose with or
without fee is hereby granted provided that the above copyright notice and
this permission notice appear in all copies.
JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
DISCLAIMED.
==============================================================================
*/
namespace juce
{
namespace
{
inline uint32 bitToMask (const int bit) noexcept { return (uint32) 1 << (bit & 31); }
inline size_t bitToIndex (const int bit) noexcept { return (size_t) (bit >> 5); }
inline size_t sizeNeededToHold (int highestBit) noexcept { return (size_t) (highestBit >> 5) + 1; }
}
int findHighestSetBit (uint32 n) noexcept
{
jassert (n != 0); // (the built-in functions may not work for n = 0)
#if JUCE_GCC || JUCE_CLANG
return 31 - __builtin_clz (n);
#elif JUCE_MSVC
unsigned long highest;
_BitScanReverse (&highest, n);
return (int) highest;
#else
n |= (n >> 1);
n |= (n >> 2);
n |= (n >> 4);
n |= (n >> 8);
n |= (n >> 16);
return countNumberOfBits (n >> 1);
#endif
}
//==============================================================================
BigInteger::BigInteger()
: allocatedSize (numPreallocatedInts)
{
for (int i = 0; i < numPreallocatedInts; ++i)
preallocated[i] = 0;
}
BigInteger::BigInteger (const int32 value)
: allocatedSize (numPreallocatedInts),
highestBit (31),
negative (value < 0)
{
preallocated[0] = (uint32) std::abs (value);
for (int i = 1; i < numPreallocatedInts; ++i)
preallocated[i] = 0;
highestBit = getHighestBit();
}
BigInteger::BigInteger (const uint32 value)
: allocatedSize (numPreallocatedInts),
highestBit (31)
{
preallocated[0] = value;
for (int i = 1; i < numPreallocatedInts; ++i)
preallocated[i] = 0;
highestBit = getHighestBit();
}
BigInteger::BigInteger (int64 value)
: allocatedSize (numPreallocatedInts),
highestBit (63),
negative (value < 0)
{
if (value < 0)
value = -value;
preallocated[0] = (uint32) value;
preallocated[1] = (uint32) (value >> 32);
for (int i = 2; i < numPreallocatedInts; ++i)
preallocated[i] = 0;
highestBit = getHighestBit();
}
BigInteger::BigInteger (const BigInteger& other)
: allocatedSize (other.allocatedSize),
highestBit (other.getHighestBit()),
negative (other.negative)
{
if (allocatedSize > numPreallocatedInts)
heapAllocation.malloc (allocatedSize);
memcpy (getValues(), other.getValues(), sizeof (uint32) * allocatedSize);
}
BigInteger::BigInteger (BigInteger&& other) noexcept
: heapAllocation (std::move (other.heapAllocation)),
allocatedSize (other.allocatedSize),
highestBit (other.highestBit),
negative (other.negative)
{
memcpy (preallocated, other.preallocated, sizeof (preallocated));
}
BigInteger& BigInteger::operator= (BigInteger&& other) noexcept
{
heapAllocation = std::move (other.heapAllocation);
memcpy (preallocated, other.preallocated, sizeof (preallocated));
allocatedSize = other.allocatedSize;
highestBit = other.highestBit;
negative = other.negative;
return *this;
}
void BigInteger::swapWith (BigInteger& other) noexcept
{
for (int i = 0; i < numPreallocatedInts; ++i)
std::swap (preallocated[i], other.preallocated[i]);
heapAllocation.swapWith (other.heapAllocation);
std::swap (allocatedSize, other.allocatedSize);
std::swap (highestBit, other.highestBit);
std::swap (negative, other.negative);
}
BigInteger& BigInteger::operator= (const BigInteger& other)
{
if (this != &other)
{
highestBit = other.getHighestBit();
auto newAllocatedSize = (size_t) jmax ((size_t) numPreallocatedInts, sizeNeededToHold (highestBit));
if (newAllocatedSize <= numPreallocatedInts)
heapAllocation.free();
else if (newAllocatedSize != allocatedSize)
heapAllocation.malloc (newAllocatedSize);
allocatedSize = newAllocatedSize;
memcpy (getValues(), other.getValues(), sizeof (uint32) * allocatedSize);
negative = other.negative;
}
return *this;
}
BigInteger::~BigInteger() = default;
uint32* BigInteger::getValues() const noexcept
{
jassert (heapAllocation != nullptr || allocatedSize <= numPreallocatedInts);
return heapAllocation != nullptr ? heapAllocation
: const_cast<uint32*> (preallocated);
}
uint32* BigInteger::ensureSize (const size_t numVals)
{
if (numVals > allocatedSize)
{
auto oldSize = allocatedSize;
allocatedSize = ((numVals + 2) * 3) / 2;
if (heapAllocation == nullptr)
{
heapAllocation.calloc (allocatedSize);
memcpy (heapAllocation, preallocated, sizeof (uint32) * numPreallocatedInts);
}
else
{
heapAllocation.realloc (allocatedSize);
for (auto* values = getValues(); oldSize < allocatedSize; ++oldSize)
values[oldSize] = 0;
}
}
return getValues();
}
//==============================================================================
bool BigInteger::operator[] (const int bit) const noexcept
{
return bit <= highestBit && bit >= 0
&& ((getValues() [bitToIndex (bit)] & bitToMask (bit)) != 0);
}
int BigInteger::toInteger() const noexcept
{
auto n = (int) (getValues()[0] & 0x7fffffff);
return negative ? -n : n;
}
int64 BigInteger::toInt64() const noexcept
{
auto* values = getValues();
auto n = (((int64) (values[1] & 0x7fffffff)) << 32) | values[0];
return negative ? -n : n;
}
BigInteger BigInteger::getBitRange (int startBit, int numBits) const
{
BigInteger r;
numBits = jmax (0, jmin (numBits, getHighestBit() + 1 - startBit));
auto* destValues = r.ensureSize (sizeNeededToHold (numBits));
r.highestBit = numBits;
for (int i = 0; numBits > 0;)
{
destValues[i++] = getBitRangeAsInt (startBit, (int) jmin (32, numBits));
numBits -= 32;
startBit += 32;
}
r.highestBit = r.getHighestBit();
return r;
}
uint32 BigInteger::getBitRangeAsInt (const int startBit, int numBits) const noexcept
{
if (numBits > 32)
{
jassertfalse; // use getBitRange() if you need more than 32 bits..
numBits = 32;
}
numBits = jmin (numBits, highestBit + 1 - startBit);
if (numBits <= 0)
return 0;
auto pos = bitToIndex (startBit);
auto offset = startBit & 31;
auto endSpace = 32 - numBits;
auto* values = getValues();
auto n = ((uint32) values [pos]) >> offset;
if (offset > endSpace)
n |= ((uint32) values [pos + 1]) << (32 - offset);
return n & (((uint32) 0xffffffff) >> endSpace);
}
BigInteger& BigInteger::setBitRangeAsInt (const int startBit, int numBits, uint32 valueToSet)
{
if (numBits > 32)
{
jassertfalse;
numBits = 32;
}
for (int i = 0; i < numBits; ++i)
{
setBit (startBit + i, (valueToSet & 1) != 0);
valueToSet >>= 1;
}
return *this;
}
//==============================================================================
BigInteger& BigInteger::clear() noexcept
{
heapAllocation.free();
allocatedSize = numPreallocatedInts;
highestBit = -1;
negative = false;
for (int i = 0; i < numPreallocatedInts; ++i)
preallocated[i] = 0;
return *this;
}
BigInteger& BigInteger::setBit (const int bit)
{
if (bit >= 0)
{
if (bit > highestBit)
{
ensureSize (sizeNeededToHold (bit));
highestBit = bit;
}
getValues() [bitToIndex (bit)] |= bitToMask (bit);
}
return *this;
}
BigInteger& BigInteger::setBit (const int bit, const bool shouldBeSet)
{
if (shouldBeSet)
setBit (bit);
else
clearBit (bit);
return *this;
}
BigInteger& BigInteger::clearBit (const int bit) noexcept
{
if (bit >= 0 && bit <= highestBit)
{
getValues() [bitToIndex (bit)] &= ~bitToMask (bit);
if (bit == highestBit)
highestBit = getHighestBit();
}
return *this;
}
BigInteger& BigInteger::setRange (int startBit, int numBits, const bool shouldBeSet)
{
while (--numBits >= 0)
setBit (startBit++, shouldBeSet);
return *this;
}
BigInteger& BigInteger::insertBit (const int bit, const bool shouldBeSet)
{
if (bit >= 0)
shiftBits (1, bit);
setBit (bit, shouldBeSet);
return *this;
}
//==============================================================================
bool BigInteger::isZero() const noexcept
{
return getHighestBit() < 0;
}
bool BigInteger::isOne() const noexcept
{
return getHighestBit() == 0 && ! negative;
}
bool BigInteger::isNegative() const noexcept
{
return negative && ! isZero();
}
void BigInteger::setNegative (const bool neg) noexcept
{
negative = neg;
}
void BigInteger::negate() noexcept
{
negative = (! negative) && ! isZero();
}
#if JUCE_MSVC && ! defined (__INTEL_COMPILER)
#pragma intrinsic (_BitScanReverse)
#endif
int BigInteger::countNumberOfSetBits() const noexcept
{
int total = 0;
auto* values = getValues();
for (int i = (int) sizeNeededToHold (highestBit); --i >= 0;)
total += countNumberOfBits (values[i]);
return total;
}
int BigInteger::getHighestBit() const noexcept
{
auto* values = getValues();
for (int i = (int) bitToIndex (highestBit); i >= 0; --i)
if (uint32 n = values[i])
return findHighestSetBit (n) + (i << 5);
return -1;
}
int BigInteger::findNextSetBit (int i) const noexcept
{
auto* values = getValues();
for (; i <= highestBit; ++i)
if ((values [bitToIndex (i)] & bitToMask (i)) != 0)
return i;
return -1;
}
int BigInteger::findNextClearBit (int i) const noexcept
{
auto* values = getValues();
for (; i <= highestBit; ++i)
if ((values [bitToIndex (i)] & bitToMask (i)) == 0)
break;
return i;
}
//==============================================================================
BigInteger& BigInteger::operator+= (const BigInteger& other)
{
if (this == &other)
return operator+= (BigInteger (other));
if (other.isNegative())
return operator-= (-other);
if (isNegative())
{
if (compareAbsolute (other) < 0)
{
auto temp = *this;
temp.negate();
*this = other;
*this -= temp;
}
else
{
negate();
*this -= other;
negate();
}
}
else
{
highestBit = jmax (highestBit, other.highestBit) + 1;
auto numInts = sizeNeededToHold (highestBit);
auto* values = ensureSize (numInts);
auto* otherValues = other.getValues();
int64 remainder = 0;
for (size_t i = 0; i < numInts; ++i)
{
remainder += values[i];
if (i < other.allocatedSize)
remainder += otherValues[i];
values[i] = (uint32) remainder;
remainder >>= 32;
}
jassert (remainder == 0);
highestBit = getHighestBit();
}
return *this;
}
BigInteger& BigInteger::operator-= (const BigInteger& other)
{
if (this == &other)
{
clear();
return *this;
}
if (other.isNegative())
return operator+= (-other);
if (isNegative())
{
negate();
*this += other;
negate();
return *this;
}
if (compareAbsolute (other) < 0)
{
auto temp = other;
swapWith (temp);
*this -= temp;
negate();
return *this;
}
auto numInts = sizeNeededToHold (getHighestBit());
auto maxOtherInts = sizeNeededToHold (other.getHighestBit());
jassert (numInts >= maxOtherInts);
auto* values = getValues();
auto* otherValues = other.getValues();
int64 amountToSubtract = 0;
for (size_t i = 0; i < numInts; ++i)
{
if (i < maxOtherInts)
amountToSubtract += (int64) otherValues[i];
if (values[i] >= amountToSubtract)
{
values[i] = (uint32) (values[i] - amountToSubtract);
amountToSubtract = 0;
}
else
{
const int64 n = ((int64) values[i] + (((int64) 1) << 32)) - amountToSubtract;
values[i] = (uint32) n;
amountToSubtract = 1;
}
}
highestBit = getHighestBit();
return *this;
}
BigInteger& BigInteger::operator*= (const BigInteger& other)
{
if (this == &other)
return operator*= (BigInteger (other));
auto n = getHighestBit();
auto t = other.getHighestBit();
auto wasNegative = isNegative();
setNegative (false);
BigInteger total;
total.highestBit = n + t + 1;
auto* totalValues = total.ensureSize (sizeNeededToHold (total.highestBit) + 1);
n >>= 5;
t >>= 5;
auto m = other;
m.setNegative (false);
auto* mValues = m.getValues();
auto* values = getValues();
for (int i = 0; i <= t; ++i)
{
uint32 c = 0;
for (int j = 0; j <= n; ++j)
{
auto uv = (uint64) totalValues[i + j] + (uint64) values[j] * (uint64) mValues[i] + (uint64) c;
totalValues[i + j] = (uint32) uv;
c = static_cast<uint32> (uv >> 32);
}
totalValues[i + n + 1] = c;
}
total.highestBit = total.getHighestBit();
total.setNegative (wasNegative ^ other.isNegative());
swapWith (total);
return *this;
}
void BigInteger::divideBy (const BigInteger& divisor, BigInteger& remainder)
{
if (this == &divisor)
return divideBy (BigInteger (divisor), remainder);
jassert (this != &remainder); // (can't handle passing itself in to get the remainder)
auto divHB = divisor.getHighestBit();
auto ourHB = getHighestBit();
if (divHB < 0 || ourHB < 0)
{
// division by zero
remainder.clear();
clear();
}
else
{
auto wasNegative = isNegative();
swapWith (remainder);
remainder.setNegative (false);
clear();
BigInteger temp (divisor);
temp.setNegative (false);
auto leftShift = ourHB - divHB;
temp <<= leftShift;
while (leftShift >= 0)
{
if (remainder.compareAbsolute (temp) >= 0)
{
remainder -= temp;
setBit (leftShift);
}
if (--leftShift >= 0)
temp >>= 1;
}
negative = wasNegative ^ divisor.isNegative();
remainder.setNegative (wasNegative);
}
}
BigInteger& BigInteger::operator/= (const BigInteger& other)
{
BigInteger remainder;
divideBy (other, remainder);
return *this;
}
BigInteger& BigInteger::operator|= (const BigInteger& other)
{
if (this == &other)
return *this;
// this operation doesn't take into account negative values..
jassert (isNegative() == other.isNegative());
if (other.highestBit >= 0)
{
auto* values = ensureSize (sizeNeededToHold (other.highestBit));
auto* otherValues = other.getValues();
auto n = (int) bitToIndex (other.highestBit) + 1;
while (--n >= 0)
values[n] |= otherValues[n];
if (other.highestBit > highestBit)
highestBit = other.highestBit;
highestBit = getHighestBit();
}
return *this;
}
BigInteger& BigInteger::operator&= (const BigInteger& other)
{
if (this == &other)
return *this;
// this operation doesn't take into account negative values..
jassert (isNegative() == other.isNegative());
auto* values = getValues();
auto* otherValues = other.getValues();
auto n = (int) allocatedSize;
while (n > (int) other.allocatedSize)
values[--n] = 0;
while (--n >= 0)
values[n] &= otherValues[n];
if (other.highestBit < highestBit)
highestBit = other.highestBit;
highestBit = getHighestBit();
return *this;
}
BigInteger& BigInteger::operator^= (const BigInteger& other)
{
if (this == &other)
{
clear();
return *this;
}
// this operation will only work with the absolute values
jassert (isNegative() == other.isNegative());
if (other.highestBit >= 0)
{
auto* values = ensureSize (sizeNeededToHold (other.highestBit));
auto* otherValues = other.getValues();
auto n = (int) bitToIndex (other.highestBit) + 1;
while (--n >= 0)
values[n] ^= otherValues[n];
if (other.highestBit > highestBit)
highestBit = other.highestBit;
highestBit = getHighestBit();
}
return *this;
}
BigInteger& BigInteger::operator%= (const BigInteger& divisor)
{
BigInteger remainder;
divideBy (divisor, remainder);
swapWith (remainder);
return *this;
}
BigInteger& BigInteger::operator++() { return operator+= (1); }
BigInteger& BigInteger::operator--() { return operator-= (1); }
BigInteger BigInteger::operator++ (int) { const auto old (*this); operator+= (1); return old; }
BigInteger BigInteger::operator-- (int) { const auto old (*this); operator-= (1); return old; }
BigInteger BigInteger::operator-() const { auto b (*this); b.negate(); return b; }
BigInteger BigInteger::operator+ (const BigInteger& other) const { auto b (*this); return b += other; }
BigInteger BigInteger::operator- (const BigInteger& other) const { auto b (*this); return b -= other; }
BigInteger BigInteger::operator* (const BigInteger& other) const { auto b (*this); return b *= other; }
BigInteger BigInteger::operator/ (const BigInteger& other) const { auto b (*this); return b /= other; }
BigInteger BigInteger::operator| (const BigInteger& other) const { auto b (*this); return b |= other; }
BigInteger BigInteger::operator& (const BigInteger& other) const { auto b (*this); return b &= other; }
BigInteger BigInteger::operator^ (const BigInteger& other) const { auto b (*this); return b ^= other; }
BigInteger BigInteger::operator% (const BigInteger& other) const { auto b (*this); return b %= other; }
BigInteger BigInteger::operator<< (const int numBits) const { auto b (*this); return b <<= numBits; }
BigInteger BigInteger::operator>> (const int numBits) const { auto b (*this); return b >>= numBits; }
BigInteger& BigInteger::operator<<= (const int numBits) { shiftBits (numBits, 0); return *this; }
BigInteger& BigInteger::operator>>= (const int numBits) { shiftBits (-numBits, 0); return *this; }
//==============================================================================
int BigInteger::compare (const BigInteger& other) const noexcept
{
auto isNeg = isNegative();
if (isNeg == other.isNegative())
{
auto absComp = compareAbsolute (other);
return isNeg ? -absComp : absComp;
}
return isNeg ? -1 : 1;
}
int BigInteger::compareAbsolute (const BigInteger& other) const noexcept
{
auto h1 = getHighestBit();
auto h2 = other.getHighestBit();
if (h1 > h2) return 1;
if (h1 < h2) return -1;
auto* values = getValues();
auto* otherValues = other.getValues();
for (int i = (int) bitToIndex (h1); i >= 0; --i)
if (values[i] != otherValues[i])
return values[i] > otherValues[i] ? 1 : -1;
return 0;
}
bool BigInteger::operator== (const BigInteger& other) const noexcept { return compare (other) == 0; }
bool BigInteger::operator!= (const BigInteger& other) const noexcept { return compare (other) != 0; }
bool BigInteger::operator< (const BigInteger& other) const noexcept { return compare (other) < 0; }
bool BigInteger::operator<= (const BigInteger& other) const noexcept { return compare (other) <= 0; }
bool BigInteger::operator> (const BigInteger& other) const noexcept { return compare (other) > 0; }
bool BigInteger::operator>= (const BigInteger& other) const noexcept { return compare (other) >= 0; }
//==============================================================================
void BigInteger::shiftLeft (int bits, const int startBit)
{
if (startBit > 0)
{
for (int i = highestBit; i >= startBit; --i)
setBit (i + bits, (*this) [i]);
while (--bits >= 0)
clearBit (bits + startBit);
}
else
{
auto* values = ensureSize (sizeNeededToHold (highestBit + bits));
auto wordsToMove = bitToIndex (bits);
auto numOriginalInts = bitToIndex (highestBit);
highestBit += bits;
if (wordsToMove > 0)
{
for (int i = (int) numOriginalInts; i >= 0; --i)
values[(size_t) i + wordsToMove] = values[i];
for (size_t j = 0; j < wordsToMove; ++j)
values[j] = 0;
bits &= 31;
}
if (bits != 0)
{
auto invBits = 32 - bits;
for (size_t i = bitToIndex (highestBit); i > wordsToMove; --i)
values[i] = (values[i] << bits) | (values[i - 1] >> invBits);
values[wordsToMove] = values[wordsToMove] << bits;
}
highestBit = getHighestBit();
}
}
void BigInteger::shiftRight (int bits, const int startBit)
{
if (startBit > 0)
{
for (int i = startBit; i <= highestBit; ++i)
setBit (i, (*this) [i + bits]);
highestBit = getHighestBit();
}
else
{
if (bits > highestBit)
{
clear();
}
else
{
auto wordsToMove = bitToIndex (bits);
auto top = 1 + bitToIndex (highestBit) - wordsToMove;
highestBit -= bits;
auto* values = getValues();
if (wordsToMove > 0)
{
for (size_t i = 0; i < top; ++i)
values[i] = values[i + wordsToMove];
for (size_t i = 0; i < wordsToMove; ++i)
values[top + i] = 0;
bits &= 31;
}
if (bits != 0)
{
auto invBits = 32 - bits;
--top;
for (size_t i = 0; i < top; ++i)
values[i] = (values[i] >> bits) | (values[i + 1] << invBits);
values[top] = (values[top] >> bits);
}
highestBit = getHighestBit();
}
}
}
BigInteger& BigInteger::shiftBits (int bits, const int startBit)
{
if (highestBit >= 0)
{
if (bits < 0)
shiftRight (-bits, startBit);
else if (bits > 0)
shiftLeft (bits, startBit);
}
return *this;
}
//==============================================================================
static BigInteger simpleGCD (BigInteger* m, BigInteger* n)
{
while (! m->isZero())
{
if (n->compareAbsolute (*m) > 0)
std::swap (m, n);
*m -= *n;
}
return *n;
}
BigInteger BigInteger::findGreatestCommonDivisor (BigInteger n) const
{
auto m = *this;
while (! n.isZero())
{
if (std::abs (m.getHighestBit() - n.getHighestBit()) <= 16)
return simpleGCD (&m, &n);
BigInteger temp2;
m.divideBy (n, temp2);
m.swapWith (n);
n.swapWith (temp2);
}
return m;
}
void BigInteger::exponentModulo (const BigInteger& exponent, const BigInteger& modulus)
{
*this %= modulus;
auto exp = exponent;
exp %= modulus;
if (modulus.getHighestBit() <= 32 || modulus % 2 == 0)
{
auto a = *this;
auto n = exp.getHighestBit();
for (int i = n; --i >= 0;)
{
*this *= *this;
if (exp[i])
*this *= a;
if (compareAbsolute (modulus) >= 0)
*this %= modulus;
}
}
else
{
auto Rfactor = modulus.getHighestBit() + 1;
BigInteger R (1);
R.shiftLeft (Rfactor, 0);
BigInteger R1, m1, g;
g.extendedEuclidean (modulus, R, m1, R1);
if (! g.isOne())
{
BigInteger a (*this);
for (int i = exp.getHighestBit(); --i >= 0;)
{
*this *= *this;
if (exp[i])
*this *= a;
if (compareAbsolute (modulus) >= 0)
*this %= modulus;
}
}
else
{
auto am = (*this * R) % modulus;
auto xm = am;
auto um = R % modulus;
for (int i = exp.getHighestBit(); --i >= 0;)
{
xm.montgomeryMultiplication (xm, modulus, m1, Rfactor);
if (exp[i])
xm.montgomeryMultiplication (am, modulus, m1, Rfactor);
}
xm.montgomeryMultiplication (1, modulus, m1, Rfactor);
swapWith (xm);
}
}
}
void BigInteger::montgomeryMultiplication (const BigInteger& other, const BigInteger& modulus,
const BigInteger& modulusp, const int k)
{
*this *= other;
auto t = *this;
setRange (k, highestBit - k + 1, false);
*this *= modulusp;
setRange (k, highestBit - k + 1, false);
*this *= modulus;
*this += t;
shiftRight (k, 0);
if (compare (modulus) >= 0)
*this -= modulus;
else if (isNegative())
*this += modulus;
}
void BigInteger::extendedEuclidean (const BigInteger& a, const BigInteger& b,
BigInteger& x, BigInteger& y)
{
BigInteger p (a), q (b), gcd (1);
Array<BigInteger> tempValues;
while (! q.isZero())
{
tempValues.add (p / q);
gcd = q;
q = p % q;
p = gcd;
}
x.clear();
y = 1;
for (int i = 1; i < tempValues.size(); ++i)
{
auto& v = tempValues.getReference (tempValues.size() - i - 1);
if ((i & 1) != 0)
x += y * v;
else
y += x * v;
}
if (gcd.compareAbsolute (y * b - x * a) != 0)
{
x.negate();
x.swapWith (y);
x.negate();
}
swapWith (gcd);
}
void BigInteger::inverseModulo (const BigInteger& modulus)
{
if (modulus.isOne() || modulus.isNegative())
{
clear();
return;
}
if (isNegative() || compareAbsolute (modulus) >= 0)
*this %= modulus;
if (isOne())
return;
if (findGreatestCommonDivisor (modulus) != 1)
{
clear(); // not invertible!
return;
}
BigInteger a1 (modulus), a2 (*this),
b1 (modulus), b2 (1);
while (! a2.isOne())
{
BigInteger temp1, multiplier (a1);
multiplier.divideBy (a2, temp1);
temp1 = a2;
temp1 *= multiplier;
auto temp2 = a1;
temp2 -= temp1;
a1 = a2;
a2 = temp2;
temp1 = b2;
temp1 *= multiplier;
temp2 = b1;
temp2 -= temp1;
b1 = b2;
b2 = temp2;
}
while (b2.isNegative())
b2 += modulus;
b2 %= modulus;
swapWith (b2);
}
//==============================================================================
OutputStream& JUCE_CALLTYPE operator<< (OutputStream& stream, const BigInteger& value)
{
return stream << value.toString (10);
}
String BigInteger::toString (const int base, const int minimumNumCharacters) const
{
String s;
auto v = *this;
if (base == 2 || base == 8 || base == 16)
{
auto bits = (base == 2) ? 1 : (base == 8 ? 3 : 4);
static const char hexDigits[] = "0123456789abcdef";
for (;;)
{
auto remainder = v.getBitRangeAsInt (0, bits);
v >>= bits;
if (remainder == 0 && v.isZero())
break;
s = String::charToString ((juce_wchar) (uint8) hexDigits [remainder]) + s;
}
}
else if (base == 10)
{
const BigInteger ten (10);
BigInteger remainder;
for (;;)
{
v.divideBy (ten, remainder);
if (remainder.isZero() && v.isZero())
break;
s = String (remainder.getBitRangeAsInt (0, 8)) + s;
}
}
else
{
jassertfalse; // can't do the specified base!
return {};
}
s = s.paddedLeft ('0', minimumNumCharacters);
return isNegative() ? "-" + s : s;
}
void BigInteger::parseString (StringRef text, const int base)
{
clear();
auto t = text.text.findEndOfWhitespace();
setNegative (*t == (juce_wchar) '-');
if (base == 2 || base == 8 || base == 16)
{
auto bits = (base == 2) ? 1 : (base == 8 ? 3 : 4);
for (;;)
{
auto c = t.getAndAdvance();
auto digit = CharacterFunctions::getHexDigitValue (c);
if (((uint32) digit) < (uint32) base)
{
*this <<= bits;
*this += digit;
}
else if (c == 0)
{
break;
}
}
}
else if (base == 10)
{
const BigInteger ten ((uint32) 10);
for (;;)
{
auto c = t.getAndAdvance();
if (c >= '0' && c <= '9')
{
*this *= ten;
*this += (int) (c - '0');
}
else if (c == 0)
{
break;
}
}
}
}
MemoryBlock BigInteger::toMemoryBlock() const
{
auto numBytes = (getHighestBit() + 8) >> 3;
MemoryBlock mb ((size_t) numBytes);
auto* values = getValues();
for (int i = 0; i < numBytes; ++i)
mb[i] = (char) ((values[i / 4] >> ((i & 3) * 8)) & 0xff);
return mb;
}
void BigInteger::loadFromMemoryBlock (const MemoryBlock& data)
{
auto numBytes = data.getSize();
auto numInts = 1 + (numBytes / sizeof (uint32));
auto* values = ensureSize (numInts);
for (int i = 0; i < (int) numInts - 1; ++i)
values[i] = (uint32) ByteOrder::littleEndianInt (addBytesToPointer (data.getData(), (size_t) i * sizeof (uint32)));
values[numInts - 1] = 0;
for (int i = (int) (numBytes & ~3u); i < (int) numBytes; ++i)
this->setBitRangeAsInt (i << 3, 8, (uint32) data [i]);
highestBit = (int) numBytes * 8;
highestBit = getHighestBit();
}
//==============================================================================
void writeLittleEndianBitsInBuffer (void* buffer, uint32 startBit, uint32 numBits, uint32 value) noexcept
{
jassert (buffer != nullptr);
jassert (numBits > 0 && numBits <= 32);
jassert (numBits == 32 || (value >> numBits) == 0);
uint8* data = static_cast<uint8*> (buffer) + startBit / 8;
if (const uint32 offset = (startBit & 7))
{
const uint32 bitsInByte = 8 - offset;
const uint8 current = *data;
if (bitsInByte >= numBits)
{
*data = (uint8) ((current & ~(((1u << numBits) - 1u) << offset)) | (value << offset));
return;
}
*data++ = current ^ (uint8) (((value << offset) ^ current) & (((1u << bitsInByte) - 1u) << offset));
numBits -= bitsInByte;
value >>= bitsInByte;
}
while (numBits >= 8)
{
*data++ = (uint8) value;
value >>= 8;
numBits -= 8;
}
if (numBits > 0)
*data = (uint8) ((*data & (uint32) (0xff << numBits)) | value);
}
uint32 readLittleEndianBitsInBuffer (const void* buffer, uint32 startBit, uint32 numBits) noexcept
{
jassert (buffer != nullptr);
jassert (numBits > 0 && numBits <= 32);
uint32 result = 0;
uint32 bitsRead = 0;
const uint8* data = static_cast<const uint8*> (buffer) + startBit / 8;
if (const uint32 offset = (startBit & 7))
{
const uint32 bitsInByte = 8 - offset;
result = (uint32) (*data >> offset);
if (bitsInByte >= numBits)
return result & ((1u << numBits) - 1u);
numBits -= bitsInByte;
bitsRead += bitsInByte;
++data;
}
while (numBits >= 8)
{
result |= (((uint32) *data++) << bitsRead);
bitsRead += 8;
numBits -= 8;
}
if (numBits > 0)
result |= ((*data & ((1u << numBits) - 1u)) << bitsRead);
return result;
}
//==============================================================================
//==============================================================================
#if JUCE_UNIT_TESTS
class BigIntegerTests final : public UnitTest
{
public:
BigIntegerTests()
: UnitTest ("BigInteger", UnitTestCategories::maths)
{}
static BigInteger getBigRandom (Random& r)
{
BigInteger b;
while (b < 2)
r.fillBitsRandomly (b, 0, r.nextInt (150) + 1);
return b;
}
void runTest() override
{
{
beginTest ("BigInteger");
Random r = getRandom();
expect (BigInteger().isZero());
expect (BigInteger (1).isOne());
for (int j = 10000; --j >= 0;)
{
BigInteger b1 (getBigRandom (r)),
b2 (getBigRandom (r));
BigInteger b3 = b1 + b2;
expect (b3 > b1 && b3 > b2);
expect (b3 - b1 == b2);
expect (b3 - b2 == b1);
BigInteger b4 = b1 * b2;
expect (b4 > b1 && b4 > b2);
expect (b4 / b1 == b2);
expect (b4 / b2 == b1);
expect (((b4 << 1) >> 1) == b4);
expect (((b4 << 10) >> 10) == b4);
expect (((b4 << 100) >> 100) == b4);
// TODO: should add tests for other ops (although they also get pretty well tested in the RSA unit test)
BigInteger b5;
b5.loadFromMemoryBlock (b3.toMemoryBlock());
expect (b3 == b5);
}
}
{
beginTest ("Bit setting");
Random r = getRandom();
static uint8 test[2048];
for (int j = 100000; --j >= 0;)
{
uint32 offset = static_cast<uint32> (r.nextInt (200) + 10);
uint32 num = static_cast<uint32> (r.nextInt (32) + 1);
uint32 value = static_cast<uint32> (r.nextInt());
if (num < 32)
value &= ((1u << num) - 1);
auto old1 = readLittleEndianBitsInBuffer (test, offset - 6, 6);
auto old2 = readLittleEndianBitsInBuffer (test, offset + num, 6);
writeLittleEndianBitsInBuffer (test, offset, num, value);
auto result = readLittleEndianBitsInBuffer (test, offset, num);
expect (result == value);
expect (old1 == readLittleEndianBitsInBuffer (test, offset - 6, 6));
expect (old2 == readLittleEndianBitsInBuffer (test, offset + num, 6));
}
}
}
};
static BigIntegerTests bigIntegerTests;
#endif
} // namespace juce
juce::Array
Definition juce_Array.h:56
juce::Array::size
int size() const noexcept
Definition juce_Array.h:215
juce::Array::add
void add(const ElementType &newElement)
Definition juce_Array.h:418
juce::Array::getReference
ElementType & getReference(int index) noexcept
Definition juce_Array.h:267
juce::BigInteger
Definition juce_BigInteger.h:39
juce::BigInteger::clear
BigInteger & clear() noexcept
Definition juce_BigInteger.cpp:281
juce::BigInteger::toMemoryBlock
MemoryBlock toMemoryBlock() const
Definition juce_BigInteger.cpp:1193
juce::BigInteger::isOne
bool isOne() const noexcept
Definition juce_BigInteger.cpp:356
juce::BigInteger::getBitRange
BigInteger getBitRange(int startBit, int numBits) const
Definition juce_BigInteger.cpp:219
juce::BigInteger::parseString
void parseString(StringRef text, int base)
Definition juce_BigInteger.cpp:1145
juce::BigInteger::toInt64
int64 toInt64() const noexcept
Definition juce_BigInteger.cpp:212
juce::BigInteger::exponentModulo
void exponentModulo(const BigInteger &exponent, const BigInteger &modulus)
Definition juce_BigInteger.cpp:919
juce::BigInteger::setNegative
void setNegative(bool shouldBeNegative) noexcept
Definition juce_BigInteger.cpp:366
juce::BigInteger::~BigInteger
~BigInteger()
juce::BigInteger::getBitRangeAsInt
uint32 getBitRangeAsInt(int startBit, int numBits) const noexcept
Definition juce_BigInteger.cpp:237
juce::BigInteger::setRange
BigInteger & setRange(int startBit, int numBits, bool shouldBeSet)
Definition juce_BigInteger.cpp:333
juce::BigInteger::findGreatestCommonDivisor
BigInteger findGreatestCommonDivisor(BigInteger other) const
Definition juce_BigInteger.cpp:900
juce::BigInteger::extendedEuclidean
void extendedEuclidean(const BigInteger &a, const BigInteger &b, BigInteger &xOut, BigInteger &yOut)
Definition juce_BigInteger.cpp:1005
juce::BigInteger::getHighestBit
int getHighestBit() const noexcept
Definition juce_BigInteger.cpp:391
juce::BigInteger::divideBy
void divideBy(const BigInteger &divisor, BigInteger &remainder)
Definition juce_BigInteger.cpp:578
juce::BigInteger::toString
String toString(int base, int minimumNumCharacters=1) const
Definition juce_BigInteger.cpp:1098
juce::BigInteger::shiftBits
BigInteger & shiftBits(int howManyBitsLeft, int startBit)
Definition juce_BigInteger.cpp:873
juce::BigInteger::findNextClearBit
int findNextClearBit(int startIndex) const noexcept
Definition juce_BigInteger.cpp:413
juce::BigInteger::compare
int compare(const BigInteger &other) const noexcept
Definition juce_BigInteger.cpp:743
juce::BigInteger::insertBit
BigInteger & insertBit(int bitNumber, bool shouldBeSet)
Definition juce_BigInteger.cpp:341
juce::BigInteger::setBitRangeAsInt
BigInteger & setBitRangeAsInt(int startBit, int numBits, uint32 valueToSet)
Definition juce_BigInteger.cpp:263
juce::BigInteger::clearBit
BigInteger & clearBit(int bitNumber) noexcept
Definition juce_BigInteger.cpp:320
juce::BigInteger::BigInteger
BigInteger()
Definition juce_BigInteger.cpp:54
juce::BigInteger::negate
void negate() noexcept
Definition juce_BigInteger.cpp:371
juce::BigInteger::findNextSetBit
int findNextSetBit(int startIndex) const noexcept
Definition juce_BigInteger.cpp:402
juce::BigInteger::loadFromMemoryBlock
void loadFromMemoryBlock(const MemoryBlock &data)
Definition juce_BigInteger.cpp:1205
juce::BigInteger::isZero
bool isZero() const noexcept
Definition juce_BigInteger.cpp:351
juce::BigInteger::countNumberOfSetBits
int countNumberOfSetBits() const noexcept
Definition juce_BigInteger.cpp:380
juce::BigInteger::swapWith
void swapWith(BigInteger &) noexcept
Definition juce_BigInteger.cpp:133
juce::BigInteger::montgomeryMultiplication
void montgomeryMultiplication(const BigInteger &other, const BigInteger &modulus, const BigInteger &modulusp, int k)
Definition juce_BigInteger.cpp:985
juce::BigInteger::isNegative
bool isNegative() const noexcept
Definition juce_BigInteger.cpp:361
juce::BigInteger::operator[]
bool operator[](int bit) const noexcept
Definition juce_BigInteger.cpp:200
juce::BigInteger::compareAbsolute
int compareAbsolute(const BigInteger &other) const noexcept
Definition juce_BigInteger.cpp:756
juce::BigInteger::operator=
BigInteger & operator=(BigInteger &&) noexcept
Definition juce_BigInteger.cpp:123
juce::BigInteger::setBit
BigInteger & setBit(int bitNumber)
Definition juce_BigInteger.cpp:294
juce::BigInteger::toInteger
int toInteger() const noexcept
Definition juce_BigInteger.cpp:206
juce::BigInteger::inverseModulo
void inverseModulo(const BigInteger &modulus)
Definition juce_BigInteger.cpp:1042
juce::ByteOrder::littleEndianInt
static constexpr uint32 littleEndianInt(const void *bytes) noexcept
Definition juce_ByteOrder.h:199
juce::CharacterFunctions::getHexDigitValue
static int getHexDigitValue(juce_wchar digit) noexcept
Definition juce_CharacterFunctions.cpp:112
juce::HeapBlock::calloc
void calloc(SizeType newNumElements, const size_t elementSize=sizeof(ElementType))
Definition juce_HeapBlock.h:259
juce::MemoryBlock
Definition juce_MemoryBlock.h:33
juce::MemoryBlock::getData
void * getData() noexcept
Definition juce_MemoryBlock.h:91
juce::MemoryBlock::getSize
size_t getSize() const noexcept
Definition juce_MemoryBlock.h:127
juce::OutputStream
Definition juce_OutputStream.h:38
juce::StringRef
Definition juce_StringRef.h:62
juce::StringRef::text
String::CharPointerType text
Definition juce_StringRef.h:130
juce::String
Definition juce_String.h:53
juce::String::paddedLeft
String paddedLeft(juce_wchar padCharacter, int minimumLength) const
Definition juce_String.cpp:1161
juce::String::charToString
static String charToString(juce_wchar character)
Definition juce_String.cpp:359
juce::UnitTest
Definition juce_UnitTest.h:70