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 <stdint.h> 16#include <assert.h> 17 18#include "host-utils.h" 19#include "atomic.h" 20 21#define BITS_PER_BYTE CHAR_BIT 22#define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) 23 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)) 28 29/** 30 * set_bit - Set a bit in memory 31 * @nr: the bit to set 32 * @addr: the address to start counting from 33 */ 34static inline void set_bit(long nr, unsigned long *addr) 35{ 36 unsigned long mask = BIT_MASK(nr); 37 unsigned long *p = addr + BIT_WORD(nr); 38 39 *p |= mask; 40} 41 42/** 43 * set_bit_atomic - Set a bit in memory atomically 44 * @nr: the bit to set 45 * @addr: the address to start counting from 46 */ 47static inline void set_bit_atomic(long nr, unsigned long *addr) 48{ 49 unsigned long mask = BIT_MASK(nr); 50 unsigned long *p = addr + BIT_WORD(nr); 51 52 atomic_or(p, mask); 53} 54 55/** 56 * clear_bit - Clears a bit in memory 57 * @nr: Bit to clear 58 * @addr: Address to start counting from 59 */ 60static inline void clear_bit(long nr, unsigned long *addr) 61{ 62 unsigned long mask = BIT_MASK(nr); 63 unsigned long *p = addr + BIT_WORD(nr); 64 65 *p &= ~mask; 66} 67 68/** 69 * change_bit - Toggle a bit in memory 70 * @nr: Bit to change 71 * @addr: Address to start counting from 72 */ 73static inline void change_bit(long nr, unsigned long *addr) 74{ 75 unsigned long mask = BIT_MASK(nr); 76 unsigned long *p = addr + BIT_WORD(nr); 77 78 *p ^= mask; 79} 80 81/** 82 * test_and_set_bit - Set a bit and return its old value 83 * @nr: Bit to set 84 * @addr: Address to count from 85 */ 86static inline int test_and_set_bit(long nr, unsigned long *addr) 87{ 88 unsigned long mask = BIT_MASK(nr); 89 unsigned long *p = addr + BIT_WORD(nr); 90 unsigned long old = *p; 91 92 *p = old | mask; 93 return (old & mask) != 0; 94} 95 96/** 97 * test_and_clear_bit - Clear a bit and return its old value 98 * @nr: Bit to clear 99 * @addr: Address to count from 100 */ 101static inline int test_and_clear_bit(long nr, unsigned long *addr) 102{ 103 unsigned long mask = BIT_MASK(nr); 104 unsigned long *p = addr + BIT_WORD(nr); 105 unsigned long old = *p; 106 107 *p = old & ~mask; 108 return (old & mask) != 0; 109} 110 111/** 112 * test_and_change_bit - Change a bit and return its old value 113 * @nr: Bit to change 114 * @addr: Address to count from 115 */ 116static inline int test_and_change_bit(long nr, unsigned long *addr) 117{ 118 unsigned long mask = BIT_MASK(nr); 119 unsigned long *p = addr + BIT_WORD(nr); 120 unsigned long old = *p; 121 122 *p = old ^ mask; 123 return (old & mask) != 0; 124} 125 126/** 127 * test_bit - Determine whether a bit is set 128 * @nr: bit number to test 129 * @addr: Address to start counting from 130 */ 131static inline int test_bit(long nr, const unsigned long *addr) 132{ 133 return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); 134} 135 136/** 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 140 * 141 * Returns the bit number of the first set bit, or size. 142 */ 143unsigned long find_last_bit(const unsigned long *addr, 144 unsigned long size); 145 146/** 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 151 */ 152unsigned long find_next_bit(const unsigned long *addr, 153 unsigned long size, 154 unsigned long offset); 155 156/** 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 161 */ 162 163unsigned long find_next_zero_bit(const unsigned long *addr, 164 unsigned long size, 165 unsigned long offset); 166 167/** 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 171 * 172 * Returns the bit number of the first set bit. 173 */ 174static inline unsigned long find_first_bit(const unsigned long *addr, 175 unsigned long size) 176{ 177 unsigned long result, tmp; 178 179 for (result = 0; result < size; result += BITS_PER_LONG) { 180 tmp = *addr++; 181 if (tmp) { 182 result += ctzl(tmp); 183 return result < size ? result : size; 184 } 185 } 186 /* Not found */ 187 return size; 188} 189 190/** 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 194 * 195 * Returns the bit number of the first cleared bit. 196 */ 197static inline unsigned long find_first_zero_bit(const unsigned long *addr, 198 unsigned long size) 199{ 200 return find_next_zero_bit(addr, size, 0); 201} 202 203static inline unsigned long hweight_long(unsigned long w) 204{ 205 unsigned long count; 206 207 for (count = 0; w; w >>= 1) { 208 count += w & 1; 209 } 210 return count; 211} 212 213/** 214 * rol8 - rotate an 8-bit value left 215 * @word: value to rotate 216 * @shift: bits to roll 217 */ 218static inline uint8_t rol8(uint8_t word, unsigned int shift) 219{ 220 return (word << shift) | (word >> (8 - shift)); 221} 222 223/** 224 * ror8 - rotate an 8-bit value right 225 * @word: value to rotate 226 * @shift: bits to roll 227 */ 228static inline uint8_t ror8(uint8_t word, unsigned int shift) 229{ 230 return (word >> shift) | (word << (8 - shift)); 231} 232 233/** 234 * rol16 - rotate a 16-bit value left 235 * @word: value to rotate 236 * @shift: bits to roll 237 */ 238static inline uint16_t rol16(uint16_t word, unsigned int shift) 239{ 240 return (word << shift) | (word >> (16 - shift)); 241} 242 243/** 244 * ror16 - rotate a 16-bit value right 245 * @word: value to rotate 246 * @shift: bits to roll 247 */ 248static inline uint16_t ror16(uint16_t word, unsigned int shift) 249{ 250 return (word >> shift) | (word << (16 - shift)); 251} 252 253/** 254 * rol32 - rotate a 32-bit value left 255 * @word: value to rotate 256 * @shift: bits to roll 257 */ 258static inline uint32_t rol32(uint32_t word, unsigned int shift) 259{ 260 return (word << shift) | (word >> (32 - shift)); 261} 262 263/** 264 * ror32 - rotate a 32-bit value right 265 * @word: value to rotate 266 * @shift: bits to roll 267 */ 268static inline uint32_t ror32(uint32_t word, unsigned int shift) 269{ 270 return (word >> shift) | (word << (32 - shift)); 271} 272 273/** 274 * rol64 - rotate a 64-bit value left 275 * @word: value to rotate 276 * @shift: bits to roll 277 */ 278static inline uint64_t rol64(uint64_t word, unsigned int shift) 279{ 280 return (word << shift) | (word >> (64 - shift)); 281} 282 283/** 284 * ror64 - rotate a 64-bit value right 285 * @word: value to rotate 286 * @shift: bits to roll 287 */ 288static inline uint64_t ror64(uint64_t word, unsigned int shift) 289{ 290 return (word >> shift) | (word << (64 - shift)); 291} 292 293/** 294 * extract32: 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 298 * 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). 303 * 304 * Returns: the value of the bit field extracted from the input value. 305 */ 306static inline uint32_t extract32(uint32_t value, int start, int length) 307{ 308 assert(start >= 0 && length > 0 && length <= 32 - start); 309 return (value >> start) & (~0U >> (32 - length)); 310} 311 312/** 313 * extract64: 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 317 * 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). 322 * 323 * Returns: the value of the bit field extracted from the input value. 324 */ 325static inline uint64_t extract64(uint64_t value, int start, int length) 326{ 327 assert(start >= 0 && length > 0 && length <= 64 - start); 328 return (value >> start) & (~0ULL >> (64 - length)); 329} 330 331/** 332 * sextract32: 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 336 * 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). 343 * 344 * Returns: the sign extended value of the bit field extracted from the 345 * input value. 346 */ 347static inline int32_t sextract32(uint32_t value, int start, int length) 348{ 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. 352 */ 353 return ((int32_t)(value << (32 - length - start))) >> (32 - length); 354} 355 356/** 357 * sextract64: 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 361 * 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). 368 * 369 * Returns: the sign extended value of the bit field extracted from the 370 * input value. 371 */ 372static inline int64_t sextract64(uint64_t value, int start, int length) 373{ 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. 377 */ 378 return ((int64_t)(value << (64 - length - start))) >> (64 - length); 379} 380 381/** 382 * deposit32: 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 387 * 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 394 * 32 and @start 0). 395 * 396 * Returns: the modified @value. 397 */ 398static inline uint32_t deposit32(uint32_t value, int start, int length, 399 uint32_t fieldval) 400{ 401 uint32_t mask; 402 assert(start >= 0 && length > 0 && length <= 32 - start); 403 mask = (~0U >> (32 - length)) << start; 404 return (value & ~mask) | ((fieldval << start) & mask); 405} 406 407/** 408 * deposit64: 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 413 * 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 420 * 64 and @start 0). 421 * 422 * Returns: the modified @value. 423 */ 424static inline uint64_t deposit64(uint64_t value, int start, int length, 425 uint64_t fieldval) 426{ 427 uint64_t mask; 428 assert(start >= 0 && length > 0 && length <= 64 - start); 429 mask = (~0ULL >> (64 - length)) << start; 430 return (value & ~mask) | ((fieldval << start) & mask); 431} 432 433#endif 434