ceph/src/boost/boost/integer/integer_log2.hpp

   1 // -----------------------------------------------------------
   2 // integer_log2.hpp
   3 //
   4 //   Gives the integer part of the logarithm, in base 2, of a
   5 // given number. Behavior is undefined if the argument is <= 0.
   6 //
   7 //        Copyright (c) 2003-2004, 2008 Gennaro Prota
   8 //            Copyright (c) 2022 Andrey Semashev
   9 //
  10 // Distributed under the Boost Software License, Version 1.0.
  11 //    (See accompanying file LICENSE_1_0.txt or copy at
  12 //          https://www.boost.org/LICENSE_1_0.txt)
  13 //
  14 // -----------------------------------------------------------
  15
  16 #ifndef BOOST_INTEGER_INTEGER_LOG2_HPP
  17 #define BOOST_INTEGER_INTEGER_LOG2_HPP
  18
  19 #include <climits>
  20 #include <limits>
  21 #include <boost/config.hpp>
  22 #include <boost/assert.hpp>
  23 #include <boost/cstdint.hpp>
  24 #include <boost/core/bit.hpp>
  25 #include <boost/core/enable_if.hpp>
  26 #include <boost/type_traits/is_integral.hpp>
  27 #include <boost/type_traits/make_unsigned.hpp>
  28
  29 namespace boost {
  30 namespace detail {
  31
  32 // helper to find the maximum power of two
  33 // less than p
  34 template< unsigned int p, unsigned int n, bool = ((2u * n) < p) >
  35 struct max_pow2_less :
  36     public max_pow2_less< p, 2u * n >
  37 {
  38 };
  39
  40 template< unsigned int p, unsigned int n >
  41 struct max_pow2_less< p, n, false >
  42 {
  43     BOOST_STATIC_CONSTANT(unsigned int, value = n);
  44 };
  45
  46 template< typename T >
  47 inline typename boost::disable_if< boost::is_integral< T >, int >::type integer_log2_impl(T x)
  48 {
  49     unsigned int n = detail::max_pow2_less<
  50         std::numeric_limits< T >::digits,
  51         CHAR_BIT / 2u
  52     >::value;
  53
  54     int result = 0;
  55     while (x != 1)
  56     {
  57         T t(x >> n);
  58         if (t)
  59         {
  60             result += static_cast< int >(n);
  61 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
  62             x = static_cast< T&& >(t);
  63 #else
  64             x = t;
  65 #endif
  66         }
  67         n >>= 1u;
  68     }
  69
  70     return result;
  71 }
  72
  73 template< typename T >
  74 inline typename boost::enable_if< boost::is_integral< T >, int >::type integer_log2_impl(T x)
  75 {
  76     // We could simply rely on numeric_limits but sometimes
  77     // Borland tries to use numeric_limits<const T>, because
  78     // of its usual const-related problems in argument deduction
  79     // - gps
  80     return static_cast< int >((sizeof(T) * CHAR_BIT - 1u) -
  81         boost::core::countl_zero(static_cast< typename boost::make_unsigned< T >::type >(x)));
  82 }
  83
  84 #if defined(BOOST_HAS_INT128)
  85 // We need to provide explicit overloads for __int128 because (a) boost/core/bit.hpp currently does not support it and
  86 // (b) std::numeric_limits are not specialized for __int128 in some standard libraries.
  87 inline int integer_log2_impl(boost::uint128_type x)
  88 {
  89     const boost::uint64_t x_hi = static_cast< boost::uint64_t >(x >> 64u);
  90     if (x_hi != 0u)
  91         return 127 - boost::core::countl_zero(x_hi);
  92     else
  93         return 63 - boost::core::countl_zero(static_cast< boost::uint64_t >(x));
  94 }
  95
  96 inline int integer_log2_impl(boost::int128_type x)
  97 {
  98     return detail::integer_log2_impl(static_cast< boost::uint128_type >(x));
  99 }
 100 #endif // defined(BOOST_HAS_INT128)
 101
 102 } // namespace detail
 103
 104
 105 // ------------
 106 // integer_log2
 107 // ------------
 108 template< typename T >
 109 inline int integer_log2(T x)
 110 {
 111     BOOST_ASSERT(x > 0);
 112     return detail::integer_log2_impl(x);
 113 }
 114
 115 } // namespace boost
 116
 117 #endif // BOOST_INTEGER_INTEGER_LOG2_HPP