utils.h 34.3 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4 5 6 7

#ifndef V8_UTILS_H_
#define V8_UTILS_H_

8
#include <limits.h>
9
#include <stdlib.h>
10
#include <string.h>
11
#include <cmath>
12
#include <string>
13
#include <type_traits>
14

15
#include "include/v8.h"
16
#include "src/allocation.h"
17
#include "src/base/bits.h"
jfb's avatar
jfb committed
18
#include "src/base/compiler-specific.h"
19
#include "src/base/logging.h"
20
#include "src/base/macros.h"
21
#include "src/base/platform/platform.h"
22
#include "src/base/v8-fallthrough.h"
23
#include "src/globals.h"
24
#include "src/third_party/siphash/halfsiphash.h"
25
#include "src/vector.h"
26

27 28 29 30
#if defined(V8_OS_AIX)
#include <fenv.h>  // NOLINT(build/c++11)
#endif

31 32
namespace v8 {
namespace internal {
33 34 35 36

// ----------------------------------------------------------------------------
// General helper functions

37 38 39 40 41 42 43 44 45 46
// Returns the value (0 .. 15) of a hexadecimal character c.
// If c is not a legal hexadecimal character, returns a value < 0.
inline int HexValue(uc32 c) {
  c -= '0';
  if (static_cast<unsigned>(c) <= 9) return c;
  c = (c | 0x20) - ('a' - '0');  // detect 0x11..0x16 and 0x31..0x36.
  if (static_cast<unsigned>(c) <= 5) return c + 10;
  return -1;
}

47 48 49 50 51
inline char HexCharOfValue(int value) {
  DCHECK(0 <= value && value <= 16);
  if (value < 10) return value + '0';
  return value - 10 + 'A';
}
52

53 54
inline int BoolToInt(bool b) { return b ? 1 : 0; }

55 56
// Checks if value is in range [lower_limit, higher_limit] using a single
// branch.
57
template <typename T, typename U>
58 59 60 61
inline constexpr bool IsInRange(T value, U lower_limit, U higher_limit) {
#if V8_CAN_HAVE_DCHECK_IN_CONSTEXPR
  DCHECK(lower_limit <= higher_limit);
#endif
62 63
  STATIC_ASSERT(sizeof(U) <= sizeof(T));
  typedef typename std::make_unsigned<T>::type unsigned_T;
64 65 66 67 68
  // Use static_cast to support enum classes.
  return static_cast<unsigned_T>(static_cast<unsigned_T>(value) -
                                 static_cast<unsigned_T>(lower_limit)) <=
         static_cast<unsigned_T>(static_cast<unsigned_T>(higher_limit) -
                                 static_cast<unsigned_T>(lower_limit));
69 70
}

71 72 73 74 75 76
// Checks if [index, index+length) is in range [0, max). Note that this check
// works even if {index+length} would wrap around.
inline constexpr bool IsInBounds(size_t index, size_t length, size_t max) {
  return length <= max && index <= (max - length);
}

77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
// Checks if [index, index+length) is in range [0, max). If not, {length} is
// clamped to its valid range. Note that this check works even if
// {index+length} would wrap around.
template <typename T>
inline bool ClampToBounds(T index, T* length, T max) {
  if (index > max) {
    *length = 0;
    return false;
  }
  T avail = max - index;
  bool oob = *length > avail;
  if (oob) *length = avail;
  return !oob;
}

92
// X must be a power of 2.  Returns the number of trailing zeros.
93 94 95
template <typename T,
          typename = typename std::enable_if<std::is_integral<T>::value>::type>
inline int WhichPowerOf2(T x) {
96
  DCHECK(base::bits::IsPowerOfTwo(x));
97 98
  int bits = 0;
#ifdef DEBUG
99
  const T original_x = x;
100
#endif
101 102 103 104 105 106 107
  constexpr int max_bits = sizeof(T) * 8;
  static_assert(max_bits <= 64, "integral types are not bigger than 64 bits");
// Avoid shifting by more than the bit width of x to avoid compiler warnings.
#define CHECK_BIGGER(s)                                      \
  if (max_bits > s && x >= T{1} << (max_bits > s ? s : 0)) { \
    bits += s;                                               \
    x >>= max_bits > s ? s : 0;                              \
108
  }
109 110 111 112 113
  CHECK_BIGGER(32)
  CHECK_BIGGER(16)
  CHECK_BIGGER(8)
  CHECK_BIGGER(4)
#undef CHECK_BIGGER
114 115
  switch (x) {
    default: UNREACHABLE();
116 117 118 119 120 121 122 123 124
    case 8:
      bits++;
      V8_FALLTHROUGH;
    case 4:
      bits++;
      V8_FALLTHROUGH;
    case 2:
      bits++;
      V8_FALLTHROUGH;
125 126
    case 1: break;
  }
127
  DCHECK_EQ(T{1} << bits, original_x);
128 129 130
  return bits;
}

131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
inline int MostSignificantBit(uint32_t x) {
  static const int msb4[] = {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4};
  int nibble = 0;
  if (x & 0xffff0000) {
    nibble += 16;
    x >>= 16;
  }
  if (x & 0xff00) {
    nibble += 8;
    x >>= 8;
  }
  if (x & 0xf0) {
    nibble += 4;
    x >>= 4;
  }
  return nibble + msb4[x];
}

149 150 151 152 153 154 155 156 157 158 159 160
template <typename T>
static T ArithmeticShiftRight(T x, int shift) {
  DCHECK_LE(0, shift);
  if (x < 0) {
    // Right shift of signed values is implementation defined. Simulate a
    // true arithmetic right shift by adding leading sign bits.
    using UnsignedT = typename std::make_unsigned<T>::type;
    UnsignedT mask = ~(static_cast<UnsignedT>(~0) >> shift);
    return (static_cast<UnsignedT>(x) >> shift) | mask;
  } else {
    return x >> shift;
  }
161 162
}

163
template <typename T>
164
int Compare(const T& a, const T& b) {
165 166 167 168 169 170 171 172
  if (a == b)
    return 0;
  else if (a < b)
    return -1;
  else
    return 1;
}

173 174 175 176 177
// Compare function to compare the object pointer value of two
// handlified objects. The handles are passed as pointers to the
// handles.
template<typename T> class Handle;  // Forward declaration.
template <typename T>
178
int HandleObjectPointerCompare(const Handle<T>* a, const Handle<T>* b) {
179 180 181
  return Compare<T*>(*(*a), *(*b));
}

182 183
// Returns the maximum of the two parameters.
template <typename T>
184
constexpr T Max(T a, T b) {
185 186 187 188 189 190
  return a < b ? b : a;
}


// Returns the minimum of the two parameters.
template <typename T>
191
constexpr T Min(T a, T b) {
192 193 194
  return a < b ? a : b;
}

195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211
// Returns the maximum of the two parameters according to JavaScript semantics.
template <typename T>
T JSMax(T x, T y) {
  if (std::isnan(x)) return x;
  if (std::isnan(y)) return y;
  if (std::signbit(x) < std::signbit(y)) return x;
  return x > y ? x : y;
}

// Returns the maximum of the two parameters according to JavaScript semantics.
template <typename T>
T JSMin(T x, T y) {
  if (std::isnan(x)) return x;
  if (std::isnan(y)) return y;
  if (std::signbit(x) < std::signbit(y)) return y;
  return x > y ? y : x;
}
212

213
// Returns the absolute value of its argument.
214
template <typename T,
215
          typename = typename std::enable_if<std::is_signed<T>::value>::type>
216
typename std::make_unsigned<T>::type Abs(T a) {
217 218 219 220 221 222 223
  // This is a branch-free implementation of the absolute value function and is
  // described in Warren's "Hacker's Delight", chapter 2. It avoids undefined
  // behavior with the arithmetic negation operation on signed values as well.
  typedef typename std::make_unsigned<T>::type unsignedT;
  unsignedT x = static_cast<unsignedT>(a);
  unsignedT y = static_cast<unsignedT>(a >> (sizeof(T) * 8 - 1));
  return (x ^ y) - y;
224 225
}

226 227 228 229 230 231 232
// Returns the negative absolute value of its argument.
template <typename T,
          typename = typename std::enable_if<std::is_signed<T>::value>::type>
T Nabs(T a) {
  return a < 0 ? a : -a;
}

233 234 235 236 237 238 239
inline double Modulo(double x, double y) {
#if defined(V8_OS_WIN)
  // Workaround MS fmod bugs. ECMA-262 says:
  // dividend is finite and divisor is an infinity => result equals dividend
  // dividend is a zero and divisor is nonzero finite => result equals dividend
  if (!(std::isfinite(x) && (!std::isfinite(y) && !std::isnan(y))) &&
      !(x == 0 && (y != 0 && std::isfinite(y)))) {
240 241 242 243 244
    double result = fmod(x, y);
    // Workaround MS bug in VS CRT in some OS versions, https://crbug.com/915045
    // fmod(-17, +/-1) should equal -0.0 but now returns 0.0.
    if (x < 0 && result == 0) result = -0.0;
    x = result;
245 246 247 248 249 250 251 252 253 254 255 256 257
  }
  return x;
#elif defined(V8_OS_AIX)
  // AIX raises an underflow exception for (Number.MIN_VALUE % Number.MAX_VALUE)
  feclearexcept(FE_ALL_EXCEPT);
  double result = std::fmod(x, y);
  int exception = fetestexcept(FE_UNDERFLOW);
  return (exception ? x : result);
#else
  return std::fmod(x, y);
#endif
}

258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281
template <typename T>
T SaturateAdd(T a, T b) {
  if (std::is_signed<T>::value) {
    if (a > 0 && b > 0) {
      if (a > std::numeric_limits<T>::max() - b) {
        return std::numeric_limits<T>::max();
      }
    } else if (a < 0 && b < 0) {
      if (a < std::numeric_limits<T>::min() - b) {
        return std::numeric_limits<T>::min();
      }
    }
  } else {
    CHECK(std::is_unsigned<T>::value);
    if (a > std::numeric_limits<T>::max() - b) {
      return std::numeric_limits<T>::max();
    }
  }
  return a + b;
}

template <typename T>
T SaturateSub(T a, T b) {
  if (std::is_signed<T>::value) {
282
    if (a >= 0 && b < 0) {
283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298
      if (a > std::numeric_limits<T>::max() + b) {
        return std::numeric_limits<T>::max();
      }
    } else if (a < 0 && b > 0) {
      if (a < std::numeric_limits<T>::min() + b) {
        return std::numeric_limits<T>::min();
      }
    }
  } else {
    CHECK(std::is_unsigned<T>::value);
    if (a < b) {
      return static_cast<T>(0);
    }
  }
  return a - b;
}
299

300
// ----------------------------------------------------------------------------
301 302
// BitField is a help template for encoding and decode bitfield with
// unsigned content.
303 304 305

template<class T, int shift, int size, class U>
class BitFieldBase {
306
 public:
307 308
  typedef T FieldType;

309 310 311 312 313 314 315
  // A type U mask of bit field.  To use all bits of a type U of x bits
  // in a bitfield without compiler warnings we have to compute 2^x
  // without using a shift count of x in the computation.
  static const U kOne = static_cast<U>(1U);
  static const U kMask = ((kOne << shift) << size) - (kOne << shift);
  static const U kShift = shift;
  static const U kSize = size;
316
  static const U kNext = kShift + kSize;
317
  static const U kNumValues = kOne << size;
318 319

  // Value for the field with all bits set.
320
  static const T kMax = static_cast<T>(kNumValues - 1);
321

322
  // Tells whether the provided value fits into the bit field.
323
  static constexpr bool is_valid(T value) {
324
    return (static_cast<U>(value) & ~static_cast<U>(kMax)) == 0;
325 326
  }

327
  // Returns a type U with the bit field value encoded.
328 329
  static constexpr U encode(T value) {
#if V8_CAN_HAVE_DCHECK_IN_CONSTEXPR
330
    DCHECK(is_valid(value));
331
#endif
332
    return static_cast<U>(value) << shift;
333 334
  }

335
  // Returns a type U with the bit field value updated.
336
  static constexpr U update(U previous, T value) {
337
    return (previous & ~kMask) | encode(value);
338 339
  }

340
  // Extracts the bit field from the value.
341
  static constexpr T decode(U value) {
342
    return static_cast<T>((value & kMask) >> shift);
343
  }
344

345 346
  STATIC_ASSERT((kNext - 1) / 8 < sizeof(U));
};
347

348 349 350 351 352 353 354 355
template <class T, int shift, int size>
class BitField8 : public BitFieldBase<T, shift, size, uint8_t> {};


template <class T, int shift, int size>
class BitField16 : public BitFieldBase<T, shift, size, uint16_t> {};


356 357 358 359 360 361 362
template<class T, int shift, int size>
class BitField : public BitFieldBase<T, shift, size, uint32_t> { };


template<class T, int shift, int size>
class BitField64 : public BitFieldBase<T, shift, size, uint64_t> { };

363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379
// Helper macros for defining a contiguous sequence of bit fields. Example:
// (backslashes at the ends of respective lines of this multi-line macro
// definition are omitted here to please the compiler)
//
// #define MAP_BIT_FIELD1(V, _)
//   V(IsAbcBit, bool, 1, _)
//   V(IsBcdBit, bool, 1, _)
//   V(CdeBits, int, 5, _)
//   V(DefBits, MutableMode, 1, _)
//
// DEFINE_BIT_FIELDS(MAP_BIT_FIELD1)
// or
// DEFINE_BIT_FIELDS_64(MAP_BIT_FIELD1)
//
#define DEFINE_BIT_FIELD_RANGE_TYPE(Name, Type, Size, _) \
  k##Name##Start, k##Name##End = k##Name##Start + Size - 1,

380 381 382
#define DEFINE_BIT_RANGES(LIST_MACRO)                               \
  struct LIST_MACRO##_Ranges {                                      \
    enum { LIST_MACRO(DEFINE_BIT_FIELD_RANGE_TYPE, _) kBitsCount }; \
383 384 385 386 387 388 389 390 391
  };

#define DEFINE_BIT_FIELD_TYPE(Name, Type, Size, RangesName) \
  typedef BitField<Type, RangesName::k##Name##Start, Size> Name;

#define DEFINE_BIT_FIELD_64_TYPE(Name, Type, Size, RangesName) \
  typedef BitField64<Type, RangesName::k##Name##Start, Size> Name;

#define DEFINE_BIT_FIELDS(LIST_MACRO) \
392
  DEFINE_BIT_RANGES(LIST_MACRO)       \
393 394 395
  LIST_MACRO(DEFINE_BIT_FIELD_TYPE, LIST_MACRO##_Ranges)

#define DEFINE_BIT_FIELDS_64(LIST_MACRO) \
396
  DEFINE_BIT_RANGES(LIST_MACRO)          \
397
  LIST_MACRO(DEFINE_BIT_FIELD_64_TYPE, LIST_MACRO##_Ranges)
398

399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437
// ----------------------------------------------------------------------------
// BitSetComputer is a help template for encoding and decoding information for
// a variable number of items in an array.
//
// To encode boolean data in a smi array you would use:
// typedef BitSetComputer<bool, 1, kSmiValueSize, uint32_t> BoolComputer;
//
template <class T, int kBitsPerItem, int kBitsPerWord, class U>
class BitSetComputer {
 public:
  static const int kItemsPerWord = kBitsPerWord / kBitsPerItem;
  static const int kMask = (1 << kBitsPerItem) - 1;

  // The number of array elements required to embed T information for each item.
  static int word_count(int items) {
    if (items == 0) return 0;
    return (items - 1) / kItemsPerWord + 1;
  }

  // The array index to look at for item.
  static int index(int base_index, int item) {
    return base_index + item / kItemsPerWord;
  }

  // Extract T data for a given item from data.
  static T decode(U data, int item) {
    return static_cast<T>((data >> shift(item)) & kMask);
  }

  // Return the encoding for a store of value for item in previous.
  static U encode(U previous, int item, T value) {
    int shift_value = shift(item);
    int set_bits = (static_cast<int>(value) << shift_value);
    return (previous & ~(kMask << shift_value)) | set_bits;
  }

  static int shift(int item) { return (item % kItemsPerWord) * kBitsPerItem; }
};

438 439 440 441 442
// Helper macros for defining a contiguous sequence of field offset constants.
// Example: (backslashes at the ends of respective lines of this multi-line
// macro definition are omitted here to please the compiler)
//
// #define MAP_FIELDS(V)
443
//   V(kField1Offset, kTaggedSize)
444 445
//   V(kField2Offset, kIntSize)
//   V(kField3Offset, kIntSize)
446
//   V(kField4Offset, kSystemPointerSize)
447 448 449 450
//   V(kSize, 0)
//
// DEFINE_FIELD_OFFSET_CONSTANTS(HeapObject::kHeaderSize, MAP_FIELDS)
//
451
#define DEFINE_ONE_FIELD_OFFSET(Name, Size) Name, Name##End = Name + (Size)-1,
452 453 454 455 456 457

#define DEFINE_FIELD_OFFSET_CONSTANTS(StartOffset, LIST_MACRO) \
  enum {                                                       \
    LIST_MACRO##_StartOffset = StartOffset - 1,                \
    LIST_MACRO(DEFINE_ONE_FIELD_OFFSET)                        \
  };
458

459 460 461
// Size of the field defined by DEFINE_FIELD_OFFSET_CONSTANTS
#define FIELD_SIZE(Name) (Name##End + 1 - Name)

462 463 464
// ----------------------------------------------------------------------------
// Hash function.

Yang Guo's avatar
Yang Guo committed
465
static const uint64_t kZeroHashSeed = 0;
466

467
// Thomas Wang, Integer Hash Functions.
468 469
// http://www.concentric.net/~Ttwang/tech/inthash.htm`
inline uint32_t ComputeUnseededHash(uint32_t key) {
470 471 472 473 474 475 476
  uint32_t hash = key;
  hash = ~hash + (hash << 15);  // hash = (hash << 15) - hash - 1;
  hash = hash ^ (hash >> 12);
  hash = hash + (hash << 2);
  hash = hash ^ (hash >> 4);
  hash = hash * 2057;  // hash = (hash + (hash << 3)) + (hash << 11);
  hash = hash ^ (hash >> 16);
477
  return hash & 0x3fffffff;
478
}
479

480
inline uint32_t ComputeLongHash(uint64_t key) {
481 482 483 484 485 486 487
  uint64_t hash = key;
  hash = ~hash + (hash << 18);  // hash = (hash << 18) - hash - 1;
  hash = hash ^ (hash >> 31);
  hash = hash * 21;  // hash = (hash + (hash << 2)) + (hash << 4);
  hash = hash ^ (hash >> 11);
  hash = hash + (hash << 6);
  hash = hash ^ (hash >> 22);
488
  return static_cast<uint32_t>(hash & 0x3fffffff);
489 490
}

491
inline uint32_t ComputeSeededHash(uint32_t key, uint64_t seed) {
492 493 494
#ifdef V8_USE_SIPHASH
  return halfsiphash(key, seed);
#else
495
  return ComputeLongHash(static_cast<uint64_t>(key) ^ seed);
496
#endif  // V8_USE_SIPHASH
497
}
498

499
inline uint32_t ComputePointerHash(void* ptr) {
500
  return ComputeUnseededHash(
501
      static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr)));
502 503
}

504
inline uint32_t ComputeAddressHash(Address address) {
505
  return ComputeUnseededHash(static_cast<uint32_t>(address & 0xFFFFFFFFul));
506
}
507

508 509 510
// ----------------------------------------------------------------------------
// Miscellaneous

511 512 513 514 515 516 517 518 519
// Memory offset for lower and higher bits in a 64 bit integer.
#if defined(V8_TARGET_LITTLE_ENDIAN)
static const int kInt64LowerHalfMemoryOffset = 0;
static const int kInt64UpperHalfMemoryOffset = 4;
#elif defined(V8_TARGET_BIG_ENDIAN)
static const int kInt64LowerHalfMemoryOffset = 4;
static const int kInt64UpperHalfMemoryOffset = 0;
#endif  // V8_TARGET_LITTLE_ENDIAN

520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541
// A static resource holds a static instance that can be reserved in
// a local scope using an instance of Access.  Attempts to re-reserve
// the instance will cause an error.
template <typename T>
class StaticResource {
 public:
  StaticResource() : is_reserved_(false)  {}

 private:
  template <typename S> friend class Access;
  T instance_;
  bool is_reserved_;
};


// Locally scoped access to a static resource.
template <typename T>
class Access {
 public:
  explicit Access(StaticResource<T>* resource)
    : resource_(resource)
    , instance_(&resource->instance_) {
542
    DCHECK(!resource->is_reserved_);
543 544 545 546 547
    resource->is_reserved_ = true;
  }

  ~Access() {
    resource_->is_reserved_ = false;
548 549
    resource_ = nullptr;
    instance_ = nullptr;
550 551 552 553 554 555 556 557 558 559
  }

  T* value()  { return instance_; }
  T* operator -> ()  { return instance_; }

 private:
  StaticResource<T>* resource_;
  T* instance_;
};

560 561 562 563
// A pointer that can only be set once and doesn't allow NULL values.
template<typename T>
class SetOncePointer {
 public:
564
  SetOncePointer() = default;
565

566
  bool is_set() const { return pointer_ != nullptr; }
567 568

  T* get() const {
569
    DCHECK_NOT_NULL(pointer_);
570 571 572 573
    return pointer_;
  }

  void set(T* value) {
574
    DCHECK(pointer_ == nullptr && value != nullptr);
575 576 577
    pointer_ = value;
  }

578 579 580 581 582 583 584 585
  T* operator=(T* value) {
    set(value);
    return value;
  }

  bool operator==(std::nullptr_t) const { return pointer_ == nullptr; }
  bool operator!=(std::nullptr_t) const { return pointer_ != nullptr; }

586
 private:
587
  T* pointer_ = nullptr;
588 589
};

590
// Compare 8bit/16bit chars to 8bit/16bit chars.
591
template <typename lchar, typename rchar>
592 593
inline int CompareCharsUnsigned(const lchar* lhs, const rchar* rhs,
                                size_t chars) {
594
  const lchar* limit = lhs + chars;
595 596 597 598
  if (sizeof(*lhs) == sizeof(char) && sizeof(*rhs) == sizeof(char)) {
    // memcmp compares byte-by-byte, yielding wrong results for two-byte
    // strings on little-endian systems.
    return memcmp(lhs, rhs, chars);
599 600 601 602 603 604 605 606 607 608
  }
  while (lhs < limit) {
    int r = static_cast<int>(*lhs) - static_cast<int>(*rhs);
    if (r != 0) return r;
    ++lhs;
    ++rhs;
  }
  return 0;
}

609 610
template <typename lchar, typename rchar>
inline int CompareChars(const lchar* lhs, const rchar* rhs, size_t chars) {
611 612
  DCHECK_LE(sizeof(lchar), 2);
  DCHECK_LE(sizeof(rchar), 2);
613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635
  if (sizeof(lchar) == 1) {
    if (sizeof(rchar) == 1) {
      return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
                                  reinterpret_cast<const uint8_t*>(rhs),
                                  chars);
    } else {
      return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
                                  reinterpret_cast<const uint16_t*>(rhs),
                                  chars);
    }
  } else {
    if (sizeof(rchar) == 1) {
      return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
                                  reinterpret_cast<const uint8_t*>(rhs),
                                  chars);
    } else {
      return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
                                  reinterpret_cast<const uint16_t*>(rhs),
                                  chars);
    }
  }
}

636

637
// Calculate 10^exponent.
638
inline int TenToThe(int exponent) {
639 640
  DCHECK_LE(exponent, 9);
  DCHECK_GE(exponent, 1);
641 642 643 644
  int answer = 10;
  for (int i = 1; i < exponent; i++) answer *= 10;
  return answer;
}
645

646

647 648 649 650 651
template<typename ElementType, int NumElements>
class EmbeddedContainer {
 public:
  EmbeddedContainer() : elems_() { }

652 653
  int length() const { return NumElements; }
  const ElementType& operator[](int i) const {
654
    DCHECK(i < length());
655 656
    return elems_[i];
  }
657
  ElementType& operator[](int i) {
658
    DCHECK(i < length());
659 660 661 662 663 664 665 666 667 668 669
    return elems_[i];
  }

 private:
  ElementType elems_[NumElements];
};


template<typename ElementType>
class EmbeddedContainer<ElementType, 0> {
 public:
670 671 672 673 674 675
  int length() const { return 0; }
  const ElementType& operator[](int i) const {
    UNREACHABLE();
    static ElementType t = 0;
    return t;
  }
676 677 678 679 680 681 682 683
  ElementType& operator[](int i) {
    UNREACHABLE();
    static ElementType t = 0;
    return t;
  }
};


684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703
// Helper class for building result strings in a character buffer. The
// purpose of the class is to use safe operations that checks the
// buffer bounds on all operations in debug mode.
// This simple base class does not allow formatted output.
class SimpleStringBuilder {
 public:
  // Create a string builder with a buffer of the given size. The
  // buffer is allocated through NewArray<char> and must be
  // deallocated by the caller of Finalize().
  explicit SimpleStringBuilder(int size);

  SimpleStringBuilder(char* buffer, int size)
      : buffer_(buffer, size), position_(0) { }

  ~SimpleStringBuilder() { if (!is_finalized()) Finalize(); }

  int size() const { return buffer_.length(); }

  // Get the current position in the builder.
  int position() const {
704
    DCHECK(!is_finalized());
705 706 707 708 709 710 711 712 713 714
    return position_;
  }

  // Reset the position.
  void Reset() { position_ = 0; }

  // Add a single character to the builder. It is not allowed to add
  // 0-characters; use the Finalize() method to terminate the string
  // instead.
  void AddCharacter(char c) {
715
    DCHECK_NE(c, '\0');
716
    DCHECK(!is_finalized() && position_ < buffer_.length());
717 718 719 720 721 722 723
    buffer_[position_++] = c;
  }

  // Add an entire string to the builder. Uses strlen() internally to
  // compute the length of the input string.
  void AddString(const char* s);

724
  // Add the first 'n' characters of the given 0-terminated string 's' to the
725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742
  // builder. The input string must have enough characters.
  void AddSubstring(const char* s, int n);

  // Add character padding to the builder. If count is non-positive,
  // nothing is added to the builder.
  void AddPadding(char c, int count);

  // Add the decimal representation of the value.
  void AddDecimalInteger(int value);

  // Finalize the string by 0-terminating it and returning the buffer.
  char* Finalize();

 protected:
  Vector<char> buffer_;
  int position_;

  bool is_finalized() const { return position_ < 0; }
743

744 745 746 747
 private:
  DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder);
};

748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767
// Bit field extraction.
inline uint32_t unsigned_bitextract_32(int msb, int lsb, uint32_t x) {
  return (x >> lsb) & ((1 << (1 + msb - lsb)) - 1);
}

inline uint64_t unsigned_bitextract_64(int msb, int lsb, uint64_t x) {
  return (x >> lsb) & ((static_cast<uint64_t>(1) << (1 + msb - lsb)) - 1);
}

inline int32_t signed_bitextract_32(int msb, int lsb, int32_t x) {
  return (x << (31 - msb)) >> (lsb + 31 - msb);
}

inline int signed_bitextract_64(int msb, int lsb, int x) {
  // TODO(jbramley): This is broken for big bitfields.
  return (x << (63 - msb)) >> (lsb + 63 - msb);
}

// Check number width.
inline bool is_intn(int64_t x, unsigned n) {
768
  DCHECK((0 < n) && (n < 64));
769 770 771 772 773
  int64_t limit = static_cast<int64_t>(1) << (n - 1);
  return (-limit <= x) && (x < limit);
}

inline bool is_uintn(int64_t x, unsigned n) {
774
  DCHECK((0 < n) && (n < (sizeof(x) * kBitsPerByte)));
775 776 777 778 779
  return !(x >> n);
}

template <class T>
inline T truncate_to_intn(T x, unsigned n) {
780
  DCHECK((0 < n) && (n < (sizeof(x) * kBitsPerByte)));
781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807
  return (x & ((static_cast<T>(1) << n) - 1));
}

#define INT_1_TO_63_LIST(V)                                                    \
V(1)  V(2)  V(3)  V(4)  V(5)  V(6)  V(7)  V(8)                                 \
V(9)  V(10) V(11) V(12) V(13) V(14) V(15) V(16)                                \
V(17) V(18) V(19) V(20) V(21) V(22) V(23) V(24)                                \
V(25) V(26) V(27) V(28) V(29) V(30) V(31) V(32)                                \
V(33) V(34) V(35) V(36) V(37) V(38) V(39) V(40)                                \
V(41) V(42) V(43) V(44) V(45) V(46) V(47) V(48)                                \
V(49) V(50) V(51) V(52) V(53) V(54) V(55) V(56)                                \
V(57) V(58) V(59) V(60) V(61) V(62) V(63)

#define DECLARE_IS_INT_N(N)                                                    \
inline bool is_int##N(int64_t x) { return is_intn(x, N); }
#define DECLARE_IS_UINT_N(N)                                                   \
template <class T>                                                             \
inline bool is_uint##N(T x) { return is_uintn(x, N); }
#define DECLARE_TRUNCATE_TO_INT_N(N)                                           \
template <class T>                                                             \
inline T truncate_to_int##N(T x) { return truncate_to_intn(x, N); }
INT_1_TO_63_LIST(DECLARE_IS_INT_N)
INT_1_TO_63_LIST(DECLARE_IS_UINT_N)
INT_1_TO_63_LIST(DECLARE_TRUNCATE_TO_INT_N)
#undef DECLARE_IS_INT_N
#undef DECLARE_IS_UINT_N
#undef DECLARE_TRUNCATE_TO_INT_N
808

809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825
// clang-format off
#define INT_0_TO_127_LIST(V)                                          \
V(0)   V(1)   V(2)   V(3)   V(4)   V(5)   V(6)   V(7)   V(8)   V(9)   \
V(10)  V(11)  V(12)  V(13)  V(14)  V(15)  V(16)  V(17)  V(18)  V(19)  \
V(20)  V(21)  V(22)  V(23)  V(24)  V(25)  V(26)  V(27)  V(28)  V(29)  \
V(30)  V(31)  V(32)  V(33)  V(34)  V(35)  V(36)  V(37)  V(38)  V(39)  \
V(40)  V(41)  V(42)  V(43)  V(44)  V(45)  V(46)  V(47)  V(48)  V(49)  \
V(50)  V(51)  V(52)  V(53)  V(54)  V(55)  V(56)  V(57)  V(58)  V(59)  \
V(60)  V(61)  V(62)  V(63)  V(64)  V(65)  V(66)  V(67)  V(68)  V(69)  \
V(70)  V(71)  V(72)  V(73)  V(74)  V(75)  V(76)  V(77)  V(78)  V(79)  \
V(80)  V(81)  V(82)  V(83)  V(84)  V(85)  V(86)  V(87)  V(88)  V(89)  \
V(90)  V(91)  V(92)  V(93)  V(94)  V(95)  V(96)  V(97)  V(98)  V(99)  \
V(100) V(101) V(102) V(103) V(104) V(105) V(106) V(107) V(108) V(109) \
V(110) V(111) V(112) V(113) V(114) V(115) V(116) V(117) V(118) V(119) \
V(120) V(121) V(122) V(123) V(124) V(125) V(126) V(127)
// clang-format on

826
class FeedbackSlot {
827
 public:
828 829
  FeedbackSlot() : id_(kInvalidSlot) {}
  explicit FeedbackSlot(int id) : id_(id) {}
830

831 832
  int ToInt() const { return id_; }

833
  static FeedbackSlot Invalid() { return FeedbackSlot(); }
834 835
  bool IsInvalid() const { return id_ == kInvalidSlot; }

836 837
  bool operator==(FeedbackSlot that) const { return this->id_ == that.id_; }
  bool operator!=(FeedbackSlot that) const { return !(*this == that); }
838

839 840
  friend size_t hash_value(FeedbackSlot slot) { return slot.ToInt(); }
  friend std::ostream& operator<<(std::ostream& os, FeedbackSlot);
841

842 843 844 845 846 847 848
 private:
  static const int kInvalidSlot = -1;

  int id_;
};


849 850 851 852 853 854
class BailoutId {
 public:
  explicit BailoutId(int id) : id_(id) { }
  int ToInt() const { return id_; }

  static BailoutId None() { return BailoutId(kNoneId); }
855 856
  static BailoutId ScriptContext() { return BailoutId(kScriptContextId); }
  static BailoutId FunctionContext() { return BailoutId(kFunctionContextId); }
857 858 859
  static BailoutId FunctionEntry() { return BailoutId(kFunctionEntryId); }
  static BailoutId Declarations() { return BailoutId(kDeclarationsId); }
  static BailoutId FirstUsable() { return BailoutId(kFirstUsableId); }
860
  static BailoutId StubEntry() { return BailoutId(kStubEntryId); }
861

862 863 864 865 866 867 868 869 870 871 872
  // Special bailout id support for deopting into the {JSConstructStub} stub.
  // The following hard-coded deoptimization points are supported by the stub:
  //  - {ConstructStubCreate} maps to {construct_stub_create_deopt_pc_offset}.
  //  - {ConstructStubInvoke} maps to {construct_stub_invoke_deopt_pc_offset}.
  static BailoutId ConstructStubCreate() { return BailoutId(1); }
  static BailoutId ConstructStubInvoke() { return BailoutId(2); }
  bool IsValidForConstructStub() const {
    return id_ == ConstructStubCreate().ToInt() ||
           id_ == ConstructStubInvoke().ToInt();
  }

873 874
  bool IsNone() const { return id_ == kNoneId; }
  bool operator==(const BailoutId& other) const { return id_ == other.id_; }
875
  bool operator!=(const BailoutId& other) const { return id_ != other.id_; }
876
  friend size_t hash_value(BailoutId);
877
  V8_EXPORT_PRIVATE friend std::ostream& operator<<(std::ostream&, BailoutId);
878 879

 private:
880 881
  friend class Builtins;

882 883 884
  static const int kNoneId = -1;

  // Using 0 could disguise errors.
885 886 887
  static const int kScriptContextId = 1;
  static const int kFunctionContextId = 2;
  static const int kFunctionEntryId = 3;
888 889 890 891

  // This AST id identifies the point after the declarations have been visited.
  // We need it to capture the environment effects of declarations that emit
  // code (function declarations).
892
  static const int kDeclarationsId = 4;
893

894
  // Every FunctionState starts with this id.
895
  static const int kFirstUsableId = 5;
896

897
  // Every compiled stub starts with this id.
898
  static const int kStubEntryId = 6;
899

900 901 902 903 904
  // Builtin continuations bailout ids start here. If you need to add a
  // non-builtin BailoutId, add it before this id so that this Id has the
  // highest number.
  static const int kFirstBuiltinContinuationId = 7;

905 906 907
  int id_;
};

908

909 910 911 912
// ----------------------------------------------------------------------------
// I/O support.

// Our version of printf().
913
V8_EXPORT_PRIVATE void PRINTF_FORMAT(1, 2) PrintF(const char* format, ...);
jfb's avatar
jfb committed
914
void PRINTF_FORMAT(2, 3) PrintF(FILE* out, const char* format, ...);
915 916

// Prepends the current process ID to the output.
jfb's avatar
jfb committed
917
void PRINTF_FORMAT(1, 2) PrintPID(const char* format, ...);
918

919
// Prepends the current process ID and given isolate pointer to the output.
jfb's avatar
jfb committed
920
void PRINTF_FORMAT(2, 3) PrintIsolate(void* isolate, const char* format, ...);
921

922 923
// Safe formatting print. Ensures that str is always null-terminated.
// Returns the number of chars written, or -1 if output was truncated.
jfb's avatar
jfb committed
924
int PRINTF_FORMAT(2, 3) SNPrintF(Vector<char> str, const char* format, ...);
925
V8_EXPORT_PRIVATE int PRINTF_FORMAT(2, 0)
jfb's avatar
jfb committed
926
    VSNPrintF(Vector<char> str, const char* format, va_list args);
927 928 929

void StrNCpy(Vector<char> dest, const char* src, size_t n);

930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974
// Our version of fflush.
void Flush(FILE* out);

inline void Flush() {
  Flush(stdout);
}


// Read a line of characters after printing the prompt to stdout. The resulting
// char* needs to be disposed off with DeleteArray by the caller.
char* ReadLine(const char* prompt);


// Append size chars from str to the file given by filename.
// The file is overwritten. Returns the number of chars written.
int AppendChars(const char* filename,
                const char* str,
                int size,
                bool verbose = true);


// Write size chars from str to the file given by filename.
// The file is overwritten. Returns the number of chars written.
int WriteChars(const char* filename,
               const char* str,
               int size,
               bool verbose = true);


// Write size bytes to the file given by filename.
// The file is overwritten. Returns the number of bytes written.
int WriteBytes(const char* filename,
               const byte* bytes,
               int size,
               bool verbose = true);


// Write the C code
// const char* <varname> = "<str>";
// const int <varname>_len = <len>;
// to the file given by filename. Only the first len chars are written.
int WriteAsCFile(const char* filename, const char* varname,
                 const char* str, int size, bool verbose = true);


975
// Simple support to read a file into std::string.
976
// On return, *exits tells whether the file existed.
977 978 979
V8_EXPORT_PRIVATE std::string ReadFile(const char* filename, bool* exists,
                                       bool verbose = true);
std::string ReadFile(FILE* file, bool* exists, bool verbose = true);
980 981 982 983 984 985 986

class StringBuilder : public SimpleStringBuilder {
 public:
  explicit StringBuilder(int size) : SimpleStringBuilder(size) { }
  StringBuilder(char* buffer, int size) : SimpleStringBuilder(buffer, size) { }

  // Add formatted contents to the builder just like printf().
jfb's avatar
jfb committed
987
  void PRINTF_FORMAT(2, 3) AddFormatted(const char* format, ...);
988 989

  // Add formatted contents like printf based on a va_list.
jfb's avatar
jfb committed
990 991
  void PRINTF_FORMAT(2, 0) AddFormattedList(const char* format, va_list list);

992 993 994 995 996
 private:
  DISALLOW_IMPLICIT_CONSTRUCTORS(StringBuilder);
};


997 998
bool DoubleToBoolean(double d);

999 1000 1001
template <typename Char>
bool TryAddIndexChar(uint32_t* index, Char c);

1002
template <typename Stream>
1003
bool StringToArrayIndex(Stream* stream, uint32_t* index);
1004

1005 1006 1007 1008 1009
// Returns the current stack top. Works correctly with ASAN and SafeStack.
// GetCurrentStackPosition() should not be inlined, because it works on stack
// frames if it were inlined into a function with a huge stack frame it would
// return an address significantly above the actual current stack position.
V8_NOINLINE uintptr_t GetCurrentStackPosition();
1010

1011
static inline uint16_t ByteReverse16(uint16_t value) {
1012
#if V8_HAS_BUILTIN_BSWAP16
1013
      return __builtin_bswap16(value);
1014 1015 1016
#else
      return value << 8 | (value >> 8 & 0x00FF);
#endif
1017 1018 1019
}

static inline uint32_t ByteReverse32(uint32_t value) {
1020
#if V8_HAS_BUILTIN_BSWAP32
1021
      return __builtin_bswap32(value);
1022
#else
1023 1024 1025 1026
      return value << 24 |
             ((value << 8) & 0x00FF0000) |
             ((value >> 8) & 0x0000FF00) |
             ((value >> 24) & 0x00000FF);
1027
#endif
1028 1029 1030
}

static inline uint64_t ByteReverse64(uint64_t value) {
1031
#if V8_HAS_BUILTIN_BSWAP64
1032
      return __builtin_bswap64(value);
1033
#else
1034
      size_t bits_of_v = sizeof(value) * kBitsPerByte;
1035 1036 1037 1038 1039 1040 1041 1042 1043
      return value << (bits_of_v - 8) |
             ((value << (bits_of_v - 24)) & 0x00FF000000000000) |
             ((value << (bits_of_v - 40)) & 0x0000FF0000000000) |
             ((value << (bits_of_v - 56)) & 0x000000FF00000000) |
             ((value >> (bits_of_v - 56)) & 0x00000000FF000000) |
             ((value >> (bits_of_v - 40)) & 0x0000000000FF0000) |
             ((value >> (bits_of_v - 24)) & 0x000000000000FF00) |
             ((value >> (bits_of_v - 8)) & 0x00000000000000FF);
#endif
1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057
}

template <typename V>
static inline V ByteReverse(V value) {
  size_t size_of_v = sizeof(value);
  switch (size_of_v) {
    case 1:
      return value;
    case 2:
      return static_cast<V>(ByteReverse16(static_cast<uint16_t>(value)));
    case 4:
      return static_cast<V>(ByteReverse32(static_cast<uint32_t>(value)));
    case 8:
      return static_cast<V>(ByteReverse64(static_cast<uint64_t>(value)));
1058 1059 1060 1061 1062
    default:
      UNREACHABLE();
  }
}

1063 1064 1065
V8_EXPORT_PRIVATE bool PassesFilter(Vector<const char> name,
                                    Vector<const char> filter);

1066 1067 1068 1069 1070 1071 1072 1073 1074
// Zap the specified area with a specific byte pattern. This currently defaults
// to int3 on x64 and ia32. On other architectures this will produce unspecified
// instruction sequences.
// TODO(jgruber): Better support for other architectures.
V8_INLINE void ZapCode(Address addr, size_t size_in_bytes) {
  static constexpr int kZapByte = 0xCC;
  std::memset(reinterpret_cast<void*>(addr), kZapByte, size_in_bytes);
}

1075 1076
}  // namespace internal
}  // namespace v8
1077

1078
#endif  // V8_UTILS_H_