src/Utility.h
author David Anderson <dvander@alliedmods.net>
Sun Jan 06 13:52:21 2013 -0800 (2013-01-06)
changeset 256 3c184218462d
parent 251 ca99a81745fe
permissions -rw-r--r--
Initial implementation of module imports.
     1 /* vim: set ts=4 sw=4 tw=99 et:
     2  *
     3  * Copyright (C) 2012 David Anderson
     4  *
     5  * This file is part of SourcePawn.
     6  *
     7  * SourcePawn is free software: you can redistribute it and/or modify it under
     8  * the terms of the GNU General Public License as published by the Free
     9  * Software Foundation, either version 3 of the License, or (at your option)
    10  * any later version.
    11  * 
    12  * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY
    13  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    14  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
    15  *
    16  * You should have received a copy of the GNU General Public License along with
    17  * SourcePawn. If not, see http://www.gnu.org/licenses/.
    18  */
    19 #ifndef _include_jitcraft_utility_h_
    20 #define _include_jitcraft_utility_h_
    21 
    22 #include <assert.h>
    23 #include <stddef.h>
    24 #include <stdlib.h>
    25 #include "../include/keima_util.h"
    26 #ifdef _MSC_VER
    27 # include <intrin.h>
    28 #endif
    29 
    30 #ifdef _MSC_VER
    31 # pragma warning(disable:4355)
    32 #endif
    33 
    34 namespace ke {
    35 
    36 static const size_t kMallocAlignment = sizeof(void *) * 2;
    37 
    38 typedef uint8_t uint8;
    39 typedef int32_t int32;
    40 typedef uint32_t uint32;
    41 typedef int64_t int64;
    42 typedef uint64_t uint64;
    43 
    44 typedef uint8 * Address;
    45 
    46 static const size_t kKB = 1024;
    47 static const size_t kMB = 1024 * kKB;
    48 static const size_t kGB = 1024 * kMB;
    49 
    50 template <typename T>
    51 class AutoFree
    52 {
    53     T *t_;
    54 
    55   public:
    56     AutoFree()
    57       : t_(NULL)
    58     {
    59     }
    60     AutoFree(T *t)
    61       : t_(t)
    62     {
    63     }
    64     ~AutoFree() {
    65         free(t_);
    66     }
    67     T *take() {
    68         T *t = t_;
    69         t_ = NULL;
    70         return t;
    71     }
    72     T *operator *() const {
    73         return t_;
    74     }
    75     void operator =(T *t) {
    76         if (t_)
    77             free(t_);
    78         t_ = t;
    79     }
    80 };
    81 
    82 // Bob Jenkin's one-at-a-time hash function[1].
    83 //
    84 // [1] http://burtleburtle.net/bob/hash/doobs.html
    85 class CharacterStreamHasher
    86 {
    87     uint32 hash;
    88 
    89   public:
    90     CharacterStreamHasher()
    91       : hash(0)
    92     { }
    93 
    94     void add(char c) {
    95         hash += c;
    96         hash += (hash << 10);
    97         hash ^= (hash >> 6);
    98     }
    99 
   100     void add(const char *s, size_t length) {
   101         for (size_t i = 0; i < length; i++)
   102             add(s[i]);
   103     }
   104 
   105     uint32 result() {
   106         hash += (hash << 3);
   107         hash ^= (hash >> 11);
   108         hash += (hash << 15);
   109         return hash;
   110     }
   111 };
   112 
   113 static inline uint32
   114 HashCharSequence(const char *s, size_t length)
   115 {
   116     CharacterStreamHasher hasher;
   117     hasher.add(s, length);
   118     return hasher.result();
   119 }
   120 
   121 // From http://burtleburtle.net/bob/hash/integer.html
   122 static inline uint32
   123 HashInt32(int32 a)
   124 {
   125     a = (a ^ 61) ^ (a >> 16);
   126     a = a + (a << 3);
   127     a = a ^ (a >> 4);
   128     a = a * 0x27d4eb2d;
   129     a = a ^ (a >> 15);
   130     return a;
   131 }
   132 
   133 // From http://www.cris.com/~Ttwang/tech/inthash.htm
   134 static inline uint32
   135 HashInt64(int64 key)
   136 {
   137   key = (~key) + (key << 18); // key = (key << 18) - key - 1;
   138   key = key ^ (uint64(key) >> 31);
   139   key = key * 21; // key = (key + (key << 2)) + (key << 4);
   140   key = key ^ (uint64(key) >> 11);
   141   key = key + (key << 6);
   142   key = key ^ (uint64(key) >> 22);
   143   return uint32(key);
   144 }
   145 
   146 static inline uint32
   147 HashPointer(void *p)
   148 {
   149 #if defined(KE_32BIT)
   150     return HashInt32(reinterpret_cast<int32>(p));
   151 #elif defined(KE_64BIT)
   152     return HashInt64(reinterpret_cast<int64>(p));
   153 #endif
   154 }
   155 
   156 static inline size_t
   157 Log2(size_t number)
   158 {
   159     assert(number != 0);
   160 
   161 #ifdef _MSC_VER
   162     unsigned long rval;
   163 # ifdef _M_IX86
   164     _BitScanReverse(&rval, number);
   165 # elif _M_X64
   166     _BitScanReverse64(&rval, number);
   167 # endif
   168     return rval;
   169 #else
   170     size_t bit;
   171     asm("bsr %1, %0\n"
   172         : "=r" (bit)
   173         : "rm" (number));
   174     return bit;
   175 #endif
   176 }
   177 
   178 static inline size_t
   179 FindRightmostBit(size_t number)
   180 {
   181     assert(number != 0);
   182 
   183 #ifdef _MSC_VER
   184     unsigned long rval;
   185 # ifdef _M_IX86
   186     _BitScanForward(&rval, number);
   187 # elif _M_X64
   188     _BitScanForward64(&rval, number);
   189 # endif
   190     return rval;
   191 #else
   192     size_t bit;
   193     asm("bsf %1, %0\n"
   194         : "=r" (bit)
   195         : "rm" (number));
   196     return bit;
   197 #endif
   198 }
   199 
   200 static inline bool
   201 IsPowerOfTwo(size_t value)
   202 {
   203     if (value == 0)
   204         return false;
   205     return !(value & (value - 1));
   206 }
   207 
   208 static inline size_t
   209 Align(size_t count, size_t alignment)
   210 {
   211     assert(IsPowerOfTwo(alignment));
   212     return count + (alignment - (count % alignment)) % alignment;
   213 }
   214 
   215 static inline bool
   216 IsUint32AddSafe(unsigned a, unsigned b)
   217 {
   218     if (!a || !b)
   219         return true;
   220     size_t log2_a = Log2(a);
   221     size_t log2_b = Log2(b);
   222     return (log2_a < sizeof(unsigned) * 8) &&
   223            (log2_b < sizeof(unsigned) * 8);
   224 }
   225 
   226 static inline bool
   227 IsUintPtrAddSafe(size_t a, size_t b)
   228 {
   229     if (!a || !b)
   230         return true;
   231     size_t log2_a = Log2(a);
   232     size_t log2_b = Log2(b);
   233     return (log2_a < sizeof(size_t) * 8) &&
   234            (log2_b < sizeof(size_t) * 8);
   235 }
   236 
   237 static inline bool
   238 IsUint32MultiplySafe(unsigned a, unsigned b)
   239 {
   240     if (a <= 1 || b <= 1)
   241         return true;
   242 
   243     size_t log2_a = Log2(a);
   244     size_t log2_b = Log2(b);
   245     return log2_a + log2_b <= sizeof(unsigned) * 8;
   246 }
   247 
   248 static inline bool
   249 IsUintPtrMultiplySafe(size_t a, size_t b)
   250 {
   251     if (a <= 1 || b <= 1)
   252         return true;
   253 
   254     size_t log2_a = Log2(a);
   255     size_t log2_b = Log2(b);
   256     return log2_a + log2_b <= sizeof(size_t) * 8;
   257 }
   258 
   259 #define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
   260 #define STATIC_ASSERT(cond) extern int static_assert_f(int a[(cond) ? 1 : -1])
   261 
   262 #define IS_ALIGNED(addr, alignment)    (!(uintptr_t(addr) & ((alignment) - 1)))
   263 
   264 template <typename T>
   265 static inline bool
   266 IsAligned(T addr, size_t alignment)
   267 {
   268     assert(IsPowerOfTwo(alignment));
   269     return !(uintptr_t(addr) & (alignment - 1));
   270 }
   271 
   272 static inline Address
   273 AlignedBase(Address addr, size_t alignment)
   274 {
   275     assert(IsPowerOfTwo(alignment));
   276     return Address(uintptr_t(addr) & ~(alignment - 1));
   277 }
   278 
   279 template <typename T> static inline T
   280 Min(const T &t1, const T &t2)
   281 {
   282     return t1 < t2 ? t1 : t2;
   283 }
   284 
   285 template <typename T> static inline T
   286 Max(const T &t1, const T &t2)
   287 {
   288     return t1 > t2 ? t1 : t2;
   289 }
   290 
   291 #define OFFSETOF(Class, Member) reinterpret_cast<size_t>(&((Class *)NULL)->Member)
   292 
   293 }
   294 
   295 #endif // _include_jitcraft_utility_h_