// verifast_options{disable_overflow_check target:ILP32}
/* Algorithm for computing simultaneously the GCD and the LCM, by Dijkstra */

extern void abort(void);
//@ requires integer(&counter, ?veri_req_counter) &*& true;
//@ ensures integer(&counter, ?veri_ens_counter) &*& true;
void reach_error()
//@ requires false;
//@ ensures true;
{}extern unsigned __VERIFIER_nondet_uint(void);
//@ requires integer(&counter, ?veri_req_counter) &*& true;
//@ ensures integer(&counter, ?veri_ens_counter) &*& true;
void assume_abort_if_not(int cond) 
//@ requires integer(&counter, ?veri_req_counter) &*& (veri_req_counter == 0);
//@ ensures integer(&counter, ?veri_ens_counter) &*& ((veri_ens_counter == veri_req_counter) && (veri_ens_counter == 0));
{  if(!cond) {abort();}
}
void __VERIFIER_assert(int cond) 
//@ requires integer(&counter, ?veri_req_counter) &*& (1 <= cond);
//@ ensures integer(&counter, ?veri_ens_counter) &*& ((veri_ens_counter == veri_req_counter) && (1 <= cond));
{    if (!(cond)) {
    ERROR:
        {reach_error();}
    }
    return;
}

int counter = 0;
int main() 
//@ requires module(lcm2_unwindbound20__verifast_instrumented, true) &*& (counter == 0);
//@ ensures (counter == 0) &*& junk();
{
    //@ open_module(); 
    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 (counter++<20)
//@ invariant integer(&counter, ?veri_inv_counter) &*& ((((( b * a) % 2147483648) * 2) == (( ( y * v) + ( x * u)) % 4294967296)) && (veri_req_counter == 0));
    {
        __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;
}