x86, generic: optimize find_next_(zero_)bit for small constant-size bitmaps
[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
19 /*
20  * Find the next set bit in a memory region.
21  */
22 unsigned long __find_next_bit(const unsigned long *addr,
23                 unsigned long size, unsigned long offset)
24 {
25         const unsigned long *p = addr + BITOP_WORD(offset);
26         unsigned long result = offset & ~(BITS_PER_LONG-1);
27         unsigned long tmp;
28
29         if (offset >= size)
30                 return size;
31         size -= result;
32         offset %= BITS_PER_LONG;
33         if (offset) {
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;
48         }
49         if (!size)
50                 return result;
51         tmp = *p;
52
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 }
60 EXPORT_SYMBOL(__find_next_bit);
61
62 /*
63  * This implementation of find_{first,next}_zero_bit was stolen from
64  * Linus' asm-alpha/bitops.h.
65  */
66 unsigned long __find_next_zero_bit(const unsigned long *addr,
67                 unsigned long size, unsigned long offset)
68 {
69         const unsigned long *p = addr + BITOP_WORD(offset);
70         unsigned long result = offset & ~(BITS_PER_LONG-1);
71         unsigned long tmp;
72
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;
92         }
93         if (!size)
94                 return result;
95         tmp = *p;
96
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);
103 }
104 EXPORT_SYMBOL(__find_next_zero_bit);
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
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);
219 #endif /* __BIG_ENDIAN */