// ************************************************************************** //
//                                                                            //
//    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 comparison checking for radix-B numbers.   //
// The depth of the algorithm below is O(N), which can be obviously improved  //
// to O(log(N)) using a parallel prefix computation. Alternatively, we refer  //
// to NatSubCLA which has depth O(log(N)) and can also compare numbers.       //
// ************************************************************************** //

macro B = 4;      // base of the radix numbers
macro N = 4;      // number of digits used
macro natval(x,m) = sum(i=0..m-1) (x[i] * exp(B,i));


module NatLes([N]nat{B} ?x,?y,bool les,eqq) {
    event [N+1]bool ls,eq;
    
    ls[N] = false;    // ls[i] := x[N-1..i] < y[N-1..i]
    eq[N] = true;     // eq[i] := x[N-1..i] = y[N-1..i]
    for(i=0..N-1) {
        ls[i] = ls[i+1] | eq[i+1] & x[i]<y[i];
        eq[i] = eq[i+1] & x[i]==y[i];           
    }
    les = ls[0];
    eqq = eq[0];
    s1 : assert(les <-> natval(x,N) <  natval(y,N));
    s2 : assert(eqq <-> natval(x,N) == natval(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;
    }
}