/*
	Copyright (c) 2013, John Ryland
 */
#include <stdlib.h>
#include <stdio.h>
int loopcount = 0;


unsigned divmod_ref(unsigned num, unsigned den, unsigned* rem)
{
	*rem = num % den;
	return num / den;
}


unsigned divmod_experiment(unsigned num, unsigned den, unsigned* rem)
{
	unsigned quot = 0, qbit = 1; // quotient, and current quotient bit

	if ( den == 0 ) {
		printf("Divide by 0\n");
		//__divide_error();
		return 0;
	}

#if 0
	// Original version
	// No assumption about den size, but assuming 2s complement
	while ( (int)den >= 0 ) {
		den <<= 1;
		qbit <<= 1;
	}
	while ( qbit ) {
		loopcount++;
		if ( den <= num ) {
			num -= den;
			quot += qbit;
		}
		den >>= 1;
		qbit >>= 1;
	}
#endif

	// newer version

	// Shift den to the left until its top most bit is hard left (ie has no leading zeros)
	// Record how much we moved it to the left
	// Also count the leading zerps in the numerator
	// XXX we are assuming den is 32bits here
	unsigned int shift;
	int leadingZeros = 0;
	qbit = 0;
	shift = (den & 0xffff0000) ? 0 : 16; den <<= shift; qbit |= shift;
	shift = (num & 0xffff0000) ? 0 : 16; num <<= shift; leadingZeros |= shift;
	shift = (den & 0xff000000) ? 0 :  8; den <<= shift; qbit |= shift;
	shift = (num & 0xff000000) ? 0 :  8; num <<= shift; leadingZeros |= shift;
	shift = (den & 0xc0000000) ? 0 :  2; den <<= shift; qbit |= shift;
	shift = (num & 0xc0000000) ? 0 :  2; num <<= shift; leadingZeros |= shift;
	shift = (den & 0x80000000) ? 0 :  1; den <<= shift; qbit |= shift;
	shift = (num & 0x80000000) ? 0 :  1; num <<= shift; leadingZeros |= shift;
	qbit = 1 << qbit;
	num >>= leadingZeros;
	leadingZeros -= 2;
	den >>= leadingZeros;
	qbit >>= leadingZeros;

	while ( qbit ) {
		loopcount++;
		if ( den <= num ) {
			// This condition is executed for as many bits as are set in the result (quotient)
			num -= den;
			quot += qbit;

			// Need to calculate how many new leading zeros the subtraction has created
			// Then can skip ahead calculations and shift right den and qbit based on this
			// Perhaps a LUT can help here
			static const int leadingZerosLUT[64] = {
				6, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2,
				1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
				0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
			};
		}
		den >>= 1;
		qbit >>= 1;
	}



	*rem = num;
	return quot;
}



int addition_ref(int x, int y)
{
	return x + y;
}

// works
// degenerative case such as x=-1, y=1 will loop 32 times for 32bit ints
int addition_experiment(int x, int y)
{
	while ( y ) {
		// some unrolling to do 3 iterations per loop iteration
		int subExp1 = (x ^ y);
		int subExp2 = (x & y) << 1;
		int subExp3 = (subExp1 ^ subExp2);
		int subExp4 = (subExp1 & subExp2) << 1;
		x = (subExp3 ^ subExp4);
		y = (subExp3 & subExp4) << 1;

/*
		// non unrolled
		int x2 = x ^ y;
		y = (x & y) << 1;
		x = x2;
*/
		loopcount++;
	}
	return x;

	// recursive version
	if ( !y )
		return x;
	return addition_experiment(x ^ y, (x & y) << 1);

}

int subtract_ref(int x, int y)
{
	return x - y;
}

// not working
int subtract_experiment(int x, int y)
{
	return addition_experiment(x, ~y + 1);

	//int a = x | y;
	//int b = x & y;
	//return (a ^ b) | (b<<1);
	//return x - y;
}


int main()
{
	printf("hello\n");
	int x = 1232344;
	int y = 232344;
	int res0 = subtract_ref(x,y);
	int res1 = subtract_experiment(x,y);
	printf("result: %s   %i - %i = %i  (%i)\n", (res0==res1) ? "PASS" : "FAIL", x, y, res0, res1);
	printf("loop count: %i\n", loopcount);
	loopcount = 0;	
	res0 = addition_ref(x,y);
	res1 = addition_experiment(x,y);
	printf("result: %s   %i + %i = %i  (%i)\n", (res0==res1) ? "PASS" : "FAIL", x, y, res0, res1);
	printf("loop count: %i\n", loopcount);

	int rem0, rem1;	
	res0 = divmod_ref(x ,y, &rem0);
	res1 = divmod_experiment(x, y, &rem1);
	printf("result: %s   %i / %i = %i+%i  (%i+%i)\n", (res0==res1) ? "PASS" : "FAIL", x, y, res0, rem0, res1, rem1);
	printf("loop count: %i\n", loopcount);
	loopcount = 0;

	return 0;
}