boost/integer/static_log2.hpp

   1 // -------------- Boost static_log2.hpp header file  ----------------------- //
   2 //
   3 //                 Copyright (C) 2001 Daryle Walker.
   4 //                 Copyright (C) 2003 Vesa Karvonen.
   5 //                 Copyright (C) 2003 Gennaro Prota.
   6 //
   7 //     Distributed under the Boost Software License, Version 1.0.
   8 //        (See accompanying file LICENSE_1_0.txt or copy at
   9 //              http://www.boost.org/LICENSE_1_0.txt)
  10 //
  11 //         ---------------------------------------------------
  12 //       See http://www.boost.org/libs/integer for documentation.
  13 // ------------------------------------------------------------------------- //
  14
  15
  16 #ifndef BOOST_INTEGER_STATIC_LOG2_HPP
  17 #define BOOST_INTEGER_STATIC_LOG2_HPP
  18
  19 #include "boost/config.hpp" // for BOOST_STATIC_CONSTANT
  20
  21 namespace boost {
  22
  23  namespace detail {
  24
  25      namespace static_log2_impl {
  26
  27      // choose_initial_n<>
  28      //
  29      // Recursively doubles its integer argument, until it
  30      // becomes >= of the "width" (C99, 6.2.6.2p4) of
  31      // static_log2_argument_type.
  32      //
  33      // Used to get the maximum power of two less then the width.
  34      //
  35      // Example: if on your platform argument_type has 48 value
  36      //          bits it yields n=32.
  37      //
  38      // It's easy to prove that, starting from such a value
  39      // of n, the core algorithm works correctly for any width
  40      // of static_log2_argument_type and that recursion always
  41      // terminates with x = 1 and n = 0 (see the algorithm's
  42      // invariant).
  43
  44      typedef unsigned long argument_type;
  45      typedef          int  result_type;
  46
  47
  48      template <result_type n>
  49      struct choose_initial_n {
  50
  51          enum { c = (argument_type(1) << n << n) != 0 };
  52          BOOST_STATIC_CONSTANT(
  53              result_type,
  54              value = !c*n + choose_initial_n<2*c*n>::value
  55          );
  56
  57      };
  58
  59      template <>
  60      struct choose_initial_n<0> {
  61          BOOST_STATIC_CONSTANT(result_type, value = 0);
  62      };
  63
  64
  65
  66      // start computing from n_zero - must be a power of two
  67      const result_type n_zero = 16;
  68      const result_type initial_n = choose_initial_n<n_zero>::value;
  69
  70      // static_log2_impl<>
  71      //
  72      // * Invariant:
  73      //                 2n
  74      //  1 <= x && x < 2    at the start of each recursion
  75      //                     (see also choose_initial_n<>)
  76      //
  77      // * Type requirements:
  78      //
  79      //   argument_type maybe any unsigned type with at least n_zero + 1
  80      //   value bits. (Note: If larger types will be standardized -e.g.
  81      //   unsigned long long- then the argument_type typedef can be
  82      //   changed without affecting the rest of the code.)
  83      //
  84
  85      template <argument_type x, result_type n = initial_n>
  86      struct static_log2_impl {
  87
  88          enum { c = (x >> n) > 0 }; // x >= 2**n ?
  89          BOOST_STATIC_CONSTANT(
  90              result_type,
  91              value = c*n + (static_log2_impl< (x>>c*n), n/2 >::value)
  92          );
  93
  94      };
  95
  96      template <>
  97      struct static_log2_impl<1, 0> {
  98         BOOST_STATIC_CONSTANT(result_type, value = 0);
  99      };
 100
 101      }
 102  } // detail
 103
 104
 105
 106  // --------------------------------------
 107  // static_log2<x>
 108  // ----------------------------------------
 109
 110  typedef detail::static_log2_impl::argument_type static_log2_argument_type;
 111  typedef detail::static_log2_impl::result_type   static_log2_result_type;
 112
 113
 114  template <static_log2_argument_type x>
 115  struct static_log2 {
 116
 117      BOOST_STATIC_CONSTANT(
 118          static_log2_result_type,
 119          value = detail::static_log2_impl::static_log2_impl<x>::value
 120      );
 121
 122  };
 123
 124
 125  template <>
 126  struct static_log2<0> { };
 127
 128 }
 129
 130
 131
 132 #endif // include guard