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; }
33 int 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);
111 memcpy (getValues(), other.getValues(), sizeof (uint32) * allocatedSize);
115 : heapAllocation (std::move (other.heapAllocation)),
116 allocatedSize (other.allocatedSize),
117 highestBit (other.highestBit),
118 negative (other.negative)
120 memcpy (preallocated, other.preallocated, sizeof (preallocated));
125 heapAllocation = std::move (other.heapAllocation);
126 memcpy (preallocated, other.preallocated, sizeof (preallocated));
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]);
142 heapAllocation.swapWith (other.heapAllocation);
143 std::swap (allocatedSize, other.allocatedSize);
144 std::swap (highestBit, other.highestBit);
145 std::swap (negative, other.negative);
153 auto newAllocatedSize = (size_t) jmax ((
size_t) numPreallocatedInts, sizeNeededToHold (highestBit));
155 if (newAllocatedSize <= numPreallocatedInts)
156 heapAllocation.
free();
157 else if (newAllocatedSize != allocatedSize)
158 heapAllocation.
malloc (newAllocatedSize);
160 allocatedSize = newAllocatedSize;
162 memcpy (getValues(), other.getValues(), sizeof (uint32) * allocatedSize);
163 negative = other.negative;
169 uint32* BigInteger::getValues() const noexcept
171 jassert (heapAllocation !=
nullptr || allocatedSize <= numPreallocatedInts);
173 return heapAllocation !=
nullptr ? heapAllocation
174 :
const_cast<uint32*
> (preallocated);
177 uint32* 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)
204 return bit <= highestBit && bit >= 0
205 && ((getValues() [bitToIndex (bit)] & bitToMask (bit)) != 0);
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;
224 numBits = jmax (0, jmin (numBits,
getHighestBit() + 1 - startBit));
225 auto* destValues = r.ensureSize (sizeNeededToHold (numBits));
226 r.highestBit = numBits;
228 for (
int i = 0; numBits > 0;)
247 numBits = jmin (numBits, highestBit + 1 - startBit);
252 auto pos = bitToIndex (startBit);
253 auto offset = startBit & 31;
254 auto endSpace = 32 - numBits;
255 auto* values = getValues();
257 auto n = ((uint32) values [pos]) >> offset;
259 if (offset > endSpace)
260 n |= ((uint32) values [pos + 1]) << (32 - offset);
262 return n & (((uint32) 0xffffffff) >> endSpace);
273 for (
int i = 0; i < numBits; ++i)
275 setBit (startBit + i, (valueToSet & 1) != 0);
283 heapAllocation.
free();
284 allocatedSize = numPreallocatedInts;
288 for (
int i = 0; i < numPreallocatedInts; ++i)
296 if (bit > highestBit)
298 ensureSize (sizeNeededToHold (bit));
302 getValues() [bitToIndex (bit)] |= bitToMask (bit);
316 if (bit >= 0 && bit <= highestBit)
318 getValues() [bitToIndex (bit)] &= ~bitToMask (bit);
320 if (bit == highestBit)
321 highestBit = getHighestBit();
327 while (--numBits >= 0)
328 setBit (startBit++, shouldBeSet);
336 setBit (bit, shouldBeSet);
352 return negative && !
isZero();
362 negative = (! negative) && !
isZero();
365 #if JUCE_MSVC && ! defined (__INTEL_COMPILER)
366 #pragma intrinsic (_BitScanReverse)
372 auto* values = getValues();
374 for (
int i = (
int) sizeNeededToHold (highestBit); --i >= 0;)
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)
396 if ((values [bitToIndex (i)] & bitToMask (i)) != 0)
404 auto* values = getValues();
406 for (; i <= highestBit; ++i)
407 if ((values [bitToIndex (i)] & bitToMask (i)) == 0)
420 return operator-= (-other);
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);
465 BigInteger& 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;
522 BigInteger& 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());
569 if (
this == &divisor)
572 jassert (
this != &remainder);
577 if (divHB < 0 || ourHB < 0)
594 auto leftShift = ourHB - divHB;
597 while (leftShift >= 0)
605 if (--leftShift >= 0)
609 negative = wasNegative ^ divisor.
isNegative();
621 BigInteger& 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;
648 BigInteger& 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;
674 BigInteger& 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;
704 BigInteger& BigInteger::operator%= (
const BigInteger& divisor)
712 BigInteger& BigInteger::operator++() {
return operator+= (1); }
713 BigInteger& BigInteger::operator--() {
return operator-= (1); }
714 BigInteger BigInteger::operator++ (
int) {
const auto old (*
this); operator+= (1);
return old; }
715 BigInteger BigInteger::operator-- (
int) {
const auto old (*
this); operator-= (1);
return old; }
717 BigInteger BigInteger::operator-()
const {
auto b (*
this); b.negate();
return b; }
718 BigInteger BigInteger::operator+ (
const BigInteger& other)
const {
auto b (*
this);
return b += other; }
719 BigInteger BigInteger::operator- (
const BigInteger& other)
const {
auto b (*
this);
return b -= other; }
720 BigInteger BigInteger::operator* (
const BigInteger& other)
const {
auto b (*
this);
return b *= other; }
721 BigInteger BigInteger::operator/ (
const BigInteger& other)
const {
auto b (*
this);
return b /= other; }
722 BigInteger BigInteger::operator| (
const BigInteger& other)
const {
auto b (*
this);
return b |= other; }
723 BigInteger BigInteger::operator& (
const BigInteger& other)
const {
auto b (*
this);
return b &= other; }
724 BigInteger BigInteger::operator^ (
const BigInteger& other)
const {
auto b (*
this);
return b ^= other; }
725 BigInteger BigInteger::operator% (
const BigInteger& other)
const {
auto b (*
this);
return b %= other; }
726 BigInteger BigInteger::operator<< (
const int numBits)
const {
auto b (*
this);
return b <<= numBits; }
727 BigInteger BigInteger::operator>> (
const int numBits)
const {
auto b (*
this);
return b >>= numBits; }
728 BigInteger& BigInteger::operator<<= (
const int numBits) {
shiftBits (numBits, 0);
return *
this; }
729 BigInteger& BigInteger::operator>>= (
const int numBits) {
shiftBits (-numBits, 0);
return *
this; }
734 auto isNeg = isNegative();
736 if (isNeg == other.isNegative())
738 auto absComp = compareAbsolute (other);
739 return isNeg ? -absComp : absComp;
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();
754 auto* otherValues = other.getValues();
756 for (
int i = (
int) bitToIndex (h1); i >= 0; --i)
757 if (values[i] != otherValues[i])
758 return values[i] > otherValues[i] ? 1 : -1;
763 bool BigInteger::operator== (
const BigInteger& other)
const noexcept {
return compare (other) == 0; }
764 bool BigInteger::operator!= (
const BigInteger& other)
const noexcept {
return compare (other) != 0; }
765 bool BigInteger::operator< (
const BigInteger& other)
const noexcept {
return compare (other) < 0; }
766 bool BigInteger::operator<= (
const BigInteger& other)
const noexcept {
return compare (other) <= 0; }
767 bool BigInteger::operator> (
const BigInteger& other)
const noexcept {
return compare (other) > 0; }
768 bool BigInteger::operator>= (
const BigInteger& other)
const noexcept {
return compare (other) >= 0; }
771 void 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;
813 void 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);
867 shiftRight (-bits, startBit);
869 shiftLeft (bits, startBit);
894 return simpleGCD (&m, &n);
917 for (
int i = n; --i >= 0;)
932 R.shiftLeft (Rfactor, 0);
941 for (
int i = exp.getHighestBit(); --i >= 0;)
954 auto am = (*
this * R) % modulus;
956 auto um = R % modulus;
958 for (
int i = exp.getHighestBit(); --i >= 0;)
963 xm.montgomeryMultiplication (am, modulus, m1, Rfactor);
966 xm.montgomeryMultiplication (1, modulus, m1, Rfactor);
978 setRange (k, highestBit - k + 1,
false);
981 setRange (k, highestBit - k + 1,
false);
1000 tempValues.
add (p / q);
1009 for (
int i = 1; i < tempValues.
size(); ++i)
1050 b1 (modulus), b2 (1);
1052 while (! a2.isOne())
1058 temp1 *= multiplier;
1065 temp1 *= multiplier;
1082 return stream << value.
toString (10);
1090 if (base == 2 || base == 8 || base == 16)
1092 auto bits = (base == 2) ? 1 : (base == 8 ? 3 : 4);
1093 static const char hexDigits[] =
"0123456789abcdef";
1097 auto remainder = v.getBitRangeAsInt (0, bits);
1100 if (remainder == 0 && v.isZero())
1106 else if (base == 10)
1115 if (remainder.
isZero() && v.isZero())
1127 s = s.
paddedLeft (
'0', minimumNumCharacters);
1139 if (base == 2 || base == 8 || base == 16)
1141 auto bits = (base == 2) ? 1 : (base == 8 ? 3 : 4);
1145 auto c = t.getAndAdvance();
1148 if (((uint32) digit) < (uint32) base)
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);
1198 for (
int i = 0; i < (int) numInts - 1; ++i)
1201 values[numInts - 1] = 0;
1203 for (
int i = (
int) (numBytes & ~3u); i < (int) numBytes; ++i)
1206 highestBit = (int) numBytes * 8;
1211 void writeLittleEndianBitsInBuffer (
void* buffer, uint32 startBit, uint32 numBits, uint32 value) noexcept
1213 jassert (buffer !=
nullptr);
1214 jassert (numBits > 0 && numBits <= 32);
1215 jassert (numBits == 32 || (value >> numBits) == 0);
1217 uint8* data =
static_cast<uint8*
> (buffer) + startBit / 8;
1219 if (
const uint32 offset = (startBit & 7))
1221 const uint32 bitsInByte = 8 - offset;
1222 const uint8 current = *data;
1224 if (bitsInByte >= numBits)
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);
1246 uint32 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);
1285 class BigIntegerTests :
public UnitTest
1288 BigIntegerTests() : UnitTest (
"BigInteger",
"Maths") {}
1290 static BigInteger getBigRandom (Random& r)
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;)
1312 BigInteger b1 (getBigRandom(r)),
1313 b2 (getBigRandom(r));
1315 BigInteger b3 = b1 + b2;
1316 expect (b3 > b1 && b3 > b2);
1317 expect (b3 - b1 == b2);
1318 expect (b3 - b2 == b1);
1320 BigInteger b4 = b1 * b2;
1321 expect (b4 > b1 && b4 > b2);
1322 expect (b4 / b1 == b2);
1323 expect (b4 / b2 == b1);
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));
1364 static BigIntegerTests bigIntegerTests;