/*
 * 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 <limits>				// for std::numeric_limits
#include <exception>
#include <stdexcept>
#include <cstddef>				// for std::size_t
#include <climits>				// for CHAR_BIT

#include <boost/config.hpp>
#include <boost/static_assert.hpp>
#include <boost/operators.hpp>
#include <boost/cstdint.hpp>	// for integer types

//#define INTERNAL_DIV
//#define INTERNAL_MUL

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

// lets us do things like Fixed<bit_size<int16_t>::size, bit_size<int16_t>::size>
template<typename T> struct bit_size {
	static const std::size_t size = sizeof(T) * CHAR_BIT;
};

// lets us do things like typedef fixed_from_type<int32_t>::fixed_type fixed;
template<typename T> struct fixed_from_type {
	typedef Fixed<bit_size<T>::size / 2, bit_size<T>::size / 2> fixed_type;
};

// 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;
};

/* no next size!, therfore we can't have a 32.32 fixed point value yet
 * or at the very least we will need to have a specialization of Fixed<64> to
 * do things diferently and not rely on a larger 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;
	typedef type_from_size<32>	prev_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;
	typedef type_from_size<16>	prev_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;
	typedef type_from_size<8>	prev_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;
	typedef type_from_size<8>	prev_size; /* we would prefer a 4-bit type here, but 8 will do */
};

// this is to assist in adding support for non-native base types (for adding big-int support)
template<typename B, typename N> struct next_to_base {
	static B convert(const N& rhs) { return static_cast<B>(rhs); }
};

#ifdef INTERNAL_DIV
//------------------------------------------------------------------------------
// Name: __do_div(const T &numerator, const T &denominator, T &quotient, T &remainder)
//------------------------------------------------------------------------------
template <typename T>
void __do_div(const T &numerator, const T &denominator, T &quotient, T &remainder) {

	static const int bits = sizeof(T) * CHAR_BIT;

	if(denominator == 0) {
		throw std::runtime_error("divide by zero");
		quotient = 0;
		remainder = 0;
	} else {
		T n			= numerator;
		T d			= denominator;
		T x			= 1;
		T 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;
	}
}
#endif

/*
 * 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(type_from_size<I + F>::is_specialized);
	BOOST_STATIC_ASSERT(type_from_size<I + F>::next_size::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 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;
	typedef typename base_type_info::prev_size::value_type	prev_type;
	
	static const std::size_t base_size = base_type_info::size;
	static const std::size_t next_size = base_type_info::next_size::size;
	static const std::size_t prev_size = base_type_info::prev_size::size;
	
	static const base_type fractional_mask	= ~(base_type(-1) << fractional_bits);
	static const base_type integer_mask		= ~fractional_mask;
	
public:
	static const base_type one = base_type(1) << fractional_bits;

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

	Fixed(const Fixed &o) : m_Data(o.m_Data) {
	}
	
	Fixed(base_type &rhs) : m_Data(rhs) {
	}
	
	Fixed& operator=(const Fixed &o) {
		m_Data = o.m_Data;		
		return *this;
	}
	
public:	// comparison operators
	bool operator==(const Fixed &o) const {
		return m_Data == o.m_Data;
	}

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

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

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

public:	// basic math operators
	Fixed& operator+=(const Fixed &n) {
		m_Data += n.m_Data;
		return *this;
	}
	
	Fixed& operator-=(const Fixed &n) {
		m_Data -= n.m_Data;
		return *this;
	}
	
	Fixed& operator&=(const Fixed &n) {
		m_Data &= n.m_Data;
		return *this;
	}
	
	Fixed& operator|=(const Fixed &n) {
		m_Data |= n.m_Data;
		return *this;
	}
	
	Fixed& operator^=(const Fixed &n) {
		m_Data ^= n.m_Data;
		return *this;
	}
	
	Fixed& operator*=(const Fixed &n) {
#ifdef INTERNAL_MUL
		static const int shift				= total_bits / 2;
		static const base_type upper_mask	= (base_type(-1) << shift);
		static const base_type lower_mask	= ~upper_mask;
		
		const base_type a_hi	= (  m_Data & upper_mask) >> shift;
		const base_type b_hi	= (n.m_Data & upper_mask) >> shift;
		const base_type a_lo	= (  m_Data & lower_mask);
		const base_type b_lo	= (n.m_Data & lower_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;

		m_Data = (x1 << shift) + (x3 + x2) + (x4 >> shift);
#else
		next_type t(static_cast<next_type>(m_Data) * static_cast<next_type>(n.m_Data));
		t >>= fractional_bits;
		m_Data = next_to_base<base_type, next_type>::convert(t);
#endif
		return *this;		
	}
	
	Fixed& operator/=(const Fixed &n) {
#ifdef INTERNAL_DIV
		Fixed temp;
		__do_div(*this, n, *this, temp);
#else
		next_type t(m_Data);	
		t <<= fractional_bits;	
		t /= n.m_Data;	
		m_Data = next_to_base<base_type, next_type>::convert(t);
#endif
		return *this;
	}
	
	Fixed& operator>>=(const Fixed &n) {
		m_Data >>= n.to_integer();
		return *this;
	}
	
	Fixed& operator<<=(const Fixed &n) {
		m_Data <<= n.to_integer();
		return *this;
	}
	
public:	// conversion to basic types
	int to_integer() const		{
		return (m_Data & integer_mask) >> fractional_bits; 
	}
	
	float to_float() const		{
		return static_cast<float>(m_Data) / Fixed::one;
	}
	
	double to_double() const		{
		return static_cast<double>(m_Data) / Fixed::one;
	}
	
	base_type to_raw() const {
		return m_Data;
	}

public:
	base_type m_Data;
};

#endif