1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* bit search implementation 3 * 4 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. 5 * Written by David Howells (dhowells@redhat.com) 6 * 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 * 11 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease 12 * size and improve performance, 2015. 13 */ 14 15 #include <linux/bitops.h> 16 #include <linux/bitmap.h> 17 #include <linux/export.h> 18 #include <linux/math.h> 19 #include <linux/minmax.h> 20 #include <linux/swab.h> 21 #include <linux/random.h> 22 23 /* 24 * Common helper for find_bit() function family 25 * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) 26 * @MUNGE: The expression that post-processes a word containing found bit (may be empty) 27 * @size: The bitmap size in bits 28 */ 29 #define FIND_FIRST_BIT(FETCH, MUNGE, size) \ 30 ({ \ 31 unsigned long idx, val, sz = (size); \ 32 \ 33 for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \ 34 val = (FETCH); \ 35 if (val) { \ 36 sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \ 37 break; \ 38 } \ 39 } \ 40 \ 41 sz; \ 42 }) 43 44 /* 45 * Common helper for find_next_bit() function family 46 * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) 47 * @MUNGE: The expression that post-processes a word containing found bit (may be empty) 48 * @size: The bitmap size in bits 49 * @start: The bitnumber to start searching at 50 */ 51 #define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \ 52 ({ \ 53 unsigned long mask, idx, tmp, sz = (size), __start = (start); \ 54 \ 55 if (unlikely(__start >= sz)) \ 56 goto out; \ 57 \ 58 mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \ 59 idx = __start / BITS_PER_LONG; \ 60 \ 61 for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \ 62 if ((idx + 1) * BITS_PER_LONG >= sz) \ 63 goto out; \ 64 idx++; \ 65 } \ 66 \ 67 sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \ 68 out: \ 69 sz; \ 70 }) 71 72 #define FIND_NTH_BIT(FETCH, size, num) \ 73 ({ \ 74 unsigned long sz = (size), nr = (num), idx, w, tmp; \ 75 \ 76 for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \ 77 if (idx * BITS_PER_LONG + nr >= sz) \ 78 goto out; \ 79 \ 80 tmp = (FETCH); \ 81 w = hweight_long(tmp); \ 82 if (w > nr) \ 83 goto found; \ 84 \ 85 nr -= w; \ 86 } \ 87 \ 88 if (sz % BITS_PER_LONG) \ 89 tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \ 90 found: \ 91 sz = idx * BITS_PER_LONG + fns(tmp, nr); \ 92 out: \ 93 sz; \ 94 }) 95 96 #ifndef find_first_bit 97 /* 98 * Find the first set bit in a memory region. 99 */ 100 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size) 101 { 102 return FIND_FIRST_BIT(addr[idx], /* nop */, size); 103 } 104 EXPORT_SYMBOL(_find_first_bit); 105 #endif 106 107 #ifndef find_first_and_bit 108 /* 109 * Find the first set bit in two memory regions. 110 */ 111 unsigned long _find_first_and_bit(const unsigned long *addr1, 112 const unsigned long *addr2, 113 unsigned long size) 114 { 115 return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size); 116 } 117 EXPORT_SYMBOL(_find_first_and_bit); 118 #endif 119 120 /* 121 * Find the first bit set in 1st memory region and unset in 2nd. 122 */ 123 unsigned long _find_first_andnot_bit(const unsigned long *addr1, 124 const unsigned long *addr2, 125 unsigned long size) 126 { 127 return FIND_FIRST_BIT(addr1[idx] & ~addr2[idx], /* nop */, size); 128 } 129 EXPORT_SYMBOL(_find_first_andnot_bit); 130 131 /* 132 * Find the first set bit in three memory regions. 133 */ 134 unsigned long _find_first_and_and_bit(const unsigned long *addr1, 135 const unsigned long *addr2, 136 const unsigned long *addr3, 137 unsigned long size) 138 { 139 return FIND_FIRST_BIT(addr1[idx] & addr2[idx] & addr3[idx], /* nop */, size); 140 } 141 EXPORT_SYMBOL(_find_first_and_and_bit); 142 143 #ifndef find_first_zero_bit 144 /* 145 * Find the first cleared bit in a memory region. 146 */ 147 unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size) 148 { 149 return FIND_FIRST_BIT(~addr[idx], /* nop */, size); 150 } 151 EXPORT_SYMBOL(_find_first_zero_bit); 152 #endif 153 154 #ifndef find_next_bit 155 unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start) 156 { 157 return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start); 158 } 159 EXPORT_SYMBOL(_find_next_bit); 160 #endif 161 162 unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n) 163 { 164 return FIND_NTH_BIT(addr[idx], size, n); 165 } 166 EXPORT_SYMBOL(__find_nth_bit); 167 168 unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2, 169 unsigned long size, unsigned long n) 170 { 171 return FIND_NTH_BIT(addr1[idx] & addr2[idx], size, n); 172 } 173 EXPORT_SYMBOL(__find_nth_and_bit); 174 175 unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, 176 unsigned long size, unsigned long n) 177 { 178 return FIND_NTH_BIT(addr1[idx] & ~addr2[idx], size, n); 179 } 180 EXPORT_SYMBOL(__find_nth_andnot_bit); 181 182 unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, 183 const unsigned long *addr2, 184 const unsigned long *addr3, 185 unsigned long size, unsigned long n) 186 { 187 return FIND_NTH_BIT(addr1[idx] & addr2[idx] & ~addr3[idx], size, n); 188 } 189 EXPORT_SYMBOL(__find_nth_and_andnot_bit); 190 191 #ifndef find_next_and_bit 192 unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, 193 unsigned long nbits, unsigned long start) 194 { 195 return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start); 196 } 197 EXPORT_SYMBOL(_find_next_and_bit); 198 #endif 199 200 #ifndef find_next_andnot_bit 201 unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, 202 unsigned long nbits, unsigned long start) 203 { 204 return FIND_NEXT_BIT(addr1[idx] & ~addr2[idx], /* nop */, nbits, start); 205 } 206 EXPORT_SYMBOL(_find_next_andnot_bit); 207 #endif 208 209 #ifndef find_next_or_bit 210 unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2, 211 unsigned long nbits, unsigned long start) 212 { 213 return FIND_NEXT_BIT(addr1[idx] | addr2[idx], /* nop */, nbits, start); 214 } 215 EXPORT_SYMBOL(_find_next_or_bit); 216 #endif 217 218 #ifndef find_next_zero_bit 219 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, 220 unsigned long start) 221 { 222 return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start); 223 } 224 EXPORT_SYMBOL(_find_next_zero_bit); 225 #endif 226 227 #ifndef find_last_bit 228 unsigned long _find_last_bit(const unsigned long *addr, unsigned long size) 229 { 230 if (size) { 231 unsigned long val = BITMAP_LAST_WORD_MASK(size); 232 unsigned long idx = (size-1) / BITS_PER_LONG; 233 234 do { 235 val &= addr[idx]; 236 if (val) 237 return idx * BITS_PER_LONG + __fls(val); 238 239 val = ~0ul; 240 } while (idx--); 241 } 242 return size; 243 } 244 EXPORT_SYMBOL(_find_last_bit); 245 #endif 246 247 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr, 248 unsigned long size, unsigned long offset) 249 { 250 offset = find_next_bit(addr, size, offset); 251 if (offset == size) 252 return size; 253 254 offset = round_down(offset, 8); 255 *clump = bitmap_get_value8(addr, offset); 256 257 return offset; 258 } 259 EXPORT_SYMBOL(find_next_clump8); 260 261 #ifdef __BIG_ENDIAN 262 263 #ifndef find_first_zero_bit_le 264 /* 265 * Find the first cleared bit in an LE memory region. 266 */ 267 unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size) 268 { 269 return FIND_FIRST_BIT(~addr[idx], swab, size); 270 } 271 EXPORT_SYMBOL(_find_first_zero_bit_le); 272 273 #endif 274 275 #ifndef find_next_zero_bit_le 276 unsigned long _find_next_zero_bit_le(const unsigned long *addr, 277 unsigned long size, unsigned long offset) 278 { 279 return FIND_NEXT_BIT(~addr[idx], swab, size, offset); 280 } 281 EXPORT_SYMBOL(_find_next_zero_bit_le); 282 #endif 283 284 #ifndef find_next_bit_le 285 unsigned long _find_next_bit_le(const unsigned long *addr, 286 unsigned long size, unsigned long offset) 287 { 288 return FIND_NEXT_BIT(addr[idx], swab, size, offset); 289 } 290 EXPORT_SYMBOL(_find_next_bit_le); 291 292 #endif 293 294 #endif /* __BIG_ENDIAN */ 295 296 /** 297 * find_random_bit - find a set bit at random position 298 * @addr: The address to base the search on 299 * @size: The bitmap size in bits 300 * 301 * Returns: a position of a random set bit; >= @size otherwise 302 */ 303 unsigned long find_random_bit(const unsigned long *addr, unsigned long size) 304 { 305 int w = bitmap_weight(addr, size); 306 307 switch (w) { 308 case 0: 309 return size; 310 case 1: 311 /* Performance trick for single-bit bitmaps */ 312 return find_first_bit(addr, size); 313 default: 314 return find_nth_bit(addr, size, get_random_u32_below(w)); 315 } 316 } 317 EXPORT_SYMBOL(find_random_bit); 318