bit_macros.h 9.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206
  1. /*
  2. bit_macros.h
  3. project: bit array C library
  4. url: https://github.com/noporpoise/BitArray/
  5. author: Isaac Turner <turner.isaac@gmail.com>
  6. license: Public Domain, no warranty
  7. date: Dec 2013
  8. */
  9. #ifndef BITSET_H_
  10. #define BITSET_H_
  11. #include <inttypes.h>
  12. #include <sched.h>
  13. // trailing_zeros is number of least significant zeros
  14. // leading_zeros is number of most significant zeros
  15. #if defined(_WIN32)
  16. #define trailing_zeros(x) ({ __typeof(x) _r; _BitScanReverse64(&_r, x); _r; })
  17. #define leading_zeros(x) ({ __typeof(x) _r; _BitScanForward64(&_r, x); _r; })
  18. #else
  19. #define trailing_zeros(x) ((x) ? (__typeof(x))__builtin_ctzll(x) : (__typeof(x))sizeof(x)*8)
  20. #define leading_zeros(x) ((x) ? (__typeof(x))__builtin_clzll(x) : (__typeof(x))sizeof(x)*8)
  21. #endif
  22. // Get index of top set bit. If x is 0 return nbits
  23. #define top_set_bit(x) ((x) ? sizeof(x)*8-leading_zeros(x)-1 : sizeof(x)*8)
  24. #define roundup_bits2bytes(bits) (((bits)+7)/8)
  25. #define roundup_bits2words32(bits) (((bits)+31)/32)
  26. #define roundup_bits2words64(bits) (((bits)+63)/64)
  27. // Round a number up to the nearest number that is a power of two
  28. #define roundup2pow(x) (1UL << (64 - leading_zeros(x)))
  29. #define rot32(x,r) (((x)<<(r)) | ((x)>>(32-(r))))
  30. #define rot64(x,r) (((x)<<(r)) | ((x)>>(64-(r))))
  31. // need to check for length == 0, undefined behaviour if uint64_t >> 64 etc
  32. #define bitmask(nbits,type) ((nbits) ? ~(type)0 >> (sizeof(type)*8-(nbits)): (type)0)
  33. #define bitmask32(nbits) bitmask(nbits,uint32_t)
  34. #define bitmask64(nbits) bitmask(nbits,uint64_t)
  35. // A possibly faster way to combine two words with a mask
  36. //#define bitmask_merge(a,b,abits) ((a & abits) | (b & ~abits))
  37. #define bitmask_merge(a,b,abits) (b ^ ((a ^ b) & abits))
  38. // Swap lowest four bits. A nibble is 4 bits (i.e. half a byte)
  39. #define rev_nibble(x) ((((x)&1)<<3)|(((x)&2)<<1)|(((x)&4)>>1)|(((x)&8)>>3))
  40. //
  41. // Bit array (bitset)
  42. //
  43. // bitsetX_wrd(): get word for a given position
  44. // bitsetX_idx(): get index within word for a given position
  45. #define _VOLPTR(x) ((volatile __typeof(x) *)(&(x)))
  46. #define _VOLVALUE(x) (*_VOLPTR(x))
  47. #define _TYPESHIFT(arr,word,shift) \
  48. ((__typeof(*(arr)))((__typeof(*(arr)))(word) << (shift)))
  49. #define bitsetX_wrd(wrdbits,pos) ((pos) / (wrdbits))
  50. #define bitsetX_idx(wrdbits,pos) ((pos) % (wrdbits))
  51. #define bitset32_wrd(pos) ((pos) >> 5)
  52. #define bitset32_idx(pos) ((pos) & 31)
  53. #define bitset64_wrd(pos) ((pos) >> 6)
  54. #define bitset64_idx(pos) ((pos) & 63)
  55. //
  56. // Bit functions on arrays
  57. //
  58. #define bitset2_get(arr,wrd,idx) (((arr)[wrd] >> (idx)) & 0x1)
  59. #define bitset2_set(arr,wrd,idx) ((arr)[wrd] |= _TYPESHIFT(arr,1,idx))
  60. #define bitset2_del(arr,wrd,idx) ((arr)[wrd] &=~ _TYPESHIFT(arr,1,idx))
  61. #define bitset2_tgl(arr,wrd,idx) ((arr)[wrd] ^= _TYPESHIFT(arr,1,idx))
  62. #define bitset2_or(arr,wrd,idx,bit) ((arr)[wrd] |= _TYPESHIFT(arr,bit,idx))
  63. #define bitset2_xor(arr,wrd,idx,bit) ((arr)[wrd] = ~((arr)[wrd] ^ (~_TYPESHIFT(arr,bit,idx))))
  64. #define bitset2_and(arr,wrd,idx,bit) ((arr)[wrd] &= (_TYPESHIFT(arr,bit,idx) | ~_TYPESHIFT(arr,1,idx)))
  65. #define bitset2_cpy(arr,wrd,idx,bit) ((arr)[wrd] = ((arr)[wrd] &~ _TYPESHIFT(arr,1,idx)) | _TYPESHIFT(arr,bit,idx))
  66. //
  67. // Thread safe versions
  68. //
  69. // They return the value of the bit (0 or 1) before it was updated
  70. #define bitset2_get_mt(arr,wrd,idx) bitset2_get(_VOLPTR(*(arr)),wrd,idx)
  71. #define bitset2_set_mt(arr,wrd,idx) ((__sync_fetch_and_or (_VOLPTR((arr)[wrd]), _TYPESHIFT(arr,1,idx)) >> (idx))&1)
  72. #define bitset2_del_mt(arr,wrd,idx) ((__sync_fetch_and_and(_VOLPTR((arr)[wrd]), ~_TYPESHIFT(arr,1,idx)) >> (idx))&1)
  73. #define bitset2_tgl_mt(arr,wrd,idx) ((__sync_fetch_and_xor(_VOLPTR((arr)[wrd]), _TYPESHIFT(arr,1,idx)) >> (idx))&1)
  74. #define bitset2_or_mt(arr,wrd,idx,bit) ((__sync_fetch_and_or (_VOLPTR((arr)[wrd]), _TYPESHIFT(arr,bit,idx)) >> (idx))&1)
  75. #define bitset2_xor_mt(arr,wrd,idx,bit) ((__sync_fetch_and_xor(_VOLPTR((arr)[wrd]), _TYPESHIFT(arr,bit,idx)) >> (idx))&1)
  76. #define bitset2_and_mt(arr,wrd,idx,bit) ((__sync_fetch_and_and(_VOLPTR((arr)[wrd]), (_TYPESHIFT(arr,bit,idx) | ~_TYPESHIFT(arr,1,idx))) >> (idx))&1)
  77. #define bitset2_cpy_mt(arr,wrd,idx,bit) ((bit) ? bitset2_set_mt(arr,wrd,idx) : bitset2_del_mt(arr,wrd,idx))
  78. //
  79. // Auto detect size of type from pointer
  80. //
  81. #define bitset_wrd(arr,pos) bitsetX_wrd(sizeof(*(arr))*8,pos)
  82. #define bitset_idx(arr,pos) bitsetX_idx(sizeof(*(arr))*8,pos)
  83. #define bitset_op(func,arr,pos) func(arr, bitset_wrd(arr,pos), bitset_idx(arr,pos))
  84. #define bitset_op2(func,arr,pos,bit) func(arr, bitset_wrd(arr,pos), bitset_idx(arr,pos), bit)
  85. // Auto-detect type size: bit functions
  86. #define bitset_get(arr,pos) bitset_op(bitset2_get, arr, pos)
  87. #define bitset_set(arr,pos) bitset_op(bitset2_set, arr, pos)
  88. #define bitset_del(arr,pos) bitset_op(bitset2_del, arr, pos)
  89. #define bitset_tgl(arr,pos) bitset_op(bitset2_tgl, arr, pos)
  90. #define bitset_or(arr,pos,bit) bitset_op2(bitset2_or, arr, pos, bit)
  91. #define bitset_xor(arr,pos,bit) bitset_op2(bitset2_xor, arr, pos, bit)
  92. #define bitset_and(arr,pos,bit) bitset_op2(bitset2_and, arr, pos, bit)
  93. #define bitset_cpy(arr,pos,bit) bitset_op2(bitset2_cpy, arr, pos, bit)
  94. // Auto-detect type size: thread safe bit functions
  95. // They return the value of the bit (0 or 1) before it was updated
  96. #define bitset_get_mt(arr,pos) bitset_op(bitset2_get_mt, arr, pos)
  97. #define bitset_set_mt(arr,pos) bitset_op(bitset2_set_mt, arr, pos)
  98. #define bitset_del_mt(arr,pos) bitset_op(bitset2_del_mt, arr, pos)
  99. #define bitset_tgl_mt(arr,pos) bitset_op(bitset2_tgl_mt, arr, pos)
  100. #define bitset_or_mt(arr,pos,bit) bitset_op2(bitset2_or_mt, arr, pos, bit)
  101. #define bitset_xor_mt(arr,pos,bit) bitset_op2(bitset2_xor_mt, arr, pos, bit)
  102. #define bitset_and_mt(arr,pos,bit) bitset_op2(bitset2_and_mt, arr, pos, bit)
  103. #define bitset_cpy_mt(arr,pos,bit) bitset_op2(bitset2_cpy_mt, arr, pos, bit)
  104. // Clearing a word does not return a meaningful value
  105. #define bitset_clear_word(arr,pos) ((arr)[bitset_wrd(arr,pos)] = 0)
  106. #define bitset_clear_word_mt(arr,pos) (_VOLVALUE((arr)[bitset_wrd(arr,pos)]) = 0)
  107. //
  108. // Compact bit array of spin locks
  109. // These are most effecient when arr is of type: volatile char*
  110. //
  111. // Acquire a lock
  112. #define bitlock_acquire_block(arr,pos,wait,abandon) do { \
  113. size_t _w = bitset_wrd(arr,pos); \
  114. __typeof(*(arr)) _o, _n, _b = _TYPESHIFT(arr, 1, bitset_idx(arr,pos)); \
  115. do { \
  116. while((_o = _VOLVALUE((arr)[_w])) & _b) { wait } \
  117. abandon \
  118. _n = _o | _b; \
  119. } while(!__sync_bool_compare_and_swap(_VOLPTR((arr)[_w]), _o, _n)); \
  120. __sync_synchronize(); /* Must not move commands to before acquiring lock */ \
  121. } while(0)
  122. // Undefined behaviour if you do not already hold the lock
  123. #define bitlock_release(arr,pos) do { \
  124. size_t _w = bitset_wrd(arr,pos); \
  125. __typeof(*(arr)) _mask = ~_TYPESHIFT(arr, 1, bitset_idx(arr,pos)); \
  126. __sync_synchronize(); /* Must get the lock before releasing it */ \
  127. __sync_and_and_fetch(_VOLPTR((arr)[_w]), _mask); \
  128. } while(0)
  129. #define bitlock_acquire(arr,pos) bitlock_acquire_block(arr,pos,{},{})
  130. // calls yield if cannot acquire the lock
  131. #define bitlock_yield_acquire(arr,pos) bitlock_acquire_block(arr,pos,sched_yield();,{})
  132. // Block until we get the lock or someone else does
  133. // sets the memory pointed to by retptr to 1 if we got the lock, 0 otherwise
  134. #define bitlock_try_acquire(arr,pos,retptr) do { \
  135. *retptr = 1; /* default to success, set to zero if locked */ \
  136. bitlock_acquire_block(arr,pos,{*retptr=0;break;},if(!*retptr){break;}); \
  137. } while(0)
  138. /*
  139. * Byteswapping
  140. */
  141. /* clang uses these to check for features */
  142. #ifndef __has_feature
  143. #define __has_feature(x) 0
  144. #endif
  145. #ifndef __has_builtin
  146. #define __has_builtin(x) 0
  147. #endif
  148. /* GCC versions < 4.3 do not have __builtin_bswapX() */
  149. #if ( defined(__clang__) && !__has_builtin(__builtin_bswap64) ) || \
  150. ( !defined(__clang__) && defined(__GNUC__) && defined(__GNUC_MINOR__) && \
  151. ( (__GNUC__ < 4) || (__GNUC__ == 4 && __GNUC_MINOR__ < 3)) )
  152. #define byteswap64(x) ( (((uint64_t)(x) << 56)) | \
  153. (((uint64_t)(x) << 40) & 0xff000000000000ULL) | \
  154. (((uint64_t)(x) << 24) & 0xff0000000000ULL) | \
  155. (((uint64_t)(x) << 8) & 0xff00000000ULL) | \
  156. (((uint64_t)(x) >> 8) & 0xff000000ULL) | \
  157. (((uint64_t)(x) >> 24) & 0xff0000ULL) | \
  158. (((uint64_t)(x) >> 40) & 0xff00ULL) | \
  159. (((uint64_t)(x) >> 56)) )
  160. #define byteswap32(x) ( (((uint32_t)(x) << 24)) | \
  161. (((uint32_t)(x) << 8) & 0xff0000U) | \
  162. (((uint32_t)(x) >> 8) & 0xff00U) | \
  163. (((uint32_t)(x) >> 24)) )
  164. /* uint16_t type might be bigger than 2 bytes, so need to mask */
  165. #define byteswap16(x) ( (((uint16_t)(x) & 0xff) << 8) | \
  166. (((uint16_t)(x) >> 8) & 0xff) )
  167. #else
  168. #define byteswap64(x) __builtin_bswap64(x)
  169. #define byteswap32(x) __builtin_bswap64(x)
  170. #define byteswap16(x) __builtin_bswap64(x)
  171. #endif
  172. #endif /* BITLOCK_H_ */