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