1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/include/am-utility.h Fri Aug 23 20:34:17 2013 -0700
1.3 @@ -0,0 +1,366 @@
1.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
1.5 +//
1.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
1.7 +// All rights reserved.
1.8 +//
1.9 +// Redistribution and use in source and binary forms, with or without
1.10 +// modification, are permitted provided that the following conditions are met:
1.11 +//
1.12 +// * Redistributions of source code must retain the above copyright notice, this
1.13 +// list of conditions and the following disclaimer.
1.14 +// * Redistributions in binary form must reproduce the above copyright notice,
1.15 +// this list of conditions and the following disclaimer in the documentation
1.16 +// and/or other materials provided with the distribution.
1.17 +// * Neither the name of AlliedModders LLC nor the names of its contributors
1.18 +// may be used to endorse or promote products derived from this software
1.19 +// without specific prior written permission.
1.20 +//
1.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.31 +// POSSIBILITY OF SUCH DAMAGE.
1.32 +
1.33 +#ifndef _include_amtl_utility_h_
1.34 +#define _include_amtl_utility_h_
1.35 +
1.36 +#include <assert.h>
1.37 +#include <stddef.h>
1.38 +#include <stdlib.h>
1.39 +#include <stdint.h>
1.40 +#if defined(_MSC_VER)
1.41 +# include <intrin.h>
1.42 +#endif
1.43 +
1.44 +#define KE_32BIT
1.45 +
1.46 +#if defined(_MSC_VER)
1.47 +# pragma warning(disable:4355)
1.48 +#endif
1.49 +
1.50 +namespace ke {
1.51 +
1.52 +static const size_t kMallocAlignment = sizeof(void *) * 2;
1.53 +
1.54 +typedef uint8_t uint8;
1.55 +typedef int32_t int32;
1.56 +typedef uint32_t uint32;
1.57 +typedef int64_t int64;
1.58 +typedef uint64_t uint64;
1.59 +
1.60 +typedef uint8 * Address;
1.61 +
1.62 +static const size_t kKB = 1024;
1.63 +static const size_t kMB = 1024 * kKB;
1.64 +static const size_t kGB = 1024 * kMB;
1.65 +
1.66 +template <typename T> T
1.67 +ReturnAndVoid(T &t)
1.68 +{
1.69 + T saved = t;
1.70 + t = T();
1.71 + return saved;
1.72 +}
1.73 +
1.74 +// Wrapper that automatically deletes its contents. The pointer can be taken
1.75 +// to avoid destruction.
1.76 +template <typename T>
1.77 +class AutoPtr
1.78 +{
1.79 + T *t_;
1.80 +
1.81 + public:
1.82 + AutoPtr()
1.83 + : t_(NULL)
1.84 + {
1.85 + }
1.86 + explicit AutoPtr(T *t)
1.87 + : t_(t)
1.88 + {
1.89 + }
1.90 + ~AutoPtr() {
1.91 + delete t_;
1.92 + }
1.93 + T *take() {
1.94 + return ReturnAndVoid(t_);
1.95 + }
1.96 + T *operator *() const {
1.97 + return t_;
1.98 + }
1.99 + T *operator ->() const {
1.100 + return t_;
1.101 + }
1.102 + operator T *() const {
1.103 + return t_;
1.104 + }
1.105 + void operator =(T *t) {
1.106 + delete t_;
1.107 + t_ = t;
1.108 + }
1.109 + bool operator !() const {
1.110 + return !t_;
1.111 + }
1.112 +};
1.113 +
1.114 +// Bob Jenkin's one-at-a-time hash function[1].
1.115 +//
1.116 +// [1] http://burtleburtle.net/bob/hash/doobs.html
1.117 +class CharacterStreamHasher
1.118 +{
1.119 + uint32 hash;
1.120 +
1.121 + public:
1.122 + CharacterStreamHasher()
1.123 + : hash(0)
1.124 + { }
1.125 +
1.126 + void add(char c) {
1.127 + hash += c;
1.128 + hash += (hash << 10);
1.129 + hash ^= (hash >> 6);
1.130 + }
1.131 +
1.132 + void add(const char *s, size_t length) {
1.133 + for (size_t i = 0; i < length; i++)
1.134 + add(s[i]);
1.135 + }
1.136 +
1.137 + uint32 result() {
1.138 + hash += (hash << 3);
1.139 + hash ^= (hash >> 11);
1.140 + hash += (hash << 15);
1.141 + return hash;
1.142 + }
1.143 +};
1.144 +
1.145 +static inline uint32
1.146 +HashCharSequence(const char *s, size_t length)
1.147 +{
1.148 + CharacterStreamHasher hasher;
1.149 + hasher.add(s, length);
1.150 + return hasher.result();
1.151 +}
1.152 +
1.153 +// From http://burtleburtle.net/bob/hash/integer.html
1.154 +static inline uint32
1.155 +HashInt32(int32 a)
1.156 +{
1.157 + a = (a ^ 61) ^ (a >> 16);
1.158 + a = a + (a << 3);
1.159 + a = a ^ (a >> 4);
1.160 + a = a * 0x27d4eb2d;
1.161 + a = a ^ (a >> 15);
1.162 + return a;
1.163 +}
1.164 +
1.165 +// From http://www.cris.com/~Ttwang/tech/inthash.htm
1.166 +static inline uint32
1.167 +HashInt64(int64 key)
1.168 +{
1.169 + key = (~key) + (key << 18); // key = (key << 18) - key - 1;
1.170 + key = key ^ (uint64(key) >> 31);
1.171 + key = key * 21; // key = (key + (key << 2)) + (key << 4);
1.172 + key = key ^ (uint64(key) >> 11);
1.173 + key = key + (key << 6);
1.174 + key = key ^ (uint64(key) >> 22);
1.175 + return uint32(key);
1.176 +}
1.177 +
1.178 +static inline uint32
1.179 +HashPointer(void *p)
1.180 +{
1.181 +#if defined(KE_32BIT)
1.182 + return HashInt32(int32_t(intptr_t(p)));
1.183 +#elif defined(KE_64BIT)
1.184 + return HashInt64(int64_t(intptr_t(p)));
1.185 +#endif
1.186 +}
1.187 +
1.188 +static inline size_t
1.189 +Log2(size_t number)
1.190 +{
1.191 + assert(number != 0);
1.192 +
1.193 +#ifdef _MSC_VER
1.194 + unsigned long rval;
1.195 +# ifdef _M_IX86
1.196 + _BitScanReverse(&rval, number);
1.197 +# elif _M_X64
1.198 + _BitScanReverse64(&rval, number);
1.199 +# endif
1.200 + return rval;
1.201 +#else
1.202 + size_t bit;
1.203 + asm("bsr %1, %0\n"
1.204 + : "=r" (bit)
1.205 + : "rm" (number));
1.206 + return bit;
1.207 +#endif
1.208 +}
1.209 +
1.210 +static inline size_t
1.211 +FindRightmostBit(size_t number)
1.212 +{
1.213 + assert(number != 0);
1.214 +
1.215 +#ifdef _MSC_VER
1.216 + unsigned long rval;
1.217 +# ifdef _M_IX86
1.218 + _BitScanForward(&rval, number);
1.219 +# elif _M_X64
1.220 + _BitScanForward64(&rval, number);
1.221 +# endif
1.222 + return rval;
1.223 +#else
1.224 + size_t bit;
1.225 + asm("bsf %1, %0\n"
1.226 + : "=r" (bit)
1.227 + : "rm" (number));
1.228 + return bit;
1.229 +#endif
1.230 +}
1.231 +
1.232 +static inline bool
1.233 +IsPowerOfTwo(size_t value)
1.234 +{
1.235 + if (value == 0)
1.236 + return false;
1.237 + return !(value & (value - 1));
1.238 +}
1.239 +
1.240 +static inline size_t
1.241 +Align(size_t count, size_t alignment)
1.242 +{
1.243 + assert(IsPowerOfTwo(alignment));
1.244 + return count + (alignment - (count % alignment)) % alignment;
1.245 +}
1.246 +
1.247 +static inline bool
1.248 +IsUint32AddSafe(unsigned a, unsigned b)
1.249 +{
1.250 + if (!a || !b)
1.251 + return true;
1.252 + size_t log2_a = Log2(a);
1.253 + size_t log2_b = Log2(b);
1.254 + return (log2_a < sizeof(unsigned) * 8) &&
1.255 + (log2_b < sizeof(unsigned) * 8);
1.256 +}
1.257 +
1.258 +static inline bool
1.259 +IsUintPtrAddSafe(size_t a, size_t b)
1.260 +{
1.261 + if (!a || !b)
1.262 + return true;
1.263 + size_t log2_a = Log2(a);
1.264 + size_t log2_b = Log2(b);
1.265 + return (log2_a < sizeof(size_t) * 8) &&
1.266 + (log2_b < sizeof(size_t) * 8);
1.267 +}
1.268 +
1.269 +static inline bool
1.270 +IsUint32MultiplySafe(unsigned a, unsigned b)
1.271 +{
1.272 + if (a <= 1 || b <= 1)
1.273 + return true;
1.274 +
1.275 + size_t log2_a = Log2(a);
1.276 + size_t log2_b = Log2(b);
1.277 + return log2_a + log2_b <= sizeof(unsigned) * 8;
1.278 +}
1.279 +
1.280 +static inline bool
1.281 +IsUintPtrMultiplySafe(size_t a, size_t b)
1.282 +{
1.283 + if (a <= 1 || b <= 1)
1.284 + return true;
1.285 +
1.286 + size_t log2_a = Log2(a);
1.287 + size_t log2_b = Log2(b);
1.288 + return log2_a + log2_b <= sizeof(size_t) * 8;
1.289 +}
1.290 +
1.291 +#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
1.292 +#define STATIC_ASSERT(cond) extern int static_assert_f(int a[(cond) ? 1 : -1])
1.293 +
1.294 +#define IS_ALIGNED(addr, alignment) (!(uintptr_t(addr) & ((alignment) - 1)))
1.295 +
1.296 +template <typename T>
1.297 +static inline bool
1.298 +IsAligned(T addr, size_t alignment)
1.299 +{
1.300 + assert(IsPowerOfTwo(alignment));
1.301 + return !(uintptr_t(addr) & (alignment - 1));
1.302 +}
1.303 +
1.304 +static inline Address
1.305 +AlignedBase(Address addr, size_t alignment)
1.306 +{
1.307 + assert(IsPowerOfTwo(alignment));
1.308 + return Address(uintptr_t(addr) & ~(alignment - 1));
1.309 +}
1.310 +
1.311 +template <typename T> static inline T
1.312 +Min(const T &t1, const T &t2)
1.313 +{
1.314 + return t1 < t2 ? t1 : t2;
1.315 +}
1.316 +
1.317 +template <typename T> static inline T
1.318 +Max(const T &t1, const T &t2)
1.319 +{
1.320 + return t1 > t2 ? t1 : t2;
1.321 +}
1.322 +
1.323 +template <typename T>
1.324 +class StorageBuffer
1.325 +{
1.326 + public:
1.327 + T *address() {
1.328 + return reinterpret_cast<T *>(buffer_);
1.329 + }
1.330 + const T *address() const {
1.331 + return reinterpret_cast<const T *>(buffer_);
1.332 + }
1.333 +
1.334 + private:
1.335 + union {
1.336 + char buffer_[sizeof(T)];
1.337 + uint64_t aligned_;
1.338 + };
1.339 +};
1.340 +
1.341 +#if __cplusplus >= 201103L
1.342 +# define KE_CXX11
1.343 +#endif
1.344 +
1.345 +#if defined(KE_CXX11)
1.346 +# define KE_DELETE delete
1.347 +# define KE_OVERRIDE override
1.348 +#else
1.349 +# define KE_DELETE
1.350 +# define KE_OVERRIDE
1.351 +#endif
1.352 +
1.353 +#if defined(_MSC_VER)
1.354 +# define KE_SIZET_FMT "%Iu"
1.355 +#elif defined(__GNUC__)
1.356 +# define KE_SIZET_FMT "%zu"
1.357 +#else
1.358 +# error "Implement format specifier string"
1.359 +#endif
1.360 +
1.361 +#if defined(__GNUC__)
1.362 +# define KE_CRITICAL_LIKELY(x) __builtin_expect(!!(x), 1)
1.363 +#else
1.364 +# define KE_CRITICAL_LIKELY(x) x
1.365 +#endif
1.366 +
1.367 +}
1.368 +
1.369 +#endif // _include_amtl_utility_h_