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: 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; _