// verifast_options{disable_overflow_check target:ILP32} 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", "lu.cmp.c", 3, "reach_error"); } void __VERIFIER_assert(int cond) //@ requires (1 <= cond); //@ ensures (1 <= cond); { if (!(cond)) { ERROR: {reach_error();abort();} } return; } /*************************************************************************/ /* */ /* SNU-RT Benchmark Suite for Worst Case Timing Analysis */ /* ===================================================== */ /* Collected and Modified by S.-S. Lim */ /* sslim@archi.snu.ac.kr */ /* Real-Time Research Group */ /* Seoul National University */ /* */ /* */ /* < Features > - restrictions for our experimental environment */ /* */ /* 1. Completely structured. */ /* - There are no unconditional jumps. */ /* - There are no exit from loop bodies. */ /* (There are no 'break' or 'return' in loop bodies) */ /* 2. No 'switch' statements. */ /* 3. No 'do..while' statements. */ /* 4. Expressions are restricted. */ /* - There are no multiple expressions joined by 'or', */ /* 'and' operations. */ /* 5. No library calls. */ /* - All the functions needed are implemented in the */ /* source file. */ /* */ /* */ /*************************************************************************/ /* */ /* FILE: ludcmp.c */ /* SOURCE : Turbo C Programming for Engineering */ /* */ /* DESCRIPTION : */ /* */ /* Simultaneous linear equations by LU decomposition. */ /* The arrays a[][] and b[] are input and the array x[] is output */ /* row vector. */ /* The variable n is the number of equations. */ /* The input arrays are initialized in function main. */ /* */ /* */ /* REMARK : */ /* */ /* EXECUTION TIME : */ /* */ /* */ /*************************************************************************/ /* ** Benchmark Suite for Real-Time Applications, by Sung-Soo Lim ** ** III-4. ludcmp.c : Simultaneous Linear Equations by LU Decomposition ** (from the book C Programming for EEs by Hyun Soon Ahn) */ double a[50][50], b[50], x[50]; int ludcmp(int nmax, int n, double eps);//@ requires true; //@ ensures true; static double fabs(double n)//@ requires true; //@ ensures true; { double f; if (n >= 0) f = n; else f = -n; return f; } int main()//@ requires module(lu_cmp__verifast_instrumented_modified, true); //@ ensures junk(); { int i, j, nmax = 50, n = 5, chkerr; double eps, w; eps = 1.0e-6; for(i = 0; i <= n; i++)//@ invariant ((i <= 49) && (5 == n)); { w = 0.0; for(j = 0; j <= n; j++)//@ invariant ((i <= 5) && (5 == n)); { a[i][j] = (i + 1) + (j + 1); if(i == j) a[i][j] *= 10.0; w += a[i][j]; } __VERIFIER_assert(i < 50); b[i] = w; } chkerr = ludcmp(nmax, n, eps); return 0; } int ludcmp(int nmax, int n, double eps) { int i, j, k; double w, y[100]; if(n > 99 || eps <= 0.0) return(999); for(i = 0; i < n; i++)//@ invariant true; { if(fabs(a[i][i]) <= eps) return(1); for(j = i+1; j <= n; j++)//@ invariant true; { w = a[j][i]; if(i != 0) for(k = 0; k < i; k++)//@ invariant true; w -= a[j][k] * a[k][i]; a[j][i] = w / a[i][i]; } for(j = i+1; j <= n; j++)//@ invariant true; { w = a[i+1][j]; for(k = 0; k <= i; k++)//@ invariant true; w -= a[i+1][k] * a[k][j]; a[i+1][j] = w; } } y[0] = b[0]; for(i = 1; i <= n; i++)//@ invariant true; { w = b[i]; for(j = 0; j < i; j++)//@ invariant true; w -= a[i][j] * y[j]; y[i] = w; } x[n] = y[n] / a[n][n]; for(i = n-1; i >= 0; i--)//@ invariant true; { w = y[i]; for(j = i+1; j <= n; j++)//@ invariant true; w -= a[i][j] * x[j]; x[i] = w / a[i][i] ; } return(0); }