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
27namespace 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{
44public:
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. */
77
78 //==============================================================================
79 /** Copies another BigInteger onto this one. */
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
212 BigInteger& operator++();
213 BigInteger& operator--();
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;
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,
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
326private:
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. */
344OutputStream& JUCE_CALLTYPE operator<< (OutputStream& stream, const BigInteger& value);
345
346} // namespace juce
347
348/** @}*/
Holds a resizable array of primitive or copy-by-value objects.
Definition juce_Array.h:60
An arbitrarily large integer class.
A class to hold a resizable block of raw data.
The base class for streams that write data to some kind of destination.
A simple class for holding temporary references to a string literal or String.
The JUCE String class!
Definition juce_String.h:43
#define JUCE_API
This macro is added to all JUCE public class declarations.