// ************************************************************************** //
//                                                                            //
//    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 of signed digit numbers.        //
// Since 0 has a unique representation as signed digit number, we check that  //
// difference of the two given numbers is zero. It works for bases A,B with   //
// floor(B/2)+1 <= D < B, thus it cannot be used for binary signed digits.    //
// Moreover, we can also check whether one number is less than another one by //
// subtraction of the former by the latter. It remains to check the sign of   //
// the result which is determined by the leftmost non-zero digit.             //
// To see that comparison can be done in time O(1) see module FirstOne that   //
// determines the first element in a sequence with a certain property in O(1).//
// ************************************************************************** //

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 used for the addition

// macro to evaluate a signed digit number
macro sgnval(x,k) = sum(i=0..k-1) (x[i] * exp(B,i));
macro sgn(x) = (x>0 ? +1 : (x<0 ? -1 : 0));
macro sign(x,k) = (k==0 ? sgn(x[0]) : (x[k]!=0 ? sgn(x[k]) : sign(x,k-1)));


module SgnCmp([N]int{D+1} ?x,?y,bool eqq,les) {
    [N+1]int{2} t;      // transfer digits
    [N+1]int{D+1} s;    // sum digits of a-b

    // compute sum and transfer digits in parallel
    t[0] = 0;
    for(i=0..N-1)
        let(ds = x[i]-y[i]) {
        t[i+1] = (ds>=D?1:(ds<=-D?-1:0));
        s[i] = ds + t[i] - t[i+1] * B;
        }
    s[N] = t[N];
    
    eqq = forall(i=0..N) (s[i]==0);
    les = (sign(s,N)==-1);

    // assertion
    assert(eqq <-> (sgnval(x,N) == sgnval(y,N)));
    assert(les <-> (sgnval(x,N) < sgnval(y,N)));
}