include/am-utility.h
changeset 0 ba3d4abaf3f1
child 5 d5deada8801f
     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_