summaryrefslogtreecommitdiff
path: root/lib/math
AgeCommit message (Collapse)AuthorFilesLines
2021-07-01lib/math/rational: add Kunit test casesTrent Piepho2-0/+57
Adds a number of test cases that cover a range of possible code paths. [akpm@linux-foundation.org: remove non-ascii characters, fix whitespace] [colin.king@canonical.com: fix spelling mistake "demominator" -> "denominator"] Link: https://lkml.kernel.org/r/20210526085049.6393-1-colin.king@canonical.com Link: https://lkml.kernel.org/r/20210525144250.214670-2-tpiepho@gmail.com Signed-off-by: Trent Piepho <tpiepho@gmail.com> Signed-off-by: Colin Ian King <colin.king@canonical.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Daniel Latypov <dlatypov@google.com> Cc: Oskar Schirmer <oskar@scara.com> Cc: Yiyuan Guo <yguoaz@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2021-07-01lib/math/rational.c: fix divide by zeroTrent Piepho1-5/+11
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. Link: https://lkml.kernel.org/r/20210525144250.214670-1-tpiepho@gmail.com Fixes: 323dd2c3ed0 ("lib/math/rational.c: fix possible incorrect result from rational fractions helper") Signed-off-by: Trent Piepho <tpiepho@gmail.com> Reported-by: Yiyuan Guo <yguoaz@gmail.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Oskar Schirmer <oskar@scara.com> Cc: Daniel Latypov <dlatypov@google.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2021-04-29Merge tag 'mips_5.13' of ↵Linus Torvalds2-0/+251
git://git.kernel.org/pub/scm/linux/kernel/git/mips/linux Pull MIPS updates from Thomas Bogendoerfer: - removed get_fs/set_fs - removed broken/unmaintained MIPS KVM trap and emulate support - added support for Loongson-2K1000 - fixes and cleanups * tag 'mips_5.13' of git://git.kernel.org/pub/scm/linux/kernel/git/mips/linux: (107 commits) MIPS: BCM63XX: Use BUG_ON instead of condition followed by BUG. MIPS: select ARCH_KEEP_MEMBLOCK unconditionally mips: Do not include hi and lo in clobber list for R6 MIPS:DTS:Correct the license for Loongson-2K MIPS:DTS:Fix label name and interrupt number of ohci for Loongson-2K MIPS: Avoid handcoded DIVU in `__div64_32' altogether lib/math/test_div64: Correct the spelling of "dividend" lib/math/test_div64: Fix error message formatting mips/bootinfo:correct some comments of fw_arg MIPS: Avoid DIVU in `__div64_32' is result would be zero MIPS: Reinstate platform `__div64_32' handler div64: Correct inline documentation for `do_div' lib/math: Add a `do_div' test module MIPS: Makefile: Replace -pg with CC_FLAGS_FTRACE MIPS: pci-legacy: revert "use generic pci_enable_resources" MIPS: Loongson64: Add kexec/kdump support MIPS: pci-legacy: use generic pci_enable_resources MIPS: pci-legacy: remove busn_resource field MIPS: pci-legacy: remove redundant info messages MIPS: pci-legacy: stop using of_pci_range_to_resource ...
2021-04-23lib/math/test_div64: Correct the spelling of "dividend"Maciej W. Rozycki1-19/+19
The word is spelt with a final "d" of course. What a massive messup! Signed-off-by: Maciej W. Rozycki <macro@orcam.me.uk> Signed-off-by: Thomas Bogendoerfer <tsbogend@alpha.franken.de>
2021-04-21lib/math/test_div64: Fix error message formattingMaciej W. Rozycki1-1/+1
Align the expected result with one actually produced for easier visual comparison; this has to take into account what the format specifiers will actually produce rather than the characters they consist of. E.g.: test_div64: ERROR: 10000000ab275080 / 00000009 => 01c71c71da20d00e,00000002 test_div64: ERROR: expected value => 0000000013045e47,00000001 (with a failure induced by setting bit #60 of the divident). Signed-off-by: Maciej W. Rozycki <macro@orcam.me.uk> Signed-off-by: Thomas Bogendoerfer <tsbogend@alpha.franken.de>
2021-04-21lib/math: Add a `do_div' test moduleMaciej W. Rozycki2-0/+251
Implement a module for correctness and performance evaluation for the `do_div' function, often handled in an optimised manner by platform code. Use a somewhat randomly generated set of inputs that is supposed to be representative, using the same set of divisors twice, expressed as a constant and as a variable each, so as to verify the implementation for both cases should they be handled by different code execution paths. Reference results were produced with GNU bc. At the conclusion output the total execution time elapsed. Signed-off-by: Maciej W. Rozycki <macro@orcam.me.uk> Signed-off-by: Thomas Bogendoerfer <tsbogend@alpha.franken.de>
2021-03-25math: Export mul_u64_u64_div_u64David S. Miller1-0/+1
Fixes: f51d7bf1dbe5 ("ptp_qoriq: fix overflow in ptp_qoriq_adjfine() u64 calcalation") Signed-off-by: David S. Miller <davem@davemloft.net>
2020-12-16kernel.h: split out mathematical helpersAndy Shevchenko4-6/+12
kernel.h is being used as a dump for all kinds of stuff for a long time. Here is the attempt to start cleaning it up by splitting out mathematical helpers. At the same time convert users in header and lib folder to use new header. Though for time being include new header back to kernel.h to avoid twisted indirected includes for existing users. [sfr@canb.auug.org.au: fix powerpc build] Link: https://lkml.kernel.org/r/20201029150809.13059608@canb.auug.org.au Link: https://lkml.kernel.org/r/20201028173212.41768-1-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: "Paul E. McKenney" <paulmck@kernel.org> Cc: Trond Myklebust <trond.myklebust@hammerspace.com> Cc: Jeff Layton <jlayton@kernel.org> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-10-16kernel.h: split out min()/max() et al. helpersAndy Shevchenko2-1/+2
kernel.h is being used as a dump for all kinds of stuff for a long time. Here is the attempt to start cleaning it up by splitting out min()/max() et al. helpers. At the same time convert users in header and lib folder to use new header. Though for time being include new header back to kernel.h to avoid twisted indirected includes for other existing users. Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Cc: "Rafael J. Wysocki" <rjw@rjwysocki.net> Cc: Steven Rostedt <rostedt@goodmis.org> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk> Cc: Joe Perches <joe@perches.com> Cc: Linus Torvalds <torvalds@linux-foundation.org> Link: https://lkml.kernel.org/r/20200910164152.GA1891694@smile.fi.intel.com Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-08-12lib/: replace HTTP links with HTTPS onesAlexander A. Klimov1-1/+1
Rationale: Reduces attack surface on kernel devs opening the links for MITM as HTTPS traffic is much harder to manipulate. Signed-off-by: Alexander A. Klimov <grandmaster@al2klimov.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Acked-by: Coly Li <colyli@suse.de> [crc64.c] Link: http://lkml.kernel.org/r/20200726112154.16510-1-grandmaster@al2klimov.de Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-06-15sched/cputime: Improve cputime_adjust()Oleg Nesterov1-0/+41
People report that utime and stime from /proc/<pid>/stat become very wrong when the numbers are big enough, especially if you watch these counters incrementally. Specifically, the current implementation of: stime*rtime/total, results in a saw-tooth function on top of the desired line, where the teeth grow in size the larger the values become. IOW, it has a relative error. The result is that, when watching incrementally as time progresses (for large values), we'll see periods of pure stime or utime increase, irrespective of the actual ratio we're striving for. Replace scale_stime() with a math64.h helper: mul_u64_u64_div_u64() that is far more accurate. This also allows architectures to override the implementation -- for instance they can opt for the old algorithm if this new one turns out to be too expensive for them. Signed-off-by: Oleg Nesterov <oleg@redhat.com> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org> Link: https://lkml.kernel.org/r/20200519172506.GA317395@hirez.programming.kicks-ass.net
2020-06-09Merge tag 'linux-kselftest-5.8-rc1' of ↵Linus Torvalds1-1/+6
git://git.kernel.org/pub/scm/linux/kernel/git/shuah/linux-kselftest Pull kselftest updates from Shuah Khan: "This consists of: - Several fixes from Masami Hiramatsu to improve coverage for lib and sysctl tests. - Clean up to vdso test and a new test for getcpu() from Mark Brown. - Add new gen_tar selftests Makefile target generate selftest package running "make gen_tar" in selftests directory from Veronika Kabatova. - Other miscellaneous fixes to timens, exec, tpm2 tests" * tag 'linux-kselftest-5.8-rc1' of git://git.kernel.org/pub/scm/linux/kernel/git/shuah/linux-kselftest: selftests/sysctl: Make sysctl test driver as a module selftests/sysctl: Fix to load test_sysctl module lib: Make test_sysctl initialized as module lib: Make prime number generator independently selectable selftests/ftrace: Return unsupported if no error_log file selftests/ftrace: Use printf for backslash included command selftests/timens: handle a case when alarm clocks are not supported Kernel selftests: Add check if TPM devices are supported selftests: vdso: Add a selftest for vDSO getcpu() selftests: vdso: Use a header file to prototype parse_vdso API selftests: vdso: Rename vdso_test to vdso_test_gettimeofday selftests/exec: Verify execve of non-regular files fail selftests: introduce gen_tar Makefile target
2020-06-05lib/math: avoid trailing newline hidden in pr_fmt()Christophe JAILLET1-5/+5
pr_xxx() functions usually have a newline at the end of the logging message. Here, this newline is added via the 'pr_fmt' macro. In order to be more consistent with other files, use a more standard convention and put these newlines back in the messages themselves and remove it from the pr_fmt macro. While at it, use __func__ instead of hardcoding a function name in the last message. Signed-off-by: Christophe JAILLET <christophe.jaillet@wanadoo.fr> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Mauro Carvalho Chehab <mchehab+samsung@kernel.org> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Link: http://lkml.kernel.org/r/20200409163234.22830-1-christophe.jaillet@wanadoo.fr Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2020-06-02lib: Make prime number generator independently selectableMasami Hiramatsu1-1/+6
Make prime number generator independently selectable from kconfig. This allows us to enable CONFIG_PRIME_NUMBERS=m and run the tools/testing/selftests/lib/prime_numbers.sh without other DRM selftest modules. Signed-off-by: Masami Hiramatsu <mhiramat@kernel.org> Reviewed-by: Kees Cook <keescook@chromium.org> Reviewed-by: Luis Chamberlain <mcgrof@kernel.org> Signed-off-by: Shuah Khan <skhan@linuxfoundation.org>
2019-12-05lib/math/rational.c: fix possible incorrect result from rational fractions ↵Trent Piepho1-13/+50
helper 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. 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. Link: http://lkml.kernel.org/r/20190330205855.19396-1-tpiepho@gmail.com Signed-off-by: Trent Piepho <tpiepho@gmail.com> Cc: Oskar Schirmer <oskar@scara.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2019-05-21treewide: Add SPDX license identifier - Makefile/KconfigThomas Gleixner2-0/+2
Add SPDX license identifiers to all Make/Kconfig files which: - Have no license information of any form These files fall under the project license, GPL v2 only. The resulting SPDX license identifier is: GPL-2.0-only Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2019-05-21treewide: Add SPDX license identifier for more missed filesThomas Gleixner1-0/+1
Add SPDX license identifiers to all files which: - Have no license information of any form - Have MODULE_LICENCE("GPL*") inside which was used in the initial scan/conversion to ignore the file These files fall under the project license, GPL v2 only. The resulting SPDX license identifier is: GPL-2.0-only Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2019-05-21treewide: Add SPDX license identifier for missed filesThomas Gleixner2-0/+2
Add SPDX license identifiers to all files which: - Have no license information of any form - Have EXPORT_.*_SYMBOL_GPL inside which was used in the initial scan/conversion to ignore the file These files fall under the project license, GPL v2 only. The resulting SPDX license identifier is: GPL-2.0-only Signed-off-by: Thomas Gleixner <tglx@linutronix.de> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
2019-05-15lib/math: move int_pow() from pwm_bl.c for wider useAndy Shevchenko2-1/+33
The integer exponentiation is used in few places and might be used in the future by other call sites. Move it to wider use. Link: http://lkml.kernel.org/r/20190323172531.80025-2-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Daniel Thompson <daniel.thompson@linaro.org> Cc: Lee Jones <lee.jones@linaro.org> Cc: Ray Jui <rjui@broadcom.com> Cc: Thierry Reding <thierry.reding@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2019-05-15lib: Move mathematic helpers to separate folderAndy Shevchenko10-0/+928
For better maintenance and expansion move the mathematic helpers to the separate folder. No functional change intended. Note, the int_sqrt() is not used as a part of lib, so, moved to regular obj. Link: http://lkml.kernel.org/r/20190323172531.80025-1-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Signed-off-by: Mauro Carvalho Chehab <mchehab+samsung@kernel.org> Cc: Randy Dunlap <rdunlap@infradead.org> Cc: Thierry Reding <thierry.reding@gmail.com> Cc: Lee Jones <lee.jones@linaro.org> Cc: Daniel Thompson <daniel.thompson@linaro.org> Cc: Ray Jui <rjui@broadcom.com> [mchehab+samsung@kernel.org: fix broken doc references for div64.c and gcd.c] Link: http://lkml.kernel.org/r/734f49bae5d4052b3c25691dfefad59bea2e5843.1555580999.git.mchehab+samsung@kernel.org Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
generated by cgit v1.2.3 (git 2.39.0) at 2024-12-28 05:44:06 +0300