Commit | Line | Data |
---|---|---|
1da177e4 LT |
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> | |
40234401 | 13 | #include <linux/module.h> |
c7f612cd | 14 | #include <asm/types.h> |
930ae745 | 15 | #include <asm/byteorder.h> |
1da177e4 | 16 | |
c7f612cd | 17 | #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) |
6fd92b63 AH |
18 | #undef find_next_bit |
19 | #undef find_next_zero_bit | |
c7f612cd AM |
20 | |
21 | /** | |
22 | * find_next_bit - find the next set bit in a memory region | |
23 | * @addr: The address to base the search on | |
24 | * @offset: The bitnumber to start searching at | |
25 | * @size: The maximum size to search | |
26 | */ | |
27 | unsigned long find_next_bit(const unsigned long *addr, unsigned long size, | |
28 | unsigned long offset) | |
1da177e4 | 29 | { |
c7f612cd AM |
30 | const unsigned long *p = addr + BITOP_WORD(offset); |
31 | unsigned long result = offset & ~(BITS_PER_LONG-1); | |
1da177e4 LT |
32 | unsigned long tmp; |
33 | ||
c7f612cd AM |
34 | if (offset >= size) |
35 | return size; | |
36 | size -= result; | |
37 | offset %= BITS_PER_LONG; | |
1da177e4 | 38 | if (offset) { |
c7f612cd AM |
39 | tmp = *(p++); |
40 | tmp &= (~0UL << offset); | |
41 | if (size < BITS_PER_LONG) | |
42 | goto found_first; | |
43 | if (tmp) | |
44 | goto found_middle; | |
45 | size -= BITS_PER_LONG; | |
46 | result += BITS_PER_LONG; | |
47 | } | |
48 | while (size & ~(BITS_PER_LONG-1)) { | |
49 | if ((tmp = *(p++))) | |
50 | goto found_middle; | |
51 | result += BITS_PER_LONG; | |
52 | size -= BITS_PER_LONG; | |
1da177e4 | 53 | } |
c7f612cd AM |
54 | if (!size) |
55 | return result; | |
56 | tmp = *p; | |
1da177e4 | 57 | |
c7f612cd AM |
58 | found_first: |
59 | tmp &= (~0UL >> (BITS_PER_LONG - size)); | |
60 | if (tmp == 0UL) /* Are any bits set? */ | |
61 | return result + size; /* Nope. */ | |
62 | found_middle: | |
63 | return result + __ffs(tmp); | |
64 | } | |
1da177e4 | 65 | |
c7f612cd | 66 | EXPORT_SYMBOL(find_next_bit); |
1da177e4 | 67 | |
c7f612cd AM |
68 | /* |
69 | * This implementation of find_{first,next}_zero_bit was stolen from | |
70 | * Linus' asm-alpha/bitops.h. | |
71 | */ | |
72 | unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, | |
73 | unsigned long offset) | |
74 | { | |
75 | const unsigned long *p = addr + BITOP_WORD(offset); | |
76 | unsigned long result = offset & ~(BITS_PER_LONG-1); | |
77 | unsigned long tmp; | |
1da177e4 | 78 | |
c7f612cd AM |
79 | if (offset >= size) |
80 | return size; | |
81 | size -= result; | |
82 | offset %= BITS_PER_LONG; | |
83 | if (offset) { | |
84 | tmp = *(p++); | |
85 | tmp |= ~0UL >> (BITS_PER_LONG - offset); | |
86 | if (size < BITS_PER_LONG) | |
87 | goto found_first; | |
88 | if (~tmp) | |
89 | goto found_middle; | |
90 | size -= BITS_PER_LONG; | |
91 | result += BITS_PER_LONG; | |
92 | } | |
93 | while (size & ~(BITS_PER_LONG-1)) { | |
94 | if (~(tmp = *(p++))) | |
95 | goto found_middle; | |
96 | result += BITS_PER_LONG; | |
97 | size -= BITS_PER_LONG; | |
1da177e4 | 98 | } |
c7f612cd AM |
99 | if (!size) |
100 | return result; | |
101 | tmp = *p; | |
1da177e4 | 102 | |
c7f612cd AM |
103 | found_first: |
104 | tmp |= ~0UL << size; | |
105 | if (tmp == ~0UL) /* Are any bits zero? */ | |
106 | return result + size; /* Nope. */ | |
107 | found_middle: | |
108 | return result + ffz(tmp); | |
1da177e4 | 109 | } |
40234401 | 110 | |
c7f612cd | 111 | EXPORT_SYMBOL(find_next_zero_bit); |
930ae745 AM |
112 | |
113 | #ifdef __BIG_ENDIAN | |
114 | ||
115 | /* include/linux/byteorder does not support "unsigned long" type */ | |
116 | static inline unsigned long ext2_swabp(const unsigned long * x) | |
117 | { | |
118 | #if BITS_PER_LONG == 64 | |
119 | return (unsigned long) __swab64p((u64 *) x); | |
120 | #elif BITS_PER_LONG == 32 | |
121 | return (unsigned long) __swab32p((u32 *) x); | |
122 | #else | |
123 | #error BITS_PER_LONG not defined | |
124 | #endif | |
125 | } | |
126 | ||
127 | /* include/linux/byteorder doesn't support "unsigned long" type */ | |
128 | static inline unsigned long ext2_swab(const unsigned long y) | |
129 | { | |
130 | #if BITS_PER_LONG == 64 | |
131 | return (unsigned long) __swab64((u64) y); | |
132 | #elif BITS_PER_LONG == 32 | |
133 | return (unsigned long) __swab32((u32) y); | |
134 | #else | |
135 | #error BITS_PER_LONG not defined | |
136 | #endif | |
137 | } | |
138 | ||
139 | unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned | |
140 | long size, unsigned long offset) | |
141 | { | |
142 | const unsigned long *p = addr + BITOP_WORD(offset); | |
143 | unsigned long result = offset & ~(BITS_PER_LONG - 1); | |
144 | unsigned long tmp; | |
145 | ||
146 | if (offset >= size) | |
147 | return size; | |
148 | size -= result; | |
149 | offset &= (BITS_PER_LONG - 1UL); | |
150 | if (offset) { | |
151 | tmp = ext2_swabp(p++); | |
152 | tmp |= (~0UL >> (BITS_PER_LONG - offset)); | |
153 | if (size < BITS_PER_LONG) | |
154 | goto found_first; | |
155 | if (~tmp) | |
156 | goto found_middle; | |
157 | size -= BITS_PER_LONG; | |
158 | result += BITS_PER_LONG; | |
159 | } | |
160 | ||
161 | while (size & ~(BITS_PER_LONG - 1)) { | |
162 | if (~(tmp = *(p++))) | |
163 | goto found_middle_swap; | |
164 | result += BITS_PER_LONG; | |
165 | size -= BITS_PER_LONG; | |
166 | } | |
167 | if (!size) | |
168 | return result; | |
169 | tmp = ext2_swabp(p); | |
170 | found_first: | |
171 | tmp |= ~0UL << size; | |
172 | if (tmp == ~0UL) /* Are any bits zero? */ | |
173 | return result + size; /* Nope. Skip ffz */ | |
174 | found_middle: | |
175 | return result + ffz(tmp); | |
176 | ||
177 | found_middle_swap: | |
178 | return result + ffz(ext2_swab(tmp)); | |
179 | } | |
180 | ||
181 | EXPORT_SYMBOL(generic_find_next_zero_le_bit); | |
182 | ||
aa02ad67 AK |
183 | unsigned long generic_find_next_le_bit(const unsigned long *addr, unsigned |
184 | long size, unsigned long offset) | |
185 | { | |
186 | const unsigned long *p = addr + BITOP_WORD(offset); | |
187 | unsigned long result = offset & ~(BITS_PER_LONG - 1); | |
188 | unsigned long tmp; | |
189 | ||
190 | if (offset >= size) | |
191 | return size; | |
192 | size -= result; | |
193 | offset &= (BITS_PER_LONG - 1UL); | |
194 | if (offset) { | |
195 | tmp = ext2_swabp(p++); | |
196 | tmp &= (~0UL << offset); | |
197 | if (size < BITS_PER_LONG) | |
198 | goto found_first; | |
199 | if (tmp) | |
200 | goto found_middle; | |
201 | size -= BITS_PER_LONG; | |
202 | result += BITS_PER_LONG; | |
203 | } | |
204 | ||
205 | while (size & ~(BITS_PER_LONG - 1)) { | |
206 | tmp = *(p++); | |
207 | if (tmp) | |
208 | goto found_middle_swap; | |
209 | result += BITS_PER_LONG; | |
210 | size -= BITS_PER_LONG; | |
211 | } | |
212 | if (!size) | |
213 | return result; | |
214 | tmp = ext2_swabp(p); | |
215 | found_first: | |
216 | tmp &= (~0UL >> (BITS_PER_LONG - size)); | |
217 | if (tmp == 0UL) /* Are any bits set? */ | |
218 | return result + size; /* Nope. */ | |
219 | found_middle: | |
220 | return result + __ffs(tmp); | |
221 | ||
222 | found_middle_swap: | |
223 | return result + __ffs(ext2_swab(tmp)); | |
224 | } | |
225 | EXPORT_SYMBOL(generic_find_next_le_bit); | |
930ae745 | 226 | #endif /* __BIG_ENDIAN */ |