Felix Held has submitted this change. ( https://review.coreboot.org/c/coreboot/+/80319?usp=email )
Change subject: commonlib: Change GCD function to always use 64 bits ......................................................................
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 --- M payloads/libpayload/libc/getopt_long.c M payloads/libpayload/libc/time.c M src/arch/arm64/arch_timer.c M src/commonlib/bsd/gcd.c M src/commonlib/bsd/include/commonlib/bsd/gcd.h M src/drivers/analogix/anx7625/anx7625.c M src/northbridge/intel/ironlake/quickpath.c M src/soc/rockchip/rk3288/clock.c M src/soc/rockchip/rk3399/clock.c M tests/commonlib/bsd/gcd-test.c 10 files changed, 28 insertions(+), 23 deletions(-)
Approvals: build bot (Jenkins): Verified Nico Huber: Looks good to me, but someone else must approve Yidi Lin: Looks good to me, approved
diff --git a/payloads/libpayload/libc/getopt_long.c b/payloads/libpayload/libc/getopt_long.c index 822ce96..c0303cf 100644 --- a/payloads/libpayload/libc/getopt_long.c +++ b/payloads/libpayload/libc/getopt_long.c @@ -122,7 +122,7 @@ */ 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 c38dbfd..28f2b3e 100644 --- a/payloads/libpayload/libc/time.c +++ b/payloads/libpayload/libc/time.c @@ -182,7 +182,7 @@ "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 3eb5656..742b82c 100644 --- a/src/arch/arm64/arch_timer.c +++ b/src/arch/arm64/arch_timer.c @@ -19,7 +19,7 @@ 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 92b601e..fbc8103 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 20949de..de02eb5 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 8726ac0..4792d07 100644 --- a/src/drivers/analogix/anx7625/anx7625.c +++ b/src/drivers/analogix/anx7625/anx7625.c @@ -160,7 +160,7 @@ 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 eb79347..aac852a 100644 --- a/src/northbridge/intel/ironlake/quickpath.c +++ b/src/northbridge/intel/ironlake/quickpath.c @@ -19,7 +19,7 @@
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 @@ 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 d52fa2a..5b1350a 100644 --- a/src/soc/rockchip/rk3288/clock.c +++ b/src/soc/rockchip/rk3288/clock.c @@ -453,7 +453,7 @@ 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 fbff5a7..115d289 100644 --- a/src/soc/rockchip/rk3399/clock.c +++ b/src/soc/rockchip/rk3399/clock.c @@ -796,7 +796,7 @@ 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 13fad86..852a3fd 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);