// ************************************************************************** //
//                                                                            //
//    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 //
// due to Brauer that is better than the addition chain obtained by the       //
// binary representation. Given numbers x and k, the Brauer sequence B(k,x) is//
// defined as B(k,x) = B(k,q) * [2q,4q,8q,…,exp(2,k)q,x] if x>=exp(2,k) with  //
// q=n/exp(2,k) and B(k,x) = [1,2,3,…,exp(2,k)-1] if x<exp(2,k). The length is//
// best for k around log(log(x)) - 2log(log(log(x))).                         //
// ************************************************************************** //

macro K = 16;
macro ceillog(x) = (exp(2,log(x))==x ? log(x) : log(x)-1);

module BrauerChain(nat{exp(2,K)} ?x,nat{K} ?k,[2*K]nat c,event !rdy) {
    nat{exp(2,K)} n,q;
    nat{2*K} i,j;

    j = 0;
    n = x;

    while(n>=exp(2,k)) {
        // determine subsequence [2q,4q,8q,…,exp(2,k)q,n] in c[j..j+k] in 
        // reversed order; we also write c[j+k+1] = q, which may be overwritten
        q = n/exp(2,k);
        next(i) = j+k;
        next(c[j]) = n;
        next(c[j+k+1]) = q;
        pause;
        while(i>j) {
            next(c[i]) = 2*c[i+1];
            next(i) = i-1;
            pause;
        }
        next(j) = j+k+1;
        next(n) = q;
        pause;
    }
    // add the final subsequence 1,2,3,…,exp(2,k)-1 in c[j..exp(2,k)]
    i = exp(2,k)-1;
    while(i>0) {
        next(c[j]) = i;
        next(j) = j+1;
        next(i) = i-1;
        pause;
    }
    emit(rdy);
}
drivenby {
    x = 31415;
    k = 3;
    await(rdy);
}
drivenby {
    x = 32767;
    k = 3;
    await(rdy);
}