/*
This program is distributed under the terms of the 'MIT license'. The text
of this licence follows...

Copyright (c) 2004-2005 J.D.Medhurst (a.k.a. Tixy)

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/

/**
@file

@brief 32-Bit fixed-point maths routines
*/

#ifndef FIX_H
#define FIX_H

/**
@defgroup fix Maths - 32bit Fixed-Point Maths

@brief Routines for performing 32bit fixed-point maths.

This code is targeted at CPUs without hardware support for division or floating point.
It has been optimised for ARM CPUs but should be suitable for other RISC architecures.

@version 2006-05-20
	- Changed code to use standard typedefs, e.g. replaced uint8 with uint8_t, and made use of size_t.

@version 2006-06-04
	- Added options to tune implementation of Fix::Mul(), Fix::MulNS() and Fix::Div().
	See #FIX_USE_64BIT_MUL and #FIX_UNROLL_DIV_LOOP.
@{
*/

/**
A type representing a 32bit fixed-point number.
The binary point lies between bits 15 and 16.

To convert between floating point and fixed point representations, numbers need
scaling by 2 to-the-power-of 16 (65536) e.g.
@code
	fix x;
	float f;
	// to convert f into x...
	x = (double)f*65536.0l;
	// to convert x into f...
	f = (double)x/65536.0l;
@endcode

Note, values are cast using <code>(double)</code> here to persuade the compiler to use
double precision floating point arithmetic. This avoids loosing precision as single
floats only have 24 significant bits, (less that the 32 bits in a <code>fix</code> number).

To convert between int and fixed point types, shift values by 16.

@code
	fix x;
	int i;
	// to convert i into x...
	x = i<<16;
	// to convert x into i (rounding towards minus infinity)...
	i = x>>16;
	// to convert x into i (rounding towards nearest integer)...
	i = ((x>>15)+1)>>1;
@endcode

Conversions described above may produce results which overflow the
range which can be represented by fixed point numbers. To detect
this, check the range of values before they are converted into fixed point...

@code
	fix x;
	float f;
	// convert f into x...
	float temp = (double)f*65536.0l;
	if((double)-2147483648.0<=temp && temp<=(double)2147483647.0)
		x = temp;
	else
		printf("Number conversion overflow!");
@endcode

or...

@code
	fix x;
	int i;
	// convert i into x...
	if(-0x8000<=i && i<=0x7fff)
		x = i<<16;
	else
		printf("Number conversion overflow!");
@endcode
*/
typedef int32_t fix;

/**
A type representing a 32bit unsigned fixed-point number.
The binary point lies between bits 15 and 16.

For convertsion into/from fixed point format, see #fix.
Note, valid input range fo unsigned values is 0..0xffff for integers, and
0..0xffffffff for the 'temp' value in the floating point conversion.
*/
typedef uint32_t ufix;

/**
A 32bit fixed-point value representing an angle.
Values are scaled by a factor of 1/(2*PI), i.e. a value of 1.0 (0x10000)
represents a full circle.

To convert angles between floating point and fixed point representations,
numbers need scaling as for #fix, but with the scaling factor reduced
by 2*PI. E.g.
@code
#define PI 3.1415926535897932384626433832795l
	fixangle a;
	double f;
	// to convert f into a...
	a = (double)f*65536.0l/(2.0l*PI);
	// to convert a into f...
	f = (double)a/65536.0l*(2.0l*PI);
@endcode

This treats <code>f</code> as an angle in radians, (the usual units for angles
in mathematics and computer functions). If you want to use values in degrees,
replace <code>2.0l*PI</code> with <code>360.0l</code>.
*/
typedef fix fixangle;


/**
@brief Fixed point arithmetic functions.

Operands are 32 bits in size with the binary point between bits 15 and 16.
@see fix
	 ufix
	 fixangle

@version 2005-02-26
	- Added Random(uint32_t& seed)
	- Added Random(uint32_t& seed,ufix range)
*/
class Fix
	{
public:
	/**
	Add two fixed-point numbers.
	Produces saturated result on overflow.

	When the addition of two numbers is know not to cause
	overflow, or when this doesn't matter, normal integer addition (+)
	can be used instead...
	@code
	fix a;
	fix b;
	fix sum = a+b;
	@endcode

	@param a Augend
	@param b Addend

	@return  a+b. <BR>
			 If a+b>0x7FFF.FFFF then 0x7FFF.FFFF is returned. <BR>
			 If a+b<-0x8000.0000 then -0x8000.0000 is returned.
	*/
	static fix Add(fix a,fix b);

	/**
	Subtract two fixed-point numbers.
	Produces saturated result on overflow.

	When the subtraction of two numbers is know not to cause
	overflow, or when this doesn't matter, normal integer subtraction (-)
	can be used instead...
	@code
	fix a;
	fix b;
	fix difference = a-b;
	@endcode

	@param a Minuend
	@param b Subtrahend

	@return  a-b. <BR>
			 If a-b>0x7FFF.FFFF then 0x7FFF.FFFF is returned. <BR>
			 If a-b<-0x8000.0000 then -0x8000.0000 is returned.
	*/
	static fix Sub(fix a,fix b);

	/**
	Multiply two fixed-point numbers.
	Produces saturated result on overflow.

	To multiply a fixed point number by an integer, normal integer multiplication (*)
	may be used...
	@code
	fix a;
	fix twoTimes = a*2;
	@endcode
	This does not detect overflow.

	@param a Multiplicand
	@param b Multiplier

	@return  a*b. <BR>
			 If a*b>0x7FFF.FFFF then 0x7FFF.FFFF is returned. <BR>
			 If a*b<-0x8000.0000 then -0x8000.0000 is returned.

	@see MulNS()
	*/
	static fix Mul(fix a,fix b);

	/**
	Multiply two fixed-point numbers.
	This is a Non-Saturating (and faster) version of Mul().
	On overflow the result is undefined.

	To multiply a fixed point number by an integer, normal integer multiplication (*)
	may be used...
	@code
	fix a;
	fix twoTimes = a*2;
	@endcode

	@param a Multiplicand
	@param b Multiplier

	@return	 a*b. <BR>
			 If a*b>0x7FFF.FFFF or a*b<-0x8000.0000 then the returned result is undefined.
	*/
	static fix MulNS(fix a,fix b);

	/**
	Divide two fixed-point numbers.
	Produces saturated result on overflow.
	Division by zero is treated as division by a very small number and
	produces a saturated result accordingly.

	To divide a fixed point number by an integer, normal integer division (/)
	may be used...
	@code
	fix a;
	fix half = a/2;
	@endcode
	This does not error conditions.

	@param a Dividend
	@param b Divisor

	@return  a/b. <BR>
			 If a/b>0x7FFF.FFFF then 0x7FFF.FFFF is returned. <BR>
			 If a/b<-0x8000.0000 then -0x8000.0000 is returned. <BR>
			 If b==0 and a>=0 then 0x7FFF.FFFF  is returned. <BR>
			 If b==0 and a<0 then -0x8000.0000 is returned. <BR>
	*/
	static fix Div(fix a,fix b);

	/**
	Calculate the square root of a fixed-point number.

	@param a Unsigned fixed point number.

	@return  a^0.5.
	*/
	static fix Sqrt(ufix a);

	/**
	Calculate the logarithm to base 2 of a fixed-point number .
	Accuracy is +/-8.40e-6 (+/-0.55 lsb).

	@param a Unsigned fixed point number.

	@return  log2(a). <BR>
			 If a==0 then -0x8000.0000 is returned
	*/
	static fix Log2(ufix a);

	/**
	Raise 2 to-the-power of a fixed-point number, (2^a).
	Accuracy is +/-1.14e-5 (+/-0.75 lsb).

	@param a Fixed point number.

	@return  2^a. <BR>
			 If 2^a>0xFFFF.FFFF then 0xFFFF.FFFF is returned.
	*/
	static ufix Exp2(fix a);

	/**
	Calculate the Sine of an angle.
	Accuracy is +/-8.55e-6 (+/-0.56 lsb).

	@param angle The angle.

	@return 	 The Sine of \a angle.
	*/
	static fix Sin(fixangle angle);

	/**
	Calculate the Cosine of an angle.
	Accuracy is +/-8.55e-6 (+/-0.56 lsb).

	@param angle The angle.

	@return 	 The Cosine of \a angle.
	*/
	static fix Cos(fixangle angle);

	/**
	Calculate the Tangent of an angle.
	Accuracy is +/-1.01e-5 (+/-0.66 lsb).

	@param angle The angle.

	@return 	 The Tangent of \a angle. <BR>
				 If Tan(\a angle)>0x7FFF.FFFF then 0x7FFF.FFFF is returned. <BR>
				 If Tan(\a angle)<-0x8000.0000 then -0x8000.0000 is returned.
	*/
	static fix Tan(fixangle angle);

	/**
	Calculate the Arc-Sine of a value.
	Accuracy is +/-8.55e-6 (+/-0.56 lsb).

	@param value The value. Should be in the range -1.0 to 1.0 (-0x10000 to 0x10000).

	@return 	 The Arc-Sine of \a value. <BR>
				 If \a value<-1.0 then -0.25 (-0x4000) is returned. <BR>
				 If \a value>1.0 then 0.25 (0x4000) is returned.
	*/
	static fixangle ASin(fix value);

	/**
	Calculate the Arc-Cosine of a value.
	Accuracy is +/-8.55e-6 (+/-0.56 lsb).

	@param value The value. Should be in the range -1.0 to 1.0 (-0x10000 to 0x10000).

	@return 	 The Arc-Cosine of \a value. <BR>
				 If \a value<-1.0 then 0.5 (0x8000) is returned. <BR>
				 If \a value>1.0 then 0.0 (0x0000) is returned.
	*/
	static fixangle ACos(fix value);

	/**
	Calculate the Arc-Tangent of a value.
	Accuracy is +/-9.00e-6 (+/-0.59 lsb).

	@param value The value.

	@return 	 The Arc-Tangent of \a value.
	*/
	static fixangle ATan(fix value);

	/**
	Generate a psuedo-random number.

	@param seed  A reference to the seed value. This will be updated after each call
				 to this function.

	@return		 A pseudo-random number

	@since 2005-02-26
	*/
	static fix Random(uint32_t& seed);

	/**
	Generate a psuedo-random number.

	@param seed  A reference to the seed value. This will be updated after each call
				 to this function.
	@param range The range for the generated numbers.

	@return		 A pseudo-random number less than the value of \a range

	@since 2005-02-26
	*/
	static ufix Random(uint32_t& seed,ufix range);
	};


/** @} */ // End of group

#endif