ceph/src/boost/boost/safe_numerics/utility.hpp

   1 #ifndef BOOST_NUMERIC_UTILITY_HPP
   2 #define BOOST_NUMERIC_UTILITY_HPP
   3
   4 //  Copyright (c) 2015 Robert Ramey
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9
  10 #include <cstdint> // intmax_t, uintmax_t, uint8_t, ...
  11 #include <algorithm>
  12 #include <type_traits> // conditional
  13 #include <limits>
  14 #include <cassert>
  15 #include <utility> // pair
  16
  17 #include <boost/integer.hpp> // (u)int_t<>::least, exact
  18
  19 namespace boost {
  20 namespace safe_numerics {
  21 namespace utility {
  22
  23 ///////////////////////////////////////////////////////////////////////////////
  24 // used for debugging
  25
  26 // provokes warning message with names of type T
  27 // usage - print_types<T, ...>;
  28 // see https://cukic.co/2019/02/19/tmp-testing-and-debugging-templates
  29
  30 /*
  31 template<typename Tx>
  32 using print_type = typename Tx::error_message;
  33 */
  34 template <typename... Ts>
  35 struct [[deprecated]] print_types {};
  36
  37 // display value of constexpr during compilation
  38 // usage print_value(N) pn;
  39 template<int N>
  40 struct print_value {
  41     enum test : char {
  42         value = N < 0 ? N - 256 : N + 256
  43     };
  44 };
  45
  46 // static warning - same as static_assert but doesn't
  47 // stop compilation.
  48 template <typename T>
  49 struct static_test{};
  50
  51 template <>
  52 struct static_test<std::false_type>{
  53     [[deprecated]] static_test(){}
  54 };
  55
  56 template<typename T>
  57 using static_warning = static_test<T>;
  58
  59 /*
  60 // can be called by constexpr to produce a compile time
  61 // trap of parameter passed is false.
  62 // usage constexpr_assert(bool)
  63 constexpr int constexpr_assert(const bool tf){
  64     return 1 / tf;
  65 }
  66 */
  67
  68 ///////////////////////////////////////////////////////////////////////////////
  69 // return an integral constant equal to the the number of bits
  70 // held by some integer type (including the sign bit)
  71
  72 template<typename T>
  73 using bits_type = std::integral_constant<
  74     int,
  75     std::numeric_limits<T>::digits
  76     + (std::numeric_limits<T>::is_signed ? 1 : 0)
  77 >;
  78
  79 /*
  80 From http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
  81 Find the log base 2 of an integer with a lookup table
  82
  83     static const char LogTable256[256] =
  84     {
  85     #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
  86         -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
  87         LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
  88         LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
  89     };
  90
  91     unsigned int v; // 32-bit word to find the log of
  92     unsigned r;     // r will be lg(v)
  93     register unsigned int t, tt; // temporaries
  94
  95     if (tt = v >> 16)
  96     {
  97       r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
  98     }
  99     else
 100     {
 101       r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
 102     }
 103
 104 The lookup table method takes only about 7 operations to find the log of a 32-bit value.
 105 If extended for 64-bit quantities, it would take roughly 9 operations. Another operation
 106 can be trimmed off by using four tables, with the possible additions incorporated into each.
 107 Using int table elements may be faster, depending on your architecture.
 108 */
 109
 110 namespace ilog2_detail {
 111
 112     template<int N>
 113     constexpr inline unsigned int ilog2(const typename boost::uint_t<N>::exact & t){
 114         using half_type = typename boost::uint_t<N/2>::exact;
 115         const half_type upper_half = static_cast<half_type>(t >> N/2);
 116         const half_type lower_half = static_cast<half_type>(t);
 117         return upper_half == 0 ? ilog2<N/2>(lower_half) : N/2 + ilog2<N/2>(upper_half);
 118     }
 119     template<>
 120     constexpr inline unsigned int ilog2<8>(const typename boost::uint_t<8>::exact & t){
 121         #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
 122         const char LogTable256[256] = {
 123             static_cast<char>(-1), 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
 124             LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
 125             LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
 126         };
 127         return LogTable256[t];
 128     }
 129
 130 } // ilog2_detail
 131
 132 template<typename T>
 133 constexpr inline unsigned int ilog2(const T & t){
 134 //  log not defined for negative numbers
 135 //    assert(t > 0);
 136     if(t == 0)
 137         return 0;
 138     return ilog2_detail::ilog2<bits_type<T>::value>(
 139         static_cast<
 140             typename boost::uint_t<
 141                 bits_type<T>::value
 142             >::least
 143         >(t)
 144     );
 145 }
 146
 147 // the number of bits required to render the value in x
 148 // including sign bit
 149 template<typename T>
 150 constexpr inline unsigned int significant_bits(const T & t){
 151     return 1 + ((t < 0) ? ilog2(~t) : ilog2(t));
 152 }
 153
 154 /*
 155 // give the value t, return the number which corresponds
 156 // to all 1's which is higher than that number
 157 template<typename T>
 158 constexpr unsigned int bits_value(const T & t){
 159     const unsigned int sb = significant_bits(t);
 160     const unsigned int sb_max = significant_bits(std::numeric_limits<T>::max());
 161     return sb < sb_max ? ((sb << 1) - 1) : std::numeric_limits<T>::max();
 162 }
 163 */
 164
 165 ///////////////////////////////////////////////////////////////////////////////
 166 // meta functions returning types
 167
 168 // If we use std::max in here we get internal compiler errors
 169 // with MSVC (tested VC2017) ...
 170
 171 // Notes from https://en.cppreference.com/w/cpp/algorithm/max
 172 // Capturing the result of std::max by reference if one of the parameters
 173 // is rvalue produces a dangling reference if that parameter is returned.
 174
 175 template <class T>
 176 // turns out this problem crashes all versions of gcc compilers.  So
 177 // make sure we return by value
 178 //constexpr const T & max(
 179 constexpr inline T max(
 180     const T & lhs,
 181     const T & rhs
 182 ){
 183     return lhs > rhs ? lhs : rhs;
 184 }
 185
 186 // given a signed range, return type required to hold all the values
 187 // in the range
 188 template<
 189     std::intmax_t Min,
 190     std::intmax_t Max
 191 >
 192 using signed_stored_type = typename boost::int_t<
 193     max(
 194         significant_bits(Min),
 195         significant_bits(Max)
 196     ) + 1
 197 >::least ;
 198
 199 // given an unsigned range, return type required to hold all the values
 200 // in the range
 201 template<
 202     std::uintmax_t Min,
 203     std::uintmax_t Max
 204 >
 205 // unsigned range
 206 using unsigned_stored_type = typename boost::uint_t<
 207     significant_bits(Max)
 208 >::least;
 209
 210 ///////////////////////////////////////////////////////////////////////////////
 211 // constexpr functions
 212
 213 // need our own version because official version
 214 // a) is not constexpr
 215 // b) is not guarenteed to handle non-assignable types
 216 template<typename T>
 217 constexpr inline std::pair<T, T>
 218 minmax(const std::initializer_list<T> & l){
 219     assert(l.size() > 0);
 220     const T * minimum = l.begin();
 221     const T * maximum = l.begin();
 222     for(const T * i = l.begin(); i != l.end(); ++i){
 223         if(*i < * minimum)
 224             minimum = i;
 225         else
 226         if(* maximum < *i)
 227             maximum = i;
 228     }
 229     return std::pair<T, T>{* minimum, * maximum};
 230 }
 231
 232 // for any given t
 233 // a) figure number of significant bits
 234 // b) return a value with all significant bits set
 235 // so for example:
 236 // 3 == round_out(2) because
 237 // 2 == 10 and 3 == 11
 238 template<typename T>
 239 constexpr inline T round_out(const T & t){
 240     if(t >= 0){
 241         const std::uint8_t sb = utility::significant_bits(t);
 242         return (sb < sizeof(T) * 8)
 243             ? ((T)1 << sb) - 1
 244             : std::numeric_limits<T>::max();
 245     }
 246     else{
 247         const std::uint8_t sb = utility::significant_bits(~t);
 248         return (sb < sizeof(T) * 8)
 249             ? ~(((T)1 << sb) - 1)
 250             : std::numeric_limits<T>::min();
 251     }
 252 }
 253
 254 } // utility
 255 } // safe_numerics
 256 } // boost
 257
 258 #endif  // BOOST_NUMERIC_UTILITY_HPP