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 = 0; \
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_and_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,const unsigned long * addr3,unsigned long size,unsigned long n)175 unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1,
176 const unsigned long *addr2,
177 const unsigned long *addr3,
178 unsigned long size, unsigned long n)
179 {
180 return FIND_NTH_BIT(addr1[idx] & addr2[idx] & ~addr3[idx], size, n);
181 }
182 EXPORT_SYMBOL(__find_nth_and_andnot_bit);
183
184 #ifndef find_next_and_bit
_find_next_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start)185 unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
186 unsigned long nbits, unsigned long start)
187 {
188 return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start);
189 }
190 EXPORT_SYMBOL(_find_next_and_bit);
191 #endif
192
193 #ifndef find_next_andnot_bit
_find_next_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start)194 unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
195 unsigned long nbits, unsigned long start)
196 {
197 return FIND_NEXT_BIT(addr1[idx] & ~addr2[idx], /* nop */, nbits, start);
198 }
199 EXPORT_SYMBOL(_find_next_andnot_bit);
200 #endif
201
202 #ifndef find_next_or_bit
_find_next_or_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start)203 unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
204 unsigned long nbits, unsigned long start)
205 {
206 return FIND_NEXT_BIT(addr1[idx] | addr2[idx], /* nop */, nbits, start);
207 }
208 EXPORT_SYMBOL(_find_next_or_bit);
209 #endif
210
211 #ifndef find_next_zero_bit
_find_next_zero_bit(const unsigned long * addr,unsigned long nbits,unsigned long start)212 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
213 unsigned long start)
214 {
215 return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
216 }
217 EXPORT_SYMBOL(_find_next_zero_bit);
218 #endif
219
220 #ifndef find_last_bit
_find_last_bit(const unsigned long * addr,unsigned long size)221 unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
222 {
223 if (size) {
224 unsigned long val = BITMAP_LAST_WORD_MASK(size);
225 unsigned long idx = (size-1) / BITS_PER_LONG;
226
227 do {
228 val &= addr[idx];
229 if (val)
230 return idx * BITS_PER_LONG + __fls(val);
231
232 val = ~0ul;
233 } while (idx--);
234 }
235 return size;
236 }
237 EXPORT_SYMBOL(_find_last_bit);
238 #endif
239
find_next_clump8(unsigned long * clump,const unsigned long * addr,unsigned long size,unsigned long offset)240 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
241 unsigned long size, unsigned long offset)
242 {
243 offset = find_next_bit(addr, size, offset);
244 if (offset == size)
245 return size;
246
247 offset = round_down(offset, 8);
248 *clump = bitmap_get_value8(addr, offset);
249
250 return offset;
251 }
252 EXPORT_SYMBOL(find_next_clump8);
253
254 #ifdef __BIG_ENDIAN
255
256 #ifndef find_first_zero_bit_le
257 /*
258 * Find the first cleared bit in an LE memory region.
259 */
_find_first_zero_bit_le(const unsigned long * addr,unsigned long size)260 unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)
261 {
262 return FIND_FIRST_BIT(~addr[idx], swab, size);
263 }
264 EXPORT_SYMBOL(_find_first_zero_bit_le);
265
266 #endif
267
268 #ifndef find_next_zero_bit_le
_find_next_zero_bit_le(const unsigned long * addr,unsigned long size,unsigned long offset)269 unsigned long _find_next_zero_bit_le(const unsigned long *addr,
270 unsigned long size, unsigned long offset)
271 {
272 return FIND_NEXT_BIT(~addr[idx], swab, size, offset);
273 }
274 EXPORT_SYMBOL(_find_next_zero_bit_le);
275 #endif
276
277 #ifndef find_next_bit_le
_find_next_bit_le(const unsigned long * addr,unsigned long size,unsigned long offset)278 unsigned long _find_next_bit_le(const unsigned long *addr,
279 unsigned long size, unsigned long offset)
280 {
281 return FIND_NEXT_BIT(addr[idx], swab, size, offset);
282 }
283 EXPORT_SYMBOL(_find_next_bit_le);
284
285 #endif
286
287 #endif /* __BIG_ENDIAN */
288
289 /**
290 * find_random_bit - find a set bit at random position
291 * @addr: The address to base the search on
292 * @size: The bitmap size in bits
293 *
294 * Returns: a position of a random set bit; >= @size otherwise
295 */
find_random_bit(const unsigned long * addr,unsigned long size)296 unsigned long find_random_bit(const unsigned long *addr, unsigned long size)
297 {
298 int w = bitmap_weight(addr, size);
299
300 switch (w) {
301 case 0:
302 return size;
303 case 1:
304 /* Performance trick for single-bit bitmaps */
305 return find_first_bit(addr, size);
306 default:
307 return find_nth_bit(addr, size, get_random_u32_below(w));
308 }
309 }
310 EXPORT_SYMBOL(find_random_bit);
311