lib/math/test_div64.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (C) 2021  Maciej W. Rozycki
0004  */
0005
0006 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
0007
0008 #include <linux/init.h>
0009 #include <linux/ktime.h>
0010 #include <linux/module.h>
0011 #include <linux/printk.h>
0012 #include <linux/time64.h>
0013 #include <linux/types.h>
0014
0015 #include <asm/div64.h>
0016
0017 #define TEST_DIV64_N_ITER 1024
0018
0019 static const u64 test_div64_dividends[] = {
0020     0x00000000ab275080,
0021     0x0000000fe73c1959,
0022     0x000000e54c0a74b1,
0023     0x00000d4398ff1ef9,
0024     0x0000a18c2ee1c097,
0025     0x00079fb80b072e4a,
0026     0x0072db27380dd689,
0027     0x0842f488162e2284,
0028     0xf66745411d8ab063,
0029 };
0030 #define SIZE_DIV64_DIVIDENDS ARRAY_SIZE(test_div64_dividends)
0031
0032 #define TEST_DIV64_DIVISOR_0 0x00000009
0033 #define TEST_DIV64_DIVISOR_1 0x0000007c
0034 #define TEST_DIV64_DIVISOR_2 0x00000204
0035 #define TEST_DIV64_DIVISOR_3 0x0000cb5b
0036 #define TEST_DIV64_DIVISOR_4 0x00010000
0037 #define TEST_DIV64_DIVISOR_5 0x0008a880
0038 #define TEST_DIV64_DIVISOR_6 0x003fd3ae
0039 #define TEST_DIV64_DIVISOR_7 0x0b658fac
0040 #define TEST_DIV64_DIVISOR_8 0xdc08b349
0041
0042 static const u32 test_div64_divisors[] = {
0043     TEST_DIV64_DIVISOR_0,
0044     TEST_DIV64_DIVISOR_1,
0045     TEST_DIV64_DIVISOR_2,
0046     TEST_DIV64_DIVISOR_3,
0047     TEST_DIV64_DIVISOR_4,
0048     TEST_DIV64_DIVISOR_5,
0049     TEST_DIV64_DIVISOR_6,
0050     TEST_DIV64_DIVISOR_7,
0051     TEST_DIV64_DIVISOR_8,
0052 };
0053 #define SIZE_DIV64_DIVISORS ARRAY_SIZE(test_div64_divisors)
0054
0055 static const struct {
0056     u64 quotient;
0057     u32 remainder;
0058 } test_div64_results[SIZE_DIV64_DIVISORS][SIZE_DIV64_DIVIDENDS] = {
0059     {
0060         { 0x0000000013045e47, 0x00000001 },
0061         { 0x000000000161596c, 0x00000030 },
0062         { 0x000000000054e9d4, 0x00000130 },
0063         { 0x000000000000d776, 0x0000278e },
0064         { 0x000000000000ab27, 0x00005080 },
0065         { 0x00000000000013c4, 0x0004ce80 },
0066         { 0x00000000000002ae, 0x001e143c },
0067         { 0x000000000000000f, 0x0033e56c },
0068         { 0x0000000000000000, 0xab275080 },
0069     }, {
0070         { 0x00000001c45c02d1, 0x00000000 },
0071         { 0x0000000020d5213c, 0x00000049 },
0072         { 0x0000000007e3d65f, 0x000001dd },
0073         { 0x0000000000140531, 0x000065ee },
0074         { 0x00000000000fe73c, 0x00001959 },
0075         { 0x000000000001d637, 0x0004e5d9 },
0076         { 0x0000000000003fc9, 0x000713bb },
0077         { 0x0000000000000165, 0x029abe7d },
0078         { 0x0000000000000012, 0x6e9f7e37 },
0079     }, {
0080         { 0x000000197a3a0cf7, 0x00000002 },
0081         { 0x00000001d9632e5c, 0x00000021 },
0082         { 0x0000000071c28039, 0x000001cd },
0083         { 0x000000000120a844, 0x0000b885 },
0084         { 0x0000000000e54c0a, 0x000074b1 },
0085         { 0x00000000001a7bb3, 0x00072331 },
0086         { 0x00000000000397ad, 0x0002c61b },
0087         { 0x000000000000141e, 0x06ea2e89 },
0088         { 0x000000000000010a, 0xab002ad7 },
0089     }, {
0090         { 0x0000017949e37538, 0x00000001 },
0091         { 0x0000001b62441f37, 0x00000055 },
0092         { 0x0000000694a3391d, 0x00000085 },
0093         { 0x0000000010b2a5d2, 0x0000a753 },
0094         { 0x000000000d4398ff, 0x00001ef9 },
0095         { 0x0000000001882ec6, 0x0005cbf9 },
0096         { 0x000000000035333b, 0x0017abdf },
0097         { 0x00000000000129f1, 0x0ab4520d },
0098         { 0x0000000000000f6e, 0x8ac0ce9b },
0099     }, {
0100         { 0x000011f321a74e49, 0x00000006 },
0101         { 0x0000014d8481d211, 0x0000005b },
0102         { 0x0000005025cbd92d, 0x000001e3 },
0103         { 0x00000000cb5e71e3, 0x000043e6 },
0104         { 0x00000000a18c2ee1, 0x0000c097 },
0105         { 0x0000000012a88828, 0x00036c97 },
0106         { 0x000000000287f16f, 0x002c2a25 },
0107         { 0x00000000000e2cc7, 0x02d581e3 },
0108         { 0x000000000000bbf4, 0x1ba08c03 },
0109     }, {
0110         { 0x0000d8db8f72935d, 0x00000005 },
0111         { 0x00000fbd5aed7a2e, 0x00000002 },
0112         { 0x000003c84b6ea64a, 0x00000122 },
0113         { 0x0000000998fa8829, 0x000044b7 },
0114         { 0x000000079fb80b07, 0x00002e4a },
0115         { 0x00000000e16b20fa, 0x0002a14a },
0116         { 0x000000001e940d22, 0x00353b2e },
0117         { 0x0000000000ab40ac, 0x06fba6ba },
0118         { 0x000000000008debd, 0x72d98365 },
0119     }, {
0120         { 0x000cc3045b8fc281, 0x00000000 },
0121         { 0x0000ed1f48b5c9fc, 0x00000079 },
0122         { 0x000038fb9c63406a, 0x000000e1 },
0123         { 0x000000909705b825, 0x00000a62 },
0124         { 0x00000072db27380d, 0x0000d689 },
0125         { 0x0000000d43fce827, 0x00082b09 },
0126         { 0x00000001ccaba11a, 0x0037e8dd },
0127         { 0x000000000a13f729, 0x0566dffd },
0128         { 0x000000000085a14b, 0x23d36726 },
0129     }, {
0130         { 0x00eafeb9c993592b, 0x00000001 },
0131         { 0x00110e5befa9a991, 0x00000048 },
0132         { 0x00041947b4a1d36a, 0x000000dc },
0133         { 0x00000a6679327311, 0x0000c079 },
0134         { 0x00000842f488162e, 0x00002284 },
0135         { 0x000000f4459740fc, 0x00084484 },
0136         { 0x0000002122c47bf9, 0x002ca446 },
0137         { 0x00000000b9936290, 0x004979c4 },
0138         { 0x00000000099ca89d, 0x9db446bf },
0139     }, {
0140         { 0x1b60cece589da1d2, 0x00000001 },
0141         { 0x01fcb42be1453f5b, 0x0000004f },
0142         { 0x007a3f2457df0749, 0x0000013f },
0143         { 0x0001363130e3ec7b, 0x000017aa },
0144         { 0x0000f66745411d8a, 0x0000b063 },
0145         { 0x00001c757dfab350, 0x00048863 },
0146         { 0x000003dc4979c652, 0x00224ea7 },
0147         { 0x000000159edc3144, 0x06409ab3 },
0148         { 0x000000011eadfee3, 0xa99c48a8 },
0149     },
0150 };
0151
0152 static inline bool test_div64_verify(u64 quotient, u32 remainder, int i, int j)
0153 {
0154     return (quotient == test_div64_results[i][j].quotient &&
0155         remainder == test_div64_results[i][j].remainder);
0156 }
0157
0158 /*
0159  * This needs to be a macro, because we don't want to rely on the compiler
0160  * to do constant propagation, and `do_div' may take a different path for
0161  * constants, so we do want to verify that as well.
0162  */
0163 #define test_div64_one(dividend, divisor, i, j) ({          \
0164     bool result = true;                     \
0165     u64 quotient;                           \
0166     u32 remainder;                          \
0167                                     \
0168     quotient = dividend;                        \
0169     remainder = do_div(quotient, divisor);              \
0170     if (!test_div64_verify(quotient, remainder, i, j)) {        \
0171         pr_err("ERROR: %016llx / %08x => %016llx,%08x\n",   \
0172                dividend, divisor, quotient, remainder);     \
0173         pr_err("ERROR: expected value              => %016llx,%08x\n",\
0174                test_div64_results[i][j].quotient,       \
0175                test_div64_results[i][j].remainder);     \
0176         result = false;                     \
0177     }                               \
0178     result;                             \
0179 })
0180
0181 /*
0182  * Run calculation for the same divisor value expressed as a constant
0183  * and as a variable, so as to verify the implementation for both cases
0184  * should they be handled by different code execution paths.
0185  */
0186 static bool __init test_div64(void)
0187 {
0188     u64 dividend;
0189     int i, j;
0190
0191     for (i = 0; i < SIZE_DIV64_DIVIDENDS; i++) {
0192         dividend = test_div64_dividends[i];
0193         if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_0, i, 0))
0194             return false;
0195         if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_1, i, 1))
0196             return false;
0197         if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_2, i, 2))
0198             return false;
0199         if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_3, i, 3))
0200             return false;
0201         if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_4, i, 4))
0202             return false;
0203         if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_5, i, 5))
0204             return false;
0205         if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_6, i, 6))
0206             return false;
0207         if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_7, i, 7))
0208             return false;
0209         if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_8, i, 8))
0210             return false;
0211         for (j = 0; j < SIZE_DIV64_DIVISORS; j++) {
0212             if (!test_div64_one(dividend, test_div64_divisors[j],
0213                         i, j))
0214                 return false;
0215         }
0216     }
0217     return true;
0218 }
0219
0220 static int __init test_div64_init(void)
0221 {
0222     struct timespec64 ts, ts0, ts1;
0223     int i;
0224
0225     pr_info("Starting 64bit/32bit division and modulo test\n");
0226     ktime_get_ts64(&ts0);
0227
0228     for (i = 0; i < TEST_DIV64_N_ITER; i++)
0229         if (!test_div64())
0230             break;
0231
0232     ktime_get_ts64(&ts1);
0233     ts = timespec64_sub(ts1, ts0);
0234     pr_info("Completed 64bit/32bit division and modulo test, "
0235         "%llu.%09lus elapsed\n", ts.tv_sec, ts.tv_nsec);
0236
0237     return 0;
0238 }
0239
0240 static void __exit test_div64_exit(void)
0241 {
0242 }
0243
0244 module_init(test_div64_init);
0245 module_exit(test_div64_exit);
0246
0247 MODULE_AUTHOR("Maciej W. Rozycki <macro@orcam.me.uk>");
0248 MODULE_LICENSE("GPL");
0249 MODULE_DESCRIPTION("64bit/32bit division and modulo test module");