// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// A simple implementation of Euclid's algorithm for computing the greatest   //
// common divisor of two given natural numbers. The core of the algorithm is  //
// the fact that the common divisors of a and b are the common divisors of b  //
// and (a%b):                                                                 //
//  * Divisors(a,b) <= Divisors(b,a%b) holds, since x*t=a, y*t=b, and a=q*b+r //
//    imply x*t = q*y*t+r, i.e., r = (x-q*y) * t so that each common divisor t//
//    of a and b also divides r = a%b.                                        //
//  * Divisors(b,a%b) <= Divisors(a,b) holds, since x*t=b, y*t=r, and a=q*b+r //
//    imply a = q*x*t+y*t = (q*x+y)*t, so that each common divisor t          //
//    of b and r=a%b also divides a.                                          //
// According to Lamé (1844), the algorithm never takes more steps than the    //
// number of digits of the smaller number (a or b) in base 10. Worst case     //
// examples are moreover the Fibonacci numbers, i.e. GCD(Fib(i+1),Fib(i)).    //
// ************************************************************************** //

macro N = 1000;
  
module EuclidMod(nat{N} ?a,?b,x,event !rdy) {
    nat{N} y;
    x = a;
    y = b;
    do {
        if(x>=y)
            next(x) = x%y;
        else
            next(y) = y%x;
        pause;
    } while(x!=0 & y!=0);
    if(x==0) next(x) = y;
    pause;
    emit(rdy);
}
drivenby {
    a = 126;
    b = 56;
    await(rdy);
}