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 */ 34 static 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 */ 47 static 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 */ 60 static 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 */ 73 static 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 */ 86 static 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 */ 101 static 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 */ 116 static 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 */ 131 static 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 */ 143 unsigned 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 */ 152 unsigned 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 163 unsigned 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 */ 174 static 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 */ 197 static 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 203 static 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 */ 218 static 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 */ 228 static 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 */ 238 static 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 */ 248 static 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 */ 258 static 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 */ 268 static 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 */ 278 static 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 */ 288 static 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 */ 306 static 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 */ 325 static 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 */ 347 static 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 */ 372 static 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 */ 398 static 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 */ 424 static 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