blob: 5140f370d460c16d7b3a3d0c9babfcf27f437cb0 [file] [log] [blame]
Jeff Thompsona28eed82013-08-22 16:21:10 -07001// -------------- 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
Jeff Thompson3d613fd2013-10-15 15:39:04 -070016#ifndef NDNBOOST_INTEGER_STATIC_LOG2_HPP
17#define NDNBOOST_INTEGER_STATIC_LOG2_HPP
Jeff Thompsona28eed82013-08-22 16:21:10 -070018
19#include "ndnboost/integer_fwd.hpp" // for ndnboost::intmax_t
20
21namespace ndnboost {
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 ndnboost::static_log2_argument_type argument_type;
45 typedef ndnboost::static_log2_result_type result_type;
46
47 template <result_type n>
48 struct choose_initial_n {
49
Jeff Thompson3d613fd2013-10-15 15:39:04 -070050 NDNBOOST_STATIC_CONSTANT(bool, c = (argument_type(1) << n << n) != 0);
51 NDNBOOST_STATIC_CONSTANT(
Jeff Thompsona28eed82013-08-22 16:21:10 -070052 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> {
Jeff Thompson3d613fd2013-10-15 15:39:04 -070060 NDNBOOST_STATIC_CONSTANT(result_type, value = 0);
Jeff Thompsona28eed82013-08-22 16:21:10 -070061 };
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
Jeff Thompson3d613fd2013-10-15 15:39:04 -070087 NDNBOOST_STATIC_CONSTANT(bool, c = (x >> n) > 0); // x >= 2**n ?
88 NDNBOOST_STATIC_CONSTANT(
Jeff Thompsona28eed82013-08-22 16:21:10 -070089 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> {
Jeff Thompson3d613fd2013-10-15 15:39:04 -070097 NDNBOOST_STATIC_CONSTANT(result_type, value = 0);
Jeff Thompsona28eed82013-08-22 16:21:10 -070098 };
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
Jeff Thompson3d613fd2013-10-15 15:39:04 -0700112 NDNBOOST_STATIC_CONSTANT(
Jeff Thompsona28eed82013-08-22 16:21:10 -0700113 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