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