qemu/roms/ipxe/src/tests/math_test.c

   1 /*
   2  * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301, USA.
  18  *
  19  * You can also choose to distribute this program under the terms of
  20  * the Unmodified Binary Distribution Licence (as given in the file
  21  * COPYING.UBDL), provided that you have satisfied its requirements.
  22  */
  23
  24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  25
  26 /** @file
  27  *
  28  * Mathematical self-tests
  29  *
  30  */
  31
  32 /* Forcibly enable assertions */
  33 #undef NDEBUG
  34
  35 #include <string.h>
  36 #include <strings.h>
  37 #include <assert.h>
  38 #include <ipxe/test.h>
  39 #include <ipxe/isqrt.h>
  40
  41 /**
  42  * Force a call to the non-constant implementation of ffsl()
  43  *
  44  * @v value             Value
  45  * @ret lsb             Least significant bit set in value (LSB=1), or zero
  46  */
  47 __attribute__ (( noinline )) int ffsl_var ( long value ) {
  48         return ffsl ( value );
  49 }
  50
  51 /**
  52  * Force a call to the non-constant implementation of ffsll()
  53  *
  54  * @v value             Value
  55  * @ret lsb             Least significant bit set in value (LSB=1), or zero
  56  */
  57 __attribute__ (( noinline )) int ffsll_var ( long long value ) {
  58         return ffsll ( value );
  59 }
  60
  61 /**
  62  * Force a call to the non-constant implementation of flsl()
  63  *
  64  * @v value             Value
  65  * @ret msb             Most significant bit set in value (LSB=1), or zero
  66  */
  67 __attribute__ (( noinline )) int flsl_var ( long value ) {
  68         return flsl ( value );
  69 }
  70
  71 /**
  72  * Force a call to the non-constant implementation of flsll()
  73  *
  74  * @v value             Value
  75  * @ret msb             Most significant bit set in value (LSB=1), or zero
  76  */
  77 __attribute__ (( noinline )) int flsll_var ( long long value ) {
  78         return flsll ( value );
  79 }
  80
  81 /**
  82  * Check current stack pointer
  83  *
  84  * @ret stack           A value at a fixed offset from the current stack pointer
  85  *
  86  * Used by check_divmod()
  87  */
  88 static __attribute__ (( noinline )) void * stack_check ( void ) {
  89         int a;
  90         void *ret;
  91
  92         /* Hide the fact that we are returning the address of a local
  93          * variable, to prevent a compiler warning.
  94          */
  95         __asm__ ( "\n" : "=g" ( ret ) : "0" ( &a ) );
  96
  97         return ret;
  98 }
  99
 100 /**
 101  * Check division/modulus operation
 102  *
 103  * One aspect of the calling convention for the implicit arithmetic
 104  * functions (__udivmoddi4() etc) is whether the caller or the callee
 105  * is expected to pop any stack-based arguments.  This distinction can
 106  * be masked if the compiler chooses to uses a frame pointer in the
 107  * caller, since the caller will then reload the stack pointer from
 108  * the frame pointer and so can mask an error in the value of the
 109  * stack pointer.
 110  *
 111  * We run the division operation in a loop, and check that the stack
 112  * pointer does not change value on the second iteration.  To prevent
 113  * the compiler from performing various optimisations which might
 114  * invalidate our intended test (such as unrolling the loop, or moving
 115  * the division operation outside the loop), we include some dummy
 116  * inline assembly code.
 117  */
 118 #define check_divmod( dividend, divisor, OP ) ( {                       \
 119         uint64_t result;                                                \
 120         int count = 2;                                                  \
 121         void *check = NULL;                                             \
 122                                                                         \
 123         /* Prevent compiler from unrolling the loop */                  \
 124         __asm__ ( "\n" : "=g" ( count ) : "0" ( count ) );              \
 125                                                                         \
 126         do {                                                            \
 127                 /* Check that stack pointer does not change between     \
 128                  * loop iterations.                                     \
 129                  */                                                     \
 130                 if ( check ) {                                          \
 131                         assert ( check == stack_check() );              \
 132                 } else {                                                \
 133                         check = stack_check();                          \
 134                 }                                                       \
 135                                                                         \
 136                 /* Perform division, preventing the compiler from       \
 137                  * moving the division out of the loop.                 \
 138                  */                                                     \
 139                 __asm__ ( "\n" : "=g" ( dividend ), "=g" ( divisor )    \
 140                           : "0" ( dividend ), "1" ( divisor ) );        \
 141                 result = ( dividend OP divisor );                       \
 142                 __asm__ ( "\n" : "=g" ( result ) : "0" ( result ) );    \
 143                                                                         \
 144         } while ( --count );                                            \
 145         result; } )
 146
 147 /**
 148  * Force a use of runtime 64-bit unsigned integer division
 149  *
 150  * @v dividend          Dividend
 151  * @v divisor           Divisor
 152  * @ret quotient        Quotient
 153  */
 154 __attribute__ (( noinline )) uint64_t u64div_var ( uint64_t dividend,
 155                                                    uint64_t divisor ) {
 156
 157         return check_divmod ( dividend, divisor, / );
 158 }
 159
 160 /**
 161  * Force a use of runtime 64-bit unsigned integer modulus
 162  *
 163  * @v dividend          Dividend
 164  * @v divisor           Divisor
 165  * @ret remainder       Remainder
 166  */
 167 __attribute__ (( noinline )) uint64_t u64mod_var ( uint64_t dividend,
 168                                                    uint64_t divisor ) {
 169
 170         return check_divmod ( dividend, divisor, % );
 171 }
 172
 173 /**
 174  * Force a use of runtime 64-bit signed integer division
 175  *
 176  * @v dividend          Dividend
 177  * @v divisor           Divisor
 178  * @ret quotient        Quotient
 179  */
 180 __attribute__ (( noinline )) int64_t s64div_var ( int64_t dividend,
 181                                                   int64_t divisor ) {
 182
 183         return check_divmod ( dividend, divisor, / );
 184 }
 185
 186 /**
 187  * Force a use of runtime 64-bit unsigned integer modulus
 188  *
 189  * @v dividend          Dividend
 190  * @v divisor           Divisor
 191  * @ret remainder       Remainder
 192  */
 193 __attribute__ (( noinline )) int64_t s64mod_var ( int64_t dividend,
 194                                                   int64_t divisor ) {
 195
 196         return check_divmod ( dividend, divisor, % );
 197 }
 198
 199 /**
 200  * Report a ffsl() test result
 201  *
 202  * @v value             Value
 203  * @v lsb               Expected LSB
 204  * @v file              Test code file
 205  * @v line              Test code line
 206  */
 207 static inline __attribute__ (( always_inline )) void
 208 ffsl_okx ( long value, int lsb, const char *file, unsigned int line ) {
 209
 210         /* Verify as a constant (requires to be inlined) */
 211         okx ( ffsl ( value ) == lsb, file, line );
 212
 213         /* Verify as a non-constant */
 214         okx ( ffsl_var ( value ) == lsb, file, line );
 215 }
 216 #define ffsl_ok( value, lsb ) ffsl_okx ( value, lsb, __FILE__, __LINE__ )
 217
 218 /**
 219  * Report a ffsll() test result
 220  *
 221  * @v value             Value
 222  * @v lsb               Expected LSB
 223  * @v file              Test code file
 224  * @v line              Test code line
 225  */
 226 static inline __attribute__ (( always_inline )) void
 227 ffsll_okx ( long long value, int lsb, const char *file, unsigned int line ) {
 228
 229         /* Verify as a constant (requires to be inlined) */
 230         okx ( ffsll ( value ) == lsb, file, line );
 231
 232         /* Verify as a non-constant */
 233         okx ( ffsll_var ( value ) == lsb, file, line );
 234 }
 235 #define ffsll_ok( value, lsb ) ffsll_okx ( value, lsb, __FILE__, __LINE__ )
 236
 237 /**
 238  * Report a flsl() test result
 239  *
 240  * @v value             Value
 241  * @v msb               Expected MSB
 242  * @v file              Test code file
 243  * @v line              Test code line
 244  */
 245 static inline __attribute__ (( always_inline )) void
 246 flsl_okx ( long value, int msb, const char *file, unsigned int line ) {
 247
 248         /* Verify as a constant (requires to be inlined) */
 249         okx ( flsl ( value ) == msb, file, line );
 250
 251         /* Verify as a non-constant */
 252         okx ( flsl_var ( value ) == msb, file, line );
 253 }
 254 #define flsl_ok( value, msb ) flsl_okx ( value, msb, __FILE__, __LINE__ )
 255
 256 /**
 257  * Report a flsll() test result
 258  *
 259  * @v value             Value
 260  * @v msb               Expected MSB
 261  * @v file              Test code file
 262  * @v line              Test code line
 263  */
 264 static inline __attribute__ (( always_inline )) void
 265 flsll_okx ( long long value, int msb, const char *file, unsigned int line ) {
 266
 267         /* Verify as a constant (requires to be inlined) */
 268         okx ( flsll ( value ) == msb, file, line );
 269
 270         /* Verify as a non-constant */
 271         okx ( flsll_var ( value ) == msb, file, line );
 272 }
 273 #define flsll_ok( value, msb ) flsll_okx ( value, msb, __FILE__, __LINE__ )
 274
 275 /**
 276  * Report a 64-bit unsigned integer division test result
 277  *
 278  * @v dividend          Dividend
 279  * @v divisor           Divisor
 280  * @v quotient          Quotient
 281  * @v remainder         Remainder
 282  * @v file              Test code file
 283  * @v line              Test code line
 284  */
 285 static void u64divmod_okx ( uint64_t dividend, uint64_t divisor,
 286                             uint64_t quotient, uint64_t remainder,
 287                             const char *file, unsigned int line ) {
 288
 289         /* Sanity check */
 290         okx ( ( ( divisor * quotient ) + remainder ) == dividend, file, line );
 291
 292         /* Check division */
 293         okx ( u64div_var ( dividend, divisor ) == quotient, file, line );
 294
 295         /* Check modulus */
 296         okx ( u64mod_var ( dividend, divisor ) == remainder, file, line );
 297 }
 298 #define u64divmod_ok( dividend, divisor, quotient, remainder )  \
 299         u64divmod_okx ( dividend, divisor, quotient, remainder, \
 300                         __FILE__, __LINE__ )
 301
 302 /**
 303  * Report a 64-bit signed integer division test result
 304  *
 305  * @v dividend          Dividend
 306  * @v divisor           Divisor
 307  * @v quotient          Quotient
 308  * @v remainder         Remainder
 309  * @v file              Test code file
 310  * @v line              Test code line
 311  */
 312 static void s64divmod_okx ( int64_t dividend, int64_t divisor,
 313                             int64_t quotient, int64_t remainder,
 314                             const char *file, unsigned int line ) {
 315
 316         /* Sanity check */
 317         okx ( ( ( divisor * quotient ) + remainder ) == dividend, file, line );
 318
 319         /* Check division */
 320         okx ( s64div_var ( dividend, divisor ) == quotient, file, line );
 321
 322         /* Check modulus */
 323         okx ( s64mod_var ( dividend, divisor ) == remainder, file, line );
 324 }
 325 #define s64divmod_ok( dividend, divisor, quotient, remainder )  \
 326         s64divmod_okx ( dividend, divisor, quotient, remainder, \
 327                         __FILE__, __LINE__ )
 328
 329 /**
 330  * Perform mathematical self-tests
 331  *
 332  */
 333 static void math_test_exec ( void ) {
 334
 335         /* Test ffsl() */
 336         ffsl_ok ( 0, 0 );
 337         ffsl_ok ( 1, 1 );
 338         ffsl_ok ( 255, 1 );
 339         ffsl_ok ( 256, 9 );
 340         ffsl_ok ( 257, 1 );
 341         ffsl_ok ( 0x54850596, 2 );
 342         ffsl_ok ( 0x80000000, 32 );
 343
 344         /* Test ffsll() */
 345         ffsll_ok ( 0, 0 );
 346         ffsll_ok ( 1, 1 );
 347         ffsll_ok ( 0x6d63623330ULL, 5 );
 348         ffsll_ok ( 0x80000000UL, 32 );
 349         ffsll_ok ( 0x8000000000000000ULL, 64 );
 350
 351         /* Test flsl() */
 352         flsl_ok ( 0, 0 );
 353         flsl_ok ( 1, 1 );
 354         flsl_ok ( 255, 8 );
 355         flsl_ok ( 256, 9 );
 356         flsl_ok ( 257, 9 );
 357         flsl_ok ( 0x69505845, 31 );
 358         flsl_ok ( -1U, ( 8 * sizeof ( int ) ) );
 359         flsl_ok ( -1UL, ( 8 * sizeof ( long ) ) );
 360
 361         /* Test flsll() */
 362         flsll_ok ( 0, 0 );
 363         flsll_ok ( 1, 1 );
 364         flsll_ok ( 0x6d63623330ULL, 39 );
 365         flsll_ok ( -1U, ( 8 * sizeof ( int ) ) );
 366         flsll_ok ( -1UL, ( 8 * sizeof ( long ) ) );
 367         flsll_ok ( -1ULL, ( 8 * sizeof ( long long ) ) );
 368
 369         /* Test 64-bit arithmetic
 370          *
 371          * On a 64-bit machine, these tests are fairly meaningless.
 372          *
 373          * On a 32-bit machine, these tests verify the correct
 374          * operation of our libgcc functions __udivmoddi4()
 375          * etc. (including checking that the implicit calling
 376          * convention assumed by gcc matches our expectations).
 377          */
 378         u64divmod_ok ( 0x2b90ddccf699f765ULL, 0xed9f5e73ULL,
 379                        0x2eef6ab4ULL, 0x0e12f089ULL );
 380         s64divmod_ok ( 0x2b90ddccf699f765ULL, 0xed9f5e73ULL,
 381                        0x2eef6ab4ULL, 0x0e12f089ULL );
 382         u64divmod_ok ( 0xc09e00dcb9e34b54ULL, 0x35968185cdc744f3ULL,
 383                        3, 0x1fda7c4b508d7c7bULL );
 384         s64divmod_ok ( -0x3f61ff23461cb4acLL, 0x35968185cdc744f3ULL,
 385                        -1LL, -0x9cb7d9d78556fb9LL );
 386         u64divmod_ok ( 0, 0x5b2f2737f4ffULL, 0, 0 );
 387         s64divmod_ok ( 0, 0xbb00ded72766207fULL, 0, 0 );
 388
 389         /* Test integer square root */
 390         ok ( isqrt ( 0 ) == 0 );
 391         ok ( isqrt ( 1 ) == 1 );
 392         ok ( isqrt ( 255 ) == 15 );
 393         ok ( isqrt ( 256 ) == 16 );
 394         ok ( isqrt ( 257 ) == 16 );
 395         ok ( isqrt ( 0xa53df2adUL ) == 52652 );
 396         ok ( isqrt ( 0x123793c6UL ) == 17482 );
 397         ok ( isqrt ( -1UL ) == ( -1UL >> ( 8 * sizeof ( unsigned long ) / 2 )));
 398 }
 399
 400 /** Mathematical self-tests */
 401 struct self_test math_test __self_test = {
 402         .name = "math",
 403         .exec = math_test_exec,
 404 };