dlvhex  2.5.0
vs12/bm/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 
00067 template<typename T>
00068 T min_value(T v1, T v2)
00069 {
00070     return v1 < v2 ? v1 : v2;
00071 }
00072 
00073 
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 
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 
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 
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