1dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith/* 2dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith * Bitops Module 3dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith * 4dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com> 5dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith * 6dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h 7dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith * 8dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith * This work is licensed under the terms of the GNU LGPL, version 2.1 or later. 9dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith * See the COPYING.LIB file in the top-level directory. 10dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith */ 11dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith 12dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith#ifndef BITOPS_H 13dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith#define BITOPS_H 14dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith 150d8ab2ed4b7555b6fde965238222e5099614d7bbSebastian Redl#include "qemu-common.h" 165e4e58b805e0e03a669aa517d1d20d4735a3192eRichard Smith#include "host-utils.h" 175e4e58b805e0e03a669aa517d1d20d4735a3192eRichard Smith 185e4e58b805e0e03a669aa517d1d20d4735a3192eRichard Smith#define BITS_PER_BYTE CHAR_BIT 195e4e58b805e0e03a669aa517d1d20d4735a3192eRichard Smith#define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) 20dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith 21dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith#define BIT(nr) (1UL << (nr)) 22dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) 23dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) 24dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) 25dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith 26dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith/** 27840462670ba7a6bc26265a2306b35f2f0f01f51cRichard Smith * set_bit - Set a bit in memory 28840462670ba7a6bc26265a2306b35f2f0f01f51cRichard Smith * @nr: the bit to set 29dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith * @addr: the address to start counting from 30dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith */ 31dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smithstatic inline void set_bit(int nr, unsigned long *addr) 32dbe01bb024ce9407954275a5e3c7e1a7113ca9faRichard Smith{ 335e4e58b805e0e03a669aa517d1d20d4735a3192eRichard Smith unsigned long mask = BIT_MASK(nr); 345e4e58b805e0e03a669aa517d1d20d4735a3192eRichard Smith 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 */ 44static 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 */ 57static 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 */ 70static 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 */ 85static 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 */ 100static 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 */ 115static 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 */ 127unsigned 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 */ 136unsigned 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 146unsigned 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 */ 157static 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 */ 170static 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 176static 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 */ 191static 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 */ 201static 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 */ 211static 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 */ 221static 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 */ 231static 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 */ 241static 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 */ 251static 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 */ 261static 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 */ 279static 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 */ 298static 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 */ 320static 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 */ 345static 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 */ 371static 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 */ 397static 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