1 /* bit search implementation
2 *
3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
5 *
6 * Copyright (C) 2008 IBM Corporation
7 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
8 * (Inspired by David Howell's find_next_bit implementation)
9 *
10 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
11 * size and improve performance, 2015.
12 *
13 * This program is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU General Public License
15 * as published by the Free Software Foundation; either version
16 * 2 of the License, or (at your option) any later version.
17 */
18
19 #include <linux/bitops.h>
20 #include <linux/bitmap.h>
21 #include <linux/export.h>
22 #include <linux/kernel.h>
23
24 #if !defined(find_next_bit) || !defined(find_next_zero_bit)
25
26 /*
27 * This is a common helper function for find_next_bit and
28 * find_next_zero_bit. The difference is the "invert" argument, which
29 * is XORed with each fetched word before searching it for one bits.
30 */
_find_next_bit(const unsigned long * addr,unsigned long nbits,unsigned long start,unsigned long invert)31 static unsigned long _find_next_bit(const unsigned long *addr,
32 unsigned long nbits, unsigned long start, unsigned long invert)
33 {
34 unsigned long tmp;
35
36 if (!nbits || start >= nbits)
37 return nbits;
38
39 tmp = addr[start / BITS_PER_LONG] ^ invert;
40
41 /* Handle 1st word. */
42 tmp &= BITMAP_FIRST_WORD_MASK(start);
43 start = round_down(start, BITS_PER_LONG);
44
45 while (!tmp) {
46 start += BITS_PER_LONG;
47 if (start >= nbits)
48 return nbits;
49
50 tmp = addr[start / BITS_PER_LONG] ^ invert;
51 }
52
53 return min(start + __ffs(tmp), nbits);
54 }
55 #endif
56
57 #ifndef find_next_bit
58 /*
59 * Find the next set bit in a memory region.
60 */
find_next_bit(const unsigned long * addr,unsigned long size,unsigned long offset)61 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
62 unsigned long offset)
63 {
64 return _find_next_bit(addr, size, offset, 0UL);
65 }
66 EXPORT_SYMBOL(find_next_bit);
67 #endif
68
69 #ifndef find_next_zero_bit
find_next_zero_bit(const unsigned long * addr,unsigned long size,unsigned long offset)70 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
71 unsigned long offset)
72 {
73 return _find_next_bit(addr, size, offset, ~0UL);
74 }
75 EXPORT_SYMBOL(find_next_zero_bit);
76 #endif
77
78 #ifndef find_first_bit
79 /*
80 * Find the first set bit in a memory region.
81 */
find_first_bit(const unsigned long * addr,unsigned long size)82 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
83 {
84 unsigned long idx;
85
86 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
87 if (addr[idx])
88 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
89 }
90
91 return size;
92 }
93 EXPORT_SYMBOL(find_first_bit);
94 #endif
95
96 #ifndef find_first_zero_bit
97 /*
98 * Find the first cleared bit in a memory region.
99 */
find_first_zero_bit(const unsigned long * addr,unsigned long size)100 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
101 {
102 unsigned long idx;
103
104 for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
105 if (addr[idx] != ~0UL)
106 return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
107 }
108
109 return size;
110 }
111 EXPORT_SYMBOL(find_first_zero_bit);
112 #endif
113
114 #ifndef find_last_bit
find_last_bit(const unsigned long * addr,unsigned long size)115 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
116 {
117 if (size) {
118 unsigned long val = BITMAP_LAST_WORD_MASK(size);
119 unsigned long idx = (size-1) / BITS_PER_LONG;
120
121 do {
122 val &= addr[idx];
123 if (val)
124 return idx * BITS_PER_LONG + __fls(val);
125
126 val = ~0ul;
127 } while (idx--);
128 }
129 return size;
130 }
131 EXPORT_SYMBOL(find_last_bit);
132 #endif
133
134 #ifdef __BIG_ENDIAN
135
136 /* include/linux/byteorder does not support "unsigned long" type */
ext2_swab(const unsigned long y)137 static inline unsigned long ext2_swab(const unsigned long y)
138 {
139 #if BITS_PER_LONG == 64
140 return (unsigned long) __swab64((u64) y);
141 #elif BITS_PER_LONG == 32
142 return (unsigned long) __swab32((u32) y);
143 #else
144 #error BITS_PER_LONG not defined
145 #endif
146 }
147
148 #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
_find_next_bit_le(const unsigned long * addr,unsigned long nbits,unsigned long start,unsigned long invert)149 static unsigned long _find_next_bit_le(const unsigned long *addr,
150 unsigned long nbits, unsigned long start, unsigned long invert)
151 {
152 unsigned long tmp;
153
154 if (!nbits || start >= nbits)
155 return nbits;
156
157 tmp = addr[start / BITS_PER_LONG] ^ invert;
158
159 /* Handle 1st word. */
160 tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
161 start = round_down(start, BITS_PER_LONG);
162
163 while (!tmp) {
164 start += BITS_PER_LONG;
165 if (start >= nbits)
166 return nbits;
167
168 tmp = addr[start / BITS_PER_LONG] ^ invert;
169 }
170
171 return min(start + __ffs(ext2_swab(tmp)), nbits);
172 }
173 #endif
174
175 #ifndef find_next_zero_bit_le
find_next_zero_bit_le(const void * addr,unsigned long size,unsigned long offset)176 unsigned long find_next_zero_bit_le(const void *addr, unsigned
177 long size, unsigned long offset)
178 {
179 return _find_next_bit_le(addr, size, offset, ~0UL);
180 }
181 EXPORT_SYMBOL(find_next_zero_bit_le);
182 #endif
183
184 #ifndef find_next_bit_le
find_next_bit_le(const void * addr,unsigned long size,unsigned long offset)185 unsigned long find_next_bit_le(const void *addr, unsigned
186 long size, unsigned long offset)
187 {
188 return _find_next_bit_le(addr, size, offset, 0UL);
189 }
190 EXPORT_SYMBOL(find_next_bit_le);
191 #endif
192
193 #endif /* __BIG_ENDIAN */
194