12874c5fdSThomas Gleixner // SPDX-License-Identifier: GPL-2.0-or-later
2840620a1SYury Norov /* bit search implementation
3840620a1SYury Norov *
4840620a1SYury Norov * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
5840620a1SYury Norov * Written by David Howells (dhowells@redhat.com)
6840620a1SYury Norov *
7840620a1SYury Norov * Copyright (C) 2008 IBM Corporation
8840620a1SYury Norov * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
9840620a1SYury Norov * (Inspired by David Howell's find_next_bit implementation)
10840620a1SYury Norov *
11840620a1SYury Norov * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
12840620a1SYury Norov * size and improve performance, 2015.
13840620a1SYury Norov */
14840620a1SYury Norov
15840620a1SYury Norov #include <linux/bitops.h>
16840620a1SYury Norov #include <linux/bitmap.h>
17840620a1SYury Norov #include <linux/export.h>
18aa6159abSAndy Shevchenko #include <linux/math.h>
19b296a6d5SAndy Shevchenko #include <linux/minmax.h>
20aa6159abSAndy Shevchenko #include <linux/swab.h>
21840620a1SYury Norov
2258414bbbSYury Norov /*
2358414bbbSYury Norov * Common helper for find_bit() function family
2458414bbbSYury Norov * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
2558414bbbSYury Norov * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
2658414bbbSYury Norov * @size: The bitmap size in bits
2758414bbbSYury Norov */
2858414bbbSYury Norov #define FIND_FIRST_BIT(FETCH, MUNGE, size) \
2958414bbbSYury Norov ({ \
3058414bbbSYury Norov unsigned long idx, val, sz = (size); \
3158414bbbSYury Norov \
3258414bbbSYury Norov for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \
3358414bbbSYury Norov val = (FETCH); \
3458414bbbSYury Norov if (val) { \
3558414bbbSYury Norov sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \
3658414bbbSYury Norov break; \
3758414bbbSYury Norov } \
3858414bbbSYury Norov } \
3958414bbbSYury Norov \
4058414bbbSYury Norov sz; \
4158414bbbSYury Norov })
4258414bbbSYury Norov
43840620a1SYury Norov /*
44e79864f3SYury Norov * Common helper for find_next_bit() function family
45e79864f3SYury Norov * @FETCH: The expression that fetches and pre-processes each word of bitmap(s)
46e79864f3SYury Norov * @MUNGE: The expression that post-processes a word containing found bit (may be empty)
47e79864f3SYury Norov * @size: The bitmap size in bits
48e79864f3SYury Norov * @start: The bitnumber to start searching at
49840620a1SYury Norov */
50e79864f3SYury Norov #define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \
51e79864f3SYury Norov ({ \
52e79864f3SYury Norov unsigned long mask, idx, tmp, sz = (size), __start = (start); \
53e79864f3SYury Norov \
54e79864f3SYury Norov if (unlikely(__start >= sz)) \
55e79864f3SYury Norov goto out; \
56e79864f3SYury Norov \
57e79864f3SYury Norov mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \
58e79864f3SYury Norov idx = __start / BITS_PER_LONG; \
59e79864f3SYury Norov \
60e79864f3SYury Norov for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \
61e79864f3SYury Norov if ((idx + 1) * BITS_PER_LONG >= sz) \
62e79864f3SYury Norov goto out; \
63e79864f3SYury Norov idx++; \
64e79864f3SYury Norov } \
65e79864f3SYury Norov \
66e79864f3SYury Norov sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \
67e79864f3SYury Norov out: \
68e79864f3SYury Norov sz; \
69e79864f3SYury Norov })
700ade34c3SClement Courbet
713cea8d47SYury Norov #define FIND_NTH_BIT(FETCH, size, num) \
723cea8d47SYury Norov ({ \
733cea8d47SYury Norov unsigned long sz = (size), nr = (num), idx, w, tmp; \
743cea8d47SYury Norov \
753cea8d47SYury Norov for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
763cea8d47SYury Norov if (idx * BITS_PER_LONG + nr >= sz) \
773cea8d47SYury Norov goto out; \
783cea8d47SYury Norov \
793cea8d47SYury Norov tmp = (FETCH); \
803cea8d47SYury Norov w = hweight_long(tmp); \
813cea8d47SYury Norov if (w > nr) \
823cea8d47SYury Norov goto found; \
833cea8d47SYury Norov \
843cea8d47SYury Norov nr -= w; \
853cea8d47SYury Norov } \
863cea8d47SYury Norov \
873cea8d47SYury Norov if (sz % BITS_PER_LONG) \
883cea8d47SYury Norov tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
893cea8d47SYury Norov found: \
903cea8d47SYury Norov sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
913cea8d47SYury Norov out: \
923cea8d47SYury Norov sz; \
933cea8d47SYury Norov })
943cea8d47SYury Norov
95840620a1SYury Norov #ifndef find_first_bit
96840620a1SYury Norov /*
97840620a1SYury Norov * Find the first set bit in a memory region.
98840620a1SYury Norov */
_find_first_bit(const unsigned long * addr,unsigned long size)992cc7b6a4SYury Norov unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
100840620a1SYury Norov {
10158414bbbSYury Norov return FIND_FIRST_BIT(addr[idx], /* nop */, size);
102840620a1SYury Norov }
1032cc7b6a4SYury Norov EXPORT_SYMBOL(_find_first_bit);
104840620a1SYury Norov #endif
105840620a1SYury Norov
106f68edc92SYury Norov #ifndef find_first_and_bit
107f68edc92SYury Norov /*
108f68edc92SYury Norov * Find the first set bit in two memory regions.
109f68edc92SYury Norov */
_find_first_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size)110f68edc92SYury Norov unsigned long _find_first_and_bit(const unsigned long *addr1,
111f68edc92SYury Norov const unsigned long *addr2,
112f68edc92SYury Norov unsigned long size)
113f68edc92SYury Norov {
11458414bbbSYury Norov return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size);
115f68edc92SYury Norov }
116f68edc92SYury Norov EXPORT_SYMBOL(_find_first_and_bit);
117f68edc92SYury Norov #endif
118f68edc92SYury Norov
119840620a1SYury Norov #ifndef find_first_zero_bit
120840620a1SYury Norov /*
121840620a1SYury Norov * Find the first cleared bit in a memory region.
122840620a1SYury Norov */
_find_first_zero_bit(const unsigned long * addr,unsigned long size)1232cc7b6a4SYury Norov unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
124840620a1SYury Norov {
12558414bbbSYury Norov return FIND_FIRST_BIT(~addr[idx], /* nop */, size);
126840620a1SYury Norov }
1272cc7b6a4SYury Norov EXPORT_SYMBOL(_find_first_zero_bit);
128840620a1SYury Norov #endif
129840620a1SYury Norov
130e79864f3SYury Norov #ifndef find_next_bit
_find_next_bit(const unsigned long * addr,unsigned long nbits,unsigned long start)131e79864f3SYury Norov unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start)
132e79864f3SYury Norov {
133e79864f3SYury Norov return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start);
134e79864f3SYury Norov }
135e79864f3SYury Norov EXPORT_SYMBOL(_find_next_bit);
136e79864f3SYury Norov #endif
137e79864f3SYury Norov
__find_nth_bit(const unsigned long * addr,unsigned long size,unsigned long n)1383cea8d47SYury Norov unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
1393cea8d47SYury Norov {
1403cea8d47SYury Norov return FIND_NTH_BIT(addr[idx], size, n);
1413cea8d47SYury Norov }
1423cea8d47SYury Norov EXPORT_SYMBOL(__find_nth_bit);
1433cea8d47SYury Norov
__find_nth_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long n)1443cea8d47SYury Norov unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
1453cea8d47SYury Norov unsigned long size, unsigned long n)
1463cea8d47SYury Norov {
1473cea8d47SYury Norov return FIND_NTH_BIT(addr1[idx] & addr2[idx], size, n);
1483cea8d47SYury Norov }
1493cea8d47SYury Norov EXPORT_SYMBOL(__find_nth_and_bit);
1503cea8d47SYury Norov
__find_nth_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long n)1513cea8d47SYury Norov unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
1523cea8d47SYury Norov unsigned long size, unsigned long n)
1533cea8d47SYury Norov {
1543cea8d47SYury Norov return FIND_NTH_BIT(addr1[idx] & ~addr2[idx], size, n);
1553cea8d47SYury Norov }
1563cea8d47SYury Norov EXPORT_SYMBOL(__find_nth_andnot_bit);
1573cea8d47SYury Norov
__find_nth_and_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,const unsigned long * addr3,unsigned long size,unsigned long n)15843245117SYury Norov unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1,
15943245117SYury Norov const unsigned long *addr2,
16043245117SYury Norov const unsigned long *addr3,
16143245117SYury Norov unsigned long size, unsigned long n)
16243245117SYury Norov {
16343245117SYury Norov return FIND_NTH_BIT(addr1[idx] & addr2[idx] & ~addr3[idx], size, n);
16443245117SYury Norov }
16543245117SYury Norov EXPORT_SYMBOL(__find_nth_and_andnot_bit);
16643245117SYury Norov
167e79864f3SYury Norov #ifndef find_next_and_bit
_find_next_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start)168e79864f3SYury Norov unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
169e79864f3SYury Norov unsigned long nbits, unsigned long start)
170e79864f3SYury Norov {
171e79864f3SYury Norov return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start);
172e79864f3SYury Norov }
173e79864f3SYury Norov EXPORT_SYMBOL(_find_next_and_bit);
174e79864f3SYury Norov #endif
175e79864f3SYury Norov
17690d48290SValentin Schneider #ifndef find_next_andnot_bit
_find_next_andnot_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start)17790d48290SValentin Schneider unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
17890d48290SValentin Schneider unsigned long nbits, unsigned long start)
17990d48290SValentin Schneider {
18090d48290SValentin Schneider return FIND_NEXT_BIT(addr1[idx] & ~addr2[idx], /* nop */, nbits, start);
18190d48290SValentin Schneider }
18290d48290SValentin Schneider EXPORT_SYMBOL(_find_next_andnot_bit);
18390d48290SValentin Schneider #endif
18490d48290SValentin Schneider
185*1470afefSDave Chinner #ifndef find_next_or_bit
_find_next_or_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start)186*1470afefSDave Chinner unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
187*1470afefSDave Chinner unsigned long nbits, unsigned long start)
188*1470afefSDave Chinner {
189*1470afefSDave Chinner return FIND_NEXT_BIT(addr1[idx] | addr2[idx], /* nop */, nbits, start);
190*1470afefSDave Chinner }
191*1470afefSDave Chinner EXPORT_SYMBOL(_find_next_or_bit);
192*1470afefSDave Chinner #endif
193*1470afefSDave Chinner
194e79864f3SYury Norov #ifndef find_next_zero_bit
_find_next_zero_bit(const unsigned long * addr,unsigned long nbits,unsigned long start)195e79864f3SYury Norov unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
196e79864f3SYury Norov unsigned long start)
197e79864f3SYury Norov {
198e79864f3SYury Norov return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
199e79864f3SYury Norov }
200e79864f3SYury Norov EXPORT_SYMBOL(_find_next_zero_bit);
201e79864f3SYury Norov #endif
202e79864f3SYury Norov
203840620a1SYury Norov #ifndef find_last_bit
_find_last_bit(const unsigned long * addr,unsigned long size)2042cc7b6a4SYury Norov unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
205840620a1SYury Norov {
206840620a1SYury Norov if (size) {
207840620a1SYury Norov unsigned long val = BITMAP_LAST_WORD_MASK(size);
208840620a1SYury Norov unsigned long idx = (size-1) / BITS_PER_LONG;
209840620a1SYury Norov
210840620a1SYury Norov do {
211840620a1SYury Norov val &= addr[idx];
212840620a1SYury Norov if (val)
213840620a1SYury Norov return idx * BITS_PER_LONG + __fls(val);
214840620a1SYury Norov
215840620a1SYury Norov val = ~0ul;
216840620a1SYury Norov } while (idx--);
217840620a1SYury Norov }
218840620a1SYury Norov return size;
219840620a1SYury Norov }
2202cc7b6a4SYury Norov EXPORT_SYMBOL(_find_last_bit);
221840620a1SYury Norov #endif
222840620a1SYury Norov
find_next_clump8(unsigned long * clump,const unsigned long * addr,unsigned long size,unsigned long offset)223169c474fSWilliam Breathitt Gray unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
224169c474fSWilliam Breathitt Gray unsigned long size, unsigned long offset)
225169c474fSWilliam Breathitt Gray {
226169c474fSWilliam Breathitt Gray offset = find_next_bit(addr, size, offset);
227169c474fSWilliam Breathitt Gray if (offset == size)
228169c474fSWilliam Breathitt Gray return size;
229169c474fSWilliam Breathitt Gray
230169c474fSWilliam Breathitt Gray offset = round_down(offset, 8);
231169c474fSWilliam Breathitt Gray *clump = bitmap_get_value8(addr, offset);
232169c474fSWilliam Breathitt Gray
233169c474fSWilliam Breathitt Gray return offset;
234169c474fSWilliam Breathitt Gray }
235169c474fSWilliam Breathitt Gray EXPORT_SYMBOL(find_next_clump8);
23614a99e13SYury Norov
23714a99e13SYury Norov #ifdef __BIG_ENDIAN
23814a99e13SYury Norov
23914a99e13SYury Norov #ifndef find_first_zero_bit_le
24014a99e13SYury Norov /*
24114a99e13SYury Norov * Find the first cleared bit in an LE memory region.
24214a99e13SYury Norov */
_find_first_zero_bit_le(const unsigned long * addr,unsigned long size)24314a99e13SYury Norov unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)
24414a99e13SYury Norov {
24514a99e13SYury Norov return FIND_FIRST_BIT(~addr[idx], swab, size);
24614a99e13SYury Norov }
24714a99e13SYury Norov EXPORT_SYMBOL(_find_first_zero_bit_le);
24814a99e13SYury Norov
24914a99e13SYury Norov #endif
25014a99e13SYury Norov
251e79864f3SYury Norov #ifndef find_next_zero_bit_le
_find_next_zero_bit_le(const unsigned long * addr,unsigned long size,unsigned long offset)252e79864f3SYury Norov unsigned long _find_next_zero_bit_le(const unsigned long *addr,
253e79864f3SYury Norov unsigned long size, unsigned long offset)
254e79864f3SYury Norov {
255e79864f3SYury Norov return FIND_NEXT_BIT(~addr[idx], swab, size, offset);
256e79864f3SYury Norov }
257e79864f3SYury Norov EXPORT_SYMBOL(_find_next_zero_bit_le);
258e79864f3SYury Norov #endif
259e79864f3SYury Norov
260e79864f3SYury Norov #ifndef find_next_bit_le
_find_next_bit_le(const unsigned long * addr,unsigned long size,unsigned long offset)261e79864f3SYury Norov unsigned long _find_next_bit_le(const unsigned long *addr,
262e79864f3SYury Norov unsigned long size, unsigned long offset)
263e79864f3SYury Norov {
264e79864f3SYury Norov return FIND_NEXT_BIT(addr[idx], swab, size, offset);
265e79864f3SYury Norov }
266e79864f3SYury Norov EXPORT_SYMBOL(_find_next_bit_le);
267e79864f3SYury Norov
268e79864f3SYury Norov #endif
269e79864f3SYury Norov
27014a99e13SYury Norov #endif /* __BIG_ENDIAN */
271