// verifast_options{disable_overflow_check target:ILP32}
/* Compute the floor of the square root, 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 int __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(dijkstra_u_unwindbound2__verifast_instrumented, true) &*& (counter == 0);
//@ ensures (counter == 0) &*& junk();
{
    //@ open_module(); 
    unsigned int n, p, q, r, h;

    n = __VERIFIER_nondet_uint();
    assume_abort_if_not(n < 4294967295 / 4);  // Avoid non-terminating loop

    p = 0;
    q = 1;
    r = n;
    h = 0;
while (counter++<2)
//@ invariant integer(&counter, ?veri_inv_counter) &*& ((veri_req_counter == 0) && ((((((p == 0) && (n == r)) && (veri_inv_counter == 1)) && (h == 0)) || (((((p == 0) && (n == r)) && (veri_inv_counter == 0)) && (h == 0)) && (q == 1))) || ((((2 <= veri_inv_counter) && (p == 0)) && (n == r)) && (h == 0))));
    {
        if (!(q <= n))
            break;

        q = 4 * q;
    }
    //q == 4^n

while (counter++<2)
//@ invariant integer(&counter, ?veri_inv_counter) &*& ((((((((p == 0) && (n == r)) && (n <= 0)) && (veri_inv_counter == 1)) && (h == 0)) && (q == 1)) || ((((2 <= veri_inv_counter) && (p == 0)) && (n == r)) && (h == 0))) && (veri_req_counter == 0));
    {
        __VERIFIER_assert(r < 2 * p + q);
        __VERIFIER_assert(p*p + r*q == n*q);
        __VERIFIER_assert(h * h * h - 12 * h * n * q + 16 * n * p * q - h * q * q - 4 * p * q * q + 12 * h * q * r - 16 * p * q * r == 0);
        __VERIFIER_assert(h * h * n - 4 * h * n * p + 4 * (n * n) * q - n * q * q - h * h * r + 4 * h * p * r - 8 * n * q * r + q * q * r + 4 * q * r * r == 0);
        __VERIFIER_assert(h * h * p - 4 * h * n * q + 4 * n * p * q - p * q * q + 4 * h * q * r - 4 * p * q * r == 0);
        __VERIFIER_assert(p * p - n * q + q * r == 0);

        if (!(q != 1))
            break;

        q = q / 4;
        h = p + q;
        p = p / 2;
        if (r >= h) {
            p = p + q;
            r = r - h;
        }
    }
    __VERIFIER_assert(h*h*h - 12*h*n + 16*n*p + 12*h*r - 16*p*r - h - 4*p == 0);
    __VERIFIER_assert(p*p - n + r == 0);
    __VERIFIER_assert(h*h*p - 4*h*n + 4*n*p + 4*h*r - 4*p*r - p == 0);
    return 0;
}