1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* bit search implementation 3 * 4 * Copied from lib/find_bit.c to tools/lib/find_bit.c 5 * 6 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. 7 * Written by David Howells (dhowells@redhat.com) 8 * 9 * Copyright (C) 2008 IBM Corporation 10 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au> 11 * (Inspired by David Howell's find_next_bit implementation) 12 * 13 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease 14 * size and improve performance, 2015. 15 */ 16 17 #include <linux/bitops.h> 18 #include <linux/bitmap.h> 19 #include <linux/kernel.h> 20 21 /* 22 * Common helper for find_bit() function family 23 * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) 24 * @MUNGE: The expression that post-processes a word containing found bit (may be empty) 25 * @size: The bitmap size in bits 26 */ 27 #define FIND_FIRST_BIT(FETCH, MUNGE, size) \ 28 ({ \ 29 unsigned long idx, val, sz = (size); \ 30 \ 31 for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \ 32 val = (FETCH); \ 33 if (val) { \ 34 sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \ 35 break; \ 36 } \ 37 } \ 38 \ 39 sz; \ 40 }) 41 42 /* 43 * Common helper for find_next_bit() function family 44 * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) 45 * @MUNGE: The expression that post-processes a word containing found bit (may be empty) 46 * @size: The bitmap size in bits 47 * @start: The bitnumber to start searching at 48 */ 49 #define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \ 50 ({ \ 51 unsigned long mask, idx, tmp, sz = (size), __start = (start); \ 52 \ 53 if (unlikely(__start >= sz)) \ 54 goto out; \ 55 \ 56 mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \ 57 idx = __start / BITS_PER_LONG; \ 58 \ 59 for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \ 60 if ((idx + 1) * BITS_PER_LONG >= sz) \ 61 goto out; \ 62 idx++; \ 63 } \ 64 \ 65 sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \ 66 out: \ 67 sz; \ 68 }) 69 70 #ifndef find_first_bit 71 /* 72 * Find the first set bit in a memory region. 73 */ 74 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size) 75 { 76 return FIND_FIRST_BIT(addr[idx], /* nop */, size); 77 } 78 #endif 79 80 #ifndef find_first_and_bit 81 /* 82 * Find the first set bit in two memory regions. 83 */ 84 unsigned long _find_first_and_bit(const unsigned long *addr1, 85 const unsigned long *addr2, 86 unsigned long size) 87 { 88 return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size); 89 } 90 #endif 91 92 #ifndef find_first_zero_bit 93 /* 94 * Find the first cleared bit in a memory region. 95 */ 96 unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size) 97 { 98 return FIND_FIRST_BIT(~addr[idx], /* nop */, size); 99 } 100 #endif 101 102 #ifndef find_next_bit 103 unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start) 104 { 105 return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start); 106 } 107 #endif 108 109 #ifndef find_next_and_bit 110 unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, 111 unsigned long nbits, unsigned long start) 112 { 113 return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start); 114 } 115 #endif 116 117 #ifndef find_next_zero_bit 118 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, 119 unsigned long start) 120 { 121 return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start); 122 } 123 #endif 124