// 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; }