28 inline uint32 bitToMask (
const int bit)
noexcept {
return (uint32) 1 << (bit & 31); }
29 inline size_t bitToIndex (
const int bit)
noexcept {
return (
size_t) (bit >> 5); }
30 inline size_t sizeNeededToHold (
int highestBit)
noexcept {
return (
size_t) (highestBit >> 5) + 1; }
33int findHighestSetBit (uint32 n)
noexcept
37 #if JUCE_GCC || JUCE_CLANG
38 return 31 - __builtin_clz (n);
40 unsigned long highest;
41 _BitScanReverse (&highest, n);
49 return countNumberOfBits (n >> 1);
55 : allocatedSize (numPreallocatedInts)
57 for (
int i = 0; i < numPreallocatedInts; ++i)
62 : allocatedSize (numPreallocatedInts),
66 preallocated[0] = (uint32) std::abs (value);
68 for (
int i = 1; i < numPreallocatedInts; ++i)
75 : allocatedSize (numPreallocatedInts),
78 preallocated[0] = value;
80 for (
int i = 1; i < numPreallocatedInts; ++i)
87 : allocatedSize (numPreallocatedInts),
94 preallocated[0] = (uint32) value;
95 preallocated[1] = (uint32) (value >> 32);
97 for (
int i = 2; i < numPreallocatedInts; ++i)
104 : allocatedSize (
other.allocatedSize),
105 highestBit (
other.getHighestBit()),
106 negative (
other.negative)
108 if (allocatedSize > numPreallocatedInts)
109 heapAllocation.
malloc (allocatedSize);
115 : heapAllocation (std::move (
other.heapAllocation)),
116 allocatedSize (
other.allocatedSize),
117 highestBit (
other.highestBit),
118 negative (
other.negative)
125 heapAllocation = std::move (
other.heapAllocation);
127 allocatedSize =
other.allocatedSize;
128 highestBit =
other.highestBit;
129 negative =
other.negative;
139 for (
int i = 0; i < numPreallocatedInts; ++i)
140 std::swap (preallocated[i],
other.preallocated[i]);
143 std::swap (allocatedSize,
other.allocatedSize);
144 std::swap (highestBit,
other.highestBit);
145 std::swap (negative,
other.negative);
152 highestBit =
other.getHighestBit();
156 heapAllocation.
free();
163 negative =
other.negative;
171 jassert (heapAllocation !=
nullptr || allocatedSize <= numPreallocatedInts);
173 return heapAllocation !=
nullptr ? heapAllocation
174 :
const_cast<uint32*
> (preallocated);
177uint32* BigInteger::ensureSize (
const size_t numVals)
179 if (numVals > allocatedSize)
181 auto oldSize = allocatedSize;
182 allocatedSize = ((numVals + 2) * 3) / 2;
184 if (heapAllocation ==
nullptr)
186 heapAllocation.
calloc (allocatedSize);
187 memcpy (heapAllocation, preallocated,
sizeof (uint32) * numPreallocatedInts);
191 heapAllocation.
realloc (allocatedSize);
193 for (
auto* values = getValues(); oldSize < allocatedSize; ++oldSize)
210 auto n = (
int) (getValues()[0] & 0x7fffffff);
211 return negative ? -
n :
n;
216 auto* values = getValues();
217 auto n = (((int64) (values[1] & 0x7fffffff)) << 32) | values[0];
218 return negative ? -
n :
n;
255 auto* values = getValues();
257 auto n = ((uint32) values [pos]) >> offset;
260 n |= ((uint32) values [pos + 1]) << (32 - offset);
262 return n & (((uint32) 0xffffffff) >>
endSpace);
273 for (
int i = 0; i <
numBits; ++i)
283 heapAllocation.
free();
284 allocatedSize = numPreallocatedInts;
288 for (
int i = 0; i < numPreallocatedInts; ++i)
296 if (
bit > highestBit)
316 if (
bit >= 0 &&
bit <= highestBit)
320 if (
bit == highestBit)
321 highestBit = getHighestBit();
352 return negative && !
isZero();
362 negative = (! negative) && !
isZero();
365#if JUCE_MSVC && ! defined (__INTEL_COMPILER)
366 #pragma intrinsic (_BitScanReverse)
372 auto* values = getValues();
375 total += countNumberOfBits (values[i]);
382 auto* values = getValues();
384 for (
int i = (
int)
bitToIndex (highestBit); i >= 0; --i)
385 if (uint32
n = values[i])
386 return findHighestSetBit (
n) + (i << 5);
393 auto* values = getValues();
395 for (; i <= highestBit; ++i)
404 auto* values = getValues();
406 for (; i <= highestBit; ++i)
419 if (
other.isNegative())
440 highestBit = jmax (highestBit, other.highestBit) + 1;
442 auto numInts = sizeNeededToHold (highestBit);
443 auto* values = ensureSize (numInts);
444 auto* otherValues = other.getValues();
447 for (
size_t i = 0; i < numInts; ++i)
449 remainder += values[i];
451 if (i < other.allocatedSize)
452 remainder += otherValues[i];
454 values[i] = (uint32) remainder;
458 jassert (remainder == 0);
465BigInteger& BigInteger::operator-= (
const BigInteger& other)
473 if (other.isNegative())
474 return operator+= (-other);
494 auto maxOtherInts = sizeNeededToHold (other.getHighestBit());
495 jassert (numInts >= maxOtherInts);
496 auto* values = getValues();
497 auto* otherValues = other.getValues();
498 int64 amountToSubtract = 0;
500 for (
size_t i = 0; i < numInts; ++i)
502 if (i < maxOtherInts)
503 amountToSubtract += (int64) otherValues[i];
505 if (values[i] >= amountToSubtract)
507 values[i] = (uint32) (values[i] - amountToSubtract);
508 amountToSubtract = 0;
512 const int64 n = ((int64) values[i] + (((int64) 1) << 32)) - amountToSubtract;
513 values[i] = (uint32) n;
514 amountToSubtract = 1;
522BigInteger& BigInteger::operator*= (
const BigInteger& other)
528 auto t = other.getHighestBit();
534 total.highestBit = n + t + 1;
535 auto* totalValues = total.ensureSize (sizeNeededToHold (total.highestBit) + 1);
541 m.setNegative (
false);
543 auto* mValues = m.getValues();
544 auto* values = getValues();
546 for (
int i = 0; i <= t; ++i)
550 for (
int j = 0; j <= n; ++j)
552 auto uv = (uint64) totalValues[i + j] + (uint64) values[j] * (uint64) mValues[i] + (uint64) c;
553 totalValues[i + j] = (uint32) uv;
557 totalValues[i + n + 1] = c;
560 total.highestBit = total.getHighestBit();
561 total.setNegative (wasNegative ^ other.isNegative());
592 temp.setNegative (
false);
597 while (leftShift >= 0)
605 if (--leftShift >= 0)
621BigInteger& BigInteger::operator|= (
const BigInteger& other)
629 if (other.highestBit >= 0)
631 auto* values = ensureSize (sizeNeededToHold (other.highestBit));
632 auto* otherValues = other.getValues();
634 auto n = (int) bitToIndex (other.highestBit) + 1;
637 values[n] |= otherValues[n];
639 if (other.highestBit > highestBit)
640 highestBit = other.highestBit;
648BigInteger& BigInteger::operator&= (
const BigInteger& other)
656 auto* values = getValues();
657 auto* otherValues = other.getValues();
659 auto n = (int) allocatedSize;
661 while (n > (
int) other.allocatedSize)
665 values[n] &= otherValues[n];
667 if (other.highestBit < highestBit)
668 highestBit = other.highestBit;
674BigInteger& BigInteger::operator^= (
const BigInteger& other)
685 if (other.highestBit >= 0)
687 auto* values = ensureSize (sizeNeededToHold (other.highestBit));
688 auto* otherValues = other.getValues();
690 auto n = (int) bitToIndex (other.highestBit) + 1;
693 values[n] ^= otherValues[n];
695 if (other.highestBit > highestBit)
696 highestBit = other.highestBit;
704BigInteger& BigInteger::operator%= (
const BigInteger& divisor)
712BigInteger& BigInteger::operator++() {
return operator+= (1); }
713BigInteger& BigInteger::operator--() {
return operator-= (1); }
714BigInteger BigInteger::operator++ (
int) {
const auto old (*
this); operator+= (1);
return old; }
715BigInteger BigInteger::operator-- (
int) {
const auto old (*
this); operator-= (1);
return old; }
717BigInteger BigInteger::operator-()
const {
auto b (*
this); b.negate();
return b; }
718BigInteger BigInteger::operator+ (
const BigInteger& other)
const {
auto b (*
this);
return b += other; }
719BigInteger BigInteger::operator- (
const BigInteger& other)
const {
auto b (*
this);
return b -= other; }
720BigInteger BigInteger::operator* (
const BigInteger& other)
const {
auto b (*
this);
return b *= other; }
721BigInteger BigInteger::operator/ (
const BigInteger& other)
const {
auto b (*
this);
return b /= other; }
722BigInteger BigInteger::operator| (
const BigInteger& other)
const {
auto b (*
this);
return b |= other; }
723BigInteger BigInteger::operator& (
const BigInteger& other)
const {
auto b (*
this);
return b &= other; }
724BigInteger BigInteger::operator^ (
const BigInteger& other)
const {
auto b (*
this);
return b ^= other; }
725BigInteger BigInteger::operator% (
const BigInteger& other)
const {
auto b (*
this);
return b %= other; }
726BigInteger BigInteger::operator<< (
const int numBits)
const {
auto b (*
this);
return b <<= numBits; }
727BigInteger BigInteger::operator>> (
const int numBits)
const {
auto b (*
this);
return b >>= numBits; }
728BigInteger& BigInteger::operator<<= (
const int numBits) {
shiftBits (numBits, 0);
return *
this; }
729BigInteger& BigInteger::operator>>= (
const int numBits) {
shiftBits (-numBits, 0);
return *
this; }
734 auto isNeg = isNegative();
742 return isNeg ? -1 : 1;
747 auto h1 = getHighestBit();
748 auto h2 =
other.getHighestBit();
750 if (
h1 >
h2)
return 1;
751 if (
h1 <
h2)
return -1;
753 auto* values = getValues();
763bool BigInteger::operator== (
const BigInteger&
other)
const noexcept {
return compare (
other) == 0; }
764bool BigInteger::operator!= (
const BigInteger& other)
const noexcept {
return compare (other) != 0; }
765bool BigInteger::operator< (
const BigInteger& other)
const noexcept {
return compare (other) < 0; }
766bool BigInteger::operator<= (
const BigInteger& other)
const noexcept {
return compare (other) <= 0; }
767bool BigInteger::operator> (
const BigInteger& other)
const noexcept {
return compare (other) > 0; }
768bool BigInteger::operator>= (
const BigInteger& other)
const noexcept {
return compare (other) >= 0; }
771void BigInteger::shiftLeft (
int bits,
const int startBit)
775 for (
int i = highestBit; i >= startBit; --i)
776 setBit (i + bits, (*
this) [i]);
783 auto* values = ensureSize (sizeNeededToHold (highestBit + bits));
784 auto wordsToMove = bitToIndex (bits);
785 auto numOriginalInts = bitToIndex (highestBit);
790 for (
int i = (
int) numOriginalInts; i >= 0; --i)
791 values[(
size_t) i + wordsToMove] = values[i];
793 for (
size_t j = 0; j < wordsToMove; ++j)
801 auto invBits = 32 - bits;
803 for (
size_t i = bitToIndex (highestBit); i > wordsToMove; --i)
804 values[i] = (values[i] << bits) | (values[i - 1] >> invBits);
806 values[wordsToMove] = values[wordsToMove] << bits;
813void BigInteger::shiftRight (
int bits,
const int startBit)
817 for (
int i = startBit; i <= highestBit; ++i)
818 setBit (i, (*
this) [i + bits]);
824 if (bits > highestBit)
830 auto wordsToMove = bitToIndex (bits);
831 auto top = 1 + bitToIndex (highestBit) - wordsToMove;
833 auto* values = getValues();
837 for (
size_t i = 0; i < top; ++i)
838 values[i] = values[i + wordsToMove];
840 for (
size_t i = 0; i < wordsToMove; ++i)
848 auto invBits = 32 - bits;
851 for (
size_t i = 0; i < top; ++i)
852 values[i] = (values[i] >> bits) | (values[i + 1] << invBits);
854 values[top] = (values[top] >> bits);
876 while (!
m->isZero())
878 if (
n->compareAbsolute (*
m) > 0)
893 if (std::abs (
m.getHighestBit() -
n.getHighestBit()) <= 16)
894 return simpleGCD (&
m, &
n);
915 auto n =
exp.getHighestBit();
917 for (
int i =
n; --i >= 0;)
941 for (
int i =
exp.getHighestBit(); --i >= 0;)
958 for (
int i =
exp.getHighestBit(); --i >= 0;)
1019 if (
gcd.compareAbsolute (
y *
b -
x *
a) != 0)
1052 while (!
a2.isOne())
1072 while (
b2.isNegative())
1082 return stream << value.
toString (10);
1093 static const char hexDigits[] =
"0123456789abcdef";
1106 else if (
base == 10)
1145 auto c =
t.getAndAdvance();
1159 else if (
base == 10)
1165 auto c =
t.getAndAdvance();
1167 if (
c >=
'0' &&
c <=
'9')
1170 *
this += (
int) (
c -
'0');
1184 auto* values = getValues();
1186 for (
int i = 0; i < numBytes; ++i)
1187 mb[i] = (
char) ((values[i / 4] >> ((i & 3) * 8)) & 0xff);
1194 auto numBytes = data.
getSize();
1195 auto numInts = 1 + (numBytes /
sizeof (uint32));
1196 auto* values = ensureSize (
numInts);
1203 for (
int i = (
int) (numBytes & ~3u); i < (
int) numBytes; ++i)
1206 highestBit = (
int) numBytes * 8;
1211void writeLittleEndianBitsInBuffer (
void* buffer, uint32
startBit, uint32
numBits, uint32 value)
noexcept
1213 jassert (buffer !=
nullptr);
1217 uint8* data =
static_cast<uint8*
> (buffer) +
startBit / 8;
1219 if (
const uint32 offset = (
startBit & 7))
1226 *data = (uint8) ((
current & ~(((1u <<
numBits) - 1u) << offset)) | (value << offset));
1230 *data++ = current ^ (uint8) (((value << offset) ^ current) & (((1u << bitsInByte) - 1u) << offset));
1231 numBits -= bitsInByte;
1232 value >>= bitsInByte;
1235 while (numBits >= 8)
1237 *data++ = (uint8) value;
1243 *data = (uint8) ((*data & (0xff << numBits)) | value);
1246uint32 readLittleEndianBitsInBuffer (
const void* buffer, uint32 startBit, uint32 numBits)
noexcept
1248 jassert (buffer !=
nullptr);
1249 jassert (numBits > 0 && numBits <= 32);
1252 uint32 bitsRead = 0;
1253 const uint8* data =
static_cast<const uint8*
> (buffer) + startBit / 8;
1255 if (
const uint32 offset = (startBit & 7))
1257 const uint32 bitsInByte = 8 - offset;
1258 result = (*data >> offset);
1260 if (bitsInByte >= numBits)
1261 return result & ((1u << numBits) - 1u);
1263 numBits -= bitsInByte;
1264 bitsRead += bitsInByte;
1268 while (numBits >= 8)
1270 result |= (((uint32) *data++) << bitsRead);
1276 result |= ((*data & ((1u << numBits) - 1u)) << bitsRead);
1285class BigIntegerTests :
public UnitTest
1295 r.fillBitsRandomly (
b, 0, r.nextInt (150) + 1);
1300 void runTest()
override
1303 beginTest (
"BigInteger");
1305 Random r = getRandom();
1307 expect (BigInteger().isZero());
1308 expect (BigInteger(1).isOne());
1310 for (
int j = 10000; --
j >= 0;)
1324 expect (((
b4 << 1) >> 1) ==
b4);
1325 expect (((
b4 << 10) >> 10) ==
b4);
1326 expect (((
b4 << 100) >> 100) ==
b4);
1331 b5.loadFromMemoryBlock (
b3.toMemoryBlock());
1337 beginTest (
"Bit setting");
1339 Random r = getRandom();
1340 static uint8
test[2048];
1342 for (
int j = 100000; --
j >= 0;)
1344 uint32 offset =
static_cast<uint32
> (r.nextInt (200) + 10);
1345 uint32
num =
static_cast<uint32
> (r.nextInt (32) + 1);
1346 uint32 value =
static_cast<uint32
> (r.nextInt());
1349 value &= ((1u <<
num) - 1);
1351 auto old1 = readLittleEndianBitsInBuffer (
test, offset - 6, 6);
1352 auto old2 = readLittleEndianBitsInBuffer (
test, offset +
num, 6);
1353 writeLittleEndianBitsInBuffer (
test, offset,
num, value);
1354 auto result = readLittleEndianBitsInBuffer (
test, offset,
num);
1356 expect (result == value);
1357 expect (
old1 == readLittleEndianBitsInBuffer (
test, offset - 6, 6));
1358 expect (
old2 == readLittleEndianBitsInBuffer (
test, offset +
num, 6));
1364static BigIntegerTests bigIntegerTests;
Holds a resizable array of primitive or copy-by-value objects.
void swapWith(OtherArrayType &otherArray) noexcept
This swaps the contents of this array with those of another array.
int size() const noexcept
Returns the current number of elements in the array.
Array()=default
Creates an empty array.
void add(const ElementType &newElement)
Appends a new element at the end of the array.
ElementType & getReference(int index) const noexcept
Returns a direct reference to one of the elements in the array, without checking the index passed in.
void clear()
Removes all elements from the array.
An arbitrarily large integer class.
MemoryBlock toMemoryBlock() const
Turns the number into a block of binary data.
bool isOne() const noexcept
Returns true if the value is 1.
void clearBit(int bitNumber) noexcept
Clears a particular bit in the number.
BigInteger getBitRange(int startBit, int numBits) const
Returns a range of bits as a new BigInteger.
void parseString(StringRef text, int base)
Reads the numeric value from a string.
int64 toInt64() const noexcept
Attempts to get the lowest 64 bits of the value as an integer.
void exponentModulo(const BigInteger &exponent, const BigInteger &modulus)
Performs a combined exponent and modulo operation.
void setNegative(bool shouldBeNegative) noexcept
Changes the sign of the number to be positive or negative.
uint32 getBitRangeAsInt(int startBit, int numBits) const noexcept
Returns a range of bits as an integer value.
void clear() noexcept
Resets the value to 0.
BigInteger findGreatestCommonDivisor(BigInteger other) const
Returns the largest value that will divide both this value and the argument.
void extendedEuclidean(const BigInteger &a, const BigInteger &b, BigInteger &xOut, BigInteger &yOut)
Performs the Extended Euclidean algorithm.
void setRange(int startBit, int numBits, bool shouldBeSet)
Sets a range of bits to be either on or off.
void shiftBits(int howManyBitsLeft, int startBit)
Shifts a section of bits left or right.
int getHighestBit() const noexcept
Returns the index of the highest set bit in the number.
void divideBy(const BigInteger &divisor, BigInteger &remainder)
Divides this value by another one and returns the remainder.
String toString(int base, int minimumNumCharacters=1) const
Converts the number to a string.
int findNextClearBit(int startIndex) const noexcept
Looks for the index of the next clear bit after a given starting point.
int compare(const BigInteger &other) const noexcept
Does a signed comparison of two BigIntegers.
BigInteger()
Creates an empty BigInteger.
void negate() noexcept
Inverts the sign of the number.
void setBit(int bitNumber)
Sets a specified bit to 1.
void setBitRangeAsInt(int startBit, int numBits, uint32 valueToSet)
Sets a range of bits to an integer value.
int findNextSetBit(int startIndex) const noexcept
Looks for the index of the next set bit after a given starting point.
void loadFromMemoryBlock(const MemoryBlock &data)
Converts a block of raw data into a number.
bool isZero() const noexcept
Returns true if no bits are set.
int countNumberOfSetBits() const noexcept
Returns the total number of set bits in the value.
void swapWith(BigInteger &) noexcept
Swaps the internal contents of this with another object.
void montgomeryMultiplication(const BigInteger &other, const BigInteger &modulus, const BigInteger &modulusp, int k)
Performs the Montgomery Multiplication with modulo.
bool isNegative() const noexcept
Returns true if the value is less than zero.
bool operator[](int bit) const noexcept
Returns the value of a specified bit in the number.
int compareAbsolute(const BigInteger &other) const noexcept
Compares the magnitudes of two BigIntegers, ignoring their signs.
BigInteger & operator=(BigInteger &&) noexcept
Move assignment operator.
void insertBit(int bitNumber, bool shouldBeSet)
Inserts a bit an a given position, shifting up any bits above it.
int toInteger() const noexcept
Attempts to get the lowest 32 bits of the value as an integer.
void inverseModulo(const BigInteger &modulus)
Performs an inverse modulo on the value.
static JUCE_CONSTEXPR uint32 littleEndianInt(const void *bytes) noexcept
Turns 4 bytes into a little-endian integer.
CharPointer_UTF8 findEndOfWhitespace() const noexcept
Returns the first non-whitespace character in the string.
static int getHexDigitValue(juce_wchar digit) noexcept
Returns 0 to 16 for '0' to 'F", or -1 for characters that aren't a legal hex digit.
void malloc(SizeType newNumElements, size_t elementSize=sizeof(ElementType))
Allocates a specified amount of memory.
void realloc(SizeType newNumElements, size_t elementSize=sizeof(ElementType))
Re-allocates a specified amount of memory.
void free() noexcept
Frees any currently-allocated data.
void calloc(SizeType newNumElements, const size_t elementSize=sizeof(ElementType))
Allocates a specified amount of memory and clears it.
A class to hold a resizable block of raw data.
size_t getSize() const noexcept
Returns the block's current allocated size, in bytes.
void * getData() const noexcept
Returns a void pointer to the data.
The base class for streams that write data to some kind of destination.
A simple class for holding temporary references to a string literal or String.
String::CharPointerType text
The text that is referenced.
static String charToString(juce_wchar character)
Creates a string from a single character.