Branch data Line data Source code
1 : : /* SPDX-License-Identifier: GPL-2.0 */
2 : : #ifndef _LINUX_BITOPS_H
3 : : #define _LINUX_BITOPS_H
4 : : #include <asm/types.h>
5 : : #include <linux/bits.h>
6 : :
7 : : /* Set bits in the first 'n' bytes when loaded from memory */
8 : : #ifdef __LITTLE_ENDIAN
9 : : # define aligned_byte_mask(n) ((1UL << 8*(n))-1)
10 : : #else
11 : : # define aligned_byte_mask(n) (~0xffUL << (BITS_PER_LONG - 8 - 8*(n)))
12 : : #endif
13 : :
14 : : #define BITS_PER_TYPE(type) (sizeof(type) * BITS_PER_BYTE)
15 : : #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
16 : : #define BITS_TO_U64(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(u64))
17 : : #define BITS_TO_U32(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(u32))
18 : : #define BITS_TO_BYTES(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(char))
19 : :
20 : : extern unsigned int __sw_hweight8(unsigned int w);
21 : : extern unsigned int __sw_hweight16(unsigned int w);
22 : : extern unsigned int __sw_hweight32(unsigned int w);
23 : : extern unsigned long __sw_hweight64(__u64 w);
24 : :
25 : : /*
26 : : * Include this here because some architectures need generic_ffs/fls in
27 : : * scope
28 : : */
29 : : #include <asm/bitops.h>
30 : :
31 : : #define for_each_set_bit(bit, addr, size) \
32 : : for ((bit) = find_first_bit((addr), (size)); \
33 : : (bit) < (size); \
34 : : (bit) = find_next_bit((addr), (size), (bit) + 1))
35 : :
36 : : /* same as for_each_set_bit() but use bit as value to start with */
37 : : #define for_each_set_bit_from(bit, addr, size) \
38 : : for ((bit) = find_next_bit((addr), (size), (bit)); \
39 : : (bit) < (size); \
40 : : (bit) = find_next_bit((addr), (size), (bit) + 1))
41 : :
42 : : #define for_each_clear_bit(bit, addr, size) \
43 : : for ((bit) = find_first_zero_bit((addr), (size)); \
44 : : (bit) < (size); \
45 : : (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
46 : :
47 : : /* same as for_each_clear_bit() but use bit as value to start with */
48 : : #define for_each_clear_bit_from(bit, addr, size) \
49 : : for ((bit) = find_next_zero_bit((addr), (size), (bit)); \
50 : : (bit) < (size); \
51 : : (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
52 : :
53 : : /**
54 : : * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
55 : : * @start: bit offset to start search and to store the current iteration offset
56 : : * @clump: location to store copy of current 8-bit clump
57 : : * @bits: bitmap address to base the search on
58 : : * @size: bitmap size in number of bits
59 : : */
60 : : #define for_each_set_clump8(start, clump, bits, size) \
61 : : for ((start) = find_first_clump8(&(clump), (bits), (size)); \
62 : : (start) < (size); \
63 : : (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))
64 : :
65 : 0 : static inline int get_bitmask_order(unsigned int count)
66 : : {
67 : 0 : int order;
68 : :
69 : 0 : order = fls(count);
70 : 0 : return order; /* We could be slightly more clever with -1 here... */
71 : : }
72 : :
73 : 2037 : static __always_inline unsigned long hweight_long(unsigned long w)
74 : : {
75 [ - + - + : 2037 : return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
- + # # ]
76 : : }
77 : :
78 : : /**
79 : : * rol64 - rotate a 64-bit value left
80 : : * @word: value to rotate
81 : : * @shift: bits to roll
82 : : */
83 : 1608124 : static inline __u64 rol64(__u64 word, unsigned int shift)
84 : : {
85 : 1608124 : return (word << (shift & 63)) | (word >> ((-shift) & 63));
86 : : }
87 : :
88 : : /**
89 : : * ror64 - rotate a 64-bit value right
90 : : * @word: value to rotate
91 : : * @shift: bits to roll
92 : : */
93 : : static inline __u64 ror64(__u64 word, unsigned int shift)
94 : : {
95 : : return (word >> (shift & 63)) | (word << ((-shift) & 63));
96 : : }
97 : :
98 : : /**
99 : : * rol32 - rotate a 32-bit value left
100 : : * @word: value to rotate
101 : : * @shift: bits to roll
102 : : */
103 : 85109884 : static inline __u32 rol32(__u32 word, unsigned int shift)
104 : : {
105 [ + + ]: 85054845 : return (word << (shift & 31)) | (word >> ((-shift) & 31));
106 : : }
107 : :
108 : : /**
109 : : * ror32 - rotate a 32-bit value right
110 : : * @word: value to rotate
111 : : * @shift: bits to roll
112 : : */
113 : 8379 : static inline __u32 ror32(__u32 word, unsigned int shift)
114 : : {
115 [ # # # # ]: 1323 : return (word >> (shift & 31)) | (word << ((-shift) & 31));
116 : : }
117 : :
118 : : /**
119 : : * rol16 - rotate a 16-bit value left
120 : : * @word: value to rotate
121 : : * @shift: bits to roll
122 : : */
123 : : static inline __u16 rol16(__u16 word, unsigned int shift)
124 : : {
125 : : return (word << (shift & 15)) | (word >> ((-shift) & 15));
126 : : }
127 : :
128 : : /**
129 : : * ror16 - rotate a 16-bit value right
130 : : * @word: value to rotate
131 : : * @shift: bits to roll
132 : : */
133 : 0 : static inline __u16 ror16(__u16 word, unsigned int shift)
134 : : {
135 : 0 : return (word >> (shift & 15)) | (word << ((-shift) & 15));
136 : : }
137 : :
138 : : /**
139 : : * rol8 - rotate an 8-bit value left
140 : : * @word: value to rotate
141 : : * @shift: bits to roll
142 : : */
143 : : static inline __u8 rol8(__u8 word, unsigned int shift)
144 : : {
145 : : return (word << (shift & 7)) | (word >> ((-shift) & 7));
146 : : }
147 : :
148 : : /**
149 : : * ror8 - rotate an 8-bit value right
150 : : * @word: value to rotate
151 : : * @shift: bits to roll
152 : : */
153 : : static inline __u8 ror8(__u8 word, unsigned int shift)
154 : : {
155 : : return (word >> (shift & 7)) | (word << ((-shift) & 7));
156 : : }
157 : :
158 : : /**
159 : : * sign_extend32 - sign extend a 32-bit value using specified bit as sign-bit
160 : : * @value: value to sign extend
161 : : * @index: 0 based bit index (0<=index<32) to sign bit
162 : : *
163 : : * This is safe to use for 16- and 8-bit types as well.
164 : : */
165 : 0 : static inline __s32 sign_extend32(__u32 value, int index)
166 : : {
167 : 0 : __u8 shift = 31 - index;
168 [ # # # # ]: 0 : return (__s32)(value << shift) >> shift;
169 : : }
170 : :
171 : : /**
172 : : * sign_extend64 - sign extend a 64-bit value using specified bit as sign-bit
173 : : * @value: value to sign extend
174 : : * @index: 0 based bit index (0<=index<64) to sign bit
175 : : */
176 : 0 : static inline __s64 sign_extend64(__u64 value, int index)
177 : : {
178 : 0 : __u8 shift = 63 - index;
179 [ # # # # : 0 : return (__s64)(value << shift) >> shift;
# # # # ]
180 : : }
181 : :
182 : 7392 : static inline unsigned fls_long(unsigned long l)
183 : : {
184 : 7392 : if (sizeof(l) == 4)
185 : : return fls(l);
186 [ + + # # : 7392 : return fls64(l);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
187 : : }
188 : :
189 : 4514 : static inline int get_count_order(unsigned int count)
190 : : {
191 : 4514 : int order;
192 : :
193 [ + + - - : 4514 : order = fls(count) - 1;
- - - - -
- ]
194 [ + + - - : 4514 : if (count & (count - 1))
- - - - -
- ]
195 : 3648 : order++;
196 [ # # # # ]: 4514 : return order;
197 : : }
198 : :
199 : : /**
200 : : * get_count_order_long - get order after rounding @l up to power of 2
201 : : * @l: parameter
202 : : *
203 : : * it is same as get_count_order() but with long type parameter
204 : : */
205 : 168 : static inline int get_count_order_long(unsigned long l)
206 : : {
207 [ + - ]: 168 : if (l == 0UL)
208 : : return -1;
209 [ - + ]: 168 : else if (l & (l - 1UL))
210 : 0 : return (int)fls_long(l);
211 : : else
212 : 168 : return (int)fls_long(l) - 1;
213 : : }
214 : :
215 : : /**
216 : : * __ffs64 - find first set bit in a 64 bit word
217 : : * @word: The 64 bit word
218 : : *
219 : : * On 64 bit arches this is a synomyn for __ffs
220 : : * The result is not defined if no bits are set, so check that @word
221 : : * is non-zero before calling this.
222 : : */
223 : 21 : static inline unsigned long __ffs64(u64 word)
224 : : {
225 : : #if BITS_PER_LONG == 32
226 : : if (((u32)word) == 0UL)
227 : : return __ffs((u32)(word >> 32)) + 32;
228 : : #elif BITS_PER_LONG != 64
229 : : #error BITS_PER_LONG not 32 or 64
230 : : #endif
231 [ # # ]: 21 : return __ffs((unsigned long)word);
232 : : }
233 : :
234 : : /**
235 : : * assign_bit - Assign value to a bit in memory
236 : : * @nr: the bit to set
237 : : * @addr: the address to start counting from
238 : : * @value: the value to assign
239 : : */
240 : 147 : static __always_inline void assign_bit(long nr, volatile unsigned long *addr,
241 : : bool value)
242 : : {
243 : 147 : if (value)
244 : 147 : set_bit(nr, addr);
245 : : else
246 : 0 : clear_bit(nr, addr);
247 : : }
248 : :
249 : : static __always_inline void __assign_bit(long nr, volatile unsigned long *addr,
250 : : bool value)
251 : : {
252 : : if (value)
253 : : __set_bit(nr, addr);
254 : : else
255 : : __clear_bit(nr, addr);
256 : : }
257 : :
258 : : #ifdef __KERNEL__
259 : :
260 : : #ifndef set_mask_bits
261 : : #define set_mask_bits(ptr, mask, bits) \
262 : : ({ \
263 : : const typeof(*(ptr)) mask__ = (mask), bits__ = (bits); \
264 : : typeof(*(ptr)) old__, new__; \
265 : : \
266 : : do { \
267 : : old__ = READ_ONCE(*(ptr)); \
268 : : new__ = (old__ & ~mask__) | bits__; \
269 : : } while (cmpxchg(ptr, old__, new__) != old__); \
270 : : \
271 : : old__; \
272 : : })
273 : : #endif
274 : :
275 : : #ifndef bit_clear_unless
276 : : #define bit_clear_unless(ptr, clear, test) \
277 : : ({ \
278 : : const typeof(*(ptr)) clear__ = (clear), test__ = (test);\
279 : : typeof(*(ptr)) old__, new__; \
280 : : \
281 : : do { \
282 : : old__ = READ_ONCE(*(ptr)); \
283 : : new__ = old__ & ~clear__; \
284 : : } while (!(old__ & test__) && \
285 : : cmpxchg(ptr, old__, new__) != old__); \
286 : : \
287 : : !(old__ & test__); \
288 : : })
289 : : #endif
290 : :
291 : : #ifndef find_last_bit
292 : : /**
293 : : * find_last_bit - find the last set bit in a memory region
294 : : * @addr: The address to start the search at
295 : : * @size: The number of bits to search
296 : : *
297 : : * Returns the bit number of the last set bit, or size.
298 : : */
299 : : extern unsigned long find_last_bit(const unsigned long *addr,
300 : : unsigned long size);
301 : : #endif
302 : :
303 : : #endif /* __KERNEL__ */
304 : : #endif
|
