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 | |
58414bbb YN |
22 | /* |
23 | * Common helper for find_bit() function family | |
24 | * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) | |
25 | * @MUNGE: The expression that post-processes a word containing found bit (may be empty) | |
26 | * @size: The bitmap size in bits | |
27 | */ | |
28 | #define FIND_FIRST_BIT(FETCH, MUNGE, size) \ | |
29 | ({ \ | |
30 | unsigned long idx, val, sz = (size); \ | |
31 | \ | |
32 | for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \ | |
33 | val = (FETCH); \ | |
34 | if (val) { \ | |
35 | sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \ | |
36 | break; \ | |
37 | } \ | |
38 | } \ | |
39 | \ | |
40 | sz; \ | |
41 | }) | |
42 | ||
b78c5713 YN |
43 | #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ |
44 | !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \ | |
45 | !defined(find_next_and_bit) | |
64970b68 | 46 | /* |
0ade34c3 CC |
47 | * This is a common helper function for find_next_bit, find_next_zero_bit, and |
48 | * find_next_and_bit. The differences are: | |
49 | * - The "invert" argument, which is XORed with each fetched word before | |
50 | * searching it for one bits. | |
51 | * - The optional "addr2", which is anded with "addr1" if present. | |
c7f612cd | 52 | */ |
5c88af59 | 53 | unsigned long _find_next_bit(const unsigned long *addr1, |
0ade34c3 | 54 | const unsigned long *addr2, unsigned long nbits, |
b78c5713 | 55 | unsigned long start, unsigned long invert, unsigned long le) |
1da177e4 | 56 | { |
b78c5713 | 57 | unsigned long tmp, mask; |
1da177e4 | 58 | |
e4afd2e5 | 59 | if (unlikely(start >= nbits)) |
2c57a0e2 YN |
60 | return nbits; |
61 | ||
0ade34c3 CC |
62 | tmp = addr1[start / BITS_PER_LONG]; |
63 | if (addr2) | |
64 | tmp &= addr2[start / BITS_PER_LONG]; | |
65 | tmp ^= invert; | |
2c57a0e2 YN |
66 | |
67 | /* Handle 1st word. */ | |
b78c5713 YN |
68 | mask = BITMAP_FIRST_WORD_MASK(start); |
69 | if (le) | |
70 | mask = swab(mask); | |
71 | ||
72 | tmp &= mask; | |
73 | ||
2c57a0e2 YN |
74 | start = round_down(start, BITS_PER_LONG); |
75 | ||
76 | while (!tmp) { | |
77 | start += BITS_PER_LONG; | |
78 | if (start >= nbits) | |
79 | return nbits; | |
80 | ||
0ade34c3 CC |
81 | tmp = addr1[start / BITS_PER_LONG]; |
82 | if (addr2) | |
83 | tmp &= addr2[start / BITS_PER_LONG]; | |
84 | tmp ^= invert; | |
1da177e4 LT |
85 | } |
86 | ||
b78c5713 YN |
87 | if (le) |
88 | tmp = swab(tmp); | |
89 | ||
2c57a0e2 | 90 | return min(start + __ffs(tmp), nbits); |
c7f612cd | 91 | } |
5c88af59 | 92 | EXPORT_SYMBOL(_find_next_bit); |
0ade34c3 CC |
93 | #endif |
94 | ||
19de85ef | 95 | #ifndef find_first_bit |
77b9bd9c AH |
96 | /* |
97 | * Find the first set bit in a memory region. | |
98 | */ | |
2cc7b6a4 | 99 | unsigned long _find_first_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c | 100 | { |
58414bbb | 101 | return FIND_FIRST_BIT(addr[idx], /* nop */, size); |
77b9bd9c | 102 | } |
2cc7b6a4 | 103 | EXPORT_SYMBOL(_find_first_bit); |
19de85ef | 104 | #endif |
77b9bd9c | 105 | |
f68edc92 YN |
106 | #ifndef find_first_and_bit |
107 | /* | |
108 | * Find the first set bit in two memory regions. | |
109 | */ | |
110 | unsigned long _find_first_and_bit(const unsigned long *addr1, | |
111 | const unsigned long *addr2, | |
112 | unsigned long size) | |
113 | { | |
58414bbb | 114 | return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size); |
f68edc92 YN |
115 | } |
116 | EXPORT_SYMBOL(_find_first_and_bit); | |
117 | #endif | |
118 | ||
19de85ef | 119 | #ifndef find_first_zero_bit |
77b9bd9c AH |
120 | /* |
121 | * Find the first cleared bit in a memory region. | |
122 | */ | |
2cc7b6a4 | 123 | unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size) |
77b9bd9c | 124 | { |
58414bbb | 125 | return FIND_FIRST_BIT(~addr[idx], /* nop */, size); |
77b9bd9c | 126 | } |
2cc7b6a4 | 127 | EXPORT_SYMBOL(_find_first_zero_bit); |
19de85ef | 128 | #endif |
930ae745 | 129 | |
8f6f19dd | 130 | #ifndef find_last_bit |
2cc7b6a4 | 131 | unsigned long _find_last_bit(const unsigned long *addr, unsigned long size) |
8f6f19dd YN |
132 | { |
133 | if (size) { | |
134 | unsigned long val = BITMAP_LAST_WORD_MASK(size); | |
135 | unsigned long idx = (size-1) / BITS_PER_LONG; | |
136 | ||
137 | do { | |
138 | val &= addr[idx]; | |
139 | if (val) | |
140 | return idx * BITS_PER_LONG + __fls(val); | |
141 | ||
142 | val = ~0ul; | |
143 | } while (idx--); | |
144 | } | |
145 | return size; | |
146 | } | |
2cc7b6a4 | 147 | EXPORT_SYMBOL(_find_last_bit); |
8f6f19dd YN |
148 | #endif |
149 | ||
169c474f WBG |
150 | unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr, |
151 | unsigned long size, unsigned long offset) | |
152 | { | |
153 | offset = find_next_bit(addr, size, offset); | |
154 | if (offset == size) | |
155 | return size; | |
156 | ||
157 | offset = round_down(offset, 8); | |
158 | *clump = bitmap_get_value8(addr, offset); | |
159 | ||
160 | return offset; | |
161 | } | |
162 | EXPORT_SYMBOL(find_next_clump8); | |
14a99e13 YN |
163 | |
164 | #ifdef __BIG_ENDIAN | |
165 | ||
166 | #ifndef find_first_zero_bit_le | |
167 | /* | |
168 | * Find the first cleared bit in an LE memory region. | |
169 | */ | |
170 | unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size) | |
171 | { | |
172 | return FIND_FIRST_BIT(~addr[idx], swab, size); | |
173 | } | |
174 | EXPORT_SYMBOL(_find_first_zero_bit_le); | |
175 | ||
176 | #endif | |
177 | ||
178 | #endif /* __BIG_ENDIAN */ |