From: Sascha Hauer <s.hauer@pengutronix.de> To: Barebox List <barebox@lists.infradead.org> Cc: Ahmad Fatoum <a.fatoum@pengutronix.de> Subject: [PATCH 11/24] Add rational_best_approximation() Date: Wed, 2 Jun 2021 11:54:54 +0200 [thread overview] Message-ID: <20210602095507.24609-12-s.hauer@pengutronix.de> (raw) In-Reply-To: <20210602095507.24609-1-s.hauer@pengutronix.de> Import rational_best_approximation() from Linux. This is used by an upcoming update of the clk_fractional_divider code. Signed-off-by: Sascha Hauer <s.hauer@pengutronix.de> Reviewed-by: Ahmad Fatoum <a.fatoum@pengutronix.de> --- include/linux/rational.h | 20 ++++++++ lib/math/Makefile | 1 + lib/math/rational.c | 100 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 121 insertions(+) create mode 100644 include/linux/rational.h create mode 100644 lib/math/rational.c diff --git a/include/linux/rational.h b/include/linux/rational.h new file mode 100644 index 0000000000..33f5f5fc3e --- /dev/null +++ b/include/linux/rational.h @@ -0,0 +1,20 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * rational fractions + * + * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com> + * + * helper functions when coping with rational numbers, + * e.g. when calculating optimum numerator/denominator pairs for + * pll configuration taking into account restricted register size + */ + +#ifndef _LINUX_RATIONAL_H +#define _LINUX_RATIONAL_H + +void rational_best_approximation( + unsigned long given_numerator, unsigned long given_denominator, + unsigned long max_numerator, unsigned long max_denominator, + unsigned long *best_numerator, unsigned long *best_denominator); + +#endif /* _LINUX_RATIONAL_H */ diff --git a/lib/math/Makefile b/lib/math/Makefile index c2c892dd55..756d7dd90d 100644 --- a/lib/math/Makefile +++ b/lib/math/Makefile @@ -1,2 +1,3 @@ obj-y += div64.o pbl-y += div64.o +obj-y += rational.o diff --git a/lib/math/rational.c b/lib/math/rational.c new file mode 100644 index 0000000000..e5367e6a8a --- /dev/null +++ b/lib/math/rational.c @@ -0,0 +1,100 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * rational fractions + * + * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com> + * Copyright (C) 2019 Trent Piepho <tpiepho@gmail.com> + * + * helper functions when coping with rational numbers + */ + +#include <linux/rational.h> +#include <linux/compiler.h> +#include <linux/export.h> +#include <linux/kernel.h> + +/* + * calculate best rational approximation for a given fraction + * taking into account restricted register size, e.g. to find + * appropriate values for a pll with 5 bit denominator and + * 8 bit numerator register fields, trying to set up with a + * frequency ratio of 3.1415, one would say: + * + * rational_best_approximation(31415, 10000, + * (1 << 8) - 1, (1 << 5) - 1, &n, &d); + * + * you may look at given_numerator as a fixed point number, + * with the fractional part size described in given_denominator. + * + * for theoretical background, see: + * https://en.wikipedia.org/wiki/Continued_fraction + */ + +void rational_best_approximation( + unsigned long given_numerator, unsigned long given_denominator, + unsigned long max_numerator, unsigned long max_denominator, + unsigned long *best_numerator, unsigned long *best_denominator) +{ + /* n/d is the starting rational, which is continually + * decreased 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 = given_numerator; + d = given_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 maxes, 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 = min((max_numerator - n0) / n1, + (max_denominator - d0) / d1); + + /* This tests if the semi-convergent is closer + * than the previous convergent. + */ + if (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; +} -- 2.29.2 _______________________________________________ barebox mailing list barebox@lists.infradead.org http://lists.infradead.org/mailman/listinfo/barebox
next prev parent reply other threads:[~2021-06-02 10:06 UTC|newest] Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-06-02 9:54 [PATCH v2 00/24] clk updates Sascha Hauer 2021-06-02 9:54 ` [PATCH 01/24] clk: clk-mux: Fix handling of CLK_MUX_HIWORD_MASK Sascha Hauer 2021-06-02 15:18 ` Ahmad Fatoum 2021-06-02 9:54 ` [PATCH 02/24] clk: introduce clk init op Sascha Hauer 2021-06-02 9:54 ` [PATCH 03/24] clk: rename clk_register() to bclk_register() Sascha Hauer 2021-06-02 9:54 ` [PATCH 04/24] clk: introduce struct clk_hw Sascha Hauer 2021-06-11 7:55 ` Ahmad Fatoum 2021-06-11 8:41 ` Sascha Hauer 2021-06-11 9:19 ` Ahmad Fatoum 2021-06-11 11:46 ` Sascha Hauer 2021-06-11 12:14 ` Ahmad Fatoum 2021-06-02 9:54 ` [PATCH 05/24] clk: introduce clk_register() Sascha Hauer 2021-06-02 9:54 ` [PATCH 06/24] clk: divider: Make clk_divider_ops const Sascha Hauer 2021-06-02 9:54 ` [PATCH 07/24] clk: divider: Add ro ops Sascha Hauer 2021-06-02 9:54 ` [PATCH 08/24] clk: divider: Make clk_mux_ops const Sascha Hauer 2021-06-02 9:54 ` [PATCH 09/24] clk: mux: Add ro ops Sascha Hauer 2021-06-02 9:54 ` [PATCH 10/24] clk: move fixed_factor to include/linux/clk.h Sascha Hauer 2021-06-02 9:54 ` Sascha Hauer [this message] 2021-06-02 18:25 ` [PATCH 11/24] Add rational_best_approximation() Trent Piepho 2021-06-07 11:22 ` Sascha Hauer 2021-06-02 9:54 ` [PATCH 12/24] clk: Update fractional divider from Linux Sascha Hauer 2021-06-02 9:54 ` [PATCH 13/24] clk: Add lock to different clock types Sascha Hauer 2021-06-02 9:54 ` [PATCH 14/24] clk: Add Linux functions to register a divider Sascha Hauer 2021-06-02 9:54 ` [PATCH 15/24] clk: Add Linux functions to register a fixed factor clock Sascha Hauer 2021-06-02 9:54 ` [PATCH 16/24] clk: Add Linux functions to register a gate Sascha Hauer 2021-06-02 9:55 ` [PATCH 17/24] clk: Add Linux functions to register a mux Sascha Hauer 2021-06-02 9:55 ` [PATCH 18/24] clk: Add CLK_GET_RATE_NOCACHE Sascha Hauer 2021-06-02 9:55 ` [PATCH 19/24] clk: Rename CLK_GATE_INVERTED to CLK_GATE_SET_TO_DISABLE Sascha Hauer 2021-06-02 9:55 ` [PATCH 20/24] clk: implement CLK_SET_RATE_UNGATE Sascha Hauer 2021-06-02 9:55 ` [PATCH 21/24] clk: implement set/get phase Sascha Hauer 2021-06-02 9:55 ` [PATCH 22/24] regmap: Add regmap_read_poll_timeout Sascha Hauer 2021-06-02 9:55 ` [PATCH 23/24] clk: rockchip: Update to current Linux Sascha Hauer 2021-06-02 9:55 ` [PATCH 24/24] clk: Rockchip: Add rk3568 clk support Sascha Hauer 2021-06-09 9:18 ` Ahmad Fatoum
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20210602095507.24609-12-s.hauer@pengutronix.de \ --to=s.hauer@pengutronix.de \ --cc=a.fatoum@pengutronix.de \ --cc=barebox@lists.infradead.org \ --subject='Re: [PATCH 11/24] Add rational_best_approximation()' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox