commonlib: Change GCD function to always use 64 bits

It seems that we have some applications where we need to calculate a GCD
in 64 bits. Now, we could instantiate the algorithm multiple times for
different bit width combinations to be able to use the most efficient
one for each problem... but considering that the function usually only
gets called once per callsite per stage, and that software emulation of
64-bit division on 32-bit systems doesn't take *that* long either, we
would probably usually be paying more time loading the second instance
of the function than we save with faster divisions. So let's just make
things easy and always do it in 64-bit and then nobody has to spend time
thinking on which version to call.

Change-Id: I028361444c4048a0d76ba4f80c7334a9d9983c87
Signed-off-by: Julius Werner <jwerner@chromium.org>
Reviewed-on: https://review.coreboot.org/c/coreboot/+/80319
Reviewed-by: Nico Huber <nico.h@gmx.de>
Tested-by: build bot (Jenkins) <no-reply@coreboot.org>
Reviewed-by: Yidi Lin <yidilin@google.com>

10 files changed, 28 insertions, 23 deletions

diff --git a/payloads/libpayload/libc/getopt_long.c b/payloads/libpayload/libc/getopt_long.c
index 822ce96904cf..c0303cfea3f9 100644
--- a/payloads/libpayload/libc/getopt_long.c
+++ b/payloads/libpayload/libc/getopt_long.c
@@ -122,7 +122,7 @@ permute_args(int panonopt_start, int panonopt_end, int opt_end,
 	 */
 	nnonopts = panonopt_end - panonopt_start;
 	nopts = opt_end - panonopt_end;
-	ncycle = gcd32(nnonopts, nopts);
+	ncycle = gcd(nnonopts, nopts);
 	cyclelen = (opt_end - panonopt_start) / ncycle;
 
 	for (i = 0; i < ncycle; i++) {
diff --git a/payloads/libpayload/libc/time.c b/payloads/libpayload/libc/time.c
index c38dbfdde8a5..28f2b3e2a959 100644
--- a/payloads/libpayload/libc/time.c
+++ b/payloads/libpayload/libc/time.c
@@ -182,7 +182,7 @@ u64 timer_us(u64 base)
 			       "must be at least 1MHz.\n", hz);
 			halt();
 		}
-		div = gcd32(hz, mult);
+		div = gcd(hz, mult);
 		hz /= div;
 		mult /= div;
 	}
diff --git a/src/arch/arm64/arch_timer.c b/src/arch/arm64/arch_timer.c
index 3eb5656a156e..742b82cad704 100644
--- a/src/arch/arm64/arch_timer.c
+++ b/src/arch/arm64/arch_timer.c
@@ -19,7 +19,7 @@ void timer_monotonic_get(struct mono_time *mt)
 	if (tfreq == 0) {
 		tfreq = raw_read_cntfrq_el0();
 		mult = USECS_PER_SEC;
-		div = gcd32(tfreq, mult);
+		div = gcd(tfreq, mult);
 		tfreq /= div;
 		mult /= div;
 	}
diff --git a/src/commonlib/bsd/gcd.c b/src/commonlib/bsd/gcd.c
index 92b601e8d01d..fbc8103a32ee 100644
--- a/src/commonlib/bsd/gcd.c
+++ b/src/commonlib/bsd/gcd.c
@@ -4,9 +4,9 @@
 #include <commonlib/bsd/helpers.h>
 #include <stdint.h>
 
-uint32_t gcd32(uint32_t a, uint32_t b)
+uint64_t gcd(uint64_t a, uint64_t b)
 {
-	uint32_t c;
+	uint64_t c;
 
 	if (a == 0 || b == 0)
 		return MAX(a, b);
diff --git a/src/commonlib/bsd/include/commonlib/bsd/gcd.h b/src/commonlib/bsd/include/commonlib/bsd/gcd.h
index 20949ded09df..de02eb56a098 100644
--- a/src/commonlib/bsd/include/commonlib/bsd/gcd.h
+++ b/src/commonlib/bsd/include/commonlib/bsd/gcd.h
@@ -5,6 +5,6 @@
 
 #include <stdint.h>
 
-uint32_t gcd32(uint32_t a, uint32_t b);
+uint64_t gcd(uint64_t a, uint64_t b);
 
 #endif /* _COMMONLIB_BSD_GCD_H_ */
diff --git a/src/drivers/analogix/anx7625/anx7625.c b/src/drivers/analogix/anx7625/anx7625.c
index 8726ac025482..4792d07296d9 100644
--- a/src/drivers/analogix/anx7625/anx7625.c
+++ b/src/drivers/analogix/anx7625/anx7625.c
@@ -160,7 +160,7 @@ static void anx7625_reduction_of_a_fraction(u32 *_a, u32 *_b)
 	u32 a = *_a, b = *_b, old_a, old_b;
 	u32 denom = 1;
 
-	gcd_num = gcd32(a, b);
+	gcd_num = gcd(a, b);
 	a /= gcd_num;
 	b /= gcd_num;
 
diff --git a/src/northbridge/intel/ironlake/quickpath.c b/src/northbridge/intel/ironlake/quickpath.c
index eb79347875c3..aac852ab11d3 100644
--- a/src/northbridge/intel/ironlake/quickpath.c
+++ b/src/northbridge/intel/ironlake/quickpath.c
@@ -19,7 +19,7 @@ static inline int div_roundup(int a, int b)
 
 static u32 lcm(u32 a, u32 b)
 {
-	return (a * b) / gcd32(a, b);
+	return (a * b) / gcd(a, b);
 }
 
 struct stru1 {
@@ -49,7 +49,7 @@ compute_frequence_ratios(struct raminfo *info, u16 freq1, u16 freq2,
 	int freq_max_reduced;
 	int freq3, freq4;
 
-	g = gcd32(freq1, freq2);
+	g = gcd(freq1, freq2);
 	freq1_reduced = freq1 / g;
 	freq2_reduced = freq2 / g;
 	freq_min_reduced = MIN(freq1_reduced, freq2_reduced);
diff --git a/src/soc/rockchip/rk3288/clock.c b/src/soc/rockchip/rk3288/clock.c
index d52fa2a85855..5b1350a4f6d9 100644
--- a/src/soc/rockchip/rk3288/clock.c
+++ b/src/soc/rockchip/rk3288/clock.c
@@ -453,7 +453,7 @@ void rkclk_configure_i2s(unsigned int hz)
 			      1 << 15 | 0 << 12 | 1 << 8 | 0 << 0));
 
 	/* set frac divider */
-	v = gcd32(GPLL_HZ, hz);
+	v = gcd(GPLL_HZ, hz);
 	n = (GPLL_HZ / v) & (0xffff);
 	d = (hz / v) & (0xffff);
 	assert(hz == GPLL_HZ / n * d);
diff --git a/src/soc/rockchip/rk3399/clock.c b/src/soc/rockchip/rk3399/clock.c
index fbff5a7cfaf3..115d289bcbbc 100644
--- a/src/soc/rockchip/rk3399/clock.c
+++ b/src/soc/rockchip/rk3399/clock.c
@@ -796,7 +796,7 @@ void rkclk_configure_i2s(unsigned int hz)
 		RK_CLRBITS(1 << 12 | 1 << 5 | 1 << 4 | 1 << 3));
 
 	/* set frac divider */
-	v = gcd32(CPLL_HZ, hz);
+	v = gcd(CPLL_HZ, hz);
 	n = (CPLL_HZ / v) & (0xffff);
 	d = (hz / v) & (0xffff);
 	assert(hz == (u64)CPLL_HZ * d / n);
diff --git a/tests/commonlib/bsd/gcd-test.c b/tests/commonlib/bsd/gcd-test.c
index 13fad86ec405..852a3fd93d8f 100644
--- a/tests/commonlib/bsd/gcd-test.c
+++ b/tests/commonlib/bsd/gcd-test.c
@@ -3,24 +3,29 @@
 #include <commonlib/bsd/gcd.h>
 #include <tests/test.h>
 
-static void test_gcd32(void **state)
+static void test_gcd(void **state)
 {
-	assert_int_equal(gcd32(17, 11), 1);
-	assert_int_equal(gcd32(64, 36), 4);
-	assert_int_equal(gcd32(90, 123), 3);
-	assert_int_equal(gcd32(65536, 339584), 128);
-	assert_int_equal(gcd32(1, 1), 1);
-	assert_int_equal(gcd32(1, 123), 1);
-	assert_int_equal(gcd32(123, 1), 1);
-	assert_int_equal(gcd32(1, UINT32_MAX), 1);
-	assert_int_equal(gcd32(UINT32_MAX, 1), 1);
-	assert_int_equal(gcd32(UINT32_MAX, UINT32_MAX), UINT32_MAX);
+	assert_int_equal(gcd(17, 11), 1);
+	assert_int_equal(gcd(64, 36), 4);
+	assert_int_equal(gcd(90, 123), 3);
+	assert_int_equal(gcd(65536, 339584), 128);
+	assert_int_equal(gcd(1, 1), 1);
+	assert_int_equal(gcd(1, 123), 1);
+	assert_int_equal(gcd(123, 1), 1);
+	assert_int_equal(gcd(1, UINT32_MAX), 1);
+	assert_int_equal(gcd(UINT32_MAX, 1), 1);
+	assert_int_equal(gcd(UINT32_MAX, UINT32_MAX), UINT32_MAX);
+	assert_int_equal(gcd(1, UINT64_MAX), 1);
+	assert_int_equal(gcd(UINT64_MAX, 1), 1);
+	assert_int_equal(gcd(UINT64_MAX, UINT64_MAX), UINT64_MAX);
+	assert_int_equal(gcd((uint64_t)UINT32_MAX + 1, UINT64_MAX / 2 + 1),
+			 (uint64_t)UINT32_MAX + 1);
 }
 
 int main(void)
 {
 	const struct CMUnitTest tests[] = {
-		cmocka_unit_test(test_gcd32),
+		cmocka_unit_test(test_gcd),
 	};
 
 	return cb_run_group_tests(tests, NULL, NULL);