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