Linux-mm Archive on lore.kernel.org
 help / color / Atom feed
From: Andrew Morton <akpm@linux-foundation.org>
To: akpm@linux-foundation.org, linux-mm@kvack.org,
	mm-commits@vger.kernel.org, oskar@scara.com,
	torvalds@linux-foundation.org, tpiepho@gmail.com
Subject: [patch 41/86] lib/math/rational.c: fix possible incorrect result from rational fractions helper
Date: Wed, 04 Dec 2019 16:51:57 -0800
Message-ID: <20191205005157.WfXR1BT89%akpm@linux-foundation.org> (raw)
In-Reply-To: <20191204164858.fe4ed8886e34ad9f3b34ea00@linux-foundation.org>

From: Trent Piepho <tpiepho@gmail.com>
Subject: lib/math/rational.c: fix possible incorrect result from rational fractions helper

In some cases the previous algorithm would not return the closest
approximation.  This would happen when a semi-convergent was the closest,
as the previous algorithm would only consider convergents.

As an example, consider an initial value of 5/4, and trying to find the
closest approximation with a maximum of 4 for numerator and denominator. 
The previous algorithm would return 1/1 as the closest approximation,
while this version will return the correct answer of 4/3.

To do this, the main loop performs effectively the same operations as it
did before.  It must now keep track of the last three approximations,
n2/d2 ..  n0/d0, while before it only needed the last two.

If an exact answer is not found, the algorithm will now calculate the best
semi-convergent term, t, which is a single expression with two divisions:

    min((max_numerator - n0) / n1, (max_denominator - d0) / d1)

This will be used if it is better than previous convergent.  The test for
this is generally a simple comparison, 2*t > a.  But in an edge case,
where the convergent's final term is even and the best allowable
semi-convergent has a final term of exactly half the convergent's final
term, the more complex comparison (d0*dp > d1*d) is used.

I also wrote some comments explaining the code.  While one still needs to
look up the math elsewhere, they should help a lot to follow how the code
relates to that math.

This routine is used in two places in the video4linux code, but in
those cases it is only used to reduce a fraction to lowest terms, which
the existing code will do correctly.  This could be done more
efficiently with a different library routine but it would still be the
Euclidean alogrithm at its heart.  So no change.

The remain users are places where a fractional PLL divider is
programmed.  What would happen is something asked for a clock of X MHz
but instead gets Y MHz, where Y is close to X but not exactly due to
the hardware limitations.  After this change they might, in some cases,
get Y' MHz, where Y' is a little closer to X then Y was.

Users like this are: Three UARTs, in 8250_mid, 8250_lpss, and imx.  One
GPU in vp4_hdmi.  And three clock drivers, clk-cdce706, clk-si5351, and
clk-fractional-divider.  The last is a generic clock driver and so
would have more users referenced via device tree entries.

I think there's a bug in that one, it's limiting an N bit field that is
offset-by-1 to the range 0 ..  (1<<N)-2, when it should be (1<<N)-1 as
the upper limit.

I have an IMX system, one of the UARTs using this, so I can provide a
real example.  If I request a custom baud rate of 1499978, the driver
will program the PLL to produce a baud rate of 1500000.  After this
change, the fractional divider in the UART is programmed to a ratio of
65535/65536, which produces a baud rate of 1499977.0625.  Closer to the
requested value.

Link: http://lkml.kernel.org/r/20190330205855.19396-1-tpiepho@gmail.com
Signed-off-by: Trent Piepho <tpiepho@gmail.com>
Cc: Oskar Schirmer <oskar@scara.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 lib/math/rational.c |   63 +++++++++++++++++++++++++++++++++---------
 1 file changed, 50 insertions(+), 13 deletions(-)

--- a/lib/math/rational.c~lib-fix-possible-incorrect-result-from-rational-fractions-helper
+++ a/lib/math/rational.c
@@ -3,6 +3,7 @@
  * 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
  */
@@ -10,6 +11,7 @@
 #include <linux/rational.h>
 #include <linux/compiler.h>
 #include <linux/export.h>
+#include <linux/kernel.h>
 
 /*
  * calculate best rational approximation for a given fraction
@@ -33,30 +35,65 @@ void rational_best_approximation(
 	unsigned long max_numerator, unsigned long max_denominator,
 	unsigned long *best_numerator, unsigned long *best_denominator)
 {
-	unsigned long n, d, n0, d0, n1, d1;
+	/* 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 t, a;
-		if ((n1 > max_numerator) || (d1 > max_denominator)) {
-			n1 = n0;
-			d1 = d0;
-			break;
-		}
+		unsigned long dp, a;
+
 		if (d == 0)
 			break;
-		t = d;
+		/* Find next term in continued fraction, 'a', via
+		 * Euclidean algorithm.
+		 */
+		dp = d;
 		a = n / d;
 		d = n % d;
-		n = t;
-		t = n0 + a * n1;
+		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 = t;
-		t = d0 + a * d1;
+		n1 = n2;
 		d0 = d1;
-		d1 = t;
+		d1 = d2;
 	}
 	*best_numerator = n1;
 	*best_denominator = d1;
_


  parent reply index

Thread overview: 88+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-12-05  0:48 incoming Andrew Morton
2019-12-05  0:49 ` [patch 01/86] mm/kasan/common.c: fix compile error Andrew Morton
2019-12-05  0:49 ` [patch 02/86] mm: memcg/slab: wait for !root kmem_cache refcnt killing on root kmem_cache destruction Andrew Morton
2019-12-05  0:49 ` [patch 03/86] mm/vmstat: add helpers to get vmstat item names for each enum type Andrew Morton
2019-12-05  0:49 ` [patch 04/86] mm/memcontrol: use vmstat names for printing statistics Andrew Morton
2019-12-05  0:49 ` [patch 05/86] mm/memory.c: replace is_zero_pfn with is_huge_zero_pmd for thp Andrew Morton
2019-12-05  0:49 ` [patch 06/86] proc: change ->nlink under proc_subdir_lock Andrew Morton
2019-12-05  0:50 ` [patch 07/86] fs/proc/generic.c: delete useless "len" variable Andrew Morton
2019-12-05  0:50 ` [patch 08/86] fs/proc/internal.h: shuffle "struct pde_opener" Andrew Morton
2019-12-05  0:50 ` [patch 09/86] include/linux/proc_fs.h: fix confusing macro arg name Andrew Morton
2019-12-05  0:50 ` [patch 10/86] fs/proc/Kconfig: fix indentation Andrew Morton
2019-12-05  0:50 ` [patch 11/86] include/linux/sysctl.h: inline braces for ctl_table and ctl_table_header Andrew Morton
2019-12-05  0:50 ` [patch 12/86] .gitattributes: use 'dts' diff driver for dts files Andrew Morton
2019-12-05  1:00   ` Frank Rowand
2019-12-05  0:50 ` [patch 13/86] linux/build_bug.h: change type to int Andrew Morton
2019-12-05  0:50 ` [patch 14/86] linux/scc.h: make uapi linux/scc.h self-contained Andrew Morton
2019-12-05  0:50 ` [patch 15/86] arch/Kconfig: fix indentation Andrew Morton
2019-12-05  0:50 ` [patch 16/86] scripts/get_maintainer.pl: add signatures from Fixes: <badcommit> lines in commit message Andrew Morton
2019-12-05  0:50 ` [patch 17/86] kernel.h: update comment about simple_strto<foo>() functions Andrew Morton
2019-12-05  0:50 ` [patch 18/86] auxdisplay: charlcd: deduplicate simple_strtoul() Andrew Morton
2019-12-05  0:50 ` [patch 19/86] kernel/notifier.c: intercept duplicate registrations to avoid infinite loops Andrew Morton
2019-12-05  0:50 ` [patch 20/86] kernel/notifier.c: remove notifier_chain_cond_register() Andrew Morton
2019-12-05  0:50 ` [patch 21/86] kernel/notifier.c: remove blocking_notifier_chain_cond_register() Andrew Morton
2019-12-05  0:50 ` [patch 22/86] kernel/profile.c: use cpumask_available to check for NULL cpumask Andrew Morton
2019-12-05  0:50 ` [patch 23/86] kernel/sys.c: avoid copying possible padding bytes in copy_to_user Andrew Morton
2019-12-05  0:50 ` [patch 24/86] bitops: introduce the for_each_set_clump8 macro Andrew Morton
2019-12-05  0:51 ` [patch 25/86] lib/test_bitmap.c: add for_each_set_clump8 test cases Andrew Morton
2019-12-05  0:51 ` [patch 26/86] gpio: 104-dio-48e: utilize for_each_set_clump8 macro Andrew Morton
2019-12-05  0:51 ` [patch 27/86] gpio: 104-idi-48: " Andrew Morton
2019-12-05  0:51 ` [patch 28/86] gpio: gpio-mm: " Andrew Morton
2019-12-05  0:51 ` [patch 29/86] gpio: ws16c48: " Andrew Morton
2019-12-05  0:51 ` [patch 30/86] gpio: pci-idio-16: " Andrew Morton
2019-12-05  0:51 ` [patch 31/86] gpio: pcie-idio-24: " Andrew Morton
2019-12-05  0:51 ` [patch 32/86] gpio: uniphier: " Andrew Morton
2019-12-05  0:51 ` [patch 33/86] gpio: 74x164: utilize the " Andrew Morton
2019-12-05  0:51 ` [patch 34/86] thermal: intel: intel_soc_dts_iosf: Utilize " Andrew Morton
2019-12-05  0:51 ` [patch 35/86] gpio: pisosr: utilize the " Andrew Morton
2019-12-05  0:51 ` [patch 36/86] gpio: max3191x: " Andrew Morton
2019-12-05  0:51 ` [patch 37/86] gpio: pca953x: " Andrew Morton
2019-12-05  0:51 ` [patch 38/86] lib/rbtree: set successor's parent unconditionally Andrew Morton
2019-12-05  0:51 ` [patch 39/86] lib/rbtree: get successor's color directly Andrew Morton
2019-12-05  0:51 ` [patch 40/86] lib/test_meminit.c: add bulk alloc/free tests Andrew Morton
2019-12-05  0:51 ` Andrew Morton [this message]
2019-12-05  0:52 ` [patch 42/86] lib/genalloc.c: export symbol addr_in_gen_pool Andrew Morton
2019-12-05  0:52 ` [patch 43/86] lib/genalloc.c: rename addr_in_gen_pool to gen_pool_has_addr Andrew Morton
2019-12-05  0:52 ` [patch 44/86] checkpatch: improve ignoring CamelCase SI style variants like mA Andrew Morton
2019-12-05  0:52 ` [patch 45/86] checkpatch: reduce is_maintained_obsolete lookup runtime Andrew Morton
2019-12-05  0:52 ` [patch 46/86] epoll: simplify ep_poll_safewake() for CONFIG_DEBUG_LOCK_ALLOC Andrew Morton
2019-12-05  0:52 ` [patch 47/86] fs/epoll: remove unnecessary wakeups of nested epoll Andrew Morton
2019-12-05  0:52 ` [patch 48/86] selftests: add epoll selftests Andrew Morton
2019-12-05  0:52 ` [patch 49/86] fs/binfmt_elf.c: delete unused "interp_map_addr" argument Andrew Morton
2019-12-05  0:52 ` [patch 50/86] fs/binfmt_elf.c: extract elf_read() function Andrew Morton
2019-12-05  0:52 ` [patch 51/86] init/Kconfig: fix indentation Andrew Morton
2019-12-05  0:52 ` [patch 52/86] drivers/rapidio/rio-driver.c: fix missing include of <linux/rio_drv.h> Andrew Morton
2019-12-05  0:52 ` [patch 53/86] drivers/rapidio/rio-access.c: " Andrew Morton
2019-12-05  0:52 ` [patch 54/86] drm: limit to INT_MAX in create_blob ioctl Andrew Morton
2019-12-05  0:52 ` [patch 55/86] uaccess: disallow > INT_MAX copy sizes Andrew Morton
2019-12-05  0:52 ` [patch 56/86] kcov: remote coverage support Andrew Morton
2019-12-05  0:52 ` [patch 57/86] usb, kcov: collect coverage from hub_event Andrew Morton
2019-12-05  0:52 ` [patch 58/86] vhost, kcov: collect coverage from vhost_worker Andrew Morton
2019-12-05  0:52 ` [patch 59/86] lib/ubsan: don't serialize UBSAN report Andrew Morton
2019-12-05  0:52 ` [patch 60/86] arch: ipcbuf.h: make uapi asm/ipcbuf.h self-contained Andrew Morton
2019-12-05  0:53 ` [patch 61/86] arch: msgbuf.h: make uapi asm/msgbuf.h self-contained Andrew Morton
2019-12-05  0:53 ` [patch 62/86] arch: sembuf.h: make uapi asm/sembuf.h self-contained Andrew Morton
2019-12-05  0:53 ` [patch 63/86] lib/test_bitmap: force argument of bitmap_parselist_user() to proper address space Andrew Morton
2019-12-05  0:53 ` [patch 64/86] lib/test_bitmap: undefine macros after use Andrew Morton
2019-12-05  0:53 ` [patch 65/86] lib/test_bitmap: name EXP_BYTES properly Andrew Morton
2019-12-05  0:53 ` [patch 66/86] lib/test_bitmap: rename exp to exp1 to avoid ambiguous name Andrew Morton
2019-12-05  0:53 ` [patch 67/86] lib/test_bitmap: move exp1 and exp2 upper for others to use Andrew Morton
2019-12-05  0:53 ` [patch 68/86] lib/test_bitmap: fix comment about this file Andrew Morton
2019-12-05  0:53 ` [patch 69/86] lib/bitmap: introduce bitmap_replace() helper Andrew Morton
2019-12-05  0:53 ` [patch 70/86] gpio: pca953x: remove redundant variable and check in IRQ handler Andrew Morton
2019-12-05  0:53 ` [patch 71/86] gpio: pca953x: use input from regs structure in pca953x_irq_pending() Andrew Morton
2019-12-05  0:53 ` [patch 72/86] gpio: pca953x: convert to use bitmap API Andrew Morton
2019-12-05  0:53 ` [patch 73/86] gpio: pca953x: tighten up indentation Andrew Morton
2019-12-05  0:53 ` [patch 74/86] alpha: use pgtable-nopud instead of 4level-fixup Andrew Morton
2019-12-05  0:53 ` [patch 75/86] arm: nommu: " Andrew Morton
2019-12-05  0:53 ` [patch 76/86] c6x: " Andrew Morton
2019-12-05  0:53 ` [patch 77/86] m68k: nommu: " Andrew Morton
2019-12-05  0:53 ` [patch 78/86] m68k: mm: use pgtable-nopXd " Andrew Morton
2019-12-05  0:54 ` [patch 79/86] microblaze: use pgtable-nopmd " Andrew Morton
2019-12-05  0:54 ` [patch 80/86] nds32: " Andrew Morton
2019-12-05  0:54 ` [patch 81/86] parisc: use pgtable-nopXd " Andrew Morton
2019-12-05  0:54 ` [patch 82/86] parisc/hugetlb: " Andrew Morton
2019-12-05  0:54 ` [patch 83/86] sparc32: use pgtable-nopud " Andrew Morton
2019-12-05  0:54 ` [patch 84/86] um: remove unused pxx_offset_proc() and addr_pte() functions Andrew Morton
2019-12-05  0:54 ` [patch 85/86] um: add support for folded p4d page tables Andrew Morton
2019-12-05  0:54 ` [patch 86/86] mm: remove __ARCH_HAS_4LEVEL_HACK and include/asm-generic/4level-fixup.h Andrew Morton

Reply instructions:

You may reply publically 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=20191205005157.WfXR1BT89%akpm@linux-foundation.org \
    --to=akpm@linux-foundation.org \
    --cc=linux-mm@kvack.org \
    --cc=mm-commits@vger.kernel.org \
    --cc=oskar@scara.com \
    --cc=torvalds@linux-foundation.org \
    --cc=tpiepho@gmail.com \
    /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

Linux-mm Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-mm/0 linux-mm/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-mm linux-mm/ https://lore.kernel.org/linux-mm \
		linux-mm@kvack.org
	public-inbox-index linux-mm

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kvack.linux-mm


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git