bitops: add #ifndef for each of find bitops
[linux-3.10.git] / lib / find_next_bit.c
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 #ifndef find_next_bit
21 /*
22  * Find the next set bit in a memory region.
23  */
24 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
25                             unsigned long offset)
26 {
27         const unsigned long *p = addr + BITOP_WORD(offset);
28         unsigned long result = offset & ~(BITS_PER_LONG-1);
29         unsigned long tmp;
30
31         if (offset >= size)
32                 return size;
33         size -= result;
34         offset %= BITS_PER_LONG;
35         if (offset) {
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;
50         }
51         if (!size)
52                 return result;
53         tmp = *p;
54
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 }
62 EXPORT_SYMBOL(find_next_bit);
63 #endif
64
65 #ifndef find_next_zero_bit
66 /*
67  * This implementation of find_{first,next}_zero_bit was stolen from
68  * Linus' asm-alpha/bitops.h.
69  */
70 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
71                                  unsigned long offset)
72 {
73         const unsigned long *p = addr + BITOP_WORD(offset);
74         unsigned long result = offset & ~(BITS_PER_LONG-1);
75         unsigned long tmp;
76
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;
96         }
97         if (!size)
98                 return result;
99         tmp = *p;
100
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);
107 }
108 EXPORT_SYMBOL(find_next_zero_bit);
109 #endif
110 #endif /* CONFIG_GENERIC_FIND_NEXT_BIT */
111
112 #ifdef CONFIG_GENERIC_FIND_FIRST_BIT
113 #ifndef find_first_bit
114 /*
115  * Find the first set bit in a memory region.
116  */
117 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
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 }
138 EXPORT_SYMBOL(find_first_bit);
139 #endif
140
141 #ifndef find_first_zero_bit
142 /*
143  * Find the first cleared bit in a memory region.
144  */
145 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
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 }
166 EXPORT_SYMBOL(find_first_zero_bit);
167 #endif
168 #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
169
170 #ifdef __BIG_ENDIAN
171 #ifdef CONFIG_GENERIC_FIND_BIT_LE
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
197 #ifndef find_next_zero_bit_le
198 unsigned long find_next_zero_bit_le(const void *addr, unsigned
199                 long size, unsigned long offset)
200 {
201         const unsigned long *p = addr;
202         unsigned long result = offset & ~(BITS_PER_LONG - 1);
203         unsigned long tmp;
204
205         if (offset >= size)
206                 return size;
207         p += BITOP_WORD(offset);
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 }
240 EXPORT_SYMBOL(find_next_zero_bit_le);
241 #endif
242
243 #ifndef find_next_bit_le
244 unsigned long find_next_bit_le(const void *addr, unsigned
245                 long size, unsigned long offset)
246 {
247         const unsigned long *p = addr;
248         unsigned long result = offset & ~(BITS_PER_LONG - 1);
249         unsigned long tmp;
250
251         if (offset >= size)
252                 return size;
253         p += BITOP_WORD(offset);
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 }
287 EXPORT_SYMBOL(find_next_bit_le);
288 #endif
289
290 #endif /* CONFIG_GENERIC_FIND_BIT_LE */
291 #endif /* __BIG_ENDIAN */