dynamic_debug: remove unneeded includes
[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/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 */