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());
599 if (
remainder.compareAbsolute (temp) >= 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);
894 return simpleGCD (&m, &n);
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);
1092 auto bits = (
base == 2) ? 1 : (
base == 8 ? 3 : 4);
1093 static const char hexDigits[] =
"0123456789abcdef";
1097 auto remainder = v.getBitRangeAsInt (0, bits);
1106 else if (
base == 10)
1135 auto t = text.
text.findEndOfWhitespace();
1141 auto bits = (
base == 2) ? 1 : (
base == 8 ? 3 : 4);
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 & (uint32) (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 = (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);
1286class BigIntegerTests :
public UnitTest
1290 : UnitTest (
"BigInteger", UnitTestCategories::maths)
1298 r.fillBitsRandomly (
b, 0, r.nextInt (150) + 1);
1303 void runTest()
override
1306 beginTest (
"BigInteger");
1308 Random r = getRandom();
1310 expect (BigInteger().isZero());
1311 expect (BigInteger(1).isOne());
1313 for (
int j = 10000; --
j >= 0;)
1327 expect (((
b4 << 1) >> 1) ==
b4);
1328 expect (((
b4 << 10) >> 10) ==
b4);
1329 expect (((
b4 << 100) >> 100) ==
b4);
1334 b5.loadFromMemoryBlock (
b3.toMemoryBlock());
1340 beginTest (
"Bit setting");
1342 Random r = getRandom();
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));
1367static BigIntegerTests bigIntegerTests;
void swapWith(OtherArrayType &otherArray) noexcept
int size() const noexcept
void add(const ElementType &newElement)
ElementType & getReference(int index) noexcept
MemoryBlock toMemoryBlock() const
bool isOne() const noexcept
void clearBit(int bitNumber) noexcept
BigInteger getBitRange(int startBit, int numBits) const
void parseString(StringRef text, int base)
int64 toInt64() const noexcept
void exponentModulo(const BigInteger &exponent, const BigInteger &modulus)
void setNegative(bool shouldBeNegative) noexcept
uint32 getBitRangeAsInt(int startBit, int numBits) const noexcept
BigInteger findGreatestCommonDivisor(BigInteger other) const
void extendedEuclidean(const BigInteger &a, const BigInteger &b, BigInteger &xOut, BigInteger &yOut)
void setRange(int startBit, int numBits, bool shouldBeSet)
void shiftBits(int howManyBitsLeft, int startBit)
int getHighestBit() const noexcept
void divideBy(const BigInteger &divisor, BigInteger &remainder)
String toString(int base, int minimumNumCharacters=1) const
int findNextClearBit(int startIndex) const noexcept
int compare(const BigInteger &other) const noexcept
void setBit(int bitNumber)
void setBitRangeAsInt(int startBit, int numBits, uint32 valueToSet)
int findNextSetBit(int startIndex) const noexcept
void loadFromMemoryBlock(const MemoryBlock &data)
bool isZero() const noexcept
int countNumberOfSetBits() const noexcept
void swapWith(BigInteger &) noexcept
void montgomeryMultiplication(const BigInteger &other, const BigInteger &modulus, const BigInteger &modulusp, int k)
bool isNegative() const noexcept
bool operator[](int bit) const noexcept
int compareAbsolute(const BigInteger &other) const noexcept
BigInteger & operator=(BigInteger &&) noexcept
void insertBit(int bitNumber, bool shouldBeSet)
int toInteger() const noexcept
void inverseModulo(const BigInteger &modulus)
static JUCE_CONSTEXPR uint32 littleEndianInt(const void *bytes) noexcept
static int getHexDigitValue(juce_wchar digit) noexcept
void malloc(SizeType newNumElements, size_t elementSize=sizeof(ElementType))
void realloc(SizeType newNumElements, size_t elementSize=sizeof(ElementType))
void calloc(SizeType newNumElements, const size_t elementSize=sizeof(ElementType))
void * getData() noexcept
size_t getSize() const noexcept
String::CharPointerType text
String paddedLeft(juce_wchar padCharacter, int minimumLength) const
static String charToString(juce_wchar character)