math_test.c File Reference

Mathematical self-tests. More...

#include <string.h>
#include <strings.h>
#include <assert.h>
#include <ipxe/test.h>
#include <ipxe/isqrt.h>

Go to the source code of this file.

Macros
#define	check_divmod(dividend, divisor, OP)
	Check division/modulus operation. More...
#define	ffsl_ok(value, lsb)   ffsl_okx ( value, lsb, __FILE__, __LINE__ )
#define	ffsll_ok(value, lsb)   ffsll_okx ( value, lsb, __FILE__, __LINE__ )
#define	flsl_ok(value, msb)   flsl_okx ( value, msb, __FILE__, __LINE__ )
#define	flsll_ok(value, msb)   flsll_okx ( value, msb, __FILE__, __LINE__ )
#define	lsl64_ok(value, shift, expected)   lsl64_okx ( value, shift, expected, __FILE__, __LINE__ )
#define	lsr64_ok(value, shift, expected)   lsr64_okx ( value, shift, expected, __FILE__, __LINE__ )
#define	asr64_ok(value, shift, expected)   asr64_okx ( value, shift, expected, __FILE__, __LINE__ )
#define	u64divmod_ok(dividend, divisor, quotient, remainder)
#define	s64divmod_ok(dividend, divisor, quotient, remainder)

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
int	ffsl_var (long value)
	Force a call to the non-constant implementation of ffsl() More...
int	ffsll_var (long long value)
	Force a call to the non-constant implementation of ffsll() More...
int	flsl_var (long value)
	Force a call to the non-constant implementation of flsl() More...
int	flsll_var (long long value)
	Force a call to the non-constant implementation of flsll() More...
uint64_t	lsl64_var (uint64_t value, unsigned int shift)
	Force a use of runtime 64-bit shift left. More...
uint64_t	lsr64_var (uint64_t value, unsigned int shift)
	Force a use of runtime 64-bit logical shift right. More...
int64_t	asr64_var (int64_t value, unsigned int shift)
	Force a use of runtime 64-bit arithmetic shift right. More...
static void *	stack_check (void)
	Check current stack pointer. More...
uint64_t	u64div_var (uint64_t dividend, uint64_t divisor)
	Force a use of runtime 64-bit unsigned integer division. More...
uint64_t	u64mod_var (uint64_t dividend, uint64_t divisor)
	Force a use of runtime 64-bit unsigned integer modulus. More...
int64_t	s64div_var (int64_t dividend, int64_t divisor)
	Force a use of runtime 64-bit signed integer division. More...
int64_t	s64mod_var (int64_t dividend, int64_t divisor)
	Force a use of runtime 64-bit unsigned integer modulus. More...
static void	ffsl_okx (long value, int lsb, const char *file, unsigned int line)
	Report a ffsl() test result. More...
static void	ffsll_okx (long long value, int lsb, const char *file, unsigned int line)
	Report a ffsll() test result. More...
static void	flsl_okx (long value, int msb, const char *file, unsigned int line)
	Report a flsl() test result. More...
static void	flsll_okx (long long value, int msb, const char *file, unsigned int line)
	Report a flsll() test result. More...
static void	lsl64_okx (uint64_t value, unsigned int shift, uint64_t expected, const char *file, unsigned int line)
	Report a 64-bit shift left test result. More...
static void	lsr64_okx (uint64_t value, unsigned int shift, uint64_t expected, const char *file, unsigned int line)
	Report a 64-bit logical shift right test result. More...
static void	asr64_okx (int64_t value, unsigned int shift, int64_t expected, const char *file, unsigned int line)
	Report a 64-bit arithmetic shift right test result. More...
static void	u64divmod_okx (uint64_t dividend, uint64_t divisor, uint64_t quotient, uint64_t remainder, const char *file, unsigned int line)
	Report a 64-bit unsigned integer division test result. More...
static void	s64divmod_okx (int64_t dividend, int64_t divisor, int64_t quotient, int64_t remainder, const char *file, unsigned int line)
	Report a 64-bit signed integer division test result. More...
static void	math_test_exec (void)
	Perform mathematical self-tests. More...

Variables
struct self_test math_test	__self_test
	Mathematical self-tests. More...

Detailed Description

Mathematical self-tests.

Definition in file math_test.c.

Macro Definition Documentation

check_divmod

#define check_divmod	(		dividend,
			divisor,
			OP
	)

Value:

( {                     \
        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; } )

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.

Definition at line 154 of file math_test.c.

ffsl_ok

#define ffsl_ok	(		value,
			lsb
	)		ffsl_okx ( value, lsb, __FILE__, __LINE__ )

Definition at line 252 of file math_test.c.

ffsll_ok

#define ffsll_ok	(		value,
			lsb
	)		ffsll_okx ( value, lsb, __FILE__, __LINE__ )

Definition at line 271 of file math_test.c.

flsl_ok

#define flsl_ok	(		value,
			msb
	)		flsl_okx ( value, msb, __FILE__, __LINE__ )

Definition at line 290 of file math_test.c.

flsll_ok

#define flsll_ok	(		value,
			msb
	)		flsll_okx ( value, msb, __FILE__, __LINE__ )

Definition at line 309 of file math_test.c.

lsl64_ok

#define lsl64_ok	(		value,
			shift,
			expected
	)		lsl64_okx ( value, shift, expected, __FILE__, __LINE__ )

Definition at line 330 of file math_test.c.

lsr64_ok

#define lsr64_ok	(		value,
			shift,
			expected
	)		lsr64_okx ( value, shift, expected, __FILE__, __LINE__ )

Definition at line 352 of file math_test.c.

asr64_ok

#define asr64_ok	(		value,
			shift,
			expected
	)		asr64_okx ( value, shift, expected, __FILE__, __LINE__ )

Definition at line 374 of file math_test.c.

u64divmod_ok

#define u64divmod_ok	(		dividend,
			divisor,
			quotient,
			remainder
	)

Value:

u64divmod_okx ( dividend, divisor, quotient, remainder, \
                        __FILE__, __LINE__ )

Definition at line 400 of file math_test.c.

s64divmod_ok

#define s64divmod_ok	(		dividend,
			divisor,
			quotient,
			remainder
	)

Value:

s64divmod_okx ( dividend, divisor, quotient, remainder, \
                        __FILE__, __LINE__ )

Definition at line 427 of file math_test.c.

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

ffsl_var()

int ffsl_var

(

long

value

)

Force a call to the non-constant implementation of ffsl()

Parameters

value

Value

Return values

lsb	Least significant bit set in value (LSB=1), or zero

Definition at line 47 of file math_test.c.

                                                         {
        return ffsl ( value );
}

References ffsl, and value.

Referenced by ffsl_okx().

ffsll_var()

int ffsll_var

(

long long

value

)

Force a call to the non-constant implementation of ffsll()

Parameters

value

Value

Return values

lsb	Least significant bit set in value (LSB=1), or zero

Definition at line 57 of file math_test.c.

                                                               {
        return ffsll ( value );
}

References ffsll, and value.

Referenced by ffsll_okx().

flsl_var()

int flsl_var

(

long

value

)

Force a call to the non-constant implementation of flsl()

Parameters

value

Value

Return values

msb	Most significant bit set in value (LSB=1), or zero

Definition at line 67 of file math_test.c.

                                                         {
        return flsl ( value );
}

References flsl, and value.

Referenced by flsl_okx().

flsll_var()

int flsll_var

(

long long

value

)

Force a call to the non-constant implementation of flsll()

Parameters

value

Value

Return values

msb	Most significant bit set in value (LSB=1), or zero

Definition at line 77 of file math_test.c.

                                                               {
        return flsll ( value );
}

References flsll, and value.

Referenced by flsll_okx().

lsl64_var()

uint64_t lsl64_var	(	uint64_t	value,
		unsigned int	shift
	)

Force a use of runtime 64-bit shift left.

Parameters

value	Value
shift	Shift amount

Return values

value

Shifted value

Definition at line 88 of file math_test.c.

                                                                       {
        return ( value << shift );
}

References value.

Referenced by lsl64_okx().

lsr64_var()

uint64_t lsr64_var	(	uint64_t	value,
		unsigned int	shift
	)

Force a use of runtime 64-bit logical shift right.

Parameters

value	Value
shift	Shift amount

Return values

value

Shifted value

Definition at line 100 of file math_test.c.

                                                                       {
        return ( value >> shift );
}

References value.

Referenced by lsr64_okx().

asr64_var()

int64_t asr64_var	(	int64_t	value,
		unsigned int	shift
	)

Force a use of runtime 64-bit arithmetic shift right.

Parameters

value	Value
shift	Shift amount

Return values

value

Shifted value

Definition at line 112 of file math_test.c.

                                                                      {
        return ( value >> shift );
}

References value.

Referenced by asr64_okx().

stack_check()

static void* stack_check ( void  )

static

Check current stack pointer.

Return values

stack

A value at a fixed offset from the current stack pointer

Used by check_divmod()

Definition at line 124 of file math_test.c.

                                                                {
        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;
}

References __asm__().

u64div_var()

uint64_t u64div_var	(	uint64_t	dividend,
		uint64_t	divisor
	)

Force a use of runtime 64-bit unsigned integer division.

Parameters

dividend	Dividend
divisor	Divisor

Return values

quotient

Quotient

Definition at line 190 of file math_test.c.

                                                                      {

        return check_divmod ( dividend, divisor, / );
}

References check_divmod.

Referenced by u64divmod_okx().

u64mod_var()

uint64_t u64mod_var	(	uint64_t	dividend,
		uint64_t	divisor
	)

Force a use of runtime 64-bit unsigned integer modulus.

Parameters

dividend	Dividend
divisor	Divisor

Return values

remainder

Remainder

Definition at line 203 of file math_test.c.

                                                                      {

        return check_divmod ( dividend, divisor, % );
}

References check_divmod.

Referenced by u64divmod_okx().

s64div_var()

int64_t s64div_var	(	int64_t	dividend,
		int64_t	divisor
	)

Force a use of runtime 64-bit signed integer division.

Parameters

dividend	Dividend
divisor	Divisor

Return values

quotient

Quotient

Definition at line 216 of file math_test.c.

                                                                    {

        return check_divmod ( dividend, divisor, / );
}

References check_divmod.

Referenced by s64divmod_okx().

s64mod_var()

int64_t s64mod_var	(	int64_t	dividend,
		int64_t	divisor
	)

Force a use of runtime 64-bit unsigned integer modulus.

Parameters

dividend	Dividend
divisor	Divisor

Return values

remainder

Remainder

Definition at line 229 of file math_test.c.

                                                                    {

        return check_divmod ( dividend, divisor, % );
}

References check_divmod.

Referenced by s64divmod_okx().

ffsl_okx()

static void ffsl_okx ( long  value, int  lsb, const char *  file, unsigned int  line  )

inlinestatic

Report a ffsl() test result.

Parameters

value	Value
lsb	Expected LSB
file	Test code file
line	Test code line

Definition at line 244 of file math_test.c.

                                                                      {

        /* 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 );
}

References ffsl, ffsl_var(), okx, and value.

ffsll_okx()

static void ffsll_okx ( long long  value, int  lsb, const char *  file, unsigned int  line  )

inlinestatic

Report a ffsll() test result.

Parameters

value	Value
lsb	Expected LSB
file	Test code file
line	Test code line

Definition at line 263 of file math_test.c.

                                                                            {

        /* 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 );
}

References ffsll, ffsll_var(), okx, and value.

flsl_okx()

static void flsl_okx ( long  value, int  msb, const char *  file, unsigned int  line  )

inlinestatic

Report a flsl() test result.

Parameters

value	Value
msb	Expected MSB
file	Test code file
line	Test code line

Definition at line 282 of file math_test.c.

                                                                      {

        /* 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 );
}

References flsl, flsl_var(), okx, and value.

flsll_okx()

static void flsll_okx ( long long  value, int  msb, const char *  file, unsigned int  line  )

inlinestatic

Report a flsll() test result.

Parameters

value	Value
msb	Expected MSB
file	Test code file
line	Test code line

Definition at line 301 of file math_test.c.

                                                                            {

        /* 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 );
}

References flsll, flsll_var(), okx, and value.

lsl64_okx()

static void lsl64_okx ( uint64_t  value, unsigned int  shift, uint64_t  expected, const char *  file, unsigned int  line  )

inlinestatic

Report a 64-bit shift left test result.

Parameters

value	Value
shift	Shift amount
expected	Expected value
file	Test code file
line	Test code line

Definition at line 321 of file math_test.c.

                                                  {

        /* 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 );
}

References lsl64_var(), okx, and value.

lsr64_okx()

static void lsr64_okx ( uint64_t  value, unsigned int  shift, uint64_t  expected, const char *  file, unsigned int  line  )

inlinestatic

Report a 64-bit logical shift right test result.

Parameters

value	Value
shift	Shift amount
expected	Expected value
file	Test code file
line	Test code line

Definition at line 343 of file math_test.c.

                                                  {

        /* 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 );
}

References lsr64_var(), okx, and value.

asr64_okx()

static void asr64_okx ( int64_t  value, unsigned int  shift, int64_t  expected, const char *  file, unsigned int  line  )

inlinestatic

Report a 64-bit arithmetic shift right test result.

Parameters

value	Value
shift	Shift amount
expected	Expected value
file	Test code file
line	Test code line

Definition at line 365 of file math_test.c.

                                                  {

        /* 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 );
}

References asr64_var(), okx, and value.

u64divmod_okx()

static void u64divmod_okx ( uint64_t  dividend, uint64_t  divisor, uint64_t  quotient, uint64_t  remainder, const char *  file, unsigned int  line  )

static

Report a 64-bit unsigned integer division test result.

Parameters

dividend	Dividend
divisor	Divisor
quotient	Quotient
remainder	Remainder
file	Test code file
line	Test code line

Definition at line 387 of file math_test.c.

                                                                  {

        /* 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 );
}

References okx, u64div_var(), and u64mod_var().

s64divmod_okx()

static void s64divmod_okx ( int64_t  dividend, int64_t  divisor, int64_t  quotient, int64_t  remainder, const char *  file, unsigned int  line  )

static

Report a 64-bit signed integer division test result.

Parameters

dividend	Dividend
divisor	Divisor
quotient	Quotient
remainder	Remainder
file	Test code file
line	Test code line

Definition at line 414 of file math_test.c.

                                                                  {

        /* 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 );
}

References okx, s64div_var(), and s64mod_var().

math_test_exec()

static void math_test_exec ( void  )

static

Perform mathematical self-tests.

Definition at line 435 of file math_test.c.

                                    {

        /* 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 )));
}

References asr64_ok, ffsl_ok, ffsll_ok, flsl_ok, flsll_ok, isqrt(), lsl64_ok, lsr64_ok, ok, s64divmod_ok, and u64divmod_ok.

Variable Documentation

__self_test

struct self_test math_test __self_test

Initial value:

= {
        .name = "math",
        .exec = math_test_exec,
}

Mathematical self-tests.

Definition at line 518 of file math_test.c.