// verifast_options{disable_overflow_check target:ILP32}

/* Algorithm for computing simultaneously the GCD and the LCM, by Dijkstra */

extern void abort(void);//@ requires true; 
//@ ensures true;

extern void __assert_fail(const char *, const char *, unsigned int, const char *) __attribute__ ((__nothrow__ , __leaf__)) __attribute__ ((__noreturn__));
void reach_error() //@ requires false; 
//@ ensures true;
{ __assert_fail("0", "lcm2.c", 5, "reach_error"); }
extern unsigned __VERIFIER_nondet_uint(void);//@ requires true; 
//@ ensures true;

extern void abort(void);
void assume_abort_if_not(int cond) //@ requires true; 
//@ ensures true;
{
  if(!cond) {abort();}
}
void __VERIFIER_assert(int cond) //@ requires (1 <= cond); 
//@ ensures (1 <= cond);
{
    if (!(cond)) {
    ERROR:
        {reach_error();}
    }
    return;
}

int main() //@ requires module(lcm2__verifast_instrumented_modified, true); 
//@ ensures junk();
{
    unsigned a, b;
    unsigned x, y, u, v;
    a = __VERIFIER_nondet_uint();
    b = __VERIFIER_nondet_uint();
    assume_abort_if_not(a >= 1); //inf loop if remove
    assume_abort_if_not(b >= 1);

    assume_abort_if_not(a <= 65535);
    assume_abort_if_not(b <= 65535);

    x = a;
    y = b;
    u = b;
    v = a;

    while (1)//@ invariant ((((b * a) % 2147483648) * 2) == (((y * v) + (x * u)) % 4294967296));
 {
        __VERIFIER_assert(x*u + y*v == 2*a*b);

        if (!(x != y))
            break;

        if (x > y) {
            x = x - y;
            v = v + u;
        } else {
            y = y - x;
            u = u + v;
        }
    }

    __VERIFIER_assert(x*u + y*v == 2*a*b);
    // x == gcd(a,b)
    //(u + v)/2==lcm(a,b)

    return 0;
}