stupid reduction of summands simulation for cs388

reductsumm.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
size_t min(size_t x, size_t y) { return x < y ? x : y; }
size_t max(size_t x, size_t y) { return x > y ? x : y; }
size_t min3(size_t x, size_t y, size_t z) { return x < y ? min(x, z) : min(y, z); }
size_t max3(size_t x, size_t y, size_t z) { return x > y ? max(x, z) : max(y, z); }


// binary to int
unsigned int btoi(const char *ptr, size_t *bitlength)
{
	unsigned int value = 0;
	if(bitlength != NULL) *bitlength=0;
	char ch = *ptr;

	while (ch == ' ' || ch == '\t')
		ch = *(++ptr);
	while(1) {

		if (ch == '0')
			value = value << 1;
		else if (ch == '1')
			value = (value << 1) + 1;
		else if (ch == 0 || ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t')
			return value;
		else
			return 0;
		ch = *(++ptr);
		if(bitlength != NULL) (*bitlength)++;
	}
}

// generate summands out of muliplicand and multiplierof bit length n
void generate_summands(uint64_t summands[], uint32_t mcand, uint32_t mplier, size_t n)
{
	size_t i;
	for(i=0;i<n;i++)
	{
		if(mplier & (1 <<i))
		{
			summands[i] = ((uint64_t)mcand) << i;
		}
		else
		{
			summands[i] = __UINT64_C(0);
		}
	}
}

// Imitate summation by full adder of 3 64 bit numbers (double XOR)
uint64_t generate_sum(uint64_t x, uint64_t y, uint64_t z)
{
	return x ^ y ^ z;
}

// Imitate carry generation by full adder of 3 64 bit numbers (ANDs into 3OR)
uint64_t generate_carry(uint64_t x, uint64_t y, uint64_t z)
{
	return ((x&y)|(x&z)|(y&z))<<1;
}

// stupid macro/func for array shifting
void delete_row_u64(uint64_t array[], size_t len, size_t index)
{
	size_t i;
	for(i=index+1;i<len;i++)
	{
		array[i-1]=array[i];
	}
}

// stupid macro/func for array shifting (this is why I choose C)
void delete_row_szt(size_t array[], size_t len, size_t index)
{
	size_t i;
	for(i=index+1;i<len;i++)
	{
		array[i-1]=array[i];
	}
}

// Reduction of summands
// Will recursively add/combine summands until only 2 summands remain, which can be added.
// Sets of 3 rows of summands are added together, producing a sum row and a carry row.
// The array is compacted (shifted down) and the call is made recursively until there
// are 2 or less rows in the summands array.
// Hardware costs are estimated by determining the number of full adders to be used
// in each group of additions. We assume that adders are not re-used between iterations.
// Note that the number of adders is doubled, so that half adders can also be tracked.
// Since reduction of summands can be done in parallel, timing is calculated by simply 
// recording the number of iterations.
//
// @param summands[]	The array of summands to be compressed
// @param row_end[]		Array containing indices into the summands where the row "ends"
// @param row_offs[]    Array containing indices into the summands where the row "starts"
// @param summandcount	The number of summand rows currently in the array
// @param adders 		Pointer to a location to store the number of adders used
// @return 		The number of iterations performed to complete reduction.
size_t reduce_summands(uint64_t summands[], size_t row_end[], size_t row_offs[], size_t summandcount, size_t *adders)
{
	size_t num_reductions = summandcount/3, i=0;
	uint64_t sum, carry;
	if(num_reductions==0) return 0;
	for(i = 0; i < num_reductions; i++)
	{
		size_t br=i*3; // base row for this reduction

		size_t num_addrs=*adders, fa_start, fa_end;
		// how many adders are we actually using here?

		// We start using full adders at this bit:
		fa_start = max3(row_offs[br], row_offs[br+1], row_offs[br+2]);
		// And our last full adder is just before this bit:
		fa_end = min3(row_end[br], row_end[br+1], row_end[br+2]);

		num_addrs += (fa_end-fa_start)*2; // number of full adders, stored as 2x so we can track half adders

		if(row_offs[br] <= row_offs[br+1]) // should be tautological 
			num_addrs += row_offs[br+2] - row_offs[br+1]; // Half adders used where only row0+row1 are added.

		if(row_end[br+1] <= row_end[br+2]) // should be tautological
			num_addrs += row_end[br+1]-row_end[br]; // Half adders used for row1+row2

		*adders = num_addrs;
		// generate sum and carry rows
		sum = generate_sum(summands[br], summands[br+1], summands[br+2]);
		carry = generate_carry(summands[br], summands[br+1], summands[br+2]);

		// store sum and carry in first two summand rows
		summands[br]=sum; summands[br+1]=carry;
		row_offs[br+1] = min(row_offs[br+1], row_offs[br+2])+1; // Carry row starts just after the actual sums
		// sum row ends at max digits
		row_end[br] = max3(row_end[br], row_end[br+1], row_end[br+2]);
		// carry row ends after our last half or full adder
		row_end[br+1]= row_end[br+1]+1;

	}
	for(i=0; i< num_reductions;i++)
	{
		// get rid of rows reduced out in this iteration
		delete_row_u64(summands, summandcount, ((i+1)*3)-(1+i));
		delete_row_szt(row_end, summandcount, ((i+1)*3)-(1+i));
		delete_row_szt(row_offs, summandcount, ((i+1)*3)-(1+i));
	}
	summandcount -= num_reductions; // we've removed one summand per reduction
	return 1+reduce_summands(summands, row_end, row_offs, summandcount, adders);
}

// Print a 32-bit number of actual length n
void print_bin32(uint32_t x, size_t n)
{
	x <<= 32-n;
	while(n--)
	{
		putchar((x & 0x80000000) ? '1' : '0');
		x <<= 1;
	}
}
// Print a 64-bit number of actual length n
void print_bin64(uint64_t x, size_t n)
{
	x <<= 64-n;
	while(n--)
	{
		putchar((x & __UINT64_C(0x8000000000000000)) ? '1' : '0');
		x <<= 1;
	}
}

// Assumes a bit-length of a number by finding the offset of the most significant high bit
size_t get_bitlength(uint32_t x)
{
	if(x) return get_bitlength(x >> 1)+1;
	return 0;
}

// Performs multiplication/reduction with a large amount of output
void do_problem_full(uint32_t in1, uint32_t in2)
{
	size_t n = 32, i, row_end[32], row_offs[32], cnt, adder_cnt=0;
	uint64_t summands[32];
	n=get_bitlength(max(in1,in2));
	printf("n=%u\n", n);
	for(i=0;i<n;i++) printf(" ");
	print_bin32(in1, n);
	printf("\nx");
	for(i=1;i<n;i++) printf(" ");
	print_bin32(in2,n);
	printf("\n\n");
	generate_summands(summands, in1, in2, n);
	for(i=0;i < n; i++)
	{
		row_end[i]=n+i;
		row_offs[i]=i;
		print_bin64(summands[i], n*2);
		printf("\n");
	}
	printf("========\n");
	adder_cnt=0;
	cnt=reduce_summands(summands, row_end, row_offs, n, &adder_cnt);
	print_bin64(summands[0], n*2);
	printf("\n");
	print_bin64(summands[1], n*2);
	printf("\n");
	printf("========\n");
	print_bin64(summands[0]+summands[1], n*2);
	printf("\n%u * %u = %llu\n", in1, in2, summands[0]+summands[1]);
	printf("Timing: 1DT + %u*4 DT + FastAdderTime\n", cnt);
	printf("Hardware cost: %u.%u Full Adders\n", adder_cnt / 2, (adder_cnt % 2) * 5);
}

// Performs the multiplication/reduction with a small amount of output
void do_problem_short(uint32_t in1, uint32_t in2, size_t n)
{
	size_t i, row_end[32], row_offs[32], cnt, adder_cnt=0;
	uint64_t summands[32];
	uint64_t sum, in64=in1;
	generate_summands(summands, in1, in2, n);
	for(i=0;i < n; i++)
	{
		row_end[i]=n+i;
		row_offs[i]=i;
	}
	adder_cnt=0;
	cnt=reduce_summands(summands, row_end, row_offs, n, &adder_cnt);
	print_bin32(in1, n);
	printf(" * ");
	print_bin32(in2, n);
	printf(" = ");
	if(n > 1)
		sum = summands[0]+summands[1];
	else
		sum = summands[0];
	print_bin64(sum, n*2);
	if(in64 * in2 != sum) {
		printf("\nABANDON SHIP!!!! %u * %u != %llu (%llu)\n", in1, in2, sum, in64*in2);
		exit(1);
	}
	printf("\n%u * %u = %llu\n", in1, in2, sum);
	printf("Timing: 1DT + %u*4 DT + FastAdderTime\n", cnt);
	printf("Hardware cost: %u.%u Full Adders\n", adder_cnt / 2, (adder_cnt % 2) * 5);
}

int main(int argc, char* argv[])
{
	uint32_t in1=0xffffffff, in2=0xffffffff;
	size_t n=32, n2=32;
	if(argc == 3)
	{
		in1 = btoi(argv[1], &n);
		in2 = btoi(argv[2], &n2);
		do_problem_short(in1, in2, max(n,n2));
	}
	else if(argc == 2)
	{
		char buf[128];
		printf("Doing file mode...\n");
		FILE * input = fopen(argv[1], "r");
		if(input == NULL)
		{
			printf("Failed opening: %s", argv[1]);
			return 1;
		}
		while(fgets(buf, 128, input) != NULL)
		{
			char * num2 = strchr(buf, (int)'*')+1;
			if(num2 == NULL) break; // we're done

			in1=btoi(buf, &n);
			in2=btoi(num2, &n2);
			printf("Inputs: %s", buf);
			do_problem_short(in1,in2, max(n,n2));
			printf("\n");
		}
	}

	return 0;
}