1 /* find_next_bit.c: fallback find next bit implementation
3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
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.
12 #include <linux/bitops.h>
13 #include <linux/module.h>
14 #include <asm/types.h>
15 #include <asm/byteorder.h>
17 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
19 #ifdef CONFIG_GENERIC_FIND_NEXT_BIT
22 * Find the next set bit in a memory region.
24 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
27 const unsigned long *p = addr + BITOP_WORD(offset);
28 unsigned long result = offset & ~(BITS_PER_LONG-1);
34 offset %= BITS_PER_LONG;
37 tmp &= (~0UL << offset);
38 if (size < BITS_PER_LONG)
42 size -= BITS_PER_LONG;
43 result += BITS_PER_LONG;
45 while (size & ~(BITS_PER_LONG-1)) {
48 result += BITS_PER_LONG;
49 size -= BITS_PER_LONG;
56 tmp &= (~0UL >> (BITS_PER_LONG - size));
57 if (tmp == 0UL) /* Are any bits set? */
58 return result + size; /* Nope. */
60 return result + __ffs(tmp);
62 EXPORT_SYMBOL(find_next_bit);
65 #ifndef find_next_zero_bit
67 * This implementation of find_{first,next}_zero_bit was stolen from
68 * Linus' asm-alpha/bitops.h.
70 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
73 const unsigned long *p = addr + BITOP_WORD(offset);
74 unsigned long result = offset & ~(BITS_PER_LONG-1);
80 offset %= BITS_PER_LONG;
83 tmp |= ~0UL >> (BITS_PER_LONG - offset);
84 if (size < BITS_PER_LONG)
88 size -= BITS_PER_LONG;
89 result += BITS_PER_LONG;
91 while (size & ~(BITS_PER_LONG-1)) {
94 result += BITS_PER_LONG;
95 size -= BITS_PER_LONG;
103 if (tmp == ~0UL) /* Are any bits zero? */
104 return result + size; /* Nope. */
106 return result + ffz(tmp);
108 EXPORT_SYMBOL(find_next_zero_bit);
110 #endif /* CONFIG_GENERIC_FIND_NEXT_BIT */
112 #ifdef CONFIG_GENERIC_FIND_FIRST_BIT
113 #ifndef find_first_bit
115 * Find the first set bit in a memory region.
117 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
119 const unsigned long *p = addr;
120 unsigned long result = 0;
123 while (size & ~(BITS_PER_LONG-1)) {
126 result += BITS_PER_LONG;
127 size -= BITS_PER_LONG;
132 tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
133 if (tmp == 0UL) /* Are any bits set? */
134 return result + size; /* Nope. */
136 return result + __ffs(tmp);
138 EXPORT_SYMBOL(find_first_bit);
141 #ifndef find_first_zero_bit
143 * Find the first cleared bit in a memory region.
145 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
147 const unsigned long *p = addr;
148 unsigned long result = 0;
151 while (size & ~(BITS_PER_LONG-1)) {
154 result += BITS_PER_LONG;
155 size -= BITS_PER_LONG;
160 tmp = (*p) | (~0UL << size);
161 if (tmp == ~0UL) /* Are any bits zero? */
162 return result + size; /* Nope. */
164 return result + ffz(tmp);
166 EXPORT_SYMBOL(find_first_zero_bit);
168 #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
171 #ifdef CONFIG_GENERIC_FIND_BIT_LE
173 /* include/linux/byteorder does not support "unsigned long" type */
174 static inline unsigned long ext2_swabp(const unsigned long * x)
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);
181 #error BITS_PER_LONG not defined
185 /* include/linux/byteorder doesn't support "unsigned long" type */
186 static inline unsigned long ext2_swab(const unsigned long y)
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);
193 #error BITS_PER_LONG not defined
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)
201 const unsigned long *p = addr;
202 unsigned long result = offset & ~(BITS_PER_LONG - 1);
207 p += BITOP_WORD(offset);
209 offset &= (BITS_PER_LONG - 1UL);
211 tmp = ext2_swabp(p++);
212 tmp |= (~0UL >> (BITS_PER_LONG - offset));
213 if (size < BITS_PER_LONG)
217 size -= BITS_PER_LONG;
218 result += BITS_PER_LONG;
221 while (size & ~(BITS_PER_LONG - 1)) {
223 goto found_middle_swap;
224 result += BITS_PER_LONG;
225 size -= BITS_PER_LONG;
232 if (tmp == ~0UL) /* Are any bits zero? */
233 return result + size; /* Nope. Skip ffz */
235 return result + ffz(tmp);
238 return result + ffz(ext2_swab(tmp));
240 EXPORT_SYMBOL(find_next_zero_bit_le);
243 #ifndef find_next_bit_le
244 unsigned long find_next_bit_le(const void *addr, unsigned
245 long size, unsigned long offset)
247 const unsigned long *p = addr;
248 unsigned long result = offset & ~(BITS_PER_LONG - 1);
253 p += BITOP_WORD(offset);
255 offset &= (BITS_PER_LONG - 1UL);
257 tmp = ext2_swabp(p++);
258 tmp &= (~0UL << offset);
259 if (size < BITS_PER_LONG)
263 size -= BITS_PER_LONG;
264 result += BITS_PER_LONG;
267 while (size & ~(BITS_PER_LONG - 1)) {
270 goto found_middle_swap;
271 result += BITS_PER_LONG;
272 size -= BITS_PER_LONG;
278 tmp &= (~0UL >> (BITS_PER_LONG - size));
279 if (tmp == 0UL) /* Are any bits set? */
280 return result + size; /* Nope. */
282 return result + __ffs(tmp);
285 return result + __ffs(ext2_swab(tmp));
287 EXPORT_SYMBOL(find_next_bit_le);
290 #endif /* CONFIG_GENERIC_FIND_BIT_LE */
291 #endif /* __BIG_ENDIAN */