]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
20effc67 TL |
19 | #include <boost/config.hpp> |
20 | #include <boost/integer_fwd.hpp> | |
7c673cae FG |
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 | ||
7c673cae | 126 | #endif // include guard |