4 * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com>
6 * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h
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.
18 #include "host-utils.h"
21 #define BITS_PER_BYTE CHAR_BIT
22 #define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE)
24 #define BIT(nr) (1UL << (nr))
25 #define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))
26 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
27 #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
30 * set_bit - Set a bit in memory
32 * @addr: the address to start counting from
34 static inline void set_bit(long nr
, unsigned long *addr
)
36 unsigned long mask
= BIT_MASK(nr
);
37 unsigned long *p
= addr
+ BIT_WORD(nr
);
43 * set_bit_atomic - Set a bit in memory atomically
45 * @addr: the address to start counting from
47 static inline void set_bit_atomic(long nr
, unsigned long *addr
)
49 unsigned long mask
= BIT_MASK(nr
);
50 unsigned long *p
= addr
+ BIT_WORD(nr
);
56 * clear_bit - Clears a bit in memory
58 * @addr: Address to start counting from
60 static inline void clear_bit(long nr
, unsigned long *addr
)
62 unsigned long mask
= BIT_MASK(nr
);
63 unsigned long *p
= addr
+ BIT_WORD(nr
);
69 * change_bit - Toggle a bit in memory
71 * @addr: Address to start counting from
73 static inline void change_bit(long nr
, unsigned long *addr
)
75 unsigned long mask
= BIT_MASK(nr
);
76 unsigned long *p
= addr
+ BIT_WORD(nr
);
82 * test_and_set_bit - Set a bit and return its old value
84 * @addr: Address to count from
86 static inline int test_and_set_bit(long nr
, unsigned long *addr
)
88 unsigned long mask
= BIT_MASK(nr
);
89 unsigned long *p
= addr
+ BIT_WORD(nr
);
90 unsigned long old
= *p
;
93 return (old
& mask
) != 0;
97 * test_and_clear_bit - Clear a bit and return its old value
99 * @addr: Address to count from
101 static inline int test_and_clear_bit(long nr
, unsigned long *addr
)
103 unsigned long mask
= BIT_MASK(nr
);
104 unsigned long *p
= addr
+ BIT_WORD(nr
);
105 unsigned long old
= *p
;
108 return (old
& mask
) != 0;
112 * test_and_change_bit - Change a bit and return its old value
114 * @addr: Address to count from
116 static inline int test_and_change_bit(long nr
, unsigned long *addr
)
118 unsigned long mask
= BIT_MASK(nr
);
119 unsigned long *p
= addr
+ BIT_WORD(nr
);
120 unsigned long old
= *p
;
123 return (old
& mask
) != 0;
127 * test_bit - Determine whether a bit is set
128 * @nr: bit number to test
129 * @addr: Address to start counting from
131 static inline int test_bit(long nr
, const unsigned long *addr
)
133 return 1UL & (addr
[BIT_WORD(nr
)] >> (nr
& (BITS_PER_LONG
-1)));
137 * find_last_bit - find the last set bit in a memory region
138 * @addr: The address to start the search at
139 * @size: The maximum size to search
141 * Returns the bit number of the first set bit, or size.
143 unsigned long find_last_bit(const unsigned long *addr
,
147 * find_next_bit - find the next set bit in a memory region
148 * @addr: The address to base the search on
149 * @offset: The bitnumber to start searching at
150 * @size: The bitmap size in bits
152 unsigned long find_next_bit(const unsigned long *addr
,
154 unsigned long offset
);
157 * find_next_zero_bit - find the next cleared bit in a memory region
158 * @addr: The address to base the search on
159 * @offset: The bitnumber to start searching at
160 * @size: The bitmap size in bits
163 unsigned long find_next_zero_bit(const unsigned long *addr
,
165 unsigned long offset
);
168 * find_first_bit - find the first set bit in a memory region
169 * @addr: The address to start the search at
170 * @size: The maximum size to search
172 * Returns the bit number of the first set bit.
174 static inline unsigned long find_first_bit(const unsigned long *addr
,
177 unsigned long result
, tmp
;
179 for (result
= 0; result
< size
; result
+= BITS_PER_LONG
) {
183 return result
< size
? result
: size
;
191 * find_first_zero_bit - find the first cleared bit in a memory region
192 * @addr: The address to start the search at
193 * @size: The maximum size to search
195 * Returns the bit number of the first cleared bit.
197 static inline unsigned long find_first_zero_bit(const unsigned long *addr
,
200 return find_next_zero_bit(addr
, size
, 0);
203 static inline unsigned long hweight_long(unsigned long w
)
207 for (count
= 0; w
; w
>>= 1) {
214 * rol8 - rotate an 8-bit value left
215 * @word: value to rotate
216 * @shift: bits to roll
218 static inline uint8_t rol8(uint8_t word
, unsigned int shift
)
220 return (word
<< shift
) | (word
>> (8 - shift
));
224 * ror8 - rotate an 8-bit value right
225 * @word: value to rotate
226 * @shift: bits to roll
228 static inline uint8_t ror8(uint8_t word
, unsigned int shift
)
230 return (word
>> shift
) | (word
<< (8 - shift
));
234 * rol16 - rotate a 16-bit value left
235 * @word: value to rotate
236 * @shift: bits to roll
238 static inline uint16_t rol16(uint16_t word
, unsigned int shift
)
240 return (word
<< shift
) | (word
>> (16 - shift
));
244 * ror16 - rotate a 16-bit value right
245 * @word: value to rotate
246 * @shift: bits to roll
248 static inline uint16_t ror16(uint16_t word
, unsigned int shift
)
250 return (word
>> shift
) | (word
<< (16 - shift
));
254 * rol32 - rotate a 32-bit value left
255 * @word: value to rotate
256 * @shift: bits to roll
258 static inline uint32_t rol32(uint32_t word
, unsigned int shift
)
260 return (word
<< shift
) | (word
>> (32 - shift
));
264 * ror32 - rotate a 32-bit value right
265 * @word: value to rotate
266 * @shift: bits to roll
268 static inline uint32_t ror32(uint32_t word
, unsigned int shift
)
270 return (word
>> shift
) | (word
<< (32 - shift
));
274 * rol64 - rotate a 64-bit value left
275 * @word: value to rotate
276 * @shift: bits to roll
278 static inline uint64_t rol64(uint64_t word
, unsigned int shift
)
280 return (word
<< shift
) | (word
>> (64 - shift
));
284 * ror64 - rotate a 64-bit value right
285 * @word: value to rotate
286 * @shift: bits to roll
288 static inline uint64_t ror64(uint64_t word
, unsigned int shift
)
290 return (word
>> shift
) | (word
<< (64 - shift
));
295 * @value: the value to extract the bit field from
296 * @start: the lowest bit in the bit field (numbered from 0)
297 * @length: the length of the bit field
299 * Extract from the 32 bit input @value the bit field specified by the
300 * @start and @length parameters, and return it. The bit field must
301 * lie entirely within the 32 bit word. It is valid to request that
302 * all 32 bits are returned (ie @length 32 and @start 0).
304 * Returns: the value of the bit field extracted from the input value.
306 static inline uint32_t extract32(uint32_t value
, int start
, int length
)
308 assert(start
>= 0 && length
> 0 && length
<= 32 - start
);
309 return (value
>> start
) & (~0U >> (32 - length
));
314 * @value: the value to extract the bit field from
315 * @start: the lowest bit in the bit field (numbered from 0)
316 * @length: the length of the bit field
318 * Extract from the 64 bit input @value the bit field specified by the
319 * @start and @length parameters, and return it. The bit field must
320 * lie entirely within the 64 bit word. It is valid to request that
321 * all 64 bits are returned (ie @length 64 and @start 0).
323 * Returns: the value of the bit field extracted from the input value.
325 static inline uint64_t extract64(uint64_t value
, int start
, int length
)
327 assert(start
>= 0 && length
> 0 && length
<= 64 - start
);
328 return (value
>> start
) & (~0ULL >> (64 - length
));
333 * @value: the value to extract the bit field from
334 * @start: the lowest bit in the bit field (numbered from 0)
335 * @length: the length of the bit field
337 * Extract from the 32 bit input @value the bit field specified by the
338 * @start and @length parameters, and return it, sign extended to
339 * an int32_t (ie with the most significant bit of the field propagated
340 * to all the upper bits of the return value). The bit field must lie
341 * entirely within the 32 bit word. It is valid to request that
342 * all 32 bits are returned (ie @length 32 and @start 0).
344 * Returns: the sign extended value of the bit field extracted from the
347 static inline int32_t sextract32(uint32_t value
, int start
, int length
)
349 assert(start
>= 0 && length
> 0 && length
<= 32 - start
);
350 /* Note that this implementation relies on right shift of signed
351 * integers being an arithmetic shift.
353 return ((int32_t)(value
<< (32 - length
- start
))) >> (32 - length
);
358 * @value: the value to extract the bit field from
359 * @start: the lowest bit in the bit field (numbered from 0)
360 * @length: the length of the bit field
362 * Extract from the 64 bit input @value the bit field specified by the
363 * @start and @length parameters, and return it, sign extended to
364 * an int64_t (ie with the most significant bit of the field propagated
365 * to all the upper bits of the return value). The bit field must lie
366 * entirely within the 64 bit word. It is valid to request that
367 * all 64 bits are returned (ie @length 64 and @start 0).
369 * Returns: the sign extended value of the bit field extracted from the
372 static inline int64_t sextract64(uint64_t value
, int start
, int length
)
374 assert(start
>= 0 && length
> 0 && length
<= 64 - start
);
375 /* Note that this implementation relies on right shift of signed
376 * integers being an arithmetic shift.
378 return ((int64_t)(value
<< (64 - length
- start
))) >> (64 - length
);
383 * @value: initial value to insert bit field into
384 * @start: the lowest bit in the bit field (numbered from 0)
385 * @length: the length of the bit field
386 * @fieldval: the value to insert into the bit field
388 * Deposit @fieldval into the 32 bit @value at the bit field specified
389 * by the @start and @length parameters, and return the modified
390 * @value. Bits of @value outside the bit field are not modified.
391 * Bits of @fieldval above the least significant @length bits are
392 * ignored. The bit field must lie entirely within the 32 bit word.
393 * It is valid to request that all 32 bits are modified (ie @length
396 * Returns: the modified @value.
398 static inline uint32_t deposit32(uint32_t value
, int start
, int length
,
402 assert(start
>= 0 && length
> 0 && length
<= 32 - start
);
403 mask
= (~0U >> (32 - length
)) << start
;
404 return (value
& ~mask
) | ((fieldval
<< start
) & mask
);
409 * @value: initial value to insert bit field into
410 * @start: the lowest bit in the bit field (numbered from 0)
411 * @length: the length of the bit field
412 * @fieldval: the value to insert into the bit field
414 * Deposit @fieldval into the 64 bit @value at the bit field specified
415 * by the @start and @length parameters, and return the modified
416 * @value. Bits of @value outside the bit field are not modified.
417 * Bits of @fieldval above the least significant @length bits are
418 * ignored. The bit field must lie entirely within the 64 bit word.
419 * It is valid to request that all 64 bits are modified (ie @length
422 * Returns: the modified @value.
424 static inline uint64_t deposit64(uint64_t value
, int start
, int length
,
428 assert(start
>= 0 && length
> 0 && length
<= 64 - start
);
429 mask
= (~0ULL >> (64 - length
)) << start
;
430 return (value
& ~mask
) | ((fieldval
<< start
) & mask
);