[tcpip] Allow supported address families to be detected at runtime
[ipxe.git] / src / tests / math_test.c
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 };