///////////////////////////////////////////////////////////////// Automatic Multiplier Generator Tool                       //// convert signed multiplication to script                   //// using Nonrecursive Signed Common Subexpression Algorithm  ///////////////////////////////////////////////////////////////////// Writer      : Boris Kipnis// Last Update : 5/5/2005//#include "GenMultScript.h"#define GMULT_MIN_OPTIMIZE 0#define GMULT_TAB_OFFSET 0////////////////////////////////////////////// PRINT FUNCTIONS                        //// Visualization functions for debugging  //////////////////////////////////////////////void GenMultScript::printArray(vector<int> ar) {  for (int j=0;j<ar.size();j++) {      printf("%d,",ar[j]);  }  printf("\r\n");}// Show Dual array a line, b linevoid  GenMultScript::printDualArray(vector<inta_intb_s> ar) {  for (int j=0;j<ar.size();j++) {      printf("%d,",ar[j].a);  }  printf("\r\n");  for (int j=0;j<ar.size();j++) {      printf("%d,",ar[j].b);  }  printf("\r\n");}// Show position Array X,Yvoid  GenMultScript::printPosArray(vector<pos_s> ar) {  for (int j=0;j<ar.size();j++) {    printf("%d,%d : ",ar[j].x,ar[j].y);  }  printf("\r\n");}void  printMultScript(vector<mult_s> ar) {  int i;  if (ar.size()==0) printf("0");  for (i=0;i<ar.size();i++) {    switch((ar[i]).type) {	   case TERMT_PP : printf("+Term%d<<%d",(ar[i]).termNum,(ar[i]).shift);  break;	   case TERMT_MM : printf("-Term%d<<%d",(ar[i]).termNum,(ar[i]).shift);  break;	   case TERMT_PM : printf("+Term%d<<%d",(ar[i]).termNum,(ar[i]).shift);  break;	   case TERMT_MP : printf("-Term%d<<%d",(ar[i]).termNum,(ar[i]).shift);  break;	   case SIG_P    : printf("+In<<%d",(ar[i]).shift);  break;	   case SIG_M    : printf("-In<<%d",(ar[i]).shift);  break;       case TEMP_P   : printf("+Temp%d<<%d",(ar[i]).termNum,(ar[i]).shift); break;       case TEMP_M   : printf("-Temp%d<<%d",(ar[i]).termNum,(ar[i]).shift); break;       default       : printf("Unknown, "); break;    }  }  printf("\r\n");}////////////////////////////////////////// Convert Integer to Binary String   //////////////////////////////////////////string  GenMultScript::int2binStr(int num, const int size) {  int i;  string str;  char *str_c;   for (i=0;i<size;i++) {    if (num & 0x01) {       str = '1' + str;    } else {       str = '0' + str;    }    num = num >> 1;  }  return(str);}/////////////////////////////////////////////////// Convert Integer to base (3x) I multArraySingleTermnteger Array  //// 0101 = [0,1,-1,1-1]                         ///////////////////////////////////////////////////vector<int>  GenMultScript::int23x(int num,int size) {  string str;  vector<int> ar;  string sym_char;  int  sym;  int i;  int numAbs;  // Limit LOWER Size to avoid calculation errors  if (size<2) size = 2;  // Calculate binary representation for Integer value  numAbs = abs(num);              // convert to positive  str = int2binStr(numAbs,size);  // convert to binary  printf("%d binary = %s =>",num,str.c_str());  //////////////////////////////////////////////  // Convert Binary to 3x representation  str='0'+str+'0';  size=str.size();    ar.clear();  for (i=0;i<size-1;i++) {      sym_char = str[i];      sym_char += str[i+1];      if      (!sym_char.compare("00")) sym = 0;      else if (!sym_char.compare("11")) sym = 0;      else if (!sym_char.compare("01")) sym = 1;      else if (!sym_char.compare("10")) sym =-1;      else                              sym = 0;      // check for negative number      if (num<0) sym = sym * (-1);      // push to array      ar.push_back(sym);  }   return(ar);}// convert 3x to integerint  GenMultScript::convert_3x_2int(vector<int> num) {	int i,res;		res=0;	for (i=0;i<num.size();i++) {   	    res = res <<1;		if (num[i]>0) res+=1;		if (num[i]<0) res-=1;	}	return(res);}/////////////////////////////////////////////////////////////////////////////////////////// Calculate Number of cases for selected distance                                     ///////////////////////////////////////////////////////////////////////////////////////////int  GenMultScript::calcSingleDistance(vector<int> ar3x,int dist,int type) {  int i;  int numOfBits;  vector<int> ar3xTemp;  int count;  numOfBits = ar3x.size();  ar3xTemp  = ar3x;  count = 0;  for (i=0;i<(numOfBits-dist-1);i++) {            if ( ( ( ( (ar3xTemp[i]==  1 )&&(ar3xTemp[i+dist+1]==  1 ) ) ||	       ( (ar3xTemp[i]==(-1))&&(ar3xTemp[i+dist+1]==(-1)) ) ) &&	         (type==DIST_PP_MM)) ||	   ( ( ( (ar3xTemp[i]==(-1) )&&(ar3xTemp[i+dist+1]==  1 ) ) ||	       ( (ar3xTemp[i]==  1  )&&(ar3xTemp[i+dist+1]==(-1)) ) ) &&                 (type==DIST_PM_MP)) ) {	////////////////////////////////////////////////////	ar3xTemp[i]=0; // Erase Current	ar3xTemp[i+dist+1]=0;	count++; // Increment counter      }     }  return(count);}////////////////////////////////////////////////////////////////               Calculate distances array                  ////////////////////////////////////////////////////////////////vector<int>  GenMultScript::calcDistance(vector<int> ar3x,int type) {  int dist,numOfBits,count;  vector<int> ar;  numOfBits = ar3x.size();  ar.clear();   /////////////////////////////////////////  // scan distance scan  for (dist=0;dist<numOfBits-1;dist++) {    count = calcSingleDistance(ar3x,dist,type);    ar.push_back(count);    //printf("Dist=%d Count=%d\r\n",dist,count);        }  return(ar);}/////////////////////////////////////////////////////////////            calculate distances array (dual)           /////////////////////////////////////////////////////////////vector<inta_intb_s>  GenMultScript::calcDistance(vector<int> ar3x) {  int dist,numOfBits;  vector<inta_intb_s> ar;  inta_intb_s count;  numOfBits = ar3x.size();  ar.clear();   /////////////////////////////////////////  // scan distance scan  for (dist=0;dist<numOfBits-1;dist++) {    count.a = calcSingleDistance(ar3x,dist,DIST_PP_MM);    count.b = calcSingleDistance(ar3x,dist,DIST_PM_MP);    ar.push_back(count);  }  return(ar);}///////////////////////////////////////////////////////////////////             Calculate Distances Array/Array                 ///////////////////////////////////////////////////////////////////vector<vector<inta_intb_s> >  GenMultScript::calcDistanceArray(vector<vector<int> > ar3x) {  int i;  vector<int> b3x;  vector<vector<inta_intb_s> > ar_dist;  ar_dist.clear();  for (i=0;i<ar3x.size();i++) {    b3x = ar3x[i];    ar_dist.push_back(calcDistance(b3x));    //printf("\r\n");    //printDualArray(ar_dist[i]);  }  return(ar_dist);}///////////////////////////////////////////////////////////////////        Find and Delete single distance from array           ///////////////////////////////////////////////////////////////////vector<int>  GenMultScript::deleteDistanceSingle(vector<int> ar_i,int dist,int type) {  int i,numOfBits;  vector<int> ar;  numOfBits = ar_i.size();  ar  = ar_i;  for (i=0;i<(numOfBits-dist-1);i++) {            if ( ( ( ( (ar[i]==  1 )&&(ar[i+dist+1]==  1 ) ) ||	       ( (ar[i]==(-1))&&(ar[i+dist+1]==(-1)) ) ) &&	         (type==DIST_PP_MM)) ||	   ( ( ( (ar[i]==(-1) )&&(ar[i+dist+1]==  1 ) ) ||	       ( (ar[i]==  1  )&&(ar[i+dist+1]==(-1)) ) ) &&                 (type==DIST_PM_MP)) ) {	////////////////////////////////////////////////////	ar[i]=0; // Erase Current	ar[i+dist+1]=0;      }     }  return(ar);}////////////////////////////////////////////////////////////////////////////                     Delete Distances Array                           ////////////////////////////////////////////////////////////////////////////vector<vector<int> >  GenMultScript::deleteDistance(vector<vector<int> > ar_i,int dist,int type) {  vector<vector<int> > ar;  int i;  ar.clear();  for (i=0;i<(ar_i).size();i++) {    ar.push_back(deleteDistanceSingle(ar_i[i],dist,type));  }  return(ar);}////////////////////////////////////////////////////////////////////////                  Calculate global distance                       ////              (add all single distances together)                 ////////////////////////////////////////////////////////////////////////vector<inta_intb_s>  GenMultScript::calcGlobalDistance(vector<vector<inta_intb_s> > l_dist) {  int i,j;  vector<inta_intb_s> g_dist;  g_dist=l_dist[0];  for (i=1;i<(l_dist).size();i++) {    // Add current to previous    for (j=0;j<(l_dist[i]).size();j++) {      g_dist[j].a+=(l_dist[i])[j].a;      g_dist[j].b+=(l_dist[i])[j].b;    }  }  printf("\r\n");  printDualArray(g_dist);  return(g_dist);}///////////////////////////////////////////////////////////////////////////           Find Maximum Value and their location in array            ///////////////////////////////////////////////////////////////////////////max_s  GenMultScript::findMax(vector<inta_intb_s> ar) {  max_s p;  int x,max;  max=0;  for (x=GMULT_TAB_OFFSET;x<ar.size();x++) {    if (ar[x].a>=max) {      max = ar[x].a;      p.max = max;      p.pos.x=x;      p.pos.y=0;    }    if (ar[x].b>=max) {      max = ar[x].b;      p.max = max;      p.pos.x=x;      p.pos.y=1;    }  }  return(p);}/////////////////////////////////////////////////////               Find Common Terms               /////////////////////////////////////////////////////vector<pos_s>  GenMultScript::getCommonTerms(vector<vector<int> > ar3x) {  vector<vector<inta_intb_s> > l_dist;  vector<inta_intb_s> g_dist;  vector<vector<int> > ar3xTemp;  max_s m;  vector<pos_s> term;    ar3xTemp = ar3x;  term.clear();  do {    l_dist = calcDistanceArray(ar3xTemp);  // Calculate Distances Array    g_dist = calcGlobalDistance(l_dist);   // calculate global distance array    m = findMax(g_dist);                   // look for maximum    if (m.max>GMULT_MIN_OPTIMIZE) {      ar3xTemp = deleteDistance(ar3xTemp,m.pos.x,m.pos.y);      term.push_back(m.pos);    }  } while(m.max>GMULT_MIN_OPTIMIZE);  printf("\r\nTerm Array:\r\n");  printPosArray(term);  return(term);}/////////////////////////////////////////////////////// Get Other feild left after extract common terms ///////////////////////////////////////////////////////vector<vector<int> >  GenMultScript::getOthers(vector<vector<int> > ar3x,vector<pos_s> Term) {  vector<vector<int> > ar3xTemp;  int i;  ar3xTemp = ar3x;   for (i=0;i<Term.size();i++) {    ar3xTemp = deleteDistance(ar3xTemp,(Term[i]).x,(Term[i]).y);  }  printf("\r\nOthers:\r\n");