Home | History | Annotate | Download | only in src
      1 // Copyright 2010 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #ifndef V8_BIGNUM_H_
     29 #define V8_BIGNUM_H_
     30 
     31 namespace v8 {
     32 namespace internal {
     33 
     34 class Bignum {
     35  public:
     36   // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately.
     37   // This bignum can encode much bigger numbers, since it contains an
     38   // exponent.
     39   static const int kMaxSignificantBits = 3584;
     40 
     41   Bignum();
     42   void AssignUInt16(uint16_t value);
     43   void AssignUInt64(uint64_t value);
     44   void AssignBignum(const Bignum& other);
     45 
     46   void AssignDecimalString(Vector<const char> value);
     47   void AssignHexString(Vector<const char> value);
     48 
     49   void AssignPowerUInt16(uint16_t base, int exponent);
     50 
     51   void AddUInt16(uint16_t operand);
     52   void AddUInt64(uint64_t operand);
     53   void AddBignum(const Bignum& other);
     54   // Precondition: this >= other.
     55   void SubtractBignum(const Bignum& other);
     56 
     57   void Square();
     58   void ShiftLeft(int shift_amount);
     59   void MultiplyByUInt32(uint32_t factor);
     60   void MultiplyByUInt64(uint64_t factor);
     61   void MultiplyByPowerOfTen(int exponent);
     62   void Times10() { return MultiplyByUInt32(10); }
     63   // Pseudocode:
     64   //  int result = this / other;
     65   //  this = this % other;
     66   // In the worst case this function is in O(this/other).
     67   uint16_t DivideModuloIntBignum(const Bignum& other);
     68 
     69   bool ToHexString(char* buffer, int buffer_size) const;
     70 
     71   static int Compare(const Bignum& a, const Bignum& b);
     72   static bool Equal(const Bignum& a, const Bignum& b) {
     73     return Compare(a, b) == 0;
     74   }
     75   static bool LessEqual(const Bignum& a, const Bignum& b) {
     76     return Compare(a, b) <= 0;
     77   }
     78   static bool Less(const Bignum& a, const Bignum& b) {
     79     return Compare(a, b) < 0;
     80   }
     81   // Returns Compare(a + b, c);
     82   static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c);
     83   // Returns a + b == c
     84   static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
     85     return PlusCompare(a, b, c) == 0;
     86   }
     87   // Returns a + b <= c
     88   static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
     89     return PlusCompare(a, b, c) <= 0;
     90   }
     91   // Returns a + b < c
     92   static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) {
     93     return PlusCompare(a, b, c) < 0;
     94   }
     95  private:
     96   typedef uint32_t Chunk;
     97   typedef uint64_t DoubleChunk;
     98 
     99   static const int kChunkSize = sizeof(Chunk) * 8;
    100   static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8;
    101   // With bigit size of 28 we loose some bits, but a double still fits easily
    102   // into two chunks, and more importantly we can use the Comba multiplication.
    103   static const int kBigitSize = 28;
    104   static const Chunk kBigitMask = (1 << kBigitSize) - 1;
    105   // Every instance allocates kBigitLength chunks on the stack. Bignums cannot
    106   // grow. There are no checks if the stack-allocated space is sufficient.
    107   static const int kBigitCapacity = kMaxSignificantBits / kBigitSize;
    108 
    109   void EnsureCapacity(int size) {
    110     if (size > kBigitCapacity) {
    111       UNREACHABLE();
    112     }
    113   }
    114   void Align(const Bignum& other);
    115   void Clamp();
    116   bool IsClamped() const;
    117   void Zero();
    118   // Requires this to have enough capacity (no tests done).
    119   // Updates used_digits_ if necessary.
    120   // by must be < kBigitSize.
    121   void BigitsShiftLeft(int shift_amount);
    122   // BigitLength includes the "hidden" digits encoded in the exponent.
    123   int BigitLength() const { return used_digits_ + exponent_; }
    124   Chunk BigitAt(int index) const;
    125   void SubtractTimes(const Bignum& other, int factor);
    126 
    127   Chunk bigits_buffer_[kBigitCapacity];
    128   // A vector backed by bigits_buffer_. This way accesses to the array are
    129   // checked for out-of-bounds errors.
    130   Vector<Chunk> bigits_;
    131   int used_digits_;
    132   // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).
    133   int exponent_;
    134 
    135   DISALLOW_COPY_AND_ASSIGN(Bignum);
    136 };
    137 
    138 } }  // namespace v8::internal
    139 
    140 #endif  // V8_BIGNUM_H_
    141