ReactOS  0.4.14-dev-614-gbfd8a84
bitops.h
Go to the documentation of this file.
1 #ifndef _LINUX_BITOPS_H
2 #define _LINUX_BITOPS_H
3 
4 #include <ntifs.h>
5 #include <linux/types.h>
6 
7 #ifdef __KERNEL__
8 #define BIT(nr) (1 << (nr))
9 #define BIT_MASK(nr) (1 << ((nr) % BITS_PER_LONG))
10 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
11 #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_LONG)
12 #define BITS_PER_BYTE 8
13 #endif
14 
15 /*
16  * Include this here because some architectures need generic_ffs/fls in
17  * scope
18  */
19 
28 #define find_first_zero_bit(addr, size) find_next_zero_bit((addr), (size), 0)
29 
36 int find_next_zero_bit(const unsigned long *addr, int size, int offset);
37 
44 static inline unsigned long __ffs(unsigned long word)
45 {
46  int num = 0;
47 
48 #if BITS_PER_LONG == 64
49  if ((word & 0xffffffff) == 0) {
50  num += 32;
51  word >>= 32;
52  }
53 #endif
54  if ((word & 0xffff) == 0) {
55  num += 16;
56  word >>= 16;
57  }
58  if ((word & 0xff) == 0) {
59  num += 8;
60  word >>= 8;
61  }
62  if ((word & 0xf) == 0) {
63  num += 4;
64  word >>= 4;
65  }
66  if ((word & 0x3) == 0) {
67  num += 2;
68  word >>= 2;
69  }
70  if ((word & 0x1) == 0)
71  num += 1;
72  return num;
73 }
74 
83 static inline unsigned find_first_bit(const unsigned long *addr, unsigned size)
84 {
85  unsigned x = 0;
86 
87  while (x < size) {
88  unsigned long val = *addr++;
89  if (val)
90  return __ffs(val) + x;
91  x += (sizeof(*addr)<<3);
92  }
93  return x;
94 }
95 
103 #pragma message("WARNINGS: find_next_bit NOT implemented ...")
104 
105 #if _X86_
106 int find_next_bit(const unsigned long *addr, int size, int offset)
107 {
108  const unsigned long *p = addr + (offset >> 5);
109  int set = 0, bit = offset & 31, res = 0;
110 #if 0
111  if (bit) {
112 
113  /*
114  * Look for nonzero in the first 32 bits:
115  */
116  __asm__("bsfl %1,%0\n\t"
117  "jne 1f\n\t"
118  "movl $32, %0\n"
119  "1:"
120  : "=r" (set)
121  : "r" (*p >> bit));
122 
123  if (set < (32 - bit))
124  return set + offset;
125  set = 32 - bit;
126  p++;
127  }
128  /*
129  * No set bit yet, search remaining full words for a bit
130  */
131  res = find_first_bit (p, size - 32 * (p - addr));
132 #endif
133  return (offset + set + res);
134 }
135 #else /* _X64_ */
136 long find_next_bit(const unsigned long * addr, long size, long offset)
137 {
138  const unsigned long * p = addr + (offset >> 6);
139  unsigned long set = 0, bit = offset & 63, res = 0;
140 
141 #if 0
142  if (bit) {
143  /*
144  * Look for nonzero in the first 64 bits:
145  */
146  asm("bsfq %1,%0\n\t"
147  "cmoveq %2,%0\n\t"
148  : "=r" (set)
149  : "r" (*p >> bit), "r" (64L));
150  if (set < (64 - bit))
151  return set + offset;
152  set = 64 - bit;
153  p++;
154  }
155  /*
156  * No set bit yet, search remaining full words for a bit
157  */
158  res = find_first_bit (p, size - 64 * (p - addr));
159 #endif
160 
161  return (offset + set + res);
162 }
163 #endif /* _X86_ */
164 
165 /*
166  * ffz - find first zero in word.
167  * @word: The word to search
168  *
169  * Undefined if no zero exists, so code should check against ~0UL first.
170  */
171 #define ffz(x) __ffs(~(x))
172 
173 
182 static inline int ffs(int x)
183 {
184  int r = 1;
185 
186  if (!x)
187  return 0;
188  if (!(x & 0xffff)) {
189  x >>= 16;
190  r += 16;
191  }
192  if (!(x & 0xff)) {
193  x >>= 8;
194  r += 8;
195  }
196  if (!(x & 0xf)) {
197  x >>= 4;
198  r += 4;
199  }
200  if (!(x & 3)) {
201  x >>= 2;
202  r += 2;
203  }
204  if (!(x & 1)) {
205  x >>= 1;
206  r += 1;
207  }
208  return r;
209 }
210 
219 static inline int fls(int x)
220 {
221  int r = 32;
222 
223  if (!x)
224  return 0;
225  if (!(x & 0xffff0000u)) {
226  x <<= 16;
227  r -= 16;
228  }
229  if (!(x & 0xff000000u)) {
230  x <<= 8;
231  r -= 8;
232  }
233  if (!(x & 0xf0000000u)) {
234  x <<= 4;
235  r -= 4;
236  }
237  if (!(x & 0xc0000000u)) {
238  x <<= 2;
239  r -= 2;
240  }
241  if (!(x & 0x80000000u)) {
242  x <<= 1;
243  r -= 1;
244  }
245  return r;
246 }
247 
248 static inline int fls64(__u64 x)
249 {
250  __u32 h = (__u32) (x >> 32);
251  if (h)
252  return fls(h) + 32;
253  return fls((int)x);
254 }
255 
256 #define for_each_bit(bit, addr, size) \
257  for ((bit) = find_first_bit((addr), (size)); \
258  (bit) < (size); \
259  (bit) = find_next_bit((addr), (size), (bit) + 1))
260 
261 
262 static __inline int get_bitmask_order(unsigned int count)
263 {
264  int order;
265 
266  order = fls(count);
267  return order; /* We could be slightly more clever with -1 here... */
268 }
269 
270 static __inline int get_count_order(unsigned int count)
271 {
272  int order;
273 
274  order = fls(count) - 1;
275  if (count & (count - 1))
276  order++;
277  return order;
278 }
279 
280 
286 static inline __u32 rol32(__u32 word, unsigned int shift)
287 {
288  return (word << shift) | (word >> (32 - shift));
289 }
290 
296 static inline __u32 ror32(__u32 word, unsigned int shift)
297 {
298  return (word >> shift) | (word << (32 - shift));
299 }
300 
301 static inline unsigned fls_long(unsigned long l)
302 {
303  if (sizeof(l) == 4)
304  return fls(l);
305  return fls64(l);
306 }
307 
308 /*
309  * hweightN: returns the hamming weight (i.e. the number
310  * of bits set) of a N-bit word
311  */
312 
313 static inline unsigned long hweight32(unsigned long w)
314 {
315  unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
316  res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
317  res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
318  res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF);
319  return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
320 }
321 
322 static inline unsigned long hweight64(__u64 w)
323 {
324 #if BITS_PER_LONG < 64
325  return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w);
326 #else
327  u64 res;
328  res = (w & 0x5555555555555555U) + ((w >> 1) & 0x5555555555555555U);
329  res = (res & 0x3333333333333333U) + ((res >> 2) & 0x3333333333333333U);
330  res = (res & 0x0F0F0F0F0F0F0F0FU) + ((res >> 4) & 0x0F0F0F0F0F0F0F0FU);
331  res = (res & 0x00FF00FF00FF00FFU) + ((res >> 8) & 0x00FF00FF00FF00FFU);
332  res = (res & 0x0000FFFF0000FFFFU) + ((res >> 16) & 0x0000FFFF0000FFFFU);
333  return (res & 0x00000000FFFFFFFFU) + ((res >> 32) & 0x00000000FFFFFFFFU);
334 #endif
335 }
336 
337 static inline unsigned long hweight_long(unsigned long w)
338 {
339  return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
340 }
341 
342 #endif
static __u32 ror32(__u32 word, unsigned int shift)
Definition: bitops.h:296
static __inline int get_count_order(unsigned int count)
Definition: bitops.h:270
GLuint GLdouble GLdouble GLint GLint order
Definition: glext.h:11194
static int ffs(int x)
Definition: bitops.h:182
#define shift
Definition: input.c:1761
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
static unsigned long hweight_long(unsigned long w)
Definition: bitops.h:337
static __u32 rol32(__u32 word, unsigned int shift)
Definition: bitops.h:286
static int fls64(__u64 x)
Definition: bitops.h:248
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLuint GLuint GLsizei count
Definition: gl.h:1545
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG x1
Definition: winddi.h:3706
#define U(x)
Definition: wordpad.c:44
GLintptr offset
Definition: glext.h:5920
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
static unsigned long hweight64(__u64 w)
Definition: bitops.h:322
int find_next_zero_bit(const unsigned long *addr, int size, int offset)
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
static unsigned long hweight32(unsigned long w)
Definition: bitops.h:313
long find_next_bit(const unsigned long *addr, long size, long offset)
Definition: bitops.h:136
__asm__("\t.globl GetPhys\n" "GetPhys:\t\n" "mflr 0\n\t" "stwu 0,-16(1)\n\t" "mfmsr 5\n\t" "andi. 6,5,0xffef\n\t" "mtmsr 6\n\t" "isync\n\t" "sync\n\t" "lwz 3,0(3)\n\t" "mtmsr 5\n\t" "isync\n\t" "sync\n\t" "lwz 0,0(1)\n\t" "addi 1,1,16\n\t" "mtlr 0\n\t" "blr")
GLuint GLfloat * val
Definition: glext.h:7180
r l[0]
Definition: byte_order.h:167
static unsigned fls_long(unsigned long l)
Definition: bitops.h:301
GLsizeiptr size
Definition: glext.h:5919
static int fls(int x)
Definition: bitops.h:219
static UINT set(struct ID3DXConstantTableImpl *table, IDirect3DDevice9 *device, struct ctab_constant *constant, const void **indata, D3DXPARAMETER_TYPE intype, UINT *size, UINT incol, D3DXPARAMETER_CLASS inclass, UINT index, BOOL is_pointer)
Definition: shader.c:1095
GLuint GLuint num
Definition: glext.h:9618
unsigned int __u32
Definition: compat.h:90
ULONG64 u64
Definition: btrfs.h:15
GLenum const GLvoid * addr
Definition: glext.h:9621
static const WCHAR L[]
Definition: oid.c:1250
static unsigned long __ffs(unsigned long word)
Definition: bitops.h:44
static __inline int get_bitmask_order(unsigned int count)
Definition: bitops.h:262
u64 __u64
Definition: btrfs.h:20
const WCHAR * word
Definition: lex.c:36
static unsigned find_first_bit(const unsigned long *addr, unsigned size)
Definition: bitops.h:83
GLuint res
Definition: glext.h:9613
GLfloat GLfloat p
Definition: glext.h:8902
Definition: _set.h:46