include/qemu/bitops.h

   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_ULL(nr)             (1ULL << (nr))
  24 #define BIT_MASK(nr)            (1UL << ((nr) % BITS_PER_LONG))
  25 #define BIT_WORD(nr)            ((nr) / BITS_PER_LONG)
  26 #define BITS_TO_LONGS(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
  27
  28 #define MAKE_64BIT_MASK(shift, length) \
  29     (((~0ULL) >> (64 - (length))) << (shift))
  30
  31 /**
  32  * set_bit - Set a bit in memory
  33  * @nr: the bit to set
  34  * @addr: the address to start counting from
  35  */
  36 static inline void set_bit(long nr, unsigned long *addr)
  37 {
  38     unsigned long mask = BIT_MASK(nr);
  39     unsigned long *p = addr + BIT_WORD(nr);
  40
  41     *p  |= mask;
  42 }
  43
  44 /**
  45  * set_bit_atomic - Set a bit in memory atomically
  46  * @nr: the bit to set
  47  * @addr: the address to start counting from
  48  */
  49 static inline void set_bit_atomic(long nr, unsigned long *addr)
  50 {
  51     unsigned long mask = BIT_MASK(nr);
  52     unsigned long *p = addr + BIT_WORD(nr);
  53
  54     qatomic_or(p, mask);
  55 }
  56
  57 /**
  58  * clear_bit - Clears a bit in memory
  59  * @nr: Bit to clear
  60  * @addr: Address to start counting from
  61  */
  62 static inline void clear_bit(long nr, unsigned long *addr)
  63 {
  64     unsigned long mask = BIT_MASK(nr);
  65     unsigned long *p = addr + BIT_WORD(nr);
  66
  67     *p &= ~mask;
  68 }
  69
  70 /**
  71  * clear_bit_atomic - Clears a bit in memory atomically
  72  * @nr: Bit to clear
  73  * @addr: Address to start counting from
  74  */
  75 static inline void clear_bit_atomic(long nr, unsigned long *addr)
  76 {
  77     unsigned long mask = BIT_MASK(nr);
  78     unsigned long *p = addr + BIT_WORD(nr);
  79
  80     return qatomic_and(p, ~mask);
  81 }
  82
  83 /**
  84  * change_bit - Toggle a bit in memory
  85  * @nr: Bit to change
  86  * @addr: Address to start counting from
  87  */
  88 static inline void change_bit(long nr, unsigned long *addr)
  89 {
  90     unsigned long mask = BIT_MASK(nr);
  91     unsigned long *p = addr + BIT_WORD(nr);
  92
  93     *p ^= mask;
  94 }
  95
  96 /**
  97  * test_and_set_bit - Set a bit and return its old value
  98  * @nr: Bit to set
  99  * @addr: Address to count from
 100  */
 101 static inline int test_and_set_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_clear_bit - Clear a bit and return its old value
 113  * @nr: Bit to clear
 114  * @addr: Address to count from
 115  */
 116 static inline int test_and_clear_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_and_change_bit - Change a bit and return its old value
 128  * @nr: Bit to change
 129  * @addr: Address to count from
 130  */
 131 static inline int test_and_change_bit(long nr, unsigned long *addr)
 132 {
 133     unsigned long mask = BIT_MASK(nr);
 134     unsigned long *p = addr + BIT_WORD(nr);
 135     unsigned long old = *p;
 136
 137     *p = old ^ mask;
 138     return (old & mask) != 0;
 139 }
 140
 141 /**
 142  * test_bit - Determine whether a bit is set
 143  * @nr: bit number to test
 144  * @addr: Address to start counting from
 145  */
 146 static inline int test_bit(long nr, const unsigned long *addr)
 147 {
 148     return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
 149 }
 150
 151 /**
 152  * find_last_bit - find the last set bit in a memory region
 153  * @addr: The address to start the search at
 154  * @size: The maximum size to search
 155  *
 156  * Returns the bit number of the last set bit,
 157  * or @size if there is no set bit in the bitmap.
 158  */
 159 unsigned long find_last_bit(const unsigned long *addr,
 160                             unsigned long size);
 161
 162 /**
 163  * find_next_bit - find the next set bit in a memory region
 164  * @addr: The address to base the search on
 165  * @offset: The bitnumber to start searching at
 166  * @size: The bitmap size in bits
 167  *
 168  * Returns the bit number of the next set bit,
 169  * or @size if there are no further set bits in the bitmap.
 170  */
 171 unsigned long find_next_bit(const unsigned long *addr,
 172                             unsigned long size,
 173                             unsigned long offset);
 174
 175 /**
 176  * find_next_zero_bit - find the next cleared bit in a memory region
 177  * @addr: The address to base the search on
 178  * @offset: The bitnumber to start searching at
 179  * @size: The bitmap size in bits
 180  *
 181  * Returns the bit number of the next cleared bit,
 182  * or @size if there are no further clear bits in the bitmap.
 183  */
 184
 185 unsigned long find_next_zero_bit(const unsigned long *addr,
 186                                  unsigned long size,
 187                                  unsigned long offset);
 188
 189 /**
 190  * find_first_bit - find the first set bit in a memory region
 191  * @addr: The address to start the search at
 192  * @size: The maximum size to search
 193  *
 194  * Returns the bit number of the first set bit,
 195  * or @size if there is no set bit in the bitmap.
 196  */
 197 static inline unsigned long find_first_bit(const unsigned long *addr,
 198                                            unsigned long size)
 199 {
 200     unsigned long result, tmp;
 201
 202     for (result = 0; result < size; result += BITS_PER_LONG) {
 203         tmp = *addr++;
 204         if (tmp) {
 205             result += ctzl(tmp);
 206             return result < size ? result : size;
 207         }
 208     }
 209     /* Not found */
 210     return size;
 211 }
 212
 213 /**
 214  * find_first_zero_bit - find the first cleared bit in a memory region
 215  * @addr: The address to start the search at
 216  * @size: The maximum size to search
 217  *
 218  * Returns the bit number of the first cleared bit,
 219  * or @size if there is no clear bit in the bitmap.
 220  */
 221 static inline unsigned long find_first_zero_bit(const unsigned long *addr,
 222                                                 unsigned long size)
 223 {
 224     return find_next_zero_bit(addr, size, 0);
 225 }
 226
 227 /**
 228  * rol8 - rotate an 8-bit value left
 229  * @word: value to rotate
 230  * @shift: bits to roll
 231  */
 232 static inline uint8_t rol8(uint8_t word, unsigned int shift)
 233 {
 234     return (word << (shift & 7)) | (word >> (-shift & 7));
 235 }
 236
 237 /**
 238  * ror8 - rotate an 8-bit value right
 239  * @word: value to rotate
 240  * @shift: bits to roll
 241  */
 242 static inline uint8_t ror8(uint8_t word, unsigned int shift)
 243 {
 244     return (word >> (shift & 7)) | (word << (-shift & 7));
 245 }
 246
 247 /**
 248  * rol16 - rotate a 16-bit value left
 249  * @word: value to rotate
 250  * @shift: bits to roll
 251  */
 252 static inline uint16_t rol16(uint16_t word, unsigned int shift)
 253 {
 254     return (word << (shift & 15)) | (word >> (-shift & 15));
 255 }
 256
 257 /**
 258  * ror16 - rotate a 16-bit value right
 259  * @word: value to rotate
 260  * @shift: bits to roll
 261  */
 262 static inline uint16_t ror16(uint16_t word, unsigned int shift)
 263 {
 264     return (word >> (shift & 15)) | (word << (-shift & 15));
 265 }
 266
 267 /**
 268  * rol32 - rotate a 32-bit value left
 269  * @word: value to rotate
 270  * @shift: bits to roll
 271  */
 272 static inline uint32_t rol32(uint32_t word, unsigned int shift)
 273 {
 274     return (word << (shift & 31)) | (word >> (-shift & 31));
 275 }
 276
 277 /**
 278  * ror32 - rotate a 32-bit value right
 279  * @word: value to rotate
 280  * @shift: bits to roll
 281  */
 282 static inline uint32_t ror32(uint32_t word, unsigned int shift)
 283 {
 284     return (word >> (shift & 31)) | (word << (-shift & 31));
 285 }
 286
 287 /**
 288  * rol64 - rotate a 64-bit value left
 289  * @word: value to rotate
 290  * @shift: bits to roll
 291  */
 292 static inline uint64_t rol64(uint64_t word, unsigned int shift)
 293 {
 294     return (word << (shift & 63)) | (word >> (-shift & 63));
 295 }
 296
 297 /**
 298  * ror64 - rotate a 64-bit value right
 299  * @word: value to rotate
 300  * @shift: bits to roll
 301  */
 302 static inline uint64_t ror64(uint64_t word, unsigned int shift)
 303 {
 304     return (word >> (shift & 63)) | (word << (-shift & 63));
 305 }
 306
 307 /**
 308  * hswap32 - swap 16-bit halfwords within a 32-bit value
 309  * @h: value to swap
 310  */
 311 static inline uint32_t hswap32(uint32_t h)
 312 {
 313     return rol32(h, 16);
 314 }
 315
 316 /**
 317  * hswap64 - swap 16-bit halfwords within a 64-bit value
 318  * @h: value to swap
 319  */
 320 static inline uint64_t hswap64(uint64_t h)
 321 {
 322     uint64_t m = 0x0000ffff0000ffffull;
 323     h = rol64(h, 32);
 324     return ((h & m) << 16) | ((h >> 16) & m);
 325 }
 326
 327 /**
 328  * wswap64 - swap 32-bit words within a 64-bit value
 329  * @h: value to swap
 330  */
 331 static inline uint64_t wswap64(uint64_t h)
 332 {
 333     return rol64(h, 32);
 334 }
 335
 336 /**
 337  * extract32:
 338  * @value: the value to extract the bit field from
 339  * @start: the lowest bit in the bit field (numbered from 0)
 340  * @length: the length of the bit field
 341  *
 342  * Extract from the 32 bit input @value the bit field specified by the
 343  * @start and @length parameters, and return it. The bit field must
 344  * lie entirely within the 32 bit word. It is valid to request that
 345  * all 32 bits are returned (ie @length 32 and @start 0).
 346  *
 347  * Returns: the value of the bit field extracted from the input value.
 348  */
 349 static inline uint32_t extract32(uint32_t value, int start, int length)
 350 {
 351     assert(start >= 0 && length > 0 && length <= 32 - start);
 352     return (value >> start) & (~0U >> (32 - length));
 353 }
 354
 355 /**
 356  * extract8:
 357  * @value: the value to extract the bit field from
 358  * @start: the lowest bit in the bit field (numbered from 0)
 359  * @length: the length of the bit field
 360  *
 361  * Extract from the 8 bit input @value the bit field specified by the
 362  * @start and @length parameters, and return it. The bit field must
 363  * lie entirely within the 8 bit word. It is valid to request that
 364  * all 8 bits are returned (ie @length 8 and @start 0).
 365  *
 366  * Returns: the value of the bit field extracted from the input value.
 367  */
 368 static inline uint8_t extract8(uint8_t value, int start, int length)
 369 {
 370     assert(start >= 0 && length > 0 && length <= 8 - start);
 371     return extract32(value, start, length);
 372 }
 373
 374 /**
 375  * extract16:
 376  * @value: the value to extract the bit field from
 377  * @start: the lowest bit in the bit field (numbered from 0)
 378  * @length: the length of the bit field
 379  *
 380  * Extract from the 16 bit input @value the bit field specified by the
 381  * @start and @length parameters, and return it. The bit field must
 382  * lie entirely within the 16 bit word. It is valid to request that
 383  * all 16 bits are returned (ie @length 16 and @start 0).
 384  *
 385  * Returns: the value of the bit field extracted from the input value.
 386  */
 387 static inline uint16_t extract16(uint16_t value, int start, int length)
 388 {
 389     assert(start >= 0 && length > 0 && length <= 16 - start);
 390     return extract32(value, start, length);
 391 }
 392
 393 /**
 394  * extract64:
 395  * @value: the value to extract the bit field from
 396  * @start: the lowest bit in the bit field (numbered from 0)
 397  * @length: the length of the bit field
 398  *
 399  * Extract from the 64 bit input @value the bit field specified by the
 400  * @start and @length parameters, and return it. The bit field must
 401  * lie entirely within the 64 bit word. It is valid to request that
 402  * all 64 bits are returned (ie @length 64 and @start 0).
 403  *
 404  * Returns: the value of the bit field extracted from the input value.
 405  */
 406 static inline uint64_t extract64(uint64_t value, int start, int length)
 407 {
 408     assert(start >= 0 && length > 0 && length <= 64 - start);
 409     return (value >> start) & (~0ULL >> (64 - length));
 410 }
 411
 412 /**
 413  * sextract32:
 414  * @value: the value to extract the bit field from
 415  * @start: the lowest bit in the bit field (numbered from 0)
 416  * @length: the length of the bit field
 417  *
 418  * Extract from the 32 bit input @value the bit field specified by the
 419  * @start and @length parameters, and return it, sign extended to
 420  * an int32_t (ie with the most significant bit of the field propagated
 421  * to all the upper bits of the return value). The bit field must lie
 422  * entirely within the 32 bit word. It is valid to request that
 423  * all 32 bits are returned (ie @length 32 and @start 0).
 424  *
 425  * Returns: the sign extended value of the bit field extracted from the
 426  * input value.
 427  */
 428 static inline int32_t sextract32(uint32_t value, int start, int length)
 429 {
 430     assert(start >= 0 && length > 0 && length <= 32 - start);
 431     /* Note that this implementation relies on right shift of signed
 432      * integers being an arithmetic shift.
 433      */
 434     return ((int32_t)(value << (32 - length - start))) >> (32 - length);
 435 }
 436
 437 /**
 438  * sextract64:
 439  * @value: the value to extract the bit field from
 440  * @start: the lowest bit in the bit field (numbered from 0)
 441  * @length: the length of the bit field
 442  *
 443  * Extract from the 64 bit input @value the bit field specified by the
 444  * @start and @length parameters, and return it, sign extended to
 445  * an int64_t (ie with the most significant bit of the field propagated
 446  * to all the upper bits of the return value). The bit field must lie
 447  * entirely within the 64 bit word. It is valid to request that
 448  * all 64 bits are returned (ie @length 64 and @start 0).
 449  *
 450  * Returns: the sign extended value of the bit field extracted from the
 451  * input value.
 452  */
 453 static inline int64_t sextract64(uint64_t value, int start, int length)
 454 {
 455     assert(start >= 0 && length > 0 && length <= 64 - start);
 456     /* Note that this implementation relies on right shift of signed
 457      * integers being an arithmetic shift.
 458      */
 459     return ((int64_t)(value << (64 - length - start))) >> (64 - length);
 460 }
 461
 462 /**
 463  * deposit32:
 464  * @value: initial value to insert bit field into
 465  * @start: the lowest bit in the bit field (numbered from 0)
 466  * @length: the length of the bit field
 467  * @fieldval: the value to insert into the bit field
 468  *
 469  * Deposit @fieldval into the 32 bit @value at the bit field specified
 470  * by the @start and @length parameters, and return the modified
 471  * @value. Bits of @value outside the bit field are not modified.
 472  * Bits of @fieldval above the least significant @length bits are
 473  * ignored. The bit field must lie entirely within the 32 bit word.
 474  * It is valid to request that all 32 bits are modified (ie @length
 475  * 32 and @start 0).
 476  *
 477  * Returns: the modified @value.
 478  */
 479 static inline uint32_t deposit32(uint32_t value, int start, int length,
 480                                  uint32_t fieldval)
 481 {
 482     uint32_t mask;
 483     assert(start >= 0 && length > 0 && length <= 32 - start);
 484     mask = (~0U >> (32 - length)) << start;
 485     return (value & ~mask) | ((fieldval << start) & mask);
 486 }
 487
 488 /**
 489  * deposit64:
 490  * @value: initial value to insert bit field into
 491  * @start: the lowest bit in the bit field (numbered from 0)
 492  * @length: the length of the bit field
 493  * @fieldval: the value to insert into the bit field
 494  *
 495  * Deposit @fieldval into the 64 bit @value at the bit field specified
 496  * by the @start and @length parameters, and return the modified
 497  * @value. Bits of @value outside the bit field are not modified.
 498  * Bits of @fieldval above the least significant @length bits are
 499  * ignored. The bit field must lie entirely within the 64 bit word.
 500  * It is valid to request that all 64 bits are modified (ie @length
 501  * 64 and @start 0).
 502  *
 503  * Returns: the modified @value.
 504  */
 505 static inline uint64_t deposit64(uint64_t value, int start, int length,
 506                                  uint64_t fieldval)
 507 {
 508     uint64_t mask;
 509     assert(start >= 0 && length > 0 && length <= 64 - start);
 510     mask = (~0ULL >> (64 - length)) << start;
 511     return (value & ~mask) | ((fieldval << start) & mask);
 512 }
 513
 514 /**
 515  * half_shuffle32:
 516  * @x: 32-bit value (of which only the bottom 16 bits are of interest)
 517  *
 518  * Given an input value::
 519  *
 520  *   xxxx xxxx xxxx xxxx ABCD EFGH IJKL MNOP
 521  *
 522  * return the value where the bottom 16 bits are spread out into
 523  * the odd bits in the word, and the even bits are zeroed::
 524  *
 525  *   0A0B 0C0D 0E0F 0G0H 0I0J 0K0L 0M0N 0O0P
 526  *
 527  * Any bits set in the top half of the input are ignored.
 528  *
 529  * Returns: the shuffled bits.
 530  */
 531 static inline uint32_t half_shuffle32(uint32_t x)
 532 {
 533     /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits".
 534      * It ignores any bits set in the top half of the input.
 535      */
 536     x = ((x & 0xFF00) << 8) | (x & 0x00FF);
 537     x = ((x << 4) | x) & 0x0F0F0F0F;
 538     x = ((x << 2) | x) & 0x33333333;
 539     x = ((x << 1) | x) & 0x55555555;
 540     return x;
 541 }
 542
 543 /**
 544  * half_shuffle64:
 545  * @x: 64-bit value (of which only the bottom 32 bits are of interest)
 546  *
 547  * Given an input value::
 548  *
 549  *   xxxx xxxx xxxx .... xxxx xxxx ABCD EFGH IJKL MNOP QRST UVWX YZab cdef
 550  *
 551  * return the value where the bottom 32 bits are spread out into
 552  * the odd bits in the word, and the even bits are zeroed::
 553  *
 554  *   0A0B 0C0D 0E0F 0G0H 0I0J 0K0L 0M0N .... 0U0V 0W0X 0Y0Z 0a0b 0c0d 0e0f
 555  *
 556  * Any bits set in the top half of the input are ignored.
 557  *
 558  * Returns: the shuffled bits.
 559  */
 560 static inline uint64_t half_shuffle64(uint64_t x)
 561 {
 562     /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits".
 563      * It ignores any bits set in the top half of the input.
 564      */
 565     x = ((x & 0xFFFF0000ULL) << 16) | (x & 0xFFFF);
 566     x = ((x << 8) | x) & 0x00FF00FF00FF00FFULL;
 567     x = ((x << 4) | x) & 0x0F0F0F0F0F0F0F0FULL;
 568     x = ((x << 2) | x) & 0x3333333333333333ULL;
 569     x = ((x << 1) | x) & 0x5555555555555555ULL;
 570     return x;
 571 }
 572
 573 /**
 574  * half_unshuffle32:
 575  * @x: 32-bit value (of which only the odd bits are of interest)
 576  *
 577  * Given an input value::
 578  *
 579  *   xAxB xCxD xExF xGxH xIxJ xKxL xMxN xOxP
 580  *
 581  * return the value where all the odd bits are compressed down
 582  * into the low half of the word, and the high half is zeroed::
 583  *
 584  *   0000 0000 0000 0000 ABCD EFGH IJKL MNOP
 585  *
 586  * Any even bits set in the input are ignored.
 587  *
 588  * Returns: the unshuffled bits.
 589  */
 590 static inline uint32_t half_unshuffle32(uint32_t x)
 591 {
 592     /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits".
 593      * where it is called an inverse half shuffle.
 594      */
 595     x &= 0x55555555;
 596     x = ((x >> 1) | x) & 0x33333333;
 597     x = ((x >> 2) | x) & 0x0F0F0F0F;
 598     x = ((x >> 4) | x) & 0x00FF00FF;
 599     x = ((x >> 8) | x) & 0x0000FFFF;
 600     return x;
 601 }
 602
 603 /**
 604  * half_unshuffle64:
 605  * @x: 64-bit value (of which only the odd bits are of interest)
 606  *
 607  * Given an input value::
 608  *
 609  *   xAxB xCxD xExF xGxH xIxJ xKxL xMxN .... xUxV xWxX xYxZ xaxb xcxd xexf
 610  *
 611  * return the value where all the odd bits are compressed down
 612  * into the low half of the word, and the high half is zeroed::
 613  *
 614  *   0000 0000 0000 .... 0000 0000 ABCD EFGH IJKL MNOP QRST UVWX YZab cdef
 615  *
 616  * Any even bits set in the input are ignored.
 617  *
 618  * Returns: the unshuffled bits.
 619  */
 620 static inline uint64_t half_unshuffle64(uint64_t x)
 621 {
 622     /* This algorithm is from _Hacker's Delight_ section 7-2 "Shuffling Bits".
 623      * where it is called an inverse half shuffle.
 624      */
 625     x &= 0x5555555555555555ULL;
 626     x = ((x >> 1) | x) & 0x3333333333333333ULL;
 627     x = ((x >> 2) | x) & 0x0F0F0F0F0F0F0F0FULL;
 628     x = ((x >> 4) | x) & 0x00FF00FF00FF00FFULL;
 629     x = ((x >> 8) | x) & 0x0000FFFF0000FFFFULL;
 630     x = ((x >> 16) | x) & 0x00000000FFFFFFFFULL;
 631     return x;
 632 }
 633
 634 #endif