Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* find_next_bit.c: fallback find next bit implementation |
2 | * | |
3 | * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. | |
4 | * Written by David Howells (dhowells@redhat.com) | |
5 | * | |
6 | * This program is free software; you can redistribute it and/or | |
7 | * modify it under the terms of the GNU General Public License | |
8 | * as published by the Free Software Foundation; either version | |
9 | * 2 of the License, or (at your option) any later version. | |
10 | */ | |
11 | ||
12 | #include <linux/bitops.h> | |
40234401 | 13 | #include <linux/module.h> |
c7f612cd | 14 | #include <asm/types.h> |
930ae745 | 15 | #include <asm/byteorder.h> |
1da177e4 | 16 | |
c7f612cd AM |
17 | #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) |
18 | ||
77b9bd9c | 19 | #ifdef CONFIG_GENERIC_FIND_NEXT_BIT |
19de85ef | 20 | #ifndef find_next_bit |
64970b68 AH |
21 | /* |
22 | * Find the next set bit in a memory region. | |
c7f612cd | 23 | */ |
fee4b19f TG |
24 | unsigned long find_next_bit(const unsigned long *addr, unsigned long size, |
25 | unsigned long offset) | |
1da177e4 | 26 | { |
c7f612cd AM |
27 | const unsigned long *p = addr + BITOP_WORD(offset); |
28 | unsigned long result = offset & ~(BITS_PER_LONG-1); | |
1da177e4 LT |
29 | unsigned long tmp; |
30 | ||
c7f612cd AM |
31 | if (offset >= size) |
32 | return size; | |
33 | size -= result; | |
34 | offset %= BITS_PER_LONG; | |
1da177e4 | 35 | if (offset) { |
c7f612cd AM |
36 | tmp = *(p++); |
37 | tmp &= (~0UL << offset); | |
38 | if (size < BITS_PER_LONG) | |
39 | goto found_first; | |
40 | if (tmp) | |
41 | goto found_middle; | |
42 | size -= BITS_PER_LONG; | |
43 | result += BITS_PER_LONG; | |
44 | } | |
45 | while (size & ~(BITS_PER_LONG-1)) { | |
46 | if ((tmp = *(p++))) | |
47 | goto found_middle; | |
48 | result += BITS_PER_LONG; | |
49 | size -= BITS_PER_LONG; | |
1da177e4 | 50 | } |
c7f612cd AM |
51 | if (!size) |
52 | return result; | |
53 | tmp = *p; | |
1da177e4 | 54 | |
c7f612cd AM |
55 | found_first: |
56 | tmp &= (~0UL >> (BITS_PER_LONG - size)); | |
57 | if (tmp == 0UL) /* Are any bits set? */ | |
58 | return result + size; /* Nope. */ | |
59 | found_middle: | |
60 | return result + __ffs(tmp); | |
61 | } | |
fee4b19f | 62 | EXPORT_SYMBOL(find_next_bit); |
19de85ef | 63 | #endif |
1da177e4 | 64 | |
19de85ef | 65 | #ifndef find_next_zero_bit |
c7f612cd AM |
66 | /* |
67 | * This implementation of find_{first,next}_zero_bit was stolen from | |
68 | * Linus' asm-alpha/bitops.h. | |
69 | */ | |
fee4b19f TG |
70 | unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, |
71 | unsigned long offset) | |
c7f612cd AM |
72 | { |
73 | const unsigned long *p = addr + BITOP_WORD(offset); | |
74 | unsigned long result = offset & ~(BITS_PER_LONG-1); | |
75 | unsigned long tmp; | |
1da177e4 | 76 | |
c7f612cd AM |
77 | if (offset >= size) |
78 | return size; | |
79 | size -= result; | |
80 | offset %= BITS_PER_LONG; | |
81 | if (offset) { | |
82 | tmp = *(p++); | |
83 | tmp |= ~0UL >> (BITS_PER_LONG - offset); | |
84 | if (size < BITS_PER_LONG) | |
85 | goto found_first; | |
86 | if (~tmp) | |
87 | goto found_middle; | |
88 | size -= BITS_PER_LONG; | |
89 | result += BITS_PER_LONG; | |
90 | } | |
91 | while (size & ~(BITS_PER_LONG-1)) { | |
92 | if (~(tmp = *(p++))) | |
93 | goto found_middle; | |
94 | result += BITS_PER_LONG; | |
95 | size -= BITS_PER_LONG; | |
1da177e4 | 96 | } |
c7f612cd AM |
97 | if (!size) |
98 | return result; | |
99 | tmp = *p; | |
1da177e4 | 100 | |
c7f612cd AM |
101 | found_first: |
102 | tmp |= ~0UL << size; | |
103 | if (tmp == ~0UL) /* Are any bits zero? */ | |
104 | return result + size; /* Nope. */ | |
105 | found_middle: | |
106 | return result + ffz(tmp); | |
1da177e4 | 107 | } |
fee4b19f | 108 | EXPORT_SYMBOL(find_next_zero_bit); |
19de85ef | 109 | #endif |
77b9bd9c AH |
110 | #endif /* CONFIG_GENERIC_FIND_NEXT_BIT */ |
111 | ||
112 | #ifdef CONFIG_GENERIC_FIND_FIRST_BIT | |
19de85ef | 113 | #ifndef find_first_bit |
77b9bd9c AH |
114 | /* |
115 | * Find the first set bit in a memory region. | |
116 | */ | |
fee4b19f | 117 | unsigned long find_first_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c AH |
118 | { |
119 | const unsigned long *p = addr; | |
120 | unsigned long result = 0; | |
121 | unsigned long tmp; | |
122 | ||
123 | while (size & ~(BITS_PER_LONG-1)) { | |
124 | if ((tmp = *(p++))) | |
125 | goto found; | |
126 | result += BITS_PER_LONG; | |
127 | size -= BITS_PER_LONG; | |
128 | } | |
129 | if (!size) | |
130 | return result; | |
131 | ||
132 | tmp = (*p) & (~0UL >> (BITS_PER_LONG - size)); | |
133 | if (tmp == 0UL) /* Are any bits set? */ | |
134 | return result + size; /* Nope. */ | |
135 | found: | |
136 | return result + __ffs(tmp); | |
137 | } | |
fee4b19f | 138 | EXPORT_SYMBOL(find_first_bit); |
19de85ef | 139 | #endif |
77b9bd9c | 140 | |
19de85ef | 141 | #ifndef find_first_zero_bit |
77b9bd9c AH |
142 | /* |
143 | * Find the first cleared bit in a memory region. | |
144 | */ | |
fee4b19f | 145 | unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c AH |
146 | { |
147 | const unsigned long *p = addr; | |
148 | unsigned long result = 0; | |
149 | unsigned long tmp; | |
150 | ||
151 | while (size & ~(BITS_PER_LONG-1)) { | |
152 | if (~(tmp = *(p++))) | |
153 | goto found; | |
154 | result += BITS_PER_LONG; | |
155 | size -= BITS_PER_LONG; | |
156 | } | |
157 | if (!size) | |
158 | return result; | |
159 | ||
160 | tmp = (*p) | (~0UL << size); | |
161 | if (tmp == ~0UL) /* Are any bits zero? */ | |
162 | return result + size; /* Nope. */ | |
163 | found: | |
164 | return result + ffz(tmp); | |
165 | } | |
fee4b19f | 166 | EXPORT_SYMBOL(find_first_zero_bit); |
19de85ef | 167 | #endif |
77b9bd9c | 168 | #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ |
930ae745 AM |
169 | |
170 | #ifdef __BIG_ENDIAN | |
0664996b | 171 | #ifdef CONFIG_GENERIC_FIND_BIT_LE |
930ae745 AM |
172 | |
173 | /* include/linux/byteorder does not support "unsigned long" type */ | |
174 | static inline unsigned long ext2_swabp(const unsigned long * x) | |
175 | { | |
176 | #if BITS_PER_LONG == 64 | |
177 | return (unsigned long) __swab64p((u64 *) x); | |
178 | #elif BITS_PER_LONG == 32 | |
179 | return (unsigned long) __swab32p((u32 *) x); | |
180 | #else | |
181 | #error BITS_PER_LONG not defined | |
182 | #endif | |
183 | } | |
184 | ||
185 | /* include/linux/byteorder doesn't support "unsigned long" type */ | |
186 | static inline unsigned long ext2_swab(const unsigned long y) | |
187 | { | |
188 | #if BITS_PER_LONG == 64 | |
189 | return (unsigned long) __swab64((u64) y); | |
190 | #elif BITS_PER_LONG == 32 | |
191 | return (unsigned long) __swab32((u32) y); | |
192 | #else | |
193 | #error BITS_PER_LONG not defined | |
194 | #endif | |
195 | } | |
196 | ||
19de85ef | 197 | #ifndef find_next_zero_bit_le |
a56560b3 | 198 | unsigned long find_next_zero_bit_le(const void *addr, unsigned |
930ae745 AM |
199 | long size, unsigned long offset) |
200 | { | |
a56560b3 | 201 | const unsigned long *p = addr; |
930ae745 AM |
202 | unsigned long result = offset & ~(BITS_PER_LONG - 1); |
203 | unsigned long tmp; | |
204 | ||
205 | if (offset >= size) | |
206 | return size; | |
a56560b3 | 207 | p += BITOP_WORD(offset); |
930ae745 AM |
208 | size -= result; |
209 | offset &= (BITS_PER_LONG - 1UL); | |
210 | if (offset) { | |
211 | tmp = ext2_swabp(p++); | |
212 | tmp |= (~0UL >> (BITS_PER_LONG - offset)); | |
213 | if (size < BITS_PER_LONG) | |
214 | goto found_first; | |
215 | if (~tmp) | |
216 | goto found_middle; | |
217 | size -= BITS_PER_LONG; | |
218 | result += BITS_PER_LONG; | |
219 | } | |
220 | ||
221 | while (size & ~(BITS_PER_LONG - 1)) { | |
222 | if (~(tmp = *(p++))) | |
223 | goto found_middle_swap; | |
224 | result += BITS_PER_LONG; | |
225 | size -= BITS_PER_LONG; | |
226 | } | |
227 | if (!size) | |
228 | return result; | |
229 | tmp = ext2_swabp(p); | |
230 | found_first: | |
231 | tmp |= ~0UL << size; | |
232 | if (tmp == ~0UL) /* Are any bits zero? */ | |
233 | return result + size; /* Nope. Skip ffz */ | |
234 | found_middle: | |
235 | return result + ffz(tmp); | |
236 | ||
237 | found_middle_swap: | |
238 | return result + ffz(ext2_swab(tmp)); | |
239 | } | |
c4945b9e | 240 | EXPORT_SYMBOL(find_next_zero_bit_le); |
19de85ef | 241 | #endif |
930ae745 | 242 | |
19de85ef | 243 | #ifndef find_next_bit_le |
a56560b3 | 244 | unsigned long find_next_bit_le(const void *addr, unsigned |
aa02ad67 AK |
245 | long size, unsigned long offset) |
246 | { | |
a56560b3 | 247 | const unsigned long *p = addr; |
aa02ad67 AK |
248 | unsigned long result = offset & ~(BITS_PER_LONG - 1); |
249 | unsigned long tmp; | |
250 | ||
251 | if (offset >= size) | |
252 | return size; | |
a56560b3 | 253 | p += BITOP_WORD(offset); |
aa02ad67 AK |
254 | size -= result; |
255 | offset &= (BITS_PER_LONG - 1UL); | |
256 | if (offset) { | |
257 | tmp = ext2_swabp(p++); | |
258 | tmp &= (~0UL << offset); | |
259 | if (size < BITS_PER_LONG) | |
260 | goto found_first; | |
261 | if (tmp) | |
262 | goto found_middle; | |
263 | size -= BITS_PER_LONG; | |
264 | result += BITS_PER_LONG; | |
265 | } | |
266 | ||
267 | while (size & ~(BITS_PER_LONG - 1)) { | |
268 | tmp = *(p++); | |
269 | if (tmp) | |
270 | goto found_middle_swap; | |
271 | result += BITS_PER_LONG; | |
272 | size -= BITS_PER_LONG; | |
273 | } | |
274 | if (!size) | |
275 | return result; | |
276 | tmp = ext2_swabp(p); | |
277 | found_first: | |
278 | tmp &= (~0UL >> (BITS_PER_LONG - size)); | |
279 | if (tmp == 0UL) /* Are any bits set? */ | |
280 | return result + size; /* Nope. */ | |
281 | found_middle: | |
282 | return result + __ffs(tmp); | |
283 | ||
284 | found_middle_swap: | |
285 | return result + __ffs(ext2_swab(tmp)); | |
286 | } | |
c4945b9e | 287 | EXPORT_SYMBOL(find_next_bit_le); |
19de85ef | 288 | #endif |
0664996b AM |
289 | |
290 | #endif /* CONFIG_GENERIC_FIND_BIT_LE */ | |
930ae745 | 291 | #endif /* __BIG_ENDIAN */ |