dvander@49: /* vim: set ts=4 sw=4 tw=99 et:
dvander@49:  *
dvander@28:  * Copyright (C) 2012 David Anderson
dvander@28:  *
dvander@115:  * This file is part of SourcePawn.
dvander@28:  *
dvander@115:  * SourcePawn is free software: you can redistribute it and/or modify it under
dvander@28:  * the terms of the GNU General Public License as published by the Free
dvander@28:  * Software Foundation, either version 3 of the License, or (at your option)
dvander@28:  * any later version.
dvander@28:  * 
dvander@115:  * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY
dvander@28:  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
dvander@28:  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
dvander@28:  *
dvander@28:  * You should have received a copy of the GNU General Public License along with
dvander@115:  * SourcePawn. If not, see http://www.gnu.org/licenses/.
dvander@28:  */
dvander@28: #ifndef _include_jitcraft_utility_h_
dvander@28: #define _include_jitcraft_utility_h_
dvander@28: 
dvander@28: #include <assert.h>
danderson@92: #include <stddef.h>
dvander@251: #include <stdlib.h>
dvander@105: #include "../include/keima_util.h"
dvander@28: #ifdef _MSC_VER
dvander@28: # include <intrin.h>
dvander@28: #endif
dvander@28: 
dvander@28: #ifdef _MSC_VER
dvander@28: # pragma warning(disable:4355)
dvander@28: #endif
dvander@28: 
dvander@59: namespace ke {
dvander@28: 
dvander@28: static const size_t kMallocAlignment = sizeof(void *) * 2;
dvander@28: 
dvander@28: typedef uint8_t uint8;
dvander@28: typedef int32_t int32;
dvander@28: typedef uint32_t uint32;
dvander@195: typedef int64_t int64;
dvander@195: typedef uint64_t uint64;
dvander@28: 
dvander@28: typedef uint8 * Address;
dvander@28: 
dvander@28: static const size_t kKB = 1024;
dvander@28: static const size_t kMB = 1024 * kKB;
dvander@28: static const size_t kGB = 1024 * kMB;
dvander@28: 
dvander@28: template <typename T>
dvander@251: class AutoFree
dvander@28: {
dvander@28:     T *t_;
dvander@28: 
dvander@28:   public:
dvander@251:     AutoFree()
dvander@28:       : t_(NULL)
dvander@28:     {
dvander@28:     }
dvander@251:     AutoFree(T *t)
dvander@28:       : t_(t)
dvander@28:     {
dvander@28:     }
dvander@251:     ~AutoFree() {
dvander@251:         free(t_);
dvander@28:     }
dvander@251:     T *take() {
dvander@251:         T *t = t_;
dvander@251:         t_ = NULL;
dvander@251:         return t;
dvander@251:     }
dvander@251:     T *operator *() const {
dvander@28:         return t_;
dvander@28:     }
dvander@28:     void operator =(T *t) {
dvander@28:         if (t_)
dvander@251:             free(t_);
dvander@28:         t_ = t;
dvander@28:     }
dvander@28: };
dvander@28: 
dvander@54: // Bob Jenkin's one-at-a-time hash function[1].
dvander@54: //
dvander@54: // [1] http://burtleburtle.net/bob/hash/doobs.html
dvander@54: class CharacterStreamHasher
dvander@54: {
dvander@54:     uint32 hash;
dvander@54: 
dvander@54:   public:
dvander@54:     CharacterStreamHasher()
dvander@54:       : hash(0)
dvander@54:     { }
dvander@54: 
dvander@54:     void add(char c) {
dvander@54:         hash += c;
dvander@54:         hash += (hash << 10);
dvander@54:         hash ^= (hash >> 6);
dvander@54:     }
dvander@54: 
dvander@54:     void add(const char *s, size_t length) {
dvander@54:         for (size_t i = 0; i < length; i++)
dvander@54:             add(s[i]);
dvander@54:     }
dvander@54: 
dvander@54:     uint32 result() {
dvander@54:         hash += (hash << 3);
dvander@54:         hash ^= (hash >> 11);
dvander@54:         hash += (hash << 15);
dvander@54:         return hash;
dvander@54:     }
dvander@54: };
dvander@54: 
dvander@54: static inline uint32
dvander@54: HashCharSequence(const char *s, size_t length)
dvander@54: {
dvander@54:     CharacterStreamHasher hasher;
dvander@54:     hasher.add(s, length);
dvander@54:     return hasher.result();
dvander@54: }
dvander@54: 
dvander@195: // From http://burtleburtle.net/bob/hash/integer.html
dvander@195: static inline uint32
dvander@195: HashInt32(int32 a)
dvander@195: {
dvander@251:     a = (a ^ 61) ^ (a >> 16);
dvander@251:     a = a + (a << 3);
dvander@251:     a = a ^ (a >> 4);
dvander@251:     a = a * 0x27d4eb2d;
dvander@251:     a = a ^ (a >> 15);
dvander@195:     return a;
dvander@195: }
dvander@195: 
dvander@195: // From http://www.cris.com/~Ttwang/tech/inthash.htm
dvander@195: static inline uint32
dvander@195: HashInt64(int64 key)
dvander@195: {
dvander@251:   key = (~key) + (key << 18); // key = (key << 18) - key - 1;
dvander@251:   key = key ^ (uint64(key) >> 31);
dvander@251:   key = key * 21; // key = (key + (key << 2)) + (key << 4);
dvander@251:   key = key ^ (uint64(key) >> 11);
dvander@251:   key = key + (key << 6);
dvander@251:   key = key ^ (uint64(key) >> 22);
dvander@195:   return uint32(key);
dvander@195: }
dvander@195: 
dvander@195: static inline uint32
dvander@195: HashPointer(void *p)
dvander@195: {
dvander@195: #if defined(KE_32BIT)
dvander@195:     return HashInt32(reinterpret_cast<int32>(p));
dvander@195: #elif defined(KE_64BIT)
dvander@195:     return HashInt64(reinterpret_cast<int64>(p));
dvander@195: #endif
dvander@195: }
dvander@195: 
dvander@28: static inline size_t
dvander@28: Log2(size_t number)
dvander@28: {
dvander@28:     assert(number != 0);
dvander@28: 
dvander@53: #ifdef _MSC_VER
dvander@28:     unsigned long rval;
dvander@86: # ifdef _M_IX86
dvander@28:     _BitScanReverse(&rval, number);
dvander@86: # elif _M_X64
dvander@86:     _BitScanReverse64(&rval, number);
dvander@86: # endif
dvander@28:     return rval;
dvander@28: #else
dvander@251:     size_t bit;
dvander@251:     asm("bsr %1, %0\n"
dvander@251:         : "=r" (bit)
dvander@251:         : "rm" (number));
dvander@251:     return bit;
dvander@28: #endif
dvander@28: }
dvander@28: 
dvander@53: static inline size_t
dvander@53: FindRightmostBit(size_t number)
dvander@53: {
dvander@53:     assert(number != 0);
dvander@53: 
dvander@53: #ifdef _MSC_VER
dvander@53:     unsigned long rval;
dvander@86: # ifdef _M_IX86
dvander@53:     _BitScanForward(&rval, number);
dvander@86: # elif _M_X64
dvander@86:     _BitScanForward64(&rval, number);
dvander@86: # endif
dvander@53:     return rval;
dvander@53: #else
dvander@251:     size_t bit;
dvander@251:     asm("bsf %1, %0\n"
dvander@251:         : "=r" (bit)
dvander@251:         : "rm" (number));
dvander@251:     return bit;
dvander@53: #endif
dvander@53: }
dvander@53: 
dvander@28: static inline bool
dvander@28: IsPowerOfTwo(size_t value)
dvander@28: {
dvander@28:     if (value == 0)
dvander@28:         return false;
dvander@28:     return !(value & (value - 1));
dvander@28: }
dvander@28: 
dvander@28: static inline size_t
dvander@28: Align(size_t count, size_t alignment)
dvander@28: {
dvander@28:     assert(IsPowerOfTwo(alignment));
dvander@28:     return count + (alignment - (count % alignment)) % alignment;
dvander@28: }
dvander@28: 
dvander@28: static inline bool
dvander@28: IsUint32AddSafe(unsigned a, unsigned b)
dvander@28: {
dvander@55:     if (!a || !b)
dvander@55:         return true;
dvander@86:     size_t log2_a = Log2(a);
dvander@86:     size_t log2_b = Log2(b);
dvander@28:     return (log2_a < sizeof(unsigned) * 8) &&
dvander@28:            (log2_b < sizeof(unsigned) * 8);
dvander@28: }
dvander@28: 
dvander@28: static inline bool
dvander@55: IsUintPtrAddSafe(size_t a, size_t b)
dvander@55: {
dvander@55:     if (!a || !b)
dvander@55:         return true;
dvander@55:     size_t log2_a = Log2(a);
dvander@55:     size_t log2_b = Log2(b);
dvander@55:     return (log2_a < sizeof(size_t) * 8) &&
dvander@55:            (log2_b < sizeof(size_t) * 8);
dvander@55: }
dvander@55: 
dvander@55: static inline bool
dvander@28: IsUint32MultiplySafe(unsigned a, unsigned b)
dvander@28: {
dvander@28:     if (a <= 1 || b <= 1)
dvander@28:         return true;
dvander@28: 
dvander@86:     size_t log2_a = Log2(a);
dvander@86:     size_t log2_b = Log2(b);
dvander@28:     return log2_a + log2_b <= sizeof(unsigned) * 8;
dvander@28: }
dvander@28: 
dvander@55: static inline bool
dvander@55: IsUintPtrMultiplySafe(size_t a, size_t b)
dvander@55: {
dvander@55:     if (a <= 1 || b <= 1)
dvander@55:         return true;
dvander@55: 
dvander@55:     size_t log2_a = Log2(a);
dvander@55:     size_t log2_b = Log2(b);
dvander@55:     return log2_a + log2_b <= sizeof(size_t) * 8;
dvander@55: }
dvander@55: 
dvander@28: #define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
dvander@28: #define STATIC_ASSERT(cond) extern int static_assert_f(int a[(cond) ? 1 : -1])
dvander@28: 
dvander@251: #define IS_ALIGNED(addr, alignment)    (!(uintptr_t(addr) & ((alignment) - 1)))
dvander@49: 
dvander@11: template <typename T>
dvander@11: static inline bool
dvander@11: IsAligned(T addr, size_t alignment)
dvander@11: {
dvander@11:     assert(IsPowerOfTwo(alignment));
dvander@11:     return !(uintptr_t(addr) & (alignment - 1));
dvander@28: }
dvander@28: 
dvander@11: static inline Address
dvander@11: AlignedBase(Address addr, size_t alignment)
dvander@11: {
dvander@11:     assert(IsPowerOfTwo(alignment));
dvander@11:     return Address(uintptr_t(addr) & ~(alignment - 1));
dvander@28: }
dvander@28: 
dvander@28: template <typename T> static inline T
dvander@28: Min(const T &t1, const T &t2)
dvander@28: {
dvander@28:     return t1 < t2 ? t1 : t2;
dvander@28: }
dvander@28: 
danderson@91: #define OFFSETOF(Class, Member) reinterpret_cast<size_t>(&((Class *)NULL)->Member)
danderson@91: 
dvander@28: }
dvander@28: 
dvander@28: #endif // _include_jitcraft_utility_h_