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=-19.4 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham 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 C8324C47098 for ; Thu, 3 Jun 2021 06:33:27 +0000 (UTC) Received: from phobos.denx.de (phobos.denx.de [85.214.62.61]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 3417D613F4 for ; Thu, 3 Jun 2021 06:33:27 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 3417D613F4 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=kernel.org Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=u-boot-bounces@lists.denx.de Received: from h2850616.stratoserver.net (localhost [IPv6:::1]) by phobos.denx.de (Postfix) with ESMTP id 5A27B82F87; Thu, 3 Jun 2021 08:33:16 +0200 (CEST) Authentication-Results: phobos.denx.de; dmarc=pass (p=none dis=none) header.from=kernel.org Authentication-Results: phobos.denx.de; spf=pass smtp.mailfrom=u-boot-bounces@lists.denx.de Authentication-Results: phobos.denx.de; dkim=pass (2048-bit key; unprotected) header.d=kernel.org header.i=@kernel.org header.b="YUWZ/tG3"; dkim-atps=neutral Received: by phobos.denx.de (Postfix, from userid 109) id 2C9E682F7E; Thu, 3 Jun 2021 08:33:13 +0200 (CEST) Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by phobos.denx.de (Postfix) with ESMTPS id 69F7282F6D for ; Thu, 3 Jun 2021 08:33:09 +0200 (CEST) Authentication-Results: phobos.denx.de; dmarc=pass (p=none dis=none) header.from=kernel.org Authentication-Results: phobos.denx.de; spf=pass smtp.mailfrom=kristo@kernel.org Received: by mail.kernel.org (Postfix) with ESMTPSA id 4241861263; Thu, 3 Jun 2021 06:33:07 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1622701988; bh=+8iLxbTv5DhZdXiAFKlJxIYsNtJ2hcyeUUJW6fz0kA4=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=YUWZ/tG38e+qMNGTqaVP4DS0oeXMr2tQ/5sSzXziidCV63hQD9sqLtjHRvVmnTgJH t5X2sIHelk1U/GxbnXOs5bUc9JGq9q+fyesuBqugeEjV9KtMdnnAP0LftbYDRewJ+S AK9JwKEcDZ4OJzNlOL/MDKJyEw6Ew3jJ2ciK6fKLEsYcs2/skLEfctEe6aHCcjdQmO Ml/AzZ/Zu3tG6bJqscqoE9emoJGCpOzytjpkCci31XAfORCMs+q4FfG5ioLP1FEXVL ZZyDDnoVqbRKQMYfPLULwqSjwHqkLoJX4OBTN2vXFHEXIYOXg87fb2htiTiay/Y5dg eLDEAXFKkH08w== From: Tero Kristo To: u-boot@lists.denx.de, lokeshvutla@ti.com Cc: trini@konsulko.com Subject: [PATCHv5 01/26] lib: rational: copy the rational fraction lib routines from Linux Date: Thu, 3 Jun 2021 09:32:30 +0300 Message-Id: <20210603063255.5483-2-kristo@kernel.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20210603063255.5483-1-kristo@kernel.org> References: <20210603063255.5483-1-kristo@kernel.org> X-BeenThere: u-boot@lists.denx.de X-Mailman-Version: 2.1.34 Precedence: list List-Id: U-Boot discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: u-boot-bounces@lists.denx.de Sender: "U-Boot" X-Virus-Scanned: clamav-milter 0.102.4 at phobos.denx.de X-Virus-Status: Clean From: Tero Kristo Copy the best rational approximation calculation routines from Linux. Typical usecase for these routines is to calculate the M/N divider values for PLLs to reach a specific clock rate. This is based on linux kernel commit: "lib/math/rational.c: fix possible incorrect result from rational fractions helper" (sha1: 323dd2c3ed0641f49e89b4e420f9eef5d3d5a881) Signed-off-by: Tero Kristo Reviewed-by: Tom Rini Signed-off-by: Tero Kristo --- include/linux/rational.h | 20 ++++++++ lib/Kconfig | 7 +++ lib/Makefile | 2 + lib/rational.c | 99 ++++++++++++++++++++++++++++++++++++++++ 4 files changed, 128 insertions(+) create mode 100644 include/linux/rational.h create mode 100644 lib/rational.c diff --git a/include/linux/rational.h b/include/linux/rational.h new file mode 100644 index 0000000000..33f5f5fc3e --- /dev/null +++ b/include/linux/rational.h @@ -0,0 +1,20 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * rational fractions + * + * Copyright (C) 2009 emlix GmbH, Oskar Schirmer + * + * helper functions when coping with rational numbers, + * e.g. when calculating optimum numerator/denominator pairs for + * pll configuration taking into account restricted register size + */ + +#ifndef _LINUX_RATIONAL_H +#define _LINUX_RATIONAL_H + +void rational_best_approximation( + unsigned long given_numerator, unsigned long given_denominator, + unsigned long max_numerator, unsigned long max_denominator, + unsigned long *best_numerator, unsigned long *best_denominator); + +#endif /* _LINUX_RATIONAL_H */ diff --git a/lib/Kconfig b/lib/Kconfig index 15019d2c65..ad0cd52edd 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -674,6 +674,13 @@ config GENERATE_SMBIOS_TABLE See also SMBIOS_SYSINFO which allows SMBIOS values to be provided in the devicetree. +config LIB_RATIONAL + bool "enable continued fraction calculation routines" + +config SPL_LIB_RATIONAL + bool "enable continued fraction calculation routines for SPL" + depends on SPL + endmenu config ASN1_COMPILER diff --git a/lib/Makefile b/lib/Makefile index b4795a62a0..881034f4ae 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -73,6 +73,8 @@ obj-$(CONFIG_$(SPL_)LZO) += lzo/ obj-$(CONFIG_$(SPL_)LZMA) += lzma/ obj-$(CONFIG_$(SPL_)LZ4) += lz4_wrapper.o +obj-$(CONFIG_$(SPL_)LIB_RATIONAL) += rational.o + obj-$(CONFIG_LIBAVB) += libavb/ obj-$(CONFIG_$(SPL_TPL_)OF_LIBFDT) += libfdt/ diff --git a/lib/rational.c b/lib/rational.c new file mode 100644 index 0000000000..316db3b590 --- /dev/null +++ b/lib/rational.c @@ -0,0 +1,99 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * rational fractions + * + * Copyright (C) 2009 emlix GmbH, Oskar Schirmer + * Copyright (C) 2019 Trent Piepho + * + * helper functions when coping with rational numbers + */ + +#include +#include +#include + +/* + * calculate best rational approximation for a given fraction + * taking into account restricted register size, e.g. to find + * appropriate values for a pll with 5 bit denominator and + * 8 bit numerator register fields, trying to set up with a + * frequency ratio of 3.1415, one would say: + * + * rational_best_approximation(31415, 10000, + * (1 << 8) - 1, (1 << 5) - 1, &n, &d); + * + * you may look at given_numerator as a fixed point number, + * with the fractional part size described in given_denominator. + * + * for theoretical background, see: + * http://en.wikipedia.org/wiki/Continued_fraction + */ + +void rational_best_approximation( + unsigned long given_numerator, unsigned long given_denominator, + unsigned long max_numerator, unsigned long max_denominator, + unsigned long *best_numerator, unsigned long *best_denominator) +{ + /* 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 dp, a; + + if (d == 0) + break; + /* Find next term in continued fraction, 'a', via + * Euclidean algorithm. + */ + dp = d; + a = n / d; + d = n % d; + 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 = n2; + d0 = d1; + d1 = d2; + } + *best_numerator = n1; + *best_denominator = d1; +} -- 2.17.1