1 | /* ----------------------------------------------------------------------- * |
2 | * |
3 | * Copyright 1996-2017 The NASM Authors - All Rights Reserved |
4 | * See the file AUTHORS included with the NASM distribution for |
5 | * the specific copyright holders. |
6 | * |
7 | * Redistribution and use in source and binary forms, with or without |
8 | * modification, are permitted provided that the following |
9 | * conditions are met: |
10 | * |
11 | * * Redistributions of source code must retain the above copyright |
12 | * notice, this list of conditions and the following disclaimer. |
13 | * * Redistributions in binary form must reproduce the above |
14 | * copyright notice, this list of conditions and the following |
15 | * disclaimer in the documentation and/or other materials provided |
16 | * with the distribution. |
17 | * |
18 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND |
19 | * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, |
20 | * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF |
21 | * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
22 | * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR |
23 | * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
24 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
25 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
26 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
27 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
28 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR |
29 | * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, |
30 | * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
31 | * |
32 | * ----------------------------------------------------------------------- */ |
33 | |
34 | #ifndef ILOG2_H |
35 | #define ILOG2_H |
36 | |
37 | #include "compiler.h" |
38 | #include <limits.h> |
39 | |
40 | #ifdef ILOG2_C /* For generating the out-of-line functions */ |
41 | # undef extern_inline |
42 | # define extern_inline |
43 | # define inline_prototypes |
44 | #endif |
45 | |
46 | #ifdef inline_prototypes |
47 | extern int const_func ilog2_32(uint32_t v); |
48 | extern int const_func ilog2_64(uint64_t v); |
49 | extern int const_func ilog2_64(uint64_t vv); |
50 | extern int const_func alignlog2_32(uint32_t v); |
51 | extern int const_func alignlog2_64(uint64_t v); |
52 | #endif |
53 | |
54 | #ifdef extern_inline |
55 | |
56 | #define ROUND(v, a, w) \ |
57 | do { \ |
58 | if (v & (((UINT32_C(1) << w) - 1) << w)) { \ |
59 | a += w; \ |
60 | v >>= w; \ |
61 | } \ |
62 | } while (0) |
63 | |
64 | |
65 | #if defined(__GNUC__) && defined(__x86_64__) |
66 | |
67 | extern_inline int const_func ilog2_32(uint32_t v) |
68 | { |
69 | int n; |
70 | |
71 | __asm__("bsrl %1,%0" |
72 | : "=r" (n) |
73 | : "rm" (v), "0" (0)); |
74 | return n; |
75 | } |
76 | |
77 | #elif defined(__GNUC__) && defined(__i386__) |
78 | |
79 | extern_inline int const_func ilog2_32(uint32_t v) |
80 | { |
81 | int n; |
82 | |
83 | #ifdef __i686__ |
84 | __asm__("bsrl %1,%0 ; cmovz %2,%0\n" |
85 | : "=&r" (n) |
86 | : "rm" (v), "r" (0)); |
87 | #else |
88 | __asm__("bsrl %1,%0 ; jnz 1f ; xorl %0,%0\n" |
89 | "1:" |
90 | : "=&r" (n) |
91 | : "rm" (v)); |
92 | #endif |
93 | return n; |
94 | } |
95 | |
96 | #elif defined(HAVE___BUILTIN_CLZ) && INT_MAX == 2147483647 |
97 | |
98 | extern_inline int const_func ilog2_32(uint32_t v) |
99 | { |
100 | if (!v) |
101 | return 0; |
102 | |
103 | return __builtin_clz(v) ^ 31; |
104 | } |
105 | |
106 | #elif defined(HAVE__BITSCANREVERSE) |
107 | |
108 | extern_inline int const_func ilog2_32(uint32_t v) |
109 | { |
110 | unsigned long ix; |
111 | return _BitScanReverse(&ix, v) ? v : 0; |
112 | } |
113 | |
114 | #else |
115 | |
116 | extern_inline int const_func ilog2_32(uint32_t v) |
117 | { |
118 | int p = 0; |
119 | |
120 | ROUND(v, p, 16); |
121 | ROUND(v, p, 8); |
122 | ROUND(v, p, 4); |
123 | ROUND(v, p, 2); |
124 | ROUND(v, p, 1); |
125 | |
126 | return p; |
127 | } |
128 | |
129 | #endif |
130 | |
131 | #if defined(__GNUC__) && defined(__x86_64__) |
132 | |
133 | extern_inline int const_func ilog2_64(uint64_t v) |
134 | { |
135 | uint64_t n; |
136 | |
137 | __asm__("bsrq %1,%0" |
138 | : "=r" (n) |
139 | : "rm" (v), "0" (UINT64_C(0))); |
140 | return n; |
141 | } |
142 | |
143 | #elif defined(HAVE__BUILTIN_CLZLL) && LLONG_MAX == 9223372036854775807LL |
144 | |
145 | extern_inline int const_func ilog2_64(uint64_t v) |
146 | { |
147 | if (!v) |
148 | return 0; |
149 | |
150 | return __builtin_clzll(v) ^ 63; |
151 | } |
152 | |
153 | #elif defined(HAVE__BITSCANREVERSE64) |
154 | |
155 | extern_inline int const_func ilog2_64(uint64_t v) |
156 | { |
157 | unsigned long ix; |
158 | return _BitScanReverse64(&ix, v) ? ix : 0; |
159 | } |
160 | |
161 | #else |
162 | |
163 | extern_inline int const_func ilog2_64(uint64_t vv) |
164 | { |
165 | int p = 0; |
166 | uint32_t v; |
167 | |
168 | v = vv >> 32; |
169 | if (v) |
170 | p += 32; |
171 | else |
172 | v = vv; |
173 | |
174 | ROUND(v, p, 16); |
175 | ROUND(v, p, 8); |
176 | ROUND(v, p, 4); |
177 | ROUND(v, p, 2); |
178 | ROUND(v, p, 1); |
179 | |
180 | return p; |
181 | } |
182 | |
183 | #endif |
184 | |
185 | /* |
186 | * v == 0 ? 0 : is_power2(x) ? ilog2_X(v) : -1 |
187 | */ |
188 | extern_inline int const_func alignlog2_32(uint32_t v) |
189 | { |
190 | if (unlikely(v & (v-1))) |
191 | return -1; /* invalid alignment */ |
192 | |
193 | return ilog2_32(v); |
194 | } |
195 | |
196 | extern_inline int const_func alignlog2_64(uint64_t v) |
197 | { |
198 | if (unlikely(v & (v-1))) |
199 | return -1; /* invalid alignment */ |
200 | |
201 | return ilog2_64(v); |
202 | } |
203 | |
204 | #undef ROUND |
205 | |
206 | #endif /* extern_inline */ |
207 | |
208 | #endif /* ILOG2_H */ |
209 | |