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#include "utilities/count_trailing_zeros.hpp"
31
32#if defined(TARGET_COMPILER_visCPP)
33#include <intrin.h>
34#pragma intrinsic(_BitScanReverse)
35#elif defined(TARGET_COMPILER_xlc)
36#include <builtins.h>
37#endif
38
39// uint32_t count_leading_zeros(uint32_t x)
40// Return the number of leading zeros in x, e.g. the zero-based index
41// of the most significant set bit in x. Undefined for 0.
42inline uint32_t count_leading_zeros(uint32_t x) {
43 assert(x != 0, "precondition");
44#if defined(TARGET_COMPILER_gcc)
45 return __builtin_clz(x);
46#elif defined(TARGET_COMPILER_visCPP)
47 unsigned long index;
48 _BitScanReverse(&index, x);
49 return index ^ 31u;
50#elif defined(TARGET_COMPILER_xlc)
51 return __cntlz4(x);
52#else
53 // Efficient and portable fallback implementation:
54 // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
55 // - with positions xor'd by 31 to get number of leading zeros
56 // rather than position of highest bit.
57 static const int MultiplyDeBruijnBitPosition[32] = {
58 31, 22, 30, 21, 18, 10, 29, 2, 20, 17, 15, 13, 9, 6, 28, 1,
59 23, 19, 11, 3, 16, 14, 7, 24, 12, 4, 8, 25, 5, 26, 27, 0
60 };
61
62 x |= x >> 1; // first round down to one less than a power of 2
63 x |= x >> 2;
64 x |= x >> 4;
65 x |= x >> 8;
66 x |= x >> 16;
67 return MultiplyDeBruijnBitPosition[(uint32_t)( x * 0x07c4acddu ) >> 27];
68#endif
69}
70
71#endif // SHARE_UTILITIES_COUNT_LEADING_ZEROS_HPP
72