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