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