On Mon, Apr 1, 2019 at 10:22 PM Andrew Morton < a...@linux-foundation.org> wrote:
> On Sat, 30 Mar 2019 13:58:55 -0700 Trent Piepho <tpie...@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.
