1 /* bit search implementation 2 * 3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. 4 * Written by David Howells (dhowells@redhat.com) 5 * 6 * Copyright (C) 2008 IBM Corporation 7 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au> 8 * (Inspired by David Howell's find_next_bit implementation) 9 * 10 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease 11 * size and improve performance, 2015. 12 * 13 * This program is free software; you can redistribute it and/or 14 * modify it under the terms of the GNU General Public License 15 * as published by the Free Software Foundation; either version 16 * 2 of the License, or (at your option) any later version. 17 */ 18 19 #include <linux/bitops.h> 20 #include <linux/bitmap.h> 21 #include <linux/export.h> 22 #include <linux/kernel.h> 23 24 #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ 25 !defined(find_next_and_bit) 26 27 /* 28 * This is a common helper function for find_next_bit, find_next_zero_bit, and 29 * find_next_and_bit. The differences are: 30 * - The "invert" argument, which is XORed with each fetched word before 31 * searching it for one bits. 32 * - The optional "addr2", which is anded with "addr1" if present. 33 */ 34 static inline unsigned long _find_next_bit(const unsigned long *addr1, 35 const unsigned long *addr2, unsigned long nbits, 36 unsigned long start, unsigned long invert) 37 { 38 unsigned long tmp; 39 40 if (unlikely(start >= nbits)) 41 return nbits; 42 43 tmp = addr1[start / BITS_PER_LONG]; 44 if (addr2) 45 tmp &= addr2[start / BITS_PER_LONG]; 46 tmp ^= invert; 47 48 /* Handle 1st word. */ 49 tmp &= BITMAP_FIRST_WORD_MASK(start); 50 start = round_down(start, BITS_PER_LONG); 51 52 while (!tmp) { 53 start += BITS_PER_LONG; 54 if (start >= nbits) 55 return nbits; 56 57 tmp = addr1[start / BITS_PER_LONG]; 58 if (addr2) 59 tmp &= addr2[start / BITS_PER_LONG]; 60 tmp ^= invert; 61 } 62 63 return min(start + __ffs(tmp), nbits); 64 } 65 #endif 66 67 #ifndef find_next_bit 68 /* 69 * Find the next set bit in a memory region. 70 */ 71 unsigned long find_next_bit(const unsigned long *addr, unsigned long size, 72 unsigned long offset) 73 { 74 return _find_next_bit(addr, NULL, size, offset, 0UL); 75 } 76 EXPORT_SYMBOL(find_next_bit); 77 #endif 78 79 #ifndef find_next_zero_bit 80 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, 81 unsigned long offset) 82 { 83 return _find_next_bit(addr, NULL, size, offset, ~0UL); 84 } 85 EXPORT_SYMBOL(find_next_zero_bit); 86 #endif 87 88 #if !defined(find_next_and_bit) 89 unsigned long find_next_and_bit(const unsigned long *addr1, 90 const unsigned long *addr2, unsigned long size, 91 unsigned long offset) 92 { 93 return _find_next_bit(addr1, addr2, size, offset, 0UL); 94 } 95 EXPORT_SYMBOL(find_next_and_bit); 96 #endif 97 98 #ifndef find_first_bit 99 /* 100 * Find the first set bit in a memory region. 101 */ 102 unsigned long find_first_bit(const unsigned long *addr, unsigned long size) 103 { 104 unsigned long idx; 105 106 for (idx = 0; idx * BITS_PER_LONG < size; idx++) { 107 if (addr[idx]) 108 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); 109 } 110 111 return size; 112 } 113 EXPORT_SYMBOL(find_first_bit); 114 #endif 115 116 #ifndef find_first_zero_bit 117 /* 118 * Find the first cleared bit in a memory region. 119 */ 120 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) 121 { 122 unsigned long idx; 123 124 for (idx = 0; idx * BITS_PER_LONG < size; idx++) { 125 if (addr[idx] != ~0UL) 126 return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); 127 } 128 129 return size; 130 } 131 EXPORT_SYMBOL(find_first_zero_bit); 132 #endif 133 134 #ifndef find_last_bit 135 unsigned long find_last_bit(const unsigned long *addr, unsigned long size) 136 { 137 if (size) { 138 unsigned long val = BITMAP_LAST_WORD_MASK(size); 139 unsigned long idx = (size-1) / BITS_PER_LONG; 140 141 do { 142 val &= addr[idx]; 143 if (val) 144 return idx * BITS_PER_LONG + __fls(val); 145 146 val = ~0ul; 147 } while (idx--); 148 } 149 return size; 150 } 151 EXPORT_SYMBOL(find_last_bit); 152 #endif 153 154 #ifdef __BIG_ENDIAN 155 156 /* include/linux/byteorder does not support "unsigned long" type */ 157 static inline unsigned long ext2_swab(const unsigned long y) 158 { 159 #if BITS_PER_LONG == 64 160 return (unsigned long) __swab64((u64) y); 161 #elif BITS_PER_LONG == 32 162 return (unsigned long) __swab32((u32) y); 163 #else 164 #error BITS_PER_LONG not defined 165 #endif 166 } 167 168 #if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le) 169 static inline unsigned long _find_next_bit_le(const unsigned long *addr1, 170 const unsigned long *addr2, unsigned long nbits, 171 unsigned long start, unsigned long invert) 172 { 173 unsigned long tmp; 174 175 if (unlikely(start >= nbits)) 176 return nbits; 177 178 tmp = addr1[start / BITS_PER_LONG]; 179 if (addr2) 180 tmp &= addr2[start / BITS_PER_LONG]; 181 tmp ^= invert; 182 183 /* Handle 1st word. */ 184 tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start)); 185 start = round_down(start, BITS_PER_LONG); 186 187 while (!tmp) { 188 start += BITS_PER_LONG; 189 if (start >= nbits) 190 return nbits; 191 192 tmp = addr1[start / BITS_PER_LONG]; 193 if (addr2) 194 tmp &= addr2[start / BITS_PER_LONG]; 195 tmp ^= invert; 196 } 197 198 return min(start + __ffs(ext2_swab(tmp)), nbits); 199 } 200 #endif 201 202 #ifndef find_next_zero_bit_le 203 unsigned long find_next_zero_bit_le(const void *addr, unsigned 204 long size, unsigned long offset) 205 { 206 return _find_next_bit_le(addr, NULL, size, offset, ~0UL); 207 } 208 EXPORT_SYMBOL(find_next_zero_bit_le); 209 #endif 210 211 #ifndef find_next_bit_le 212 unsigned long find_next_bit_le(const void *addr, unsigned 213 long size, unsigned long offset) 214 { 215 return _find_next_bit_le(addr, NULL, size, offset, 0UL); 216 } 217 EXPORT_SYMBOL(find_next_bit_le); 218 #endif 219 220 #endif /* __BIG_ENDIAN */ 221