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
LeadingZeroBitCount(std::uint64_t x)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
LeadingZeroBitCount(std::uint32_t x)66 inline constexpr int LeadingZeroBitCount(std::uint32_t x) {
67 return LeadingZeroBitCount(static_cast<std::uint64_t>(x)) - 32;
68 }
69
LeadingZeroBitCount(std::uint16_t x)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
LeadingZeroBitCount(std::uint8_t x)88 inline constexpr int LeadingZeroBitCount(std::uint8_t x) {
89 return eightBitLeadingZeroBitCount[x];
90 }
91
BitsNeededFor(A x)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