blob: d04c3a814137f93feb5acdeee77a91e5d4577248 [file] [log] [blame]
// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
#include "platform/utils.h"
#include "platform/allocation.h"
#include "platform/globals.h"
namespace dart {
// Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
// figure 3-3, page 48, where the function is called clp2.
uintptr_t Utils::RoundUpToPowerOfTwo(uintptr_t x) {
x = x - 1;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
#if defined(ARCH_IS_64_BIT)
x = x | (x >> 32);
#endif // defined(ARCH_IS_64_BIT)
return x + 1;
}
int Utils::CountOneBits64(uint64_t x) {
// Apparently there are x64 chips without popcount.
#if __GNUC__ && !defined(HOST_ARCH_IA32) && !defined(HOST_ARCH_X64)
return __builtin_popcountll(x);
#else
return CountOneBits32(static_cast<uint32_t>(x)) +
CountOneBits32(static_cast<uint32_t>(x >> 32));
#endif
}
int Utils::CountOneBits32(uint32_t x) {
// Apparently there are x64 chips without popcount.
#if __GNUC__ && !defined(HOST_ARCH_IA32) && !defined(HOST_ARCH_X64)
return __builtin_popcount(x);
#else
// Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
// figure 5-2, page 66, where the function is called pop.
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return static_cast<int>(x & 0x0000003F);
#endif
}
int Utils::CountLeadingZeros64(uint64_t x) {
#if defined(ARCH_IS_32_BIT)
const uint32_t x_hi = static_cast<uint32_t>(x >> 32);
if (x_hi != 0) {
return CountLeadingZeros32(x_hi);
}
return 32 + CountLeadingZeros32(static_cast<uint32_t>(x));
#elif defined(DART_HOST_OS_WINDOWS)
unsigned long position; // NOLINT
return (_BitScanReverse64(&position, x) == 0)
? 64
: 63 - static_cast<int>(position);
#else
return x == 0 ? 64 : __builtin_clzll(x);
#endif
}
int Utils::CountLeadingZeros32(uint32_t x) {
#if defined(DART_HOST_OS_WINDOWS)
unsigned long position; // NOLINT
return (_BitScanReverse(&position, x) == 0) ? 32
: 31 - static_cast<int>(position);
#else
return x == 0 ? 32 : __builtin_clz(x);
#endif
}
int Utils::CountTrailingZeros64(uint64_t x) {
#if defined(ARCH_IS_32_BIT)
const uint32_t x_lo = static_cast<uint32_t>(x);
if (x_lo != 0) {
return CountTrailingZeros32(x_lo);
}
return 32 + CountTrailingZeros32(static_cast<uint32_t>(x >> 32));
#elif defined(DART_HOST_OS_WINDOWS)
unsigned long position; // NOLINT
return (_BitScanForward64(&position, x) == 0) ? 64
: static_cast<int>(position);
#else
return x == 0 ? 64 : __builtin_ctzll(x);
#endif
}
int Utils::CountTrailingZeros32(uint32_t x) {
#if defined(DART_HOST_OS_WINDOWS)
unsigned long position; // NOLINT
return (_BitScanForward(&position, x) == 0) ? 32 : static_cast<int>(position);
#else
return x == 0 ? 32 : __builtin_ctz(x);
#endif
}
uint64_t Utils::ReverseBits64(uint64_t x) {
const uint64_t one = static_cast<uint64_t>(1);
uint64_t result = 0;
for (uint64_t rbit = one << 63; x != 0; x >>= 1) {
if ((x & one) != 0) result |= rbit;
rbit >>= 1;
}
return result;
}
uint32_t Utils::ReverseBits32(uint32_t x) {
const uint32_t one = static_cast<uint32_t>(1);
uint32_t result = 0;
for (uint32_t rbit = one << 31; x != 0; x >>= 1) {
if ((x & one) != 0) result |= rbit;
rbit >>= 1;
}
return result;
}
// Implementation according to H.S.Warren's "Hacker's Delight"
// (Addison Wesley, 2002) Chapter 10 and T.Grablund, P.L.Montogomery's
// "Division by Invariant Integers Using Multiplication" (PLDI 1994).
void Utils::CalculateMagicAndShiftForDivRem(int64_t divisor,
int64_t* magic,
int64_t* shift) {
ASSERT(divisor <= -2 || divisor >= 2);
/* The magic number M and shift S can be calculated in the following way:
* Let nc be the most positive value of numerator(n) such that nc = kd - 1,
* where divisor(d) >= 2.
* Let nc be the most negative value of numerator(n) such that nc = kd + 1,
* where divisor(d) <= -2.
* Thus nc can be calculated like:
* nc = exp + exp % d - 1, where d >= 2 and exp = 2^63.
* nc = -exp + (exp + 1) % d, where d >= 2 and exp = 2^63.
*
* So the shift p is the smallest p satisfying
* 2^p > nc * (d - 2^p % d), where d >= 2
* 2^p > nc * (d + 2^p % d), where d <= -2.
*
* The magic number M is calculated by
* M = (2^p + d - 2^p % d) / d, where d >= 2
* M = (2^p - d - 2^p % d) / d, where d <= -2.
*/
int64_t p = 63;
const uint64_t exp = 1LL << 63;
// Initialize the computations.
uint64_t abs_d = (divisor >= 0) ? divisor : -static_cast<uint64_t>(divisor);
uint64_t sign_bit = static_cast<uint64_t>(divisor) >> 63;
uint64_t tmp = exp + sign_bit;
uint64_t abs_nc = tmp - 1 - (tmp % abs_d);
uint64_t quotient1 = exp / abs_nc;
uint64_t remainder1 = exp % abs_nc;
uint64_t quotient2 = exp / abs_d;
uint64_t remainder2 = exp % abs_d;
// To avoid handling both positive and negative divisor,
// "Hacker's Delight" introduces a method to handle these
// two cases together to avoid duplication.
uint64_t delta;
do {
p++;
quotient1 = 2 * quotient1;
remainder1 = 2 * remainder1;
if (remainder1 >= abs_nc) {
quotient1++;
remainder1 = remainder1 - abs_nc;
}
quotient2 = 2 * quotient2;
remainder2 = 2 * remainder2;
if (remainder2 >= abs_d) {
quotient2++;
remainder2 = remainder2 - abs_d;
}
delta = abs_d - remainder2;
} while (quotient1 < delta || (quotient1 == delta && remainder1 == 0));
*magic = (divisor > 0) ? (quotient2 + 1) : (-quotient2 - 1);
*shift = p - 64;
}
// This implementation is based on the public domain MurmurHash
// version 2.0. The constants M and R have been determined
// to work well experimentally.
static constexpr uint32_t kStringHashM = 0x5bd1e995;
static constexpr int kStringHashR = 24;
// hash and part must be lvalues.
#define MIX(hash, part) \
{ \
(part) *= kStringHashM; \
(part) ^= (part) >> kStringHashR; \
(part) *= kStringHashM; \
(hash) *= kStringHashM; \
(hash) ^= (part); \
}
uint32_t Utils::StringHash(const void* data, int length) {
int size = length;
uint32_t hash = size;
auto cursor = reinterpret_cast<const uint8_t*>(data);
if (size >= kInt32Size) {
const intptr_t misalignment =
reinterpret_cast<intptr_t>(cursor) % kInt32Size;
if (misalignment > 0) {
// Stores 4-byte values starting from the start of the string to mimic
// the algorithm on aligned data.
uint32_t data_window = 0;
// Shift sizes for adjusting the data window when adding the next aligned
// piece of data.
const uint32_t sr = misalignment * kBitsPerByte;
const uint32_t sl = kBitsPerInt32 - sr;
const intptr_t pre_alignment_length = kInt32Size - misalignment;
switch (pre_alignment_length) {
case 3:
data_window |= cursor[2] << 16;
FALL_THROUGH;
case 2:
data_window |= cursor[1] << 8;
FALL_THROUGH;
case 1:
data_window |= cursor[0];
}
cursor += pre_alignment_length;
size -= pre_alignment_length;
// Mix four bytes at a time now that we're at an aligned spot.
for (; size >= kInt32Size; cursor += kInt32Size, size -= kInt32Size) {
uint32_t aligned_part = *reinterpret_cast<const uint32_t*>(cursor);
data_window |= (aligned_part << sl);
MIX(hash, data_window);
data_window = aligned_part >> sr;
}
if (size >= misalignment) {
// There's one more full window in the data. We'll let the normal tail
// code handle any partial window.
switch (misalignment) {
case 3:
data_window |= cursor[2] << (16 + sl);
FALL_THROUGH;
case 2:
data_window |= cursor[1] << (8 + sl);
FALL_THROUGH;
case 1:
data_window |= cursor[0] << sl;
}
MIX(hash, data_window);
cursor += misalignment;
size -= misalignment;
} else {
// This is a partial window, so just xor and multiply by M.
switch (size) {
case 2:
data_window |= cursor[1] << (8 + sl);
FALL_THROUGH;
case 1:
data_window |= cursor[0] << sl;
}
hash ^= data_window;
hash *= kStringHashM;
cursor += size;
size = 0;
}
} else {
// Mix four bytes at a time into the hash.
for (; size >= kInt32Size; size -= kInt32Size, cursor += kInt32Size) {
uint32_t part = *reinterpret_cast<const uint32_t*>(cursor);
MIX(hash, part);
}
}
}
// Handle the last few bytes of the string if any.
switch (size) {
case 3:
hash ^= cursor[2] << 16;
FALL_THROUGH;
case 2:
hash ^= cursor[1] << 8;
FALL_THROUGH;
case 1:
hash ^= cursor[0];
hash *= kStringHashM;
}
// Do a few final mixes of the hash to ensure the last few bytes are
// well-incorporated.
hash ^= hash >> 13;
hash *= kStringHashM;
hash ^= hash >> 15;
return hash;
}
#undef MIX
uint32_t Utils::WordHash(intptr_t key) {
// TODO(iposva): Need to check hash spreading.
// This example is from http://www.concentric.net/~Ttwang/tech/inthash.htm
// via. http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm
uword a = static_cast<uword>(key);
a = (a + 0x7ed55d16) + (a << 12);
a = (a ^ 0xc761c23c) ^ (a >> 19);
a = (a + 0x165667b1) + (a << 5);
a = (a + 0xd3a2646c) ^ (a << 9);
a = (a + 0xfd7046c5) + (a << 3);
a = (a ^ 0xb55a4f09) ^ (a >> 16);
return static_cast<uint32_t>(a);
}
char* Utils::SCreate(const char* format, ...) {
va_list args;
va_start(args, format);
char* buffer = VSCreate(format, args);
va_end(args);
return buffer;
}
char* Utils::VSCreate(const char* format, va_list args) {
// Measure.
va_list measure_args;
va_copy(measure_args, args);
intptr_t len = VSNPrint(NULL, 0, format, measure_args);
va_end(measure_args);
char* buffer = reinterpret_cast<char*>(malloc(len + 1));
ASSERT(buffer != NULL);
// Print.
va_list print_args;
va_copy(print_args, args);
VSNPrint(buffer, len + 1, format, print_args);
va_end(print_args);
return buffer;
}
Utils::CStringUniquePtr Utils::CreateCStringUniquePtr(char* str) {
return std::unique_ptr<char, decltype(std::free)*>{str, std::free};
}
} // namespace dart