aboutsummaryrefslogtreecommitdiffstats
path: root/lib/find_next_bit.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/find_next_bit.c')
-rw-r--r--lib/find_next_bit.c177
1 files changed, 150 insertions, 27 deletions
diff --git a/lib/find_next_bit.c b/lib/find_next_bit.c
index c05b4b19cf6c..bda0d71a2514 100644
--- a/lib/find_next_bit.c
+++ b/lib/find_next_bit.c
@@ -11,48 +11,171 @@
11 11
12#include <linux/bitops.h> 12#include <linux/bitops.h>
13#include <linux/module.h> 13#include <linux/module.h>
14#include <asm/types.h>
15#include <asm/byteorder.h>
14 16
15int find_next_bit(const unsigned long *addr, int size, int offset) 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 */
25unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
26 unsigned long offset)
16{ 27{
17 const unsigned long *base; 28 const unsigned long *p = addr + BITOP_WORD(offset);
18 const int NBITS = sizeof(*addr) * 8; 29 unsigned long result = offset & ~(BITS_PER_LONG-1);
19 unsigned long tmp; 30 unsigned long tmp;
20 31
21 base = addr; 32 if (offset >= size)
33 return size;
34 size -= result;
35 offset %= BITS_PER_LONG;
22 if (offset) { 36 if (offset) {
23 int suboffset; 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;
24 55
25 addr += offset / NBITS; 56found_first:
57 tmp &= (~0UL >> (BITS_PER_LONG - size));
58 if (tmp == 0UL) /* Are any bits set? */
59 return result + size; /* Nope. */
60found_middle:
61 return result + __ffs(tmp);
62}
26 63
27 suboffset = offset % NBITS; 64EXPORT_SYMBOL(find_next_bit);
28 if (suboffset) {
29 tmp = *addr;
30 tmp >>= suboffset;
31 if (tmp)
32 goto finish;
33 }
34 65
35 addr++; 66/*
67 * This implementation of find_{first,next}_zero_bit was stolen from
68 * Linus' asm-alpha/bitops.h.
69 */
70unsigned 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;
36 } 96 }
97 if (!size)
98 return result;
99 tmp = *p;
100
101found_first:
102 tmp |= ~0UL << size;
103 if (tmp == ~0UL) /* Are any bits zero? */
104 return result + size; /* Nope. */
105found_middle:
106 return result + ffz(tmp);
107}
108
109EXPORT_SYMBOL(find_next_zero_bit);
37 110
38 while ((tmp = *addr) == 0) 111#ifdef __BIG_ENDIAN
39 addr++;
40 112
41 offset = (addr - base) * NBITS; 113/* include/linux/byteorder does not support "unsigned long" type */
114static 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 */
126static 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}
42 136
43 finish: 137unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned
44 /* count the remaining bits without using __ffs() since that takes a 32-bit arg */ 138 long size, unsigned long offset)
45 while (!(tmp & 0xff)) { 139{
46 offset += 8; 140 const unsigned long *p = addr + BITOP_WORD(offset);
47 tmp >>= 8; 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;
48 } 157 }
49 158
50 while (!(tmp & 1)) { 159 while (size & ~(BITS_PER_LONG - 1)) {
51 offset++; 160 if (~(tmp = *(p++)))
52 tmp >>= 1; 161 goto found_middle_swap;
162 result += BITS_PER_LONG;
163 size -= BITS_PER_LONG;
53 } 164 }
165 if (!size)
166 return result;
167 tmp = ext2_swabp(p);
168found_first:
169 tmp |= ~0UL << size;
170 if (tmp == ~0UL) /* Are any bits zero? */
171 return result + size; /* Nope. Skip ffz */
172found_middle:
173 return result + ffz(tmp);
54 174
55 return offset; 175found_middle_swap:
176 return result + ffz(ext2_swab(tmp));
56} 177}
57 178
58EXPORT_SYMBOL(find_next_bit); 179EXPORT_SYMBOL(generic_find_next_zero_le_bit);
180
181#endif /* __BIG_ENDIAN */
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-17 21:19:40 -0500