| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include "ignite/ignite_error.h" |
| #include "ignite/common/bits.h" |
| #include "ignite/common/big_integer.h" |
| |
| namespace ignite |
| { |
| namespace common |
| { |
| BigInteger::BigInteger() : |
| sign(1), |
| mag() |
| { |
| // No-op. |
| } |
| |
| BigInteger::BigInteger(int64_t val) : |
| sign(1), |
| mag() |
| { |
| AssignInt64(val); |
| } |
| |
| BigInteger::BigInteger(const char* val, int32_t len) : |
| sign(1), |
| mag() |
| { |
| AssignString(val, len); |
| } |
| |
| BigInteger::BigInteger(const BigInteger& other) : |
| sign(other.sign), |
| mag(other.mag) |
| { |
| // No-op. |
| } |
| |
| BigInteger::BigInteger(const int8_t* val, int32_t len, int32_t sign, bool bigEndian) : |
| sign(sign), |
| mag() |
| { |
| assert(val != 0); |
| assert(len >= 0); |
| assert(sign == 1 || sign == 0 || sign == -1); |
| |
| if (bigEndian) |
| { |
| int32_t firstNonZero = 0; |
| while (firstNonZero < len && val[firstNonZero] == 0) |
| ++firstNonZero; |
| |
| if (firstNonZero == len) |
| { |
| AssignInt64(0); |
| |
| return; |
| } |
| |
| int32_t intLength = (len - firstNonZero + 3) / 4; |
| |
| mag.Resize(intLength); |
| |
| int32_t b = len - 1; |
| |
| for (int32_t i = 0; i < intLength - 1; ++i) |
| { |
| mag[i] = (val[b] & 0xFFUL) |
| | ((val[b - 1] & 0xFFUL) << 8) |
| | ((val[b - 2] & 0xFFUL) << 16) |
| | ((val[b - 3] & 0xFFUL) << 24); |
| |
| b -= 4; |
| } |
| |
| int32_t bytesRemaining = b - firstNonZero + 1; |
| |
| assert(bytesRemaining > 0 && bytesRemaining <= 4); |
| |
| switch (bytesRemaining) |
| { |
| case 4: |
| mag[intLength - 1] |= (val[b - 3] & 0xFF) << 24; |
| // Fall-through. |
| |
| case 3: |
| mag[intLength - 1] |= (val[b - 2] & 0xFF) << 16; |
| // Fall-through. |
| |
| case 2: |
| mag[intLength - 1] |= (val[b - 1] & 0xFF) << 8; |
| // Fall-through. |
| |
| case 1: |
| mag[intLength - 1] |= val[b] & 0xFF; |
| // Fall-through. |
| |
| default: |
| break; |
| } |
| } |
| else |
| { |
| int32_t firstNonZero = len - 1; |
| |
| while (firstNonZero >= 0 && val[firstNonZero] == 0) |
| --firstNonZero; |
| |
| if (firstNonZero == -1) |
| { |
| AssignInt64(0); |
| |
| return; |
| } |
| |
| int32_t intLength = (firstNonZero + 4) / 4; |
| |
| mag.Resize(intLength); |
| |
| int32_t b = 0; |
| |
| for (int32_t i = 0; i < intLength - 1; ++i) |
| { |
| mag[i] = (val[b] & 0xFFUL) |
| | ((val[b + 1] & 0xFFUL) << 8) |
| | ((val[b + 2] & 0xFFUL) << 16) |
| | ((val[b + 3] & 0xFFUL) << 24); |
| |
| b += 4; |
| } |
| |
| int32_t bytesRemaining = firstNonZero - b + 1; |
| |
| assert(bytesRemaining > 0 && bytesRemaining <= 4); |
| |
| switch (bytesRemaining) |
| { |
| case 4: |
| mag[intLength - 1] |= (val[b + 3] & 0xFF) << 24; |
| // Fall-through. |
| |
| case 3: |
| mag[intLength - 1] |= (val[b + 2] & 0xFF) << 16; |
| // Fall-through. |
| |
| case 2: |
| mag[intLength - 1] |= (val[b + 1] & 0xFF) << 8; |
| // Fall-through. |
| |
| case 1: |
| mag[intLength - 1] |= val[b] & 0xFF; |
| // Fall-through. |
| |
| default: |
| break; |
| } |
| } |
| } |
| |
| BigInteger::BigInteger(MagArray &mag, int8_t sign) : |
| sign(sign), |
| mag() |
| { |
| this->mag.Swap(mag); |
| } |
| |
| BigInteger& BigInteger::operator=(const BigInteger& other) |
| { |
| Assign(other); |
| |
| return *this; |
| } |
| |
| void BigInteger::Assign(const BigInteger& val) |
| { |
| if (this != &val) |
| { |
| sign = val.sign; |
| mag = val.mag; |
| } |
| } |
| |
| void BigInteger::AssignInt64(int64_t val) |
| { |
| if (val < 0) |
| { |
| AssignUint64(val > INT64_MIN ? static_cast<uint64_t>(-val) : static_cast<uint64_t>(val)); |
| |
| sign = -1; |
| } |
| else |
| AssignUint64(static_cast<uint64_t>(val)); |
| } |
| |
| void BigInteger::AssignString(const char* val, int32_t len) |
| { |
| std::stringstream converter; |
| |
| converter.write(val, len); |
| |
| converter >> *this; |
| } |
| |
| void BigInteger::AssignUint64(uint64_t val) |
| { |
| sign = 1; |
| |
| if (val == 0) |
| { |
| mag.Clear(); |
| |
| return; |
| } |
| |
| uint32_t highWord = static_cast<uint32_t>(val >> 32); |
| |
| if (highWord == 0) |
| mag.Resize(1); |
| else |
| { |
| mag.Resize(2); |
| mag[1] = highWord; |
| } |
| |
| mag[0] = static_cast<uint32_t>(val); |
| } |
| |
| int8_t BigInteger::GetSign() const |
| { |
| return sign; |
| } |
| |
| void BigInteger::Swap(BigInteger& other) |
| { |
| using std::swap; |
| |
| swap(sign, other.sign); |
| mag.Swap(other.mag); |
| } |
| |
| const BigInteger::MagArray& BigInteger::GetMagnitude() const |
| { |
| return mag; |
| } |
| |
| uint32_t BigInteger::GetBitLength() const |
| { |
| if (mag.IsEmpty()) |
| return 0; |
| |
| int32_t res = bits::BitLengthU32(mag[mag.GetSize() - 1]); |
| |
| if (mag.GetSize() > 1) |
| res += (mag.GetSize() - 1) * 32; |
| |
| return res; |
| } |
| |
| int32_t BigInteger::GetPrecision() const |
| { |
| // See http://graphics.stanford.edu/~seander/bithacks.html |
| // for the details on the algorithm. |
| |
| if (mag.GetSize() == 0) |
| return 1; |
| |
| int32_t r = static_cast<uint32_t>((( |
| static_cast<uint64_t>(GetBitLength()) + 1) * 646456993) >> 31); |
| |
| BigInteger prec; |
| BigInteger::GetPowerOfTen(r, prec); |
| |
| return Compare(prec, true) < 0 ? r : r + 1; |
| } |
| |
| void BigInteger::MagnitudeToBytes(common::FixedSizeArray<int8_t>& buffer) const |
| { |
| int32_t bytesNum = static_cast<int32_t>((GetBitLength() + 7) / 8); |
| |
| if (bytesNum == 0) |
| { |
| buffer.Reset(1); |
| |
| return; |
| } |
| |
| buffer.Reset(bytesNum); |
| |
| int32_t i; |
| for (i = 0; i < mag.GetSize() - 1; ++i) |
| { |
| int32_t j = bytesNum - 1 - 4 * i; |
| |
| buffer[j] = static_cast<int8_t>(mag[i]); |
| buffer[j - 1] = static_cast<int8_t>(mag[i] >> 8); |
| buffer[j - 2] = static_cast<int8_t>(mag[i] >> 16); |
| buffer[j - 3] = static_cast<int8_t>(mag[i] >> 24); |
| } |
| |
| int32_t bytesRemaining = bytesNum - 4 * i; |
| |
| assert(bytesRemaining >= 0 && bytesRemaining <= 4); |
| |
| i = 0; |
| switch (bytesRemaining) |
| { |
| case 4: |
| buffer[i++] |= static_cast<int8_t>(mag[mag.GetSize() - 1] >> 24); |
| // Fall-through. |
| |
| case 3: |
| buffer[i++] |= static_cast<int8_t>(mag[mag.GetSize() - 1] >> 16); |
| // Fall-through. |
| |
| case 2: |
| buffer[i++] |= static_cast<int8_t>(mag[mag.GetSize() - 1] >> 8); |
| // Fall-through. |
| |
| case 1: |
| buffer[i++] |= static_cast<int8_t>(mag[mag.GetSize() - 1]); |
| // Fall-through. |
| |
| default: |
| break; |
| } |
| } |
| |
| void BigInteger::Pow(int32_t exp) |
| { |
| if (exp < 0) |
| { |
| AssignInt64(0); |
| |
| return; |
| } |
| |
| uint32_t bitsLen = GetBitLength(); |
| |
| if (!bitsLen) |
| return; |
| |
| if (bitsLen == 1) |
| { |
| if ((exp % 2 == 0) && sign < 0) |
| sign = -sign; |
| |
| return; |
| } |
| |
| BigInteger multiplicant(*this); |
| AssignInt64(1); |
| |
| int32_t mutExp = exp; |
| while (mutExp) |
| { |
| if (mutExp & 1) |
| Multiply(multiplicant, *this); |
| |
| mutExp >>= 1; |
| |
| if (mutExp) |
| multiplicant.Multiply(multiplicant, multiplicant); |
| } |
| } |
| |
| void BigInteger::Multiply(const BigInteger& other, BigInteger& res) const |
| { |
| MagArray resMag(mag.GetSize() + other.mag.GetSize()); |
| |
| resMag.Resize(mag.GetSize() + other.mag.GetSize()); |
| |
| for (int32_t i = 0; i < other.mag.GetSize(); ++i) |
| { |
| uint32_t carry = 0; |
| |
| for (int32_t j = 0; j < mag.GetSize(); ++j) |
| { |
| uint64_t product = static_cast<uint64_t>(mag[j]) * other.mag[i] + |
| + resMag[i + j] + carry; |
| |
| resMag[i + j] = static_cast<uint32_t>(product); |
| carry = static_cast<uint32_t>(product >> 32); |
| } |
| |
| resMag[i + mag.GetSize()] = carry; |
| } |
| |
| res.mag.Swap(resMag); |
| res.sign = sign * other.sign; |
| |
| res.Normalize(); |
| } |
| |
| /** |
| * Shift magnitude left by the specified number of bits. |
| * |
| * @param in Input magnitude. |
| * @param len Magnitude length. |
| * @param out Output magnitude. Should be not shorter than the input |
| * magnitude. |
| * @param n Number of bits to shift to. |
| */ |
| void ShiftLeft(const uint32_t* in, int32_t len, uint32_t* out, unsigned n) |
| { |
| assert(n < 32); |
| |
| if (n == 0) |
| { |
| std::copy(in, in + len, out); |
| |
| return; |
| } |
| |
| for (int32_t i = len - 1; i > 0; --i) |
| out[i] = (in[i] << n) | (in[i - 1] >> (32 - n)); |
| |
| out[0] = in[0] << n; |
| } |
| |
| /** |
| * Shift magnitude right by the specified number of bits. |
| * |
| * @param in Input magnitude. |
| * @param len Magnitude length. |
| * @param out Output magnitude. Should be not shorter than the input |
| * magnitude. |
| * @param n Number of bits to shift to. |
| */ |
| void ShiftRight(const uint32_t* in, int32_t len, uint32_t* out, unsigned n) |
| { |
| assert(n < 32); |
| |
| if (n == 0) |
| { |
| std::copy(in, in + len, out); |
| |
| return; |
| } |
| |
| for (int32_t i = 0; i < len - 1; ++i) |
| out[i] = (in[i] >> n) | (in[i + 1] << (32 - n)); |
| |
| out[len - 1] = in[len - 1] >> n; |
| } |
| |
| /** |
| * Part of the division algorithm. Computes q - (a * x). |
| * |
| * @param q Minuend. |
| * @param a Multipliplier of the subtrahend. |
| * @param alen Length of the a. |
| * @param x Multipliplicand of the subtrahend. |
| * @return Carry. |
| */ |
| uint32_t MultiplyAndSubstruct(uint32_t* q, const uint32_t* a, int32_t alen, uint32_t x) |
| { |
| uint64_t carry = 0; |
| |
| for (int32_t i = 0; i < alen; ++i) |
| { |
| uint64_t product = a[i] * static_cast<uint64_t>(x); |
| int64_t difference = q[i] - carry - (product & 0xFFFFFFFF); |
| |
| q[i] = static_cast<uint32_t>(difference); |
| |
| // This will add one if difference is negative. |
| carry = (product >> 32) - (difference >> 32); |
| } |
| |
| return static_cast<uint32_t>(carry); |
| } |
| |
| /** |
| * Add two magnitude arrays and return carry. |
| * |
| * @param res First addend. Result is placed here. Length of this addend |
| * should be equal or greater than len. |
| * @param addend Second addend. |
| * @param len Length of the second addend. |
| * @return Carry. |
| */ |
| uint32_t Add(uint32_t* res, const uint32_t* addend, int32_t len) |
| { |
| uint64_t carry = 0; |
| |
| for (int32_t i = 0; i < len; ++i) |
| { |
| uint64_t sum = static_cast<uint64_t>(res[i]) + addend[i] + carry; |
| res[i] = static_cast<uint32_t>(sum); |
| carry = sum >> 32; |
| } |
| |
| return static_cast<uint32_t>(carry); |
| } |
| |
| /** |
| * Add single number to a magnitude array and return carry. |
| * |
| * @param res First addend. Result is placed here. Length of this addend |
| * should be equal or greater than len. |
| * @param len Length of the First addend. |
| * @param addend Second addend. |
| * @return Carry. |
| */ |
| uint32_t Add(uint32_t* res, int32_t len, uint32_t addend) |
| { |
| uint64_t carry = addend; |
| |
| for (int32_t i = 0; (i < len) && carry; ++i) |
| { |
| uint64_t sum = static_cast<uint64_t>(res[i]) + carry; |
| res[i] = static_cast<uint32_t>(sum); |
| carry = sum >> 32; |
| } |
| |
| return static_cast<uint32_t>(carry); |
| } |
| |
| void BigInteger::Divide(const BigInteger& divisor, BigInteger& res) const |
| { |
| Divide(divisor, res, 0); |
| } |
| |
| void BigInteger::Divide(const BigInteger& divisor, BigInteger& res, BigInteger& rem) const |
| { |
| Divide(divisor, res, &rem); |
| } |
| |
| void BigInteger::Add(const uint32_t* addend, int32_t len) |
| { |
| if (mag.GetSize() < len) |
| { |
| mag.Reserve(len + 1); |
| |
| mag.Resize(len); |
| } |
| else |
| mag.Reserve(mag.GetSize() + 1); |
| |
| uint32_t carry = common::Add(mag.GetData(), addend, len); |
| |
| if (carry) |
| { |
| carry = common::Add(mag.GetData() + len, mag.GetSize() - len, carry); |
| |
| if (carry) |
| mag.PushBack(carry); |
| } |
| } |
| |
| void BigInteger::Add(uint64_t x) |
| { |
| if (x == 0) |
| return; |
| |
| if (IsZero()) |
| { |
| AssignUint64(x); |
| |
| return; |
| } |
| |
| uint32_t val[2]; |
| |
| val[0] = static_cast<uint32_t>(x); |
| val[1] = static_cast<uint32_t>(x >> 32); |
| |
| Add(val, val[1] ? 2 : 1); |
| } |
| |
| int32_t BigInteger::Compare(const BigInteger& other, bool ignoreSign) const |
| { |
| // What we should return if magnitude is greater. |
| int32_t mgt = 1; |
| |
| if (!ignoreSign) |
| { |
| if (sign != other.sign) |
| return sign > other.sign ? 1 : -1; |
| else |
| mgt = sign; |
| } |
| |
| if (mag.GetSize() != other.mag.GetSize()) |
| return mag.GetSize() > other.mag.GetSize() ? mgt : -mgt; |
| |
| for (int32_t i = mag.GetSize() - 1; i >= 0; --i) |
| { |
| if (mag[i] == other.mag[i]) |
| continue; |
| else if (mag[i] > other.mag[i]) |
| return mgt; |
| else |
| return -mgt; |
| } |
| |
| return 0; |
| } |
| |
| int64_t BigInteger::ToInt64() const |
| { |
| return (static_cast<uint64_t>(GetMagInt(1)) << 32) | GetMagInt(0); |
| } |
| |
| void BigInteger::GetPowerOfTen(int32_t pow, BigInteger& res) |
| { |
| using namespace common; |
| |
| assert(pow >= 0); |
| |
| if (pow < bits::UINT64_MAX_PRECISION) |
| { |
| res.AssignUint64(bits::TenPowerU64(pow)); |
| |
| return; |
| } |
| |
| res.AssignInt64(10); |
| res.Pow(pow); |
| } |
| |
| uint32_t BigInteger::GetMagInt(int32_t n) const |
| { |
| assert(n >= 0); |
| |
| if (n >= mag.GetSize()) |
| return sign > 0 ? 0 : -1; |
| |
| return sign * mag[n]; |
| } |
| |
| void BigInteger::Divide(const BigInteger& divisor, BigInteger& res, BigInteger* rem) const |
| { |
| // Can't divide by zero. |
| if (divisor.mag.IsEmpty()) |
| throw IgniteError(IgniteError::IGNITE_ERR_ILLEGAL_ARGUMENT, "Division by zero."); |
| |
| int32_t compRes = Compare(divisor, true); |
| |
| int8_t resSign = sign * divisor.sign; |
| |
| // The same magnitude. Result is [-]1 and remainder is zero. |
| if (compRes == 0) |
| { |
| res.AssignInt64(resSign); |
| |
| if (rem) |
| rem->AssignInt64(0); |
| |
| return; |
| } |
| |
| // Divisor is greater than this. Result is 0 and remainder is this. |
| if (compRes == -1) |
| { |
| // Order is important here! Copy to rem first to handle the case |
| // when &res == this. |
| if (rem) |
| rem->Assign(*this); |
| |
| res.AssignInt64(0); |
| |
| return; |
| } |
| |
| // If divisor is [-]1 result is [-]this and remainder is zero. |
| if (divisor.GetBitLength() == 1) |
| { |
| // Once again: order is important. |
| res.Assign(*this); |
| res.sign = sign * divisor.sign; |
| |
| if (rem) |
| rem->AssignInt64(0); |
| |
| return; |
| } |
| |
| // Trivial case. |
| if (mag.GetSize() <= 2) |
| { |
| uint64_t u = mag[0]; |
| uint64_t v = divisor.mag[0]; |
| |
| if (mag.GetSize() == 2) |
| u |= static_cast<uint64_t>(mag[1]) << 32; |
| |
| if (divisor.mag.GetSize() == 2) |
| v |= static_cast<uint64_t>(divisor.mag[1]) << 32; |
| |
| // Divisor can not be 1, or 0. |
| assert(v > 1); |
| |
| // It should also be less than dividend. |
| assert(v < u); |
| |
| // (u / v) is always fits into int64_t because abs(v) >= 2. |
| res.AssignInt64(resSign * static_cast<int64_t>(u / v)); |
| |
| // (u % v) is always fits into int64_t because (u > v) -> |
| // (u % v) < (u / 2). |
| if (rem) |
| rem->AssignInt64(resSign * static_cast<int64_t>(u % v)); |
| |
| return; |
| } |
| |
| // Using Knuth division algorithm D for common case. |
| |
| // Short aliases. |
| const MagArray& u = mag; |
| const MagArray& v = divisor.mag; |
| MagArray& q = res.mag; |
| int32_t ulen = u.GetSize(); |
| int32_t vlen = v.GetSize(); |
| |
| // First we need to normilize divisor. |
| MagArray nv; |
| nv.Resize(v.GetSize()); |
| |
| int32_t shift = bits::NumberOfLeadingZerosU32(v.Back()); |
| ShiftLeft(v.GetData(), vlen, nv.GetData(), shift); |
| |
| // Divisor is normilized. Now we need to normilize divident. |
| MagArray nu; |
| |
| // First find out what is the size of it. |
| if (bits::NumberOfLeadingZerosU32(u.Back()) >= shift) |
| { |
| // Everything is the same as with divisor. Just add leading zero. |
| nu.Resize(ulen + 1); |
| |
| ShiftLeft(u.GetData(), ulen, nu.GetData(), shift); |
| |
| assert((static_cast<uint64_t>(u.Back()) >> (32 - shift)) == 0); |
| } |
| else |
| { |
| // We need one more byte here. Also adding leading zero. |
| nu.Resize(ulen + 2); |
| |
| ShiftLeft(u.GetData(), ulen, nu.GetData(), shift); |
| |
| nu[ulen] = u[ulen - 1] >> (32 - shift); |
| |
| assert(nu[ulen] != 0); |
| } |
| |
| assert(nu.Back() == 0); |
| |
| // Resizing resulting array. |
| q.Resize(ulen - vlen + 1); |
| |
| // Main loop |
| for (int32_t i = ulen - vlen; i >= 0; --i) |
| { |
| uint64_t base = bits::MakeU64(nu[i + vlen], nu[i + vlen - 1]); |
| |
| uint64_t qhat = base / nv[vlen - 1]; // Estimated quotient. |
| uint64_t rhat = base % nv[vlen - 1]; // A remainder. |
| |
| // Adjusting result if needed. |
| while (qhat > UINT32_MAX || |
| ((qhat * nv[vlen - 2]) > ((UINT32_MAX + static_cast<uint64_t>(1)) * rhat + nu[i + vlen - 2]))) |
| { |
| --qhat; |
| rhat += nv[vlen - 1]; |
| |
| if (rhat > UINT32_MAX) |
| break; |
| } |
| |
| uint32_t qhat32 = static_cast<uint32_t>(qhat); |
| |
| // Multiply and subtract. |
| uint32_t carry = MultiplyAndSubstruct(nu.GetData() + i, nv.GetData(), vlen, qhat32); |
| |
| int64_t difference = nu[i + vlen] - carry; |
| |
| nu[i + vlen] = static_cast<uint32_t>(difference); |
| |
| if (difference < 0) |
| { |
| --qhat32; |
| carry = common::Add(nu.GetData() + i, nv.GetData(), vlen); |
| |
| assert(carry == 0); |
| } |
| |
| q[i] = qhat32; |
| } |
| |
| res.sign = resSign; |
| res.Normalize(); |
| |
| // If remainder is needed unnormolize it. |
| if (rem) |
| { |
| rem->sign = resSign; |
| rem->mag.Resize(vlen); |
| |
| ShiftRight(nu.GetData(), rem->mag.GetSize(), rem->mag.GetData(), shift); |
| |
| rem->Normalize(); |
| } |
| } |
| |
| void BigInteger::Normalize() |
| { |
| int32_t lastNonZero = mag.GetSize() - 1; |
| while (lastNonZero >= 0 && mag[lastNonZero] == 0) |
| --lastNonZero; |
| |
| mag.Resize(lastNonZero + 1); |
| } |
| |
| bool operator==(const BigInteger& val1, const BigInteger& val2) |
| { |
| return val1.Compare(val2) == 0; |
| } |
| |
| bool operator!=(const BigInteger& val1, const BigInteger& val2) |
| { |
| return val1.Compare(val2) != 0; |
| } |
| |
| bool operator<(const BigInteger& val1, const BigInteger& val2) |
| { |
| return val1.Compare(val2) < 0; |
| } |
| |
| bool operator<=(const BigInteger& val1, const BigInteger& val2) |
| { |
| return val1.Compare(val2) <= 0; |
| } |
| |
| bool operator>(const BigInteger& val1, const BigInteger& val2) |
| { |
| return val1.Compare(val2) > 0; |
| } |
| |
| bool operator>=(const BigInteger& val1, const BigInteger& val2) |
| { |
| return val1.Compare(val2) >= 0; |
| } |
| } |
| } |
| |
