1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/public/sourcepawn/ke_utility.h Thu Aug 08 09:41:24 2013 -0700
1.3 @@ -0,0 +1,318 @@
1.4 +/* vim: set ts=4 sw=4 tw=99 et:
1.5 + *
1.6 + * Copyright (C) 2012-2013 David Anderson
1.7 + *
1.8 + * This file is part of SourcePawn.
1.9 + *
1.10 + * SourcePawn is free software: you can redistribute it and/or modify it under
1.11 + * the terms of the GNU General Public License as published by the Free
1.12 + * Software Foundation, either version 3 of the License, or (at your option)
1.13 + * any later version.
1.14 + *
1.15 + * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY
1.16 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.17 + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License along with
1.20 + * SourcePawn. If not, see http://www.gnu.org/licenses/.
1.21 + */
1.22 +#ifndef _include_jitcraft_utility_h_
1.23 +#define _include_jitcraft_utility_h_
1.24 +
1.25 +#include <assert.h>
1.26 +#include <stddef.h>
1.27 +#include <stdlib.h>
1.28 +#if defined(_MSC_VER)
1.29 +# include <intrin.h>
1.30 +#endif
1.31 +
1.32 +#define KE_32BIT
1.33 +
1.34 +#if defined(_MSC_VER)
1.35 +# pragma warning(disable:4355)
1.36 +#endif
1.37 +
1.38 +namespace ke {
1.39 +
1.40 +static const size_t kMallocAlignment = sizeof(void *) * 2;
1.41 +
1.42 +typedef uint8_t uint8;
1.43 +typedef int32_t int32;
1.44 +typedef uint32_t uint32;
1.45 +typedef int64_t int64;
1.46 +typedef uint64_t uint64;
1.47 +
1.48 +typedef uint8 * Address;
1.49 +
1.50 +static const size_t kKB = 1024;
1.51 +static const size_t kMB = 1024 * kKB;
1.52 +static const size_t kGB = 1024 * kMB;
1.53 +
1.54 +template <typename T>
1.55 +class AutoFree
1.56 +{
1.57 + T *t_;
1.58 +
1.59 + public:
1.60 + AutoFree()
1.61 + : t_(NULL)
1.62 + {
1.63 + }
1.64 + AutoFree(T *t)
1.65 + : t_(t)
1.66 + {
1.67 + }
1.68 + ~AutoFree() {
1.69 + free(t_);
1.70 + }
1.71 + T *take() {
1.72 + T *t = t_;
1.73 + t_ = NULL;
1.74 + return t;
1.75 + }
1.76 + T *operator *() const {
1.77 + return t_;
1.78 + }
1.79 + void operator =(T *t) {
1.80 + if (t_)
1.81 + free(t_);
1.82 + t_ = t;
1.83 + }
1.84 +};
1.85 +
1.86 +// Bob Jenkin's one-at-a-time hash function[1].
1.87 +//
1.88 +// [1] http://burtleburtle.net/bob/hash/doobs.html
1.89 +class CharacterStreamHasher
1.90 +{
1.91 + uint32 hash;
1.92 +
1.93 + public:
1.94 + CharacterStreamHasher()
1.95 + : hash(0)
1.96 + { }
1.97 +
1.98 + void add(char c) {
1.99 + hash += c;
1.100 + hash += (hash << 10);
1.101 + hash ^= (hash >> 6);
1.102 + }
1.103 +
1.104 + void add(const char *s, size_t length) {
1.105 + for (size_t i = 0; i < length; i++)
1.106 + add(s[i]);
1.107 + }
1.108 +
1.109 + uint32 result() {
1.110 + hash += (hash << 3);
1.111 + hash ^= (hash >> 11);
1.112 + hash += (hash << 15);
1.113 + return hash;
1.114 + }
1.115 +};
1.116 +
1.117 +static inline uint32
1.118 +HashCharSequence(const char *s, size_t length)
1.119 +{
1.120 + CharacterStreamHasher hasher;
1.121 + hasher.add(s, length);
1.122 + return hasher.result();
1.123 +}
1.124 +
1.125 +// From http://burtleburtle.net/bob/hash/integer.html
1.126 +static inline uint32
1.127 +HashInt32(int32 a)
1.128 +{
1.129 + a = (a ^ 61) ^ (a >> 16);
1.130 + a = a + (a << 3);
1.131 + a = a ^ (a >> 4);
1.132 + a = a * 0x27d4eb2d;
1.133 + a = a ^ (a >> 15);
1.134 + return a;
1.135 +}
1.136 +
1.137 +// From http://www.cris.com/~Ttwang/tech/inthash.htm
1.138 +static inline uint32
1.139 +HashInt64(int64 key)
1.140 +{
1.141 + key = (~key) + (key << 18); // key = (key << 18) - key - 1;
1.142 + key = key ^ (uint64(key) >> 31);
1.143 + key = key * 21; // key = (key + (key << 2)) + (key << 4);
1.144 + key = key ^ (uint64(key) >> 11);
1.145 + key = key + (key << 6);
1.146 + key = key ^ (uint64(key) >> 22);
1.147 + return uint32(key);
1.148 +}
1.149 +
1.150 +static inline uint32
1.151 +HashPointer(void *p)
1.152 +{
1.153 +#if defined(KE_32BIT)
1.154 + return HashInt32(reinterpret_cast<int32>(p));
1.155 +#elif defined(KE_64BIT)
1.156 + return HashInt64(reinterpret_cast<int64>(p));
1.157 +#endif
1.158 +}
1.159 +
1.160 +static inline size_t
1.161 +Log2(size_t number)
1.162 +{
1.163 + assert(number != 0);
1.164 +
1.165 +#ifdef _MSC_VER
1.166 + unsigned long rval;
1.167 +# ifdef _M_IX86
1.168 + _BitScanReverse(&rval, number);
1.169 +# elif _M_X64
1.170 + _BitScanReverse64(&rval, number);
1.171 +# endif
1.172 + return rval;
1.173 +#else
1.174 + size_t bit;
1.175 + asm("bsr %1, %0\n"
1.176 + : "=r" (bit)
1.177 + : "rm" (number));
1.178 + return bit;
1.179 +#endif
1.180 +}
1.181 +
1.182 +static inline size_t
1.183 +FindRightmostBit(size_t number)
1.184 +{
1.185 + assert(number != 0);
1.186 +
1.187 +#ifdef _MSC_VER
1.188 + unsigned long rval;
1.189 +# ifdef _M_IX86
1.190 + _BitScanForward(&rval, number);
1.191 +# elif _M_X64
1.192 + _BitScanForward64(&rval, number);
1.193 +# endif
1.194 + return rval;
1.195 +#else
1.196 + size_t bit;
1.197 + asm("bsf %1, %0\n"
1.198 + : "=r" (bit)
1.199 + : "rm" (number));
1.200 + return bit;
1.201 +#endif
1.202 +}
1.203 +
1.204 +static inline bool
1.205 +IsPowerOfTwo(size_t value)
1.206 +{
1.207 + if (value == 0)
1.208 + return false;
1.209 + return !(value & (value - 1));
1.210 +}
1.211 +
1.212 +static inline size_t
1.213 +Align(size_t count, size_t alignment)
1.214 +{
1.215 + assert(IsPowerOfTwo(alignment));
1.216 + return count + (alignment - (count % alignment)) % alignment;
1.217 +}
1.218 +
1.219 +static inline bool
1.220 +IsUint32AddSafe(unsigned a, unsigned b)
1.221 +{
1.222 + if (!a || !b)
1.223 + return true;
1.224 + size_t log2_a = Log2(a);
1.225 + size_t log2_b = Log2(b);
1.226 + return (log2_a < sizeof(unsigned) * 8) &&
1.227 + (log2_b < sizeof(unsigned) * 8);
1.228 +}
1.229 +
1.230 +static inline bool
1.231 +IsUintPtrAddSafe(size_t a, size_t b)
1.232 +{
1.233 + if (!a || !b)
1.234 + return true;
1.235 + size_t log2_a = Log2(a);
1.236 + size_t log2_b = Log2(b);
1.237 + return (log2_a < sizeof(size_t) * 8) &&
1.238 + (log2_b < sizeof(size_t) * 8);
1.239 +}
1.240 +
1.241 +static inline bool
1.242 +IsUint32MultiplySafe(unsigned a, unsigned b)
1.243 +{
1.244 + if (a <= 1 || b <= 1)
1.245 + return true;
1.246 +
1.247 + size_t log2_a = Log2(a);
1.248 + size_t log2_b = Log2(b);
1.249 + return log2_a + log2_b <= sizeof(unsigned) * 8;
1.250 +}
1.251 +
1.252 +static inline bool
1.253 +IsUintPtrMultiplySafe(size_t a, size_t b)
1.254 +{
1.255 + if (a <= 1 || b <= 1)
1.256 + return true;
1.257 +
1.258 + size_t log2_a = Log2(a);
1.259 + size_t log2_b = Log2(b);
1.260 + return log2_a + log2_b <= sizeof(size_t) * 8;
1.261 +}
1.262 +
1.263 +#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
1.264 +#define STATIC_ASSERT(cond) extern int static_assert_f(int a[(cond) ? 1 : -1])
1.265 +
1.266 +#define IS_ALIGNED(addr, alignment) (!(uintptr_t(addr) & ((alignment) - 1)))
1.267 +
1.268 +template <typename T>
1.269 +static inline bool
1.270 +IsAligned(T addr, size_t alignment)
1.271 +{
1.272 + assert(IsPowerOfTwo(alignment));
1.273 + return !(uintptr_t(addr) & (alignment - 1));
1.274 +}
1.275 +
1.276 +static inline Address
1.277 +AlignedBase(Address addr, size_t alignment)
1.278 +{
1.279 + assert(IsPowerOfTwo(alignment));
1.280 + return Address(uintptr_t(addr) & ~(alignment - 1));
1.281 +}
1.282 +
1.283 +template <typename T> static inline T
1.284 +Min(const T &t1, const T &t2)
1.285 +{
1.286 + return t1 < t2 ? t1 : t2;
1.287 +}
1.288 +
1.289 +template <typename T> static inline T
1.290 +Max(const T &t1, const T &t2)
1.291 +{
1.292 + return t1 > t2 ? t1 : t2;
1.293 +}
1.294 +
1.295 +template <typename T> T
1.296 +ReturnAndVoid(T &t)
1.297 +{
1.298 + T saved = t;
1.299 + t = T();
1.300 + return saved;
1.301 +}
1.302 +
1.303 +#define OFFSETOF(Class, Member) reinterpret_cast<size_t>(&((Class *)NULL)->Member)
1.304 +
1.305 +#if defined(_MSC_VER)
1.306 +# define KE_SIZET_FMT "%Iu"
1.307 +#elif defined(__GNUC__)
1.308 +# define KE_SIZET_FMT "%zu"
1.309 +#else
1.310 +# error "Implement format specifier string"
1.311 +#endif
1.312 +
1.313 +#if defined(__GNUC__)
1.314 +# define KE_CRITICAL_LIKELY(x) __builtin_expect(!!(x), 1)
1.315 +#else
1.316 +# define KE_CRITICAL_LIKELY(x) x
1.317 +#endif
1.318 +
1.319 +}
1.320 +
1.321 +#endif // _include_jitcraft_utility_h_
