OpenShot Library | libopenshot-audio  0.2.0
juce_BigInteger.h
1 
2 /** @weakgroup juce_core-maths
3  * @{
4  */
5 /*
6  ==============================================================================
7 
8  This file is part of the JUCE library.
9  Copyright (c) 2017 - ROLI Ltd.
10 
11  JUCE is an open source library subject to commercial or open-source
12  licensing.
13 
14  The code included in this file is provided under the terms of the ISC license
15  http://www.isc.org/downloads/software-support-policy/isc-license. Permission
16  To use, copy, modify, and/or distribute this software for any purpose with or
17  without fee is hereby granted provided that the above copyright notice and
18  this permission notice appear in all copies.
19 
20  JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
21  EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
22  DISCLAIMED.
23 
24  ==============================================================================
25 */
26 
27 namespace juce
28 {
29 
30 //==============================================================================
31 /**
32  An arbitrarily large integer class.
33 
34  A BigInteger can be used in a similar way to a normal integer, but has no size
35  limit (except for memory and performance constraints).
36 
37  Negative values are possible, but the value isn't stored as 2s-complement, so
38  be careful if you use negative values and look at the values of individual bits.
39 
40  @tags{Core}
41 */
43 {
44 public:
45  //==============================================================================
46  /** Creates an empty BigInteger */
47  BigInteger();
48 
49  /** Creates a BigInteger containing an integer value in its low bits.
50  The low 32 bits of the number are initialised with this value.
51  */
52  BigInteger (uint32 value);
53 
54  /** Creates a BigInteger containing an integer value in its low bits.
55  The low 32 bits of the number are initialised with the absolute value
56  passed in, and its sign is set to reflect the sign of the number.
57  */
58  BigInteger (int32 value);
59 
60  /** Creates a BigInteger containing an integer value in its low bits.
61  The low 64 bits of the number are initialised with the absolute value
62  passed in, and its sign is set to reflect the sign of the number.
63  */
64  BigInteger (int64 value);
65 
66  /** Creates a copy of another BigInteger. */
67  BigInteger (const BigInteger&);
68 
69  /** Move constructor */
70  BigInteger (BigInteger&&) noexcept;
71 
72  /** Move assignment operator */
73  BigInteger& operator= (BigInteger&&) noexcept;
74 
75  /** Destructor. */
76  ~BigInteger();
77 
78  //==============================================================================
79  /** Copies another BigInteger onto this one. */
80  BigInteger& operator= (const BigInteger&);
81 
82  /** Swaps the internal contents of this with another object. */
83  void swapWith (BigInteger&) noexcept;
84 
85  //==============================================================================
86  /** Returns the value of a specified bit in the number.
87  If the index is out-of-range, the result will be false.
88  */
89  bool operator[] (int bit) const noexcept;
90 
91  /** Returns true if no bits are set. */
92  bool isZero() const noexcept;
93 
94  /** Returns true if the value is 1. */
95  bool isOne() const noexcept;
96 
97  /** Attempts to get the lowest 32 bits of the value as an integer.
98  If the value is bigger than the integer limits, this will return only the lower bits.
99  */
100  int toInteger() const noexcept;
101 
102  /** Attempts to get the lowest 64 bits of the value as an integer.
103  If the value is bigger than the integer limits, this will return only the lower bits.
104  */
105  int64 toInt64() const noexcept;
106 
107  //==============================================================================
108  /** Resets the value to 0. */
109  void clear() noexcept;
110 
111  /** Clears a particular bit in the number. */
112  void clearBit (int bitNumber) noexcept;
113 
114  /** Sets a specified bit to 1. */
115  void setBit (int bitNumber);
116 
117  /** Sets or clears a specified bit. */
118  void setBit (int bitNumber, bool shouldBeSet);
119 
120  /** Sets a range of bits to be either on or off.
121 
122  @param startBit the first bit to change
123  @param numBits the number of bits to change
124  @param shouldBeSet whether to turn these bits on or off
125  */
126  void setRange (int startBit, int numBits, bool shouldBeSet);
127 
128  /** Inserts a bit an a given position, shifting up any bits above it. */
129  void insertBit (int bitNumber, bool shouldBeSet);
130 
131  /** Returns a range of bits as a new BigInteger.
132 
133  e.g. getBitRangeAsInt (0, 64) would return the lowest 64 bits.
134  @see getBitRangeAsInt
135  */
136  BigInteger getBitRange (int startBit, int numBits) const;
137 
138  /** Returns a range of bits as an integer value.
139 
140  e.g. getBitRangeAsInt (0, 32) would return the lowest 32 bits.
141 
142  Asking for more than 32 bits isn't allowed (obviously) - for that, use
143  getBitRange().
144  */
145  uint32 getBitRangeAsInt (int startBit, int numBits) const noexcept;
146 
147  /** Sets a range of bits to an integer value.
148 
149  Copies the given integer onto a range of bits, starting at startBit,
150  and using up to numBits of the available bits.
151  */
152  void setBitRangeAsInt (int startBit, int numBits, uint32 valueToSet);
153 
154  /** Shifts a section of bits left or right.
155 
156  @param howManyBitsLeft how far to move the bits (+ve numbers shift it left, -ve numbers shift it right).
157  @param startBit the first bit to affect - if this is > 0, only bits above that index will be affected.
158  */
159  void shiftBits (int howManyBitsLeft, int startBit);
160 
161  /** Returns the total number of set bits in the value. */
162  int countNumberOfSetBits() const noexcept;
163 
164  /** Looks for the index of the next set bit after a given starting point.
165 
166  This searches from startIndex (inclusive) upwards for the first set bit,
167  and returns its index. If no set bits are found, it returns -1.
168  */
169  int findNextSetBit (int startIndex) const noexcept;
170 
171  /** Looks for the index of the next clear bit after a given starting point.
172 
173  This searches from startIndex (inclusive) upwards for the first clear bit,
174  and returns its index.
175  */
176  int findNextClearBit (int startIndex) const noexcept;
177 
178  /** Returns the index of the highest set bit in the number.
179  If the value is zero, this will return -1.
180  */
181  int getHighestBit() const noexcept;
182 
183  //==============================================================================
184  /** Returns true if the value is less than zero.
185  @see setNegative, negate
186  */
187  bool isNegative() const noexcept;
188 
189  /** Changes the sign of the number to be positive or negative.
190  @see isNegative, negate
191  */
192  void setNegative (bool shouldBeNegative) noexcept;
193 
194  /** Inverts the sign of the number.
195  @see isNegative, setNegative
196  */
197  void negate() noexcept;
198 
199  //==============================================================================
200  // All the standard arithmetic ops...
201 
202  BigInteger& operator+= (const BigInteger&);
203  BigInteger& operator-= (const BigInteger&);
204  BigInteger& operator*= (const BigInteger&);
205  BigInteger& operator/= (const BigInteger&);
206  BigInteger& operator|= (const BigInteger&);
207  BigInteger& operator&= (const BigInteger&);
208  BigInteger& operator^= (const BigInteger&);
209  BigInteger& operator%= (const BigInteger&);
210  BigInteger& operator<<= (int numBitsToShift);
211  BigInteger& operator>>= (int numBitsToShift);
212  BigInteger& operator++();
213  BigInteger& operator--();
214  BigInteger operator++ (int);
215  BigInteger operator-- (int);
216 
217  BigInteger operator-() const;
218  BigInteger operator+ (const BigInteger&) const;
219  BigInteger operator- (const BigInteger&) const;
220  BigInteger operator* (const BigInteger&) const;
221  BigInteger operator/ (const BigInteger&) const;
222  BigInteger operator| (const BigInteger&) const;
223  BigInteger operator& (const BigInteger&) const;
224  BigInteger operator^ (const BigInteger&) const;
225  BigInteger operator% (const BigInteger&) const;
226  BigInteger operator<< (int numBitsToShift) const;
227  BigInteger operator>> (int numBitsToShift) const;
228 
229  bool operator== (const BigInteger&) const noexcept;
230  bool operator!= (const BigInteger&) const noexcept;
231  bool operator< (const BigInteger&) const noexcept;
232  bool operator<= (const BigInteger&) const noexcept;
233  bool operator> (const BigInteger&) const noexcept;
234  bool operator>= (const BigInteger&) const noexcept;
235 
236  //==============================================================================
237  /** Does a signed comparison of two BigIntegers.
238 
239  Return values are:
240  - 0 if the numbers are the same
241  - < 0 if this number is smaller than the other
242  - > 0 if this number is bigger than the other
243  */
244  int compare (const BigInteger& other) const noexcept;
245 
246  /** Compares the magnitudes of two BigIntegers, ignoring their signs.
247 
248  Return values are:
249  - 0 if the numbers are the same
250  - < 0 if this number is smaller than the other
251  - > 0 if this number is bigger than the other
252  */
253  int compareAbsolute (const BigInteger& other) const noexcept;
254 
255  //==============================================================================
256  /** Divides this value by another one and returns the remainder.
257 
258  This number is divided by other, leaving the quotient in this number,
259  with the remainder being copied to the other BigInteger passed in.
260  */
261  void divideBy (const BigInteger& divisor, BigInteger& remainder);
262 
263  /** Returns the largest value that will divide both this value and the argument. */
264  BigInteger findGreatestCommonDivisor (BigInteger other) const;
265 
266  /** Performs a combined exponent and modulo operation.
267  This BigInteger's value becomes (this ^ exponent) % modulus.
268  */
269  void exponentModulo (const BigInteger& exponent, const BigInteger& modulus);
270 
271  /** Performs an inverse modulo on the value.
272  i.e. the result is (this ^ -1) mod (modulus).
273  */
274  void inverseModulo (const BigInteger& modulus);
275 
276  /** Performs the Montgomery Multiplication with modulo.
277  This object is left containing the result value: ((this * other) * R1) % modulus.
278  To get this result, we need modulus, modulusp and k such as R = 2^k, with
279  modulus * modulusp - R * R1 = GCD(modulus, R) = 1
280  */
281  void montgomeryMultiplication (const BigInteger& other, const BigInteger& modulus,
282  const BigInteger& modulusp, int k);
283 
284  /** Performs the Extended Euclidean algorithm.
285  This method will set the xOut and yOut arguments such that (a * xOut) - (b * yOut) = GCD (a, b).
286  On return, this object is left containing the value of the GCD.
287  */
288  void extendedEuclidean (const BigInteger& a, const BigInteger& b,
289  BigInteger& xOut, BigInteger& yOut);
290 
291  //==============================================================================
292  /** Converts the number to a string.
293 
294  Specify a base such as 2 (binary), 8 (octal), 10 (decimal), 16 (hex).
295  If minimumNumCharacters is greater than 0, the returned string will be
296  padded with leading zeros to reach at least that length.
297  */
298  String toString (int base, int minimumNumCharacters = 1) const;
299 
300  /** Reads the numeric value from a string.
301 
302  Specify a base such as 2 (binary), 8 (octal), 10 (decimal), 16 (hex).
303  Any invalid characters will be ignored.
304  */
305  void parseString (StringRef text, int base);
306 
307  //==============================================================================
308  /** Turns the number into a block of binary data.
309 
310  The data is arranged as little-endian, so the first byte of data is the low 8 bits
311  of the number, and so on.
312 
313  @see loadFromMemoryBlock
314  */
315  MemoryBlock toMemoryBlock() const;
316 
317  /** Converts a block of raw data into a number.
318 
319  The data is arranged as little-endian, so the first byte of data is the low 8 bits
320  of the number, and so on.
321 
322  @see toMemoryBlock
323  */
324  void loadFromMemoryBlock (const MemoryBlock& data);
325 
326 private:
327  //==============================================================================
328  enum { numPreallocatedInts = 4 };
329  HeapBlock<uint32> heapAllocation;
330  uint32 preallocated[numPreallocatedInts];
331  size_t allocatedSize;
332  int highestBit = -1;
333  bool negative = false;
334 
335  uint32* getValues() const noexcept;
336  uint32* ensureSize (size_t);
337  void shiftLeft (int bits, int startBit);
338  void shiftRight (int bits, int startBit);
339 
340  JUCE_LEAK_DETECTOR (BigInteger)
341 };
342 
343 /** Writes a BigInteger to an OutputStream as a UTF8 decimal string. */
344 OutputStream& JUCE_CALLTYPE operator<< (OutputStream& stream, const BigInteger& value);
345 
346 } // namespace juce
347 
348 /** @}*/
#define JUCE_API
This macro is added to all JUCE public class declarations.
A simple class for holding temporary references to a string literal or String.
The JUCE String class!
Definition: juce_String.h:42
An arbitrarily large integer class.
The base class for streams that write data to some kind of destination.
A class to hold a resizable block of raw data.