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 /*
 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 
 63 /*
 64  * This implementation of find_{first,next}_zero_bit was stolen from
 65  * Linus' asm-alpha/bitops.h.
 66  */
 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  */
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  */
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 */
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 */
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 
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 
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
This page was automatically generated by LXR 0.3.1. • Linux is a registered trademark of Linus Torvalds
Linux Cross Reference

Free Electrons

Linux/lib/find_next_bit.c
