00001 #ifndef BMUTIL__H__INCLUDED__
00002 #define BMUTIL__H__INCLUDED__
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
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
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
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
00066
00067
00068 template<typename T>
00069 T ilog2(T x)
00070 {
00071 unsigned int l = 0;
00072 if(x >= 1<<16) { x>>=16; l |= 16; }
00073 if(x >= 1<<8) { x>>=8; l |= 8; }
00074 if(x >= 1<<4) { x>>=4; l |= 4; }
00075 if(x >= 1<<2) { x>>=2; l |= 2; }
00076 if(x >= 1<<1) l |=1;
00077 return l;
00078 }
00079
00080 template<>
00081 inline bm::gap_word_t ilog2(gap_word_t x)
00082 {
00083 unsigned int l = 0;
00084 if(x >= 1<<8) { x>>=8; l |= 8; }
00085 if(x >= 1<<4) { x>>=4; l |= 4; }
00086 if(x >= 1<<2) { x>>=2; l |= 2; }
00087 if(x >= 1<<1) l |=1;
00088 return l;
00089 }
00090
00091
00092
00093
00094
00095 template<class T>
00096 class ptr_guard
00097 {
00098 public:
00099 ptr_guard(T* p) : ptr_(p) {}
00100 ~ptr_guard() { delete ptr_; }
00101 private:
00102 ptr_guard(const ptr_guard<T>& p);
00103 ptr_guard& operator=(const ptr_guard<T>& p);
00104 private:
00105 T* ptr_;
00106 };
00107
00108
00109
00110
00111 template<typename T>
00112 T ilog2_LUT(T x)
00113 {
00114 unsigned l = 0;
00115 if (x & 0xffff0000)
00116 {
00117 l += 16; x >>= 16;
00118 }
00119
00120 if (x & 0xff00)
00121 {
00122 l += 8; x >>= 8;
00123 }
00124 return l + first_bit_table<true>::_idx[x];
00125 }
00126
00127
00128
00129
00130 template<>
00131 inline bm::gap_word_t ilog2_LUT<bm::gap_word_t>(bm::gap_word_t x)
00132 {
00133 unsigned l = 0;
00134 if (x & 0xff00)
00135 {
00136 l += 8; x >>= 8;
00137 }
00138 return l + first_bit_table<true>::_idx[x];
00139 }
00140
00141
00142
00143
00144 #ifdef BM_x86
00145 #ifdef __GNUG__
00146
00147 inline
00148 unsigned bsf_asm32(unsigned int v)
00149 {
00150 unsigned r;
00151 asm volatile(" bsfl %1, %0": "=r"(r): "rm"(v) );
00152 return r;
00153 }
00154
00155 BMFORCEINLINE unsigned bsr_asm32(register unsigned int v)
00156 {
00157 unsigned r;
00158 asm volatile(" bsrl %1, %0": "=r"(r): "rm"(v) );
00159 return r;
00160 }
00161
00162 #endif // __GNUG__
00163
00164 #ifdef _MSC_VER
00165
00166 #if defined(_M_AMD64) || defined(_M_X64) // inline assembly not supported
00167
00168 BMFORCEINLINE unsigned int bsr_asm32(unsigned int value)
00169 {
00170 unsigned long r;
00171 _BitScanReverse(&r, value);
00172 return r;
00173 }
00174
00175 BMFORCEINLINE unsigned int bsf_asm32(unsigned int value)
00176 {
00177 unsigned long r;
00178 _BitScanForward(&r, value);
00179 return r;
00180 }
00181
00182 #else
00183
00184 BMFORCEINLINE unsigned int bsr_asm32(register unsigned int value)
00185 {
00186 __asm bsr eax, value
00187 }
00188
00189 BMFORCEINLINE unsigned int bsf_asm32(register unsigned int value)
00190 {
00191 __asm bsf eax, value
00192 }
00193
00194 #endif
00195
00196 #endif // _MSC_VER
00197
00198 #endif // BM_x86
00199
00200
00201
00202 }
00203
00204 #endif