- Main Page
- Modules
- Namespaces
- Data Structures
- Files
- Examples

- File List
- Globals

# bmutil.h

Go to the documentation of this file.

    00001 #ifndef BMUTIL__H__INCLUDED__
    00002 #define BMUTIL__H__INCLUDED__
    00003 /*
    00004 Copyright(c) 2002-2009 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
    00005
    00006 Permission is hereby granted, free of charge, to any person
    00007 obtaining a copy of this software and associated documentation
    00008 files (the "Software"), to deal in the Software without restriction,
    00009 including without limitation the rights to use, copy, modify, merge,
    00010 publish, distribute, sublicense, and/or sell copies of the Software,
    00011 and to permit persons to whom the Software is furnished to do so,
    00012 subject to the following conditions:
    00013
    00014 The above copyright notice and this permission notice shall be included
    00015 in all copies or substantial portions of the Software.
    00016
    00017 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
    00018 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
    00019 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
    00020 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
    00021 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
    00022 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
    00023 OTHER DEALINGS IN THE SOFTWARE.
    00024
    00025 For more information please visit:  http://bmagic.sourceforge.net
    00026
    00027 */
    00028
    00029 #include "bmdef.h"
    00030 #include "bmconst.h"
    00031
    00032 #if defined(_M_AMD64) || defined(_M_X64)
    00033 #include <intrin.h>
    00034 #endif
    00035
    00036 namespace bm
    00037 {
    00038
    00039
    00040 /*
    00041 // SSE2 vector equality comparison
    00042 int _mm_any_eq( vFloat a, vFloat b )
    00043 {
    00044
    00045     //test a==b for each float in a & b
    00046     vFloat mask = _mm_cmpeq_ps( a, b );
    00047
    00048     //copy top bit of each result to maskbits
    00049     int maskBits = _mm_movemask_ps( mask );
    00050     return maskBits != 0;
    00051 }
    00052 */
    00053
    00054 // From:
    00055 // http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.8562
    00056 //
    00057 template<typename T>
    00058 T bit_scan_fwd(T v)
    00059 {
    00060     return
    00061         DeBruijn_bit_position<true>::_multiply[((word_t)((v & -v) * 0x077CB531U)) >> 27];
    00062 }
    00063
    00064 /**
    00065     Get minimum of 2 values
    00066 */
    00067 template<typename T>
    00068 T min_value(T v1, T v2)
    00069 {
    00070     return v1 < v2 ? v1 : v2;
    00071 }
    00072
    00073
    00074 /**
    00075     Fast loop-less function to find LOG2
    00076 */
    00077 template<typename T>
    00078 T ilog2(T x)
    00079 {
    00080     unsigned int l = 0;
    00081     if(x >= 1<<16) { x>>=16; l |= 16; }
    00082     if(x >= 1<<8)  { x>>=8; l |= 8; }
    00083     if(x >= 1<<4)  { x>>=4; l |= 4; }
    00084     if(x >= 1<<2)  { x>>=2; l |= 2; }
    00085     if(x >= 1<<1)  l |=1;
    00086     return l;
    00087 }
    00088
    00089 template<>
    00090 inline bm::gap_word_t ilog2(gap_word_t x)
    00091 {
    00092     unsigned int l = 0;
    00093     if(x >= 1<<8)  { x>>=8; l |= 8; }
    00094     if(x >= 1<<4)  { x>>=4; l |= 4; }
    00095     if(x >= 1<<2)  { x>>=2; l |= 2; }
    00096     if(x >= 1<<1)  l |=1;
    00097     return (bm::gap_word_t)l;
    00098 }
    00099
    00100 /**
    00101      Mini auto-pointer for internal memory management
    00102      @internal
    00103 */
    00104 template<class T>
    00105 class ptr_guard
    00106 {
    00107 public:
    00108     ptr_guard(T* p) : ptr_(p) {}
    00109     ~ptr_guard() { delete ptr_; }
    00110 private:
    00111     ptr_guard(const ptr_guard<T>& p);
    00112     ptr_guard& operator=(const ptr_guard<T>& p);
    00113 private:
    00114     T* ptr_;
    00115 };
    00116
    00117 /**
    00118     Lookup table based integer LOG2
    00119 */
    00120 template<typename T>
    00121 T ilog2_LUT(T x)
    00122 {
    00123     unsigned l = 0;
    00124     if (x & 0xffff0000)
    00125     {
    00126         l += 16; x >>= 16;
    00127     }
    00128
    00129     if (x & 0xff00)
    00130     {
    00131         l += 8; x >>= 8;
    00132     }
    00133     return l + first_bit_table<true>::_idx[x];
    00134 }
    00135
    00136 /**
    00137     Lookup table based short integer LOG2
    00138 */
    00139 template<>
    00140 inline bm::gap_word_t ilog2_LUT<bm::gap_word_t>(bm::gap_word_t x)
    00141 {
    00142     unsigned l = 0;
    00143     if (x & 0xff00)
    00144     {
    00145         l += 8; x >>= 8;
    00146     }
    00147     return (bm::gap_word_t)(l + first_bit_table<true>::_idx[x]);
    00148 }
    00149
    00150
    00151 // if we are running on x86 CPU we can use inline ASM
    00152
    00153 #ifdef BM_x86
    00154 #ifdef __GNUG__
    00155
    00156 inline
    00157 unsigned bsf_asm32(unsigned int v)
    00158 {
    00159     unsigned r;
    00160     asm volatile(" bsfl %1, %0": "=r"(r): "rm"(v) );
    00161     return r;
    00162 }
    00163
    00164 BMFORCEINLINE unsigned bsr_asm32(register unsigned int v)
    00165 {
    00166     unsigned r;
    00167     asm volatile(" bsrl %1, %0": "=r"(r): "rm"(v) );
    00168     return r;
    00169 }
    00170
    00171 #endif  // __GNUG__
    00172
    00173 #ifdef _MSC_VER
    00174
    00175 #if defined(_M_AMD64) || defined(_M_X64) // inline assembly not supported
    00176
    00177 BMFORCEINLINE unsigned int bsr_asm32(unsigned int value)
    00178 {
    00179     unsigned long r;
    00180     _BitScanReverse(&r, value);
    00181     return r;
    00182 }
    00183
    00184 BMFORCEINLINE unsigned int bsf_asm32(unsigned int value)
    00185 {
    00186     unsigned long r;
    00187     _BitScanForward(&r, value);
    00188     return r;
    00189 }
    00190
    00191 #else
    00192
    00193 BMFORCEINLINE unsigned int bsr_asm32(register unsigned int value)
    00194 {
    00195   __asm  bsr  eax, value
    00196 }
    00197
    00198 BMFORCEINLINE unsigned int bsf_asm32(register unsigned int value)
    00199 {
    00200   __asm  bsf  eax, value
    00201 }
    00202
    00203 #endif
    00204
    00205 #endif // _MSC_VER
    00206
    00207 #endif // BM_x86
    00208
    00209
    00210
    00211 } // bm
    00212
    00213 #endif