Warning: This file is not a C or C++ file. It does not have highlighting.
| 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> |
| 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> |
| 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> |
| 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> |
| 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 | |
| 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 | |
| 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 |
Warning: This file is not a C or C++ file. It does not have highlighting.