1 /* 2 ============================================================================== 3 4 This file is part of the JUCE library. 5 Copyright (c) 2020 - 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 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