Stack overflow in quickcheck case shrinking #285

/// Greatest common divisor of two integers.
pub fn gcd(a: i64, b: i64) -> i64 {
    assert!(!(a == i64::MIN && b == i64::MIN));
    if a == 0 {
        b.abs()
    } else {
        gcd(b % a, a)
    }
}


/// Returns (gcd(a, b), x, y) such that a*x + b*y = gcd(a, b) (ignoring overflow in the LHS).
pub fn egcd(a: i64, b: i64) -> (i64, i64, i64) {
    assert!(!(a == i64::MIN && b == i64::MIN));
    let mut r = (a, b);
    let mut s = (1, 0);
    let mut t = (0, 1);

    while r.1 != 0 {
        let q = r.0 / r.1;
        r = (r.1, r.0 - q*r.1);
        s = (s.1, s.0 - q*s.1);
        t = (t.1, t.0 - q*t.1);
    }

    if r.0 < 0 {
        (-r.0, -s.0, -t.0)
    } else {
        (r.0, s.0, t.0)
    }
}


#[cfg(test)]
mod tests {
    use super::*;
    use quickcheck::quickcheck;

    quickcheck! {
        fn qc_egcd(a: i64, b: i64) -> bool {
            if a == 0 || b == 0 {
                return true;
            }

            let (g, x, y) = egcd(a, b);
            g == gcd(a, b) && a.wrapping_mul(x).wrapping_add(b.wrapping_mul(y)) == g
        }
    }
}