// Copyright 2021 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "src/bigint/bigint-internal.h" #include "src/bigint/digit-arithmetic.h" #include "src/bigint/util.h" #include "src/bigint/vector-arithmetic.h" namespace v8 { namespace bigint { void BitwiseAnd_PosPos(RWDigits Z, Digits X, Digits Y) { int pairs = std::min(X.len(), Y.len()); DCHECK(Z.len() >= pairs); int i = 0; for (; i < pairs; i++) Z[i] = X[i] & Y[i]; for (; i < Z.len(); i++) Z[i] = 0; } void BitwiseAnd_NegNeg(RWDigits Z, Digits X, Digits Y) { // (-x) & (-y) == ~(x-1) & ~(y-1) // == ~((x-1) | (y-1)) // == -(((x-1) | (y-1)) + 1) int pairs = std::min(X.len(), Y.len()); digit_t x_borrow = 1; digit_t y_borrow = 1; int i = 0; for (; i < pairs; i++) { Z[i] = digit_sub(X[i], x_borrow, &x_borrow) | digit_sub(Y[i], y_borrow, &y_borrow); } // (At least) one of the next two loops will perform zero iterations: for (; i < X.len(); i++) Z[i] = digit_sub(X[i], x_borrow, &x_borrow); for (; i < Y.len(); i++) Z[i] = digit_sub(Y[i], y_borrow, &y_borrow); DCHECK(x_borrow == 0); DCHECK(y_borrow == 0); for (; i < Z.len(); i++) Z[i] = 0; Add(Z, 1); } void BitwiseAnd_PosNeg(RWDigits Z, Digits X, Digits Y) { // x & (-y) == x & ~(y-1) int pairs = std::min(X.len(), Y.len()); digit_t borrow = 1; int i = 0; for (; i < pairs; i++) Z[i] = X[i] & ~digit_sub(Y[i], borrow, &borrow); for (; i < X.len(); i++) Z[i] = X[i]; for (; i < Z.len(); i++) Z[i] = 0; } void BitwiseOr_PosPos(RWDigits Z, Digits X, Digits Y) { int pairs = std::min(X.len(), Y.len()); int i = 0; for (; i < pairs; i++) Z[i] = X[i] | Y[i]; // (At least) one of the next two loops will perform zero iterations: for (; i < X.len(); i++) Z[i] = X[i]; for (; i < Y.len(); i++) Z[i] = Y[i]; for (; i < Z.len(); i++) Z[i] = 0; } void BitwiseOr_NegNeg(RWDigits Z, Digits X, Digits Y) { // (-x) | (-y) == ~(x-1) | ~(y-1) // == ~((x-1) & (y-1)) // == -(((x-1) & (y-1)) + 1) int pairs = std::min(X.len(), Y.len()); digit_t x_borrow = 1; digit_t y_borrow = 1; int i = 0; for (; i < pairs; i++) { Z[i] = digit_sub(X[i], x_borrow, &x_borrow) & digit_sub(Y[i], y_borrow, &y_borrow); } // Any leftover borrows don't matter, the '&' would drop them anyway. for (; i < Z.len(); i++) Z[i] = 0; Add(Z, 1); } void BitwiseOr_PosNeg(RWDigits Z, Digits X, Digits Y) { // x | (-y) == x | ~(y-1) == ~((y-1) &~ x) == -(((y-1) &~ x) + 1) int pairs = std::min(X.len(), Y.len()); digit_t borrow = 1; int i = 0; for (; i < pairs; i++) Z[i] = digit_sub(Y[i], borrow, &borrow) & ~X[i]; for (; i < Y.len(); i++) Z[i] = digit_sub(Y[i], borrow, &borrow); DCHECK(borrow == 0); for (; i < Z.len(); i++) Z[i] = 0; Add(Z, 1); } void BitwiseXor_PosPos(RWDigits Z, Digits X, Digits Y) { int pairs = X.len(); if (Y.len() < X.len()) { std::swap(X, Y); pairs = X.len(); } DCHECK(X.len() <= Y.len()); int i = 0; for (; i < pairs; i++) Z[i] = X[i] ^ Y[i]; for (; i < Y.len(); i++) Z[i] = Y[i]; for (; i < Z.len(); i++) Z[i] = 0; } void BitwiseXor_NegNeg(RWDigits Z, Digits X, Digits Y) { // (-x) ^ (-y) == ~(x-1) ^ ~(y-1) == (x-1) ^ (y-1) int pairs = std::min(X.len(), Y.len()); digit_t x_borrow = 1; digit_t y_borrow = 1; int i = 0; for (; i < pairs; i++) { Z[i] = digit_sub(X[i], x_borrow, &x_borrow) ^ digit_sub(Y[i], y_borrow, &y_borrow); } // (At least) one of the next two loops will perform zero iterations: for (; i < X.len(); i++) Z[i] = digit_sub(X[i], x_borrow, &x_borrow); for (; i < Y.len(); i++) Z[i] = digit_sub(Y[i], y_borrow, &y_borrow); DCHECK(x_borrow == 0); DCHECK(y_borrow == 0); for (; i < Z.len(); i++) Z[i] = 0; } void BitwiseXor_PosNeg(RWDigits Z, Digits X, Digits Y) { // x ^ (-y) == x ^ ~(y-1) == ~(x ^ (y-1)) == -((x ^ (y-1)) + 1) int pairs = std::min(X.len(), Y.len()); digit_t borrow = 1; int i = 0; for (; i < pairs; i++) Z[i] = X[i] ^ digit_sub(Y[i], borrow, &borrow); // (At least) one of the next two loops will perform zero iterations: for (; i < X.len(); i++) Z[i] = X[i]; for (; i < Y.len(); i++) Z[i] = digit_sub(Y[i], borrow, &borrow); DCHECK(borrow == 0); for (; i < Z.len(); i++) Z[i] = 0; Add(Z, 1); } void LeftShift(RWDigits Z, Digits X, digit_t shift) { int digit_shift = static_cast<int>(shift / kDigitBits); int bits_shift = static_cast<int>(shift % kDigitBits); int i = 0; for (; i < digit_shift; ++i) Z[i] = 0; if (bits_shift == 0) { for (; i < X.len() + digit_shift; ++i) Z[i] = X[i - digit_shift]; for (; i < Z.len(); ++i) Z[i] = 0; } else { digit_t carry = 0; for (; i < X.len() + digit_shift; ++i) { digit_t d = X[i - digit_shift]; Z[i] = (d << bits_shift) | carry; carry = d >> (kDigitBits - bits_shift); } if (carry != 0) Z[i++] = carry; for (; i < Z.len(); ++i) Z[i] = 0; } } int RightShift_ResultLength(Digits X, bool x_sign, digit_t shift, RightShiftState* state) { int digit_shift = static_cast<int>(shift / kDigitBits); int bits_shift = static_cast<int>(shift % kDigitBits); int result_length = X.len() - digit_shift; if (result_length <= 0) return 0; // For negative numbers, round down if any bit was shifted out (so that e.g. // -5n >> 1n == -3n and not -2n). Check now whether this will happen and // whether it can cause overflow into a new digit. bool must_round_down = false; if (x_sign) { const digit_t mask = (static_cast<digit_t>(1) << bits_shift) - 1; if ((X[digit_shift] & mask) != 0) { must_round_down = true; } else { for (int i = 0; i < digit_shift; i++) { if (X[i] != 0) { must_round_down = true; break; } } } } // If bits_shift is non-zero, it frees up bits, preventing overflow. if (must_round_down && bits_shift == 0) { // Overflow cannot happen if the most significant digit has unset bits. const bool rounding_can_overflow = digit_ismax(X.msd()); if (rounding_can_overflow) ++result_length; } if (state) { DCHECK(!must_round_down || x_sign); state->must_round_down = must_round_down; } return result_length; } void RightShift(RWDigits Z, Digits X, digit_t shift, const RightShiftState& state) { int digit_shift = static_cast<int>(shift / kDigitBits); int bits_shift = static_cast<int>(shift % kDigitBits); int i = 0; if (bits_shift == 0) { for (; i < X.len() - digit_shift; ++i) Z[i] = X[i + digit_shift]; } else { digit_t carry = X[digit_shift] >> bits_shift; for (; i < X.len() - digit_shift - 1; ++i) { digit_t d = X[i + digit_shift + 1]; Z[i] = (d << (kDigitBits - bits_shift)) | carry; carry = d >> bits_shift; } Z[i++] = carry; } for (; i < Z.len(); ++i) Z[i] = 0; if (state.must_round_down) { // Rounding down (a negative value) means adding one to // its absolute value. This cannot overflow. Add(Z, 1); } } namespace { // Z := (least significant n bits of X). void TruncateToNBits(RWDigits Z, Digits X, int n) { int digits = DIV_CEIL(n, kDigitBits); int bits = n % kDigitBits; // Copy all digits except the MSD. int last = digits - 1; for (int i = 0; i < last; i++) { Z[i] = X[i]; } // The MSD might contain extra bits that we don't want. digit_t msd = X[last]; if (bits != 0) { int drop = kDigitBits - bits; msd = (msd << drop) >> drop; } Z[last] = msd; } // Z := 2**n - (least significant n bits of X). void TruncateAndSubFromPowerOfTwo(RWDigits Z, Digits X, int n) { int digits = DIV_CEIL(n, kDigitBits); int bits = n % kDigitBits; // Process all digits except the MSD. Take X's digits, then simulate leading // zeroes. int last = digits - 1; int have_x = std::min(last, X.len()); digit_t borrow = 0; int i = 0; for (; i < have_x; i++) Z[i] = digit_sub2(0, X[i], borrow, &borrow); for (; i < last; i++) Z[i] = digit_sub(0, borrow, &borrow); // The MSD might contain extra bits that we don't want. digit_t msd = last < X.len() ? X[last] : 0; if (bits == 0) { Z[last] = digit_sub2(0, msd, borrow, &borrow); } else { int drop = kDigitBits - bits; msd = (msd << drop) >> drop; digit_t minuend_msd = static_cast<digit_t>(1) << bits; digit_t result_msd = digit_sub2(minuend_msd, msd, borrow, &borrow); DCHECK(borrow == 0); // result < 2^n. // If all subtracted bits were zero, we have to get rid of the // materialized minuend_msd again. Z[last] = result_msd & (minuend_msd - 1); } } } // namespace // Returns -1 when the operation would return X unchanged. int AsIntNResultLength(Digits X, bool x_negative, int n) { int needed_digits = DIV_CEIL(n, kDigitBits); // Generally: decide based on number of digits, and bits in the top digit. if (X.len() < needed_digits) return -1; if (X.len() > needed_digits) return needed_digits; digit_t top_digit = X[needed_digits - 1]; digit_t compare_digit = digit_t{1} << ((n - 1) % kDigitBits); if (top_digit < compare_digit) return -1; if (top_digit > compare_digit) return needed_digits; // Special case: if X == -2**(n-1), truncation is a no-op. if (!x_negative) return needed_digits; for (int i = needed_digits - 2; i >= 0; i--) { if (X[i] != 0) return needed_digits; } return -1; } bool AsIntN(RWDigits Z, Digits X, bool x_negative, int n) { DCHECK(X.len() > 0); DCHECK(n > 0); DCHECK(AsIntNResultLength(X, x_negative, n) > 0); int needed_digits = DIV_CEIL(n, kDigitBits); digit_t top_digit = X[needed_digits - 1]; digit_t compare_digit = digit_t{1} << ((n - 1) % kDigitBits); // The canonical algorithm would be: convert negative numbers to two's // complement representation, truncate, convert back to sign+magnitude. To // avoid the conversions, we predict what the result would be: // When the (n-1)th bit is not set: // - truncate the absolute value // - preserve the sign. // When the (n-1)th bit is set: // - subtract the truncated absolute value from 2**n to simulate two's // complement representation // - flip the sign, unless it's the special case where the input is negative // and the result is the minimum n-bit integer. E.g. asIntN(3, -12) => -4. bool has_bit = (top_digit & compare_digit) == compare_digit; if (!has_bit) { TruncateToNBits(Z, X, n); return x_negative; } TruncateAndSubFromPowerOfTwo(Z, X, n); if (!x_negative) return true; // Result is negative. // Scan for the special case (see above): if all bits below the (n-1)th // digit are zero, the result is negative. if ((top_digit & (compare_digit - 1)) != 0) return false; for (int i = needed_digits - 2; i >= 0; i--) { if (X[i] != 0) return false; } return true; } // Returns -1 when the operation would return X unchanged. int AsUintN_Pos_ResultLength(Digits X, int n) { int needed_digits = DIV_CEIL(n, kDigitBits); if (X.len() < needed_digits) return -1; if (X.len() > needed_digits) return needed_digits; int bits_in_top_digit = n % kDigitBits; if (bits_in_top_digit == 0) return -1; digit_t top_digit = X[needed_digits - 1]; if ((top_digit >> bits_in_top_digit) == 0) return -1; return needed_digits; } void AsUintN_Pos(RWDigits Z, Digits X, int n) { DCHECK(AsUintN_Pos_ResultLength(X, n) > 0); TruncateToNBits(Z, X, n); } void AsUintN_Neg(RWDigits Z, Digits X, int n) { TruncateAndSubFromPowerOfTwo(Z, X, n); } } // namespace bigint } // namespace v8