find_bit.c

  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#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;			\
 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_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
176				 unsigned long size, unsigned long n)
177{
178	return FIND_NTH_BIT(addr1[idx] & ~addr2[idx], size, n);
179}
180EXPORT_SYMBOL(__find_nth_andnot_bit);
181
182unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1,
183					const unsigned long *addr2,
184					const unsigned long *addr3,
185					unsigned long size, unsigned long n)
186{
187	return FIND_NTH_BIT(addr1[idx] & addr2[idx] & ~addr3[idx], size, n);
188}
189EXPORT_SYMBOL(__find_nth_and_andnot_bit);
190
191#ifndef find_next_and_bit
192unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
193					unsigned long nbits, unsigned long start)
194{
195	return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start);
196}
197EXPORT_SYMBOL(_find_next_and_bit);
198#endif
199
200#ifndef find_next_andnot_bit
201unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
202					unsigned long nbits, unsigned long start)
203{
204	return FIND_NEXT_BIT(addr1[idx] & ~addr2[idx], /* nop */, nbits, start);
205}
206EXPORT_SYMBOL(_find_next_andnot_bit);
207#endif
208
209#ifndef find_next_or_bit
210unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
211					unsigned long nbits, unsigned long start)
212{
213	return FIND_NEXT_BIT(addr1[idx] | addr2[idx], /* nop */, nbits, start);
214}
215EXPORT_SYMBOL(_find_next_or_bit);
216#endif
217
218#ifndef find_next_zero_bit
219unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
220					 unsigned long start)
221{
222	return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start);
223}
224EXPORT_SYMBOL(_find_next_zero_bit);
225#endif
226
227#ifndef find_last_bit
228unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
229{
230	if (size) {
231		unsigned long val = BITMAP_LAST_WORD_MASK(size);
232		unsigned long idx = (size-1) / BITS_PER_LONG;
233
234		do {
235			val &= addr[idx];
236			if (val)
237				return idx * BITS_PER_LONG + __fls(val);
238
239			val = ~0ul;
240		} while (idx--);
241	}
242	return size;
243}
244EXPORT_SYMBOL(_find_last_bit);
245#endif
246
247unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
248			       unsigned long size, unsigned long offset)
249{
250	offset = find_next_bit(addr, size, offset);
251	if (offset == size)
252		return size;
253
254	offset = round_down(offset, 8);
255	*clump = bitmap_get_value8(addr, offset);
256
257	return offset;
258}
259EXPORT_SYMBOL(find_next_clump8);
260
261#ifdef __BIG_ENDIAN
262
263#ifndef find_first_zero_bit_le
264/*
265 * Find the first cleared bit in an LE memory region.
266 */
267unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size)
268{
269	return FIND_FIRST_BIT(~addr[idx], swab, size);
270}
271EXPORT_SYMBOL(_find_first_zero_bit_le);
272
273#endif
274
275#ifndef find_next_zero_bit_le
276unsigned long _find_next_zero_bit_le(const unsigned long *addr,
277					unsigned long size, unsigned long offset)
278{
279	return FIND_NEXT_BIT(~addr[idx], swab, size, offset);
280}
281EXPORT_SYMBOL(_find_next_zero_bit_le);
282#endif
283
284#ifndef find_next_bit_le
285unsigned long _find_next_bit_le(const unsigned long *addr,
286				unsigned long size, unsigned long offset)
287{
288	return FIND_NEXT_BIT(addr[idx], swab, size, offset);
289}
290EXPORT_SYMBOL(_find_next_bit_le);
291
292#endif
293
294#endif /* __BIG_ENDIAN */
295
296/**
297 * find_random_bit - find a set bit at random position
298 * @addr: The address to base the search on
299 * @size: The bitmap size in bits
300 *
301 * Returns: a position of a random set bit; >= @size otherwise
302 */
303unsigned long find_random_bit(const unsigned long *addr, unsigned long size)
304{
305	int w = bitmap_weight(addr, size);
306
307	switch (w) {
308	case 0:
309		return size;
310	case 1:
311		/* Performance trick for single-bit bitmaps */
312		return find_first_bit(addr, size);
313	default:
314		return find_nth_bit(addr, size, get_random_u32_below(w));
315	}
316}
317EXPORT_SYMBOL(find_random_bit);