// ************************************************************************** //
//                                                                            //
//    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 module below decodes a given residue number x_enc[i] with respect to   //
// the moduli prime[i] that must be relatively prime numbers. The decoding    //
// is mainly based on the computation of multiplicative inverse elements for  //
// the prime[i] that are stored in the local array inverse[i]. As a result,   //
// the algorithm computes a number x_dec such that the following Chinese      //
// Remaindering puzzle is solved where N = numPrim:                           //
//                                                                            //
//      x_dec % prime[0] = x_enc[0]                                           //
//        :        :     =  :                                                 //
//      x_dec % prime[N] = x_enc[N]                                           //
//                                                                            //
// ************************************************************************** //

macro numPrim = 4;
macro Product(p,i) = (i==0 ? p[i] : p[i]*Product(p,i-1));


module DecodeRNS([4]nat ?prime,?x_enc,int x_dec,event rdy) {
    nat ProdPrimes;
    [4]int inverse;

    // compute the product of the given relatively prime numbers
    ProdPrimes = Product(prime,numPrim-1);

    // Compute multiplicative inverse elements inverse[i] for ProdPrimes/prime[i]
    // modulo prime[i], i.e. numbers inverse[i] such that the following holds:
    //      (inverse[i] * (ProdPrimes/prime[i])) % prime[i] = 1
    // The computation of the multiplicative inverse elements is done by the 
    // extended Euclidean algorithm that makes use of B├ęzout's Lemma.
    
    for(i=0..numPrim-1) do || {
        int m,n,q,s,t,u,v;
        m = ProdPrimes/prime[i];
        n = prime[i];
        u = 1;
        v = 0;
        s = 0;
        t = 1;
        while(n!=0) {
            q = m / n;
            next(m) = n;
            next(n) = m - q * n;
            next(u) = s;
            next(v) = t;
            next(s) = u - q * s;
            next(t) = v - q * t;
            pause;
        }
        inverse[i] = u;
    }
    
    // now we can easily decode any given number x given in RNS representation
    x_dec = (sum(i=0..numPrim-1) (x_enc[i] * inverse[i] * ProdPrimes/prime[i])) % ProdPrimes;
    emit(rdy);
}
drivenby {
    prime[0] = 8;   x_enc[0] = 5;
    prime[1] = 7;   x_enc[1] = 3;
    prime[2] = 5;   x_enc[2] = 4;
    prime[3] = 3;   x_enc[3] = 2;
    await(rdy);
}
drivenby {
    prime[0] = 25;   x_enc[0] = 20;
    prime[1] = 27;   x_enc[1] = 15;
    prime[2] = 23;   x_enc[2] = 16;
    prime[3] = 22;   x_enc[3] = 21;
    await(rdy);
}