Messages in this thread | | | Subject | Re: [PATCH] lib: Fix possible incorrect result from rational fractions helper | From | tpiepho@gmail ... | Date | Wed, 03 Apr 2019 20:41:30 -0700 |
| |
On Mon, Apr 1, 2019 at 10:22 PM Andrew Morton < akpm@linux-foundation.org> wrote:
> On Sat, 30 Mar 2019 13:58:55 -0700 Trent Piepho <tpiepho@gmail.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. > > What are the userspace-visible runtime effects of this change?
Ok, I looked into this in some detail.
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.
| |