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