]>
Commit | Line | Data |
---|---|---|
92f5a8d4 TL |
1 | #ifndef BOOST_NUMERIC_UTILITY_HPP |
2 | #define BOOST_NUMERIC_UTILITY_HPP | |
3 | ||
4 | // Copyright (c) 2015 Robert Ramey | |
5 | // | |
6 | // Distributed under the Boost Software License, Version 1.0. (See | |
7 | // accompanying file LICENSE_1_0.txt or copy at | |
8 | // http://www.boost.org/LICENSE_1_0.txt) | |
9 | ||
10 | #include <cstdint> // intmax_t, uintmax_t, uint8_t, ... | |
11 | #include <algorithm> | |
12 | #include <type_traits> // conditional | |
13 | #include <limits> | |
14 | #include <cassert> | |
15 | #include <utility> // pair | |
16 | ||
17 | #include <boost/integer.hpp> // (u)int_t<>::least, exact | |
18 | ||
19 | namespace boost { | |
20 | namespace safe_numerics { | |
21 | namespace utility { | |
22 | ||
23 | /////////////////////////////////////////////////////////////////////////////// | |
24 | // used for debugging | |
25 | ||
26 | // provokes warning message with names of type T | |
27 | // usage - print_types<T, ...>; | |
28 | // see https://cukic.co/2019/02/19/tmp-testing-and-debugging-templates | |
29 | ||
30 | /* | |
31 | template<typename Tx> | |
32 | using print_type = typename Tx::error_message; | |
33 | */ | |
34 | template <typename... Ts> | |
35 | struct [[deprecated]] print_types {}; | |
36 | ||
37 | // display value of constexpr during compilation | |
38 | // usage print_value(N) pn; | |
39 | template<int N> | |
1e59de90 | 40 | struct print_value { |
92f5a8d4 TL |
41 | enum test : char { |
42 | value = N < 0 ? N - 256 : N + 256 | |
43 | }; | |
44 | }; | |
45 | ||
92f5a8d4 TL |
46 | // static warning - same as static_assert but doesn't |
47 | // stop compilation. | |
48 | template <typename T> | |
49 | struct static_test{}; | |
50 | ||
51 | template <> | |
52 | struct static_test<std::false_type>{ | |
53 | [[deprecated]] static_test(){} | |
54 | }; | |
55 | ||
56 | template<typename T> | |
1e59de90 | 57 | using static_warning = static_test<T>; |
92f5a8d4 TL |
58 | |
59 | /* | |
60 | // can be called by constexpr to produce a compile time | |
61 | // trap of parameter passed is false. | |
62 | // usage constexpr_assert(bool) | |
63 | constexpr int constexpr_assert(const bool tf){ | |
64 | return 1 / tf; | |
65 | } | |
66 | */ | |
67 | ||
68 | /////////////////////////////////////////////////////////////////////////////// | |
69 | // return an integral constant equal to the the number of bits | |
70 | // held by some integer type (including the sign bit) | |
71 | ||
72 | template<typename T> | |
73 | using bits_type = std::integral_constant< | |
74 | int, | |
75 | std::numeric_limits<T>::digits | |
76 | + (std::numeric_limits<T>::is_signed ? 1 : 0) | |
77 | >; | |
78 | ||
79 | /* | |
80 | From http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious | |
81 | Find the log base 2 of an integer with a lookup table | |
82 | ||
83 | static const char LogTable256[256] = | |
84 | { | |
85 | #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n | |
86 | -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, | |
87 | LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6), | |
88 | LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7) | |
89 | }; | |
90 | ||
91 | unsigned int v; // 32-bit word to find the log of | |
92 | unsigned r; // r will be lg(v) | |
93 | register unsigned int t, tt; // temporaries | |
94 | ||
95 | if (tt = v >> 16) | |
96 | { | |
97 | r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; | |
98 | } | |
99 | else | |
100 | { | |
101 | r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v]; | |
102 | } | |
103 | ||
104 | The lookup table method takes only about 7 operations to find the log of a 32-bit value. | |
105 | If extended for 64-bit quantities, it would take roughly 9 operations. Another operation | |
106 | can be trimmed off by using four tables, with the possible additions incorporated into each. | |
107 | Using int table elements may be faster, depending on your architecture. | |
108 | */ | |
109 | ||
110 | namespace ilog2_detail { | |
111 | ||
1e59de90 TL |
112 | template<int N> |
113 | constexpr inline unsigned int ilog2(const typename boost::uint_t<N>::exact & t){ | |
114 | using half_type = typename boost::uint_t<N/2>::exact; | |
115 | const half_type upper_half = static_cast<half_type>(t >> N/2); | |
116 | const half_type lower_half = static_cast<half_type>(t); | |
117 | return upper_half == 0 ? ilog2<N/2>(lower_half) : N/2 + ilog2<N/2>(upper_half); | |
118 | } | |
119 | template<> | |
120 | constexpr inline unsigned int ilog2<8>(const typename boost::uint_t<8>::exact & t){ | |
92f5a8d4 TL |
121 | #define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n |
122 | const char LogTable256[256] = { | |
f67539c2 | 123 | static_cast<char>(-1), 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, |
92f5a8d4 TL |
124 | LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6), |
125 | LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7) | |
126 | }; | |
127 | return LogTable256[t]; | |
128 | } | |
92f5a8d4 TL |
129 | |
130 | } // ilog2_detail | |
131 | ||
132 | template<typename T> | |
1e59de90 | 133 | constexpr inline unsigned int ilog2(const T & t){ |
92f5a8d4 TL |
134 | // log not defined for negative numbers |
135 | // assert(t > 0); | |
136 | if(t == 0) | |
137 | return 0; | |
1e59de90 | 138 | return ilog2_detail::ilog2<bits_type<T>::value>( |
92f5a8d4 TL |
139 | static_cast< |
140 | typename boost::uint_t< | |
141 | bits_type<T>::value | |
142 | >::least | |
143 | >(t) | |
144 | ); | |
145 | } | |
146 | ||
147 | // the number of bits required to render the value in x | |
148 | // including sign bit | |
149 | template<typename T> | |
1e59de90 | 150 | constexpr inline unsigned int significant_bits(const T & t){ |
92f5a8d4 TL |
151 | return 1 + ((t < 0) ? ilog2(~t) : ilog2(t)); |
152 | } | |
153 | ||
154 | /* | |
155 | // give the value t, return the number which corresponds | |
156 | // to all 1's which is higher than that number | |
157 | template<typename T> | |
158 | constexpr unsigned int bits_value(const T & t){ | |
159 | const unsigned int sb = significant_bits(t); | |
160 | const unsigned int sb_max = significant_bits(std::numeric_limits<T>::max()); | |
161 | return sb < sb_max ? ((sb << 1) - 1) : std::numeric_limits<T>::max(); | |
162 | } | |
163 | */ | |
164 | ||
165 | /////////////////////////////////////////////////////////////////////////////// | |
166 | // meta functions returning types | |
167 | ||
168 | // If we use std::max in here we get internal compiler errors | |
169 | // with MSVC (tested VC2017) ... | |
170 | ||
171 | // Notes from https://en.cppreference.com/w/cpp/algorithm/max | |
172 | // Capturing the result of std::max by reference if one of the parameters | |
173 | // is rvalue produces a dangling reference if that parameter is returned. | |
174 | ||
175 | template <class T> | |
176 | // turns out this problem crashes all versions of gcc compilers. So | |
177 | // make sure we return by value | |
178 | //constexpr const T & max( | |
1e59de90 | 179 | constexpr inline T max( |
92f5a8d4 TL |
180 | const T & lhs, |
181 | const T & rhs | |
182 | ){ | |
183 | return lhs > rhs ? lhs : rhs; | |
184 | } | |
185 | ||
186 | // given a signed range, return type required to hold all the values | |
187 | // in the range | |
188 | template< | |
189 | std::intmax_t Min, | |
190 | std::intmax_t Max | |
191 | > | |
192 | using signed_stored_type = typename boost::int_t< | |
193 | max( | |
194 | significant_bits(Min), | |
195 | significant_bits(Max) | |
196 | ) + 1 | |
197 | >::least ; | |
198 | ||
199 | // given an unsigned range, return type required to hold all the values | |
200 | // in the range | |
201 | template< | |
202 | std::uintmax_t Min, | |
203 | std::uintmax_t Max | |
204 | > | |
205 | // unsigned range | |
206 | using unsigned_stored_type = typename boost::uint_t< | |
207 | significant_bits(Max) | |
208 | >::least; | |
209 | ||
210 | /////////////////////////////////////////////////////////////////////////////// | |
211 | // constexpr functions | |
212 | ||
213 | // need our own version because official version | |
214 | // a) is not constexpr | |
215 | // b) is not guarenteed to handle non-assignable types | |
216 | template<typename T> | |
1e59de90 | 217 | constexpr inline std::pair<T, T> |
20effc67 | 218 | minmax(const std::initializer_list<T> & l){ |
92f5a8d4 TL |
219 | assert(l.size() > 0); |
220 | const T * minimum = l.begin(); | |
221 | const T * maximum = l.begin(); | |
222 | for(const T * i = l.begin(); i != l.end(); ++i){ | |
223 | if(*i < * minimum) | |
224 | minimum = i; | |
225 | else | |
226 | if(* maximum < *i) | |
227 | maximum = i; | |
228 | } | |
229 | return std::pair<T, T>{* minimum, * maximum}; | |
230 | } | |
231 | ||
232 | // for any given t | |
233 | // a) figure number of significant bits | |
234 | // b) return a value with all significant bits set | |
235 | // so for example: | |
236 | // 3 == round_out(2) because | |
237 | // 2 == 10 and 3 == 11 | |
238 | template<typename T> | |
1e59de90 | 239 | constexpr inline T round_out(const T & t){ |
92f5a8d4 TL |
240 | if(t >= 0){ |
241 | const std::uint8_t sb = utility::significant_bits(t); | |
242 | return (sb < sizeof(T) * 8) | |
243 | ? ((T)1 << sb) - 1 | |
244 | : std::numeric_limits<T>::max(); | |
245 | } | |
246 | else{ | |
247 | const std::uint8_t sb = utility::significant_bits(~t); | |
248 | return (sb < sizeof(T) * 8) | |
249 | ? ~(((T)1 << sb) - 1) | |
250 | : std::numeric_limits<T>::min(); | |
251 | } | |
252 | } | |
253 | ||
254 | } // utility | |
255 | } // safe_numerics | |
256 | } // boost | |
257 | ||
258 | #endif // BOOST_NUMERIC_UTILITY_HPP |