fixed_point  rev.2
Binary Fixed-Point Arithmetic Library in C++
fixed_point_arithmetic.h
1 
2 // Copyright John McFarlane 2015 - 2016.
3 // Distributed under the Boost Software License, Version 1.0.
4 // (See accompanying file ../LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6 
9 
10 #if !defined(SG14_FIXED_POINT_ARITHMETIC_H)
11 #define SG14_FIXED_POINT_ARITHMETIC_H 1
12 
13 #include "common.h"
14 
15 #include "fixed_point_type.h"
16 
18 namespace sg14 {
19 
21  // implementation-specific definitions
22 
23  namespace _impl {
24  namespace fp {
25  namespace arithmetic {
26 
28  // tags
29 
30  // strategy
31  struct raw_tag;
32  struct lean_tag; // like-for-like interger arithmetic
33  struct wide_tag; // effort is made to widen to accommodate results of multiplication and division
34 
36  // file-local implementation-specific definitions
37 
38  using ::sg14::fixed_point;
39 
41  // sg14::_impl::fp::arithmetic::binary_pair
42 
43  template<class LhsRep, int LhsExponent, class RhsRep, int RhsExponent>
44  struct binary_pair_base {
45  using lhs_type = fixed_point<LhsRep, LhsExponent>;
46  using rhs_type = fixed_point<RhsRep, RhsExponent>;
47  };
48 
49  template<class Lhs, class Rhs>
50  struct binary_pair;
51 
52  template<class LhsRep, int LhsExponent, class RhsRep, int RhsExponent>
53  struct binary_pair<fixed_point<LhsRep, LhsExponent>, fixed_point<RhsRep, RhsExponent>>
54  : binary_pair_base<LhsRep, LhsExponent, RhsRep, RhsExponent> {
55  };
56 
57  template<class LhsRep, int LhsExponent, class Rhs>
58  struct binary_pair<fixed_point<LhsRep, LhsExponent>, Rhs>
59  : binary_pair_base<LhsRep, LhsExponent, Rhs, 0> {
60  static_assert(std::numeric_limits<Rhs>::is_integer,
61  "named arithmetic functions take only fixed_point and integral types");
62  };
63 
64  template<class Lhs, class RhsRep, int RhsExponent>
65  struct binary_pair<Lhs, fixed_point<RhsRep, RhsExponent>>
66  : binary_pair_base<Lhs, 0, RhsRep, RhsExponent> {
67  static_assert(std::numeric_limits<Lhs>::is_integer,
68  "named arithmetic functions take only fixed_point and integral types");
69  };
70 
72  // sg14::_impl::fp::arithmetic::rep_op_exponent
73 
74  template<class OperationTag, class ... Operands>
75  struct rep_op_exponent;
76 
77  template<class Rhs>
78  struct rep_op_exponent<_impl::plus_op, Rhs> : public std::integral_constant<int, Rhs::exponent> {
79  };
80 
81  template<class Rhs>
82  struct rep_op_exponent<_impl::minus_op, Rhs> : public std::integral_constant<int, Rhs::exponent> {
83  };
84 
85  template<class Lhs, class Rhs>
86  struct rep_op_exponent<_impl::add_op, Lhs, Rhs> : public std::integral_constant<int, _impl::min<int>(
87  Lhs::exponent,
88  Rhs::exponent)> {
89  };
90 
91  template<class Lhs, class Rhs>
92  struct rep_op_exponent<_impl::subtract_op, Lhs, Rhs>
93  : public std::integral_constant<int, _impl::min<int>(
94  Lhs::exponent,
95  Rhs::exponent)> {
96  };
97 
98  template<class Lhs, class Rhs>
99  struct rep_op_exponent<_impl::multiply_op, Lhs, Rhs> : public std::integral_constant<int,
100  Lhs::exponent+Rhs::exponent> {
101  };
102 
103  template<class Lhs, class Rhs>
104  struct rep_op_exponent<_impl::divide_op, Lhs, Rhs> : public std::integral_constant<int,
105  Lhs::exponent-Rhs::exponent> {
106  };
107 
109  // sg14::_impl::fp::arithmetic::result
110 
111  template<class PolicyTag, class OperationTag, class Lhs, class Rhs>
112  struct result;
113 
114  // result<raw_tag>
115  template<class OperationTag, class Lhs, class Rhs>
116  struct result<raw_tag, OperationTag, Lhs, Rhs> {
117  using lhs_rep = typename Lhs::rep;
118  using rhs_rep = typename Rhs::rep;
119  using rep_op_result = _impl::op_result<OperationTag, lhs_rep, rhs_rep>;
120 
121  static constexpr int exponent = rep_op_exponent<OperationTag, Lhs, Rhs>::value;
122 
123  using type = fixed_point<rep_op_result, exponent>;
124  };
125 
126  // result<lean_tag>
127  template<class OperationTag, class Lhs, class Rhs>
128  struct result<lean_tag, OperationTag, Lhs, Rhs> : result<raw_tag, OperationTag, Lhs, Rhs> {};
129 
130  // result<wide_tag>
131  template<class OperationTag, class Lhs, class Rhs>
132  struct result<wide_tag, OperationTag, Lhs, Rhs> {
133  using lhs_rep = typename Lhs::rep;
134  using rhs_rep = typename Rhs::rep;
135  using rep_op_result = _impl::op_result<OperationTag, lhs_rep, rhs_rep>;
136 
137  // 'Wide' doesn't guarantee avoiding overflow. Adding a single bit to add/subtract results would often lead to double the width being used.
138  static constexpr int sufficient_sign_bits = std::is_signed<rep_op_result>::value;
139  static constexpr int sufficient_integer_digits = _impl::max(Lhs::integer_digits,
140  Rhs::integer_digits);
141  static constexpr int sufficient_fractional_digits = _impl::max(Lhs::fractional_digits,
142  Rhs::fractional_digits);
143  static constexpr _digits_type sufficient_digits = sufficient_integer_digits+sufficient_fractional_digits;
144  static constexpr int result_digits = _impl::max(sufficient_digits, digits<rep_op_result>::value);
145 
146  using rep_type = set_digits_t<rep_op_result, result_digits>;
147  using type = fixed_point<rep_type, -sufficient_fractional_digits>;
148  };
149 
150  template<class Lhs, class Rhs>
151  struct result<wide_tag, _impl::multiply_op, Lhs, Rhs> {
152  using lhs_rep = typename Lhs::rep;
153  using rhs_rep = typename Rhs::rep;
154  using rep_op_result = _impl::op_result<_impl::multiply_op, lhs_rep, rhs_rep>;
155 
156  static constexpr int digits = Lhs::digits+Rhs::digits;
157  static constexpr bool is_signed =
158  std::numeric_limits<lhs_rep>::is_signed || std::numeric_limits<rhs_rep>::is_signed;
159 
160  using prewidened_result_rep = _impl::make_signed_t<rep_op_result, is_signed>;
161  using rep_type = set_digits_t<prewidened_result_rep, digits>;
162 
163  static constexpr int rep_exponent = rep_op_exponent<_impl::multiply_op, Lhs, Rhs>::value;
164 
165  using type = fixed_point<rep_type, rep_exponent>;
166  };
167 
168  template<class Lhs, class Rhs>
169  struct result<wide_tag, _impl::divide_op, Lhs, Rhs> {
170  using lhs_rep = typename Lhs::rep;
171  using rhs_rep = typename Rhs::rep;
172  using rep_op_result = _impl::op_result<_impl::multiply_op, lhs_rep, rhs_rep>;
173 
174  static constexpr int integer_digits = Lhs::integer_digits+Rhs::fractional_digits;
175  static constexpr int fractional_digits = Lhs::fractional_digits+Rhs::integer_digits;
176  static constexpr int necessary_digits = integer_digits+fractional_digits;
177  static constexpr bool is_signed =
178  std::numeric_limits<lhs_rep>::is_signed || std::numeric_limits<rhs_rep>::is_signed;
179 
180  static constexpr int promotion_digits = digits<rep_op_result>::value;
181  static constexpr int digits = _impl::max(necessary_digits, promotion_digits);
182 
183  using prewidened_result_rep = _impl::make_signed_t<rep_op_result, is_signed>;
184  using rep_type = set_digits_t<prewidened_result_rep, digits>;
185 
186  static constexpr int rep_exponent = -fractional_digits;
187 
188  using type = fixed_point<rep_type, rep_exponent>;
189  };
190 
192  // sg14::_impl::fp::arithmetic::intermediate
193 
194  template<class PolicyTag, class OperationTag, class Lhs, class Rhs>
195  struct intermediate;
196 
197  // bare add / subtract
198 
199  template<class OperationTag, class Lhs, class Rhs>
200  struct intermediate<lean_tag, OperationTag, Lhs, Rhs> {
201  using _result = result<lean_tag, OperationTag, Lhs, Rhs>;
202  using lhs_type = typename _result::type;
203  using rhs_type = lhs_type;
204  };
205 
206  template<class Lhs, class Rhs>
207  struct intermediate<lean_tag, _impl::multiply_op, Lhs, Rhs> {
208  using lhs_type = Lhs;
209  using rhs_type = Rhs;
210  };
211 
212  template<class Lhs, class Rhs>
213  struct intermediate<lean_tag, _impl::divide_op, Lhs, Rhs> {
214  using lhs_type = Lhs;
215  using rhs_type = Rhs;
216  };
217 
218  // intermediate - wide
219 
220  // wide - add/subtract
221  template<class OperationTag, class Lhs, class Rhs>
222  struct intermediate<wide_tag, OperationTag, Lhs, Rhs> {
223  using _result = result<wide_tag, OperationTag, Lhs, Rhs>;
224  using lhs_type = typename _result::type;
225  using rhs_type = lhs_type;
226  };
227 
228  template<class Lhs, class Rhs>
229  struct intermediate<wide_tag, _impl::multiply_op, Lhs, Rhs> {
230  using _result = result<wide_tag, _impl::multiply_op, Lhs, Rhs>;
231  using result_rep = typename _result::rep_type;
232  using prewidened_result_rep = typename _result::prewidened_result_rep;
233 
234  // If the 'natural' result of the rep op is wide enough, stick with it.
235  // This ensures that auto-widening rep types (e.g. elastic_integer) don't get widened twice
236  // but types that need a little help (e.g. built-ins) get widened going into the op.
237  using rep_type = typename std::conditional<
238  digits<prewidened_result_rep>::value>=_result::digits,
239  typename Lhs::rep, result_rep>::type;
240 
241  using lhs_type = fixed_point<rep_type, Lhs::exponent>;
242  using rhs_type = Rhs;
243  };
244 
245  template<class Lhs, class Rhs>
246  struct intermediate<wide_tag, _impl::divide_op, Lhs, Rhs> {
247  using wide_result = result<wide_tag, _impl::divide_op, Lhs, Rhs>;
248  using rep_type = typename wide_result::rep_type;
249 
250  static constexpr int exponent = Lhs::exponent-Rhs::digits;
251 
252  using lhs_type = fixed_point<rep_type, exponent>;
253  using rhs_type = Rhs;
254  };
255 
257  // sg14::_impl::fp::arithmetic::operate_params
258 
259  template<class PolicyTag, class OperationTag, class Lhs, class Rhs>
260  struct operate_params {
261  using _binary_pair = binary_pair<Lhs, Rhs>;
262  using lhs_type = typename _binary_pair::lhs_type;
263  using rhs_type = typename _binary_pair::rhs_type;
264 
265  using _intermediate = intermediate<PolicyTag, OperationTag, lhs_type, rhs_type>;
266  using intermediate_lhs = typename _intermediate::lhs_type;
267  using intermediate_rhs = typename _intermediate::rhs_type;
268 
269  using _result = result<PolicyTag, OperationTag, lhs_type, rhs_type>;
270  using result_type = typename _result::type;
271  };
272  }
273 
275  // mappings from named function strategies to public API
276 
277  // strategy aliases - for ease of flip-flopping
278  using arithmetic_operator_tag = arithmetic::lean_tag;
279  using division_arithmetic_operator_tag = arithmetic::wide_tag;
280  using named_function_tag = arithmetic::wide_tag;
281  using division_named_function_tag = arithmetic::lean_tag;
282 
284  // sg14::_impl::fixed_point::operate
285 
286  template<class PolicyTag, class Operation, class Lhs, class Rhs>
287  constexpr auto operate(const Lhs& lhs, const Rhs& rhs, Operation)
288  -> typename arithmetic::operate_params<PolicyTag, Operation, Lhs, Rhs>::result_type
289  {
290  using params = arithmetic::operate_params<PolicyTag, Operation, Lhs, Rhs>;
291  using intermediate_lhs = typename params::intermediate_lhs;
292  using intermediate_rhs = typename params::intermediate_rhs;
293  using result_type = typename params::result_type;
294  using result_rep = typename result_type::rep;
295 
296  return result_type::from_data(
297  static_cast<result_rep>(
298  Operation()(
299  static_cast<intermediate_lhs>(lhs).data(),
300  static_cast<intermediate_rhs>(rhs).data())));
301  };
302  }
303  }
304 }
305 
306 #endif // SG14_FIXED_POINT_ARITHMETIC_H
study group 14 of the C++ working group
Definition: const_integer.h:22