Two's Complement Binary Division

TwosComplementBinaryDivision.c

//*******************************************************************
// File:			TwosComplementBinaryDivision.c
// Author(s):		Mohamed Ennahdi El Idrissi
// Date:  			06-Aug-2012
// 
// Input Files:		NONE
// Output Files:	NONE
// Description:  	CSC 2304 - <Computer Architecture and Organization>
//							   <Computer Arithmetic>
//					This program implements the Two's Complement Binary Division algorithm 
//					that is discussed in Chapter 9 of
//					William Stallings' Computer Organization and Architecture, 8th edition
//*******************************************************************
#include <stdio.h>
#include <ctype.h>

#define WORD 4
#define VERBOSE 1 // 0

#define YES	'Y'
#define NO	'N'

void  leftShift( char*, char* ) ;
void  addition( char*, const char* );
void  twosComplement( char* );
void  twosComplementAddition( char* , const char* );
char* twosComplementMultiplication( char* , char* );

int main() {
	char M[] = {"0011"}, divisor[WORD + 1];
	char Q[] = {"0111"}, dividend[WORD + 1];
	char *result, c;

	printf("\n\t\tTwo's Complement Binary Division Algorithm");
	printf("\n\t\t******************************************");
	do {
		printf("\n\n\nEnter dividend:	");
		gets(Q);
		printf("\nEnter divisor:	");
		gets(M);
		strcpy(dividend, Q);
		strcpy(divisor, M);
		result = twosComplementMultiplication(M, Q);
		printf("\nDividend:\t%s", dividend);
		printf("\nDivisor:\t%s", divisor);
		printf("\nQuotient:\t%s", Q);
		printf("\nRemainder:\t%s", result);
		printf("\n\n\n");
		printf("Continue? (Y/N): ");
		do {
			c = toupper(getch());
		} while ( c != YES && c != NO );
		putchar(c);
	} while ( c == YES );
	puts("\n");
	return 0;
}

void leftShift(char A[], char Q[]) {
	int i;
	char c;
	c = Q[0];
	for (i = 0; i < WORD - 1; i++) {
		A[i] = A[i + 1];
		Q[i] = Q[i + 1];
	}
	A[WORD - 1] = c;
	Q[WORD - 1] = '0';
}

void addition(char A[], const char M[]) {
	int i;
	char c = '0';
	for (i = WORD - 1; i >= 0; i--) {
		if (A[i] == '0' && M[i] == '0') {
			A[i] = c;
			c = '0';
		} else {
			if ((A[i] == '1' && M[i] == '0') || (A[i] == '0' && M[i] == '1')) {
				if (c == '0') {
					A[i] = '1';
				} else {
					A[i] = '0';
				}
			} else {
				if (A[i] == '1' && M[i] == '1') {
					A[i] = c;
					c = '1';
				}
			}
		}
	}
}

void twosComplement(char M[]) {
	short i;
	for (i = 0; i < WORD; i++) {
		if (M[i] == '0') {
			M[i] = '1';
		} else {
			M[i] = '0';
		}
	}
	addition(M, "0001");
}

void twosComplementAddition(char A[], const char M[]) {
	int i;
	char temp[WORD + 1];
	
	strcpy(temp, M);
	twosComplement(temp);

	if (VERBOSE) {
		printf("\n\t%s\t\t    \t\tTwo's Complement of %s", temp, M);
	}
	addition(A, temp);
}

char* twosComplementMultiplication(char M[], char Q[]) {
	char *A = (char*) malloc( sizeof(char) * (2 * WORD + 1));
	int i, quotient = 0, remainder = 0;
	char *m;
	strcpy(A, "0000");
	/*
	 * When Dividend (D) and/or Divisor (V) are negative (first bit is '1'):
	 * - When D and V are negative: Remainder is negative (undergoes a two's complement).
	 * - When D is negative: Quotient and Remainder are both negative (undergo a two's complement).
	 * - When V is negative: Quotient is negative (undergoes a two's complement).
	 * The display of Quotient and Remainder depends on the abovementionned rules.
	 */
	if ( Q[0] == '1' && M[0] == '1' ) {
		remainder = 1;
		twosComplement(M);
	} else {
		if ( Q[0] == '1' ) {
			quotient = 1;
			remainder = 1;
		} else {
			if ( M[0] == '1' ) {
				twosComplement(M);
				quotient = 1;
			}
		}
	}
	
	if (VERBOSE) {
		printf("\n\tA\t\tQ");
		printf("\n\t%s\t\t%s\t\tInitial value", A, Q);
		printf("\n--------------------------------------------------------------");
	}
	
	for (i = 0; i < WORD; i++) {
		leftShift(A, Q);
		if (VERBOSE) {
			printf("\n\t%s\t\t%s\t\tLeft Shift", A, Q);
		}
		twosComplementAddition(A, M);
		if (VERBOSE) {
			printf("\n\t____");
			printf("\n\t%s\t\t    \t\tSubtract", A);
		}

		if (A[0] == '1') {
			Q[WORD - 1] = '0';
			addition(A, M);
			if (VERBOSE) {
				printf("\n\t%s\t\t%s\t\tRestore", A, M);
			}
		} else {
			Q[WORD - 1] = '1';
		}
		if (VERBOSE) {
			printf(", set Q0 = %c", Q[WORD - 1]);
			printf("\n--------------------------------------------------------------\n");
		}
	}
	if (remainder) {
	//	printf("\nREMAINDER undergoes a two's complement");
		twosComplement(A);
	}
	if (quotient) {
	//	printf("\nQUOTIENT undergoes a two's complement");
		twosComplement(Q);
	}

	return A;
}