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); \
68out: \
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); \
90found: \
91 sz = idx * BITS_PER_LONG + fns(tmp, nr); \
92out: \
93 sz; \
94})
95
96#ifndef find_first_bit
97/*
98 * Find the first set bit in a memory region.
99 */
100unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
101{
102 return FIND_FIRST_BIT(addr[idx], /* nop */, size);
103}
104EXPORT_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 */
111unsigned 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}
117EXPORT_SYMBOL(_find_first_and_bit);
118#endif
119
120/*
121 * Find the first bit set in 1st memory region and unset in 2nd.
122 */
123unsigned 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}
129EXPORT_SYMBOL(_find_first_andnot_bit);
130
131/*
132 * Find the first set bit in three memory regions.
133 */
134unsigned 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}
141EXPORT_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 */
147unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
148{
149 return FIND_FIRST_BIT(~addr[idx], /* nop */, size);
150}
151EXPORT_SYMBOL(_find_first_zero_bit);
152#endif
153
154#ifndef find_next_bit
155unsigned 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}
159EXPORT_SYMBOL(_find_next_bit);
160#endif
161
162unsigned 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}
166EXPORT_SYMBOL(__find_nth_bit);
167
168unsigned 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}
173EXPORT_SYMBOL(__find_nth_and_bit);
174
175unsigned 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}
180EXPORT_SYMBOL(__find_nth_andnot_bit);
181
182unsigned 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}
189EXPORT_SYMBOL(__find_nth_and_andnot_bit);
190
191#ifndef find_next_and_bit
192unsigned 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}
197EXPORT_SYMBOL(_find_next_and_bit);
198#endif
199
200#ifndef find_next_andnot_bit
201unsigned 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}
206EXPORT_SYMBOL(_find_next_andnot_bit);
207#endif
208
209#ifndef find_next_or_bit
210unsigned 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}
215EXPORT_SYMBOL(_find_next_or_bit);
216#endif
217
218#ifndef find_next_zero_bit
219unsigned 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}
224EXPORT_SYMBOL(_find_next_zero_bit);
225#endif
226
227#ifndef find_last_bit
228unsigned 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(word: val);
238
239 val = ~0ul;
240 } while (idx--);
241 }
242 return size;
243}
244EXPORT_SYMBOL(_find_last_bit);
245#endif
246
247unsigned 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}
259EXPORT_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 */
267unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)
268{
269 return FIND_FIRST_BIT(~addr[idx], swab, size);
270}
271EXPORT_SYMBOL(_find_first_zero_bit_le);
272
273#endif
274
275#ifndef find_next_zero_bit_le
276unsigned 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}
281EXPORT_SYMBOL(_find_next_zero_bit_le);
282#endif
283
284#ifndef find_next_bit_le
285unsigned 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}
290EXPORT_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 */
303unsigned long find_random_bit(const unsigned long *addr, unsigned long size)
304{
305 int w = bitmap_weight(src: addr, nbits: 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, n: get_random_u32_below(ceil: w));
315 }
316}
317EXPORT_SYMBOL(find_random_bit);
318