OpenShot Audio Library | OpenShotAudio 0.4.0
Loading...
Searching...
No Matches
juce_BigInteger.cpp
1/*
2 ==============================================================================
3
4 This file is part of the JUCE library.
5 Copyright (c) 2022 - Raw Material Software Limited
6
7 JUCE is an open source library subject to commercial or open-source
8 licensing.
9
10 The code included in this file is provided under the terms of the ISC license
11 http://www.isc.org/downloads/software-support-policy/isc-license. Permission
12 To use, copy, modify, and/or distribute this software for any purpose with or
13 without fee is hereby granted provided that the above copyright notice and
14 this permission notice appear in all copies.
15
16 JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
17 EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
18 DISCLAIMED.
19
20 ==============================================================================
21*/
22
23namespace juce
24{
25
26namespace
27{
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; }
31}
32
33int findHighestSetBit (uint32 n) noexcept
34{
35 jassert (n != 0); // (the built-in functions may not work for n = 0)
36
37 #if JUCE_GCC || JUCE_CLANG
38 return 31 - __builtin_clz (n);
39 #elif JUCE_MSVC
40 unsigned long highest;
41 _BitScanReverse (&highest, n);
42 return (int) highest;
43 #else
44 n |= (n >> 1);
45 n |= (n >> 2);
46 n |= (n >> 4);
47 n |= (n >> 8);
48 n |= (n >> 16);
49 return countNumberOfBits (n >> 1);
50 #endif
51}
52
53//==============================================================================
55 : allocatedSize (numPreallocatedInts)
56{
57 for (int i = 0; i < numPreallocatedInts; ++i)
58 preallocated[i] = 0;
59}
60
61BigInteger::BigInteger (const int32 value)
62 : allocatedSize (numPreallocatedInts),
63 highestBit (31),
64 negative (value < 0)
65{
66 preallocated[0] = (uint32) std::abs (value);
67
68 for (int i = 1; i < numPreallocatedInts; ++i)
69 preallocated[i] = 0;
70
71 highestBit = getHighestBit();
72}
73
74BigInteger::BigInteger (const uint32 value)
75 : allocatedSize (numPreallocatedInts),
76 highestBit (31)
77{
78 preallocated[0] = value;
79
80 for (int i = 1; i < numPreallocatedInts; ++i)
81 preallocated[i] = 0;
82
83 highestBit = getHighestBit();
84}
85
87 : allocatedSize (numPreallocatedInts),
88 highestBit (63),
89 negative (value < 0)
90{
91 if (value < 0)
92 value = -value;
93
94 preallocated[0] = (uint32) value;
95 preallocated[1] = (uint32) (value >> 32);
96
97 for (int i = 2; i < numPreallocatedInts; ++i)
98 preallocated[i] = 0;
99
100 highestBit = getHighestBit();
101}
102
104 : allocatedSize (other.allocatedSize),
105 highestBit (other.getHighestBit()),
106 negative (other.negative)
107{
108 if (allocatedSize > numPreallocatedInts)
109 heapAllocation.malloc (allocatedSize);
110
111 memcpy (getValues(), other.getValues(), sizeof (uint32) * allocatedSize);
112}
113
115 : heapAllocation (std::move (other.heapAllocation)),
116 allocatedSize (other.allocatedSize),
117 highestBit (other.highestBit),
118 negative (other.negative)
119{
120 memcpy (preallocated, other.preallocated, sizeof (preallocated));
121}
122
124{
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;
130 return *this;
131}
132
133void BigInteger::swapWith (BigInteger& other) noexcept
134{
135 for (int i = 0; i < numPreallocatedInts; ++i)
136 std::swap (preallocated[i], other.preallocated[i]);
137
138 heapAllocation.swapWith (other.heapAllocation);
139 std::swap (allocatedSize, other.allocatedSize);
140 std::swap (highestBit, other.highestBit);
141 std::swap (negative, other.negative);
142}
143
145{
146 if (this != &other)
147 {
148 highestBit = other.getHighestBit();
149 auto newAllocatedSize = (size_t) jmax ((size_t) numPreallocatedInts, sizeNeededToHold (highestBit));
150
151 if (newAllocatedSize <= numPreallocatedInts)
152 heapAllocation.free();
153 else if (newAllocatedSize != allocatedSize)
154 heapAllocation.malloc (newAllocatedSize);
155
156 allocatedSize = newAllocatedSize;
157
158 memcpy (getValues(), other.getValues(), sizeof (uint32) * allocatedSize);
159 negative = other.negative;
160 }
161
162 return *this;
163}
164
165BigInteger::~BigInteger() = default;
166
167uint32* BigInteger::getValues() const noexcept
168{
169 jassert (heapAllocation != nullptr || allocatedSize <= numPreallocatedInts);
170
171 return heapAllocation != nullptr ? heapAllocation
172 : const_cast<uint32*> (preallocated);
173}
174
175uint32* BigInteger::ensureSize (const size_t numVals)
176{
177 if (numVals > allocatedSize)
178 {
179 auto oldSize = allocatedSize;
180 allocatedSize = ((numVals + 2) * 3) / 2;
181
182 if (heapAllocation == nullptr)
183 {
184 heapAllocation.calloc (allocatedSize);
185 memcpy (heapAllocation, preallocated, sizeof (uint32) * numPreallocatedInts);
186 }
187 else
188 {
189 heapAllocation.realloc (allocatedSize);
190
191 for (auto* values = getValues(); oldSize < allocatedSize; ++oldSize)
192 values[oldSize] = 0;
193 }
194 }
195
196 return getValues();
197}
198
199//==============================================================================
200bool BigInteger::operator[] (const int bit) const noexcept
201{
203 && ((getValues() [bitToIndex (bit)] & bitToMask (bit)) != 0);
204}
205
207{
208 auto n = (int) (getValues()[0] & 0x7fffffff);
209 return negative ? -n : n;
210}
211
213{
214 auto* values = getValues();
215 auto n = (((int64) (values[1] & 0x7fffffff)) << 32) | values[0];
216 return negative ? -n : n;
217}
218
220{
221 BigInteger r;
222 numBits = jmax (0, jmin (numBits, getHighestBit() + 1 - startBit));
223 auto* destValues = r.ensureSize (sizeNeededToHold (numBits));
224 r.highestBit = numBits;
225
226 for (int i = 0; numBits > 0;)
227 {
228 destValues[i++] = getBitRangeAsInt (startBit, (int) jmin (32, numBits));
229 numBits -= 32;
230 startBit += 32;
231 }
232
233 r.highestBit = r.getHighestBit();
234 return r;
235}
236
237uint32 BigInteger::getBitRangeAsInt (const int startBit, int numBits) const noexcept
238{
239 if (numBits > 32)
240 {
241 jassertfalse; // use getBitRange() if you need more than 32 bits..
242 numBits = 32;
243 }
244
245 numBits = jmin (numBits, highestBit + 1 - startBit);
246
247 if (numBits <= 0)
248 return 0;
249
250 auto pos = bitToIndex (startBit);
251 auto offset = startBit & 31;
252 auto endSpace = 32 - numBits;
253 auto* values = getValues();
254
255 auto n = ((uint32) values [pos]) >> offset;
256
257 if (offset > endSpace)
258 n |= ((uint32) values [pos + 1]) << (32 - offset);
259
260 return n & (((uint32) 0xffffffff) >> endSpace);
261}
262
264{
265 if (numBits > 32)
266 {
267 jassertfalse;
268 numBits = 32;
269 }
270
271 for (int i = 0; i < numBits; ++i)
272 {
273 setBit (startBit + i, (valueToSet & 1) != 0);
274 valueToSet >>= 1;
275 }
276
277 return *this;
278}
279
280//==============================================================================
282{
283 heapAllocation.free();
284 allocatedSize = numPreallocatedInts;
285 highestBit = -1;
286 negative = false;
287
288 for (int i = 0; i < numPreallocatedInts; ++i)
289 preallocated[i] = 0;
290
291 return *this;
292}
293
295{
296 if (bit >= 0)
297 {
298 if (bit > highestBit)
299 {
300 ensureSize (sizeNeededToHold (bit));
301 highestBit = bit;
302 }
303
304 getValues() [bitToIndex (bit)] |= bitToMask (bit);
305 }
306
307 return *this;
308}
309
311{
312 if (shouldBeSet)
313 setBit (bit);
314 else
315 clearBit (bit);
316
317 return *this;
318}
319
321{
322 if (bit >= 0 && bit <= highestBit)
323 {
324 getValues() [bitToIndex (bit)] &= ~bitToMask (bit);
325
326 if (bit == highestBit)
327 highestBit = getHighestBit();
328 }
329
330 return *this;
331}
332
334{
335 while (--numBits >= 0)
337
338 return *this;
339}
340
342{
343 if (bit >= 0)
344 shiftBits (1, bit);
345
347 return *this;
348}
349
350//==============================================================================
352{
353 return getHighestBit() < 0;
354}
355
357{
358 return getHighestBit() == 0 && ! negative;
359}
360
362{
363 return negative && ! isZero();
364}
365
366void BigInteger::setNegative (const bool neg) noexcept
367{
368 negative = neg;
369}
370
372{
373 negative = (! negative) && ! isZero();
374}
375
376#if JUCE_MSVC && ! defined (__INTEL_COMPILER)
377 #pragma intrinsic (_BitScanReverse)
378#endif
379
381{
382 int total = 0;
383 auto* values = getValues();
384
385 for (int i = (int) sizeNeededToHold (highestBit); --i >= 0;)
386 total += countNumberOfBits (values[i]);
387
388 return total;
389}
390
392{
393 auto* values = getValues();
394
395 for (int i = (int) bitToIndex (highestBit); i >= 0; --i)
396 if (uint32 n = values[i])
397 return findHighestSetBit (n) + (i << 5);
398
399 return -1;
400}
401
402int BigInteger::findNextSetBit (int i) const noexcept
403{
404 auto* values = getValues();
405
406 for (; i <= highestBit; ++i)
407 if ((values [bitToIndex (i)] & bitToMask (i)) != 0)
408 return i;
409
410 return -1;
411}
412
413int BigInteger::findNextClearBit (int i) const noexcept
414{
415 auto* values = getValues();
416
417 for (; i <= highestBit; ++i)
418 if ((values [bitToIndex (i)] & bitToMask (i)) == 0)
419 break;
420
421 return i;
422}
423
424//==============================================================================
425BigInteger& BigInteger::operator+= (const BigInteger& other)
426{
427 if (this == &other)
428 return operator+= (BigInteger (other));
429
430 if (other.isNegative())
431 return operator-= (-other);
432
433 if (isNegative())
434 {
435 if (compareAbsolute (other) < 0)
436 {
437 auto temp = *this;
438 temp.negate();
439 *this = other;
440 *this -= temp;
441 }
442 else
443 {
444 negate();
445 *this -= other;
446 negate();
447 }
448 }
449 else
450 {
451 highestBit = jmax (highestBit, other.highestBit) + 1;
452
453 auto numInts = sizeNeededToHold (highestBit);
454 auto* values = ensureSize (numInts);
455 auto* otherValues = other.getValues();
456 int64 remainder = 0;
457
458 for (size_t i = 0; i < numInts; ++i)
459 {
460 remainder += values[i];
461
462 if (i < other.allocatedSize)
463 remainder += otherValues[i];
464
465 values[i] = (uint32) remainder;
466 remainder >>= 32;
467 }
468
469 jassert (remainder == 0);
470 highestBit = getHighestBit();
471 }
472
473 return *this;
474}
475
476BigInteger& BigInteger::operator-= (const BigInteger& other)
477{
478 if (this == &other)
479 {
480 clear();
481 return *this;
482 }
483
484 if (other.isNegative())
485 return operator+= (-other);
486
487 if (isNegative())
488 {
489 negate();
490 *this += other;
491 negate();
492 return *this;
493 }
494
495 if (compareAbsolute (other) < 0)
496 {
497 auto temp = other;
498 swapWith (temp);
499 *this -= temp;
500 negate();
501 return *this;
502 }
503
504 auto numInts = sizeNeededToHold (getHighestBit());
505 auto maxOtherInts = sizeNeededToHold (other.getHighestBit());
506 jassert (numInts >= maxOtherInts);
507 auto* values = getValues();
508 auto* otherValues = other.getValues();
509 int64 amountToSubtract = 0;
510
511 for (size_t i = 0; i < numInts; ++i)
512 {
513 if (i < maxOtherInts)
514 amountToSubtract += (int64) otherValues[i];
515
516 if (values[i] >= amountToSubtract)
517 {
518 values[i] = (uint32) (values[i] - amountToSubtract);
519 amountToSubtract = 0;
520 }
521 else
522 {
523 const int64 n = ((int64) values[i] + (((int64) 1) << 32)) - amountToSubtract;
524 values[i] = (uint32) n;
525 amountToSubtract = 1;
526 }
527 }
528
529 highestBit = getHighestBit();
530 return *this;
531}
532
533BigInteger& BigInteger::operator*= (const BigInteger& other)
534{
535 if (this == &other)
536 return operator*= (BigInteger (other));
537
538 auto n = getHighestBit();
539 auto t = other.getHighestBit();
540
541 auto wasNegative = isNegative();
542 setNegative (false);
543
544 BigInteger total;
545 total.highestBit = n + t + 1;
546 auto* totalValues = total.ensureSize (sizeNeededToHold (total.highestBit) + 1);
547
548 n >>= 5;
549 t >>= 5;
550
551 auto m = other;
552 m.setNegative (false);
553
554 auto* mValues = m.getValues();
555 auto* values = getValues();
556
557 for (int i = 0; i <= t; ++i)
558 {
559 uint32 c = 0;
560
561 for (int j = 0; j <= n; ++j)
562 {
563 auto uv = (uint64) totalValues[i + j] + (uint64) values[j] * (uint64) mValues[i] + (uint64) c;
564 totalValues[i + j] = (uint32) uv;
565 c = static_cast<uint32> (uv >> 32);
566 }
567
568 totalValues[i + n + 1] = c;
569 }
570
571 total.highestBit = total.getHighestBit();
572 total.setNegative (wasNegative ^ other.isNegative());
573 swapWith (total);
574
575 return *this;
576}
577
579{
580 if (this == &divisor)
582
583 jassert (this != &remainder); // (can't handle passing itself in to get the remainder)
584
585 auto divHB = divisor.getHighestBit();
586 auto ourHB = getHighestBit();
587
588 if (divHB < 0 || ourHB < 0)
589 {
590 // division by zero
591 remainder.clear();
592 clear();
593 }
594 else
595 {
596 auto wasNegative = isNegative();
597
599 remainder.setNegative (false);
600 clear();
601
602 BigInteger temp (divisor);
603 temp.setNegative (false);
604
605 auto leftShift = ourHB - divHB;
606 temp <<= leftShift;
607
608 while (leftShift >= 0)
609 {
610 if (remainder.compareAbsolute (temp) >= 0)
611 {
612 remainder -= temp;
614 }
615
616 if (--leftShift >= 0)
617 temp >>= 1;
618 }
619
620 negative = wasNegative ^ divisor.isNegative();
621 remainder.setNegative (wasNegative);
622 }
623}
624
625BigInteger& BigInteger::operator/= (const BigInteger& other)
626{
628 divideBy (other, remainder);
629 return *this;
630}
631
632BigInteger& BigInteger::operator|= (const BigInteger& other)
633{
634 if (this == &other)
635 return *this;
636
637 // this operation doesn't take into account negative values..
638 jassert (isNegative() == other.isNegative());
639
640 if (other.highestBit >= 0)
641 {
642 auto* values = ensureSize (sizeNeededToHold (other.highestBit));
643 auto* otherValues = other.getValues();
644
645 auto n = (int) bitToIndex (other.highestBit) + 1;
646
647 while (--n >= 0)
648 values[n] |= otherValues[n];
649
650 if (other.highestBit > highestBit)
651 highestBit = other.highestBit;
652
653 highestBit = getHighestBit();
654 }
655
656 return *this;
657}
658
659BigInteger& BigInteger::operator&= (const BigInteger& other)
660{
661 if (this == &other)
662 return *this;
663
664 // this operation doesn't take into account negative values..
665 jassert (isNegative() == other.isNegative());
666
667 auto* values = getValues();
668 auto* otherValues = other.getValues();
669
670 auto n = (int) allocatedSize;
671
672 while (n > (int) other.allocatedSize)
673 values[--n] = 0;
674
675 while (--n >= 0)
676 values[n] &= otherValues[n];
677
678 if (other.highestBit < highestBit)
679 highestBit = other.highestBit;
680
681 highestBit = getHighestBit();
682 return *this;
683}
684
685BigInteger& BigInteger::operator^= (const BigInteger& other)
686{
687 if (this == &other)
688 {
689 clear();
690 return *this;
691 }
692
693 // this operation will only work with the absolute values
694 jassert (isNegative() == other.isNegative());
695
696 if (other.highestBit >= 0)
697 {
698 auto* values = ensureSize (sizeNeededToHold (other.highestBit));
699 auto* otherValues = other.getValues();
700
701 auto n = (int) bitToIndex (other.highestBit) + 1;
702
703 while (--n >= 0)
704 values[n] ^= otherValues[n];
705
706 if (other.highestBit > highestBit)
707 highestBit = other.highestBit;
708
709 highestBit = getHighestBit();
710 }
711
712 return *this;
713}
714
715BigInteger& BigInteger::operator%= (const BigInteger& divisor)
716{
717 BigInteger remainder;
718 divideBy (divisor, remainder);
719 swapWith (remainder);
720 return *this;
721}
722
723BigInteger& BigInteger::operator++() { return operator+= (1); }
724BigInteger& BigInteger::operator--() { return operator-= (1); }
725BigInteger BigInteger::operator++ (int) { const auto old (*this); operator+= (1); return old; }
726BigInteger BigInteger::operator-- (int) { const auto old (*this); operator-= (1); return old; }
727
728BigInteger BigInteger::operator-() const { auto b (*this); b.negate(); return b; }
729BigInteger BigInteger::operator+ (const BigInteger& other) const { auto b (*this); return b += other; }
730BigInteger BigInteger::operator- (const BigInteger& other) const { auto b (*this); return b -= other; }
731BigInteger BigInteger::operator* (const BigInteger& other) const { auto b (*this); return b *= other; }
732BigInteger BigInteger::operator/ (const BigInteger& other) const { auto b (*this); return b /= other; }
733BigInteger BigInteger::operator| (const BigInteger& other) const { auto b (*this); return b |= other; }
734BigInteger BigInteger::operator& (const BigInteger& other) const { auto b (*this); return b &= other; }
735BigInteger BigInteger::operator^ (const BigInteger& other) const { auto b (*this); return b ^= other; }
736BigInteger BigInteger::operator% (const BigInteger& other) const { auto b (*this); return b %= other; }
737BigInteger BigInteger::operator<< (const int numBits) const { auto b (*this); return b <<= numBits; }
738BigInteger BigInteger::operator>> (const int numBits) const { auto b (*this); return b >>= numBits; }
739BigInteger& BigInteger::operator<<= (const int numBits) { shiftBits (numBits, 0); return *this; }
740BigInteger& BigInteger::operator>>= (const int numBits) { shiftBits (-numBits, 0); return *this; }
741
742//==============================================================================
743int BigInteger::compare (const BigInteger& other) const noexcept
744{
745 auto isNeg = isNegative();
746
747 if (isNeg == other.isNegative())
748 {
749 auto absComp = compareAbsolute (other);
750 return isNeg ? -absComp : absComp;
751 }
752
753 return isNeg ? -1 : 1;
754}
755
756int BigInteger::compareAbsolute (const BigInteger& other) const noexcept
757{
758 auto h1 = getHighestBit();
759 auto h2 = other.getHighestBit();
760
761 if (h1 > h2) return 1;
762 if (h1 < h2) return -1;
763
764 auto* values = getValues();
765 auto* otherValues = other.getValues();
766
767 for (int i = (int) bitToIndex (h1); i >= 0; --i)
768 if (values[i] != otherValues[i])
769 return values[i] > otherValues[i] ? 1 : -1;
770
771 return 0;
772}
773
774bool BigInteger::operator== (const BigInteger& other) const noexcept { return compare (other) == 0; }
775bool BigInteger::operator!= (const BigInteger& other) const noexcept { return compare (other) != 0; }
776bool BigInteger::operator< (const BigInteger& other) const noexcept { return compare (other) < 0; }
777bool BigInteger::operator<= (const BigInteger& other) const noexcept { return compare (other) <= 0; }
778bool BigInteger::operator> (const BigInteger& other) const noexcept { return compare (other) > 0; }
779bool BigInteger::operator>= (const BigInteger& other) const noexcept { return compare (other) >= 0; }
780
781//==============================================================================
782void BigInteger::shiftLeft (int bits, const int startBit)
783{
784 if (startBit > 0)
785 {
786 for (int i = highestBit; i >= startBit; --i)
787 setBit (i + bits, (*this) [i]);
788
789 while (--bits >= 0)
790 clearBit (bits + startBit);
791 }
792 else
793 {
794 auto* values = ensureSize (sizeNeededToHold (highestBit + bits));
795 auto wordsToMove = bitToIndex (bits);
796 auto numOriginalInts = bitToIndex (highestBit);
797 highestBit += bits;
798
799 if (wordsToMove > 0)
800 {
801 for (int i = (int) numOriginalInts; i >= 0; --i)
802 values[(size_t) i + wordsToMove] = values[i];
803
804 for (size_t j = 0; j < wordsToMove; ++j)
805 values[j] = 0;
806
807 bits &= 31;
808 }
809
810 if (bits != 0)
811 {
812 auto invBits = 32 - bits;
813
814 for (size_t i = bitToIndex (highestBit); i > wordsToMove; --i)
815 values[i] = (values[i] << bits) | (values[i - 1] >> invBits);
816
817 values[wordsToMove] = values[wordsToMove] << bits;
818 }
819
820 highestBit = getHighestBit();
821 }
822}
823
824void BigInteger::shiftRight (int bits, const int startBit)
825{
826 if (startBit > 0)
827 {
828 for (int i = startBit; i <= highestBit; ++i)
829 setBit (i, (*this) [i + bits]);
830
831 highestBit = getHighestBit();
832 }
833 else
834 {
835 if (bits > highestBit)
836 {
837 clear();
838 }
839 else
840 {
841 auto wordsToMove = bitToIndex (bits);
842 auto top = 1 + bitToIndex (highestBit) - wordsToMove;
843 highestBit -= bits;
844 auto* values = getValues();
845
846 if (wordsToMove > 0)
847 {
848 for (size_t i = 0; i < top; ++i)
849 values[i] = values[i + wordsToMove];
850
851 for (size_t i = 0; i < wordsToMove; ++i)
852 values[top + i] = 0;
853
854 bits &= 31;
855 }
856
857 if (bits != 0)
858 {
859 auto invBits = 32 - bits;
860 --top;
861
862 for (size_t i = 0; i < top; ++i)
863 values[i] = (values[i] >> bits) | (values[i + 1] << invBits);
864
865 values[top] = (values[top] >> bits);
866 }
867
868 highestBit = getHighestBit();
869 }
870 }
871}
872
874{
875 if (highestBit >= 0)
876 {
877 if (bits < 0)
878 shiftRight (-bits, startBit);
879 else if (bits > 0)
880 shiftLeft (bits, startBit);
881 }
882
883 return *this;
884}
885
886//==============================================================================
887static BigInteger simpleGCD (BigInteger* m, BigInteger* n)
888{
889 while (! m->isZero())
890 {
891 if (n->compareAbsolute (*m) > 0)
892 std::swap (m, n);
893
894 *m -= *n;
895 }
896
897 return *n;
898}
899
901{
902 auto m = *this;
903
904 while (! n.isZero())
905 {
906 if (std::abs (m.getHighestBit() - n.getHighestBit()) <= 16)
907 return simpleGCD (&m, &n);
908
910 m.divideBy (n, temp2);
911
912 m.swapWith (n);
913 n.swapWith (temp2);
914 }
915
916 return m;
917}
918
920{
921 *this %= modulus;
922 auto exp = exponent;
923 exp %= modulus;
924
925 if (modulus.getHighestBit() <= 32 || modulus % 2 == 0)
926 {
927 auto a = *this;
928 auto n = exp.getHighestBit();
929
930 for (int i = n; --i >= 0;)
931 {
932 *this *= *this;
933
934 if (exp[i])
935 *this *= a;
936
937 if (compareAbsolute (modulus) >= 0)
938 *this %= modulus;
939 }
940 }
941 else
942 {
943 auto Rfactor = modulus.getHighestBit() + 1;
944 BigInteger R (1);
945 R.shiftLeft (Rfactor, 0);
946
947 BigInteger R1, m1, g;
949
950 if (! g.isOne())
951 {
952 BigInteger a (*this);
953
954 for (int i = exp.getHighestBit(); --i >= 0;)
955 {
956 *this *= *this;
957
958 if (exp[i])
959 *this *= a;
960
961 if (compareAbsolute (modulus) >= 0)
962 *this %= modulus;
963 }
964 }
965 else
966 {
967 auto am = (*this * R) % modulus;
968 auto xm = am;
969 auto um = R % modulus;
970
971 for (int i = exp.getHighestBit(); --i >= 0;)
972 {
973 xm.montgomeryMultiplication (xm, modulus, m1, Rfactor);
974
975 if (exp[i])
976 xm.montgomeryMultiplication (am, modulus, m1, Rfactor);
977 }
978
979 xm.montgomeryMultiplication (1, modulus, m1, Rfactor);
980 swapWith (xm);
981 }
982 }
983}
984
986 const BigInteger& modulusp, const int k)
987{
988 *this *= other;
989 auto t = *this;
990
991 setRange (k, highestBit - k + 1, false);
992 *this *= modulusp;
993
994 setRange (k, highestBit - k + 1, false);
995 *this *= modulus;
996 *this += t;
997 shiftRight (k, 0);
998
999 if (compare (modulus) >= 0)
1000 *this -= modulus;
1001 else if (isNegative())
1002 *this += modulus;
1003}
1004
1006 BigInteger& x, BigInteger& y)
1007{
1008 BigInteger p (a), q (b), gcd (1);
1010
1011 while (! q.isZero())
1012 {
1013 tempValues.add (p / q);
1014 gcd = q;
1015 q = p % q;
1016 p = gcd;
1017 }
1018
1019 x.clear();
1020 y = 1;
1021
1022 for (int i = 1; i < tempValues.size(); ++i)
1023 {
1024 auto& v = tempValues.getReference (tempValues.size() - i - 1);
1025
1026 if ((i & 1) != 0)
1027 x += y * v;
1028 else
1029 y += x * v;
1030 }
1031
1032 if (gcd.compareAbsolute (y * b - x * a) != 0)
1033 {
1034 x.negate();
1035 x.swapWith (y);
1036 x.negate();
1037 }
1038
1039 swapWith (gcd);
1040}
1041
1043{
1044 if (modulus.isOne() || modulus.isNegative())
1045 {
1046 clear();
1047 return;
1048 }
1049
1050 if (isNegative() || compareAbsolute (modulus) >= 0)
1051 *this %= modulus;
1052
1053 if (isOne())
1054 return;
1055
1057 {
1058 clear(); // not invertible!
1059 return;
1060 }
1061
1062 BigInteger a1 (modulus), a2 (*this),
1063 b1 (modulus), b2 (1);
1064
1065 while (! a2.isOne())
1066 {
1068 multiplier.divideBy (a2, temp1);
1069
1070 temp1 = a2;
1071 temp1 *= multiplier;
1072 auto temp2 = a1;
1073 temp2 -= temp1;
1074 a1 = a2;
1075 a2 = temp2;
1076
1077 temp1 = b2;
1078 temp1 *= multiplier;
1079 temp2 = b1;
1080 temp2 -= temp1;
1081 b1 = b2;
1082 b2 = temp2;
1083 }
1084
1085 while (b2.isNegative())
1086 b2 += modulus;
1087
1088 b2 %= modulus;
1089 swapWith (b2);
1090}
1091
1092//==============================================================================
1093OutputStream& JUCE_CALLTYPE operator<< (OutputStream& stream, const BigInteger& value)
1094{
1095 return stream << value.toString (10);
1096}
1097
1098String BigInteger::toString (const int base, const int minimumNumCharacters) const
1099{
1100 String s;
1101 auto v = *this;
1102
1103 if (base == 2 || base == 8 || base == 16)
1104 {
1105 auto bits = (base == 2) ? 1 : (base == 8 ? 3 : 4);
1106 static const char hexDigits[] = "0123456789abcdef";
1107
1108 for (;;)
1109 {
1110 auto remainder = v.getBitRangeAsInt (0, bits);
1111 v >>= bits;
1112
1113 if (remainder == 0 && v.isZero())
1114 break;
1115
1116 s = String::charToString ((juce_wchar) (uint8) hexDigits [remainder]) + s;
1117 }
1118 }
1119 else if (base == 10)
1120 {
1121 const BigInteger ten (10);
1123
1124 for (;;)
1125 {
1126 v.divideBy (ten, remainder);
1127
1128 if (remainder.isZero() && v.isZero())
1129 break;
1130
1131 s = String (remainder.getBitRangeAsInt (0, 8)) + s;
1132 }
1133 }
1134 else
1135 {
1136 jassertfalse; // can't do the specified base!
1137 return {};
1138 }
1139
1140 s = s.paddedLeft ('0', minimumNumCharacters);
1141
1142 return isNegative() ? "-" + s : s;
1143}
1144
1145void BigInteger::parseString (StringRef text, const int base)
1146{
1147 clear();
1148 auto t = text.text.findEndOfWhitespace();
1149
1150 setNegative (*t == (juce_wchar) '-');
1151
1152 if (base == 2 || base == 8 || base == 16)
1153 {
1154 auto bits = (base == 2) ? 1 : (base == 8 ? 3 : 4);
1155
1156 for (;;)
1157 {
1158 auto c = t.getAndAdvance();
1160
1161 if (((uint32) digit) < (uint32) base)
1162 {
1163 *this <<= bits;
1164 *this += digit;
1165 }
1166 else if (c == 0)
1167 {
1168 break;
1169 }
1170 }
1171 }
1172 else if (base == 10)
1173 {
1174 const BigInteger ten ((uint32) 10);
1175
1176 for (;;)
1177 {
1178 auto c = t.getAndAdvance();
1179
1180 if (c >= '0' && c <= '9')
1181 {
1182 *this *= ten;
1183 *this += (int) (c - '0');
1184 }
1185 else if (c == 0)
1186 {
1187 break;
1188 }
1189 }
1190 }
1191}
1192
1194{
1195 auto numBytes = (getHighestBit() + 8) >> 3;
1196 MemoryBlock mb ((size_t) numBytes);
1197 auto* values = getValues();
1198
1199 for (int i = 0; i < numBytes; ++i)
1200 mb[i] = (char) ((values[i / 4] >> ((i & 3) * 8)) & 0xff);
1201
1202 return mb;
1203}
1204
1206{
1207 auto numBytes = data.getSize();
1208 auto numInts = 1 + (numBytes / sizeof (uint32));
1209 auto* values = ensureSize (numInts);
1210
1211 for (int i = 0; i < (int) numInts - 1; ++i)
1212 values[i] = (uint32) ByteOrder::littleEndianInt (addBytesToPointer (data.getData(), (size_t) i * sizeof (uint32)));
1213
1214 values[numInts - 1] = 0;
1215
1216 for (int i = (int) (numBytes & ~3u); i < (int) numBytes; ++i)
1217 this->setBitRangeAsInt (i << 3, 8, (uint32) data [i]);
1218
1219 highestBit = (int) numBytes * 8;
1220 highestBit = getHighestBit();
1221}
1222
1223//==============================================================================
1224void writeLittleEndianBitsInBuffer (void* buffer, uint32 startBit, uint32 numBits, uint32 value) noexcept
1225{
1226 jassert (buffer != nullptr);
1227 jassert (numBits > 0 && numBits <= 32);
1228 jassert (numBits == 32 || (value >> numBits) == 0);
1229
1230 uint8* data = static_cast<uint8*> (buffer) + startBit / 8;
1231
1232 if (const uint32 offset = (startBit & 7))
1233 {
1234 const uint32 bitsInByte = 8 - offset;
1235 const uint8 current = *data;
1236
1237 if (bitsInByte >= numBits)
1238 {
1239 *data = (uint8) ((current & ~(((1u << numBits) - 1u) << offset)) | (value << offset));
1240 return;
1241 }
1242
1243 *data++ = current ^ (uint8) (((value << offset) ^ current) & (((1u << bitsInByte) - 1u) << offset));
1244 numBits -= bitsInByte;
1245 value >>= bitsInByte;
1246 }
1247
1248 while (numBits >= 8)
1249 {
1250 *data++ = (uint8) value;
1251 value >>= 8;
1252 numBits -= 8;
1253 }
1254
1255 if (numBits > 0)
1256 *data = (uint8) ((*data & (uint32) (0xff << numBits)) | value);
1257}
1258
1259uint32 readLittleEndianBitsInBuffer (const void* buffer, uint32 startBit, uint32 numBits) noexcept
1260{
1261 jassert (buffer != nullptr);
1262 jassert (numBits > 0 && numBits <= 32);
1263
1264 uint32 result = 0;
1265 uint32 bitsRead = 0;
1266 const uint8* data = static_cast<const uint8*> (buffer) + startBit / 8;
1267
1268 if (const uint32 offset = (startBit & 7))
1269 {
1270 const uint32 bitsInByte = 8 - offset;
1271 result = (uint32) (*data >> offset);
1272
1273 if (bitsInByte >= numBits)
1274 return result & ((1u << numBits) - 1u);
1275
1276 numBits -= bitsInByte;
1277 bitsRead += bitsInByte;
1278 ++data;
1279 }
1280
1281 while (numBits >= 8)
1282 {
1283 result |= (((uint32) *data++) << bitsRead);
1284 bitsRead += 8;
1285 numBits -= 8;
1286 }
1287
1288 if (numBits > 0)
1289 result |= ((*data & ((1u << numBits) - 1u)) << bitsRead);
1290
1291 return result;
1292}
1293
1294
1295//==============================================================================
1296//==============================================================================
1297#if JUCE_UNIT_TESTS
1298
1299class BigIntegerTests final : public UnitTest
1300{
1301public:
1302 BigIntegerTests()
1303 : UnitTest ("BigInteger", UnitTestCategories::maths)
1304 {}
1305
1306 static BigInteger getBigRandom (Random& r)
1307 {
1308 BigInteger b;
1309
1310 while (b < 2)
1311 r.fillBitsRandomly (b, 0, r.nextInt (150) + 1);
1312
1313 return b;
1314 }
1315
1316 void runTest() override
1317 {
1318 {
1319 beginTest ("BigInteger");
1320
1321 Random r = getRandom();
1322
1323 expect (BigInteger().isZero());
1324 expect (BigInteger (1).isOne());
1325
1326 for (int j = 10000; --j >= 0;)
1327 {
1328 BigInteger b1 (getBigRandom (r)),
1329 b2 (getBigRandom (r));
1330
1331 BigInteger b3 = b1 + b2;
1332 expect (b3 > b1 && b3 > b2);
1333 expect (b3 - b1 == b2);
1334 expect (b3 - b2 == b1);
1335
1336 BigInteger b4 = b1 * b2;
1337 expect (b4 > b1 && b4 > b2);
1338 expect (b4 / b1 == b2);
1339 expect (b4 / b2 == b1);
1340 expect (((b4 << 1) >> 1) == b4);
1341 expect (((b4 << 10) >> 10) == b4);
1342 expect (((b4 << 100) >> 100) == b4);
1343
1344 // TODO: should add tests for other ops (although they also get pretty well tested in the RSA unit test)
1345
1346 BigInteger b5;
1347 b5.loadFromMemoryBlock (b3.toMemoryBlock());
1348 expect (b3 == b5);
1349 }
1350 }
1351
1352 {
1353 beginTest ("Bit setting");
1354
1355 Random r = getRandom();
1356 static uint8 test[2048];
1357
1358 for (int j = 100000; --j >= 0;)
1359 {
1360 uint32 offset = static_cast<uint32> (r.nextInt (200) + 10);
1361 uint32 num = static_cast<uint32> (r.nextInt (32) + 1);
1362 uint32 value = static_cast<uint32> (r.nextInt());
1363
1364 if (num < 32)
1365 value &= ((1u << num) - 1);
1366
1367 auto old1 = readLittleEndianBitsInBuffer (test, offset - 6, 6);
1368 auto old2 = readLittleEndianBitsInBuffer (test, offset + num, 6);
1369 writeLittleEndianBitsInBuffer (test, offset, num, value);
1370 auto result = readLittleEndianBitsInBuffer (test, offset, num);
1371
1372 expect (result == value);
1373 expect (old1 == readLittleEndianBitsInBuffer (test, offset - 6, 6));
1374 expect (old2 == readLittleEndianBitsInBuffer (test, offset + num, 6));
1375 }
1376 }
1377 }
1378};
1379
1380static BigIntegerTests bigIntegerTests;
1381
1382#endif
1383
1384} // namespace juce
BigInteger & clear() noexcept
MemoryBlock toMemoryBlock() const
bool isOne() const 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 & setRange(int startBit, int numBits, bool shouldBeSet)
BigInteger findGreatestCommonDivisor(BigInteger other) const
void extendedEuclidean(const BigInteger &a, const BigInteger &b, BigInteger &xOut, BigInteger &yOut)
int getHighestBit() const noexcept
void divideBy(const BigInteger &divisor, BigInteger &remainder)
String toString(int base, int minimumNumCharacters=1) const
BigInteger & shiftBits(int howManyBitsLeft, int startBit)
int findNextClearBit(int startIndex) const noexcept
int compare(const BigInteger &other) const noexcept
BigInteger & insertBit(int bitNumber, bool shouldBeSet)
BigInteger & setBitRangeAsInt(int startBit, int numBits, uint32 valueToSet)
BigInteger & clearBit(int bitNumber) noexcept
void negate() noexcept
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
BigInteger & setBit(int bitNumber)
int toInteger() const noexcept
void inverseModulo(const BigInteger &modulus)
static 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 free() noexcept
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)