// verifast_options{disable_overflow_check target:ILP32} extern void abort(void); //@ requires true; //@ ensures true; void reach_error() //@ requires false; //@ ensures true; {} /* * Recursive implementation of prime number test * (Sieve of Eratosthenes) * * Author: Jan Leike * Date: 2013-07-17 * */ extern int __VERIFIER_nondet_int(void); //@ requires true; //@ ensures true; // Multiplies two integers n and m int mult(int n, int m) //@ requires true; //@ ensures ((((2 < result) || (result == 0)) || (m < 2)) || (n < 2)); { if (m < 0) { return mult(n, -m); } if (m == 0) { return 0; } if (m == 1) { return 1; } return n + mult(n, m - 1); } // Is n a multiple of m? int multiple_of(int n, int m) //@ requires true; //@ ensures ((((((m * 2) < (n + 1)) || (n == m)) || (n == 0)) || ((n + m) < 1)) || (m < 1)); { if (m < 0) { return multiple_of(n, -m); } if (n < 0) { return multiple_of(-n, m); // false } if (m == 0) { return 0; // false } if (n == 0) { return 1; // true } return multiple_of(n - m, m); } int is_prime_(int n, int m); int is_prime(int n); // Is n prime? int is_prime(int n) //@ requires true; //@ ensures ((n < 3) || (result == 0)); { return is_prime_(n, n - 1); } int is_prime_(int n, int m) //@ requires true; //@ ensures true; { if (n <= 1) { return 0; // false } if (n == 2) { return 1; // true } if (n > 2) { if (m <= 1) { return 1; // true } else { if (multiple_of(n, m) == 0) { return 0; // false } return is_prime_(n, m - 1); } } } int main() //@ requires module(Primes__verifast_instrumented, true); //@ ensures junk(); { //@ open_module(); int n = __VERIFIER_nondet_int(); if (n < 1 || n > 46340) { // additional branch to avoid undefined behavior // (because of signed integer overflow) return 0; } int result = is_prime(n); int f1 = __VERIFIER_nondet_int(); if (f1 < 1 || f1 > 46340) { // additional branch to avoid undefined behavior // (because of signed integer overflow) return 0; } int f2 = __VERIFIER_nondet_int(); if (f2 < 1 || f2 > 46340) { // additional branch to avoid undefined behavior // (because of signed integer overflow) return 0; } if (result == 1 && mult(f1, f2) == n && f1 > 1 && f2 > 1) { ERROR: {reach_error();abort();} } else { return 0; } return 0; }