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