説明を見る。00001 #ifndef OSL_MISC_MASK_H
00002 #define OSL_MISC_MASK_H
00003 #include "osl/config.h"
00004 #include <cassert>
00005 #include <iosfwd>
00006
00007 namespace osl
00008 {
00009 namespace misc
00010 {
00014 template <class Integer> struct Bsf;
00015
00016 template <>
00017 struct Bsf<unsigned int>
00018 {
00019 static int bsf(unsigned int mask)
00020 {
00021 assert(mask);
00022 #ifdef __x86_64__
00023 int ret;
00024 __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));
00025 return ret;
00026 #else
00027 # ifdef __i386__
00028 int ret;
00029 __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));
00030 return ret;
00031 # elif defined __GNUC__
00032 return __builtin_ctzl(mask);
00033 # else
00034 for (int i=0;i<32;i++)
00035 if (mask & (1<<i))
00036 return i;
00037 # endif
00038 #endif
00039 assert(0);
00040 return -1;
00041 }
00042 };
00043 template <>
00044 struct Bsf<unsigned short>
00045 {
00046 static unsigned short bsf(unsigned short mask)
00047 {
00048 assert(mask);
00049 #ifdef __x86_64__
00050 unsigned short ret;
00051 __asm__("bsfw %1,%0" : "=r"(ret) : "r"(mask));
00052 return ret;
00053 #else
00054 # ifdef __i386__
00055 unsigned short ret;
00056 __asm__("bsfw %1,%0" : "=r"(ret) : "r"(mask));
00057 return ret;
00058 # else
00059 return __builtin_ctzl(mask);
00060 # endif
00061 #endif
00062 }
00063 };
00064
00065 template <>
00066 struct Bsf<unsigned long long>
00067 {
00068 static int bsf(unsigned long long mask)
00069 {
00070 assert(mask);
00071 #ifdef __x86_64__
00072 long long ret;
00073 __asm__("bsfq %1,%0" : "=r"(ret) : "r"(mask));
00074 return static_cast<int>(ret);
00075 #else
00076 unsigned int mask32 = static_cast<unsigned int>(mask);
00077 if (mask32)
00078 return Bsf<unsigned int>::bsf(mask32);
00079 mask32 = static_cast<unsigned int>(mask >> 32);
00080 return 32+Bsf<unsigned int>::bsf(mask32);
00081 #endif
00082 }
00083 };
00084
00085 template <class Integer> struct Bsr;
00086
00087 template <>
00088 struct Bsr<unsigned int>
00089 {
00090 static int bsr(unsigned int mask)
00091 {
00092 assert(mask);
00093 #ifdef __x86_64__
00094 int ret;
00095 __asm__("bsrl %1,%0" : "=r"(ret) : "r"(mask));
00096 return ret;
00097 #else
00098 # ifdef __i386__
00099 int ret;
00100 __asm__("bsrl %1,%0" : "=r"(ret) : "r"(mask));
00101 return ret;
00102 # elif __GNUC__
00103 return __builtin_clzl(mask);
00104 # else
00105 for (int i=31; i>=0; --i)
00106 if (mask & (1<<i))
00107 return i;
00108 # endif
00109 #endif
00110 assert(0);
00111 return -1;
00112 }
00113 };
00114
00115 template <>
00116 struct Bsr<unsigned long long>
00117 {
00118 static int bsr(unsigned long long mask)
00119 {
00120 assert(mask);
00121 #ifdef __x86_64__
00122 long long ret;
00123 __asm__("bsrq %1,%0" : "=r"(ret) : "r"(mask));
00124 return static_cast<int>(ret);
00125 #else
00126 unsigned int mask32 = static_cast<unsigned int>(mask >> 32);
00127 if (mask32)
00128 return 32+Bsr<unsigned int>::bsr(mask32);
00129 mask32 = static_cast<unsigned int>(mask);
00130 return Bsr<unsigned int>::bsr(mask32);
00131 #endif
00132 }
00133 };
00134
00135 struct BitOp
00136 {
00137 template <class Integer>
00138 static int bsf(Integer mask)
00139 {
00140 return Bsf<Integer>::bsf(mask);
00141 }
00142 template <class Integer>
00143 static int bsr(Integer mask)
00144 {
00145 return Bsr<Integer>::bsr(mask);
00146 }
00147 template <class Integer>
00148 static int takeOneBit(Integer& mask){
00149 assert(mask);
00150 const int num=bsf(mask);
00151 mask &= mask-1;
00152 return num;
00153 }
00154
00155 template <class Integer>
00156 static int
00157 #ifdef __GNUC__
00158 __attribute__ ((const))
00159 #endif
00160 countBit(Integer mask)
00161 {
00162 int count=0;
00163 while (mask)
00164 {
00165 ++count;
00166 mask &= (mask-1);
00167 }
00168 return count;
00169 }
00170 template <class Integer>
00171 static bool hasMultipleBit(Integer mask){
00172 assert(mask);
00173 return (mask & (mask-1));
00174 }
00178 template <class Integer>
00179 static Integer lowestBit(Integer mask){
00180 assert(mask);
00181 return static_cast<Integer>(mask & (-mask));
00182 }
00183 };
00184
00185 #if 0
00186
00199 inline int countBitDense(unsigned int mask)
00200 {
00201 mask = ((mask>>1)&0x55555555)+(mask&0x55555555);
00202 mask = ((mask>>2)&0x33333333)+(mask&0x33333333);
00203 mask = ((mask>>4)+mask)&0xf0f0f0f;
00204 mask = (mask>>8)+mask;
00205 return ((mask>>16)+mask)&0x3f;
00206 }
00207 #endif
00208 }
00209 namespace misc
00210 {
00211 template <class Integer>
00212 class GeneralMask
00213 {
00214 Integer mask;
00215 private:
00216 GeneralMask(Integer value) : mask(value) {}
00217 public:
00218 GeneralMask() : mask(0) {}
00219 static const GeneralMask makeDirect(Integer value) { return GeneralMask(value); }
00220 GeneralMask& operator&=(const GeneralMask& r)
00221 {
00222 mask &= r.mask;
00223 return *this;
00224 }
00225 GeneralMask& operator|=(const GeneralMask& r)
00226 {
00227 mask |= r.mask;
00228 return *this;
00229 }
00230 GeneralMask& operator^=(const GeneralMask& r)
00231 {
00232 mask ^= r.mask;
00233 return *this;
00234 }
00235 GeneralMask& operator-=(const GeneralMask& r)
00236 {
00237 mask -= r.mask;
00238 return *this;
00239 }
00240 GeneralMask& operator+=(const GeneralMask& r)
00241 {
00242 mask += r.mask;
00243 return *this;
00244 }
00245 GeneralMask& operator<<=(int shift)
00246 {
00247 mask <<= shift;
00248 return *this;
00249 }
00250 GeneralMask& operator>>=(int shift)
00251 {
00252 mask >>= shift;
00253 return *this;
00254 }
00255 const GeneralMask operator~() const { return GeneralMask(~mask); }
00256
00257 int bsf() const { return BitOp::bsf(mask); }
00258 int bsr() const { return BitOp::bsr(mask); }
00265 int takeOneBit() { return BitOp::takeOneBit(mask); }
00266
00272 bool hasMultipleBit() const { return BitOp::hasMultipleBit(mask); }
00278 int countBit2() const {
00279 assert(mask);
00280 return (mask & (mask-1)) ? 2 : 1;
00281 }
00286 int
00287 #ifdef __GNUC__
00288 __attribute__ ((pure))
00289 #endif
00290 countBit() const { return BitOp::countBit(mask); }
00296 GeneralMask lowestBit() const { return BitOp::lowestBit(mask); }
00297 bool none() const { return mask == 0; }
00298 bool any() const { return ! none(); }
00299 Integer value() const { return mask; }
00300 };
00301
00302 template <class Integer> inline
00303 bool operator==(const GeneralMask<Integer>& l, const GeneralMask<Integer>& r)
00304 {
00305 return l.value() == r.value();
00306 }
00307 template <class Integer> inline
00308 bool operator!=(const GeneralMask<Integer>& l, const GeneralMask<Integer>& r)
00309 {
00310 return ! (l == r);
00311 }
00312 template <class Integer> inline
00313 bool operator<(const GeneralMask<Integer>& l, const GeneralMask<Integer>& r)
00314 {
00315 return l.value() < r.value();
00316 }
00317
00318 template <class Integer> inline
00319 const GeneralMask<Integer> operator&(GeneralMask<Integer> l,
00320 GeneralMask<Integer> r) {
00321 GeneralMask<Integer> result = l;
00322 return result &= r;
00323 }
00324 template <class Integer> inline
00325 const GeneralMask<Integer> operator|(GeneralMask<Integer> l,
00326 GeneralMask<Integer> r) {
00327 GeneralMask<Integer> result = l;
00328 return result |= r;
00329 }
00330 template <class Integer> inline
00331 const GeneralMask<Integer> operator^(GeneralMask<Integer> l,
00332 GeneralMask<Integer> r) {
00333 GeneralMask<Integer> result = l;
00334 return result ^= r;
00335 }
00336 template <class Integer> inline
00337 const GeneralMask<Integer> operator<<(GeneralMask<Integer> m, int shift) {
00338 GeneralMask<Integer> result = m;
00339 return result <<= shift;
00340 }
00341 template <class Integer> inline
00342 const GeneralMask<Integer> operator>>(GeneralMask<Integer> m, int shift) {
00343 GeneralMask<Integer> result = m;
00344 return result >>= shift;
00345 }
00346
00347 typedef GeneralMask<unsigned long long> Mask64;
00348
00349
00350 typedef unsigned long long mask_int_t;
00351 typedef GeneralMask<mask_int_t> mask_t;
00352
00353 std::ostream& operator<<(std::ostream&, const mask_t&);
00354 }
00355 using misc::mask_int_t;
00356 using misc::mask_t;
00357 using misc::Mask64;
00358 using misc::BitOp;
00359 }
00360
00361 #endif
00362
00363
00364
00365