All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
bitOp.h
Go to the documentation of this file.
1 #ifndef OSL_MISC_BITOP_H
2 #define OSL_MISC_BITOP_H
3 
4 #include "osl/config.h"
5 #include <cassert>
6 namespace osl
7 {
8  namespace misc
9  {
13  template <class Integer> struct Bsf;
14 
15  template <>
16  struct Bsf<unsigned int>
17  {
18  static int bsf(unsigned int mask)
19  {
20  assert(mask);
21 #ifdef __x86_64__
22  int ret;
23  __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));
24  return ret;
25 #else /* これ以下は 32bit 環境 */
26 # ifdef __i386__
27  int ret;
28  __asm__("bsfl %1,%0" : "=r"(ret) : "r"(mask));
29  return ret;
30 # elif defined __GNUC__
31  return __builtin_ctzl(mask);
32 # else
33  for (int i=0;i<32;i++)
34  if (mask & (1<<i))
35  return i;
36 # endif
37 #endif
38  assert(0);
39  return -1;
40  }
41  };
42  template <>
43  struct Bsf<unsigned short>
44  {
45  static unsigned short bsf(unsigned short mask)
46  {
47  assert(mask);
48 #ifdef __x86_64__
49  unsigned short ret;
50  __asm__("bsfw %1,%0" : "=r"(ret) : "r"(mask));
51  return ret;
52 #else /* これ以下は 32bit 環境 */
53 # ifdef __i386__
54  unsigned short ret;
55  __asm__("bsfw %1,%0" : "=r"(ret) : "r"(mask));
56  return ret;
57 # else
58  return __builtin_ctzl(mask);
59 # endif
60 #endif
61  }
62  };
63 
64  template <>
65  struct Bsf<unsigned long long>
66  {
67  static int bsf(unsigned long long mask)
68  {
69  assert(mask);
70 #ifdef __x86_64__
71  long long ret;
72  __asm__("bsfq %1,%0" : "=r"(ret) : "r"(mask));
73  return static_cast<int>(ret);
74 #else /* これ以下は 32bit 環境 */
75  unsigned int mask32 = static_cast<unsigned int>(mask);
76  if (mask32)
77  return Bsf<unsigned int>::bsf(mask32);
78  mask32 = static_cast<unsigned int>(mask >> 32);
79  return 32+Bsf<unsigned int>::bsf(mask32);
80 #endif
81  }
82  };
83 
84  template <class Integer> struct Bsr;
85 
86  template <>
87  struct Bsr<unsigned int>
88  {
89  static int bsr(unsigned int mask)
90  {
91  assert(mask);
92 #ifdef __x86_64__
93  int ret;
94  __asm__("bsrl %1,%0" : "=r"(ret) : "r"(mask));
95  return ret;
96 #else /* これ以下は 32bit 環境 */
97 # ifdef __i386__
98  int ret;
99  __asm__("bsrl %1,%0" : "=r"(ret) : "r"(mask));
100  return ret;
101 # elif __GNUC__
102  return __builtin_clzl(mask);
103 # else
104  for (int i=31; i>=0; --i)
105  if (mask & (1<<i))
106  return i;
107 # endif
108 #endif
109  assert(0);
110  return -1;
111  }
112  };
113 
114  template <>
115  struct Bsr<unsigned long long>
116  {
117  static int bsr(unsigned long long mask)
118  {
119  assert(mask);
120 #ifdef __x86_64__
121  long long ret;
122  __asm__("bsrq %1,%0" : "=r"(ret) : "r"(mask));
123  return static_cast<int>(ret);
124 #else /* これ以下は 32bit 環境 */
125  unsigned int mask32 = static_cast<unsigned int>(mask >> 32);
126  if (mask32)
127  return 32+Bsr<unsigned int>::bsr(mask32);
128  mask32 = static_cast<unsigned int>(mask);
129  return Bsr<unsigned int>::bsr(mask32);
130 #endif
131  }
132  };
133 
134  struct BitOp
135  {
136  template <class Integer>
137  static int bsf(Integer mask)
138  {
139  return Bsf<Integer>::bsf(mask);
140  }
141  template <class Integer>
142  static int bsr(Integer mask)
143  {
144  return Bsr<Integer>::bsr(mask);
145  }
146  template <class Integer>
147  static int takeOneBit(Integer& mask){
148  assert(mask);
149  const int num=bsf(mask);
150  mask &= mask-1;
151  return num;
152  }
153 
154  template <class Integer>
155  static int
156 #ifdef __GNUC__
157  __attribute__ ((const))
158 #endif
159  countBit(Integer mask)
160  {
161  int count=0;
162  while (mask)
163  {
164  ++count;
165  mask &= (mask-1);
166  }
167  return count;
168  }
169  template <class Integer>
170  static bool hasMultipleBit(Integer mask){
171  assert(mask);
172  return (mask & (mask-1));
173  }
177  template <class Integer>
178  static Integer lowestBit(Integer mask){
179  assert(mask);
180  return static_cast<Integer>(mask & (-mask));
181  }
182  };
183 
184 #if 0
185 
198  inline int countBitDense(unsigned int mask)
199  {
200  mask = ((mask>>1)&0x55555555)+(mask&0x55555555);
201  mask = ((mask>>2)&0x33333333)+(mask&0x33333333);
202  mask = ((mask>>4)+mask)&0xf0f0f0f;
203  mask = (mask>>8)+mask;
204  return ((mask>>16)+mask)&0x3f;
205  }
206 #endif
207  } // namespace misc
208 } // namespace osl
209 #endif // _BITOP_H
210 // ;;; Local Variables:
211 // ;;; mode:c++
212 // ;;; c-basic-offset:2
213 // ;;; End: