My Project
mask.h
Go to the documentation of this file.
1 #ifndef OSL_MISC_MASK_H
2 #define OSL_MISC_MASK_H
3 #include "osl/config.h"
4 #include <cassert>
5 #include <iosfwd>
6 
7 namespace osl
8 {
9  namespace misc
10  {
14  template <class Integer> struct Bsf;
15 
16  template <>
17  struct Bsf<unsigned int>
18  {
19  static int bsf(unsigned int mask)
20  {
21  assert(mask);
22 #ifdef __x86_64__
23  int ret;
24  __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));
25  return ret;
26 #else /* これ以下は 32bit 環境 */
27 # ifdef __i386__
28  int ret;
29  __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));
30  return ret;
31 # elif defined __GNUC__
32  return __builtin_ctzl(mask);
33 # else
34  for (int i=0;i<32;i++)
35  if (mask & (1<<i))
36  return i;
37 # endif
38 #endif
39  assert(0);
40  return -1;
41  }
42  };
43  template <>
44  struct Bsf<unsigned short>
45  {
46  static unsigned short bsf(unsigned short mask)
47  {
48  assert(mask);
49 #ifdef __x86_64__
50  unsigned short ret;
51  __asm__("bsfw %1,%0" : "=r"(ret) : "r"(mask));
52  return ret;
53 #else /* これ以下は 32bit 環境 */
54 # ifdef __i386__
55  unsigned short ret;
56  __asm__("bsfw %1,%0" : "=r"(ret) : "r"(mask));
57  return ret;
58 # else
59  return __builtin_ctzl(mask);
60 # endif
61 #endif
62  }
63  };
64 
65  template <>
66  struct Bsf<unsigned long long>
67  {
68  static int bsf(unsigned long long mask)
69  {
70  assert(mask);
71 #ifdef __x86_64__
72  long long ret;
73  __asm__("bsfq %1,%0" : "=r"(ret) : "r"(mask));
74  return static_cast<int>(ret);
75 #else /* これ以下は 32bit 環境 */
76  unsigned int mask32 = static_cast<unsigned int>(mask);
77  if (mask32)
78  return Bsf<unsigned int>::bsf(mask32);
79  mask32 = static_cast<unsigned int>(mask >> 32);
80  return 32+Bsf<unsigned int>::bsf(mask32);
81 #endif
82  }
83  };
84 
85  template <class Integer> struct Bsr;
86 
87  template <>
88  struct Bsr<unsigned int>
89  {
90  static int bsr(unsigned int mask)
91  {
92  assert(mask);
93 #ifdef __x86_64__
94  int ret;
95  __asm__("bsrl %1,%0" : "=r"(ret) : "r"(mask));
96  return ret;
97 #else /* これ以下は 32bit 環境 */
98 # ifdef __i386__
99  int ret;
100  __asm__("bsrl %1,%0" : "=r"(ret) : "r"(mask));
101  return ret;
102 # elif __GNUC__
103  return __builtin_clzl(mask);
104 # else
105  for (int i=31; i>=0; --i)
106  if (mask & (1<<i))
107  return i;
108 # endif
109 #endif
110  assert(0);
111  return -1;
112  }
113  };
114 
115  template <>
116  struct Bsr<unsigned long long>
117  {
118  static int bsr(unsigned long long mask)
119  {
120  assert(mask);
121 #ifdef __x86_64__
122  long long ret;
123  __asm__("bsrq %1,%0" : "=r"(ret) : "r"(mask));
124  return static_cast<int>(ret);
125 #else /* これ以下は 32bit 環境 */
126  unsigned int mask32 = static_cast<unsigned int>(mask >> 32);
127  if (mask32)
128  return 32+Bsr<unsigned int>::bsr(mask32);
129  mask32 = static_cast<unsigned int>(mask);
130  return Bsr<unsigned int>::bsr(mask32);
131 #endif
132  }
133  };
134 
135  struct BitOp
136  {
137  template <class Integer>
138  static int bsf(Integer mask)
139  {
140  return Bsf<Integer>::bsf(mask);
141  }
142  template <class Integer>
143  static int bsr(Integer mask)
144  {
145  return Bsr<Integer>::bsr(mask);
146  }
147  template <class Integer>
148  static int takeOneBit(Integer& mask){
149  assert(mask);
150  const int num=bsf(mask);
151  mask &= mask-1;
152  return num;
153  }
154 
155  template <class Integer>
156  static int
157 #ifdef __GNUC__
158  __attribute__ ((const))
159 #endif
160  countBit(Integer mask)
161  {
162  int count=0;
163  while (mask)
164  {
165  ++count;
166  mask &= (mask-1);
167  }
168  return count;
169  }
170  template <class Integer>
171  static bool hasMultipleBit(Integer mask){
172  assert(mask);
173  return (mask & (mask-1));
174  }
178  template <class Integer>
179  static Integer lowestBit(Integer mask){
180  assert(mask);
181  return static_cast<Integer>(mask & (-mask));
182  }
183  };
184 
185 #if 0
199  inline int countBitDense(unsigned int mask)
200  {
201  mask = ((mask>>1)&0x55555555)+(mask&0x55555555);
202  mask = ((mask>>2)&0x33333333)+(mask&0x33333333);
203  mask = ((mask>>4)+mask)&0xf0f0f0f;
204  mask = (mask>>8)+mask;
205  return ((mask>>16)+mask)&0x3f;
206  }
207 #endif
208  } // namespace misc
209  namespace misc
210  {
211  template <class Integer>
213  {
214  Integer mask;
215  private:
216  GeneralMask(Integer value) : mask(value) {}
217  public:
218  GeneralMask() : mask(0) {}
219  static const GeneralMask makeDirect(Integer value) { return GeneralMask(value); }
221  {
222  mask &= r.mask;
223  return *this;
224  }
226  {
227  mask |= r.mask;
228  return *this;
229  }
231  {
232  mask ^= r.mask;
233  return *this;
234  }
236  {
237  mask -= r.mask;
238  return *this;
239  }
241  {
242  mask += r.mask;
243  return *this;
244  }
246  {
247  mask <<= shift;
248  return *this;
249  }
251  {
252  mask >>= shift;
253  return *this;
254  }
255  const GeneralMask operator~() const { return GeneralMask(~mask); }
256 
257  int bsf() const { return BitOp::bsf(mask); }
258  int bsr() const { return BitOp::bsr(mask); }
265  int takeOneBit() { return BitOp::takeOneBit(mask); }
266 
272  bool hasMultipleBit() const { return BitOp::hasMultipleBit(mask); }
278  int countBit2() const {
279  assert(mask);
280  return (mask & (mask-1)) ? 2 : 1;
281  }
286  int
287 #ifdef __GNUC__
288  __attribute__ ((pure))
289 #endif
290  countBit() const { return BitOp::countBit(mask); }
297  bool none() const { return mask == 0; }
298  bool any() const { return ! none(); }
299  Integer value() const { return mask; }
300  };
301 
302  template <class Integer> inline
304  {
305  return l.value() == r.value();
306  }
307  template <class Integer> inline
309  {
310  return ! (l == r);
311  }
312  template <class Integer> inline
314  {
315  return l.value() < r.value();
316  }
317 
318  template <class Integer> inline
321  GeneralMask<Integer> result = l;
322  return result &= r;
323  }
324  template <class Integer> inline
327  GeneralMask<Integer> result = l;
328  return result |= r;
329  }
330  template <class Integer> inline
333  GeneralMask<Integer> result = l;
334  return result ^= r;
335  }
336  template <class Integer> inline
338  GeneralMask<Integer> result = m;
339  return result <<= shift;
340  }
341  template <class Integer> inline
343  GeneralMask<Integer> result = m;
344  return result >>= shift;
345  }
346 
348 
349 
350  typedef unsigned long long mask_int_t;
352 
353  std::ostream& operator<<(std::ostream&, const mask_t&);
354  } // namespace misc
355  using misc::mask_int_t;
356  using misc::mask_t;
357  using misc::Mask64;
358  using misc::BitOp;
359 } // namespace osl
360 
361 #endif
362 // ;;; Local Variables:
363 // ;;; mode:c++
364 // ;;; c-basic-offset:2
365 // ;;; End:
bool none() const
Definition: mask.h:297
GeneralMask & operator>>=(int shift)
Definition: mask.h:250
static const GeneralMask makeDirect(Integer value)
Definition: mask.h:219
GeneralMask(Integer value)
Definition: mask.h:216
const GeneralMask operator~() const
Definition: mask.h:255
int bsr() const
Definition: mask.h:258
Integer value() const
Definition: mask.h:299
bool hasMultipleBit() const
non-zeroのmaskが複数ビットセットされているかどうかを返す.
Definition: mask.h:272
bool any() const
Definition: mask.h:298
int countBit() const
mask にセットされているビットの数を数える. あまり速くない.
Definition: mask.h:290
GeneralMask & operator-=(const GeneralMask &r)
Definition: mask.h:235
GeneralMask & operator&=(const GeneralMask &r)
Definition: mask.h:220
GeneralMask & operator<<=(int shift)
Definition: mask.h:245
GeneralMask & operator+=(const GeneralMask &r)
Definition: mask.h:240
int countBit2() const
non-zeroのmaskにセットされているビットの数を2まで数える.
Definition: mask.h:278
GeneralMask & operator^=(const GeneralMask &r)
Definition: mask.h:230
int bsf() const
Definition: mask.h:257
int takeOneBit()
non-zeroのmaskのsetされているビットをLSBから探し,その番号を返す 副作用としてmaskの対応するビットをクリアする
Definition: mask.h:265
GeneralMask lowestBit() const
non-zeroのmaskのsetされているビットをLSBから探し,そのビットだけがsetされたmaskを返す.
Definition: mask.h:296
GeneralMask & operator|=(const GeneralMask &r)
Definition: mask.h:225
bool operator==(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
Definition: mask.h:303
const GeneralMask< Integer > operator>>(GeneralMask< Integer > m, int shift)
Definition: mask.h:342
bool operator<(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
Definition: mask.h:313
const GeneralMask< Integer > operator^(GeneralMask< Integer > l, GeneralMask< Integer > r)
Definition: mask.h:331
GeneralMask< mask_int_t > mask_t
Definition: mask.h:351
bool operator!=(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
Definition: mask.h:308
unsigned long long mask_int_t
Definition: mask.h:350
const GeneralMask< Integer > operator&(GeneralMask< Integer > l, GeneralMask< Integer > r)
Definition: mask.h:319
const GeneralMask< Integer > operator<<(GeneralMask< Integer > m, int shift)
Definition: mask.h:337
GeneralMask< unsigned long long > Mask64
Definition: mask.h:347
const GeneralMask< Integer > operator|(GeneralMask< Integer > l, GeneralMask< Integer > r)
Definition: mask.h:325
const PtypeO PTYPEO_EDGE __attribute__((unused))
static int bsf(Integer mask)
Definition: mask.h:138
static int takeOneBit(Integer &mask)
Definition: mask.h:148
static int bsr(Integer mask)
Definition: mask.h:143
static bool hasMultipleBit(Integer mask)
Definition: mask.h:171
static Integer lowestBit(Integer mask)
non-zeroのmaskのsetされているビットをLSBから探し,そのビットだけがsetされたmaskを返す.
Definition: mask.h:179
static int countBit(Integer mask)
Definition: mask.h:160
static int bsf(unsigned int mask)
Definition: mask.h:19
static int bsf(unsigned long long mask)
Definition: mask.h:68
static unsigned short bsf(unsigned short mask)
Definition: mask.h:46
x86 bsf 命令
Definition: mask.h:14
static int bsr(unsigned int mask)
Definition: mask.h:90
static int bsr(unsigned long long mask)
Definition: mask.h:118