test_mul_u64_u64_div_u64.c

  1// SPDX-License-Identifier: GPL-2.0
  2/*
  3 * Copyright (C) 2024 BayLibre SAS
  4 */
  5
  6#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
  7
  8#include <linux/init.h>
  9#include <linux/module.h>
 10#include <linux/printk.h>
 11#include <linux/math64.h>
 12
 13typedef struct { u64 a; u64 b; u64 d; u64 result; uint round_up;} test_params;
 14
 15static test_params test_values[] = {
 16/* this contains many edge values followed by a couple random values */
 17{                0xb,                0x7,                0x3,               0x19, 1 },
 18{         0xffff0000,         0xffff0000,                0xf, 0x1110eeef00000000, 0 },
 19{         0xffffffff,         0xffffffff,                0x1, 0xfffffffe00000001, 0 },
 20{         0xffffffff,         0xffffffff,                0x2, 0x7fffffff00000000, 1 },
 21{        0x1ffffffff,         0xffffffff,                0x2, 0xfffffffe80000000, 1 },
 22{        0x1ffffffff,         0xffffffff,                0x3, 0xaaaaaaa9aaaaaaab, 0 },
 23{        0x1ffffffff,        0x1ffffffff,                0x4, 0xffffffff00000000, 1 },
 24{ 0xffff000000000000, 0xffff000000000000, 0xffff000000000001, 0xfffeffffffffffff, 1 },
 25{ 0x3333333333333333, 0x3333333333333333, 0x5555555555555555, 0x1eb851eb851eb851, 1 },
 26{ 0x7fffffffffffffff,                0x2,                0x3, 0x5555555555555554, 1 },
 27{ 0xffffffffffffffff,                0x2, 0x8000000000000000,                0x3, 1 },
 28{ 0xffffffffffffffff,                0x2, 0xc000000000000000,                0x2, 1 },
 29{ 0xffffffffffffffff, 0x4000000000000004, 0x8000000000000000, 0x8000000000000007, 1 },
 30{ 0xffffffffffffffff, 0x4000000000000001, 0x8000000000000000, 0x8000000000000001, 1 },
 31{ 0xffffffffffffffff, 0x8000000000000001, 0xffffffffffffffff, 0x8000000000000001, 0 },
 32{ 0xfffffffffffffffe, 0x8000000000000001, 0xffffffffffffffff, 0x8000000000000000, 1 },
 33{ 0xffffffffffffffff, 0x8000000000000001, 0xfffffffffffffffe, 0x8000000000000001, 1 },
 34{ 0xffffffffffffffff, 0x8000000000000001, 0xfffffffffffffffd, 0x8000000000000002, 1 },
 35{ 0x7fffffffffffffff, 0xffffffffffffffff, 0xc000000000000000, 0xaaaaaaaaaaaaaaa8, 1 },
 36{ 0xffffffffffffffff, 0x7fffffffffffffff, 0xa000000000000000, 0xccccccccccccccca, 1 },
 37{ 0xffffffffffffffff, 0x7fffffffffffffff, 0x9000000000000000, 0xe38e38e38e38e38b, 1 },
 38{ 0x7fffffffffffffff, 0x7fffffffffffffff, 0x5000000000000000, 0xccccccccccccccc9, 1 },
 39{ 0xffffffffffffffff, 0xfffffffffffffffe, 0xffffffffffffffff, 0xfffffffffffffffe, 0 },
 40{ 0xe6102d256d7ea3ae, 0x70a77d0be4c31201, 0xd63ec35ab3220357, 0x78f8bf8cc86c6e18, 1 },
 41{ 0xf53bae05cb86c6e1, 0x3847b32d2f8d32e0, 0xcfd4f55a647f403c, 0x42687f79d8998d35, 1 },
 42{ 0x9951c5498f941092, 0x1f8c8bfdf287a251, 0xa3c8dc5f81ea3fe2, 0x1d887cb25900091f, 1 },
 43{ 0x374fee9daa1bb2bb, 0x0d0bfbff7b8ae3ef, 0xc169337bd42d5179, 0x03bb2dbaffcbb961, 1 },
 44{ 0xeac0d03ac10eeaf0, 0x89be05dfa162ed9b, 0x92bb1679a41f0e4b, 0xdc5f5cc9e270d216, 1 },
 45};
 46
 47/*
 48 * The above table can be verified with the following shell script:
 49
 50#!/bin/sh
 51sed -ne 's/^{ \+\(.*\), \+\(.*\), \+\(.*\), \+\(.*\), \+\(.*\) },$/\1 \2 \3 \4 \5/p' \
 52    lib/math/test_mul_u64_u64_div_u64.c |
 53while read a b d r e; do
 54  expected=$( printf "obase=16; ibase=16; %X * %X / %X\n" $a $b $d | bc )
 55  given=$( printf "%X\n" $r )
 56  if [ "$expected" = "$given" ]; then
 57    echo "$a * $b  / $d = $r OK"
 58  else
 59    echo "$a * $b  / $d = $r is wrong" >&2
 60    echo "should be equivalent to 0x$expected" >&2
 61    exit 1
 62  fi
 63  expected=$( printf "obase=16; ibase=16; (%X * %X + %X) / %X\n" $a $b $((d-1)) $d | bc )
 64  given=$( printf "%X\n" $((r + e)) )
 65  if [ "$expected" = "$given" ]; then
 66    echo "$a * $b +/ $d = $(printf '%#x' $((r + e))) OK"
 67  else
 68    echo "$a * $b +/ $d = $(printf '%#x' $((r + e))) is wrong" >&2
 69    echo "should be equivalent to 0x$expected" >&2
 70    exit 1
 71  fi
 72done
 73
 74 */
 75
 76static u64 test_mul_u64_add_u64_div_u64(u64 a, u64 b, u64 c, u64 d);
 77#if __LONG_WIDTH__ >= 64
 78#define TEST_32BIT_DIV
 79static u64 test_mul_u64_add_u64_div_u64_32bit(u64 a, u64 b, u64 c, u64 d);
 80#endif
 81
 82static int __init test_run(unsigned int fn_no, const char *fn_name)
 83{
 84	u64 start_time;
 85	int errors = 0;
 86	int tests = 0;
 87	int i;
 88
 89	start_time = ktime_get_ns();
 90
 91	for (i = 0; i < ARRAY_SIZE(test_values); i++) {
 92		u64 a = test_values[i].a;
 93		u64 b = test_values[i].b;
 94		u64 d = test_values[i].d;
 95		u64 expected_result = test_values[i].result;
 96		u64 result, result_up;
 97
 98		switch (fn_no) {
 99		default:
100			result = mul_u64_u64_div_u64(a, b, d);
101			result_up = mul_u64_u64_div_u64_roundup(a, b, d);
102			break;
103		case 1:
104			result = test_mul_u64_add_u64_div_u64(a, b, 0, d);
105			result_up = test_mul_u64_add_u64_div_u64(a, b, d - 1, d);
106			break;
107#ifdef TEST_32BIT_DIV
108		case 2:
109			result = test_mul_u64_add_u64_div_u64_32bit(a, b, 0, d);
110			result_up = test_mul_u64_add_u64_div_u64_32bit(a, b, d - 1, d);
111			break;
112#endif
113		}
114
115		tests += 2;
116
117		if (result != expected_result) {
118			pr_err("ERROR: 0x%016llx * 0x%016llx / 0x%016llx\n", a, b, d);
119			pr_err("ERROR: expected result: %016llx\n", expected_result);
120			pr_err("ERROR: obtained result: %016llx\n", result);
121			errors++;
122		}
123		expected_result += test_values[i].round_up;
124		if (result_up != expected_result) {
125			pr_err("ERROR: 0x%016llx * 0x%016llx +/ 0x%016llx\n", a, b, d);
126			pr_err("ERROR: expected result: %016llx\n", expected_result);
127			pr_err("ERROR: obtained result: %016llx\n", result_up);
128			errors++;
129		}
130	}
131
132	pr_info("Completed %s() test, %d tests, %d errors, %llu ns\n",
133		fn_name, tests, errors, ktime_get_ns() - start_time);
134	return errors;
135}
136
137static int __init test_init(void)
138{
139	pr_info("Starting mul_u64_u64_div_u64() test\n");
140	if (test_run(0, "mul_u64_u64_div_u64"))
141		return -EINVAL;
142	if (test_run(1, "test_mul_u64_u64_div_u64"))
143		return -EINVAL;
144#ifdef TEST_32BIT_DIV
145	if (test_run(2, "test_mul_u64_u64_div_u64_32bit"))
146		return -EINVAL;
147#endif
148	return 0;
149}
150
151static void __exit test_exit(void)
152{
153}
154
155/* Compile the generic mul_u64_add_u64_div_u64() code */
156#undef __div64_32
157#define __div64_32 __div64_32
158#define div_s64_rem div_s64_rem
159#define div64_u64_rem div64_u64_rem
160#define div64_u64 div64_u64
161#define div64_s64 div64_s64
162#define iter_div_u64_rem iter_div_u64_rem
163
164#undef mul_u64_add_u64_div_u64
165#define mul_u64_add_u64_div_u64 test_mul_u64_add_u64_div_u64
166#define test_mul_u64_add_u64_div_u64 test_mul_u64_add_u64_div_u64
167
168#include "div64.c"
169
170#ifdef TEST_32BIT_DIV
171/* Recompile the generic code for 32bit long */
172#undef test_mul_u64_add_u64_div_u64
173#define test_mul_u64_add_u64_div_u64 test_mul_u64_add_u64_div_u64_32bit
174#undef BITS_PER_ITER
175#define BITS_PER_ITER 16
176
177#define mul_u64_u64_add_u64 mul_u64_u64_add_u64_32bit
178#undef mul_u64_long_add_u64
179#undef add_u64_long
180#undef mul_add
181
182#include "div64.c"
183#endif
184
185module_init(test_init);
186module_exit(test_exit);
187
188MODULE_AUTHOR("Nicolas Pitre");
189MODULE_LICENSE("GPL");
190MODULE_DESCRIPTION("mul_u64_u64_div_u64() test module");