deps/v8/src/utils.h

   1 // Copyright 2012 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_UTILS_H_
   6 #define V8_UTILS_H_
   7
   8 #include <limits.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11 #include <cmath>
  12
  13 #include "include/v8.h"
  14 #include "src/allocation.h"
  15 #include "src/base/bits.h"
  16 #include "src/base/logging.h"
  17 #include "src/base/macros.h"
  18 #include "src/base/platform/platform.h"
  19 #include "src/globals.h"
  20 #include "src/list.h"
  21 #include "src/vector.h"
  22
  23 namespace v8 {
  24 namespace internal {
  25
  26 // ----------------------------------------------------------------------------
  27 // General helper functions
  28
  29
  30 inline int BoolToInt(bool b) { return b ? 1 : 0; }
  31
  32
  33 // Same as strcmp, but can handle NULL arguments.
  34 inline bool CStringEquals(const char* s1, const char* s2) {
  35   return (s1 == s2) || (s1 != NULL && s2 != NULL && strcmp(s1, s2) == 0);
  36 }
  37
  38
  39 // X must be a power of 2.  Returns the number of trailing zeros.
  40 inline int WhichPowerOf2(uint32_t x) {
  41   DCHECK(base::bits::IsPowerOfTwo32(x));
  42   int bits = 0;
  43 #ifdef DEBUG
  44   int original_x = x;
  45 #endif
  46   if (x >= 0x10000) {
  47     bits += 16;
  48     x >>= 16;
  49   }
  50   if (x >= 0x100) {
  51     bits += 8;
  52     x >>= 8;
  53   }
  54   if (x >= 0x10) {
  55     bits += 4;
  56     x >>= 4;
  57   }
  58   switch (x) {
  59     default: UNREACHABLE();
  60     case 8: bits++;  // Fall through.
  61     case 4: bits++;  // Fall through.
  62     case 2: bits++;  // Fall through.
  63     case 1: break;
  64   }
  65   DCHECK_EQ(1 << bits, original_x);
  66   return bits;
  67 }
  68
  69
  70 inline int MostSignificantBit(uint32_t x) {
  71   static const int msb4[] = {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4};
  72   int nibble = 0;
  73   if (x & 0xffff0000) {
  74     nibble += 16;
  75     x >>= 16;
  76   }
  77   if (x & 0xff00) {
  78     nibble += 8;
  79     x >>= 8;
  80   }
  81   if (x & 0xf0) {
  82     nibble += 4;
  83     x >>= 4;
  84   }
  85   return nibble + msb4[x];
  86 }
  87
  88
  89 // The C++ standard leaves the semantics of '>>' undefined for
  90 // negative signed operands. Most implementations do the right thing,
  91 // though.
  92 inline int ArithmeticShiftRight(int x, int s) {
  93   return x >> s;
  94 }
  95
  96
  97 template <typename T>
  98 int Compare(const T& a, const T& b) {
  99   if (a == b)
 100     return 0;
 101   else if (a < b)
 102     return -1;
 103   else
 104     return 1;
 105 }
 106
 107
 108 template <typename T>
 109 int PointerValueCompare(const T* a, const T* b) {
 110   return Compare<T>(*a, *b);
 111 }
 112
 113
 114 // Compare function to compare the object pointer value of two
 115 // handlified objects. The handles are passed as pointers to the
 116 // handles.
 117 template<typename T> class Handle;  // Forward declaration.
 118 template <typename T>
 119 int HandleObjectPointerCompare(const Handle<T>* a, const Handle<T>* b) {
 120   return Compare<T*>(*(*a), *(*b));
 121 }
 122
 123
 124 template <typename T, typename U>
 125 inline bool IsAligned(T value, U alignment) {
 126   return (value & (alignment - 1)) == 0;
 127 }
 128
 129
 130 // Returns true if (addr + offset) is aligned.
 131 inline bool IsAddressAligned(Address addr,
 132                              intptr_t alignment,
 133                              int offset = 0) {
 134   intptr_t offs = OffsetFrom(addr + offset);
 135   return IsAligned(offs, alignment);
 136 }
 137
 138
 139 // Returns the maximum of the two parameters.
 140 template <typename T>
 141 T Max(T a, T b) {
 142   return a < b ? b : a;
 143 }
 144
 145
 146 // Returns the minimum of the two parameters.
 147 template <typename T>
 148 T Min(T a, T b) {
 149   return a < b ? a : b;
 150 }
 151
 152
 153 // Returns the absolute value of its argument.
 154 template <typename T>
 155 T Abs(T a) {
 156   return a < 0 ? -a : a;
 157 }
 158
 159
 160 // Floor(-0.0) == 0.0
 161 inline double Floor(double x) {
 162 #if V8_CC_MSVC
 163   if (x == 0) return x;  // Fix for issue 3477.
 164 #endif
 165   return std::floor(x);
 166 }
 167
 168
 169 // TODO(svenpanne) Clean up the whole power-of-2 mess.
 170 inline int32_t WhichPowerOf2Abs(int32_t x) {
 171   return (x == kMinInt) ? 31 : WhichPowerOf2(Abs(x));
 172 }
 173
 174
 175 // Obtains the unsigned type corresponding to T
 176 // available in C++11 as std::make_unsigned
 177 template<typename T>
 178 struct make_unsigned {
 179   typedef T type;
 180 };
 181
 182
 183 // Template specializations necessary to have make_unsigned work
 184 template<> struct make_unsigned<int32_t> {
 185   typedef uint32_t type;
 186 };
 187
 188
 189 template<> struct make_unsigned<int64_t> {
 190   typedef uint64_t type;
 191 };
 192
 193
 194 // ----------------------------------------------------------------------------
 195 // BitField is a help template for encoding and decode bitfield with
 196 // unsigned content.
 197
 198 template<class T, int shift, int size, class U>
 199 class BitFieldBase {
 200  public:
 201   // A type U mask of bit field.  To use all bits of a type U of x bits
 202   // in a bitfield without compiler warnings we have to compute 2^x
 203   // without using a shift count of x in the computation.
 204   static const U kOne = static_cast<U>(1U);
 205   static const U kMask = ((kOne << shift) << size) - (kOne << shift);
 206   static const U kShift = shift;
 207   static const U kSize = size;
 208   static const U kNext = kShift + kSize;
 209
 210   // Value for the field with all bits set.
 211   static const T kMax = static_cast<T>((kOne << size) - 1);
 212
 213   // Tells whether the provided value fits into the bit field.
 214   static bool is_valid(T value) {
 215     return (static_cast<U>(value) & ~static_cast<U>(kMax)) == 0;
 216   }
 217
 218   // Returns a type U with the bit field value encoded.
 219   static U encode(T value) {
 220     DCHECK(is_valid(value));
 221     return static_cast<U>(value) << shift;
 222   }
 223
 224   // Returns a type U with the bit field value updated.
 225   static U update(U previous, T value) {
 226     return (previous & ~kMask) | encode(value);
 227   }
 228
 229   // Extracts the bit field from the value.
 230   static T decode(U value) {
 231     return static_cast<T>((value & kMask) >> shift);
 232   }
 233 };
 234
 235
 236 template <class T, int shift, int size>
 237 class BitField8 : public BitFieldBase<T, shift, size, uint8_t> {};
 238
 239
 240 template <class T, int shift, int size>
 241 class BitField16 : public BitFieldBase<T, shift, size, uint16_t> {};
 242
 243
 244 template<class T, int shift, int size>
 245 class BitField : public BitFieldBase<T, shift, size, uint32_t> { };
 246
 247
 248 template<class T, int shift, int size>
 249 class BitField64 : public BitFieldBase<T, shift, size, uint64_t> { };
 250
 251
 252 // ----------------------------------------------------------------------------
 253 // BitSetComputer is a help template for encoding and decoding information for
 254 // a variable number of items in an array.
 255 //
 256 // To encode boolean data in a smi array you would use:
 257 // typedef BitSetComputer<bool, 1, kSmiValueSize, uint32_t> BoolComputer;
 258 //
 259 template <class T, int kBitsPerItem, int kBitsPerWord, class U>
 260 class BitSetComputer {
 261  public:
 262   static const int kItemsPerWord = kBitsPerWord / kBitsPerItem;
 263   static const int kMask = (1 << kBitsPerItem) - 1;
 264
 265   // The number of array elements required to embed T information for each item.
 266   static int word_count(int items) {
 267     if (items == 0) return 0;
 268     return (items - 1) / kItemsPerWord + 1;
 269   }
 270
 271   // The array index to look at for item.
 272   static int index(int base_index, int item) {
 273     return base_index + item / kItemsPerWord;
 274   }
 275
 276   // Extract T data for a given item from data.
 277   static T decode(U data, int item) {
 278     return static_cast<T>((data >> shift(item)) & kMask);
 279   }
 280
 281   // Return the encoding for a store of value for item in previous.
 282   static U encode(U previous, int item, T value) {
 283     int shift_value = shift(item);
 284     int set_bits = (static_cast<int>(value) << shift_value);
 285     return (previous & ~(kMask << shift_value)) | set_bits;
 286   }
 287
 288   static int shift(int item) { return (item % kItemsPerWord) * kBitsPerItem; }
 289 };
 290
 291
 292 // ----------------------------------------------------------------------------
 293 // Hash function.
 294
 295 static const uint32_t kZeroHashSeed = 0;
 296
 297 // Thomas Wang, Integer Hash Functions.
 298 // http://www.concentric.net/~Ttwang/tech/inthash.htm
 299 inline uint32_t ComputeIntegerHash(uint32_t key, uint32_t seed) {
 300   uint32_t hash = key;
 301   hash = hash ^ seed;
 302   hash = ~hash + (hash << 15);  // hash = (hash << 15) - hash - 1;
 303   hash = hash ^ (hash >> 12);
 304   hash = hash + (hash << 2);
 305   hash = hash ^ (hash >> 4);
 306   hash = hash * 2057;  // hash = (hash + (hash << 3)) + (hash << 11);
 307   hash = hash ^ (hash >> 16);
 308   return hash;
 309 }
 310
 311
 312 inline uint32_t ComputeLongHash(uint64_t key) {
 313   uint64_t hash = key;
 314   hash = ~hash + (hash << 18);  // hash = (hash << 18) - hash - 1;
 315   hash = hash ^ (hash >> 31);
 316   hash = hash * 21;  // hash = (hash + (hash << 2)) + (hash << 4);
 317   hash = hash ^ (hash >> 11);
 318   hash = hash + (hash << 6);
 319   hash = hash ^ (hash >> 22);
 320   return static_cast<uint32_t>(hash);
 321 }
 322
 323
 324 inline uint32_t ComputePointerHash(void* ptr) {
 325   return ComputeIntegerHash(
 326       static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr)),
 327       v8::internal::kZeroHashSeed);
 328 }
 329
 330
 331 // ----------------------------------------------------------------------------
 332 // Generated memcpy/memmove
 333
 334 // Initializes the codegen support that depends on CPU features. This is
 335 // called after CPU initialization.
 336 void init_memcopy_functions();
 337
 338 #if defined(V8_TARGET_ARCH_IA32) || defined(V8_TARGET_ARCH_X87)
 339 // Limit below which the extra overhead of the MemCopy function is likely
 340 // to outweigh the benefits of faster copying.
 341 const int kMinComplexMemCopy = 64;
 342
 343 // Copy memory area. No restrictions.
 344 void MemMove(void* dest, const void* src, size_t size);
 345 typedef void (*MemMoveFunction)(void* dest, const void* src, size_t size);
 346
 347 // Keep the distinction of "move" vs. "copy" for the benefit of other
 348 // architectures.
 349 V8_INLINE void MemCopy(void* dest, const void* src, size_t size) {
 350   MemMove(dest, src, size);
 351 }
 352 #elif defined(V8_HOST_ARCH_ARM)
 353 typedef void (*MemCopyUint8Function)(uint8_t* dest, const uint8_t* src,
 354                                      size_t size);
 355 extern MemCopyUint8Function memcopy_uint8_function;
 356 V8_INLINE void MemCopyUint8Wrapper(uint8_t* dest, const uint8_t* src,
 357                                    size_t chars) {
 358   memcpy(dest, src, chars);
 359 }
 360 // For values < 16, the assembler function is slower than the inlined C code.
 361 const int kMinComplexMemCopy = 16;
 362 V8_INLINE void MemCopy(void* dest, const void* src, size_t size) {
 363   (*memcopy_uint8_function)(reinterpret_cast<uint8_t*>(dest),
 364                             reinterpret_cast<const uint8_t*>(src), size);
 365 }
 366 V8_INLINE void MemMove(void* dest, const void* src, size_t size) {
 367   memmove(dest, src, size);
 368 }
 369
 370 typedef void (*MemCopyUint16Uint8Function)(uint16_t* dest, const uint8_t* src,
 371                                            size_t size);
 372 extern MemCopyUint16Uint8Function memcopy_uint16_uint8_function;
 373 void MemCopyUint16Uint8Wrapper(uint16_t* dest, const uint8_t* src,
 374                                size_t chars);
 375 // For values < 12, the assembler function is slower than the inlined C code.
 376 const int kMinComplexConvertMemCopy = 12;
 377 V8_INLINE void MemCopyUint16Uint8(uint16_t* dest, const uint8_t* src,
 378                                   size_t size) {
 379   (*memcopy_uint16_uint8_function)(dest, src, size);
 380 }
 381 #elif defined(V8_HOST_ARCH_MIPS)
 382 typedef void (*MemCopyUint8Function)(uint8_t* dest, const uint8_t* src,
 383                                      size_t size);
 384 extern MemCopyUint8Function memcopy_uint8_function;
 385 V8_INLINE void MemCopyUint8Wrapper(uint8_t* dest, const uint8_t* src,
 386                                    size_t chars) {
 387   memcpy(dest, src, chars);
 388 }
 389 // For values < 16, the assembler function is slower than the inlined C code.
 390 const int kMinComplexMemCopy = 16;
 391 V8_INLINE void MemCopy(void* dest, const void* src, size_t size) {
 392   (*memcopy_uint8_function)(reinterpret_cast<uint8_t*>(dest),
 393                             reinterpret_cast<const uint8_t*>(src), size);
 394 }
 395 V8_INLINE void MemMove(void* dest, const void* src, size_t size) {
 396   memmove(dest, src, size);
 397 }
 398 #else
 399 // Copy memory area to disjoint memory area.
 400 V8_INLINE void MemCopy(void* dest, const void* src, size_t size) {
 401   memcpy(dest, src, size);
 402 }
 403 V8_INLINE void MemMove(void* dest, const void* src, size_t size) {
 404   memmove(dest, src, size);
 405 }
 406 const int kMinComplexMemCopy = 16 * kPointerSize;
 407 #endif  // V8_TARGET_ARCH_IA32
 408
 409
 410 // ----------------------------------------------------------------------------
 411 // Miscellaneous
 412
 413 // A static resource holds a static instance that can be reserved in
 414 // a local scope using an instance of Access.  Attempts to re-reserve
 415 // the instance will cause an error.
 416 template <typename T>
 417 class StaticResource {
 418  public:
 419   StaticResource() : is_reserved_(false)  {}
 420
 421  private:
 422   template <typename S> friend class Access;
 423   T instance_;
 424   bool is_reserved_;
 425 };
 426
 427
 428 // Locally scoped access to a static resource.
 429 template <typename T>
 430 class Access {
 431  public:
 432   explicit Access(StaticResource<T>* resource)
 433     : resource_(resource)
 434     , instance_(&resource->instance_) {
 435     DCHECK(!resource->is_reserved_);
 436     resource->is_reserved_ = true;
 437   }
 438
 439   ~Access() {
 440     resource_->is_reserved_ = false;
 441     resource_ = NULL;
 442     instance_ = NULL;
 443   }
 444
 445   T* value()  { return instance_; }
 446   T* operator -> ()  { return instance_; }
 447
 448  private:
 449   StaticResource<T>* resource_;
 450   T* instance_;
 451 };
 452
 453
 454 // A pointer that can only be set once and doesn't allow NULL values.
 455 template<typename T>
 456 class SetOncePointer {
 457  public:
 458   SetOncePointer() : pointer_(NULL) { }
 459
 460   bool is_set() const { return pointer_ != NULL; }
 461
 462   T* get() const {
 463     DCHECK(pointer_ != NULL);
 464     return pointer_;
 465   }
 466
 467   void set(T* value) {
 468     DCHECK(pointer_ == NULL && value != NULL);
 469     pointer_ = value;
 470   }
 471
 472  private:
 473   T* pointer_;
 474 };
 475
 476
 477 template <typename T, int kSize>
 478 class EmbeddedVector : public Vector<T> {
 479  public:
 480   EmbeddedVector() : Vector<T>(buffer_, kSize) { }
 481
 482   explicit EmbeddedVector(T initial_value) : Vector<T>(buffer_, kSize) {
 483     for (int i = 0; i < kSize; ++i) {
 484       buffer_[i] = initial_value;
 485     }
 486   }
 487
 488   // When copying, make underlying Vector to reference our buffer.
 489   EmbeddedVector(const EmbeddedVector& rhs)
 490       : Vector<T>(rhs) {
 491     MemCopy(buffer_, rhs.buffer_, sizeof(T) * kSize);
 492     this->set_start(buffer_);
 493   }
 494
 495   EmbeddedVector& operator=(const EmbeddedVector& rhs) {
 496     if (this == &rhs) return *this;
 497     Vector<T>::operator=(rhs);
 498     MemCopy(buffer_, rhs.buffer_, sizeof(T) * kSize);
 499     this->set_start(buffer_);
 500     return *this;
 501   }
 502
 503  private:
 504   T buffer_[kSize];
 505 };
 506
 507
 508 /*
 509  * A class that collects values into a backing store.
 510  * Specialized versions of the class can allow access to the backing store
 511  * in different ways.
 512  * There is no guarantee that the backing store is contiguous (and, as a
 513  * consequence, no guarantees that consecutively added elements are adjacent
 514  * in memory). The collector may move elements unless it has guaranteed not
 515  * to.
 516  */
 517 template <typename T, int growth_factor = 2, int max_growth = 1 * MB>
 518 class Collector {
 519  public:
 520   explicit Collector(int initial_capacity = kMinCapacity)
 521       : index_(0), size_(0) {
 522     current_chunk_ = Vector<T>::New(initial_capacity);
 523   }
 524
 525   virtual ~Collector() {
 526     // Free backing store (in reverse allocation order).
 527     current_chunk_.Dispose();
 528     for (int i = chunks_.length() - 1; i >= 0; i--) {
 529       chunks_.at(i).Dispose();
 530     }
 531   }
 532
 533   // Add a single element.
 534   inline void Add(T value) {
 535     if (index_ >= current_chunk_.length()) {
 536       Grow(1);
 537     }
 538     current_chunk_[index_] = value;
 539     index_++;
 540     size_++;
 541   }
 542
 543   // Add a block of contiguous elements and return a Vector backed by the
 544   // memory area.
 545   // A basic Collector will keep this vector valid as long as the Collector
 546   // is alive.
 547   inline Vector<T> AddBlock(int size, T initial_value) {
 548     DCHECK(size > 0);
 549     if (size > current_chunk_.length() - index_) {
 550       Grow(size);
 551     }
 552     T* position = current_chunk_.start() + index_;
 553     index_ += size;
 554     size_ += size;
 555     for (int i = 0; i < size; i++) {
 556       position[i] = initial_value;
 557     }
 558     return Vector<T>(position, size);
 559   }
 560
 561
 562   // Add a contiguous block of elements and return a vector backed
 563   // by the added block.
 564   // A basic Collector will keep this vector valid as long as the Collector
 565   // is alive.
 566   inline Vector<T> AddBlock(Vector<const T> source) {
 567     if (source.length() > current_chunk_.length() - index_) {
 568       Grow(source.length());
 569     }
 570     T* position = current_chunk_.start() + index_;
 571     index_ += source.length();
 572     size_ += source.length();
 573     for (int i = 0; i < source.length(); i++) {
 574       position[i] = source[i];
 575     }
 576     return Vector<T>(position, source.length());
 577   }
 578
 579
 580   // Write the contents of the collector into the provided vector.
 581   void WriteTo(Vector<T> destination) {
 582     DCHECK(size_ <= destination.length());
 583     int position = 0;
 584     for (int i = 0; i < chunks_.length(); i++) {
 585       Vector<T> chunk = chunks_.at(i);
 586       for (int j = 0; j < chunk.length(); j++) {
 587         destination[position] = chunk[j];
 588         position++;
 589       }
 590     }
 591     for (int i = 0; i < index_; i++) {
 592       destination[position] = current_chunk_[i];
 593       position++;
 594     }
 595   }
 596
 597   // Allocate a single contiguous vector, copy all the collected
 598   // elements to the vector, and return it.
 599   // The caller is responsible for freeing the memory of the returned
 600   // vector (e.g., using Vector::Dispose).
 601   Vector<T> ToVector() {
 602     Vector<T> new_store = Vector<T>::New(size_);
 603     WriteTo(new_store);
 604     return new_store;
 605   }
 606
 607   // Resets the collector to be empty.
 608   virtual void Reset();
 609
 610   // Total number of elements added to collector so far.
 611   inline int size() { return size_; }
 612
 613  protected:
 614   static const int kMinCapacity = 16;
 615   List<Vector<T> > chunks_;
 616   Vector<T> current_chunk_;  // Block of memory currently being written into.
 617   int index_;  // Current index in current chunk.
 618   int size_;  // Total number of elements in collector.
 619
 620   // Creates a new current chunk, and stores the old chunk in the chunks_ list.
 621   void Grow(int min_capacity) {
 622     DCHECK(growth_factor > 1);
 623     int new_capacity;
 624     int current_length = current_chunk_.length();
 625     if (current_length < kMinCapacity) {
 626       // The collector started out as empty.
 627       new_capacity = min_capacity * growth_factor;
 628       if (new_capacity < kMinCapacity) new_capacity = kMinCapacity;
 629     } else {
 630       int growth = current_length * (growth_factor - 1);
 631       if (growth > max_growth) {
 632         growth = max_growth;
 633       }
 634       new_capacity = current_length + growth;
 635       if (new_capacity < min_capacity) {
 636         new_capacity = min_capacity + growth;
 637       }
 638     }
 639     NewChunk(new_capacity);
 640     DCHECK(index_ + min_capacity <= current_chunk_.length());
 641   }
 642
 643   // Before replacing the current chunk, give a subclass the option to move
 644   // some of the current data into the new chunk. The function may update
 645   // the current index_ value to represent data no longer in the current chunk.
 646   // Returns the initial index of the new chunk (after copied data).
 647   virtual void NewChunk(int new_capacity)  {
 648     Vector<T> new_chunk = Vector<T>::New(new_capacity);
 649     if (index_ > 0) {
 650       chunks_.Add(current_chunk_.SubVector(0, index_));
 651     } else {
 652       current_chunk_.Dispose();
 653     }
 654     current_chunk_ = new_chunk;
 655     index_ = 0;
 656   }
 657 };
 658
 659
 660 /*
 661  * A collector that allows sequences of values to be guaranteed to
 662  * stay consecutive.
 663  * If the backing store grows while a sequence is active, the current
 664  * sequence might be moved, but after the sequence is ended, it will
 665  * not move again.
 666  * NOTICE: Blocks allocated using Collector::AddBlock(int) can move
 667  * as well, if inside an active sequence where another element is added.
 668  */
 669 template <typename T, int growth_factor = 2, int max_growth = 1 * MB>
 670 class SequenceCollector : public Collector<T, growth_factor, max_growth> {
 671  public:
 672   explicit SequenceCollector(int initial_capacity)
 673       : Collector<T, growth_factor, max_growth>(initial_capacity),
 674         sequence_start_(kNoSequence) { }
 675
 676   virtual ~SequenceCollector() {}
 677
 678   void StartSequence() {
 679     DCHECK(sequence_start_ == kNoSequence);
 680     sequence_start_ = this->index_;
 681   }
 682
 683   Vector<T> EndSequence() {
 684     DCHECK(sequence_start_ != kNoSequence);
 685     int sequence_start = sequence_start_;
 686     sequence_start_ = kNoSequence;
 687     if (sequence_start == this->index_) return Vector<T>();
 688     return this->current_chunk_.SubVector(sequence_start, this->index_);
 689   }
 690
 691   // Drops the currently added sequence, and all collected elements in it.
 692   void DropSequence() {
 693     DCHECK(sequence_start_ != kNoSequence);
 694     int sequence_length = this->index_ - sequence_start_;
 695     this->index_ = sequence_start_;
 696     this->size_ -= sequence_length;
 697     sequence_start_ = kNoSequence;
 698   }
 699
 700   virtual void Reset() {
 701     sequence_start_ = kNoSequence;
 702     this->Collector<T, growth_factor, max_growth>::Reset();
 703   }
 704
 705  private:
 706   static const int kNoSequence = -1;
 707   int sequence_start_;
 708
 709   // Move the currently active sequence to the new chunk.
 710   virtual void NewChunk(int new_capacity) {
 711     if (sequence_start_ == kNoSequence) {
 712       // Fall back on default behavior if no sequence has been started.
 713       this->Collector<T, growth_factor, max_growth>::NewChunk(new_capacity);
 714       return;
 715     }
 716     int sequence_length = this->index_ - sequence_start_;
 717     Vector<T> new_chunk = Vector<T>::New(sequence_length + new_capacity);
 718     DCHECK(sequence_length < new_chunk.length());
 719     for (int i = 0; i < sequence_length; i++) {
 720       new_chunk[i] = this->current_chunk_[sequence_start_ + i];
 721     }
 722     if (sequence_start_ > 0) {
 723       this->chunks_.Add(this->current_chunk_.SubVector(0, sequence_start_));
 724     } else {
 725       this->current_chunk_.Dispose();
 726     }
 727     this->current_chunk_ = new_chunk;
 728     this->index_ = sequence_length;
 729     sequence_start_ = 0;
 730   }
 731 };
 732
 733
 734 // Compare 8bit/16bit chars to 8bit/16bit chars.
 735 template <typename lchar, typename rchar>
 736 inline int CompareCharsUnsigned(const lchar* lhs, const rchar* rhs,
 737                                 size_t chars) {
 738   const lchar* limit = lhs + chars;
 739   if (sizeof(*lhs) == sizeof(char) && sizeof(*rhs) == sizeof(char)) {
 740     // memcmp compares byte-by-byte, yielding wrong results for two-byte
 741     // strings on little-endian systems.
 742     return memcmp(lhs, rhs, chars);
 743   }
 744   while (lhs < limit) {
 745     int r = static_cast<int>(*lhs) - static_cast<int>(*rhs);
 746     if (r != 0) return r;
 747     ++lhs;
 748     ++rhs;
 749   }
 750   return 0;
 751 }
 752
 753 template <typename lchar, typename rchar>
 754 inline int CompareChars(const lchar* lhs, const rchar* rhs, size_t chars) {
 755   DCHECK(sizeof(lchar) <= 2);
 756   DCHECK(sizeof(rchar) <= 2);
 757   if (sizeof(lchar) == 1) {
 758     if (sizeof(rchar) == 1) {
 759       return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
 760                                   reinterpret_cast<const uint8_t*>(rhs),
 761                                   chars);
 762     } else {
 763       return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
 764                                   reinterpret_cast<const uint16_t*>(rhs),
 765                                   chars);
 766     }
 767   } else {
 768     if (sizeof(rchar) == 1) {
 769       return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
 770                                   reinterpret_cast<const uint8_t*>(rhs),
 771                                   chars);
 772     } else {
 773       return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
 774                                   reinterpret_cast<const uint16_t*>(rhs),
 775                                   chars);
 776     }
 777   }
 778 }
 779
 780
 781 // Calculate 10^exponent.
 782 inline int TenToThe(int exponent) {
 783   DCHECK(exponent <= 9);
 784   DCHECK(exponent >= 1);
 785   int answer = 10;
 786   for (int i = 1; i < exponent; i++) answer *= 10;
 787   return answer;
 788 }
 789
 790
 791 template<typename ElementType, int NumElements>
 792 class EmbeddedContainer {
 793  public:
 794   EmbeddedContainer() : elems_() { }
 795
 796   int length() const { return NumElements; }
 797   const ElementType& operator[](int i) const {
 798     DCHECK(i < length());
 799     return elems_[i];
 800   }
 801   ElementType& operator[](int i) {
 802     DCHECK(i < length());
 803     return elems_[i];
 804   }
 805
 806  private:
 807   ElementType elems_[NumElements];
 808 };
 809
 810
 811 template<typename ElementType>
 812 class EmbeddedContainer<ElementType, 0> {
 813  public:
 814   int length() const { return 0; }
 815   const ElementType& operator[](int i) const {
 816     UNREACHABLE();
 817     static ElementType t = 0;
 818     return t;
 819   }
 820   ElementType& operator[](int i) {
 821     UNREACHABLE();
 822     static ElementType t = 0;
 823     return t;
 824   }
 825 };
 826
 827
 828 // Helper class for building result strings in a character buffer. The
 829 // purpose of the class is to use safe operations that checks the
 830 // buffer bounds on all operations in debug mode.
 831 // This simple base class does not allow formatted output.
 832 class SimpleStringBuilder {
 833  public:
 834   // Create a string builder with a buffer of the given size. The
 835   // buffer is allocated through NewArray<char> and must be
 836   // deallocated by the caller of Finalize().
 837   explicit SimpleStringBuilder(int size);
 838
 839   SimpleStringBuilder(char* buffer, int size)
 840       : buffer_(buffer, size), position_(0) { }
 841
 842   ~SimpleStringBuilder() { if (!is_finalized()) Finalize(); }
 843
 844   int size() const { return buffer_.length(); }
 845
 846   // Get the current position in the builder.
 847   int position() const {
 848     DCHECK(!is_finalized());
 849     return position_;
 850   }
 851
 852   // Reset the position.
 853   void Reset() { position_ = 0; }
 854
 855   // Add a single character to the builder. It is not allowed to add
 856   // 0-characters; use the Finalize() method to terminate the string
 857   // instead.
 858   void AddCharacter(char c) {
 859     DCHECK(c != '\0');
 860     DCHECK(!is_finalized() && position_ < buffer_.length());
 861     buffer_[position_++] = c;
 862   }
 863
 864   // Add an entire string to the builder. Uses strlen() internally to
 865   // compute the length of the input string.
 866   void AddString(const char* s);
 867
 868   // Add the first 'n' characters of the given 0-terminated string 's' to the
 869   // builder. The input string must have enough characters.
 870   void AddSubstring(const char* s, int n);
 871
 872   // Add character padding to the builder. If count is non-positive,
 873   // nothing is added to the builder.
 874   void AddPadding(char c, int count);
 875
 876   // Add the decimal representation of the value.
 877   void AddDecimalInteger(int value);
 878
 879   // Finalize the string by 0-terminating it and returning the buffer.
 880   char* Finalize();
 881
 882  protected:
 883   Vector<char> buffer_;
 884   int position_;
 885
 886   bool is_finalized() const { return position_ < 0; }
 887
 888  private:
 889   DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder);
 890 };
 891
 892
 893 // A poor man's version of STL's bitset: A bit set of enums E (without explicit
 894 // values), fitting into an integral type T.
 895 template <class E, class T = int>
 896 class EnumSet {
 897  public:
 898   explicit EnumSet(T bits = 0) : bits_(bits) {}
 899   bool IsEmpty() const { return bits_ == 0; }
 900   bool Contains(E element) const { return (bits_ & Mask(element)) != 0; }
 901   bool ContainsAnyOf(const EnumSet& set) const {
 902     return (bits_ & set.bits_) != 0;
 903   }
 904   void Add(E element) { bits_ |= Mask(element); }
 905   void Add(const EnumSet& set) { bits_ |= set.bits_; }
 906   void Remove(E element) { bits_ &= ~Mask(element); }
 907   void Remove(const EnumSet& set) { bits_ &= ~set.bits_; }
 908   void RemoveAll() { bits_ = 0; }
 909   void Intersect(const EnumSet& set) { bits_ &= set.bits_; }
 910   T ToIntegral() const { return bits_; }
 911   bool operator==(const EnumSet& set) { return bits_ == set.bits_; }
 912   bool operator!=(const EnumSet& set) { return bits_ != set.bits_; }
 913   EnumSet<E, T> operator|(const EnumSet& set) const {
 914     return EnumSet<E, T>(bits_ | set.bits_);
 915   }
 916
 917  private:
 918   T Mask(E element) const {
 919     // The strange typing in DCHECK is necessary to avoid stupid warnings, see:
 920     // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43680
 921     DCHECK(static_cast<int>(element) < static_cast<int>(sizeof(T) * CHAR_BIT));
 922     return static_cast<T>(1) << element;
 923   }
 924
 925   T bits_;
 926 };
 927
 928 // Bit field extraction.
 929 inline uint32_t unsigned_bitextract_32(int msb, int lsb, uint32_t x) {
 930   return (x >> lsb) & ((1 << (1 + msb - lsb)) - 1);
 931 }
 932
 933 inline uint64_t unsigned_bitextract_64(int msb, int lsb, uint64_t x) {
 934   return (x >> lsb) & ((static_cast<uint64_t>(1) << (1 + msb - lsb)) - 1);
 935 }
 936
 937 inline int32_t signed_bitextract_32(int msb, int lsb, int32_t x) {
 938   return (x << (31 - msb)) >> (lsb + 31 - msb);
 939 }
 940
 941 inline int signed_bitextract_64(int msb, int lsb, int x) {
 942   // TODO(jbramley): This is broken for big bitfields.
 943   return (x << (63 - msb)) >> (lsb + 63 - msb);
 944 }
 945
 946 // Check number width.
 947 inline bool is_intn(int64_t x, unsigned n) {
 948   DCHECK((0 < n) && (n < 64));
 949   int64_t limit = static_cast<int64_t>(1) << (n - 1);
 950   return (-limit <= x) && (x < limit);
 951 }
 952
 953 inline bool is_uintn(int64_t x, unsigned n) {
 954   DCHECK((0 < n) && (n < (sizeof(x) * kBitsPerByte)));
 955   return !(x >> n);
 956 }
 957
 958 template <class T>
 959 inline T truncate_to_intn(T x, unsigned n) {
 960   DCHECK((0 < n) && (n < (sizeof(x) * kBitsPerByte)));
 961   return (x & ((static_cast<T>(1) << n) - 1));
 962 }
 963
 964 #define INT_1_TO_63_LIST(V)                                                    \
 965 V(1)  V(2)  V(3)  V(4)  V(5)  V(6)  V(7)  V(8)                                 \
 966 V(9)  V(10) V(11) V(12) V(13) V(14) V(15) V(16)                                \
 967 V(17) V(18) V(19) V(20) V(21) V(22) V(23) V(24)                                \
 968 V(25) V(26) V(27) V(28) V(29) V(30) V(31) V(32)                                \
 969 V(33) V(34) V(35) V(36) V(37) V(38) V(39) V(40)                                \
 970 V(41) V(42) V(43) V(44) V(45) V(46) V(47) V(48)                                \
 971 V(49) V(50) V(51) V(52) V(53) V(54) V(55) V(56)                                \
 972 V(57) V(58) V(59) V(60) V(61) V(62) V(63)
 973
 974 #define DECLARE_IS_INT_N(N)                                                    \
 975 inline bool is_int##N(int64_t x) { return is_intn(x, N); }
 976 #define DECLARE_IS_UINT_N(N)                                                   \
 977 template <class T>                                                             \
 978 inline bool is_uint##N(T x) { return is_uintn(x, N); }
 979 #define DECLARE_TRUNCATE_TO_INT_N(N)                                           \
 980 template <class T>                                                             \
 981 inline T truncate_to_int##N(T x) { return truncate_to_intn(x, N); }
 982 INT_1_TO_63_LIST(DECLARE_IS_INT_N)
 983 INT_1_TO_63_LIST(DECLARE_IS_UINT_N)
 984 INT_1_TO_63_LIST(DECLARE_TRUNCATE_TO_INT_N)
 985 #undef DECLARE_IS_INT_N
 986 #undef DECLARE_IS_UINT_N
 987 #undef DECLARE_TRUNCATE_TO_INT_N
 988
 989 class TypeFeedbackId {
 990  public:
 991   explicit TypeFeedbackId(int id) : id_(id) { }
 992   int ToInt() const { return id_; }
 993
 994   static TypeFeedbackId None() { return TypeFeedbackId(kNoneId); }
 995   bool IsNone() const { return id_ == kNoneId; }
 996
 997  private:
 998   static const int kNoneId = -1;
 999
1000   int id_;
1001 };
1002
1003
1004 template <int dummy_parameter>
1005 class VectorSlot {
1006  public:
1007   explicit VectorSlot(int id) : id_(id) {}
1008   int ToInt() const { return id_; }
1009
1010   static VectorSlot Invalid() { return VectorSlot(kInvalidSlot); }
1011   bool IsInvalid() const { return id_ == kInvalidSlot; }
1012
1013   VectorSlot next() const {
1014     DCHECK(id_ != kInvalidSlot);
1015     return VectorSlot(id_ + 1);
1016   }
1017
1018   bool operator==(const VectorSlot& other) const { return id_ == other.id_; }
1019
1020  private:
1021   static const int kInvalidSlot = -1;
1022
1023   int id_;
1024 };
1025
1026
1027 typedef VectorSlot<0> FeedbackVectorSlot;
1028 typedef VectorSlot<1> FeedbackVectorICSlot;
1029
1030
1031 class BailoutId {
1032  public:
1033   explicit BailoutId(int id) : id_(id) { }
1034   int ToInt() const { return id_; }
1035
1036   static BailoutId None() { return BailoutId(kNoneId); }
1037   static BailoutId FunctionEntry() { return BailoutId(kFunctionEntryId); }
1038   static BailoutId Declarations() { return BailoutId(kDeclarationsId); }
1039   static BailoutId FirstUsable() { return BailoutId(kFirstUsableId); }
1040   static BailoutId StubEntry() { return BailoutId(kStubEntryId); }
1041
1042   bool IsNone() const { return id_ == kNoneId; }
1043   bool operator==(const BailoutId& other) const { return id_ == other.id_; }
1044   bool operator!=(const BailoutId& other) const { return id_ != other.id_; }
1045   friend size_t hash_value(BailoutId);
1046   friend std::ostream& operator<<(std::ostream&, BailoutId);
1047
1048  private:
1049   static const int kNoneId = -1;
1050
1051   // Using 0 could disguise errors.
1052   static const int kFunctionEntryId = 2;
1053
1054   // This AST id identifies the point after the declarations have been visited.
1055   // We need it to capture the environment effects of declarations that emit
1056   // code (function declarations).
1057   static const int kDeclarationsId = 3;
1058
1059   // Every FunctionState starts with this id.
1060   static const int kFirstUsableId = 4;
1061
1062   // Every compiled stub starts with this id.
1063   static const int kStubEntryId = 5;
1064
1065   int id_;
1066 };
1067
1068
1069 template <class C>
1070 class ContainerPointerWrapper {
1071  public:
1072   typedef typename C::iterator iterator;
1073   typedef typename C::reverse_iterator reverse_iterator;
1074   explicit ContainerPointerWrapper(C* container) : container_(container) {}
1075   iterator begin() { return container_->begin(); }
1076   iterator end() { return container_->end(); }
1077   reverse_iterator rbegin() { return container_->rbegin(); }
1078   reverse_iterator rend() { return container_->rend(); }
1079  private:
1080   C* container_;
1081 };
1082
1083
1084 // ----------------------------------------------------------------------------
1085 // I/O support.
1086
1087 #if __GNUC__ >= 4
1088 // On gcc we can ask the compiler to check the types of %d-style format
1089 // specifiers and their associated arguments.  TODO(erikcorry) fix this
1090 // so it works on MacOSX.
1091 #if defined(__MACH__) && defined(__APPLE__)
1092 #define PRINTF_CHECKING
1093 #define FPRINTF_CHECKING
1094 #define PRINTF_METHOD_CHECKING
1095 #define FPRINTF_METHOD_CHECKING
1096 #else  // MacOsX.
1097 #define PRINTF_CHECKING __attribute__ ((format (printf, 1, 2)))
1098 #define FPRINTF_CHECKING __attribute__ ((format (printf, 2, 3)))
1099 #define PRINTF_METHOD_CHECKING __attribute__ ((format (printf, 2, 3)))
1100 #define FPRINTF_METHOD_CHECKING __attribute__ ((format (printf, 3, 4)))
1101 #endif
1102 #else
1103 #define PRINTF_CHECKING
1104 #define FPRINTF_CHECKING
1105 #define PRINTF_METHOD_CHECKING
1106 #define FPRINTF_METHOD_CHECKING
1107 #endif
1108
1109 // Our version of printf().
1110 void PRINTF_CHECKING PrintF(const char* format, ...);
1111 void FPRINTF_CHECKING PrintF(FILE* out, const char* format, ...);
1112
1113 // Prepends the current process ID to the output.
1114 void PRINTF_CHECKING PrintPID(const char* format, ...);
1115
1116 // Safe formatting print. Ensures that str is always null-terminated.
1117 // Returns the number of chars written, or -1 if output was truncated.
1118 int FPRINTF_CHECKING SNPrintF(Vector<char> str, const char* format, ...);
1119 int VSNPrintF(Vector<char> str, const char* format, va_list args);
1120
1121 void StrNCpy(Vector<char> dest, const char* src, size_t n);
1122
1123 // Our version of fflush.
1124 void Flush(FILE* out);
1125
1126 inline void Flush() {
1127   Flush(stdout);
1128 }
1129
1130
1131 // Read a line of characters after printing the prompt to stdout. The resulting
1132 // char* needs to be disposed off with DeleteArray by the caller.
1133 char* ReadLine(const char* prompt);
1134
1135
1136 // Read and return the raw bytes in a file. the size of the buffer is returned
1137 // in size.
1138 // The returned buffer must be freed by the caller.
1139 byte* ReadBytes(const char* filename, int* size, bool verbose = true);
1140
1141
1142 // Append size chars from str to the file given by filename.
1143 // The file is overwritten. Returns the number of chars written.
1144 int AppendChars(const char* filename,
1145                 const char* str,
1146                 int size,
1147                 bool verbose = true);
1148
1149
1150 // Write size chars from str to the file given by filename.
1151 // The file is overwritten. Returns the number of chars written.
1152 int WriteChars(const char* filename,
1153                const char* str,
1154                int size,
1155                bool verbose = true);
1156
1157
1158 // Write size bytes to the file given by filename.
1159 // The file is overwritten. Returns the number of bytes written.
1160 int WriteBytes(const char* filename,
1161                const byte* bytes,
1162                int size,
1163                bool verbose = true);
1164
1165
1166 // Write the C code
1167 // const char* <varname> = "<str>";
1168 // const int <varname>_len = <len>;
1169 // to the file given by filename. Only the first len chars are written.
1170 int WriteAsCFile(const char* filename, const char* varname,
1171                  const char* str, int size, bool verbose = true);
1172
1173
1174 // ----------------------------------------------------------------------------
1175 // Data structures
1176
1177 template <typename T>
1178 inline Vector< Handle<Object> > HandleVector(v8::internal::Handle<T>* elms,
1179                                              int length) {
1180   return Vector< Handle<Object> >(
1181       reinterpret_cast<v8::internal::Handle<Object>*>(elms), length);
1182 }
1183
1184
1185 // ----------------------------------------------------------------------------
1186 // Memory
1187
1188 // Copies words from |src| to |dst|. The data spans must not overlap.
1189 template <typename T>
1190 inline void CopyWords(T* dst, const T* src, size_t num_words) {
1191   STATIC_ASSERT(sizeof(T) == kPointerSize);
1192   // TODO(mvstanton): disabled because mac builds are bogus failing on this
1193   // assert. They are doing a signed comparison. Investigate in
1194   // the morning.
1195   // DCHECK(Min(dst, const_cast<T*>(src)) + num_words <=
1196   //       Max(dst, const_cast<T*>(src)));
1197   DCHECK(num_words > 0);
1198
1199   // Use block copying MemCopy if the segment we're copying is
1200   // enough to justify the extra call/setup overhead.
1201   static const size_t kBlockCopyLimit = 16;
1202
1203   if (num_words < kBlockCopyLimit) {
1204     do {
1205       num_words--;
1206       *dst++ = *src++;
1207     } while (num_words > 0);
1208   } else {
1209     MemCopy(dst, src, num_words * kPointerSize);
1210   }
1211 }
1212
1213
1214 // Copies words from |src| to |dst|. No restrictions.
1215 template <typename T>
1216 inline void MoveWords(T* dst, const T* src, size_t num_words) {
1217   STATIC_ASSERT(sizeof(T) == kPointerSize);
1218   DCHECK(num_words > 0);
1219
1220   // Use block copying MemCopy if the segment we're copying is
1221   // enough to justify the extra call/setup overhead.
1222   static const size_t kBlockCopyLimit = 16;
1223
1224   if (num_words < kBlockCopyLimit &&
1225       ((dst < src) || (dst >= (src + num_words * kPointerSize)))) {
1226     T* end = dst + num_words;
1227     do {
1228       num_words--;
1229       *dst++ = *src++;
1230     } while (num_words > 0);
1231   } else {
1232     MemMove(dst, src, num_words * kPointerSize);
1233   }
1234 }
1235
1236
1237 // Copies data from |src| to |dst|.  The data spans must not overlap.
1238 template <typename T>
1239 inline void CopyBytes(T* dst, const T* src, size_t num_bytes) {
1240   STATIC_ASSERT(sizeof(T) == 1);
1241   DCHECK(Min(dst, const_cast<T*>(src)) + num_bytes <=
1242          Max(dst, const_cast<T*>(src)));
1243   if (num_bytes == 0) return;
1244
1245   // Use block copying MemCopy if the segment we're copying is
1246   // enough to justify the extra call/setup overhead.
1247   static const int kBlockCopyLimit = kMinComplexMemCopy;
1248
1249   if (num_bytes < static_cast<size_t>(kBlockCopyLimit)) {
1250     do {
1251       num_bytes--;
1252       *dst++ = *src++;
1253     } while (num_bytes > 0);
1254   } else {
1255     MemCopy(dst, src, num_bytes);
1256   }
1257 }
1258
1259
1260 template <typename T, typename U>
1261 inline void MemsetPointer(T** dest, U* value, int counter) {
1262 #ifdef DEBUG
1263   T* a = NULL;
1264   U* b = NULL;
1265   a = b;  // Fake assignment to check assignability.
1266   USE(a);
1267 #endif  // DEBUG
1268 #if V8_HOST_ARCH_IA32
1269 #define STOS "stosl"
1270 #elif V8_HOST_ARCH_X64
1271 #if V8_HOST_ARCH_32_BIT
1272 #define STOS "addr32 stosl"
1273 #else
1274 #define STOS "stosq"
1275 #endif
1276 #endif
1277 #if defined(__native_client__)
1278   // This STOS sequence does not validate for x86_64 Native Client.
1279   // Here we #undef STOS to force use of the slower C version.
1280   // TODO(bradchen): Profile V8 and implement a faster REP STOS
1281   // here if the profile indicates it matters.
1282 #undef STOS
1283 #endif
1284
1285 #if defined(MEMORY_SANITIZER)
1286   // MemorySanitizer does not understand inline assembly.
1287 #undef STOS
1288 #endif
1289
1290 #if defined(__GNUC__) && defined(STOS)
1291   asm volatile(
1292       "cld;"
1293       "rep ; " STOS
1294       : "+&c" (counter), "+&D" (dest)
1295       : "a" (value)
1296       : "memory", "cc");
1297 #else
1298   for (int i = 0; i < counter; i++) {
1299     dest[i] = value;
1300   }
1301 #endif
1302
1303 #undef STOS
1304 }
1305
1306
1307 // Simple support to read a file into a 0-terminated C-string.
1308 // The returned buffer must be freed by the caller.
1309 // On return, *exits tells whether the file existed.
1310 Vector<const char> ReadFile(const char* filename,
1311                             bool* exists,
1312                             bool verbose = true);
1313 Vector<const char> ReadFile(FILE* file,
1314                             bool* exists,
1315                             bool verbose = true);
1316
1317
1318 template <typename sourcechar, typename sinkchar>
1319 INLINE(static void CopyCharsUnsigned(sinkchar* dest, const sourcechar* src,
1320                                      size_t chars));
1321 #if defined(V8_HOST_ARCH_ARM)
1322 INLINE(void CopyCharsUnsigned(uint8_t* dest, const uint8_t* src, size_t chars));
1323 INLINE(void CopyCharsUnsigned(uint16_t* dest, const uint8_t* src,
1324                               size_t chars));
1325 INLINE(void CopyCharsUnsigned(uint16_t* dest, const uint16_t* src,
1326                               size_t chars));
1327 #elif defined(V8_HOST_ARCH_MIPS)
1328 INLINE(void CopyCharsUnsigned(uint8_t* dest, const uint8_t* src, size_t chars));
1329 INLINE(void CopyCharsUnsigned(uint16_t* dest, const uint16_t* src,
1330                               size_t chars));
1331 #elif defined(V8_HOST_ARCH_PPC)
1332 INLINE(void CopyCharsUnsigned(uint8_t* dest, const uint8_t* src, size_t chars));
1333 INLINE(void CopyCharsUnsigned(uint16_t* dest, const uint16_t* src,
1334                               size_t chars));
1335 #endif
1336
1337 // Copy from 8bit/16bit chars to 8bit/16bit chars.
1338 template <typename sourcechar, typename sinkchar>
1339 INLINE(void CopyChars(sinkchar* dest, const sourcechar* src, size_t chars));
1340
1341 template <typename sourcechar, typename sinkchar>
1342 void CopyChars(sinkchar* dest, const sourcechar* src, size_t chars) {
1343   DCHECK(sizeof(sourcechar) <= 2);
1344   DCHECK(sizeof(sinkchar) <= 2);
1345   if (sizeof(sinkchar) == 1) {
1346     if (sizeof(sourcechar) == 1) {
1347       CopyCharsUnsigned(reinterpret_cast<uint8_t*>(dest),
1348                         reinterpret_cast<const uint8_t*>(src),
1349                         chars);
1350     } else {
1351       CopyCharsUnsigned(reinterpret_cast<uint8_t*>(dest),
1352                         reinterpret_cast<const uint16_t*>(src),
1353                         chars);
1354     }
1355   } else {
1356     if (sizeof(sourcechar) == 1) {
1357       CopyCharsUnsigned(reinterpret_cast<uint16_t*>(dest),
1358                         reinterpret_cast<const uint8_t*>(src),
1359                         chars);
1360     } else {
1361       CopyCharsUnsigned(reinterpret_cast<uint16_t*>(dest),
1362                         reinterpret_cast<const uint16_t*>(src),
1363                         chars);
1364     }
1365   }
1366 }
1367
1368 template <typename sourcechar, typename sinkchar>
1369 void CopyCharsUnsigned(sinkchar* dest, const sourcechar* src, size_t chars) {
1370   sinkchar* limit = dest + chars;
1371   if ((sizeof(*dest) == sizeof(*src)) &&
1372       (chars >= static_cast<int>(kMinComplexMemCopy / sizeof(*dest)))) {
1373     MemCopy(dest, src, chars * sizeof(*dest));
1374   } else {
1375     while (dest < limit) *dest++ = static_cast<sinkchar>(*src++);
1376   }
1377 }
1378
1379
1380 #if defined(V8_HOST_ARCH_ARM)
1381 void CopyCharsUnsigned(uint8_t* dest, const uint8_t* src, size_t chars) {
1382   switch (static_cast<unsigned>(chars)) {
1383     case 0:
1384       break;
1385     case 1:
1386       *dest = *src;
1387       break;
1388     case 2:
1389       memcpy(dest, src, 2);
1390       break;
1391     case 3:
1392       memcpy(dest, src, 3);
1393       break;
1394     case 4:
1395       memcpy(dest, src, 4);
1396       break;
1397     case 5:
1398       memcpy(dest, src, 5);
1399       break;
1400     case 6:
1401       memcpy(dest, src, 6);
1402       break;
1403     case 7:
1404       memcpy(dest, src, 7);
1405       break;
1406     case 8:
1407       memcpy(dest, src, 8);
1408       break;
1409     case 9:
1410       memcpy(dest, src, 9);
1411       break;
1412     case 10:
1413       memcpy(dest, src, 10);
1414       break;
1415     case 11:
1416       memcpy(dest, src, 11);
1417       break;
1418     case 12:
1419       memcpy(dest, src, 12);
1420       break;
1421     case 13:
1422       memcpy(dest, src, 13);
1423       break;
1424     case 14:
1425       memcpy(dest, src, 14);
1426       break;
1427     case 15:
1428       memcpy(dest, src, 15);
1429       break;
1430     default:
1431       MemCopy(dest, src, chars);
1432       break;
1433   }
1434 }
1435
1436
1437 void CopyCharsUnsigned(uint16_t* dest, const uint8_t* src, size_t chars) {
1438   if (chars >= static_cast<size_t>(kMinComplexConvertMemCopy)) {
1439     MemCopyUint16Uint8(dest, src, chars);
1440   } else {
1441     MemCopyUint16Uint8Wrapper(dest, src, chars);
1442   }
1443 }
1444
1445
1446 void CopyCharsUnsigned(uint16_t* dest, const uint16_t* src, size_t chars) {
1447   switch (static_cast<unsigned>(chars)) {
1448     case 0:
1449       break;
1450     case 1:
1451       *dest = *src;
1452       break;
1453     case 2:
1454       memcpy(dest, src, 4);
1455       break;
1456     case 3:
1457       memcpy(dest, src, 6);
1458       break;
1459     case 4:
1460       memcpy(dest, src, 8);
1461       break;
1462     case 5:
1463       memcpy(dest, src, 10);
1464       break;
1465     case 6:
1466       memcpy(dest, src, 12);
1467       break;
1468     case 7:
1469       memcpy(dest, src, 14);
1470       break;
1471     default:
1472       MemCopy(dest, src, chars * sizeof(*dest));
1473       break;
1474   }
1475 }
1476
1477
1478 #elif defined(V8_HOST_ARCH_MIPS)
1479 void CopyCharsUnsigned(uint8_t* dest, const uint8_t* src, size_t chars) {
1480   if (chars < kMinComplexMemCopy) {
1481     memcpy(dest, src, chars);
1482   } else {
1483     MemCopy(dest, src, chars);
1484   }
1485 }
1486
1487 void CopyCharsUnsigned(uint16_t* dest, const uint16_t* src, size_t chars) {
1488   if (chars < kMinComplexMemCopy) {
1489     memcpy(dest, src, chars * sizeof(*dest));
1490   } else {
1491     MemCopy(dest, src, chars * sizeof(*dest));
1492   }
1493 }
1494 #elif defined(V8_HOST_ARCH_PPC)
1495 #define CASE(n)           \
1496   case n:                 \
1497     memcpy(dest, src, n); \
1498     break
1499 void CopyCharsUnsigned(uint8_t* dest, const uint8_t* src, size_t chars) {
1500   switch (static_cast<unsigned>(chars)) {
1501     case 0:
1502       break;
1503     case 1:
1504       *dest = *src;
1505       break;
1506       CASE(2);
1507       CASE(3);
1508       CASE(4);
1509       CASE(5);
1510       CASE(6);
1511       CASE(7);
1512       CASE(8);
1513       CASE(9);
1514       CASE(10);
1515       CASE(11);
1516       CASE(12);
1517       CASE(13);
1518       CASE(14);
1519       CASE(15);
1520       CASE(16);
1521       CASE(17);
1522       CASE(18);
1523       CASE(19);
1524       CASE(20);
1525       CASE(21);
1526       CASE(22);
1527       CASE(23);
1528       CASE(24);
1529       CASE(25);
1530       CASE(26);
1531       CASE(27);
1532       CASE(28);
1533       CASE(29);
1534       CASE(30);
1535       CASE(31);
1536       CASE(32);
1537       CASE(33);
1538       CASE(34);
1539       CASE(35);
1540       CASE(36);
1541       CASE(37);
1542       CASE(38);
1543       CASE(39);
1544       CASE(40);
1545       CASE(41);
1546       CASE(42);
1547       CASE(43);
1548       CASE(44);
1549       CASE(45);
1550       CASE(46);
1551       CASE(47);
1552       CASE(48);
1553       CASE(49);
1554       CASE(50);
1555       CASE(51);
1556       CASE(52);
1557       CASE(53);
1558       CASE(54);
1559       CASE(55);
1560       CASE(56);
1561       CASE(57);
1562       CASE(58);
1563       CASE(59);
1564       CASE(60);
1565       CASE(61);
1566       CASE(62);
1567       CASE(63);
1568       CASE(64);
1569     default:
1570       memcpy(dest, src, chars);
1571       break;
1572   }
1573 }
1574 #undef CASE
1575
1576 #define CASE(n)               \
1577   case n:                     \
1578     memcpy(dest, src, n * 2); \
1579     break
1580 void CopyCharsUnsigned(uint16_t* dest, const uint16_t* src, size_t chars) {
1581   switch (static_cast<unsigned>(chars)) {
1582     case 0:
1583       break;
1584     case 1:
1585       *dest = *src;
1586       break;
1587       CASE(2);
1588       CASE(3);
1589       CASE(4);
1590       CASE(5);
1591       CASE(6);
1592       CASE(7);
1593       CASE(8);
1594       CASE(9);
1595       CASE(10);
1596       CASE(11);
1597       CASE(12);
1598       CASE(13);
1599       CASE(14);
1600       CASE(15);
1601       CASE(16);
1602       CASE(17);
1603       CASE(18);
1604       CASE(19);
1605       CASE(20);
1606       CASE(21);
1607       CASE(22);
1608       CASE(23);
1609       CASE(24);
1610       CASE(25);
1611       CASE(26);
1612       CASE(27);
1613       CASE(28);
1614       CASE(29);
1615       CASE(30);
1616       CASE(31);
1617       CASE(32);
1618     default:
1619       memcpy(dest, src, chars * 2);
1620       break;
1621   }
1622 }
1623 #undef CASE
1624 #endif
1625
1626
1627 class StringBuilder : public SimpleStringBuilder {
1628  public:
1629   explicit StringBuilder(int size) : SimpleStringBuilder(size) { }
1630   StringBuilder(char* buffer, int size) : SimpleStringBuilder(buffer, size) { }
1631
1632   // Add formatted contents to the builder just like printf().
1633   void AddFormatted(const char* format, ...);
1634
1635   // Add formatted contents like printf based on a va_list.
1636   void AddFormattedList(const char* format, va_list list);
1637  private:
1638   DISALLOW_IMPLICIT_CONSTRUCTORS(StringBuilder);
1639 };
1640
1641
1642 bool DoubleToBoolean(double d);
1643
1644 template <typename Stream>
1645 bool StringToArrayIndex(Stream* stream, uint32_t* index) {
1646   uint16_t ch = stream->GetNext();
1647
1648   // If the string begins with a '0' character, it must only consist
1649   // of it to be a legal array index.
1650   if (ch == '0') {
1651     *index = 0;
1652     return !stream->HasMore();
1653   }
1654
1655   // Convert string to uint32 array index; character by character.
1656   int d = ch - '0';
1657   if (d < 0 || d > 9) return false;
1658   uint32_t result = d;
1659   while (stream->HasMore()) {
1660     d = stream->GetNext() - '0';
1661     if (d < 0 || d > 9) return false;
1662     // Check that the new result is below the 32 bit limit.
1663     if (result > 429496729U - ((d > 5) ? 1 : 0)) return false;
1664     result = (result * 10) + d;
1665   }
1666
1667   *index = result;
1668   return true;
1669 }
1670
1671
1672 // Returns current value of top of the stack. Works correctly with ASAN.
1673 DISABLE_ASAN
1674 inline uintptr_t GetCurrentStackPosition() {
1675   // Takes the address of the limit variable in order to find out where
1676   // the top of stack is right now.
1677   uintptr_t limit = reinterpret_cast<uintptr_t>(&limit);
1678   return limit;
1679 }
1680
1681 }  // namespace internal
1682 }  // namespace v8
1683
1684 #endif  // V8_UTILS_H_