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/kernel.h> 19 20 #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ 21 !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) || \ 22 !defined(find_next_and_bit) 23 /* 24 * This is a common helper function for find_next_bit, find_next_zero_bit, and 25 * find_next_and_bit. The differences are: 26 * - The "invert" argument, which is XORed with each fetched word before 27 * searching it for one bits. 28 * - The optional "addr2", which is anded with "addr1" if present. 29 */ 30 static unsigned long _find_next_bit(const unsigned long *addr1, 31 const unsigned long *addr2, unsigned long nbits, 32 unsigned long start, unsigned long invert, unsigned long le) 33 { 34 unsigned long tmp, mask; 35 36 if (unlikely(start >= nbits)) 37 return nbits; 38 39 tmp = addr1[start / BITS_PER_LONG]; 40 if (addr2) 41 tmp &= addr2[start / BITS_PER_LONG]; 42 tmp ^= invert; 43 44 /* Handle 1st word. */ 45 mask = BITMAP_FIRST_WORD_MASK(start); 46 if (le) 47 mask = swab(mask); 48 49 tmp &= mask; 50 51 start = round_down(start, BITS_PER_LONG); 52 53 while (!tmp) { 54 start += BITS_PER_LONG; 55 if (start >= nbits) 56 return nbits; 57 58 tmp = addr1[start / BITS_PER_LONG]; 59 if (addr2) 60 tmp &= addr2[start / BITS_PER_LONG]; 61 tmp ^= invert; 62 } 63 64 if (le) 65 tmp = swab(tmp); 66 67 return min(start + __ffs(tmp), nbits); 68 } 69 #endif 70 71 #ifndef find_next_bit 72 /* 73 * Find the next set bit in a memory region. 74 */ 75 unsigned long find_next_bit(const unsigned long *addr, unsigned long size, 76 unsigned long offset) 77 { 78 return _find_next_bit(addr, NULL, size, offset, 0UL, 0); 79 } 80 EXPORT_SYMBOL(find_next_bit); 81 #endif 82 83 #ifndef find_next_zero_bit 84 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, 85 unsigned long offset) 86 { 87 return _find_next_bit(addr, NULL, size, offset, ~0UL, 0); 88 } 89 EXPORT_SYMBOL(find_next_zero_bit); 90 #endif 91 92 #if !defined(find_next_and_bit) 93 unsigned long find_next_and_bit(const unsigned long *addr1, 94 const unsigned long *addr2, unsigned long size, 95 unsigned long offset) 96 { 97 return _find_next_bit(addr1, addr2, size, offset, 0UL, 0); 98 } 99 EXPORT_SYMBOL(find_next_and_bit); 100 #endif 101 102 #ifndef find_first_bit 103 /* 104 * Find the first set bit in a memory region. 105 */ 106 unsigned long find_first_bit(const unsigned long *addr, unsigned long size) 107 { 108 unsigned long idx; 109 110 for (idx = 0; idx * BITS_PER_LONG < size; idx++) { 111 if (addr[idx]) 112 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); 113 } 114 115 return size; 116 } 117 EXPORT_SYMBOL(find_first_bit); 118 #endif 119 120 #ifndef find_first_zero_bit 121 /* 122 * Find the first cleared bit in a memory region. 123 */ 124 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) 125 { 126 unsigned long idx; 127 128 for (idx = 0; idx * BITS_PER_LONG < size; idx++) { 129 if (addr[idx] != ~0UL) 130 return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); 131 } 132 133 return size; 134 } 135 EXPORT_SYMBOL(find_first_zero_bit); 136 #endif 137 138 #ifndef find_last_bit 139 unsigned long find_last_bit(const unsigned long *addr, unsigned long size) 140 { 141 if (size) { 142 unsigned long val = BITMAP_LAST_WORD_MASK(size); 143 unsigned long idx = (size-1) / BITS_PER_LONG; 144 145 do { 146 val &= addr[idx]; 147 if (val) 148 return idx * BITS_PER_LONG + __fls(val); 149 150 val = ~0ul; 151 } while (idx--); 152 } 153 return size; 154 } 155 EXPORT_SYMBOL(find_last_bit); 156 #endif 157 158 #ifdef __BIG_ENDIAN 159 160 #ifndef find_next_zero_bit_le 161 unsigned long find_next_zero_bit_le(const void *addr, unsigned 162 long size, unsigned long offset) 163 { 164 return _find_next_bit(addr, NULL, size, offset, ~0UL, 1); 165 } 166 EXPORT_SYMBOL(find_next_zero_bit_le); 167 #endif 168 169 #ifndef find_next_bit_le 170 unsigned long find_next_bit_le(const void *addr, unsigned 171 long size, unsigned long offset) 172 { 173 return _find_next_bit(addr, NULL, size, offset, 0UL, 1); 174 } 175 EXPORT_SYMBOL(find_next_bit_le); 176 #endif 177 178 #endif /* __BIG_ENDIAN */ 179 180 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr, 181 unsigned long size, unsigned long offset) 182 { 183 offset = find_next_bit(addr, size, offset); 184 if (offset == size) 185 return size; 186 187 offset = round_down(offset, 8); 188 *clump = bitmap_get_value8(addr, offset); 189 190 return offset; 191 } 192 EXPORT_SYMBOL(find_next_clump8); 193