2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
17 #ifndef incl_HPHP_BITOPS_H_
18 #define incl_HPHP_BITOPS_H_
20 #if !defined(__x86_64__) && !defined(__aarch64__)
21 #include <folly/Bits.h>
24 #include "hphp/util/assertions.h"
28 // GLIBC doesn't provide an fls primitive. Since we're rolling our own
29 // anyway, fix ffs's wacky offset-by-one historical implementation. These
30 // guys return success/failure (failure for input of all zeros) and the
31 // unoffset bit position in their reference param.
32 template<typename I64
, typename J64
>
33 inline bool ffs64(I64 input
, J64
&out
) {
35 #if defined(__x86_64__)
37 "bsfq %2, %1\n\t" // bit scan forward
38 "setnz %0\n\t": // zero retval if input == 0
39 "=r"(retval
), "=r"(out
):
43 #elif defined(__aarch64__)
45 "rbit %2, %2\n\t" // reverse bits
46 "clz %1, %2\n\t" // count leading zeros
48 "cset %w0, NE": // return (result != 64)
49 "=r"(retval
), "=r"(out
), "+r"(input
):
53 #elif defined(__powerpc64__)
54 // In PowerPC 64, bit 0 is the most significant
56 "neg %0, %2\n\t" // 2-complement of input, using retval as temp
58 "cntlzd %1, %0\n\t" // count leading zeros (starting from index 0)
60 "li %0, 1\n\t" // using retval as temp
61 "iseleq %0, 0, %0\n\t" // (input == 0) ? 0 : 1
63 "addi %1, %1, 63\n\t":// 63 - amount of leading zeros -> position in LSB
64 "+r"(retval
), "=r"(out
):// +r else %0 and %2 will be the same register
69 out
= folly::findFirstSet(input
);
75 template<typename I64
, typename J64
>
76 inline bool fls64(I64 input
, J64
&out
) {
78 #if defined(__x86_64__)
80 "bsrq %2, %1\n\t" // bit scan reverse
81 "setnz %0\n\t": // zero retval if input == 0
82 "=r"(retval
), "=r"(out
):
86 #elif defined(__aarch64__)
88 "clz %1, %2\n\t" // count leading zeros
90 "adds %1, %1, #63\n\t" // result = 63 - (# of leading zeros)
91 // "s" suffix sets condition flags
92 "cset %w0, PL": // return (result >= 0)
93 // because result < 0 iff input == 0
94 "=r"(retval
), "=r"(out
):
98 #elif defined(__powerpc64__)
99 // In PowerPC 64, bit 0 is the most significant
101 "cntlzd %1, %2\n\t" // count leading zeros (starting from index 0)
103 "li %0, 1\n\t" // using retval as temp
104 "iseleq %0, 0, %0\n\t" // (input == 0) ? 0 : 1
106 "addi %1, %1, 63\n\t":// 63 - amount of leading zeros -> position in LSB
107 "=r"(retval
), "=r"(out
):
112 out
= folly::findLastSet(input
) - 1;
119 * Return the index (0..63) of the most significant bit in x.
122 inline size_t fls64(size_t x
) {
124 #if defined(__x86_64__)
126 __asm__ ("bsrq %1, %0"
127 : "=r"(ret
) // Outputs.
131 #elif defined(__powerpc64__)
133 __asm__ ("cntlzd %0, %1"
134 : "=r"(ret
) // Outputs.
138 #elif defined(__aarch64__)
140 __asm__ ("clz %x0, %x1"
141 : "=r"(ret
) // Outputs.
146 // Equivalent (but incompletely strength-reduced by gcc):
147 return 63 - __builtin_clzl(x
);
152 * Return the index (0..63) of the least significant bit in x.
155 inline size_t ffs64(size_t x
) {
157 #if defined(__x86_64__)
159 __asm__ ("bsfq %1, %0"
160 : "=r"(ret
) // Outputs.
164 #elif defined(__aarch64__)
166 __asm__ ("rbit %0, %1\n\t"
168 : "=r"(ret
) // Outputs.
173 return __builtin_ffsll(x
) - 1;
177 inline void bitvec_set(uint64_t* bits
, size_t index
) {
178 #if defined(__x86_64__)
179 asm ("bts %1,%0" : "+m"(*bits
) : "r"(index
));
181 bits
[index
/ 64] |= 1ull << (index
% 64);
185 inline void bitvec_clear(uint64_t* bits
, size_t index
) {
186 #if defined(__x86_64__)
187 asm ("btr %1,%0" : "+m"(*bits
) : "r"(index
));
189 bits
[index
/ 64] &= ~(1ull << (index
% 64));
193 inline bool bitvec_test(const uint64_t* bits
, size_t index
) {
194 #if defined(__x86_64__)
197 "setc %0\n" : "=r"(b
) : "m"(*bits
), "r"(index
));
200 return (bits
[index
/ 64] & (1ull << (index
% 64))) != 0;