]>
Commit | Line | Data |
---|---|---|
2874c5fd | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
8f6f19dd | 2 | /* bit search implementation |
1da177e4 LT |
3 | * |
4 | * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. | |
5 | * Written by David Howells (dhowells@redhat.com) | |
6 | * | |
8f6f19dd YN |
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 | * | |
2c57a0e2 YN |
11 | * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease |
12 | * size and improve performance, 2015. | |
1da177e4 LT |
13 | */ |
14 | ||
15 | #include <linux/bitops.h> | |
8f6f19dd | 16 | #include <linux/bitmap.h> |
8bc3bcc9 | 17 | #include <linux/export.h> |
2c57a0e2 | 18 | #include <linux/kernel.h> |
1da177e4 | 19 | |
0ade34c3 CC |
20 | #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ |
21 | !defined(find_next_and_bit) | |
c7f612cd | 22 | |
64970b68 | 23 | /* |
0ade34c3 CC |
24 | * This is a common helper function for find_next_bit, find_next_zero_bit, and |
25 | * find_next_and_bit. The differences are: | |
26 | * - The "invert" argument, which is XORed with each fetched word before | |
27 | * searching it for one bits. | |
28 | * - The optional "addr2", which is anded with "addr1" if present. | |
c7f612cd | 29 | */ |
0ade34c3 CC |
30 | static inline unsigned long _find_next_bit(const unsigned long *addr1, |
31 | const unsigned long *addr2, unsigned long nbits, | |
32 | unsigned long start, unsigned long invert) | |
1da177e4 | 33 | { |
1da177e4 LT |
34 | unsigned long tmp; |
35 | ||
e4afd2e5 | 36 | if (unlikely(start >= nbits)) |
2c57a0e2 YN |
37 | return nbits; |
38 | ||
0ade34c3 CC |
39 | tmp = addr1[start / BITS_PER_LONG]; |
40 | if (addr2) | |
41 | tmp &= addr2[start / BITS_PER_LONG]; | |
42 | tmp ^= invert; | |
2c57a0e2 YN |
43 | |
44 | /* Handle 1st word. */ | |
45 | tmp &= BITMAP_FIRST_WORD_MASK(start); | |
46 | start = round_down(start, BITS_PER_LONG); | |
47 | ||
48 | while (!tmp) { | |
49 | start += BITS_PER_LONG; | |
50 | if (start >= nbits) | |
51 | return nbits; | |
52 | ||
0ade34c3 CC |
53 | tmp = addr1[start / BITS_PER_LONG]; |
54 | if (addr2) | |
55 | tmp &= addr2[start / BITS_PER_LONG]; | |
56 | tmp ^= invert; | |
1da177e4 LT |
57 | } |
58 | ||
2c57a0e2 | 59 | return min(start + __ffs(tmp), nbits); |
c7f612cd | 60 | } |
19de85ef | 61 | #endif |
1da177e4 | 62 | |
2c57a0e2 | 63 | #ifndef find_next_bit |
c7f612cd | 64 | /* |
2c57a0e2 | 65 | * Find the next set bit in a memory region. |
c7f612cd | 66 | */ |
2c57a0e2 YN |
67 | unsigned long find_next_bit(const unsigned long *addr, unsigned long size, |
68 | unsigned long offset) | |
69 | { | |
0ade34c3 | 70 | return _find_next_bit(addr, NULL, size, offset, 0UL); |
2c57a0e2 YN |
71 | } |
72 | EXPORT_SYMBOL(find_next_bit); | |
73 | #endif | |
74 | ||
75 | #ifndef find_next_zero_bit | |
fee4b19f TG |
76 | unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, |
77 | unsigned long offset) | |
c7f612cd | 78 | { |
0ade34c3 | 79 | return _find_next_bit(addr, NULL, size, offset, ~0UL); |
1da177e4 | 80 | } |
fee4b19f | 81 | EXPORT_SYMBOL(find_next_zero_bit); |
19de85ef | 82 | #endif |
77b9bd9c | 83 | |
0ade34c3 CC |
84 | #if !defined(find_next_and_bit) |
85 | unsigned long find_next_and_bit(const unsigned long *addr1, | |
86 | const unsigned long *addr2, unsigned long size, | |
87 | unsigned long offset) | |
88 | { | |
89 | return _find_next_bit(addr1, addr2, size, offset, 0UL); | |
90 | } | |
91 | EXPORT_SYMBOL(find_next_and_bit); | |
92 | #endif | |
93 | ||
19de85ef | 94 | #ifndef find_first_bit |
77b9bd9c AH |
95 | /* |
96 | * Find the first set bit in a memory region. | |
97 | */ | |
fee4b19f | 98 | unsigned long find_first_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c | 99 | { |
2c57a0e2 | 100 | unsigned long idx; |
77b9bd9c | 101 | |
2c57a0e2 YN |
102 | for (idx = 0; idx * BITS_PER_LONG < size; idx++) { |
103 | if (addr[idx]) | |
104 | return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); | |
77b9bd9c | 105 | } |
77b9bd9c | 106 | |
2c57a0e2 | 107 | return size; |
77b9bd9c | 108 | } |
fee4b19f | 109 | EXPORT_SYMBOL(find_first_bit); |
19de85ef | 110 | #endif |
77b9bd9c | 111 | |
19de85ef | 112 | #ifndef find_first_zero_bit |
77b9bd9c AH |
113 | /* |
114 | * Find the first cleared bit in a memory region. | |
115 | */ | |
fee4b19f | 116 | unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c | 117 | { |
2c57a0e2 | 118 | unsigned long idx; |
77b9bd9c | 119 | |
2c57a0e2 YN |
120 | for (idx = 0; idx * BITS_PER_LONG < size; idx++) { |
121 | if (addr[idx] != ~0UL) | |
122 | return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); | |
77b9bd9c | 123 | } |
77b9bd9c | 124 | |
2c57a0e2 | 125 | return size; |
77b9bd9c | 126 | } |
fee4b19f | 127 | EXPORT_SYMBOL(find_first_zero_bit); |
19de85ef | 128 | #endif |
930ae745 | 129 | |
8f6f19dd YN |
130 | #ifndef find_last_bit |
131 | unsigned long find_last_bit(const unsigned long *addr, unsigned long size) | |
132 | { | |
133 | if (size) { | |
134 | unsigned long val = BITMAP_LAST_WORD_MASK(size); | |
135 | unsigned long idx = (size-1) / BITS_PER_LONG; | |
136 | ||
137 | do { | |
138 | val &= addr[idx]; | |
139 | if (val) | |
140 | return idx * BITS_PER_LONG + __fls(val); | |
141 | ||
142 | val = ~0ul; | |
143 | } while (idx--); | |
144 | } | |
145 | return size; | |
146 | } | |
147 | EXPORT_SYMBOL(find_last_bit); | |
148 | #endif | |
149 | ||
930ae745 AM |
150 | #ifdef __BIG_ENDIAN |
151 | ||
152 | /* include/linux/byteorder does not support "unsigned long" type */ | |
930ae745 AM |
153 | static inline unsigned long ext2_swab(const unsigned long y) |
154 | { | |
155 | #if BITS_PER_LONG == 64 | |
156 | return (unsigned long) __swab64((u64) y); | |
157 | #elif BITS_PER_LONG == 32 | |
158 | return (unsigned long) __swab32((u32) y); | |
159 | #else | |
160 | #error BITS_PER_LONG not defined | |
161 | #endif | |
162 | } | |
163 | ||
2c57a0e2 | 164 | #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) |
0ade34c3 CC |
165 | static inline unsigned long _find_next_bit_le(const unsigned long *addr1, |
166 | const unsigned long *addr2, unsigned long nbits, | |
167 | unsigned long start, unsigned long invert) | |
930ae745 | 168 | { |
930ae745 AM |
169 | unsigned long tmp; |
170 | ||
e4afd2e5 | 171 | if (unlikely(start >= nbits)) |
2c57a0e2 YN |
172 | return nbits; |
173 | ||
0ade34c3 CC |
174 | tmp = addr1[start / BITS_PER_LONG]; |
175 | if (addr2) | |
176 | tmp &= addr2[start / BITS_PER_LONG]; | |
177 | tmp ^= invert; | |
2c57a0e2 YN |
178 | |
179 | /* Handle 1st word. */ | |
180 | tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start)); | |
181 | start = round_down(start, BITS_PER_LONG); | |
930ae745 | 182 | |
2c57a0e2 YN |
183 | while (!tmp) { |
184 | start += BITS_PER_LONG; | |
185 | if (start >= nbits) | |
186 | return nbits; | |
187 | ||
0ade34c3 CC |
188 | tmp = addr1[start / BITS_PER_LONG]; |
189 | if (addr2) | |
190 | tmp &= addr2[start / BITS_PER_LONG]; | |
191 | tmp ^= invert; | |
930ae745 | 192 | } |
930ae745 | 193 | |
2c57a0e2 YN |
194 | return min(start + __ffs(ext2_swab(tmp)), nbits); |
195 | } | |
196 | #endif | |
197 | ||
198 | #ifndef find_next_zero_bit_le | |
199 | unsigned long find_next_zero_bit_le(const void *addr, unsigned | |
200 | long size, unsigned long offset) | |
201 | { | |
0ade34c3 | 202 | return _find_next_bit_le(addr, NULL, size, offset, ~0UL); |
930ae745 | 203 | } |
c4945b9e | 204 | EXPORT_SYMBOL(find_next_zero_bit_le); |
19de85ef | 205 | #endif |
930ae745 | 206 | |
19de85ef | 207 | #ifndef find_next_bit_le |
a56560b3 | 208 | unsigned long find_next_bit_le(const void *addr, unsigned |
aa02ad67 AK |
209 | long size, unsigned long offset) |
210 | { | |
0ade34c3 | 211 | return _find_next_bit_le(addr, NULL, size, offset, 0UL); |
aa02ad67 | 212 | } |
c4945b9e | 213 | EXPORT_SYMBOL(find_next_bit_le); |
19de85ef | 214 | #endif |
0664996b | 215 | |
930ae745 | 216 | #endif /* __BIG_ENDIAN */ |
169c474f WBG |
217 | |
218 | unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr, | |
219 | unsigned long size, unsigned long offset) | |
220 | { | |
221 | offset = find_next_bit(addr, size, offset); | |
222 | if (offset == size) | |
223 | return size; | |
224 | ||
225 | offset = round_down(offset, 8); | |
226 | *clump = bitmap_get_value8(addr, offset); | |
227 | ||
228 | return offset; | |
229 | } | |
230 | EXPORT_SYMBOL(find_next_clump8); |