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 17353 : unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start)
132 : {
133 33289 : 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_zero_bit
186 1411 : unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
187 : unsigned long start)
188 : {
189 2396 : return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
190 : }
191 : EXPORT_SYMBOL(_find_next_zero_bit);
192 : #endif
193 :
194 : #ifndef find_last_bit
195 12082 : unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
196 : {
197 12082 : if (size) {
198 12082 : unsigned long val = BITMAP_LAST_WORD_MASK(size);
199 12082 : unsigned long idx = (size-1) / BITS_PER_LONG;
200 :
201 : do {
202 772485 : val &= addr[idx];
203 772485 : if (val)
204 24164 : return idx * BITS_PER_LONG + __fls(val);
205 :
206 760403 : val = ~0ul;
207 760403 : } while (idx--);
208 : }
209 : return size;
210 : }
211 : EXPORT_SYMBOL(_find_last_bit);
212 : #endif
213 :
214 0 : unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
215 : unsigned long size, unsigned long offset)
216 : {
217 0 : offset = find_next_bit(addr, size, offset);
218 0 : if (offset == size)
219 : return size;
220 :
221 0 : offset = round_down(offset, 8);
222 0 : *clump = bitmap_get_value8(addr, offset);
223 :
224 0 : return offset;
225 : }
226 : EXPORT_SYMBOL(find_next_clump8);
227 :
228 : #ifdef __BIG_ENDIAN
229 :
230 : #ifndef find_first_zero_bit_le
231 : /*
232 : * Find the first cleared bit in an LE memory region.
233 : */
234 : unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)
235 : {
236 : return FIND_FIRST_BIT(~addr[idx], swab, size);
237 : }
238 : EXPORT_SYMBOL(_find_first_zero_bit_le);
239 :
240 : #endif
241 :
242 : #ifndef find_next_zero_bit_le
243 : unsigned long _find_next_zero_bit_le(const unsigned long *addr,
244 : unsigned long size, unsigned long offset)
245 : {
246 : return FIND_NEXT_BIT(~addr[idx], swab, size, offset);
247 : }
248 : EXPORT_SYMBOL(_find_next_zero_bit_le);
249 : #endif
250 :
251 : #ifndef find_next_bit_le
252 : unsigned long _find_next_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_bit_le);
258 :
259 : #endif
260 :
261 : #endif /* __BIG_ENDIAN */
|
