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 75533074 : c -= '0';
41 75533074 : if (static_cast<unsigned>(c) <= 9) return c;
42 8094853 : c = (c | 0x20) - ('a' - '0'); // detect 0x11..0x16 and 0x31..0x36.
43 8094853 : 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 37298 : 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 6557128478 : 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 6366774 : 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 9426 : if (index > max) {
83 : *length = 0;
84 : return false;
85 : }
86 8102 : T avail = max - index;
87 : bool oob = *length > avail;
88 8102 : if (oob) *length = avail;
89 8102 : 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 21091 : 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 17986 : CHECK_BIGGER(32)
110 21091 : CHECK_BIGGER(16)
111 21091 : CHECK_BIGGER(8)
112 21091 : CHECK_BIGGER(4)
113 : #undef CHECK_BIGGER
114 21091 : switch (x) {
115 0 : default: UNREACHABLE();
116 : case 8:
117 1513 : bits++;
118 : V8_FALLTHROUGH;
119 : case 4:
120 9620 : bits++;
121 : V8_FALLTHROUGH;
122 : case 2:
123 13500 : bits++;
124 : V8_FALLTHROUGH;
125 : case 1: break;
126 : }
127 : DCHECK_EQ(T{1} << bits, original_x);
128 21091 : 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 194523652 : 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 376830904 : return a < b ? a : b;
193 : }
194 :
195 : // Returns the maximum of the two parameters according to JavaScript semantics.
196 : template <typename T>
197 427940 : T JSMax(T x, T y) {
198 427940 : if (std::isnan(x)) return x;
199 419144 : if (std::isnan(y)) return y;
200 821120 : if (std::signbit(x) < std::signbit(y)) return x;
201 309832 : return x > y ? x : y;
202 : }
203 :
204 : // Returns the maximum of the two parameters according to JavaScript semantics.
205 : template <typename T>
206 427940 : T JSMin(T x, T y) {
207 427940 : if (std::isnan(x)) return x;
208 419144 : if (std::isnan(y)) return y;
209 821120 : if (std::signbit(x) < std::signbit(y)) return y;
210 309832 : 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 5868 : unsignedT x = static_cast<unsignedT>(a);
222 5868 : unsignedT y = static_cast<unsignedT>(a >> (sizeof(T) * 8 - 1));
223 5868 : 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 724270 : 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 82639508 : return (static_cast<U>(value) & ~static_cast<U>(kMax)) == 0;
325 : }
326 :
327 : // Returns a type U with the bit field value encoded.
328 23496 : static constexpr U encode(T value) {
329 : #if V8_CAN_HAVE_DCHECK_IN_CONSTEXPR
330 : DCHECK(is_valid(value));
331 : #endif
332 5617448670 : return static_cast<U>(value) << shift;
333 : }
334 :
335 : // Returns a type U with the bit field value updated.
336 5856 : static constexpr U update(U previous, T value) {
337 5938958325 : return (previous & ~kMask) | encode(value);
338 : }
339 :
340 : // Extracts the bit field from the value.
341 : static constexpr T decode(U value) {
342 48904309494 : 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 6899444 : if (items == 0) return 0;
415 5864552 : 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 70161602 : 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 44259053 : 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 25906719 : int set_bits = (static_cast<int>(value) << shift_value);
432 25906719 : return (previous & ~(kMask << shift_value)) | set_bits;
433 : }
434 :
435 70161602 : 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 : // ----------------------------------------------------------------------------
463 : // Hash function.
464 :
465 : static const uint64_t kZeroHashSeed = 0;
466 :
467 : // Thomas Wang, Integer Hash Functions.
468 : // http://www.concentric.net/~Ttwang/tech/inthash.htm`
469 : inline uint32_t ComputeUnseededHash(uint32_t key) {
470 : uint32_t hash = key;
471 90050315 : hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1;
472 90050315 : hash = hash ^ (hash >> 12);
473 90050315 : hash = hash + (hash << 2);
474 90050315 : hash = hash ^ (hash >> 4);
475 90050315 : hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11);
476 90050315 : hash = hash ^ (hash >> 16);
477 33399108 : return hash & 0x3fffffff;
478 : }
479 :
480 : inline uint32_t ComputeLongHash(uint64_t key) {
481 : uint64_t hash = key;
482 150208577 : hash = ~hash + (hash << 18); // hash = (hash << 18) - hash - 1;
483 150208577 : hash = hash ^ (hash >> 31);
484 150208577 : hash = hash * 21; // hash = (hash + (hash << 2)) + (hash << 4);
485 150208577 : hash = hash ^ (hash >> 11);
486 150208577 : hash = hash + (hash << 6);
487 150208577 : hash = hash ^ (hash >> 22);
488 150208577 : return static_cast<uint32_t>(hash & 0x3fffffff);
489 : }
490 :
491 : inline uint32_t ComputeSeededHash(uint32_t key, uint64_t seed) {
492 : #ifdef V8_USE_SIPHASH
493 : return halfsiphash(key, seed);
494 : #else
495 146177273 : return ComputeLongHash(static_cast<uint64_t>(key) ^ seed);
496 : #endif // V8_USE_SIPHASH
497 : }
498 :
499 : inline uint32_t ComputePointerHash(void* ptr) {
500 21713 : return ComputeUnseededHash(
501 : static_cast<uint32_t>(reinterpret_cast<intptr_t>(ptr)));
502 : }
503 :
504 : inline uint32_t ComputeAddressHash(Address address) {
505 10551837 : return ComputeUnseededHash(static_cast<uint32_t>(address & 0xFFFFFFFFul));
506 : }
507 :
508 : // ----------------------------------------------------------------------------
509 : // Miscellaneous
510 :
511 : // Memory offset for lower and higher bits in a 64 bit integer.
512 : #if defined(V8_TARGET_LITTLE_ENDIAN)
513 : static const int kInt64LowerHalfMemoryOffset = 0;
514 : static const int kInt64UpperHalfMemoryOffset = 4;
515 : #elif defined(V8_TARGET_BIG_ENDIAN)
516 : static const int kInt64LowerHalfMemoryOffset = 4;
517 : static const int kInt64UpperHalfMemoryOffset = 0;
518 : #endif // V8_TARGET_LITTLE_ENDIAN
519 :
520 : // A static resource holds a static instance that can be reserved in
521 : // a local scope using an instance of Access. Attempts to re-reserve
522 : // the instance will cause an error.
523 : template <typename T>
524 : class StaticResource {
525 : public:
526 61531 : StaticResource() : is_reserved_(false) {}
527 :
528 : private:
529 : template <typename S> friend class Access;
530 : T instance_;
531 : bool is_reserved_;
532 : };
533 :
534 :
535 : // Locally scoped access to a static resource.
536 : template <typename T>
537 : class Access {
538 : public:
539 : explicit Access(StaticResource<T>* resource)
540 : : resource_(resource)
541 10 : , instance_(&resource->instance_) {
542 : DCHECK(!resource->is_reserved_);
543 10 : resource->is_reserved_ = true;
544 : }
545 :
546 : ~Access() {
547 10 : resource_->is_reserved_ = false;
548 : resource_ = nullptr;
549 : instance_ = nullptr;
550 : }
551 :
552 : T* value() { return instance_; }
553 : T* operator -> () { return instance_; }
554 :
555 : private:
556 : StaticResource<T>* resource_;
557 : T* instance_;
558 : };
559 :
560 : // A pointer that can only be set once and doesn't allow NULL values.
561 : template<typename T>
562 : class SetOncePointer {
563 : public:
564 4055266 : SetOncePointer() = default;
565 :
566 7623654 : bool is_set() const { return pointer_ != nullptr; }
567 :
568 : T* get() const {
569 : DCHECK_NOT_NULL(pointer_);
570 9897015 : return pointer_;
571 : }
572 :
573 : void set(T* value) {
574 : DCHECK(pointer_ == nullptr && value != nullptr);
575 1742444 : pointer_ = value;
576 : }
577 :
578 : T* operator=(T* value) {
579 : set(value);
580 : return value;
581 : }
582 :
583 73741 : bool operator==(std::nullptr_t) const { return pointer_ == nullptr; }
584 : bool operator!=(std::nullptr_t) const { return pointer_ != nullptr; }
585 :
586 : private:
587 : T* pointer_ = nullptr;
588 : };
589 :
590 : // Compare 8bit/16bit chars to 8bit/16bit chars.
591 : template <typename lchar, typename rchar>
592 : inline int CompareCharsUnsigned(const lchar* lhs, const rchar* rhs,
593 : size_t chars) {
594 820110 : const lchar* limit = lhs + chars;
595 : if (sizeof(*lhs) == sizeof(char) && sizeof(*rhs) == sizeof(char)) {
596 : // memcmp compares byte-by-byte, yielding wrong results for two-byte
597 : // strings on little-endian systems.
598 203130614 : return memcmp(lhs, rhs, chars);
599 : }
600 20376369 : while (lhs < limit) {
601 19574740 : int r = static_cast<int>(*lhs) - static_cast<int>(*rhs);
602 19574740 : if (r != 0) return r;
603 19556259 : ++lhs;
604 19556259 : ++rhs;
605 : }
606 : return 0;
607 : }
608 :
609 : template <typename lchar, typename rchar>
610 : inline int CompareChars(const lchar* lhs, const rchar* rhs, size_t chars) {
611 : DCHECK_LE(sizeof(lchar), 2);
612 : DCHECK_LE(sizeof(rchar), 2);
613 : if (sizeof(lchar) == 1) {
614 : if (sizeof(rchar) == 1) {
615 : return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
616 : reinterpret_cast<const uint8_t*>(rhs),
617 : chars);
618 : } else {
619 : return CompareCharsUnsigned(reinterpret_cast<const uint8_t*>(lhs),
620 : reinterpret_cast<const uint16_t*>(rhs),
621 : chars);
622 : }
623 : } else {
624 : if (sizeof(rchar) == 1) {
625 : return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
626 : reinterpret_cast<const uint8_t*>(rhs),
627 : chars);
628 : } else {
629 : return CompareCharsUnsigned(reinterpret_cast<const uint16_t*>(lhs),
630 : reinterpret_cast<const uint16_t*>(rhs),
631 : chars);
632 : }
633 : }
634 : }
635 :
636 :
637 : // Calculate 10^exponent.
638 : inline int TenToThe(int exponent) {
639 : DCHECK_LE(exponent, 9);
640 : DCHECK_GE(exponent, 1);
641 : int answer = 10;
642 : for (int i = 1; i < exponent; i++) answer *= 10;
643 : return answer;
644 : }
645 :
646 :
647 : template<typename ElementType, int NumElements>
648 : class EmbeddedContainer {
649 : public:
650 : EmbeddedContainer() : elems_() { }
651 :
652 : int length() const { return NumElements; }
653 : const ElementType& operator[](int i) const {
654 : DCHECK(i < length());
655 : return elems_[i];
656 : }
657 : ElementType& operator[](int i) {
658 : DCHECK(i < length());
659 : return elems_[i];
660 : }
661 :
662 : private:
663 : ElementType elems_[NumElements];
664 : };
665 :
666 :
667 : template<typename ElementType>
668 : class EmbeddedContainer<ElementType, 0> {
669 : public:
670 : int length() const { return 0; }
671 : const ElementType& operator[](int i) const {
672 : UNREACHABLE();
673 : static ElementType t = 0;
674 : return t;
675 : }
676 : ElementType& operator[](int i) {
677 : UNREACHABLE();
678 : static ElementType t = 0;
679 : return t;
680 : }
681 : };
682 :
683 :
684 : // Helper class for building result strings in a character buffer. The
685 : // purpose of the class is to use safe operations that checks the
686 : // buffer bounds on all operations in debug mode.
687 : // This simple base class does not allow formatted output.
688 : class SimpleStringBuilder {
689 : public:
690 : // Create a string builder with a buffer of the given size. The
691 : // buffer is allocated through NewArray<char> and must be
692 : // deallocated by the caller of Finalize().
693 : explicit SimpleStringBuilder(int size);
694 :
695 : SimpleStringBuilder(char* buffer, int size)
696 2259650 : : buffer_(buffer, size), position_(0) { }
697 :
698 1139765 : ~SimpleStringBuilder() { if (!is_finalized()) Finalize(); }
699 :
700 : int size() const { return buffer_.length(); }
701 :
702 : // Get the current position in the builder.
703 : int position() const {
704 : DCHECK(!is_finalized());
705 : return position_;
706 : }
707 :
708 : // Reset the position.
709 0 : void Reset() { position_ = 0; }
710 :
711 : // Add a single character to the builder. It is not allowed to add
712 : // 0-characters; use the Finalize() method to terminate the string
713 : // instead.
714 : void AddCharacter(char c) {
715 : DCHECK_NE(c, '\0');
716 : DCHECK(!is_finalized() && position_ < buffer_.length());
717 4228176 : buffer_[position_++] = c;
718 : }
719 :
720 : // Add an entire string to the builder. Uses strlen() internally to
721 : // compute the length of the input string.
722 : void AddString(const char* s);
723 :
724 : // Add the first 'n' characters of the given 0-terminated string 's' to the
725 : // builder. The input string must have enough characters.
726 : void AddSubstring(const char* s, int n);
727 :
728 : // Add character padding to the builder. If count is non-positive,
729 : // nothing is added to the builder.
730 : void AddPadding(char c, int count);
731 :
732 : // Add the decimal representation of the value.
733 : void AddDecimalInteger(int value);
734 :
735 : // Finalize the string by 0-terminating it and returning the buffer.
736 : char* Finalize();
737 :
738 : protected:
739 : Vector<char> buffer_;
740 : int position_;
741 :
742 : bool is_finalized() const { return position_ < 0; }
743 :
744 : private:
745 : DISALLOW_IMPLICIT_CONSTRUCTORS(SimpleStringBuilder);
746 : };
747 :
748 : // Bit field extraction.
749 : inline uint32_t unsigned_bitextract_32(int msb, int lsb, uint32_t x) {
750 : return (x >> lsb) & ((1 << (1 + msb - lsb)) - 1);
751 : }
752 :
753 : inline uint64_t unsigned_bitextract_64(int msb, int lsb, uint64_t x) {
754 : return (x >> lsb) & ((static_cast<uint64_t>(1) << (1 + msb - lsb)) - 1);
755 : }
756 :
757 : inline int32_t signed_bitextract_32(int msb, int lsb, int32_t x) {
758 : return (x << (31 - msb)) >> (lsb + 31 - msb);
759 : }
760 :
761 : inline int signed_bitextract_64(int msb, int lsb, int x) {
762 : // TODO(jbramley): This is broken for big bitfields.
763 : return (x << (63 - msb)) >> (lsb + 63 - msb);
764 : }
765 :
766 : // Check number width.
767 : inline bool is_intn(int64_t x, unsigned n) {
768 : DCHECK((0 < n) && (n < 64));
769 : int64_t limit = static_cast<int64_t>(1) << (n - 1);
770 72309968 : return (-limit <= x) && (x < limit);
771 : }
772 :
773 : inline bool is_uintn(int64_t x, unsigned n) {
774 : DCHECK((0 < n) && (n < (sizeof(x) * kBitsPerByte)));
775 19349431 : return !(x >> n);
776 : }
777 :
778 : template <class T>
779 : inline T truncate_to_intn(T x, unsigned n) {
780 : DCHECK((0 < n) && (n < (sizeof(x) * kBitsPerByte)));
781 : return (x & ((static_cast<T>(1) << n) - 1));
782 : }
783 :
784 : #define INT_1_TO_63_LIST(V) \
785 : V(1) V(2) V(3) V(4) V(5) V(6) V(7) V(8) \
786 : V(9) V(10) V(11) V(12) V(13) V(14) V(15) V(16) \
787 : V(17) V(18) V(19) V(20) V(21) V(22) V(23) V(24) \
788 : V(25) V(26) V(27) V(28) V(29) V(30) V(31) V(32) \
789 : V(33) V(34) V(35) V(36) V(37) V(38) V(39) V(40) \
790 : V(41) V(42) V(43) V(44) V(45) V(46) V(47) V(48) \
791 : V(49) V(50) V(51) V(52) V(53) V(54) V(55) V(56) \
792 : V(57) V(58) V(59) V(60) V(61) V(62) V(63)
793 :
794 : #define DECLARE_IS_INT_N(N) \
795 : inline bool is_int##N(int64_t x) { return is_intn(x, N); }
796 : #define DECLARE_IS_UINT_N(N) \
797 : template <class T> \
798 : inline bool is_uint##N(T x) { return is_uintn(x, N); }
799 : #define DECLARE_TRUNCATE_TO_INT_N(N) \
800 : template <class T> \
801 : inline T truncate_to_int##N(T x) { return truncate_to_intn(x, N); }
802 : INT_1_TO_63_LIST(DECLARE_IS_INT_N)
803 5414431 : INT_1_TO_63_LIST(DECLARE_IS_UINT_N)
804 : INT_1_TO_63_LIST(DECLARE_TRUNCATE_TO_INT_N)
805 : #undef DECLARE_IS_INT_N
806 : #undef DECLARE_IS_UINT_N
807 : #undef DECLARE_TRUNCATE_TO_INT_N
808 :
809 : // clang-format off
810 : #define INT_0_TO_127_LIST(V) \
811 : V(0) V(1) V(2) V(3) V(4) V(5) V(6) V(7) V(8) V(9) \
812 : V(10) V(11) V(12) V(13) V(14) V(15) V(16) V(17) V(18) V(19) \
813 : V(20) V(21) V(22) V(23) V(24) V(25) V(26) V(27) V(28) V(29) \
814 : V(30) V(31) V(32) V(33) V(34) V(35) V(36) V(37) V(38) V(39) \
815 : V(40) V(41) V(42) V(43) V(44) V(45) V(46) V(47) V(48) V(49) \
816 : V(50) V(51) V(52) V(53) V(54) V(55) V(56) V(57) V(58) V(59) \
817 : V(60) V(61) V(62) V(63) V(64) V(65) V(66) V(67) V(68) V(69) \
818 : V(70) V(71) V(72) V(73) V(74) V(75) V(76) V(77) V(78) V(79) \
819 : V(80) V(81) V(82) V(83) V(84) V(85) V(86) V(87) V(88) V(89) \
820 : V(90) V(91) V(92) V(93) V(94) V(95) V(96) V(97) V(98) V(99) \
821 : V(100) V(101) V(102) V(103) V(104) V(105) V(106) V(107) V(108) V(109) \
822 : V(110) V(111) V(112) V(113) V(114) V(115) V(116) V(117) V(118) V(119) \
823 : V(120) V(121) V(122) V(123) V(124) V(125) V(126) V(127)
824 : // clang-format on
825 :
826 : class FeedbackSlot {
827 : public:
828 301494994 : FeedbackSlot() : id_(kInvalidSlot) {}
829 2163462 : explicit FeedbackSlot(int id) : id_(id) {}
830 :
831 1513286 : int ToInt() const { return id_; }
832 :
833 : static FeedbackSlot Invalid() { return FeedbackSlot(); }
834 2699334 : bool IsInvalid() const { return id_ == kInvalidSlot; }
835 :
836 63 : bool operator==(FeedbackSlot that) const { return this->id_ == that.id_; }
837 : bool operator!=(FeedbackSlot that) const { return !(*this == that); }
838 :
839 189 : friend size_t hash_value(FeedbackSlot slot) { return slot.ToInt(); }
840 : friend std::ostream& operator<<(std::ostream& os, FeedbackSlot);
841 :
842 : private:
843 : static const int kInvalidSlot = -1;
844 :
845 : int id_;
846 : };
847 :
848 :
849 : class BailoutId {
850 : public:
851 7250525 : explicit BailoutId(int id) : id_(id) { }
852 3898615 : int ToInt() const { return id_; }
853 :
854 : static BailoutId None() { return BailoutId(kNoneId); }
855 : static BailoutId ScriptContext() { return BailoutId(kScriptContextId); }
856 : static BailoutId FunctionContext() { return BailoutId(kFunctionContextId); }
857 : static BailoutId FunctionEntry() { return BailoutId(kFunctionEntryId); }
858 : static BailoutId Declarations() { return BailoutId(kDeclarationsId); }
859 : static BailoutId FirstUsable() { return BailoutId(kFirstUsableId); }
860 : static BailoutId StubEntry() { return BailoutId(kStubEntryId); }
861 :
862 : // Special bailout id support for deopting into the {JSConstructStub} stub.
863 : // The following hard-coded deoptimization points are supported by the stub:
864 : // - {ConstructStubCreate} maps to {construct_stub_create_deopt_pc_offset}.
865 : // - {ConstructStubInvoke} maps to {construct_stub_invoke_deopt_pc_offset}.
866 : static BailoutId ConstructStubCreate() { return BailoutId(1); }
867 : static BailoutId ConstructStubInvoke() { return BailoutId(2); }
868 : bool IsValidForConstructStub() const {
869 : return id_ == ConstructStubCreate().ToInt() ||
870 : id_ == ConstructStubInvoke().ToInt();
871 : }
872 :
873 11092249 : bool IsNone() const { return id_ == kNoneId; }
874 2 : 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 : friend class Builtins;
881 :
882 : static const int kNoneId = -1;
883 :
884 : // Using 0 could disguise errors.
885 : static const int kScriptContextId = 1;
886 : static const int kFunctionContextId = 2;
887 : static const int kFunctionEntryId = 3;
888 :
889 : // This AST id identifies the point after the declarations have been visited.
890 : // We need it to capture the environment effects of declarations that emit
891 : // 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 : // Builtin continuations bailout ids start here. If you need to add a
901 : // non-builtin BailoutId, add it before this id so that this Id has the
902 : // highest number.
903 : static const int kFirstBuiltinContinuationId = 7;
904 :
905 : int id_;
906 : };
907 :
908 :
909 : // ----------------------------------------------------------------------------
910 : // I/O support.
911 :
912 : // Our version of printf().
913 : V8_EXPORT_PRIVATE void PRINTF_FORMAT(1, 2) PrintF(const char* format, ...);
914 : void PRINTF_FORMAT(2, 3) PrintF(FILE* out, const char* format, ...);
915 :
916 : // Prepends the current process ID to the output.
917 : void PRINTF_FORMAT(1, 2) PrintPID(const char* format, ...);
918 :
919 : // Prepends the current process ID and given isolate pointer to the output.
920 : void PRINTF_FORMAT(2, 3) PrintIsolate(void* isolate, const char* format, ...);
921 :
922 : // Safe formatting print. Ensures that str is always null-terminated.
923 : // Returns the number of chars written, or -1 if output was truncated.
924 : int PRINTF_FORMAT(2, 3) SNPrintF(Vector<char> str, const char* format, ...);
925 : V8_EXPORT_PRIVATE int PRINTF_FORMAT(2, 0)
926 : VSNPrintF(Vector<char> str, const char* format, va_list args);
927 :
928 : void StrNCpy(Vector<char> dest, const char* src, size_t n);
929 :
930 : // Our version of fflush.
931 : void Flush(FILE* out);
932 :
933 : inline void Flush() {
934 : Flush(stdout);
935 : }
936 :
937 :
938 : // Read a line of characters after printing the prompt to stdout. The resulting
939 : // char* needs to be disposed off with DeleteArray by the caller.
940 : char* ReadLine(const char* prompt);
941 :
942 :
943 : // Append size chars from str to the file given by filename.
944 : // The file is overwritten. Returns the number of chars written.
945 : int AppendChars(const char* filename,
946 : const char* str,
947 : int size,
948 : bool verbose = true);
949 :
950 :
951 : // Write size chars from str to the file given by filename.
952 : // The file is overwritten. Returns the number of chars written.
953 : int WriteChars(const char* filename,
954 : const char* str,
955 : int size,
956 : bool verbose = true);
957 :
958 :
959 : // Write size bytes to the file given by filename.
960 : // The file is overwritten. Returns the number of bytes written.
961 : int WriteBytes(const char* filename,
962 : const byte* bytes,
963 : int size,
964 : bool verbose = true);
965 :
966 :
967 : // Write the C code
968 : // const char* <varname> = "<str>";
969 : // const int <varname>_len = <len>;
970 : // to the file given by filename. Only the first len chars are written.
971 : int WriteAsCFile(const char* filename, const char* varname,
972 : const char* str, int size, bool verbose = true);
973 :
974 :
975 : // Simple support to read a file into std::string.
976 : // On return, *exits tells whether the file existed.
977 : V8_EXPORT_PRIVATE std::string ReadFile(const char* filename, bool* exists,
978 : bool verbose = true);
979 : std::string ReadFile(FILE* file, bool* exists, bool verbose = true);
980 :
981 0 : class StringBuilder : public SimpleStringBuilder {
982 : public:
983 : explicit StringBuilder(int size) : SimpleStringBuilder(size) { }
984 : StringBuilder(char* buffer, int size) : SimpleStringBuilder(buffer, size) { }
985 :
986 : // Add formatted contents to the builder just like printf().
987 : void PRINTF_FORMAT(2, 3) AddFormatted(const char* format, ...);
988 :
989 : // Add formatted contents like printf based on a va_list.
990 : void PRINTF_FORMAT(2, 0) AddFormattedList(const char* format, va_list list);
991 :
992 : private:
993 : DISALLOW_IMPLICIT_CONSTRUCTORS(StringBuilder);
994 : };
995 :
996 :
997 : bool DoubleToBoolean(double d);
998 :
999 : template <typename Char>
1000 : bool TryAddIndexChar(uint32_t* index, Char c);
1001 :
1002 : template <typename Stream>
1003 : bool StringToArrayIndex(Stream* stream, uint32_t* index);
1004 :
1005 : // Returns the current stack top. Works correctly with ASAN and SafeStack.
1006 : // GetCurrentStackPosition() should not be inlined, because it works on stack
1007 : // frames if it were inlined into a function with a huge stack frame it would
1008 : // return an address significantly above the actual current stack position.
1009 : 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 : #else
1015 : return value << 8 | (value >> 8 & 0x00FF);
1016 : #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 : return value << 24 |
1024 : ((value << 8) & 0x00FF0000) |
1025 : ((value >> 8) & 0x0000FF00) |
1026 : ((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 : return value << (bits_of_v - 8) |
1036 : ((value << (bits_of_v - 24)) & 0x00FF000000000000) |
1037 : ((value << (bits_of_v - 40)) & 0x0000FF0000000000) |
1038 : ((value << (bits_of_v - 56)) & 0x000000FF00000000) |
1039 : ((value >> (bits_of_v - 56)) & 0x00000000FF000000) |
1040 : ((value >> (bits_of_v - 40)) & 0x0000000000FF0000) |
1041 : ((value >> (bits_of_v - 24)) & 0x000000000000FF00) |
1042 : ((value >> (bits_of_v - 8)) & 0x00000000000000FF);
1043 : #endif
1044 : }
1045 :
1046 : template <typename V>
1047 : static inline V ByteReverse(V value) {
1048 : size_t size_of_v = sizeof(value);
1049 : switch (size_of_v) {
1050 : case 1:
1051 : return value;
1052 : case 2:
1053 : return static_cast<V>(ByteReverse16(static_cast<uint16_t>(value)));
1054 : case 4:
1055 : return static_cast<V>(ByteReverse32(static_cast<uint32_t>(value)));
1056 : case 8:
1057 : return static_cast<V>(ByteReverse64(static_cast<uint64_t>(value)));
1058 : default:
1059 : UNREACHABLE();
1060 : }
1061 : }
1062 :
1063 : V8_EXPORT_PRIVATE bool PassesFilter(Vector<const char> name,
1064 : Vector<const char> filter);
1065 :
1066 : // Zap the specified area with a specific byte pattern. This currently defaults
1067 : // to int3 on x64 and ia32. On other architectures this will produce unspecified
1068 : // instruction sequences.
1069 : // TODO(jgruber): Better support for other architectures.
1070 : V8_INLINE void ZapCode(Address addr, size_t size_in_bytes) {
1071 : static constexpr int kZapByte = 0xCC;
1072 0 : std::memset(reinterpret_cast<void*>(addr), kZapByte, size_in_bytes);
1073 : }
1074 :
1075 : } // namespace internal
1076 : } // namespace v8
1077 :
1078 : #endif // V8_UTILS_H_
|
