// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// This module implements carry-ripple addition of B-complement numbers.      //
// Carry-ripple addition has depth O(N) and is therefore not optimal.         //
// ** Note: We are only interested in even values of B **                     // 
// ************************************************************************** //

macro B = 4;
macro N = 4;

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 natval(x,m) = sum(i=0..m-1) (x[i] * exp(B,i));
macro intval(x,k) = sum(i=0..k-1) (dval(x,i,k) * exp(B,i));

module IntAddCRA([N]nat{B} ?x,?y,[N+1]nat{B} s) {
    [N+1]nat{2} c;  // carry digits
    c[0] = 0;
    for(i=0..N-2) {
        nat{2*B} sm;
        sm = x[i] + y[i] + c[i];
        c[i+1] = sm / B;
        s[i] = sm % B;
    }
    {// most significant digits require alpha/gamma applications
    int{B} sm;
    sm = alpha(x[N-1]) + alpha(y[N-1]) + c[N-1];
    s[N] = gamma(sm / B);
    s[N-1] = sm % B;
    }
    assert(intval(s,N+1) == intval(x,N) + intval(y,N));
}
drivenby Test01 {
    for(i=0..N-1) {
        x[i] = i % B;
        y[i] = (N+i) % B;
    }
}
drivenby Test02 {
    for(i=0..N-1) {
        x[i] = (2*i+1) % B;
        y[i] = (N+2*i) % B;
    }
}