|
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 |