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/kernel.h>
19 #include <linux/minmax.h>
20
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)
24 /*
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.
30 */
_find_next_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long nbits,unsigned long start,unsigned long invert,unsigned long le)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)
34 {
35 unsigned long tmp, mask;
36
37 if (unlikely(start >= nbits))
38 return nbits;
39
40 tmp = addr1[start / BITS_PER_LONG];
41 if (addr2)
42 tmp &= addr2[start / BITS_PER_LONG];
43 tmp ^= invert;
44
45 /* Handle 1st word. */
46 mask = BITMAP_FIRST_WORD_MASK(start);
47 if (le)
48 mask = swab(mask);
49
50 tmp &= mask;
51
52 start = round_down(start, BITS_PER_LONG);
53
54 while (!tmp) {
55 start += BITS_PER_LONG;
56 if (start >= nbits)
57 return nbits;
58
59 tmp = addr1[start / BITS_PER_LONG];
60 if (addr2)
61 tmp &= addr2[start / BITS_PER_LONG];
62 tmp ^= invert;
63 }
64
65 if (le)
66 tmp = swab(tmp);
67
68 return min(start + __ffs(tmp), nbits);
69 }
70 #endif
71
72 #ifndef find_next_bit
73 /*
74 * Find the next set bit in a memory region.
75 */
find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)76 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
77 unsigned long offset)
78 {
79 return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
80 }
81 EXPORT_SYMBOL(find_next_bit);
82 #endif
83
84 #ifndef find_next_zero_bit
find_next_zero_bit(const unsigned long * addr,unsigned long size,unsigned long offset)85 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
86 unsigned long offset)
87 {
88 return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
89 }
90 EXPORT_SYMBOL(find_next_zero_bit);
91 #endif
92
93 #if !defined(find_next_and_bit)
find_next_and_bit(const unsigned long * addr1,const unsigned long * addr2,unsigned long size,unsigned long offset)94 unsigned long find_next_and_bit(const unsigned long *addr1,
95 const unsigned long *addr2, unsigned long size,
96 unsigned long offset)
97 {
98 return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
99 }
100 EXPORT_SYMBOL(find_next_and_bit);
101 #endif
102
103 #ifndef find_first_bit
104 /*
105 * Find the first set bit in a memory region.
106 */
find_first_bit(const unsigned long * addr,unsigned long size)107 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
108 {
109 unsigned long idx;
110
111 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
112 if (addr[idx])
113 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
114 }
115
116 return size;
117 }
118 EXPORT_SYMBOL(find_first_bit);
119 #endif
120
121 #ifndef find_first_zero_bit
122 /*
123 * Find the first cleared bit in a memory region.
124 */
find_first_zero_bit(const unsigned long * addr,unsigned long size)125 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
126 {
127 unsigned long idx;
128
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);
132 }
133
134 return size;
135 }
136 EXPORT_SYMBOL(find_first_zero_bit);
137 #endif
138
139 #ifndef find_last_bit
find_last_bit(const unsigned long * addr,unsigned long size)140 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
141 {
142 if (size) {
143 unsigned long val = BITMAP_LAST_WORD_MASK(size);
144 unsigned long idx = (size-1) / BITS_PER_LONG;
145
146 do {
147 val &= addr[idx];
148 if (val)
149 return idx * BITS_PER_LONG + __fls(val);
150
151 val = ~0ul;
152 } while (idx--);
153 }
154 return size;
155 }
156 EXPORT_SYMBOL(find_last_bit);
157 #endif
158
159 #ifdef __BIG_ENDIAN
160
161 #ifndef find_next_zero_bit_le
find_next_zero_bit_le(const void * addr,unsigned long size,unsigned long offset)162 unsigned long find_next_zero_bit_le(const void *addr, unsigned
163 long size, unsigned long offset)
164 {
165 return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
166 }
167 EXPORT_SYMBOL(find_next_zero_bit_le);
168 #endif
169
170 #ifndef find_next_bit_le
find_next_bit_le(const void * addr,unsigned long size,unsigned long offset)171 unsigned long find_next_bit_le(const void *addr, unsigned
172 long size, unsigned long offset)
173 {
174 return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
175 }
176 EXPORT_SYMBOL(find_next_bit_le);
177 #endif
178
179 #endif /* __BIG_ENDIAN */
180
find_next_clump8(unsigned long * clump,const unsigned long * addr,unsigned long size,unsigned long offset)181 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
182 unsigned long size, unsigned long offset)
183 {
184 offset = find_next_bit(addr, size, offset);
185 if (offset == size)
186 return size;
187
188 offset = round_down(offset, 8);
189 *clump = bitmap_get_value8(addr, offset);
190
191 return offset;
192 }
193 EXPORT_SYMBOL(find_next_clump8);
194