// ************************************************************************** //
//                                                                            //
//    eses                   eses                                             //
//   eses                     eses                                            //
//  eses    eseses  esesese    eses   Embedded Systems Group                  //
//  ese    ese  ese ese         ese                                           //
//  ese    eseseses eseseses    ese   Department of Computer Science          //
//  eses   eses          ese   eses                                           //
//   eses   eseses  eseseses  eses    University of Kaiserslautern            //
//    eses                   eses                                             //
//                                                                            //
// ************************************************************************** //
// The following module implements a multiplication of B-complement numbers.  //
// The computation is done by summing up the usual partial products by the use//

// of carry-ripple adders both for the intermediate steps and the final step: //
//                                                                            //
//                               pp[0][1] pp[0][0] p[0]                       //
//                      pp[1][1] pp[1][0]  p[1]                               //
//             pp[2][1] pp[2][0]  p[2]                                        //
//     p[5]     p[4]     p[3]                                                 //
//    ------------------------------------------------------                  //
//     p[5]     p[4]     p[3]     p[2]     p[1]     p[0]                      //
//                                                                            //
// where B*pp[i][N-1..0]+p[i] = y[N-1..0] * x[i] + pp[i-1][N-1..0] for i>0    //
// and   B*pp[i][N-1..0]+p[i] = y[N-1..0] * x[i] for i==0.                    //
//                                                                            //
// The depth of the circuit is seen by observing that the evaluation can      //
// proceed diagonally through the array. Thus, the depth of the circuit       //
// is O(M+N) and therefore not optimal.                                       //
// ** Note: We are only interested in even values of B **                     // 
// ************************************************************************** //

macro B = 4;    // base of the radix numbers
macro M = 4;    // number of digits used for x
macro N = 3;    // number of digits used for y
macro alpha(x) = (x<(B/2) ? +x : +x-B);
macro gamma(y) = (y<0 ? y+B : y);
macro dval(x,i,k) = (i==k-1 ? alpha(x[i]) : +x[i]);
macro intval(x,k) = sum(i=0..k-1) (dval(x,i,k) * exp(B,i));

module IntMulCRACRA([M]nat{B} ?x,[N]nat{B} ?y,[M+N]nat{B} p) {
    event [M][N+1]nat{B} pp;  // digits of partial products
    event [M][N]int{B} cp;    // carries for summation
    for(i=0..M-1) {
        // compute pp[i][N..0] = y[N-1..0] * x[i] + pp[i-1][N..1]
        for(j=0..N-1)
            let(xin = (i==M-1 ? alpha(x[i]) : +x[i])) 
            let(yin = (j==N-1 ? alpha(y[j]) : +y[j])) 
            let(pin = (i==0 ? 0 : (j==N-1 ? alpha(pp[i-1][j+1]) : +pp[i-1][j+1])))
            let(cin = (j==0 ? 0 : cp[i][j-1]))
            let(sm = xin * yin + pin + cin) { // has type int{B*B}
            cp[i][j] = sm / B;
            pp[i][j] = sm % B;
        }
        pp[i][N] = gamma(cp[i][N-1]);
    }
    for(k=0..M-1) p[k] = pp[k][0];
    for(k=0..N-1) p[k+M] = pp[M-1][k+1];
    assert(intval(p,M+N) == intval(x,M) * intval(y,N));
}
drivenby example1 {
    x = [0,0,0,3];
    y = [0,0,3];
}
drivenby example2 {
    x = [3,3,3,0];
    y = [0,0,3];
}
drivenby example3 {
    x = [0,0,0,3];
    y = [3,3,0];
}
drivenby example4 {
    x = [3,3,3,0];
    y = [3,3,0];
}
drivenby example5 {
    x = [0,0,0,2];
    y = [0,0,2];
}