blob: 4bd75a73ba0041c0e4607e4c292c10f37ff343a2 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/* 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>
David Howells40234402006-01-08 01:01:19 -080013#include <linux/module.h>
Akinobu Mitac7f612c2006-03-26 01:39:11 -080014#include <asm/types.h>
Akinobu Mita930ae742006-03-26 01:39:15 -080015#include <asm/byteorder.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070016
Akinobu Mitac7f612c2006-03-26 01:39:11 -080017#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
18
Akinobu Mita19de85e2011-05-26 16:26:09 -070019#ifndef find_next_bit
Alexander van Heukelum64970b62008-03-11 16:17:19 +010020/*
21 * Find the next set bit in a memory region.
Akinobu Mitac7f612c2006-03-26 01:39:11 -080022 */
Thomas Gleixnerfee4b192008-04-29 12:01:02 +020023unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
24 unsigned long offset)
Linus Torvalds1da177e2005-04-16 15:20:36 -070025{
Akinobu Mitac7f612c2006-03-26 01:39:11 -080026 const unsigned long *p = addr + BITOP_WORD(offset);
27 unsigned long result = offset & ~(BITS_PER_LONG-1);
Linus Torvalds1da177e2005-04-16 15:20:36 -070028 unsigned long tmp;
29
Akinobu Mitac7f612c2006-03-26 01:39:11 -080030 if (offset >= size)
31 return size;
32 size -= result;
33 offset %= BITS_PER_LONG;
Linus Torvalds1da177e2005-04-16 15:20:36 -070034 if (offset) {
Akinobu Mitac7f612c2006-03-26 01:39:11 -080035 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -070043 }
Akinobu Mitac7f612c2006-03-26 01:39:11 -080044 while (size & ~(BITS_PER_LONG-1)) {
45 if ((tmp = *(p++)))
46 goto found_middle;
47 result += BITS_PER_LONG;
48 size -= BITS_PER_LONG;
Linus Torvalds1da177e2005-04-16 15:20:36 -070049 }
Akinobu Mitac7f612c2006-03-26 01:39:11 -080050 if (!size)
51 return result;
52 tmp = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -070053
Akinobu Mitac7f612c2006-03-26 01:39:11 -080054found_first:
55 tmp &= (~0UL >> (BITS_PER_LONG - size));
56 if (tmp == 0UL) /* Are any bits set? */
57 return result + size; /* Nope. */
58found_middle:
59 return result + __ffs(tmp);
Linus Torvalds1da177e2005-04-16 15:20:36 -070060}
Thomas Gleixnerfee4b192008-04-29 12:01:02 +020061EXPORT_SYMBOL(find_next_bit);
Akinobu Mita19de85e2011-05-26 16:26:09 -070062#endif
Akinobu Mitac7f612c2006-03-26 01:39:11 -080063
Akinobu Mita19de85e2011-05-26 16:26:09 -070064#ifndef find_next_zero_bit
Akinobu Mitac7f612c2006-03-26 01:39:11 -080065/*
66 * This implementation of find_{first,next}_zero_bit was stolen from
67 * Linus' asm-alpha/bitops.h.
68 */
Thomas Gleixnerfee4b192008-04-29 12:01:02 +020069unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
70 unsigned long offset)
Akinobu Mitac7f612c2006-03-26 01:39:11 -080071{
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
100found_first:
101 tmp |= ~0UL << size;
102 if (tmp == ~0UL) /* Are any bits zero? */
103 return result + size; /* Nope. */
104found_middle:
105 return result + ffz(tmp);
106}
Thomas Gleixnerfee4b192008-04-29 12:01:02 +0200107EXPORT_SYMBOL(find_next_zero_bit);
Akinobu Mita19de85e2011-05-26 16:26:09 -0700108#endif
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200109
Akinobu Mita19de85e2011-05-26 16:26:09 -0700110#ifndef find_first_bit
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200111/*
112 * Find the first set bit in a memory region.
113 */
Thomas Gleixnerfee4b192008-04-29 12:01:02 +0200114unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200115{
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. */
132found:
133 return result + __ffs(tmp);
134}
Thomas Gleixnerfee4b192008-04-29 12:01:02 +0200135EXPORT_SYMBOL(find_first_bit);
Akinobu Mita19de85e2011-05-26 16:26:09 -0700136#endif
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200137
Akinobu Mita19de85e2011-05-26 16:26:09 -0700138#ifndef find_first_zero_bit
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200139/*
140 * Find the first cleared bit in a memory region.
141 */
Thomas Gleixnerfee4b192008-04-29 12:01:02 +0200142unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
Alexander van Heukelum77b9bd92008-04-01 11:46:19 +0200143{
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. */
160found:
161 return result + ffz(tmp);
162}
Thomas Gleixnerfee4b192008-04-29 12:01:02 +0200163EXPORT_SYMBOL(find_first_zero_bit);
Akinobu Mita19de85e2011-05-26 16:26:09 -0700164#endif
Akinobu Mita930ae742006-03-26 01:39:15 -0800165
166#ifdef __BIG_ENDIAN
167
168/* include/linux/byteorder does not support "unsigned long" type */
169static 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 */
181static 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
Akinobu Mita19de85e2011-05-26 16:26:09 -0700192#ifndef find_next_zero_bit_le
Akinobu Mitaa56560b2011-03-23 16:41:50 -0700193unsigned long find_next_zero_bit_le(const void *addr, unsigned
Akinobu Mita930ae742006-03-26 01:39:15 -0800194 long size, unsigned long offset)
195{
Akinobu Mitaa56560b2011-03-23 16:41:50 -0700196 const unsigned long *p = addr;
Akinobu Mita930ae742006-03-26 01:39:15 -0800197 unsigned long result = offset & ~(BITS_PER_LONG - 1);
198 unsigned long tmp;
199
200 if (offset >= size)
201 return size;
Akinobu Mitaa56560b2011-03-23 16:41:50 -0700202 p += BITOP_WORD(offset);
Akinobu Mita930ae742006-03-26 01:39:15 -0800203 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);
225found_first:
226 tmp |= ~0UL << size;
227 if (tmp == ~0UL) /* Are any bits zero? */
228 return result + size; /* Nope. Skip ffz */
229found_middle:
230 return result + ffz(tmp);
231
232found_middle_swap:
233 return result + ffz(ext2_swab(tmp));
234}
Akinobu Mitac4945b92011-03-23 16:41:47 -0700235EXPORT_SYMBOL(find_next_zero_bit_le);
Akinobu Mita19de85e2011-05-26 16:26:09 -0700236#endif
Akinobu Mita930ae742006-03-26 01:39:15 -0800237
Akinobu Mita19de85e2011-05-26 16:26:09 -0700238#ifndef find_next_bit_le
Akinobu Mitaa56560b2011-03-23 16:41:50 -0700239unsigned long find_next_bit_le(const void *addr, unsigned
Aneesh Kumar K.Vaa02ad62008-01-28 23:58:27 -0500240 long size, unsigned long offset)
241{
Akinobu Mitaa56560b2011-03-23 16:41:50 -0700242 const unsigned long *p = addr;
Aneesh Kumar K.Vaa02ad62008-01-28 23:58:27 -0500243 unsigned long result = offset & ~(BITS_PER_LONG - 1);
244 unsigned long tmp;
245
246 if (offset >= size)
247 return size;
Akinobu Mitaa56560b2011-03-23 16:41:50 -0700248 p += BITOP_WORD(offset);
Aneesh Kumar K.Vaa02ad62008-01-28 23:58:27 -0500249 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);
272found_first:
273 tmp &= (~0UL >> (BITS_PER_LONG - size));
274 if (tmp == 0UL) /* Are any bits set? */
275 return result + size; /* Nope. */
276found_middle:
277 return result + __ffs(tmp);
278
279found_middle_swap:
280 return result + __ffs(ext2_swab(tmp));
281}
Akinobu Mitac4945b92011-03-23 16:41:47 -0700282EXPORT_SYMBOL(find_next_bit_le);
Akinobu Mita19de85e2011-05-26 16:26:09 -0700283#endif
Akinobu Mita06649962011-03-23 16:41:59 -0700284
Akinobu Mita930ae742006-03-26 01:39:15 -0800285#endif /* __BIG_ENDIAN */