Commit | Line | Data |
---|---|---|
1da177e4 LT |
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 | ||
06024f21 AO |
8 | static inline long |
9 | __find_first_zero_bit(const unsigned long * addr, unsigned long size) | |
1da177e4 LT |
10 | { |
11 | long d0, d1, d2; | |
12 | long res; | |
13 | ||
06024f21 AO |
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; | |
1da177e4 LT |
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) | |
06024f21 AO |
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 | */ | |
1da177e4 LT |
44 | return res; |
45 | } | |
46 | ||
06024f21 AO |
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 | */ | |
55 | long find_first_zero_bit(const unsigned long * addr, unsigned long size) | |
56 | { | |
57 | return __find_first_zero_bit (addr, size); | |
58 | } | |
59 | ||
1da177e4 LT |
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 | */ | |
66 | long find_next_zero_bit (const unsigned long * addr, long size, long offset) | |
67 | { | |
06024f21 | 68 | const unsigned long * p = addr + (offset >> 6); |
1da177e4 LT |
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 | */ | |
06024f21 AO |
88 | res = __find_first_zero_bit (p, size - 64 * (p - addr)); |
89 | ||
1da177e4 LT |
90 | return (offset + set + res); |
91 | } | |
92 | ||
93 | static inline long | |
94 | __find_first_bit(const unsigned long * addr, unsigned long size) | |
95 | { | |
96 | long d0, d1; | |
97 | long res; | |
98 | ||
06024f21 AO |
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; | |
1da177e4 LT |
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) | |
06024f21 | 121 | :"0" (0ULL), "1" (size), "2" (addr), |
1da177e4 LT |
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 | */ | |
134 | long 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 | */ | |
145 | long 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 | ||
172 | EXPORT_SYMBOL(find_next_bit); | |
173 | EXPORT_SYMBOL(find_first_bit); | |
174 | EXPORT_SYMBOL(find_first_zero_bit); | |
175 | EXPORT_SYMBOL(find_next_zero_bit); |