linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Trent Piepho <tpiepho@gmail.com>
To: linux-kernel@vger.kernel.org
Cc: andy@kernel.org, akpm@linux-foundation.org, oskar@scara.com,
	Daniel Latypov <dlatypov@google.com>,
	Trent Piepho <tpiepho@gmail.com>, Yiyuan Guo <yguoaz@gmail.com>
Subject: [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero
Date: Tue, 25 May 2021 16:35:18 -0700	[thread overview]
Message-ID: <20210525233519.343068-1-tpiepho@gmail.com> (raw)

If the input is out of the range of the allowed values, either larger
than the largest value or closer to zero than the smallest non-zero
allowed value, then a division by zero would occur.

In the case of input too large, the division by zero will occur on the
first iteration.  The best result (largest allowed value) will be found
by always choosing the semi-convergent and excluding the denominator
based limit when finding it.

In the case of the input too small, the division by zero will occur on
the second iteration.  The numerator based semi-convergent should not be
calculated to avoid the division by zero.  But the semi-convergent vs
previous convergent test is still needed, which effectively chooses
between 0 (the previous convergent) vs the smallest allowed fraction
(best semi-convergent) as the result.

Fixes: 323dd2c3ed0 ("lib/math/rational.c: fix possible incorrect result from rational fractions helper")
Reported-by: Yiyuan Guo <yguoaz@gmail.com>
Signed-off-by: Trent Piepho <tpiepho@gmail.com>
---
 lib/math/rational.c | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)

diff --git a/lib/math/rational.c b/lib/math/rational.c
index 9781d521963d..c0ab51d8fbb9 100644
--- a/lib/math/rational.c
+++ b/lib/math/rational.c
@@ -12,6 +12,7 @@
 #include <linux/compiler.h>
 #include <linux/export.h>
 #include <linux/minmax.h>
+#include <linux/limits.h>
 
 /*
  * calculate best rational approximation for a given fraction
@@ -78,13 +79,18 @@ void rational_best_approximation(
 		 * found below as 't'.
 		 */
 		if ((n2 > max_numerator) || (d2 > max_denominator)) {
-			unsigned long t = min((max_numerator - n0) / n1,
-					      (max_denominator - d0) / d1);
+			unsigned long t = ULONG_MAX;
 
-			/* This tests if the semi-convergent is closer
-			 * than the previous convergent.
+			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 (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
+			if (!d1 || 2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
 				n1 = n0 + t * n1;
 				d1 = d0 + t * d1;
 			}
-- 
2.26.2


             reply	other threads:[~2021-05-25 23:35 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-05-25 23:35 Trent Piepho [this message]
2021-05-25 23:35 ` [PATCH v3 2/2] lib/math/rational: Add Kunit test cases Trent Piepho
2021-05-25 23:53   ` Daniel Latypov
2021-05-26  8:04 ` [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero Andy Shevchenko
2021-05-26  8:06   ` Andy Shevchenko
2021-05-26 19:09   ` Trent Piepho

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=20210525233519.343068-1-tpiepho@gmail.com \
    --to=tpiepho@gmail.com \
    --cc=akpm@linux-foundation.org \
    --cc=andy@kernel.org \
    --cc=dlatypov@google.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=oskar@scara.com \
    --cc=yguoaz@gmail.com \
    --subject='Re: [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero' \
    /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;
as well as URLs for NNTP newsgroup(s).