ReactOS  0.4.13-dev-544-gede3fdd
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 /*
104  * ffz - find first zero in word.
105  * @word: The word to search
106  *
107  * Undefined if no zero exists, so code should check against ~0UL first.
108  */
109 #define ffz(x) __ffs(~(x))
110 
111 
120 static inline int ffs(int x)
121 {
122  int r = 1;
123 
124  if (!x)
125  return 0;
126  if (!(x & 0xffff)) {
127  x >>= 16;
128  r += 16;
129  }
130  if (!(x & 0xff)) {
131  x >>= 8;
132  r += 8;
133  }
134  if (!(x & 0xf)) {
135  x >>= 4;
136  r += 4;
137  }
138  if (!(x & 3)) {
139  x >>= 2;
140  r += 2;
141  }
142  if (!(x & 1)) {
143  x >>= 1;
144  r += 1;
145  }
146  return r;
147 }
148 
157 static inline int fls(int x)
158 {
159  int r = 32;
160 
161  if (!x)
162  return 0;
163  if (!(x & 0xffff0000u)) {
164  x <<= 16;
165  r -= 16;
166  }
167  if (!(x & 0xff000000u)) {
168  x <<= 8;
169  r -= 8;
170  }
171  if (!(x & 0xf0000000u)) {
172  x <<= 4;
173  r -= 4;
174  }
175  if (!(x & 0xc0000000u)) {
176  x <<= 2;
177  r -= 2;
178  }
179  if (!(x & 0x80000000u)) {
180  x <<= 1;
181  r -= 1;
182  }
183  return r;
184 }
185 
186 static inline int fls64(__u64 x)
187 {
188  __u32 h = (__u32) (x >> 32);
189  if (h)
190  return fls(h) + 32;
191  return fls((int)x);
192 }
193 
194 #define for_each_bit(bit, addr, size) \
195  for ((bit) = find_first_bit((addr), (size)); \
196  (bit) < (size); \
197  (bit) = find_next_bit((addr), (size), (bit) + 1))
198 
199 
200 static __inline int get_bitmask_order(unsigned int count)
201 {
202  int order;
203 
204  order = fls(count);
205  return order; /* We could be slightly more clever with -1 here... */
206 }
207 
208 static __inline int get_count_order(unsigned int count)
209 {
210  int order;
211 
212  order = fls(count) - 1;
213  if (count & (count - 1))
214  order++;
215  return order;
216 }
217 
218 
224 static inline __u32 rol32(__u32 word, unsigned int shift)
225 {
226  return (word << shift) | (word >> (32 - shift));
227 }
228 
234 static inline __u32 ror32(__u32 word, unsigned int shift)
235 {
236  return (word >> shift) | (word << (32 - shift));
237 }
238 
239 static inline unsigned fls_long(unsigned long l)
240 {
241  if (sizeof(l) == 4)
242  return fls(l);
243  return fls64(l);
244 }
245 
246 /*
247  * hweightN: returns the hamming weight (i.e. the number
248  * of bits set) of a N-bit word
249  */
250 
251 static inline unsigned long hweight32(unsigned long w)
252 {
253  unsigned int res = (w & 0x55555555) + ((w >> 1) & 0x55555555);
254  res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
255  res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
256  res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF);
257  return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
258 }
259 
260 static inline unsigned long hweight64(__u64 w)
261 {
262 #if BITS_PER_LONG < 64
263  return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w);
264 #else
265  u64 res;
266  res = (w & 0x5555555555555555U) + ((w >> 1) & 0x5555555555555555U);
267  res = (res & 0x3333333333333333U) + ((res >> 2) & 0x3333333333333333U);
268  res = (res & 0x0F0F0F0F0F0F0F0FU) + ((res >> 4) & 0x0F0F0F0F0F0F0F0FU);
269  res = (res & 0x00FF00FF00FF00FFU) + ((res >> 8) & 0x00FF00FF00FF00FFU);
270  res = (res & 0x0000FFFF0000FFFFU) + ((res >> 16) & 0x0000FFFF0000FFFFU);
271  return (res & 0x00000000FFFFFFFFU) + ((res >> 32) & 0x00000000FFFFFFFFU);
272 #endif
273 }
274 
275 static inline unsigned long hweight_long(unsigned long w)
276 {
277  return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
278 }
279 
280 #endif
static unsigned long hweight64(__u64 w)
Definition: bitops.h:260
GLuint GLdouble GLdouble GLint GLint order
Definition: glext.h:11194
#define shift
Definition: input.c:1668
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
static unsigned long __ffs(unsigned long word)
Definition: bitops.h:44
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
static unsigned long hweight32(unsigned long w)
Definition: bitops.h:251
GLintptr offset
Definition: glext.h:5920
static int fls64(__u64 x)
Definition: bitops.h:186
static __u32 ror32(__u32 word, unsigned int shift)
Definition: bitops.h:234
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
int find_next_zero_bit(const unsigned long *addr, int size, int offset)
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
static int ffs(int x)
Definition: bitops.h:120
static int fls(int x)
Definition: bitops.h:157
static unsigned long hweight_long(unsigned long w)
Definition: bitops.h:275
static __u32 rol32(__u32 word, unsigned int shift)
Definition: bitops.h:224
static __inline int get_bitmask_order(unsigned int count)
Definition: bitops.h:200
GLuint GLfloat * val
Definition: glext.h:7180
r l[0]
Definition: byte_order.h:167
static __inline int get_count_order(unsigned int count)
Definition: bitops.h:208
GLsizeiptr size
Definition: glext.h:5919
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 unsigned find_first_bit(const unsigned long *addr, unsigned size)
Definition: bitops.h:83
u64 __u64
Definition: btrfs.h:20
const WCHAR * word
Definition: lex.c:78
static unsigned fls_long(unsigned long l)
Definition: bitops.h:239
GLuint res
Definition: glext.h:9613