Line data    Source code

       1              : /*
       2              :  *
       3              :  *    Copyright (c) 2026 Project CHIP Authors
       4              :  *
       5              :  *    Licensed under the Apache License, Version 2.0 (the "License");
       6              :  *    you may not use this file except in compliance with the License.
       7              :  *    You may obtain a copy of the License at
       8              :  *
       9              :  *        http://www.apache.org/licenses/LICENSE-2.0
      10              :  *
      11              :  *    Unless required by applicable law or agreed to in writing, software
      12              :  *    distributed under the License is distributed on an "AS IS" BASIS,
      13              :  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      14              :  *    See the License for the specific language governing permissions and
      15              :  *    limitations under the License.
      16              :  */
      17              : 
      18              : #pragma once
      19              : 
      20              : #include <type_traits>
      21              : 
      22              : namespace chip {
      23              : 
      24              : /**
      25              :  * Returns the number of 1 bits in the specified word (population count).
      26              :  *
      27              :  * The base template uses a portable software implementation. Explicit
      28              :  * specializations below use compiler builtins where available.
      29              :  */
      30              : template <typename T>
      31              : constexpr int PopCount(T word)
      32              : {
      33              :     static_assert(std::is_integral_v<T> && std::is_unsigned_v<T>, "PopCount requires an unsigned integer type");
      34              :     int count = 0;
      35              :     while (word)
      36              :     {
      37              :         count++;
      38              :         word &= static_cast<T>(word - 1);
      39              :     }
      40              :     return count;
      41              : }
      42              : 
      43              : // GCC and Clang both define __GNUC__ and provide these builtins. They map
      44              : // directly to a single instruction on most architectures (e.g. x86 POPCNT,
      45              : // ARM VCNT). The three variants cover the three distinct widths that the
      46              : // standard guarantees: unsigned int, unsigned long, unsigned long long.
      47              : #if defined(__GNUC__)
      48              : template <>
      49           43 : constexpr inline int PopCount<unsigned int>(unsigned int word)
      50              : {
      51           43 :     return __builtin_popcount(word);
      52              : }
      53              : 
      54              : template <>
      55            3 : constexpr inline int PopCount<unsigned long>(unsigned long word)
      56              : {
      57            3 :     return __builtin_popcountl(word);
      58              : }
      59              : 
      60              : template <>
      61           64 : constexpr inline int PopCount<unsigned long long>(unsigned long long word)
      62              : {
      63           64 :     return __builtin_popcountll(word);
      64              : }
      65              : #endif // defined(__GNUC__)
      66              : 
      67              : // Narrow types delegate to unsigned int. Even in the software fallback,
      68              : // operating on a full int avoids repeated masking with a narrow type and
      69              : // lets the compiler use its natural word size. When the builtin specialization
      70              : // above is available they also benefit from it automatically.
      71              : template <>
      72            4 : constexpr inline int PopCount<unsigned char>(unsigned char word)
      73              : {
      74            4 :     return PopCount(static_cast<unsigned int>(word));
      75              : }
      76              : 
      77              : template <>
      78            4 : constexpr inline int PopCount<unsigned short>(unsigned short word)
      79              : {
      80            4 :     return PopCount(static_cast<unsigned int>(word));
      81              : }
      82              : 
      83              : } // namespace chip