include/linux/bitops.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 #ifndef _LINUX_BITOPS_H
   3 #define _LINUX_BITOPS_H
   4
   5 #include <asm/types.h>
   6 #include <linux/bits.h>
   7 #include <linux/typecheck.h>
   8
   9 #include <uapi/linux/kernel.h>
  10
  11 #define BITS_PER_TYPE(type)     (sizeof(type) * BITS_PER_BYTE)
  12 #define BITS_TO_LONGS(nr)       __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
  13 #define BITS_TO_U64(nr)         __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
  14 #define BITS_TO_U32(nr)         __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
  15 #define BITS_TO_BYTES(nr)       __KERNEL_DIV_ROUND_UP(nr, BITS_PER_TYPE(char))
  16
  17 #define BYTES_TO_BITS(nb)       ((nb) * BITS_PER_BYTE)
  18
  19 extern unsigned int __sw_hweight8(unsigned int w);
  20 extern unsigned int __sw_hweight16(unsigned int w);
  21 extern unsigned int __sw_hweight32(unsigned int w);
  22 extern unsigned long __sw_hweight64(__u64 w);
  23
  24 /*
  25  * Defined here because those may be needed by architecture-specific static
  26  * inlines.
  27  */
  28
  29 #include <asm-generic/bitops/generic-non-atomic.h>
  30
  31 /*
  32  * Many architecture-specific non-atomic bitops contain inline asm code and due
  33  * to that the compiler can't optimize them to compile-time expressions or
  34  * constants. In contrary, generic_*() helpers are defined in pure C and
  35  * compilers optimize them just well.
  36  * Therefore, to make `unsigned long foo = 0; __set_bit(BAR, &foo)` effectively
  37  * equal to `unsigned long foo = BIT(BAR)`, pick the generic C alternative when
  38  * the arguments can be resolved at compile time. That expression itself is a
  39  * constant and doesn't bring any functional changes to the rest of cases.
  40  * The casts to `uintptr_t` are needed to mitigate `-Waddress` warnings when
  41  * passing a bitmap from .bss or .data (-> `!!addr` is always true).
  42  */
  43 #define bitop(op, nr, addr)                                             \
  44         ((__builtin_constant_p(nr) &&                                   \
  45           __builtin_constant_p((uintptr_t)(addr) != (uintptr_t)NULL) && \
  46           (uintptr_t)(addr) != (uintptr_t)NULL &&                       \
  47           __builtin_constant_p(*(const unsigned long *)(addr))) ?       \
  48          const##op(nr, addr) : op(nr, addr))
  49
  50 #define __set_bit(nr, addr)             bitop(___set_bit, nr, addr)
  51 #define __clear_bit(nr, addr)           bitop(___clear_bit, nr, addr)
  52 #define __change_bit(nr, addr)          bitop(___change_bit, nr, addr)
  53 #define __test_and_set_bit(nr, addr)    bitop(___test_and_set_bit, nr, addr)
  54 #define __test_and_clear_bit(nr, addr)  bitop(___test_and_clear_bit, nr, addr)
  55 #define __test_and_change_bit(nr, addr) bitop(___test_and_change_bit, nr, addr)
  56 #define test_bit(nr, addr)              bitop(_test_bit, nr, addr)
  57 #define test_bit_acquire(nr, addr)      bitop(_test_bit_acquire, nr, addr)
  58
  59 /*
  60  * Include this here because some architectures need generic_ffs/fls in
  61  * scope
  62  */
  63 #include <asm/bitops.h>
  64
  65 /* Check that the bitops prototypes are sane */
  66 #define __check_bitop_pr(name)                                          \
  67         static_assert(__same_type(arch_##name, generic_##name) &&       \
  68                       __same_type(const_##name, generic_##name) &&      \
  69                       __same_type(_##name, generic_##name))
  70
  71 __check_bitop_pr(__set_bit);
  72 __check_bitop_pr(__clear_bit);
  73 __check_bitop_pr(__change_bit);
  74 __check_bitop_pr(__test_and_set_bit);
  75 __check_bitop_pr(__test_and_clear_bit);
  76 __check_bitop_pr(__test_and_change_bit);
  77 __check_bitop_pr(test_bit);
  78 __check_bitop_pr(test_bit_acquire);
  79
  80 #undef __check_bitop_pr
  81
  82 static inline int get_bitmask_order(unsigned int count)
  83 {
  84         int order;
  85
  86         order = fls(count);
  87         return order;   /* We could be slightly more clever with -1 here... */
  88 }
  89
  90 static __always_inline unsigned long hweight_long(unsigned long w)
  91 {
  92         return sizeof(w) == 4 ? hweight32(w) : hweight64((__u64)w);
  93 }
  94
  95 /**
  96  * rol64 - rotate a 64-bit value left
  97  * @word: value to rotate
  98  * @shift: bits to roll
  99  */
 100 static inline __u64 rol64(__u64 word, unsigned int shift)
 101 {
 102         return (word << (shift & 63)) | (word >> ((-shift) & 63));
 103 }
 104
 105 /**
 106  * ror64 - rotate a 64-bit value right
 107  * @word: value to rotate
 108  * @shift: bits to roll
 109  */
 110 static inline __u64 ror64(__u64 word, unsigned int shift)
 111 {
 112         return (word >> (shift & 63)) | (word << ((-shift) & 63));
 113 }
 114
 115 /**
 116  * rol32 - rotate a 32-bit value left
 117  * @word: value to rotate
 118  * @shift: bits to roll
 119  */
 120 static inline __u32 rol32(__u32 word, unsigned int shift)
 121 {
 122         return (word << (shift & 31)) | (word >> ((-shift) & 31));
 123 }
 124
 125 /**
 126  * ror32 - rotate a 32-bit value right
 127  * @word: value to rotate
 128  * @shift: bits to roll
 129  */
 130 static inline __u32 ror32(__u32 word, unsigned int shift)
 131 {
 132         return (word >> (shift & 31)) | (word << ((-shift) & 31));
 133 }
 134
 135 /**
 136  * rol16 - rotate a 16-bit value left
 137  * @word: value to rotate
 138  * @shift: bits to roll
 139  */
 140 static inline __u16 rol16(__u16 word, unsigned int shift)
 141 {
 142         return (word << (shift & 15)) | (word >> ((-shift) & 15));
 143 }
 144
 145 /**
 146  * ror16 - rotate a 16-bit value right
 147  * @word: value to rotate
 148  * @shift: bits to roll
 149  */
 150 static inline __u16 ror16(__u16 word, unsigned int shift)
 151 {
 152         return (word >> (shift & 15)) | (word << ((-shift) & 15));
 153 }
 154
 155 /**
 156  * rol8 - rotate an 8-bit value left
 157  * @word: value to rotate
 158  * @shift: bits to roll
 159  */
 160 static inline __u8 rol8(__u8 word, unsigned int shift)
 161 {
 162         return (word << (shift & 7)) | (word >> ((-shift) & 7));
 163 }
 164
 165 /**
 166  * ror8 - rotate an 8-bit value right
 167  * @word: value to rotate
 168  * @shift: bits to roll
 169  */
 170 static inline __u8 ror8(__u8 word, unsigned int shift)
 171 {
 172         return (word >> (shift & 7)) | (word << ((-shift) & 7));
 173 }
 174
 175 /**
 176  * sign_extend32 - sign extend a 32-bit value using specified bit as sign-bit
 177  * @value: value to sign extend
 178  * @index: 0 based bit index (0<=index<32) to sign bit
 179  *
 180  * This is safe to use for 16- and 8-bit types as well.
 181  */
 182 static __always_inline __s32 sign_extend32(__u32 value, int index)
 183 {
 184         __u8 shift = 31 - index;
 185         return (__s32)(value << shift) >> shift;
 186 }
 187
 188 /**
 189  * sign_extend64 - sign extend a 64-bit value using specified bit as sign-bit
 190  * @value: value to sign extend
 191  * @index: 0 based bit index (0<=index<64) to sign bit
 192  */
 193 static __always_inline __s64 sign_extend64(__u64 value, int index)
 194 {
 195         __u8 shift = 63 - index;
 196         return (__s64)(value << shift) >> shift;
 197 }
 198
 199 static inline unsigned int fls_long(unsigned long l)
 200 {
 201         if (sizeof(l) == 4)
 202                 return fls(l);
 203         return fls64(l);
 204 }
 205
 206 static inline int get_count_order(unsigned int count)
 207 {
 208         if (count == 0)
 209                 return -1;
 210
 211         return fls(--count);
 212 }
 213
 214 /**
 215  * get_count_order_long - get order after rounding @l up to power of 2
 216  * @l: parameter
 217  *
 218  * it is same as get_count_order() but with long type parameter
 219  */
 220 static inline int get_count_order_long(unsigned long l)
 221 {
 222         if (l == 0UL)
 223                 return -1;
 224         return (int)fls_long(--l);
 225 }
 226
 227 /**
 228  * __ffs64 - find first set bit in a 64 bit word
 229  * @word: The 64 bit word
 230  *
 231  * On 64 bit arches this is a synonym for __ffs
 232  * The result is not defined if no bits are set, so check that @word
 233  * is non-zero before calling this.
 234  */
 235 static inline unsigned int __ffs64(u64 word)
 236 {
 237 #if BITS_PER_LONG == 32
 238         if (((u32)word) == 0UL)
 239                 return __ffs((u32)(word >> 32)) + 32;
 240 #elif BITS_PER_LONG != 64
 241 #error BITS_PER_LONG not 32 or 64
 242 #endif
 243         return __ffs((unsigned long)word);
 244 }
 245
 246 /**
 247  * fns - find N'th set bit in a word
 248  * @word: The word to search
 249  * @n: Bit to find
 250  */
 251 static inline unsigned int fns(unsigned long word, unsigned int n)
 252 {
 253         while (word && n--)
 254                 word &= word - 1;
 255
 256         return word ? __ffs(word) : BITS_PER_LONG;
 257 }
 258
 259 /**
 260  * assign_bit - Assign value to a bit in memory
 261  * @nr: the bit to set
 262  * @addr: the address to start counting from
 263  * @value: the value to assign
 264  */
 265 #define assign_bit(nr, addr, value)                                     \
 266         ((value) ? set_bit((nr), (addr)) : clear_bit((nr), (addr)))
 267
 268 #define __assign_bit(nr, addr, value)                                   \
 269         ((value) ? __set_bit((nr), (addr)) : __clear_bit((nr), (addr)))
 270
 271 /**
 272  * __ptr_set_bit - Set bit in a pointer's value
 273  * @nr: the bit to set
 274  * @addr: the address of the pointer variable
 275  *
 276  * Example:
 277  *      void *p = foo();
 278  *      __ptr_set_bit(bit, &p);
 279  */
 280 #define __ptr_set_bit(nr, addr)                         \
 281         ({                                              \
 282                 typecheck_pointer(*(addr));             \
 283                 __set_bit(nr, (unsigned long *)(addr)); \
 284         })
 285
 286 /**
 287  * __ptr_clear_bit - Clear bit in a pointer's value
 288  * @nr: the bit to clear
 289  * @addr: the address of the pointer variable
 290  *
 291  * Example:
 292  *      void *p = foo();
 293  *      __ptr_clear_bit(bit, &p);
 294  */
 295 #define __ptr_clear_bit(nr, addr)                         \
 296         ({                                                \
 297                 typecheck_pointer(*(addr));               \
 298                 __clear_bit(nr, (unsigned long *)(addr)); \
 299         })
 300
 301 /**
 302  * __ptr_test_bit - Test bit in a pointer's value
 303  * @nr: the bit to test
 304  * @addr: the address of the pointer variable
 305  *
 306  * Example:
 307  *      void *p = foo();
 308  *      if (__ptr_test_bit(bit, &p)) {
 309  *              ...
 310  *      } else {
 311  *              ...
 312  *      }
 313  */
 314 #define __ptr_test_bit(nr, addr)                       \
 315         ({                                             \
 316                 typecheck_pointer(*(addr));            \
 317                 test_bit(nr, (unsigned long *)(addr)); \
 318         })
 319
 320 #ifdef __KERNEL__
 321
 322 #ifndef set_mask_bits
 323 #define set_mask_bits(ptr, mask, bits)  \
 324 ({                                                              \
 325         const typeof(*(ptr)) mask__ = (mask), bits__ = (bits);  \
 326         typeof(*(ptr)) old__, new__;                            \
 327                                                                 \
 328         old__ = READ_ONCE(*(ptr));                              \
 329         do {                                                    \
 330                 new__ = (old__ & ~mask__) | bits__;             \
 331         } while (!try_cmpxchg(ptr, &old__, new__));             \
 332                                                                 \
 333         old__;                                                  \
 334 })
 335 #endif
 336
 337 #ifndef bit_clear_unless
 338 #define bit_clear_unless(ptr, clear, test)      \
 339 ({                                                              \
 340         const typeof(*(ptr)) clear__ = (clear), test__ = (test);\
 341         typeof(*(ptr)) old__, new__;                            \
 342                                                                 \
 343         old__ = READ_ONCE(*(ptr));                              \
 344         do {                                                    \
 345                 if (old__ & test__)                             \
 346                         break;                                  \
 347                 new__ = old__ & ~clear__;                       \
 348         } while (!try_cmpxchg(ptr, &old__, new__));             \
 349                                                                 \
 350         !(old__ & test__);                                      \
 351 })
 352 #endif
 353
 354 #endif /* __KERNEL__ */
 355 #endif