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> 20 #include <boost/integer_fwd.hpp> 21 22 namespace boost { 23 24 namespace detail { 25 26 namespace static_log2_impl { 27 28 // choose_initial_n<> 29 // 30 // Recursively doubles its integer argument, until it 31 // becomes >= of the "width" (C99, 6.2.6.2p4) of 32 // static_log2_argument_type. 33 // 34 // Used to get the maximum power of two less then the width. 35 // 36 // Example: if on your platform argument_type has 48 value 37 // bits it yields n=32. 38 // 39 // It's easy to prove that, starting from such a value 40 // of n, the core algorithm works correctly for any width 41 // of static_log2_argument_type and that recursion always 42 // terminates with x = 1 and n = 0 (see the algorithm's 43 // invariant). 44 45 typedef boost::static_log2_argument_type argument_type; 46 typedef boost::static_log2_result_type result_type; 47 48 template <result_type n> 49 struct choose_initial_n { 50 51 BOOST_STATIC_CONSTANT(bool, 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 BOOST_STATIC_CONSTANT(bool, 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 template <static_log2_argument_type x> 111 struct static_log2 { 112 113 BOOST_STATIC_CONSTANT( 114 static_log2_result_type, 115 value = detail::static_log2_impl::static_log2_impl<x>::value 116 ); 117 118 }; 119 120 121 template <> 122 struct static_log2<0> { }; 123 124 } 125 126 #endif // include guard 127