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