projects/linux·blob master · refs

310 lines · 8.2 KiB

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 ([email protected])
6 *
7 * Copyright (C) 2008 IBM Corporation
8 * 'find_last_bit' is written by Rusty Russell <[email protected]>
9 * (Inspired by David Howell's find_next_bit implementation)
10 *
11 * Rewritten by Yury Norov <[email protected]> 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 = 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); \
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_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}
182EXPORT_SYMBOL(__find_nth_and_andnot_bit);
183
184#ifndef find_next_and_bit
185unsigned 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}
190EXPORT_SYMBOL(_find_next_and_bit);
191#endif
192
193#ifndef find_next_andnot_bit
194unsigned 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}
199EXPORT_SYMBOL(_find_next_andnot_bit);
200#endif
201
202#ifndef find_next_or_bit
203unsigned 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}
208EXPORT_SYMBOL(_find_next_or_bit);
209#endif
210
211#ifndef find_next_zero_bit
212unsigned 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}
217EXPORT_SYMBOL(_find_next_zero_bit);
218#endif
219
220#ifndef find_last_bit
221unsigned 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}
237EXPORT_SYMBOL(_find_last_bit);
238#endif
239
240unsigned 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}
252EXPORT_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 */
260unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)
261{
262 return FIND_FIRST_BIT(~addr[idx], swab, size);
263}
264EXPORT_SYMBOL(_find_first_zero_bit_le);
265
266#endif
267
268#ifndef find_next_zero_bit_le
269unsigned 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}
274EXPORT_SYMBOL(_find_next_zero_bit_le);
275#endif
276
277#ifndef find_next_bit_le
278unsigned 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}
283EXPORT_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 */
296unsigned 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}
310EXPORT_SYMBOL(find_random_bit);