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