Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 286 lines (259 sloc) 6.535 kb
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
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>
4023440 [PATCH] frv: implement and export various things required by modules
David Howells authored
13 #include <linux/module.h>
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
14 #include <asm/types.h>
930ae74 [PATCH] bitops: generic ext2_{set,clear,test,find_first_zero,find_nex…
Akinobu Mita authored
15 #include <asm/byteorder.h>
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
16
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
17 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
18
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
19 #ifndef find_next_bit
64970b6 x86, generic: optimize find_next_(zero_)bit for small constant-size b…
Alexander van Heukelum authored
20 /*
21 * Find the next set bit in a memory region.
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
22 */
fee4b19 bitops: remove "optimizations"
Thomas Gleixner authored
23 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
24 unsigned long offset)
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
25 {
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
26 const unsigned long *p = addr + BITOP_WORD(offset);
27 unsigned long result = offset & ~(BITS_PER_LONG-1);
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
28 unsigned long tmp;
29
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
30 if (offset >= size)
31 return size;
32 size -= result;
33 offset %= BITS_PER_LONG;
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
34 if (offset) {
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
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;
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
49 }
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
50 if (!size)
51 return result;
52 tmp = *p;
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
53
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
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 }
fee4b19 bitops: remove "optimizations"
Thomas Gleixner authored
61 EXPORT_SYMBOL(find_next_bit);
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
62 #endif
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
63
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
64 #ifndef find_next_zero_bit
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
65 /*
66 * This implementation of find_{first,next}_zero_bit was stolen from
67 * Linus' asm-alpha/bitops.h.
68 */
fee4b19 bitops: remove "optimizations"
Thomas Gleixner authored
69 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
70 unsigned long offset)
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
71 {
72 const unsigned long *p = addr + BITOP_WORD(offset);
73 unsigned long result = offset & ~(BITS_PER_LONG-1);
74 unsigned long tmp;
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
75
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
76 if (offset >= size)
77 return size;
78 size -= result;
79 offset %= BITS_PER_LONG;
80 if (offset) {
81 tmp = *(p++);
82 tmp |= ~0UL >> (BITS_PER_LONG - offset);
83 if (size < BITS_PER_LONG)
84 goto found_first;
85 if (~tmp)
86 goto found_middle;
87 size -= BITS_PER_LONG;
88 result += BITS_PER_LONG;
89 }
90 while (size & ~(BITS_PER_LONG-1)) {
91 if (~(tmp = *(p++)))
92 goto found_middle;
93 result += BITS_PER_LONG;
94 size -= BITS_PER_LONG;
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
95 }
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
96 if (!size)
97 return result;
98 tmp = *p;
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
99
c7f612c [PATCH] bitops: generic find_{next,first}{,_zero}_bit()
Akinobu Mita authored
100 found_first:
101 tmp |= ~0UL << size;
102 if (tmp == ~0UL) /* Are any bits zero? */
103 return result + size; /* Nope. */
104 found_middle:
105 return result + ffz(tmp);
1da177e Linux-2.6.12-rc2
Linus Torvalds authored
106 }
fee4b19 bitops: remove "optimizations"
Thomas Gleixner authored
107 EXPORT_SYMBOL(find_next_zero_bit);
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
108 #endif
77b9bd9 x86: generic versions of find_first_(zero_)bit, convert i386
Alexander van Heukelum authored
109
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
110 #ifndef find_first_bit
77b9bd9 x86: generic versions of find_first_(zero_)bit, convert i386
Alexander van Heukelum authored
111 /*
112 * Find the first set bit in a memory region.
113 */
fee4b19 bitops: remove "optimizations"
Thomas Gleixner authored
114 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
77b9bd9 x86: generic versions of find_first_(zero_)bit, convert i386
Alexander van Heukelum authored
115 {
116 const unsigned long *p = addr;
117 unsigned long result = 0;
118 unsigned long tmp;
119
120 while (size & ~(BITS_PER_LONG-1)) {
121 if ((tmp = *(p++)))
122 goto found;
123 result += BITS_PER_LONG;
124 size -= BITS_PER_LONG;
125 }
126 if (!size)
127 return result;
128
129 tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
130 if (tmp == 0UL) /* Are any bits set? */
131 return result + size; /* Nope. */
132 found:
133 return result + __ffs(tmp);
134 }
fee4b19 bitops: remove "optimizations"
Thomas Gleixner authored
135 EXPORT_SYMBOL(find_first_bit);
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
136 #endif
77b9bd9 x86: generic versions of find_first_(zero_)bit, convert i386
Alexander van Heukelum authored
137
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
138 #ifndef find_first_zero_bit
77b9bd9 x86: generic versions of find_first_(zero_)bit, convert i386
Alexander van Heukelum authored
139 /*
140 * Find the first cleared bit in a memory region.
141 */
fee4b19 bitops: remove "optimizations"
Thomas Gleixner authored
142 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
77b9bd9 x86: generic versions of find_first_(zero_)bit, convert i386
Alexander van Heukelum authored
143 {
144 const unsigned long *p = addr;
145 unsigned long result = 0;
146 unsigned long tmp;
147
148 while (size & ~(BITS_PER_LONG-1)) {
149 if (~(tmp = *(p++)))
150 goto found;
151 result += BITS_PER_LONG;
152 size -= BITS_PER_LONG;
153 }
154 if (!size)
155 return result;
156
157 tmp = (*p) | (~0UL << size);
158 if (tmp == ~0UL) /* Are any bits zero? */
159 return result + size; /* Nope. */
160 found:
161 return result + ffz(tmp);
162 }
fee4b19 bitops: remove "optimizations"
Thomas Gleixner authored
163 EXPORT_SYMBOL(find_first_zero_bit);
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
164 #endif
930ae74 [PATCH] bitops: generic ext2_{set,clear,test,find_first_zero,find_nex…
Akinobu Mita authored
165
166 #ifdef __BIG_ENDIAN
167
168 /* include/linux/byteorder does not support "unsigned long" type */
169 static inline unsigned long ext2_swabp(const unsigned long * x)
170 {
171 #if BITS_PER_LONG == 64
172 return (unsigned long) __swab64p((u64 *) x);
173 #elif BITS_PER_LONG == 32
174 return (unsigned long) __swab32p((u32 *) x);
175 #else
176 #error BITS_PER_LONG not defined
177 #endif
178 }
179
180 /* include/linux/byteorder doesn't support "unsigned long" type */
181 static inline unsigned long ext2_swab(const unsigned long y)
182 {
183 #if BITS_PER_LONG == 64
184 return (unsigned long) __swab64((u64) y);
185 #elif BITS_PER_LONG == 32
186 return (unsigned long) __swab32((u32) y);
187 #else
188 #error BITS_PER_LONG not defined
189 #endif
190 }
191
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
192 #ifndef find_next_zero_bit_le
a56560b @mita asm-generic: change little-endian bitops to take any pointer types
mita authored
193 unsigned long find_next_zero_bit_le(const void *addr, unsigned
930ae74 [PATCH] bitops: generic ext2_{set,clear,test,find_first_zero,find_nex…
Akinobu Mita authored
194 long size, unsigned long offset)
195 {
a56560b @mita asm-generic: change little-endian bitops to take any pointer types
mita authored
196 const unsigned long *p = addr;
930ae74 [PATCH] bitops: generic ext2_{set,clear,test,find_first_zero,find_nex…
Akinobu Mita authored
197 unsigned long result = offset & ~(BITS_PER_LONG - 1);
198 unsigned long tmp;
199
200 if (offset >= size)
201 return size;
a56560b @mita asm-generic: change little-endian bitops to take any pointer types
mita authored
202 p += BITOP_WORD(offset);
930ae74 [PATCH] bitops: generic ext2_{set,clear,test,find_first_zero,find_nex…
Akinobu Mita authored
203 size -= result;
204 offset &= (BITS_PER_LONG - 1UL);
205 if (offset) {
206 tmp = ext2_swabp(p++);
207 tmp |= (~0UL >> (BITS_PER_LONG - offset));
208 if (size < BITS_PER_LONG)
209 goto found_first;
210 if (~tmp)
211 goto found_middle;
212 size -= BITS_PER_LONG;
213 result += BITS_PER_LONG;
214 }
215
216 while (size & ~(BITS_PER_LONG - 1)) {
217 if (~(tmp = *(p++)))
218 goto found_middle_swap;
219 result += BITS_PER_LONG;
220 size -= BITS_PER_LONG;
221 }
222 if (!size)
223 return result;
224 tmp = ext2_swabp(p);
225 found_first:
226 tmp |= ~0UL << size;
227 if (tmp == ~0UL) /* Are any bits zero? */
228 return result + size; /* Nope. Skip ffz */
229 found_middle:
230 return result + ffz(tmp);
231
232 found_middle_swap:
233 return result + ffz(ext2_swab(tmp));
234 }
c4945b9 @mita asm-generic: rename generic little-endian bitops functions
mita authored
235 EXPORT_SYMBOL(find_next_zero_bit_le);
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
236 #endif
930ae74 [PATCH] bitops: generic ext2_{set,clear,test,find_first_zero,find_nex…
Akinobu Mita authored
237
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
238 #ifndef find_next_bit_le
a56560b @mita asm-generic: change little-endian bitops to take any pointer types
mita authored
239 unsigned long find_next_bit_le(const void *addr, unsigned
aa02ad6 @kvaneesh ext4: Add ext4_find_next_bit()
kvaneesh authored
240 long size, unsigned long offset)
241 {
a56560b @mita asm-generic: change little-endian bitops to take any pointer types
mita authored
242 const unsigned long *p = addr;
aa02ad6 @kvaneesh ext4: Add ext4_find_next_bit()
kvaneesh authored
243 unsigned long result = offset & ~(BITS_PER_LONG - 1);
244 unsigned long tmp;
245
246 if (offset >= size)
247 return size;
a56560b @mita asm-generic: change little-endian bitops to take any pointer types
mita authored
248 p += BITOP_WORD(offset);
aa02ad6 @kvaneesh ext4: Add ext4_find_next_bit()
kvaneesh authored
249 size -= result;
250 offset &= (BITS_PER_LONG - 1UL);
251 if (offset) {
252 tmp = ext2_swabp(p++);
253 tmp &= (~0UL << offset);
254 if (size < BITS_PER_LONG)
255 goto found_first;
256 if (tmp)
257 goto found_middle;
258 size -= BITS_PER_LONG;
259 result += BITS_PER_LONG;
260 }
261
262 while (size & ~(BITS_PER_LONG - 1)) {
263 tmp = *(p++);
264 if (tmp)
265 goto found_middle_swap;
266 result += BITS_PER_LONG;
267 size -= BITS_PER_LONG;
268 }
269 if (!size)
270 return result;
271 tmp = ext2_swabp(p);
272 found_first:
273 tmp &= (~0UL >> (BITS_PER_LONG - size));
274 if (tmp == 0UL) /* Are any bits set? */
275 return result + size; /* Nope. */
276 found_middle:
277 return result + __ffs(tmp);
278
279 found_middle_swap:
280 return result + __ffs(ext2_swab(tmp));
281 }
c4945b9 @mita asm-generic: rename generic little-endian bitops functions
mita authored
282 EXPORT_SYMBOL(find_next_bit_le);
19de85e @mita bitops: add #ifndef for each of find bitops
mita authored
283 #endif
0664996 @mita bitops: introduce CONFIG_GENERIC_FIND_BIT_LE
mita authored
284
930ae74 [PATCH] bitops: generic ext2_{set,clear,test,find_first_zero,find_nex…
Akinobu Mita authored
285 #endif /* __BIG_ENDIAN */
Something went wrong with that request. Please try again.