boost/boost/integer/static_log2.hpp

   1 //  Boost integer/static_log2.hpp header file  -------------------------------//
   2
   3 //  (C) Copyright Daryle Walker 2001.  Permission to copy, use, modify, sell and
   4 //  distribute this software is granted provided this copyright notice appears
   5 //  in all copies.  This software is provided "as is" without express or
   6 //  implied warranty, and with no claim as to its suitability for any purpose.
   7
   8 //  See http://www.boost.org for updates, documentation, and revision history.
   9
  10 #ifndef BOOST_INTEGER_STATIC_LOG2_HPP
  11 #define BOOST_INTEGER_STATIC_LOG2_HPP
  12
  13 #include <boost/integer_fwd.hpp>  // self include
  14
  15 #include <boost/config.hpp>  // for BOOST_STATIC_CONSTANT, etc.
  16 #include <boost/limits.hpp>  // for std::numeric_limits
  17
  18 #ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  19 #include <boost/pending/ct_if.hpp>  // for boost::ct_if<>
  20 #endif
  21
  22
  23 namespace boost
  24 {
  25
  26
  27 //  Implementation details  --------------------------------------------------//
  28
  29 namespace detail
  30 {
  31
  32 // Forward declarations
  33 template < unsigned long Val, int Place = 0, int Index
  34  = std::numeric_limits<unsigned long>::digits >
  35     struct static_log2_helper_t;
  36
  37 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  38
  39 template < unsigned long Val, int Place >
  40     struct static_log2_helper_t< Val, Place, 1 >;
  41
  42 #else
  43
  44 template < int Place >
  45     struct static_log2_helper_final_step;
  46
  47 template < unsigned long Val, int Place = 0, int Index
  48  = std::numeric_limits<unsigned long>::digits >
  49     struct static_log2_helper_nopts_t;
  50
  51 #endif
  52
  53 // Recursively build the logarithm by examining the upper bits
  54 template < unsigned long Val, int Place, int Index >
  55 struct static_log2_helper_t
  56 {
  57 private:
  58     BOOST_STATIC_CONSTANT( int, half_place = Index / 2 );
  59     BOOST_STATIC_CONSTANT( unsigned long, lower_mask = (1ul << half_place)
  60      - 1ul );
  61     BOOST_STATIC_CONSTANT( unsigned long, upper_mask = ~lower_mask );
  62     BOOST_STATIC_CONSTANT( bool, do_shift = (Val & upper_mask) != 0ul );
  63
  64     BOOST_STATIC_CONSTANT( unsigned long, new_val = do_shift ? (Val
  65      >> half_place) : Val );
  66     BOOST_STATIC_CONSTANT( int, new_place = do_shift ? (Place + half_place)
  67      : Place );
  68     BOOST_STATIC_CONSTANT( int, new_index = Index - half_place );
  69
  70 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  71     typedef static_log2_helper_t<new_val, new_place, new_index>  next_step_type;
  72 #else
  73     typedef static_log2_helper_nopts_t<new_val, new_place, new_index>  next_step_type;
  74 #endif
  75
  76 public:
  77     BOOST_STATIC_CONSTANT( int, value = next_step_type::value );
  78
  79 };  // boost::detail::static_log2_helper_t
  80
  81 // Non-recursive case
  82 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  83
  84 template < unsigned long Val, int Place >
  85 struct static_log2_helper_t< Val, Place, 1 >
  86 {
  87 public:
  88     BOOST_STATIC_CONSTANT( int, value = Place );
  89
  90 };  // boost::detail::static_log2_helper_t
  91
  92 #else
  93
  94 template < int Place >
  95 struct static_log2_helper_final_step
  96 {
  97 public:
  98     BOOST_STATIC_CONSTANT( int, value = Place );
  99
 100 };  // boost::detail::static_log2_helper_final_step
 101
 102 template < unsigned long Val, int Place, int Index >
 103 struct static_log2_helper_nopts_t
 104 {
 105 private:
 106     typedef static_log2_helper_t<Val, Place, Index>  recursive_step_type;
 107     typedef static_log2_helper_final_step<Place>     final_step_type;
 108
 109     typedef typename ct_if<( Index != 1 ), recursive_step_type,
 110      final_step_type>::type  next_step_type;
 111
 112 public:
 113     BOOST_STATIC_CONSTANT( int, value = next_step_type::value );
 114
 115 };  // boost::detail::static_log2_helper_nopts_t
 116
 117 #endif
 118
 119 }  // namespace detail
 120
 121
 122 //  Compile-time log-base-2 evaluator class declaration  ---------------------//
 123
 124 template < unsigned long Value >
 125 struct static_log2
 126 {
 127     BOOST_STATIC_CONSTANT( int, value
 128      = detail::static_log2_helper_t<Value>::value );
 129 };
 130
 131 template < >
 132 struct static_log2< 0ul >
 133 {
 134     // The logarithm of zero is undefined.
 135 };
 136
 137
 138 }  // namespace boost
 139
 140
 141 #endif  // BOOST_INTEGER_STATIC_LOG2_HPP