v8::internal::Bignum Class Reference

#include <bignum.h>

Collaboration diagram for v8::internal::Bignum:

Public Member Functions
	Bignum ()
void	AssignUInt16 (uint16_t value)
void	AssignUInt64 (uint64_t value)
void	AssignBignum (const Bignum &other)
void	AssignDecimalString (Vector< const char > value)
void	AssignHexString (Vector< const char > value)
void	AssignPowerUInt16 (uint16_t base, int exponent)
void	AddUInt16 (uint16_t operand)
void	AddUInt64 (uint64_t operand)
void	AddBignum (const Bignum &other)
void	SubtractBignum (const Bignum &other)
void	Square ()
void	ShiftLeft (int shift_amount)
void	MultiplyByUInt32 (uint32_t factor)
void	MultiplyByUInt64 (uint64_t factor)
void	MultiplyByPowerOfTen (int exponent)
void	Times10 ()
uint16_t	DivideModuloIntBignum (const Bignum &other)
bool	ToHexString (char *buffer, int buffer_size) const

Static Public Member Functions
static int	Compare (const Bignum &a, const Bignum &b)
static bool	Equal (const Bignum &a, const Bignum &b)
static bool	LessEqual (const Bignum &a, const Bignum &b)
static bool	Less (const Bignum &a, const Bignum &b)
static int	PlusCompare (const Bignum &a, const Bignum &b, const Bignum &c)
static bool	PlusEqual (const Bignum &a, const Bignum &b, const Bignum &c)
static bool	PlusLessEqual (const Bignum &a, const Bignum &b, const Bignum &c)
static bool	PlusLess (const Bignum &a, const Bignum &b, const Bignum &c)

Static Public Attributes
static const int	kMaxSignificantBits = 3584

Private Types
typedef uint32_t	Chunk
typedef uint64_t	DoubleChunk

Private Member Functions
void	EnsureCapacity (int size)
void	Align (const Bignum &other)
void	Clamp ()
bool	IsClamped () const
void	Zero ()
void	BigitsShiftLeft (int shift_amount)
int	BigitLength () const
Chunk	BigitAt (int index) const
void	SubtractTimes (const Bignum &other, int factor)
	DISALLOW_COPY_AND_ASSIGN (Bignum)

Private Attributes
Chunk	bigits_buffer_ [kBigitCapacity]
Vector< Chunk >	bigits_
int	used_digits_
int	exponent_

Static Private Attributes
static const int	kChunkSize = sizeof(Chunk) * 8
static const int	kDoubleChunkSize = sizeof(DoubleChunk) * 8
static const int	kBigitSize = 28
static const Chunk	kBigitMask = (1 << kBigitSize) - 1
static const int	kBigitCapacity = kMaxSignificantBits / kBigitSize

Detailed Description

Definition at line 11 of file bignum.h.

Member Typedef Documentation

Chunk

typedef uint32_t v8::internal::Bignum::Chunk

private

Definition at line 74 of file bignum.h.

DoubleChunk

typedef uint64_t v8::internal::Bignum::DoubleChunk

private

Definition at line 75 of file bignum.h.

Constructor & Destructor Documentation

Bignum()

v8::internal::Bignum::Bignum

(

)

Definition at line 13 of file bignum.cc.

    : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) {
  for (int i = 0; i < kBigitCapacity; ++i) {
    bigits_[i] = 0;
  }
}

References bigits_, and kBigitCapacity.

Member Function Documentation

AddBignum()

void v8::internal::Bignum::AddBignum

(

const Bignum &

other

)

Definition at line 150 of file bignum.cc.

                                          {
  DCHECK(IsClamped());
  DCHECK(other.IsClamped());
 
  // If this has a greater exponent than other append zero-bigits to this.
  // After this call exponent_ <= other.exponent_.
  Align(other);
 
  // There are two possibilities:
  //   aaaaaaaaaaa 0000  (where the 0s represent a's exponent)
  //     bbbbb 00000000
  //   ----------------
  //   ccccccccccc 0000
  // or
  //    aaaaaaaaaa 0000
  //  bbbbbbbbb 0000000
  //  -----------------
  //  cccccccccccc 0000
  // In both cases we might need a carry bigit.
 
  EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_);
  Chunk carry = 0;
  int bigit_pos = other.exponent_ - exponent_;
  DCHECK(bigit_pos >= 0);
  for (int i = 0; i < other.used_digits_; ++i) {
    Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;
    bigits_[bigit_pos] = sum & kBigitMask;
    carry = sum >> kBigitSize;
    bigit_pos++;
  }
 
  while (carry != 0) {
    Chunk sum = bigits_[bigit_pos] + carry;
    bigits_[bigit_pos] = sum & kBigitMask;
    carry = sum >> kBigitSize;
    bigit_pos++;
  }
  used_digits_ = Max(bigit_pos, used_digits_);
  DCHECK(IsClamped());
}

References Align(), BigitLength(), bigits_, v8::internal::carry, DCHECK, EnsureCapacity(), exponent_, IsClamped(), kBigitMask, kBigitSize, v8::internal::Max(), and used_digits_.

Referenced by AddUInt64().

Here is the call graph for this function:

Here is the caller graph for this function:

AddUInt16()

void v8::internal::Bignum::AddUInt16

(

uint16_t

operand

)

AddUInt64()

void v8::internal::Bignum::AddUInt64

(

uint64_t

operand

)

Definition at line 142 of file bignum.cc.

                                       {
  if (operand == 0) return;
  Bignum other;
  other.AssignUInt64(operand);
  AddBignum(other);
}

References AddBignum(), and AssignUInt64().

Referenced by AssignDecimalString().

Here is the call graph for this function:

Here is the caller graph for this function:

Align()

void v8::internal::Bignum::Align ( const Bignum &  other )

private

Definition at line 676 of file bignum.cc.

                                      {
  if (exponent_ > other.exponent_) {
    // If "X" represents a "hidden" digit (by the exponent) then we are in the
    // following case (a == this, b == other):
    // a:  aaaaaaXXXX   or a:   aaaaaXXX
    // b:     bbbbbbX      b: bbbbbbbbXX
    // We replace some of the hidden digits (X) of a with 0 digits.
    // a:  aaaaaa000X   or a:   aaaaa0XX
    int zero_digits = exponent_ - other.exponent_;
    EnsureCapacity(used_digits_ + zero_digits);
    for (int i = used_digits_ - 1; i >= 0; --i) {
      bigits_[i + zero_digits] = bigits_[i];
    }
    for (int i = 0; i < zero_digits; ++i) {
      bigits_[i] = 0;
    }
    used_digits_ += zero_digits;
    exponent_ -= zero_digits;
    DCHECK(used_digits_ >= 0);
    DCHECK(exponent_ >= 0);
  }
}

References bigits_, DCHECK, EnsureCapacity(), exponent_, and used_digits_.

Referenced by AddBignum(), DivideModuloIntBignum(), and SubtractBignum().

Here is the call graph for this function:

Here is the caller graph for this function:

AssignBignum()

void v8::internal::Bignum::AssignBignum

(

const Bignum &

other

)

Definition at line 56 of file bignum.cc.

                                             {
  exponent_ = other.exponent_;
  for (int i = 0; i < other.used_digits_; ++i) {
    bigits_[i] = other.bigits_[i];
  }
  // Clear the excess digits (if there were any).
  for (int i = other.used_digits_; i < used_digits_; ++i) {
    bigits_[i] = 0;
  }
  used_digits_ = other.used_digits_;
}

References bigits_, exponent_, and used_digits_.

Referenced by v8::internal::FixupMultiply10(), v8::internal::InitialScaledStartValuesNegativeExponentNegativePower(), and SubtractTimes().

Here is the caller graph for this function:

AssignDecimalString()

void v8::internal::Bignum::AssignDecimalString

(

Vector< const char >

value

)

Definition at line 82 of file bignum.cc.

                                                         {
  // 2^64 = 18446744073709551616 > 10^19
  const int kMaxUint64DecimalDigits = 19;
  Zero();
  int length = value.length();
  int pos = 0;
  // Let's just say that each digit needs 4 bits.
  while (length >= kMaxUint64DecimalDigits) {
    uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits);
    pos += kMaxUint64DecimalDigits;
    length -= kMaxUint64DecimalDigits;
    MultiplyByPowerOfTen(kMaxUint64DecimalDigits);
    AddUInt64(digits);
  }
  uint64_t digits = ReadUInt64(value, pos, length);
  MultiplyByPowerOfTen(length);
  AddUInt64(digits);
  Clamp();
}

References AddUInt64(), Clamp(), v8::internal::kMaxUint64DecimalDigits, v8::internal::Vector< T >::length(), MultiplyByPowerOfTen(), v8::internal::ReadUInt64(), and Zero().

Referenced by v8::internal::BignumStrtod().

Here is the call graph for this function:

Here is the caller graph for this function:

AssignHexString()

void v8::internal::Bignum::AssignHexString

(

Vector< const char >

value

)

Definition at line 112 of file bignum.cc.

                                                     {
  Zero();
  int length = value.length();
 
  int needed_bigits = length * 4 / kBigitSize + 1;
  EnsureCapacity(needed_bigits);
  int string_index = length - 1;
  for (int i = 0; i < needed_bigits - 1; ++i) {
    // These bigits are guaranteed to be "full".
    Chunk current_bigit = 0;
    for (int j = 0; j < kBigitSize / 4; j++) {
      current_bigit += HexCharValue(value[string_index--]) << (j * 4);
    }
    bigits_[i] = current_bigit;
  }
  used_digits_ = needed_bigits - 1;
 
  Chunk most_significant_bigit = 0;  // Could be = 0;
  for (int j = 0; j <= string_index; ++j) {
    most_significant_bigit <<= 4;
    most_significant_bigit += HexCharValue(value[j]);
  }
  if (most_significant_bigit != 0) {
    bigits_[used_digits_] = most_significant_bigit;
    used_digits_++;
  }
  Clamp();
}

References bigits_, Clamp(), EnsureCapacity(), v8::internal::HexCharValue(), kBigitSize, v8::internal::Vector< T >::length(), used_digits_, and Zero().

Here is the call graph for this function:

AssignPowerUInt16()

void v8::internal::Bignum::AssignPowerUInt16	(	uint16_t	base,
		int	exponent
	)

Definition at line 393 of file bignum.cc.

                                                                {
  DCHECK(base != 0);
  DCHECK(power_exponent >= 0);
  if (power_exponent == 0) {
    AssignUInt16(1);
    return;
  }
  Zero();
  int shifts = 0;
  // We expect base to be in range 2-32, and most often to be 10.
  // It does not make much sense to implement different algorithms for counting
  // the bits.
  while ((base & 1) == 0) {
    base >>= 1;
    shifts++;
  }
  int bit_size = 0;
  int tmp_base = base;
  while (tmp_base != 0) {
    tmp_base >>= 1;
    bit_size++;
  }
  int final_size = bit_size * power_exponent;
  // 1 extra bigit for the shifting, and one for rounded final_size.
  EnsureCapacity(final_size / kBigitSize + 2);
 
  // Left to Right exponentiation.
  int mask = 1;
  while (power_exponent >= mask) mask <<= 1;
 
  // The mask is now pointing to the bit above the most significant 1-bit of
  // power_exponent.
  // Get rid of first 1-bit;
  mask >>= 2;
  uint64_t this_value = base;
 
  bool delayed_multipliciation = false;
  const uint64_t max_32bits = 0xFFFFFFFF;
  while (mask != 0 && this_value <= max_32bits) {
    this_value = this_value * this_value;
    // Verify that there is enough space in this_value to perform the
    // multiplication.  The first bit_size bits must be 0.
    if ((power_exponent & mask) != 0) {
      uint64_t base_bits_mask =
          ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1);
      bool high_bits_zero = (this_value & base_bits_mask) == 0;
      if (high_bits_zero) {
        this_value *= base;
      } else {
        delayed_multipliciation = true;
      }
    }
    mask >>= 1;
  }
  AssignUInt64(this_value);
  if (delayed_multipliciation) {
    MultiplyByUInt32(base);
  }
 
  // Now do the same thing as a bignum.
  while (mask != 0) {
    Square();
    if ((power_exponent & mask) != 0) {
      MultiplyByUInt32(base);
    }
    mask >>= 1;
  }
 
  // And finally add the saved shifts.
  ShiftLeft(shifts * power_exponent);
}

References AssignUInt16(), AssignUInt64(), DCHECK, EnsureCapacity(), kBigitSize, MultiplyByUInt32(), ShiftLeft(), Square(), and Zero().

Referenced by v8::internal::InitialScaledStartValuesNegativeExponentNegativePower(), v8::internal::InitialScaledStartValuesNegativeExponentPositivePower(), and v8::internal::InitialScaledStartValuesPositiveExponent().

Here is the call graph for this function:

Here is the caller graph for this function:

AssignUInt16()

void v8::internal::Bignum::AssignUInt16

(

uint16_t

value

)

Definition at line 28 of file bignum.cc.

                                        {
  DCHECK(kBigitSize >= BitSize(value));
  Zero();
  if (value == 0) return;
 
  EnsureCapacity(1);
  bigits_[0] = value;
  used_digits_ = 1;
}

References bigits_, v8::internal::BitSize(), DCHECK, EnsureCapacity(), kBigitSize, used_digits_, and Zero().

Referenced by AssignPowerUInt16(), v8::internal::InitialScaledStartValuesNegativeExponentNegativePower(), v8::internal::InitialScaledStartValuesNegativeExponentPositivePower(), and v8::internal::InitialScaledStartValuesPositiveExponent().

Here is the call graph for this function:

Here is the caller graph for this function:

AssignUInt64()

void v8::internal::Bignum::AssignUInt64

(

uint64_t

value

)

Definition at line 39 of file bignum.cc.

                                        {
  const int kUInt64Size = 64;
 
  Zero();
  if (value == 0) return;
 
  int needed_bigits = kUInt64Size / kBigitSize + 1;
  EnsureCapacity(needed_bigits);
  for (int i = 0; i < needed_bigits; ++i) {
    bigits_[i] = static_cast<Chunk>(value & kBigitMask);
    value = value >> kBigitSize;
  }
  used_digits_ = needed_bigits;
  Clamp();
}

References bigits_, Clamp(), EnsureCapacity(), kBigitMask, kBigitSize, used_digits_, and Zero().

Referenced by AddUInt64(), AssignPowerUInt16(), v8::internal::BignumStrtod(), v8::internal::InitialScaledStartValuesNegativeExponentPositivePower(), and v8::internal::InitialScaledStartValuesPositiveExponent().

Here is the call graph for this function:

Here is the caller graph for this function:

BigitAt()

Bignum::Chunk v8::internal::Bignum::BigitAt ( int  index ) const

private

Definition at line 589 of file bignum.cc.

                                           {
  if (index >= BigitLength()) return 0;
  if (index < exponent_) return 0;
  return bigits_[index - exponent_];
}

References BigitLength(), bigits_, and exponent_.

Referenced by Compare(), and PlusCompare().

Here is the call graph for this function:

Here is the caller graph for this function:

BigitLength()

int v8::internal::Bignum::BigitLength ( ) const

inlineprivate

Definition at line 101 of file bignum.h.

{ return used_digits_ + exponent_; }

References exponent_, and used_digits_.

Referenced by AddBignum(), BigitAt(), Compare(), DivideModuloIntBignum(), PlusCompare(), and ToHexString().

Here is the caller graph for this function:

BigitsShiftLeft()

void v8::internal::Bignum::BigitsShiftLeft ( int  shift_amount )

private

Definition at line 700 of file bignum.cc.

                                             {
  DCHECK(shift_amount < kBigitSize);
  DCHECK(shift_amount >= 0);
  Chunk carry = 0;
  for (int i = 0; i < used_digits_; ++i) {
    Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);
    bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;
    carry = new_carry;
  }
  if (carry != 0) {
    bigits_[used_digits_] = carry;
    used_digits_++;
  }
}

References bigits_, v8::internal::carry, DCHECK, kBigitMask, kBigitSize, and used_digits_.

Referenced by ShiftLeft().

Here is the caller graph for this function:

Clamp()

void v8::internal::Bignum::Clamp ( )

private

Definition at line 651 of file bignum.cc.

                   {
  while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {
    used_digits_--;
  }
  if (used_digits_ == 0) {
    // Zero.
    exponent_ = 0;
  }
}

References bigits_, exponent_, and used_digits_.

Referenced by AssignDecimalString(), AssignHexString(), AssignUInt64(), DivideModuloIntBignum(), Square(), SubtractBignum(), and SubtractTimes().

Here is the caller graph for this function:

Compare()

int v8::internal::Bignum::Compare ( const Bignum &  a, const Bignum &  b  )

static

Definition at line 596 of file bignum.cc.

                                                    {
  DCHECK(a.IsClamped());
  DCHECK(b.IsClamped());
  int bigit_length_a = a.BigitLength();
  int bigit_length_b = b.BigitLength();
  if (bigit_length_a < bigit_length_b) return -1;
  if (bigit_length_a > bigit_length_b) return +1;
  for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) {
    Chunk bigit_a = a.BigitAt(i);
    Chunk bigit_b = b.BigitAt(i);
    if (bigit_a < bigit_b) return -1;
    if (bigit_a > bigit_b) return +1;
    // Otherwise they are equal up to this digit. Try the next digit.
  }
  return 0;
}

References BigitAt(), BigitLength(), DCHECK, exponent_, IsClamped(), and v8::internal::Min().

Referenced by v8::internal::BignumStrtod(), Equal(), Less(), and LessEqual().

Here is the call graph for this function:

Here is the caller graph for this function:

DISALLOW_COPY_AND_ASSIGN()

v8::internal::Bignum::DISALLOW_COPY_AND_ASSIGN ( Bignum  )

private

DivideModuloIntBignum()

uint16_t v8::internal::Bignum::DivideModuloIntBignum

(

const Bignum &

other

)

Definition at line 467 of file bignum.cc.

                                                          {
  DCHECK(IsClamped());
  DCHECK(other.IsClamped());
  DCHECK(other.used_digits_ > 0);
 
  // Easy case: if we have less digits than the divisor than the result is 0.
  // Note: this handles the case where this == 0, too.
  if (BigitLength() < other.BigitLength()) {
    return 0;
  }
 
  Align(other);
 
  uint16_t result = 0;
 
  // Start by removing multiples of 'other' until both numbers have the same
  // number of digits.
  while (BigitLength() > other.BigitLength()) {
    // This naive approach is extremely inefficient if the this divided other
    // might be big. This function is implemented for doubleToString where
    // the result should be small (less than 10).
    DCHECK(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));
    // Remove the multiples of the first digit.
    // Example this = 23 and other equals 9. -> Remove 2 multiples.
    result += bigits_[used_digits_ - 1];
    SubtractTimes(other, bigits_[used_digits_ - 1]);
  }
 
  DCHECK(BigitLength() == other.BigitLength());
 
  // Both bignums are at the same length now.
  // Since other has more than 0 digits we know that the access to
  // bigits_[used_digits_ - 1] is safe.
  Chunk this_bigit = bigits_[used_digits_ - 1];
  Chunk other_bigit = other.bigits_[other.used_digits_ - 1];
 
  if (other.used_digits_ == 1) {
    // Shortcut for easy (and common) case.
    int quotient = this_bigit / other_bigit;
    bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;
    result += quotient;
    Clamp();
    return result;
  }
 
  int division_estimate = this_bigit / (other_bigit + 1);
  result += division_estimate;
  SubtractTimes(other, division_estimate);
 
  if (other_bigit * (division_estimate + 1) > this_bigit) {
    // No need to even try to subtract. Even if other's remaining digits were 0
    // another subtraction would be too much.
    return result;
  }
 
  while (LessEqual(other, *this)) {
    SubtractBignum(other);
    result++;
  }
  return result;
}

References Align(), BigitLength(), bigits_, Clamp(), DCHECK, IsClamped(), kBigitSize, LessEqual(), SubtractBignum(), SubtractTimes(), and used_digits_.

Referenced by v8::internal::GenerateCountedDigits(), and v8::internal::GenerateShortestDigits().

Here is the call graph for this function:

Here is the caller graph for this function:

EnsureCapacity()

void v8::internal::Bignum::EnsureCapacity ( int  size )

inlineprivate

Definition at line 87 of file bignum.h.

                                {
    if (size > kBigitCapacity) {
      UNREACHABLE();
    }
  }

References kBigitCapacity, size, and UNREACHABLE.

Referenced by AddBignum(), Align(), AssignHexString(), AssignPowerUInt16(), AssignUInt16(), AssignUInt64(), MultiplyByUInt32(), MultiplyByUInt64(), ShiftLeft(), and Square().

Here is the caller graph for this function:

Equal()

static bool v8::internal::Bignum::Equal ( const Bignum &  a, const Bignum &  b  )

inlinestatic

Definition at line 49 of file bignum.h.

                                                      {
    return Compare(a, b) == 0;
  }

References Compare().

Referenced by v8::internal::FixupMultiply10(), v8::internal::GenerateShortestDigits(), and SubtractTimes().

Here is the call graph for this function:

Here is the caller graph for this function:

IsClamped()

bool v8::internal::Bignum::IsClamped ( ) const

private

Definition at line 662 of file bignum.cc.

                             {
  return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;
}

References bigits_, and used_digits_.

Referenced by AddBignum(), Compare(), DivideModuloIntBignum(), PlusCompare(), Square(), SubtractBignum(), and ToHexString().

Here is the caller graph for this function:

Less()

static bool v8::internal::Bignum::Less ( const Bignum &  a, const Bignum &  b  )

inlinestatic

Definition at line 55 of file bignum.h.

                                                     {
    return Compare(a, b) < 0;
  }

References Compare().

Referenced by v8::internal::GenerateShortestDigits().

Here is the call graph for this function:

Here is the caller graph for this function:

LessEqual()

static bool v8::internal::Bignum::LessEqual ( const Bignum &  a, const Bignum &  b  )

inlinestatic

Definition at line 52 of file bignum.h.

                                                          {
    return Compare(a, b) <= 0;
  }

References Compare().

Referenced by DivideModuloIntBignum(), v8::internal::GenerateShortestDigits(), and SubtractBignum().

Here is the call graph for this function:

Here is the caller graph for this function:

MultiplyByPowerOfTen()

void v8::internal::Bignum::MultiplyByPowerOfTen

(

int

exponent

)

Definition at line 281 of file bignum.cc.

                                              {
  const uint64_t kFive27 = V8_2PART_UINT64_C(0x6765c793, fa10079d);
  const uint16_t kFive1 = 5;
  const uint16_t kFive2 = kFive1 * 5;
  const uint16_t kFive3 = kFive2 * 5;
  const uint16_t kFive4 = kFive3 * 5;
  const uint16_t kFive5 = kFive4 * 5;
  const uint16_t kFive6 = kFive5 * 5;
  const uint32_t kFive7 = kFive6 * 5;
  const uint32_t kFive8 = kFive7 * 5;
  const uint32_t kFive9 = kFive8 * 5;
  const uint32_t kFive10 = kFive9 * 5;
  const uint32_t kFive11 = kFive10 * 5;
  const uint32_t kFive12 = kFive11 * 5;
  const uint32_t kFive13 = kFive12 * 5;
  const uint32_t kFive1_to_12[] =
      { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6,
        kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 };
 
  DCHECK(exponent >= 0);
  if (exponent == 0) return;
  if (used_digits_ == 0) return;
 
  // We shift by exponent at the end just before returning.
  int remaining_exponent = exponent;
  while (remaining_exponent >= 27) {
    MultiplyByUInt64(kFive27);
    remaining_exponent -= 27;
  }
  while (remaining_exponent >= 13) {
    MultiplyByUInt32(kFive13);
    remaining_exponent -= 13;
  }
  if (remaining_exponent > 0) {
    MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]);
  }
  ShiftLeft(exponent);
}

References DCHECK, MultiplyByUInt32(), MultiplyByUInt64(), ShiftLeft(), used_digits_, and V8_2PART_UINT64_C.

Referenced by AssignDecimalString(), and v8::internal::BignumStrtod().

Here is the call graph for this function:

Here is the caller graph for this function:

MultiplyByUInt32()

void v8::internal::Bignum::MultiplyByUInt32

(

uint32_t

factor

)

Definition at line 228 of file bignum.cc.

                                             {
  if (factor == 1) return;
  if (factor == 0) {
    Zero();
    return;
  }
  if (used_digits_ == 0) return;
 
  // The product of a bigit with the factor is of size kBigitSize + 32.
  // Assert that this number + 1 (for the carry) fits into double chunk.
  DCHECK(kDoubleChunkSize >= kBigitSize + 32 + 1);
  DoubleChunk carry = 0;
  for (int i = 0; i < used_digits_; ++i) {
    DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;
    bigits_[i] = static_cast<Chunk>(product & kBigitMask);
    carry = (product >> kBigitSize);
  }
  while (carry != 0) {
    EnsureCapacity(used_digits_ + 1);
    bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask);
    used_digits_++;
    carry >>= kBigitSize;
  }
}

References bigits_, v8::internal::carry, DCHECK, EnsureCapacity(), kBigitMask, kBigitSize, kDoubleChunkSize, used_digits_, and Zero().

Referenced by AssignPowerUInt16(), MultiplyByPowerOfTen(), SubtractTimes(), and Times10().

Here is the call graph for this function:

Here is the caller graph for this function:

MultiplyByUInt64()

void v8::internal::Bignum::MultiplyByUInt64

(

uint64_t

factor

)

Definition at line 254 of file bignum.cc.

                                             {
  if (factor == 1) return;
  if (factor == 0) {
    Zero();
    return;
  }
  DCHECK(kBigitSize < 32);
  uint64_t carry = 0;
  uint64_t low = factor & 0xFFFFFFFF;
  uint64_t high = factor >> 32;
  for (int i = 0; i < used_digits_; ++i) {
    uint64_t product_low = low * bigits_[i];
    uint64_t product_high = high * bigits_[i];
    uint64_t tmp = (carry & kBigitMask) + product_low;
    bigits_[i] = static_cast<Chunk>(tmp & kBigitMask);
    carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
        (product_high << (32 - kBigitSize));
  }
  while (carry != 0) {
    EnsureCapacity(used_digits_ + 1);
    bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask);
    used_digits_++;
    carry >>= kBigitSize;
  }
}

References bigits_, v8::internal::carry, DCHECK, EnsureCapacity(), kBigitMask, kBigitSize, used_digits_, and Zero().

Referenced by v8::internal::InitialScaledStartValuesNegativeExponentNegativePower(), and MultiplyByPowerOfTen().

Here is the call graph for this function:

Here is the caller graph for this function:

PlusCompare()

int v8::internal::Bignum::PlusCompare ( const Bignum &  a, const Bignum &  b, const Bignum &  c  )

static

Definition at line 614 of file bignum.cc.

                                                                         {
  DCHECK(a.IsClamped());
  DCHECK(b.IsClamped());
  DCHECK(c.IsClamped());
  if (a.BigitLength() < b.BigitLength()) {
    return PlusCompare(b, a, c);
  }
  if (a.BigitLength() + 1 < c.BigitLength()) return -1;
  if (a.BigitLength() > c.BigitLength()) return +1;
  // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than
  // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one
  // of 'a'.
  if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) {
    return -1;
  }
 
  Chunk borrow = 0;
  // Starting at min_exponent all digits are == 0. So no need to compare them.
  int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_);
  for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {
    Chunk chunk_a = a.BigitAt(i);
    Chunk chunk_b = b.BigitAt(i);
    Chunk chunk_c = c.BigitAt(i);
    Chunk sum = chunk_a + chunk_b;
    if (sum > chunk_c + borrow) {
      return +1;
    } else {
      borrow = chunk_c + borrow - sum;
      if (borrow > 1) return -1;
      borrow <<= kBigitSize;
    }
  }
  if (borrow == 0) return 0;
  return -1;
}

References BigitAt(), BigitLength(), DCHECK, exponent_, IsClamped(), kBigitSize, and v8::internal::Min().

Referenced by v8::internal::BignumToFixed(), v8::internal::FixupMultiply10(), v8::internal::GenerateCountedDigits(), v8::internal::GenerateShortestDigits(), PlusEqual(), PlusLess(), and PlusLessEqual().

Here is the call graph for this function:

Here is the caller graph for this function:

PlusEqual()

static bool v8::internal::Bignum::PlusEqual ( const Bignum &  a, const Bignum &  b, const Bignum &  c  )

inlinestatic

Definition at line 61 of file bignum.h.

                                                                           {
    return PlusCompare(a, b, c) == 0;
  }

References PlusCompare().

Here is the call graph for this function:

PlusLess()

static bool v8::internal::Bignum::PlusLess ( const Bignum &  a, const Bignum &  b, const Bignum &  c  )

inlinestatic

Definition at line 69 of file bignum.h.

                                                                          {
    return PlusCompare(a, b, c) < 0;
  }

References PlusCompare().

Here is the call graph for this function:

PlusLessEqual()

static bool v8::internal::Bignum::PlusLessEqual ( const Bignum &  a, const Bignum &  b, const Bignum &  c  )

inlinestatic

Definition at line 65 of file bignum.h.

                                                                               {
    return PlusCompare(a, b, c) <= 0;
  }

References PlusCompare().

Here is the call graph for this function:

ShiftLeft()

void v8::internal::Bignum::ShiftLeft

(

int

shift_amount

)

Definition at line 219 of file bignum.cc.

                                       {
  if (used_digits_ == 0) return;
  exponent_ += shift_amount / kBigitSize;
  int local_shift = shift_amount % kBigitSize;
  EnsureCapacity(used_digits_ + 1);
  BigitsShiftLeft(local_shift);
}

References BigitsShiftLeft(), EnsureCapacity(), exponent_, kBigitSize, and used_digits_.

Referenced by AssignPowerUInt16(), v8::internal::BignumStrtod(), v8::internal::InitialScaledStartValuesNegativeExponentNegativePower(), v8::internal::InitialScaledStartValuesNegativeExponentPositivePower(), v8::internal::InitialScaledStartValuesPositiveExponent(), and MultiplyByPowerOfTen().

Here is the call graph for this function:

Here is the caller graph for this function:

Square()

void v8::internal::Bignum::Square

(

)

Definition at line 321 of file bignum.cc.

                    {
  DCHECK(IsClamped());
  int product_length = 2 * used_digits_;
  EnsureCapacity(product_length);
 
  // Comba multiplication: compute each column separately.
  // Example: r = a2a1a0 * b2b1b0.
  //    r =  1    * a0b0 +
  //        10    * (a1b0 + a0b1) +
  //        100   * (a2b0 + a1b1 + a0b2) +
  //        1000  * (a2b1 + a1b2) +
  //        10000 * a2b2
  //
  // In the worst case we have to accumulate nb-digits products of digit*digit.
  //
  // Assert that the additional number of bits in a DoubleChunk are enough to
  // sum up used_digits of Bigit*Bigit.
  if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) {
    UNIMPLEMENTED();
  }
  DoubleChunk accumulator = 0;
  // First shift the digits so we don't overwrite them.
  int copy_offset = used_digits_;
  for (int i = 0; i < used_digits_; ++i) {
    bigits_[copy_offset + i] = bigits_[i];
  }
  // We have two loops to avoid some 'if's in the loop.
  for (int i = 0; i < used_digits_; ++i) {
    // Process temporary digit i with power i.
    // The sum of the two indices must be equal to i.
    int bigit_index1 = i;
    int bigit_index2 = 0;
    // Sum all of the sub-products.
    while (bigit_index1 >= 0) {
      Chunk chunk1 = bigits_[copy_offset + bigit_index1];
      Chunk chunk2 = bigits_[copy_offset + bigit_index2];
      accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
      bigit_index1--;
      bigit_index2++;
    }
    bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
    accumulator >>= kBigitSize;
  }
  for (int i = used_digits_; i < product_length; ++i) {
    int bigit_index1 = used_digits_ - 1;
    int bigit_index2 = i - bigit_index1;
    // Invariant: sum of both indices is again equal to i.
    // Inner loop runs 0 times on last iteration, emptying accumulator.
    while (bigit_index2 < used_digits_) {
      Chunk chunk1 = bigits_[copy_offset + bigit_index1];
      Chunk chunk2 = bigits_[copy_offset + bigit_index2];
      accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
      bigit_index1--;
      bigit_index2++;
    }
    // The overwritten bigits_[i] will never be read in further loop iterations,
    // because bigit_index1 and bigit_index2 are always greater
    // than i - used_digits_.
    bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
    accumulator >>= kBigitSize;
  }
  // Since the result was guaranteed to lie inside the number the
  // accumulator must be 0 now.
  DCHECK(accumulator == 0);
 
  // Don't forget to update the used_digits and the exponent.
  used_digits_ = product_length;
  exponent_ *= 2;
  Clamp();
}

References bigits_, Clamp(), DCHECK, EnsureCapacity(), exponent_, IsClamped(), kBigitMask, kBigitSize, kChunkSize, UNIMPLEMENTED, and used_digits_.

Referenced by AssignPowerUInt16().

Here is the call graph for this function:

Here is the caller graph for this function:

SubtractBignum()

void v8::internal::Bignum::SubtractBignum

(

const Bignum &

other

)

Definition at line 192 of file bignum.cc.

                                               {
  DCHECK(IsClamped());
  DCHECK(other.IsClamped());
  // We require this to be bigger than other.
  DCHECK(LessEqual(other, *this));
 
  Align(other);
 
  int offset = other.exponent_ - exponent_;
  Chunk borrow = 0;
  int i;
  for (i = 0; i < other.used_digits_; ++i) {
    DCHECK((borrow == 0) || (borrow == 1));
    Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;
    bigits_[i + offset] = difference & kBigitMask;
    borrow = difference >> (kChunkSize - 1);
  }
  while (borrow != 0) {
    Chunk difference = bigits_[i + offset] - borrow;
    bigits_[i + offset] = difference & kBigitMask;
    borrow = difference >> (kChunkSize - 1);
    ++i;
  }
  Clamp();
}

References Align(), bigits_, Clamp(), DCHECK, exponent_, IsClamped(), kBigitMask, kChunkSize, LessEqual(), and used_digits_.

Referenced by DivideModuloIntBignum(), and SubtractTimes().

Here is the call graph for this function:

Here is the caller graph for this function:

SubtractTimes()

void v8::internal::Bignum::SubtractTimes ( const Bignum &  other, int  factor  )

private

Definition at line 716 of file bignum.cc.

                                                          {
#ifdef DEBUG
  Bignum a, b;
  a.AssignBignum(*this);
  b.AssignBignum(other);
  b.MultiplyByUInt32(factor);
  a.SubtractBignum(b);
#endif
  DCHECK(exponent_ <= other.exponent_);
  if (factor < 3) {
    for (int i = 0; i < factor; ++i) {
      SubtractBignum(other);
    }
    return;
  }
  Chunk borrow = 0;
  int exponent_diff = other.exponent_ - exponent_;
  for (int i = 0; i < other.used_digits_; ++i) {
    DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];
    DoubleChunk remove = borrow + product;
    Chunk difference =
        bigits_[i + exponent_diff] - static_cast<Chunk>(remove & kBigitMask);
    bigits_[i + exponent_diff] = difference & kBigitMask;
    borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +
                                (remove >> kBigitSize));
  }
  for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {
    if (borrow == 0) return;
    Chunk difference = bigits_[i] - borrow;
    bigits_[i] = difference & kBigitMask;
    borrow = difference >> (kChunkSize - 1);
  }
  Clamp();
  DCHECK(Bignum::Equal(a, *this));
}

References AssignBignum(), bigits_, Clamp(), DCHECK, Equal(), exponent_, kBigitMask, kBigitSize, kChunkSize, MultiplyByUInt32(), SubtractBignum(), and used_digits_.

Referenced by DivideModuloIntBignum().

Here is the call graph for this function:

Here is the caller graph for this function:

Times10()

void v8::internal::Bignum::Times10 ( )

inline

Definition at line 39 of file bignum.h.

{ return MultiplyByUInt32(10); }

References MultiplyByUInt32().

Referenced by v8::internal::BignumToFixed(), v8::internal::FixupMultiply10(), v8::internal::GenerateCountedDigits(), and v8::internal::GenerateShortestDigits().

Here is the call graph for this function:

Here is the caller graph for this function:

ToHexString()

bool v8::internal::Bignum::ToHexString	(	char *	buffer,
		int	buffer_size
	)		const

Definition at line 549 of file bignum.cc.

                                                            {
  DCHECK(IsClamped());
  // Each bigit must be printable as separate hex-character.
  DCHECK(kBigitSize % 4 == 0);
  const int kHexCharsPerBigit = kBigitSize / 4;
 
  if (used_digits_ == 0) {
    if (buffer_size < 2) return false;
    buffer[0] = '0';
    buffer[1] = '\0';
    return true;
  }
  // We add 1 for the terminating '\0' character.
  int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +
      SizeInHexChars(bigits_[used_digits_ - 1]) + 1;
  if (needed_chars > buffer_size) return false;
  int string_index = needed_chars - 1;
  buffer[string_index--] = '\0';
  for (int i = 0; i < exponent_; ++i) {
    for (int j = 0; j < kHexCharsPerBigit; ++j) {
      buffer[string_index--] = '0';
    }
  }
  for (int i = 0; i < used_digits_ - 1; ++i) {
    Chunk current_bigit = bigits_[i];
    for (int j = 0; j < kHexCharsPerBigit; ++j) {
      buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);
      current_bigit >>= 4;
    }
  }
  // And finally the last bigit.
  Chunk most_significant_bigit = bigits_[used_digits_ - 1];
  while (most_significant_bigit != 0) {
    buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);
    most_significant_bigit >>= 4;
  }
  return true;
}

References BigitLength(), bigits_, DCHECK, exponent_, v8::internal::HexCharOfValue(), IsClamped(), kBigitSize, v8::internal::SizeInHexChars(), and used_digits_.

Here is the call graph for this function:

Zero()

void v8::internal::Bignum::Zero ( )

private

Definition at line 667 of file bignum.cc.

                  {
  for (int i = 0; i < used_digits_; ++i) {
    bigits_[i] = 0;
  }
  used_digits_ = 0;
  exponent_ = 0;
}

References bigits_, exponent_, and used_digits_.

Referenced by AssignDecimalString(), AssignHexString(), AssignPowerUInt16(), AssignUInt16(), AssignUInt64(), MultiplyByUInt32(), and MultiplyByUInt64().

Here is the caller graph for this function:

Member Data Documentation

bigits_

Vector<Chunk> v8::internal::Bignum::bigits_

private

Definition at line 108 of file bignum.h.

Referenced by AddBignum(), Align(), AssignBignum(), AssignHexString(), AssignUInt16(), AssignUInt64(), BigitAt(), BigitsShiftLeft(), Bignum(), Clamp(), DivideModuloIntBignum(), IsClamped(), MultiplyByUInt32(), MultiplyByUInt64(), Square(), SubtractBignum(), SubtractTimes(), ToHexString(), and Zero().

bigits_buffer_

Chunk v8::internal::Bignum::bigits_buffer_[kBigitCapacity]

private

Definition at line 105 of file bignum.h.

exponent_

int v8::internal::Bignum::exponent_

private

Definition at line 111 of file bignum.h.

Referenced by AddBignum(), Align(), AssignBignum(), BigitAt(), BigitLength(), Clamp(), Compare(), PlusCompare(), ShiftLeft(), Square(), SubtractBignum(), SubtractTimes(), ToHexString(), and Zero().

kBigitCapacity

const int v8::internal::Bignum::kBigitCapacity = kMaxSignificantBits / kBigitSize

staticprivate

Definition at line 85 of file bignum.h.

Referenced by Bignum(), and EnsureCapacity().

kBigitMask

const Chunk v8::internal::Bignum::kBigitMask = (1 << kBigitSize) - 1

staticprivate

Definition at line 82 of file bignum.h.

Referenced by AddBignum(), AssignUInt64(), BigitsShiftLeft(), MultiplyByUInt32(), MultiplyByUInt64(), Square(), SubtractBignum(), and SubtractTimes().

kBigitSize

const int v8::internal::Bignum::kBigitSize = 28

staticprivate

Definition at line 81 of file bignum.h.

Referenced by AddBignum(), AssignHexString(), AssignPowerUInt16(), AssignUInt16(), AssignUInt64(), BigitsShiftLeft(), DivideModuloIntBignum(), MultiplyByUInt32(), MultiplyByUInt64(), PlusCompare(), ShiftLeft(), Square(), SubtractTimes(), and ToHexString().

kChunkSize

const int v8::internal::Bignum::kChunkSize = sizeof(Chunk) * 8

staticprivate

Definition at line 77 of file bignum.h.

Referenced by Square(), SubtractBignum(), and SubtractTimes().

kDoubleChunkSize

const int v8::internal::Bignum::kDoubleChunkSize = sizeof(DoubleChunk) * 8

staticprivate

Definition at line 78 of file bignum.h.

Referenced by MultiplyByUInt32().

kMaxSignificantBits

const int v8::internal::Bignum::kMaxSignificantBits = 3584

static

Definition at line 16 of file bignum.h.

Referenced by v8::internal::BignumDtoa(), and v8::internal::BignumStrtod().

used_digits_

int v8::internal::Bignum::used_digits_

private

Definition at line 109 of file bignum.h.

Referenced by AddBignum(), Align(), AssignBignum(), AssignHexString(), AssignUInt16(), AssignUInt64(), BigitLength(), BigitsShiftLeft(), Clamp(), DivideModuloIntBignum(), IsClamped(), MultiplyByPowerOfTen(), MultiplyByUInt32(), MultiplyByUInt64(), ShiftLeft(), Square(), SubtractBignum(), SubtractTimes(), ToHexString(), and Zero().

---

The documentation for this class was generated from the following files:

• /mnt/V8SourceCode/src/bignum.h
• /mnt/V8SourceCode/src/bignum.cc