// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// Exponentiation of a number can be reduced to the multiplication of smaller //
// numbers by the equation exp(a,b+c) = exp(a,b) * exp(a,c). To make use of as//
// few multiplications as possible, addition chains of minimal length have to //
// be computed: Formally, an addition chain is a sequence of numbers c[i] so  //
// that c[0] = 1 and c[i+1] = c[j]+c[k] for j,k<=i. Often, one requires that  //
// even c[i+1] = c[j]+c[i] for j<=i holds (as below). It is obvious that the  //
// length of the addition chain ending in x is the number of multiplications  //
// required to compute exp(a,x). The module below computes the addition chain //
// that corresponds to the simple exponentiation algorithm that is based on   //
// the binary representation of x. Thus, its length is O(log(x)).             // 
// ************************************************************************** //

macro K = 16;


module ExpChain(nat{exp(2,K)} ?x,[2*K]nat c,event !rdy) {
    bv{K} b;
    nat{2*K} j;

    // compute binary representation of x
    b = nat2bv(x,K);

    // compute exponentials c[i] = exp(2,i) which are additions of the
    // previous number with itself
    c[0] = 1;
    j = 0;
    while(c[j]+c[j]<x) {
        next(c[j+1]) = c[j] + c[j];
        next(j) = j+1;
        pause;
    }
    // finally, determine additions to compute number x based on its 
    // binary representation
    for(i=0..K-1)
        if(b{i}) {
            next(c[j+1]) = c[j] + c[i];
            next(j) = j+1;
            pause;
        }

    emit(rdy);
}
drivenby {
    x = 31415;
    await(rdy);
}
drivenby {
    x = 32767;
    await(rdy);
}