Warning: This file is not a C or C++ file. It does not have highlighting.
1 | //===-- include/flang/Common/leading-zero-bit-count.h -----------*- C++ -*-===// |
---|---|
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #ifndef FORTRAN_COMMON_LEADING_ZERO_BIT_COUNT_H_ |
10 | #define FORTRAN_COMMON_LEADING_ZERO_BIT_COUNT_H_ |
11 | |
12 | // A fast and portable function that implements Fortran's LEADZ intrinsic |
13 | // function, which counts the number of leading (most significant) zero bit |
14 | // positions in an integer value. (If the most significant bit is set, the |
15 | // leading zero count is zero; if no bit is set, the leading zero count is the |
16 | // word size in bits; otherwise, it's the largest left shift count that |
17 | // doesn't reduce the number of bits in the word that are set.) |
18 | |
19 | #include <cinttypes> |
20 | |
21 | namespace Fortran::common { |
22 | namespace { |
23 | // The following magic constant is a binary deBruijn sequence. |
24 | // It has the remarkable property that if one extends it |
25 | // (virtually) on the right with 5 more zero bits, then all |
26 | // of the 64 contiguous framed blocks of six bits in the |
27 | // extended 69-bit sequence are distinct. Consequently, |
28 | // if one shifts it left by any shift count [0..63] with |
29 | // truncation and extracts the uppermost six bit field |
30 | // of the shifted value, each shift count maps to a distinct |
31 | // field value. That means that we can map those 64 field |
32 | // values back to the shift counts that produce them, |
33 | // and (the point) this means that we can shift this value |
34 | // by an unknown bit count in [0..63] and then figure out |
35 | // what that count must have been. |
36 | // 0 7 e d d 5 e 5 9 a 4 e 2 8 c 2 |
37 | // 0000011111101101110101011110010110011010010011100010100011000010 |
38 | static constexpr std::uint64_t deBruijn{0x07edd5e59a4e28c2}; |
39 | static constexpr std::uint8_t mapping[64]{63, 0, 58, 1, 59, 47, 53, 2, 60, 39, |
40 | 48, 27, 54, 33, 42, 3, 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, |
41 | 14, 22, 4, 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, |
42 | 56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5}; |
43 | } // namespace |
44 | |
45 | inline constexpr int LeadingZeroBitCount(std::uint64_t x) { |
46 | if (x == 0) { |
47 | return 64; |
48 | } else { |
49 | x |= x >> 1; |
50 | x |= x >> 2; |
51 | x |= x >> 4; |
52 | x |= x >> 8; |
53 | x |= x >> 16; |
54 | x |= x >> 32; |
55 | // All of the bits below the uppermost set bit are now also set. |
56 | x -= x >> 1; // All of the bits below the uppermost are now clear. |
57 | // x now has exactly one bit set, so it is a power of two, so |
58 | // multiplication by x is equivalent to a left shift by its |
59 | // base-2 logarithm. We calculate that unknown base-2 logarithm |
60 | // by shifting the deBruijn sequence and mapping the framed value. |
61 | int base2Log{mapping[(x * deBruijn) >> 58]}; |
62 | return 63 - base2Log; // convert to leading zero count |
63 | } |
64 | } |
65 | |
66 | inline constexpr int LeadingZeroBitCount(std::uint32_t x) { |
67 | return LeadingZeroBitCount(static_cast<std::uint64_t>(x)) - 32; |
68 | } |
69 | |
70 | inline constexpr int LeadingZeroBitCount(std::uint16_t x) { |
71 | return LeadingZeroBitCount(static_cast<std::uint64_t>(x)) - 48; |
72 | } |
73 | |
74 | namespace { |
75 | static constexpr std::uint8_t eightBitLeadingZeroBitCount[256]{8, 7, 6, 6, 5, 5, |
76 | 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, |
77 | 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, |
78 | 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
79 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
80 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, |
81 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
82 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
83 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
84 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
85 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; |
86 | } |
87 | |
88 | inline constexpr int LeadingZeroBitCount(std::uint8_t x) { |
89 | return eightBitLeadingZeroBitCount[x]; |
90 | } |
91 | |
92 | template <typename A> inline constexpr int BitsNeededFor(A x) { |
93 | return 8 * sizeof x - LeadingZeroBitCount(x); |
94 | } |
95 | } // namespace Fortran::common |
96 | #endif // FORTRAN_COMMON_LEADING_ZERO_BIT_COUNT_H_ |
97 |
Warning: This file is not a C or C++ file. It does not have highlighting.