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),
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)
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);
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;
534 total.highestBit = n + t + 1;
535 auto* totalValues = total.ensureSize (sizeNeededToHold (total.highestBit) + 1);
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;
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();
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;
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;
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;
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; }
739 return isNeg ? -absComp : absComp;
742 return isNeg ? -1 : 1;
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);
1135 auto t = text.
text.findEndOfWhitespace();
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 & (uint32) (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 = (uint32) (*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);
1286 class BigIntegerTests :
public UnitTest 1290 :
UnitTest (
"BigInteger", UnitTestCategories::maths)
1303 void runTest()
override 1306 beginTest (
"BigInteger");
1313 for (
int j = 10000; --j >= 0;)
1316 b2 (getBigRandom(r));
1319 expect (b3 > b1 && b3 > b2);
1320 expect (b3 - b1 == b2);
1321 expect (b3 - b2 == b1);
1324 expect (b4 > b1 && b4 > b2);
1325 expect (b4 / b1 == b2);
1326 expect (b4 / b2 == b1);
1327 expect (((b4 << 1) >> 1) == b4);
1328 expect (((b4 << 10) >> 10) == b4);
1329 expect (((b4 << 100) >> 100) == b4);
1340 beginTest (
"Bit setting");
1343 static uint8 test[2048];
1345 for (
int j = 100000; --j >= 0;)
1347 uint32 offset =
static_cast<uint32
> (r.
nextInt (200) + 10);
1348 uint32 num =
static_cast<uint32
> (r.
nextInt (32) + 1);
1349 uint32 value =
static_cast<uint32
> (r.
nextInt());
1352 value &= ((1u << num) - 1);
1354 auto old1 = readLittleEndianBitsInBuffer (test, offset - 6, 6);
1355 auto old2 = readLittleEndianBitsInBuffer (test, offset + num, 6);
1356 writeLittleEndianBitsInBuffer (test, offset, num, value);
1357 auto result = readLittleEndianBitsInBuffer (test, offset, num);
1359 expect (result == value);
1360 expect (old1 == readLittleEndianBitsInBuffer (test, offset - 6, 6));
1361 expect (old2 == readLittleEndianBitsInBuffer (test, offset + num, 6));
1367 static BigIntegerTests bigIntegerTests;
size_t getSize() const noexcept
void montgomeryMultiplication(const BigInteger &other, const BigInteger &modulus, const BigInteger &modulusp, int k)
void malloc(SizeType newNumElements, size_t elementSize=sizeof(ElementType))
void swapWith(BigInteger &) noexcept
BigInteger & operator=(BigInteger &&) noexcept
void add(const ElementType &newElement)
void realloc(SizeType newNumElements, size_t elementSize=sizeof(ElementType))
void divideBy(const BigInteger &divisor, BigInteger &remainder)
void parseString(StringRef text, int base)
bool operator[](int bit) const noexcept
void calloc(SizeType newNumElements, const size_t elementSize=sizeof(ElementType))
BigInteger getBitRange(int startBit, int numBits) const
BigInteger findGreatestCommonDivisor(BigInteger other) const
void * getData() noexcept
void exponentModulo(const BigInteger &exponent, const BigInteger &modulus)
bool isOne() const noexcept
uint32 getBitRangeAsInt(int startBit, int numBits) const noexcept
int findNextClearBit(int startIndex) const noexcept
int compareAbsolute(const BigInteger &other) const noexcept
bool isNegative() const noexcept
static int getHexDigitValue(juce_wchar digit) noexcept
static JUCE_CONSTEXPR uint32 littleEndianInt(const void *bytes) noexcept
void fillBitsRandomly(void *bufferToFill, size_t sizeInBytes)
void clearBit(int bitNumber) noexcept
void extendedEuclidean(const BigInteger &a, const BigInteger &b, BigInteger &xOut, BigInteger &yOut)
int getHighestBit() const noexcept
String paddedLeft(juce_wchar padCharacter, int minimumLength) const
int size() const noexcept
bool isZero() const noexcept
void swapWith(HeapBlock< ElementType, otherBlockThrows > &other) noexcept
void inverseModulo(const BigInteger &modulus)
String toString(int base, int minimumNumCharacters=1) const
String::CharPointerType text
int toInteger() const noexcept
void shiftBits(int howManyBitsLeft, int startBit)
ElementType & getReference(int index) noexcept
static String charToString(juce_wchar character)
void insertBit(int bitNumber, bool shouldBeSet)
void setNegative(bool shouldBeNegative) noexcept
int countNumberOfSetBits() const noexcept
int findNextSetBit(int startIndex) const noexcept
int compare(const BigInteger &other) const noexcept
void setBit(int bitNumber)
void loadFromMemoryBlock(const MemoryBlock &data)
MemoryBlock toMemoryBlock() const
void setBitRangeAsInt(int startBit, int numBits, uint32 valueToSet)
int64 toInt64() const noexcept
void setRange(int startBit, int numBits, bool shouldBeSet)