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 : #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \
23 : !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \
24 : !defined(find_next_and_bit)
25 : /*
26 : * This is a common helper function for find_next_bit, find_next_zero_bit, and
27 : * find_next_and_bit. The differences are:
28 : * - The "invert" argument, which is XORed with each fetched word before
29 : * searching it for one bits.
30 : * - The optional "addr2", which is anded with "addr1" if present.
31 : */
32 841955 : static unsigned long _find_next_bit(const unsigned long *addr1,
33 : const unsigned long *addr2, unsigned long nbits,
34 : unsigned long start, unsigned long invert, unsigned long le)
35 : {
36 841955 : unsigned long tmp, mask;
37 :
38 841955 : if (unlikely(start >= nbits))
39 : return nbits;
40 :
41 822126 : tmp = addr1[start / BITS_PER_LONG];
42 822126 : if (addr2)
43 254324 : tmp &= addr2[start / BITS_PER_LONG];
44 822126 : tmp ^= invert;
45 :
46 : /* Handle 1st word. */
47 822126 : mask = BITMAP_FIRST_WORD_MASK(start);
48 822126 : if (le)
49 0 : mask = swab(mask);
50 :
51 822126 : tmp &= mask;
52 :
53 822126 : start = round_down(start, BITS_PER_LONG);
54 :
55 928395 : while (!tmp) {
56 444207 : start += BITS_PER_LONG;
57 444207 : if (start >= nbits)
58 : return nbits;
59 :
60 106269 : tmp = addr1[start / BITS_PER_LONG];
61 106269 : if (addr2)
62 0 : tmp &= addr2[start / BITS_PER_LONG];
63 106269 : tmp ^= invert;
64 : }
65 :
66 484188 : if (le)
67 0 : tmp = swab(tmp);
68 :
69 484188 : return min(start + __ffs(tmp), nbits);
70 : }
71 : #endif
72 :
73 : #ifndef find_next_bit
74 : /*
75 : * Find the next set bit in a memory region.
76 : */
77 425803 : unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
78 : unsigned long offset)
79 : {
80 425803 : return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
81 : }
82 : EXPORT_SYMBOL(find_next_bit);
83 : #endif
84 :
85 : #ifndef find_next_zero_bit
86 161852 : unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
87 : unsigned long offset)
88 : {
89 161852 : return _find_next_bit(addr, NULL, size, offset, ~0UL, 0);
90 : }
91 : EXPORT_SYMBOL(find_next_zero_bit);
92 : #endif
93 :
94 : #if !defined(find_next_and_bit)
95 254171 : unsigned long find_next_and_bit(const unsigned long *addr1,
96 : const unsigned long *addr2, unsigned long size,
97 : unsigned long offset)
98 : {
99 254171 : return _find_next_bit(addr1, addr2, size, offset, 0UL, 0);
100 : }
101 : EXPORT_SYMBOL(find_next_and_bit);
102 : #endif
103 :
104 : #ifndef find_first_bit
105 : /*
106 : * Find the first set bit in a memory region.
107 : */
108 27693 : unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
109 : {
110 27693 : unsigned long idx;
111 :
112 27775 : for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
113 27755 : if (addr[idx])
114 27673 : return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
115 : }
116 :
117 : return size;
118 : }
119 : EXPORT_SYMBOL(find_first_bit);
120 : #endif
121 :
122 : #ifndef find_first_zero_bit
123 : /*
124 : * Find the first cleared bit in a memory region.
125 : */
126 15762 : unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
127 : {
128 15762 : unsigned long idx;
129 :
130 811370 : for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
131 811370 : if (addr[idx] != ~0UL)
132 15762 : return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
133 : }
134 :
135 : return size;
136 : }
137 : EXPORT_SYMBOL(find_first_zero_bit);
138 : #endif
139 :
140 : #ifndef find_last_bit
141 1823 : unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
142 : {
143 1823 : if (size) {
144 1822 : unsigned long val = BITMAP_LAST_WORD_MASK(size);
145 1822 : unsigned long idx = (size-1) / BITS_PER_LONG;
146 :
147 1860 : do {
148 1860 : val &= addr[idx];
149 1860 : if (val)
150 1822 : return idx * BITS_PER_LONG + __fls(val);
151 :
152 38 : val = ~0ul;
153 38 : } while (idx--);
154 : }
155 : return size;
156 : }
157 : EXPORT_SYMBOL(find_last_bit);
158 : #endif
159 :
160 : #ifdef __BIG_ENDIAN
161 :
162 : #ifndef find_next_zero_bit_le
163 : unsigned long find_next_zero_bit_le(const void *addr, unsigned
164 : long size, unsigned long offset)
165 : {
166 : return _find_next_bit(addr, NULL, size, offset, ~0UL, 1);
167 : }
168 : EXPORT_SYMBOL(find_next_zero_bit_le);
169 : #endif
170 :
171 : #ifndef find_next_bit_le
172 : unsigned long find_next_bit_le(const void *addr, unsigned
173 : long size, unsigned long offset)
174 : {
175 : return _find_next_bit(addr, NULL, size, offset, 0UL, 1);
176 : }
177 : EXPORT_SYMBOL(find_next_bit_le);
178 : #endif
179 :
180 : #endif /* __BIG_ENDIAN */
181 :
182 0 : unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
183 : unsigned long size, unsigned long offset)
184 : {
185 0 : offset = find_next_bit(addr, size, offset);
186 0 : if (offset == size)
187 : return size;
188 :
189 0 : offset = round_down(offset, 8);
190 0 : *clump = bitmap_get_value8(addr, offset);
191 :
192 0 : return offset;
193 : }
194 : EXPORT_SYMBOL(find_next_clump8);
|
