src/bignum.h

   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 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   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     return Compare(a, b) == 0;
  53   }
  54   static bool LessEqual(const Bignum& a, const Bignum& b) {
  55     return Compare(a, b) <= 0;
  56   }
  57   static bool Less(const Bignum& a, const Bignum& b) {
  58     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     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     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     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     if (size > kBigitCapacity) {
  91       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   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 v8::internal
 119
 120 #endif  // V8_BIGNUM_H_