x86: change x86 to use generic find_next_bit
[linux-2.6.git] / lib / find_next_bit.c
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 #undef find_next_bit
19 #undef find_next_zero_bit
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)
29 {
30         const unsigned long *p = addr + BITOP_WORD(offset);
31         unsigned long result = offset & ~(BITS_PER_LONG-1);
32         unsigned long tmp;
33
34         if (offset >= size)
35                 return size;
36         size -= result;
37         offset %= BITS_PER_LONG;
38         if (offset) {
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;
53         }
54         if (!size)
55                 return result;
56         tmp = *p;
57
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 }
65
66 EXPORT_SYMBOL(find_next_bit);
67
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;
78
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;
98         }
99         if (!size)
100                 return result;
101         tmp = *p;
102
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);
109 }
110
111 EXPORT_SYMBOL(find_next_zero_bit);
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
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);
226 #endif /* __BIG_ENDIAN */