/
githubmirror
/
ipxe
Обзор
Документация
Войти
/
githubmirror
/
ipxe
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/tests/math_test.c
521 строка
15 KB
Michael Brown
[test] Add tests for 64-bit logical and arithmetic shifts
15 сен 2024, 12:01
15 сен 2024, 12:01
1d43e53
Код
Авторство
О чём код?
/* * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of the * License, or any later version. * * This program is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA * 02110-1301, USA. * * You can also choose to distribute this program under the terms of * the Unmodified Binary Distribution Licence (as given in the file * COPYING.UBDL), provided that you have satisfied its requirements. */ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); /** @file * * Mathematical self-tests * */ /* Forcibly enable assertions */ #undef NDEBUG #include <string.h> #include <strings.h> #include <assert.h> #include <ipxe/test.h> #include <ipxe/isqrt.h> /** * Force a call to the non-constant implementation of ffsl() * * @v value Value * @ret lsb Least significant bit set in value (LSB=1), or zero */ __attribute__ (( noinline )) int ffsl_var ( long value ) { return ffsl ( value ); } /** * Force a call to the non-constant implementation of ffsll() * * @v value Value * @ret lsb Least significant bit set in value (LSB=1), or zero */ __attribute__ (( noinline )) int ffsll_var ( long long value ) { return ffsll ( value ); } /** * Force a call to the non-constant implementation of flsl() * * @v value Value * @ret msb Most significant bit set in value (LSB=1), or zero */ __attribute__ (( noinline )) int flsl_var ( long value ) { return flsl ( value ); } /** * Force a call to the non-constant implementation of flsll() * * @v value Value * @ret msb Most significant bit set in value (LSB=1), or zero */ __attribute__ (( noinline )) int flsll_var ( long long value ) { return flsll ( value ); } /** * Force a use of runtime 64-bit shift left * * @v value Value * @v shift Shift amount * @ret value Shifted value */ __attribute__ (( noinline )) uint64_t lsl64_var ( uint64_t value, unsigned int shift ) { return ( value << shift ); } /** * Force a use of runtime 64-bit logical shift right * * @v value Value * @v shift Shift amount * @ret value Shifted value */ __attribute__ (( noinline )) uint64_t lsr64_var ( uint64_t value, unsigned int shift ) { return ( value >> shift ); } /** * Force a use of runtime 64-bit arithmetic shift right * * @v value Value * @v shift Shift amount * @ret value Shifted value */ __attribute__ (( noinline )) int64_t asr64_var ( int64_t value, unsigned int shift ) { return ( value >> shift ); } /** * Check current stack pointer * * @ret stack A value at a fixed offset from the current stack pointer * * Used by check_divmod() */ static __attribute__ (( noinline )) void * stack_check ( void ) { int a; void *ret; /* Hide the fact that we are returning the address of a local * variable, to prevent a compiler warning. */ __asm__ ( "\n" : "=g" ( ret ) : "0" ( &a ) ); return ret; } /** * Check division/modulus operation * * One aspect of the calling convention for the implicit arithmetic * functions (__udivmoddi4() etc) is whether the caller or the callee * is expected to pop any stack-based arguments. This distinction can * be masked if the compiler chooses to uses a frame pointer in the * caller, since the caller will then reload the stack pointer from * the frame pointer and so can mask an error in the value of the * stack pointer. * * We run the division operation in a loop, and check that the stack * pointer does not change value on the second iteration. To prevent * the compiler from performing various optimisations which might * invalidate our intended test (such as unrolling the loop, or moving * the division operation outside the loop), we include some dummy * inline assembly code. */ #define check_divmod( dividend, divisor, OP ) ( { \ uint64_t result; \ int count = 2; \ void *check = NULL; \ \ /* Prevent compiler from unrolling the loop */ \ __asm__ ( "\n" : "=g" ( count ) : "0" ( count ) ); \ \ do { \ /* Check that stack pointer does not change between \ * loop iterations. \ */ \ if ( check ) { \ assert ( check == stack_check() ); \ } else { \ check = stack_check(); \ } \ \ /* Perform division, preventing the compiler from \ * moving the division out of the loop. \ */ \ __asm__ ( "\n" : "=g" ( dividend ), "=g" ( divisor ) \ : "0" ( dividend ), "1" ( divisor ) ); \ result = ( dividend OP divisor ); \ __asm__ ( "\n" : "=g" ( result ) : "0" ( result ) ); \ \ } while ( --count ); \ result; } ) /** * Force a use of runtime 64-bit unsigned integer division * * @v dividend Dividend * @v divisor Divisor * @ret quotient Quotient */ __attribute__ (( noinline )) uint64_t u64div_var ( uint64_t dividend, uint64_t divisor ) { return check_divmod ( dividend, divisor, / ); } /** * Force a use of runtime 64-bit unsigned integer modulus * * @v dividend Dividend * @v divisor Divisor * @ret remainder Remainder */ __attribute__ (( noinline )) uint64_t u64mod_var ( uint64_t dividend, uint64_t divisor ) { return check_divmod ( dividend, divisor, % ); } /** * Force a use of runtime 64-bit signed integer division * * @v dividend Dividend * @v divisor Divisor * @ret quotient Quotient */ __attribute__ (( noinline )) int64_t s64div_var ( int64_t dividend, int64_t divisor ) { return check_divmod ( dividend, divisor, / ); } /** * Force a use of runtime 64-bit unsigned integer modulus * * @v dividend Dividend * @v divisor Divisor * @ret remainder Remainder */ __attribute__ (( noinline )) int64_t s64mod_var ( int64_t dividend, int64_t divisor ) { return check_divmod ( dividend, divisor, % ); } /** * Report a ffsl() test result * * @v value Value * @v lsb Expected LSB * @v file Test code file * @v line Test code line */ static inline __attribute__ (( always_inline )) void ffsl_okx ( long value, int lsb, const char *file, unsigned int line ) { /* Verify as a constant (requires to be inlined) */ okx ( ffsl ( value ) == lsb, file, line ); /* Verify as a non-constant */ okx ( ffsl_var ( value ) == lsb, file, line ); } #define ffsl_ok( value, lsb ) ffsl_okx ( value, lsb, __FILE__, __LINE__ ) /** * Report a ffsll() test result * * @v value Value * @v lsb Expected LSB * @v file Test code file * @v line Test code line */ static inline __attribute__ (( always_inline )) void ffsll_okx ( long long value, int lsb, const char *file, unsigned int line ) { /* Verify as a constant (requires to be inlined) */ okx ( ffsll ( value ) == lsb, file, line ); /* Verify as a non-constant */ okx ( ffsll_var ( value ) == lsb, file, line ); } #define ffsll_ok( value, lsb ) ffsll_okx ( value, lsb, __FILE__, __LINE__ ) /** * Report a flsl() test result * * @v value Value * @v msb Expected MSB * @v file Test code file * @v line Test code line */ static inline __attribute__ (( always_inline )) void flsl_okx ( long value, int msb, const char *file, unsigned int line ) { /* Verify as a constant (requires to be inlined) */ okx ( flsl ( value ) == msb, file, line ); /* Verify as a non-constant */ okx ( flsl_var ( value ) == msb, file, line ); } #define flsl_ok( value, msb ) flsl_okx ( value, msb, __FILE__, __LINE__ ) /** * Report a flsll() test result * * @v value Value * @v msb Expected MSB * @v file Test code file * @v line Test code line */ static inline __attribute__ (( always_inline )) void flsll_okx ( long long value, int msb, const char *file, unsigned int line ) { /* Verify as a constant (requires to be inlined) */ okx ( flsll ( value ) == msb, file, line ); /* Verify as a non-constant */ okx ( flsll_var ( value ) == msb, file, line ); } #define flsll_ok( value, msb ) flsll_okx ( value, msb, __FILE__, __LINE__ ) /** * Report a 64-bit shift left test result * * @v value Value * @v shift Shift amount * @v expected Expected value * @v file Test code file * @v line Test code line */ static inline __attribute__ (( always_inline )) void lsl64_okx ( uint64_t value, unsigned int shift, uint64_t expected, const char *file, unsigned int line ) { /* Verify as a compile-time calculation */ okx ( ( value << shift ) == expected, file, line ); /* Verify as a runtime calculation */ okx ( lsl64_var ( value, shift ) == expected, file, line ); } #define lsl64_ok( value, shift, expected ) \ lsl64_okx ( value, shift, expected, __FILE__, __LINE__ ) /** * Report a 64-bit logical shift right test result * * @v value Value * @v shift Shift amount * @v expected Expected value * @v file Test code file * @v line Test code line */ static inline __attribute__ (( always_inline )) void lsr64_okx ( uint64_t value, unsigned int shift, uint64_t expected, const char *file, unsigned int line ) { /* Verify as a compile-time calculation */ okx ( ( value >> shift ) == expected, file, line ); /* Verify as a runtime calculation */ okx ( lsr64_var ( value, shift ) == expected, file, line ); } #define lsr64_ok( value, shift, expected ) \ lsr64_okx ( value, shift, expected, __FILE__, __LINE__ ) /** * Report a 64-bit arithmetic shift right test result * * @v value Value * @v shift Shift amount * @v expected Expected value * @v file Test code file * @v line Test code line */ static inline __attribute__ (( always_inline )) void asr64_okx ( int64_t value, unsigned int shift, int64_t expected, const char *file, unsigned int line ) { /* Verify as a compile-time calculation */ okx ( ( value >> shift ) == expected, file, line ); /* Verify as a runtime calculation */ okx ( asr64_var ( value, shift ) == expected, file, line ); } #define asr64_ok( value, shift, expected ) \ asr64_okx ( value, shift, expected, __FILE__, __LINE__ ) /** * Report a 64-bit unsigned integer division test result * * @v dividend Dividend * @v divisor Divisor * @v quotient Quotient * @v remainder Remainder * @v file Test code file * @v line Test code line */ static void u64divmod_okx ( uint64_t dividend, uint64_t divisor, uint64_t quotient, uint64_t remainder, const char *file, unsigned int line ) { /* Sanity check */ okx ( ( ( divisor * quotient ) + remainder ) == dividend, file, line ); /* Check division */ okx ( u64div_var ( dividend, divisor ) == quotient, file, line ); /* Check modulus */ okx ( u64mod_var ( dividend, divisor ) == remainder, file, line ); } #define u64divmod_ok( dividend, divisor, quotient, remainder ) \ u64divmod_okx ( dividend, divisor, quotient, remainder, \ __FILE__, __LINE__ ) /** * Report a 64-bit signed integer division test result * * @v dividend Dividend * @v divisor Divisor * @v quotient Quotient * @v remainder Remainder * @v file Test code file * @v line Test code line */ static void s64divmod_okx ( int64_t dividend, int64_t divisor, int64_t quotient, int64_t remainder, const char *file, unsigned int line ) { /* Sanity check */ okx ( ( ( divisor * quotient ) + remainder ) == dividend, file, line ); /* Check division */ okx ( s64div_var ( dividend, divisor ) == quotient, file, line ); /* Check modulus */ okx ( s64mod_var ( dividend, divisor ) == remainder, file, line ); } #define s64divmod_ok( dividend, divisor, quotient, remainder ) \ s64divmod_okx ( dividend, divisor, quotient, remainder, \ __FILE__, __LINE__ ) /** * Perform mathematical self-tests * */ static void math_test_exec ( void ) { /* Test ffsl() */ ffsl_ok ( 0, 0 ); ffsl_ok ( 1, 1 ); ffsl_ok ( 255, 1 ); ffsl_ok ( 256, 9 ); ffsl_ok ( 257, 1 ); ffsl_ok ( 0x54850596, 2 ); ffsl_ok ( 0x80000000, 32 ); /* Test ffsll() */ ffsll_ok ( 0, 0 ); ffsll_ok ( 1, 1 ); ffsll_ok ( 0x6d63623330ULL, 5 ); ffsll_ok ( 0x80000000UL, 32 ); ffsll_ok ( 0x8000000000000000ULL, 64 ); /* Test flsl() */ flsl_ok ( 0, 0 ); flsl_ok ( 1, 1 ); flsl_ok ( 255, 8 ); flsl_ok ( 256, 9 ); flsl_ok ( 257, 9 ); flsl_ok ( 0x69505845, 31 ); flsl_ok ( -1U, ( 8 * sizeof ( int ) ) ); flsl_ok ( -1UL, ( 8 * sizeof ( long ) ) ); /* Test flsll() */ flsll_ok ( 0, 0 ); flsll_ok ( 1, 1 ); flsll_ok ( 0x6d63623330ULL, 39 ); flsll_ok ( -1U, ( 8 * sizeof ( int ) ) ); flsll_ok ( -1UL, ( 8 * sizeof ( long ) ) ); flsll_ok ( -1ULL, ( 8 * sizeof ( long long ) ) ); /* Test 64-bit arithmetic * * On a 64-bit machine, these tests are fairly meaningless. * * On a 32-bit machine, these tests verify the correct * operation of our libgcc functions __udivmoddi4() * etc. (including checking that the implicit calling * convention assumed by gcc matches our expectations). */ lsl64_ok ( 0x06760c14710540c2ULL, 0, 0x06760c14710540c2ULL ); lsr64_ok ( 0x06760c14710540c2ULL, 0, 0x06760c14710540c2ULL ); asr64_ok ( 0x06760c14710540c2ULL, 0, 0x06760c14710540c2ULL ); lsl64_ok ( 0xccafd1a8cb724c13ULL, 20, 0x1a8cb724c1300000ULL ); lsr64_ok ( 0xccafd1a8cb724c13ULL, 20, 0x00000ccafd1a8cb7ULL ); asr64_ok ( 0xccafd1a8cb724c13ULL, 20, 0xfffffccafd1a8cb7ULL ); lsl64_ok ( 0x83567264b1234518ULL, 32, 0xb123451800000000ULL ); lsr64_ok ( 0x83567264b1234518ULL, 32, 0x0000000083567264ULL ); asr64_ok ( 0x83567264b1234518ULL, 32, 0xffffffff83567264ULL ); lsl64_ok ( 0x69ee42fcbf1a4ea4ULL, 47, 0x2752000000000000ULL ); lsr64_ok ( 0x69ee42fcbf1a4ea4ULL, 47, 0x000000000000d3dcULL ); asr64_ok ( 0x69ee42fcbf1a4ea4ULL, 47, 0x000000000000d3dcULL ); lsl64_ok ( 0xaa20b8caddee4269ULL, 63, 0x8000000000000000ULL ); lsr64_ok ( 0xaa20b8caddee4269ULL, 63, 0x0000000000000001ULL ); asr64_ok ( 0xaa20b8caddee4269ULL, 63, 0xffffffffffffffffULL ); u64divmod_ok ( 0x2b90ddccf699f765ULL, 0xed9f5e73ULL, 0x2eef6ab4ULL, 0x0e12f089ULL ); s64divmod_ok ( 0x2b90ddccf699f765ULL, 0xed9f5e73ULL, 0x2eef6ab4ULL, 0x0e12f089ULL ); u64divmod_ok ( 0xc09e00dcb9e34b54ULL, 0x35968185cdc744f3ULL, 3, 0x1fda7c4b508d7c7bULL ); s64divmod_ok ( -0x3f61ff23461cb4acLL, 0x35968185cdc744f3ULL, -1LL, -0x9cb7d9d78556fb9LL ); u64divmod_ok ( 0, 0x5b2f2737f4ffULL, 0, 0 ); s64divmod_ok ( 0, 0xbb00ded72766207fULL, 0, 0 ); /* Test integer square root */ ok ( isqrt ( 0 ) == 0 ); ok ( isqrt ( 1 ) == 1 ); ok ( isqrt ( 255 ) == 15 ); ok ( isqrt ( 256 ) == 16 ); ok ( isqrt ( 257 ) == 16 ); ok ( isqrt ( 0xa53df2adUL ) == 52652 ); ok ( isqrt ( 0x123793c6UL ) == 17482 ); ok ( isqrt ( -1UL ) == ( -1UL >> ( 8 * sizeof ( unsigned long ) / 2 ))); } /** Mathematical self-tests */ struct self_test math_test __self_test = { .name = "math", .exec = math_test_exec, };