// verifast_options{disable_overflow_check target:ILP32} /* Cohen's integer division returns x % y http://www.cs.upc.edu/~erodri/webpage/polynomial_invariants/cohendiv.htm */ extern void abort(void); //@ requires true; //@ ensures true; void reach_error() //@ requires false; //@ ensures true; {}extern int __VERIFIER_nondet_int(void); //@ requires true; //@ ensures true; void assume_abort_if_not(int cond) //@ requires true; //@ ensures (cond != 0); { if(!cond) {abort();} } void __VERIFIER_assert(int cond) //@ requires (cond != 0); //@ ensures (cond != 0); { if (!(cond)) { ERROR: {reach_error();} } return; } int main() //@ requires module(cohendiv_ll_valuebound1__verifast_instrumented, true); //@ ensures junk(); { //@ open_module(); int x, y; long long q, r, a, b; x = __VERIFIER_nondet_int(); assume_abort_if_not(x>=0 && x<=1); y = __VERIFIER_nondet_int(); assume_abort_if_not(y>=0 && y<=1); assume_abort_if_not(y >= 1); q = 0; r = x; a = 0; b = 0; while (1) //@ invariant (((((q * y) + r) == x) && ((((q * y) + r) + (a * y)) == (b + x))) && (1 <= y)); { __VERIFIER_assert(b == y*a); __VERIFIER_assert(x == q*y + r); if (!(r >= y)) break; a = 1; b = y; while (1) //@ invariant ((((((q * y) + r) == x) && (1 <= r)) && ((((q * y) + r) + (a * y)) == (b + x))) && (1 <= y)); { __VERIFIER_assert(b == y*a); __VERIFIER_assert(x == q*y + r); __VERIFIER_assert(r >= 0); if (!(r >= 2 * b)) break; __VERIFIER_assert(r >= 2 * y * a); a = 2 * a; b = 2 * b; } r = r - b; q = q + a; } __VERIFIER_assert(x == q*y + r); return 0; }