Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / 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