lib/math/test_div64.c

   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         0xfffffffffffffffb,
  30         0xfffffffffffffffc,
  31         0xffffffffffffffff,
  32 };
  33 #define SIZE_DIV64_DIVIDENDS ARRAY_SIZE(test_div64_dividends)
  34
  35 #define TEST_DIV64_DIVISOR_0 0x00000009
  36 #define TEST_DIV64_DIVISOR_1 0x0000007c
  37 #define TEST_DIV64_DIVISOR_2 0x00000204
  38 #define TEST_DIV64_DIVISOR_3 0x0000cb5b
  39 #define TEST_DIV64_DIVISOR_4 0x00010000
  40 #define TEST_DIV64_DIVISOR_5 0x0008a880
  41 #define TEST_DIV64_DIVISOR_6 0x003fd3ae
  42 #define TEST_DIV64_DIVISOR_7 0x0b658fac
  43 #define TEST_DIV64_DIVISOR_8 0x80000001
  44 #define TEST_DIV64_DIVISOR_9 0xdc08b349
  45 #define TEST_DIV64_DIVISOR_A 0xfffffffe
  46 #define TEST_DIV64_DIVISOR_B 0xffffffff
  47
  48 static const u32 test_div64_divisors[] = {
  49         TEST_DIV64_DIVISOR_0,
  50         TEST_DIV64_DIVISOR_1,
  51         TEST_DIV64_DIVISOR_2,
  52         TEST_DIV64_DIVISOR_3,
  53         TEST_DIV64_DIVISOR_4,
  54         TEST_DIV64_DIVISOR_5,
  55         TEST_DIV64_DIVISOR_6,
  56         TEST_DIV64_DIVISOR_7,
  57         TEST_DIV64_DIVISOR_8,
  58         TEST_DIV64_DIVISOR_9,
  59         TEST_DIV64_DIVISOR_A,
  60         TEST_DIV64_DIVISOR_B,
  61 };
  62 #define SIZE_DIV64_DIVISORS ARRAY_SIZE(test_div64_divisors)
  63
  64 static const struct {
  65         u64 quotient;
  66         u32 remainder;
  67 } test_div64_results[SIZE_DIV64_DIVIDENDS][SIZE_DIV64_DIVISORS] = {
  68         {
  69                 { 0x0000000013045e47, 0x00000001 },
  70                 { 0x000000000161596c, 0x00000030 },
  71                 { 0x000000000054e9d4, 0x00000130 },
  72                 { 0x000000000000d776, 0x0000278e },
  73                 { 0x000000000000ab27, 0x00005080 },
  74                 { 0x00000000000013c4, 0x0004ce80 },
  75                 { 0x00000000000002ae, 0x001e143c },
  76                 { 0x000000000000000f, 0x0033e56c },
  77                 { 0x0000000000000001, 0x2b27507f },
  78                 { 0x0000000000000000, 0xab275080 },
  79                 { 0x0000000000000000, 0xab275080 },
  80                 { 0x0000000000000000, 0xab275080 },
  81         }, {
  82                 { 0x00000001c45c02d1, 0x00000000 },
  83                 { 0x0000000020d5213c, 0x00000049 },
  84                 { 0x0000000007e3d65f, 0x000001dd },
  85                 { 0x0000000000140531, 0x000065ee },
  86                 { 0x00000000000fe73c, 0x00001959 },
  87                 { 0x000000000001d637, 0x0004e5d9 },
  88                 { 0x0000000000003fc9, 0x000713bb },
  89                 { 0x0000000000000165, 0x029abe7d },
  90                 { 0x000000000000001f, 0x673c193a },
  91                 { 0x0000000000000012, 0x6e9f7e37 },
  92                 { 0x000000000000000f, 0xe73c1977 },
  93                 { 0x000000000000000f, 0xe73c1968 },
  94         }, {
  95                 { 0x000000197a3a0cf7, 0x00000002 },
  96                 { 0x00000001d9632e5c, 0x00000021 },
  97                 { 0x0000000071c28039, 0x000001cd },
  98                 { 0x000000000120a844, 0x0000b885 },
  99                 { 0x0000000000e54c0a, 0x000074b1 },
 100                 { 0x00000000001a7bb3, 0x00072331 },
 101                 { 0x00000000000397ad, 0x0002c61b },
 102                 { 0x000000000000141e, 0x06ea2e89 },
 103                 { 0x00000000000001ca, 0x4c0a72e7 },
 104                 { 0x000000000000010a, 0xab002ad7 },
 105                 { 0x00000000000000e5, 0x4c0a767b },
 106                 { 0x00000000000000e5, 0x4c0a7596 },
 107         }, {
 108                 { 0x0000017949e37538, 0x00000001 },
 109                 { 0x0000001b62441f37, 0x00000055 },
 110                 { 0x0000000694a3391d, 0x00000085 },
 111                 { 0x0000000010b2a5d2, 0x0000a753 },
 112                 { 0x000000000d4398ff, 0x00001ef9 },
 113                 { 0x0000000001882ec6, 0x0005cbf9 },
 114                 { 0x000000000035333b, 0x0017abdf },
 115                 { 0x00000000000129f1, 0x0ab4520d },
 116                 { 0x0000000000001a87, 0x18ff0472 },
 117                 { 0x0000000000000f6e, 0x8ac0ce9b },
 118                 { 0x0000000000000d43, 0x98ff397f },
 119                 { 0x0000000000000d43, 0x98ff2c3c },
 120         }, {
 121                 { 0x000011f321a74e49, 0x00000006 },
 122                 { 0x0000014d8481d211, 0x0000005b },
 123                 { 0x0000005025cbd92d, 0x000001e3 },
 124                 { 0x00000000cb5e71e3, 0x000043e6 },
 125                 { 0x00000000a18c2ee1, 0x0000c097 },
 126                 { 0x0000000012a88828, 0x00036c97 },
 127                 { 0x000000000287f16f, 0x002c2a25 },
 128                 { 0x00000000000e2cc7, 0x02d581e3 },
 129                 { 0x0000000000014318, 0x2ee07d7f },
 130                 { 0x000000000000bbf4, 0x1ba08c03 },
 131                 { 0x000000000000a18c, 0x2ee303af },
 132                 { 0x000000000000a18c, 0x2ee26223 },
 133         }, {
 134                 { 0x0000d8db8f72935d, 0x00000005 },
 135                 { 0x00000fbd5aed7a2e, 0x00000002 },
 136                 { 0x000003c84b6ea64a, 0x00000122 },
 137                 { 0x0000000998fa8829, 0x000044b7 },
 138                 { 0x000000079fb80b07, 0x00002e4a },
 139                 { 0x00000000e16b20fa, 0x0002a14a },
 140                 { 0x000000001e940d22, 0x00353b2e },
 141                 { 0x0000000000ab40ac, 0x06fba6ba },
 142                 { 0x00000000000f3f70, 0x0af7eeda },
 143                 { 0x000000000008debd, 0x72d98365 },
 144                 { 0x0000000000079fb8, 0x0b166dba },
 145                 { 0x0000000000079fb8, 0x0b0ece02 },
 146         }, {
 147                 { 0x000cc3045b8fc281, 0x00000000 },
 148                 { 0x0000ed1f48b5c9fc, 0x00000079 },
 149                 { 0x000038fb9c63406a, 0x000000e1 },
 150                 { 0x000000909705b825, 0x00000a62 },
 151                 { 0x00000072db27380d, 0x0000d689 },
 152                 { 0x0000000d43fce827, 0x00082b09 },
 153                 { 0x00000001ccaba11a, 0x0037e8dd },
 154                 { 0x000000000a13f729, 0x0566dffd },
 155                 { 0x0000000000e5b64e, 0x3728203b },
 156                 { 0x000000000085a14b, 0x23d36726 },
 157                 { 0x000000000072db27, 0x38f38cd7 },
 158                 { 0x000000000072db27, 0x3880b1b0 },
 159         }, {
 160                 { 0x00eafeb9c993592b, 0x00000001 },
 161                 { 0x00110e5befa9a991, 0x00000048 },
 162                 { 0x00041947b4a1d36a, 0x000000dc },
 163                 { 0x00000a6679327311, 0x0000c079 },
 164                 { 0x00000842f488162e, 0x00002284 },
 165                 { 0x000000f4459740fc, 0x00084484 },
 166                 { 0x0000002122c47bf9, 0x002ca446 },
 167                 { 0x00000000b9936290, 0x004979c4 },
 168                 { 0x000000001085e910, 0x05a83974 },
 169                 { 0x00000000099ca89d, 0x9db446bf },
 170                 { 0x000000000842f488, 0x26b40b94 },
 171                 { 0x000000000842f488, 0x1e71170c },
 172         }, {
 173                 { 0x1b60cece589da1d2, 0x00000001 },
 174                 { 0x01fcb42be1453f5b, 0x0000004f },
 175                 { 0x007a3f2457df0749, 0x0000013f },
 176                 { 0x0001363130e3ec7b, 0x000017aa },
 177                 { 0x0000f66745411d8a, 0x0000b063 },
 178                 { 0x00001c757dfab350, 0x00048863 },
 179                 { 0x000003dc4979c652, 0x00224ea7 },
 180                 { 0x000000159edc3144, 0x06409ab3 },
 181                 { 0x00000001ecce8a7e, 0x30bc25e5 },
 182                 { 0x000000011eadfee3, 0xa99c48a8 },
 183                 { 0x00000000f6674543, 0x0a593ae9 },
 184                 { 0x00000000f6674542, 0x13f1f5a5 },
 185         }, {
 186                 { 0x1c71c71c71c71c71, 0x00000002 },
 187                 { 0x0210842108421084, 0x0000000b },
 188                 { 0x007f01fc07f01fc0, 0x000000fb },
 189                 { 0x00014245eabf1f9a, 0x0000a63d },
 190                 { 0x0000ffffffffffff, 0x0000fffb },
 191                 { 0x00001d913cecc509, 0x0007937b },
 192                 { 0x00000402c70c678f, 0x0005bfc9 },
 193                 { 0x00000016766cb70b, 0x045edf97 },
 194                 { 0x00000001fffffffb, 0x80000000 },
 195                 { 0x0000000129d84b3a, 0xa2e8fe71 },
 196                 { 0x0000000100000001, 0xfffffffd },
 197                 { 0x0000000100000000, 0xfffffffb },
 198         }, {
 199                 { 0x1c71c71c71c71c71, 0x00000003 },
 200                 { 0x0210842108421084, 0x0000000c },
 201                 { 0x007f01fc07f01fc0, 0x000000fc },
 202                 { 0x00014245eabf1f9a, 0x0000a63e },
 203                 { 0x0000ffffffffffff, 0x0000fffc },
 204                 { 0x00001d913cecc509, 0x0007937c },
 205                 { 0x00000402c70c678f, 0x0005bfca },
 206                 { 0x00000016766cb70b, 0x045edf98 },
 207                 { 0x00000001fffffffc, 0x00000000 },
 208                 { 0x0000000129d84b3a, 0xa2e8fe72 },
 209                 { 0x0000000100000002, 0x00000000 },
 210                 { 0x0000000100000000, 0xfffffffc },
 211         }, {
 212                 { 0x1c71c71c71c71c71, 0x00000006 },
 213                 { 0x0210842108421084, 0x0000000f },
 214                 { 0x007f01fc07f01fc0, 0x000000ff },
 215                 { 0x00014245eabf1f9a, 0x0000a641 },
 216                 { 0x0000ffffffffffff, 0x0000ffff },
 217                 { 0x00001d913cecc509, 0x0007937f },
 218                 { 0x00000402c70c678f, 0x0005bfcd },
 219                 { 0x00000016766cb70b, 0x045edf9b },
 220                 { 0x00000001fffffffc, 0x00000003 },
 221                 { 0x0000000129d84b3a, 0xa2e8fe75 },
 222                 { 0x0000000100000002, 0x00000003 },
 223                 { 0x0000000100000001, 0x00000000 },
 224         },
 225 };
 226
 227 static inline bool test_div64_verify(u64 quotient, u32 remainder, int i, int j)
 228 {
 229         return (quotient == test_div64_results[i][j].quotient &&
 230                 remainder == test_div64_results[i][j].remainder);
 231 }
 232
 233 /*
 234  * This needs to be a macro, because we don't want to rely on the compiler
 235  * to do constant propagation, and `do_div' may take a different path for
 236  * constants, so we do want to verify that as well.
 237  */
 238 #define test_div64_one(dividend, divisor, i, j) ({                      \
 239         bool result = true;                                             \
 240         u64 quotient;                                                   \
 241         u32 remainder;                                                  \
 242                                                                         \
 243         quotient = dividend;                                            \
 244         remainder = do_div(quotient, divisor);                          \
 245         if (!test_div64_verify(quotient, remainder, i, j)) {            \
 246                 pr_err("ERROR: %016llx / %08x => %016llx,%08x\n",       \
 247                        dividend, divisor, quotient, remainder);         \
 248                 pr_err("ERROR: expected value              => %016llx,%08x\n",\
 249                        test_div64_results[i][j].quotient,               \
 250                        test_div64_results[i][j].remainder);             \
 251                 result = false;                                         \
 252         }                                                               \
 253         result;                                                         \
 254 })
 255
 256 /*
 257  * Run calculation for the same divisor value expressed as a constant
 258  * and as a variable, so as to verify the implementation for both cases
 259  * should they be handled by different code execution paths.
 260  */
 261 static bool __init test_div64(void)
 262 {
 263         u64 dividend;
 264         int i, j;
 265
 266         for (i = 0; i < SIZE_DIV64_DIVIDENDS; i++) {
 267                 dividend = test_div64_dividends[i];
 268                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_0, i, 0))
 269                         return false;
 270                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_1, i, 1))
 271                         return false;
 272                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_2, i, 2))
 273                         return false;
 274                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_3, i, 3))
 275                         return false;
 276                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_4, i, 4))
 277                         return false;
 278                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_5, i, 5))
 279                         return false;
 280                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_6, i, 6))
 281                         return false;
 282                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_7, i, 7))
 283                         return false;
 284                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_8, i, 8))
 285                         return false;
 286                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_9, i, 9))
 287                         return false;
 288                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_A, i, 10))
 289                         return false;
 290                 if (!test_div64_one(dividend, TEST_DIV64_DIVISOR_B, i, 11))
 291                         return false;
 292                 for (j = 0; j < SIZE_DIV64_DIVISORS; j++) {
 293                         if (!test_div64_one(dividend, test_div64_divisors[j],
 294                                             i, j))
 295                                 return false;
 296                 }
 297         }
 298         return true;
 299 }
 300
 301 static int __init test_div64_init(void)
 302 {
 303         struct timespec64 ts, ts0, ts1;
 304         int i;
 305
 306         pr_info("Starting 64bit/32bit division and modulo test\n");
 307         ktime_get_ts64(&ts0);
 308
 309         for (i = 0; i < TEST_DIV64_N_ITER; i++)
 310                 if (!test_div64())
 311                         break;
 312
 313         ktime_get_ts64(&ts1);
 314         ts = timespec64_sub(ts1, ts0);
 315         pr_info("Completed 64bit/32bit division and modulo test, "
 316                 "%llu.%09lus elapsed\n", ts.tv_sec, ts.tv_nsec);
 317
 318         return 0;
 319 }
 320
 321 static void __exit test_div64_exit(void)
 322 {
 323 }
 324
 325 module_init(test_div64_init);
 326 module_exit(test_div64_exit);
 327
 328 MODULE_AUTHOR("Maciej W. Rozycki <macro@orcam.me.uk>");
 329 MODULE_LICENSE("GPL");
 330 MODULE_DESCRIPTION("64bit/32bit division and modulo test module");