1 /*-
2 * Copyright (c) 1998 Doug Rabson
3 * Copyright (c) 2017-2022 Intel Corporation.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $FreeBSD$
27 */
28
29 #ifndef BITS_H
30 #define BITS_H
31 #include <asm/lib/atomic.h>
32
33 /**
34 *
35 * INVALID_BIT_INDEX means when input paramter is zero,
36 * bit operations function can't find bit set and return
37 * the invalid bit index directly.
38 *
39 **/
40 #define INVALID_BIT_INDEX 0xffffU
41
42 /*
43 *
44 * fls32 - Find the Last (most significant) bit Set in value and
45 * return the bit index of that bit.
46 *
47 * Bits are numbered starting at 0,the least significant bit.
48 * A return value of INVALID_BIT_INDEX means return value is
49 * invalid bit index when the input argument was zero.
50 *
51 * Examples:
52 * fls32 (0x0) = INVALID_BIT_INDEX
53 * fls32 (0x01) = 0
54 * fls32 (0x80) = 7
55 * ...
56 * fls32 (0x80000001) = 31
57 *
58 * @param value: 'uint32_t' type value
59 *
60 * @return value: zero-based bit index, INVALID_BIT_INDEX means
61 * when 'value' was zero, bit operations function can't find bit
62 * set and return the invalid bit index directly.
63 *
64 */
fls32(uint32_t value)65 static inline uint16_t fls32(uint32_t value)
66 {
67 uint32_t ret;
68 asm volatile("bsrl %1,%0\n\t"
69 "jnz 1f\n\t"
70 "mov %2,%0\n"
71 "1:" : "=r" (ret)
72 : "rm" (value), "i" (INVALID_BIT_INDEX));
73 return (uint16_t)ret;
74 }
75
fls64(uint64_t value)76 static inline uint16_t fls64(uint64_t value)
77 {
78 uint64_t ret = 0UL;
79 asm volatile("bsrq %1,%0\n\t"
80 "jnz 1f\n\t"
81 "mov %2,%0\n"
82 "1:" : "=r" (ret)
83 : "rm" (value), "i" (INVALID_BIT_INDEX));
84 return (uint16_t)ret;
85 }
86
87 /*
88 *
89 * ffs64 - Find the First (least significant) bit Set in value(Long type)
90 * and return the index of that bit.
91 *
92 * Bits are numbered starting at 0,the least significant bit.
93 * A return value of INVALID_BIT_INDEX means that the return value is the inalid
94 * bit index when the input argument was zero.
95 *
96 * Examples:
97 * ffs64 (0x0) = INVALID_BIT_INDEX
98 * ffs64 (0x01) = 0
99 * ffs64 (0xf0) = 4
100 * ffs64 (0xf00) = 8
101 * ...
102 * ffs64 (0x8000000000000001) = 0
103 * ffs64 (0xf000000000000000) = 60
104 *
105 * @param value: 'uint64_t' type value
106 *
107 * @return value: zero-based bit index, INVALID_BIT_INDEX means
108 * when 'value' was zero, bit operations function can't find bit
109 * set and return the invalid bit index directly.
110 *
111 */
ffs64(uint64_t value)112 static inline uint16_t ffs64(uint64_t value)
113 {
114 uint64_t ret;
115 asm volatile("bsfq %1,%0\n\t"
116 "jnz 1f\n\t"
117 "mov %2,%0\n"
118 "1:" : "=r" (ret)
119 : "rm" (value), "i" (INVALID_BIT_INDEX));
120 return (uint16_t)ret;
121 }
122
123 /*bit scan forward for the least significant bit '0'*/
ffz64(uint64_t value)124 static inline uint16_t ffz64(uint64_t value)
125 {
126 return ffs64(~value);
127 }
128
129
130 /*
131 * find the first zero bit in a uint64_t array.
132 * @pre: the size must be multiple of 64.
133 */
ffz64_ex(const uint64_t * addr,uint64_t size)134 static inline uint64_t ffz64_ex(const uint64_t *addr, uint64_t size)
135 {
136 uint64_t ret = size;
137 uint64_t idx;
138
139 for (idx = 0UL; (idx << 6U) < size; idx++) {
140 if (addr[idx] != ~0UL) {
141 ret = (idx << 6U) + ffz64(addr[idx]);
142 break;
143 }
144 }
145
146 return ret;
147 }
148 /*
149 * Counts leading zeros.
150 *
151 * The number of leading zeros is defined as the number of
152 * most significant bits which are not '1'. E.g.:
153 * clz(0x80000000)==0
154 * clz(0x40000000)==1
155 * ...
156 * clz(0x00000001)==31
157 * clz(0x00000000)==32
158 *
159 * @param value:The 32 bit value to count the number of leading zeros.
160 *
161 * @return The number of leading zeros in 'value'.
162 */
clz(uint32_t value)163 static inline uint16_t clz(uint32_t value)
164 {
165 return ((value != 0U) ? (31U - fls32(value)) : 32U);
166 }
167
168 /*
169 * Counts leading zeros (64 bit version).
170 *
171 * @param value:The 64 bit value to count the number of leading zeros.
172 *
173 * @return The number of leading zeros in 'value'.
174 */
clz64(uint64_t value)175 static inline uint16_t clz64(uint64_t value)
176 {
177 return ((value != 0UL) ? (63U - fls64(value)) : 64U);
178 }
179
180 /*
181 * (*addr) |= (1UL<<nr);
182 * Note:Input parameter nr shall be less than 64.
183 * If nr>=64, it will be truncated.
184 */
185 #define build_bitmap_set(name, op_len, op_type, lock) \
186 static inline void name(uint16_t nr_arg, volatile op_type *addr) \
187 { \
188 uint16_t nr; \
189 nr = nr_arg & ((8U * sizeof(op_type)) - 1U); \
190 asm volatile(lock "or" op_len " %1,%0" \
191 : "+m" (*addr) \
192 : "r" ((op_type)(1UL<<nr)) \
193 : "cc", "memory"); \
194 }
195 build_bitmap_set(bitmap_set_nolock, "q", uint64_t, "")
196 build_bitmap_set(bitmap_set_lock, "q", uint64_t, BUS_LOCK)
197 build_bitmap_set(bitmap32_set_nolock, "l", uint32_t, "")
198 build_bitmap_set(bitmap32_set_lock, "l", uint32_t, BUS_LOCK)
199
200 /*
201 * (*addr) &= ~(1UL<<nr);
202 * Note:Input parameter nr shall be less than 64.
203 * If nr>=64, it will be truncated.
204 */
205 #define build_bitmap_clear(name, op_len, op_type, lock) \
206 static inline void name(uint16_t nr_arg, volatile op_type *addr) \
207 { \
208 uint16_t nr; \
209 nr = nr_arg & ((8U * sizeof(op_type)) - 1U); \
210 asm volatile(lock "and" op_len " %1,%0" \
211 : "+m" (*addr) \
212 : "r" ((op_type)(~(1UL<<(nr)))) \
213 : "cc", "memory"); \
214 }
215 build_bitmap_clear(bitmap_clear_nolock, "q", uint64_t, "")
216 build_bitmap_clear(bitmap_clear_lock, "q", uint64_t, BUS_LOCK)
217 build_bitmap_clear(bitmap32_clear_nolock, "l", uint32_t, "")
218 build_bitmap_clear(bitmap32_clear_lock, "l", uint32_t, BUS_LOCK)
219
220 /*
221 * return !!((*addr) & (1UL<<nr));
222 * Note:Input parameter nr shall be less than 64. If nr>=64, it will
223 * be truncated.
224 */
bitmap_test(uint16_t nr,const volatile uint64_t * addr)225 static inline bool bitmap_test(uint16_t nr, const volatile uint64_t *addr)
226 {
227 int32_t ret = 0;
228 asm volatile("btq %q2,%1\n\tsbbl %0, %0"
229 : "=r" (ret)
230 : "m" (*addr), "r" ((uint64_t)(nr & 0x3fU))
231 : "cc", "memory");
232 return (ret != 0);
233 }
234
bitmap32_test(uint16_t nr,const volatile uint32_t * addr)235 static inline bool bitmap32_test(uint16_t nr, const volatile uint32_t *addr)
236 {
237 int32_t ret = 0;
238 asm volatile("btl %2,%1\n\tsbbl %0, %0"
239 : "=r" (ret)
240 : "m" (*addr), "r" ((uint32_t)(nr & 0x1fU))
241 : "cc", "memory");
242 return (ret != 0);
243 }
244
245 /*
246 * bool ret = (*addr) & (1UL<<nr);
247 * (*addr) |= (1UL<<nr);
248 * return ret;
249 * Note:Input parameter nr shall be less than 64. If nr>=64, it
250 * will be truncated.
251 */
252 #define build_bitmap_testandset(name, op_len, op_type, lock) \
253 static inline bool name(uint16_t nr_arg, volatile op_type *addr) \
254 { \
255 uint16_t nr; \
256 int32_t ret=0; \
257 nr = nr_arg & ((8U * sizeof(op_type)) - 1U); \
258 asm volatile(lock "bts" op_len " %2,%1\n\tsbbl %0,%0" \
259 : "=r" (ret), "=m" (*addr) \
260 : "r" ((op_type)nr) \
261 : "cc", "memory"); \
262 return (ret != 0); \
263 }
264 build_bitmap_testandset(bitmap_test_and_set_nolock, "q", uint64_t, "")
265 build_bitmap_testandset(bitmap_test_and_set_lock, "q", uint64_t, BUS_LOCK)
266 build_bitmap_testandset(bitmap32_test_and_set_nolock, "l", uint32_t, "")
267 build_bitmap_testandset(bitmap32_test_and_set_lock, "l", uint32_t, BUS_LOCK)
268
269 /*
270 * bool ret = (*addr) & (1UL<<nr);
271 * (*addr) &= ~(1UL<<nr);
272 * return ret;
273 * Note:Input parameter nr shall be less than 64. If nr>=64,
274 * it will be truncated.
275 */
276 #define build_bitmap_testandclear(name, op_len, op_type, lock) \
277 static inline bool name(uint16_t nr_arg, volatile op_type *addr) \
278 { \
279 uint16_t nr; \
280 int32_t ret=0; \
281 nr = nr_arg & ((8U * sizeof(op_type)) - 1U); \
282 asm volatile(lock "btr" op_len " %2,%1\n\tsbbl %0,%0" \
283 : "=r" (ret), "=m" (*addr) \
284 : "r" ((op_type)nr) \
285 : "cc", "memory"); \
286 return (ret != 0); \
287 }
288 build_bitmap_testandclear(bitmap_test_and_clear_nolock, "q", uint64_t, "")
289 build_bitmap_testandclear(bitmap_test_and_clear_lock, "q", uint64_t, BUS_LOCK)
290 build_bitmap_testandclear(bitmap32_test_and_clear_nolock, "l", uint32_t, "")
291 build_bitmap_testandclear(bitmap32_test_and_clear_lock, "l", uint32_t, BUS_LOCK)
292
bitmap_weight(uint64_t bits)293 static inline uint16_t bitmap_weight(uint64_t bits)
294 {
295 return (uint16_t)__builtin_popcountl(bits);
296 }
297
298 #endif /* BITS_H*/
299