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 #include <xen/bitops.h>
12 #include <xen/byteorder.h>
13
14 #define __ffs(x) (ffsl(x) - 1)
15 #define ffz(x) __ffs(~(x))
16
17 #ifndef find_next_bit
18 /*
19 * Find the next set bit in a memory region.
20 */
find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)21 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
22 unsigned long offset)
23 {
24 const unsigned long *p = addr + BIT_WORD(offset);
25 unsigned long result = offset & ~(BITS_PER_LONG-1);
26 unsigned long tmp;
27
28 if (offset >= size)
29 return size;
30 size -= result;
31 offset %= BITS_PER_LONG;
32 if (offset) {
33 tmp = *(p++);
34 tmp &= (~0UL << offset);
35 if (size < BITS_PER_LONG)
36 goto found_first;
37 if (tmp)
38 goto found_middle;
39 size -= BITS_PER_LONG;
40 result += BITS_PER_LONG;
41 }
42 while (size & ~(BITS_PER_LONG-1)) {
43 if ((tmp = *(p++)))
44 goto found_middle;
45 result += BITS_PER_LONG;
46 size -= BITS_PER_LONG;
47 }
48 if (!size)
49 return result;
50 tmp = *p;
51
52 found_first:
53 tmp &= (~0UL >> (BITS_PER_LONG - size));
54 if (tmp == 0UL) /* Are any bits set? */
55 return result + size; /* Nope. */
56 found_middle:
57 return result + __ffs(tmp);
58 }
59 EXPORT_SYMBOL(find_next_bit);
60 #endif
61
62 #ifndef find_next_zero_bit
63 /*
64 * This implementation of find_{first,next}_zero_bit was stolen from
65 * Linus' asm-alpha/bitops.h.
66 */
find_next_zero_bit(const unsigned long * addr,unsigned long size,unsigned long offset)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 + BIT_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
107
108 #ifndef find_first_bit
109 /*
110 * Find the first set bit in a memory region.
111 */
find_first_bit(const unsigned long * addr,unsigned long size)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 #endif
135
136 #ifndef find_first_zero_bit
137 /*
138 * Find the first cleared bit in a memory region.
139 */
find_first_zero_bit(const unsigned long * addr,unsigned long size)140 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
141 {
142 const unsigned long *p = addr;
143 unsigned long result = 0;
144 unsigned long tmp;
145
146 while (size & ~(BITS_PER_LONG-1)) {
147 if (~(tmp = *(p++)))
148 goto found;
149 result += BITS_PER_LONG;
150 size -= BITS_PER_LONG;
151 }
152 if (!size)
153 return result;
154
155 tmp = (*p) | (~0UL << size);
156 if (tmp == ~0UL) /* Are any bits zero? */
157 return result + size; /* Nope. */
158 found:
159 return result + ffz(tmp);
160 }
161 EXPORT_SYMBOL(find_first_zero_bit);
162 #endif
163
164 #ifdef __BIG_ENDIAN
165
166 #ifndef find_next_zero_bit_le
find_next_zero_bit_le(const void * addr,unsigned long size,unsigned long offset)167 unsigned long find_next_zero_bit_le(const void *addr, unsigned
168 long size, unsigned long offset)
169 {
170 const unsigned long *p = addr;
171 unsigned long result = offset & ~(BITS_PER_LONG - 1);
172 unsigned long tmp;
173
174 if (offset >= size)
175 return size;
176 p += BIT_WORD(offset);
177 size -= result;
178 offset &= (BITS_PER_LONG - 1UL);
179 if (offset) {
180 tmp = bswapl(*p++);
181 tmp |= (~0UL >> (BITS_PER_LONG - offset));
182 if (size < BITS_PER_LONG)
183 goto found_first;
184 if (~tmp)
185 goto found_middle;
186 size -= BITS_PER_LONG;
187 result += BITS_PER_LONG;
188 }
189
190 while (size & ~(BITS_PER_LONG - 1)) {
191 if (~(tmp = *(p++)))
192 goto found_middle_swap;
193 result += BITS_PER_LONG;
194 size -= BITS_PER_LONG;
195 }
196 if (!size)
197 return result;
198 tmp = bswapl(*p);
199 found_first:
200 tmp |= ~0UL << size;
201 if (tmp == ~0UL) /* Are any bits zero? */
202 return result + size; /* Nope. Skip ffz */
203 found_middle:
204 return result + ffz(tmp);
205
206 found_middle_swap:
207 return result + ffz(bswapl(tmp));
208 }
209 EXPORT_SYMBOL(find_next_zero_bit_le);
210 #endif
211
212 #ifndef find_next_bit_le
find_next_bit_le(const void * addr,unsigned long size,unsigned long offset)213 unsigned long find_next_bit_le(const void *addr, unsigned
214 long size, unsigned long offset)
215 {
216 const unsigned long *p = addr;
217 unsigned long result = offset & ~(BITS_PER_LONG - 1);
218 unsigned long tmp;
219
220 if (offset >= size)
221 return size;
222 p += BIT_WORD(offset);
223 size -= result;
224 offset &= (BITS_PER_LONG - 1UL);
225 if (offset) {
226 tmp = bswapl(*p++);
227 tmp &= (~0UL << offset);
228 if (size < BITS_PER_LONG)
229 goto found_first;
230 if (tmp)
231 goto found_middle;
232 size -= BITS_PER_LONG;
233 result += BITS_PER_LONG;
234 }
235
236 while (size & ~(BITS_PER_LONG - 1)) {
237 tmp = *(p++);
238 if (tmp)
239 goto found_middle_swap;
240 result += BITS_PER_LONG;
241 size -= BITS_PER_LONG;
242 }
243 if (!size)
244 return result;
245 tmp = bswapl(*p);
246 found_first:
247 tmp &= (~0UL >> (BITS_PER_LONG - size));
248 if (tmp == 0UL) /* Are any bits set? */
249 return result + size; /* Nope. */
250 found_middle:
251 return result + __ffs(tmp);
252
253 found_middle_swap:
254 return result + __ffs(bswapl(tmp));
255 }
256 EXPORT_SYMBOL(find_next_bit_le);
257 #endif
258
259 #endif /* __BIG_ENDIAN */
260