?/*---------------------------------------------------------------

THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF
ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED
TO THE IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
PARTICULAR PURPOSE.

Copyright (C) 2003.  Microsoft Corporation.  All rights reserved.

SafeInt.hpp

This header implements an integer handling class designed to catch
unsafe integer operations

This header compiles properly at warning level 4.

Please read the leading comments before using the class.

Version 1.0.3
---------------------------------------------------------------*/
#ifndef SAFEINT_HPP
#define SAFEINT_HPP

#include <assert.h>

/*
*  The SafeInt class is designed to have as low an overhead as possible
*  while still ensuring that all integer operations are conducted safely.
*  Nearly every operator has been overloaded, with a very few exceptions.
*
*  A usability-safety trade-off has been made to help ensure safety. This 
*  requires that every operation return either a SafeInt or a bool. If we 
*  allowed an operator to return a base integer type T, then the following 
*  can happen:
*  
*  char i = SafeInt<char>(32) * 2 + SafeInt<char>(16) * 4;
*
*  The * operators take precedence, get overloaded, return a char, and then 
*  you have:
*
*  char i = (char)64 + (char)64; //overflow!
*  
*  This situation would mean that safety would depend on usage, which isn't
*  acceptable. The problem that this leaves us with is that you'd like to be able 
*  to do something like:
*
*  void* ptr = malloc(SafeInt<unsigned short>(23) * SafeInt<unsigned short>(HowMany));
*
*  and have it be a safe operation. The way out of this is to use the following type of
*  construct:
*
*   SafeInt<int> s = 1, s1 = 2;
*  	int	m = (s | s1).Value();
*
*  A little clunky, and less programmer-friendly than would be ideal, but it is safe.
*
*  One key operator that is missing is an implicit cast. The reason for
*  this is that if there is an implicit cast operator, then we end up with
*  an ambiguous compile-time precedence. Because of this amiguity, there
*  are two methods that are provided:
*
*  SafeInt::Value() - returns the value of the object as an integer
*  SafeInt::Ptr()   - returns the address of the internal integer
*  Note - the '&' (address of) operator has been overloaded and returns
*         the address of the internal integer.
*
*  The SafeInt class should be used in any circumstances where ensuring
*  integrity of the calculations is more important than performance. See Performance
*  Notes below for additional information. 
*
*  Many of the conditionals will optimize out or be inlined for a release
*  build (especially with /Ox), but it does have significantly more overhead, 
*  especially for signed numbers. If you do not _require_ negative numbers, use 
*  unsigned integer types - certain types of problems cannot occur, and this class
*  performs most efficiently.
*
*  Here's an example of when the class should ideally be used -
*
*  void* AllocateMemForStructs(int StructSize, int HowMany)
*  {
*     SafeInt<unsigned long> s(StructSize);
*
*     s *= HowMany;
*
*     return malloc(s.Value());
*
*  }
*
*  Here's when it should NOT be used:
*
*  void foo()
*  {
*    int i;
*
*    for(i = 0; i < 0xffff; i++)
*      ....
*  }
*
*  Error handling - a SafeInt class will throw exceptions if something
*  objectionable happens. The exceptions are SafeIntException classes,
*  which contain one signed long as a code (for compatability with Windows
*  errors). The values that may be assigned currently are:
*
*  ERROR_ARITHMETIC_OVERFLOW
*  EXCEPTION_INT_DIVIDE_BY_ZERO
*
*  Typical usage might be:
*
*  bool foo()
*  {
*    SafeInt<unsigned long> s; //note that s == 0 unless set
*
*    try{
*      s *= 23;
*      ....
*    }
*    catch(SafeIntException err)
*    {
*       //handle errors here
*    }
*  }
*
*  Performance:
*
*  Due to the highly nested nature of this class, you can expect relatively poor
*  performance in unoptimized code. In tests of optimized code vs. correct inline checks
*  in native code, this class has been found to take approximately 8% more CPU time,
*  most of which is due to exception handling. Solutions:
*
*  1) Compile optimized code - /Ox is best, /O2 also performs well. Interestingly, /O1
*     (optimize for size) does not work as well. 
*  2) If that 8% hit is really a serious problem, walk through the code and inline the
*     exact same checks as the class uses.
*  3) Some operations are more difficult than others - avoid using signed integers, and if
*     possible keep them all the same size. 64-bit integers are also expensive. Mixing 
*     different integer sizes and types may prove expensive. Be aware that literals are
*     actually ints. For best performance, cast them to the type desired.
*
*
*  Binary Operators
*  
*  All of the binary operators have certain assumptions built into the class design. 
*  This is to ensure correctness. Notes on each class of operator follow:
*  
*  Arithmetic Operators (*,/,+,-,%)
*  There are three possible variants:
*  SafeInt<T> op SafeInt<T>
*  SafeInt<T> op U
*  U op SafeInt<T>
*  
*  The SafeInt<T> op SafeInt<U> variant is explicitly not supported, and if you try to do 
*  this the compiler with throw the following error:
*  
*  error C2593: 'operator *' is ambiguous
*  
*  This is because the arithmetic operators are required to return a SafeInt of some type. 
*  The compiler cannot know whether you'd prefer to get a type T or a type U returned. If 
*  you need to do this, you need to extract the value contained within one of the two using 
*  the SafeInt::Value() method. For example:
*  
*  SafeInt<T> t, result;
*  SafeInt<U> u;
*  
*  result = t * u.Value();
*  
*  Comparison Operators
*  Because each of these operators return type bool, mixing SafeInts of differing types is 
*  allowed.
*  
*  Shift Operators
*  Shift operators always return the type on the left hand side of the operator. Mixed type 
*  operations are allowed because the return type is always known.
*  
*  Boolean Operators
*  Like comparison operators, these overloads always return type bool, and mixed-type SafeInts 
*  are allowed. Additionally, specific overloads exist for type bool on both sides of the 
*  operator.
*  
*  Binary Operators
*  Mixed-type operations are discouraged, however some provision has been made in order to 
*  enable things like:
*  
*  SafeInt<char> c = 2;
*  
*  if(c & 0x02)
*    ...
*  
*  The "0x02" is actually an int, and it needs to work. The rule is that if the non-SafeInt type 
*  can be cast to the type of the SafeInt, and back to the original type without losing any 
*  significant bits then the operation is allowed.
*  
*  
*  Documented issues:
*
*  This header compiles correctly at /W4 using VC++ 7.1 (Version 13.10.3077). 
*  It is strongly recommended that any code doing integer manipulation be compiled at /W4 
*  - there are a number of warnings which pertain to integer manipulation enabled that are 
*  not enabled at /W3 (default for VC++)
*
*  Perf note - postfix operators are slightly more costly than prefix operators.
*  Unless you're actually assigning it to something, ++SafeInt is less expensive than SafeInt++
*
*  The comparison operator behavior in this class varies from the ANSI definition, which is 
*  arguably broken. As an example, consider the following:
*  
*  unsigned int l = 0xffffffff;
*  char c = -1;
*  
*  if(c == l)
*    printf("Why is -1 equal to 4 billion???\n");
*  
*  The problem here is that c gets cast to an int, now has a value of 0xffffffff, and then gets 
*  cast again to an unsigned int, losing the true value. This behavior is despite the fact that
*  an _int64 exists, and the following code will yield a different (and intuitively correct)
*  answer:
*  
*  if((_int64)c == (_int64)l))
*    printf("Why is -1 equal to 4 billion???\n");
*  else
*    printf("Why doesn't the compiler upcast to 64-bits when needed?\n");
*  
*  Note that combinations with smaller integers won't display the problem - if you 
*  changed "unsigned int" above to "unsigned short", you'd get the right answer.
*
*  If you prefer to retain the ANSI standard behavior insert 
*  #define ANSI_CONVERSIONS 
*  into your source. Behavior differences occur in the following cases:
*  8, 16, and 32-bit signed int, unsigned 32-bit int
*  any signed int, unsigned 64-bit int
*  Note - the signed int must be negative to show the problem
*  
*  
*  Revision history:
*
*  Oct 12, 2003 - Created
*  Author - David LeBlanc - dleblanc@microsoft.com
*
*  Oct 27, 2003 - fixed numerous items pointed out by michmarc and bdawson
*  Dec 28, 2003 - 1.0
*                 added support for mixed-type operations
*                 thanks to vikramh
*                 also fixed broken _int64 multiplication section
*                 added extended support for mixed-type operations where possible
*  Jan 28, 2004 - 1.0.1
*                 changed WCHAR to wchar_t
*                 fixed a construct in two mixed-type assignment overloads that was 
*                 not compiling on some compilers
*                 Also changed name of private method to comply with standards on 
*                 reserved names
*                 Thanks to Niels Dekker for the input
*  Feb 12, 2004 - 1.0.2
*                 Minor changes to remove dependency on Windows headers
*                 Consistently used _int16, _int32 and _int64 to ensure
*                 portability
*  May 10, 2003 - 1.0.3
*                 Corrected bug in one case of GreaterThan
*                 
*/

#pragma warning(push)
//this avoids warnings from the unary '-' operator being applied to unsigned numbers
//the overload itself resolves to nothing for the unsigned case
#pragma warning(disable:4146)
// conditional expression is constant - these are used intentionally
#pragma warning(disable:4127)

//use these if the compiler does not support _intXX
#ifdef NEEDS_INT_DEFINED
#define _int16 short
#define _int32 long
#define _int64 long long
#endif

/* catch these to handle errors
** Currently implemented code values:
** ERROR_ARITHMETIC_OVERFLOW
** EXCEPTION_INT_DIVIDE_BY_ZERO
*/

#ifndef ERROR_ARITHMETIC_OVERFLOW
#define ERROR_ARITHMETIC_OVERFLOW 534L
#endif

#ifndef EXCEPTION_INT_DIVIDE_BY_ZERO
#define EXCEPTION_INT_DIVIDE_BY_ZERO ((unsigned _int32)0xC0000094L)
#endif

class SafeIntException
{
public:
	SafeIntException(){m_code = 0;}
	SafeIntException(_int32 code)
	{
		m_code = code;
	}
	_int32 m_code;
};

template<typename T> class SafeInt
{
public:
	SafeInt()
	{
		m_int = 0;
	}

	//Having a constructor for every type of int 
	//avoids having the compiler evade our checks when doing implicit casts - 
	//e.g., SafeInt<char> s = 0x7fffffff;
	SafeInt(T i)
	{
		//always safe
		m_int = i;
	}

	//provide explicit boolean converter
	SafeInt(bool b)
	{
		m_int = b ? 1 : 0;
	}

	template <typename U> SafeInt(SafeInt<U> u)
	{
		*this = SafeInt<T>(u.Value());
	}

	template <typename U> SafeInt(U i)
	{
		//use signed-unsigned test on U
		if(SafeInt<U>::IsSigned())
		{
			//U is signed
			//whether T is signed or unsigned, must test range if sizeof T is smaller 
			//than sizeof U
			//if sizeof(T) >= sizeof(U) this optimizes out, only test for negative
			//for completely safe cases, optimizes to NOOP
			if(sizeof(T) < sizeof(U))
			{
				//test size
				if(i > (U)SafeInt<T>::MaxInt() || i < (U)SafeInt<T>::MinInt())
					throw SafeIntException(ERROR_ARITHMETIC_OVERFLOW);
			}
			else //test +/- for sizeof(T) >= sizeof(U) and T unsigned
			if(!IsSigned())
			{
				if(i < 0)
					throw SafeIntException(ERROR_ARITHMETIC_OVERFLOW);
			}
		}
		else
		{
			//U is unsigned
			//if sizeof T <= sizeof U AND T is signed,
			//test upper bound because MaxInt(unsigned) > MaxInt(signed)
			//OR
			//if sizeof T < sizeof U and T is unsigned
			if((IsSigned() && sizeof(T) <= sizeof(U)) ||
			(!IsSigned() && sizeof(T) < sizeof(U)) )
			{
				if(i > (U)MaxInt())
					throw SafeIntException(ERROR_ARITHMETIC_OVERFLOW);
			}	
		}

		m_int = (T)i;
	}

	~SafeInt(){};

	//helpful methods
	//these compile down to something as efficient as macros and allow run-time testing 
	//of type by the developer

	template <typename U> static bool IsSigned(SafeInt<U>)
	{
		return( (U)-1 < 0 );
	}

	template <typename U> static bool IsSigned(U)
	{
		return( (U)-1 < 0 );
	}

	static bool IsSigned()
	{
		return( (T)-1 < 0 );
	}

	static unsigned char BitCount(){return (sizeof(T)*8);}
	template <typename U> static unsigned char BitCount(U){return (sizeof(U)*8);}

	static bool Is64Bit(){return sizeof(T) == 8;}
	static bool Is32Bit(){return sizeof(T) == 4;}
	static bool Is16Bit(){return sizeof(T) == 2;}
	static bool Is8Bit(){return sizeof(T) == 1;}

	template <typename U> static bool Is64Bit(U){return sizeof(U) == 8;}
	template <typename U> static bool Is32Bit(U){return sizeof(U) == 4;}
	template <typename U> static bool Is16Bit(U){return sizeof(U) == 2;}
	template <typename U> static bool Is8Bit(U){return sizeof(U) == 1;}

	//both of the following should optimize away
	static T MaxInt()
	{
		if(IsSigned())
		{
			return (T)~((T)1 << (BitCount()-1));
		}
		//else
		return (T)(~(T)0);
	}

	static T MinInt()
	{
		if(IsSigned())
		{
			return (T)((T)1 << (BitCount()-1));
		}
		else
		{
			return ((T)0);
		}
	}

	//now start overloading operators
	//assignment operator
	//constructors exist for all int types and will ensure safety

	template <typename U> inline SafeInt<T>& operator =(U rhs)
	{
		//use constructor to test size
		//constructor is optimized to do minimal checking based
		//on whether T can contain U
		*this = SafeInt<T>(rhs);
		return *this;
	}

	inline SafeInt<T>& operator =(T rhs)
	{
		m_int = rhs;
		return *this;
	}

	template <typename U> inline SafeInt<T>& operator =(SafeInt<U> rhs)
	{
		*this = SafeInt<T>(rhs.Value());
		return *this;
	}

	inline SafeInt<T>& operator =(SafeInt<T> rhs)
	{
		m_int = rhs.m_int;
		return *this;
	}

	//casting operator not implemented
	//because it causes ambiguous compilation

	//Use the methods below to gain access to the data
	T Value() const {return m_int;}
	//and if you need a pointer to the data
	//this could be dangerous, but allows you to correctly pass
	//instances of this class to APIs that take a pointer to an integer
	//also see overloaded address-of operator below
	T* Ptr(){return &m_int;}
	const T* Ptr() const {return &m_int;}

	//or if SafeInt<T>::Ptr() is inconvenient, use the overload
	// operator & 
	//This allows you to do unsafe things!
	//It is meant to allow you to more easily
	//pass a SafeInt into things like ReadFile
	T* operator &(){return &m_int;}
	const T* operator &() const {return &m_int;}

	//unary operators
	bool operator !() const {return (!m_int) ? true : false;}
	
	//operator + (unary) 
	//note - normally, the '+' and '-' operators will upcast to a signed int
	//for T < 32 bits. This class changes behavior to preserve type
	SafeInt<T> operator +(void) const { return *this; };

	//unary  - 
		
	SafeInt<T> operator -() const
	{
		if(IsSigned())
		{
			//corner case
			if(m_int == MinInt())
				throw SafeIntException(ERROR_ARITHMETIC_OVERFLOW);

			//cast improves perf in the case of small ints
			return SafeInt<T>((T)-m_int);
		}
		//no-op for unsigned - generates warning 4146 at warning levels 2 and above
		return SafeInt<T>((T)-m_int);
	}

	//prefix increment operator
	SafeInt<T>& operator ++()
	{
		if(m_int == MaxInt())
		{