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
7namespace 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:
217 public:
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); }
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:
GeneralMask & operator|=(const GeneralMask &r)
Definition mask.h:225
bool none() const
Definition mask.h:297
GeneralMask & operator+=(const GeneralMask &r)
Definition mask.h:240
GeneralMask & operator<<=(int shift)
Definition mask.h:245
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
GeneralMask & operator>>=(int shift)
Definition mask.h:250
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
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:220
bool operator==(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
Definition mask.h:303
const GeneralMask< Integer > operator^(GeneralMask< Integer > l, GeneralMask< Integer > r)
Definition mask.h:331
bool operator<(const GeneralMask< Integer > &l, const GeneralMask< Integer > &r)
Definition mask.h:313
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 > m, int shift)
Definition mask.h:342
const GeneralMask< Integer > operator|(GeneralMask< Integer > l, GeneralMask< Integer > r)
Definition mask.h:325
GeneralMask< unsigned long long > Mask64
Definition mask.h:347
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
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