Merge master.kernel.org:/pub/scm/linux/kernel/git/lethal/sh-2.6
[linux-2.6] / 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_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 #endif /* __BIG_ENDIAN */