1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_PLATFORM_UTILS_H_
6#define RUNTIME_PLATFORM_UTILS_H_
7
8#include <limits>
9#include <memory>
10#include <type_traits>
11
12#include "platform/assert.h"
13#include "platform/globals.h"
14
15namespace dart {
16
17class Utils {
18 public:
19 template <typename T>
20 static inline T Minimum(T x, T y) {
21 return x < y ? x : y;
22 }
23
24 template <typename T>
25 static constexpr inline T Maximum(T x, T y) {
26 return x > y ? x : y;
27 }
28
29 // Calculates absolute value of a given signed integer.
30 // `x` must not be equal to minimum value representable by `T`
31 // as its absolute value is out of range.
32 template <typename T>
33 static inline T Abs(T x) {
34 // Note: as a general rule, it is not OK to use STL in Dart VM.
35 // However, std::numeric_limits<T>::min() and max() are harmless
36 // and worthwhile exception from this rule.
37 ASSERT(x != std::numeric_limits<T>::min());
38 if (x < 0) return -x;
39 return x;
40 }
41
42 // Calculates absolute value of a given signed integer with saturation.
43 // If `x` equals to minimum value representable by `T`, then
44 // absolute value is saturated to the maximum value representable by `T`.
45 template <typename T>
46 static inline T AbsWithSaturation(T x) {
47 if (x < 0) {
48 // Note: as a general rule, it is not OK to use STL in Dart VM.
49 // However, std::numeric_limits<T>::min() and max() are harmless
50 // and worthwhile exception from this rule.
51 if (x == std::numeric_limits<T>::min()) {
52 return std::numeric_limits<T>::max();
53 }
54 return -x;
55 }
56 return x;
57 }
58
59 template <typename T>
60 static constexpr bool IsPowerOfTwo(T x) {
61 return ((x & (x - 1)) == 0) && (x != 0);
62 }
63
64 template <typename T>
65 static inline int ShiftForPowerOfTwo(T x) {
66 ASSERT(IsPowerOfTwo(x));
67 int num_shifts = 0;
68 while (x > 1) {
69 num_shifts++;
70 x = x >> 1;
71 }
72 return num_shifts;
73 }
74
75 template <typename T>
76 static constexpr bool IsAligned(T x,
77 uintptr_t alignment,
78 uintptr_t offset = 0) {
79 ASSERT(IsPowerOfTwo(alignment));
80 ASSERT(offset < alignment);
81 return (x & (alignment - 1)) == offset;
82 }
83
84 template <typename T>
85 static constexpr bool IsAligned(T* x,
86 uintptr_t alignment,
87 uintptr_t offset = 0) {
88 return IsAligned(x: reinterpret_cast<uword>(x), alignment, offset);
89 }
90
91 template <typename T>
92 static constexpr inline T RoundDown(T x, intptr_t alignment) {
93 ASSERT(IsPowerOfTwo(alignment));
94 return (x & -alignment);
95 }
96
97 template <typename T>
98 static inline T* RoundDown(T* x, intptr_t alignment) {
99 return reinterpret_cast<T*>(
100 RoundDown(x: reinterpret_cast<uword>(x), alignment));
101 }
102
103 template <typename T>
104 static constexpr inline T RoundUp(T x,
105 uintptr_t alignment,
106 uintptr_t offset = 0) {
107 ASSERT(offset < alignment);
108 return RoundDown(x + alignment - 1 + offset, alignment) - offset;
109 }
110
111 template <typename T>
112 static inline T* RoundUp(T* x, uintptr_t alignment, uintptr_t offset = 0) {
113 return reinterpret_cast<T*>(
114 RoundUp(x: reinterpret_cast<uword>(x), alignment, offset));
115 }
116
117 // Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
118 // figure 3-3, page 48, where the function is called clp2.
119 static constexpr uintptr_t RoundUpToPowerOfTwo(uintptr_t x) {
120 x = x - 1;
121 x = x | (x >> 1);
122 x = x | (x >> 2);
123 x = x | (x >> 4);
124 x = x | (x >> 8);
125 x = x | (x >> 16);
126#if defined(ARCH_IS_64_BIT)
127 x = x | (x >> 32);
128#endif // defined(ARCH_IS_64_BIT)
129 return x + 1;
130 }
131
132 static constexpr int CountOneBits64(uint64_t x) {
133 // Apparently there are x64 chips without popcount.
134#if __GNUC__ && !defined(HOST_ARCH_IA32) && !defined(HOST_ARCH_X64)
135 return __builtin_popcountll(x);
136#else
137 x = x - ((x >> 1) & 0x5555555555555555);
138 x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
139 x = (((x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f) * 0x0101010101010101) >> 56;
140 return x;
141#endif
142 }
143
144 static constexpr int CountOneBits32(uint32_t x) {
145 // Apparently there are x64 chips without popcount.
146#if __GNUC__ && !defined(HOST_ARCH_IA32) && !defined(HOST_ARCH_X64)
147 return __builtin_popcount(x);
148#else
149 // Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
150 // figure 5-2, page 66, where the function is called pop.
151 x = x - ((x >> 1) & 0x55555555);
152 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
153 x = (x + (x >> 4)) & 0x0F0F0F0F;
154 x = x + (x >> 8);
155 x = x + (x >> 16);
156 return static_cast<int>(x & 0x0000003F);
157#endif
158 }
159
160 static constexpr int CountOneBitsWord(uword x) {
161#ifdef ARCH_IS_64_BIT
162 return CountOneBits64(x);
163#else
164 return CountOneBits32(x);
165#endif
166 }
167
168 // TODO(koda): Compare to flsll call/intrinsic.
169 static constexpr size_t HighestBit(int64_t v) {
170 uint64_t x = static_cast<uint64_t>((v > 0) ? v : -v);
171 uint64_t t = 0;
172 size_t r = 0;
173 if ((t = x >> 32) != 0) {
174 x = t;
175 r += 32;
176 }
177 if ((t = x >> 16) != 0) {
178 x = t;
179 r += 16;
180 }
181 if ((t = x >> 8) != 0) {
182 x = t;
183 r += 8;
184 }
185 if ((t = x >> 4) != 0) {
186 x = t;
187 r += 4;
188 }
189 if ((t = x >> 2) != 0) {
190 x = t;
191 r += 2;
192 }
193 if (x > 1) r += 1;
194 return r;
195 }
196
197 static constexpr size_t BitLength(int64_t value) {
198 // Flip bits if negative (-1 becomes 0).
199 value ^= value >> (8 * sizeof(value) - 1);
200 return (value == 0) ? 0 : (Utils::HighestBit(v: value) + 1);
201 }
202
203 static int CountLeadingZeros32(uint32_t x) {
204#if defined(DART_HOST_OS_WINDOWS)
205 unsigned long position; // NOLINT
206 return (_BitScanReverse(&position, x) == 0)
207 ? 32
208 : 31 - static_cast<int>(position);
209#else
210 return x == 0 ? 32 : __builtin_clz(x);
211#endif
212 }
213 static int CountLeadingZeros64(uint64_t x) {
214#if defined(DART_HOST_OS_WINDOWS)
215#if defined(ARCH_IS_32_BIT)
216 const uint32_t x_hi = static_cast<uint32_t>(x >> 32);
217 if (x_hi != 0) {
218 return CountLeadingZeros32(x_hi);
219 }
220 return 32 + CountLeadingZeros32(static_cast<uint32_t>(x));
221#else
222 unsigned long position; // NOLINT
223 return (_BitScanReverse64(&position, x) == 0)
224 ? 64
225 : 63 - static_cast<int>(position);
226#endif
227#else
228 return x == 0 ? 64 : __builtin_clzll(x);
229#endif
230 }
231 static int CountLeadingZerosWord(uword x) {
232#ifdef ARCH_IS_64_BIT
233 return CountLeadingZeros64(x);
234#else
235 return CountLeadingZeros32(x);
236#endif
237 }
238
239 static int CountTrailingZeros32(uint32_t x) {
240#if defined(DART_HOST_OS_WINDOWS)
241 unsigned long position; // NOLINT
242 return (_BitScanForward(&position, x) == 0) ? 32
243 : static_cast<int>(position);
244#else
245 return x == 0 ? 32 : __builtin_ctz(x);
246#endif
247 }
248 static int CountTrailingZeros64(uint64_t x) {
249#if defined(DART_HOST_OS_WINDOWS)
250#if defined(ARCH_IS_32_BIT)
251 const uint32_t x_lo = static_cast<uint32_t>(x);
252 if (x_lo != 0) {
253 return CountTrailingZeros32(x_lo);
254 }
255 return 32 + CountTrailingZeros32(static_cast<uint32_t>(x >> 32));
256#else
257 unsigned long position; // NOLINT
258 return (_BitScanForward64(&position, x) == 0) ? 64
259 : static_cast<int>(position);
260#endif
261#else
262 return x == 0 ? 64 : __builtin_ctzll(x);
263#endif
264 }
265 static int CountTrailingZerosWord(uword x) {
266#ifdef ARCH_IS_64_BIT
267 return CountTrailingZeros64(x);
268#else
269 return CountTrailingZeros32(x);
270#endif
271 }
272
273 static uint64_t ReverseBits64(uint64_t x);
274 static uint32_t ReverseBits32(uint32_t x);
275
276 static uword ReverseBitsWord(uword x) {
277#ifdef ARCH_IS_64_BIT
278 return ReverseBits64(x);
279#else
280 return ReverseBits32(x);
281#endif
282 }
283
284 // Computes magic numbers to implement DIV or MOD operator.
285 static void CalculateMagicAndShiftForDivRem(int64_t divisor,
286 int64_t* magic,
287 int64_t* shift);
288
289 // Computes a hash value for the given series of bytes.
290 static uint32_t StringHash(const void* data, int length);
291
292 // Computes a hash value for the given word.
293 static uint32_t WordHash(intptr_t key);
294
295 // Check whether an N-bit two's-complement representation can hold value.
296 template <typename T>
297 static inline bool IsInt(intptr_t N, T value) {
298 ASSERT(N >= 1);
299 constexpr intptr_t value_size_in_bits = kBitsPerByte * sizeof(T);
300 if constexpr (std::is_signed<T>::value) {
301 if (N >= value_size_in_bits) return true; // Trivially fits.
302 } else {
303 if (N > value_size_in_bits) return true; // Trivially fits.
304 if (N == value_size_in_bits) {
305 return static_cast<typename std::make_signed<T>::type>(value) >= 0;
306 }
307 }
308 const T limit = static_cast<T>(1) << (N - 1);
309 return (-limit <= value) && (value < limit);
310 }
311
312 template <typename T>
313 static inline bool IsUint(intptr_t N, T value) {
314 ASSERT(N >= 1);
315 constexpr intptr_t value_size_in_bits = kBitsPerByte * sizeof(T);
316 if constexpr (std::is_signed<T>::value) {
317 if (value < 0) return false; // Not an unsigned value.
318 if (N >= value_size_in_bits - 1) {
319 return true; // N can fit the magnitude bits.
320 }
321 } else {
322 if (N >= value_size_in_bits) return true; // Trivially fits.
323 }
324 const T limit = (static_cast<T>(1) << N) - 1;
325 return value <= limit;
326 }
327
328 // Check whether the magnitude of value fits in N bits. This differs from
329 // IsInt(N + 1, value) only in that this returns false for the minimum value
330 // of a N+1 bit two's complement value.
331 //
332 // Primarily used for testing whether a two's complement value can be used in
333 // a place where the sign is replaced with a marker that says whether the
334 // magnitude is added or subtracted, e.g., the U bit (bit 23) in some ARM7
335 // instructions.
336 template <typename T>
337 static inline bool MagnitudeIsUint(intptr_t N, T value) {
338 ASSERT(N >= 1);
339 if constexpr (std::is_signed<T>::value) {
340 using Unsigned = typename std::make_unsigned<T>::type;
341 if (value < 0) return IsUint<Unsigned>(N, -value);
342 }
343 return IsUint(N, value);
344 }
345
346 static inline int32_t Low16Bits(int32_t value) {
347 return static_cast<int32_t>(value & 0xffff);
348 }
349
350 static inline int32_t High16Bits(int32_t value) {
351 return static_cast<int32_t>(value >> 16);
352 }
353
354 static inline int32_t Low32Bits(int64_t value) {
355 return static_cast<int32_t>(value);
356 }
357
358 static inline int32_t High32Bits(int64_t value) {
359 return static_cast<int32_t>(value >> 32);
360 }
361
362 static inline int64_t LowHighTo64Bits(uint32_t low, int32_t high) {
363 return (static_cast<uint64_t>(high) << 32) | (low & 0x0ffffffffLL);
364 }
365
366 static inline constexpr bool IsAlphaNumeric(uint32_t c) {
367 return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') ||
368 IsDecimalDigit(c);
369 }
370
371 static inline constexpr bool IsDecimalDigit(uint32_t c) {
372 return ('0' <= c) && (c <= '9');
373 }
374
375 static bool IsHexDigit(char c) {
376 return IsDecimalDigit(c) || (('A' <= c) && (c <= 'F')) ||
377 (('a' <= c) && (c <= 'f'));
378 }
379
380 static int HexDigitToInt(char c) {
381 ASSERT(IsHexDigit(c));
382 if (IsDecimalDigit(c)) return c - '0';
383 if (('A' <= c) && (c <= 'F')) return 10 + (c - 'A');
384 return 10 + (c - 'a');
385 }
386
387 static char IntToHexDigit(int i) {
388 ASSERT(0 <= i && i < 16);
389 if (i < 10) return static_cast<char>('0' + i);
390 return static_cast<char>('A' + (i - 10));
391 }
392
393 // Perform a range check, checking if
394 // offset + count <= length
395 // without the risk of integer overflow.
396 static inline bool RangeCheck(intptr_t offset,
397 intptr_t count,
398 intptr_t length) {
399 return offset >= 0 && count >= 0 && length >= 0 &&
400 count <= (length - offset);
401 }
402
403 static inline bool WillAddOverflow(int64_t a, int64_t b) {
404 return ((b > 0) && (a > (kMaxInt64 - b))) ||
405 ((b < 0) && (a < (kMinInt64 - b)));
406 }
407
408 static inline bool WillSubOverflow(int64_t a, int64_t b) {
409 return ((b > 0) && (a < (kMinInt64 + b))) ||
410 ((b < 0) && (a > (kMaxInt64 + b)));
411 }
412
413 // Adds two int64_t values with wrapping around
414 // (two's complement arithmetic).
415 template <typename T = int64_t>
416 static inline T AddWithWrapAround(T a, T b) {
417 // Avoid undefined behavior by doing arithmetic in the unsigned type.
418 using Unsigned = typename std::make_unsigned<T>::type;
419 return static_cast<T>(static_cast<Unsigned>(a) + static_cast<Unsigned>(b));
420 }
421
422 // Subtracts two int64_t values with wrapping around
423 // (two's complement arithmetic).
424 template <typename T = int64_t>
425 static inline T SubWithWrapAround(T a, T b) {
426 // Avoid undefined behavior by doing arithmetic in the unsigned type.
427 using Unsigned = typename std::make_unsigned<T>::type;
428 return static_cast<T>(static_cast<Unsigned>(a) - static_cast<Unsigned>(b));
429 }
430
431 // Multiplies two int64_t values with wrapping around
432 // (two's complement arithmetic).
433 template <typename T = int64_t>
434 static inline T MulWithWrapAround(T a, T b) {
435 // Avoid undefined behavior by doing arithmetic in the unsigned type.
436 using Unsigned = typename std::make_unsigned<T>::type;
437 return static_cast<T>(static_cast<Unsigned>(a) * static_cast<Unsigned>(b));
438 }
439
440 template <typename T = int64_t>
441 static inline T NegWithWrapAround(T a) {
442 // Avoid undefined behavior by doing arithmetic in the unsigned type.
443 using Unsigned = typename std::make_unsigned<T>::type;
444 return static_cast<T>(-static_cast<Unsigned>(a));
445 }
446
447 // Shifts int64_t value left. Supports any non-negative number of bits and
448 // silently discards shifted out bits.
449 static inline int64_t ShiftLeftWithTruncation(int64_t a, int64_t b) {
450 ASSERT(b >= 0);
451 if (b >= kBitsPerInt64) {
452 return 0;
453 }
454 // Avoid undefined behavior by doing arithmetic in the unsigned type.
455 return static_cast<int64_t>(static_cast<uint64_t>(a) << b);
456 }
457
458 template <typename T>
459 static inline T RotateLeft(T value, uint8_t rotate) {
460 const uint8_t width = sizeof(T) * kBitsPerByte;
461 ASSERT(0 <= rotate);
462 ASSERT(rotate <= width);
463 using Unsigned = typename std::make_unsigned<T>::type;
464 return (static_cast<Unsigned>(value) << rotate) |
465 (static_cast<T>(value) >> ((width - rotate) & (width - 1)));
466 }
467 template <typename T>
468 static inline T RotateRight(T value, uint8_t rotate) {
469 const uint8_t width = sizeof(T) * kBitsPerByte;
470 ASSERT(0 <= rotate);
471 ASSERT(rotate <= width);
472 using Unsigned = typename std::make_unsigned<T>::type;
473 return (static_cast<T>(value) >> rotate) |
474 (static_cast<Unsigned>(value) << ((width - rotate) & (width - 1)));
475 }
476
477 // Utility functions for converting values from host endianness to
478 // big or little endian values.
479 static uint16_t HostToBigEndian16(uint16_t host_value);
480 static uint32_t HostToBigEndian32(uint32_t host_value);
481 static uint64_t HostToBigEndian64(uint64_t host_value);
482 static uint16_t HostToLittleEndian16(uint16_t host_value);
483 static uint32_t HostToLittleEndian32(uint32_t host_value);
484 static uint64_t HostToLittleEndian64(uint64_t host_value);
485
486 // Going between Host <-> LE/BE is the same operation for all practical
487 // purposes.
488 static inline uint32_t BigEndianToHost32(uint32_t be_value) {
489 return HostToBigEndian32(host_value: be_value);
490 }
491 static inline uint64_t LittleEndianToHost64(uint64_t le_value) {
492 return HostToLittleEndian64(host_value: le_value);
493 }
494
495 static bool DoublesBitEqual(const double a, const double b) {
496 return bit_cast<int64_t, double>(source: a) == bit_cast<int64_t, double>(source: b);
497 }
498
499 // A double-to-integer conversion that avoids undefined behavior.
500 // Out of range values and NaNs are converted to minimum value
501 // for type T.
502 template <typename T>
503 static T SafeDoubleToInt(double v) {
504 const double min = static_cast<double>(std::numeric_limits<T>::min());
505 const double max = static_cast<double>(std::numeric_limits<T>::max());
506 return (min <= v && v <= max) ? static_cast<T>(v)
507 : std::numeric_limits<T>::min();
508 }
509
510 // dart2js represents integers as double precision floats, which can
511 // represent anything in the range -2^53 ... 2^53.
512 static bool IsJavaScriptInt(int64_t value) {
513 return ((-0x20000000000000LL <= value) && (value <= 0x20000000000000LL));
514 }
515
516 // The lowest n bits are 1, the others are 0.
517 template <typename T = uword>
518 static constexpr T NBitMask(size_t n) {
519 using Unsigned = typename std::make_unsigned<T>::type;
520 constexpr size_t kBitsPerT = sizeof(T) * kBitsPerByte;
521 assert(n <= sizeof(T) * kBitsPerT);
522 return static_cast<T>(n == kBitsPerT ? std::numeric_limits<Unsigned>::max()
523 : (static_cast<Unsigned>(1) << n) - 1);
524 }
525
526 template <typename T = uword>
527 static constexpr T Bit(size_t n) {
528 ASSERT(n < sizeof(T) * kBitsPerByte);
529 T bit = 1;
530 return bit << n;
531 }
532
533 template <typename T>
534 static constexpr bool TestBit(T mask, size_t position) {
535 ASSERT(position < sizeof(T) * kBitsPerByte);
536 return ((mask >> position) & 1) != 0;
537 }
538
539 static char* StrError(int err, char* buffer, size_t bufsize);
540
541 // Not all platforms support strndup.
542 static char* StrNDup(const char* s, intptr_t n);
543 static char* StrDup(const char* s);
544 static intptr_t StrNLen(const char* s, intptr_t n);
545 static bool StrStartsWith(const char* s, const char* prefix) {
546 return strncmp(s1: s, s2: prefix, n: strlen(s: prefix)) == 0;
547 }
548
549 static int Close(int fildes);
550 static size_t Read(int filedes, void* buf, size_t nbyte);
551 static int Unlink(const char* path);
552
553 // Print formatted output info a buffer.
554 //
555 // Does not write more than size characters (including the trailing '\0').
556 //
557 // Returns the number of characters (excluding the trailing '\0')
558 // that would been written if the buffer had been big enough. If
559 // the return value is greater or equal than the given size then the
560 // output has been truncated. The return value is never negative.
561 //
562 // The buffer will always be terminated by a '\0', unless the buffer
563 // is of size 0. The buffer might be nullptr if the size is 0.
564 //
565 // This specification conforms to C99 standard which is implemented
566 // by glibc 2.1+ with one exception: the C99 standard allows a
567 // negative return value. We will terminate the vm rather than let
568 // that occur.
569 static int SNPrint(char* str, size_t size, const char* format, ...)
570 PRINTF_ATTRIBUTE(3, 4);
571 static int VSNPrint(char* str, size_t size, const char* format, va_list args);
572
573 // Allocate a string and print formatted output into a malloc'd buffer.
574 static char* SCreate(const char* format, ...) PRINTF_ATTRIBUTE(1, 2);
575 static char* VSCreate(const char* format, va_list args);
576
577 typedef std::unique_ptr<char, decltype(std::free)*> CStringUniquePtr;
578
579 // Returns str in a unique_ptr with free used as its deleter.
580 static CStringUniquePtr CreateCStringUniquePtr(char* str);
581
582 // Load dynamic library from the given |library_path| and return the
583 // library handle. |library_path| can be |nullptr| in which case
584 // library handle representing the executable is returned.
585 // If an error occurs returns |nullptr| and populates
586 // |error| (if provided) with an error message (caller must free this message
587 // when it is no longer needed).
588 static void* LoadDynamicLibrary(const char* library_path,
589 char** error = nullptr);
590
591 // Resolve the given |symbol| within the library referenced by the
592 // given |library_handle|.
593 // If an error occurs populates |error| (if provided) with an error message
594 // (caller must free this message when it is no longer needed).
595 // Note: on some platforms |nullptr| is a valid value for a symbol, so to
596 // check if resolution succeeded one must instead provide non-null |error|
597 // and then check if it was populated with an error message.
598 static void* ResolveSymbolInDynamicLibrary(void* library_handle,
599 const char* symbol,
600 char** error = nullptr);
601
602 // Unload the library referenced by the given |library_handle|.
603 // If an error occurs returns |nullptr| and populates
604 // |error| (if provided) with an error message (caller must free this message
605 // when it is no longer needed).
606 static void UnloadDynamicLibrary(void* library_handle,
607 char** error = nullptr);
608};
609
610} // namespace dart
611
612#if defined(DART_HOST_OS_ANDROID)
613#include "platform/utils_android.h"
614#elif defined(DART_HOST_OS_FUCHSIA)
615#include "platform/utils_fuchsia.h"
616#elif defined(DART_HOST_OS_LINUX)
617#include "platform/utils_linux.h"
618#elif defined(DART_HOST_OS_MACOS)
619#include "platform/utils_macos.h"
620#elif defined(DART_HOST_OS_WINDOWS)
621#include "platform/utils_win.h"
622#else
623#error Unknown target os.
624#endif
625
626#endif // RUNTIME_PLATFORM_UTILS_H_
627

source code of flutter_engine/third_party/dart/runtime/platform/utils.h