mul.cpp

#include <iostream>

struct longNumber {
	int length;
	unsigned char *digits;
};

//TODO: also print in binary!
void printLongNumber asBinary(longNumber a)
{
	fixme;
}

void printLongNumber(longNumber a) {
	for (int i = 0; i < a.length; i++)
		std::cout << (int)a.digits[i] << " ";

	std::cout << std::endl;
}

longNumber multiplyBySingleDigit(longNumber a, unsigned char b)
{
	longNumber result;
	result.length = a.length + 1;
	result.digits = new unsigned char[result.length];

	unsigned char carry = 0;
	for (int i =a.length - 1; i>=0; i--) {// loop over digits
		int aDigit =(int)a.digits[i];
		int bDigit = (int)b;// step 1. multiply current digit by b
		int Mult=aDigit*bDigit;
		// step 2. add carry
		Mult =Mult+carry;
		// step 3. split result to current digit and new carry
		result.digits[i+1]=Mult%256;
		carry=Mult/256;
		// step 4. write out current digit

	}

	//write out carry
	result.digits[0]=carry;

	return result;

}

longNumber extend(longNumber a, int extendToDigits)
{
	int extendBy = extendToDigits - a.length;
	longNumber result;
	result.length=extendToDigits;	
	result.digits = new unsigned char[result.length];

	for ( int i=0; i<a.length; i++){
		result.digits[i+extendBy]=a.digits[i];
	}

	return result;
}

longNumber shiftLeft(longNumber a, int shiftBy)
{
	longNumber result;
	result.length = shiftBy+a.length;
	result.digits = new unsigned char[result.length];

	for(int i = 0; i<a.length;i++){
		result.digits[i]=a.digits[i];
	}
	return result;
}

longNumber extendAndShiftLeft(longNumber a, int extendToDigits, int shiftBy)
{
	longNumber eash;
	//printLongNumber(eash);
	eash= shiftLeft(a, shiftBy);
	//printLongNumber(eash);
	eash =extend(eash, extendToDigits);
	//printLongNumber(eash);

	return eash;
}

longNumber addLongNumbers(longNumber numbers[], int count)
{
	longNumber result;
	result.length=numbers[0].length;
	result.digits=new unsigned char[result.length];
	int S=0;
	int carry=0;

	for(int digitIndex=result.length -1; digitIndex>=0; digitIndex--){
		S=0;
		for(int numberIndex = 0; numberIndex<= count-1; numberIndex++){

			S=S+numbers[numberIndex].digits[digitIndex];

		}
		S=S+carry;
		result.digits[digitIndex]=S%256;
		carry=S/256;

	}
	return result;
}

longNumber multiply(longNumber a, longNumber b) {
	longNumber result;
	//std::cout << a.length << " " << b.length << std::endl;
	result.length = a.length + b.length;
	result.digits = new unsigned char[result.length];

	longNumber arr[b.length];
	int shiftBy=0;

	for(int i = b.length-1; i>=0; i--){
		longNumber temp= multiplyBySingleDigit(a,b.digits[i]);
		temp =shiftLeft(temp, shiftBy);
		shiftBy++;
		temp= extend(temp, result.length);
		arr[i]=temp;

	}
	result= addLongNumbers(arr, b.length);

	return result;
}

void checkMultiplicationByDigit(longNumber a, unsigned char b, longNumber expectedResult) {
	longNumber actualResult = multiplyBySingleDigit(a, b);
	if (actualResult.length != expectedResult.length) {
		std::cout << "Wrong multiplication result: length mismatch" << std::endl;
		return;
	}

	for (int i = 0; i < actualResult.length; i++) {
		if (actualResult.digits[i] != expectedResult.digits[i]) {
			std::cout << "Wrong multiplication result: digit mismatch" << std::endl;
			return;
		}
	}

	std::cout << "Correct multiplication result" << std::endl;
}

void checkMultiplication(longNumber a, longNumber b, longNumber expectedResult) {
	longNumber actualResult = multiply(a, b);
	if (actualResult.length != expectedResult.length) {
		std::cout << "Wrong multiplication result: length mismatch" << std::endl;
		return;
	}

	for (int i = 0; i < actualResult.length; i++) {
		if (actualResult.digits[i] != expectedResult.digits[i]) {
			std::cout << "Wrong multiplication result: digit mismatch" << std::endl;
			return;
		}
	}

	std::cout << "Correct multiplication result" << std::endl;
}

int main() {
	longNumber one;
	one.length = 1;
	one.digits = new unsigned char[one.length];
	one.digits[0] = 1;

	longNumber one2byte; // = {2, {0, 1}};
	one2byte.length = 2;
	one2byte.digits = new unsigned char[one2byte.length];
	one2byte.digits[0] = 0;
	one2byte.digits[1] = 1;

	longNumber twenty;
	twenty.length = 1;
	twenty.digits = new unsigned char[twenty.length];
	twenty.digits[0] = 20;

	longNumber fourHundred;
	fourHundred.length = 2;
	fourHundred.digits = new unsigned char[fourHundred.length];
	fourHundred.digits[0] = 1;
	fourHundred.digits[1] = 144;

	checkMultiplicationByDigit(one, 1, one2byte);
	checkMultiplicationByDigit(twenty, 20, fourHundred);

	printLongNumber(fourHundred);
	printLongNumber(shiftLeft(fourHundred, 2));
	printLongNumber(extendAndShiftLeft(fourHundred, 7, 2));

	longNumber numbers[3];
	numbers[0] = numbers[1] = numbers[2] = fourHundred;
	printLongNumber(addLongNumbers(numbers, 3));

	//printLongNumber(one2byte);
	//printLongNumber(multiplyBySingleDigit(one, 1));

	checkMultiplication(one, one, one2byte); // one * one == one2byte
	checkMultiplication(twenty, twenty, fourHundred);

	longNumber l_255;
	l_255.length = 1;
	l_255.digits = new unsigned char[l_255.length];
	l_255.digits[0] = 255;

	longNumber l_65025;
	l_65025.length = 2;
	l_65025.digits = new unsigned char[l_65025.length];
	l_65025.digits[0] = 254;
	l_65025.digits[1] = 1;

	checkMultiplication(l_255, l_255, l_65025);


	//printLongNumber(multiply(l_255, l_255));

	longNumber l_0xFFAA0101;
	l_0xFFAA0101.length = 4;
	l_0xFFAA0101.digits = new unsigned char[4];
	l_0xFFAA0101.digits[0] = 0xFF;
	l_0xFFAA0101.digits[1] = 0xAA;
	l_0xFFAA0101.digits[2] = 0x01;
	l_0xFFAA0101.digits[3] = 0x01;


	longNumber l_0xEE01AA;
	l_0xEE01AA.length = 3;
	l_0xEE01AA.digits = new unsigned char[3];
	l_0xEE01AA.digits[0] = 0xEE;
	l_0xEE01AA.digits[1] = 0x01;
	l_0xEE01AA.digits[2] = 0xAA;

	longNumber l_0xedb1b65fd3abaa;
	l_0xedb1b65fd3abaa.length = 7;
	l_0xedb1b65fd3abaa.digits = new unsigned char[7];
	l_0xedb1b65fd3abaa.digits[0] = 0xED;
	l_0xedb1b65fd3abaa.digits[1] = 0xB1;
	l_0xedb1b65fd3abaa.digits[2] = 0xB6;
	l_0xedb1b65fd3abaa.digits[3] = 0x5F;
	l_0xedb1b65fd3abaa.digits[4] = 0xD3;
	l_0xedb1b65fd3abaa.digits[5] = 0xAB;
	l_0xedb1b65fd3abaa.digits[6] = 0xAA;

	checkMultiplication(l_0xFFAA0101, l_0xEE01AA, l_0xedb1b65fd3abaa);

}