// ************************************************************************** //
//                                                                            //
//    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 binary Euclid algorithm is a refinement of Euclid's algorithm that is  //
// based on the binary representation of the given numbers. This is due to the//
// following rules:                                                           //
//      GCD(2*x,2*y)   = 2*GCD(x,y)                                           //
//      GCD(2*x,2*y+1) = GCD(x,2*y+1)                                         //
//      GCD(2*x+1,2*y) = GCD(2*x+1,y)                                         //
//      otherwise GCD(x,y) = (y<=x ? GCD(x%y,y) : GCD(x,y%x)                  //
// ************************************************************************** //

macro N = 1000;
macro isEven(x) = (x % 2==0);

module EuclidModBin(nat{N} ?a,?b,x,event !rdy) {
    nat{N} y,z;
    x = a;
    y = b;
    z = 0;
    do {
        case
        (isEven(x) & isEven(y)) do {
            next(x) = x/2;
            next(y) = y/2;
            next(z) = z+1;
            }
        (isEven(x) & !isEven(y)) do
            next(x) = x/2;
        (!isEven(x) & isEven(y)) do
            next(y) = y/2;
        default
            if(x<=y)
                next(y) = y%x;
            else
                next(x) = x%y;
        pause;
    } while(x!=0 & y!=0);
    if(x==0) next(x) = y;
    pause;
    // finally multiply x by exp(2,z)
    while(z != 0) {
        next(z) = z - 1;
        next(x) = x + x;
        pause;
    }
    pause;
    emit(rdy);
}
drivenby {
    a = 126;
    b = 56;
    await(rdy);
}