FixedPoint.h

1 /* Copyright Jukka Jyl�nki
2
3    Licensed under the Apache License, Version 2.0 (the "License");
4    you may not use this file except in compliance with the License.
5    You may obtain a copy of the License at
6
7        http://www.apache.org/licenses/LICENSE-2.0
8
9    Unless required by applicable law or agreed to in writing, software
10    distributed under the License is distributed on an "AS IS" BASIS,
11    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12    See the License for the specific language governing permissions and
13    limitations under the License. */
14
15 /** @file FixedPoint.h
16         @author Jukka Jyl�nki
17         @brief FixedPoint is a templatized structure for representing fixed-point decimal numbers. */
18 #pragma once
19
20 #ifdef MATH_ENABLE_STL_SUPPORT
21 #include <iostream>
22 #endif
23
24 MATH_BEGIN_NAMESPACE
25
26 /** @brief Fixed-precision decimal number.
27
28         BaseT is the base type that is used to hold the value (it should be able to represent negative
29         numbers, so consider using a signed integer with either 8,16,32 or 64 bits. FracSize is the number
30         of bits to use for the fractional part of the value. */
31 template<typename BaseT, int FracSize>
32 class FixedPoint
33 {
34 public:
35         enum
36         {
37                 One = 1 << FracSize,
38                 IntBits = sizeof(BaseT)*8 - FracSize - 1, // -1 to take the sign into account.
39                 FracBits = FracSize,
40                 MaxVal = (1 << (IntBits))-1, // IntBits-1 to take the sign into account.
41                 MaxFrac = (1 << FracBits)-1,
42                 Epsilon = 1
43         };
44
45         /// Stores the fixed-point value.
46         BaseT value;
47
48         FixedPoint()
49         {
50         }
51
52         /** Converts an integer value to fixed-point value. */
53         FixedPoint(const BaseT &v)
54         :value(v << FracBits)
55         {
56         }
57
58         /** Converts a whole/fractional pair to fixed-point. */
59         FixedPoint(const BaseT &whole, const BaseT &frac)
60         :value((whole << FracBits) + frac)
61         {
62         }
63
64         /** Converts a whole, (nomin/denom) combination to fixed-point.
65                 For example, FixedPoint(2, 1, 3) would produce a fixed-point that corresponds to a rational 2 1/3, or 7/3. */
66         FixedPoint(const BaseT &whole, const BaseT &nomin, const BaseT &denom)
67         :value((whole << FracBits) + (nomin << FracBits) / denom)
68         {
69                 assert(denom != 0);
70         }
71
72         operator double() const
73         {
74                 return value/(double)One;
75         }
76
77         operator float() const
78         {
79                 return value/(float)One;
80         }
81
82         /// Returns the truncated integer part.
83         BaseT Int() const { return value >> FracBits; }
84
85         BaseT Frac() const { return value & MaxFrac; }
86 };
87
88 template<typename T, int F, int F2>
89 void Add(FixedPoint<T, F> &dst, const FixedPoint<T, F2> &src)
90 {
91         if (F > F2)
92                 dst.value += src.value << (F - F2);
93         else if (F < F2)
94                 dst.value += src.value >> (F2 - F);
95         else
96                 dst.value += src.value;
97 }
98
99 template<typename T, int F>
100 void Add(FixedPoint<T, F> &dst, const T &src)
101 {
102         dst.value += src << FixedPoint<T, F>::FracBits;
103 }
104
105 template<typename T, int F, int F2>
106 void Sub(FixedPoint<T, F> &dst, const FixedPoint<T, F2> &src)
107 {
108         if (F > F2)
109                 dst.value -= src.value << (F - F2);
110         else if (F < F2)
111                 dst.value -= src.value >> (F2 - F);
112         else
113                 dst.value -= src.value;
114 }
115
116 template<typename T, int F>
117 void Sub(FixedPoint<T, F> &dst, const T &src)
118 {
119         dst.value -= src.value << FixedPoint<T, F>::FracBits;
120 }
121
122 template<typename T, int F>
123 void Mul(FixedPoint<T, F> &dst, const T &src)
124 {
125         dst.value *= src;
126 }
127
128 /** The most straightforward (a*b)>>F, but the possible range for a & b is very limited, since
129         the intermediate result a*b is so large. */
130 template<typename T, int F, int F2>
131 void MulExtraFast(FixedPoint<T, F> &a, const FixedPoint<T, F2> &b)
132 {
133         a.value = (a.value * b.value) >> FixedPoint<T, F2>::FracBits;
134 }
135
136 /** Computes (a >> F/2)*(b >> F/2), which is a lot better than above, but suffers from a really
137         small precision error. */
138 template<typename T, int F, int F2>
139 void MulFast(FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
140 {
141 // Share the shifting between the two multiplicands: (Causes a slight precision error)
142         a.value = (a.value >> ((FixedPoint<T, F2>::FracBits+1)/2)) * (b.value >> (FixedPoint<T, F2>::FracBits/2));
143 }
144
145 /** Precisely multiplies two fixed-point numbers by breaking up the whole calculation into sums so that overflowing
146         in the intermediate range is not possible. */
147 template<typename T, int F>
148 void MulPrecise(FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
149 {
150         a.value = ((a.Int() * b.Int()) << FixedPoint<T, F>::FracBits) +
151                 (a.Int() * b.Frac() + a.Frac() * b.Int()) +
152                 ((a.Frac() * b.Frac()) >> (FixedPoint<T, F>::FracBits));
153 }
154 /*
155 template<int F>
156 void MulPrecise(FixedPoint<__int32, F> &a, const FixedPoint<__int32, F> &b)
157 {
158         const __int32 dst = a.value;
159         const __int32 src = b.value;
160         if (F >= 32) // the result is wholly in EDX.
161         {
162                 const int shift = F-32;
163                 __asm {
164                         mov eax, dst
165                         imul src
166                         mov ecx, shift
167                         sar edx, cl
168                         mov dst, edx
169                 };
170         }
171         else // the result overlaps EDX:EAX.
172         {
173                 const int shift1 = 32 - F;
174                 const int shift2 = F;
175                 __asm {
176                         // Multiply
177                         mov eax, dst
178                         imul src
179
180                         // Shift bits in edx to proper place
181                         mov ecx, shift1
182                         sal edx, cl
183
184                         // Shift bits in eax to proper place
185                         mov ecx, shift2
186                         shr eax, cl
187
188                         // Combine edx and eax and store the value.
189                         or edx, eax
190                         mov dst, edx
191                 };
192         }
193         a.value = dst;
194 }
195 */
196 template<typename T, int F>
197 void Div(FixedPoint<T, F> &a, const T &b)
198 {
199         a.value /= b;
200 }
201
202 template<typename T, int F, int F2>
203 void DivExtraFast(FixedPoint<T, F> &a, const FixedPoint<T, F2> &b)
204 {
205         a.value = (a.value << FixedPoint<T, F2>::FracBits) / b.value;
206 }
207
208 template<typename T, int F>
209 const FixedPoint<T, F> &operator+=(FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
210 {
211         Add(a, b);
212         return a;
213 }
214
215 template<typename T, int F>
216 const FixedPoint<T, F> &operator+=(FixedPoint<T, F> &a, const T &b)
217 {
218         Add(a, b);
219         return a;
220 }
221
222 template<typename T, int F>
223 const FixedPoint<T, F> operator+(const FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
224 {
225         FixedPoint<T, F> t(a);
226         t += b;
227         return t;
228 }
229
230 template<typename T, int F>
231 const FixedPoint<T, F> operator+(const FixedPoint<T, F> &a, const T &b)
232 {
233         FixedPoint<T, F> t(a);
234         t += b;
235         return t;
236 }
237
238 template<typename T, int F>
239 const FixedPoint<T, F> &operator-=(FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
240 {
241         Sub(a, b);
242         return a;
243 }
244
245 template<typename T, int F>
246 const FixedPoint<T, F> operator-(const FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
247 {
248         FixedPoint<T, F> t(a);
249         t -= b;
250         return t;
251 }
252
253 template<typename T, int F>
254 const FixedPoint<T, F> &operator*=(FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
255 {
256         MulPrecise(a, b);
257         return a;
258 }
259
260 template<typename T, int F>
261 const FixedPoint<T, F> operator*(const FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
262 {
263         FixedPoint<T, F> t(a);
264         t *= b;
265         return t;
266 }
267
268 template<typename T, int F>
269 bool operator<(const FixedPoint<T, F> &a, const T &b)
270 {
271         return a.Int() < b;
272 }
273
274 template<typename T, int F>
275 bool operator<(const FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
276 {
277         return a.value < b.value;
278 }
279
280 template<typename T, int F>
281 bool operator==(const FixedPoint<T, F> &a, const T &b)
282 {
283         return a.value == b << FixedPoint<T, F>::FracBits;
284 }
285
286 template<typename T, int F>
287 bool operator==(const FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
288 {
289         return a.value == b.value;
290 }
291
292 template<typename T, int F>
293 bool operator!=(const FixedPoint<T, F> &a, const FixedPoint<T, F> &b)
294 {
295         return !(a == b);
296 }
297
298 #ifdef MATH_ENABLE_STL_SUPPORT
299 template<typename T, int F>
300 std::ostream &operator<<(std::ostream &out, const FixedPoint<T, F> &f)
301 {
302 //      out << (double)f.value/(double)FixedPoint<T, F>::One;
303         if (f < 0 && f.Frac() != 0)
304                 out << f.Int()+1 << "." << (FixedPoint<T, F>::One-f.Frac()) * 10000 / FixedPoint<T, F>::One;
305         else
306                 out << f.Int() << "." << f.Frac() * 10000 / FixedPoint<T, F>::One;
307         return out;
308 }
309 #endif
310
311 MATH_END_NAMESPACE