xref: /linux/lib/math/test_div64.c (revision 8be98d2f2a0a262f8bf8a0bc1fdf522b3c7aab17)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) 2021  Maciej W. Rozycki
4  */
5 
6 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
7 
8 #include <linux/init.h>
9 #include <linux/ktime.h>
10 #include <linux/module.h>
11 #include <linux/printk.h>
12 #include <linux/time64.h>
13 #include <linux/types.h>
14 
15 #include <asm/div64.h>
16 
17 #define TEST_DIV64_N_ITER 1024
18 
19 static const u64 test_div64_dividends[] = {
20 	0x00000000ab275080,
21 	0x0000000fe73c1959,
22 	0x000000e54c0a74b1,
23 	0x00000d4398ff1ef9,
24 	0x0000a18c2ee1c097,
25 	0x00079fb80b072e4a,
26 	0x0072db27380dd689,
27 	0x0842f488162e2284,
28 	0xf66745411d8ab063,
29 };
30 #define SIZE_DIV64_DIVIDENDS ARRAY_SIZE(test_div64_dividends)
31 
32 #define TEST_DIV64_DIVISOR_0 0x00000009
33 #define TEST_DIV64_DIVISOR_1 0x0000007c
34 #define TEST_DIV64_DIVISOR_2 0x00000204
35 #define TEST_DIV64_DIVISOR_3 0x0000cb5b
36 #define TEST_DIV64_DIVISOR_4 0x00010000
37 #define TEST_DIV64_DIVISOR_5 0x0008a880
38 #define TEST_DIV64_DIVISOR_6 0x003fd3ae
39 #define TEST_DIV64_DIVISOR_7 0x0b658fac
40 #define TEST_DIV64_DIVISOR_8 0xdc08b349
41 
42 static const u32 test_div64_divisors[] = {
43 	TEST_DIV64_DIVISOR_0,
44 	TEST_DIV64_DIVISOR_1,
45 	TEST_DIV64_DIVISOR_2,
46 	TEST_DIV64_DIVISOR_3,
47 	TEST_DIV64_DIVISOR_4,
48 	TEST_DIV64_DIVISOR_5,
49 	TEST_DIV64_DIVISOR_6,
50 	TEST_DIV64_DIVISOR_7,
51 	TEST_DIV64_DIVISOR_8,
52 };
53 #define SIZE_DIV64_DIVISORS ARRAY_SIZE(test_div64_divisors)
54 
55 static const struct {
56 	u64 quotient;
57 	u32 remainder;
58 } test_div64_results[SIZE_DIV64_DIVISORS][SIZE_DIV64_DIVIDENDS] = {
59 	{
60 		{ 0x0000000013045e47, 0x00000001 },
61 		{ 0x000000000161596c, 0x00000030 },
62 		{ 0x000000000054e9d4, 0x00000130 },
63 		{ 0x000000000000d776, 0x0000278e },
64 		{ 0x000000000000ab27, 0x00005080 },
65 		{ 0x00000000000013c4, 0x0004ce80 },
66 		{ 0x00000000000002ae, 0x001e143c },
67 		{ 0x000000000000000f, 0x0033e56c },
68 		{ 0x0000000000000000, 0xab275080 },
69 	}, {
70 		{ 0x00000001c45c02d1, 0x00000000 },
71 		{ 0x0000000020d5213c, 0x00000049 },
72 		{ 0x0000000007e3d65f, 0x000001dd },
73 		{ 0x0000000000140531, 0x000065ee },
74 		{ 0x00000000000fe73c, 0x00001959 },
75 		{ 0x000000000001d637, 0x0004e5d9 },
76 		{ 0x0000000000003fc9, 0x000713bb },
77 		{ 0x0000000000000165, 0x029abe7d },
78 		{ 0x0000000000000012, 0x6e9f7e37 },
79 	}, {
80 		{ 0x000000197a3a0cf7, 0x00000002 },
81 		{ 0x00000001d9632e5c, 0x00000021 },
82 		{ 0x0000000071c28039, 0x000001cd },
83 		{ 0x000000000120a844, 0x0000b885 },
84 		{ 0x0000000000e54c0a, 0x000074b1 },
85 		{ 0x00000000001a7bb3, 0x00072331 },
86 		{ 0x00000000000397ad, 0x0002c61b },
87 		{ 0x000000000000141e, 0x06ea2e89 },
88 		{ 0x000000000000010a, 0xab002ad7 },
89 	}, {
90 		{ 0x0000017949e37538, 0x00000001 },
91 		{ 0x0000001b62441f37, 0x00000055 },
92 		{ 0x0000000694a3391d, 0x00000085 },
93 		{ 0x0000000010b2a5d2, 0x0000a753 },
94 		{ 0x000000000d4398ff, 0x00001ef9 },
95 		{ 0x0000000001882ec6, 0x0005cbf9 },
96 		{ 0x000000000035333b, 0x0017abdf },
97 		{ 0x00000000000129f1, 0x0ab4520d },
98 		{ 0x0000000000000f6e, 0x8ac0ce9b },
99 	}, {
100 		{ 0x000011f321a74e49, 0x00000006 },
101 		{ 0x0000014d8481d211, 0x0000005b },
102 		{ 0x0000005025cbd92d, 0x000001e3 },
103 		{ 0x00000000cb5e71e3, 0x000043e6 },
104 		{ 0x00000000a18c2ee1, 0x0000c097 },
105 		{ 0x0000000012a88828, 0x00036c97 },
106 		{ 0x000000000287f16f, 0x002c2a25 },
107 		{ 0x00000000000e2cc7, 0x02d581e3 },
108 		{ 0x000000000000bbf4, 0x1ba08c03 },
109 	}, {
110 		{ 0x0000d8db8f72935d, 0x00000005 },
111 		{ 0x00000fbd5aed7a2e, 0x00000002 },
112 		{ 0x000003c84b6ea64a, 0x00000122 },
113 		{ 0x0000000998fa8829, 0x000044b7 },
114 		{ 0x000000079fb80b07, 0x00002e4a },
115 		{ 0x00000000e16b20fa, 0x0002a14a },
116 		{ 0x000000001e940d22, 0x00353b2e },
117 		{ 0x0000000000ab40ac, 0x06fba6ba },
118 		{ 0x000000000008debd, 0x72d98365 },
119 	}, {
120 		{ 0x000cc3045b8fc281, 0x00000000 },
121 		{ 0x0000ed1f48b5c9fc, 0x00000079 },
122 		{ 0x000038fb9c63406a, 0x000000e1 },
123 		{ 0x000000909705b825, 0x00000a62 },
124 		{ 0x00000072db27380d, 0x0000d689 },
125 		{ 0x0000000d43fce827, 0x00082b09 },
126 		{ 0x00000001ccaba11a, 0x0037e8dd },
127 		{ 0x000000000a13f729, 0x0566dffd },
128 		{ 0x000000000085a14b, 0x23d36726 },
129 	}, {
130 		{ 0x00eafeb9c993592b, 0x00000001 },
131 		{ 0x00110e5befa9a991, 0x00000048 },
132 		{ 0x00041947b4a1d36a, 0x000000dc },
133 		{ 0x00000a6679327311, 0x0000c079 },
134 		{ 0x00000842f488162e, 0x00002284 },
135 		{ 0x000000f4459740fc, 0x00084484 },
136 		{ 0x0000002122c47bf9, 0x002ca446 },
137 		{ 0x00000000b9936290, 0x004979c4 },
138 		{ 0x00000000099ca89d, 0x9db446bf },
139 	}, {
140 		{ 0x1b60cece589da1d2, 0x00000001 },
141 		{ 0x01fcb42be1453f5b, 0x0000004f },
142 		{ 0x007a3f2457df0749, 0x0000013f },
143 		{ 0x0001363130e3ec7b, 0x000017aa },
144 		{ 0x0000f66745411d8a, 0x0000b063 },
145 		{ 0x00001c757dfab350, 0x00048863 },
146 		{ 0x000003dc4979c652, 0x00224ea7 },
147 		{ 0x000000159edc3144, 0x06409ab3 },
148 		{ 0x000000011eadfee3, 0xa99c48a8 },
149 	},
150 };
151 
test_div64_verify(u64 quotient,u32 remainder,int i,int j)152 static inline bool test_div64_verify(u64 quotient, u32 remainder, int i, int j)
153 {
154 	return (quotient == test_div64_results[i][j].quotient &&
155 		remainder == test_div64_results[i][j].remainder);
156 }
157 
158 /*
159  * This needs to be a macro, because we don't want to rely on the compiler
160  * to do constant propagation, and `do_div' may take a different path for
161  * constants, so we do want to verify that as well.
162  */
163 #define test_div64_one(dividend, divisor, i, j) ({			\
164 	bool result = true;						\
165 	u64 quotient;							\
166 	u32 remainder;							\
167 									\
168 	quotient = dividend;						\
169 	remainder = do_div(quotient, divisor);				\
170 	if (!test_div64_verify(quotient, remainder, i, j)) {		\
171 		pr_err("ERROR: %016llx / %08x => %016llx,%08x\n",	\
172 		       dividend, divisor, quotient, remainder);		\
173 		pr_err("ERROR: expected value              => %016llx,%08x\n",\
174 		       test_div64_results[i][j].quotient,		\
175 		       test_div64_results[i][j].remainder);		\
176 		result = false;						\
177 	}								\
178 	result;								\
179 })
180 
181 /*
182  * Run calculation for the same divisor value expressed as a constant
183  * and as a variable, so as to verify the implementation for both cases
184  * should they be handled by different code execution paths.
185  */
test_div64(void)186 static bool __init test_div64(void)
187 {
188 	u64 dividend;
189 	int i, j;
190 
191 	for (i = 0; i < SIZE_DIV64_DIVIDENDS; i++) {
192 		dividend = test_div64_dividends[i];
193 		if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_0, i, 0))
194 			return false;
195 		if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_1, i, 1))
196 			return false;
197 		if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_2, i, 2))
198 			return false;
199 		if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_3, i, 3))
200 			return false;
201 		if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_4, i, 4))
202 			return false;
203 		if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_5, i, 5))
204 			return false;
205 		if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_6, i, 6))
206 			return false;
207 		if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_7, i, 7))
208 			return false;
209 		if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_8, i, 8))
210 			return false;
211 		for (j = 0; j < SIZE_DIV64_DIVISORS; j++) {
212 			if (!test_div64_one(dividend, test_div64_divisors[j],
213 					    i, j))
214 				return false;
215 		}
216 	}
217 	return true;
218 }
219 
test_div64_init(void)220 static int __init test_div64_init(void)
221 {
222 	struct timespec64 ts, ts0, ts1;
223 	int i;
224 
225 	pr_info("Starting 64bit/32bit division and modulo test\n");
226 	ktime_get_ts64(&ts0);
227 
228 	for (i = 0; i < TEST_DIV64_N_ITER; i++)
229 		if (!test_div64())
230 			break;
231 
232 	ktime_get_ts64(&ts1);
233 	ts = timespec64_sub(ts1, ts0);
234 	pr_info("Completed 64bit/32bit division and modulo test, "
235 		"%llu.%09lus elapsed\n", ts.tv_sec, ts.tv_nsec);
236 
237 	return 0;
238 }
239 
test_div64_exit(void)240 static void __exit test_div64_exit(void)
241 {
242 }
243 
244 module_init(test_div64_init);
245 module_exit(test_div64_exit);
246 
247 MODULE_AUTHOR("Maciej W. Rozycki <macro@orcam.me.uk>");
248 MODULE_LICENSE("GPL");
249 MODULE_DESCRIPTION("64bit/32bit division and modulo test module");
250