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 #include <xen/bitops.h>
12 #include <asm/types.h>
13 #include <asm/byteorder.h>
14
15 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
16
17 #ifndef find_next_bit
18 /*
19 * Find the next set bit in a memory region.
20 */
find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)21 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
22 unsigned long offset)
23 {
24 const unsigned long *p = addr + BITOP_WORD(offset);
25 unsigned long result = offset & ~(BITS_PER_LONG-1);
26 unsigned long tmp;
27
28 if (offset >= size)
29 return size;
30 size -= result;
31 offset %= BITS_PER_LONG;
32 if (offset) {
33 tmp = *(p++);
34 tmp &= (~0UL << offset);
35 if (size < BITS_PER_LONG)
36 goto found_first;
37 if (tmp)
38 goto found_middle;
39 size -= BITS_PER_LONG;
40 result += BITS_PER_LONG;
41 }
42 while (size & ~(BITS_PER_LONG-1)) {
43 if ((tmp = *(p++)))
44 goto found_middle;
45 result += BITS_PER_LONG;
46 size -= BITS_PER_LONG;
47 }
48 if (!size)
49 return result;
50 tmp = *p;
51
52 found_first:
53 tmp &= (~0UL >> (BITS_PER_LONG - size));
54 if (tmp == 0UL) /* Are any bits set? */
55 return result + size; /* Nope. */
56 found_middle:
57 return result + __ffs(tmp);
58 }
59 EXPORT_SYMBOL(find_next_bit);
60 #endif
61
62 #ifndef find_next_zero_bit
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
107
108 #ifndef 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 #endif
135
136 #ifndef find_first_zero_bit
137 /*
138 * Find the first cleared bit in a memory region.
139 */
find_first_zero_bit(const unsigned long * addr,unsigned long size)140 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
141 {
142 const unsigned long *p = addr;
143 unsigned long result = 0;
144 unsigned long tmp;
145
146 while (size & ~(BITS_PER_LONG-1)) {
147 if (~(tmp = *(p++)))
148 goto found;
149 result += BITS_PER_LONG;
150 size -= BITS_PER_LONG;
151 }
152 if (!size)
153 return result;
154
155 tmp = (*p) | (~0UL << size);
156 if (tmp == ~0UL) /* Are any bits zero? */
157 return result + size; /* Nope. */
158 found:
159 return result + ffz(tmp);
160 }
161 EXPORT_SYMBOL(find_first_zero_bit);
162 #endif
163
164 #ifdef __BIG_ENDIAN
165
166 /* include/linux/byteorder does not support "unsigned long" type */
ext2_swabp(const unsigned long * x)167 static inline unsigned long ext2_swabp(const unsigned long * x)
168 {
169 #if BITS_PER_LONG == 64
170 return (unsigned long) __swab64p((u64 *) x);
171 #elif BITS_PER_LONG == 32
172 return (unsigned long) __swab32p((u32 *) x);
173 #else
174 #error BITS_PER_LONG not defined
175 #endif
176 }
177
178 /* include/linux/byteorder doesn't support "unsigned long" type */
ext2_swab(const unsigned long y)179 static inline unsigned long ext2_swab(const unsigned long y)
180 {
181 #if BITS_PER_LONG == 64
182 return (unsigned long) __swab64((u64) y);
183 #elif BITS_PER_LONG == 32
184 return (unsigned long) __swab32((u32) y);
185 #else
186 #error BITS_PER_LONG not defined
187 #endif
188 }
189
190 #ifndef find_next_zero_bit_le
find_next_zero_bit_le(const void * addr,unsigned long size,unsigned long offset)191 unsigned long find_next_zero_bit_le(const void *addr, unsigned
192 long size, unsigned long offset)
193 {
194 const unsigned long *p = addr;
195 unsigned long result = offset & ~(BITS_PER_LONG - 1);
196 unsigned long tmp;
197
198 if (offset >= size)
199 return size;
200 p += BITOP_WORD(offset);
201 size -= result;
202 offset &= (BITS_PER_LONG - 1UL);
203 if (offset) {
204 tmp = ext2_swabp(p++);
205 tmp |= (~0UL >> (BITS_PER_LONG - offset));
206 if (size < BITS_PER_LONG)
207 goto found_first;
208 if (~tmp)
209 goto found_middle;
210 size -= BITS_PER_LONG;
211 result += BITS_PER_LONG;
212 }
213
214 while (size & ~(BITS_PER_LONG - 1)) {
215 if (~(tmp = *(p++)))
216 goto found_middle_swap;
217 result += BITS_PER_LONG;
218 size -= BITS_PER_LONG;
219 }
220 if (!size)
221 return result;
222 tmp = ext2_swabp(p);
223 found_first:
224 tmp |= ~0UL << size;
225 if (tmp == ~0UL) /* Are any bits zero? */
226 return result + size; /* Nope. Skip ffz */
227 found_middle:
228 return result + ffz(tmp);
229
230 found_middle_swap:
231 return result + ffz(ext2_swab(tmp));
232 }
233 EXPORT_SYMBOL(find_next_zero_bit_le);
234 #endif
235
236 #ifndef find_next_bit_le
find_next_bit_le(const void * addr,unsigned long size,unsigned long offset)237 unsigned long find_next_bit_le(const void *addr, unsigned
238 long size, unsigned long offset)
239 {
240 const unsigned long *p = addr;
241 unsigned long result = offset & ~(BITS_PER_LONG - 1);
242 unsigned long tmp;
243
244 if (offset >= size)
245 return size;
246 p += BITOP_WORD(offset);
247 size -= result;
248 offset &= (BITS_PER_LONG - 1UL);
249 if (offset) {
250 tmp = ext2_swabp(p++);
251 tmp &= (~0UL << offset);
252 if (size < BITS_PER_LONG)
253 goto found_first;
254 if (tmp)
255 goto found_middle;
256 size -= BITS_PER_LONG;
257 result += BITS_PER_LONG;
258 }
259
260 while (size & ~(BITS_PER_LONG - 1)) {
261 tmp = *(p++);
262 if (tmp)
263 goto found_middle_swap;
264 result += BITS_PER_LONG;
265 size -= BITS_PER_LONG;
266 }
267 if (!size)
268 return result;
269 tmp = ext2_swabp(p);
270 found_first:
271 tmp &= (~0UL >> (BITS_PER_LONG - size));
272 if (tmp == 0UL) /* Are any bits set? */
273 return result + size; /* Nope. */
274 found_middle:
275 return result + __ffs(tmp);
276
277 found_middle_swap:
278 return result + __ffs(ext2_swab(tmp));
279 }
280 EXPORT_SYMBOL(find_next_bit_le);
281 #endif
282
283 #endif /* __BIG_ENDIAN */
284