ReactOS 0.4.15-dev-8227-g32d615f
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
36int find_next_zero_bit(const unsigned long *addr, int size, int offset);
37
44static 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
83static 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
120static 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
157static 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
186static 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
200static __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
208static __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
224static inline __u32 rol32(__u32 word, unsigned int shift)
225{
226 return (word << shift) | (word >> (32 - shift));
227}
228
234static inline __u32 ror32(__u32 word, unsigned int shift)
235{
236 return (word >> shift) | (word << (32 - shift));
237}
238
239static 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
251static 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
260static 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
275static inline unsigned long hweight_long(unsigned long w)
276{
277 return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
278}
279
280#endif
static __u32 rol32(__u32 word, unsigned int shift)
Definition: bitops.h:224
static __u32 ror32(__u32 word, unsigned int shift)
Definition: bitops.h:234
static int fls(int x)
Definition: bitops.h:157
static int fls64(__u64 x)
Definition: bitops.h:186
int find_next_zero_bit(const unsigned long *addr, int size, int offset)
static unsigned long hweight64(__u64 w)
Definition: bitops.h:260
static unsigned find_first_bit(const unsigned long *addr, unsigned size)
Definition: bitops.h:83
static unsigned long hweight_long(unsigned long w)
Definition: bitops.h:275
static unsigned fls_long(unsigned long l)
Definition: bitops.h:239
static unsigned long hweight32(unsigned long w)
Definition: bitops.h:251
static __inline int get_count_order(unsigned int count)
Definition: bitops.h:208
static unsigned long __ffs(unsigned long word)
Definition: bitops.h:44
static __inline int get_bitmask_order(unsigned int count)
Definition: bitops.h:200
ULONG64 u64
Definition: btrfs.h:15
u32 __u32
Definition: btrfs.h:19
u64 __u64
Definition: btrfs.h:20
r l[0]
Definition: byte_order.h:168
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLsizeiptr size
Definition: glext.h:5919
GLuint res
Definition: glext.h:9613
GLenum const GLvoid * addr
Definition: glext.h:9621
GLuint GLfloat * val
Definition: glext.h:7180
GLuint GLuint num
Definition: glext.h:9618
GLuint GLdouble GLdouble GLint GLint order
Definition: glext.h:11194
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
GLintptr offset
Definition: glext.h:5920
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
const WCHAR * word
Definition: lex.c:36
#define shift
Definition: input.c:1755
#define ffs
Definition: port.h:359
#define __u32
Definition: types.h:15