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