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>

namespace numeric {

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

namespace detail {
	template <class T>
	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>
	struct type_from_size {
		static const bool is_specialized = false;
		typedef void				value_type;
	};

	template <>
	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 <>
	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 <>
	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 <>
	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);
	}

	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>
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>
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.
	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