package gcd

// GCD binary algorithm, derived from
// https://en.wikipedia.org/wiki/Binary_GCD_algorithm#Iterative_version_in_C
func GCD(u, v uint64) uint64 {
	var shift uint

	/* GCD(0,v) == v; GCD(u,0) == u, GCD(0,0) == 0 */
	if u == 0 {
		return v
	}
	if v == 0 {
		return u
	}

	/* Let shift := lg K, where K is the greatest power of 2
	   dividing both u and v. */
	for shift = 0; ((u | v) & 1) == 0; shift++ {
		u >>= 1
		v >>= 1
	}

	// While u is even, continue dividing by 2 (right-shift) until it becomes odd
	for (u & 1) == 0 {
		u >>= 1
	}

	/* From here on, u is always odd. */
	for ok := true; ok; ok = (v != 0) {
		/* remove all factors of 2 in v -- they are not common */
		/*   note: v is not zero, so while will terminate */
		for (v & 1) == 0 /* Loop X */ {
			v >>= 1
		}

		/* Now u and v are both odd. Swap if necessary so u <= v,
		   then set v = v - u (which is even). For bignums, the
		   swapping is just pointer movement, and the subtraction
		   can be done in-place. */
		if u > v {
			// Swap u and v.
			//  unsigned int t = v; v = u; u = t;}
			v, u = u, v
		}
		v = v - u // Here v >= u.
	}

	/* restore common factors of 2 */
	return u << shift
}