iPXE
math_test.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 /** @file
00027  *
00028  * Mathematical self-tests
00029  *
00030  */
00031 
00032 /* Forcibly enable assertions */
00033 #undef NDEBUG
00034 
00035 #include <string.h>
00036 #include <strings.h>
00037 #include <assert.h>
00038 #include <ipxe/test.h>
00039 #include <ipxe/isqrt.h>
00040 
00041 /**
00042  * Force a call to the non-constant implementation of ffsl()
00043  *
00044  * @v value             Value
00045  * @ret lsb             Least significant bit set in value (LSB=1), or zero
00046  */
00047 __attribute__ (( noinline )) int ffsl_var ( long value ) {
00048         return ffsl ( value );
00049 }
00050 
00051 /**
00052  * Force a call to the non-constant implementation of ffsll()
00053  *
00054  * @v value             Value
00055  * @ret lsb             Least significant bit set in value (LSB=1), or zero
00056  */
00057 __attribute__ (( noinline )) int ffsll_var ( long long value ) {
00058         return ffsll ( value );
00059 }
00060 
00061 /**
00062  * Force a call to the non-constant implementation of flsl()
00063  *
00064  * @v value             Value
00065  * @ret msb             Most significant bit set in value (LSB=1), or zero
00066  */
00067 __attribute__ (( noinline )) int flsl_var ( long value ) {
00068         return flsl ( value );
00069 }
00070 
00071 /**
00072  * Force a call to the non-constant implementation of flsll()
00073  *
00074  * @v value             Value
00075  * @ret msb             Most significant bit set in value (LSB=1), or zero
00076  */
00077 __attribute__ (( noinline )) int flsll_var ( long long value ) {
00078         return flsll ( value );
00079 }
00080 
00081 /**
00082  * Check current stack pointer
00083  *
00084  * @ret stack           A value at a fixed offset from the current stack pointer
00085  *
00086  * Used by check_divmod()
00087  */
00088 static __attribute__ (( noinline )) void * stack_check ( void ) {
00089         int a;
00090         void *ret;
00091 
00092         /* Hide the fact that we are returning the address of a local
00093          * variable, to prevent a compiler warning.
00094          */
00095         __asm__ ( "\n" : "=g" ( ret ) : "0" ( &a ) );
00096 
00097         return ret;
00098 }
00099 
00100 /**
00101  * Check division/modulus operation
00102  *
00103  * One aspect of the calling convention for the implicit arithmetic
00104  * functions (__udivmoddi4() etc) is whether the caller or the callee
00105  * is expected to pop any stack-based arguments.  This distinction can
00106  * be masked if the compiler chooses to uses a frame pointer in the
00107  * caller, since the caller will then reload the stack pointer from
00108  * the frame pointer and so can mask an error in the value of the
00109  * stack pointer.
00110  *
00111  * We run the division operation in a loop, and check that the stack
00112  * pointer does not change value on the second iteration.  To prevent
00113  * the compiler from performing various optimisations which might
00114  * invalidate our intended test (such as unrolling the loop, or moving
00115  * the division operation outside the loop), we include some dummy
00116  * inline assembly code.
00117  */
00118 #define check_divmod( dividend, divisor, OP ) ( {                       \
00119         uint64_t result;                                                \
00120         int count = 2;                                                  \
00121         void *check = NULL;                                             \
00122                                                                         \
00123         /* Prevent compiler from unrolling the loop */                  \
00124         __asm__ ( "\n" : "=g" ( count ) : "0" ( count ) );              \
00125                                                                         \
00126         do {                                                            \
00127                 /* Check that stack pointer does not change between     \
00128                  * loop iterations.                                     \
00129                  */                                                     \
00130                 if ( check ) {                                          \
00131                         assert ( check == stack_check() );              \
00132                 } else {                                                \
00133                         check = stack_check();                          \
00134                 }                                                       \
00135                                                                         \
00136                 /* Perform division, preventing the compiler from       \
00137                  * moving the division out of the loop.                 \
00138                  */                                                     \
00139                 __asm__ ( "\n" : "=g" ( dividend ), "=g" ( divisor )    \
00140                           : "0" ( dividend ), "1" ( divisor ) );        \
00141                 result = ( dividend OP divisor );                       \
00142                 __asm__ ( "\n" : "=g" ( result ) : "0" ( result ) );    \
00143                                                                         \
00144         } while ( --count );                                            \
00145         result; } )
00146 
00147 /**
00148  * Force a use of runtime 64-bit unsigned integer division
00149  *
00150  * @v dividend          Dividend
00151  * @v divisor           Divisor
00152  * @ret quotient        Quotient
00153  */
00154 __attribute__ (( noinline )) uint64_t u64div_var ( uint64_t dividend,
00155                                                    uint64_t divisor ) {
00156 
00157         return check_divmod ( dividend, divisor, / );
00158 }
00159 
00160 /**
00161  * Force a use of runtime 64-bit unsigned integer modulus
00162  *
00163  * @v dividend          Dividend
00164  * @v divisor           Divisor
00165  * @ret remainder       Remainder
00166  */
00167 __attribute__ (( noinline )) uint64_t u64mod_var ( uint64_t dividend,
00168                                                    uint64_t divisor ) {
00169 
00170         return check_divmod ( dividend, divisor, % );
00171 }
00172 
00173 /**
00174  * Force a use of runtime 64-bit signed integer division
00175  *
00176  * @v dividend          Dividend
00177  * @v divisor           Divisor
00178  * @ret quotient        Quotient
00179  */
00180 __attribute__ (( noinline )) int64_t s64div_var ( int64_t dividend,
00181                                                   int64_t divisor ) {
00182 
00183         return check_divmod ( dividend, divisor, / );
00184 }
00185 
00186 /**
00187  * Force a use of runtime 64-bit unsigned integer modulus
00188  *
00189  * @v dividend          Dividend
00190  * @v divisor           Divisor
00191  * @ret remainder       Remainder
00192  */
00193 __attribute__ (( noinline )) int64_t s64mod_var ( int64_t dividend,
00194                                                   int64_t divisor ) {
00195 
00196         return check_divmod ( dividend, divisor, % );
00197 }
00198 
00199 /**
00200  * Report a ffsl() test result
00201  *
00202  * @v value             Value
00203  * @v lsb               Expected LSB
00204  * @v file              Test code file
00205  * @v line              Test code line
00206  */
00207 static inline __attribute__ (( always_inline )) void
00208 ffsl_okx ( long value, int lsb, const char *file, unsigned int line ) {
00209 
00210         /* Verify as a constant (requires to be inlined) */
00211         okx ( ffsl ( value ) == lsb, file, line );
00212 
00213         /* Verify as a non-constant */
00214         okx ( ffsl_var ( value ) == lsb, file, line );
00215 }
00216 #define ffsl_ok( value, lsb ) ffsl_okx ( value, lsb, __FILE__, __LINE__ )
00217 
00218 /**
00219  * Report a ffsll() test result
00220  *
00221  * @v value             Value
00222  * @v lsb               Expected LSB
00223  * @v file              Test code file
00224  * @v line              Test code line
00225  */
00226 static inline __attribute__ (( always_inline )) void
00227 ffsll_okx ( long long value, int lsb, const char *file, unsigned int line ) {
00228 
00229         /* Verify as a constant (requires to be inlined) */
00230         okx ( ffsll ( value ) == lsb, file, line );
00231 
00232         /* Verify as a non-constant */
00233         okx ( ffsll_var ( value ) == lsb, file, line );
00234 }
00235 #define ffsll_ok( value, lsb ) ffsll_okx ( value, lsb, __FILE__, __LINE__ )
00236 
00237 /**
00238  * Report a flsl() test result
00239  *
00240  * @v value             Value
00241  * @v msb               Expected MSB
00242  * @v file              Test code file
00243  * @v line              Test code line
00244  */
00245 static inline __attribute__ (( always_inline )) void
00246 flsl_okx ( long value, int msb, const char *file, unsigned int line ) {
00247 
00248         /* Verify as a constant (requires to be inlined) */
00249         okx ( flsl ( value ) == msb, file, line );
00250 
00251         /* Verify as a non-constant */
00252         okx ( flsl_var ( value ) == msb, file, line );
00253 }
00254 #define flsl_ok( value, msb ) flsl_okx ( value, msb, __FILE__, __LINE__ )
00255 
00256 /**
00257  * Report a flsll() test result
00258  *
00259  * @v value             Value
00260  * @v msb               Expected MSB
00261  * @v file              Test code file
00262  * @v line              Test code line
00263  */
00264 static inline __attribute__ (( always_inline )) void
00265 flsll_okx ( long long value, int msb, const char *file, unsigned int line ) {
00266 
00267         /* Verify as a constant (requires to be inlined) */
00268         okx ( flsll ( value ) == msb, file, line );
00269 
00270         /* Verify as a non-constant */
00271         okx ( flsll_var ( value ) == msb, file, line );
00272 }
00273 #define flsll_ok( value, msb ) flsll_okx ( value, msb, __FILE__, __LINE__ )
00274 
00275 /**
00276  * Report a 64-bit unsigned integer division test result
00277  *
00278  * @v dividend          Dividend
00279  * @v divisor           Divisor
00280  * @v quotient          Quotient
00281  * @v remainder         Remainder
00282  * @v file              Test code file
00283  * @v line              Test code line
00284  */
00285 static void u64divmod_okx ( uint64_t dividend, uint64_t divisor,
00286                             uint64_t quotient, uint64_t remainder,
00287                             const char *file, unsigned int line ) {
00288 
00289         /* Sanity check */
00290         okx ( ( ( divisor * quotient ) + remainder ) == dividend, file, line );
00291 
00292         /* Check division */
00293         okx ( u64div_var ( dividend, divisor ) == quotient, file, line );
00294 
00295         /* Check modulus */
00296         okx ( u64mod_var ( dividend, divisor ) == remainder, file, line );
00297 }
00298 #define u64divmod_ok( dividend, divisor, quotient, remainder )  \
00299         u64divmod_okx ( dividend, divisor, quotient, remainder, \
00300                         __FILE__, __LINE__ )
00301 
00302 /**
00303  * Report a 64-bit signed integer division test result
00304  *
00305  * @v dividend          Dividend
00306  * @v divisor           Divisor
00307  * @v quotient          Quotient
00308  * @v remainder         Remainder
00309  * @v file              Test code file
00310  * @v line              Test code line
00311  */
00312 static void s64divmod_okx ( int64_t dividend, int64_t divisor,
00313                             int64_t quotient, int64_t remainder,
00314                             const char *file, unsigned int line ) {
00315 
00316         /* Sanity check */
00317         okx ( ( ( divisor * quotient ) + remainder ) == dividend, file, line );
00318 
00319         /* Check division */
00320         okx ( s64div_var ( dividend, divisor ) == quotient, file, line );
00321 
00322         /* Check modulus */
00323         okx ( s64mod_var ( dividend, divisor ) == remainder, file, line );
00324 }
00325 #define s64divmod_ok( dividend, divisor, quotient, remainder )  \
00326         s64divmod_okx ( dividend, divisor, quotient, remainder, \
00327                         __FILE__, __LINE__ )
00328 
00329 /**
00330  * Perform mathematical self-tests
00331  *
00332  */
00333 static void math_test_exec ( void ) {
00334 
00335         /* Test ffsl() */
00336         ffsl_ok ( 0, 0 );
00337         ffsl_ok ( 1, 1 );
00338         ffsl_ok ( 255, 1 );
00339         ffsl_ok ( 256, 9 );
00340         ffsl_ok ( 257, 1 );
00341         ffsl_ok ( 0x54850596, 2 );
00342         ffsl_ok ( 0x80000000, 32 );
00343 
00344         /* Test ffsll() */
00345         ffsll_ok ( 0, 0 );
00346         ffsll_ok ( 1, 1 );
00347         ffsll_ok ( 0x6d63623330ULL, 5 );
00348         ffsll_ok ( 0x80000000UL, 32 );
00349         ffsll_ok ( 0x8000000000000000ULL, 64 );
00350 
00351         /* Test flsl() */
00352         flsl_ok ( 0, 0 );
00353         flsl_ok ( 1, 1 );
00354         flsl_ok ( 255, 8 );
00355         flsl_ok ( 256, 9 );
00356         flsl_ok ( 257, 9 );
00357         flsl_ok ( 0x69505845, 31 );
00358         flsl_ok ( -1U, ( 8 * sizeof ( int ) ) );
00359         flsl_ok ( -1UL, ( 8 * sizeof ( long ) ) );
00360 
00361         /* Test flsll() */
00362         flsll_ok ( 0, 0 );
00363         flsll_ok ( 1, 1 );
00364         flsll_ok ( 0x6d63623330ULL, 39 );
00365         flsll_ok ( -1U, ( 8 * sizeof ( int ) ) );
00366         flsll_ok ( -1UL, ( 8 * sizeof ( long ) ) );
00367         flsll_ok ( -1ULL, ( 8 * sizeof ( long long ) ) );
00368 
00369         /* Test 64-bit arithmetic
00370          *
00371          * On a 64-bit machine, these tests are fairly meaningless.
00372          *
00373          * On a 32-bit machine, these tests verify the correct
00374          * operation of our libgcc functions __udivmoddi4()
00375          * etc. (including checking that the implicit calling
00376          * convention assumed by gcc matches our expectations).
00377          */
00378         u64divmod_ok ( 0x2b90ddccf699f765ULL, 0xed9f5e73ULL,
00379                        0x2eef6ab4ULL, 0x0e12f089ULL );
00380         s64divmod_ok ( 0x2b90ddccf699f765ULL, 0xed9f5e73ULL,
00381                        0x2eef6ab4ULL, 0x0e12f089ULL );
00382         u64divmod_ok ( 0xc09e00dcb9e34b54ULL, 0x35968185cdc744f3ULL,
00383                        3, 0x1fda7c4b508d7c7bULL );
00384         s64divmod_ok ( -0x3f61ff23461cb4acLL, 0x35968185cdc744f3ULL,
00385                        -1LL, -0x9cb7d9d78556fb9LL );
00386         u64divmod_ok ( 0, 0x5b2f2737f4ffULL, 0, 0 );
00387         s64divmod_ok ( 0, 0xbb00ded72766207fULL, 0, 0 );
00388 
00389         /* Test integer square root */
00390         ok ( isqrt ( 0 ) == 0 );
00391         ok ( isqrt ( 1 ) == 1 );
00392         ok ( isqrt ( 255 ) == 15 );
00393         ok ( isqrt ( 256 ) == 16 );
00394         ok ( isqrt ( 257 ) == 16 );
00395         ok ( isqrt ( 0xa53df2adUL ) == 52652 );
00396         ok ( isqrt ( 0x123793c6UL ) == 17482 );
00397         ok ( isqrt ( -1UL ) == ( -1UL >> ( 8 * sizeof ( unsigned long ) / 2 )));
00398 }
00399 
00400 /** Mathematical self-tests */
00401 struct self_test math_test __self_test = {
00402         .name = "math",
00403         .exec = math_test_exec,
00404 };