OpenShot Library | libopenshot-audio  0.2.0
juce_BigInteger.cpp
1 /*
2  ==============================================================================
3 
4  This file is part of the JUCE library.
5  Copyright (c) 2017 - ROLI Ltd.
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 
23 namespace juce
24 {
25 
26 namespace
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 
33 int 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 
61 BigInteger::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 
74 BigInteger::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 
134 {
135 }
136 
137 void BigInteger::swapWith (BigInteger& other) noexcept
138 {
139  for (int i = 0; i < numPreallocatedInts; ++i)
140  std::swap (preallocated[i], other.preallocated[i]);
141 
142  heapAllocation.swapWith (other.heapAllocation);
143  std::swap (allocatedSize, other.allocatedSize);
144  std::swap (highestBit, other.highestBit);
145  std::swap (negative, other.negative);
146 }
147 
149 {
150  if (this != &other)
151  {
152  highestBit = other.getHighestBit();
153  auto newAllocatedSize = (size_t) jmax ((size_t) numPreallocatedInts, sizeNeededToHold (highestBit));
154 
155  if (newAllocatedSize <= numPreallocatedInts)
156  heapAllocation.free();
157  else if (newAllocatedSize != allocatedSize)
158  heapAllocation.malloc (newAllocatedSize);
159 
160  allocatedSize = newAllocatedSize;
161 
162  memcpy (getValues(), other.getValues(), sizeof (uint32) * allocatedSize);
163  negative = other.negative;
164  }
165 
166  return *this;
167 }
168 
169 uint32* BigInteger::getValues() const noexcept
170 {
171  jassert (heapAllocation != nullptr || allocatedSize <= numPreallocatedInts);
172 
173  return heapAllocation != nullptr ? heapAllocation
174  : const_cast<uint32*> (preallocated);
175 }
176 
177 uint32* BigInteger::ensureSize (const size_t numVals)
178 {
179  if (numVals > allocatedSize)
180  {
181  auto oldSize = allocatedSize;
182  allocatedSize = ((numVals + 2) * 3) / 2;
183 
184  if (heapAllocation == nullptr)
185  {
186  heapAllocation.calloc (allocatedSize);
187  memcpy (heapAllocation, preallocated, sizeof (uint32) * numPreallocatedInts);
188  }
189  else
190  {
191  heapAllocation.realloc (allocatedSize);
192 
193  for (auto* values = getValues(); oldSize < allocatedSize; ++oldSize)
194  values[oldSize] = 0;
195  }
196  }
197 
198  return getValues();
199 }
200 
201 //==============================================================================
202 bool BigInteger::operator[] (const int bit) const noexcept
203 {
204  return bit <= highestBit && bit >= 0
205  && ((getValues() [bitToIndex (bit)] & bitToMask (bit)) != 0);
206 }
207 
208 int BigInteger::toInteger() const noexcept
209 {
210  auto n = (int) (getValues()[0] & 0x7fffffff);
211  return negative ? -n : n;
212 }
213 
214 int64 BigInteger::toInt64() const noexcept
215 {
216  auto* values = getValues();
217  auto n = (((int64) (values[1] & 0x7fffffff)) << 32) | values[0];
218  return negative ? -n : n;
219 }
220 
221 BigInteger BigInteger::getBitRange (int startBit, int numBits) const
222 {
223  BigInteger r;
224  numBits = jmax (0, jmin (numBits, getHighestBit() + 1 - startBit));
225  auto* destValues = r.ensureSize (sizeNeededToHold (numBits));
226  r.highestBit = numBits;
227 
228  for (int i = 0; numBits > 0;)
229  {
230  destValues[i++] = getBitRangeAsInt (startBit, (int) jmin (32, numBits));
231  numBits -= 32;
232  startBit += 32;
233  }
234 
235  r.highestBit = r.getHighestBit();
236  return r;
237 }
238 
239 uint32 BigInteger::getBitRangeAsInt (const int startBit, int numBits) const noexcept
240 {
241  if (numBits > 32)
242  {
243  jassertfalse; // use getBitRange() if you need more than 32 bits..
244  numBits = 32;
245  }
246 
247  numBits = jmin (numBits, highestBit + 1 - startBit);
248 
249  if (numBits <= 0)
250  return 0;
251 
252  auto pos = bitToIndex (startBit);
253  auto offset = startBit & 31;
254  auto endSpace = 32 - numBits;
255  auto* values = getValues();
256 
257  auto n = ((uint32) values [pos]) >> offset;
258 
259  if (offset > endSpace)
260  n |= ((uint32) values [pos + 1]) << (32 - offset);
261 
262  return n & (((uint32) 0xffffffff) >> endSpace);
263 }
264 
265 void BigInteger::setBitRangeAsInt (const int startBit, int numBits, uint32 valueToSet)
266 {
267  if (numBits > 32)
268  {
269  jassertfalse;
270  numBits = 32;
271  }
272 
273  for (int i = 0; i < numBits; ++i)
274  {
275  setBit (startBit + i, (valueToSet & 1) != 0);
276  valueToSet >>= 1;
277  }
278 }
279 
280 //==============================================================================
281 void BigInteger::clear() noexcept
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 
292 void BigInteger::setBit (const int bit)
293 {
294  if (bit >= 0)
295  {
296  if (bit > highestBit)
297  {
298  ensureSize (sizeNeededToHold (bit));
299  highestBit = bit;
300  }
301 
302  getValues() [bitToIndex (bit)] |= bitToMask (bit);
303  }
304 }
305 
306 void BigInteger::setBit (const int bit, const bool shouldBeSet)
307 {
308  if (shouldBeSet)
309  setBit (bit);
310  else
311  clearBit (bit);
312 }
313 
314 void BigInteger::clearBit (const int bit) noexcept
315 {
316  if (bit >= 0 && bit <= highestBit)
317  {
318  getValues() [bitToIndex (bit)] &= ~bitToMask (bit);
319 
320  if (bit == highestBit)
321  highestBit = getHighestBit();
322  }
323 }
324 
325 void BigInteger::setRange (int startBit, int numBits, const bool shouldBeSet)
326 {
327  while (--numBits >= 0)
328  setBit (startBit++, shouldBeSet);
329 }
330 
331 void BigInteger::insertBit (const int bit, const bool shouldBeSet)
332 {
333  if (bit >= 0)
334  shiftBits (1, bit);
335 
336  setBit (bit, shouldBeSet);
337 }
338 
339 //==============================================================================
340 bool BigInteger::isZero() const noexcept
341 {
342  return getHighestBit() < 0;
343 }
344 
345 bool BigInteger::isOne() const noexcept
346 {
347  return getHighestBit() == 0 && ! negative;
348 }
349 
350 bool BigInteger::isNegative() const noexcept
351 {
352  return negative && ! isZero();
353 }
354 
355 void BigInteger::setNegative (const bool neg) noexcept
356 {
357  negative = neg;
358 }
359 
360 void BigInteger::negate() noexcept
361 {
362  negative = (! negative) && ! isZero();
363 }
364 
365 #if JUCE_MSVC && ! defined (__INTEL_COMPILER)
366  #pragma intrinsic (_BitScanReverse)
367 #endif
368 
370 {
371  int total = 0;
372  auto* values = getValues();
373 
374  for (int i = (int) sizeNeededToHold (highestBit); --i >= 0;)
375  total += countNumberOfBits (values[i]);
376 
377  return total;
378 }
379 
380 int BigInteger::getHighestBit() const noexcept
381 {
382  auto* values = getValues();
383 
384  for (int i = (int) bitToIndex (highestBit); i >= 0; --i)
385  if (uint32 n = values[i])
386  return findHighestSetBit (n) + (i << 5);
387 
388  return -1;
389 }
390 
391 int BigInteger::findNextSetBit (int i) const noexcept
392 {
393  auto* values = getValues();
394 
395  for (; i <= highestBit; ++i)
396  if ((values [bitToIndex (i)] & bitToMask (i)) != 0)
397  return i;
398 
399  return -1;
400 }
401 
402 int BigInteger::findNextClearBit (int i) const noexcept
403 {
404  auto* values = getValues();
405 
406  for (; i <= highestBit; ++i)
407  if ((values [bitToIndex (i)] & bitToMask (i)) == 0)
408  break;
409 
410  return i;
411 }
412 
413 //==============================================================================
414 BigInteger& BigInteger::operator+= (const BigInteger& other)
415 {
416  if (this == &other)
417  return operator+= (BigInteger (other));
418 
419  if (other.isNegative())
420  return operator-= (-other);
421 
422  if (isNegative())
423  {
424  if (compareAbsolute (other) < 0)
425  {
426  auto temp = *this;
427  temp.negate();
428  *this = other;
429  *this -= temp;
430  }
431  else
432  {
433  negate();
434  *this -= other;
435  negate();
436  }
437  }
438  else
439  {
440  highestBit = jmax (highestBit, other.highestBit) + 1;
441 
442  auto numInts = sizeNeededToHold (highestBit);
443  auto* values = ensureSize (numInts);
444  auto* otherValues = other.getValues();
445  int64 remainder = 0;
446 
447  for (size_t i = 0; i < numInts; ++i)
448  {
449  remainder += values[i];
450 
451  if (i < other.allocatedSize)
452  remainder += otherValues[i];
453 
454  values[i] = (uint32) remainder;
455  remainder >>= 32;
456  }
457 
458  jassert (remainder == 0);
459  highestBit = getHighestBit();
460  }
461 
462  return *this;
463 }
464 
465 BigInteger& BigInteger::operator-= (const BigInteger& other)
466 {
467  if (this == &other)
468  {
469  clear();
470  return *this;
471  }
472 
473  if (other.isNegative())
474  return operator+= (-other);
475 
476  if (isNegative())
477  {
478  negate();
479  *this += other;
480  negate();
481  return *this;
482  }
483 
484  if (compareAbsolute (other) < 0)
485  {
486  auto temp = other;
487  swapWith (temp);
488  *this -= temp;
489  negate();
490  return *this;
491  }
492 
493  auto numInts = sizeNeededToHold (getHighestBit());
494  auto maxOtherInts = sizeNeededToHold (other.getHighestBit());
495  jassert (numInts >= maxOtherInts);
496  auto* values = getValues();
497  auto* otherValues = other.getValues();
498  int64 amountToSubtract = 0;
499 
500  for (size_t i = 0; i < numInts; ++i)
501  {
502  if (i < maxOtherInts)
503  amountToSubtract += (int64) otherValues[i];
504 
505  if (values[i] >= amountToSubtract)
506  {
507  values[i] = (uint32) (values[i] - amountToSubtract);
508  amountToSubtract = 0;
509  }
510  else
511  {
512  const int64 n = ((int64) values[i] + (((int64) 1) << 32)) - amountToSubtract;
513  values[i] = (uint32) n;
514  amountToSubtract = 1;
515  }
516  }
517 
518  highestBit = getHighestBit();
519  return *this;
520 }
521 
522 BigInteger& BigInteger::operator*= (const BigInteger& other)
523 {
524  if (this == &other)
525  return operator*= (BigInteger (other));
526 
527  auto n = getHighestBit();
528  auto t = other.getHighestBit();
529 
530  auto wasNegative = isNegative();
531  setNegative (false);
532 
533  BigInteger total;
534  total.highestBit = n + t + 1;
535  auto* totalValues = total.ensureSize (sizeNeededToHold (total.highestBit) + 1);
536 
537  n >>= 5;
538  t >>= 5;
539 
540  auto m = other;
541  m.setNegative (false);
542 
543  auto* mValues = m.getValues();
544  auto* values = getValues();
545 
546  for (int i = 0; i <= t; ++i)
547  {
548  uint32 c = 0;
549 
550  for (int j = 0; j <= n; ++j)
551  {
552  auto uv = (uint64) totalValues[i + j] + (uint64) values[j] * (uint64) mValues[i] + (uint64) c;
553  totalValues[i + j] = (uint32) uv;
554  c = uv >> 32;
555  }
556 
557  totalValues[i + n + 1] = c;
558  }
559 
560  total.highestBit = total.getHighestBit();
561  total.setNegative (wasNegative ^ other.isNegative());
562  swapWith (total);
563 
564  return *this;
565 }
566 
567 void BigInteger::divideBy (const BigInteger& divisor, BigInteger& remainder)
568 {
569  if (this == &divisor)
570  return divideBy (BigInteger (divisor), remainder);
571 
572  jassert (this != &remainder); // (can't handle passing itself in to get the remainder)
573 
574  auto divHB = divisor.getHighestBit();
575  auto ourHB = getHighestBit();
576 
577  if (divHB < 0 || ourHB < 0)
578  {
579  // division by zero
580  remainder.clear();
581  clear();
582  }
583  else
584  {
585  auto wasNegative = isNegative();
586 
587  swapWith (remainder);
588  remainder.setNegative (false);
589  clear();
590 
591  BigInteger temp (divisor);
592  temp.setNegative (false);
593 
594  auto leftShift = ourHB - divHB;
595  temp <<= leftShift;
596 
597  while (leftShift >= 0)
598  {
599  if (remainder.compareAbsolute (temp) >= 0)
600  {
601  remainder -= temp;
602  setBit (leftShift);
603  }
604 
605  if (--leftShift >= 0)
606  temp >>= 1;
607  }
608 
609  negative = wasNegative ^ divisor.isNegative();
610  remainder.setNegative (wasNegative);
611  }
612 }
613 
614 BigInteger& BigInteger::operator/= (const BigInteger& other)
615 {
616  BigInteger remainder;
617  divideBy (other, remainder);
618  return *this;
619 }
620 
621 BigInteger& BigInteger::operator|= (const BigInteger& other)
622 {
623  if (this == &other)
624  return *this;
625 
626  // this operation doesn't take into account negative values..
627  jassert (isNegative() == other.isNegative());
628 
629  if (other.highestBit >= 0)
630  {
631  auto* values = ensureSize (sizeNeededToHold (other.highestBit));
632  auto* otherValues = other.getValues();
633 
634  auto n = (int) bitToIndex (other.highestBit) + 1;
635 
636  while (--n >= 0)
637  values[n] |= otherValues[n];
638 
639  if (other.highestBit > highestBit)
640  highestBit = other.highestBit;
641 
642  highestBit = getHighestBit();
643  }
644 
645  return *this;
646 }
647 
648 BigInteger& BigInteger::operator&= (const BigInteger& other)
649 {
650  if (this == &other)
651  return *this;
652 
653  // this operation doesn't take into account negative values..
654  jassert (isNegative() == other.isNegative());
655 
656  auto* values = getValues();
657  auto* otherValues = other.getValues();
658 
659  auto n = (int) allocatedSize;
660 
661  while (n > (int) other.allocatedSize)
662  values[--n] = 0;
663 
664  while (--n >= 0)
665  values[n] &= otherValues[n];
666 
667  if (other.highestBit < highestBit)
668  highestBit = other.highestBit;
669 
670  highestBit = getHighestBit();
671  return *this;
672 }
673 
674 BigInteger& BigInteger::operator^= (const BigInteger& other)
675 {
676  if (this == &other)
677  {
678  clear();
679  return *this;
680  }
681 
682  // this operation will only work with the absolute values
683  jassert (isNegative() == other.isNegative());
684 
685  if (other.highestBit >= 0)
686  {
687  auto* values = ensureSize (sizeNeededToHold (other.highestBit));
688  auto* otherValues = other.getValues();
689 
690  auto n = (int) bitToIndex (other.highestBit) + 1;
691 
692  while (--n >= 0)
693  values[n] ^= otherValues[n];
694 
695  if (other.highestBit > highestBit)
696  highestBit = other.highestBit;
697 
698  highestBit = getHighestBit();
699  }
700 
701  return *this;
702 }
703 
704 BigInteger& BigInteger::operator%= (const BigInteger& divisor)
705 {
706  BigInteger remainder;
707  divideBy (divisor, remainder);
708  swapWith (remainder);
709  return *this;
710 }
711 
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; }
716 
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; }
730 
731 //==============================================================================
732 int BigInteger::compare (const BigInteger& other) const noexcept
733 {
734  auto isNeg = isNegative();
735 
736  if (isNeg == other.isNegative())
737  {
738  auto absComp = compareAbsolute (other);
739  return isNeg ? -absComp : absComp;
740  }
741 
742  return isNeg ? -1 : 1;
743 }
744 
745 int BigInteger::compareAbsolute (const BigInteger& other) const noexcept
746 {
747  auto h1 = getHighestBit();
748  auto h2 = other.getHighestBit();
749 
750  if (h1 > h2) return 1;
751  if (h1 < h2) return -1;
752 
753  auto* values = getValues();
754  auto* otherValues = other.getValues();
755 
756  for (int i = (int) bitToIndex (h1); i >= 0; --i)
757  if (values[i] != otherValues[i])
758  return values[i] > otherValues[i] ? 1 : -1;
759 
760  return 0;
761 }
762 
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; }
769 
770 //==============================================================================
771 void BigInteger::shiftLeft (int bits, const int startBit)
772 {
773  if (startBit > 0)
774  {
775  for (int i = highestBit; i >= startBit; --i)
776  setBit (i + bits, (*this) [i]);
777 
778  while (--bits >= 0)
779  clearBit (bits + startBit);
780  }
781  else
782  {
783  auto* values = ensureSize (sizeNeededToHold (highestBit + bits));
784  auto wordsToMove = bitToIndex (bits);
785  auto numOriginalInts = bitToIndex (highestBit);
786  highestBit += bits;
787 
788  if (wordsToMove > 0)
789  {
790  for (int i = (int) numOriginalInts; i >= 0; --i)
791  values[(size_t) i + wordsToMove] = values[i];
792 
793  for (size_t j = 0; j < wordsToMove; ++j)
794  values[j] = 0;
795 
796  bits &= 31;
797  }
798 
799  if (bits != 0)
800  {
801  auto invBits = 32 - bits;
802 
803  for (size_t i = bitToIndex (highestBit); i > wordsToMove; --i)
804  values[i] = (values[i] << bits) | (values[i - 1] >> invBits);
805 
806  values[wordsToMove] = values[wordsToMove] << bits;
807  }
808 
809  highestBit = getHighestBit();
810  }
811 }
812 
813 void BigInteger::shiftRight (int bits, const int startBit)
814 {
815  if (startBit > 0)
816  {
817  for (int i = startBit; i <= highestBit; ++i)
818  setBit (i, (*this) [i + bits]);
819 
820  highestBit = getHighestBit();
821  }
822  else
823  {
824  if (bits > highestBit)
825  {
826  clear();
827  }
828  else
829  {
830  auto wordsToMove = bitToIndex (bits);
831  auto top = 1 + bitToIndex (highestBit) - wordsToMove;
832  highestBit -= bits;
833  auto* values = getValues();
834 
835  if (wordsToMove > 0)
836  {
837  for (size_t i = 0; i < top; ++i)
838  values[i] = values[i + wordsToMove];
839 
840  for (size_t i = 0; i < wordsToMove; ++i)
841  values[top + i] = 0;
842 
843  bits &= 31;
844  }
845 
846  if (bits != 0)
847  {
848  auto invBits = 32 - bits;
849  --top;
850 
851  for (size_t i = 0; i < top; ++i)
852  values[i] = (values[i] >> bits) | (values[i + 1] << invBits);
853 
854  values[top] = (values[top] >> bits);
855  }
856 
857  highestBit = getHighestBit();
858  }
859  }
860 }
861 
862 void BigInteger::shiftBits (int bits, const int startBit)
863 {
864  if (highestBit >= 0)
865  {
866  if (bits < 0)
867  shiftRight (-bits, startBit);
868  else if (bits > 0)
869  shiftLeft (bits, startBit);
870  }
871 }
872 
873 //==============================================================================
874 static BigInteger simpleGCD (BigInteger* m, BigInteger* n)
875 {
876  while (! m->isZero())
877  {
878  if (n->compareAbsolute (*m) > 0)
879  std::swap (m, n);
880 
881  *m -= *n;
882  }
883 
884  return *n;
885 }
886 
888 {
889  auto m = *this;
890 
891  while (! n.isZero())
892  {
893  if (std::abs (m.getHighestBit() - n.getHighestBit()) <= 16)
894  return simpleGCD (&m, &n);
895 
896  BigInteger temp2;
897  m.divideBy (n, temp2);
898 
899  m.swapWith (n);
900  n.swapWith (temp2);
901  }
902 
903  return m;
904 }
905 
906 void BigInteger::exponentModulo (const BigInteger& exponent, const BigInteger& modulus)
907 {
908  *this %= modulus;
909  auto exp = exponent;
910  exp %= modulus;
911 
912  if (modulus.getHighestBit() <= 32 || modulus % 2 == 0)
913  {
914  auto a = *this;
915  auto n = exp.getHighestBit();
916 
917  for (int i = n; --i >= 0;)
918  {
919  *this *= *this;
920 
921  if (exp[i])
922  *this *= a;
923 
924  if (compareAbsolute (modulus) >= 0)
925  *this %= modulus;
926  }
927  }
928  else
929  {
930  auto Rfactor = modulus.getHighestBit() + 1;
931  BigInteger R (1);
932  R.shiftLeft (Rfactor, 0);
933 
934  BigInteger R1, m1, g;
935  g.extendedEuclidean (modulus, R, m1, R1);
936 
937  if (! g.isOne())
938  {
939  BigInteger a (*this);
940 
941  for (int i = exp.getHighestBit(); --i >= 0;)
942  {
943  *this *= *this;
944 
945  if (exp[i])
946  *this *= a;
947 
948  if (compareAbsolute (modulus) >= 0)
949  *this %= modulus;
950  }
951  }
952  else
953  {
954  auto am = (*this * R) % modulus;
955  auto xm = am;
956  auto um = R % modulus;
957 
958  for (int i = exp.getHighestBit(); --i >= 0;)
959  {
960  xm.montgomeryMultiplication (xm, modulus, m1, Rfactor);
961 
962  if (exp[i])
963  xm.montgomeryMultiplication (am, modulus, m1, Rfactor);
964  }
965 
966  xm.montgomeryMultiplication (1, modulus, m1, Rfactor);
967  swapWith (xm);
968  }
969  }
970 }
971 
972 void BigInteger::montgomeryMultiplication (const BigInteger& other, const BigInteger& modulus,
973  const BigInteger& modulusp, const int k)
974 {
975  *this *= other;
976  auto t = *this;
977 
978  setRange (k, highestBit - k + 1, false);
979  *this *= modulusp;
980 
981  setRange (k, highestBit - k + 1, false);
982  *this *= modulus;
983  *this += t;
984  shiftRight (k, 0);
985 
986  if (compare (modulus) >= 0)
987  *this -= modulus;
988  else if (isNegative())
989  *this += modulus;
990 }
991 
993  BigInteger& x, BigInteger& y)
994 {
995  BigInteger p(a), q(b), gcd(1);
996  Array<BigInteger> tempValues;
997 
998  while (! q.isZero())
999  {
1000  tempValues.add (p / q);
1001  gcd = q;
1002  q = p % q;
1003  p = gcd;
1004  }
1005 
1006  x.clear();
1007  y = 1;
1008 
1009  for (int i = 1; i < tempValues.size(); ++i)
1010  {
1011  auto& v = tempValues.getReference (tempValues.size() - i - 1);
1012 
1013  if ((i & 1) != 0)
1014  x += y * v;
1015  else
1016  y += x * v;
1017  }
1018 
1019  if (gcd.compareAbsolute (y * b - x * a) != 0)
1020  {
1021  x.negate();
1022  x.swapWith (y);
1023  x.negate();
1024  }
1025 
1026  swapWith (gcd);
1027 }
1028 
1030 {
1031  if (modulus.isOne() || modulus.isNegative())
1032  {
1033  clear();
1034  return;
1035  }
1036 
1037  if (isNegative() || compareAbsolute (modulus) >= 0)
1038  *this %= modulus;
1039 
1040  if (isOne())
1041  return;
1042 
1043  if (findGreatestCommonDivisor (modulus) != 1)
1044  {
1045  clear(); // not invertible!
1046  return;
1047  }
1048 
1049  BigInteger a1 (modulus), a2 (*this),
1050  b1 (modulus), b2 (1);
1051 
1052  while (! a2.isOne())
1053  {
1054  BigInteger temp1, multiplier (a1);
1055  multiplier.divideBy (a2, temp1);
1056 
1057  temp1 = a2;
1058  temp1 *= multiplier;
1059  auto temp2 = a1;
1060  temp2 -= temp1;
1061  a1 = a2;
1062  a2 = temp2;
1063 
1064  temp1 = b2;
1065  temp1 *= multiplier;
1066  temp2 = b1;
1067  temp2 -= temp1;
1068  b1 = b2;
1069  b2 = temp2;
1070  }
1071 
1072  while (b2.isNegative())
1073  b2 += modulus;
1074 
1075  b2 %= modulus;
1076  swapWith (b2);
1077 }
1078 
1079 //==============================================================================
1080 OutputStream& JUCE_CALLTYPE operator<< (OutputStream& stream, const BigInteger& value)
1081 {
1082  return stream << value.toString (10);
1083 }
1084 
1085 String BigInteger::toString (const int base, const int minimumNumCharacters) const
1086 {
1087  String s;
1088  auto v = *this;
1089 
1090  if (base == 2 || base == 8 || base == 16)
1091  {
1092  auto bits = (base == 2) ? 1 : (base == 8 ? 3 : 4);
1093  static const char hexDigits[] = "0123456789abcdef";
1094 
1095  for (;;)
1096  {
1097  auto remainder = v.getBitRangeAsInt (0, bits);
1098  v >>= bits;
1099 
1100  if (remainder == 0 && v.isZero())
1101  break;
1102 
1103  s = String::charToString ((juce_wchar) (uint8) hexDigits [remainder]) + s;
1104  }
1105  }
1106  else if (base == 10)
1107  {
1108  const BigInteger ten (10);
1109  BigInteger remainder;
1110 
1111  for (;;)
1112  {
1113  v.divideBy (ten, remainder);
1114 
1115  if (remainder.isZero() && v.isZero())
1116  break;
1117 
1118  s = String (remainder.getBitRangeAsInt (0, 8)) + s;
1119  }
1120  }
1121  else
1122  {
1123  jassertfalse; // can't do the specified base!
1124  return {};
1125  }
1126 
1127  s = s.paddedLeft ('0', minimumNumCharacters);
1128 
1129  return isNegative() ? "-" + s : s;
1130 }
1131 
1132 void BigInteger::parseString (StringRef text, const int base)
1133 {
1134  clear();
1135  auto t = text.text.findEndOfWhitespace();
1136 
1137  setNegative (*t == (juce_wchar) '-');
1138 
1139  if (base == 2 || base == 8 || base == 16)
1140  {
1141  auto bits = (base == 2) ? 1 : (base == 8 ? 3 : 4);
1142 
1143  for (;;)
1144  {
1145  auto c = t.getAndAdvance();
1146  auto digit = CharacterFunctions::getHexDigitValue (c);
1147 
1148  if (((uint32) digit) < (uint32) base)
1149  {
1150  *this <<= bits;
1151  *this += digit;
1152  }
1153  else if (c == 0)
1154  {
1155  break;
1156  }
1157  }
1158  }
1159  else if (base == 10)
1160  {
1161  const BigInteger ten ((uint32) 10);
1162 
1163  for (;;)
1164  {
1165  auto c = t.getAndAdvance();
1166 
1167  if (c >= '0' && c <= '9')
1168  {
1169  *this *= ten;
1170  *this += (int) (c - '0');
1171  }
1172  else if (c == 0)
1173  {
1174  break;
1175  }
1176  }
1177  }
1178 }
1179 
1181 {
1182  auto numBytes = (getHighestBit() + 8) >> 3;
1183  MemoryBlock mb ((size_t) numBytes);
1184  auto* values = getValues();
1185 
1186  for (int i = 0; i < numBytes; ++i)
1187  mb[i] = (char) ((values[i / 4] >> ((i & 3) * 8)) & 0xff);
1188 
1189  return mb;
1190 }
1191 
1193 {
1194  auto numBytes = data.getSize();
1195  auto numInts = 1 + (numBytes / sizeof (uint32));
1196  auto* values = ensureSize (numInts);
1197 
1198  for (int i = 0; i < (int) numInts - 1; ++i)
1199  values[i] = (uint32) ByteOrder::littleEndianInt (addBytesToPointer (data.getData(), sizeof (uint32) * (size_t) i));
1200 
1201  values[numInts - 1] = 0;
1202 
1203  for (int i = (int) (numBytes & ~3u); i < (int) numBytes; ++i)
1204  this->setBitRangeAsInt (i << 3, 8, (uint32) data [i]);
1205 
1206  highestBit = (int) numBytes * 8;
1207  highestBit = getHighestBit();
1208 }
1209 
1210 //==============================================================================
1211 void writeLittleEndianBitsInBuffer (void* buffer, uint32 startBit, uint32 numBits, uint32 value) noexcept
1212 {
1213  jassert (buffer != nullptr);
1214  jassert (numBits > 0 && numBits <= 32);
1215  jassert (numBits == 32 || (value >> numBits) == 0);
1216 
1217  uint8* data = static_cast<uint8*> (buffer) + startBit / 8;
1218 
1219  if (const uint32 offset = (startBit & 7))
1220  {
1221  const uint32 bitsInByte = 8 - offset;
1222  const uint8 current = *data;
1223 
1224  if (bitsInByte >= numBits)
1225  {
1226  *data = (uint8) ((current & ~(((1u << numBits) - 1u) << offset)) | (value << offset));
1227  return;
1228  }
1229 
1230  *data++ = current ^ (uint8) (((value << offset) ^ current) & (((1u << bitsInByte) - 1u) << offset));
1231  numBits -= bitsInByte;
1232  value >>= bitsInByte;
1233  }
1234 
1235  while (numBits >= 8)
1236  {
1237  *data++ = (uint8) value;
1238  value >>= 8;
1239  numBits -= 8;
1240  }
1241 
1242  if (numBits > 0)
1243  *data = (uint8) ((*data & (0xff << numBits)) | value);
1244 }
1245 
1246 uint32 readLittleEndianBitsInBuffer (const void* buffer, uint32 startBit, uint32 numBits) noexcept
1247 {
1248  jassert (buffer != nullptr);
1249  jassert (numBits > 0 && numBits <= 32);
1250 
1251  uint32 result = 0;
1252  uint32 bitsRead = 0;
1253  const uint8* data = static_cast<const uint8*> (buffer) + startBit / 8;
1254 
1255  if (const uint32 offset = (startBit & 7))
1256  {
1257  const uint32 bitsInByte = 8 - offset;
1258  result = (*data >> offset);
1259 
1260  if (bitsInByte >= numBits)
1261  return result & ((1u << numBits) - 1u);
1262 
1263  numBits -= bitsInByte;
1264  bitsRead += bitsInByte;
1265  ++data;
1266  }
1267 
1268  while (numBits >= 8)
1269  {
1270  result |= (((uint32) *data++) << bitsRead);
1271  bitsRead += 8;
1272  numBits -= 8;
1273  }
1274 
1275  if (numBits > 0)
1276  result |= ((*data & ((1u << numBits) - 1u)) << bitsRead);
1277 
1278  return result;
1279 }
1280 
1281 //==============================================================================
1282 //==============================================================================
1283 #if JUCE_UNIT_TESTS
1284 
1285 class BigIntegerTests : public UnitTest
1286 {
1287 public:
1288  BigIntegerTests() : UnitTest ("BigInteger", "Maths") {}
1289 
1290  static BigInteger getBigRandom (Random& r)
1291  {
1292  BigInteger b;
1293 
1294  while (b < 2)
1295  r.fillBitsRandomly (b, 0, r.nextInt (150) + 1);
1296 
1297  return b;
1298  }
1299 
1300  void runTest() override
1301  {
1302  {
1303  beginTest ("BigInteger");
1304 
1305  Random r = getRandom();
1306 
1307  expect (BigInteger().isZero());
1308  expect (BigInteger(1).isOne());
1309 
1310  for (int j = 10000; --j >= 0;)
1311  {
1312  BigInteger b1 (getBigRandom(r)),
1313  b2 (getBigRandom(r));
1314 
1315  BigInteger b3 = b1 + b2;
1316  expect (b3 > b1 && b3 > b2);
1317  expect (b3 - b1 == b2);
1318  expect (b3 - b2 == b1);
1319 
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);
1327 
1328  // TODO: should add tests for other ops (although they also get pretty well tested in the RSA unit test)
1329 
1330  BigInteger b5;
1332  expect (b3 == b5);
1333  }
1334  }
1335 
1336  {
1337  beginTest ("Bit setting");
1338 
1339  Random r = getRandom();
1340  static uint8 test[2048];
1341 
1342  for (int j = 100000; --j >= 0;)
1343  {
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());
1347 
1348  if (num < 32)
1349  value &= ((1u << num) - 1);
1350 
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);
1355 
1356  expect (result == value);
1357  expect (old1 == readLittleEndianBitsInBuffer (test, offset - 6, 6));
1358  expect (old2 == readLittleEndianBitsInBuffer (test, offset + num, 6));
1359  }
1360  }
1361  }
1362 };
1363 
1364 static BigIntegerTests bigIntegerTests;
1365 
1366 #endif
1367 
1368 } // namespace juce
size_t getSize() const noexcept
Returns the block&#39;s current allocated size, in bytes.
BigInteger()
Creates an empty BigInteger.
void montgomeryMultiplication(const BigInteger &other, const BigInteger &modulus, const BigInteger &modulusp, int k)
Performs the Montgomery Multiplication with modulo.
void malloc(SizeType newNumElements, size_t elementSize=sizeof(ElementType))
Allocates a specified amount of memory.
void swapWith(BigInteger &) noexcept
Swaps the internal contents of this with another object.
BigInteger & operator=(BigInteger &&) noexcept
Move assignment operator.
int nextInt() noexcept
Returns the next random 32 bit integer.
Definition: juce_Random.cpp:78
A simple class for holding temporary references to a string literal or String.
void add(const ElementType &newElement)
Appends a new element at the end of the array.
Definition: juce_Array.h:375
void realloc(SizeType newNumElements, size_t elementSize=sizeof(ElementType))
Re-allocates a specified amount of memory.
void divideBy(const BigInteger &divisor, BigInteger &remainder)
Divides this value by another one and returns the remainder.
void parseString(StringRef text, int base)
Reads the numeric value from a string.
The JUCE String class!
Definition: juce_String.h:42
bool operator[](int bit) const noexcept
Returns the value of a specified bit in the number.
CharPointer_UTF8 findEndOfWhitespace() const noexcept
Returns the first non-whitespace character in the string.
An arbitrarily large integer class.
void calloc(SizeType newNumElements, const size_t elementSize=sizeof(ElementType))
Allocates a specified amount of memory and clears it.
This is a base class for classes that perform a unit test.
Definition: juce_UnitTest.h:73
~BigInteger()
Destructor.
void clear() noexcept
Resets the value to 0.
void * getData() const noexcept
Returns a void pointer to the data.
BigInteger getBitRange(int startBit, int numBits) const
Returns a range of bits as a new BigInteger.
BigInteger findGreatestCommonDivisor(BigInteger other) const
Returns the largest value that will divide both this value and the argument.
void exponentModulo(const BigInteger &exponent, const BigInteger &modulus)
Performs a combined exponent and modulo operation.
bool isOne() const noexcept
Returns true if the value is 1.
uint32 getBitRangeAsInt(int startBit, int numBits) const noexcept
Returns a range of bits as an integer value.
int findNextClearBit(int startIndex) const noexcept
Looks for the index of the next clear bit after a given starting point.
int compareAbsolute(const BigInteger &other) const noexcept
Compares the magnitudes of two BigIntegers, ignoring their signs.
bool isNegative() const noexcept
Returns true if the value is less than zero.
static int getHexDigitValue(juce_wchar digit) noexcept
Returns 0 to 16 for &#39;0&#39; to &#39;F", or -1 for characters that aren&#39;t a legal hex digit.
void free() noexcept
Frees any currently-allocated data.
static JUCE_CONSTEXPR uint32 littleEndianInt(const void *bytes) noexcept
Turns 4 bytes into a little-endian integer.
The base class for streams that write data to some kind of destination.
void fillBitsRandomly(void *bufferToFill, size_t sizeInBytes)
Fills a block of memory with random values.
void clearBit(int bitNumber) noexcept
Clears a particular bit in the number.
Holds a resizable array of primitive or copy-by-value objects.
Definition: juce_Array.h:59
void extendedEuclidean(const BigInteger &a, const BigInteger &b, BigInteger &xOut, BigInteger &yOut)
Performs the Extended Euclidean algorithm.
int getHighestBit() const noexcept
Returns the index of the highest set bit in the number.
String paddedLeft(juce_wchar padCharacter, int minimumLength) const
Returns a copy of this string with the specified character repeatedly added to its beginning until th...
int size() const noexcept
Returns the current number of elements in the array.
Definition: juce_Array.h:219
bool isZero() const noexcept
Returns true if no bits are set.
void swapWith(HeapBlock< ElementType, otherBlockThrows > &other) noexcept
Swaps this object&#39;s data with the data of another HeapBlock.
void inverseModulo(const BigInteger &modulus)
Performs an inverse modulo on the value.
String toString(int base, int minimumNumCharacters=1) const
Converts the number to a string.
String::CharPointerType text
The text that is referenced.
int toInteger() const noexcept
Attempts to get the lowest 32 bits of the value as an integer.
ElementType & getReference(int index) const noexcept
Returns a direct reference to one of the elements in the array, without checking the index passed in...
Definition: juce_Array.h:271
void shiftBits(int howManyBitsLeft, int startBit)
Shifts a section of bits left or right.
static String charToString(juce_wchar character)
Creates a string from a single character.
void insertBit(int bitNumber, bool shouldBeSet)
Inserts a bit an a given position, shifting up any bits above it.
A random number generator.
Definition: juce_Random.h:38
void setNegative(bool shouldBeNegative) noexcept
Changes the sign of the number to be positive or negative.
int countNumberOfSetBits() const noexcept
Returns the total number of set bits in the value.
int findNextSetBit(int startIndex) const noexcept
Looks for the index of the next set bit after a given starting point.
int compare(const BigInteger &other) const noexcept
Does a signed comparison of two BigIntegers.
A class to hold a resizable block of raw data.
void setBit(int bitNumber)
Sets a specified bit to 1.
void loadFromMemoryBlock(const MemoryBlock &data)
Converts a block of raw data into a number.
MemoryBlock toMemoryBlock() const
Turns the number into a block of binary data.
void negate() noexcept
Inverts the sign of the number.
void setBitRangeAsInt(int startBit, int numBits, uint32 valueToSet)
Sets a range of bits to an integer value.
int64 toInt64() const noexcept
Attempts to get the lowest 64 bits of the value as an integer.
void setRange(int startBit, int numBits, bool shouldBeSet)
Sets a range of bits to be either on or off.