Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 1 | //===-- APInt.cpp - Implement APInt class ---------------------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Reid Spencer | 96d9137 | 2007-02-27 19:31:09 +0000 | [diff] [blame] | 5 | // This file was developed by Sheng Zhou and is distributed under the |
| 6 | // University of Illinois Open Source License. See LICENSE.TXT for details. |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 10 | // This file implements a class to represent arbitrary precision integer |
| 11 | // constant values and provide a variety of arithmetic operations on them. |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 15 | #define DEBUG_TYPE "apint" |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 16 | #include "llvm/ADT/APInt.h" |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 17 | #include "llvm/Support/Debug.h" |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 18 | #include "llvm/Support/MathExtras.h" |
Jeff Cohen | ca5183d | 2007-03-05 00:00:42 +0000 | [diff] [blame] | 19 | #include <math.h> |
Jeff Cohen | 09dfd8e | 2007-03-20 20:42:36 +0000 | [diff] [blame] | 20 | #include <limits> |
Zhou Sheng | a3832fd | 2007-02-07 06:14:53 +0000 | [diff] [blame] | 21 | #include <cstring> |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 22 | #include <cstdlib> |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 23 | #include <iomanip> |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 24 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 25 | using namespace llvm; |
| 26 | |
Reid Spencer | 9af1887 | 2007-12-11 06:53:58 +0000 | [diff] [blame] | 27 | |
| 28 | /// This enumeration just provides for internal constants used in this |
| 29 | /// translation unit. |
| 30 | enum { |
| 31 | MIN_INT_BITS = 1, ///< Minimum number of bits that can be specified |
| 32 | ///< Note that this must remain synchronized with IntegerType::MIN_INT_BITS |
| 33 | MAX_INT_BITS = (1<<23)-1 ///< Maximum number of bits that can be specified |
| 34 | ///< Note that this must remain synchronized with IntegerType::MAX_INT_BITS |
| 35 | }; |
| 36 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 37 | /// A utility function for allocating memory, checking for allocation failures, |
| 38 | /// and ensuring the contents are zeroed. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 39 | inline static uint64_t* getClearedMemory(uint32_t numWords) { |
| 40 | uint64_t * result = new uint64_t[numWords]; |
| 41 | assert(result && "APInt memory allocation fails!"); |
| 42 | memset(result, 0, numWords * sizeof(uint64_t)); |
| 43 | return result; |
Zhou Sheng | 353815d | 2007-02-06 06:04:53 +0000 | [diff] [blame] | 44 | } |
| 45 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 46 | /// A utility function for allocating memory and checking for allocation |
| 47 | /// failure. The content is not zeroed. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 48 | inline static uint64_t* getMemory(uint32_t numWords) { |
| 49 | uint64_t * result = new uint64_t[numWords]; |
| 50 | assert(result && "APInt memory allocation fails!"); |
| 51 | return result; |
| 52 | } |
| 53 | |
Reid Spencer | adf2a20 | 2007-03-19 21:19:02 +0000 | [diff] [blame] | 54 | APInt::APInt(uint32_t numBits, uint64_t val, bool isSigned) |
Reid Spencer | 3a34137 | 2007-03-19 20:37:47 +0000 | [diff] [blame] | 55 | : BitWidth(numBits), VAL(0) { |
Reid Spencer | 9af1887 | 2007-12-11 06:53:58 +0000 | [diff] [blame] | 56 | assert(BitWidth >= MIN_INT_BITS && "bitwidth too small"); |
| 57 | assert(BitWidth <= MAX_INT_BITS && "bitwidth too large"); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 58 | if (isSingleWord()) |
| 59 | VAL = val; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 60 | else { |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 61 | pVal = getClearedMemory(getNumWords()); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 62 | pVal[0] = val; |
Reid Spencer | 3a34137 | 2007-03-19 20:37:47 +0000 | [diff] [blame] | 63 | if (isSigned && int64_t(val) < 0) |
| 64 | for (unsigned i = 1; i < getNumWords(); ++i) |
| 65 | pVal[i] = -1ULL; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 66 | } |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 67 | clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 68 | } |
| 69 | |
Dale Johannesen | 910993e | 2007-09-21 22:09:37 +0000 | [diff] [blame] | 70 | APInt::APInt(uint32_t numBits, uint32_t numWords, const uint64_t bigVal[]) |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 71 | : BitWidth(numBits), VAL(0) { |
Reid Spencer | 9af1887 | 2007-12-11 06:53:58 +0000 | [diff] [blame] | 72 | assert(BitWidth >= MIN_INT_BITS && "bitwidth too small"); |
| 73 | assert(BitWidth <= MAX_INT_BITS && "bitwidth too large"); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 74 | assert(bigVal && "Null pointer detected!"); |
| 75 | if (isSingleWord()) |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 76 | VAL = bigVal[0]; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 77 | else { |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 78 | // Get memory, cleared to 0 |
| 79 | pVal = getClearedMemory(getNumWords()); |
| 80 | // Calculate the number of words to copy |
| 81 | uint32_t words = std::min<uint32_t>(numWords, getNumWords()); |
| 82 | // Copy the words from bigVal to pVal |
| 83 | memcpy(pVal, bigVal, words * APINT_WORD_SIZE); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 84 | } |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 85 | // Make sure unused high bits are cleared |
| 86 | clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 87 | } |
| 88 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 89 | APInt::APInt(uint32_t numbits, const char StrStart[], uint32_t slen, |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 90 | uint8_t radix) |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 91 | : BitWidth(numbits), VAL(0) { |
Reid Spencer | 9af1887 | 2007-12-11 06:53:58 +0000 | [diff] [blame] | 92 | assert(BitWidth >= MIN_INT_BITS && "bitwidth too small"); |
| 93 | assert(BitWidth <= MAX_INT_BITS && "bitwidth too large"); |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 94 | fromString(numbits, StrStart, slen, radix); |
Zhou Sheng | a3832fd | 2007-02-07 06:14:53 +0000 | [diff] [blame] | 95 | } |
| 96 | |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 97 | APInt::APInt(uint32_t numbits, const std::string& Val, uint8_t radix) |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 98 | : BitWidth(numbits), VAL(0) { |
Reid Spencer | 9af1887 | 2007-12-11 06:53:58 +0000 | [diff] [blame] | 99 | assert(BitWidth >= MIN_INT_BITS && "bitwidth too small"); |
| 100 | assert(BitWidth <= MAX_INT_BITS && "bitwidth too large"); |
Zhou Sheng | a3832fd | 2007-02-07 06:14:53 +0000 | [diff] [blame] | 101 | assert(!Val.empty() && "String empty?"); |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 102 | fromString(numbits, Val.c_str(), Val.size(), radix); |
Zhou Sheng | a3832fd | 2007-02-07 06:14:53 +0000 | [diff] [blame] | 103 | } |
| 104 | |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 105 | APInt::APInt(const APInt& that) |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 106 | : BitWidth(that.BitWidth), VAL(0) { |
Reid Spencer | 9af1887 | 2007-12-11 06:53:58 +0000 | [diff] [blame] | 107 | assert(BitWidth >= MIN_INT_BITS && "bitwidth too small"); |
| 108 | assert(BitWidth <= MAX_INT_BITS && "bitwidth too large"); |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 109 | if (isSingleWord()) |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 110 | VAL = that.VAL; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 111 | else { |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 112 | pVal = getMemory(getNumWords()); |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 113 | memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 114 | } |
| 115 | } |
| 116 | |
| 117 | APInt::~APInt() { |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 118 | if (!isSingleWord() && pVal) |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 119 | delete [] pVal; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 120 | } |
| 121 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 122 | APInt& APInt::operator=(const APInt& RHS) { |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 123 | // Don't do anything for X = X |
| 124 | if (this == &RHS) |
| 125 | return *this; |
| 126 | |
| 127 | // If the bitwidths are the same, we can avoid mucking with memory |
| 128 | if (BitWidth == RHS.getBitWidth()) { |
| 129 | if (isSingleWord()) |
| 130 | VAL = RHS.VAL; |
| 131 | else |
| 132 | memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE); |
| 133 | return *this; |
| 134 | } |
| 135 | |
| 136 | if (isSingleWord()) |
| 137 | if (RHS.isSingleWord()) |
| 138 | VAL = RHS.VAL; |
| 139 | else { |
| 140 | VAL = 0; |
| 141 | pVal = getMemory(RHS.getNumWords()); |
| 142 | memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); |
| 143 | } |
| 144 | else if (getNumWords() == RHS.getNumWords()) |
| 145 | memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); |
| 146 | else if (RHS.isSingleWord()) { |
| 147 | delete [] pVal; |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 148 | VAL = RHS.VAL; |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 149 | } else { |
| 150 | delete [] pVal; |
| 151 | pVal = getMemory(RHS.getNumWords()); |
| 152 | memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); |
| 153 | } |
| 154 | BitWidth = RHS.BitWidth; |
| 155 | return clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 156 | } |
| 157 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 158 | APInt& APInt::operator=(uint64_t RHS) { |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 159 | if (isSingleWord()) |
| 160 | VAL = RHS; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 161 | else { |
| 162 | pVal[0] = RHS; |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 163 | memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 164 | } |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 165 | return clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 166 | } |
| 167 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 168 | /// add_1 - This function adds a single "digit" integer, y, to the multiple |
| 169 | /// "digit" integer array, x[]. x[] is modified to reflect the addition and |
| 170 | /// 1 is returned if there is a carry out, otherwise 0 is returned. |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 171 | /// @returns the carry of the addition. |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 172 | static bool add_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) { |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 173 | for (uint32_t i = 0; i < len; ++i) { |
Reid Spencer | f2c521c | 2007-02-18 06:39:42 +0000 | [diff] [blame] | 174 | dest[i] = y + x[i]; |
| 175 | if (dest[i] < y) |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 176 | y = 1; // Carry one to next digit. |
Reid Spencer | f2c521c | 2007-02-18 06:39:42 +0000 | [diff] [blame] | 177 | else { |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 178 | y = 0; // No need to carry so exit early |
Reid Spencer | f2c521c | 2007-02-18 06:39:42 +0000 | [diff] [blame] | 179 | break; |
| 180 | } |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 181 | } |
Reid Spencer | f2c521c | 2007-02-18 06:39:42 +0000 | [diff] [blame] | 182 | return y; |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 183 | } |
| 184 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 185 | /// @brief Prefix increment operator. Increments the APInt by one. |
| 186 | APInt& APInt::operator++() { |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 187 | if (isSingleWord()) |
| 188 | ++VAL; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 189 | else |
Zhou Sheng | a3832fd | 2007-02-07 06:14:53 +0000 | [diff] [blame] | 190 | add_1(pVal, pVal, getNumWords(), 1); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 191 | return clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 192 | } |
| 193 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 194 | /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from |
| 195 | /// the multi-digit integer array, x[], propagating the borrowed 1 value until |
| 196 | /// no further borrowing is neeeded or it runs out of "digits" in x. The result |
| 197 | /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted. |
| 198 | /// In other words, if y > x then this function returns 1, otherwise 0. |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 199 | /// @returns the borrow out of the subtraction |
| 200 | static bool sub_1(uint64_t x[], uint32_t len, uint64_t y) { |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 201 | for (uint32_t i = 0; i < len; ++i) { |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 202 | uint64_t X = x[i]; |
Reid Spencer | f2c521c | 2007-02-18 06:39:42 +0000 | [diff] [blame] | 203 | x[i] -= y; |
| 204 | if (y > X) |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 205 | y = 1; // We have to "borrow 1" from next "digit" |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 206 | else { |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 207 | y = 0; // No need to borrow |
| 208 | break; // Remaining digits are unchanged so exit early |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 209 | } |
| 210 | } |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 211 | return bool(y); |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 212 | } |
| 213 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 214 | /// @brief Prefix decrement operator. Decrements the APInt by one. |
| 215 | APInt& APInt::operator--() { |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 216 | if (isSingleWord()) |
| 217 | --VAL; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 218 | else |
Zhou Sheng | a3832fd | 2007-02-07 06:14:53 +0000 | [diff] [blame] | 219 | sub_1(pVal, getNumWords(), 1); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 220 | return clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 221 | } |
| 222 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 223 | /// add - This function adds the integer array x to the integer array Y and |
| 224 | /// places the result in dest. |
| 225 | /// @returns the carry out from the addition |
| 226 | /// @brief General addition of 64-bit integer arrays |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 227 | static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y, |
| 228 | uint32_t len) { |
| 229 | bool carry = false; |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 230 | for (uint32_t i = 0; i< len; ++i) { |
Reid Spencer | 9290463 | 2007-02-23 01:57:13 +0000 | [diff] [blame] | 231 | uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 232 | dest[i] = x[i] + y[i] + carry; |
Reid Spencer | 60c0a6a | 2007-02-21 05:44:56 +0000 | [diff] [blame] | 233 | carry = dest[i] < limit || (carry && dest[i] == limit); |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 234 | } |
| 235 | return carry; |
| 236 | } |
| 237 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 238 | /// Adds the RHS APint to this APInt. |
| 239 | /// @returns this, after addition of RHS. |
| 240 | /// @brief Addition assignment operator. |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 241 | APInt& APInt::operator+=(const APInt& RHS) { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 242 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 243 | if (isSingleWord()) |
| 244 | VAL += RHS.VAL; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 245 | else { |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 246 | add(pVal, pVal, RHS.pVal, getNumWords()); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 247 | } |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 248 | return clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 249 | } |
| 250 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 251 | /// Subtracts the integer array y from the integer array x |
| 252 | /// @returns returns the borrow out. |
| 253 | /// @brief Generalized subtraction of 64-bit integer arrays. |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 254 | static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y, |
| 255 | uint32_t len) { |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 256 | bool borrow = false; |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 257 | for (uint32_t i = 0; i < len; ++i) { |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 258 | uint64_t x_tmp = borrow ? x[i] - 1 : x[i]; |
| 259 | borrow = y[i] > x_tmp || (borrow && x[i] == 0); |
| 260 | dest[i] = x_tmp - y[i]; |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 261 | } |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 262 | return borrow; |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 263 | } |
| 264 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 265 | /// Subtracts the RHS APInt from this APInt |
| 266 | /// @returns this, after subtraction |
| 267 | /// @brief Subtraction assignment operator. |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 268 | APInt& APInt::operator-=(const APInt& RHS) { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 269 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 270 | if (isSingleWord()) |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 271 | VAL -= RHS.VAL; |
| 272 | else |
| 273 | sub(pVal, pVal, RHS.pVal, getNumWords()); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 274 | return clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 275 | } |
| 276 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 277 | /// Multiplies an integer array, x by a a uint64_t integer and places the result |
| 278 | /// into dest. |
| 279 | /// @returns the carry out of the multiplication. |
| 280 | /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer. |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 281 | static uint64_t mul_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) { |
| 282 | // Split y into high 32-bit part (hy) and low 32-bit part (ly) |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 283 | uint64_t ly = y & 0xffffffffULL, hy = y >> 32; |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 284 | uint64_t carry = 0; |
| 285 | |
| 286 | // For each digit of x. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 287 | for (uint32_t i = 0; i < len; ++i) { |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 288 | // Split x into high and low words |
| 289 | uint64_t lx = x[i] & 0xffffffffULL; |
| 290 | uint64_t hx = x[i] >> 32; |
| 291 | // hasCarry - A flag to indicate if there is a carry to the next digit. |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 292 | // hasCarry == 0, no carry |
| 293 | // hasCarry == 1, has carry |
| 294 | // hasCarry == 2, no carry and the calculation result == 0. |
| 295 | uint8_t hasCarry = 0; |
| 296 | dest[i] = carry + lx * ly; |
| 297 | // Determine if the add above introduces carry. |
| 298 | hasCarry = (dest[i] < carry) ? 1 : 0; |
| 299 | carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0); |
| 300 | // The upper limit of carry can be (2^32 - 1)(2^32 - 1) + |
| 301 | // (2^32 - 1) + 2^32 = 2^64. |
| 302 | hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); |
| 303 | |
| 304 | carry += (lx * hy) & 0xffffffffULL; |
| 305 | dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL); |
| 306 | carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) + |
| 307 | (carry >> 32) + ((lx * hy) >> 32) + hx * hy; |
| 308 | } |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 309 | return carry; |
| 310 | } |
| 311 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 312 | /// Multiplies integer array x by integer array y and stores the result into |
| 313 | /// the integer array dest. Note that dest's size must be >= xlen + ylen. |
| 314 | /// @brief Generalized multiplicate of integer arrays. |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 315 | static void mul(uint64_t dest[], uint64_t x[], uint32_t xlen, uint64_t y[], |
| 316 | uint32_t ylen) { |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 317 | dest[xlen] = mul_1(dest, x, xlen, y[0]); |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 318 | for (uint32_t i = 1; i < ylen; ++i) { |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 319 | uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32; |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 320 | uint64_t carry = 0, lx = 0, hx = 0; |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 321 | for (uint32_t j = 0; j < xlen; ++j) { |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 322 | lx = x[j] & 0xffffffffULL; |
| 323 | hx = x[j] >> 32; |
| 324 | // hasCarry - A flag to indicate if has carry. |
| 325 | // hasCarry == 0, no carry |
| 326 | // hasCarry == 1, has carry |
| 327 | // hasCarry == 2, no carry and the calculation result == 0. |
| 328 | uint8_t hasCarry = 0; |
| 329 | uint64_t resul = carry + lx * ly; |
| 330 | hasCarry = (resul < carry) ? 1 : 0; |
| 331 | carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32); |
| 332 | hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); |
| 333 | |
| 334 | carry += (lx * hy) & 0xffffffffULL; |
| 335 | resul = (carry << 32) | (resul & 0xffffffffULL); |
| 336 | dest[i+j] += resul; |
| 337 | carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+ |
| 338 | (carry >> 32) + (dest[i+j] < resul ? 1 : 0) + |
| 339 | ((lx * hy) >> 32) + hx * hy; |
| 340 | } |
| 341 | dest[i+xlen] = carry; |
| 342 | } |
| 343 | } |
| 344 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 345 | APInt& APInt::operator*=(const APInt& RHS) { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 346 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 347 | if (isSingleWord()) { |
Reid Spencer | 61eb180 | 2007-02-20 20:42:10 +0000 | [diff] [blame] | 348 | VAL *= RHS.VAL; |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 349 | clearUnusedBits(); |
| 350 | return *this; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 351 | } |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 352 | |
| 353 | // Get some bit facts about LHS and check for zero |
| 354 | uint32_t lhsBits = getActiveBits(); |
| 355 | uint32_t lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1; |
| 356 | if (!lhsWords) |
| 357 | // 0 * X ===> 0 |
| 358 | return *this; |
| 359 | |
| 360 | // Get some bit facts about RHS and check for zero |
| 361 | uint32_t rhsBits = RHS.getActiveBits(); |
| 362 | uint32_t rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1; |
| 363 | if (!rhsWords) { |
| 364 | // X * 0 ===> 0 |
| 365 | clear(); |
| 366 | return *this; |
| 367 | } |
| 368 | |
| 369 | // Allocate space for the result |
| 370 | uint32_t destWords = rhsWords + lhsWords; |
| 371 | uint64_t *dest = getMemory(destWords); |
| 372 | |
| 373 | // Perform the long multiply |
| 374 | mul(dest, pVal, lhsWords, RHS.pVal, rhsWords); |
| 375 | |
| 376 | // Copy result back into *this |
| 377 | clear(); |
| 378 | uint32_t wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords; |
| 379 | memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE); |
| 380 | |
| 381 | // delete dest array and return |
| 382 | delete[] dest; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 383 | return *this; |
| 384 | } |
| 385 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 386 | APInt& APInt::operator&=(const APInt& RHS) { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 387 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 388 | if (isSingleWord()) { |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 389 | VAL &= RHS.VAL; |
| 390 | return *this; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 391 | } |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 392 | uint32_t numWords = getNumWords(); |
| 393 | for (uint32_t i = 0; i < numWords; ++i) |
| 394 | pVal[i] &= RHS.pVal[i]; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 395 | return *this; |
| 396 | } |
| 397 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 398 | APInt& APInt::operator|=(const APInt& RHS) { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 399 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 400 | if (isSingleWord()) { |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 401 | VAL |= RHS.VAL; |
| 402 | return *this; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 403 | } |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 404 | uint32_t numWords = getNumWords(); |
| 405 | for (uint32_t i = 0; i < numWords; ++i) |
| 406 | pVal[i] |= RHS.pVal[i]; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 407 | return *this; |
| 408 | } |
| 409 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 410 | APInt& APInt::operator^=(const APInt& RHS) { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 411 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 412 | if (isSingleWord()) { |
Reid Spencer | f2c521c | 2007-02-18 06:39:42 +0000 | [diff] [blame] | 413 | VAL ^= RHS.VAL; |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 414 | this->clearUnusedBits(); |
Reid Spencer | f2c521c | 2007-02-18 06:39:42 +0000 | [diff] [blame] | 415 | return *this; |
| 416 | } |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 417 | uint32_t numWords = getNumWords(); |
| 418 | for (uint32_t i = 0; i < numWords; ++i) |
| 419 | pVal[i] ^= RHS.pVal[i]; |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 420 | return clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 421 | } |
| 422 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 423 | APInt APInt::operator&(const APInt& RHS) const { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 424 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 425 | if (isSingleWord()) |
| 426 | return APInt(getBitWidth(), VAL & RHS.VAL); |
| 427 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 428 | uint32_t numWords = getNumWords(); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 429 | uint64_t* val = getMemory(numWords); |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 430 | for (uint32_t i = 0; i < numWords; ++i) |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 431 | val[i] = pVal[i] & RHS.pVal[i]; |
| 432 | return APInt(val, getBitWidth()); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 433 | } |
| 434 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 435 | APInt APInt::operator|(const APInt& RHS) const { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 436 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 437 | if (isSingleWord()) |
| 438 | return APInt(getBitWidth(), VAL | RHS.VAL); |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 439 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 440 | uint32_t numWords = getNumWords(); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 441 | uint64_t *val = getMemory(numWords); |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 442 | for (uint32_t i = 0; i < numWords; ++i) |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 443 | val[i] = pVal[i] | RHS.pVal[i]; |
| 444 | return APInt(val, getBitWidth()); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 445 | } |
| 446 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 447 | APInt APInt::operator^(const APInt& RHS) const { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 448 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 449 | if (isSingleWord()) |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 450 | return APInt(BitWidth, VAL ^ RHS.VAL); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 451 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 452 | uint32_t numWords = getNumWords(); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 453 | uint64_t *val = getMemory(numWords); |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 454 | for (uint32_t i = 0; i < numWords; ++i) |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 455 | val[i] = pVal[i] ^ RHS.pVal[i]; |
| 456 | |
| 457 | // 0^0==1 so clear the high bits in case they got set. |
| 458 | return APInt(val, getBitWidth()).clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 459 | } |
| 460 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 461 | bool APInt::operator !() const { |
| 462 | if (isSingleWord()) |
| 463 | return !VAL; |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 464 | |
| 465 | for (uint32_t i = 0; i < getNumWords(); ++i) |
| 466 | if (pVal[i]) |
| 467 | return false; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 468 | return true; |
| 469 | } |
| 470 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 471 | APInt APInt::operator*(const APInt& RHS) const { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 472 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 473 | if (isSingleWord()) |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 474 | return APInt(BitWidth, VAL * RHS.VAL); |
Reid Spencer | 61eb180 | 2007-02-20 20:42:10 +0000 | [diff] [blame] | 475 | APInt Result(*this); |
| 476 | Result *= RHS; |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 477 | return Result.clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 478 | } |
| 479 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 480 | APInt APInt::operator+(const APInt& RHS) const { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 481 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 482 | if (isSingleWord()) |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 483 | return APInt(BitWidth, VAL + RHS.VAL); |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 484 | APInt Result(BitWidth, 0); |
| 485 | add(Result.pVal, this->pVal, RHS.pVal, getNumWords()); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 486 | return Result.clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 487 | } |
| 488 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 489 | APInt APInt::operator-(const APInt& RHS) const { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 490 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 491 | if (isSingleWord()) |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 492 | return APInt(BitWidth, VAL - RHS.VAL); |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 493 | APInt Result(BitWidth, 0); |
| 494 | sub(Result.pVal, this->pVal, RHS.pVal, getNumWords()); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 495 | return Result.clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 496 | } |
| 497 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 498 | bool APInt::operator[](uint32_t bitPosition) const { |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 499 | return (maskBit(bitPosition) & |
| 500 | (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 501 | } |
| 502 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 503 | bool APInt::operator==(const APInt& RHS) const { |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 504 | assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths"); |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 505 | if (isSingleWord()) |
| 506 | return VAL == RHS.VAL; |
| 507 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 508 | // Get some facts about the number of bits used in the two operands. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 509 | uint32_t n1 = getActiveBits(); |
| 510 | uint32_t n2 = RHS.getActiveBits(); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 511 | |
| 512 | // If the number of bits isn't the same, they aren't equal |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 513 | if (n1 != n2) |
| 514 | return false; |
| 515 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 516 | // If the number of bits fits in a word, we only need to compare the low word. |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 517 | if (n1 <= APINT_BITS_PER_WORD) |
| 518 | return pVal[0] == RHS.pVal[0]; |
| 519 | |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 520 | // Otherwise, compare everything |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 521 | for (int i = whichWord(n1 - 1); i >= 0; --i) |
| 522 | if (pVal[i] != RHS.pVal[i]) |
| 523 | return false; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 524 | return true; |
| 525 | } |
| 526 | |
Zhou Sheng | a3832fd | 2007-02-07 06:14:53 +0000 | [diff] [blame] | 527 | bool APInt::operator==(uint64_t Val) const { |
| 528 | if (isSingleWord()) |
| 529 | return VAL == Val; |
Reid Spencer | 54362ca | 2007-02-20 23:40:25 +0000 | [diff] [blame] | 530 | |
| 531 | uint32_t n = getActiveBits(); |
| 532 | if (n <= APINT_BITS_PER_WORD) |
| 533 | return pVal[0] == Val; |
| 534 | else |
| 535 | return false; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 536 | } |
| 537 | |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 538 | bool APInt::ult(const APInt& RHS) const { |
| 539 | assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); |
| 540 | if (isSingleWord()) |
| 541 | return VAL < RHS.VAL; |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 542 | |
| 543 | // Get active bit length of both operands |
| 544 | uint32_t n1 = getActiveBits(); |
| 545 | uint32_t n2 = RHS.getActiveBits(); |
| 546 | |
| 547 | // If magnitude of LHS is less than RHS, return true. |
| 548 | if (n1 < n2) |
| 549 | return true; |
| 550 | |
| 551 | // If magnitude of RHS is greather than LHS, return false. |
| 552 | if (n2 < n1) |
| 553 | return false; |
| 554 | |
| 555 | // If they bot fit in a word, just compare the low order word |
| 556 | if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD) |
| 557 | return pVal[0] < RHS.pVal[0]; |
| 558 | |
| 559 | // Otherwise, compare all words |
Reid Spencer | 1fa111e | 2007-02-27 18:23:40 +0000 | [diff] [blame] | 560 | uint32_t topWord = whichWord(std::max(n1,n2)-1); |
| 561 | for (int i = topWord; i >= 0; --i) { |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 562 | if (pVal[i] > RHS.pVal[i]) |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 563 | return false; |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 564 | if (pVal[i] < RHS.pVal[i]) |
| 565 | return true; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 566 | } |
| 567 | return false; |
| 568 | } |
| 569 | |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 570 | bool APInt::slt(const APInt& RHS) const { |
| 571 | assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 572 | if (isSingleWord()) { |
| 573 | int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth); |
| 574 | int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth); |
| 575 | return lhsSext < rhsSext; |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 576 | } |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 577 | |
| 578 | APInt lhs(*this); |
Reid Spencer | 1fa111e | 2007-02-27 18:23:40 +0000 | [diff] [blame] | 579 | APInt rhs(RHS); |
| 580 | bool lhsNeg = isNegative(); |
| 581 | bool rhsNeg = rhs.isNegative(); |
| 582 | if (lhsNeg) { |
| 583 | // Sign bit is set so perform two's complement to make it positive |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 584 | lhs.flip(); |
| 585 | lhs++; |
| 586 | } |
Reid Spencer | 1fa111e | 2007-02-27 18:23:40 +0000 | [diff] [blame] | 587 | if (rhsNeg) { |
| 588 | // Sign bit is set so perform two's complement to make it positive |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 589 | rhs.flip(); |
| 590 | rhs++; |
| 591 | } |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 592 | |
| 593 | // Now we have unsigned values to compare so do the comparison if necessary |
| 594 | // based on the negativeness of the values. |
Reid Spencer | 1fa111e | 2007-02-27 18:23:40 +0000 | [diff] [blame] | 595 | if (lhsNeg) |
| 596 | if (rhsNeg) |
| 597 | return lhs.ugt(rhs); |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 598 | else |
| 599 | return true; |
Reid Spencer | 1fa111e | 2007-02-27 18:23:40 +0000 | [diff] [blame] | 600 | else if (rhsNeg) |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 601 | return false; |
| 602 | else |
| 603 | return lhs.ult(rhs); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 604 | } |
| 605 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 606 | APInt& APInt::set(uint32_t bitPosition) { |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 607 | if (isSingleWord()) |
| 608 | VAL |= maskBit(bitPosition); |
| 609 | else |
| 610 | pVal[whichWord(bitPosition)] |= maskBit(bitPosition); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 611 | return *this; |
| 612 | } |
| 613 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 614 | APInt& APInt::set() { |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 615 | if (isSingleWord()) { |
| 616 | VAL = -1ULL; |
| 617 | return clearUnusedBits(); |
Zhou Sheng | b04973e | 2007-02-15 06:36:31 +0000 | [diff] [blame] | 618 | } |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 619 | |
| 620 | // Set all the bits in all the words. |
Zhou Sheng | 6dbe233 | 2007-03-21 04:34:37 +0000 | [diff] [blame] | 621 | for (uint32_t i = 0; i < getNumWords(); ++i) |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 622 | pVal[i] = -1ULL; |
| 623 | // Clear the unused ones |
| 624 | return clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 625 | } |
| 626 | |
| 627 | /// Set the given bit to 0 whose position is given as "bitPosition". |
| 628 | /// @brief Set a given bit to 0. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 629 | APInt& APInt::clear(uint32_t bitPosition) { |
| 630 | if (isSingleWord()) |
| 631 | VAL &= ~maskBit(bitPosition); |
| 632 | else |
| 633 | pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 634 | return *this; |
| 635 | } |
| 636 | |
| 637 | /// @brief Set every bit to 0. |
| 638 | APInt& APInt::clear() { |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 639 | if (isSingleWord()) |
| 640 | VAL = 0; |
Zhou Sheng | a3832fd | 2007-02-07 06:14:53 +0000 | [diff] [blame] | 641 | else |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 642 | memset(pVal, 0, getNumWords() * APINT_WORD_SIZE); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 643 | return *this; |
| 644 | } |
| 645 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 646 | /// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on |
| 647 | /// this APInt. |
| 648 | APInt APInt::operator~() const { |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 649 | APInt Result(*this); |
| 650 | Result.flip(); |
| 651 | return Result; |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 652 | } |
| 653 | |
| 654 | /// @brief Toggle every bit to its opposite value. |
| 655 | APInt& APInt::flip() { |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 656 | if (isSingleWord()) { |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 657 | VAL ^= -1ULL; |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 658 | return clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 659 | } |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 660 | for (uint32_t i = 0; i < getNumWords(); ++i) |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 661 | pVal[i] ^= -1ULL; |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 662 | return clearUnusedBits(); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 663 | } |
| 664 | |
| 665 | /// Toggle a given bit to its opposite value whose position is given |
| 666 | /// as "bitPosition". |
| 667 | /// @brief Toggles a given bit to its opposite value. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 668 | APInt& APInt::flip(uint32_t bitPosition) { |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 669 | assert(bitPosition < BitWidth && "Out of the bit-width range!"); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 670 | if ((*this)[bitPosition]) clear(bitPosition); |
| 671 | else set(bitPosition); |
| 672 | return *this; |
| 673 | } |
| 674 | |
Reid Spencer | 57ae4f5 | 2007-04-13 19:19:07 +0000 | [diff] [blame] | 675 | uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) { |
| 676 | assert(str != 0 && "Invalid value string"); |
| 677 | assert(slen > 0 && "Invalid string length"); |
| 678 | |
| 679 | // Each computation below needs to know if its negative |
| 680 | uint32_t isNegative = str[0] == '-'; |
| 681 | if (isNegative) { |
| 682 | slen--; |
| 683 | str++; |
| 684 | } |
| 685 | // For radixes of power-of-two values, the bits required is accurately and |
| 686 | // easily computed |
| 687 | if (radix == 2) |
| 688 | return slen + isNegative; |
| 689 | if (radix == 8) |
| 690 | return slen * 3 + isNegative; |
| 691 | if (radix == 16) |
| 692 | return slen * 4 + isNegative; |
| 693 | |
| 694 | // Otherwise it must be radix == 10, the hard case |
| 695 | assert(radix == 10 && "Invalid radix"); |
| 696 | |
| 697 | // This is grossly inefficient but accurate. We could probably do something |
| 698 | // with a computation of roughly slen*64/20 and then adjust by the value of |
| 699 | // the first few digits. But, I'm not sure how accurate that could be. |
| 700 | |
| 701 | // Compute a sufficient number of bits that is always large enough but might |
| 702 | // be too large. This avoids the assertion in the constructor. |
| 703 | uint32_t sufficient = slen*64/18; |
| 704 | |
| 705 | // Convert to the actual binary value. |
| 706 | APInt tmp(sufficient, str, slen, radix); |
| 707 | |
| 708 | // Compute how many bits are required. |
Reid Spencer | 0468ab3 | 2007-04-14 00:00:10 +0000 | [diff] [blame] | 709 | return isNegative + tmp.logBase2() + 1; |
Reid Spencer | 57ae4f5 | 2007-04-13 19:19:07 +0000 | [diff] [blame] | 710 | } |
| 711 | |
Reid Spencer | 794f472 | 2007-02-26 21:02:27 +0000 | [diff] [blame] | 712 | uint64_t APInt::getHashValue() const { |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 713 | // Put the bit width into the low order bits. |
| 714 | uint64_t hash = BitWidth; |
Reid Spencer | 794f472 | 2007-02-26 21:02:27 +0000 | [diff] [blame] | 715 | |
| 716 | // Add the sum of the words to the hash. |
| 717 | if (isSingleWord()) |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 718 | hash += VAL << 6; // clear separation of up to 64 bits |
Reid Spencer | 794f472 | 2007-02-26 21:02:27 +0000 | [diff] [blame] | 719 | else |
| 720 | for (uint32_t i = 0; i < getNumWords(); ++i) |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 721 | hash += pVal[i] << 6; // clear sepration of up to 64 bits |
Reid Spencer | 794f472 | 2007-02-26 21:02:27 +0000 | [diff] [blame] | 722 | return hash; |
| 723 | } |
| 724 | |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 725 | /// HiBits - This function returns the high "numBits" bits of this APInt. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 726 | APInt APInt::getHiBits(uint32_t numBits) const { |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 727 | return APIntOps::lshr(*this, BitWidth - numBits); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 728 | } |
| 729 | |
| 730 | /// LoBits - This function returns the low "numBits" bits of this APInt. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 731 | APInt APInt::getLoBits(uint32_t numBits) const { |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 732 | return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits), |
| 733 | BitWidth - numBits); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 734 | } |
| 735 | |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 736 | bool APInt::isPowerOf2() const { |
| 737 | return (!!*this) && !(*this & (*this - APInt(BitWidth,1))); |
| 738 | } |
| 739 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 740 | uint32_t APInt::countLeadingZeros() const { |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 741 | uint32_t Count = 0; |
Reid Spencer | e549c49 | 2007-02-21 00:29:48 +0000 | [diff] [blame] | 742 | if (isSingleWord()) |
| 743 | Count = CountLeadingZeros_64(VAL); |
| 744 | else { |
| 745 | for (uint32_t i = getNumWords(); i > 0u; --i) { |
| 746 | if (pVal[i-1] == 0) |
| 747 | Count += APINT_BITS_PER_WORD; |
| 748 | else { |
| 749 | Count += CountLeadingZeros_64(pVal[i-1]); |
| 750 | break; |
| 751 | } |
| 752 | } |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 753 | } |
Reid Spencer | ab2b2c8 | 2007-02-22 00:22:00 +0000 | [diff] [blame] | 754 | uint32_t remainder = BitWidth % APINT_BITS_PER_WORD; |
| 755 | if (remainder) |
| 756 | Count -= APINT_BITS_PER_WORD - remainder; |
Chris Lattner | 9e513ac | 2007-11-23 22:42:31 +0000 | [diff] [blame] | 757 | return std::min(Count, BitWidth); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 758 | } |
| 759 | |
Reid Spencer | 681dcd1 | 2007-02-27 21:59:26 +0000 | [diff] [blame] | 760 | static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) { |
| 761 | uint32_t Count = 0; |
| 762 | if (skip) |
| 763 | V <<= skip; |
| 764 | while (V && (V & (1ULL << 63))) { |
| 765 | Count++; |
| 766 | V <<= 1; |
| 767 | } |
| 768 | return Count; |
| 769 | } |
| 770 | |
| 771 | uint32_t APInt::countLeadingOnes() const { |
| 772 | if (isSingleWord()) |
| 773 | return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth); |
| 774 | |
| 775 | uint32_t highWordBits = BitWidth % APINT_BITS_PER_WORD; |
| 776 | uint32_t shift = (highWordBits == 0 ? 0 : APINT_BITS_PER_WORD - highWordBits); |
| 777 | int i = getNumWords() - 1; |
| 778 | uint32_t Count = countLeadingOnes_64(pVal[i], shift); |
| 779 | if (Count == highWordBits) { |
| 780 | for (i--; i >= 0; --i) { |
| 781 | if (pVal[i] == -1ULL) |
| 782 | Count += APINT_BITS_PER_WORD; |
| 783 | else { |
| 784 | Count += countLeadingOnes_64(pVal[i], 0); |
| 785 | break; |
| 786 | } |
| 787 | } |
| 788 | } |
| 789 | return Count; |
| 790 | } |
| 791 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 792 | uint32_t APInt::countTrailingZeros() const { |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 793 | if (isSingleWord()) |
Anton Korobeynikov | 97d3726 | 2007-12-24 11:16:47 +0000 | [diff] [blame] | 794 | return std::min(uint32_t(CountTrailingZeros_64(VAL)), BitWidth); |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 795 | uint32_t Count = 0; |
| 796 | uint32_t i = 0; |
| 797 | for (; i < getNumWords() && pVal[i] == 0; ++i) |
| 798 | Count += APINT_BITS_PER_WORD; |
| 799 | if (i < getNumWords()) |
| 800 | Count += CountTrailingZeros_64(pVal[i]); |
Chris Lattner | 5e55712 | 2007-11-23 22:36:25 +0000 | [diff] [blame] | 801 | return std::min(Count, BitWidth); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 802 | } |
| 803 | |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 804 | uint32_t APInt::countPopulation() const { |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 805 | if (isSingleWord()) |
| 806 | return CountPopulation_64(VAL); |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 807 | uint32_t Count = 0; |
| 808 | for (uint32_t i = 0; i < getNumWords(); ++i) |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 809 | Count += CountPopulation_64(pVal[i]); |
| 810 | return Count; |
| 811 | } |
| 812 | |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 813 | APInt APInt::byteSwap() const { |
| 814 | assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!"); |
| 815 | if (BitWidth == 16) |
Jeff Cohen | 09dfd8e | 2007-03-20 20:42:36 +0000 | [diff] [blame] | 816 | return APInt(BitWidth, ByteSwap_16(uint16_t(VAL))); |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 817 | else if (BitWidth == 32) |
Jeff Cohen | 09dfd8e | 2007-03-20 20:42:36 +0000 | [diff] [blame] | 818 | return APInt(BitWidth, ByteSwap_32(uint32_t(VAL))); |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 819 | else if (BitWidth == 48) { |
Jeff Cohen | 09dfd8e | 2007-03-20 20:42:36 +0000 | [diff] [blame] | 820 | uint32_t Tmp1 = uint32_t(VAL >> 16); |
Zhou Sheng | b04973e | 2007-02-15 06:36:31 +0000 | [diff] [blame] | 821 | Tmp1 = ByteSwap_32(Tmp1); |
Jeff Cohen | 09dfd8e | 2007-03-20 20:42:36 +0000 | [diff] [blame] | 822 | uint16_t Tmp2 = uint16_t(VAL); |
Zhou Sheng | b04973e | 2007-02-15 06:36:31 +0000 | [diff] [blame] | 823 | Tmp2 = ByteSwap_16(Tmp2); |
Jeff Cohen | 09dfd8e | 2007-03-20 20:42:36 +0000 | [diff] [blame] | 824 | return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1); |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 825 | } else if (BitWidth == 64) |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 826 | return APInt(BitWidth, ByteSwap_64(VAL)); |
Zhou Sheng | b04973e | 2007-02-15 06:36:31 +0000 | [diff] [blame] | 827 | else { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 828 | APInt Result(BitWidth, 0); |
Zhou Sheng | b04973e | 2007-02-15 06:36:31 +0000 | [diff] [blame] | 829 | char *pByte = (char*)Result.pVal; |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 830 | for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) { |
Zhou Sheng | b04973e | 2007-02-15 06:36:31 +0000 | [diff] [blame] | 831 | char Tmp = pByte[i]; |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 832 | pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i]; |
| 833 | pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp; |
Zhou Sheng | b04973e | 2007-02-15 06:36:31 +0000 | [diff] [blame] | 834 | } |
| 835 | return Result; |
| 836 | } |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 837 | } |
| 838 | |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 839 | APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1, |
| 840 | const APInt& API2) { |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 841 | APInt A = API1, B = API2; |
| 842 | while (!!B) { |
| 843 | APInt T = B; |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 844 | B = APIntOps::urem(A, B); |
Zhou Sheng | fd43dcf | 2007-02-06 03:00:16 +0000 | [diff] [blame] | 845 | A = T; |
| 846 | } |
| 847 | return A; |
| 848 | } |
Chris Lattner | 6ad4c14 | 2007-02-06 05:38:37 +0000 | [diff] [blame] | 849 | |
Reid Spencer | 1fa111e | 2007-02-27 18:23:40 +0000 | [diff] [blame] | 850 | APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) { |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 851 | union { |
| 852 | double D; |
| 853 | uint64_t I; |
| 854 | } T; |
| 855 | T.D = Double; |
Reid Spencer | 30f44f3 | 2007-02-27 01:28:10 +0000 | [diff] [blame] | 856 | |
| 857 | // Get the sign bit from the highest order bit |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 858 | bool isNeg = T.I >> 63; |
Reid Spencer | 30f44f3 | 2007-02-27 01:28:10 +0000 | [diff] [blame] | 859 | |
| 860 | // Get the 11-bit exponent and adjust for the 1023 bit bias |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 861 | int64_t exp = ((T.I >> 52) & 0x7ff) - 1023; |
Reid Spencer | 30f44f3 | 2007-02-27 01:28:10 +0000 | [diff] [blame] | 862 | |
| 863 | // If the exponent is negative, the value is < 0 so just return 0. |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 864 | if (exp < 0) |
Reid Spencer | ff60576 | 2007-02-28 01:30:08 +0000 | [diff] [blame] | 865 | return APInt(width, 0u); |
Reid Spencer | 30f44f3 | 2007-02-27 01:28:10 +0000 | [diff] [blame] | 866 | |
| 867 | // Extract the mantissa by clearing the top 12 bits (sign + exponent). |
| 868 | uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52; |
| 869 | |
| 870 | // If the exponent doesn't shift all bits out of the mantissa |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 871 | if (exp < 52) |
Reid Spencer | 1fa111e | 2007-02-27 18:23:40 +0000 | [diff] [blame] | 872 | return isNeg ? -APInt(width, mantissa >> (52 - exp)) : |
| 873 | APInt(width, mantissa >> (52 - exp)); |
| 874 | |
| 875 | // If the client didn't provide enough bits for us to shift the mantissa into |
| 876 | // then the result is undefined, just return 0 |
| 877 | if (width <= exp - 52) |
| 878 | return APInt(width, 0); |
Reid Spencer | 30f44f3 | 2007-02-27 01:28:10 +0000 | [diff] [blame] | 879 | |
| 880 | // Otherwise, we have to shift the mantissa bits up to the right location |
Reid Spencer | 1fa111e | 2007-02-27 18:23:40 +0000 | [diff] [blame] | 881 | APInt Tmp(width, mantissa); |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 882 | Tmp = Tmp.shl(exp - 52); |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 883 | return isNeg ? -Tmp : Tmp; |
| 884 | } |
| 885 | |
Reid Spencer | db3faa6 | 2007-02-13 22:41:58 +0000 | [diff] [blame] | 886 | /// RoundToDouble - This function convert this APInt to a double. |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 887 | /// The layout for double is as following (IEEE Standard 754): |
| 888 | /// -------------------------------------- |
| 889 | /// | Sign Exponent Fraction Bias | |
| 890 | /// |-------------------------------------- | |
| 891 | /// | 1[63] 11[62-52] 52[51-00] 1023 | |
| 892 | /// -------------------------------------- |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 893 | double APInt::roundToDouble(bool isSigned) const { |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 894 | |
| 895 | // Handle the simple case where the value is contained in one uint64_t. |
Reid Spencer | a58f058 | 2007-02-18 20:09:41 +0000 | [diff] [blame] | 896 | if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) { |
| 897 | if (isSigned) { |
| 898 | int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth); |
| 899 | return double(sext); |
| 900 | } else |
| 901 | return double(VAL); |
| 902 | } |
| 903 | |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 904 | // Determine if the value is negative. |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 905 | bool isNeg = isSigned ? (*this)[BitWidth-1] : false; |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 906 | |
| 907 | // Construct the absolute value if we're negative. |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 908 | APInt Tmp(isNeg ? -(*this) : (*this)); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 909 | |
| 910 | // Figure out how many bits we're using. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 911 | uint32_t n = Tmp.getActiveBits(); |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 912 | |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 913 | // The exponent (without bias normalization) is just the number of bits |
| 914 | // we are using. Note that the sign bit is gone since we constructed the |
| 915 | // absolute value. |
| 916 | uint64_t exp = n; |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 917 | |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 918 | // Return infinity for exponent overflow |
| 919 | if (exp > 1023) { |
| 920 | if (!isSigned || !isNeg) |
Jeff Cohen | 09dfd8e | 2007-03-20 20:42:36 +0000 | [diff] [blame] | 921 | return std::numeric_limits<double>::infinity(); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 922 | else |
Jeff Cohen | 09dfd8e | 2007-03-20 20:42:36 +0000 | [diff] [blame] | 923 | return -std::numeric_limits<double>::infinity(); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 924 | } |
| 925 | exp += 1023; // Increment for 1023 bias |
| 926 | |
| 927 | // Number of bits in mantissa is 52. To obtain the mantissa value, we must |
| 928 | // extract the high 52 bits from the correct words in pVal. |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 929 | uint64_t mantissa; |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 930 | unsigned hiWord = whichWord(n-1); |
| 931 | if (hiWord == 0) { |
| 932 | mantissa = Tmp.pVal[0]; |
| 933 | if (n > 52) |
| 934 | mantissa >>= n - 52; // shift down, we want the top 52 bits. |
| 935 | } else { |
| 936 | assert(hiWord > 0 && "huh?"); |
| 937 | uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD); |
| 938 | uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD); |
| 939 | mantissa = hibits | lobits; |
| 940 | } |
| 941 | |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 942 | // The leading bit of mantissa is implicit, so get rid of it. |
Reid Spencer | 443b570 | 2007-02-18 00:44:22 +0000 | [diff] [blame] | 943 | uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0; |
Zhou Sheng | d93f00c | 2007-02-12 20:02:55 +0000 | [diff] [blame] | 944 | union { |
| 945 | double D; |
| 946 | uint64_t I; |
| 947 | } T; |
| 948 | T.I = sign | (exp << 52) | mantissa; |
| 949 | return T.D; |
| 950 | } |
| 951 | |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 952 | // Truncate to new width. |
Reid Spencer | 9490077 | 2007-02-28 17:34:32 +0000 | [diff] [blame] | 953 | APInt &APInt::trunc(uint32_t width) { |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 954 | assert(width < BitWidth && "Invalid APInt Truncate request"); |
Reid Spencer | 9af1887 | 2007-12-11 06:53:58 +0000 | [diff] [blame] | 955 | assert(width >= MIN_INT_BITS && "Can't truncate to 0 bits"); |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 956 | uint32_t wordsBefore = getNumWords(); |
| 957 | BitWidth = width; |
| 958 | uint32_t wordsAfter = getNumWords(); |
| 959 | if (wordsBefore != wordsAfter) { |
| 960 | if (wordsAfter == 1) { |
| 961 | uint64_t *tmp = pVal; |
| 962 | VAL = pVal[0]; |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 963 | delete [] tmp; |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 964 | } else { |
| 965 | uint64_t *newVal = getClearedMemory(wordsAfter); |
| 966 | for (uint32_t i = 0; i < wordsAfter; ++i) |
| 967 | newVal[i] = pVal[i]; |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 968 | delete [] pVal; |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 969 | pVal = newVal; |
| 970 | } |
| 971 | } |
Reid Spencer | 9490077 | 2007-02-28 17:34:32 +0000 | [diff] [blame] | 972 | return clearUnusedBits(); |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 973 | } |
| 974 | |
| 975 | // Sign extend to a new width. |
Reid Spencer | 9490077 | 2007-02-28 17:34:32 +0000 | [diff] [blame] | 976 | APInt &APInt::sext(uint32_t width) { |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 977 | assert(width > BitWidth && "Invalid APInt SignExtend request"); |
Reid Spencer | 9af1887 | 2007-12-11 06:53:58 +0000 | [diff] [blame] | 978 | assert(width <= MAX_INT_BITS && "Too many bits"); |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 979 | // If the sign bit isn't set, this is the same as zext. |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 980 | if (!isNegative()) { |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 981 | zext(width); |
Reid Spencer | 9490077 | 2007-02-28 17:34:32 +0000 | [diff] [blame] | 982 | return *this; |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 983 | } |
| 984 | |
| 985 | // The sign bit is set. First, get some facts |
| 986 | uint32_t wordsBefore = getNumWords(); |
| 987 | uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD; |
| 988 | BitWidth = width; |
| 989 | uint32_t wordsAfter = getNumWords(); |
| 990 | |
| 991 | // Mask the high order word appropriately |
| 992 | if (wordsBefore == wordsAfter) { |
| 993 | uint32_t newWordBits = width % APINT_BITS_PER_WORD; |
| 994 | // The extension is contained to the wordsBefore-1th word. |
Reid Spencer | 36184ed | 2007-03-02 01:19:42 +0000 | [diff] [blame] | 995 | uint64_t mask = ~0ULL; |
| 996 | if (newWordBits) |
| 997 | mask >>= APINT_BITS_PER_WORD - newWordBits; |
| 998 | mask <<= wordBits; |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 999 | if (wordsBefore == 1) |
| 1000 | VAL |= mask; |
| 1001 | else |
| 1002 | pVal[wordsBefore-1] |= mask; |
Reid Spencer | 295e40a | 2007-03-01 23:30:25 +0000 | [diff] [blame] | 1003 | return clearUnusedBits(); |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 1004 | } |
| 1005 | |
Reid Spencer | f30b188 | 2007-02-25 23:54:00 +0000 | [diff] [blame] | 1006 | uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits; |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 1007 | uint64_t *newVal = getMemory(wordsAfter); |
| 1008 | if (wordsBefore == 1) |
| 1009 | newVal[0] = VAL | mask; |
| 1010 | else { |
| 1011 | for (uint32_t i = 0; i < wordsBefore; ++i) |
| 1012 | newVal[i] = pVal[i]; |
| 1013 | newVal[wordsBefore-1] |= mask; |
| 1014 | } |
| 1015 | for (uint32_t i = wordsBefore; i < wordsAfter; i++) |
| 1016 | newVal[i] = -1ULL; |
| 1017 | if (wordsBefore != 1) |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 1018 | delete [] pVal; |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 1019 | pVal = newVal; |
Reid Spencer | 9490077 | 2007-02-28 17:34:32 +0000 | [diff] [blame] | 1020 | return clearUnusedBits(); |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 1021 | } |
| 1022 | |
| 1023 | // Zero extend to a new width. |
Reid Spencer | 9490077 | 2007-02-28 17:34:32 +0000 | [diff] [blame] | 1024 | APInt &APInt::zext(uint32_t width) { |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 1025 | assert(width > BitWidth && "Invalid APInt ZeroExtend request"); |
Reid Spencer | 9af1887 | 2007-12-11 06:53:58 +0000 | [diff] [blame] | 1026 | assert(width <= MAX_INT_BITS && "Too many bits"); |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 1027 | uint32_t wordsBefore = getNumWords(); |
| 1028 | BitWidth = width; |
| 1029 | uint32_t wordsAfter = getNumWords(); |
| 1030 | if (wordsBefore != wordsAfter) { |
| 1031 | uint64_t *newVal = getClearedMemory(wordsAfter); |
| 1032 | if (wordsBefore == 1) |
| 1033 | newVal[0] = VAL; |
| 1034 | else |
| 1035 | for (uint32_t i = 0; i < wordsBefore; ++i) |
| 1036 | newVal[i] = pVal[i]; |
| 1037 | if (wordsBefore != 1) |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 1038 | delete [] pVal; |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 1039 | pVal = newVal; |
| 1040 | } |
Reid Spencer | 9490077 | 2007-02-28 17:34:32 +0000 | [diff] [blame] | 1041 | return *this; |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 1042 | } |
| 1043 | |
Reid Spencer | 68e2300 | 2007-03-01 17:15:32 +0000 | [diff] [blame] | 1044 | APInt &APInt::zextOrTrunc(uint32_t width) { |
| 1045 | if (BitWidth < width) |
| 1046 | return zext(width); |
| 1047 | if (BitWidth > width) |
| 1048 | return trunc(width); |
| 1049 | return *this; |
| 1050 | } |
| 1051 | |
| 1052 | APInt &APInt::sextOrTrunc(uint32_t width) { |
| 1053 | if (BitWidth < width) |
| 1054 | return sext(width); |
| 1055 | if (BitWidth > width) |
| 1056 | return trunc(width); |
| 1057 | return *this; |
| 1058 | } |
| 1059 | |
Zhou Sheng | ff4304f | 2007-02-09 07:48:24 +0000 | [diff] [blame] | 1060 | /// Arithmetic right-shift this APInt by shiftAmt. |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1061 | /// @brief Arithmetic right-shift function. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 1062 | APInt APInt::ashr(uint32_t shiftAmt) const { |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1063 | assert(shiftAmt <= BitWidth && "Invalid shift amount"); |
Reid Spencer | 46f9c94 | 2007-03-02 22:39:11 +0000 | [diff] [blame] | 1064 | // Handle a degenerate case |
| 1065 | if (shiftAmt == 0) |
| 1066 | return *this; |
| 1067 | |
| 1068 | // Handle single word shifts with built-in ashr |
Reid Spencer | 24c4a8f | 2007-02-25 01:56:07 +0000 | [diff] [blame] | 1069 | if (isSingleWord()) { |
| 1070 | if (shiftAmt == BitWidth) |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1071 | return APInt(BitWidth, 0); // undefined |
| 1072 | else { |
| 1073 | uint32_t SignBit = APINT_BITS_PER_WORD - BitWidth; |
Reid Spencer | 24c4a8f | 2007-02-25 01:56:07 +0000 | [diff] [blame] | 1074 | return APInt(BitWidth, |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1075 | (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt)); |
| 1076 | } |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1077 | } |
Reid Spencer | 24c4a8f | 2007-02-25 01:56:07 +0000 | [diff] [blame] | 1078 | |
Reid Spencer | 46f9c94 | 2007-03-02 22:39:11 +0000 | [diff] [blame] | 1079 | // If all the bits were shifted out, the result is, technically, undefined. |
| 1080 | // We return -1 if it was negative, 0 otherwise. We check this early to avoid |
| 1081 | // issues in the algorithm below. |
Chris Lattner | a5ae15e | 2007-05-03 18:15:36 +0000 | [diff] [blame] | 1082 | if (shiftAmt == BitWidth) { |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1083 | if (isNegative()) |
| 1084 | return APInt(BitWidth, -1ULL); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 1085 | else |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1086 | return APInt(BitWidth, 0); |
Chris Lattner | a5ae15e | 2007-05-03 18:15:36 +0000 | [diff] [blame] | 1087 | } |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1088 | |
| 1089 | // Create some space for the result. |
| 1090 | uint64_t * val = new uint64_t[getNumWords()]; |
| 1091 | |
Reid Spencer | 46f9c94 | 2007-03-02 22:39:11 +0000 | [diff] [blame] | 1092 | // Compute some values needed by the following shift algorithms |
| 1093 | uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word |
| 1094 | uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift |
| 1095 | uint32_t breakWord = getNumWords() - 1 - offset; // last word affected |
| 1096 | uint32_t bitsInWord = whichBit(BitWidth); // how many bits in last word? |
| 1097 | if (bitsInWord == 0) |
| 1098 | bitsInWord = APINT_BITS_PER_WORD; |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1099 | |
| 1100 | // If we are shifting whole words, just move whole words |
| 1101 | if (wordShift == 0) { |
Reid Spencer | 46f9c94 | 2007-03-02 22:39:11 +0000 | [diff] [blame] | 1102 | // Move the words containing significant bits |
| 1103 | for (uint32_t i = 0; i <= breakWord; ++i) |
| 1104 | val[i] = pVal[i+offset]; // move whole word |
| 1105 | |
| 1106 | // Adjust the top significant word for sign bit fill, if negative |
| 1107 | if (isNegative()) |
| 1108 | if (bitsInWord < APINT_BITS_PER_WORD) |
| 1109 | val[breakWord] |= ~0ULL << bitsInWord; // set high bits |
| 1110 | } else { |
| 1111 | // Shift the low order words |
| 1112 | for (uint32_t i = 0; i < breakWord; ++i) { |
| 1113 | // This combines the shifted corresponding word with the low bits from |
| 1114 | // the next word (shifted into this word's high bits). |
| 1115 | val[i] = (pVal[i+offset] >> wordShift) | |
| 1116 | (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); |
| 1117 | } |
| 1118 | |
| 1119 | // Shift the break word. In this case there are no bits from the next word |
| 1120 | // to include in this word. |
| 1121 | val[breakWord] = pVal[breakWord+offset] >> wordShift; |
| 1122 | |
| 1123 | // Deal with sign extenstion in the break word, and possibly the word before |
| 1124 | // it. |
Chris Lattner | a5ae15e | 2007-05-03 18:15:36 +0000 | [diff] [blame] | 1125 | if (isNegative()) { |
Reid Spencer | 46f9c94 | 2007-03-02 22:39:11 +0000 | [diff] [blame] | 1126 | if (wordShift > bitsInWord) { |
| 1127 | if (breakWord > 0) |
| 1128 | val[breakWord-1] |= |
| 1129 | ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord)); |
| 1130 | val[breakWord] |= ~0ULL; |
| 1131 | } else |
| 1132 | val[breakWord] |= (~0ULL << (bitsInWord - wordShift)); |
Chris Lattner | a5ae15e | 2007-05-03 18:15:36 +0000 | [diff] [blame] | 1133 | } |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1134 | } |
| 1135 | |
Reid Spencer | 46f9c94 | 2007-03-02 22:39:11 +0000 | [diff] [blame] | 1136 | // Remaining words are 0 or -1, just assign them. |
| 1137 | uint64_t fillValue = (isNegative() ? -1ULL : 0); |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1138 | for (uint32_t i = breakWord+1; i < getNumWords(); ++i) |
Reid Spencer | 46f9c94 | 2007-03-02 22:39:11 +0000 | [diff] [blame] | 1139 | val[i] = fillValue; |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1140 | return APInt(val, BitWidth).clearUnusedBits(); |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1141 | } |
| 1142 | |
Zhou Sheng | ff4304f | 2007-02-09 07:48:24 +0000 | [diff] [blame] | 1143 | /// Logical right-shift this APInt by shiftAmt. |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1144 | /// @brief Logical right-shift function. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 1145 | APInt APInt::lshr(uint32_t shiftAmt) const { |
Chris Lattner | a5ae15e | 2007-05-03 18:15:36 +0000 | [diff] [blame] | 1146 | if (isSingleWord()) { |
Reid Spencer | 24c4a8f | 2007-02-25 01:56:07 +0000 | [diff] [blame] | 1147 | if (shiftAmt == BitWidth) |
| 1148 | return APInt(BitWidth, 0); |
| 1149 | else |
| 1150 | return APInt(BitWidth, this->VAL >> shiftAmt); |
Chris Lattner | a5ae15e | 2007-05-03 18:15:36 +0000 | [diff] [blame] | 1151 | } |
Reid Spencer | 24c4a8f | 2007-02-25 01:56:07 +0000 | [diff] [blame] | 1152 | |
Reid Spencer | ba81c2b | 2007-02-26 01:19:48 +0000 | [diff] [blame] | 1153 | // If all the bits were shifted out, the result is 0. This avoids issues |
| 1154 | // with shifting by the size of the integer type, which produces undefined |
| 1155 | // results. We define these "undefined results" to always be 0. |
| 1156 | if (shiftAmt == BitWidth) |
| 1157 | return APInt(BitWidth, 0); |
| 1158 | |
Reid Spencer | 02ae8b7 | 2007-05-17 06:26:29 +0000 | [diff] [blame] | 1159 | // If none of the bits are shifted out, the result is *this. This avoids |
| 1160 | // issues with shifting byt he size of the integer type, which produces |
| 1161 | // undefined results in the code below. This is also an optimization. |
| 1162 | if (shiftAmt == 0) |
| 1163 | return *this; |
| 1164 | |
Reid Spencer | ba81c2b | 2007-02-26 01:19:48 +0000 | [diff] [blame] | 1165 | // Create some space for the result. |
| 1166 | uint64_t * val = new uint64_t[getNumWords()]; |
| 1167 | |
| 1168 | // If we are shifting less than a word, compute the shift with a simple carry |
| 1169 | if (shiftAmt < APINT_BITS_PER_WORD) { |
| 1170 | uint64_t carry = 0; |
| 1171 | for (int i = getNumWords()-1; i >= 0; --i) { |
Reid Spencer | af8fb19 | 2007-03-01 05:39:56 +0000 | [diff] [blame] | 1172 | val[i] = (pVal[i] >> shiftAmt) | carry; |
Reid Spencer | ba81c2b | 2007-02-26 01:19:48 +0000 | [diff] [blame] | 1173 | carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt); |
| 1174 | } |
| 1175 | return APInt(val, BitWidth).clearUnusedBits(); |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 1176 | } |
| 1177 | |
Reid Spencer | ba81c2b | 2007-02-26 01:19:48 +0000 | [diff] [blame] | 1178 | // Compute some values needed by the remaining shift algorithms |
| 1179 | uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; |
| 1180 | uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; |
| 1181 | |
| 1182 | // If we are shifting whole words, just move whole words |
| 1183 | if (wordShift == 0) { |
| 1184 | for (uint32_t i = 0; i < getNumWords() - offset; ++i) |
| 1185 | val[i] = pVal[i+offset]; |
| 1186 | for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++) |
| 1187 | val[i] = 0; |
| 1188 | return APInt(val,BitWidth).clearUnusedBits(); |
| 1189 | } |
| 1190 | |
| 1191 | // Shift the low order words |
| 1192 | uint32_t breakWord = getNumWords() - offset -1; |
| 1193 | for (uint32_t i = 0; i < breakWord; ++i) |
Reid Spencer | af8fb19 | 2007-03-01 05:39:56 +0000 | [diff] [blame] | 1194 | val[i] = (pVal[i+offset] >> wordShift) | |
| 1195 | (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); |
Reid Spencer | ba81c2b | 2007-02-26 01:19:48 +0000 | [diff] [blame] | 1196 | // Shift the break word. |
| 1197 | val[breakWord] = pVal[breakWord+offset] >> wordShift; |
| 1198 | |
| 1199 | // Remaining words are 0 |
| 1200 | for (uint32_t i = breakWord+1; i < getNumWords(); ++i) |
| 1201 | val[i] = 0; |
| 1202 | return APInt(val, BitWidth).clearUnusedBits(); |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1203 | } |
| 1204 | |
Zhou Sheng | ff4304f | 2007-02-09 07:48:24 +0000 | [diff] [blame] | 1205 | /// Left-shift this APInt by shiftAmt. |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1206 | /// @brief Left-shift function. |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 1207 | APInt APInt::shl(uint32_t shiftAmt) const { |
Reid Spencer | 5bce854 | 2007-02-24 20:19:37 +0000 | [diff] [blame] | 1208 | assert(shiftAmt <= BitWidth && "Invalid shift amount"); |
Reid Spencer | 8755380 | 2007-02-25 00:56:44 +0000 | [diff] [blame] | 1209 | if (isSingleWord()) { |
Reid Spencer | 5bce854 | 2007-02-24 20:19:37 +0000 | [diff] [blame] | 1210 | if (shiftAmt == BitWidth) |
Reid Spencer | 8755380 | 2007-02-25 00:56:44 +0000 | [diff] [blame] | 1211 | return APInt(BitWidth, 0); // avoid undefined shift results |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1212 | return APInt(BitWidth, VAL << shiftAmt); |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1213 | } |
Reid Spencer | 5bce854 | 2007-02-24 20:19:37 +0000 | [diff] [blame] | 1214 | |
Reid Spencer | 8755380 | 2007-02-25 00:56:44 +0000 | [diff] [blame] | 1215 | // If all the bits were shifted out, the result is 0. This avoids issues |
| 1216 | // with shifting by the size of the integer type, which produces undefined |
| 1217 | // results. We define these "undefined results" to always be 0. |
| 1218 | if (shiftAmt == BitWidth) |
| 1219 | return APInt(BitWidth, 0); |
| 1220 | |
Reid Spencer | 92c7283 | 2007-05-12 18:01:57 +0000 | [diff] [blame] | 1221 | // If none of the bits are shifted out, the result is *this. This avoids a |
| 1222 | // lshr by the words size in the loop below which can produce incorrect |
| 1223 | // results. It also avoids the expensive computation below for a common case. |
| 1224 | if (shiftAmt == 0) |
| 1225 | return *this; |
| 1226 | |
Reid Spencer | 8755380 | 2007-02-25 00:56:44 +0000 | [diff] [blame] | 1227 | // Create some space for the result. |
| 1228 | uint64_t * val = new uint64_t[getNumWords()]; |
| 1229 | |
| 1230 | // If we are shifting less than a word, do it the easy way |
| 1231 | if (shiftAmt < APINT_BITS_PER_WORD) { |
| 1232 | uint64_t carry = 0; |
Reid Spencer | 8755380 | 2007-02-25 00:56:44 +0000 | [diff] [blame] | 1233 | for (uint32_t i = 0; i < getNumWords(); i++) { |
| 1234 | val[i] = pVal[i] << shiftAmt | carry; |
| 1235 | carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt); |
| 1236 | } |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 1237 | return APInt(val, BitWidth).clearUnusedBits(); |
Reid Spencer | 5bce854 | 2007-02-24 20:19:37 +0000 | [diff] [blame] | 1238 | } |
| 1239 | |
Reid Spencer | 8755380 | 2007-02-25 00:56:44 +0000 | [diff] [blame] | 1240 | // Compute some values needed by the remaining shift algorithms |
| 1241 | uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; |
| 1242 | uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; |
| 1243 | |
| 1244 | // If we are shifting whole words, just move whole words |
| 1245 | if (wordShift == 0) { |
| 1246 | for (uint32_t i = 0; i < offset; i++) |
| 1247 | val[i] = 0; |
| 1248 | for (uint32_t i = offset; i < getNumWords(); i++) |
| 1249 | val[i] = pVal[i-offset]; |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 1250 | return APInt(val,BitWidth).clearUnusedBits(); |
Reid Spencer | 5bce854 | 2007-02-24 20:19:37 +0000 | [diff] [blame] | 1251 | } |
Reid Spencer | 8755380 | 2007-02-25 00:56:44 +0000 | [diff] [blame] | 1252 | |
| 1253 | // Copy whole words from this to Result. |
| 1254 | uint32_t i = getNumWords() - 1; |
| 1255 | for (; i > offset; --i) |
| 1256 | val[i] = pVal[i-offset] << wordShift | |
| 1257 | pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift); |
Reid Spencer | 438d71e | 2007-02-25 01:08:58 +0000 | [diff] [blame] | 1258 | val[offset] = pVal[0] << wordShift; |
Reid Spencer | 8755380 | 2007-02-25 00:56:44 +0000 | [diff] [blame] | 1259 | for (i = 0; i < offset; ++i) |
| 1260 | val[i] = 0; |
Reid Spencer | 5d0d05c | 2007-02-25 19:32:03 +0000 | [diff] [blame] | 1261 | return APInt(val, BitWidth).clearUnusedBits(); |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1262 | } |
| 1263 | |
Reid Spencer | 19dc32a | 2007-05-13 23:44:59 +0000 | [diff] [blame] | 1264 | APInt APInt::rotl(uint32_t rotateAmt) const { |
Reid Spencer | 69944e8 | 2007-05-14 00:15:28 +0000 | [diff] [blame] | 1265 | if (rotateAmt == 0) |
| 1266 | return *this; |
Reid Spencer | 19dc32a | 2007-05-13 23:44:59 +0000 | [diff] [blame] | 1267 | // Don't get too fancy, just use existing shift/or facilities |
| 1268 | APInt hi(*this); |
| 1269 | APInt lo(*this); |
| 1270 | hi.shl(rotateAmt); |
| 1271 | lo.lshr(BitWidth - rotateAmt); |
| 1272 | return hi | lo; |
| 1273 | } |
| 1274 | |
| 1275 | APInt APInt::rotr(uint32_t rotateAmt) const { |
Reid Spencer | 69944e8 | 2007-05-14 00:15:28 +0000 | [diff] [blame] | 1276 | if (rotateAmt == 0) |
| 1277 | return *this; |
Reid Spencer | 19dc32a | 2007-05-13 23:44:59 +0000 | [diff] [blame] | 1278 | // Don't get too fancy, just use existing shift/or facilities |
| 1279 | APInt hi(*this); |
| 1280 | APInt lo(*this); |
| 1281 | lo.lshr(rotateAmt); |
| 1282 | hi.shl(BitWidth - rotateAmt); |
| 1283 | return hi | lo; |
| 1284 | } |
Reid Spencer | af8fb19 | 2007-03-01 05:39:56 +0000 | [diff] [blame] | 1285 | |
| 1286 | // Square Root - this method computes and returns the square root of "this". |
| 1287 | // Three mechanisms are used for computation. For small values (<= 5 bits), |
| 1288 | // a table lookup is done. This gets some performance for common cases. For |
| 1289 | // values using less than 52 bits, the value is converted to double and then |
| 1290 | // the libc sqrt function is called. The result is rounded and then converted |
| 1291 | // back to a uint64_t which is then used to construct the result. Finally, |
| 1292 | // the Babylonian method for computing square roots is used. |
| 1293 | APInt APInt::sqrt() const { |
| 1294 | |
| 1295 | // Determine the magnitude of the value. |
| 1296 | uint32_t magnitude = getActiveBits(); |
| 1297 | |
| 1298 | // Use a fast table for some small values. This also gets rid of some |
| 1299 | // rounding errors in libc sqrt for small values. |
| 1300 | if (magnitude <= 5) { |
Reid Spencer | 4e1e87f | 2007-03-01 17:47:31 +0000 | [diff] [blame] | 1301 | static const uint8_t results[32] = { |
Reid Spencer | b5ca2cd | 2007-03-01 06:23:32 +0000 | [diff] [blame] | 1302 | /* 0 */ 0, |
| 1303 | /* 1- 2 */ 1, 1, |
| 1304 | /* 3- 6 */ 2, 2, 2, 2, |
| 1305 | /* 7-12 */ 3, 3, 3, 3, 3, 3, |
| 1306 | /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4, |
| 1307 | /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, |
| 1308 | /* 31 */ 6 |
| 1309 | }; |
| 1310 | return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]); |
Reid Spencer | af8fb19 | 2007-03-01 05:39:56 +0000 | [diff] [blame] | 1311 | } |
| 1312 | |
| 1313 | // If the magnitude of the value fits in less than 52 bits (the precision of |
| 1314 | // an IEEE double precision floating point value), then we can use the |
| 1315 | // libc sqrt function which will probably use a hardware sqrt computation. |
| 1316 | // This should be faster than the algorithm below. |
Jeff Cohen | ca5183d | 2007-03-05 00:00:42 +0000 | [diff] [blame] | 1317 | if (magnitude < 52) { |
| 1318 | #ifdef _MSC_VER |
| 1319 | // Amazingly, VC++ doesn't have round(). |
| 1320 | return APInt(BitWidth, |
| 1321 | uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5); |
| 1322 | #else |
Reid Spencer | af8fb19 | 2007-03-01 05:39:56 +0000 | [diff] [blame] | 1323 | return APInt(BitWidth, |
| 1324 | uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0]))))); |
Jeff Cohen | ca5183d | 2007-03-05 00:00:42 +0000 | [diff] [blame] | 1325 | #endif |
| 1326 | } |
Reid Spencer | af8fb19 | 2007-03-01 05:39:56 +0000 | [diff] [blame] | 1327 | |
| 1328 | // Okay, all the short cuts are exhausted. We must compute it. The following |
| 1329 | // is a classical Babylonian method for computing the square root. This code |
| 1330 | // was adapted to APINt from a wikipedia article on such computations. |
| 1331 | // See http://www.wikipedia.org/ and go to the page named |
| 1332 | // Calculate_an_integer_square_root. |
| 1333 | uint32_t nbits = BitWidth, i = 4; |
| 1334 | APInt testy(BitWidth, 16); |
| 1335 | APInt x_old(BitWidth, 1); |
| 1336 | APInt x_new(BitWidth, 0); |
| 1337 | APInt two(BitWidth, 2); |
| 1338 | |
| 1339 | // Select a good starting value using binary logarithms. |
| 1340 | for (;; i += 2, testy = testy.shl(2)) |
| 1341 | if (i >= nbits || this->ule(testy)) { |
| 1342 | x_old = x_old.shl(i / 2); |
| 1343 | break; |
| 1344 | } |
| 1345 | |
| 1346 | // Use the Babylonian method to arrive at the integer square root: |
| 1347 | for (;;) { |
| 1348 | x_new = (this->udiv(x_old) + x_old).udiv(two); |
| 1349 | if (x_old.ule(x_new)) |
| 1350 | break; |
| 1351 | x_old = x_new; |
| 1352 | } |
| 1353 | |
| 1354 | // Make sure we return the closest approximation |
Reid Spencer | f09aef7 | 2007-03-02 04:21:55 +0000 | [diff] [blame] | 1355 | // NOTE: The rounding calculation below is correct. It will produce an |
| 1356 | // off-by-one discrepancy with results from pari/gp. That discrepancy has been |
| 1357 | // determined to be a rounding issue with pari/gp as it begins to use a |
| 1358 | // floating point representation after 192 bits. There are no discrepancies |
| 1359 | // between this algorithm and pari/gp for bit widths < 192 bits. |
Reid Spencer | af8fb19 | 2007-03-01 05:39:56 +0000 | [diff] [blame] | 1360 | APInt square(x_old * x_old); |
| 1361 | APInt nextSquare((x_old + 1) * (x_old +1)); |
| 1362 | if (this->ult(square)) |
| 1363 | return x_old; |
Reid Spencer | f09aef7 | 2007-03-02 04:21:55 +0000 | [diff] [blame] | 1364 | else if (this->ule(nextSquare)) { |
| 1365 | APInt midpoint((nextSquare - square).udiv(two)); |
| 1366 | APInt offset(*this - square); |
| 1367 | if (offset.ult(midpoint)) |
Reid Spencer | af8fb19 | 2007-03-01 05:39:56 +0000 | [diff] [blame] | 1368 | return x_old; |
Reid Spencer | f09aef7 | 2007-03-02 04:21:55 +0000 | [diff] [blame] | 1369 | else |
| 1370 | return x_old + 1; |
| 1371 | } else |
Reid Spencer | af8fb19 | 2007-03-01 05:39:56 +0000 | [diff] [blame] | 1372 | assert(0 && "Error in APInt::sqrt computation"); |
| 1373 | return x_old + 1; |
| 1374 | } |
| 1375 | |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1376 | /// Implementation of Knuth's Algorithm D (Division of nonnegative integers) |
| 1377 | /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The |
| 1378 | /// variables here have the same names as in the algorithm. Comments explain |
| 1379 | /// the algorithm and any deviation from it. |
| 1380 | static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r, |
| 1381 | uint32_t m, uint32_t n) { |
| 1382 | assert(u && "Must provide dividend"); |
| 1383 | assert(v && "Must provide divisor"); |
| 1384 | assert(q && "Must provide quotient"); |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1385 | assert(u != v && u != q && v != q && "Must us different memory"); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1386 | assert(n>1 && "n must be > 1"); |
| 1387 | |
| 1388 | // Knuth uses the value b as the base of the number system. In our case b |
| 1389 | // is 2^31 so we just set it to -1u. |
| 1390 | uint64_t b = uint64_t(1) << 32; |
| 1391 | |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1392 | DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n'); |
| 1393 | DEBUG(cerr << "KnuthDiv: original:"); |
| 1394 | DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]); |
| 1395 | DEBUG(cerr << " by"); |
| 1396 | DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]); |
| 1397 | DEBUG(cerr << '\n'); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1398 | // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of |
| 1399 | // u and v by d. Note that we have taken Knuth's advice here to use a power |
| 1400 | // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of |
| 1401 | // 2 allows us to shift instead of multiply and it is easy to determine the |
| 1402 | // shift amount from the leading zeros. We are basically normalizing the u |
| 1403 | // and v so that its high bits are shifted to the top of v's range without |
| 1404 | // overflow. Note that this can require an extra word in u so that u must |
| 1405 | // be of length m+n+1. |
| 1406 | uint32_t shift = CountLeadingZeros_32(v[n-1]); |
| 1407 | uint32_t v_carry = 0; |
| 1408 | uint32_t u_carry = 0; |
| 1409 | if (shift) { |
| 1410 | for (uint32_t i = 0; i < m+n; ++i) { |
| 1411 | uint32_t u_tmp = u[i] >> (32 - shift); |
| 1412 | u[i] = (u[i] << shift) | u_carry; |
| 1413 | u_carry = u_tmp; |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 1414 | } |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1415 | for (uint32_t i = 0; i < n; ++i) { |
| 1416 | uint32_t v_tmp = v[i] >> (32 - shift); |
| 1417 | v[i] = (v[i] << shift) | v_carry; |
| 1418 | v_carry = v_tmp; |
| 1419 | } |
| 1420 | } |
| 1421 | u[m+n] = u_carry; |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1422 | DEBUG(cerr << "KnuthDiv: normal:"); |
| 1423 | DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]); |
| 1424 | DEBUG(cerr << " by"); |
| 1425 | DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]); |
| 1426 | DEBUG(cerr << '\n'); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1427 | |
| 1428 | // D2. [Initialize j.] Set j to m. This is the loop counter over the places. |
| 1429 | int j = m; |
| 1430 | do { |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1431 | DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n'); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1432 | // D3. [Calculate q'.]. |
| 1433 | // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q') |
| 1434 | // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r') |
| 1435 | // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease |
| 1436 | // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test |
| 1437 | // on v[n-2] determines at high speed most of the cases in which the trial |
| 1438 | // value qp is one too large, and it eliminates all cases where qp is two |
| 1439 | // too large. |
Reid Spencer | 9290463 | 2007-02-23 01:57:13 +0000 | [diff] [blame] | 1440 | uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]); |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1441 | DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n'); |
Reid Spencer | 9290463 | 2007-02-23 01:57:13 +0000 | [diff] [blame] | 1442 | uint64_t qp = dividend / v[n-1]; |
| 1443 | uint64_t rp = dividend % v[n-1]; |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1444 | if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) { |
| 1445 | qp--; |
| 1446 | rp += v[n-1]; |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 1447 | if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2])) |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1448 | qp--; |
Reid Spencer | 9290463 | 2007-02-23 01:57:13 +0000 | [diff] [blame] | 1449 | } |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1450 | DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n'); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1451 | |
Reid Spencer | 9290463 | 2007-02-23 01:57:13 +0000 | [diff] [blame] | 1452 | // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with |
| 1453 | // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation |
| 1454 | // consists of a simple multiplication by a one-place number, combined with |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 1455 | // a subtraction. |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1456 | bool isNeg = false; |
Reid Spencer | 9290463 | 2007-02-23 01:57:13 +0000 | [diff] [blame] | 1457 | for (uint32_t i = 0; i < n; ++i) { |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 1458 | uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32); |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1459 | uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]); |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 1460 | bool borrow = subtrahend > u_tmp; |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1461 | DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 1462 | << ", subtrahend == " << subtrahend |
| 1463 | << ", borrow = " << borrow << '\n'); |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1464 | |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 1465 | uint64_t result = u_tmp - subtrahend; |
| 1466 | uint32_t k = j + i; |
| 1467 | u[k++] = result & (b-1); // subtract low word |
| 1468 | u[k++] = result >> 32; // subtract high word |
| 1469 | while (borrow && k <= m+n) { // deal with borrow to the left |
| 1470 | borrow = u[k] == 0; |
| 1471 | u[k]--; |
| 1472 | k++; |
| 1473 | } |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1474 | isNeg |= borrow; |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 1475 | DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " << |
| 1476 | u[j+i+1] << '\n'); |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1477 | } |
| 1478 | DEBUG(cerr << "KnuthDiv: after subtraction:"); |
| 1479 | DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]); |
| 1480 | DEBUG(cerr << '\n'); |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 1481 | // The digits (u[j+n]...u[j]) should be kept positive; if the result of |
| 1482 | // this step is actually negative, (u[j+n]...u[j]) should be left as the |
| 1483 | // true value plus b**(n+1), namely as the b's complement of |
Reid Spencer | 9290463 | 2007-02-23 01:57:13 +0000 | [diff] [blame] | 1484 | // the true value, and a "borrow" to the left should be remembered. |
| 1485 | // |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1486 | if (isNeg) { |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 1487 | bool carry = true; // true because b's complement is "complement + 1" |
| 1488 | for (uint32_t i = 0; i <= m+n; ++i) { |
| 1489 | u[i] = ~u[i] + carry; // b's complement |
| 1490 | carry = carry && u[i] == 0; |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1491 | } |
Reid Spencer | 9290463 | 2007-02-23 01:57:13 +0000 | [diff] [blame] | 1492 | } |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1493 | DEBUG(cerr << "KnuthDiv: after complement:"); |
| 1494 | DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]); |
| 1495 | DEBUG(cerr << '\n'); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1496 | |
| 1497 | // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was |
| 1498 | // negative, go to step D6; otherwise go on to step D7. |
| 1499 | q[j] = qp; |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1500 | if (isNeg) { |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1501 | // D6. [Add back]. The probability that this step is necessary is very |
| 1502 | // small, on the order of only 2/b. Make sure that test data accounts for |
Reid Spencer | 9290463 | 2007-02-23 01:57:13 +0000 | [diff] [blame] | 1503 | // this possibility. Decrease q[j] by 1 |
| 1504 | q[j]--; |
| 1505 | // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]). |
| 1506 | // A carry will occur to the left of u[j+n], and it should be ignored |
| 1507 | // since it cancels with the borrow that occurred in D4. |
| 1508 | bool carry = false; |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1509 | for (uint32_t i = 0; i < n; i++) { |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1510 | uint32_t limit = std::min(u[j+i],v[i]); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1511 | u[j+i] += v[i] + carry; |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1512 | carry = u[j+i] < limit || (carry && u[j+i] == limit); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1513 | } |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1514 | u[j+n] += carry; |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1515 | } |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1516 | DEBUG(cerr << "KnuthDiv: after correction:"); |
| 1517 | DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]); |
| 1518 | DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n'); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1519 | |
Reid Spencer | 9290463 | 2007-02-23 01:57:13 +0000 | [diff] [blame] | 1520 | // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3. |
| 1521 | } while (--j >= 0); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1522 | |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1523 | DEBUG(cerr << "KnuthDiv: quotient:"); |
| 1524 | DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]); |
| 1525 | DEBUG(cerr << '\n'); |
| 1526 | |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1527 | // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired |
| 1528 | // remainder may be obtained by dividing u[...] by d. If r is non-null we |
| 1529 | // compute the remainder (urem uses this). |
| 1530 | if (r) { |
| 1531 | // The value d is expressed by the "shift" value above since we avoided |
| 1532 | // multiplication by d by using a shift left. So, all we have to do is |
| 1533 | // shift right here. In order to mak |
Reid Spencer | 1050ec5 | 2007-02-24 20:38:01 +0000 | [diff] [blame] | 1534 | if (shift) { |
| 1535 | uint32_t carry = 0; |
| 1536 | DEBUG(cerr << "KnuthDiv: remainder:"); |
| 1537 | for (int i = n-1; i >= 0; i--) { |
| 1538 | r[i] = (u[i] >> shift) | carry; |
| 1539 | carry = u[i] << (32 - shift); |
| 1540 | DEBUG(cerr << " " << r[i]); |
| 1541 | } |
| 1542 | } else { |
| 1543 | for (int i = n-1; i >= 0; i--) { |
| 1544 | r[i] = u[i]; |
| 1545 | DEBUG(cerr << " " << r[i]); |
| 1546 | } |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1547 | } |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1548 | DEBUG(cerr << '\n'); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1549 | } |
Reid Spencer | 9d6c919 | 2007-02-24 03:58:46 +0000 | [diff] [blame] | 1550 | DEBUG(cerr << std::setbase(10) << '\n'); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1551 | } |
| 1552 | |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1553 | void APInt::divide(const APInt LHS, uint32_t lhsWords, |
| 1554 | const APInt &RHS, uint32_t rhsWords, |
| 1555 | APInt *Quotient, APInt *Remainder) |
| 1556 | { |
| 1557 | assert(lhsWords >= rhsWords && "Fractional result"); |
| 1558 | |
| 1559 | // First, compose the values into an array of 32-bit words instead of |
| 1560 | // 64-bit words. This is a necessity of both the "short division" algorithm |
| 1561 | // and the the Knuth "classical algorithm" which requires there to be native |
| 1562 | // operations for +, -, and * on an m bit value with an m*2 bit result. We |
| 1563 | // can't use 64-bit operands here because we don't have native results of |
| 1564 | // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't |
| 1565 | // work on large-endian machines. |
| 1566 | uint64_t mask = ~0ull >> (sizeof(uint32_t)*8); |
| 1567 | uint32_t n = rhsWords * 2; |
| 1568 | uint32_t m = (lhsWords * 2) - n; |
Reid Spencer | 24c4a8f | 2007-02-25 01:56:07 +0000 | [diff] [blame] | 1569 | |
| 1570 | // Allocate space for the temporary values we need either on the stack, if |
| 1571 | // it will fit, or on the heap if it won't. |
| 1572 | uint32_t SPACE[128]; |
| 1573 | uint32_t *U = 0; |
| 1574 | uint32_t *V = 0; |
| 1575 | uint32_t *Q = 0; |
| 1576 | uint32_t *R = 0; |
| 1577 | if ((Remainder?4:3)*n+2*m+1 <= 128) { |
| 1578 | U = &SPACE[0]; |
| 1579 | V = &SPACE[m+n+1]; |
| 1580 | Q = &SPACE[(m+n+1) + n]; |
| 1581 | if (Remainder) |
| 1582 | R = &SPACE[(m+n+1) + n + (m+n)]; |
| 1583 | } else { |
| 1584 | U = new uint32_t[m + n + 1]; |
| 1585 | V = new uint32_t[n]; |
| 1586 | Q = new uint32_t[m+n]; |
| 1587 | if (Remainder) |
| 1588 | R = new uint32_t[n]; |
| 1589 | } |
| 1590 | |
| 1591 | // Initialize the dividend |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1592 | memset(U, 0, (m+n+1)*sizeof(uint32_t)); |
| 1593 | for (unsigned i = 0; i < lhsWords; ++i) { |
Reid Spencer | 15aab8a | 2007-02-22 00:58:45 +0000 | [diff] [blame] | 1594 | uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1595 | U[i * 2] = tmp & mask; |
| 1596 | U[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8); |
| 1597 | } |
| 1598 | U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm. |
| 1599 | |
Reid Spencer | 24c4a8f | 2007-02-25 01:56:07 +0000 | [diff] [blame] | 1600 | // Initialize the divisor |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1601 | memset(V, 0, (n)*sizeof(uint32_t)); |
| 1602 | for (unsigned i = 0; i < rhsWords; ++i) { |
Reid Spencer | 15aab8a | 2007-02-22 00:58:45 +0000 | [diff] [blame] | 1603 | uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1604 | V[i * 2] = tmp & mask; |
| 1605 | V[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8); |
| 1606 | } |
| 1607 | |
Reid Spencer | 24c4a8f | 2007-02-25 01:56:07 +0000 | [diff] [blame] | 1608 | // initialize the quotient and remainder |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1609 | memset(Q, 0, (m+n) * sizeof(uint32_t)); |
Reid Spencer | 24c4a8f | 2007-02-25 01:56:07 +0000 | [diff] [blame] | 1610 | if (Remainder) |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1611 | memset(R, 0, n * sizeof(uint32_t)); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1612 | |
| 1613 | // Now, adjust m and n for the Knuth division. n is the number of words in |
| 1614 | // the divisor. m is the number of words by which the dividend exceeds the |
| 1615 | // divisor (i.e. m+n is the length of the dividend). These sizes must not |
| 1616 | // contain any zero words or the Knuth algorithm fails. |
| 1617 | for (unsigned i = n; i > 0 && V[i-1] == 0; i--) { |
| 1618 | n--; |
| 1619 | m++; |
| 1620 | } |
| 1621 | for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--) |
| 1622 | m--; |
| 1623 | |
| 1624 | // If we're left with only a single word for the divisor, Knuth doesn't work |
| 1625 | // so we implement the short division algorithm here. This is much simpler |
| 1626 | // and faster because we are certain that we can divide a 64-bit quantity |
| 1627 | // by a 32-bit quantity at hardware speed and short division is simply a |
| 1628 | // series of such operations. This is just like doing short division but we |
| 1629 | // are using base 2^32 instead of base 10. |
| 1630 | assert(n != 0 && "Divide by zero?"); |
| 1631 | if (n == 1) { |
| 1632 | uint32_t divisor = V[0]; |
| 1633 | uint32_t remainder = 0; |
| 1634 | for (int i = m+n-1; i >= 0; i--) { |
| 1635 | uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i]; |
| 1636 | if (partial_dividend == 0) { |
| 1637 | Q[i] = 0; |
| 1638 | remainder = 0; |
| 1639 | } else if (partial_dividend < divisor) { |
| 1640 | Q[i] = 0; |
| 1641 | remainder = partial_dividend; |
| 1642 | } else if (partial_dividend == divisor) { |
| 1643 | Q[i] = 1; |
| 1644 | remainder = 0; |
| 1645 | } else { |
| 1646 | Q[i] = partial_dividend / divisor; |
| 1647 | remainder = partial_dividend - (Q[i] * divisor); |
| 1648 | } |
| 1649 | } |
| 1650 | if (R) |
| 1651 | R[0] = remainder; |
| 1652 | } else { |
| 1653 | // Now we're ready to invoke the Knuth classical divide algorithm. In this |
| 1654 | // case n > 1. |
| 1655 | KnuthDiv(U, V, Q, R, m, n); |
| 1656 | } |
| 1657 | |
| 1658 | // If the caller wants the quotient |
| 1659 | if (Quotient) { |
| 1660 | // Set up the Quotient value's memory. |
| 1661 | if (Quotient->BitWidth != LHS.BitWidth) { |
| 1662 | if (Quotient->isSingleWord()) |
| 1663 | Quotient->VAL = 0; |
| 1664 | else |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 1665 | delete [] Quotient->pVal; |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1666 | Quotient->BitWidth = LHS.BitWidth; |
| 1667 | if (!Quotient->isSingleWord()) |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 1668 | Quotient->pVal = getClearedMemory(Quotient->getNumWords()); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1669 | } else |
| 1670 | Quotient->clear(); |
| 1671 | |
| 1672 | // The quotient is in Q. Reconstitute the quotient into Quotient's low |
| 1673 | // order words. |
| 1674 | if (lhsWords == 1) { |
| 1675 | uint64_t tmp = |
| 1676 | uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2)); |
| 1677 | if (Quotient->isSingleWord()) |
| 1678 | Quotient->VAL = tmp; |
| 1679 | else |
| 1680 | Quotient->pVal[0] = tmp; |
| 1681 | } else { |
| 1682 | assert(!Quotient->isSingleWord() && "Quotient APInt not large enough"); |
| 1683 | for (unsigned i = 0; i < lhsWords; ++i) |
| 1684 | Quotient->pVal[i] = |
| 1685 | uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2)); |
| 1686 | } |
| 1687 | } |
| 1688 | |
| 1689 | // If the caller wants the remainder |
| 1690 | if (Remainder) { |
| 1691 | // Set up the Remainder value's memory. |
| 1692 | if (Remainder->BitWidth != RHS.BitWidth) { |
| 1693 | if (Remainder->isSingleWord()) |
| 1694 | Remainder->VAL = 0; |
| 1695 | else |
Reid Spencer | 9ac4411 | 2007-02-26 23:38:21 +0000 | [diff] [blame] | 1696 | delete [] Remainder->pVal; |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1697 | Remainder->BitWidth = RHS.BitWidth; |
| 1698 | if (!Remainder->isSingleWord()) |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 1699 | Remainder->pVal = getClearedMemory(Remainder->getNumWords()); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1700 | } else |
| 1701 | Remainder->clear(); |
| 1702 | |
| 1703 | // The remainder is in R. Reconstitute the remainder into Remainder's low |
| 1704 | // order words. |
| 1705 | if (rhsWords == 1) { |
| 1706 | uint64_t tmp = |
| 1707 | uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2)); |
| 1708 | if (Remainder->isSingleWord()) |
| 1709 | Remainder->VAL = tmp; |
| 1710 | else |
| 1711 | Remainder->pVal[0] = tmp; |
| 1712 | } else { |
| 1713 | assert(!Remainder->isSingleWord() && "Remainder APInt not large enough"); |
| 1714 | for (unsigned i = 0; i < rhsWords; ++i) |
| 1715 | Remainder->pVal[i] = |
| 1716 | uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2)); |
| 1717 | } |
| 1718 | } |
| 1719 | |
| 1720 | // Clean up the memory we allocated. |
Reid Spencer | 24c4a8f | 2007-02-25 01:56:07 +0000 | [diff] [blame] | 1721 | if (U != &SPACE[0]) { |
| 1722 | delete [] U; |
| 1723 | delete [] V; |
| 1724 | delete [] Q; |
| 1725 | delete [] R; |
| 1726 | } |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 1727 | } |
| 1728 | |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 1729 | APInt APInt::udiv(const APInt& RHS) const { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 1730 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1731 | |
| 1732 | // First, deal with the easy case |
| 1733 | if (isSingleWord()) { |
| 1734 | assert(RHS.VAL != 0 && "Divide by zero?"); |
| 1735 | return APInt(BitWidth, VAL / RHS.VAL); |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1736 | } |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1737 | |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1738 | // Get some facts about the LHS and RHS number of bits and words |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 1739 | uint32_t rhsBits = RHS.getActiveBits(); |
| 1740 | uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1741 | assert(rhsWords && "Divided by zero???"); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1742 | uint32_t lhsBits = this->getActiveBits(); |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 1743 | uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1744 | |
| 1745 | // Deal with some degenerate cases |
| 1746 | if (!lhsWords) |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 1747 | // 0 / X ===> 0 |
| 1748 | return APInt(BitWidth, 0); |
| 1749 | else if (lhsWords < rhsWords || this->ult(RHS)) { |
| 1750 | // X / Y ===> 0, iff X < Y |
| 1751 | return APInt(BitWidth, 0); |
| 1752 | } else if (*this == RHS) { |
| 1753 | // X / X ===> 1 |
| 1754 | return APInt(BitWidth, 1); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1755 | } else if (lhsWords == 1 && rhsWords == 1) { |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1756 | // All high words are zero, just use native divide |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 1757 | return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]); |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1758 | } |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1759 | |
| 1760 | // We have to compute it the hard way. Invoke the Knuth divide algorithm. |
| 1761 | APInt Quotient(1,0); // to hold result. |
| 1762 | divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0); |
| 1763 | return Quotient; |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1764 | } |
| 1765 | |
Reid Spencer | e81d2da | 2007-02-16 22:36:51 +0000 | [diff] [blame] | 1766 | APInt APInt::urem(const APInt& RHS) const { |
Reid Spencer | cd6f2bf | 2007-02-17 00:18:01 +0000 | [diff] [blame] | 1767 | assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1768 | if (isSingleWord()) { |
| 1769 | assert(RHS.VAL != 0 && "Remainder by zero?"); |
| 1770 | return APInt(BitWidth, VAL % RHS.VAL); |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1771 | } |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1772 | |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 1773 | // Get some facts about the LHS |
| 1774 | uint32_t lhsBits = getActiveBits(); |
| 1775 | uint32_t lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1); |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1776 | |
| 1777 | // Get some facts about the RHS |
Reid Spencer | af0e956 | 2007-02-18 18:38:44 +0000 | [diff] [blame] | 1778 | uint32_t rhsBits = RHS.getActiveBits(); |
| 1779 | uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1780 | assert(rhsWords && "Performing remainder operation by zero ???"); |
| 1781 | |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1782 | // Check the degenerate cases |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1783 | if (lhsWords == 0) { |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 1784 | // 0 % Y ===> 0 |
| 1785 | return APInt(BitWidth, 0); |
| 1786 | } else if (lhsWords < rhsWords || this->ult(RHS)) { |
| 1787 | // X % Y ===> X, iff X < Y |
| 1788 | return *this; |
| 1789 | } else if (*this == RHS) { |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1790 | // X % X == 0; |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 1791 | return APInt(BitWidth, 0); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1792 | } else if (lhsWords == 1) { |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1793 | // All high words are zero, just use native remainder |
Reid Spencer | e0cdd33 | 2007-02-21 08:21:52 +0000 | [diff] [blame] | 1794 | return APInt(BitWidth, pVal[0] % RHS.pVal[0]); |
Reid Spencer | 71bd08f | 2007-02-17 02:07:07 +0000 | [diff] [blame] | 1795 | } |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1796 | |
Reid Spencer | 19dc32a | 2007-05-13 23:44:59 +0000 | [diff] [blame] | 1797 | // We have to compute it the hard way. Invoke the Knuth divide algorithm. |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1798 | APInt Remainder(1,0); |
| 1799 | divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder); |
| 1800 | return Remainder; |
Zhou Sheng | 0b706b1 | 2007-02-08 14:35:19 +0000 | [diff] [blame] | 1801 | } |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 1802 | |
Reid Spencer | 19dc32a | 2007-05-13 23:44:59 +0000 | [diff] [blame] | 1803 | void APInt::udivrem(const APInt &LHS, const APInt &RHS, |
| 1804 | APInt &Quotient, APInt &Remainder) { |
| 1805 | // Get some size facts about the dividend and divisor |
| 1806 | uint32_t lhsBits = LHS.getActiveBits(); |
| 1807 | uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); |
| 1808 | uint32_t rhsBits = RHS.getActiveBits(); |
| 1809 | uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); |
| 1810 | |
| 1811 | // Check the degenerate cases |
| 1812 | if (lhsWords == 0) { |
| 1813 | Quotient = 0; // 0 / Y ===> 0 |
| 1814 | Remainder = 0; // 0 % Y ===> 0 |
| 1815 | return; |
| 1816 | } |
| 1817 | |
| 1818 | if (lhsWords < rhsWords || LHS.ult(RHS)) { |
| 1819 | Quotient = 0; // X / Y ===> 0, iff X < Y |
| 1820 | Remainder = LHS; // X % Y ===> X, iff X < Y |
| 1821 | return; |
| 1822 | } |
| 1823 | |
| 1824 | if (LHS == RHS) { |
| 1825 | Quotient = 1; // X / X ===> 1 |
| 1826 | Remainder = 0; // X % X ===> 0; |
| 1827 | return; |
| 1828 | } |
| 1829 | |
| 1830 | if (lhsWords == 1 && rhsWords == 1) { |
| 1831 | // There is only one word to consider so use the native versions. |
| 1832 | if (LHS.isSingleWord()) { |
| 1833 | Quotient = APInt(LHS.getBitWidth(), LHS.VAL / RHS.VAL); |
| 1834 | Remainder = APInt(LHS.getBitWidth(), LHS.VAL % RHS.VAL); |
| 1835 | } else { |
| 1836 | Quotient = APInt(LHS.getBitWidth(), LHS.pVal[0] / RHS.pVal[0]); |
| 1837 | Remainder = APInt(LHS.getBitWidth(), LHS.pVal[0] % RHS.pVal[0]); |
| 1838 | } |
| 1839 | return; |
| 1840 | } |
| 1841 | |
| 1842 | // Okay, lets do it the long way |
| 1843 | divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder); |
| 1844 | } |
| 1845 | |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1846 | void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen, |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 1847 | uint8_t radix) { |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1848 | // Check our assumptions here |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 1849 | assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && |
| 1850 | "Radix should be 2, 8, 10, or 16!"); |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1851 | assert(str && "String is null?"); |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1852 | bool isNeg = str[0] == '-'; |
| 1853 | if (isNeg) |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 1854 | str++, slen--; |
Chris Lattner | a5ae15e | 2007-05-03 18:15:36 +0000 | [diff] [blame] | 1855 | assert((slen <= numbits || radix != 2) && "Insufficient bit width"); |
| 1856 | assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width"); |
| 1857 | assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width"); |
| 1858 | assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width"); |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1859 | |
| 1860 | // Allocate memory |
| 1861 | if (!isSingleWord()) |
| 1862 | pVal = getClearedMemory(getNumWords()); |
| 1863 | |
| 1864 | // Figure out if we can shift instead of multiply |
| 1865 | uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0); |
| 1866 | |
| 1867 | // Set up an APInt for the digit to add outside the loop so we don't |
| 1868 | // constantly construct/destruct it. |
| 1869 | APInt apdigit(getBitWidth(), 0); |
| 1870 | APInt apradix(getBitWidth(), radix); |
| 1871 | |
| 1872 | // Enter digit traversal loop |
| 1873 | for (unsigned i = 0; i < slen; i++) { |
| 1874 | // Get a digit |
| 1875 | uint32_t digit = 0; |
| 1876 | char cdigit = str[i]; |
Reid Spencer | 6551dcd | 2007-05-16 19:18:22 +0000 | [diff] [blame] | 1877 | if (radix == 16) { |
| 1878 | if (!isxdigit(cdigit)) |
| 1879 | assert(0 && "Invalid hex digit in string"); |
| 1880 | if (isdigit(cdigit)) |
| 1881 | digit = cdigit - '0'; |
| 1882 | else if (cdigit >= 'a') |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1883 | digit = cdigit - 'a' + 10; |
| 1884 | else if (cdigit >= 'A') |
| 1885 | digit = cdigit - 'A' + 10; |
| 1886 | else |
Reid Spencer | 6551dcd | 2007-05-16 19:18:22 +0000 | [diff] [blame] | 1887 | assert(0 && "huh? we shouldn't get here"); |
| 1888 | } else if (isdigit(cdigit)) { |
| 1889 | digit = cdigit - '0'; |
| 1890 | } else { |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1891 | assert(0 && "Invalid character in digit string"); |
Reid Spencer | 6551dcd | 2007-05-16 19:18:22 +0000 | [diff] [blame] | 1892 | } |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1893 | |
Reid Spencer | 6551dcd | 2007-05-16 19:18:22 +0000 | [diff] [blame] | 1894 | // Shift or multiply the value by the radix |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1895 | if (shift) |
Reid Spencer | 6551dcd | 2007-05-16 19:18:22 +0000 | [diff] [blame] | 1896 | *this <<= shift; |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1897 | else |
| 1898 | *this *= apradix; |
| 1899 | |
| 1900 | // Add in the digit we just interpreted |
Reid Spencer | 5bce854 | 2007-02-24 20:19:37 +0000 | [diff] [blame] | 1901 | if (apdigit.isSingleWord()) |
| 1902 | apdigit.VAL = digit; |
| 1903 | else |
| 1904 | apdigit.pVal[0] = digit; |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1905 | *this += apdigit; |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 1906 | } |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 1907 | // If its negative, put it in two's complement form |
Reid Spencer | 47fbe9e | 2007-02-26 07:44:38 +0000 | [diff] [blame] | 1908 | if (isNeg) { |
| 1909 | (*this)--; |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 1910 | this->flip(); |
Reid Spencer | 9eec241 | 2007-02-25 23:44:53 +0000 | [diff] [blame] | 1911 | } |
Reid Spencer | 5e0a851 | 2007-02-17 03:16:00 +0000 | [diff] [blame] | 1912 | } |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1913 | |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1914 | std::string APInt::toString(uint8_t radix, bool wantSigned) const { |
| 1915 | assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && |
| 1916 | "Radix should be 2, 8, 10, or 16!"); |
| 1917 | static const char *digits[] = { |
| 1918 | "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F" |
| 1919 | }; |
| 1920 | std::string result; |
| 1921 | uint32_t bits_used = getActiveBits(); |
| 1922 | if (isSingleWord()) { |
| 1923 | char buf[65]; |
| 1924 | const char *format = (radix == 10 ? (wantSigned ? "%lld" : "%llu") : |
| 1925 | (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0))); |
| 1926 | if (format) { |
| 1927 | if (wantSigned) { |
| 1928 | int64_t sextVal = (int64_t(VAL) << (APINT_BITS_PER_WORD-BitWidth)) >> |
| 1929 | (APINT_BITS_PER_WORD-BitWidth); |
| 1930 | sprintf(buf, format, sextVal); |
| 1931 | } else |
| 1932 | sprintf(buf, format, VAL); |
| 1933 | } else { |
| 1934 | memset(buf, 0, 65); |
| 1935 | uint64_t v = VAL; |
| 1936 | while (bits_used) { |
| 1937 | uint32_t bit = v & 1; |
| 1938 | bits_used--; |
| 1939 | buf[bits_used] = digits[bit][0]; |
| 1940 | v >>=1; |
| 1941 | } |
| 1942 | } |
| 1943 | result = buf; |
| 1944 | return result; |
| 1945 | } |
| 1946 | |
| 1947 | if (radix != 10) { |
Reid Spencer | fb0709a | 2007-05-17 19:23:02 +0000 | [diff] [blame] | 1948 | // For the 2, 8 and 16 bit cases, we can just shift instead of divide |
| 1949 | // because the number of bits per digit (1,3 and 4 respectively) divides |
| 1950 | // equaly. We just shift until there value is zero. |
| 1951 | |
| 1952 | // First, check for a zero value and just short circuit the logic below. |
| 1953 | if (*this == 0) |
| 1954 | result = "0"; |
| 1955 | else { |
| 1956 | APInt tmp(*this); |
| 1957 | size_t insert_at = 0; |
| 1958 | if (wantSigned && this->isNegative()) { |
| 1959 | // They want to print the signed version and it is a negative value |
| 1960 | // Flip the bits and add one to turn it into the equivalent positive |
| 1961 | // value and put a '-' in the result. |
| 1962 | tmp.flip(); |
| 1963 | tmp++; |
| 1964 | result = "-"; |
| 1965 | insert_at = 1; |
| 1966 | } |
| 1967 | // Just shift tmp right for each digit width until it becomes zero |
| 1968 | uint32_t shift = (radix == 16 ? 4 : (radix == 8 ? 3 : 1)); |
| 1969 | uint64_t mask = radix - 1; |
| 1970 | APInt zero(tmp.getBitWidth(), 0); |
| 1971 | while (tmp.ne(zero)) { |
Reid Spencer | 20a4c23 | 2007-05-19 00:29:55 +0000 | [diff] [blame] | 1972 | unsigned digit = (tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask; |
Reid Spencer | fb0709a | 2007-05-17 19:23:02 +0000 | [diff] [blame] | 1973 | result.insert(insert_at, digits[digit]); |
Reid Spencer | 20a4c23 | 2007-05-19 00:29:55 +0000 | [diff] [blame] | 1974 | tmp = tmp.lshr(shift); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1975 | } |
| 1976 | } |
| 1977 | return result; |
| 1978 | } |
| 1979 | |
| 1980 | APInt tmp(*this); |
| 1981 | APInt divisor(4, radix); |
| 1982 | APInt zero(tmp.getBitWidth(), 0); |
| 1983 | size_t insert_at = 0; |
| 1984 | if (wantSigned && tmp[BitWidth-1]) { |
| 1985 | // They want to print the signed version and it is a negative value |
| 1986 | // Flip the bits and add one to turn it into the equivalent positive |
| 1987 | // value and put a '-' in the result. |
| 1988 | tmp.flip(); |
| 1989 | tmp++; |
| 1990 | result = "-"; |
| 1991 | insert_at = 1; |
| 1992 | } |
Reid Spencer | e549c49 | 2007-02-21 00:29:48 +0000 | [diff] [blame] | 1993 | if (tmp == APInt(tmp.getBitWidth(), 0)) |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1994 | result = "0"; |
| 1995 | else while (tmp.ne(zero)) { |
| 1996 | APInt APdigit(1,0); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 1997 | APInt tmp2(tmp.getBitWidth(), 0); |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 1998 | divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2, |
| 1999 | &APdigit); |
Reid Spencer | 794f472 | 2007-02-26 21:02:27 +0000 | [diff] [blame] | 2000 | uint32_t digit = APdigit.getZExtValue(); |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 2001 | assert(digit < radix && "divide failed"); |
| 2002 | result.insert(insert_at,digits[digit]); |
Reid Spencer | 9c0696f | 2007-02-20 08:51:03 +0000 | [diff] [blame] | 2003 | tmp = tmp2; |
| 2004 | } |
| 2005 | |
| 2006 | return result; |
| 2007 | } |
| 2008 | |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 2009 | void APInt::dump() const |
| 2010 | { |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 2011 | cerr << "APInt(" << BitWidth << ")=" << std::setbase(16); |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 2012 | if (isSingleWord()) |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 2013 | cerr << VAL; |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 2014 | else for (unsigned i = getNumWords(); i > 0; i--) { |
Reid Spencer | 610fad8 | 2007-02-24 10:01:42 +0000 | [diff] [blame] | 2015 | cerr << pVal[i-1] << " "; |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 2016 | } |
Chris Lattner | 9132a2b | 2007-08-23 05:15:32 +0000 | [diff] [blame] | 2017 | cerr << " U(" << this->toStringUnsigned(10) << ") S(" |
Dale Johannesen | 9e3d3ab | 2007-09-14 22:26:36 +0000 | [diff] [blame] | 2018 | << this->toStringSigned(10) << ")" << std::setbase(10); |
Reid Spencer | 385f754 | 2007-02-21 03:55:44 +0000 | [diff] [blame] | 2019 | } |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2020 | |
| 2021 | // This implements a variety of operations on a representation of |
| 2022 | // arbitrary precision, two's-complement, bignum integer values. |
| 2023 | |
| 2024 | /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe |
| 2025 | and unrestricting assumption. */ |
Chris Lattner | b39cdde | 2007-08-20 22:49:32 +0000 | [diff] [blame] | 2026 | COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0); |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2027 | |
| 2028 | /* Some handy functions local to this file. */ |
| 2029 | namespace { |
| 2030 | |
Chris Lattner | b39cdde | 2007-08-20 22:49:32 +0000 | [diff] [blame] | 2031 | /* Returns the integer part with the least significant BITS set. |
| 2032 | BITS cannot be zero. */ |
| 2033 | inline integerPart |
| 2034 | lowBitMask(unsigned int bits) |
| 2035 | { |
| 2036 | assert (bits != 0 && bits <= integerPartWidth); |
| 2037 | |
| 2038 | return ~(integerPart) 0 >> (integerPartWidth - bits); |
| 2039 | } |
| 2040 | |
Neil Booth | 055c0b3 | 2007-10-06 00:43:45 +0000 | [diff] [blame] | 2041 | /* Returns the value of the lower half of PART. */ |
Chris Lattner | b39cdde | 2007-08-20 22:49:32 +0000 | [diff] [blame] | 2042 | inline integerPart |
| 2043 | lowHalf(integerPart part) |
| 2044 | { |
| 2045 | return part & lowBitMask(integerPartWidth / 2); |
| 2046 | } |
| 2047 | |
Neil Booth | 055c0b3 | 2007-10-06 00:43:45 +0000 | [diff] [blame] | 2048 | /* Returns the value of the upper half of PART. */ |
Chris Lattner | b39cdde | 2007-08-20 22:49:32 +0000 | [diff] [blame] | 2049 | inline integerPart |
| 2050 | highHalf(integerPart part) |
| 2051 | { |
| 2052 | return part >> (integerPartWidth / 2); |
| 2053 | } |
| 2054 | |
Neil Booth | 055c0b3 | 2007-10-06 00:43:45 +0000 | [diff] [blame] | 2055 | /* Returns the bit number of the most significant set bit of a part. |
| 2056 | If the input number has no bits set -1U is returned. */ |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2057 | unsigned int |
Chris Lattner | b39cdde | 2007-08-20 22:49:32 +0000 | [diff] [blame] | 2058 | partMSB(integerPart value) |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2059 | { |
| 2060 | unsigned int n, msb; |
| 2061 | |
| 2062 | if (value == 0) |
| 2063 | return -1U; |
| 2064 | |
| 2065 | n = integerPartWidth / 2; |
| 2066 | |
| 2067 | msb = 0; |
| 2068 | do { |
| 2069 | if (value >> n) { |
| 2070 | value >>= n; |
| 2071 | msb += n; |
| 2072 | } |
| 2073 | |
| 2074 | n >>= 1; |
| 2075 | } while (n); |
| 2076 | |
| 2077 | return msb; |
| 2078 | } |
| 2079 | |
Neil Booth | 055c0b3 | 2007-10-06 00:43:45 +0000 | [diff] [blame] | 2080 | /* Returns the bit number of the least significant set bit of a |
| 2081 | part. If the input number has no bits set -1U is returned. */ |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2082 | unsigned int |
| 2083 | partLSB(integerPart value) |
| 2084 | { |
| 2085 | unsigned int n, lsb; |
| 2086 | |
| 2087 | if (value == 0) |
| 2088 | return -1U; |
| 2089 | |
| 2090 | lsb = integerPartWidth - 1; |
| 2091 | n = integerPartWidth / 2; |
| 2092 | |
| 2093 | do { |
| 2094 | if (value << n) { |
| 2095 | value <<= n; |
| 2096 | lsb -= n; |
| 2097 | } |
| 2098 | |
| 2099 | n >>= 1; |
| 2100 | } while (n); |
| 2101 | |
| 2102 | return lsb; |
| 2103 | } |
| 2104 | } |
| 2105 | |
| 2106 | /* Sets the least significant part of a bignum to the input value, and |
| 2107 | zeroes out higher parts. */ |
| 2108 | void |
| 2109 | APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts) |
| 2110 | { |
| 2111 | unsigned int i; |
| 2112 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2113 | assert (parts > 0); |
| 2114 | |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2115 | dst[0] = part; |
| 2116 | for(i = 1; i < parts; i++) |
| 2117 | dst[i] = 0; |
| 2118 | } |
| 2119 | |
| 2120 | /* Assign one bignum to another. */ |
| 2121 | void |
| 2122 | APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts) |
| 2123 | { |
| 2124 | unsigned int i; |
| 2125 | |
| 2126 | for(i = 0; i < parts; i++) |
| 2127 | dst[i] = src[i]; |
| 2128 | } |
| 2129 | |
| 2130 | /* Returns true if a bignum is zero, false otherwise. */ |
| 2131 | bool |
| 2132 | APInt::tcIsZero(const integerPart *src, unsigned int parts) |
| 2133 | { |
| 2134 | unsigned int i; |
| 2135 | |
| 2136 | for(i = 0; i < parts; i++) |
| 2137 | if (src[i]) |
| 2138 | return false; |
| 2139 | |
| 2140 | return true; |
| 2141 | } |
| 2142 | |
| 2143 | /* Extract the given bit of a bignum; returns 0 or 1. */ |
| 2144 | int |
| 2145 | APInt::tcExtractBit(const integerPart *parts, unsigned int bit) |
| 2146 | { |
| 2147 | return(parts[bit / integerPartWidth] |
| 2148 | & ((integerPart) 1 << bit % integerPartWidth)) != 0; |
| 2149 | } |
| 2150 | |
| 2151 | /* Set the given bit of a bignum. */ |
| 2152 | void |
| 2153 | APInt::tcSetBit(integerPart *parts, unsigned int bit) |
| 2154 | { |
| 2155 | parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth); |
| 2156 | } |
| 2157 | |
Neil Booth | 055c0b3 | 2007-10-06 00:43:45 +0000 | [diff] [blame] | 2158 | /* Returns the bit number of the least significant set bit of a |
| 2159 | number. If the input number has no bits set -1U is returned. */ |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2160 | unsigned int |
| 2161 | APInt::tcLSB(const integerPart *parts, unsigned int n) |
| 2162 | { |
| 2163 | unsigned int i, lsb; |
| 2164 | |
| 2165 | for(i = 0; i < n; i++) { |
| 2166 | if (parts[i] != 0) { |
| 2167 | lsb = partLSB(parts[i]); |
| 2168 | |
| 2169 | return lsb + i * integerPartWidth; |
| 2170 | } |
| 2171 | } |
| 2172 | |
| 2173 | return -1U; |
| 2174 | } |
| 2175 | |
Neil Booth | 055c0b3 | 2007-10-06 00:43:45 +0000 | [diff] [blame] | 2176 | /* Returns the bit number of the most significant set bit of a number. |
| 2177 | If the input number has no bits set -1U is returned. */ |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2178 | unsigned int |
| 2179 | APInt::tcMSB(const integerPart *parts, unsigned int n) |
| 2180 | { |
| 2181 | unsigned int msb; |
| 2182 | |
| 2183 | do { |
| 2184 | --n; |
| 2185 | |
| 2186 | if (parts[n] != 0) { |
Chris Lattner | b39cdde | 2007-08-20 22:49:32 +0000 | [diff] [blame] | 2187 | msb = partMSB(parts[n]); |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2188 | |
| 2189 | return msb + n * integerPartWidth; |
| 2190 | } |
| 2191 | } while (n); |
| 2192 | |
| 2193 | return -1U; |
| 2194 | } |
| 2195 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2196 | /* Copy the bit vector of width srcBITS from SRC, starting at bit |
| 2197 | srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes |
| 2198 | the least significant bit of DST. All high bits above srcBITS in |
| 2199 | DST are zero-filled. */ |
| 2200 | void |
| 2201 | APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src, |
| 2202 | unsigned int srcBits, unsigned int srcLSB) |
| 2203 | { |
| 2204 | unsigned int firstSrcPart, dstParts, shift, n; |
| 2205 | |
| 2206 | dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth; |
| 2207 | assert (dstParts <= dstCount); |
| 2208 | |
| 2209 | firstSrcPart = srcLSB / integerPartWidth; |
| 2210 | tcAssign (dst, src + firstSrcPart, dstParts); |
| 2211 | |
| 2212 | shift = srcLSB % integerPartWidth; |
| 2213 | tcShiftRight (dst, dstParts, shift); |
| 2214 | |
| 2215 | /* We now have (dstParts * integerPartWidth - shift) bits from SRC |
| 2216 | in DST. If this is less that srcBits, append the rest, else |
| 2217 | clear the high bits. */ |
| 2218 | n = dstParts * integerPartWidth - shift; |
| 2219 | if (n < srcBits) { |
| 2220 | integerPart mask = lowBitMask (srcBits - n); |
| 2221 | dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask) |
| 2222 | << n % integerPartWidth); |
| 2223 | } else if (n > srcBits) { |
Neil Booth | 1e8390d | 2007-10-12 15:31:31 +0000 | [diff] [blame] | 2224 | if (srcBits % integerPartWidth) |
| 2225 | dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth); |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2226 | } |
| 2227 | |
| 2228 | /* Clear high parts. */ |
| 2229 | while (dstParts < dstCount) |
| 2230 | dst[dstParts++] = 0; |
| 2231 | } |
| 2232 | |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2233 | /* DST += RHS + C where C is zero or one. Returns the carry flag. */ |
| 2234 | integerPart |
| 2235 | APInt::tcAdd(integerPart *dst, const integerPart *rhs, |
| 2236 | integerPart c, unsigned int parts) |
| 2237 | { |
| 2238 | unsigned int i; |
| 2239 | |
| 2240 | assert(c <= 1); |
| 2241 | |
| 2242 | for(i = 0; i < parts; i++) { |
| 2243 | integerPart l; |
| 2244 | |
| 2245 | l = dst[i]; |
| 2246 | if (c) { |
| 2247 | dst[i] += rhs[i] + 1; |
| 2248 | c = (dst[i] <= l); |
| 2249 | } else { |
| 2250 | dst[i] += rhs[i]; |
| 2251 | c = (dst[i] < l); |
| 2252 | } |
| 2253 | } |
| 2254 | |
| 2255 | return c; |
| 2256 | } |
| 2257 | |
| 2258 | /* DST -= RHS + C where C is zero or one. Returns the carry flag. */ |
| 2259 | integerPart |
| 2260 | APInt::tcSubtract(integerPart *dst, const integerPart *rhs, |
| 2261 | integerPart c, unsigned int parts) |
| 2262 | { |
| 2263 | unsigned int i; |
| 2264 | |
| 2265 | assert(c <= 1); |
| 2266 | |
| 2267 | for(i = 0; i < parts; i++) { |
| 2268 | integerPart l; |
| 2269 | |
| 2270 | l = dst[i]; |
| 2271 | if (c) { |
| 2272 | dst[i] -= rhs[i] + 1; |
| 2273 | c = (dst[i] >= l); |
| 2274 | } else { |
| 2275 | dst[i] -= rhs[i]; |
| 2276 | c = (dst[i] > l); |
| 2277 | } |
| 2278 | } |
| 2279 | |
| 2280 | return c; |
| 2281 | } |
| 2282 | |
| 2283 | /* Negate a bignum in-place. */ |
| 2284 | void |
| 2285 | APInt::tcNegate(integerPart *dst, unsigned int parts) |
| 2286 | { |
| 2287 | tcComplement(dst, parts); |
| 2288 | tcIncrement(dst, parts); |
| 2289 | } |
| 2290 | |
Neil Booth | 055c0b3 | 2007-10-06 00:43:45 +0000 | [diff] [blame] | 2291 | /* DST += SRC * MULTIPLIER + CARRY if add is true |
| 2292 | DST = SRC * MULTIPLIER + CARRY if add is false |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2293 | |
| 2294 | Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC |
| 2295 | they must start at the same point, i.e. DST == SRC. |
| 2296 | |
| 2297 | If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is |
| 2298 | returned. Otherwise DST is filled with the least significant |
| 2299 | DSTPARTS parts of the result, and if all of the omitted higher |
| 2300 | parts were zero return zero, otherwise overflow occurred and |
| 2301 | return one. */ |
| 2302 | int |
| 2303 | APInt::tcMultiplyPart(integerPart *dst, const integerPart *src, |
| 2304 | integerPart multiplier, integerPart carry, |
| 2305 | unsigned int srcParts, unsigned int dstParts, |
| 2306 | bool add) |
| 2307 | { |
| 2308 | unsigned int i, n; |
| 2309 | |
| 2310 | /* Otherwise our writes of DST kill our later reads of SRC. */ |
| 2311 | assert(dst <= src || dst >= src + srcParts); |
| 2312 | assert(dstParts <= srcParts + 1); |
| 2313 | |
| 2314 | /* N loops; minimum of dstParts and srcParts. */ |
| 2315 | n = dstParts < srcParts ? dstParts: srcParts; |
| 2316 | |
| 2317 | for(i = 0; i < n; i++) { |
| 2318 | integerPart low, mid, high, srcPart; |
| 2319 | |
| 2320 | /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY. |
| 2321 | |
| 2322 | This cannot overflow, because |
| 2323 | |
| 2324 | (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1) |
| 2325 | |
| 2326 | which is less than n^2. */ |
| 2327 | |
| 2328 | srcPart = src[i]; |
| 2329 | |
| 2330 | if (multiplier == 0 || srcPart == 0) { |
| 2331 | low = carry; |
| 2332 | high = 0; |
| 2333 | } else { |
| 2334 | low = lowHalf(srcPart) * lowHalf(multiplier); |
| 2335 | high = highHalf(srcPart) * highHalf(multiplier); |
| 2336 | |
| 2337 | mid = lowHalf(srcPart) * highHalf(multiplier); |
| 2338 | high += highHalf(mid); |
| 2339 | mid <<= integerPartWidth / 2; |
| 2340 | if (low + mid < low) |
| 2341 | high++; |
| 2342 | low += mid; |
| 2343 | |
| 2344 | mid = highHalf(srcPart) * lowHalf(multiplier); |
| 2345 | high += highHalf(mid); |
| 2346 | mid <<= integerPartWidth / 2; |
| 2347 | if (low + mid < low) |
| 2348 | high++; |
| 2349 | low += mid; |
| 2350 | |
| 2351 | /* Now add carry. */ |
| 2352 | if (low + carry < low) |
| 2353 | high++; |
| 2354 | low += carry; |
| 2355 | } |
| 2356 | |
| 2357 | if (add) { |
| 2358 | /* And now DST[i], and store the new low part there. */ |
| 2359 | if (low + dst[i] < low) |
| 2360 | high++; |
| 2361 | dst[i] += low; |
| 2362 | } else |
| 2363 | dst[i] = low; |
| 2364 | |
| 2365 | carry = high; |
| 2366 | } |
| 2367 | |
| 2368 | if (i < dstParts) { |
| 2369 | /* Full multiplication, there is no overflow. */ |
| 2370 | assert(i + 1 == dstParts); |
| 2371 | dst[i] = carry; |
| 2372 | return 0; |
| 2373 | } else { |
| 2374 | /* We overflowed if there is carry. */ |
| 2375 | if (carry) |
| 2376 | return 1; |
| 2377 | |
| 2378 | /* We would overflow if any significant unwritten parts would be |
| 2379 | non-zero. This is true if any remaining src parts are non-zero |
| 2380 | and the multiplier is non-zero. */ |
| 2381 | if (multiplier) |
| 2382 | for(; i < srcParts; i++) |
| 2383 | if (src[i]) |
| 2384 | return 1; |
| 2385 | |
| 2386 | /* We fitted in the narrow destination. */ |
| 2387 | return 0; |
| 2388 | } |
| 2389 | } |
| 2390 | |
| 2391 | /* DST = LHS * RHS, where DST has the same width as the operands and |
| 2392 | is filled with the least significant parts of the result. Returns |
| 2393 | one if overflow occurred, otherwise zero. DST must be disjoint |
| 2394 | from both operands. */ |
| 2395 | int |
| 2396 | APInt::tcMultiply(integerPart *dst, const integerPart *lhs, |
| 2397 | const integerPart *rhs, unsigned int parts) |
| 2398 | { |
| 2399 | unsigned int i; |
| 2400 | int overflow; |
| 2401 | |
| 2402 | assert(dst != lhs && dst != rhs); |
| 2403 | |
| 2404 | overflow = 0; |
| 2405 | tcSet(dst, 0, parts); |
| 2406 | |
| 2407 | for(i = 0; i < parts; i++) |
| 2408 | overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, |
| 2409 | parts - i, true); |
| 2410 | |
| 2411 | return overflow; |
| 2412 | } |
| 2413 | |
Neil Booth | 978661d | 2007-10-06 00:24:48 +0000 | [diff] [blame] | 2414 | /* DST = LHS * RHS, where DST has width the sum of the widths of the |
| 2415 | operands. No overflow occurs. DST must be disjoint from both |
| 2416 | operands. Returns the number of parts required to hold the |
| 2417 | result. */ |
| 2418 | unsigned int |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2419 | APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs, |
Neil Booth | 978661d | 2007-10-06 00:24:48 +0000 | [diff] [blame] | 2420 | const integerPart *rhs, unsigned int lhsParts, |
| 2421 | unsigned int rhsParts) |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2422 | { |
Neil Booth | 978661d | 2007-10-06 00:24:48 +0000 | [diff] [blame] | 2423 | /* Put the narrower number on the LHS for less loops below. */ |
| 2424 | if (lhsParts > rhsParts) { |
| 2425 | return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts); |
| 2426 | } else { |
| 2427 | unsigned int n; |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2428 | |
Neil Booth | 978661d | 2007-10-06 00:24:48 +0000 | [diff] [blame] | 2429 | assert(dst != lhs && dst != rhs); |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2430 | |
Neil Booth | 978661d | 2007-10-06 00:24:48 +0000 | [diff] [blame] | 2431 | tcSet(dst, 0, rhsParts); |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2432 | |
Neil Booth | 978661d | 2007-10-06 00:24:48 +0000 | [diff] [blame] | 2433 | for(n = 0; n < lhsParts; n++) |
| 2434 | tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true); |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2435 | |
Neil Booth | 978661d | 2007-10-06 00:24:48 +0000 | [diff] [blame] | 2436 | n = lhsParts + rhsParts; |
| 2437 | |
| 2438 | return n - (dst[n - 1] == 0); |
| 2439 | } |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2440 | } |
| 2441 | |
| 2442 | /* If RHS is zero LHS and REMAINDER are left unchanged, return one. |
| 2443 | Otherwise set LHS to LHS / RHS with the fractional part discarded, |
| 2444 | set REMAINDER to the remainder, return zero. i.e. |
| 2445 | |
| 2446 | OLD_LHS = RHS * LHS + REMAINDER |
| 2447 | |
| 2448 | SCRATCH is a bignum of the same size as the operands and result for |
| 2449 | use by the routine; its contents need not be initialized and are |
| 2450 | destroyed. LHS, REMAINDER and SCRATCH must be distinct. |
| 2451 | */ |
| 2452 | int |
| 2453 | APInt::tcDivide(integerPart *lhs, const integerPart *rhs, |
| 2454 | integerPart *remainder, integerPart *srhs, |
| 2455 | unsigned int parts) |
| 2456 | { |
| 2457 | unsigned int n, shiftCount; |
| 2458 | integerPart mask; |
| 2459 | |
| 2460 | assert(lhs != remainder && lhs != srhs && remainder != srhs); |
| 2461 | |
Chris Lattner | b39cdde | 2007-08-20 22:49:32 +0000 | [diff] [blame] | 2462 | shiftCount = tcMSB(rhs, parts) + 1; |
| 2463 | if (shiftCount == 0) |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2464 | return true; |
| 2465 | |
Chris Lattner | b39cdde | 2007-08-20 22:49:32 +0000 | [diff] [blame] | 2466 | shiftCount = parts * integerPartWidth - shiftCount; |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2467 | n = shiftCount / integerPartWidth; |
| 2468 | mask = (integerPart) 1 << (shiftCount % integerPartWidth); |
| 2469 | |
| 2470 | tcAssign(srhs, rhs, parts); |
| 2471 | tcShiftLeft(srhs, parts, shiftCount); |
| 2472 | tcAssign(remainder, lhs, parts); |
| 2473 | tcSet(lhs, 0, parts); |
| 2474 | |
| 2475 | /* Loop, subtracting SRHS if REMAINDER is greater and adding that to |
| 2476 | the total. */ |
| 2477 | for(;;) { |
| 2478 | int compare; |
| 2479 | |
| 2480 | compare = tcCompare(remainder, srhs, parts); |
| 2481 | if (compare >= 0) { |
| 2482 | tcSubtract(remainder, srhs, 0, parts); |
| 2483 | lhs[n] |= mask; |
| 2484 | } |
| 2485 | |
| 2486 | if (shiftCount == 0) |
| 2487 | break; |
| 2488 | shiftCount--; |
| 2489 | tcShiftRight(srhs, parts, 1); |
| 2490 | if ((mask >>= 1) == 0) |
| 2491 | mask = (integerPart) 1 << (integerPartWidth - 1), n--; |
| 2492 | } |
| 2493 | |
| 2494 | return false; |
| 2495 | } |
| 2496 | |
| 2497 | /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero. |
| 2498 | There are no restrictions on COUNT. */ |
| 2499 | void |
| 2500 | APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count) |
| 2501 | { |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2502 | if (count) { |
| 2503 | unsigned int jump, shift; |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2504 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2505 | /* Jump is the inter-part jump; shift is is intra-part shift. */ |
| 2506 | jump = count / integerPartWidth; |
| 2507 | shift = count % integerPartWidth; |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2508 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2509 | while (parts > jump) { |
| 2510 | integerPart part; |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2511 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2512 | parts--; |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2513 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2514 | /* dst[i] comes from the two parts src[i - jump] and, if we have |
| 2515 | an intra-part shift, src[i - jump - 1]. */ |
| 2516 | part = dst[parts - jump]; |
| 2517 | if (shift) { |
| 2518 | part <<= shift; |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2519 | if (parts >= jump + 1) |
| 2520 | part |= dst[parts - jump - 1] >> (integerPartWidth - shift); |
| 2521 | } |
| 2522 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2523 | dst[parts] = part; |
| 2524 | } |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2525 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2526 | while (parts > 0) |
| 2527 | dst[--parts] = 0; |
| 2528 | } |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2529 | } |
| 2530 | |
| 2531 | /* Shift a bignum right COUNT bits in-place. Shifted in bits are |
| 2532 | zero. There are no restrictions on COUNT. */ |
| 2533 | void |
| 2534 | APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count) |
| 2535 | { |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2536 | if (count) { |
| 2537 | unsigned int i, jump, shift; |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2538 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2539 | /* Jump is the inter-part jump; shift is is intra-part shift. */ |
| 2540 | jump = count / integerPartWidth; |
| 2541 | shift = count % integerPartWidth; |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2542 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2543 | /* Perform the shift. This leaves the most significant COUNT bits |
| 2544 | of the result at zero. */ |
| 2545 | for(i = 0; i < parts; i++) { |
| 2546 | integerPart part; |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2547 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2548 | if (i + jump >= parts) { |
| 2549 | part = 0; |
| 2550 | } else { |
| 2551 | part = dst[i + jump]; |
| 2552 | if (shift) { |
| 2553 | part >>= shift; |
| 2554 | if (i + jump + 1 < parts) |
| 2555 | part |= dst[i + jump + 1] << (integerPartWidth - shift); |
| 2556 | } |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2557 | } |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2558 | |
Neil Booth | 68e53ad | 2007-10-08 13:47:12 +0000 | [diff] [blame] | 2559 | dst[i] = part; |
| 2560 | } |
Chris Lattner | fe8e14a | 2007-08-16 15:56:55 +0000 | [diff] [blame] | 2561 | } |
| 2562 | } |
| 2563 | |
| 2564 | /* Bitwise and of two bignums. */ |
| 2565 | void |
| 2566 | APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts) |
| 2567 | { |
| 2568 | unsigned int i; |
| 2569 | |
| 2570 | for(i = 0; i < parts; i++) |
| 2571 | dst[i] &= rhs[i]; |
| 2572 | } |
| 2573 | |
| 2574 | /* Bitwise inclusive or of two bignums. */ |
| 2575 | void |
| 2576 | APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts) |
| 2577 | { |
| 2578 | unsigned int i; |
| 2579 | |
| 2580 | for(i = 0; i < parts; i++) |
| 2581 | dst[i] |= rhs[i]; |
| 2582 | } |
| 2583 | |
| 2584 | /* Bitwise exclusive or of two bignums. */ |
| 2585 | void |
| 2586 | APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts) |
| 2587 | { |
| 2588 | unsigned int i; |
| 2589 | |
| 2590 | for(i = 0; i < parts; i++) |
| 2591 | dst[i] ^= rhs[i]; |
| 2592 | } |
| 2593 | |
| 2594 | /* Complement a bignum in-place. */ |
| 2595 | void |
| 2596 | APInt::tcComplement(integerPart *dst, unsigned int parts) |
| 2597 | { |
| 2598 | unsigned int i; |
| 2599 | |
| 2600 | for(i = 0; i < parts; i++) |
| 2601 | dst[i] = ~dst[i]; |
| 2602 | } |
| 2603 | |
| 2604 | /* Comparison (unsigned) of two bignums. */ |
| 2605 | int |
| 2606 | APInt::tcCompare(const integerPart *lhs, const integerPart *rhs, |
| 2607 | unsigned int parts) |
| 2608 | { |
| 2609 | while (parts) { |
| 2610 | parts--; |
| 2611 | if (lhs[parts] == rhs[parts]) |
| 2612 | continue; |
| 2613 | |
| 2614 | if (lhs[parts] > rhs[parts]) |
| 2615 | return 1; |
| 2616 | else |
| 2617 | return -1; |
| 2618 | } |
| 2619 | |
| 2620 | return 0; |
| 2621 | } |
| 2622 | |
| 2623 | /* Increment a bignum in-place, return the carry flag. */ |
| 2624 | integerPart |
| 2625 | APInt::tcIncrement(integerPart *dst, unsigned int parts) |
| 2626 | { |
| 2627 | unsigned int i; |
| 2628 | |
| 2629 | for(i = 0; i < parts; i++) |
| 2630 | if (++dst[i] != 0) |
| 2631 | break; |
| 2632 | |
| 2633 | return i == parts; |
| 2634 | } |
| 2635 | |
| 2636 | /* Set the least significant BITS bits of a bignum, clear the |
| 2637 | rest. */ |
| 2638 | void |
| 2639 | APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts, |
| 2640 | unsigned int bits) |
| 2641 | { |
| 2642 | unsigned int i; |
| 2643 | |
| 2644 | i = 0; |
| 2645 | while (bits > integerPartWidth) { |
| 2646 | dst[i++] = ~(integerPart) 0; |
| 2647 | bits -= integerPartWidth; |
| 2648 | } |
| 2649 | |
| 2650 | if (bits) |
| 2651 | dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits); |
| 2652 | |
| 2653 | while (i < parts) |
| 2654 | dst[i++] = 0; |
| 2655 | } |