Commit | Line | Data |
---|---|---|
2874c5fd | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
8f6f19dd | 2 | /* bit search implementation |
1da177e4 LT |
3 | * |
4 | * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. | |
5 | * Written by David Howells (dhowells@redhat.com) | |
6 | * | |
8f6f19dd YN |
7 | * Copyright (C) 2008 IBM Corporation |
8 | * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au> | |
9 | * (Inspired by David Howell's find_next_bit implementation) | |
10 | * | |
2c57a0e2 YN |
11 | * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease |
12 | * size and improve performance, 2015. | |
1da177e4 LT |
13 | */ |
14 | ||
15 | #include <linux/bitops.h> | |
8f6f19dd | 16 | #include <linux/bitmap.h> |
8bc3bcc9 | 17 | #include <linux/export.h> |
aa6159ab | 18 | #include <linux/math.h> |
b296a6d5 | 19 | #include <linux/minmax.h> |
aa6159ab | 20 | #include <linux/swab.h> |
1da177e4 | 21 | |
b78c5713 YN |
22 | #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ |
23 | !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \ | |
24 | !defined(find_next_and_bit) | |
64970b68 | 25 | /* |
0ade34c3 CC |
26 | * This is a common helper function for find_next_bit, find_next_zero_bit, and |
27 | * find_next_and_bit. The differences are: | |
28 | * - The "invert" argument, which is XORed with each fetched word before | |
29 | * searching it for one bits. | |
30 | * - The optional "addr2", which is anded with "addr1" if present. | |
c7f612cd | 31 | */ |
7dfaa98f | 32 | static unsigned long _find_next_bit(const unsigned long *addr1, |
0ade34c3 | 33 | const unsigned long *addr2, unsigned long nbits, |
b78c5713 | 34 | unsigned long start, unsigned long invert, unsigned long le) |
1da177e4 | 35 | { |
b78c5713 | 36 | unsigned long tmp, mask; |
1da177e4 | 37 | |
e4afd2e5 | 38 | if (unlikely(start >= nbits)) |
2c57a0e2 YN |
39 | return nbits; |
40 | ||
0ade34c3 CC |
41 | tmp = addr1[start / BITS_PER_LONG]; |
42 | if (addr2) | |
43 | tmp &= addr2[start / BITS_PER_LONG]; | |
44 | tmp ^= invert; | |
2c57a0e2 YN |
45 | |
46 | /* Handle 1st word. */ | |
b78c5713 YN |
47 | mask = BITMAP_FIRST_WORD_MASK(start); |
48 | if (le) | |
49 | mask = swab(mask); | |
50 | ||
51 | tmp &= mask; | |
52 | ||
2c57a0e2 YN |
53 | start = round_down(start, BITS_PER_LONG); |
54 | ||
55 | while (!tmp) { | |
56 | start += BITS_PER_LONG; | |
57 | if (start >= nbits) | |
58 | return nbits; | |
59 | ||
0ade34c3 CC |
60 | tmp = addr1[start / BITS_PER_LONG]; |
61 | if (addr2) | |
62 | tmp &= addr2[start / BITS_PER_LONG]; | |
63 | tmp ^= invert; | |
1da177e4 LT |
64 | } |
65 | ||
b78c5713 YN |
66 | if (le) |
67 | tmp = swab(tmp); | |
68 | ||
2c57a0e2 | 69 | return min(start + __ffs(tmp), nbits); |
c7f612cd | 70 | } |
19de85ef | 71 | #endif |
1da177e4 | 72 | |
2c57a0e2 | 73 | #ifndef find_next_bit |
c7f612cd | 74 | /* |
2c57a0e2 | 75 | * Find the next set bit in a memory region. |
c7f612cd | 76 | */ |
2c57a0e2 YN |
77 | unsigned long find_next_bit(const unsigned long *addr, unsigned long size, |
78 | unsigned long offset) | |
79 | { | |
b78c5713 | 80 | return _find_next_bit(addr, NULL, size, offset, 0UL, 0); |
2c57a0e2 YN |
81 | } |
82 | EXPORT_SYMBOL(find_next_bit); | |
83 | #endif | |
84 | ||
85 | #ifndef find_next_zero_bit | |
fee4b19f TG |
86 | unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, |
87 | unsigned long offset) | |
c7f612cd | 88 | { |
b78c5713 | 89 | return _find_next_bit(addr, NULL, size, offset, ~0UL, 0); |
1da177e4 | 90 | } |
fee4b19f | 91 | EXPORT_SYMBOL(find_next_zero_bit); |
19de85ef | 92 | #endif |
77b9bd9c | 93 | |
0ade34c3 CC |
94 | #if !defined(find_next_and_bit) |
95 | unsigned long find_next_and_bit(const unsigned long *addr1, | |
96 | const unsigned long *addr2, unsigned long size, | |
97 | unsigned long offset) | |
98 | { | |
b78c5713 | 99 | return _find_next_bit(addr1, addr2, size, offset, 0UL, 0); |
0ade34c3 CC |
100 | } |
101 | EXPORT_SYMBOL(find_next_and_bit); | |
102 | #endif | |
103 | ||
19de85ef | 104 | #ifndef find_first_bit |
77b9bd9c AH |
105 | /* |
106 | * Find the first set bit in a memory region. | |
107 | */ | |
fee4b19f | 108 | unsigned long find_first_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c | 109 | { |
2c57a0e2 | 110 | unsigned long idx; |
77b9bd9c | 111 | |
2c57a0e2 YN |
112 | for (idx = 0; idx * BITS_PER_LONG < size; idx++) { |
113 | if (addr[idx]) | |
114 | return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); | |
77b9bd9c | 115 | } |
77b9bd9c | 116 | |
2c57a0e2 | 117 | return size; |
77b9bd9c | 118 | } |
fee4b19f | 119 | EXPORT_SYMBOL(find_first_bit); |
19de85ef | 120 | #endif |
77b9bd9c | 121 | |
19de85ef | 122 | #ifndef find_first_zero_bit |
77b9bd9c AH |
123 | /* |
124 | * Find the first cleared bit in a memory region. | |
125 | */ | |
fee4b19f | 126 | unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c | 127 | { |
2c57a0e2 | 128 | unsigned long idx; |
77b9bd9c | 129 | |
2c57a0e2 YN |
130 | for (idx = 0; idx * BITS_PER_LONG < size; idx++) { |
131 | if (addr[idx] != ~0UL) | |
132 | return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); | |
77b9bd9c | 133 | } |
77b9bd9c | 134 | |
2c57a0e2 | 135 | return size; |
77b9bd9c | 136 | } |
fee4b19f | 137 | EXPORT_SYMBOL(find_first_zero_bit); |
19de85ef | 138 | #endif |
930ae745 | 139 | |
8f6f19dd YN |
140 | #ifndef find_last_bit |
141 | unsigned long find_last_bit(const unsigned long *addr, unsigned long size) | |
142 | { | |
143 | if (size) { | |
144 | unsigned long val = BITMAP_LAST_WORD_MASK(size); | |
145 | unsigned long idx = (size-1) / BITS_PER_LONG; | |
146 | ||
147 | do { | |
148 | val &= addr[idx]; | |
149 | if (val) | |
150 | return idx * BITS_PER_LONG + __fls(val); | |
151 | ||
152 | val = ~0ul; | |
153 | } while (idx--); | |
154 | } | |
155 | return size; | |
156 | } | |
157 | EXPORT_SYMBOL(find_last_bit); | |
158 | #endif | |
159 | ||
930ae745 AM |
160 | #ifdef __BIG_ENDIAN |
161 | ||
2c57a0e2 YN |
162 | #ifndef find_next_zero_bit_le |
163 | unsigned long find_next_zero_bit_le(const void *addr, unsigned | |
164 | long size, unsigned long offset) | |
165 | { | |
b78c5713 | 166 | return _find_next_bit(addr, NULL, size, offset, ~0UL, 1); |
930ae745 | 167 | } |
c4945b9e | 168 | EXPORT_SYMBOL(find_next_zero_bit_le); |
19de85ef | 169 | #endif |
930ae745 | 170 | |
19de85ef | 171 | #ifndef find_next_bit_le |
a56560b3 | 172 | unsigned long find_next_bit_le(const void *addr, unsigned |
aa02ad67 AK |
173 | long size, unsigned long offset) |
174 | { | |
b78c5713 | 175 | return _find_next_bit(addr, NULL, size, offset, 0UL, 1); |
aa02ad67 | 176 | } |
c4945b9e | 177 | EXPORT_SYMBOL(find_next_bit_le); |
19de85ef | 178 | #endif |
0664996b | 179 | |
930ae745 | 180 | #endif /* __BIG_ENDIAN */ |
169c474f WBG |
181 | |
182 | unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr, | |
183 | unsigned long size, unsigned long offset) | |
184 | { | |
185 | offset = find_next_bit(addr, size, offset); | |
186 | if (offset == size) | |
187 | return size; | |
188 | ||
189 | offset = round_down(offset, 8); | |
190 | *clump = bitmap_get_value8(addr, offset); | |
191 | ||
192 | return offset; | |
193 | } | |
194 | EXPORT_SYMBOL(find_next_clump8); |