]>
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 | ||
19 | #include "boost/integer_fwd.hpp" // for boost::intmax_t | |
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 boost::static_log2_argument_type argument_type; | |
45 | typedef boost::static_log2_result_type result_type; | |
46 | ||
47 | template <result_type n> | |
48 | struct choose_initial_n { | |
49 | ||
50 | BOOST_STATIC_CONSTANT(bool, c = (argument_type(1) << n << n) != 0); | |
51 | BOOST_STATIC_CONSTANT( | |
52 | result_type, | |
53 | value = !c*n + choose_initial_n<2*c*n>::value | |
54 | ); | |
55 | ||
56 | }; | |
57 | ||
58 | template <> | |
59 | struct choose_initial_n<0> { | |
60 | BOOST_STATIC_CONSTANT(result_type, value = 0); | |
61 | }; | |
62 | ||
63 | ||
64 | ||
65 | // start computing from n_zero - must be a power of two | |
66 | const result_type n_zero = 16; | |
67 | const result_type initial_n = choose_initial_n<n_zero>::value; | |
68 | ||
69 | // static_log2_impl<> | |
70 | // | |
71 | // * Invariant: | |
72 | // 2n | |
73 | // 1 <= x && x < 2 at the start of each recursion | |
74 | // (see also choose_initial_n<>) | |
75 | // | |
76 | // * Type requirements: | |
77 | // | |
78 | // argument_type maybe any unsigned type with at least n_zero + 1 | |
79 | // value bits. (Note: If larger types will be standardized -e.g. | |
80 | // unsigned long long- then the argument_type typedef can be | |
81 | // changed without affecting the rest of the code.) | |
82 | // | |
83 | ||
84 | template <argument_type x, result_type n = initial_n> | |
85 | struct static_log2_impl { | |
86 | ||
87 | BOOST_STATIC_CONSTANT(bool, c = (x >> n) > 0); // x >= 2**n ? | |
88 | BOOST_STATIC_CONSTANT( | |
89 | result_type, | |
90 | value = c*n + (static_log2_impl< (x>>c*n), n/2 >::value) | |
91 | ); | |
92 | ||
93 | }; | |
94 | ||
95 | template <> | |
96 | struct static_log2_impl<1, 0> { | |
97 | BOOST_STATIC_CONSTANT(result_type, value = 0); | |
98 | }; | |
99 | ||
100 | } | |
101 | } // detail | |
102 | ||
103 | ||
104 | ||
105 | // -------------------------------------- | |
106 | // static_log2<x> | |
107 | // ---------------------------------------- | |
108 | ||
109 | template <static_log2_argument_type x> | |
110 | struct static_log2 { | |
111 | ||
112 | BOOST_STATIC_CONSTANT( | |
113 | static_log2_result_type, | |
114 | value = detail::static_log2_impl::static_log2_impl<x>::value | |
115 | ); | |
116 | ||
117 | }; | |
118 | ||
119 | ||
120 | template <> | |
121 | struct static_log2<0> { }; | |
122 | ||
123 | } | |
124 | ||
125 | ||
126 | ||
127 | #endif // include guard |