1 /* 2 * Bitops Module 3 * 4 * Copyright (C) 2010 Corentin Chary <corentin.chary (at) 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(int 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(int 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(int 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(int 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(int 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(int 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(int 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 return find_next_bit(addr, size, 0); 161 } 162 163 /** 164 * find_first_zero_bit - find the first cleared bit in a memory region 165 * @addr: The address to start the search at 166 * @size: The maximum size to search 167 * 168 * Returns the bit number of the first cleared bit. 169 */ 170 static inline unsigned long find_first_zero_bit(const unsigned long *addr, 171 unsigned long size) 172 { 173 return find_next_zero_bit(addr, size, 0); 174 } 175 176 static inline unsigned long hweight_long(unsigned long w) 177 { 178 unsigned long count; 179 180 for (count = 0; w; w >>= 1) { 181 count += w & 1; 182 } 183 return count; 184 } 185 186 /** 187 * rol8 - rotate an 8-bit value left 188 * @word: value to rotate 189 * @shift: bits to roll 190 */ 191 static inline uint8_t rol8(uint8_t word, unsigned int shift) 192 { 193 return (word << shift) | (word >> (8 - shift)); 194 } 195 196 /** 197 * ror8 - rotate an 8-bit value right 198 * @word: value to rotate 199 * @shift: bits to roll 200 */ 201 static inline uint8_t ror8(uint8_t word, unsigned int shift) 202 { 203 return (word >> shift) | (word << (8 - shift)); 204 } 205 206 /** 207 * rol16 - rotate a 16-bit value left 208 * @word: value to rotate 209 * @shift: bits to roll 210 */ 211 static inline uint16_t rol16(uint16_t word, unsigned int shift) 212 { 213 return (word << shift) | (word >> (16 - shift)); 214 } 215 216 /** 217 * ror16 - rotate a 16-bit value right 218 * @word: value to rotate 219 * @shift: bits to roll 220 */ 221 static inline uint16_t ror16(uint16_t word, unsigned int shift) 222 { 223 return (word >> shift) | (word << (16 - shift)); 224 } 225 226 /** 227 * rol32 - rotate a 32-bit value left 228 * @word: value to rotate 229 * @shift: bits to roll 230 */ 231 static inline uint32_t rol32(uint32_t word, unsigned int shift) 232 { 233 return (word << shift) | (word >> (32 - shift)); 234 } 235 236 /** 237 * ror32 - rotate a 32-bit value right 238 * @word: value to rotate 239 * @shift: bits to roll 240 */ 241 static inline uint32_t ror32(uint32_t word, unsigned int shift) 242 { 243 return (word >> shift) | (word << (32 - shift)); 244 } 245 246 /** 247 * rol64 - rotate a 64-bit value left 248 * @word: value to rotate 249 * @shift: bits to roll 250 */ 251 static inline uint64_t rol64(uint64_t word, unsigned int shift) 252 { 253 return (word << shift) | (word >> (64 - shift)); 254 } 255 256 /** 257 * ror64 - rotate a 64-bit value right 258 * @word: value to rotate 259 * @shift: bits to roll 260 */ 261 static inline uint64_t ror64(uint64_t word, unsigned int shift) 262 { 263 return (word >> shift) | (word << (64 - shift)); 264 } 265 266 /** 267 * extract32: 268 * @value: the value to extract the bit field from 269 * @start: the lowest bit in the bit field (numbered from 0) 270 * @length: the length of the bit field 271 * 272 * Extract from the 32 bit input @value the bit field specified by the 273 * @start and @length parameters, and return it. The bit field must 274 * lie entirely within the 32 bit word. It is valid to request that 275 * all 32 bits are returned (ie @length 32 and @start 0). 276 * 277 * Returns: the value of the bit field extracted from the input value. 278 */ 279 static inline uint32_t extract32(uint32_t value, int start, int length) 280 { 281 assert(start >= 0 && length > 0 && length <= 32 - start); 282 return (value >> start) & (~0U >> (32 - length)); 283 } 284 285 /** 286 * extract64: 287 * @value: the value to extract the bit field from 288 * @start: the lowest bit in the bit field (numbered from 0) 289 * @length: the length of the bit field 290 * 291 * Extract from the 64 bit input @value the bit field specified by the 292 * @start and @length parameters, and return it. The bit field must 293 * lie entirely within the 64 bit word. It is valid to request that 294 * all 64 bits are returned (ie @length 64 and @start 0). 295 * 296 * Returns: the value of the bit field extracted from the input value. 297 */ 298 static inline uint64_t extract64(uint64_t value, int start, int length) 299 { 300 assert(start >= 0 && length > 0 && length <= 64 - start); 301 return (value >> start) & (~0ULL >> (64 - length)); 302 } 303 304 /** 305 * sextract32: 306 * @value: the value to extract the bit field from 307 * @start: the lowest bit in the bit field (numbered from 0) 308 * @length: the length of the bit field 309 * 310 * Extract from the 32 bit input @value the bit field specified by the 311 * @start and @length parameters, and return it, sign extended to 312 * an int32_t (ie with the most significant bit of the field propagated 313 * to all the upper bits of the return value). The bit field must lie 314 * entirely within the 32 bit word. It is valid to request that 315 * all 32 bits are returned (ie @length 32 and @start 0). 316 * 317 * Returns: the sign extended value of the bit field extracted from the 318 * input value. 319 */ 320 static inline int32_t sextract32(uint32_t value, int start, int length) 321 { 322 assert(start >= 0 && length > 0 && length <= 32 - start); 323 /* Note that this implementation relies on right shift of signed 324 * integers being an arithmetic shift. 325 */ 326 return ((int32_t)(value << (32 - length - start))) >> (32 - length); 327 } 328 329 /** 330 * sextract64: 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 64 bit input @value the bit field specified by the 336 * @start and @length parameters, and return it, sign extended to 337 * an int64_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 64 bit word. It is valid to request that 340 * all 64 bits are returned (ie @length 64 and @start 0). 341 * 342 * Returns: the sign extended value of the bit field extracted from the 343 * input value. 344 */ 345 static inline uint64_t sextract64(uint64_t value, int start, int length) 346 { 347 assert(start >= 0 && length > 0 && length <= 64 - start); 348 /* Note that this implementation relies on right shift of signed 349 * integers being an arithmetic shift. 350 */ 351 return ((int64_t)(value << (64 - length - start))) >> (64 - length); 352 } 353 354 /** 355 * deposit32: 356 * @value: initial value to insert bit field into 357 * @start: the lowest bit in the bit field (numbered from 0) 358 * @length: the length of the bit field 359 * @fieldval: the value to insert into the bit field 360 * 361 * Deposit @fieldval into the 32 bit @value at the bit field specified 362 * by the @start and @length parameters, and return the modified 363 * @value. Bits of @value outside the bit field are not modified. 364 * Bits of @fieldval above the least significant @length bits are 365 * ignored. The bit field must lie entirely within the 32 bit word. 366 * It is valid to request that all 32 bits are modified (ie @length 367 * 32 and @start 0). 368 * 369 * Returns: the modified @value. 370 */ 371 static inline uint32_t deposit32(uint32_t value, int start, int length, 372 uint32_t fieldval) 373 { 374 uint32_t mask; 375 assert(start >= 0 && length > 0 && length <= 32 - start); 376 mask = (~0U >> (32 - length)) << start; 377 return (value & ~mask) | ((fieldval << start) & mask); 378 } 379 380 /** 381 * deposit64: 382 * @value: initial value to insert bit field into 383 * @start: the lowest bit in the bit field (numbered from 0) 384 * @length: the length of the bit field 385 * @fieldval: the value to insert into the bit field 386 * 387 * Deposit @fieldval into the 64 bit @value at the bit field specified 388 * by the @start and @length parameters, and return the modified 389 * @value. Bits of @value outside the bit field are not modified. 390 * Bits of @fieldval above the least significant @length bits are 391 * ignored. The bit field must lie entirely within the 64 bit word. 392 * It is valid to request that all 64 bits are modified (ie @length 393 * 64 and @start 0). 394 * 395 * Returns: the modified @value. 396 */ 397 static inline uint64_t deposit64(uint64_t value, int start, int length, 398 uint64_t fieldval) 399 { 400 uint64_t mask; 401 assert(start >= 0 && length > 0 && length <= 64 - start); 402 mask = (~0ULL >> (64 - length)) << start; 403 return (value & ~mask) | ((fieldval << start) & mask); 404 } 405 406 #endif 407
