Line data Source code
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 : #include <string>
13 : #include <type_traits>
14 :
15 : #include "include/v8.h"
16 : #include "src/allocation.h"
17 : #include "src/base/bits.h"
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 : #if defined(V8_OS_AIX)
28 : #include <fenv.h> // NOLINT(build/c++11)
29 : #endif
30 :
31 : namespace v8 {
32 : namespace internal {
33 :
34 : // ----------------------------------------------------------------------------
35 : // General helper functions
36 :
37 : // Returns the value (0 .. 15) of a hexadecimal character c.
38 : // If c is not a legal hexadecimal character, returns a value < 0.
39 : inline int HexValue(uc32 c) {
40 74747656 : c -= '0';
41 74747656 : if (static_cast<unsigned>(c) <= 9) return c;
42 8016235 : c = (c | 0x20) - ('a' - '0'); // detect 0x11..0x16 and 0x31..0x36.
43 8016235 : if (static_cast<unsigned>(c) <= 5) return c + 10;
44 : return -1;
45 : }
46 :
47 : inline char HexCharOfValue(int value) {
48 : DCHECK(0 <= value && value <= 16);
49 8201226 : if (value < 10) return value + '0';
50 533385 : return value - 10 + 'A';
51 : }
52 :
53 37308 : inline int BoolToInt(bool b) { return b ? 1 : 0; }
54 :
55 : // Checks if value is in range [lower_limit, higher_limit] using a single
56 : // branch.
57 : template <typename T, typename U>
58 : inline constexpr bool IsInRange(T value, U lower_limit, U higher_limit) {
59 : #if V8_CAN_HAVE_DCHECK_IN_CONSTEXPR
60 : DCHECK(lower_limit <= higher_limit);
61 : #endif
62 : STATIC_ASSERT(sizeof(U) <= sizeof(T));
63 : typedef typename std::make_unsigned<T>::type unsigned_T;
64 : // Use static_cast to support enum classes.
65 : return static_cast<unsigned_T>(static_cast<unsigned_T>(value) -
66 : static_cast<unsigned_T>(lower_limit)) <=
67 : static_cast<unsigned_T>(static_cast<unsigned_T>(higher_limit) -
68 6639324966 : static_cast<unsigned_T>(lower_limit));
69 : }
70 :
71 : // Checks if [index, index+length) is in range [0, max). Note that this check
72 : // works even if {index+length} would wrap around.
73 : inline constexpr bool IsInBounds(size_t index, size_t length, size_t max) {
74 6346538 : return length <= max && index <= (max - length);
75 : }
76 :
77 : // Checks if [index, index+length) is in range [0, max). If not, {length} is
78 : // clamped to its valid range. Note that this check works even if
79 : // {index+length} would wrap around.
80 : template <typename T>
81 : inline bool ClampToBounds(T index, T* length, T max) {
82 10782 : if (index > max) {
83 : *length = 0;
84 : return false;
85 : }
86 9334 : T avail = max - index;
87 : bool oob = *length > avail;
88 9334 : if (oob) *length = avail;
89 9334 : return !oob;
90 : }
91 :
92 : // X must be a power of 2. Returns the number of trailing zeros.
93 : template <typename T,
94 : typename = typename std::enable_if<std::is_integral<T>::value>::type>
95 14061 : inline int WhichPowerOf2(T x) {
96 : DCHECK(base::bits::IsPowerOfTwo(x));
97 : int bits = 0;
98 : #ifdef DEBUG
99 : const T original_x = x;
100 : #endif
101 : constexpr int max_bits = sizeof(T) * 8;
102 : static_assert(max_bits <= 64, "integral types are not bigger than 64 bits");
103 : // Avoid shifting by more than the bit width of x to avoid compiler warnings.
104 : #define CHECK_BIGGER(s) \
105 : if (max_bits > s && x >= T{1} << (max_bits > s ? s : 0)) { \
106 : bits += s; \
107 : x >>= max_bits > s ? s : 0; \
108 : }
109 11094 : CHECK_BIGGER(32)
110 14061 : CHECK_BIGGER(16)
111 14061 : CHECK_BIGGER(8)
112 14061 : CHECK_BIGGER(4)
113 : #undef CHECK_BIGGER
114 14061 : switch (x) {
115 0 : default: UNREACHABLE();
116 : case 8:
117 7752 : bits++;
118 : V8_FALLTHROUGH;
119 : case 4:
120 8209 : bits++;
121 : V8_FALLTHROUGH;
122 : case 2:
123 12074 : bits++;
124 : V8_FALLTHROUGH;
125 : case 1: break;
126 : }
127 : DCHECK_EQ(T{1} << bits, original_x);
128 14061 : return bits;
129 : }
130 :
131 : inline int MostSignificantBit(uint32_t x) {
132 : static const int msb4[] = {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4};
133 : int nibble = 0;
134 : if (x & 0xffff0000) {
135 : nibble += 16;
136 : x >>= 16;
137 : }
138 : if (x & 0xff00) {
139 : nibble += 8;
140 : x >>= 8;
141 : }
142 : if (x & 0xf0) {
143 : nibble += 4;
144 : x >>= 4;
145 : }
146 : return nibble + msb4[x];
147 : }
148 :
149 : template <typename T>
150 23952 : static T ArithmeticShiftRight(T x, int shift) {
151 : DCHECK_LE(0, shift);
152 24324 : if (x < 0) {
153 : // Right shift of signed values is implementation defined. Simulate a
154 : // true arithmetic right shift by adding leading sign bits.
155 : using UnsignedT = typename std::make_unsigned<T>::type;
156 5610 : UnsignedT mask = ~(static_cast<UnsignedT>(~0) >> shift);
157 5610 : return (static_cast<UnsignedT>(x) >> shift) | mask;
158 : } else {
159 18714 : return x >> shift;
160 : }
161 : }
162 :
163 : template <typename T>
164 : int Compare(const T& a, const T& b) {
165 3935 : if (a == b)
166 : return 0;
167 3935 : else if (a < b)
168 : return -1;
169 : else
170 : return 1;
171 : }
172 :
173 : // Compare function to compare the object pointer value of two
174 : // handlified objects. The handles are passed as pointers to the
175 : // handles.
176 : template<typename T> class Handle; // Forward declaration.
177 : template <typename T>
178 : int HandleObjectPointerCompare(const Handle<T>* a, const Handle<T>* b) {
179 : return Compare<T*>(*(*a), *(*b));
180 : }
181 :
182 : // Returns the maximum of the two parameters.
183 : template <typename T>
184 : constexpr T Max(T a, T b) {
185 186845770 : return a < b ? b : a;
186 : }
187 :
188 :
189 : // Returns the minimum of the two parameters.
190 : template <typename T>
191 : constexpr T Min(T a, T b) {
192 534382418 : return a < b ? a : b;
193 : }
194 :
195 : // Returns the maximum of the two parameters according to JavaScript semantics.
196 : template <typename T>
197 428908 : T JSMax(T x, T y) {
198 428908 : if (std::isnan(x)) return x;
199 419672 : if (std::isnan(y)) return y;
200 821696 : if (std::signbit(x) < std::signbit(y)) return x;
201 310048 : return x > y ? x : y;
202 : }
203 :
204 : // Returns the maximum of the two parameters according to JavaScript semantics.
205 : template <typename T>
206 428924 : T JSMin(T x, T y) {
207 428924 : if (std::isnan(x)) return x;
208 419688 : if (std::isnan(y)) return y;
209 821728 : if (std::signbit(x) < std::signbit(y)) return y;
210 310064 : return x > y ? y : x;
211 : }
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 : // This is a branch-free implementation of the absolute value function and is
218 : // described in Warren's "Hacker's Delight", chapter 2. It avoids undefined
219 : // behavior with the arithmetic negation operation on signed values as well.
220 : typedef typename std::make_unsigned<T>::type unsignedT;
221 5835 : unsignedT x = static_cast<unsignedT>(a);
222 5835 : unsignedT y = static_cast<unsignedT>(a >> (sizeof(T) * 8 - 1));
223 5835 : return (x ^ y) - y;
224 : }
225 :
226 : // Returns the negative absolute value of its argument.
227 : template <typename T,
228 : typename = typename std::enable_if<std::is_signed<T>::value>::type>
229 : T Nabs(T a) {
230 : return a < 0 ? a : -a;
231 : }
232 :
233 : inline double Modulo(double x, double y) {
234 : #if defined(V8_OS_WIN)
235 : // Workaround MS fmod bugs. ECMA-262 says:
236 : // dividend is finite and divisor is an infinity => result equals dividend
237 : // dividend is a zero and divisor is nonzero finite => result equals dividend
238 : if (!(std::isfinite(x) && (!std::isfinite(y) && !std::isnan(y))) &&
239 : !(x == 0 && (y != 0 && std::isfinite(y)))) {
240 : double result = fmod(x, y);
241 : // Workaround MS bug in VS CRT in some OS versions, https://crbug.com/915045
242 : // fmod(-17, +/-1) should equal -0.0 but now returns 0.0.
243 : if (x < 0 && result == 0) result = -0.0;
244 : x = result;
245 : }
246 : return x;
247 : #elif defined(V8_OS_AIX)
248 : // AIX raises an underflow exception for (Number.MIN_VALUE % Number.MAX_VALUE)
249 : feclearexcept(FE_ALL_EXCEPT);
250 : double result = std::fmod(x, y);
251 : int exception = fetestexcept(FE_UNDERFLOW);
252 : return (exception ? x : result);
253 : #else
254 723268 : return std::fmod(x, y);
255 : #endif
256 : }
257 :
258 : template <typename T>
259 : T SaturateAdd(T a, T b) {
260 : if (std::is_signed<T>::value) {
261 9361 : if (a > 0 && b > 0) {
262 2305 : if (a > std::numeric_limits<T>::max() - b) {
263 : return std::numeric_limits<T>::max();
264 : }
265 7056 : } else if (a < 0 && b < 0) {
266 1641 : if (a < std::numeric_limits<T>::min() - b) {
267 : return std::numeric_limits<T>::min();
268 : }
269 : }
270 : } else {
271 : CHECK(std::is_unsigned<T>::value);
272 9369 : if (a > std::numeric_limits<T>::max() - b) {
273 : return std::numeric_limits<T>::max();
274 : }
275 : }
276 11939 : return a + b;
277 : }
278 :
279 : template <typename T>
280 : T SaturateSub(T a, T b) {
281 : if (std::is_signed<T>::value) {
282 9397 : if (a >= 0 && b < 0) {
283 2238 : if (a > std::numeric_limits<T>::max() + b) {
284 : return std::numeric_limits<T>::max();
285 : }
286 7167 : } else if (a < 0 && b > 0) {
287 1835 : if (a < std::numeric_limits<T>::min() + b) {
288 : return std::numeric_limits<T>::min();
289 : }
290 : }
291 : } else {
292 : CHECK(std::is_unsigned<T>::value);
293 9369 : if (a < b) {
294 : return static_cast<T>(0);
295 : }
296 : }
297 11745 : return a - b;
298 : }
299 :
300 : // ----------------------------------------------------------------------------
301 : // BitField is a help template for encoding and decode bitfield with
302 : // unsigned content.
303 :
304 : template<class T, int shift, int size, class U>
305 : class BitFieldBase {
306 : public:
307 : typedef T FieldType;
308 :
309 : // A type U mask of bit field. To use all bits of a type U of x bits
310 : // in a bitfield without compiler warnings we have to compute 2^x
311 : // without using a shift count of x in the computation.
312 : static const U kOne = static_cast<U>(1U);
313 : static const U kMask = ((kOne << shift) << size) - (kOne << shift);
314 : static const U kShift = shift;
315 : 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 82013863 : return (static_cast<U>(value) & ~static_cast<U>(kMax)) == 0;
325 : }
326 :
327 : // Returns a type U with the bit field value encoded.
328 : static constexpr U encode(T value) {
329 : #if V8_CAN_HAVE_DCHECK_IN_CONSTEXPR
330 : DCHECK(is_valid(value));
331 : #endif
332 5490006064 : 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 5978674775 : return (previous & ~kMask) | encode(value);
338 : }
339 :
340 : // Extracts the bit field from the value.
341 : static constexpr T decode(U value) {
342 48623441770 : return static_cast<T>((value & kMask) >> shift);
343 : }
344 :
345 : STATIC_ASSERT((kNext - 1) / 8 < sizeof(U));
346 : };
347 :
348 : template <class T, int shift, int size>
349 : class BitField8 : public BitFieldBase<T, shift, size, uint8_t> {};
350 :
351 :
352 : template <class T, int shift, int size>
353 : class BitField16 : public BitFieldBase<T, shift, size, uint16_t> {};
354 :
355 :
356 : template<class T, int shift, int size>
357 : class BitField : public BitFieldBase<T, shift, size, uint32_t> { };
358 :
359 :
360 : template<class T, int shift, int size>
361 : class BitField64 : public BitFieldBase<T, shift, size, uint64_t> { };
362 :
363 : // Helper macros for defining a contiguous sequence of bit fields. Example:
364 : // (backslashes at the ends of respective lines of this multi-line macro
365 : // definition are omitted here to please the compiler)
366 : //
367 : // #define MAP_BIT_FIELD1(V, _)
368 : // V(IsAbcBit, bool, 1, _)
369 : // V(IsBcdBit, bool, 1, _)
370 : // V(CdeBits, int, 5, _)
371 : // V(DefBits, MutableMode, 1, _)
372 : //
373 : // DEFINE_BIT_FIELDS(MAP_BIT_FIELD1)
374 : // or
375 : // DEFINE_BIT_FIELDS_64(MAP_BIT_FIELD1)
376 : //
377 : #define DEFINE_BIT_FIELD_RANGE_TYPE(Name, Type, Size, _) \
378 : k##Name##Start, k##Name##End = k##Name##Start + Size - 1,
379 :
380 : #define DEFINE_BIT_RANGES(LIST_MACRO) \
381 : struct LIST_MACRO##_Ranges { \
382 : enum { LIST_MACRO(DEFINE_BIT_FIELD_RANGE_TYPE, _) kBitsCount }; \
383 : };
384 :
385 : #define DEFINE_BIT_FIELD_TYPE(Name, Type, Size, RangesName) \
386 : typedef BitField<Type, RangesName::k##Name##Start, Size> Name;
387 :
388 : #define DEFINE_BIT_FIELD_64_TYPE(Name, Type, Size, RangesName) \
389 : typedef BitField64<Type, RangesName::k##Name##Start, Size> Name;
390 :
391 : #define DEFINE_BIT_FIELDS(LIST_MACRO) \
392 : DEFINE_BIT_RANGES(LIST_MACRO) \
393 : LIST_MACRO(DEFINE_BIT_FIELD_TYPE, LIST_MACRO##_Ranges)
394 :
395 : #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 : // BitSetComputer is a help template for encoding and decoding information for
401 : // a variable number of items in an array.
402 : //
403 : // To encode boolean data in a smi array you would use:
404 : // typedef BitSetComputer<bool, 1, kSmiValueSize, uint32_t> BoolComputer;
405 : //
406 : template <class T, int kBitsPerItem, int kBitsPerWord, class U>
407 : class BitSetComputer {
408 : public:
409 : static const int kItemsPerWord = kBitsPerWord / kBitsPerItem;
410 : static const int kMask = (1 << kBitsPerItem) - 1;
411 :
412 : // The number of array elements required to embed T information for each item.
413 : static int word_count(int items) {
414 6975049 : if (items == 0) return 0;
415 5844271 : return (items - 1) / kItemsPerWord + 1;
416 : }
417 :
418 : // The array index to look at for item.
419 : static int index(int base_index, int item) {
420 69967008 : return base_index + item / kItemsPerWord;
421 : }
422 :
423 : // Extract T data for a given item from data.
424 : static T decode(U data, int item) {
425 43985243 : return static_cast<T>((data >> shift(item)) & kMask);
426 : }
427 :
428 : // Return the encoding for a store of value for item in previous.
429 : static U encode(U previous, int item, T value) {
430 : int shift_value = shift(item);
431 25985935 : int set_bits = (static_cast<int>(value) << shift_value);
432 25985935 : return (previous & ~(kMask << shift_value)) | set_bits;
433 : }
434 :
435 69967008 : static int shift(int item) { return (item % kItemsPerWord) * kBitsPerItem; }
436 : };
437 :
438 : // Helper macros for defining a contiguous sequence of field offset constants.
439 : // Example: (backslashes at the ends of respective lines of this multi-line
440 : // macro definition are omitted here to please the compiler)
441 : //
442 : // #define MAP_FIELDS(V)
443 : // V(kField1Offset, kTaggedSize)
444 : // V(kField2Offset, kIntSize)
445 : // V(kField3Offset, kIntSize)
446 : // V(kField4Offset, kSystemPointerSize)
447 : // V(kSize, 0)
448 : //
449 : // DEFINE_FIELD_OFFSET_CONSTANTS(HeapObject::kHeaderSize, MAP_FIELDS)
450 : //
451 : #define DEFINE_ONE_FIELD_OFFSET(Name, Size) Name, Name##End = Name + (Size)-1,
452 :
453 : #define DEFINE_FIELD_OFFSET_CONSTANTS(StartOffset, LIST_MACRO) \
454 : enum { \
455 : LIST_MACRO##_StartOffset = StartOffset - 1, \
456 : LIST_MACRO(DEFINE_ONE_FIELD_OFFSET) \
457 : };
458 :
459 : // Size of the field defined by DEFINE_FIELD_OFFSET_CONSTANTS
460 : #define FIELD_SIZE(Name) (Name##End + 1 - Name)
461 :
462 : // Compare two offsets with static cast
463 : #define STATIC_ASSERT_FIELD_OFFSETS_EQUAL(Offset1, Offset2) \
464 : STATIC_ASSERT(static_cast<int>(Offset1) == Offset2)
465 : // ----------------------------------------------------------------------------
466 : // Hash function.
467 :
468 : static const uint64_t kZeroHashSeed = 0;
469 :
470 : // Thomas Wang, Integer Hash Functions.
471 : // http://www.concentric.net/~Ttwang/tech/inthash.htm`
472 : inline uint32_t ComputeUnseededHash(uint32_t key) {
473 : uint32_t hash = key;
474 93392299 : hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1;
475 93392299 : hash = hash ^ (hash >> 12);
476 93392299 : hash = hash + (hash << 2);
477 93392299 : hash = hash ^ (hash >> 4);
478 93392299 : hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11);
479 93392299 : hash = hash ^ (hash >> 16);
480 33409808 : return hash & 0x3fffffff;
481 : }
482 :
483 : inline uint32_t ComputeLongHash(uint64_t key) {
484 : uint64_t hash = key;
485 155789573 : hash = ~hash + (hash << 18); // hash = (hash << 18) - hash - 1;
486 155789573 : hash = hash ^ (hash >> 31);
487 155789573 : hash = hash * 21; // hash = (hash + (hash << 2)) + (hash << 4);
488 155789573 : hash = hash ^ (hash >> 11);
489 155789573 : hash = hash + (hash << 6);
490 155789573 : hash = hash ^ (hash >> 22);
491 155789573 : return static_cast<uint32_t>(hash & 0x3fffffff);
492 : }
493 :
494 : inline uint32_t ComputeSeededHash(uint32_t key, uint64_t seed) {
495 : #ifdef V8_USE_SIPHASH
496 : return halfsiphash(key, seed);
497 : #else
498 151758208 : return ComputeLongHash(static_cast<uint64_t>(key) ^ seed);
499 : #endif // V8_USE_SIPHASH
500 : }
501 :
502 : inline uint32_t ComputePointerHash(void* ptr) {
503 21959 : return ComputeUnseededHash(
504 : static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr)));
505 : }
506 :
507 : inline uint32_t ComputeAddressHash(Address address) {
508 10593849 : return ComputeUnseededHash(static_cast<uint32_t>(address & 0xFFFFFFFFul));
509 : }
510 :
511 : // ----------------------------------------------------------------------------
512 : // Miscellaneous
513 :
514 : // Memory offset for lower and higher bits in a 64 bit integer.
515 : #if defined(V8_TARGET_LITTLE_ENDIAN)
516 : static const int kInt64LowerHalfMemoryOffset = 0;
517 : static const int kInt64UpperHalfMemoryOffset = 4;
518 : #elif defined(V8_TARGET_BIG_ENDIAN)
519 : static const int kInt64LowerHalfMemoryOffset = 4;
520 : static const int kInt64UpperHalfMemoryOffset = 0;
521 : #endif // V8_TARGET_LITTLE_ENDIAN
522 :
523 : // A static resource holds a static instance that can be reserved in
524 : // a local scope using an instance of Access. Attempts to re-reserve
525 : // the instance will cause an error.
526 : template <typename T>
527 : class StaticResource {
528 : public:
529 62442 : StaticResource() : is_reserved_(false) {}
530 :
531 : private:
532 : template <typename S> friend class Access;
533 : T instance_;
534 : bool is_reserved_;
535 : };
536 :
537 :
538 : // Locally scoped access to a static resource.
539 : template <typename T>
540 : class Access {
541 : public:
542 : explicit Access(StaticResource<T>* resource)
543 : : resource_(resource)
544 10 : , instance_(&resource->instance_) {
545 : DCHECK(!resource->is_reserved_);
546 10 : resource->is_reserved_ = true;
547 : }
548 :
549 : ~Access() {
550 10 : resource_->is_reserved_ = false;
551 : resource_ = nullptr;
552 : instance_ = nullptr;
553 : }
554 :
555 : T* value() { return instance_; }
556 : T* operator -> () { return instance_; }
557 :
558 : private:
559 : StaticResource<T>* resource_;
560 : T* instance_;
561 : };
562 :
563 : // A pointer that can only be set once and doesn't allow NULL values.
564 : template<typename T>
565 : class SetOncePointer {
566 : public:
567 4187807 : SetOncePointer() = default;
568 :
569 7011088 : bool is_set() const { return pointer_ != nullptr; }
570 :
571 : T* get() const {
572 : DCHECK_NOT_NULL(pointer_);
573 10207992 : return pointer_;
574 : }
575 :
576 : void set(T* value) {
577 : DCHECK(pointer_ == nullptr && value != nullptr);
578 2059438 : pointer_ = value;
579 : }
580 :
581 : T* operator=(T* value) {
582 : set(value);
583 : return value;
584 : }
585 :
586 184693 : bool operator==(std::nullptr_t) const { return pointer_ == nullptr; }
587 : bool operator!=(std::nullptr_t) const { return pointer_ != nullptr; }
588 :
589 : private:
590 : T* pointer_ = nullptr;
591 : };
592 :
593 : // Compare 8bit/16bit chars to 8bit/16bit chars.
594 : template <typename lchar, typename rchar>
595 : inline int CompareCharsUnsigned(const lchar* lhs, const rchar* rhs,
596 : size_t chars) {
597 819884 : const lchar* limit = lhs + chars;
598 : if (sizeof(*lhs) == sizeof(char) && sizeof(*rhs) == sizeof(char)) {
599 : // memcmp compares byte-by-byte, yielding wrong results for two-byte
600 : // strings on little-endian systems.
601 343640012 : return memcmp(lhs, rhs, chars);
602 : }
603 20418576 : while (lhs < limit) {
604 19616869 : int r = static_cast<int>(*lhs) - static_cast<int>(*rhs);
605 19616869 : if (r != 0) return r;
606 19598692 : ++lhs;
607 19598692 : ++rhs;
608 : }
609 : return 0;
610 : }
611 :
612 : template <typename lchar, typename rchar>
613 : inline int CompareChars(const lchar* lhs, const rchar* rhs, size_t chars) {
614 : DCHECK_LE(sizeof(lchar), 2);
615 : DCHECK_LE(sizeof(rchar), 2);
616 : if (sizeof(lchar) == 1) {
617 : if (sizeof(rchar) == 1) {
618 : return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
619 : reinterpret_cast<const uint8_t*>(rhs),
620 : chars);
621 : } else {
622 : return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
623 : reinterpret_cast<const uint16_t*>(rhs),
624 : chars);
625 : }
626 : } else {
627 : if (sizeof(rchar) == 1) {
628 : return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
629 : reinterpret_cast<const uint8_t*>(rhs),
630 : chars);
631 : } else {
632 : return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
633 : reinterpret_cast<const uint16_t*>(rhs),
634 : chars);
635 : }
636 : }
637 : }
638 :
639 :
640 : // Calculate 10^exponent.
641 : inline int TenToThe(int exponent) {
642 : DCHECK_LE(exponent, 9);
643 : DCHECK_GE(exponent, 1);
644 : int answer = 10;
645 : for (int i = 1; i < exponent; i++) answer *= 10;
646 : return answer;
647 : }
648 :
649 :
650 : template<typename ElementType, int NumElements>
651 : class EmbeddedContainer {
652 : public:
653 : EmbeddedContainer() : elems_() { }
654 :
655 : int length() const { return NumElements; }
656 : const ElementType& operator[](int i) const {
657 : DCHECK(i < length());
658 : return elems_[i];
659 : }
660 : ElementType& operator[](int i) {
661 : DCHECK(i < length());
662 : return elems_[i];
663 : }
664 :
665 : private:
666 : ElementType elems_[NumElements];
667 : };
668 :
669 :
670 : template<typename ElementType>
671 : class EmbeddedContainer<ElementType, 0> {
672 : public:
673 : int length() const { return 0; }
674 : const ElementType& operator[](int i) const {
675 : UNREACHABLE();
676 : static ElementType t = 0;
677 : return t;
678 : }
679 : ElementType& operator[](int i) {
680 : UNREACHABLE();
681 : static ElementType t = 0;
682 : return t;
683 : }
684 : };
685 :
686 :
687 : // Helper class for building result strings in a character buffer. The
688 : // purpose of the class is to use safe operations that checks the
689 : // buffer bounds on all operations in debug mode.
690 : // This simple base class does not allow formatted output.
691 : class SimpleStringBuilder {
692 : public:
693 : // Create a string builder with a buffer of the given size. The
694 : // buffer is allocated through NewArray<char> and must be
695 : // deallocated by the caller of Finalize().
696 : explicit SimpleStringBuilder(int size);
697 :
698 : SimpleStringBuilder(char* buffer, int size)
699 2250682 : : buffer_(buffer, size), position_(0) { }
700 :
701 1135281 : ~SimpleStringBuilder() { if (!is_finalized()) Finalize(); }
702 :
703 : int size() const { return buffer_.length(); }
704 :
705 : // Get the current position in the builder.
706 : int position() const {
707 : DCHECK(!is_finalized());
708 : return position_;
709 : }
710 :
711 : // Reset the position.
712 0 : void Reset() { position_ = 0; }
713 :
714 : // Add a single character to the builder. It is not allowed to add
715 : // 0-characters; use the Finalize() method to terminate the string
716 : // instead.
717 : void AddCharacter(char c) {
718 : DCHECK_NE(c, '\0');
719 : DCHECK(!is_finalized() && position_ < buffer_.length());
720 4217928 : buffer_[position_++] = c;
721 : }
722 :
723 : // Add an entire string to the builder. Uses strlen() internally to
724 : // compute the length of the input string.
725 : void AddString(const char* s);
726 :
727 : // Add the first 'n' characters of the given 0-terminated string 's' to the
728 : // builder. The input string must have enough characters.
729 : void AddSubstring(const char* s, int n);
730 :
731 : // Add character padding to the builder. If count is non-positive,
732 : // nothing is added to the builder.
733 : void AddPadding(char c, int count);
734 :
735 : // Add the decimal representation of the value.
736 : void AddDecimalInteger(int value);
737 :
738 : // Finalize the string by 0-terminating it and returning the buffer.
739 : char* Finalize();
740 :
741 : protected:
742 : Vector<char> buffer_;
743 : int position_;
744 :
745 : bool is_finalized() const { return position_ < 0; }
746 :
747 : private:
748 : DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder);
749 : };
750 :
751 : // Bit field extraction.
752 : inline uint32_t unsigned_bitextract_32(int msb, int lsb, uint32_t x) {
753 : return (x >> lsb) & ((1 << (1 + msb - lsb)) - 1);
754 : }
755 :
756 : inline uint64_t unsigned_bitextract_64(int msb, int lsb, uint64_t x) {
757 : return (x >> lsb) & ((static_cast<uint64_t>(1) << (1 + msb - lsb)) - 1);
758 : }
759 :
760 : inline int32_t signed_bitextract_32(int msb, int lsb, int32_t x) {
761 : return (x << (31 - msb)) >> (lsb + 31 - msb);
762 : }
763 :
764 : inline int signed_bitextract_64(int msb, int lsb, int x) {
765 : // TODO(jbramley): This is broken for big bitfields.
766 : return (x << (63 - msb)) >> (lsb + 63 - msb);
767 : }
768 :
769 : // Check number width.
770 : inline bool is_intn(int64_t x, unsigned n) {
771 : DCHECK((0 < n) && (n < 64));
772 : int64_t limit = static_cast<int64_t>(1) << (n - 1);
773 69349262 : return (-limit <= x) && (x < limit);
774 : }
775 :
776 : inline bool is_uintn(int64_t x, unsigned n) {
777 : DCHECK((0 < n) && (n < (sizeof(x) * kBitsPerByte)));
778 19207822 : return !(x >> n);
779 : }
780 :
781 : template <class T>
782 : inline T truncate_to_intn(T x, unsigned n) {
783 : DCHECK((0 < n) && (n < (sizeof(x) * kBitsPerByte)));
784 : return (x & ((static_cast<T>(1) << n) - 1));
785 : }
786 :
787 : #define INT_1_TO_63_LIST(V) \
788 : V(1) V(2) V(3) V(4) V(5) V(6) V(7) V(8) \
789 : V(9) V(10) V(11) V(12) V(13) V(14) V(15) V(16) \
790 : V(17) V(18) V(19) V(20) V(21) V(22) V(23) V(24) \
791 : V(25) V(26) V(27) V(28) V(29) V(30) V(31) V(32) \
792 : V(33) V(34) V(35) V(36) V(37) V(38) V(39) V(40) \
793 : V(41) V(42) V(43) V(44) V(45) V(46) V(47) V(48) \
794 : V(49) V(50) V(51) V(52) V(53) V(54) V(55) V(56) \
795 : V(57) V(58) V(59) V(60) V(61) V(62) V(63)
796 :
797 : #define DECLARE_IS_INT_N(N) \
798 : inline bool is_int##N(int64_t x) { return is_intn(x, N); }
799 : #define DECLARE_IS_UINT_N(N) \
800 : template <class T> \
801 : inline bool is_uint##N(T x) { return is_uintn(x, N); }
802 : #define DECLARE_TRUNCATE_TO_INT_N(N) \
803 : template <class T> \
804 : inline T truncate_to_int##N(T x) { return truncate_to_intn(x, N); }
805 : INT_1_TO_63_LIST(DECLARE_IS_INT_N)
806 5366780 : INT_1_TO_63_LIST(DECLARE_IS_UINT_N)
807 : INT_1_TO_63_LIST(DECLARE_TRUNCATE_TO_INT_N)
808 : #undef DECLARE_IS_INT_N
809 : #undef DECLARE_IS_UINT_N
810 : #undef DECLARE_TRUNCATE_TO_INT_N
811 :
812 : // clang-format off
813 : #define INT_0_TO_127_LIST(V) \
814 : V(0) V(1) V(2) V(3) V(4) V(5) V(6) V(7) V(8) V(9) \
815 : V(10) V(11) V(12) V(13) V(14) V(15) V(16) V(17) V(18) V(19) \
816 : V(20) V(21) V(22) V(23) V(24) V(25) V(26) V(27) V(28) V(29) \
817 : V(30) V(31) V(32) V(33) V(34) V(35) V(36) V(37) V(38) V(39) \
818 : V(40) V(41) V(42) V(43) V(44) V(45) V(46) V(47) V(48) V(49) \
819 : V(50) V(51) V(52) V(53) V(54) V(55) V(56) V(57) V(58) V(59) \
820 : V(60) V(61) V(62) V(63) V(64) V(65) V(66) V(67) V(68) V(69) \
821 : V(70) V(71) V(72) V(73) V(74) V(75) V(76) V(77) V(78) V(79) \
822 : V(80) V(81) V(82) V(83) V(84) V(85) V(86) V(87) V(88) V(89) \
823 : V(90) V(91) V(92) V(93) V(94) V(95) V(96) V(97) V(98) V(99) \
824 : V(100) V(101) V(102) V(103) V(104) V(105) V(106) V(107) V(108) V(109) \
825 : V(110) V(111) V(112) V(113) V(114) V(115) V(116) V(117) V(118) V(119) \
826 : V(120) V(121) V(122) V(123) V(124) V(125) V(126) V(127)
827 : // clang-format on
828 :
829 : class FeedbackSlot {
830 : public:
831 286929881 : FeedbackSlot() : id_(kInvalidSlot) {}
832 2186032 : explicit FeedbackSlot(int id) : id_(id) {}
833 :
834 1524809 : int ToInt() const { return id_; }
835 :
836 : static FeedbackSlot Invalid() { return FeedbackSlot(); }
837 2442357 : bool IsInvalid() const { return id_ == kInvalidSlot; }
838 :
839 75 : bool operator==(FeedbackSlot that) const { return this->id_ == that.id_; }
840 : bool operator!=(FeedbackSlot that) const { return !(*this == that); }
841 :
842 219 : friend size_t hash_value(FeedbackSlot slot) { return slot.ToInt(); }
843 : V8_EXPORT_PRIVATE friend std::ostream& operator<<(std::ostream& os,
844 : FeedbackSlot);
845 :
846 : private:
847 : static const int kInvalidSlot = -1;
848 :
849 : int id_;
850 : };
851 :
852 : V8_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& os, FeedbackSlot);
853 :
854 : class BailoutId {
855 : public:
856 6687323 : explicit BailoutId(int id) : id_(id) { }
857 3624361 : int ToInt() const { return id_; }
858 :
859 : static BailoutId None() { return BailoutId(kNoneId); }
860 : static BailoutId ScriptContext() { return BailoutId(kScriptContextId); }
861 : static BailoutId FunctionContext() { return BailoutId(kFunctionContextId); }
862 : static BailoutId FunctionEntry() { return BailoutId(kFunctionEntryId); }
863 : static BailoutId Declarations() { return BailoutId(kDeclarationsId); }
864 : static BailoutId FirstUsable() { return BailoutId(kFirstUsableId); }
865 : static BailoutId StubEntry() { return BailoutId(kStubEntryId); }
866 :
867 : // Special bailout id support for deopting into the {JSConstructStub} stub.
868 : // The following hard-coded deoptimization points are supported by the stub:
869 : // - {ConstructStubCreate} maps to {construct_stub_create_deopt_pc_offset}.
870 : // - {ConstructStubInvoke} maps to {construct_stub_invoke_deopt_pc_offset}.
871 : static BailoutId ConstructStubCreate() { return BailoutId(1); }
872 : static BailoutId ConstructStubInvoke() { return BailoutId(2); }
873 : bool IsValidForConstructStub() const {
874 : return id_ == ConstructStubCreate().ToInt() ||
875 : id_ == ConstructStubInvoke().ToInt();
876 : }
877 :
878 11932949 : bool IsNone() const { return id_ == kNoneId; }
879 2 : bool operator==(const BailoutId& other) const { return id_ == other.id_; }
880 6209 : bool operator!=(const BailoutId& other) const { return id_ != other.id_; }
881 : friend size_t hash_value(BailoutId);
882 : V8_EXPORT_PRIVATE friend std::ostream& operator<<(std::ostream&, BailoutId);
883 :
884 : private:
885 : friend class Builtins;
886 :
887 : static const int kNoneId = -1;
888 :
889 : // Using 0 could disguise errors.
890 : static const int kScriptContextId = 1;
891 : static const int kFunctionContextId = 2;
892 : static const int kFunctionEntryId = 3;
893 :
894 : // This AST id identifies the point after the declarations have been visited.
895 : // We need it to capture the environment effects of declarations that emit
896 : // code (function declarations).
897 : static const int kDeclarationsId = 4;
898 :
899 : // Every FunctionState starts with this id.
900 : static const int kFirstUsableId = 5;
901 :
902 : // Every compiled stub starts with this id.
903 : static const int kStubEntryId = 6;
904 :
905 : // Builtin continuations bailout ids start here. If you need to add a
906 : // non-builtin BailoutId, add it before this id so that this Id has the
907 : // highest number.
908 : static const int kFirstBuiltinContinuationId = 7;
909 :
910 : int id_;
911 : };
912 :
913 :
914 : // ----------------------------------------------------------------------------
915 : // I/O support.
916 :
917 : // Our version of printf().
918 : V8_EXPORT_PRIVATE void PRINTF_FORMAT(1, 2) PrintF(const char* format, ...);
919 : void PRINTF_FORMAT(2, 3) PrintF(FILE* out, const char* format, ...);
920 :
921 : // Prepends the current process ID to the output.
922 : void PRINTF_FORMAT(1, 2) PrintPID(const char* format, ...);
923 :
924 : // Prepends the current process ID and given isolate pointer to the output.
925 : void PRINTF_FORMAT(2, 3) PrintIsolate(void* isolate, const char* format, ...);
926 :
927 : // Safe formatting print. Ensures that str is always null-terminated.
928 : // Returns the number of chars written, or -1 if output was truncated.
929 : V8_EXPORT_PRIVATE int PRINTF_FORMAT(2, 3)
930 : SNPrintF(Vector<char> str, const char* format, ...);
931 : V8_EXPORT_PRIVATE int PRINTF_FORMAT(2, 0)
932 : VSNPrintF(Vector<char> str, const char* format, va_list args);
933 :
934 : void StrNCpy(Vector<char> dest, const char* src, size_t n);
935 :
936 : // Our version of fflush.
937 : void Flush(FILE* out);
938 :
939 : inline void Flush() {
940 : Flush(stdout);
941 : }
942 :
943 :
944 : // Read a line of characters after printing the prompt to stdout. The resulting
945 : // char* needs to be disposed off with DeleteArray by the caller.
946 : char* ReadLine(const char* prompt);
947 :
948 :
949 : // Append size chars from str to the file given by filename.
950 : // The file is overwritten. Returns the number of chars written.
951 : int AppendChars(const char* filename,
952 : const char* str,
953 : int size,
954 : bool verbose = true);
955 :
956 :
957 : // Write size chars from str to the file given by filename.
958 : // The file is overwritten. Returns the number of chars written.
959 : int WriteChars(const char* filename,
960 : const char* str,
961 : int size,
962 : bool verbose = true);
963 :
964 :
965 : // Write size bytes to the file given by filename.
966 : // The file is overwritten. Returns the number of bytes written.
967 : int WriteBytes(const char* filename,
968 : const byte* bytes,
969 : int size,
970 : bool verbose = true);
971 :
972 :
973 : // Write the C code
974 : // const char* <varname> = "<str>";
975 : // const int <varname>_len = <len>;
976 : // to the file given by filename. Only the first len chars are written.
977 : int WriteAsCFile(const char* filename, const char* varname,
978 : const char* str, int size, bool verbose = true);
979 :
980 :
981 : // Simple support to read a file into std::string.
982 : // On return, *exits tells whether the file existed.
983 : V8_EXPORT_PRIVATE std::string ReadFile(const char* filename, bool* exists,
984 : bool verbose = true);
985 : V8_EXPORT_PRIVATE std::string ReadFile(FILE* file, bool* exists,
986 : bool verbose = true);
987 :
988 0 : class StringBuilder : public SimpleStringBuilder {
989 : public:
990 : explicit StringBuilder(int size) : SimpleStringBuilder(size) { }
991 : StringBuilder(char* buffer, int size) : SimpleStringBuilder(buffer, size) { }
992 :
993 : // Add formatted contents to the builder just like printf().
994 : void PRINTF_FORMAT(2, 3) AddFormatted(const char* format, ...);
995 :
996 : // Add formatted contents like printf based on a va_list.
997 : void PRINTF_FORMAT(2, 0) AddFormattedList(const char* format, va_list list);
998 :
999 : private:
1000 : DISALLOW_IMPLICIT_CONSTRUCTORS(StringBuilder);
1001 : };
1002 :
1003 :
1004 : bool DoubleToBoolean(double d);
1005 :
1006 : template <typename Char>
1007 : bool TryAddIndexChar(uint32_t* index, Char c);
1008 :
1009 : template <typename Stream>
1010 : bool StringToArrayIndex(Stream* stream, uint32_t* index);
1011 :
1012 : // Returns the current stack top. Works correctly with ASAN and SafeStack.
1013 : // GetCurrentStackPosition() should not be inlined, because it works on stack
1014 : // frames if it were inlined into a function with a huge stack frame it would
1015 : // return an address significantly above the actual current stack position.
1016 : V8_EXPORT_PRIVATE V8_NOINLINE uintptr_t GetCurrentStackPosition();
1017 :
1018 : static inline uint16_t ByteReverse16(uint16_t value) {
1019 : #if V8_HAS_BUILTIN_BSWAP16
1020 : return __builtin_bswap16(value);
1021 : #else
1022 : return value << 8 | (value >> 8 & 0x00FF);
1023 : #endif
1024 : }
1025 :
1026 : static inline uint32_t ByteReverse32(uint32_t value) {
1027 : #if V8_HAS_BUILTIN_BSWAP32
1028 : return __builtin_bswap32(value);
1029 : #else
1030 : return value << 24 |
1031 : ((value << 8) & 0x00FF0000) |
1032 : ((value >> 8) & 0x0000FF00) |
1033 : ((value >> 24) & 0x00000FF);
1034 : #endif
1035 : }
1036 :
1037 : static inline uint64_t ByteReverse64(uint64_t value) {
1038 : #if V8_HAS_BUILTIN_BSWAP64
1039 : return __builtin_bswap64(value);
1040 : #else
1041 : size_t bits_of_v = sizeof(value) * kBitsPerByte;
1042 : return value << (bits_of_v - 8) |
1043 : ((value << (bits_of_v - 24)) & 0x00FF000000000000) |
1044 : ((value << (bits_of_v - 40)) & 0x0000FF0000000000) |
1045 : ((value << (bits_of_v - 56)) & 0x000000FF00000000) |
1046 : ((value >> (bits_of_v - 56)) & 0x00000000FF000000) |
1047 : ((value >> (bits_of_v - 40)) & 0x0000000000FF0000) |
1048 : ((value >> (bits_of_v - 24)) & 0x000000000000FF00) |
1049 : ((value >> (bits_of_v - 8)) & 0x00000000000000FF);
1050 : #endif
1051 : }
1052 :
1053 : template <typename V>
1054 : static inline V ByteReverse(V value) {
1055 : size_t size_of_v = sizeof(value);
1056 : switch (size_of_v) {
1057 : case 1:
1058 : return value;
1059 : case 2:
1060 : return static_cast<V>(ByteReverse16(static_cast<uint16_t>(value)));
1061 : case 4:
1062 : return static_cast<V>(ByteReverse32(static_cast<uint32_t>(value)));
1063 : case 8:
1064 : return static_cast<V>(ByteReverse64(static_cast<uint64_t>(value)));
1065 : default:
1066 : UNREACHABLE();
1067 : }
1068 : }
1069 :
1070 : V8_EXPORT_PRIVATE bool PassesFilter(Vector<const char> name,
1071 : Vector<const char> filter);
1072 :
1073 : // Zap the specified area with a specific byte pattern. This currently defaults
1074 : // to int3 on x64 and ia32. On other architectures this will produce unspecified
1075 : // instruction sequences.
1076 : // TODO(jgruber): Better support for other architectures.
1077 : V8_INLINE void ZapCode(Address addr, size_t size_in_bytes) {
1078 : static constexpr int kZapByte = 0xCC;
1079 0 : std::memset(reinterpret_cast<void*>(addr), kZapByte, size_in_bytes);
1080 : }
1081 :
1082 : } // namespace internal
1083 : } // namespace v8
1084 :
1085 : #endif // V8_UTILS_H_
|