1 //===-- include/flang/Common/bit-population-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_BIT_POPULATION_COUNT_H_
10 #define FORTRAN_COMMON_BIT_POPULATION_COUNT_H_
11
12 // Fast and portable functions that implement Fortran's POPCNT and POPPAR
13 // intrinsic functions. POPCNT returns the number of bits that are set (1)
14 // in its argument. POPPAR is a parity function that returns true
15 // when POPCNT is odd.
16
17 #include <climits>
18 #include <type_traits>
19
20 namespace Fortran::common {
21
22 template <typename INT,
23 std::enable_if_t<(sizeof(INT) > 4 && sizeof(INT) <= 8), int> = 0>
BitPopulationCount(INT x)24 inline constexpr int BitPopulationCount(INT x) {
25 // In each of the 32 2-bit fields, count the bits that were present.
26 // This leaves a value [0..2] in each of these 2-bit fields.
27 x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555);
28 // Combine into 16 4-bit fields, each holding [0..4]
29 x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
30 // Now 8 8-bit fields, each with [0..8] in their lower 4 bits.
31 x = (x & 0x0f0f0f0f0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f0f0f0f0f);
32 // Now 4 16-bit fields, each with [0..16] in their lower 5 bits.
33 x = (x & 0x001f001f001f001f) + ((x >> 8) & 0x001f001f001f001f);
34 // Now 2 32-bit fields, each with [0..32] in their lower 6 bits.
35 x = (x & 0x0000003f0000003f) + ((x >> 16) & 0x0000003f0000003f);
36 // Last step: 1 64-bit field, with [0..64]
37 return (x & 0x7f) + (x >> 32);
38 }
39
40 template <typename INT,
41 std::enable_if_t<(sizeof(INT) > 2 && sizeof(INT) <= 4), int> = 0>
BitPopulationCount(INT x)42 inline constexpr int BitPopulationCount(INT x) {
43 // In each of the 16 2-bit fields, count the bits that were present.
44 // This leaves a value [0..2] in each of these 2-bit fields.
45 x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
46 // Combine into 8 4-bit fields, each holding [0..4]
47 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
48 // Now 4 8-bit fields, each with [0..8] in their lower 4 bits.
49 x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
50 // Now 2 16-bit fields, each with [0..16] in their lower 5 bits.
51 x = (x & 0x001f001f) + ((x >> 8) & 0x001f001f);
52 // Last step: 1 32-bit field, with [0..32]
53 return (x & 0x3f) + (x >> 16);
54 }
55
56 template <typename INT, std::enable_if_t<sizeof(INT) == 2, int> = 0>
BitPopulationCount(INT x)57 inline constexpr int BitPopulationCount(INT x) {
58 // In each of the 8 2-bit fields, count the bits that were present.
59 // This leaves a value [0..2] in each of these 2-bit fields.
60 x = (x & 0x5555) + ((x >> 1) & 0x5555);
61 // Combine into 4 4-bit fields, each holding [0..4]
62 x = (x & 0x3333) + ((x >> 2) & 0x3333);
63 // Now 2 8-bit fields, each with [0..8] in their lower 4 bits.
64 x = (x & 0x0f0f) + ((x >> 4) & 0x0f0f);
65 // Last step: 1 16-bit field, with [0..16]
66 return (x & 0x1f) + (x >> 8);
67 }
68
69 template <typename INT, std::enable_if_t<sizeof(INT) == 1, int> = 0>
BitPopulationCount(INT x)70 inline constexpr int BitPopulationCount(INT x) {
71 // In each of the 4 2-bit fields, count the bits that were present.
72 // This leaves a value [0..2] in each of these 2-bit fields.
73 x = (x & 0x55) + ((x >> 1) & 0x55);
74 // Combine into 2 4-bit fields, each holding [0..4]
75 x = (x & 0x33) + ((x >> 2) & 0x33);
76 // Last step: 1 8-bit field, with [0..8]
77 return (x & 0xf) + (x >> 4);
78 }
79
Parity(INT x)80 template <typename INT> inline constexpr bool Parity(INT x) {
81 return BitPopulationCount(x) & 1;
82 }
83
84 // "Parity is for farmers." -- Seymour R. Cray
85
TrailingZeroBitCount(INT x)86 template <typename INT> inline constexpr int TrailingZeroBitCount(INT x) {
87 if ((x & 1) != 0) {
88 return 0; // fast path for odd values
89 } else if (x == 0) {
90 return CHAR_BIT * sizeof x;
91 } else {
92 return BitPopulationCount(static_cast<INT>(x ^ (x - 1))) - 1;
93 }
94 }
95 } // namespace Fortran::common
96 #endif // FORTRAN_COMMON_BIT_POPULATION_COUNT_H_
97