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#include "platform/utils.h"
6
7namespace dart {
8
9// Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
10// figure 3-3, page 48, where the function is called clp2.
11uintptr_t Utils::RoundUpToPowerOfTwo(uintptr_t x) {
12 x = x - 1;
13 x = x | (x >> 1);
14 x = x | (x >> 2);
15 x = x | (x >> 4);
16 x = x | (x >> 8);
17 x = x | (x >> 16);
18#if defined(ARCH_IS_64_BIT)
19 x = x | (x >> 32);
20#endif // defined(ARCH_IS_64_BIT)
21 return x + 1;
22}
23
24int Utils::CountOneBits64(uint64_t x) {
25 // Apparently there are x64 chips without popcount.
26#if __GNUC__ && !defined(HOST_ARCH_IA32) && !defined(HOST_ARCH_X64)
27 return __builtin_popcountll(x);
28#else
29 return CountOneBits32(static_cast<uint32_t>(x)) +
30 CountOneBits32(static_cast<uint32_t>(x >> 32));
31#endif
32}
33
34int Utils::CountOneBits32(uint32_t x) {
35 // Apparently there are x64 chips without popcount.
36#if __GNUC__ && !defined(HOST_ARCH_IA32) && !defined(HOST_ARCH_X64)
37 return __builtin_popcount(x);
38#else
39 // Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
40 // figure 5-2, page 66, where the function is called pop.
41 x = x - ((x >> 1) & 0x55555555);
42 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
43 x = (x + (x >> 4)) & 0x0F0F0F0F;
44 x = x + (x >> 8);
45 x = x + (x >> 16);
46 return static_cast<int>(x & 0x0000003F);
47#endif
48}
49
50// TODO(koda): Compare to flsll call/intrinsic.
51int Utils::HighestBit(int64_t v) {
52 uint64_t x = static_cast<uint64_t>((v > 0) ? v : -v);
53 uint64_t t;
54 int r = 0;
55 if ((t = x >> 32) != 0) {
56 x = t;
57 r += 32;
58 }
59 if ((t = x >> 16) != 0) {
60 x = t;
61 r += 16;
62 }
63 if ((t = x >> 8) != 0) {
64 x = t;
65 r += 8;
66 }
67 if ((t = x >> 4) != 0) {
68 x = t;
69 r += 4;
70 }
71 if ((t = x >> 2) != 0) {
72 x = t;
73 r += 2;
74 }
75 if (x > 1) r += 1;
76 return r;
77}
78
79int Utils::CountLeadingZeros64(uint64_t x) {
80#if defined(ARCH_IS_32_BIT)
81 const uint32_t x_hi = static_cast<uint32_t>(x >> 32);
82 if (x_hi != 0) {
83 return CountLeadingZeros32(x_hi);
84 }
85 return 32 + CountLeadingZeros32(static_cast<uint32_t>(x));
86#elif defined(HOST_OS_WINDOWS)
87 unsigned long position; // NOLINT
88 return (_BitScanReverse64(&position, x) == 0)
89 ? 64
90 : 63 - static_cast<int>(position);
91#else
92 return x == 0 ? 64 : __builtin_clzll(x);
93#endif
94}
95
96int Utils::CountLeadingZeros32(uint32_t x) {
97#if defined(HOST_OS_WINDOWS)
98 unsigned long position; // NOLINT
99 return (_BitScanReverse(&position, x) == 0) ? 32
100 : 31 - static_cast<int>(position);
101#else
102 return x == 0 ? 32 : __builtin_clz(x);
103#endif
104}
105
106int Utils::CountTrailingZeros64(uint64_t x) {
107#if defined(ARCH_IS_32_BIT)
108 const uint32_t x_lo = static_cast<uint32_t>(x);
109 if (x_lo != 0) {
110 return CountTrailingZeros32(x_lo);
111 }
112 return 32 + CountTrailingZeros32(static_cast<uint32_t>(x >> 32));
113#elif defined(HOST_OS_WINDOWS)
114 unsigned long position; // NOLINT
115 return (_BitScanForward64(&position, x) == 0) ? 64
116 : static_cast<int>(position);
117#else
118 return x == 0 ? 64 : __builtin_ctzll(x);
119#endif
120}
121
122int Utils::CountTrailingZeros32(uint32_t x) {
123#if defined(HOST_OS_WINDOWS)
124 unsigned long position; // NOLINT
125 return (_BitScanForward(&position, x) == 0) ? 32 : static_cast<int>(position);
126#else
127 return x == 0 ? 32 : __builtin_ctz(x);
128#endif
129}
130
131uint64_t Utils::ReverseBits64(uint64_t x) {
132 const uint64_t one = static_cast<uint64_t>(1);
133 uint64_t result = 0;
134 for (uint64_t rbit = one << 63; x != 0; x >>= 1) {
135 if ((x & one) != 0) result |= rbit;
136 rbit >>= 1;
137 }
138 return result;
139}
140
141uint32_t Utils::ReverseBits32(uint32_t x) {
142 const uint32_t one = static_cast<uint32_t>(1);
143 uint32_t result = 0;
144 for (uint32_t rbit = one << 31; x != 0; x >>= 1) {
145 if ((x & one) != 0) result |= rbit;
146 rbit >>= 1;
147 }
148 return result;
149}
150
151// Implementation according to H.S.Warren's "Hacker's Delight"
152// (Addison Wesley, 2002) Chapter 10 and T.Grablund, P.L.Montogomery's
153// "Division by Invariant Integers Using Multiplication" (PLDI 1994).
154void Utils::CalculateMagicAndShiftForDivRem(int64_t divisor,
155 int64_t* magic,
156 int64_t* shift) {
157 ASSERT(divisor <= -2 || divisor >= 2);
158 /* The magic number M and shift S can be calculated in the following way:
159 * Let nc be the most positive value of numerator(n) such that nc = kd - 1,
160 * where divisor(d) >= 2.
161 * Let nc be the most negative value of numerator(n) such that nc = kd + 1,
162 * where divisor(d) <= -2.
163 * Thus nc can be calculated like:
164 * nc = exp + exp % d - 1, where d >= 2 and exp = 2^63.
165 * nc = -exp + (exp + 1) % d, where d >= 2 and exp = 2^63.
166 *
167 * So the shift p is the smallest p satisfying
168 * 2^p > nc * (d - 2^p % d), where d >= 2
169 * 2^p > nc * (d + 2^p % d), where d <= -2.
170 *
171 * The magic number M is calculated by
172 * M = (2^p + d - 2^p % d) / d, where d >= 2
173 * M = (2^p - d - 2^p % d) / d, where d <= -2.
174 */
175 int64_t p = 63;
176 const uint64_t exp = 1LL << 63;
177
178 // Initialize the computations.
179 uint64_t abs_d = (divisor >= 0) ? divisor : -static_cast<uint64_t>(divisor);
180 uint64_t sign_bit = static_cast<uint64_t>(divisor) >> 63;
181 uint64_t tmp = exp + sign_bit;
182 uint64_t abs_nc = tmp - 1 - (tmp % abs_d);
183 uint64_t quotient1 = exp / abs_nc;
184 uint64_t remainder1 = exp % abs_nc;
185 uint64_t quotient2 = exp / abs_d;
186 uint64_t remainder2 = exp % abs_d;
187
188 // To avoid handling both positive and negative divisor,
189 // "Hacker's Delight" introduces a method to handle these
190 // two cases together to avoid duplication.
191 uint64_t delta;
192 do {
193 p++;
194 quotient1 = 2 * quotient1;
195 remainder1 = 2 * remainder1;
196 if (remainder1 >= abs_nc) {
197 quotient1++;
198 remainder1 = remainder1 - abs_nc;
199 }
200 quotient2 = 2 * quotient2;
201 remainder2 = 2 * remainder2;
202 if (remainder2 >= abs_d) {
203 quotient2++;
204 remainder2 = remainder2 - abs_d;
205 }
206 delta = abs_d - remainder2;
207 } while (quotient1 < delta || (quotient1 == delta && remainder1 == 0));
208
209 *magic = (divisor > 0) ? (quotient2 + 1) : (-quotient2 - 1);
210 *shift = p - 64;
211}
212
213uint32_t Utils::StringHash(const char* data, int length) {
214 // This implementation is based on the public domain MurmurHash
215 // version 2.0. It assumes that the underlying CPU can read from
216 // unaligned addresses. The constants M and R have been determined
217 // to work well experimentally.
218 // TODO(3158902): need to account for unaligned address access on ARM.
219 const uint32_t M = 0x5bd1e995;
220 const int R = 24;
221 int size = length;
222 uint32_t hash = size;
223
224 // Mix four bytes at a time into the hash.
225 const uint8_t* cursor = reinterpret_cast<const uint8_t*>(data);
226 while (size >= 4) {
227 uint32_t part = *reinterpret_cast<const uint32_t*>(cursor);
228 part *= M;
229 part ^= part >> R;
230 part *= M;
231 hash *= M;
232 hash ^= part;
233 cursor += 4;
234 size -= 4;
235 }
236
237 // Handle the last few bytes of the string.
238 switch (size) {
239 case 3:
240 hash ^= cursor[2] << 16;
241 FALL_THROUGH;
242 case 2:
243 hash ^= cursor[1] << 8;
244 FALL_THROUGH;
245 case 1:
246 hash ^= cursor[0];
247 hash *= M;
248 }
249
250 // Do a few final mixes of the hash to ensure the last few bytes are
251 // well-incorporated.
252 hash ^= hash >> 13;
253 hash *= M;
254 hash ^= hash >> 15;
255 return hash;
256}
257
258uint32_t Utils::WordHash(intptr_t key) {
259 // TODO(iposva): Need to check hash spreading.
260 // This example is from http://www.concentric.net/~Ttwang/tech/inthash.htm
261 // via. http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm
262 uword a = static_cast<uword>(key);
263 a = (a + 0x7ed55d16) + (a << 12);
264 a = (a ^ 0xc761c23c) ^ (a >> 19);
265 a = (a + 0x165667b1) + (a << 5);
266 a = (a + 0xd3a2646c) ^ (a << 9);
267 a = (a + 0xfd7046c5) + (a << 3);
268 a = (a ^ 0xb55a4f09) ^ (a >> 16);
269 return static_cast<uint32_t>(a);
270}
271
272char* Utils::SCreate(const char* format, ...) {
273 va_list args;
274 va_start(args, format);
275 char* buffer = VSCreate(format, args);
276 va_end(args);
277 return buffer;
278}
279
280char* Utils::VSCreate(const char* format, va_list args) {
281 // Measure.
282 va_list measure_args;
283 va_copy(measure_args, args);
284 intptr_t len = VSNPrint(NULL, 0, format, measure_args);
285 va_end(measure_args);
286
287 char* buffer = reinterpret_cast<char*>(malloc(len + 1));
288 ASSERT(buffer != NULL);
289
290 // Print.
291 va_list print_args;
292 va_copy(print_args, args);
293 VSNPrint(buffer, len + 1, format, print_args);
294 va_end(print_args);
295 return buffer;
296}
297
298Utils::CStringUniquePtr Utils::CreateCStringUniquePtr(char* str) {
299 return std::unique_ptr<char, decltype(std::free)*>{str, std::free};
300}
301
302} // namespace dart
303