iPXE
math_test.c
Go to the documentation of this file.
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  * You can also choose to distribute this program under the terms of
20  * the Unmodified Binary Distribution Licence (as given in the file
21  * COPYING.UBDL), provided that you have satisfied its requirements.
22  */
23 
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
25 
26 /** @file
27  *
28  * Mathematical self-tests
29  *
30  */
31 
32 /* Forcibly enable assertions */
33 #undef NDEBUG
34 
35 #include <string.h>
36 #include <strings.h>
37 #include <assert.h>
38 #include <ipxe/test.h>
39 #include <ipxe/isqrt.h>
40 
41 /**
42  * Force a call to the non-constant implementation of ffsl()
43  *
44  * @v value Value
45  * @ret lsb Least significant bit set in value (LSB=1), or zero
46  */
47 __attribute__ (( noinline )) int ffsl_var ( long value ) {
48  return ffsl ( value );
49 }
50 
51 /**
52  * Force a call to the non-constant implementation of ffsll()
53  *
54  * @v value Value
55  * @ret lsb Least significant bit set in value (LSB=1), or zero
56  */
57 __attribute__ (( noinline )) int ffsll_var ( long long value ) {
58  return ffsll ( value );
59 }
60 
61 /**
62  * Force a call to the non-constant implementation of flsl()
63  *
64  * @v value Value
65  * @ret msb Most significant bit set in value (LSB=1), or zero
66  */
67 __attribute__ (( noinline )) int flsl_var ( long value ) {
68  return flsl ( value );
69 }
70 
71 /**
72  * Force a call to the non-constant implementation of flsll()
73  *
74  * @v value Value
75  * @ret msb Most significant bit set in value (LSB=1), or zero
76  */
77 __attribute__ (( noinline )) int flsll_var ( long long value ) {
78  return flsll ( value );
79 }
80 
81 /**
82  * Check current stack pointer
83  *
84  * @ret stack A value at a fixed offset from the current stack pointer
85  *
86  * Used by check_divmod()
87  */
88 static __attribute__ (( noinline )) void * stack_check ( void ) {
89  int a;
90  void *ret;
91 
92  /* Hide the fact that we are returning the address of a local
93  * variable, to prevent a compiler warning.
94  */
95  __asm__ ( "\n" : "=g" ( ret ) : "0" ( &a ) );
96 
97  return ret;
98 }
99 
100 /**
101  * Check division/modulus operation
102  *
103  * One aspect of the calling convention for the implicit arithmetic
104  * functions (__udivmoddi4() etc) is whether the caller or the callee
105  * is expected to pop any stack-based arguments. This distinction can
106  * be masked if the compiler chooses to uses a frame pointer in the
107  * caller, since the caller will then reload the stack pointer from
108  * the frame pointer and so can mask an error in the value of the
109  * stack pointer.
110  *
111  * We run the division operation in a loop, and check that the stack
112  * pointer does not change value on the second iteration. To prevent
113  * the compiler from performing various optimisations which might
114  * invalidate our intended test (such as unrolling the loop, or moving
115  * the division operation outside the loop), we include some dummy
116  * inline assembly code.
117  */
118 #define check_divmod( dividend, divisor, OP ) ( { \
119  uint64_t result; \
120  int count = 2; \
121  void *check = NULL; \
122  \
123  /* Prevent compiler from unrolling the loop */ \
124  __asm__ ( "\n" : "=g" ( count ) : "0" ( count ) ); \
125  \
126  do { \
127  /* Check that stack pointer does not change between \
128  * loop iterations. \
129  */ \
130  if ( check ) { \
131  assert ( check == stack_check() ); \
132  } else { \
133  check = stack_check(); \
134  } \
135  \
136  /* Perform division, preventing the compiler from \
137  * moving the division out of the loop. \
138  */ \
139  __asm__ ( "\n" : "=g" ( dividend ), "=g" ( divisor ) \
140  : "0" ( dividend ), "1" ( divisor ) ); \
141  result = ( dividend OP divisor ); \
142  __asm__ ( "\n" : "=g" ( result ) : "0" ( result ) ); \
143  \
144  } while ( --count ); \
145  result; } )
146 
147 /**
148  * Force a use of runtime 64-bit unsigned integer division
149  *
150  * @v dividend Dividend
151  * @v divisor Divisor
152  * @ret quotient Quotient
153  */
154 __attribute__ (( noinline )) uint64_t u64div_var ( uint64_t dividend,
155  uint64_t divisor ) {
156 
157  return check_divmod ( dividend, divisor, / );
158 }
159 
160 /**
161  * Force a use of runtime 64-bit unsigned integer modulus
162  *
163  * @v dividend Dividend
164  * @v divisor Divisor
165  * @ret remainder Remainder
166  */
167 __attribute__ (( noinline )) uint64_t u64mod_var ( uint64_t dividend,
168  uint64_t divisor ) {
169 
170  return check_divmod ( dividend, divisor, % );
171 }
172 
173 /**
174  * Force a use of runtime 64-bit signed integer division
175  *
176  * @v dividend Dividend
177  * @v divisor Divisor
178  * @ret quotient Quotient
179  */
180 __attribute__ (( noinline )) int64_t s64div_var ( int64_t dividend,
181  int64_t divisor ) {
182 
183  return check_divmod ( dividend, divisor, / );
184 }
185 
186 /**
187  * Force a use of runtime 64-bit unsigned integer modulus
188  *
189  * @v dividend Dividend
190  * @v divisor Divisor
191  * @ret remainder Remainder
192  */
193 __attribute__ (( noinline )) int64_t s64mod_var ( int64_t dividend,
194  int64_t divisor ) {
195 
196  return check_divmod ( dividend, divisor, % );
197 }
198 
199 /**
200  * Report a ffsl() test result
201  *
202  * @v value Value
203  * @v lsb Expected LSB
204  * @v file Test code file
205  * @v line Test code line
206  */
207 static inline __attribute__ (( always_inline )) void
208 ffsl_okx ( long value, int lsb, const char *file, unsigned int line ) {
209 
210  /* Verify as a constant (requires to be inlined) */
211  okx ( ffsl ( value ) == lsb, file, line );
212 
213  /* Verify as a non-constant */
214  okx ( ffsl_var ( value ) == lsb, file, line );
215 }
216 #define ffsl_ok( value, lsb ) ffsl_okx ( value, lsb, __FILE__, __LINE__ )
217 
218 /**
219  * Report a ffsll() test result
220  *
221  * @v value Value
222  * @v lsb Expected LSB
223  * @v file Test code file
224  * @v line Test code line
225  */
226 static inline __attribute__ (( always_inline )) void
227 ffsll_okx ( long long value, int lsb, const char *file, unsigned int line ) {
228 
229  /* Verify as a constant (requires to be inlined) */
230  okx ( ffsll ( value ) == lsb, file, line );
231 
232  /* Verify as a non-constant */
233  okx ( ffsll_var ( value ) == lsb, file, line );
234 }
235 #define ffsll_ok( value, lsb ) ffsll_okx ( value, lsb, __FILE__, __LINE__ )
236 
237 /**
238  * Report a flsl() test result
239  *
240  * @v value Value
241  * @v msb Expected MSB
242  * @v file Test code file
243  * @v line Test code line
244  */
245 static inline __attribute__ (( always_inline )) void
246 flsl_okx ( long value, int msb, const char *file, unsigned int line ) {
247 
248  /* Verify as a constant (requires to be inlined) */
249  okx ( flsl ( value ) == msb, file, line );
250 
251  /* Verify as a non-constant */
252  okx ( flsl_var ( value ) == msb, file, line );
253 }
254 #define flsl_ok( value, msb ) flsl_okx ( value, msb, __FILE__, __LINE__ )
255 
256 /**
257  * Report a flsll() test result
258  *
259  * @v value Value
260  * @v msb Expected MSB
261  * @v file Test code file
262  * @v line Test code line
263  */
264 static inline __attribute__ (( always_inline )) void
265 flsll_okx ( long long value, int msb, const char *file, unsigned int line ) {
266 
267  /* Verify as a constant (requires to be inlined) */
268  okx ( flsll ( value ) == msb, file, line );
269 
270  /* Verify as a non-constant */
271  okx ( flsll_var ( value ) == msb, file, line );
272 }
273 #define flsll_ok( value, msb ) flsll_okx ( value, msb, __FILE__, __LINE__ )
274 
275 /**
276  * Report a 64-bit unsigned integer division test result
277  *
278  * @v dividend Dividend
279  * @v divisor Divisor
280  * @v quotient Quotient
281  * @v remainder Remainder
282  * @v file Test code file
283  * @v line Test code line
284  */
285 static void u64divmod_okx ( uint64_t dividend, uint64_t divisor,
286  uint64_t quotient, uint64_t remainder,
287  const char *file, unsigned int line ) {
288 
289  /* Sanity check */
290  okx ( ( ( divisor * quotient ) + remainder ) == dividend, file, line );
291 
292  /* Check division */
293  okx ( u64div_var ( dividend, divisor ) == quotient, file, line );
294 
295  /* Check modulus */
296  okx ( u64mod_var ( dividend, divisor ) == remainder, file, line );
297 }
298 #define u64divmod_ok( dividend, divisor, quotient, remainder ) \
299  u64divmod_okx ( dividend, divisor, quotient, remainder, \
300  __FILE__, __LINE__ )
301 
302 /**
303  * Report a 64-bit signed integer division test result
304  *
305  * @v dividend Dividend
306  * @v divisor Divisor
307  * @v quotient Quotient
308  * @v remainder Remainder
309  * @v file Test code file
310  * @v line Test code line
311  */
312 static void s64divmod_okx ( int64_t dividend, int64_t divisor,
313  int64_t quotient, int64_t remainder,
314  const char *file, unsigned int line ) {
315 
316  /* Sanity check */
317  okx ( ( ( divisor * quotient ) + remainder ) == dividend, file, line );
318 
319  /* Check division */
320  okx ( s64div_var ( dividend, divisor ) == quotient, file, line );
321 
322  /* Check modulus */
323  okx ( s64mod_var ( dividend, divisor ) == remainder, file, line );
324 }
325 #define s64divmod_ok( dividend, divisor, quotient, remainder ) \
326  s64divmod_okx ( dividend, divisor, quotient, remainder, \
327  __FILE__, __LINE__ )
328 
329 /**
330  * Perform mathematical self-tests
331  *
332  */
333 static void math_test_exec ( void ) {
334 
335  /* Test ffsl() */
336  ffsl_ok ( 0, 0 );
337  ffsl_ok ( 1, 1 );
338  ffsl_ok ( 255, 1 );
339  ffsl_ok ( 256, 9 );
340  ffsl_ok ( 257, 1 );
341  ffsl_ok ( 0x54850596, 2 );
342  ffsl_ok ( 0x80000000, 32 );
343 
344  /* Test ffsll() */
345  ffsll_ok ( 0, 0 );
346  ffsll_ok ( 1, 1 );
347  ffsll_ok ( 0x6d63623330ULL, 5 );
348  ffsll_ok ( 0x80000000UL, 32 );
349  ffsll_ok ( 0x8000000000000000ULL, 64 );
350 
351  /* Test flsl() */
352  flsl_ok ( 0, 0 );
353  flsl_ok ( 1, 1 );
354  flsl_ok ( 255, 8 );
355  flsl_ok ( 256, 9 );
356  flsl_ok ( 257, 9 );
357  flsl_ok ( 0x69505845, 31 );
358  flsl_ok ( -1U, ( 8 * sizeof ( int ) ) );
359  flsl_ok ( -1UL, ( 8 * sizeof ( long ) ) );
360 
361  /* Test flsll() */
362  flsll_ok ( 0, 0 );
363  flsll_ok ( 1, 1 );
364  flsll_ok ( 0x6d63623330ULL, 39 );
365  flsll_ok ( -1U, ( 8 * sizeof ( int ) ) );
366  flsll_ok ( -1UL, ( 8 * sizeof ( long ) ) );
367  flsll_ok ( -1ULL, ( 8 * sizeof ( long long ) ) );
368 
369  /* Test 64-bit arithmetic
370  *
371  * On a 64-bit machine, these tests are fairly meaningless.
372  *
373  * On a 32-bit machine, these tests verify the correct
374  * operation of our libgcc functions __udivmoddi4()
375  * etc. (including checking that the implicit calling
376  * convention assumed by gcc matches our expectations).
377  */
378  u64divmod_ok ( 0x2b90ddccf699f765ULL, 0xed9f5e73ULL,
379  0x2eef6ab4ULL, 0x0e12f089ULL );
380  s64divmod_ok ( 0x2b90ddccf699f765ULL, 0xed9f5e73ULL,
381  0x2eef6ab4ULL, 0x0e12f089ULL );
382  u64divmod_ok ( 0xc09e00dcb9e34b54ULL, 0x35968185cdc744f3ULL,
383  3, 0x1fda7c4b508d7c7bULL );
384  s64divmod_ok ( -0x3f61ff23461cb4acLL, 0x35968185cdc744f3ULL,
385  -1LL, -0x9cb7d9d78556fb9LL );
386  u64divmod_ok ( 0, 0x5b2f2737f4ffULL, 0, 0 );
387  s64divmod_ok ( 0, 0xbb00ded72766207fULL, 0, 0 );
388 
389  /* Test integer square root */
390  ok ( isqrt ( 0 ) == 0 );
391  ok ( isqrt ( 1 ) == 1 );
392  ok ( isqrt ( 255 ) == 15 );
393  ok ( isqrt ( 256 ) == 16 );
394  ok ( isqrt ( 257 ) == 16 );
395  ok ( isqrt ( 0xa53df2adUL ) == 52652 );
396  ok ( isqrt ( 0x123793c6UL ) == 17482 );
397  ok ( isqrt ( -1UL ) == ( -1UL >> ( 8 * sizeof ( unsigned long ) / 2 )));
398 }
399 
400 /** Mathematical self-tests */
401 struct self_test math_test __self_test = {
402  .name = "math",
403  .exec = math_test_exec,
404 };
#define __attribute__(x)
Definition: compiler.h:10
#define s64divmod_ok(dividend, divisor, quotient, remainder)
Definition: math_test.c:325
#define ffsl(x)
Find first (i.e.
Definition: strings.h:131
#define ffsl_ok(value, lsb)
Definition: math_test.c:216
unsigned long isqrt(unsigned long value)
Find integer square root.
Definition: isqrt.c:40
unsigned long long uint64_t
Definition: stdint.h:13
Self-test infrastructure.
const char * name
Test set name.
Definition: test.h:17
static void ffsl_okx(long value, int lsb, const char *file, unsigned int line)
Report a ffsl() test result.
Definition: math_test.c:208
#define flsll(x)
Find last (i.e.
Definition: strings.h:148
A self-test set.
Definition: test.h:15
int ffsll_var(long long value)
Force a call to the non-constant implementation of ffsll()
Definition: math_test.c:57
int64_t s64div_var(int64_t dividend, int64_t divisor)
Force a use of runtime 64-bit signed integer division.
Definition: math_test.c:180
#define u64divmod_ok(dividend, divisor, quotient, remainder)
Definition: math_test.c:298
uint64_t u64div_var(uint64_t dividend, uint64_t divisor)
Force a use of runtime 64-bit unsigned integer division.
Definition: math_test.c:154
struct self_test math_test __self_test
Mathematical self-tests.
Definition: math_test.c:401
#define okx(success, file, line)
Report test result.
Definition: test.h:44
Assertions.
#define ffsll(x)
Find first (i.e.
Definition: strings.h:122
signed long long int64_t
Definition: stdint.h:18
#define ffsll_ok(value, lsb)
Definition: math_test.c:235
static void math_test_exec(void)
Perform mathematical self-tests.
Definition: math_test.c:333
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
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.
Definition: math_test.c:285
static void ffsll_okx(long long value, int lsb, const char *file, unsigned int line)
Report a ffsll() test result.
Definition: math_test.c:227
Integer square root.
static void * stack_check(void)
Check current stack pointer.
Definition: math_test.c:88
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.
Definition: math_test.c:312
int64_t s64mod_var(int64_t dividend, int64_t divisor)
Force a use of runtime 64-bit unsigned integer modulus.
Definition: math_test.c:193
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
__asm__(".section \".rodata\", \"a\", " PROGBITS "\n\t" "\nprivate_key_data:\n\t" ".size private_key_data, ( . - private_key_data )\n\t" ".equ private_key_len, ( . - private_key_data )\n\t" ".previous\n\t")
uint64_t u64mod_var(uint64_t dividend, uint64_t divisor)
Force a use of runtime 64-bit unsigned integer modulus.
Definition: math_test.c:167
#define flsll_ok(value, msb)
Definition: math_test.c:273
static void flsl_okx(long value, int msb, const char *file, unsigned int line)
Report a flsl() test result.
Definition: math_test.c:246
int flsll_var(long long value)
Force a call to the non-constant implementation of flsll()
Definition: math_test.c:77
static void flsll_okx(long long value, int msb, const char *file, unsigned int line)
Report a flsll() test result.
Definition: math_test.c:265
#define check_divmod(dividend, divisor, OP)
Check division/modulus operation.
Definition: math_test.c:118
int ffsl_var(long value)
Force a call to the non-constant implementation of ffsl()
Definition: math_test.c:47
#define flsl(x)
Find last (i.e.
Definition: strings.h:157
int flsl_var(long value)
Force a call to the non-constant implementation of flsl()
Definition: math_test.c:67
#define ok(success)
Definition: test.h:46
String functions.
String functions.
#define flsl_ok(value, msb)
Definition: math_test.c:254