New bigint implementation in the vm.

runtime/vm/object.h

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #ifndef VM_OBJECT_H_
 #define VM_OBJECT_H_
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "platform/utils.h"
@@ skipping 1012 matching lines @@
   intptr_t FindClosureIndex(const Function& function) const;
   RawFunction* ClosureFunctionFromIndex(intptr_t idx) const;
 
   RawFunction* LookupDynamicFunction(const String& name) const;
   RawFunction* LookupDynamicFunctionAllowPrivate(const String& name) const;
   RawFunction* LookupStaticFunction(const String& name) const;
   RawFunction* LookupStaticFunctionAllowPrivate(const String& name) const;
   RawFunction* LookupConstructor(const String& name) const;
   RawFunction* LookupConstructorAllowPrivate(const String& name) const;
   RawFunction* LookupFactory(const String& name) const;
+  RawFunction* LookupFactoryAllowPrivate(const String& name) const;
   RawFunction* LookupFunction(const String& name) const;
   RawFunction* LookupFunctionAllowPrivate(const String& name) const;
   RawFunction* LookupGetterFunction(const String& name) const;
   RawFunction* LookupSetterFunction(const String& name) const;
   RawFunction* LookupFunctionAtToken(intptr_t token_pos) const;
   RawField* LookupInstanceField(const String& name) const;
   RawField* LookupStaticField(const String& name) const;
   RawField* LookupField(const String& name) const;
 
   RawLibraryPrefix* LookupLibraryPrefix(const String& name) const;
@@ skipping 4060 matching lines @@
 
  private:
   OBJECT_IMPLEMENTATION(Number, Instance);
   friend class Class;
 };
 
 
 class Integer : public Number {
  public:
   static RawInteger* New(const String& str, Heap::Space space = Heap::kNew);
-  static RawInteger* NewFromUint64(
-      uint64_t value, Heap::Space space = Heap::kNew);
+  static RawInteger* NewFromUint64(uint64_t value,
+                                   Heap::Space space = Heap::kNew);
 
   // Returns a canonical Integer object allocated in the old gen space.
   static RawInteger* NewCanonical(const String& str);
 
   // Do not throw JavascriptIntegerOverflow if 'silent' is true.
   static RawInteger* New(int64_t value,
                          Heap::Space space = Heap::kNew,
                          const bool silent = false);
 
   virtual bool OperatorEquals(const Instance& other) const {
     return Equals(other);
   }
   virtual bool CanonicalizeEquals(const Instance& other) const {
     return Equals(other);
   }
-  virtual bool Equals(const Instance& other) const {
-    UNREACHABLE();
-    return false;
-  }
+  virtual bool Equals(const Instance& other) const;
 
   virtual RawObject* HashCode() const { return raw(); }
 
-  // Integer is an abstract class.
-  virtual bool IsZero() const {
-    UNREACHABLE();
-    return false;
-  }
-  virtual bool IsNegative() const {
-    // Number is an abstract class.
-    UNREACHABLE();
-    return false;
-  }
+  virtual bool IsZero() const;
+  virtual bool IsNegative() const;
+
   virtual double AsDoubleValue() const;
   virtual int64_t AsInt64Value() const;
   virtual uint32_t AsTruncatedUint32Value() const;
 
+  virtual bool FitsIntoSmi() const;
+
   // Returns 0, -1 or 1.
   virtual int CompareWith(const Integer& other) const;
 
   // Return the most compact presentation of an integer.
   RawInteger* AsValidInteger() const;
 
   RawInteger* ArithmeticOp(Token::Kind operation, const Integer& other) const;
   RawInteger* BitOp(Token::Kind operation, const Integer& other) const;
 
   // Returns true if the Integer does not fit in a Javascript integer.
   bool CheckJavascriptIntegerOverflow() const;
 
  private:
-  // Return an integer in the form of a RawBigint.
-  RawBigint* AsBigint() const;
-
   OBJECT_IMPLEMENTATION(Integer, Number);
   friend class Class;
 };
 
 
 class Smi : public Integer {
  public:
   static const intptr_t kBits = kSmiBits;
   static const intptr_t kMaxValue = kSmiMax;
   static const intptr_t kMinValue = kSmiMin;
 
   intptr_t Value() const {
     return ValueFromRaw(raw_value());
   }
 
   virtual bool Equals(const Instance& other) const;
   virtual bool IsZero() const { return Value() == 0; }
   virtual bool IsNegative() const { return Value() < 0; }
   // Smi values are implicitly canonicalized.
   virtual RawInstance* CheckAndCanonicalize(const char** error_str) const {
     return reinterpret_cast<RawSmi*>(raw_value());
   }
 
   virtual double AsDoubleValue() const;
   virtual int64_t AsInt64Value() const;
   virtual uint32_t AsTruncatedUint32Value() const;
 
+  virtual bool FitsIntoSmi() const { return true; }
+
   virtual int CompareWith(const Integer& other) const;
 
   static intptr_t InstanceSize() { return 0; }
 
   static RawSmi* New(intptr_t value) {
     intptr_t raw_smi = (value << kSmiTagShift) | kSmiTag;
     ASSERT(ValueFromRaw(raw_smi) == value);
     return reinterpret_cast<RawSmi*>(raw_smi);
   }
 
@@ skipping 66 matching lines @@
   virtual bool IsNegative() const {
     return value() < 0;
   }
 
   virtual bool Equals(const Instance& other) const;
 
   virtual double AsDoubleValue() const;
   virtual int64_t AsInt64Value() const;
   virtual uint32_t AsTruncatedUint32Value() const;
 
+  virtual bool FitsIntoSmi() const;
+
   virtual int CompareWith(const Integer& other) const;
 
   static intptr_t InstanceSize() {
     return RoundedAllocationSize(sizeof(RawMint));
   }
 
  protected:
   // Only Integer::NewXXX is allowed to call Mint::NewXXX directly.
   friend class Integer;
 
   static RawMint* New(int64_t value, Heap::Space space = Heap::kNew);
 
   static RawMint* NewCanonical(int64_t value);
 
  private:
   void set_value(int64_t value) const;
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(Mint, Integer);
   friend class Class;
 };
 
 
 class Bigint : public Integer {
- private:
-  typedef uint32_t Chunk;
-  typedef uint64_t DoubleChunk;
-  static const int kChunkSize = sizeof(Chunk);
-
  public:
-  virtual bool IsZero() const { return raw_ptr()->signed_length_ == 0; }
-  virtual bool IsNegative() const { return raw_ptr()->signed_length_ < 0; }
-
+  virtual bool IsZero() const { return Used() == 0;}
+  virtual bool IsNegative() const { return Neg(); }
   virtual bool Equals(const Instance& other) const;
 
   virtual double AsDoubleValue() const;
   virtual int64_t AsInt64Value() const;
   virtual uint32_t AsTruncatedUint32Value() const;
 
   virtual int CompareWith(const Integer& other) const;
 
-  static const intptr_t kBytesPerElement = kChunkSize;
-  static const intptr_t kMaxElements = kSmiMax / kBytesPerElement;
+  virtual bool CheckAndCanonicalizeFields(const char** error_str) const;
 
-  static intptr_t InstanceSize() { return 0; }
+  virtual bool FitsIntoSmi() const;
+  bool FitsIntoInt64() const;
+  bool FitsIntoUint64() const;
+  uint64_t AsUint64Value() const;
 
-  static intptr_t InstanceSize(intptr_t len) {
-    ASSERT(0 <= len && len <= kMaxElements);
-    return RoundedAllocationSize(sizeof(RawBigint) + (len * kBytesPerElement));
+  static intptr_t InstanceSize() {
+    return RoundedAllocationSize(sizeof(RawBigint));
   }
 
- protected:
-  // Only Integer::NewXXX is allowed to call Bigint::NewXXX directly.
-  friend class Integer;
+  // Accessors used by native calls from Dart.
+  RawBool* neg() const { return raw_ptr()->neg_; }
+  void set_neg(const Bool& value) const;
+  RawSmi* used() const { return raw_ptr()->used_; }
+  void set_used(const Smi& value) const;
+  RawTypedData* digits() const { return raw_ptr()->digits_; }
+  void set_digits(const TypedData& value) const;
 
-  RawBigint* BigArithmeticOp(Token::Kind operation, const Bigint& other) const;
+  // Accessors used by runtime calls from C++.
+  bool Neg() const;
+  void SetNeg(bool value) const;
+  intptr_t Used() const;
+  void SetUsed(intptr_t value) const;
+  uint32_t DigitAt(intptr_t index) const;
+  void SetDigitAt(intptr_t index, uint32_t value) const;
 
-  static RawBigint* New(const String& str, Heap::Space space = Heap::kNew);
+  const char* ToDecCString(uword (*allocator)(intptr_t size)) const;
+  const char* ToHexCString(uword (*allocator)(intptr_t size)) const;
+
+  static const intptr_t kExtraDigits = 4;  // Same as _Bigint.EXTRA_DIGITS
+  static const intptr_t kBitsPerDigit = 32;  // Same as _Bigint.DIGIT_BITS
+  static const int64_t kDigitBase = 1LL << kBitsPerDigit;
+  static const int64_t kDigitMask = kDigitBase - 1;
+
+  static RawBigint* New(Heap::Space space = Heap::kNew);
+
+  static RawBigint* NewFromInt64(int64_t value,
+                                  Heap::Space space = Heap::kNew);
+
+  static RawBigint* NewFromUint64(uint64_t value,
+                                   Heap::Space space = Heap::kNew);
+
+  static RawBigint* NewFromShiftedInt64(int64_t value, intptr_t shift,
+                                         Heap::Space space = Heap::kNew);
+
+  static RawBigint* NewFromCString(const char* str,
+                                    Heap::Space space = Heap::kNew);
 
   // Returns a canonical Bigint object allocated in the old gen space.
   static RawBigint* NewCanonical(const String& str);
 
  private:
-  Chunk GetChunkAt(intptr_t i) const {
-    return *ChunkAddr(i);
-  }
+  static RawBigint* NewFromHexCString(const char* str,
+                                       Heap::Space space = Heap::kNew);
+  static RawBigint* NewFromDecCString(const char* str,
+                                       Heap::Space space = Heap::kNew);
 
-  void SetChunkAt(intptr_t i, Chunk newValue) const {
-    *ChunkAddr(i) = newValue;
-  }
+  // Make sure at least 'length' _digits are allocated.
+  // Copy existing _digits if reallocation is necessary.
+  // TODO(regis): Check that we are not preserving digits unnecessarily.
+  void EnsureLength(intptr_t length, Heap::Space space = Heap::kNew) const;
 
-  // Returns the number of chunks in use.
-  intptr_t Length() const {
-    intptr_t signed_length = raw_ptr()->signed_length_;
-    return Utils::Abs(signed_length);
-  }
+  // Do not count zero high digits as used.
+  void Clamp() const;
 
-  // SetLength does not change the sign.
-  void SetLength(intptr_t length) const {
-    ASSERT(length >= 0);
-    bool is_negative = IsNegative();
-    raw_ptr()->signed_length_ = length;
-    if (is_negative) ToggleSign();
-  }
-
-  void SetSign(bool is_negative) const {
-    if (is_negative != IsNegative()) {
-      ToggleSign();
-    }
-  }
-
-  void ToggleSign() const {
-    raw_ptr()->signed_length_ = -raw_ptr()->signed_length_;
-  }
-
-  Chunk* ChunkAddr(intptr_t index) const {
-    ASSERT(0 <= index);
-    ASSERT(index < Length());
-    uword digits_start = reinterpret_cast<uword>(raw_ptr()) + sizeof(RawBigint);
-    return &(reinterpret_cast<Chunk*>(digits_start)[index]);
-  }
+  bool IsClamped() const;
 
   static RawBigint* Allocate(intptr_t length, Heap::Space space = Heap::kNew);
 
   FINAL_HEAP_OBJECT_IMPLEMENTATION(Bigint, Integer);
-  friend class BigintOperations;
   friend class Class;
 };
 
 
 // Class Double represents class Double in corelib_impl, which implements
 // abstract class double in corelib.
 class Double : public Number {
  public:
   double value() const {
     return raw_ptr()->value_;
@@ skipping 1193 matching lines @@
     intptr_t cid = raw()->GetClassId();
     return (ElementSizeInBytes(cid) * Length());
   }
 
   void* DataAddr(intptr_t byte_offset) const {
     ASSERT((byte_offset == 0) ||
            ((byte_offset > 0) && (byte_offset < LengthInBytes())));
     return reinterpret_cast<void*>(raw_ptr()->data() + byte_offset);
   }
 
+  virtual bool CanonicalizeEquals(const Instance& other) const;
+
 #define TYPED_GETTER_SETTER(name, type)                                        \
   type Get##name(intptr_t byte_offset) const {                                 \
     return *reinterpret_cast<type*>(DataAddr(byte_offset));                    \
   }                                                                            \
   void Set##name(intptr_t byte_offset, type value) const {                     \
     *reinterpret_cast<type*>(DataAddr(byte_offset)) = value;                   \
   }
   TYPED_GETTER_SETTER(Int8, int8_t)
   TYPED_GETTER_SETTER(Uint8, uint8_t)
   TYPED_GETTER_SETTER(Int16, int16_t)
@@ skipping 812 matching lines @@
 
 
 RawObject* MegamorphicCache::GetTargetFunction(const Array& array,
                                                intptr_t index) {
   return array.At((index * kEntryLength) + kTargetFunctionIndex);
 }
 
 }  // namespace dart
 
 #endif  // VM_OBJECT_H_