linux-kernel - Re: [PATCH] lib: Fix possible incorrect result from rational fractions helper

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 1 Apr 2019 22:22:28 -0700
From:   Andrew Morton <akpm@...ux-foundation.org>
To:     Trent Piepho <tpiepho@...il.com>
Cc:     linux-kernel@...r.kernel.org, Oskar Schirmer <oskar@...ra.com>
Subject: Re: [PATCH] lib: Fix possible incorrect result from rational
 fractions helper

On Sat, 30 Mar 2019 13:58:55 -0700 Trent Piepho <tpiepho@...il.com> wrote:

> 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.

What are the userspace-visible runtime effects of this change?