From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path:
X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on
aws-us-west-2-korg-lkml-1.web.codeaurora.org
X-Spam-Level:
X-Spam-Status: No, score=-3.8 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED,
DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SIGNED_OFF_BY,
SPF_HELO_NONE,SPF_PASS autolearn=no autolearn_force=no version=3.4.0
Received: from mail.kernel.org (mail.kernel.org [198.145.29.99])
by smtp.lore.kernel.org (Postfix) with ESMTP id 34A23C43603
for ; Thu, 5 Dec 2019 00:52:00 +0000 (UTC)
Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17])
by mail.kernel.org (Postfix) with ESMTP id DCCDC21823
for ; Thu, 5 Dec 2019 00:51:59 +0000 (UTC)
Authentication-Results: mail.kernel.org;
dkim=pass (1024-bit key) header.d=kernel.org header.i=@kernel.org header.b="qDRznhCB"
DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org DCCDC21823
Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=linux-foundation.org
Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org
Received: by kanga.kvack.org (Postfix)
id 727296B0DB5; Wed, 4 Dec 2019 19:51:59 -0500 (EST)
Received: by kanga.kvack.org (Postfix, from userid 40)
id 6D8A56B0DB7; Wed, 4 Dec 2019 19:51:59 -0500 (EST)
X-Delivered-To: int-list-linux-mm@kvack.org
Received: by kanga.kvack.org (Postfix, from userid 63042)
id 5C5D86B0DB8; Wed, 4 Dec 2019 19:51:59 -0500 (EST)
X-Delivered-To: linux-mm@kvack.org
Received: from forelay.hostedemail.com (smtprelay0033.hostedemail.com [216.40.44.33])
by kanga.kvack.org (Postfix) with ESMTP id 4665E6B0DB5
for ; Wed, 4 Dec 2019 19:51:59 -0500 (EST)
Received: from smtpin10.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251])
by forelay03.hostedemail.com (Postfix) with SMTP id 194A9816BFE5
for ; Thu, 5 Dec 2019 00:51:59 +0000 (UTC)
X-FDA: 76229260758.10.can88_1142e6ba50b63
X-HE-Tag: can88_1142e6ba50b63
X-Filterd-Recvd-Size: 7480
Received: from mail.kernel.org (mail.kernel.org [198.145.29.99])
by imf41.hostedemail.com (Postfix) with ESMTP
for ; Thu, 5 Dec 2019 00:51:58 +0000 (UTC)
Received: from localhost.localdomain (c-73-231-172-41.hsd1.ca.comcast.net [73.231.172.41])
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
(No client certificate requested)
by mail.kernel.org (Postfix) with ESMTPSA id 8E94524658;
Thu, 5 Dec 2019 00:51:57 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org;
s=default; t=1575507117;
bh=hzgEPwF7+O9Vh9VBPpRFAShVxXQkP3f2pAdqSeIBSnw=;
h=Date:From:To:Subject:In-Reply-To:From;
b=qDRznhCBS9utCkoS/bEhTT8I6M8geBuDdT+wRmyb6E4h8uXRmatA6yhbBxNTi8bGw
6+KmfZZiL2sErNOsUUunWTNjPu4NyESMzRs8CYK3oODC+NSiJPruhd7bxW1RUHlpAr
HccEZZGvnonqJNAR0f+b5bWTstNiIOsAFCG8d/oA=
Date: Wed, 04 Dec 2019 16:51:57 -0800
From: Andrew Morton
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
Message-ID: <20191205005157.WfXR1BT89%akpm@linux-foundation.org>
In-Reply-To: <20191204164858.fe4ed8886e34ad9f3b34ea00@linux-foundation.org>
User-Agent: s-nail v14.8.16
X-Bogosity: Ham, tests=bogofilter, spamicity=0.000003, version=1.2.4
Sender: owner-linux-mm@kvack.org
Precedence: bulk
X-Loop: owner-majordomo@kvack.org
List-ID:
Archived-At:
List-Archive:
List-Post:
From: Trent Piepho
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<
Cc: Oskar Schirmer
Signed-off-by: Andrew Morton
---
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
+ * Copyright (C) 2019 Trent Piepho
*
* helper functions when coping with rational numbers
*/
@@ -10,6 +11,7 @@
#include
#include
#include
+#include
/*
* 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;
_