1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* bit search implementation
4 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
5 * Written by David Howells (dhowells@redhat.com)
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)
11 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
12 * size and improve performance, 2015.
15 #include <linux/bitops.h>
16 #include <linux/bitmap.h>
17 #include <linux/export.h>
18 #include <linux/kernel.h>
19 #include <linux/minmax.h>
21 #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
22 !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \
23 !defined(find_next_and_bit)
25 * This is a common helper function for find_next_bit, find_next_zero_bit, and
26 * find_next_and_bit. The differences are:
27 * - The "invert" argument, which is XORed with each fetched word before
28 * searching it for one bits.
29 * - The optional "addr2", which is anded with "addr1" if present.
31 static unsigned long _find_next_bit(const unsigned long *addr1,
32 const unsigned long *addr2, unsigned long nbits,
33 unsigned long start, unsigned long invert, unsigned long le)
35 unsigned long tmp, mask;
37 if (unlikely(start >= nbits))
40 tmp = addr1[start / BITS_PER_LONG];
42 tmp &= addr2[start / BITS_PER_LONG];
45 /* Handle 1st word. */
46 mask = BITMAP_FIRST_WORD_MASK(start);
52 start = round_down(start, BITS_PER_LONG);
55 start += BITS_PER_LONG;
59 tmp = addr1[start / BITS_PER_LONG];
61 tmp &= addr2[start / BITS_PER_LONG];
68 return min(start + __ffs(tmp), nbits);
74 * Find the next set bit in a memory region.
76 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
79 return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
81 EXPORT_SYMBOL(find_next_bit);
84 #ifndef find_next_zero_bit
85 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
88 return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
90 EXPORT_SYMBOL(find_next_zero_bit);
93 #if !defined(find_next_and_bit)
94 unsigned long find_next_and_bit(const unsigned long *addr1,
95 const unsigned long *addr2, unsigned long size,
98 return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
100 EXPORT_SYMBOL(find_next_and_bit);
103 #ifndef find_first_bit
105 * Find the first set bit in a memory region.
107 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
111 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
113 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
118 EXPORT_SYMBOL(find_first_bit);
121 #ifndef find_first_zero_bit
123 * Find the first cleared bit in a memory region.
125 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
129 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
130 if (addr[idx] != ~0UL)
131 return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
136 EXPORT_SYMBOL(find_first_zero_bit);
139 #ifndef find_last_bit
140 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
143 unsigned long val = BITMAP_LAST_WORD_MASK(size);
144 unsigned long idx = (size-1) / BITS_PER_LONG;
149 return idx * BITS_PER_LONG + __fls(val);
156 EXPORT_SYMBOL(find_last_bit);
161 #ifndef find_next_zero_bit_le
162 unsigned long find_next_zero_bit_le(const void *addr, unsigned
163 long size, unsigned long offset)
165 return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
167 EXPORT_SYMBOL(find_next_zero_bit_le);
170 #ifndef find_next_bit_le
171 unsigned long find_next_bit_le(const void *addr, unsigned
172 long size, unsigned long offset)
174 return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
176 EXPORT_SYMBOL(find_next_bit_le);
179 #endif /* __BIG_ENDIAN */
181 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
182 unsigned long size, unsigned long offset)
184 offset = find_next_bit(addr, size, offset);
188 offset = round_down(offset, 8);
189 *clump = bitmap_get_value8(addr, offset);
193 EXPORT_SYMBOL(find_next_clump8);