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 */
find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)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 */
find_next_zero_bit(const unsigned long * addr,unsigned long size,unsigned long offset)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 */
find_first_bit(const unsigned long * addr,unsigned long size)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 */
find_first_zero_bit(const unsigned long * addr,unsigned long size)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 */
ext2_swabp(const unsigned long * x)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 */
ext2_swab(const unsigned long y)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
generic_find_next_zero_le_bit(const unsigned long * addr,unsigned long size,unsigned long offset)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
generic_find_next_le_bit(const unsigned long * addr,unsigned long size,unsigned long offset)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