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 16#include "host-utils.h" 17#include "atomic.h" 18 19#define BITS_PER_BYTE CHAR_BIT 20#define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) 21 22#define BIT(nr) (1UL << (nr)) 23#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) 24#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 25#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) 26 27/** 28 * set_bit - Set a bit in memory 29 * @nr: the bit to set 30 * @addr: the address to start counting from 31 */ 32static inline void set_bit(long nr, unsigned long *addr) 33{ 34 unsigned long mask = BIT_MASK(nr); 35 unsigned long *p = addr + BIT_WORD(nr); 36 37 *p |= mask; 38} 39 40/** 41 * set_bit_atomic - Set a bit in memory atomically 42 * @nr: the bit to set 43 * @addr: the address to start counting from 44 */ 45static inline void set_bit_atomic(long nr, unsigned long *addr) 46{ 47 unsigned long mask = BIT_MASK(nr); 48 unsigned long *p = addr + BIT_WORD(nr); 49 50 atomic_or(p, mask); 51} 52 53/** 54 * clear_bit - Clears a bit in memory 55 * @nr: Bit to clear 56 * @addr: Address to start counting from 57 */ 58static inline void clear_bit(long nr, unsigned long *addr) 59{ 60 unsigned long mask = BIT_MASK(nr); 61 unsigned long *p = addr + BIT_WORD(nr); 62 63 *p &= ~mask; 64} 65 66/** 67 * change_bit - Toggle a bit in memory 68 * @nr: Bit to change 69 * @addr: Address to start counting from 70 */ 71static inline void change_bit(long nr, unsigned long *addr) 72{ 73 unsigned long mask = BIT_MASK(nr); 74 unsigned long *p = addr + BIT_WORD(nr); 75 76 *p ^= mask; 77} 78 79/** 80 * test_and_set_bit - Set a bit and return its old value 81 * @nr: Bit to set 82 * @addr: Address to count from 83 */ 84static inline int test_and_set_bit(long nr, unsigned long *addr) 85{ 86 unsigned long mask = BIT_MASK(nr); 87 unsigned long *p = addr + BIT_WORD(nr); 88 unsigned long old = *p; 89 90 *p = old | mask; 91 return (old & mask) != 0; 92} 93 94/** 95 * test_and_clear_bit - Clear a bit and return its old value 96 * @nr: Bit to clear 97 * @addr: Address to count from 98 */ 99static inline int test_and_clear_bit(long nr, unsigned long *addr) 100{ 101 unsigned long mask = BIT_MASK(nr); 102 unsigned long *p = addr + BIT_WORD(nr); 103 unsigned long old = *p; 104 105 *p = old & ~mask; 106 return (old & mask) != 0; 107} 108 109/** 110 * test_and_change_bit - Change a bit and return its old value 111 * @nr: Bit to change 112 * @addr: Address to count from 113 */ 114static inline int test_and_change_bit(long nr, unsigned long *addr) 115{ 116 unsigned long mask = BIT_MASK(nr); 117 unsigned long *p = addr + BIT_WORD(nr); 118 unsigned long old = *p; 119 120 *p = old ^ mask; 121 return (old & mask) != 0; 122} 123 124/** 125 * test_bit - Determine whether a bit is set 126 * @nr: bit number to test 127 * @addr: Address to start counting from 128 */ 129static inline int test_bit(long nr, const unsigned long *addr) 130{ 131 return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); 132} 133 134/** 135 * find_last_bit - find the last set bit in a memory region 136 * @addr: The address to start the search at 137 * @size: The maximum size to search 138 * 139 * Returns the bit number of the first set bit, or size. 140 */ 141unsigned long find_last_bit(const unsigned long *addr, 142 unsigned long size); 143 144/** 145 * find_next_bit - find the next set bit in a memory region 146 * @addr: The address to base the search on 147 * @offset: The bitnumber to start searching at 148 * @size: The bitmap size in bits 149 */ 150unsigned long find_next_bit(const unsigned long *addr, 151 unsigned long size, 152 unsigned long offset); 153 154/** 155 * find_next_zero_bit - find the next cleared bit in a memory region 156 * @addr: The address to base the search on 157 * @offset: The bitnumber to start searching at 158 * @size: The bitmap size in bits 159 */ 160 161unsigned long find_next_zero_bit(const unsigned long *addr, 162 unsigned long size, 163 unsigned long offset); 164 165/** 166 * find_first_bit - find the first set bit in a memory region 167 * @addr: The address to start the search at 168 * @size: The maximum size to search 169 * 170 * Returns the bit number of the first set bit. 171 */ 172static inline unsigned long find_first_bit(const unsigned long *addr, 173 unsigned long size) 174{ 175 unsigned long result, tmp; 176 177 for (result = 0; result < size; result += BITS_PER_LONG) { 178 tmp = *addr++; 179 if (tmp) { 180 result += ctzl(tmp); 181 return result < size ? result : size; 182 } 183 } 184 /* Not found */ 185 return size; 186} 187 188/** 189 * find_first_zero_bit - find the first cleared bit in a memory region 190 * @addr: The address to start the search at 191 * @size: The maximum size to search 192 * 193 * Returns the bit number of the first cleared bit. 194 */ 195static inline unsigned long find_first_zero_bit(const unsigned long *addr, 196 unsigned long size) 197{ 198 return find_next_zero_bit(addr, size, 0); 199} 200 201static inline unsigned long hweight_long(unsigned long w) 202{ 203 unsigned long count; 204 205 for (count = 0; w; w >>= 1) { 206 count += w & 1; 207 } 208 return count; 209} 210 211/** 212 * rol8 - rotate an 8-bit value left 213 * @word: value to rotate 214 * @shift: bits to roll 215 */ 216static inline uint8_t rol8(uint8_t word, unsigned int shift) 217{ 218 return (word << shift) | (word >> (8 - shift)); 219} 220 221/** 222 * ror8 - rotate an 8-bit value right 223 * @word: value to rotate 224 * @shift: bits to roll 225 */ 226static inline uint8_t ror8(uint8_t word, unsigned int shift) 227{ 228 return (word >> shift) | (word << (8 - shift)); 229} 230 231/** 232 * rol16 - rotate a 16-bit value left 233 * @word: value to rotate 234 * @shift: bits to roll 235 */ 236static inline uint16_t rol16(uint16_t word, unsigned int shift) 237{ 238 return (word << shift) | (word >> (16 - shift)); 239} 240 241/** 242 * ror16 - rotate a 16-bit value right 243 * @word: value to rotate 244 * @shift: bits to roll 245 */ 246static inline uint16_t ror16(uint16_t word, unsigned int shift) 247{ 248 return (word >> shift) | (word << (16 - shift)); 249} 250 251/** 252 * rol32 - rotate a 32-bit value left 253 * @word: value to rotate 254 * @shift: bits to roll 255 */ 256static inline uint32_t rol32(uint32_t word, unsigned int shift) 257{ 258 return (word << shift) | (word >> (32 - shift)); 259} 260 261/** 262 * ror32 - rotate a 32-bit value right 263 * @word: value to rotate 264 * @shift: bits to roll 265 */ 266static inline uint32_t ror32(uint32_t word, unsigned int shift) 267{ 268 return (word >> shift) | (word << (32 - shift)); 269} 270 271/** 272 * rol64 - rotate a 64-bit value left 273 * @word: value to rotate 274 * @shift: bits to roll 275 */ 276static inline uint64_t rol64(uint64_t word, unsigned int shift) 277{ 278 return (word << shift) | (word >> (64 - shift)); 279} 280 281/** 282 * ror64 - rotate a 64-bit value right 283 * @word: value to rotate 284 * @shift: bits to roll 285 */ 286static inline uint64_t ror64(uint64_t word, unsigned int shift) 287{ 288 return (word >> shift) | (word << (64 - shift)); 289} 290 291/** 292 * extract32: 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 32 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 32 bit word. It is valid to request that 300 * all 32 bits are returned (ie @length 32 and @start 0). 301 * 302 * Returns: the value of the bit field extracted from the input value. 303 */ 304static inline uint32_t extract32(uint32_t value, int start, int length) 305{ 306 assert(start >= 0 && length > 0 && length <= 32 - start); 307 return (value >> start) & (~0U >> (32 - length)); 308} 309 310/** 311 * extract64: 312 * @value: the value to extract the bit field from 313 * @start: the lowest bit in the bit field (numbered from 0) 314 * @length: the length of the bit field 315 * 316 * Extract from the 64 bit input @value the bit field specified by the 317 * @start and @length parameters, and return it. The bit field must 318 * lie entirely within the 64 bit word. It is valid to request that 319 * all 64 bits are returned (ie @length 64 and @start 0). 320 * 321 * Returns: the value of the bit field extracted from the input value. 322 */ 323static inline uint64_t extract64(uint64_t value, int start, int length) 324{ 325 assert(start >= 0 && length > 0 && length <= 64 - start); 326 return (value >> start) & (~0ULL >> (64 - length)); 327} 328 329/** 330 * sextract32: 331 * @value: the value to extract the bit field from 332 * @start: the lowest bit in the bit field (numbered from 0) 333 * @length: the length of the bit field 334 * 335 * Extract from the 32 bit input @value the bit field specified by the 336 * @start and @length parameters, and return it, sign extended to 337 * an int32_t (ie with the most significant bit of the field propagated 338 * to all the upper bits of the return value). The bit field must lie 339 * entirely within the 32 bit word. It is valid to request that 340 * all 32 bits are returned (ie @length 32 and @start 0). 341 * 342 * Returns: the sign extended value of the bit field extracted from the 343 * input value. 344 */ 345static inline int32_t sextract32(uint32_t value, int start, int length) 346{ 347 assert(start >= 0 && length > 0 && length <= 32 - start); 348 /* Note that this implementation relies on right shift of signed 349 * integers being an arithmetic shift. 350 */ 351 return ((int32_t)(value << (32 - length - start))) >> (32 - length); 352} 353 354/** 355 * sextract64: 356 * @value: the value to extract the bit field from 357 * @start: the lowest bit in the bit field (numbered from 0) 358 * @length: the length of the bit field 359 * 360 * Extract from the 64 bit input @value the bit field specified by the 361 * @start and @length parameters, and return it, sign extended to 362 * an int64_t (ie with the most significant bit of the field propagated 363 * to all the upper bits of the return value). The bit field must lie 364 * entirely within the 64 bit word. It is valid to request that 365 * all 64 bits are returned (ie @length 64 and @start 0). 366 * 367 * Returns: the sign extended value of the bit field extracted from the 368 * input value. 369 */ 370static inline int64_t sextract64(uint64_t value, int start, int length) 371{ 372 assert(start >= 0 && length > 0 && length <= 64 - start); 373 /* Note that this implementation relies on right shift of signed 374 * integers being an arithmetic shift. 375 */ 376 return ((int64_t)(value << (64 - length - start))) >> (64 - length); 377} 378 379/** 380 * deposit32: 381 * @value: initial value to insert bit field into 382 * @start: the lowest bit in the bit field (numbered from 0) 383 * @length: the length of the bit field 384 * @fieldval: the value to insert into the bit field 385 * 386 * Deposit @fieldval into the 32 bit @value at the bit field specified 387 * by the @start and @length parameters, and return the modified 388 * @value. Bits of @value outside the bit field are not modified. 389 * Bits of @fieldval above the least significant @length bits are 390 * ignored. The bit field must lie entirely within the 32 bit word. 391 * It is valid to request that all 32 bits are modified (ie @length 392 * 32 and @start 0). 393 * 394 * Returns: the modified @value. 395 */ 396static inline uint32_t deposit32(uint32_t value, int start, int length, 397 uint32_t fieldval) 398{ 399 uint32_t mask; 400 assert(start >= 0 && length > 0 && length <= 32 - start); 401 mask = (~0U >> (32 - length)) << start; 402 return (value & ~mask) | ((fieldval << start) & mask); 403} 404 405/** 406 * deposit64: 407 * @value: initial value to insert bit field into 408 * @start: the lowest bit in the bit field (numbered from 0) 409 * @length: the length of the bit field 410 * @fieldval: the value to insert into the bit field 411 * 412 * Deposit @fieldval into the 64 bit @value at the bit field specified 413 * by the @start and @length parameters, and return the modified 414 * @value. Bits of @value outside the bit field are not modified. 415 * Bits of @fieldval above the least significant @length bits are 416 * ignored. The bit field must lie entirely within the 64 bit word. 417 * It is valid to request that all 64 bits are modified (ie @length 418 * 64 and @start 0). 419 * 420 * Returns: the modified @value. 421 */ 422static inline uint64_t deposit64(uint64_t value, int start, int length, 423 uint64_t fieldval) 424{ 425 uint64_t mask; 426 assert(start >= 0 && length > 0 && length <= 64 - start); 427 mask = (~0ULL >> (64 - length)) << start; 428 return (value & ~mask) | ((fieldval << start) & mask); 429} 430 431#define ONES(num) ((num) == 64 ? ~0ull : (1ull << (num)) - 1) 432 433#endif 434