summaryrefslogtreecommitdiff
path: root/lib/math
diff options
context:
space:
mode:
Diffstat (limited to 'lib/math')
-rw-r--r--lib/math/Makefile4
-rw-r--r--lib/math/div64.c104
-rw-r--r--lib/math/prime_numbers.c94
-rw-r--r--lib/math/prime_numbers_private.h16
-rw-r--r--lib/math/rational.c1
-rw-r--r--lib/math/test_div64.c85
-rw-r--r--lib/math/test_mul_u64_u64_div_u64.c99
-rw-r--r--lib/math/tests/Makefile8
-rw-r--r--lib/math/tests/gcd_kunit.c56
-rw-r--r--lib/math/tests/int_log_kunit.c74
-rw-r--r--lib/math/tests/int_pow_kunit.c52
-rw-r--r--lib/math/tests/int_sqrt_kunit.c66
-rw-r--r--lib/math/tests/prime_numbers_kunit.c59
-rw-r--r--lib/math/tests/rational_kunit.c (renamed from lib/math/rational-test.c)1
14 files changed, 612 insertions, 107 deletions
diff --git a/lib/math/Makefile b/lib/math/Makefile
index 91fcdb0c9efe..d1caba23baa0 100644
--- a/lib/math/Makefile
+++ b/lib/math/Makefile
@@ -6,4 +6,6 @@ obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o
obj-$(CONFIG_RATIONAL) += rational.o
obj-$(CONFIG_TEST_DIV64) += test_div64.o
-obj-$(CONFIG_RATIONAL_KUNIT_TEST) += rational-test.o
+obj-$(CONFIG_TEST_MULDIV64) += test_mul_u64_u64_div_u64.o
+
+obj-y += tests/
diff --git a/lib/math/div64.c b/lib/math/div64.c
index 55a81782e271..5faa29208bdb 100644
--- a/lib/math/div64.c
+++ b/lib/math/div64.c
@@ -22,6 +22,7 @@
#include <linux/export.h>
#include <linux/math.h>
#include <linux/math64.h>
+#include <linux/minmax.h>
#include <linux/log2.h>
/* Not needed on 64bit architectures */
@@ -185,41 +186,84 @@ EXPORT_SYMBOL(iter_div_u64_rem);
#ifndef mul_u64_u64_div_u64
u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 c)
{
- u64 res = 0, div, rem;
- int shift;
+ if (ilog2(a) + ilog2(b) <= 62)
+ return div64_u64(a * b, c);
- /* can a * b overflow ? */
- if (ilog2(a) + ilog2(b) > 62) {
+#if defined(__SIZEOF_INT128__)
+
+ /* native 64x64=128 bits multiplication */
+ u128 prod = (u128)a * b;
+ u64 n_lo = prod, n_hi = prod >> 64;
+
+#else
+
+ /* perform a 64x64=128 bits multiplication manually */
+ u32 a_lo = a, a_hi = a >> 32, b_lo = b, b_hi = b >> 32;
+ u64 x, y, z;
+
+ x = (u64)a_lo * b_lo;
+ y = (u64)a_lo * b_hi + (u32)(x >> 32);
+ z = (u64)a_hi * b_hi + (u32)(y >> 32);
+ y = (u64)a_hi * b_lo + (u32)y;
+ z += (u32)(y >> 32);
+ x = (y << 32) + (u32)x;
+
+ u64 n_lo = x, n_hi = z;
+
+#endif
+
+ /* make sure c is not zero, trigger exception otherwise */
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wdiv-by-zero"
+ if (unlikely(c == 0))
+ return 1/0;
+#pragma GCC diagnostic pop
+
+ int shift = __builtin_ctzll(c);
+
+ /* try reducing the fraction in case the dividend becomes <= 64 bits */
+ if ((n_hi >> shift) == 0) {
+ u64 n = shift ? (n_lo >> shift) | (n_hi << (64 - shift)) : n_lo;
+
+ return div64_u64(n, c >> shift);
/*
- * (b * a) / c is equal to
- *
- * (b / c) * a +
- * (b % c) * a / c
- *
- * if nothing overflows. Can the 1st multiplication
- * overflow? Yes, but we do not care: this can only
- * happen if the end result can't fit in u64 anyway.
- *
- * So the code below does
- *
- * res = (b / c) * a;
- * b = b % c;
+ * The remainder value if needed would be:
+ * res = div64_u64_rem(n, c >> shift, &rem);
+ * rem = (rem << shift) + (n_lo - (n << shift));
*/
- div = div64_u64_rem(b, c, &rem);
- res = div * a;
- b = rem;
-
- shift = ilog2(a) + ilog2(b) - 62;
- if (shift > 0) {
- /* drop precision */
- b >>= shift;
- c >>= shift;
- if (!c)
- return res;
- }
}
- return res + div64_u64(a * b, c);
+ if (n_hi >= c) {
+ /* overflow: result is unrepresentable in a u64 */
+ return -1;
+ }
+
+ /* Do the full 128 by 64 bits division */
+
+ shift = __builtin_clzll(c);
+ c <<= shift;
+
+ int p = 64 + shift;
+ u64 res = 0;
+ bool carry;
+
+ do {
+ carry = n_hi >> 63;
+ shift = carry ? 1 : __builtin_clzll(n_hi);
+ if (p < shift)
+ break;
+ p -= shift;
+ n_hi <<= shift;
+ n_hi |= n_lo >> (64 - shift);
+ n_lo <<= shift;
+ if (carry || (n_hi >= c)) {
+ n_hi -= c;
+ res |= 1ULL << p;
+ }
+ } while (n_hi);
+ /* The remainder value if needed would be n_hi << p */
+
+ return res;
}
EXPORT_SYMBOL(mul_u64_u64_div_u64);
#endif
diff --git a/lib/math/prime_numbers.c b/lib/math/prime_numbers.c
index d42cebf7407f..95a6f7960db9 100644
--- a/lib/math/prime_numbers.c
+++ b/lib/math/prime_numbers.c
@@ -1,18 +1,11 @@
// SPDX-License-Identifier: GPL-2.0-only
-#define pr_fmt(fmt) "prime numbers: " fmt
#include <linux/module.h>
#include <linux/mutex.h>
#include <linux/prime_numbers.h>
#include <linux/slab.h>
-#define bitmap_size(nbits) (BITS_TO_LONGS(nbits) * sizeof(unsigned long))
-
-struct primes {
- struct rcu_head rcu;
- unsigned long last, sz;
- unsigned long primes[];
-};
+#include "prime_numbers_private.h"
#if BITS_PER_LONG == 64
static const struct primes small_primes = {
@@ -64,9 +57,25 @@ static const struct primes small_primes = {
static DEFINE_MUTEX(lock);
static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes);
-static unsigned long selftest_max;
+#if IS_ENABLED(CONFIG_PRIME_NUMBERS_KUNIT_TEST)
+/*
+ * Calls the callback under RCU lock. The callback must not retain
+ * the primes pointer.
+ */
+void with_primes(void *ctx, primes_fn fn)
+{
+ rcu_read_lock();
+ fn(ctx, rcu_dereference(primes));
+ rcu_read_unlock();
+}
+EXPORT_SYMBOL(with_primes);
+
+EXPORT_SYMBOL(slow_is_prime_number);
-static bool slow_is_prime_number(unsigned long x)
+#else
+static
+#endif
+bool slow_is_prime_number(unsigned long x)
{
unsigned long y = int_sqrt(x);
@@ -241,76 +250,13 @@ bool is_prime_number(unsigned long x)
}
EXPORT_SYMBOL(is_prime_number);
-static void dump_primes(void)
-{
- const struct primes *p;
- char *buf;
-
- buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
-
- rcu_read_lock();
- p = rcu_dereference(primes);
-
- if (buf)
- bitmap_print_to_pagebuf(true, buf, p->primes, p->sz);
- pr_info("primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s\n",
- p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf);
-
- rcu_read_unlock();
-
- kfree(buf);
-}
-
-static int selftest(unsigned long max)
-{
- unsigned long x, last;
-
- if (!max)
- return 0;
-
- for (last = 0, x = 2; x < max; x++) {
- bool slow = slow_is_prime_number(x);
- bool fast = is_prime_number(x);
-
- if (slow != fast) {
- pr_err("inconsistent result for is-prime(%lu): slow=%s, fast=%s!\n",
- x, slow ? "yes" : "no", fast ? "yes" : "no");
- goto err;
- }
-
- if (!slow)
- continue;
-
- if (next_prime_number(last) != x) {
- pr_err("incorrect result for next-prime(%lu): expected %lu, got %lu\n",
- last, x, next_prime_number(last));
- goto err;
- }
- last = x;
- }
-
- pr_info("%s(%lu) passed, last prime was %lu\n", __func__, x, last);
- return 0;
-
-err:
- dump_primes();
- return -EINVAL;
-}
-
-static int __init primes_init(void)
-{
- return selftest(selftest_max);
-}
-
static void __exit primes_exit(void)
{
free_primes();
}
-module_init(primes_init);
module_exit(primes_exit);
-module_param_named(selftest, selftest_max, ulong, 0400);
-
MODULE_AUTHOR("Intel Corporation");
+MODULE_DESCRIPTION("Prime number library");
MODULE_LICENSE("GPL");
diff --git a/lib/math/prime_numbers_private.h b/lib/math/prime_numbers_private.h
new file mode 100644
index 000000000000..f3ebf5386e6b
--- /dev/null
+++ b/lib/math/prime_numbers_private.h
@@ -0,0 +1,16 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#include <linux/types.h>
+
+struct primes {
+ struct rcu_head rcu;
+ unsigned long last, sz;
+ unsigned long primes[];
+};
+
+#if IS_ENABLED(CONFIG_PRIME_NUMBERS_KUNIT_TEST)
+typedef void (*primes_fn)(void *, const struct primes *);
+
+void with_primes(void *ctx, primes_fn fn);
+bool slow_is_prime_number(unsigned long x);
+#endif
diff --git a/lib/math/rational.c b/lib/math/rational.c
index ec59d426ea63..d2c34e629ee1 100644
--- a/lib/math/rational.c
+++ b/lib/math/rational.c
@@ -108,4 +108,5 @@ void rational_best_approximation(
EXPORT_SYMBOL(rational_best_approximation);
+MODULE_DESCRIPTION("Rational fraction support library");
MODULE_LICENSE("GPL v2");
diff --git a/lib/math/test_div64.c b/lib/math/test_div64.c
index c15edd688dd2..3cd699b654d9 100644
--- a/lib/math/test_div64.c
+++ b/lib/math/test_div64.c
@@ -26,6 +26,9 @@ static const u64 test_div64_dividends[] = {
0x0072db27380dd689,
0x0842f488162e2284,
0xf66745411d8ab063,
+ 0xfffffffffffffffb,
+ 0xfffffffffffffffc,
+ 0xffffffffffffffff,
};
#define SIZE_DIV64_DIVIDENDS ARRAY_SIZE(test_div64_dividends)
@@ -37,7 +40,10 @@ static const u64 test_div64_dividends[] = {
#define TEST_DIV64_DIVISOR_5 0x0008a880
#define TEST_DIV64_DIVISOR_6 0x003fd3ae
#define TEST_DIV64_DIVISOR_7 0x0b658fac
-#define TEST_DIV64_DIVISOR_8 0xdc08b349
+#define TEST_DIV64_DIVISOR_8 0x80000001
+#define TEST_DIV64_DIVISOR_9 0xdc08b349
+#define TEST_DIV64_DIVISOR_A 0xfffffffe
+#define TEST_DIV64_DIVISOR_B 0xffffffff
static const u32 test_div64_divisors[] = {
TEST_DIV64_DIVISOR_0,
@@ -49,13 +55,16 @@ static const u32 test_div64_divisors[] = {
TEST_DIV64_DIVISOR_6,
TEST_DIV64_DIVISOR_7,
TEST_DIV64_DIVISOR_8,
+ TEST_DIV64_DIVISOR_9,
+ TEST_DIV64_DIVISOR_A,
+ TEST_DIV64_DIVISOR_B,
};
#define SIZE_DIV64_DIVISORS ARRAY_SIZE(test_div64_divisors)
static const struct {
u64 quotient;
u32 remainder;
-} test_div64_results[SIZE_DIV64_DIVISORS][SIZE_DIV64_DIVIDENDS] = {
+} test_div64_results[SIZE_DIV64_DIVIDENDS][SIZE_DIV64_DIVISORS] = {
{
{ 0x0000000013045e47, 0x00000001 },
{ 0x000000000161596c, 0x00000030 },
@@ -65,6 +74,9 @@ static const struct {
{ 0x00000000000013c4, 0x0004ce80 },
{ 0x00000000000002ae, 0x001e143c },
{ 0x000000000000000f, 0x0033e56c },
+ { 0x0000000000000001, 0x2b27507f },
+ { 0x0000000000000000, 0xab275080 },
+ { 0x0000000000000000, 0xab275080 },
{ 0x0000000000000000, 0xab275080 },
}, {
{ 0x00000001c45c02d1, 0x00000000 },
@@ -75,7 +87,10 @@ static const struct {
{ 0x000000000001d637, 0x0004e5d9 },
{ 0x0000000000003fc9, 0x000713bb },
{ 0x0000000000000165, 0x029abe7d },
+ { 0x000000000000001f, 0x673c193a },
{ 0x0000000000000012, 0x6e9f7e37 },
+ { 0x000000000000000f, 0xe73c1977 },
+ { 0x000000000000000f, 0xe73c1968 },
}, {
{ 0x000000197a3a0cf7, 0x00000002 },
{ 0x00000001d9632e5c, 0x00000021 },
@@ -85,7 +100,10 @@ static const struct {
{ 0x00000000001a7bb3, 0x00072331 },
{ 0x00000000000397ad, 0x0002c61b },
{ 0x000000000000141e, 0x06ea2e89 },
+ { 0x00000000000001ca, 0x4c0a72e7 },
{ 0x000000000000010a, 0xab002ad7 },
+ { 0x00000000000000e5, 0x4c0a767b },
+ { 0x00000000000000e5, 0x4c0a7596 },
}, {
{ 0x0000017949e37538, 0x00000001 },
{ 0x0000001b62441f37, 0x00000055 },
@@ -95,7 +113,10 @@ static const struct {
{ 0x0000000001882ec6, 0x0005cbf9 },
{ 0x000000000035333b, 0x0017abdf },
{ 0x00000000000129f1, 0x0ab4520d },
+ { 0x0000000000001a87, 0x18ff0472 },
{ 0x0000000000000f6e, 0x8ac0ce9b },
+ { 0x0000000000000d43, 0x98ff397f },
+ { 0x0000000000000d43, 0x98ff2c3c },
}, {
{ 0x000011f321a74e49, 0x00000006 },
{ 0x0000014d8481d211, 0x0000005b },
@@ -105,7 +126,10 @@ static const struct {
{ 0x0000000012a88828, 0x00036c97 },
{ 0x000000000287f16f, 0x002c2a25 },
{ 0x00000000000e2cc7, 0x02d581e3 },
+ { 0x0000000000014318, 0x2ee07d7f },
{ 0x000000000000bbf4, 0x1ba08c03 },
+ { 0x000000000000a18c, 0x2ee303af },
+ { 0x000000000000a18c, 0x2ee26223 },
}, {
{ 0x0000d8db8f72935d, 0x00000005 },
{ 0x00000fbd5aed7a2e, 0x00000002 },
@@ -115,7 +139,10 @@ static const struct {
{ 0x00000000e16b20fa, 0x0002a14a },
{ 0x000000001e940d22, 0x00353b2e },
{ 0x0000000000ab40ac, 0x06fba6ba },
+ { 0x00000000000f3f70, 0x0af7eeda },
{ 0x000000000008debd, 0x72d98365 },
+ { 0x0000000000079fb8, 0x0b166dba },
+ { 0x0000000000079fb8, 0x0b0ece02 },
}, {
{ 0x000cc3045b8fc281, 0x00000000 },
{ 0x0000ed1f48b5c9fc, 0x00000079 },
@@ -125,7 +152,10 @@ static const struct {
{ 0x0000000d43fce827, 0x00082b09 },
{ 0x00000001ccaba11a, 0x0037e8dd },
{ 0x000000000a13f729, 0x0566dffd },
+ { 0x0000000000e5b64e, 0x3728203b },
{ 0x000000000085a14b, 0x23d36726 },
+ { 0x000000000072db27, 0x38f38cd7 },
+ { 0x000000000072db27, 0x3880b1b0 },
}, {
{ 0x00eafeb9c993592b, 0x00000001 },
{ 0x00110e5befa9a991, 0x00000048 },
@@ -135,7 +165,10 @@ static const struct {
{ 0x000000f4459740fc, 0x00084484 },
{ 0x0000002122c47bf9, 0x002ca446 },
{ 0x00000000b9936290, 0x004979c4 },
+ { 0x000000001085e910, 0x05a83974 },
{ 0x00000000099ca89d, 0x9db446bf },
+ { 0x000000000842f488, 0x26b40b94 },
+ { 0x000000000842f488, 0x1e71170c },
}, {
{ 0x1b60cece589da1d2, 0x00000001 },
{ 0x01fcb42be1453f5b, 0x0000004f },
@@ -145,7 +178,49 @@ static const struct {
{ 0x00001c757dfab350, 0x00048863 },
{ 0x000003dc4979c652, 0x00224ea7 },
{ 0x000000159edc3144, 0x06409ab3 },
+ { 0x00000001ecce8a7e, 0x30bc25e5 },
{ 0x000000011eadfee3, 0xa99c48a8 },
+ { 0x00000000f6674543, 0x0a593ae9 },
+ { 0x00000000f6674542, 0x13f1f5a5 },
+ }, {
+ { 0x1c71c71c71c71c71, 0x00000002 },
+ { 0x0210842108421084, 0x0000000b },
+ { 0x007f01fc07f01fc0, 0x000000fb },
+ { 0x00014245eabf1f9a, 0x0000a63d },
+ { 0x0000ffffffffffff, 0x0000fffb },
+ { 0x00001d913cecc509, 0x0007937b },
+ { 0x00000402c70c678f, 0x0005bfc9 },
+ { 0x00000016766cb70b, 0x045edf97 },
+ { 0x00000001fffffffb, 0x80000000 },
+ { 0x0000000129d84b3a, 0xa2e8fe71 },
+ { 0x0000000100000001, 0xfffffffd },
+ { 0x0000000100000000, 0xfffffffb },
+ }, {
+ { 0x1c71c71c71c71c71, 0x00000003 },
+ { 0x0210842108421084, 0x0000000c },
+ { 0x007f01fc07f01fc0, 0x000000fc },
+ { 0x00014245eabf1f9a, 0x0000a63e },
+ { 0x0000ffffffffffff, 0x0000fffc },
+ { 0x00001d913cecc509, 0x0007937c },
+ { 0x00000402c70c678f, 0x0005bfca },
+ { 0x00000016766cb70b, 0x045edf98 },
+ { 0x00000001fffffffc, 0x00000000 },
+ { 0x0000000129d84b3a, 0xa2e8fe72 },
+ { 0x0000000100000002, 0x00000000 },
+ { 0x0000000100000000, 0xfffffffc },
+ }, {
+ { 0x1c71c71c71c71c71, 0x00000006 },
+ { 0x0210842108421084, 0x0000000f },
+ { 0x007f01fc07f01fc0, 0x000000ff },
+ { 0x00014245eabf1f9a, 0x0000a641 },
+ { 0x0000ffffffffffff, 0x0000ffff },
+ { 0x00001d913cecc509, 0x0007937f },
+ { 0x00000402c70c678f, 0x0005bfcd },
+ { 0x00000016766cb70b, 0x045edf9b },
+ { 0x00000001fffffffc, 0x00000003 },
+ { 0x0000000129d84b3a, 0xa2e8fe75 },
+ { 0x0000000100000002, 0x00000003 },
+ { 0x0000000100000001, 0x00000000 },
},
};
@@ -208,6 +283,12 @@ static bool __init test_div64(void)
return false;
if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_8, i, 8))
return false;
+ if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_9, i, 9))
+ return false;
+ if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_A, i, 10))
+ return false;
+ if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_B, i, 11))
+ return false;
for (j = 0; j < SIZE_DIV64_DIVISORS; j++) {
if (!test_div64_one(dividend, test_div64_divisors[j],
i, j))
diff --git a/lib/math/test_mul_u64_u64_div_u64.c b/lib/math/test_mul_u64_u64_div_u64.c
new file mode 100644
index 000000000000..58d058de4e73
--- /dev/null
+++ b/lib/math/test_mul_u64_u64_div_u64.c
@@ -0,0 +1,99 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright (C) 2024 BayLibre SAS
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/printk.h>
+#include <linux/math64.h>
+
+typedef struct { u64 a; u64 b; u64 c; u64 result; } test_params;
+
+static test_params test_values[] = {
+/* this contains many edge values followed by a couple random values */
+{ 0xb, 0x7, 0x3, 0x19 },
+{ 0xffff0000, 0xffff0000, 0xf, 0x1110eeef00000000 },
+{ 0xffffffff, 0xffffffff, 0x1, 0xfffffffe00000001 },
+{ 0xffffffff, 0xffffffff, 0x2, 0x7fffffff00000000 },
+{ 0x1ffffffff, 0xffffffff, 0x2, 0xfffffffe80000000 },
+{ 0x1ffffffff, 0xffffffff, 0x3, 0xaaaaaaa9aaaaaaab },
+{ 0x1ffffffff, 0x1ffffffff, 0x4, 0xffffffff00000000 },
+{ 0xffff000000000000, 0xffff000000000000, 0xffff000000000001, 0xfffeffffffffffff },
+{ 0x3333333333333333, 0x3333333333333333, 0x5555555555555555, 0x1eb851eb851eb851 },
+{ 0x7fffffffffffffff, 0x2, 0x3, 0x5555555555555554 },
+{ 0xffffffffffffffff, 0x2, 0x8000000000000000, 0x3 },
+{ 0xffffffffffffffff, 0x2, 0xc000000000000000, 0x2 },
+{ 0xffffffffffffffff, 0x4000000000000004, 0x8000000000000000, 0x8000000000000007 },
+{ 0xffffffffffffffff, 0x4000000000000001, 0x8000000000000000, 0x8000000000000001 },
+{ 0xffffffffffffffff, 0x8000000000000001, 0xffffffffffffffff, 0x8000000000000001 },
+{ 0xfffffffffffffffe, 0x8000000000000001, 0xffffffffffffffff, 0x8000000000000000 },
+{ 0xffffffffffffffff, 0x8000000000000001, 0xfffffffffffffffe, 0x8000000000000001 },
+{ 0xffffffffffffffff, 0x8000000000000001, 0xfffffffffffffffd, 0x8000000000000002 },
+{ 0x7fffffffffffffff, 0xffffffffffffffff, 0xc000000000000000, 0xaaaaaaaaaaaaaaa8 },
+{ 0xffffffffffffffff, 0x7fffffffffffffff, 0xa000000000000000, 0xccccccccccccccca },
+{ 0xffffffffffffffff, 0x7fffffffffffffff, 0x9000000000000000, 0xe38e38e38e38e38b },
+{ 0x7fffffffffffffff, 0x7fffffffffffffff, 0x5000000000000000, 0xccccccccccccccc9 },
+{ 0xffffffffffffffff, 0xfffffffffffffffe, 0xffffffffffffffff, 0xfffffffffffffffe },
+{ 0xe6102d256d7ea3ae, 0x70a77d0be4c31201, 0xd63ec35ab3220357, 0x78f8bf8cc86c6e18 },
+{ 0xf53bae05cb86c6e1, 0x3847b32d2f8d32e0, 0xcfd4f55a647f403c, 0x42687f79d8998d35 },
+{ 0x9951c5498f941092, 0x1f8c8bfdf287a251, 0xa3c8dc5f81ea3fe2, 0x1d887cb25900091f },
+{ 0x374fee9daa1bb2bb, 0x0d0bfbff7b8ae3ef, 0xc169337bd42d5179, 0x03bb2dbaffcbb961 },
+{ 0xeac0d03ac10eeaf0, 0x89be05dfa162ed9b, 0x92bb1679a41f0e4b, 0xdc5f5cc9e270d216 },
+};
+
+/*
+ * The above table can be verified with the following shell script:
+ *
+ * #!/bin/sh
+ * sed -ne 's/^{ \+\(.*\), \+\(.*\), \+\(.*\), \+\(.*\) },$/\1 \2 \3 \4/p' \
+ * lib/math/test_mul_u64_u64_div_u64.c |
+ * while read a b c r; do
+ * expected=$( printf "obase=16; ibase=16; %X * %X / %X\n" $a $b $c | bc )
+ * given=$( printf "%X\n" $r )
+ * if [ "$expected" = "$given" ]; then
+ * echo "$a * $b / $c = $r OK"
+ * else
+ * echo "$a * $b / $c = $r is wrong" >&2
+ * echo "should be equivalent to 0x$expected" >&2
+ * exit 1
+ * fi
+ * done
+ */
+
+static int __init test_init(void)
+{
+ int i;
+
+ pr_info("Starting mul_u64_u64_div_u64() test\n");
+
+ for (i = 0; i < ARRAY_SIZE(test_values); i++) {
+ u64 a = test_values[i].a;
+ u64 b = test_values[i].b;
+ u64 c = test_values[i].c;
+ u64 expected_result = test_values[i].result;
+ u64 result = mul_u64_u64_div_u64(a, b, c);
+
+ if (result != expected_result) {
+ pr_err("ERROR: 0x%016llx * 0x%016llx / 0x%016llx\n", a, b, c);
+ pr_err("ERROR: expected result: %016llx\n", expected_result);
+ pr_err("ERROR: obtained result: %016llx\n", result);
+ }
+ }
+
+ pr_info("Completed mul_u64_u64_div_u64() test\n");
+ return 0;
+}
+
+static void __exit test_exit(void)
+{
+}
+
+module_init(test_init);
+module_exit(test_exit);
+
+MODULE_AUTHOR("Nicolas Pitre");
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("mul_u64_u64_div_u64() test module");
diff --git a/lib/math/tests/Makefile b/lib/math/tests/Makefile
new file mode 100644
index 000000000000..13dc96e48408
--- /dev/null
+++ b/lib/math/tests/Makefile
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: GPL-2.0-only
+
+obj-$(CONFIG_GCD_KUNIT_TEST) += gcd_kunit.o
+obj-$(CONFIG_INT_LOG_KUNIT_TEST) += int_log_kunit.o
+obj-$(CONFIG_INT_POW_KUNIT_TEST) += int_pow_kunit.o
+obj-$(CONFIG_INT_SQRT_KUNIT_TEST) += int_sqrt_kunit.o
+obj-$(CONFIG_PRIME_NUMBERS_KUNIT_TEST) += prime_numbers_kunit.o
+obj-$(CONFIG_RATIONAL_KUNIT_TEST) += rational_kunit.o
diff --git a/lib/math/tests/gcd_kunit.c b/lib/math/tests/gcd_kunit.c
new file mode 100644
index 000000000000..ede1883583b1
--- /dev/null
+++ b/lib/math/tests/gcd_kunit.c
@@ -0,0 +1,56 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#include <kunit/test.h>
+#include <linux/gcd.h>
+#include <linux/limits.h>
+
+struct test_case_params {
+ unsigned long val1;
+ unsigned long val2;
+ unsigned long expected_result;
+ const char *name;
+};
+
+static const struct test_case_params params[] = {
+ { 48, 18, 6, "GCD of 48 and 18" },
+ { 18, 48, 6, "GCD of 18 and 48" },
+ { 56, 98, 14, "GCD of 56 and 98" },
+ { 17, 13, 1, "Coprime numbers" },
+ { 101, 103, 1, "Coprime numbers" },
+ { 270, 192, 6, "GCD of 270 and 192" },
+ { 0, 5, 5, "GCD with zero" },
+ { 7, 0, 7, "GCD with zero reversed" },
+ { 36, 36, 36, "GCD of identical numbers" },
+ { ULONG_MAX, 1, 1, "GCD of max ulong and 1" },
+ { ULONG_MAX, ULONG_MAX, ULONG_MAX, "GCD of max ulong values" },
+};
+
+static void get_desc(const struct test_case_params *tc, char *desc)
+{
+ strscpy(desc, tc->name, KUNIT_PARAM_DESC_SIZE);
+}
+
+KUNIT_ARRAY_PARAM(gcd, params, get_desc);
+
+static void gcd_test(struct kunit *test)
+{
+ const struct test_case_params *tc = (const struct test_case_params *)test->param_value;
+
+ KUNIT_EXPECT_EQ(test, tc->expected_result, gcd(tc->val1, tc->val2));
+}
+
+static struct kunit_case math_gcd_test_cases[] = {
+ KUNIT_CASE_PARAM(gcd_test, gcd_gen_params),
+ {}
+};
+
+static struct kunit_suite gcd_test_suite = {
+ .name = "math-gcd",
+ .test_cases = math_gcd_test_cases,
+};
+
+kunit_test_suite(gcd_test_suite);
+
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("math.gcd KUnit test suite");
+MODULE_AUTHOR("Yu-Chun Lin <eleanor15x@gmail.com>");
diff --git a/lib/math/tests/int_log_kunit.c b/lib/math/tests/int_log_kunit.c
new file mode 100644
index 000000000000..14e854146cb4
--- /dev/null
+++ b/lib/math/tests/int_log_kunit.c
@@ -0,0 +1,74 @@
+// SPDX-License-Identifier: GPL-2.0-only
+#include <kunit/test.h>
+#include <linux/int_log.h>
+
+struct test_case_params {
+ u32 value;
+ unsigned int expected_result;
+ const char *name;
+};
+
+
+/* The expected result takes into account the log error */
+static const struct test_case_params intlog2_params[] = {
+ {0, 0, "Log base 2 of 0"},
+ {1, 0, "Log base 2 of 1"},
+ {2, 16777216, "Log base 2 of 2"},
+ {3, 26591232, "Log base 2 of 3"},
+ {4, 33554432, "Log base 2 of 4"},
+ {8, 50331648, "Log base 2 of 8"},
+ {16, 67108864, "Log base 2 of 16"},
+ {32, 83886080, "Log base 2 of 32"},
+ {U32_MAX, 536870911, "Log base 2 of MAX"},
+};
+
+static const struct test_case_params intlog10_params[] = {
+ {0, 0, "Log base 10 of 0"},
+ {1, 0, "Log base 10 of 1"},
+ {6, 13055203, "Log base 10 of 6"},
+ {10, 16777225, "Log base 10 of 10"},
+ {100, 33554450, "Log base 10 of 100"},
+ {1000, 50331675, "Log base 10 of 1000"},
+ {10000, 67108862, "Log base 10 of 10000"},
+ {U32_MAX, 161614247, "Log base 10 of MAX"}
+};
+
+static void get_desc(const struct test_case_params *tc, char *desc)
+{
+ strscpy(desc, tc->name, KUNIT_PARAM_DESC_SIZE);
+}
+
+
+KUNIT_ARRAY_PARAM(intlog2, intlog2_params, get_desc);
+
+static void intlog2_test(struct kunit *test)
+{
+ const struct test_case_params *tc = (const struct test_case_params *)test->param_value;
+
+ KUNIT_EXPECT_EQ(test, tc->expected_result, intlog2(tc->value));
+}
+
+KUNIT_ARRAY_PARAM(intlog10, intlog10_params, get_desc);
+
+static void intlog10_test(struct kunit *test)
+{
+ const struct test_case_params *tc = (const struct test_case_params *)test->param_value;
+
+ KUNIT_EXPECT_EQ(test, tc->expected_result, intlog10(tc->value));
+}
+
+static struct kunit_case math_int_log_test_cases[] = {
+ KUNIT_CASE_PARAM(intlog2_test, intlog2_gen_params),
+ KUNIT_CASE_PARAM(intlog10_test, intlog10_gen_params),
+ {}
+};
+
+static struct kunit_suite int_log_test_suite = {
+ .name = "math-int_log",
+ .test_cases = math_int_log_test_cases,
+};
+
+kunit_test_suites(&int_log_test_suite);
+
+MODULE_DESCRIPTION("math.int_log KUnit test suite");
+MODULE_LICENSE("GPL");
diff --git a/lib/math/tests/int_pow_kunit.c b/lib/math/tests/int_pow_kunit.c
new file mode 100644
index 000000000000..34b33677d458
--- /dev/null
+++ b/lib/math/tests/int_pow_kunit.c
@@ -0,0 +1,52 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#include <kunit/test.h>
+#include <linux/math.h>
+
+struct test_case_params {
+ u64 base;
+ unsigned int exponent;
+ u64 expected_result;
+ const char *name;
+};
+
+static const struct test_case_params params[] = {
+ { 64, 0, 1, "Power of zero" },
+ { 64, 1, 64, "Power of one"},
+ { 0, 5, 0, "Base zero" },
+ { 1, 64, 1, "Base one" },
+ { 2, 2, 4, "Two squared"},
+ { 2, 3, 8, "Two cubed"},
+ { 5, 5, 3125, "Five raised to the fifth power" },
+ { U64_MAX, 1, U64_MAX, "Max base" },
+ { 2, 63, 9223372036854775808ULL, "Large result"},
+};
+
+static void get_desc(const struct test_case_params *tc, char *desc)
+{
+ strscpy(desc, tc->name, KUNIT_PARAM_DESC_SIZE);
+}
+
+KUNIT_ARRAY_PARAM(int_pow, params, get_desc);
+
+static void int_pow_test(struct kunit *test)
+{
+ const struct test_case_params *tc = (const struct test_case_params *)test->param_value;
+
+ KUNIT_EXPECT_EQ(test, tc->expected_result, int_pow(tc->base, tc->exponent));
+}
+
+static struct kunit_case math_int_pow_test_cases[] = {
+ KUNIT_CASE_PARAM(int_pow_test, int_pow_gen_params),
+ {}
+};
+
+static struct kunit_suite int_pow_test_suite = {
+ .name = "math-int_pow",
+ .test_cases = math_int_pow_test_cases,
+};
+
+kunit_test_suites(&int_pow_test_suite);
+
+MODULE_DESCRIPTION("math.int_pow KUnit test suite");
+MODULE_LICENSE("GPL");
diff --git a/lib/math/tests/int_sqrt_kunit.c b/lib/math/tests/int_sqrt_kunit.c
new file mode 100644
index 000000000000..1798e1312eb7
--- /dev/null
+++ b/lib/math/tests/int_sqrt_kunit.c
@@ -0,0 +1,66 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#include <kunit/test.h>
+#include <linux/limits.h>
+#include <linux/math.h>
+#include <linux/module.h>
+#include <linux/string.h>
+
+struct test_case_params {
+ unsigned long x;
+ unsigned long expected_result;
+ const char *name;
+};
+
+static const struct test_case_params params[] = {
+ { 0, 0, "edge case: square root of 0" },
+ { 1, 1, "perfect square: square root of 1" },
+ { 2, 1, "non-perfect square: square root of 2" },
+ { 3, 1, "non-perfect square: square root of 3" },
+ { 4, 2, "perfect square: square root of 4" },
+ { 5, 2, "non-perfect square: square root of 5" },
+ { 6, 2, "non-perfect square: square root of 6" },
+ { 7, 2, "non-perfect square: square root of 7" },
+ { 8, 2, "non-perfect square: square root of 8" },
+ { 9, 3, "perfect square: square root of 9" },
+ { 15, 3, "non-perfect square: square root of 15 (N-1 from 16)" },
+ { 16, 4, "perfect square: square root of 16" },
+ { 17, 4, "non-perfect square: square root of 17 (N+1 from 16)" },
+ { 80, 8, "non-perfect square: square root of 80 (N-1 from 81)" },
+ { 81, 9, "perfect square: square root of 81" },
+ { 82, 9, "non-perfect square: square root of 82 (N+1 from 81)" },
+ { 255, 15, "non-perfect square: square root of 255 (N-1 from 256)" },
+ { 256, 16, "perfect square: square root of 256" },
+ { 257, 16, "non-perfect square: square root of 257 (N+1 from 256)" },
+ { 2147483648, 46340, "large input: square root of 2147483648" },
+ { 4294967295, 65535, "edge case: ULONG_MAX for 32-bit" },
+};
+
+static void get_desc(const struct test_case_params *tc, char *desc)
+{
+ strscpy(desc, tc->name, KUNIT_PARAM_DESC_SIZE);
+}
+
+KUNIT_ARRAY_PARAM(int_sqrt, params, get_desc);
+
+static void int_sqrt_test(struct kunit *test)
+{
+ const struct test_case_params *tc = (const struct test_case_params *)test->param_value;
+
+ KUNIT_EXPECT_EQ(test, tc->expected_result, int_sqrt(tc->x));
+}
+
+static struct kunit_case math_int_sqrt_test_cases[] = {
+ KUNIT_CASE_PARAM(int_sqrt_test, int_sqrt_gen_params),
+ {}
+};
+
+static struct kunit_suite int_sqrt_test_suite = {
+ .name = "math-int_sqrt",
+ .test_cases = math_int_sqrt_test_cases,
+};
+
+kunit_test_suites(&int_sqrt_test_suite);
+
+MODULE_DESCRIPTION("math.int_sqrt KUnit test suite");
+MODULE_LICENSE("GPL");
diff --git a/lib/math/tests/prime_numbers_kunit.c b/lib/math/tests/prime_numbers_kunit.c
new file mode 100644
index 000000000000..2f1643208c66
--- /dev/null
+++ b/lib/math/tests/prime_numbers_kunit.c
@@ -0,0 +1,59 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#include <kunit/test.h>
+#include <linux/module.h>
+#include <linux/prime_numbers.h>
+
+#include "../prime_numbers_private.h"
+
+static void dump_primes(void *ctx, const struct primes *p)
+{
+ static char buf[PAGE_SIZE];
+ struct kunit_suite *suite = ctx;
+
+ bitmap_print_to_pagebuf(true, buf, p->primes, p->sz);
+ kunit_info(suite, "primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s",
+ p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf);
+}
+
+static void prime_numbers_test(struct kunit *test)
+{
+ const unsigned long max = 65536;
+ unsigned long x, last, next;
+
+ for (last = 0, x = 2; x < max; x++) {
+ const bool slow = slow_is_prime_number(x);
+ const bool fast = is_prime_number(x);
+
+ KUNIT_ASSERT_EQ_MSG(test, slow, fast, "is-prime(%lu)", x);
+
+ if (!slow)
+ continue;
+
+ next = next_prime_number(last);
+ KUNIT_ASSERT_EQ_MSG(test, next, x, "next-prime(%lu)", last);
+ last = next;
+ }
+}
+
+static void kunit_suite_exit(struct kunit_suite *suite)
+{
+ with_primes(suite, dump_primes);
+}
+
+static struct kunit_case prime_numbers_cases[] = {
+ KUNIT_CASE(prime_numbers_test),
+ {},
+};
+
+static struct kunit_suite prime_numbers_suite = {
+ .name = "math-prime_numbers",
+ .suite_exit = kunit_suite_exit,
+ .test_cases = prime_numbers_cases,
+};
+
+kunit_test_suite(prime_numbers_suite);
+
+MODULE_AUTHOR("Intel Corporation");
+MODULE_DESCRIPTION("Prime number library");
+MODULE_LICENSE("GPL");
diff --git a/lib/math/rational-test.c b/lib/math/tests/rational_kunit.c
index 01611ddff420..47486a95f088 100644
--- a/lib/math/rational-test.c
+++ b/lib/math/tests/rational_kunit.c
@@ -53,4 +53,5 @@ static struct kunit_suite rational_test_suite = {
kunit_test_suites(&rational_test_suite);
+MODULE_DESCRIPTION("Rational fractions unit test");
MODULE_LICENSE("GPL v2");
generated by cgit (git 2.34.1) at 2025-07-28 14:29:19 +0000