root / bitops.h @ c995b495
History | View | Annotate | Download (6.3 kB)
1 |
/*
|
---|---|
2 |
* Bitops Module
|
3 |
*
|
4 |
* Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com>
|
5 |
*
|
6 |
* Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h
|
7 |
*
|
8 |
* This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
|
9 |
* See the COPYING.LIB file in the top-level directory.
|
10 |
*/
|
11 |
|
12 |
#ifndef BITOPS_H
|
13 |
#define BITOPS_H
|
14 |
|
15 |
#include "qemu-common.h" |
16 |
|
17 |
#define BITS_PER_BYTE CHAR_BIT
|
18 |
#define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) |
19 |
|
20 |
#define BIT(nr) (1UL << (nr)) |
21 |
#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) |
22 |
#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
|
23 |
#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) |
24 |
|
25 |
/**
|
26 |
* bitops_ffs - find first bit in word.
|
27 |
* @word: The word to search
|
28 |
*
|
29 |
* Undefined if no bit exists, so code should check against 0 first.
|
30 |
*/
|
31 |
static unsigned long bitops_ffsl(unsigned long word) |
32 |
{ |
33 |
int num = 0; |
34 |
|
35 |
#if LONG_MAX > 0x7FFFFFFF |
36 |
if ((word & 0xffffffff) == 0) { |
37 |
num += 32;
|
38 |
word >>= 32;
|
39 |
} |
40 |
#endif
|
41 |
if ((word & 0xffff) == 0) { |
42 |
num += 16;
|
43 |
word >>= 16;
|
44 |
} |
45 |
if ((word & 0xff) == 0) { |
46 |
num += 8;
|
47 |
word >>= 8;
|
48 |
} |
49 |
if ((word & 0xf) == 0) { |
50 |
num += 4;
|
51 |
word >>= 4;
|
52 |
} |
53 |
if ((word & 0x3) == 0) { |
54 |
num += 2;
|
55 |
word >>= 2;
|
56 |
} |
57 |
if ((word & 0x1) == 0) { |
58 |
num += 1;
|
59 |
} |
60 |
return num;
|
61 |
} |
62 |
|
63 |
/**
|
64 |
* bitops_fls - find last (most-significant) set bit in a long word
|
65 |
* @word: the word to search
|
66 |
*
|
67 |
* Undefined if no set bit exists, so code should check against 0 first.
|
68 |
*/
|
69 |
static inline unsigned long bitops_flsl(unsigned long word) |
70 |
{ |
71 |
int num = BITS_PER_LONG - 1; |
72 |
|
73 |
#if LONG_MAX > 0x7FFFFFFF |
74 |
if (!(word & (~0ul << 32))) { |
75 |
num -= 32;
|
76 |
word <<= 32;
|
77 |
} |
78 |
#endif
|
79 |
if (!(word & (~0ul << (BITS_PER_LONG-16)))) { |
80 |
num -= 16;
|
81 |
word <<= 16;
|
82 |
} |
83 |
if (!(word & (~0ul << (BITS_PER_LONG-8)))) { |
84 |
num -= 8;
|
85 |
word <<= 8;
|
86 |
} |
87 |
if (!(word & (~0ul << (BITS_PER_LONG-4)))) { |
88 |
num -= 4;
|
89 |
word <<= 4;
|
90 |
} |
91 |
if (!(word & (~0ul << (BITS_PER_LONG-2)))) { |
92 |
num -= 2;
|
93 |
|
94 |
word <<= 2;
|
95 |
} |
96 |
if (!(word & (~0ul << (BITS_PER_LONG-1)))) |
97 |
num -= 1;
|
98 |
return num;
|
99 |
} |
100 |
|
101 |
/**
|
102 |
* ffz - find first zero in word.
|
103 |
* @word: The word to search
|
104 |
*
|
105 |
* Undefined if no zero exists, so code should check against ~0UL first.
|
106 |
*/
|
107 |
static inline unsigned long ffz(unsigned long word) |
108 |
{ |
109 |
return bitops_ffsl(~word);
|
110 |
} |
111 |
|
112 |
/**
|
113 |
* set_bit - Set a bit in memory
|
114 |
* @nr: the bit to set
|
115 |
* @addr: the address to start counting from
|
116 |
*/
|
117 |
static inline void set_bit(int nr, volatile unsigned long *addr) |
118 |
{ |
119 |
unsigned long mask = BIT_MASK(nr); |
120 |
unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
121 |
|
122 |
*p |= mask; |
123 |
} |
124 |
|
125 |
/**
|
126 |
* clear_bit - Clears a bit in memory
|
127 |
* @nr: Bit to clear
|
128 |
* @addr: Address to start counting from
|
129 |
*/
|
130 |
static inline void clear_bit(int nr, volatile unsigned long *addr) |
131 |
{ |
132 |
unsigned long mask = BIT_MASK(nr); |
133 |
unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
134 |
|
135 |
*p &= ~mask; |
136 |
} |
137 |
|
138 |
/**
|
139 |
* change_bit - Toggle a bit in memory
|
140 |
* @nr: Bit to change
|
141 |
* @addr: Address to start counting from
|
142 |
*/
|
143 |
static inline void change_bit(int nr, volatile unsigned long *addr) |
144 |
{ |
145 |
unsigned long mask = BIT_MASK(nr); |
146 |
unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
147 |
|
148 |
*p ^= mask; |
149 |
} |
150 |
|
151 |
/**
|
152 |
* test_and_set_bit - Set a bit and return its old value
|
153 |
* @nr: Bit to set
|
154 |
* @addr: Address to count from
|
155 |
*/
|
156 |
static inline int test_and_set_bit(int nr, volatile unsigned long *addr) |
157 |
{ |
158 |
unsigned long mask = BIT_MASK(nr); |
159 |
unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
160 |
unsigned long old = *p; |
161 |
|
162 |
*p = old | mask; |
163 |
return (old & mask) != 0; |
164 |
} |
165 |
|
166 |
/**
|
167 |
* test_and_clear_bit - Clear a bit and return its old value
|
168 |
* @nr: Bit to clear
|
169 |
* @addr: Address to count from
|
170 |
*/
|
171 |
static inline int test_and_clear_bit(int nr, volatile unsigned long *addr) |
172 |
{ |
173 |
unsigned long mask = BIT_MASK(nr); |
174 |
unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
175 |
unsigned long old = *p; |
176 |
|
177 |
*p = old & ~mask; |
178 |
return (old & mask) != 0; |
179 |
} |
180 |
|
181 |
/**
|
182 |
* test_and_change_bit - Change a bit and return its old value
|
183 |
* @nr: Bit to change
|
184 |
* @addr: Address to count from
|
185 |
*/
|
186 |
static inline int test_and_change_bit(int nr, volatile unsigned long *addr) |
187 |
{ |
188 |
unsigned long mask = BIT_MASK(nr); |
189 |
unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); |
190 |
unsigned long old = *p; |
191 |
|
192 |
*p = old ^ mask; |
193 |
return (old & mask) != 0; |
194 |
} |
195 |
|
196 |
/**
|
197 |
* test_bit - Determine whether a bit is set
|
198 |
* @nr: bit number to test
|
199 |
* @addr: Address to start counting from
|
200 |
*/
|
201 |
static inline int test_bit(int nr, const volatile unsigned long *addr) |
202 |
{ |
203 |
return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); |
204 |
} |
205 |
|
206 |
/**
|
207 |
* find_last_bit - find the last set bit in a memory region
|
208 |
* @addr: The address to start the search at
|
209 |
* @size: The maximum size to search
|
210 |
*
|
211 |
* Returns the bit number of the first set bit, or size.
|
212 |
*/
|
213 |
unsigned long find_last_bit(const unsigned long *addr, |
214 |
unsigned long size); |
215 |
|
216 |
/**
|
217 |
* find_next_bit - find the next set bit in a memory region
|
218 |
* @addr: The address to base the search on
|
219 |
* @offset: The bitnumber to start searching at
|
220 |
* @size: The bitmap size in bits
|
221 |
*/
|
222 |
unsigned long find_next_bit(const unsigned long *addr, |
223 |
unsigned long size, unsigned long offset); |
224 |
|
225 |
/**
|
226 |
* find_next_zero_bit - find the next cleared bit in a memory region
|
227 |
* @addr: The address to base the search on
|
228 |
* @offset: The bitnumber to start searching at
|
229 |
* @size: The bitmap size in bits
|
230 |
*/
|
231 |
|
232 |
unsigned long find_next_zero_bit(const unsigned long *addr, |
233 |
unsigned long size, |
234 |
unsigned long offset); |
235 |
|
236 |
/**
|
237 |
* find_first_bit - find the first set bit in a memory region
|
238 |
* @addr: The address to start the search at
|
239 |
* @size: The maximum size to search
|
240 |
*
|
241 |
* Returns the bit number of the first set bit.
|
242 |
*/
|
243 |
static inline unsigned long find_first_bit(const unsigned long *addr, |
244 |
unsigned long size) |
245 |
{ |
246 |
return find_next_bit(addr, size, 0); |
247 |
} |
248 |
|
249 |
/**
|
250 |
* find_first_zero_bit - find the first cleared bit in a memory region
|
251 |
* @addr: The address to start the search at
|
252 |
* @size: The maximum size to search
|
253 |
*
|
254 |
* Returns the bit number of the first cleared bit.
|
255 |
*/
|
256 |
static inline unsigned long find_first_zero_bit(const unsigned long *addr, |
257 |
unsigned long size) |
258 |
{ |
259 |
return find_next_zero_bit(addr, size, 0); |
260 |
} |
261 |
|
262 |
static inline unsigned long hweight_long(unsigned long w) |
263 |
{ |
264 |
unsigned long count; |
265 |
|
266 |
for (count = 0; w; w >>= 1) { |
267 |
count += w & 1;
|
268 |
} |
269 |
return count;
|
270 |
} |
271 |
|
272 |
#endif
|