// DivInt
//
// This program demonstrate division of two integers.
//
// REQUIREMENTS:
//  * Must operate on integers and return integer quotient.
//  * Must be quick.
//
// Copyright (C) 2013 Greg Hedger
//

#ifdef WINDOWS
#include "stdafx.h"
#endif
#include <stdio.h>
#include <climits>

//
// Constants
//
typedef enum ErrCode
{
	ERR_DIVISIONBYZERO = 1,
};

//
// Macros
//
#define BITTOT(a) ( sizeof(a) * CHAR_BIT )

#define OUTCONS(a) printf( a "\n" );
#define GETNUMERICARG(a,b) sscanf( argv[a], "%d", &b );
#ifdef WINDOWS
define main _tmain
#endif

//
// Helper functions
//

// MakeAbs
// Make value positive and return whether it was flipped.
// Entry: value
// Exit:  true == flipped
bool MakeAbs( int *val )
{
	bool flipped = false;
	if( val )		// sanity
	{
		if( *val < 0 )
		{
			*val = -*val;		// 2s-complement negation
			flipped = true;
		}
	}
	return flipped;
}

// Div
// Entry: dividend
//        divisor
//        pointer to remainder
// Exit:  Quotient
// Throws: Division-by-zero
//
// ALGORITHM:
// if D == 0 then throw DivisionByZeroException end
// Q := 0                 initialize quotient and remainder to zero
// R := 0                     
// for i = n-1...0 do     where n is number of bits
//   R := R << 1          left-shift R by 1 bit    
//   R(0) := N(i)         set lsb of R equal to bit i of the numerator
//   if R >= D then
//     R = R - D               
//     Q(i) := 1
//   end
// end  
//
// NOTES: Performance is LOG(N), i.e. # of bits in datum.
// It is not dependent upon the size of the input as with the simpler
// repetitive substraction algorithm.
//
int Div( int dividend, int divisor, int *pRemainder )
{
	int	quotient = 0, 
		remainder = 0, 
		numerator = 0, 
		denominator = 0;
	bool negate = false;		// Negate result?
	if( 0 == divisor )
		throw ERR_DIVISIONBYZERO;

	if( MakeAbs( &dividend ) || MakeAbs( &divisor ) )
		negate = true;

	// Perform long division on integer
	int i;
	for( i = BITTOT(int) - 1; i >= 0; --i )
	{
		remainder <<= 1;
		remainder |= ( dividend & ( 1 << i ) ) ? 1 : 0;
		if( remainder >= divisor )
		{
			remainder -= divisor;
			quotient |= 1 << i;
		}
	}

	// Negate if necessary
	if( negate )
	{
		quotient = -quotient;
		remainder = -remainder;
	}
	if( pRemainder )
		*pRemainder = remainder;
	return quotient;
}

// PrintException
// Prints human-readable error
//
// Entry: ErrCode
// Exit: -
void PrintException( ErrCode ex )
{
	switch( ex )
	{
	case ERR_DIVISIONBYZERO:
		OUTCONS( "Division-by-zero error" );
		break;
		// TODO: Add additional exception output here
	default:
		break;
	}
}

// ValidateArgs
// Entry: arg count
//        args
// Exit: true == success
bool ValidateArgs( int argc, char *argv[] )
{
	bool ret = true;		// Assume success
	if( argc != 3 )			// Validate # of args
	{
		ret = false;
	}

	return ret;
}

// Entry point
int main(int argc, char* argv[])
{
	int divisor = 0, dividend = 0, remainder = 0;
	double work = 0.0;

	// Validate arguments
	if( !ValidateArgs( argc, argv ) )
	{
		OUTCONS( "Please enter a dividend and divisor." );
		return -1;
	}

	// Grab arguments
	GETNUMERICARG( 1, dividend );
	GETNUMERICARG( 2, divisor );

	// Make call, account for possibility of error
	try 
	{
		int quotient = Div( dividend, divisor, &remainder );
		printf( "%d / %d = %d R%d\n", dividend, divisor, quotient, remainder );
	}
	catch( ErrCode ex )
	{
		PrintException( ex );
	}

	// And exit...
	return 0;
}