diff options
| -rw-r--r-- | src/commonlib/Makefile.inc | 3 | ||||
| -rw-r--r-- | src/commonlib/include/commonlib/rational.h | 22 | ||||
| -rw-r--r-- | src/commonlib/rational.c | 95 | ||||
| -rw-r--r-- | tests/commonlib/Makefile.inc | 4 | ||||
| -rw-r--r-- | tests/commonlib/rational-test.c | 57 |
5 files changed, 181 insertions, 0 deletions
diff --git a/src/commonlib/Makefile.inc b/src/commonlib/Makefile.inc index 2477e07268..e90ed4f283 100644 --- a/src/commonlib/Makefile.inc +++ b/src/commonlib/Makefile.inc @@ -21,6 +21,9 @@ ramstage-y += region.c smm-y += region.c postcar-y += region.c +romstage-y += rational.c +ramstage-y += rational.c + ramstage-$(CONFIG_PLATFORM_USES_FSP1_1) += fsp_relocate.c ifeq ($(CONFIG_FSP_M_XIP),) romstage-$(CONFIG_PLATFORM_USES_FSP2_0) += fsp_relocate.c diff --git a/src/commonlib/include/commonlib/rational.h b/src/commonlib/include/commonlib/rational.h new file mode 100644 index 0000000000..f172e0b191 --- /dev/null +++ b/src/commonlib/include/commonlib/rational.h @@ -0,0 +1,22 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ + +#ifndef _COMMONLIB_RATIONAL_H_ +#define _COMMONLIB_RATIONAL_H_ + +#include <stddef.h> + +/* + * Calculate the best rational approximation for a given fraction, + * with the restriction of maximum numerator and denominator. + * For example, to find the approximation of 3.1415 with 5 bit denominator + * and 8 bit numerator fields: + * + * rational_best_approximation(31415, 10000, + * (1 << 8) - 1, (1 << 5) - 1, &n, &d); + */ +void rational_best_approximation( + unsigned long numerator, unsigned long denominator, + unsigned long max_numerator, unsigned long max_denominator, + unsigned long *best_numerator, unsigned long *best_denominator); + +#endif /* _COMMONLIB_RATIONAL_H_ */ diff --git a/src/commonlib/rational.c b/src/commonlib/rational.c new file mode 100644 index 0000000000..2e5f3296cf --- /dev/null +++ b/src/commonlib/rational.c @@ -0,0 +1,95 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* + * Helper functions for rational numbers. + * + * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com> + * Copyright (C) 2019 Trent Piepho <tpiepho@gmail.com> + */ + +#include <commonlib/helpers.h> +#include <commonlib/rational.h> +#include <limits.h> + +/* + * For theoretical background, see: + * https://en.wikipedia.org/wiki/Continued_fraction + */ +void rational_best_approximation( + unsigned long numerator, unsigned long denominator, + unsigned long max_numerator, unsigned long max_denominator, + unsigned long *best_numerator, unsigned long *best_denominator) +{ + /* + * n/d is the starting rational, where both n and d will + * decrease in each iteration using the Euclidean algorithm. + * + * dp is the value of d from the prior iteration. + * + * n2/d2, n1/d1, and n0/d0 are our successively more accurate + * approximations of the rational. They are, respectively, + * the current, previous, and two prior iterations of it. + * + * a is current term of the continued fraction. + */ + unsigned long n, d, n0, d0, n1, d1, n2, d2; + n = numerator; + d = denominator; + n0 = d1 = 0; + n1 = d0 = 1; + + for (;;) { + unsigned long dp, a; + + if (d == 0) + break; + /* + * Find next term in continued fraction, 'a', via + * Euclidean algorithm. + */ + dp = d; + a = n / d; + d = n % d; + n = dp; + + /* + * Calculate the current rational approximation (aka + * convergent), n2/d2, using the term just found and + * the two prior approximations. + */ + n2 = n0 + a * n1; + d2 = d0 + a * d1; + + /* + * If the current convergent exceeds the maximum, then + * return either the previous convergent or the + * largest semi-convergent, the final term of which is + * found below as 't'. + */ + if ((n2 > max_numerator) || (d2 > max_denominator)) { + unsigned long t = ULONG_MAX; + + if (d1) + t = (max_denominator - d0) / d1; + if (n1) + t = MIN(t, (max_numerator - n0) / n1); + + /* + * This tests if the semi-convergent is closer than the previous + * convergent. If d1 is zero there is no previous convergent as + * this is the 1st iteration, so always choose the semi-convergent. + */ + if (!d1 || 2u * t > a || (2u * t == a && d0 * dp > d1 * d)) { + n1 = n0 + t * n1; + d1 = d0 + t * d1; + } + break; + } + n0 = n1; + n1 = n2; + d0 = d1; + d1 = d2; + } + + *best_numerator = n1; + *best_denominator = d1; +} diff --git a/tests/commonlib/Makefile.inc b/tests/commonlib/Makefile.inc index 054e7db16d..6df1db8fc5 100644 --- a/tests/commonlib/Makefile.inc +++ b/tests/commonlib/Makefile.inc @@ -2,7 +2,11 @@ subdirs-y += bsd +tests-y += rational-test tests-y += region-test +rational-test-srcs += tests/commonlib/rational-test.c +rational-test-srcs += src/commonlib/rational.c + region-test-srcs += tests/commonlib/region-test.c region-test-srcs += src/commonlib/region.c diff --git a/tests/commonlib/rational-test.c b/tests/commonlib/rational-test.c new file mode 100644 index 0000000000..4d6c215aad --- /dev/null +++ b/tests/commonlib/rational-test.c @@ -0,0 +1,57 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ + +#include <commonlib/rational.h> +#include <tests/test.h> + +struct rational_test_param { + unsigned long num, den; + unsigned long max_num, max_den; + unsigned long exp_num, exp_den; +}; + +static const struct rational_test_param test_params[] = { + /* Exceeds bounds, semi-convergent term > half last term */ + { 1230, 10, 100, 20, 100, 1}, + /* Exceeds bounds, semi-convergent term < half last term */ + { 34567, 100, 120, 20, 120, 1}, + /* Closest to zero */ + { 1, 30, 100, 10, 0, 1}, + /* Closest to smallest non-zero */ + { 1, 19, 100, 10, 1, 10}, + /* Exact answer */ + { 1155, 7735, 255, 255, 33, 221}, + /* Convergent */ + { 27, 32, 16, 16, 11, 13}, + /* Convergent, semiconvergent term half convergent term */ + { 67, 54, 17, 18, 5, 4}, + /* Semiconvergent, semiconvergent term half convergent term */ + { 453, 182, 60, 60, 57, 23}, + /* Semiconvergent, numerator limit */ + { 87, 32, 70, 32, 68, 25}, + /* Semiconvergent, demominator limit */ + { 14533, 4626, 15000, 2400, 7433, 2366}, +}; + +static void test_rational(void **state) +{ + int i; + unsigned long num = 0, den = 0; + + for (i = 0; i < ARRAY_SIZE(test_params); i++) { + rational_best_approximation(test_params[i].num, test_params[i].den, + test_params[i].max_num, test_params[i].max_den, + &num, &den); + assert_int_equal(num, test_params[i].exp_num); + assert_int_equal(den, test_params[i].exp_den); + } +} + +int main(void) +{ + const struct CMUnitTest tests[] = { + cmocka_unit_test(test_rational), + }; + + return cmocka_run_group_tests(tests, NULL, NULL); +} + |