1#include <linux/bitops.h> 2 3#undef find_first_zero_bit 4#undef find_next_zero_bit 5#undef find_first_bit 6#undef find_next_bit 7 8static inline long 9__find_first_zero_bit(const unsigned long * addr, unsigned long size) 10{ 11 long d0, d1, d2; 12 long res; 13 14 /* 15 * We must test the size in words, not in bits, because 16 * otherwise incoming sizes in the range -63..-1 will not run 17 * any scasq instructions, and then the flags used by the je 18 * instruction will have whatever random value was in place 19 * before. Nobody should call us like that, but 20 * find_next_zero_bit() does when offset and size are at the 21 * same word and it fails to find a zero itself. 22 */ 23 size += 63; 24 size >>= 6; 25 if (!size) 26 return 0; 27 asm volatile( 28 " repe; scasq\n" 29 " je 1f\n" 30 " xorq -8(%%rdi),%%rax\n" 31 " subq $8,%%rdi\n" 32 " bsfq %%rax,%%rdx\n" 33 "1: subq %[addr],%%rdi\n" 34 " shlq $3,%%rdi\n" 35 " addq %%rdi,%%rdx" 36 :"=d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2) 37 :"0" (0ULL), "1" (size), "2" (addr), "3" (-1ULL), 38 [addr] "S" (addr) : "memory"); 39 /* 40 * Any register would do for [addr] above, but GCC tends to 41 * prefer rbx over rsi, even though rsi is readily available 42 * and doesn't have to be saved. 43 */ 44 return res; 45} 46 47/** 48 * find_first_zero_bit - find the first zero bit in a memory region 49 * @addr: The address to start the search at 50 * @size: The maximum size to search 51 * 52 * Returns the bit-number of the first zero bit, not the number of the byte 53 * containing a bit. 54 */ 55long find_first_zero_bit(const unsigned long * addr, unsigned long size) 56{ 57 return __find_first_zero_bit (addr, size); 58} 59 60/** 61 * find_next_zero_bit - find the first zero bit in a memory region 62 * @addr: The address to base the search on 63 * @offset: The bitnumber to start searching at 64 * @size: The maximum size to search 65 */ 66long find_next_zero_bit (const unsigned long * addr, long size, long offset) 67{ 68 const unsigned long * p = addr + (offset >> 6); 69 unsigned long set = 0; 70 unsigned long res, bit = offset&63; 71 72 if (bit) { 73 /* 74 * Look for zero in first word 75 */ 76 asm("bsfq %1,%0\n\t" 77 "cmoveq %2,%0" 78 : "=r" (set) 79 : "r" (~(*p >> bit)), "r"(64L)); 80 if (set < (64 - bit)) 81 return set + offset; 82 set = 64 - bit; 83 p++; 84 } 85 /* 86 * No zero yet, search remaining full words for a zero 87 */ 88 res = __find_first_zero_bit (p, size - 64 * (p - addr)); 89 90 return (offset + set + res); 91} 92 93static inline long 94__find_first_bit(const unsigned long * addr, unsigned long size) 95{ 96 long d0, d1; 97 long res; 98 99 /* 100 * We must test the size in words, not in bits, because 101 * otherwise incoming sizes in the range -63..-1 will not run 102 * any scasq instructions, and then the flags used by the jz 103 * instruction will have whatever random value was in place 104 * before. Nobody should call us like that, but 105 * find_next_bit() does when offset and size are at the same 106 * word and it fails to find a one itself. 107 */ 108 size += 63; 109 size >>= 6; 110 if (!size) 111 return 0; 112 asm volatile( 113 " repe; scasq\n" 114 " jz 1f\n" 115 " subq $8,%%rdi\n" 116 " bsfq (%%rdi),%%rax\n" 117 "1: subq %[addr],%%rdi\n" 118 " shlq $3,%%rdi\n" 119 " addq %%rdi,%%rax" 120 :"=a" (res), "=&c" (d0), "=&D" (d1) 121 :"0" (0ULL), "1" (size), "2" (addr), 122 [addr] "r" (addr) : "memory"); 123 return res; 124} 125 126/** 127 * find_first_bit - find the first set bit in a memory region 128 * @addr: The address to start the search at 129 * @size: The maximum size to search 130 * 131 * Returns the bit-number of the first set bit, not the number of the byte 132 * containing a bit. 133 */ 134long find_first_bit(const unsigned long * addr, unsigned long size) 135{ 136 return __find_first_bit(addr,size); 137} 138 139/** 140 * find_next_bit - find the first set bit in a memory region 141 * @addr: The address to base the search on 142 * @offset: The bitnumber to start searching at 143 * @size: The maximum size to search 144 */ 145long find_next_bit(const unsigned long * addr, long size, long offset) 146{ 147 const unsigned long * p = addr + (offset >> 6); 148 unsigned long set = 0, bit = offset & 63, res; 149 150 if (bit) { 151 /* 152 * Look for nonzero in the first 64 bits: 153 */ 154 asm("bsfq %1,%0\n\t" 155 "cmoveq %2,%0\n\t" 156 : "=r" (set) 157 : "r" (*p >> bit), "r" (64L)); 158 if (set < (64 - bit)) 159 return set + offset; 160 set = 64 - bit; 161 p++; 162 } 163 /* 164 * No set bit yet, search remaining full words for a bit 165 */ 166 res = __find_first_bit (p, size - 64 * (p - addr)); 167 return (offset + set + res); 168} 169 170#include <linux/module.h> 171 172EXPORT_SYMBOL(find_next_bit); 173EXPORT_SYMBOL(find_first_bit); 174EXPORT_SYMBOL(find_first_zero_bit); 175EXPORT_SYMBOL(find_next_zero_bit); 176