[ VIGRA Homepage | Class Index | Function Index | File Index | Main Page ]

details vigra/fixedpoint.hxx VIGRA

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)
Cognitive Systems Group, University of Hamburg, Germany

html generated using doxygen and Python
VIGRA 1.3.3 (18 Aug 2005)