Chris@16: // -------------- Boost static_log2.hpp header file  ----------------------- //
Chris@16: //
Chris@16: //                 Copyright (C) 2001 Daryle Walker.
Chris@16: //                 Copyright (C) 2003 Vesa Karvonen.
Chris@16: //                 Copyright (C) 2003 Gennaro Prota.
Chris@16: //
Chris@16: //     Distributed under the Boost Software License, Version 1.0.
Chris@16: //        (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //              http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: //         ---------------------------------------------------
Chris@16: //       See http://www.boost.org/libs/integer for documentation.
Chris@16: // ------------------------------------------------------------------------- //
Chris@16: 
Chris@16: 
Chris@16: #ifndef BOOST_INTEGER_STATIC_LOG2_HPP
Chris@16: #define BOOST_INTEGER_STATIC_LOG2_HPP
Chris@16: 
Chris@16: #include "boost/integer_fwd.hpp" // for boost::intmax_t
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:  namespace detail {
Chris@16: 
Chris@16:      namespace static_log2_impl {
Chris@16: 
Chris@16:      // choose_initial_n<>
Chris@16:      //
Chris@16:      // Recursively doubles its integer argument, until it
Chris@16:      // becomes >= of the "width" (C99, 6.2.6.2p4) of
Chris@16:      // static_log2_argument_type.
Chris@16:      //
Chris@16:      // Used to get the maximum power of two less then the width.
Chris@16:      //
Chris@16:      // Example: if on your platform argument_type has 48 value
Chris@16:      //          bits it yields n=32.
Chris@16:      //
Chris@16:      // It's easy to prove that, starting from such a value
Chris@16:      // of n, the core algorithm works correctly for any width
Chris@16:      // of static_log2_argument_type and that recursion always
Chris@16:      // terminates with x = 1 and n = 0 (see the algorithm's
Chris@16:      // invariant).
Chris@16: 
Chris@16:      typedef boost::static_log2_argument_type argument_type;
Chris@16:      typedef boost::static_log2_result_type result_type;
Chris@16: 
Chris@16:      template <result_type n>
Chris@16:      struct choose_initial_n {
Chris@16: 
Chris@16:          BOOST_STATIC_CONSTANT(bool, c = (argument_type(1) << n << n) != 0);
Chris@16:          BOOST_STATIC_CONSTANT(
Chris@16:              result_type,
Chris@16:              value = !c*n + choose_initial_n<2*c*n>::value
Chris@16:          );
Chris@16: 
Chris@16:      };
Chris@16: 
Chris@16:      template <>
Chris@16:      struct choose_initial_n<0> {
Chris@16:          BOOST_STATIC_CONSTANT(result_type, value = 0);
Chris@16:      };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:      // start computing from n_zero - must be a power of two
Chris@16:      const result_type n_zero = 16;
Chris@16:      const result_type initial_n = choose_initial_n<n_zero>::value;
Chris@16: 
Chris@16:      // static_log2_impl<>
Chris@16:      //
Chris@16:      // * Invariant:
Chris@16:      //                 2n
Chris@16:      //  1 <= x && x < 2    at the start of each recursion
Chris@16:      //                     (see also choose_initial_n<>)
Chris@16:      //
Chris@16:      // * Type requirements:
Chris@16:      //
Chris@16:      //   argument_type maybe any unsigned type with at least n_zero + 1
Chris@16:      //   value bits. (Note: If larger types will be standardized -e.g.
Chris@16:      //   unsigned long long- then the argument_type typedef can be
Chris@16:      //   changed without affecting the rest of the code.)
Chris@16:      //
Chris@16: 
Chris@16:      template <argument_type x, result_type n = initial_n>
Chris@16:      struct static_log2_impl {
Chris@16: 
Chris@16:          BOOST_STATIC_CONSTANT(bool, c = (x >> n) > 0); // x >= 2**n ?
Chris@16:          BOOST_STATIC_CONSTANT(
Chris@16:              result_type,
Chris@16:              value = c*n + (static_log2_impl< (x>>c*n), n/2 >::value)
Chris@16:          );
Chris@16: 
Chris@16:      };
Chris@16: 
Chris@16:      template <>
Chris@16:      struct static_log2_impl<1, 0> {
Chris@16:         BOOST_STATIC_CONSTANT(result_type, value = 0);
Chris@16:      };
Chris@16: 
Chris@16:      }
Chris@16:  } // detail
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:  // --------------------------------------
Chris@16:  // static_log2<x>
Chris@16:  // ----------------------------------------
Chris@16: 
Chris@16:  template <static_log2_argument_type x>
Chris@16:  struct static_log2 {
Chris@16: 
Chris@16:      BOOST_STATIC_CONSTANT(
Chris@16:          static_log2_result_type,
Chris@16:          value = detail::static_log2_impl::static_log2_impl<x>::value
Chris@16:      );
Chris@16: 
Chris@16:  };
Chris@16: 
Chris@16: 
Chris@16:  template <>
Chris@16:  struct static_log2<0> { };
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: #endif // include guard