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/export.h> |
14 | #include <asm/types.h> |
15 | #include <asm/byteorder.h> |
16 | |
17 | #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) |
18 | |
19 | #ifndef 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 | #endif |
63 | |
64 | #ifndef find_next_zero_bit |
65 | /* |
66 | * This implementation of find_{first,next}_zero_bit was stolen from |
67 | * Linus' asm-alpha/bitops.h. |
68 | */ |
69 | unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, |
70 | unsigned long offset) |
71 | { |
72 | const unsigned long *p = addr + BITOP_WORD(offset); |
73 | unsigned long result = offset & ~(BITS_PER_LONG-1); |
74 | unsigned long tmp; |
75 | |
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; |
95 | } |
96 | if (!size) |
97 | return result; |
98 | tmp = *p; |
99 | |
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); |
106 | } |
107 | EXPORT_SYMBOL(find_next_zero_bit); |
108 | #endif |
109 | |
110 | #ifndef find_first_bit |
111 | /* |
112 | * Find the first set bit in a memory region. |
113 | */ |
114 | unsigned long find_first_bit(const unsigned long *addr, unsigned long size) |
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 | } |
135 | EXPORT_SYMBOL(find_first_bit); |
136 | #endif |
137 | |
138 | #ifndef find_first_zero_bit |
139 | /* |
140 | * Find the first cleared bit in a memory region. |
141 | */ |
142 | unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) |
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 | } |
163 | EXPORT_SYMBOL(find_first_zero_bit); |
164 | #endif |
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 | |
192 | #ifndef find_next_zero_bit_le |
193 | unsigned long find_next_zero_bit_le(const void *addr, unsigned |
194 | long size, unsigned long offset) |
195 | { |
196 | const unsigned long *p = addr; |
197 | unsigned long result = offset & ~(BITS_PER_LONG - 1); |
198 | unsigned long tmp; |
199 | |
200 | if (offset >= size) |
201 | return size; |
202 | p += BITOP_WORD(offset); |
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 | } |
235 | EXPORT_SYMBOL(find_next_zero_bit_le); |
236 | #endif |
237 | |
238 | #ifndef find_next_bit_le |
239 | unsigned long find_next_bit_le(const void *addr, unsigned |
240 | long size, unsigned long offset) |
241 | { |
242 | const unsigned long *p = addr; |
243 | unsigned long result = offset & ~(BITS_PER_LONG - 1); |
244 | unsigned long tmp; |
245 | |
246 | if (offset >= size) |
247 | return size; |
248 | p += BITOP_WORD(offset); |
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 | } |
282 | EXPORT_SYMBOL(find_next_bit_le); |
283 | #endif |
284 | |
285 | #endif /* __BIG_ENDIAN */ |
286 |
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