1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* bit search implementation
3 *
4 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
5 * Written by David Howells (dhowells@redhat.com)
6 *
7 * Copyright (C) 2008 IBM Corporation
8 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
9 * (Inspired by David Howell's find_next_bit implementation)
10 *
11 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
12 * size and improve performance, 2015.
13 */
14
15 #include <linux/bitops.h>
16 #include <linux/bitmap.h>
17 #include <linux/export.h>
18 #include <linux/math.h>
19 #include <linux/minmax.h>
20 #include <linux/swab.h>
21 #include <linux/random.h>
22
23 /*
24 * Common helper for find_bit() function family
25 * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
26 * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
27 * @size: The bitmap size in bits
28 */
29 #define FIND_FIRST_BIT(FETCH, MUNGE, size) \
30 ({ \
31 unsigned long idx, val, sz = (size); \
32 \
33 for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \
34 val = (FETCH); \
35 if (val) { \
36 sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \
37 break; \
38 } \
39 } \
40 \
41 sz; \
42 })
43
44 /*
45 * Common helper for find_next_bit() function family
46 * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
47 * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
48 * @size: The bitmap size in bits
49 * @start: The bitnumber to start searching at
50 */
51 #define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \
52 ({ \
53 unsigned long mask, idx, tmp, sz = (size), __start = (start); \
54 \
55 if (unlikely(__start >= sz)) \
56 goto out; \
57 \
58 mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \
59 idx = __start / BITS_PER_LONG; \
60 \
61 for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \
62 if ((idx + 1) * BITS_PER_LONG >= sz) \
63 goto out; \
64 idx++; \
65 } \
66 \
67 sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \
68 out: \
69 sz; \
70 })
71
72 #define FIND_NTH_BIT(FETCH, size, num) \
73 ({ \
74 unsigned long sz = (size), nr = (num), idx, w, tmp; \
75 \
76 for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
77 if (idx * BITS_PER_LONG + nr >= sz) \
78 goto out; \
79 \
80 tmp = (FETCH); \
81 w = hweight_long(tmp); \
82 if (w > nr) \
83 goto found; \
84 \
85 nr -= w; \
86 } \
87 \
88 if (sz % BITS_PER_LONG) \
89 tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
90 found: \
91 sz = idx * BITS_PER_LONG + fns(tmp, nr); \
92 out: \
93 sz; \
94 })
95
96 #ifndef find_first_bit
97 /*
98 * Find the first set bit in a memory region.
99 */
_find_first_bit(const unsigned long * addr,unsigned long size)100 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
101 {
102 return FIND_FIRST_BIT(addr[idx], /* nop */, size);
103 }
104 EXPORT_SYMBOL(_find_first_bit);
105 #endif
106
107 #ifndef find_first_and_bit
108 /*
109 * Find the first set bit in two memory regions.
110 */
_find_first_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size)111 unsigned long _find_first_and_bit(const unsigned long *addr1,
112 const unsigned long *addr2,
113 unsigned long size)
114 {
115 return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size);
116 }
117 EXPORT_SYMBOL(_find_first_and_bit);
118 #endif
119
120 /*
121 * Find the first bit set in 1st memory region and unset in 2nd.
122 */
_find_first_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size)123 unsigned long _find_first_andnot_bit(const unsigned long *addr1,
124 const unsigned long *addr2,
125 unsigned long size)
126 {
127 return FIND_FIRST_BIT(addr1[idx] & ~addr2[idx], /* nop */, size);
128 }
129 EXPORT_SYMBOL(_find_first_andnot_bit);
130
131 /*
132 * Find the first set bit in three memory regions.
133 */
_find_first_and_and_bit(const unsigned long * addr1,const unsigned long * addr2,const unsigned long * addr3,unsigned long size)134 unsigned long _find_first_and_and_bit(const unsigned long *addr1,
135 const unsigned long *addr2,
136 const unsigned long *addr3,
137 unsigned long size)
138 {
139 return FIND_FIRST_BIT(addr1[idx] & addr2[idx] & addr3[idx], /* nop */, size);
140 }
141 EXPORT_SYMBOL(_find_first_and_and_bit);
142
143 #ifndef find_first_zero_bit
144 /*
145 * Find the first cleared bit in a memory region.
146 */
_find_first_zero_bit(const unsigned long * addr,unsigned long size)147 unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
148 {
149 return FIND_FIRST_BIT(~addr[idx], /* nop */, size);
150 }
151 EXPORT_SYMBOL(_find_first_zero_bit);
152 #endif
153
154 #ifndef find_next_bit
_find_next_bit(const unsigned long * addr,unsigned long nbits,unsigned long start)155 unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start)
156 {
157 return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start);
158 }
159 EXPORT_SYMBOL(_find_next_bit);
160 #endif
161
__find_nth_bit(const unsigned long * addr,unsigned long size,unsigned long n)162 unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
163 {
164 return FIND_NTH_BIT(addr[idx], size, n);
165 }
166 EXPORT_SYMBOL(__find_nth_bit);
167
__find_nth_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long n)168 unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
169 unsigned long size, unsigned long n)
170 {
171 return FIND_NTH_BIT(addr1[idx] & addr2[idx], size, n);
172 }
173 EXPORT_SYMBOL(__find_nth_and_bit);
174
__find_nth_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long n)175 unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
176 unsigned long size, unsigned long n)
177 {
178 return FIND_NTH_BIT(addr1[idx] & ~addr2[idx], size, n);
179 }
180 EXPORT_SYMBOL(__find_nth_andnot_bit);
181
__find_nth_and_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,const unsigned long * addr3,unsigned long size,unsigned long n)182 unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1,
183 const unsigned long *addr2,
184 const unsigned long *addr3,
185 unsigned long size, unsigned long n)
186 {
187 return FIND_NTH_BIT(addr1[idx] & addr2[idx] & ~addr3[idx], size, n);
188 }
189 EXPORT_SYMBOL(__find_nth_and_andnot_bit);
190
191 #ifndef find_next_and_bit
_find_next_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start)192 unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
193 unsigned long nbits, unsigned long start)
194 {
195 return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start);
196 }
197 EXPORT_SYMBOL(_find_next_and_bit);
198 #endif
199
200 #ifndef find_next_andnot_bit
_find_next_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start)201 unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
202 unsigned long nbits, unsigned long start)
203 {
204 return FIND_NEXT_BIT(addr1[idx] & ~addr2[idx], /* nop */, nbits, start);
205 }
206 EXPORT_SYMBOL(_find_next_andnot_bit);
207 #endif
208
209 #ifndef find_next_or_bit
_find_next_or_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start)210 unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
211 unsigned long nbits, unsigned long start)
212 {
213 return FIND_NEXT_BIT(addr1[idx] | addr2[idx], /* nop */, nbits, start);
214 }
215 EXPORT_SYMBOL(_find_next_or_bit);
216 #endif
217
218 #ifndef find_next_zero_bit
_find_next_zero_bit(const unsigned long * addr,unsigned long nbits,unsigned long start)219 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
220 unsigned long start)
221 {
222 return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
223 }
224 EXPORT_SYMBOL(_find_next_zero_bit);
225 #endif
226
227 #ifndef find_last_bit
_find_last_bit(const unsigned long * addr,unsigned long size)228 unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
229 {
230 if (size) {
231 unsigned long val = BITMAP_LAST_WORD_MASK(size);
232 unsigned long idx = (size-1) / BITS_PER_LONG;
233
234 do {
235 val &= addr[idx];
236 if (val)
237 return idx * BITS_PER_LONG + __fls(val);
238
239 val = ~0ul;
240 } while (idx--);
241 }
242 return size;
243 }
244 EXPORT_SYMBOL(_find_last_bit);
245 #endif
246
find_next_clump8(unsigned long * clump,const unsigned long * addr,unsigned long size,unsigned long offset)247 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
248 unsigned long size, unsigned long offset)
249 {
250 offset = find_next_bit(addr, size, offset);
251 if (offset == size)
252 return size;
253
254 offset = round_down(offset, 8);
255 *clump = bitmap_get_value8(addr, offset);
256
257 return offset;
258 }
259 EXPORT_SYMBOL(find_next_clump8);
260
261 #ifdef __BIG_ENDIAN
262
263 #ifndef find_first_zero_bit_le
264 /*
265 * Find the first cleared bit in an LE memory region.
266 */
_find_first_zero_bit_le(const unsigned long * addr,unsigned long size)267 unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)
268 {
269 return FIND_FIRST_BIT(~addr[idx], swab, size);
270 }
271 EXPORT_SYMBOL(_find_first_zero_bit_le);
272
273 #endif
274
275 #ifndef find_next_zero_bit_le
_find_next_zero_bit_le(const unsigned long * addr,unsigned long size,unsigned long offset)276 unsigned long _find_next_zero_bit_le(const unsigned long *addr,
277 unsigned long size, unsigned long offset)
278 {
279 return FIND_NEXT_BIT(~addr[idx], swab, size, offset);
280 }
281 EXPORT_SYMBOL(_find_next_zero_bit_le);
282 #endif
283
284 #ifndef find_next_bit_le
_find_next_bit_le(const unsigned long * addr,unsigned long size,unsigned long offset)285 unsigned long _find_next_bit_le(const unsigned long *addr,
286 unsigned long size, unsigned long offset)
287 {
288 return FIND_NEXT_BIT(addr[idx], swab, size, offset);
289 }
290 EXPORT_SYMBOL(_find_next_bit_le);
291
292 #endif
293
294 #endif /* __BIG_ENDIAN */
295
296 /**
297 * find_random_bit - find a set bit at random position
298 * @addr: The address to base the search on
299 * @size: The bitmap size in bits
300 *
301 * Returns: a position of a random set bit; >= @size otherwise
302 */
find_random_bit(const unsigned long * addr,unsigned long size)303 unsigned long find_random_bit(const unsigned long *addr, unsigned long size)
304 {
305 int w = bitmap_weight(addr, size);
306
307 switch (w) {
308 case 0:
309 return size;
310 case 1:
311 /* Performance trick for single-bit bitmaps */
312 return find_first_bit(addr, size);
313 default:
314 return find_nth_bit(addr, size, get_random_u32_below(w));
315 }
316 }
317 EXPORT_SYMBOL(find_random_bit);
318