root / include / qemu / bitops.h @ 1de7afc9
History | View | Annotate | Download (9.5 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, unsigned long *addr) |
118 |
{ |
119 |
unsigned long mask = BIT_MASK(nr); |
120 |
unsigned long *p = 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, unsigned long *addr) |
131 |
{ |
132 |
unsigned long mask = BIT_MASK(nr); |
133 |
unsigned long *p = 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, unsigned long *addr) |
144 |
{ |
145 |
unsigned long mask = BIT_MASK(nr); |
146 |
unsigned long *p = 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, unsigned long *addr) |
157 |
{ |
158 |
unsigned long mask = BIT_MASK(nr); |
159 |
unsigned long *p = 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, unsigned long *addr) |
172 |
{ |
173 |
unsigned long mask = BIT_MASK(nr); |
174 |
unsigned long *p = 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, unsigned long *addr) |
187 |
{ |
188 |
unsigned long mask = BIT_MASK(nr); |
189 |
unsigned long *p = 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 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 |
/**
|
273 |
* extract32:
|
274 |
* @value: the value to extract the bit field from
|
275 |
* @start: the lowest bit in the bit field (numbered from 0)
|
276 |
* @length: the length of the bit field
|
277 |
*
|
278 |
* Extract from the 32 bit input @value the bit field specified by the
|
279 |
* @start and @length parameters, and return it. The bit field must
|
280 |
* lie entirely within the 32 bit word. It is valid to request that
|
281 |
* all 32 bits are returned (ie @length 32 and @start 0).
|
282 |
*
|
283 |
* Returns: the value of the bit field extracted from the input value.
|
284 |
*/
|
285 |
static inline uint32_t extract32(uint32_t value, int start, int length) |
286 |
{ |
287 |
assert(start >= 0 && length > 0 && length <= 32 - start); |
288 |
return (value >> start) & (~0U >> (32 - length)); |
289 |
} |
290 |
|
291 |
/**
|
292 |
* extract64:
|
293 |
* @value: the value to extract the bit field from
|
294 |
* @start: the lowest bit in the bit field (numbered from 0)
|
295 |
* @length: the length of the bit field
|
296 |
*
|
297 |
* Extract from the 64 bit input @value the bit field specified by the
|
298 |
* @start and @length parameters, and return it. The bit field must
|
299 |
* lie entirely within the 64 bit word. It is valid to request that
|
300 |
* all 64 bits are returned (ie @length 64 and @start 0).
|
301 |
*
|
302 |
* Returns: the value of the bit field extracted from the input value.
|
303 |
*/
|
304 |
static inline uint64_t extract64(uint64_t value, int start, int length) |
305 |
{ |
306 |
assert(start >= 0 && length > 0 && length <= 64 - start); |
307 |
return (value >> start) & (~0ULL >> (64 - length)); |
308 |
} |
309 |
|
310 |
/**
|
311 |
* deposit32:
|
312 |
* @value: initial value to insert bit field into
|
313 |
* @start: the lowest bit in the bit field (numbered from 0)
|
314 |
* @length: the length of the bit field
|
315 |
* @fieldval: the value to insert into the bit field
|
316 |
*
|
317 |
* Deposit @fieldval into the 32 bit @value at the bit field specified
|
318 |
* by the @start and @length parameters, and return the modified
|
319 |
* @value. Bits of @value outside the bit field are not modified.
|
320 |
* Bits of @fieldval above the least significant @length bits are
|
321 |
* ignored. The bit field must lie entirely within the 32 bit word.
|
322 |
* It is valid to request that all 32 bits are modified (ie @length
|
323 |
* 32 and @start 0).
|
324 |
*
|
325 |
* Returns: the modified @value.
|
326 |
*/
|
327 |
static inline uint32_t deposit32(uint32_t value, int start, int length, |
328 |
uint32_t fieldval) |
329 |
{ |
330 |
uint32_t mask; |
331 |
assert(start >= 0 && length > 0 && length <= 32 - start); |
332 |
mask = (~0U >> (32 - length)) << start; |
333 |
return (value & ~mask) | ((fieldval << start) & mask);
|
334 |
} |
335 |
|
336 |
/**
|
337 |
* deposit64:
|
338 |
* @value: initial value to insert bit field into
|
339 |
* @start: the lowest bit in the bit field (numbered from 0)
|
340 |
* @length: the length of the bit field
|
341 |
* @fieldval: the value to insert into the bit field
|
342 |
*
|
343 |
* Deposit @fieldval into the 64 bit @value at the bit field specified
|
344 |
* by the @start and @length parameters, and return the modified
|
345 |
* @value. Bits of @value outside the bit field are not modified.
|
346 |
* Bits of @fieldval above the least significant @length bits are
|
347 |
* ignored. The bit field must lie entirely within the 64 bit word.
|
348 |
* It is valid to request that all 64 bits are modified (ie @length
|
349 |
* 64 and @start 0).
|
350 |
*
|
351 |
* Returns: the modified @value.
|
352 |
*/
|
353 |
static inline uint64_t deposit64(uint64_t value, int start, int length, |
354 |
uint64_t fieldval) |
355 |
{ |
356 |
uint64_t mask; |
357 |
assert(start >= 0 && length > 0 && length <= 64 - start); |
358 |
mask = (~0ULL >> (64 - length)) << start; |
359 |
return (value & ~mask) | ((fieldval << start) & mask);
|
360 |
} |
361 |
|
362 |
#endif
|