Line data Source code
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 :
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 :
43 : /*
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
49 : */
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 : })
70 :
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: \
90 : sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
91 : out: \
92 : sz; \
93 : })
94 :
95 : #ifndef find_first_bit
96 : /*
97 : * Find the first set bit in a memory region.
98 : */
99 12047 : unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
100 : {
101 24094 : return FIND_FIRST_BIT(addr[idx], /* nop */, size);
102 : }
103 : EXPORT_SYMBOL(_find_first_bit);
104 : #endif
105 :
106 : #ifndef find_first_and_bit
107 : /*
108 : * Find the first set bit in two memory regions.
109 : */
110 0 : unsigned long _find_first_and_bit(const unsigned long *addr1,
111 : const unsigned long *addr2,
112 : unsigned long size)
113 : {
114 0 : return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size);
115 : }
116 : EXPORT_SYMBOL(_find_first_and_bit);
117 : #endif
118 :
119 : #ifndef find_first_zero_bit
120 : /*
121 : * Find the first cleared bit in a memory region.
122 : */
123 119 : unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
124 : {
125 238 : return FIND_FIRST_BIT(~addr[idx], /* nop */, size);
126 : }
127 : EXPORT_SYMBOL(_find_first_zero_bit);
128 : #endif
129 :
130 : #ifndef find_next_bit
131 17486 : unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start)
132 : {
133 33454 : return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start);
134 : }
135 : EXPORT_SYMBOL(_find_next_bit);
136 : #endif
137 :
138 0 : unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
139 : {
140 0 : return FIND_NTH_BIT(addr[idx], size, n);
141 : }
142 : EXPORT_SYMBOL(__find_nth_bit);
143 :
144 0 : unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
145 : unsigned long size, unsigned long n)
146 : {
147 0 : return FIND_NTH_BIT(addr1[idx] & addr2[idx], size, n);
148 : }
149 : EXPORT_SYMBOL(__find_nth_and_bit);
150 :
151 0 : unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
152 : unsigned long size, unsigned long n)
153 : {
154 0 : return FIND_NTH_BIT(addr1[idx] & ~addr2[idx], size, n);
155 : }
156 : EXPORT_SYMBOL(__find_nth_andnot_bit);
157 :
158 0 : unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1,
159 : const unsigned long *addr2,
160 : const unsigned long *addr3,
161 : unsigned long size, unsigned long n)
162 : {
163 0 : return FIND_NTH_BIT(addr1[idx] & addr2[idx] & ~addr3[idx], size, n);
164 : }
165 : EXPORT_SYMBOL(__find_nth_and_andnot_bit);
166 :
167 : #ifndef find_next_and_bit
168 0 : unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
169 : unsigned long nbits, unsigned long start)
170 : {
171 0 : return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start);
172 : }
173 : EXPORT_SYMBOL(_find_next_and_bit);
174 : #endif
175 :
176 : #ifndef find_next_andnot_bit
177 0 : unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
178 : unsigned long nbits, unsigned long start)
179 : {
180 0 : return FIND_NEXT_BIT(addr1[idx] & ~addr2[idx], /* nop */, nbits, start);
181 : }
182 : EXPORT_SYMBOL(_find_next_andnot_bit);
183 : #endif
184 :
185 : #ifndef find_next_or_bit
186 0 : unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
187 : unsigned long nbits, unsigned long start)
188 : {
189 0 : return FIND_NEXT_BIT(addr1[idx] | addr2[idx], /* nop */, nbits, start);
190 : }
191 : EXPORT_SYMBOL(_find_next_or_bit);
192 : #endif
193 :
194 : #ifndef find_next_zero_bit
195 1481 : unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
196 : unsigned long start)
197 : {
198 2510 : return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
199 : }
200 : EXPORT_SYMBOL(_find_next_zero_bit);
201 : #endif
202 :
203 : #ifndef find_last_bit
204 12092 : unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
205 : {
206 12092 : if (size) {
207 12092 : unsigned long val = BITMAP_LAST_WORD_MASK(size);
208 12092 : unsigned long idx = (size-1) / BITS_PER_LONG;
209 :
210 : do {
211 774255 : val &= addr[idx];
212 774255 : if (val)
213 24184 : return idx * BITS_PER_LONG + __fls(val);
214 :
215 762163 : val = ~0ul;
216 762163 : } while (idx--);
217 : }
218 : return size;
219 : }
220 : EXPORT_SYMBOL(_find_last_bit);
221 : #endif
222 :
223 0 : unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
224 : unsigned long size, unsigned long offset)
225 : {
226 0 : offset = find_next_bit(addr, size, offset);
227 0 : if (offset == size)
228 : return size;
229 :
230 0 : offset = round_down(offset, 8);
231 0 : *clump = bitmap_get_value8(addr, offset);
232 :
233 0 : return offset;
234 : }
235 : EXPORT_SYMBOL(find_next_clump8);
236 :
237 : #ifdef __BIG_ENDIAN
238 :
239 : #ifndef find_first_zero_bit_le
240 : /*
241 : * Find the first cleared bit in an LE memory region.
242 : */
243 : unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)
244 : {
245 : return FIND_FIRST_BIT(~addr[idx], swab, size);
246 : }
247 : EXPORT_SYMBOL(_find_first_zero_bit_le);
248 :
249 : #endif
250 :
251 : #ifndef find_next_zero_bit_le
252 : unsigned long _find_next_zero_bit_le(const unsigned long *addr,
253 : unsigned long size, unsigned long offset)
254 : {
255 : return FIND_NEXT_BIT(~addr[idx], swab, size, offset);
256 : }
257 : EXPORT_SYMBOL(_find_next_zero_bit_le);
258 : #endif
259 :
260 : #ifndef find_next_bit_le
261 : unsigned long _find_next_bit_le(const unsigned long *addr,
262 : unsigned long size, unsigned long offset)
263 : {
264 : return FIND_NEXT_BIT(addr[idx], swab, size, offset);
265 : }
266 : EXPORT_SYMBOL(_find_next_bit_le);
267 :
268 : #endif
269 :
270 : #endif /* __BIG_ENDIAN */
|
