Line data Source code
1 : /* Included by fd_bits.h */
2 : /* DO NOT INCLUDE DIRECTLY */
3 :
4 108 : FD_FN_CONST static inline int fd_uchar_find_msb ( uchar x ) { return 31 - __builtin_clz ( (uint)x ); }
5 408 : FD_FN_CONST static inline int fd_ushort_find_msb( ushort x ) { return 31 - __builtin_clz ( (uint)x ); }
6 18446064069 : FD_FN_CONST static inline int fd_uint_find_msb ( uint x ) { return 31 - __builtin_clz ( x ); }
7 27090132995 : FD_FN_CONST static inline int fd_ulong_find_msb ( ulong x ) { return 63 - __builtin_clzl( x ); }
8 :
9 : #if FD_HAS_INT128
10 :
11 : #if FD_HAS_X86
12 :
13 : FD_FN_CONST static inline int
14 24768 : fd_uint128_find_msb( uint128 x ) {
15 24768 : ulong xl = (ulong) x;
16 24768 : ulong xh = (ulong)(x>>64);
17 24768 : int _0 = 0;
18 24768 : int c = 64;
19 24768 : __asm__( "testq %1, %1 # cc.zf = !xh;\n\t"
20 24768 : "cmovz %3, %0 # if( !xh ) c = 0;\n\t"
21 24768 : "cmovz %2, %1 # if( !xh ) xh = xl;"
22 24768 : : "+&r" (c), "+&r" (xh) : "r" (xl), "r" (_0) : "cc" );
23 24768 : return c + fd_ulong_find_msb( xh );
24 24768 : }
25 :
26 : #else /* other architectures */
27 :
28 : FD_FN_CONST static inline int
29 : fd_uint128_find_msb( uint128 x ) {
30 : ulong xl = (ulong) x;
31 : ulong xh = (ulong)(x>>64);
32 : int c = !xh;
33 : return (127-((c)<<6)) - __builtin_clzl( fd_ulong_if( c, xl, xh ) );
34 : }
35 :
36 : #endif
37 :
38 : #endif
39 :
40 : /* find_msb_w_default */
41 :
42 : #if FD_HAS_X86
43 :
44 : /* find_msb_w_default has been optimized for both lzcnt and bsr. Note
45 : that in older Intel architectures (before Skylake) lzcnt has a false
46 : dependency on the destination register (this is true for bsr, but
47 : should not be the case for lzcnt). Instead of using the typical xor
48 : operation on the output register (to break the dependency), the code
49 : below reuses the input register to that end, without affecting the
50 : performance on newer architectures. */
51 :
52 : FD_FN_CONST static inline int
53 : fd_uchar_find_msb_w_default( uchar x,
54 111 : int d ) {
55 111 : union { int i; uint u; } r, c;
56 111 : # if __LZCNT__
57 111 : c.i = 31-d;
58 111 : r.u = (uint)x;
59 111 : __asm__( " lzcnt %0, %0 # cc.cf = !x;\n\t"
60 111 : " cmovb %1, %0 # move if cf is set;"
61 111 : : "+&r" (r.u) : "r" (c.u) : "cc" );
62 111 : return 31 - r.i;
63 : # else
64 : c.i = d;
65 : r.u = (uint)x;
66 : __asm__( " bsr %0, %0 # cc.zf = !x;\n\t"
67 : " cmovz %1, %0 # move if zf is set;"
68 : : "+&r" (r.u) : "r" (c.u) : "cc" );
69 : return r.i;
70 : # endif
71 111 : }
72 :
73 : FD_FN_CONST static inline int
74 : fd_ushort_find_msb_w_default( ushort x,
75 411 : int d ) {
76 411 : union { int i; uint u; } r, c;
77 411 : # if __LZCNT__
78 411 : c.i = 31-d;
79 411 : r.u = (uint)x;
80 411 : __asm__( " lzcnt %0, %0 # cc.cf = !x;\n\t"
81 411 : " cmovb %1, %0 # move if cf is set;"
82 411 : : "+&r" (r.u) : "r" (c.u) : "cc" );
83 411 : return 31 - r.i;
84 : # else
85 : c.i = d;
86 : r.u = (uint)x;
87 : __asm__( " bsr %0, %0 # cc.zf = !x;\n\t"
88 : " cmovz %1, %0 # move if zf is set;"
89 : : "+&r" (r.u) : "r" (c.u) : "cc" );
90 : return r.i;
91 : # endif
92 411 : }
93 :
94 : FD_FN_CONST static inline int
95 : fd_uint_find_msb_w_default( uint x,
96 1587 : int d ) {
97 1587 : union { int i; uint u; } r, c;
98 1587 : # if __LZCNT__
99 1587 : c.i = 31-d;
100 1587 : r.u = x;
101 1587 : __asm__( " lzcnt %0, %0 # cc.cf = !x;\n\t"
102 1587 : " cmovb %1, %0 # move if cf is set;"
103 1587 : : "+&r" (r.u) : "r" (c.u) : "cc" );
104 1587 : return 31 - r.i;
105 : # else
106 : c.i = d;
107 : r.u = x;
108 : __asm__( " bsr %0, %0 # cc.zf = !x;\n\t"
109 : " cmovz %1, %0 # move if zf is set;"
110 : : "+&r" (r.u) : "r" (c.u) : "cc" );
111 : return r.i;
112 : # endif
113 1587 : }
114 :
115 : FD_FN_CONST static inline int
116 : fd_ulong_find_msb_w_default( ulong x,
117 84385308 : int d ) {
118 84385308 : union { long l; ulong u; } r, c;
119 84385308 : # if __LZCNT__
120 84385308 : c.l = (long)(63L-d);
121 84385308 : r.u = x;
122 84385308 : __asm__( " lzcnt %0, %0 # cc.cf = !x;\n\t"
123 84385308 : " cmovb %1, %0 # move if cf is set;"
124 84385308 : : "+&r" (r.u) : "r" (c.u) : "cc" );
125 84385308 : return (int) (63L - r.l);
126 : # else
127 : c.l = (long)d;
128 : r.u = x;
129 : __asm__( " bsr %0, %0 # cc.zf = !x;\n\t"
130 : " cmovz %1, %0 # move if zf is set;"
131 : : "+&r" (r.u) : "r" (c.u) : "cc" );
132 : return (int)r.l;
133 : # endif
134 84385308 : }
135 :
136 : #else /* other architectures */
137 :
138 : FD_FN_CONST static inline int fd_uchar_find_msb_w_default ( uchar x, int d ) { return (!x) ? d : fd_uchar_find_msb ( x ); }
139 : FD_FN_CONST static inline int fd_ushort_find_msb_w_default( ushort x, int d ) { return (!x) ? d : fd_ushort_find_msb ( x ); }
140 : FD_FN_CONST static inline int fd_uint_find_msb_w_default ( uint x, int d ) { return (!x) ? d : fd_uint_find_msb ( x ); }
141 : FD_FN_CONST static inline int fd_ulong_find_msb_w_default ( ulong x, int d ) { return (!x) ? d : fd_ulong_find_msb ( x ); }
142 :
143 : #endif
144 :
145 : #if FD_HAS_INT128
146 :
147 : #if FD_HAS_X86
148 :
149 : FD_FN_CONST static inline int
150 : fd_uint128_find_msb_w_default( uint128 x,
151 24771 : int d ) {
152 24771 : ulong xl = (ulong) x;
153 24771 : ulong xh = (ulong)(x>>64);
154 24771 : int c = 64;
155 24771 : int _0 = 0;
156 24771 : __asm__( "testq %2, %2 # cc.zf = !xh;\n\t"
157 24771 : "cmovz %3, %0 # if( !xh ) c = 0;\n\t"
158 24771 : "cmovnz %2, %1 # if(!!xh ) xl = xh;"
159 24771 : : "+&r" (c), "+&r" (xl) : "r" (xh), "r" (_0) : "cc" );
160 24771 : return c + fd_ulong_find_msb_w_default( xl, d );
161 24771 : }
162 :
163 : #else /* other architectures */
164 :
165 : FD_FN_CONST static inline int fd_uint128_find_msb_w_default( uint128 x, int d ) { return (!x) ? d : fd_uint128_find_msb( x ); }
166 :
167 : #endif
168 :
169 : #endif
170 :
|
