Logo Search packages:      
Sourcecode: pcb2gcode version File versions  Download package

Fixed.hpp

/**
 * http://www.codef00.com/coding.php
 * Modified (pbirnzain)
 *
 * Copyright (c) 2008
 * Evan Teran
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted, provided
 * that the above copyright notice appears in all copies and that both the
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the same name not be used in advertising or
 * publicity pertaining to distribution of the software without specific,
 * written prior permission. We make no representations about the
 * suitability this software for any purpose. It is provided "as is"
 * without express or implied warranty.
 */

#ifndef FIXED_20060211_H_
#define FIXED_20060211_H_


#include <ostream>
#include <exception>
#include <cstddef>                        // for std::size_t
#include <climits>                        // for CHAR_BIT

#include <boost/static_assert.hpp>
#include <boost/operators.hpp>
#include <boost/cstdint.hpp>
#include <boost/utility/enable_if.hpp>

00033 namespace numeric {

template <std::size_t I, std::size_t F>
class Fixed;

namespace detail {
      template <class T>
00040       struct bit_size {
            static const std::size_t size = sizeof(T) * CHAR_BIT;
      };

      // helper templates to make magic with types :)
      // these allow us to determine resonable types from 
      // a desired size, they also let us infer the next largest type
      // from a type which is nice for the division op
      template <std::size_t T>
00049       struct type_from_size {
            static const bool is_specialized = false;
            typedef void                        value_type;
      };

      template <>
00055       struct type_from_size<64> {
            static const bool is_specialized = true;
            static const std::size_t      size = 64;
            typedef int64_t                     value_type;
            typedef type_from_size<128>   next_size;
      };

      template <>
00063       struct type_from_size<32> {
            static const bool is_specialized = true;
            static const std::size_t      size = 32;
            typedef int32_t                     value_type;
            typedef type_from_size<64>    next_size;
      };

      template <>
00071       struct type_from_size<16> {
            static const bool is_specialized = true;
            static const std::size_t      size = 16;
            typedef int16_t                     value_type;
            typedef type_from_size<32>    next_size;
      };

      template <>
00079       struct type_from_size<8> {
            static const bool is_specialized = true;
            static const std::size_t      size = 8;
            typedef int8_t                      value_type;
            typedef type_from_size<16>    next_size;
      };

      // this is to assist in adding support for non-native base 
      // types (for adding big-int support), this should be fine
      // unless your bit-int class doesn't nicely support casting
      template<class B, class N>
      B next_to_base(const N& rhs) {
            return static_cast<B>(rhs);
      }

00094       struct divide_by_zero : std::exception {
      };    
      
      template <std::size_t I, std::size_t F>
      void divide(const Fixed<I,F> &numerator, const Fixed<I,F> &denominator, Fixed<I,F> &quotient, Fixed<I,F> &remainder, typename boost::enable_if_c<detail::type_from_size<I+F>::next_size::is_specialized>::type* = 0) {
            
            BOOST_STATIC_ASSERT(detail::type_from_size<I + F>::next_size::is_specialized);
            
            typedef typename Fixed<I,F>::next_type next_type;
            typedef typename Fixed<I,F>::base_type base_type;
            static const std::size_t fractional_bits = Fixed<I,F>::fractional_bits;
            
            next_type t(numerator.to_raw());    
            t <<= fractional_bits;  
            
            quotient    = Fixed<I,F>::from_base(detail::next_to_base<base_type>(t / denominator.to_raw()));
            remainder   = Fixed<I,F>::from_base(detail::next_to_base<base_type>(t % denominator.to_raw()));
      }

      template <std::size_t I, std::size_t F>
      void divide(Fixed<I,F> numerator, Fixed<I,F> denominator, Fixed<I,F> &quotient, Fixed<I,F> &remainder, typename boost::disable_if_c<detail::type_from_size<I+F>::next_size::is_specialized>::type* = 0) {
            
            // NOTE: division is broken for large types :-(
            // especially when dealing with negative quantities

            typedef typename Fixed<I,F>::base_type base_type;
            static const int bits = Fixed<I,F>::total_bits;

            if(denominator == 0) {
                  throw divide_by_zero();
                  quotient    = 0;
                  remainder   = 0;
            } else {
                        
                  int sign = 0;
                  
                  if(numerator < 0) {
                        sign ^= 1;
                        numerator = -numerator;
                  }
                  
                  if(denominator < 0) {
                        sign ^= 1;
                        denominator = -denominator;
                  }
                  
                  base_type n             = numerator.to_raw();
                  base_type d             = denominator.to_raw();
                  base_type x             = 1;
                  base_type answer  = 0;

                  
                  while((n >= d) && (((d >> (bits - 1)) & 1) == 0)) {
                        x <<= 1;
                        d <<= 1;
                  }
                  
                  while(x != 0) {
                        if(n >= d) {
                              n -= d;
                              answer |= x;
                        }

                        x >>= 1;
                        d >>= 1;
                  }
                  
                  quotient    = answer;
                  remainder   = n;
                  
                  if(sign) {
                        quotient = -quotient;
                  }
            }
      }

      // this is the usual implementation of multiplication
      template <std::size_t I, std::size_t F>
      void multiply(const Fixed<I,F> &lhs, const Fixed<I,F> &rhs, Fixed<I,F> &result, typename boost::enable_if_c<detail::type_from_size<I+F>::next_size::is_specialized>::type* = 0) {
            
            BOOST_STATIC_ASSERT(detail::type_from_size<I + F>::next_size::is_specialized);
            
            typedef typename Fixed<I,F>::next_type next_type;
            typedef typename Fixed<I,F>::base_type base_type;
            
            static const std::size_t fractional_bits = Fixed<I,F>::fractional_bits;
      
            next_type t(static_cast<next_type>(lhs.to_raw()) * static_cast<next_type>(rhs.to_raw()));
            t >>= fractional_bits;
            result = Fixed<I,F>::from_base(next_to_base<base_type>(t));
      }
      
      // this is the fall back version we use when we don't have a next size
      // it is slightly slower, but is more robust since it doesn't
      // require and upgraded type
      template <std::size_t I, std::size_t F>
      void multiply(const Fixed<I,F> &lhs, const Fixed<I,F> &rhs, Fixed<I,F> &result, typename boost::disable_if_c<detail::type_from_size<I+F>::next_size::is_specialized>::type* = 0) {
      
            typedef typename Fixed<I,F>::base_type base_type;
            
            static const std::size_t fractional_bits  = Fixed<I,F>::fractional_bits;
            static const std::size_t integer_mask           = Fixed<I,F>::integer_mask;
            static const std::size_t fractional_mask  = Fixed<I,F>::fractional_mask;
      
            // more costly but doesn't need a larger type
            const base_type a_hi    = (lhs.to_raw() & integer_mask) >> fractional_bits;
            const base_type b_hi    = (rhs.to_raw() & integer_mask) >> fractional_bits;
            const base_type a_lo    = (lhs.to_raw() & fractional_mask);
            const base_type b_lo    = (rhs.to_raw() & fractional_mask);
            
            const base_type x1 = a_hi * b_hi;
            const base_type x2 = a_hi * b_lo;
            const base_type x3 = a_lo * b_hi;
            const base_type x4 = a_lo * b_lo;

            result = Fixed<I,F>::from_base((x1 << fractional_bits) + (x3 + x2) + (x4 >> fractional_bits));
      
      }
}


// lets us do things like "typedef numeric::fixed_from_type<int32_t>::fixed_type fixed";
// NOTE: that we will use a type of equivalent size, not neccessarily the type
// specified. Should make little to no difference to the user
template <class T>
00219 struct fixed_from_type {
      typedef Fixed<detail::bit_size<T>::size / 2, detail::bit_size<T>::size / 2> fixed_type;
};


/*
 * inheriting from boost::operators enables us to be a drop in replacement for base types
 * without having to specify all the different versions of operators manually
 */
template <std::size_t I, std::size_t F>
00229 class Fixed : boost::operators<Fixed<I,F> >, boost::shiftable<Fixed<I,F> > {
      BOOST_STATIC_ASSERT(detail::type_from_size<I + F>::is_specialized);

public:
      static const std::size_t fractional_bits  = F;
      static const std::size_t integer_bits           = I;
      static const std::size_t total_bits             = I + F;
      
      typedef detail::type_from_size<total_bits>                        base_type_info;
      
      typedef typename base_type_info::value_type                       base_type;
      typedef typename base_type_info::next_size::value_type      next_type;
      
private:
      static const std::size_t base_size        = base_type_info::size; 
      static const base_type fractional_mask    = ~((~base_type(0)) << fractional_bits);
      static const base_type integer_mask       = ~fractional_mask;
      
public:
      static const base_type one = base_type(1) << fractional_bits;

public:     // constructors
      Fixed() : data_(0) {
      }
      
      Fixed(long n) : data_(base_type(n) << fractional_bits) {
            // TODO: assert in range!
      }
      
      Fixed(unsigned long n) : data_(base_type(n) << fractional_bits) {
            // TODO: assert in range!
      }
      
      Fixed(int n) : data_(base_type(n) << fractional_bits) {
            // TODO: assert in range!
      }
      
      Fixed(unsigned int n) : data_(base_type(n) << fractional_bits) {
            // TODO: assert in range!
      }
      
      Fixed(float n) : data_(static_cast<base_type>(n * one)) {
            // TODO: assert in range!
      }
      
      Fixed(double n) : data_(static_cast<base_type>(n * one))  {
            // TODO: assert in range!
      }

      Fixed(const Fixed &o) : data_(o.data_) {
      }
            
      Fixed& operator=(const Fixed &o) {
            data_ = o.data_;        
            return *this;
      }

private:
      // this makes it simpler to create a fixed point object from
      // a native type without scaling
      // use "Fixed::from_base" in order to perform this.
00290       struct no_scale {};

      Fixed(base_type n, const no_scale &) : data_(n) {
      }
      
public:
      static Fixed from_base(base_type n) {
            return Fixed(n, no_scale());
      }

public:     // comparison operators
      bool operator==(const Fixed &o) const {
            return data_ == o.data_;
      }

      bool operator<(const Fixed &o) const {
            return data_ < o.data_;
      }

public:     // unary operators
      bool operator!() const {
            return !data_;
      }

      Fixed operator~() const {
            Fixed t(*this);
            t.data_ = ~t.data_;
            return t;
      }
      
      Fixed operator-() const {
            Fixed t(*this);
            t.data_ = -t.data_;
            return t;
      }
      
      Fixed& operator++() {
            data_ += one;
            return *this;
      }
      
      Fixed& operator--() {
            data_ -= one;
            return *this;
      }

public:     // basic math operators
      Fixed& operator+=(const Fixed &n) {
            data_ += n.data_;
            return *this;
      }
      
      Fixed& operator-=(const Fixed &n) {
            data_ -= n.data_;
            return *this;
      }
      
      Fixed& operator&=(const Fixed &n) {
            data_ &= n.data_;
            return *this;
      }
      
      Fixed& operator|=(const Fixed &n) {
            data_ |= n.data_;
            return *this;
      }
      
      Fixed& operator^=(const Fixed &n) {
            data_ ^= n.data_;
            return *this;
      }
      
      Fixed& operator*=(const Fixed &n) {
            detail::multiply(*this, n, *this);
            return *this;           
      }
      
      Fixed& operator/=(const Fixed &n) {
            Fixed temp;
            detail::divide(*this, n, *this, temp);
            return *this;
      }
      
      Fixed& operator>>=(const Fixed &n) {
            data_ >>= n.to_int();
            return *this;
      }
      
      Fixed& operator<<=(const Fixed &n) {
            data_ <<= n.to_int();
            return *this;
      }
      
public:     // conversion to basic types
      int to_int() const {
            return (data_ & integer_mask) >> fractional_bits; 
      }

      operator int() const {
            return this->to_int();
      }
      
      unsigned int to_uint() const {
            return (data_ & integer_mask) >> fractional_bits; 
      }
      
      float to_float() const {
            return static_cast<float>(data_) / Fixed::one;
      }
      
      double to_double() const            {
            return static_cast<double>(data_) / Fixed::one;
      }
      
      base_type to_raw() const {
            return data_;
      }
      
public:
      void swap(Fixed &rhs) {
            std::swap(data_, rhs.data_);
      }

public:
      base_type data_;
};

template <std::size_t I, std::size_t F>
std::ostream &operator<<(std::ostream &os, const Fixed<I,F> &f) {
      os << f.to_double();
      return os;
}
}
#endif

Generated by  Doxygen 1.6.0   Back to index