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	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...
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	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 118 of file math_test.c.

ffsl_ok

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

Definition at line 216 of file math_test.c.

ffsll_ok

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

Definition at line 235 of file math_test.c.

flsl_ok

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

Definition at line 254 of file math_test.c.

flsll_ok

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

Definition at line 273 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 298 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 325 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().

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 88 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__(), and a.

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 154 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 167 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 180 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 193 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 208 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 227 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 246 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 265 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.

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 285 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 312 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 333 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).
         */
        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 ffsl_ok, ffsll_ok, flsl_ok, flsll_ok, isqrt(), 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 401 of file math_test.c.