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 #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ 22 !defined(find_next_and_bit) 23 24 /* 25 * This is a common helper function for find_next_bit, find_next_zero_bit, and 26 * find_next_and_bit. The differences are: 27 * - The "invert" argument, which is XORed with each fetched word before 28 * searching it for one bits. 29 * - The optional "addr2", which is anded with "addr1" if present. 30 */ 31 static inline unsigned long _find_next_bit(const unsigned long *addr1, 32 const unsigned long *addr2, unsigned long nbits, 33 unsigned long start, unsigned long invert) 34 { 35 unsigned long tmp; 36 37 if (unlikely(start >= nbits)) 38 return nbits; 39 40 tmp = addr1[start / BITS_PER_LONG]; 41 if (addr2) 42 tmp &= addr2[start / BITS_PER_LONG]; 43 tmp ^= invert; 44 45 /* Handle 1st word. */ 46 tmp &= BITMAP_FIRST_WORD_MASK(start); 47 start = round_down(start, BITS_PER_LONG); 48 49 while (!tmp) { 50 start += BITS_PER_LONG; 51 if (start >= nbits) 52 return nbits; 53 54 tmp = addr1[start / BITS_PER_LONG]; 55 if (addr2) 56 tmp &= addr2[start / BITS_PER_LONG]; 57 tmp ^= invert; 58 } 59 60 return min(start + __ffs(tmp), nbits); 61 } 62 #endif 63 64 #ifndef find_next_bit 65 /* 66 * Find the next set bit in a memory region. 67 */ 68 unsigned long find_next_bit(const unsigned long *addr, unsigned long size, 69 unsigned long offset) 70 { 71 return _find_next_bit(addr, NULL, size, offset, 0UL); 72 } 73 #endif 74 75 #ifndef find_first_bit 76 /* 77 * Find the first set bit in a memory region. 78 */ 79 unsigned long find_first_bit(const unsigned long *addr, unsigned long size) 80 { 81 unsigned long idx; 82 83 for (idx = 0; idx * BITS_PER_LONG < size; idx++) { 84 if (addr[idx]) 85 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); 86 } 87 88 return 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 unsigned long idx; 99 100 for (idx = 0; idx * BITS_PER_LONG < size; idx++) { 101 if (addr[idx] != ~0UL) 102 return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); 103 } 104 105 return size; 106 } 107 #endif 108 109 #ifndef find_next_zero_bit 110 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, 111 unsigned long offset) 112 { 113 return _find_next_bit(addr, NULL, size, offset, ~0UL); 114 } 115 #endif 116 117 #ifndef find_next_and_bit 118 unsigned long find_next_and_bit(const unsigned long *addr1, 119 const unsigned long *addr2, unsigned long size, 120 unsigned long offset) 121 { 122 return _find_next_bit(addr1, addr2, size, offset, 0UL); 123 } 124 #endif 125