[ VIGRA Homepage | Class Index | Function Index | File Index | Main Page ]
![]() |
vigra/fixedpoint.hxx | ![]() |
---|
00001 /************************************************************************/ 00002 /* */ 00003 /* Copyright 2004-2005 by Ullrich Koethe */ 00004 /* Cognitive Systems Group, University of Hamburg, Germany */ 00005 /* */ 00006 /* This file is part of the VIGRA computer vision library. */ 00007 /* ( Version 1.3.3, Aug 18 2005 ) */ 00008 /* You may use, modify, and distribute this software according */ 00009 /* to the terms stated in the LICENSE file included in */ 00010 /* the VIGRA distribution. */ 00011 /* */ 00012 /* The VIGRA Website is */ 00013 /* http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/ */ 00014 /* Please direct questions, bug reports, and contributions to */ 00015 /* koethe@informatik.uni-hamburg.de */ 00016 /* */ 00017 /* THIS SOFTWARE IS PROVIDED AS IS AND WITHOUT ANY EXPRESS OR */ 00018 /* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ 00019 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. */ 00020 /* */ 00021 /************************************************************************/ 00022 00023 #ifndef VIGRA_FIXEDPOINT_HXX 00024 #define VIGRA_FIXEDPOINT_HXX 00025 00026 #include "vigra/mathutil.hxx" 00027 #include "vigra/static_assert.hxx" 00028 #include "vigra/error.hxx" 00029 #include "vigra/numerictraits.hxx" 00030 00031 namespace vigra { 00032 00033 template <unsigned IntBits, unsigned FractionalBits> 00034 class FixedPoint; 00035 00036 struct Error_FixedPointTraits_not_specialized_for_this_case; 00037 00038 template <class T1, class T2> 00039 class FixedPointTraits 00040 { 00041 public: 00042 typedef Error_FixedPointTraits_not_specialized_for_this_case PlusType; 00043 typedef Error_FixedPointTraits_not_specialized_for_this_case MinusType; 00044 typedef Error_FixedPointTraits_not_specialized_for_this_case MultipliesType; 00045 // typedef Error_FixedPointTraits_not_specialized_for_this_case DividesType; 00046 }; 00047 00048 // return type policy: 00049 // * try to allocate enough bits to represent the biggest possible result 00050 // * in case of ass/subtract: if all bits of the internal int are used up, 00051 // keep the representation 00052 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00053 class FixedPointTraits<FixedPoint<IntBits1, FracBits1>, FixedPoint<IntBits2, FracBits2> > 00054 { 00055 enum { MaxIntBits = (IntBits1 < IntBits2) ? IntBits2 : IntBits1, 00056 MaxFracBits = (FracBits1 < FracBits2) ? FracBits2 : FracBits1, 00057 PlusMinusIntBits = (MaxIntBits + 1 + MaxFracBits < 32) ? 00058 MaxIntBits + 1 : MaxIntBits}; 00059 public: 00060 typedef FixedPoint<PlusMinusIntBits, MaxFracBits> PlusType; 00061 typedef FixedPoint<PlusMinusIntBits, MaxFracBits> MinusType; 00062 typedef FixedPoint<IntBits1 + IntBits2, FracBits1 + FracBits2> MultipliesType; 00063 // typedef FixedPoint<IntBits1 + FracBits2, FracBits1 + IntBits2> DividesType; 00064 }; 00065 00066 template <int N> 00067 struct FixedPoint_overflow_error__More_than_31_bits_requested 00068 : staticAssert::AssertBool<(N < 32)> 00069 {}; 00070 00071 00072 template <bool Predicate> 00073 struct FixedPoint_assignment_error__Target_object_has_too_few_integer_bits 00074 : staticAssert::AssertBool<Predicate> 00075 {}; 00076 00077 enum FixedPointNoShift { FPNoShift }; 00078 00079 namespace detail { 00080 00081 template <bool MustRound> 00082 struct FPAssignWithRound; 00083 00084 template <> 00085 struct FPAssignWithRound<false> 00086 { 00087 template <int N> 00088 static inline int exec(int v) { return v << (-N); } 00089 }; 00090 00091 template <> 00092 struct FPAssignWithRound<true> 00093 { 00094 template <int N> 00095 static inline int exec(int const v) 00096 { 00097 return (v + (1 << (N - 1))) >> (N); 00098 } 00099 }; 00100 00101 template <bool MustRound> 00102 struct FPMulImplementation; 00103 00104 template <> 00105 struct FPMulImplementation<false> 00106 { 00107 template <int N> 00108 static inline int exec(int l, int r) { return (l * r) << (-N); } 00109 }; 00110 00111 template <> 00112 struct FPMulImplementation<true> 00113 { 00114 template <int N> 00115 static inline int exec(int l, int r) 00116 { 00117 // there is not enough space in the result 00118 // => perform calculations that preserve as much accuracy as possible 00119 enum { diffl = N / 2, diffr = N - diffl, maskl = (1 << diffl) - 1, maskr = (1 << diffr) - 1 }; 00120 int shiftl = l >> diffl; 00121 int shiftr = r >> diffr; 00122 00123 return shiftl * shiftr + (((l & maskl) * shiftr) >> diffl) + 00124 (((r & maskr) * shiftl) >> diffr); 00125 } 00126 }; 00127 00128 } // namespace detail 00129 00130 template <unsigned IntBits, unsigned FractionalBits> 00131 class FixedPoint 00132 { 00133 public: 00134 enum { 00135 INT_BITS = IntBits, 00136 FRACTIONAL_BITS = FractionalBits, 00137 TOTAL_BITS = IntBits + FractionalBits, 00138 MAX = (int)(((unsigned)1 << TOTAL_BITS) - 1), 00139 ONE = 1 << FractionalBits, 00140 ONE_HALF = ONE >> 1, 00141 FRACTIONAL_MASK = ONE - 1, 00142 INT_MASK = MAX ^ FRACTIONAL_MASK 00143 }; 00144 00145 int value; 00146 00147 FixedPoint() 00148 {} 00149 00150 /** 00151 */ 00152 explicit FixedPoint(int v) 00153 : value(v << FractionalBits) 00154 { 00155 VIGRA_STATIC_ASSERT((FixedPoint_overflow_error__More_than_31_bits_requested<(IntBits + FractionalBits)>)); 00156 } 00157 00158 /** 00159 */ 00160 FixedPoint(int v, FixedPointNoShift) 00161 : value(v) 00162 { 00163 VIGRA_STATIC_ASSERT((FixedPoint_overflow_error__More_than_31_bits_requested<(IntBits + FractionalBits)>)); 00164 } 00165 00166 explicit FixedPoint(double rhs) 00167 : value((int)round(rhs * ONE)) 00168 { 00169 vigra_precondition(abs(rhs * ONE) <= (double)MAX, 00170 "FixedPoint(double rhs): Too few integer bits to convert rhs."); 00171 } 00172 00173 00174 FixedPoint(const FixedPoint &other) 00175 : value(other.value) 00176 {} 00177 00178 template <unsigned Int2, unsigned Frac2> 00179 FixedPoint(const FixedPoint<Int2, Frac2> &other) 00180 : value(detail::FPAssignWithRound<(Frac2 > FractionalBits)>::template exec<Frac2 - FractionalBits>(other.value)) 00181 { 00182 VIGRA_STATIC_ASSERT((FixedPoint_assignment_error__Target_object_has_too_few_integer_bits<(IntBits >= Int2)>)); 00183 } 00184 00185 FixedPoint &operator=(int rhs) 00186 { 00187 vigra_precondition(abs(rhs) < (1 << IntBits), 00188 "FixedPoint::operator=(int rhs): Too few integer bits to represent rhs."); 00189 value = rhs << FractionalBits; 00190 return *this; 00191 } 00192 00193 FixedPoint &operator=(double rhs) 00194 { 00195 vigra_precondition(abs(rhs) <= ((1 << IntBits) - 1), 00196 "FixedPoint::operator=(double rhs): Too few integer bits to convert rhs."); 00197 value = (int)round(rhs * ONE); 00198 return *this; 00199 } 00200 00201 FixedPoint & operator=(const FixedPoint &other) 00202 { 00203 value = other.value; 00204 return *this; 00205 } 00206 00207 template <unsigned Int2, unsigned Frac2> 00208 FixedPoint & operator=(const FixedPoint<Int2, Frac2> &other) 00209 { 00210 VIGRA_STATIC_ASSERT((FixedPoint_assignment_error__Target_object_has_too_few_integer_bits<(IntBits >= Int2)>)); 00211 value = detail::FPAssignWithRound<(Frac2 > FractionalBits)>::template exec<Frac2 - FractionalBits>(other.value); 00212 return *this; 00213 } 00214 00215 operator double() const 00216 { 00217 return (double)value / ONE; 00218 } 00219 00220 FixedPoint operator-() const 00221 { 00222 return FixedPoint(-value, FPNoShift); 00223 } 00224 00225 FixedPoint & operator++() 00226 { 00227 value += ONE; 00228 return *this; 00229 } 00230 00231 FixedPoint operator++(int) 00232 { 00233 FixedPoint old(*this); 00234 value += ONE; 00235 return old; 00236 } 00237 00238 FixedPoint & operator--() 00239 { 00240 value -= ONE; 00241 return *this; 00242 } 00243 00244 FixedPoint operator--(int) 00245 { 00246 FixedPoint old(*this); 00247 value -= ONE; 00248 return old; 00249 } 00250 00251 template <unsigned Int2, unsigned Frac2> 00252 FixedPoint & operator+=(const FixedPoint<Int2, Frac2> &other) 00253 { 00254 VIGRA_STATIC_ASSERT((FixedPoint_assignment_error__Target_object_has_too_few_integer_bits<(IntBits >= Int2)>)); 00255 value += detail::FPAssignWithRound<(Frac2 > FractionalBits)>::template exec<Frac2 - FractionalBits>(other.value); 00256 return *this; 00257 } 00258 00259 template <unsigned Int2, unsigned Frac2> 00260 FixedPoint & operator-=(const FixedPoint<Int2, Frac2> &other) 00261 { 00262 VIGRA_STATIC_ASSERT((FixedPoint_assignment_error__Target_object_has_too_few_integer_bits<(IntBits >= Int2)>)); 00263 value -= detail::FPAssignWithRound<(Frac2 > FractionalBits)>::template exec<Frac2 - FractionalBits>(other.value); 00264 return *this; 00265 } 00266 00267 template <unsigned Int2, unsigned Frac2> 00268 FixedPoint & operator*=(const FixedPoint<Int2, Frac2> &other) 00269 { 00270 VIGRA_STATIC_ASSERT((FixedPoint_assignment_error__Target_object_has_too_few_integer_bits<(IntBits >= Int2)>)); 00271 value = detail::FPMulImplementation<(Frac2 > 0)>::template exec<Frac2>(value, other.value); 00272 return *this; 00273 } 00274 }; 00275 00276 #define VIGRA_FIXED_POINT_FACTORY(T, INTBITS) \ 00277 inline FixedPoint<INTBITS, 0> fixedPoint(T t) \ 00278 { \ 00279 return FixedPoint<INTBITS, 0>(t, FPNoShift); \ 00280 } 00281 00282 VIGRA_FIXED_POINT_FACTORY(unsigned char, 8) 00283 VIGRA_FIXED_POINT_FACTORY(signed char, 7) 00284 VIGRA_FIXED_POINT_FACTORY(unsigned short, 16) 00285 VIGRA_FIXED_POINT_FACTORY(signed short, 15) 00286 VIGRA_FIXED_POINT_FACTORY(int, 31) 00287 00288 #undef VIGRA_FIXED_POINT_FACTORY 00289 00290 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00291 inline 00292 bool operator==(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r) 00293 { 00294 enum { MaxFracBits = (FracBits1 < FracBits2) ? FracBits2 : FracBits1 }; 00295 return (l.value << (MaxFracBits - FracBits1)) == (r.value << (MaxFracBits - FracBits2)); 00296 } 00297 00298 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00299 inline 00300 bool operator!=(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r) 00301 { 00302 enum { MaxFracBits = (FracBits1 < FracBits2) ? FracBits2 : FracBits1 }; 00303 return (l.value << (MaxFracBits - FracBits1)) != (r.value << (MaxFracBits - FracBits2)); 00304 } 00305 00306 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00307 inline 00308 bool operator<(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r) 00309 { 00310 enum { MaxFracBits = (FracBits1 < FracBits2) ? FracBits2 : FracBits1 }; 00311 return (l.value << (MaxFracBits - FracBits1)) < (r.value << (MaxFracBits - FracBits2)); 00312 } 00313 00314 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00315 inline 00316 bool operator<=(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r) 00317 { 00318 enum { MaxFracBits = (FracBits1 < FracBits2) ? FracBits2 : FracBits1 }; 00319 return (l.value << (MaxFracBits - FracBits1)) <= (r.value << (MaxFracBits - FracBits2)); 00320 } 00321 00322 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00323 inline 00324 bool operator>(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r) 00325 { 00326 enum { MaxFracBits = (FracBits1 < FracBits2) ? FracBits2 : FracBits1 }; 00327 return (l.value << (MaxFracBits - FracBits1)) > (r.value << (MaxFracBits - FracBits2)); 00328 } 00329 00330 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00331 inline 00332 bool operator>=(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r) 00333 { 00334 enum { MaxFracBits = (FracBits1 < FracBits2) ? FracBits2 : FracBits1 }; 00335 return (l.value << (MaxFracBits - FracBits1)) >= (r.value << (MaxFracBits - FracBits2)); 00336 } 00337 00338 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00339 inline 00340 typename FixedPointTraits<FixedPoint<IntBits1, FracBits1>, FixedPoint<IntBits2, FracBits2> >::PlusType 00341 operator+(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r) 00342 { 00343 enum { MaxFracBits = (FracBits1 < FracBits2) ? FracBits2 : FracBits1 }; 00344 return typename 00345 FixedPointTraits<FixedPoint<IntBits1, FracBits1>, FixedPoint<IntBits2, FracBits2> >:: 00346 PlusType((l.value << (MaxFracBits - FracBits1)) + (r.value << (MaxFracBits - FracBits2)), FPNoShift); 00347 } 00348 00349 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2, 00350 unsigned IntBits3, unsigned FracBits3> 00351 inline void 00352 add(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r, 00353 FixedPoint<IntBits3, FracBits3> & result) 00354 { 00355 result = l + r; 00356 } 00357 00358 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00359 inline 00360 typename FixedPointTraits<FixedPoint<IntBits1, FracBits1>, FixedPoint<IntBits2, FracBits2> >::MinusType 00361 operator-(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r) 00362 { 00363 enum { MaxFracBits = (FracBits1 < FracBits2) ? FracBits2 : FracBits1 }; 00364 return typename 00365 FixedPointTraits<FixedPoint<IntBits1, FracBits1>, FixedPoint<IntBits2, FracBits2> >:: 00366 MinusType((l.value << (MaxFracBits - FracBits1)) - (r.value << (MaxFracBits - FracBits2)), FPNoShift); 00367 } 00368 00369 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2, 00370 unsigned IntBits3, unsigned FracBits3> 00371 inline void 00372 sub(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r, 00373 FixedPoint<IntBits3, FracBits3> & result) 00374 { 00375 result = l - r; 00376 } 00377 00378 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00379 inline 00380 typename FixedPointTraits<FixedPoint<IntBits1, FracBits1>, FixedPoint<IntBits2, FracBits2> >::MultipliesType 00381 operator*(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r) 00382 { 00383 return typename 00384 FixedPointTraits<FixedPoint<IntBits1, FracBits1>, FixedPoint<IntBits2, FracBits2> >:: 00385 MultipliesType(l.value * r.value, FPNoShift); 00386 } 00387 00388 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2, 00389 unsigned IntBits3, unsigned FracBits3> 00390 inline void 00391 mul(FixedPoint<IntBits1, FracBits1> l, FixedPoint<IntBits2, FracBits2> r, 00392 FixedPoint<IntBits3, FracBits3> & result) 00393 { 00394 VIGRA_STATIC_ASSERT((FixedPoint_assignment_error__Target_object_has_too_few_integer_bits<(IntBits1 + IntBits2 <= IntBits3)>)); 00395 enum { diff = FracBits1 + FracBits2 - FracBits3 }; 00396 result.value = detail::FPMulImplementation<(diff > 0)>::template exec<diff>(l.value, r.value); 00397 } 00398 00399 template <unsigned IntBits, unsigned FracBits> 00400 inline FixedPoint<IntBits, FracBits> 00401 abs(FixedPoint<IntBits, FracBits> v) 00402 { 00403 return FixedPoint<IntBits, FracBits>(abs(v.value), FPNoShift); 00404 } 00405 00406 template <unsigned IntBits, unsigned FracBits> 00407 inline FixedPoint<0, FracBits> 00408 frac(FixedPoint<IntBits, FracBits> v) 00409 { 00410 return FixedPoint<0, FracBits>(v.value & FixedPoint<IntBits, FracBits>::FRACTIONAL_MASK, FPNoShift); 00411 } 00412 00413 template <unsigned IntBits, unsigned FracBits> 00414 inline FixedPoint<0, FracBits> 00415 dual_frac(FixedPoint<IntBits, FracBits> v) 00416 { 00417 return FixedPoint<0, FracBits>(FixedPoint<0, FracBits>::ONE - 00418 (v.value & FixedPoint<IntBits, FracBits>::FRACTIONAL_MASK), FPNoShift); 00419 } 00420 00421 template <unsigned IntBits, unsigned FracBits> 00422 inline int 00423 floor(FixedPoint<IntBits, FracBits> v) 00424 { 00425 return(v.value >> FracBits); 00426 } 00427 00428 template <unsigned IntBits, unsigned FracBits> 00429 inline int 00430 ceil(FixedPoint<IntBits, FracBits> v) 00431 { 00432 return((v.value + FixedPoint<IntBits, FracBits>::FRACTIONAL_MASK) >> FracBits); 00433 } 00434 00435 template <unsigned IntBits, unsigned FracBits> 00436 inline int 00437 round(FixedPoint<IntBits, FracBits> v) 00438 { 00439 return((v.value + FixedPoint<IntBits, FracBits>::ONE_HALF) >> FracBits); 00440 } 00441 00442 template <unsigned IntBits, unsigned FracBits> 00443 struct NumericTraits<FixedPoint<IntBits, FracBits> > 00444 { 00445 typedef FixedPoint<IntBits, FracBits> Type; 00446 //typedef FixedPoint<IntBits, FracBits> Promote; 00447 //typedef FixedPoint<IntBits, FracBits> RealPromote; 00448 //typedef std::complex<RealPromote> ComplexPromote; 00449 typedef Type ValueType; 00450 00451 //typedef VigraFalseType isIntegral; 00452 typedef VigraTrueType isScalar; 00453 typedef VigraTrueType isOrdered; 00454 typedef VigraFalseType isComplex; 00455 00456 static Type zero() { return Type(0, FPNoShift); } 00457 static Type one() { return Type(Type::ONE, FPNoShift); } 00458 static Type nonZero() { return one(); } 00459 static Type epsilon() { return Type(1, FPNoShift); } 00460 static Type smallestPositive() { return Type(1, FPNoShift); } 00461 static Type max() { return Type( Type::MAX, FPNoShift); } 00462 static Type min() { return -max(); } 00463 }; 00464 00465 template <unsigned IntBits1, unsigned FracBits1, unsigned IntBits2, unsigned FracBits2> 00466 struct PromoteTraits<FixedPoint<IntBits1, FracBits1>, 00467 FixedPoint<IntBits2, FracBits2> > 00468 { 00469 typedef typename 00470 FixedPointTraits<FixedPoint<IntBits1, FracBits1>, FixedPoint<IntBits2, FracBits2> >::PlusType 00471 Promote; 00472 }; 00473 00474 } // namespace vigra 00475 00476 #endif // VIGRA_FIXEDPOINT_HXX
© Ullrich Köthe (koethe@informatik.uni-hamburg.de) |
html generated using doxygen and Python
|