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