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
  20 FILE_LICENCE ( GPL2_OR_LATER );
  21
  22 /** @file
  23  *
  24  * Mathematical self-tests
  25  *
  26  */
  27
  28 /* Forcibly enable assertions */
  29 #undef NDEBUG
  30
  31 #include <string.h>
  32 #include <strings.h>
  33 #include <assert.h>
  34 #include <ipxe/test.h>
  35 #include <ipxe/isqrt.h>
  36
  37 /**
  38  * Force a call to the non-constant implementation of flsl()
  39  *
  40  * @v value             Value
  41  * @ret msb             Most significant bit set in value (LSB=1), or zero
  42  */
  43 __attribute__ (( noinline )) int flsl_var ( long value ) {
  44         return flsl ( value );
  45 }
  46
  47 /**
  48  * Force a call to the non-constant implementation of flsll()
  49  *
  50  * @v value             Value
  51  * @ret msb             Most significant bit set in value (LSB=1), or zero
  52  */
  53 __attribute__ (( noinline )) int flsll_var ( long long value ) {
  54         return flsll ( value );
  55 }
  56
  57 /**
  58  * Check current stack pointer
  59  *
  60  * @ret stack           A value at a fixed offset from the current stack pointer
  61  *
  62  * Used by check_divmod()
  63  */
  64 static __attribute__ (( noinline )) void * stack_check ( void ) {
  65         int a;
  66         void *ret;
  67
  68         /* Hide the fact that we are returning the address of a local
  69          * variable, to prevent a compiler warning.
  70          */
  71         __asm__ ( "\n" : "=g" ( ret ) : "0" ( &a ) );
  72
  73         return ret;
  74 }
  75
  76 /**
  77  * Check division/modulus operation
  78  *
  79  * One aspect of the calling convention for the implicit arithmetic
  80  * functions (__udivmoddi4() etc) is whether the caller or the callee
  81  * is expected to pop any stack-based arguments.  This distinction can
  82  * be masked if the compiler chooses to uses a frame pointer in the
  83  * caller, since the caller will then reload the stack pointer from
  84  * the frame pointer and so can mask an error in the value of the
  85  * stack pointer.
  86  *
  87  * We run the division operation in a loop, and check that the stack
  88  * pointer does not change value on the second iteration.  To prevent
  89  * the compiler from performing various optimisations which might
  90  * invalidate our intended test (such as unrolling the loop, or moving
  91  * the division operation outside the loop), we include some dummy
  92  * inline assembly code.
  93  */
  94 #define check_divmod( dividend, divisor, OP ) ( {                       \
  95         uint64_t result;                                                \
  96         int count = 2;                                                  \
  97         void *check = NULL;                                             \
  98                                                                         \
  99         /* Prevent compiler from unrolling the loop */                  \
 100         __asm__ ( "\n" : "=g" ( count ) : "0" ( count ) );              \
 101                                                                         \
 102         do {                                                            \
 103                 /* Check that stack pointer does not change between     \
 104                  * loop iterations.                                     \
 105                  */                                                     \
 106                 if ( check ) {                                          \
 107                         assert ( check == stack_check() );              \
 108                 } else {                                                \
 109                         check = stack_check();                          \
 110                 }                                                       \
 111                                                                         \
 112                 /* Perform division, preventing the compiler from       \
 113                  * moving the division out of the loop.                 \
 114                  */                                                     \
 115                 __asm__ ( "\n" : "=g" ( dividend ), "=g" ( divisor )    \
 116                           : "0" ( dividend ), "1" ( divisor ) );        \
 117                 result = ( dividend OP divisor );                       \
 118                 __asm__ ( "\n" : "=g" ( result ) : "0" ( result ) );    \
 119                                                                         \
 120         } while ( --count );                                            \
 121         result; } )
 122
 123 /**
 124  * Force a use of runtime 64-bit unsigned integer division
 125  *
 126  * @v dividend          Dividend
 127  * @v divisor           Divisor
 128  * @ret quotient        Quotient
 129  */
 130 __attribute__ (( noinline )) uint64_t u64div_var ( uint64_t dividend,
 131                                                    uint64_t divisor ) {
 132
 133         return check_divmod ( dividend, divisor, / );
 134 }
 135
 136 /**
 137  * Force a use of runtime 64-bit unsigned integer modulus
 138  *
 139  * @v dividend          Dividend
 140  * @v divisor           Divisor
 141  * @ret remainder       Remainder
 142  */
 143 __attribute__ (( noinline )) uint64_t u64mod_var ( uint64_t dividend,
 144                                                    uint64_t divisor ) {
 145
 146         return check_divmod ( dividend, divisor, % );
 147 }
 148
 149 /**
 150  * Force a use of runtime 64-bit signed integer division
 151  *
 152  * @v dividend          Dividend
 153  * @v divisor           Divisor
 154  * @ret quotient        Quotient
 155  */
 156 __attribute__ (( noinline )) int64_t s64div_var ( int64_t dividend,
 157                                                   int64_t divisor ) {
 158
 159         return check_divmod ( dividend, divisor, / );
 160 }
 161
 162 /**
 163  * Force a use of runtime 64-bit unsigned integer modulus
 164  *
 165  * @v dividend          Dividend
 166  * @v divisor           Divisor
 167  * @ret remainder       Remainder
 168  */
 169 __attribute__ (( noinline )) int64_t s64mod_var ( int64_t dividend,
 170                                                   int64_t divisor ) {
 171
 172         return check_divmod ( dividend, divisor, % );
 173 }
 174
 175 /**
 176  * Report a flsl() test result
 177  *
 178  * @v value             Value
 179  * @v msb               Expected MSB
 180  * @v file              Test code file
 181  * @v line              Test code line
 182  */
 183 static inline __attribute__ (( always_inline )) void
 184 flsl_okx ( long value, int msb, const char *file, unsigned int line ) {
 185
 186         /* Verify as a constant (requires to be inlined) */
 187         okx ( flsl ( value ) == msb, file, line );
 188
 189         /* Verify as a non-constant */
 190         okx ( flsl_var ( value ) == msb, file, line );
 191 }
 192 #define flsl_ok( value, msb ) flsl_okx ( value, msb, __FILE__, __LINE__ )
 193
 194 /**
 195  * Report a flsll() test result
 196  *
 197  * @v value             Value
 198  * @v msb               Expected MSB
 199  * @v file              Test code file
 200  * @v line              Test code line
 201  */
 202 static inline __attribute__ (( always_inline )) void
 203 flsll_okx ( long long value, int msb, const char *file, unsigned int line ) {
 204
 205         /* Verify as a constant (requires to be inlined) */
 206         okx ( flsll ( value ) == msb, file, line );
 207
 208         /* Verify as a non-constant */
 209         okx ( flsll_var ( value ) == msb, file, line );
 210 }
 211 #define flsll_ok( value, msb ) flsll_okx ( value, msb, __FILE__, __LINE__ )
 212
 213 /**
 214  * Report a 64-bit unsigned integer division test result
 215  *
 216  * @v dividend          Dividend
 217  * @v divisor           Divisor
 218  * @v quotient          Quotient
 219  * @v remainder         Remainder
 220  * @v file              Test code file
 221  * @v line              Test code line
 222  */
 223 static void u64divmod_okx ( uint64_t dividend, uint64_t divisor,
 224                             uint64_t quotient, uint64_t remainder,
 225                             const char *file, unsigned int line ) {
 226
 227         /* Sanity check */
 228         okx ( ( ( divisor * quotient ) + remainder ) == dividend, file, line );
 229
 230         /* Check division */
 231         okx ( u64div_var ( dividend, divisor ) == quotient, file, line );
 232
 233         /* Check modulus */
 234         okx ( u64mod_var ( dividend, divisor ) == remainder, file, line );
 235 }
 236 #define u64divmod_ok( dividend, divisor, quotient, remainder )  \
 237         u64divmod_okx ( dividend, divisor, quotient, remainder, \
 238                         __FILE__, __LINE__ )
 239
 240 /**
 241  * Report a 64-bit signed integer division test result
 242  *
 243  * @v dividend          Dividend
 244  * @v divisor           Divisor
 245  * @v quotient          Quotient
 246  * @v remainder         Remainder
 247  * @v file              Test code file
 248  * @v line              Test code line
 249  */
 250 static void s64divmod_okx ( int64_t dividend, int64_t divisor,
 251                             int64_t quotient, int64_t remainder,
 252                             const char *file, unsigned int line ) {
 253
 254         /* Sanity check */
 255         okx ( ( ( divisor * quotient ) + remainder ) == dividend, file, line );
 256
 257         /* Check division */
 258         okx ( s64div_var ( dividend, divisor ) == quotient, file, line );
 259
 260         /* Check modulus */
 261         okx ( s64mod_var ( dividend, divisor ) == remainder, file, line );
 262 }
 263 #define s64divmod_ok( dividend, divisor, quotient, remainder )  \
 264         s64divmod_okx ( dividend, divisor, quotient, remainder, \
 265                         __FILE__, __LINE__ )
 266
 267 /**
 268  * Perform mathematical self-tests
 269  *
 270  */
 271 static void math_test_exec ( void ) {
 272
 273         /* Test flsl() */
 274         flsl_ok ( 0, 0 );
 275         flsl_ok ( 1, 1 );
 276         flsl_ok ( 255, 8 );
 277         flsl_ok ( 256, 9 );
 278         flsl_ok ( 257, 9 );
 279         flsl_ok ( 0x69505845, 31 );
 280         flsl_ok ( -1U, ( 8 * sizeof ( int ) ) );
 281         flsl_ok ( -1UL, ( 8 * sizeof ( long ) ) );
 282
 283         /* Test flsll() */
 284         flsll_ok ( 0, 0 );
 285         flsll_ok ( 1, 1 );
 286         flsll_ok ( 0x6d63623330ULL, 39 );
 287         flsll_ok ( -1U, ( 8 * sizeof ( int ) ) );
 288         flsll_ok ( -1UL, ( 8 * sizeof ( long ) ) );
 289         flsll_ok ( -1ULL, ( 8 * sizeof ( long long ) ) );
 290
 291         /* Test 64-bit arithmetic
 292          *
 293          * On a 64-bit machine, these tests are fairly meaningless.
 294          *
 295          * On a 32-bit machine, these tests verify the correct
 296          * operation of our libgcc functions __udivmoddi4()
 297          * etc. (including checking that the implicit calling
 298          * convention assumed by gcc matches our expectations).
 299          */
 300         u64divmod_ok ( 0x2b90ddccf699f765ULL, 0xed9f5e73ULL,
 301                        0x2eef6ab4ULL, 0x0e12f089ULL );
 302         s64divmod_ok ( 0x2b90ddccf699f765ULL, 0xed9f5e73ULL,
 303                        0x2eef6ab4ULL, 0x0e12f089ULL );
 304         u64divmod_ok ( 0xc09e00dcb9e34b54ULL, 0x35968185cdc744f3ULL,
 305                        3, 0x1fda7c4b508d7c7bULL );
 306         s64divmod_ok ( -0x3f61ff23461cb4acLL, 0x35968185cdc744f3ULL,
 307                        -1LL, -0x9cb7d9d78556fb9LL );
 308         u64divmod_ok ( 0, 0x5b2f2737f4ffULL, 0, 0 );
 309         s64divmod_ok ( 0, 0xbb00ded72766207fULL, 0, 0 );
 310
 311         /* Test integer square root */
 312         ok ( isqrt ( 0 ) == 0 );
 313         ok ( isqrt ( 1 ) == 1 );
 314         ok ( isqrt ( 255 ) == 15 );
 315         ok ( isqrt ( 256 ) == 16 );
 316         ok ( isqrt ( 257 ) == 16 );
 317         ok ( isqrt ( 0xa53df2adUL ) == 52652 );
 318         ok ( isqrt ( 0x123793c6UL ) == 17482 );
 319         ok ( isqrt ( -1UL ) == ( -1UL >> ( 8 * sizeof ( unsigned long ) / 2 )));
 320 }
 321
 322 /** Mathematical self-tests */
 323 struct self_test math_test __self_test = {
 324         .name = "math",
 325         .exec = math_test_exec,
 326 };