Extras/CDTestFramework/Opcode/Ice/_IceUtils.h

   1 /*
   2  *      ICE / OPCODE - Optimized Collision Detection
   3  * http://www.codercorner.com/Opcode.htm
   4  *
   5  * Copyright (c) 2001-2008 Pierre Terdiman,  pierre@codercorner.com
   6
   7 This software is provided 'as-is', without any express or implied warranty.
   8 In no event will the authors be held liable for any damages arising from the use of this software.
   9 Permission is granted to anyone to use this software for any purpose,
  10 including commercial applications, and to alter it and redistribute it freely,
  11 subject to the following restrictions:
  12
  13 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
  14 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
  15 3. This notice may not be removed or altered from any source distribution.
  16 */
  17 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  18 /**
  19  *      Contains misc. useful macros & defines.
  20  *      \file           IceUtils.h
  21  *      \author         Pierre Terdiman (collected from various sources)
  22  *      \date           April, 4, 2000
  23  */
  24 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  25
  26 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  27 // Include Guard
  28 #ifndef __ICEUTILS_H__
  29 #define __ICEUTILS_H__
  30
  31         #define START_RUNONCE   { static bool __RunOnce__ = false;      if(!__RunOnce__){
  32         #define END_RUNONCE             __RunOnce__ = true;}}
  33
  34         //! Reverse all the bits in a 32 bit word (from Steve Baker's Cute Code Collection)
  35         //! (each line can be done in any order.
  36         inline_ void    ReverseBits(udword& n)
  37         {
  38                 n = ((n >>  1) & 0x55555555) | ((n <<  1) & 0xaaaaaaaa);
  39                 n = ((n >>  2) & 0x33333333) | ((n <<  2) & 0xcccccccc);
  40                 n = ((n >>  4) & 0x0f0f0f0f) | ((n <<  4) & 0xf0f0f0f0);
  41                 n = ((n >>  8) & 0x00ff00ff) | ((n <<  8) & 0xff00ff00);
  42                 n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);
  43                 // Etc for larger intergers (64 bits in Java)
  44                 // NOTE: the >> operation must be unsigned! (>>> in java)
  45         }
  46
  47         //! Count the number of '1' bits in a 32 bit word (from Steve Baker's Cute Code Collection)
  48         inline_ udword  CountBits(udword n)
  49         {
  50                 // This relies of the fact that the count of n bits can NOT overflow
  51                 // an n bit interger. EG: 1 bit count takes a 1 bit interger, 2 bit counts
  52                 // 2 bit interger, 3 bit count requires only a 2 bit interger.
  53                 // So we add all bit pairs, then each nible, then each byte etc...
  54                 n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
  55                 n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
  56                 n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
  57                 n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
  58                 n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);
  59                 // Etc for larger intergers (64 bits in Java)
  60                 // NOTE: the >> operation must be unsigned! (>>> in java)
  61                 return n;
  62         }
  63
  64         //! Even faster?
  65         inline_ udword  CountBits2(udword bits)
  66         {
  67                 bits = bits - ((bits >> 1) & 0x55555555);
  68                 bits = ((bits >> 2) & 0x33333333) + (bits & 0x33333333);
  69                 bits = ((bits >> 4) + bits) & 0x0F0F0F0F;
  70                 return (bits * 0x01010101) >> 24;
  71         }
  72
  73         //! Spread out bits.    EG      00001111  ->   0101010101
  74         //!                                             00001010  ->   0100010000
  75         //! This is used to interleve to intergers to produce a `Morten Key'
  76         //! used in Space Filling Curves (See DrDobbs Journal, July 1999)
  77         //! Order is important.
  78         inline_ void    SpreadBits(udword& n)
  79         {
  80                 n = ( n & 0x0000ffff) | (( n & 0xffff0000) << 16);
  81                 n = ( n & 0x000000ff) | (( n & 0x0000ff00) <<  8);
  82                 n = ( n & 0x000f000f) | (( n & 0x00f000f0) <<  4);
  83                 n = ( n & 0x03030303) | (( n & 0x0c0c0c0c) <<  2);
  84                 n = ( n & 0x11111111) | (( n & 0x22222222) <<  1);
  85         }
  86
  87         // Next Largest Power of 2
  88         // Given a binary integer value x, the next largest power of 2 can be computed by a SWAR algorithm
  89         // that recursively "folds" the upper bits into the lower bits. This process yields a bit vector with
  90         // the same most significant 1 as x, but all 1's below it. Adding 1 to that value yields the next
  91         // largest power of 2. For a 32-bit value:
  92         inline_ udword  nlpo2(udword x)
  93         {
  94                 x |= (x >> 1);
  95                 x |= (x >> 2);
  96                 x |= (x >> 4);
  97                 x |= (x >> 8);
  98                 x |= (x >> 16);
  99                 return x+1;
 100         }
 101
 102         //! Test to see if a number is an exact power of two (from Steve Baker's Cute Code Collection)
 103         inline_ bool    IsPowerOfTwo(udword n)                          { return ((n&(n-1))==0);                                        }
 104
 105         //! Zero the least significant '1' bit in a word. (from Steve Baker's Cute Code Collection)
 106         inline_ void    ZeroLeastSetBit(udword& n)                      { n&=(n-1);                                                                     }
 107
 108         //! Set the least significant N bits in a word. (from Steve Baker's Cute Code Collection)
 109         inline_ void    SetLeastNBits(udword& x, udword n)      { x|=~(~0<<n);                                                          }
 110
 111         //! Classic XOR swap (from Steve Baker's Cute Code Collection)
 112         //! x ^= y;             /* x' = (x^y) */
 113         //! y ^= x;             /* y' = (y^(x^y)) = x */
 114         //! x ^= y;             /* x' = (x^y)^x = y */
 115         inline_ void    Swap(udword& x, udword& y)                      { x ^= y; y ^= x; x ^= y;                                       }
 116
 117         //! Little/Big endian (from Steve Baker's Cute Code Collection)
 118         //!
 119         //! Extra comments by Kenny Hoff:
 120         //! Determines the byte-ordering of the current machine (little or big endian)
 121         //! by setting an integer value to 1 (so least significant bit is now 1); take
 122         //! the address of the int and cast to a byte pointer (treat integer as an
 123         //! array of four bytes); check the value of the first byte (must be 0 or 1).
 124         //! If the value is 1, then the first byte least significant byte and this
 125         //! implies LITTLE endian. If the value is 0, the first byte is the most
 126         //! significant byte, BIG endian. Examples:
 127         //!      integer 1 on BIG endian: 00000000 00000000 00000000 00000001
 128         //!   integer 1 on LITTLE endian: 00000001 00000000 00000000 00000000
 129         //!---------------------------------------------------------------------------
 130         //! int IsLittleEndian()        { int x=1;      return ( ((char*)(&x))[0] );    }
 131         inline_ char    LittleEndian()                                          { int i = 1; return *((char*)&i);                       }
 132
 133         //!< Alternative abs function
 134         inline_ udword  abs_(sdword x)                                  { sdword y= x >> 31;    return (x^y)-y;         }
 135
 136         //!< Alternative min function
 137         inline_ sdword  min_(sdword a, sdword b)                        { sdword delta = b-a;   return a + (delta&(delta>>31)); }
 138
 139         // Determine if one of the bytes in a 4 byte word is zero
 140         inline_ BOOL    HasNullByte(udword x)                   { return ((x + 0xfefefeff) & (~x) & 0x80808080);                }
 141
 142         // To find the smallest 1 bit in a word  EG: ~~~~~~10---0    =>    0----010---0
 143         inline_ udword  LowestOneBit(udword w)                  { return ((w) & (~(w)+1));                                      }
 144 //      inline_ udword  LowestOneBit_(udword w)                 { return ((w) & (-(w)));                                        }
 145
 146         // Most Significant 1 Bit
 147         // Given a binary integer value x, the most significant 1 bit (highest numbered element of a bit set)
 148         // can be computed using a SWAR algorithm that recursively "folds" the upper bits into the lower bits.
 149         // This process yields a bit vector with the same most significant 1 as x, but all 1's below it.
 150          // Bitwise AND of the original value with the complement of the "folded" value shifted down by one
 151         // yields the most significant bit. For a 32-bit value:
 152         inline_ udword  msb32(udword x)
 153         {
 154                 x |= (x >> 1);
 155                 x |= (x >> 2);
 156                 x |= (x >> 4);
 157                 x |= (x >> 8);
 158                 x |= (x >> 16);
 159                 return (x & ~(x >> 1));
 160         }
 161
 162         /*
 163         "Just call it repeatedly with various input values and always with the same variable as "memory".
 164         The sharpness determines the degree of filtering, where 0 completely filters out the input, and 1
 165         does no filtering at all.
 166
 167         I seem to recall from college that this is called an IIR (Infinite Impulse Response) filter. As opposed
 168         to the more typical FIR (Finite Impulse Response).
 169
 170         Also, I'd say that you can make more intelligent and interesting filters than this, for example filters
 171         that remove wrong responses from the mouse because it's being moved too fast. You'd want such a filter
 172         to be applied before this one, of course."
 173
 174         (JCAB on Flipcode)
 175         */
 176         inline_ float   FeedbackFilter(float val, float& memory, float sharpness)
 177         {
 178                 ASSERT(sharpness>=0.0f && sharpness<=1.0f && "Invalid sharpness value in feedback filter");
 179                                 if(sharpness<0.0f)      sharpness = 0.0f;
 180                 else    if(sharpness>1.0f)      sharpness = 1.0f;
 181                 return memory = val * sharpness + memory * (1.0f - sharpness);
 182         }
 183
 184         //! If you can guarantee that your input domain (i.e. value of x) is slightly
 185         //! limited (abs(x) must be < ((1<<31u)-32767)), then you can use the
 186         //! following code to clamp the resulting value into [-32768,+32767] range:
 187         inline_ int     ClampToInt16(int x)
 188         {
 189 //              ASSERT(abs(x) < (int)((1<<31u)-32767));
 190
 191                 int delta = 32767 - x;
 192                 x += (delta>>31) & delta;
 193                 delta = x + 32768;
 194                 x -= (delta>>31) & delta;
 195                 return x;
 196         }
 197
 198         // Generic functions
 199         template<class Type> inline_ void TSwap(Type& a, Type& b)                                                               { const Type c = a; a = b; b = c;                       }
 200         template<class Type> inline_ Type TClamp(const Type& x, const Type& lo, const Type& hi) { return ((x<lo) ? lo : (x>hi) ? hi : x);       }
 201
 202         template<class Type> inline_ void TSort(Type& a, Type& b)
 203         {
 204                 if(a>b) TSwap(a, b);
 205         }
 206
 207         template<class Type> inline_ void TSort(Type& a, Type& b, Type& c)
 208         {
 209                 if(a>b) TSwap(a, b);
 210                 if(b>c) TSwap(b, c);
 211                 if(a>b) TSwap(a, b);
 212                 if(b>c) TSwap(b, c);
 213         }
 214
 215         // Prevent nasty user-manipulations (strategy borrowed from Charles Bloom)
 216 //      #define PREVENT_COPY(curclass)  void operator = (const curclass& object)        {       ASSERT(!"Bad use of operator =");       }
 217         // ... actually this is better !
 218         #define PREVENT_COPY(cur_class) private: cur_class(const cur_class& object);    cur_class& operator=(const cur_class& object);
 219
 220         //! TO BE DOCUMENTED
 221         #define OFFSET_OF(Class, Member)        (size_t)&(((Class*)0)->Member)
 222         //! TO BE DOCUMENTED
 223         #define ARRAYSIZE(p)                            (sizeof(p)/sizeof(p[0]))
 224
 225         ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 226         /**
 227          *      Returns the alignment of the input address.
 228          *      \fn                     Alignment()
 229          *      \param          address [in] address to check
 230          *      \return         the best alignment (e.g. 1 for odd addresses, etc)
 231          */
 232         ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 233         FUNCTION ICECORE_API udword Alignment(udword address);
 234
 235         #define IS_ALIGNED_2(x)         ((x&1)==0)
 236         #define IS_ALIGNED_4(x)         ((x&3)==0)
 237         #define IS_ALIGNED_8(x)         ((x&7)==0)
 238
 239         inline_ void _prefetch(void const* ptr)         { (void)*(char const volatile *)ptr;    }
 240
 241         // Compute implicit coords from an index:
 242         // The idea is to get back 2D coords from a 1D index.
 243         // For example:
 244         //
 245         // 0            1               2       ...     nbu-1
 246         // nbu          nbu+1   i       ...
 247         //
 248         // We have i, we're looking for the equivalent (u=2, v=1) location.
 249         //              i = u + v*nbu
 250         // <=>  i/nbu = u/nbu + v
 251         // Since 0 <= u < nbu, u/nbu = 0 (integer)
 252         // Hence: v = i/nbu
 253         // Then we simply put it back in the original equation to compute u = i - v*nbu
 254         inline_ void Compute2DCoords(udword& u, udword& v, udword i, udword nbu)
 255         {
 256                 v = i / nbu;
 257                 u = i - (v * nbu);
 258         }
 259
 260         // In 3D:       i = u + v*nbu + w*nbu*nbv
 261         // <=>          i/(nbu*nbv) = u/(nbu*nbv) + v/nbv + w
 262         // u/(nbu*nbv) is null since u/nbu was null already.
 263         // v/nbv is null as well for the same reason.
 264         // Hence w = i/(nbu*nbv)
 265         // Then we're left with a 2D problem: i' = i - w*nbu*nbv = u + v*nbu
 266         inline_ void Compute3DCoords(udword& u, udword& v, udword& w, udword i, udword nbu, udword nbu_nbv)
 267         {
 268                 w = i / (nbu_nbv);
 269                 Compute2DCoords(u, v, i - (w * nbu_nbv), nbu);
 270         }
 271
 272 #endif // __ICEUTILS_H__