src/builtins/builtins-bigint.tq

// Copyright 2019 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/builtins/builtins-bigint-gen.h'

namespace bigint {

const kPositiveSign: uint32 = 0;
const kNegativeSign: uint32 = 1;
const kGreaterThan: intptr = 1;
const kLessThan: intptr = -1;

const kMustRoundDownBitShift: uint32 = 30;

extern macro BigIntBuiltinsAssembler::CppAbsoluteAddAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppAbsoluteSubAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppAbsoluteMulAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): int32;
extern macro BigIntBuiltinsAssembler::CppAbsoluteDivAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): int32;
extern macro BigIntBuiltinsAssembler::CppAbsoluteModAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): int32;
extern macro BigIntBuiltinsAssembler::CppBitwiseAndPosPosAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppBitwiseAndNegNegAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppBitwiseAndPosNegAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppBitwiseOrPosPosAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppBitwiseOrNegNegAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppBitwiseOrPosNegAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppBitwiseXorPosPosAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppBitwiseXorNegNegAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppBitwiseXorPosNegAndCanonicalize(
    MutableBigInt, BigIntBase, BigIntBase): void;
extern macro BigIntBuiltinsAssembler::CppLeftShiftAndCanonicalize(
    MutableBigInt, BigIntBase, intptr): void;
extern macro BigIntBuiltinsAssembler::CppRightShiftResultLength(
    BigIntBase, uint32, intptr): uint32;
extern macro BigIntBuiltinsAssembler::CppRightShiftAndCanonicalize(
    MutableBigInt, BigIntBase, intptr, uint32): void;
extern macro BigIntBuiltinsAssembler::CppAbsoluteCompare(
    BigIntBase, BigIntBase): int32;

extern macro BigIntBuiltinsAssembler::ReadBigIntSign(BigIntBase): uint32;
extern macro BigIntBuiltinsAssembler::ReadBigIntLength(BigIntBase): intptr;
extern macro BigIntBuiltinsAssembler::WriteBigIntSignAndLength(
    MutableBigInt, uint32, intptr): void;

extern macro CodeStubAssembler::AllocateBigInt(intptr): MutableBigInt;
extern macro CodeStubAssembler::AllocateRawBigInt(intptr): MutableBigInt;
extern macro CodeStubAssembler::StoreBigIntDigit(
    MutableBigInt, intptr, uintptr): void;
extern macro CodeStubAssembler::LoadBigIntDigit(BigIntBase, intptr): uintptr;

macro IsCanonicalized(bigint: BigIntBase): bool {
  const length = ReadBigIntLength(bigint);

  if (length == 0) {
    return ReadBigIntSign(bigint) == kPositiveSign;
  }

  return LoadBigIntDigit(bigint, length - 1) != 0;
}

macro InvertSign(sign: uint32): uint32 {
  return sign == kPositiveSign ? kNegativeSign : kPositiveSign;
}

macro AllocateEmptyBigIntNoThrow(
    implicit context: Context)(sign: uint32,
    length: intptr): MutableBigInt labels BigIntTooBig {
  if (length > kBigIntMaxLength) {
    goto BigIntTooBig;
  }
  const result: MutableBigInt = AllocateRawBigInt(length);

  WriteBigIntSignAndLength(result, sign, length);
  return result;
}

macro AllocateEmptyBigInt(
    implicit context: Context)(sign: uint32, length: intptr): MutableBigInt {
  try {
    return AllocateEmptyBigIntNoThrow(sign, length) otherwise BigIntTooBig;
  } label BigIntTooBig {
    ThrowRangeError(MessageTemplate::kBigIntTooBig);
  }
}

macro MutableBigIntAbsoluteCompare(x: BigIntBase, y: BigIntBase): int32 {
  return CppAbsoluteCompare(x, y);
}

macro MutableBigIntAbsoluteSub(
    implicit context: Context)(x: BigInt, y: BigInt,
    resultSign: uint32): BigInt {
  const xlength = ReadBigIntLength(x);
  const ylength = ReadBigIntLength(y);
  const xsign = ReadBigIntSign(x);

  dcheck(MutableBigIntAbsoluteCompare(x, y) >= 0);
  if (xlength == 0) {
    dcheck(ylength == 0);
    return x;
  }

  if (ylength == 0) {
    return resultSign == xsign ? x : BigIntUnaryMinus(x);
  }

  const result = AllocateEmptyBigInt(resultSign, xlength);
  CppAbsoluteSubAndCanonicalize(result, x, y);
  return Convert<BigInt>(result);
}

macro MutableBigIntAbsoluteAdd(
    implicit context: Context)(xBigint: BigInt, yBigint: BigInt,
    resultSign: uint32): BigInt labels BigIntTooBig {
  let xlength = ReadBigIntLength(xBigint);
  let ylength = ReadBigIntLength(yBigint);

  let x = xBigint;
  let y = yBigint;
  if (xlength < ylength) {
    // Swap x and y so that x is longer.
    x = yBigint;
    y = xBigint;
    const tempLength = xlength;
    xlength = ylength;
    ylength = tempLength;
  }

  // case: 0n + 0n
  if (xlength == 0) {
    dcheck(ylength == 0);
    return x;
  }

  // case: x + 0n
  if (ylength == 0) {
    return resultSign == ReadBigIntSign(x) ? x : BigIntUnaryMinus(x);
  }

  // case: x + y
  const result = AllocateEmptyBigIntNoThrow(resultSign, xlength + 1)
      otherwise BigIntTooBig;
  CppAbsoluteAddAndCanonicalize(result, x, y);
  return Convert<BigInt>(result);
}

macro BigIntAddImpl(implicit context: Context)(x: BigInt, y: BigInt): BigInt
    labels BigIntTooBig {
  const xsign = ReadBigIntSign(x);
  const ysign = ReadBigIntSign(y);
  if (xsign == ysign) {
    // x + y == x + y
    // -x + -y == -(x + y)
    return MutableBigIntAbsoluteAdd(x, y, xsign) otherwise BigIntTooBig;
  }

  // x + -y == x - y == -(y - x)
  // -x + y == y - x == -(x - y)
  if (MutableBigIntAbsoluteCompare(x, y) >= 0) {
    return MutableBigIntAbsoluteSub(x, y, xsign);
  }
  return MutableBigIntAbsoluteSub(y, x, InvertSign(xsign));
}

builtin BigIntAddNoThrow(implicit context: Context)(x: BigInt,
                          y: BigInt): Numeric {
  try {
    return BigIntAddImpl(x, y) otherwise BigIntTooBig;
  } label BigIntTooBig {
    // Smi sentinal is used to signal BigIntTooBig exception.
    return Convert<Smi>(0);
  }
}

builtin BigIntAdd(implicit context: Context)(xNum: Numeric,
                   yNum: Numeric): BigInt {
  try {
    const x = Cast<BigInt>(xNum) otherwise MixedTypes;
    const y = Cast<BigInt>(yNum) otherwise MixedTypes;

    return BigIntAddImpl(x, y) otherwise BigIntTooBig;
  } label MixedTypes {
    ThrowTypeError(MessageTemplate::kBigIntMixedTypes);
  } label BigIntTooBig {
    ThrowRangeError(MessageTemplate::kBigIntTooBig);
  }
}

macro BigIntSubtractImpl(implicit context: Context)(x: BigInt,
                            y: BigInt): BigInt labels BigIntTooBig {
  const xsign = ReadBigIntSign(x);
  const ysign = ReadBigIntSign(y);
  if (xsign != ysign) {
    // x - (-y) == x + y
    // (-x) - y == -(x + y)
    return MutableBigIntAbsoluteAdd(x, y, xsign) otherwise BigIntTooBig;
  }

  // x - y == -(y - x)
  // (-x) - (-y) == y - x == -(x - y)
  if (MutableBigIntAbsoluteCompare(x, y) >= 0) {
    return MutableBigIntAbsoluteSub(x, y, xsign);
  }
  return MutableBigIntAbsoluteSub(y, x, InvertSign(xsign));
}

builtin BigIntSubtractNoThrow(
    implicit context: Context)(x: BigInt, y: BigInt): Numeric {
  try {
    return BigIntSubtractImpl(x, y) otherwise BigIntTooBig;
  } label BigIntTooBig {
    // Smi sentinal is used to signal BigIntTooBig exception.
    return Convert<Smi>(0);
  }
}

builtin BigIntSubtract(
    implicit context: Context)(xNum: Numeric, yNum: Numeric): BigInt {
  try {
    const x = Cast<BigInt>(xNum) otherwise MixedTypes;
    const y = Cast<BigInt>(yNum) otherwise MixedTypes;

    return BigIntSubtractImpl(x, y) otherwise BigIntTooBig;
  } label MixedTypes {
    ThrowTypeError(MessageTemplate::kBigIntMixedTypes);
  } label BigIntTooBig {
    ThrowRangeError(MessageTemplate::kBigIntTooBig);
  }
}

macro BigIntMultiplyImpl(implicit context: Context)(x: BigInt, y: BigInt):
    BigInt labels BigIntTooBig, TerminationRequested {
  const xlength = ReadBigIntLength(x);
  const ylength = ReadBigIntLength(y);

  // case: 0n * y
  if (xlength == 0) {
    return x;
  }

  // case: x * 0n
  if (ylength == 0) {
    return y;
  }

  // case: x * y
  const xsign = ReadBigIntSign(x);
  const ysign = ReadBigIntSign(y);
  const resultSign = (xsign != ysign) ? kNegativeSign : kPositiveSign;
  const result = AllocateEmptyBigIntNoThrow(resultSign, xlength + ylength)
      otherwise BigIntTooBig;

  if (CppAbsoluteMulAndCanonicalize(result, x, y) == 1) {
    goto TerminationRequested;
  }

  return Convert<BigInt>(result);
}

builtin BigIntMultiplyNoThrow(
    implicit context: Context)(x: BigInt, y: BigInt): Numeric {
  try {
    return BigIntMultiplyImpl(x, y) otherwise BigIntTooBig,
           TerminationRequested;
  } label BigIntTooBig {
    // Smi sentinel 0 is used to signal BigIntTooBig exception.
    return Convert<Smi>(0);
  } label TerminationRequested {
    // Smi sentinel 1 is used to signal TerminateExecution exception.
    return Convert<Smi>(1);
  }
}

builtin BigIntMultiply(
    implicit context: Context)(xNum: Numeric, yNum: Numeric): BigInt {
  try {
    const x = Cast<BigInt>(xNum) otherwise MixedTypes;
    const y = Cast<BigInt>(yNum) otherwise MixedTypes;

    return BigIntMultiplyImpl(x, y) otherwise BigIntTooBig,
           TerminationRequested;
  } label MixedTypes {
    ThrowTypeError(MessageTemplate::kBigIntMixedTypes);
  } label BigIntTooBig {
    ThrowRangeError(MessageTemplate::kBigIntTooBig);
  } label TerminationRequested {
    TerminateExecution();
  }
}

macro BigIntDivideImpl(implicit context: Context)(x: BigInt, y: BigInt):
    BigInt labels BigIntDivZero, TerminationRequested {
  const xlength = ReadBigIntLength(x);
  const ylength = ReadBigIntLength(y);

  // case: x / 0n
  if (ylength == 0) {
    goto BigIntDivZero;
  }

  // case: x / y, where x < y
  if (MutableBigIntAbsoluteCompare(x, y) < 0) {
    const zero = AllocateEmptyBigInt(kPositiveSign, 0);
    return Convert<BigInt>(zero);
  }

  // case: x / 1n
  const xsign = ReadBigIntSign(x);
  const ysign = ReadBigIntSign(y);
  const resultSign = (xsign != ysign) ? kNegativeSign : kPositiveSign;
  if (ylength == 1 && LoadBigIntDigit(y, 0) == 1) {
    return resultSign == xsign ? x : BigIntUnaryMinus(x);
  }

  // case: x / y
  let resultLength = xlength - ylength + 1;
  // This implies a *very* conservative estimate that kBarrettThreshold > 10.
  if (ylength > 10) resultLength++;
  const result = AllocateEmptyBigIntNoThrow(resultSign, resultLength)
      otherwise unreachable;

  if (CppAbsoluteDivAndCanonicalize(result, x, y) == 1) {
    goto TerminationRequested;
  }

  return Convert<BigInt>(result);
}

builtin BigIntDivideNoThrow(implicit context: Context)(x: BigInt,
                             y: BigInt): Numeric {
  try {
    return BigIntDivideImpl(x, y) otherwise BigIntDivZero, TerminationRequested;
  } label BigIntDivZero {
    // Smi sentinel 0 is used to signal BigIntDivZero exception.
    return Convert<Smi>(0);
  } label TerminationRequested {
    // Smi sentinel 1 is used to signal TerminateExecution exception.
    return Convert<Smi>(1);
  }
}

builtin BigIntDivide(implicit context: Context)(xNum: Numeric,
                      yNum: Numeric): BigInt {
  try {
    const x = Cast<BigInt>(xNum) otherwise MixedTypes;
    const y = Cast<BigInt>(yNum) otherwise MixedTypes;

    return BigIntDivideImpl(x, y) otherwise BigIntDivZero, TerminationRequested;
  } label MixedTypes {
    ThrowTypeError(MessageTemplate::kBigIntMixedTypes);
  } label BigIntDivZero {
    ThrowRangeError(MessageTemplate::kBigIntDivZero);
  } label TerminationRequested {
    TerminateExecution();
  }
}

macro BigIntModulusImpl(implicit context: Context)(x: BigInt, y: BigInt):
    BigInt labels BigIntDivZero, TerminationRequested {
  const ylength = ReadBigIntLength(y);

  // case: x % 0n
  if (ylength == 0) {
    goto BigIntDivZero;
  }

  // case: x % y, where x < y
  if (MutableBigIntAbsoluteCompare(x, y) < 0) {
    return x;
  }

  // case: x % 1n or x % -1n
  if (ylength == 1 && LoadBigIntDigit(y, 0) == 1) {
    const zero = AllocateEmptyBigInt(kPositiveSign, 0);
    return Convert<BigInt>(zero);
  }

  // case: x % y
  const resultSign = ReadBigIntSign(x);
  const resultLength = ylength;
  const result = AllocateEmptyBigIntNoThrow(resultSign, resultLength)
      otherwise unreachable;

  if (CppAbsoluteModAndCanonicalize(result, x, y) == 1) {
    goto TerminationRequested;
  }

  return Convert<BigInt>(result);
}

builtin BigIntModulusNoThrow(implicit context: Context)(x: BigInt,
                              y: BigInt): Numeric {
  try {
    return BigIntModulusImpl(x, y) otherwise BigIntDivZero,
           TerminationRequested;
  } label BigIntDivZero {
    // Smi sentinel 0 is used to signal BigIntDivZero exception.
    return Convert<Smi>(0);
  } label TerminationRequested {
    // Smi sentinel 1 is used to signal TerminateExecution exception.
    return Convert<Smi>(1);
  }
}

builtin BigIntModulus(
    implicit context: Context)(xNum: Numeric, yNum: Numeric): BigInt {
  try {
    const x = Cast<BigInt>(xNum) otherwise MixedTypes;
    const y = Cast<BigInt>(yNum) otherwise MixedTypes;

    return BigIntModulusImpl(x, y) otherwise BigIntDivZero,
           TerminationRequested;
  } label MixedTypes {
    ThrowTypeError(MessageTemplate::kBigIntMixedTypes);
  } label BigIntDivZero {
    ThrowRangeError(MessageTemplate::kBigIntDivZero);
  } label TerminationRequested {
    TerminateExecution();
  }
}

macro BigIntBitwiseAndImpl(implicit context: Context)(x: BigInt,
                              y: BigInt): BigInt labels BigIntTooBig {
  const xlength = ReadBigIntLength(x);
  const ylength = ReadBigIntLength(y);

  // case: 0n & y
  if (xlength == 0) {
    return x;
  }

  // case: x & 0n
  if (ylength == 0) {
    return y;
  }

  const xsign = ReadBigIntSign(x);
  const ysign = ReadBigIntSign(y);

  if (xsign == kPositiveSign && ysign == kPositiveSign) {
    const resultLength = (xlength < ylength) ? xlength : ylength;
    const result = AllocateEmptyBigIntNoThrow(kPositiveSign, resultLength)
        otherwise unreachable;
    CppBitwiseAndPosPosAndCanonicalize(result, x, y);
    return Convert<BigInt>(result);
  } else if (xsign == kNegativeSign && ysign == kNegativeSign) {
    const resultLength = ((xlength > ylength) ? xlength : ylength) + 1;
    const result = AllocateEmptyBigIntNoThrow(kNegativeSign, resultLength)
        otherwise BigIntTooBig;
    CppBitwiseAndNegNegAndCanonicalize(result, x, y);
    return Convert<BigInt>(result);
  } else if (xsign == kPositiveSign && ysign == kNegativeSign) {
    const result = AllocateEmptyBigIntNoThrow(kPositiveSign, xlength)
        otherwise unreachable;
    CppBitwiseAndPosNegAndCanonicalize(result, x, y);
    return Convert<BigInt>(result);
  } else {
    const result = AllocateEmptyBigIntNoThrow(kPositiveSign, ylength)
        otherwise unreachable;
    CppBitwiseAndPosNegAndCanonicalize(result, y, x);
    return Convert<BigInt>(result);
  }
}

builtin BigIntBitwiseAndNoThrow(
    implicit context: Context)(x: BigInt, y: BigInt): Numeric {
  try {
    return BigIntBitwiseAndImpl(x, y) otherwise BigIntTooBig;
  } label BigIntTooBig {
    // Smi sentinel 0 is used to signal BigIntTooBig exception.
    return Convert<Smi>(0);
  }
}

builtin BigIntBitwiseAnd(
    implicit context: Context)(xNum: Numeric, yNum: Numeric): BigInt {
  try {
    const x = Cast<BigInt>(xNum) otherwise MixedTypes;
    const y = Cast<BigInt>(yNum) otherwise MixedTypes;

    return BigIntBitwiseAndImpl(x, y) otherwise BigIntTooBig;
  } label MixedTypes {
    ThrowTypeError(MessageTemplate::kBigIntMixedTypes);
  } label BigIntTooBig {
    ThrowRangeError(MessageTemplate::kBigIntTooBig);
  }
}

macro BigIntBitwiseOrImpl(implicit context: Context)(x: BigInt,
                             y: BigInt): BigInt {
  const xlength = ReadBigIntLength(x);
  const ylength = ReadBigIntLength(y);

  // case: 0n | y
  if (xlength == 0) {
    return y;
  }

  // case: x | 0n
  if (ylength == 0) {
    return x;
  }

  const xsign = ReadBigIntSign(x);
  const ysign = ReadBigIntSign(y);
  const resultLength = (xlength > ylength) ? xlength : ylength;

  if (xsign == kPositiveSign && ysign == kPositiveSign) {
    const result = AllocateEmptyBigIntNoThrow(kPositiveSign, resultLength)
        otherwise unreachable;
    CppBitwiseOrPosPosAndCanonicalize(result, x, y);
    return Convert<BigInt>(result);
  } else if (xsign == kNegativeSign && ysign == kNegativeSign) {
    const result = AllocateEmptyBigIntNoThrow(kNegativeSign, resultLength)
        otherwise unreachable;
    CppBitwiseOrNegNegAndCanonicalize(result, x, y);
    return Convert<BigInt>(result);
  } else if (xsign == kPositiveSign && ysign == kNegativeSign) {
    const result = AllocateEmptyBigIntNoThrow(kNegativeSign, resultLength)
        otherwise unreachable;
    CppBitwiseOrPosNegAndCanonicalize(result, x, y);
    return Convert<BigInt>(result);
  } else {
    const result = AllocateEmptyBigIntNoThrow(kNegativeSign, resultLength)
        otherwise unreachable;
    CppBitwiseOrPosNegAndCanonicalize(result, y, x);
    return Convert<BigInt>(result);
  }
}

builtin BigIntBitwiseOrNoThrow(
    implicit context: Context)(x: BigInt, y: BigInt): Numeric {
  return BigIntBitwiseOrImpl(x, y);
}

builtin BigIntBitwiseOr(
    implicit context: Context)(xNum: Numeric, yNum: Numeric): BigInt {
  try {
    const x = Cast<BigInt>(xNum) otherwise MixedTypes;
    const y = Cast<BigInt>(yNum) otherwise MixedTypes;

    return BigIntBitwiseOrImpl(x, y);
  } label MixedTypes {
    ThrowTypeError(MessageTemplate::kBigIntMixedTypes);
  }
}

macro BigIntBitwiseXorImpl(implicit context: Context)(x: BigInt,
                              y: BigInt): BigInt labels BigIntTooBig {
  const xlength = ReadBigIntLength(x);
  const ylength = ReadBigIntLength(y);

  // case: 0n ^ y
  if (xlength == 0) {
    return y;
  }

  // case: x ^ 0n
  if (ylength == 0) {
    return x;
  }

  const xsign = ReadBigIntSign(x);
  const ysign = ReadBigIntSign(y);

  if (xsign == kPositiveSign && ysign == kPositiveSign) {
    const resultLength = (xlength > ylength) ? xlength : ylength;
    const result = AllocateEmptyBigIntNoThrow(kPositiveSign, resultLength)
        otherwise unreachable;
    CppBitwiseXorPosPosAndCanonicalize(result, x, y);
    return Convert<BigInt>(result);
  } else if (xsign == kNegativeSign && ysign == kNegativeSign) {
    const resultLength = (xlength > ylength) ? xlength : ylength;
    const result = AllocateEmptyBigIntNoThrow(kPositiveSign, resultLength)
        otherwise unreachable;
    CppBitwiseXorNegNegAndCanonicalize(result, x, y);
    return Convert<BigInt>(result);
  } else if (xsign == kPositiveSign && ysign == kNegativeSign) {
    const resultLength = ((xlength > ylength) ? xlength : ylength) + 1;
    const result = AllocateEmptyBigIntNoThrow(kNegativeSign, resultLength)
        otherwise BigIntTooBig;
    CppBitwiseXorPosNegAndCanonicalize(result, x, y);
    return Convert<BigInt>(result);
  } else {
    const resultLength = ((xlength > ylength) ? xlength : ylength) + 1;
    const result = AllocateEmptyBigIntNoThrow(kNegativeSign, resultLength)
        otherwise BigIntTooBig;
    CppBitwiseXorPosNegAndCanonicalize(result, y, x);
    return Convert<BigInt>(result);
  }
}

builtin BigIntBitwiseXorNoThrow(
    implicit context: Context)(x: BigInt, y: BigInt): Numeric {
  try {
    return BigIntBitwiseXorImpl(x, y) otherwise BigIntTooBig;
  } label BigIntTooBig {
    // Smi sentinel 0 is used to signal BigIntTooBig exception.
    return Convert<Smi>(0);
  }
}

builtin BigIntBitwiseXor(
    implicit context: Context)(xNum: Numeric, yNum: Numeric): BigInt {
  try {
    const x = Cast<BigInt>(xNum) otherwise MixedTypes;
    const y = Cast<BigInt>(yNum) otherwise MixedTypes;

    return BigIntBitwiseXorImpl(x, y) otherwise BigIntTooBig;
  } label MixedTypes {
    ThrowTypeError(MessageTemplate::kBigIntMixedTypes);
  } label BigIntTooBig {
    ThrowRangeError(MessageTemplate::kBigIntTooBig);
  }
}

macro MutableBigIntLeftShiftByAbsolute(
    implicit context: Context)(x: BigInt,
    y: BigInt): BigInt labels BigIntTooBig {
  const xlength = ReadBigIntLength(x);
  const ylength = ReadBigIntLength(y);

  // case: 0n << y
  if (xlength == 0) {
    return x;
  }

  // case: x << 0n
  if (ylength == 0) {
    return x;
  }

  if (ylength > 1) {
    // Depends on kBigIntMaxLengthBits <= (1 << kBigIntDigitSize).
    goto BigIntTooBig;
  }
  const shiftAbs = LoadBigIntDigit(y, 0);
  if (shiftAbs > kBigIntMaxLengthBits) {
    goto BigIntTooBig;
  }

  // {shift} is positive.
  const shift = Convert<intptr>(shiftAbs);
  let resultLength = xlength + shift / kBigIntDigitBits;
  const bitsShift = shift % kBigIntDigitBits;
  const xmsd = LoadBigIntDigit(x, xlength - 1);
  if (bitsShift != 0 &&
      xmsd >>> Convert<uintptr>(kBigIntDigitBits - bitsShift) != 0) {
    resultLength++;
  }
  const result = AllocateEmptyBigIntNoThrow(ReadBigIntSign(x), resultLength)
      otherwise BigIntTooBig;
  CppLeftShiftAndCanonicalize(result, x, shift);
  return Convert<BigInt>(result);
}

macro RightShiftByMaximum(implicit context: Context)(sign: uint32): BigInt {
  if (sign == kNegativeSign) {
    const minusOne = AllocateEmptyBigInt(kNegativeSign, 1);
    StoreBigIntDigit(minusOne, 0, 1);
    return Convert<BigInt>(minusOne);
  } else {
    return Convert<BigInt>(AllocateEmptyBigInt(kPositiveSign, 0));
  }
}

macro MutableBigIntRightShiftByAbsolute(
    implicit context: Context)(x: BigInt, y: BigInt): BigInt {
  const xlength = ReadBigIntLength(x);
  const ylength = ReadBigIntLength(y);

  // case: 0n >> y
  if (xlength == 0) {
    return x;
  }

  // case: x >> 0n
  if (ylength == 0) {
    return x;
  }

  const sign = ReadBigIntSign(x);
  if (ylength > 1) {
    // Depends on kBigIntMaxLengthBits <= (1 << kBigIntDigitSize).
    return RightShiftByMaximum(sign);
  }
  const shiftAbs = LoadBigIntDigit(y, 0);
  if (shiftAbs > kBigIntMaxLengthBits) {
    return RightShiftByMaximum(sign);
  }

  // {shift} is positive.
  const shift = Convert<intptr>(shiftAbs);
  const returnVal = CppRightShiftResultLength(x, sign, shift);
  const mustRoundDown = returnVal >>> kMustRoundDownBitShift;
  const lengthMask = (1 << kMustRoundDownBitShift) - 1;
  const resultLength = Convert<intptr>(returnVal & lengthMask);
  if (resultLength == 0) {
    return RightShiftByMaximum(sign);
  }

  const result = AllocateEmptyBigIntNoThrow(sign, resultLength)
      otherwise unreachable;
  CppRightShiftAndCanonicalize(result, x, shift, mustRoundDown);
  return Convert<BigInt>(result);
}

macro BigIntShiftLeftImpl(implicit context: Context)(x: BigInt,
                             y: BigInt): BigInt labels BigIntTooBig {
  if (ReadBigIntSign(y) == kNegativeSign) {
    return MutableBigIntRightShiftByAbsolute(x, y);
  } else {
    return MutableBigIntLeftShiftByAbsolute(x, y) otherwise BigIntTooBig;
  }
}

macro BigIntShiftRightImpl(implicit context: Context)(x: BigInt,
                              y: BigInt): BigInt labels BigIntTooBig {
  if (ReadBigIntSign(y) == kNegativeSign) {
    return MutableBigIntLeftShiftByAbsolute(x, y) otherwise BigIntTooBig;
  } else {
    return MutableBigIntRightShiftByAbsolute(x, y);
  }
}

builtin BigIntShiftLeftNoThrow(
    implicit context: Context)(x: BigInt, y: BigInt): Numeric {
  try {
    return BigIntShiftLeftImpl(x, y) otherwise BigIntTooBig;
  } label BigIntTooBig {
    // Smi sentinel 0 is used to signal BigIntTooBig exception.
    return Convert<Smi>(0);
  }
}

builtin BigIntShiftLeft(
    implicit context: Context)(xNum: Numeric, yNum: Numeric): BigInt {
  try {
    const x = Cast<BigInt>(xNum) otherwise MixedTypes;
    const y = Cast<BigInt>(yNum) otherwise MixedTypes;

    return BigIntShiftLeftImpl(x, y) otherwise BigIntTooBig;
  } label MixedTypes {
    ThrowTypeError(MessageTemplate::kBigIntMixedTypes);
  } label BigIntTooBig {
    ThrowRangeError(MessageTemplate::kBigIntTooBig);
  }
}

builtin BigIntShiftRightNoThrow(
    implicit context: Context)(x: BigInt, y: BigInt): Numeric {
  try {
    return BigIntShiftRightImpl(x, y) otherwise BigIntTooBig;
  } label BigIntTooBig {
    // Smi sentinel 0 is used to signal BigIntTooBig exception.
    return Convert<Smi>(0);
  }
}

builtin BigIntShiftRight(
    implicit context: Context)(xNum: Numeric, yNum: Numeric): BigInt {
  try {
    const x = Cast<BigInt>(xNum) otherwise MixedTypes;
    const y = Cast<BigInt>(yNum) otherwise MixedTypes;

    return BigIntShiftRightImpl(x, y) otherwise BigIntTooBig;
  } label MixedTypes {
    ThrowTypeError(MessageTemplate::kBigIntMixedTypes);
  } label BigIntTooBig {
    ThrowRangeError(MessageTemplate::kBigIntTooBig);
  }
}

builtin BigIntEqual(implicit context: Context)(x: BigInt,
                     y: BigInt): Boolean {
  if (ReadBigIntSign(x) != ReadBigIntSign(y)) {
    return False;
  }

  const xlength = ReadBigIntLength(x);
  const ylength = ReadBigIntLength(y);
  if (xlength != ylength) {
    return False;
  }

  for (let i: intptr = 0; i < xlength; ++i) {
    if (LoadBigIntDigit(x, i) != LoadBigIntDigit(y, i)) {
      return False;
    }
  }

  return True;
}

// Returns r such that r < 0 if |x| < |y|; r > 0 if |x| > |y|;
// r == 0 if |x| == |y|.
macro BigIntCompareAbsolute(
    implicit context: Context)(x: BigInt, y: BigInt): intptr {
  const xlength = ReadBigIntLength(x);
  const ylength = ReadBigIntLength(y);
  const diff = xlength - ylength;
  if (diff != 0) {
    return diff;
  }

  // case: {xlength} == {ylength}
  for (let i: intptr = xlength - 1; i >= 0; --i) {
    const xdigit = LoadBigIntDigit(x, i);
    const ydigit = LoadBigIntDigit(y, i);
    if (xdigit != ydigit) {
      return (xdigit > ydigit) ? kGreaterThan : kLessThan;
    }
  }
  return 0;
}

// Returns r such that r < 0 if x < y; r > 0 if x > y; r == 0 if x == y.
macro BigIntCompare(implicit context: Context)(x: BigInt,
                       y: BigInt): intptr {
  const xsign = ReadBigIntSign(x);
  const ysign = ReadBigIntSign(y);
  if (xsign != ysign) {
    return xsign == kPositiveSign ? kGreaterThan : kLessThan;
  }

  // case: {xsign} == {ysign}
  const diff = BigIntCompareAbsolute(x, y);
  return xsign == kPositiveSign ? diff : 0 - diff;
}

builtin BigIntLessThan(implicit context: Context)(x: BigInt,
                        y: BigInt): Boolean {
  return BigIntCompare(x, y) < 0 ? True : False;
}

builtin BigIntGreaterThan(implicit context: Context)(x: BigInt,
                           y: BigInt): Boolean {
  return BigIntCompare(x, y) > 0 ? True : False;
}

builtin BigIntLessThanOrEqual(
    implicit context: Context)(x: BigInt, y: BigInt): Boolean {
  return BigIntCompare(x, y) <= 0 ? True : False;
}

builtin BigIntGreaterThanOrEqual(
    implicit context: Context)(x: BigInt, y: BigInt): Boolean {
  return BigIntCompare(x, y) >= 0 ? True : False;
}

builtin BigIntUnaryMinus(implicit context: Context)(bigint: BigInt): BigInt {
  const length = ReadBigIntLength(bigint);

  // There is no -0n.
  if (length == 0) {
    return bigint;
  }

  const result =
      AllocateEmptyBigInt(InvertSign(ReadBigIntSign(bigint)), length);
  for (let i: intptr = 0; i < length; ++i) {
    StoreBigIntDigit(result, i, LoadBigIntDigit(bigint, i));
  }
  return Convert<BigInt>(result);
}

}  // namespace bigint