Booth's Multiplication Algorithm

[DaNYer]

// Booth's Multiplication Algorithm
// 1. Depending on the current and previous bits, do one of the following:
// 00: a. Middle of a string of 0s, so no arithmetic operations.
// 01: b. End of a string of 1s, so add the multiplicand to the left half of the product.
// 10: c. Beginning of a string of 1s, so subtract the multiplicand from the left half of the product.
// 11: d. Middle of a string of 1s, so no arithmetic operation.
// 2. Shift the Product register right (arithmetic) 1 bit.
//
// Example: 2 x 6
// m=2,p=6;
//
// m = 0010
// p = 0000 0110
//
// p
// 0000 0110 0 no-op
// 0000 0011 0 >> p
// 1110 0011 0 p = p - m
// 1111 0001 1 >> p
// 1111 0001 1 no-op
// 1111 1000 1 >> p
// 0001 1000 1 p = p + m
// 0000 1100 0 >> p
//
// =12
//
// Example: 2 x -3
//
// m = 0010
// p = 0000 1101
//
// 1110 1101 0 p = p - m
// 1111 0110 1 >> p
// 0001 0110 1 p = p + m
// 0000 1011 1 >> p
// 1110 1011 0 p = p - m
// 1111 0101 1 >>p
// 1111 0101 1 no-op
// 1111 1010 1 >>p
//
// =-6



#include <stdio.h>
#include <stdlib.h>

void load(int*, int*, int*);
void display(int*, int*, int*);
bool compute(int*, int*, int*, bool);
void addPLM(int*, int*);
void negate(int*);

void main()
{
int PLreg [4];
int PRreg [5];
int Mreg [4];
bool neg=0;

load(PLreg, PRreg, Mreg); //initialising registers with data

printf(" PL\t PR\t\tM\n"); //page title

display(PLreg, PRreg, Mreg); //general display
printf("\t-------------------------------------\n");//page title


//computation first step
neg = compute(PLreg, PRreg, Mreg, neg); //compute 1st bit
display(PLreg, PRreg, Mreg); //display


neg = compute(PLreg, PRreg, Mreg, neg); //compute 2nd bit
display(PLreg, PRreg, Mreg); //display

neg = compute(PLreg, PRreg, Mreg, neg); //compute 3rd bit
display(PLreg, PRreg, Mreg); //display

neg = compute(PLreg, PRreg, Mreg, neg); //compute 4th bit
display(PLreg, PRreg, Mreg); //display
}


bool compute(int PL[], int PR[], int M[], bool neg)
{
int MCopy [4];

if((PR[3] == 0) && (PR[4] == 0)) // BOOTH - 00 - NO-OP
{
printf("\t\t\t\t\t\t 00; Outside. shifting...\n");
PR[4] = PR[3];
PR[3] = PR[2];
PR[2] = PR[1];
PR[1] = PR[0];
PR[0] = PL[3];
PL[3] = PL[2];
PL[2] = PL[1];
PL[1] = PL[0];
if(neg)
{
PL[0] = 1;
neg = 1;
}
else
{
PL[0] = 0;
neg = 0;
}
return neg;
}
else if ((PR[3] == 1) && (PR[4] == 1)) // BOOTH - 11 - NO-OP
{
printf("\t\t\t\t\t\t 11; Inside. shifting...\n");
PR[4] = PR[3];
PR[3] = PR[2];
PR[2] = PR[1];
PR[1] = PR[0];
PR[0] = PL[3];
PL[3] = PL[2];
PL[2] = PL[1];
PL[1] = PL[0];
if(neg)
{
PL[0] = 1;
neg = 1;
}
else
{
PL[0] = 0;
neg = 0;
}
return neg;
}


else if ((PR[3] == 0) && (PR[4] == 1)) // BOOTH - 01 - Add
{
printf("\t\t\t\t\t\t 01; End. Add.\n");

addPLM(PL, M); // Addition

PR[4] = PR[3]; // then shifting
PR[3] = PR[2];
PR[2] = PR[1];
PR[1] = PR[0];
PR[0] = PL[3];
PL[3] = PL[2];
PL[2] = PL[1];
PL[1] = PL[0];
/* if(neg)
{
PL[0] = 1; //wrong???
neg = 1;
}
else
{*/
PL[0] = 0;
/* neg = 0;
}*/
return neg;
}


else if ((PR[3] == 1) && (PR[4] == 0)) // BOOTH - 10 - Substract
{
printf("\t\t\t\t\t\t 10; Begining. Sub.\n");

/////////////////////////
// ISUBSTRACT operation HERE.
// PL, M, neg
//
// first lets negate MCopy (an image of M)
//
MCopy[0] = M[0];
MCopy[1] = M[1];
MCopy[2] = M[2];
MCopy[3] = M[3];

negate(MCopy);
neg = 1;

// now add up
addPLM(PL, MCopy); // Addition (actually substraction)

/////////////////////////

PR[4] = PR[3]; // then shifting
PR[3] = PR[2];
PR[2] = PR[1];
PR[1] = PR[0];
PR[0] = PL[3];
PL[3] = PL[2];
PL[2] = PL[1];
PL[1] = PL[0];
if(neg)
{
PL[0] = 1;
neg = 1;
}
else
{
PL[0] = 0;
neg = 0;
}
return neg;
}

}


void negate(int A[])
{
int i;
int ONE[4];
ONE[0] = 0;
ONE[1] = 0;
ONE[2] = 0;
ONE[3] = 1;


for (i=0; i<=3; i++)
{
if(A[i] == 1)
A[i] = 0;
else
A[i] = 1;
}

//ADD 1
addPLM(A, ONE);
}




// done.
void addPLM(int A[], int B[])
{
int next, i, carry=0;

for (i=3; i>=0; i--)
{
next = 1;
if (A[i]==0 && B[i]==0) //00 case
{
A[i]= carry;
carry = 0;
next = 0;
} // good.

if (next)
if (A[i]==0 && B[i]==1) //01 case - transfer
{
if (carry == 0)
A[i] =1;
else
A[i]=0;
next = 0;
}

if(next)
if (A[i]==1 && B[i]==0) //10 case - transfer
{
if (carry == 0)
A[i] =1;
else
A[i]=0;
next = 0;
}

if(next)
if (A[i]==1 && B[i]==1) //11 case - generate
{
if (carry == 0)
{
A[i] =0;
carry = 1;
}
else
A[i]=1;
next = 0;
}
}
}



///////////////////////////////////////////////////////
//displaying {OK}
void display(int PL[], int PR[], int M[])
{
int i;
printf("\t");
for(i=0; i<=3; i++)
printf(" %d", PL[i]);
printf(" ");
//////////////////

for(i=0; i<=3; i++)
printf(" %d", PR[i]);
printf(" %d", PR[4]);
///////////////////

printf("\t ");
for(i=0; i<=3; i++)
printf(" %d", M[i]);
///////////////////

printf("\n");
}


//function to load registers with data. {OK}
void load(int PL[], int PR[], int M[])
{
PL[0] = 0;
PL[1] = 0;
PL[2] = 0;
PL[3] = 0;

PR[0] = 0;
PR[1] = 1;
PR[2] = 1;
PR[3] = 0;
PR[4] = 0; //DUMMY BIT

M[0] = 0;
M[1] = 1;
M[2] = 1;
M[3] = 0;

}

[DaNYer]

Output:


PL PR M
0 0 0 0 0 1 1 0 0 0 1 1 0
-------------------------------------
00; Outside. shifting...
0 0 0 0 0 0 1 1 0 0 1 1 0
10; Begining. Sub.
1 1 0 1 0 0 0 1 1 0 1 1 0
11; Inside. shifting...
1 1 1 0 1 0 0 0 1 0 1 1 0
01; End. Add.
0 0 1 0 0 1 0 0 0 0 1 1 0
Press any key to continue

[greka]

recepty na budushee, DaNYer:


if(neg)
{
PL[0] = 1;
neg = 1;
}
else
{
PL[0] = 0;
neg = 0;
}

zamenyaetsa na:


PL[0] = neg & 0x01;
neg = neg & 0x01;


konstrukcii s "IF"-m sil'no zamedlyayut programmu.

[greka]

to je est' v funkcii NEGATE:


for (i=0; i<=3; i++)
{
if(A[i] == 1)
A[i] = 0;
else
A[i] = 1;
}


zamenyaetsa na:


for (i=0; i<=3; i++)
{
A[i] = -A[i];
}

[greka]

i ne nado poshlit'....


PR[4] = PR[3]; // then shifting
PR[3] = PR[2];
PR[2] = PR[1];
PR[1] = PR[0];
PR[0] = PL[3];
PL[3] = PL[2];
PL[2] = PL[1];
PL[1] = PL[0];


oformi eto v vide funkcii, bud' gumannee k chitayushim tvoy kod ;)

[DaNYer]

Originally posted by Greco El
to je est' v funkcii NEGATE:


for (i=0; i<=3; i++)
{
if(A[i] == 1)
A[i] = 0;
else
A[i] = 1;
}


zamenyaetsa na:


for (i=0; i<=3; i++)
{
A[i] = -A[i];
}



chegooooo!????

eto binary negate, Greco jan, cavt tanem ya..... minusom tut ne pomojesh :)

[greka]

sorry, ty prav, konechno...

tut nujna operaciya podobnogo roda:


for (i=0; i<=3; i++)
{
A[i] = A[i] ^ 0x01;
}


;)

[Tumanyan]

Вдогонку: вектора с константами лучше вывести из тел функций и сделать глобальными. Иначе, выделение места под вектор/инициализация будут происходить при каждом вызове функции, что не есть хорошо для производительности.

[Фича]

Одно улучшение уже заметно - господин Даньер стал писать int * вместо int []... :)
Про эту функцию было уже много сказано и все равно написана не по людски :(
Вот... а за одно предложу еще один вариант суммирования, который соответствует аппаратной реализации:


pC[i] = pA[i] ^ pB[i] ^ bCarry;
bCarry = (pA[i]&pB[i]) || (pB[i] & bCarry) || (pA[i] & bCarry);


:)

[DaNYer]

Originally posted by Фича
Одно улучшение уже заметно - господин Даньер стал писать int * вместо int []... :)



da ladno.... "gospodin"....

ya * pisal v pozaproshlom semestre s tex por ni strochki na c ne napisal. podzabil, sorry. spasibo chto napomnil :devil:



Tumanyan: del'no. thanx.