1 /*
2 * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_UTILITIES_COUNT_LEADING_ZEROS_HPP
26 #define SHARE_UTILITIES_COUNT_LEADING_ZEROS_HPP
27
28 #include "utilities/debug.hpp"
29 #include "utilities/globalDefinitions.hpp"
30
31 // uint32_t count_leading_zeros(T x)
32
33 // Return the number of leading zeros in x, e.g. the zero-based index
34 // of the most significant set bit in x. Undefined for 0.
35
36 // We implement and support variants for 8, 16, 32 and 64 bit integral types.
37 template <typename T, size_t n> struct CountLeadingZerosImpl;
38
count_leading_zeros(T v)39 template <typename T> unsigned count_leading_zeros(T v) {
40 assert(v != 0, "precondition");
41 return CountLeadingZerosImpl<T, sizeof(T)>::doit(v);
42 }
43
44 /*****************************************************************************
45 * GCC and compatible (including Clang)
46 *****************************************************************************/
47 #if defined(TARGET_COMPILER_gcc)
48
49 template <typename T> struct CountLeadingZerosImpl<T, 1> {
doitCountLeadingZerosImpl50 static unsigned doit(T v) {
51 return __builtin_clz((uint32_t)v & 0xFF) - 24u;
52 }
53 };
54
55 template <typename T> struct CountLeadingZerosImpl<T, 2> {
doitCountLeadingZerosImpl56 static unsigned doit(T v) {
57 return __builtin_clz((uint32_t)v & 0xFFFF) - 16u;
58 }
59 };
60
61 template <typename T> struct CountLeadingZerosImpl<T, 4> {
doitCountLeadingZerosImpl62 static unsigned doit(T v) {
63 return __builtin_clz(v);
64 }
65 };
66
67 template <typename T> struct CountLeadingZerosImpl<T, 8> {
doitCountLeadingZerosImpl68 static unsigned doit(T v) {
69 return __builtin_clzll(v);
70 }
71 };
72
73 /*****************************************************************************
74 * Microsoft Visual Studio
75 *****************************************************************************/
76 #elif defined(TARGET_COMPILER_visCPP)
77
78 #include <intrin.h>
79 #pragma intrinsic(_BitScanReverse)
80
81 #ifdef _LP64
82 #pragma intrinsic(_BitScanReverse64)
83 #endif
84
85 template <typename T> struct CountLeadingZerosImpl<T, 1> {
doitCountLeadingZerosImpl86 static unsigned doit(T v) {
87 unsigned long index;
88 _BitScanReverse(&index, (uint32_t)v & 0xFF);
89 return 7u - index;
90 }
91 };
92
93 template <typename T> struct CountLeadingZerosImpl<T, 2> {
doitCountLeadingZerosImpl94 static unsigned doit(T v) {
95 unsigned long index;
96 _BitScanReverse(&index, (uint32_t)v & 0xFFFF);
97 return 15u - index;
98 }
99 };
100
101 template <typename T> struct CountLeadingZerosImpl<T, 4> {
doitCountLeadingZerosImpl102 static unsigned doit(T v) {
103 unsigned long index;
104 _BitScanReverse(&index, v);
105 return 31u - index;
106 }
107 };
108
109 template <typename T> struct CountLeadingZerosImpl<T, 8> {
doitCountLeadingZerosImpl110 static unsigned doit(T v) {
111 #ifdef _LP64
112 unsigned long index;
113 _BitScanReverse64(&index, v);
114 return 63u - index;
115 #else
116 uint64_t high = ((uint64_t)v) >> 32ULL;
117 if (high != 0) {
118 return count_leading_zeros((uint32_t)high);
119 } else {
120 return count_leading_zeros((uint32_t)v) + 32;
121 }
122 #endif
123 }
124 };
125
126 /*****************************************************************************
127 * IBM XL C/C++
128 *****************************************************************************/
129 #elif defined(TARGET_COMPILER_xlc)
130
131 #include <builtins.h>
132
133 template <typename T> struct CountLeadingZerosImpl<T, 1> {
doitCountLeadingZerosImpl134 static unsigned doit(T v) {
135 return __cntlz4((uint32_t)v & 0xFF) - 24u;
136 }
137 };
138
139 template <typename T> struct CountLeadingZerosImpl<T, 2> {
doitCountLeadingZerosImpl140 static unsigned doit(T v) {
141 return __cntlz4((uint32_t)v & 0xFFFF) - 16u;
142 }
143 };
144
145 template <typename T> struct CountLeadingZerosImpl<T, 4> {
doitCountLeadingZerosImpl146 static unsigned doit(T v) {
147 return __cntlz4(v);
148 }
149 };
150
151 template <typename T> struct CountLeadingZerosImpl<T, 8> {
doitCountLeadingZerosImpl152 static unsigned doit(T v) {
153 return __cntlz8(v);
154 }
155 };
156
157 /*****************************************************************************
158 * Fallback
159 *****************************************************************************/
160 #else
161
count_leading_zeros_32(uint32_t x)162 inline uint32_t count_leading_zeros_32(uint32_t x) {
163 assert(x != 0, "precondition");
164
165 // Efficient and portable fallback implementation:
166 // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
167 // - with positions xor'd by 31 to get number of leading zeros
168 // rather than position of highest bit.
169 static const uint32_t MultiplyDeBruijnBitPosition[32] = {
170 31, 22, 30, 21, 18, 10, 29, 2, 20, 17, 15, 13, 9, 6, 28, 1,
171 23, 19, 11, 3, 16, 14, 7, 24, 12, 4, 8, 25, 5, 26, 27, 0
172 };
173
174 // First round down to one less than a power of 2
175 x |= x >> 1;
176 x |= x >> 2;
177 x |= x >> 4;
178 x |= x >> 8;
179 x |= x >> 16;
180 // Multiply by a magic constant which ensure the highest 5 bits point to
181 // the right index in the lookup table
182 return MultiplyDeBruijnBitPosition[(x * 0x07c4acddu) >> 27u];
183 }
184
185 template <typename T> struct CountLeadingZerosImpl<T, 1> {
doitCountLeadingZerosImpl186 static unsigned doit(T v) {
187 return count_leading_zeros_32((uint32_t)v & 0xFF) - 24u;
188 }
189 };
190
191 template <typename T> struct CountLeadingZerosImpl<T, 2> {
doitCountLeadingZerosImpl192 static unsigned doit(T v) {
193 return count_leading_zeros_32((uint32_t)v & 0xFFFF) - 16u;
194 }
195 };
196
197 template <typename T> struct CountLeadingZerosImpl<T, 4> {
doitCountLeadingZerosImpl198 static unsigned doit(T v) {
199 return count_leading_zeros_32(v);
200 }
201 };
202
203 template <typename T> struct CountLeadingZerosImpl<T, 8> {
doitCountLeadingZerosImpl204 static unsigned doit(T v) {
205 uint64_t high = ((uint64_t)v) >> 32ULL;
206 if (high != 0) {
207 return count_leading_zeros_32((uint32_t)high);
208 } else {
209 return count_leading_zeros_32((uint32_t)v) + 32u;
210 }
211 }
212 };
213
214 #endif
215
216 #endif // SHARE_UTILITIES_COUNT_LEADING_ZEROS_HPP
217