Line data    Source code

       1             : // Copyright 2010 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #ifndef V8_BIGNUM_H_
       6             : #define V8_BIGNUM_H_
       7             : 
       8             : #include "src/vector.h"
       9             : 
      10             : namespace v8 {
      11             : namespace internal {
      12             : 
      13             : class V8_EXPORT_PRIVATE Bignum {
      14             :  public:
      15             :   // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately.
      16             :   // This bignum can encode much bigger numbers, since it contains an
      17             :   // exponent.
      18             :   static const int kMaxSignificantBits = 3584;
      19             : 
      20             :   Bignum();
      21             :   void AssignUInt16(uint16_t value);
      22             :   void AssignUInt64(uint64_t value);
      23             :   void AssignBignum(const Bignum& other);
      24             : 
      25             :   void AssignDecimalString(Vector<const char> value);
      26             :   void AssignHexString(Vector<const char> value);
      27             : 
      28             :   void AssignPowerUInt16(uint16_t base, int exponent);
      29             : 
      30             :   void AddUInt16(uint16_t operand);
      31             :   void AddUInt64(uint64_t operand);
      32             :   void AddBignum(const Bignum& other);
      33             :   // Precondition: this >= other.
      34             :   void SubtractBignum(const Bignum& other);
      35             : 
      36             :   void Square();
      37             :   void ShiftLeft(int shift_amount);
      38             :   void MultiplyByUInt32(uint32_t factor);
      39             :   void MultiplyByUInt64(uint64_t factor);
      40             :   void MultiplyByPowerOfTen(int exponent);
      41    21706153 :   void Times10() { return MultiplyByUInt32(10); }
      42             :   // Pseudocode:
      43             :   //  int result = this / other;
      44             :   //  this = this % other;
      45             :   // In the worst case this function is in O(this/other).
      46             :   uint16_t DivideModuloIntBignum(const Bignum& other);
      47             : 
      48             :   bool ToHexString(char* buffer, int buffer_size) const;
      49             : 
      50             :   static int Compare(const Bignum& a, const Bignum& b);
      51             :   static bool Equal(const Bignum& a, const Bignum& b) {
      52     1697790 :     return Compare(a, b) == 0;
      53             :   }
      54             :   static bool LessEqual(const Bignum& a, const Bignum& b) {
      55     6928751 :     return Compare(a, b) <= 0;
      56             :   }
      57             :   static bool Less(const Bignum& a, const Bignum& b) {
      58     4149366 :     return Compare(a, b) < 0;
      59             :   }
      60             :   // Returns Compare(a + b, c);
      61             :   static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c);
      62             :   // Returns a + b == c
      63             :   static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
      64          15 :     return PlusCompare(a, b, c) == 0;
      65             :   }
      66             :   // Returns a + b <= c
      67             :   static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
      68          15 :     return PlusCompare(a, b, c) <= 0;
      69             :   }
      70             :   // Returns a + b < c
      71             :   static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) {
      72          15 :     return PlusCompare(a, b, c) < 0;
      73             :   }
      74             : 
      75             :  private:
      76             :   typedef uint32_t Chunk;
      77             :   typedef uint64_t DoubleChunk;
      78             : 
      79             :   static const int kChunkSize = sizeof(Chunk) * 8;
      80             :   static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8;
      81             :   // With bigit size of 28 we loose some bits, but a double still fits easily
      82             :   // into two chunks, and more importantly we can use the Comba multiplication.
      83             :   static const int kBigitSize = 28;
      84             :   static const Chunk kBigitMask = (1 << kBigitSize) - 1;
      85             :   // Every instance allocates kBigitLength chunks on the stack. Bignums cannot
      86             :   // grow. There are no checks if the stack-allocated space is sufficient.
      87             :   static const int kBigitCapacity = kMaxSignificantBits / kBigitSize;
      88             : 
      89             :   void EnsureCapacity(int size) {
      90    15614947 :     if (size > kBigitCapacity) {
      91           0 :       UNREACHABLE();
      92             :     }
      93             :   }
      94             :   void Align(const Bignum& other);
      95             :   void Clamp();
      96             :   bool IsClamped() const;
      97             :   void Zero();
      98             :   // Requires this to have enough capacity (no tests done).
      99             :   // Updates used_digits_ if necessary.
     100             :   // by must be < kBigitSize.
     101             :   void BigitsShiftLeft(int shift_amount);
     102             :   // BigitLength includes the "hidden" digits encoded in the exponent.
     103    81725758 :   int BigitLength() const { return used_digits_ + exponent_; }
     104             :   Chunk BigitAt(int index) const;
     105             :   void SubtractTimes(const Bignum& other, int factor);
     106             : 
     107             :   Chunk bigits_buffer_[kBigitCapacity];
     108             :   // A vector backed by bigits_buffer_. This way accesses to the array are
     109             :   // checked for out-of-bounds errors.
     110             :   Vector<Chunk> bigits_;
     111             :   int used_digits_;
     112             :   // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).
     113             :   int exponent_;
     114             : 
     115             :   DISALLOW_COPY_AND_ASSIGN(Bignum);
     116             : };
     117             : 
     118             : }  // namespace internal
     119             : }  // namespace v8
     120             : 
     121             : #endif  // V8_BIGNUM_H_