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 inline 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 inline bool IsAligned(T x, intptr_t n) {
77 ASSERT(IsPowerOfTwo(n));
78 return (x & (n - 1)) == 0;
79 }
80
81 template <typename T>
82 static inline bool IsAligned(T* x, intptr_t n) {
83 return IsAligned(reinterpret_cast<uword>(x), n);
84 }
85
86 template <typename T>
87 static inline T RoundDown(T x, intptr_t n) {
88 ASSERT(IsPowerOfTwo(n));
89 return (x & -n);
90 }
91
92 template <typename T>
93 static inline T* RoundDown(T* x, intptr_t n) {
94 return reinterpret_cast<T*>(RoundDown(reinterpret_cast<uword>(x), n));
95 }
96
97 template <typename T>
98 static inline T RoundUp(T x, intptr_t n) {
99 return RoundDown(x + n - 1, n);
100 }
101
102 template <typename T>
103 static inline T* RoundUp(T* x, intptr_t n) {
104 return reinterpret_cast<T*>(RoundUp(reinterpret_cast<uword>(x), n));
105 }
106
107 static uintptr_t RoundUpToPowerOfTwo(uintptr_t x);
108
109 static int CountOneBits64(uint64_t x);
110 static int CountOneBits32(uint32_t x);
111
112 static int CountOneBitsWord(uword x) {
113#ifdef ARCH_IS_64_BIT
114 return CountOneBits64(x);
115#else
116 return CountOneBits32(x);
117#endif
118 }
119
120 static int HighestBit(int64_t v);
121
122 static int BitLength(int64_t value) {
123 // Flip bits if negative (-1 becomes 0).
124 value ^= value >> (8 * sizeof(value) - 1);
125 return (value == 0) ? 0 : (Utils::HighestBit(value) + 1);
126 }
127
128 static int CountLeadingZeros64(uint64_t x);
129 static int CountLeadingZeros32(uint32_t x);
130
131 static int CountLeadingZerosWord(uword x) {
132#ifdef ARCH_IS_64_BIT
133 return CountLeadingZeros64(x);
134#else
135 return CountLeadingZeros32(x);
136#endif
137 }
138
139 static int CountTrailingZeros64(uint64_t x);
140 static int CountTrailingZeros32(uint32_t x);
141
142 static int CountTrailingZerosWord(uword x) {
143#ifdef ARCH_IS_64_BIT
144 return CountTrailingZeros64(x);
145#else
146 return CountTrailingZeros32(x);
147#endif
148 }
149
150 static uint64_t ReverseBits64(uint64_t x);
151 static uint32_t ReverseBits32(uint32_t x);
152
153 static uword ReverseBitsWord(uword x) {
154#ifdef ARCH_IS_64_BIT
155 return ReverseBits64(x);
156#else
157 return ReverseBits32(x);
158#endif
159 }
160
161 // Computes magic numbers to implement DIV or MOD operator.
162 static void CalculateMagicAndShiftForDivRem(int64_t divisor,
163 int64_t* magic,
164 int64_t* shift);
165
166 // Computes a hash value for the given string.
167 static uint32_t StringHash(const char* data, int length);
168
169 // Computes a hash value for the given word.
170 static uint32_t WordHash(intptr_t key);
171
172 // Check whether an N-bit two's-complement representation can hold value.
173 template <typename T>
174 static inline bool IsInt(int N, T value) {
175 ASSERT((0 < N) &&
176 (static_cast<unsigned int>(N) < (kBitsPerByte * sizeof(value))));
177 T limit = static_cast<T>(1) << (N - 1);
178 return (-limit <= value) && (value < limit);
179 }
180
181 template <typename T>
182 static inline bool IsUint(int N, T value) {
183 ASSERT((0 < N) &&
184 (static_cast<unsigned int>(N) < (kBitsPerByte * sizeof(value))));
185 const auto limit =
186 (static_cast<typename std::make_unsigned<T>::type>(1) << N) - 1;
187 return (0 <= value) &&
188 (static_cast<typename std::make_unsigned<T>::type>(value) <= limit);
189 }
190
191 // Check whether the magnitude of value fits in N bits, i.e., whether an
192 // (N+1)-bit sign-magnitude representation can hold value.
193 template <typename T>
194 static inline bool IsAbsoluteUint(int N, T value) {
195 ASSERT((0 < N) &&
196 (static_cast<unsigned int>(N) < (kBitsPerByte * sizeof(value))));
197 if (value < 0) value = -value;
198 return IsUint(N, value);
199 }
200
201 static inline int32_t Low16Bits(int32_t value) {
202 return static_cast<int32_t>(value & 0xffff);
203 }
204
205 static inline int32_t High16Bits(int32_t value) {
206 return static_cast<int32_t>(value >> 16);
207 }
208
209 static inline int32_t Low32Bits(int64_t value) {
210 return static_cast<int32_t>(value);
211 }
212
213 static inline int32_t High32Bits(int64_t value) {
214 return static_cast<int32_t>(value >> 32);
215 }
216
217 static inline int64_t LowHighTo64Bits(uint32_t low, int32_t high) {
218 return (static_cast<uint64_t>(high) << 32) | (low & 0x0ffffffffLL);
219 }
220
221 static inline constexpr bool IsAlphaNumeric(uint32_t c) {
222 return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') ||
223 IsDecimalDigit(c);
224 }
225
226 static inline constexpr bool IsDecimalDigit(uint32_t c) {
227 return ('0' <= c) && (c <= '9');
228 }
229
230 static bool IsHexDigit(char c) {
231 return IsDecimalDigit(c) || (('A' <= c) && (c <= 'F')) ||
232 (('a' <= c) && (c <= 'f'));
233 }
234
235 static int HexDigitToInt(char c) {
236 ASSERT(IsHexDigit(c));
237 if (IsDecimalDigit(c)) return c - '0';
238 if (('A' <= c) && (c <= 'F')) return 10 + (c - 'A');
239 return 10 + (c - 'a');
240 }
241
242 static char IntToHexDigit(int i) {
243 ASSERT(0 <= i && i < 16);
244 if (i < 10) return static_cast<char>('0' + i);
245 return static_cast<char>('A' + (i - 10));
246 }
247
248 // Perform a range check, checking if
249 // offset + count <= length
250 // without the risk of integer overflow.
251 static inline bool RangeCheck(intptr_t offset,
252 intptr_t count,
253 intptr_t length) {
254 return offset >= 0 && count >= 0 && length >= 0 &&
255 count <= (length - offset);
256 }
257
258 static inline bool WillAddOverflow(int64_t a, int64_t b) {
259 return ((b > 0) && (a > (kMaxInt64 - b))) ||
260 ((b < 0) && (a < (kMinInt64 - b)));
261 }
262
263 static inline bool WillSubOverflow(int64_t a, int64_t b) {
264 return ((b > 0) && (a < (kMinInt64 + b))) ||
265 ((b < 0) && (a > (kMaxInt64 + b)));
266 }
267
268 // Adds two int64_t values with wrapping around
269 // (two's complement arithmetic).
270 static inline int64_t AddWithWrapAround(int64_t a, int64_t b) {
271 // Avoid undefined behavior by doing arithmetic in the unsigned type.
272 return static_cast<int64_t>(static_cast<uint64_t>(a) +
273 static_cast<uint64_t>(b));
274 }
275
276 // Subtracts two int64_t values with wrapping around
277 // (two's complement arithmetic).
278 static inline int64_t SubWithWrapAround(int64_t a, int64_t b) {
279 // Avoid undefined behavior by doing arithmetic in the unsigned type.
280 return static_cast<int64_t>(static_cast<uint64_t>(a) -
281 static_cast<uint64_t>(b));
282 }
283
284 // Multiplies two int64_t values with wrapping around
285 // (two's complement arithmetic).
286 static inline int64_t MulWithWrapAround(int64_t a, int64_t b) {
287 // Avoid undefined behavior by doing arithmetic in the unsigned type.
288 return static_cast<int64_t>(static_cast<uint64_t>(a) *
289 static_cast<uint64_t>(b));
290 }
291
292 // Shifts int64_t value left. Supports any non-negative number of bits and
293 // silently discards shifted out bits.
294 static inline int64_t ShiftLeftWithTruncation(int64_t a, int64_t b) {
295 ASSERT(b >= 0);
296 if (b >= kBitsPerInt64) {
297 return 0;
298 }
299 // Avoid undefined behavior by doing arithmetic in the unsigned type.
300 return static_cast<int64_t>(static_cast<uint64_t>(a) << b);
301 }
302
303 template <typename T>
304 static inline T RotateLeft(T value, uint8_t rotate) {
305 const uint8_t width = sizeof(T) * kBitsPerByte;
306 ASSERT(0 <= rotate);
307 ASSERT(rotate <= width);
308 using Unsigned = typename std::make_unsigned<T>::type;
309 return (static_cast<Unsigned>(value) << rotate) |
310 (static_cast<T>(value) >> ((width - rotate) & (width - 1)));
311 }
312 template <typename T>
313 static inline T RotateRight(T value, uint8_t rotate) {
314 const uint8_t width = sizeof(T) * kBitsPerByte;
315 ASSERT(0 <= rotate);
316 ASSERT(rotate <= width);
317 using Unsigned = typename std::make_unsigned<T>::type;
318 return (static_cast<T>(value) >> rotate) |
319 (static_cast<Unsigned>(value) << ((width - rotate) & (width - 1)));
320 }
321
322 // Utility functions for converting values from host endianness to
323 // big or little endian values.
324 static uint16_t HostToBigEndian16(uint16_t host_value);
325 static uint32_t HostToBigEndian32(uint32_t host_value);
326 static uint64_t HostToBigEndian64(uint64_t host_value);
327 static uint16_t HostToLittleEndian16(uint16_t host_value);
328 static uint32_t HostToLittleEndian32(uint32_t host_value);
329 static uint64_t HostToLittleEndian64(uint64_t host_value);
330
331 // Going between Host <-> LE/BE is the same operation for all practical
332 // purposes.
333 static inline uint32_t BigEndianToHost32(uint32_t be_value) {
334 return HostToBigEndian32(be_value);
335 }
336 static inline uint64_t LittleEndianToHost64(uint64_t le_value) {
337 return HostToLittleEndian64(le_value);
338 }
339
340 static bool DoublesBitEqual(const double a, const double b) {
341 return bit_cast<int64_t, double>(a) == bit_cast<int64_t, double>(b);
342 }
343
344 // A double-to-integer conversion that avoids undefined behavior.
345 // Out of range values and NaNs are converted to minimum value
346 // for type T.
347 template <typename T>
348 static T SafeDoubleToInt(double v) {
349 const double min = static_cast<double>(std::numeric_limits<T>::min());
350 const double max = static_cast<double>(std::numeric_limits<T>::max());
351 return (min <= v && v <= max) ? static_cast<T>(v)
352 : std::numeric_limits<T>::min();
353 }
354
355 // dart2js represents integers as double precision floats, which can
356 // represent anything in the range -2^53 ... 2^53.
357 static bool IsJavascriptInt(int64_t value) {
358 return ((-0x20000000000000LL <= value) && (value <= 0x20000000000000LL));
359 }
360
361 // The lowest n bits are 1, the others are 0.
362 static uword NBitMask(uint32_t n) {
363 ASSERT(n <= kBitsPerWord);
364 if (n == kBitsPerWord) {
365 static_assert((sizeof(uword) * kBitsPerByte) == kBitsPerWord,
366 "Unexpected uword size");
367 return std::numeric_limits<uword>::max();
368 }
369 return (static_cast<uword>(1) << n) - 1;
370 }
371
372 static word SignedNBitMask(uint32_t n) {
373 uword mask = NBitMask(n);
374 return bit_cast<word>(mask);
375 }
376
377 template <typename T = uword>
378 static T Bit(uint32_t n) {
379 ASSERT(n < sizeof(T) * kBitsPerByte);
380 T bit = 1;
381 return bit << n;
382 }
383
384 template <typename T>
385 DART_FORCE_INLINE static bool TestBit(T mask, intptr_t position) {
386 ASSERT(position < static_cast<intptr_t>(sizeof(T) * kBitsPerByte));
387 return ((mask >> position) & 1) != 0;
388 }
389
390 // Decode integer in SLEB128 format from |data| and update |byte_index|.
391 template <typename ValueType>
392 static ValueType DecodeSLEB128(const uint8_t* data,
393 const intptr_t data_length,
394 intptr_t* byte_index) {
395 using Unsigned = typename std::make_unsigned<ValueType>::type;
396 ASSERT(*byte_index < data_length);
397 uword shift = 0;
398 Unsigned value = 0;
399 uint8_t part = 0;
400 do {
401 part = data[(*byte_index)++];
402 value |= static_cast<Unsigned>(part & 0x7f) << shift;
403 shift += 7;
404 } while ((part & 0x80) != 0);
405
406 if ((shift < (sizeof(ValueType) * CHAR_BIT)) && ((part & 0x40) != 0)) {
407 const Unsigned kMax = std::numeric_limits<Unsigned>::max();
408 value |= static_cast<Unsigned>(kMax << shift);
409 }
410 return static_cast<ValueType>(value);
411 }
412
413 static char* StrError(int err, char* buffer, size_t bufsize);
414
415 // Not all platforms support strndup.
416 static char* StrNDup(const char* s, intptr_t n);
417 static char* StrDup(const char* s);
418 static intptr_t StrNLen(const char* s, intptr_t n);
419
420 static int Close(int fildes);
421 static size_t Read(int filedes, void* buf, size_t nbyte);
422 static int Unlink(const char* path);
423
424 // Print formatted output info a buffer.
425 //
426 // Does not write more than size characters (including the trailing '\0').
427 //
428 // Returns the number of characters (excluding the trailing '\0')
429 // that would been written if the buffer had been big enough. If
430 // the return value is greater or equal than the given size then the
431 // output has been truncated. The return value is never negative.
432 //
433 // The buffer will always be terminated by a '\0', unless the buffer
434 // is of size 0. The buffer might be NULL if the size is 0.
435 //
436 // This specification conforms to C99 standard which is implemented
437 // by glibc 2.1+ with one exception: the C99 standard allows a
438 // negative return value. We will terminate the vm rather than let
439 // that occur.
440 static int SNPrint(char* str, size_t size, const char* format, ...)
441 PRINTF_ATTRIBUTE(3, 4);
442 static int VSNPrint(char* str, size_t size, const char* format, va_list args);
443
444 // Allocate a string and print formatted output into a malloc'd buffer.
445 static char* SCreate(const char* format, ...) PRINTF_ATTRIBUTE(1, 2);
446 static char* VSCreate(const char* format, va_list args);
447
448 typedef std::unique_ptr<char, decltype(std::free)*> CStringUniquePtr;
449
450 // Returns str in a unique_ptr with free used as its deleter.
451 static CStringUniquePtr CreateCStringUniquePtr(char* str);
452};
453
454} // namespace dart
455
456#if defined(HOST_OS_ANDROID)
457#include "platform/utils_android.h"
458#elif defined(HOST_OS_FUCHSIA)
459#include "platform/utils_fuchsia.h"
460#elif defined(HOST_OS_LINUX)
461#include "platform/utils_linux.h"
462#elif defined(HOST_OS_MACOS)
463#include "platform/utils_macos.h"
464#elif defined(HOST_OS_WINDOWS)
465#include "platform/utils_win.h"
466#else
467#error Unknown target os.
468#endif
469
470#endif // RUNTIME_PLATFORM_UTILS_H_
471