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