Root/
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> |
13 | #include <linux/module.h> |
14 | #include <asm/types.h> |
15 | #include <asm/byteorder.h> |
16 | |
17 | #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) |
18 | |
19 | #ifdef CONFIG_GENERIC_FIND_NEXT_BIT |
20 | /* |
21 | * Find the next set bit in a memory region. |
22 | */ |
23 | unsigned long find_next_bit(const unsigned long *addr, unsigned long size, |
24 | unsigned long offset) |
25 | { |
26 | const unsigned long *p = addr + BITOP_WORD(offset); |
27 | unsigned long result = offset & ~(BITS_PER_LONG-1); |
28 | unsigned long tmp; |
29 | |
30 | if (offset >= size) |
31 | return size; |
32 | size -= result; |
33 | offset %= BITS_PER_LONG; |
34 | if (offset) { |
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; |
49 | } |
50 | if (!size) |
51 | return result; |
52 | tmp = *p; |
53 | |
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 | } |
61 | EXPORT_SYMBOL(find_next_bit); |
62 | |
63 | /* |
64 | * This implementation of find_{first,next}_zero_bit was stolen from |
65 | * Linus' asm-alpha/bitops.h. |
66 | */ |
67 | unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, |
68 | unsigned long offset) |
69 | { |
70 | const unsigned long *p = addr + BITOP_WORD(offset); |
71 | unsigned long result = offset & ~(BITS_PER_LONG-1); |
72 | unsigned long tmp; |
73 | |
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; |
93 | } |
94 | if (!size) |
95 | return result; |
96 | tmp = *p; |
97 | |
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); |
104 | } |
105 | EXPORT_SYMBOL(find_next_zero_bit); |
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 | */ |
112 | unsigned long find_first_bit(const unsigned long *addr, unsigned long size) |
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 | } |
133 | EXPORT_SYMBOL(find_first_bit); |
134 | |
135 | /* |
136 | * Find the first cleared bit in a memory region. |
137 | */ |
138 | unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) |
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 | } |
159 | EXPORT_SYMBOL(find_first_zero_bit); |
160 | #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ |
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 | |
188 | unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned |
189 | long size, unsigned long offset) |
190 | { |
191 | const unsigned long *p = addr + BITOP_WORD(offset); |
192 | unsigned long result = offset & ~(BITS_PER_LONG - 1); |
193 | unsigned long tmp; |
194 | |
195 | if (offset >= size) |
196 | return size; |
197 | size -= result; |
198 | offset &= (BITS_PER_LONG - 1UL); |
199 | if (offset) { |
200 | tmp = ext2_swabp(p++); |
201 | tmp |= (~0UL >> (BITS_PER_LONG - offset)); |
202 | if (size < BITS_PER_LONG) |
203 | goto found_first; |
204 | if (~tmp) |
205 | goto found_middle; |
206 | size -= BITS_PER_LONG; |
207 | result += BITS_PER_LONG; |
208 | } |
209 | |
210 | while (size & ~(BITS_PER_LONG - 1)) { |
211 | if (~(tmp = *(p++))) |
212 | goto found_middle_swap; |
213 | result += BITS_PER_LONG; |
214 | size -= BITS_PER_LONG; |
215 | } |
216 | if (!size) |
217 | return result; |
218 | tmp = ext2_swabp(p); |
219 | found_first: |
220 | tmp |= ~0UL << size; |
221 | if (tmp == ~0UL) /* Are any bits zero? */ |
222 | return result + size; /* Nope. Skip ffz */ |
223 | found_middle: |
224 | return result + ffz(tmp); |
225 | |
226 | found_middle_swap: |
227 | return result + ffz(ext2_swab(tmp)); |
228 | } |
229 | |
230 | EXPORT_SYMBOL(generic_find_next_zero_le_bit); |
231 | |
232 | unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned |
233 | long size, unsigned long offset) |
234 | { |
235 | const unsigned long *p = addr + BITOP_WORD(offset); |
236 | unsigned long result = offset & ~(BITS_PER_LONG - 1); |
237 | unsigned long tmp; |
238 | |
239 | if (offset >= size) |
240 | return size; |
241 | size -= result; |
242 | offset &= (BITS_PER_LONG - 1UL); |
243 | if (offset) { |
244 | tmp = ext2_swabp(p++); |
245 | tmp &= (~0UL << offset); |
246 | if (size < BITS_PER_LONG) |
247 | goto found_first; |
248 | if (tmp) |
249 | goto found_middle; |
250 | size -= BITS_PER_LONG; |
251 | result += BITS_PER_LONG; |
252 | } |
253 | |
254 | while (size & ~(BITS_PER_LONG - 1)) { |
255 | tmp = *(p++); |
256 | if (tmp) |
257 | goto found_middle_swap; |
258 | result += BITS_PER_LONG; |
259 | size -= BITS_PER_LONG; |
260 | } |
261 | if (!size) |
262 | return result; |
263 | tmp = ext2_swabp(p); |
264 | found_first: |
265 | tmp &= (~0UL >> (BITS_PER_LONG - size)); |
266 | if (tmp == 0UL) /* Are any bits set? */ |
267 | return result + size; /* Nope. */ |
268 | found_middle: |
269 | return result + __ffs(tmp); |
270 | |
271 | found_middle_swap: |
272 | return result + __ffs(ext2_swab(tmp)); |
273 | } |
274 | EXPORT_SYMBOL(generic_find_next_le_bit); |
275 | #endif /* __BIG_ENDIAN */ |
276 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9