// ************************************************************************** //
//                                                                            //
//    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 procedure for converting B-complement    //
// numbers to equivalent signed digit numbers. It is essentially the addition //
// of the given number with number zero.                                      //
// It works for bases B,D with floor(B/2)+1 <= D < B, thus it cannot be used  //
// for binary signed digit numbers without further care. However, we can use  //
// it for B=2^k with D=2^k-1 and convert then the digits separately.          //
// ************************************************************************** //

macro D = 3;     // digit set is -D,...,-1,0,1,...,D
macro B = 5;     // base of the radix numbers
macro N = 4;     // number of digits

// macros for signed digit and B-complement numbers
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));
macro sgnval(x,k) = sum(i=0..k-1) (x[i] * exp(B,i));


module Int2Sgn([N]nat{B} ?x,[N+1]int{D+1} y) {
    [N+1]int{2} t; // transfer digits
    
    // compute sum and transfer digits in parallel
    t[0] = 0;
    for(i=0..N-1)
        let(xi = dval(x,i,N)) {
        t[i+1] = (xi>=D ? +1 : (xi<=-D ? -1 : 0));
        y[i] = xi + t[i] - t[i+1] * B;
    }
    y[N] = t[N];
    // specification
    assert(sgnval(y,N+1) == intval(x,N));
}