1 /*
2 Copyright (C) 2010, 2013 William Hart
3
4 All rights reserved.
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions are met:
8
9 1. Redistributions of source code must retain the above copyright notice,
10 this list of conditions and the following disclaimer.
11
12 2. Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in the
14 documentation and/or other materials provided with the distribution.
15
16 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
17 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE
20 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
22 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
23 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include "nn.h"
31 #include "test.h"
32
33 rand_t state;
34
35 #undef ITER
36 #define ITER 50000
37
test_gc(void)38 int test_gc(void)
39 {
40 int result = 1;
41 len_t m;
42 word_t w1, w2, w3, w4;
43 nn_t a, b, c;
44
45 printf("gc...");
46
47 TEST_START(1, ITER)
48 {
49 randoms_upto(100, NONZERO, state, &m, NULL);
50 randoms_upto(m, ANY, state, &w1, &w2, &w3, &w4, NULL);
51
52 randoms_of_len(w1, ANY, state, &a, &b, &c, NULL);
53 } TEST_END;
54
55 return result;
56 }
57
test_tmp(void)58 int test_tmp(void)
59 {
60 int result = 1;
61 len_t m1, m2, m3;
62 nn_t a, b, c;
63 TMP_INIT;
64
65 printf("tmp...");
66
67 TEST_START(1, 64)
68 {
69 TMP_START;
70
71 randoms_upto(2048, NONZERO, state, &m1, &m2, &m3, NULL);
72
73 a = (nn_t) TMP_ALLOC(m1);
74 b = (nn_t) TMP_ALLOC(m2);
75 c = (nn_t) TMP_ALLOC(m3);
76
77 randoms_of_len(m1, ANY, state, &a, NULL);
78 randoms_of_len(m2, ANY, state, &b, NULL);
79 randoms_of_len(m3, ANY, state, &c, NULL);
80
81 TMP_END;
82 } TEST_END;
83
84 return result;
85 }
86
test_bit_set(void)87 int test_bit_set(void)
88 {
89 int result = 1;
90 nn_t a;
91 len_t m;
92 bits_t bit, sh1;
93
94 printf("nn_bit_set...");
95
96 /* test that setting a bit works */
97 TEST_START(1, ITER)
98 {
99 randoms_upto(100, NONZERO, state, &m, NULL);
100 randoms_upto(m*WORD_BITS, ANY, state, &bit, NULL);
101
102 randoms_of_len(m, ANY, state, &a, NULL);
103
104 nn_bit_set(a, bit);
105
106 result = nn_bit_test(a, bit);
107
108 if (!result)
109 {
110 bsdnt_printf("bit = %b\n", bit);
111 print_debug(a, m);
112 }
113 } TEST_END;
114
115 /* test that setting a bit then shifting works */
116 TEST_START(2, ITER)
117 {
118 randoms_upto(100, NONZERO, state, &m, NULL);
119 randoms_upto(m*WORD_BITS - WORD_BITS/2, ANY, state, &bit, NULL);
120 randoms_upto(WORD_BITS/2, ANY, state, &sh1, NULL);
121
122 randoms_of_len(m, ANY, state, &a, NULL);
123
124 nn_bit_set(a, bit);
125 nn_shl(a, a, m, sh1);
126
127 result = nn_bit_test(a, bit + sh1);
128
129 if (!result)
130 {
131 bsdnt_printf("bit = %b, sh1 = %b\n", bit, sh1);
132 print_debug(a, m);
133 }
134 } TEST_END;
135
136 return result;
137 }
138
test_bit_clear(void)139 int test_bit_clear(void)
140 {
141 int result = 1;
142 nn_t a;
143 len_t m;
144 bits_t bit, sh1;
145
146 printf("nn_bit_clear...");
147
148 /* test that setting a bit works */
149 TEST_START(1, ITER)
150 {
151 randoms_upto(100, NONZERO, state, &m, NULL);
152 randoms_upto(m*WORD_BITS, ANY, state, &bit, NULL);
153
154 randoms_of_len(m, ANY, state, &a, NULL);
155
156 nn_bit_clear(a, bit);
157
158 result = !nn_bit_test(a, bit);
159
160 if (!result)
161 {
162 bsdnt_printf("bit = %b\n", bit);
163 print_debug(a, m);
164 }
165 } TEST_END;
166
167 /* test that setting a bit then shifting works */
168 TEST_START(2, ITER)
169 {
170 randoms_upto(100, NONZERO, state, &m, NULL);
171 randoms_upto(m*WORD_BITS - WORD_BITS/2, ANY, state, &bit, NULL);
172 randoms_upto(WORD_BITS/2, ANY, state, &sh1, NULL);
173
174 randoms_of_len(m, ANY, state, &a, NULL);
175
176 nn_bit_clear(a, bit);
177 nn_shl(a, a, m, sh1);
178
179 result = !nn_bit_test(a, bit + sh1);
180
181 if (!result)
182 {
183 bsdnt_printf("bit = %b, sh1 = %b\n", bit, sh1);
184 print_debug(a, m);
185 }
186 } TEST_END;
187
188 return result;
189 }
190
test_add_m(void)191 int test_add_m(void)
192 {
193 int result = 1;
194 nn_t a, b, c, r1, r2;
195 len_t m, n;
196 word_t ci;
197
198 printf("nn_add_m...");
199
200 /* test (a + b) + c = a + (b + c) */
201 TEST_START(1, ITER)
202 {
203 randoms_upto(100, ANY, state, &m, NULL);
204
205 randoms_of_len(m, ANY, state, &a, &b, &c, NULL);
206 randoms_of_len(m + 1, ANY, state, &r1, &r2, NULL);
207
208 r1[m] = nn_add_m(r1, a, b, m);
209 r1[m] += nn_add_m(r1, r1, c, m);
210
211 r2[m] = nn_add_m(r2, b, c, m);
212 r2[m] += nn_add_m(r2, r2, a, m);
213
214 result = nn_equal_m(r1, r2, m + 1);
215
216 if (!result)
217 {
218 print_debug(a, m); print_debug(b, m); print_debug(c, m);
219 print_debug_diff(r1, r2, m + 1);
220 }
221 } TEST_END;
222
223 /* test chaining of addition */
224 TEST_START(chaining, ITER)
225 {
226 randoms_upto(100, ANY, state, &m, &n, NULL);
227
228 randoms_of_len(m + n, ANY, state, &a, &b, NULL);
229 randoms_of_len(m + n + 1, ANY, state, &r1, &r2, NULL);
230
231 ci = nn_add_m(r1, a, b, m);
232 r1[m + n] = nn_add_mc(r1 + m, a + m, b + m, n, ci);
233
234 r2[m + n] = nn_add_m(r2, a, b, m + n);
235
236 result = nn_equal_m(r1, r2, m + n + 1);
237
238 if (!result)
239 {
240 bsdnt_printf("m = %m n = %m\n", m, n);
241 print_debug(a, m + n); print_debug(b, m + n);
242 print_debug_diff(r1, r2, m + n + 1);
243 }
244 } TEST_END;
245
246 return result;
247 }
248
test_add(void)249 int test_add(void)
250 {
251 int result = 1;
252 nn_t a, b, c, r1, r2;
253 len_t m1, m2, m3;
254 word_t ci;
255
256 printf("nn_add...");
257
258 /* test (a + b) + c = (a + c) + b */
259 TEST_START(1, ITER)
260 {
261 randoms_upto(100, NONZERO, state, &m1, NULL);
262 randoms_upto(m1, ANY, state, &m2, &m3, NULL);
263
264 randoms_of_len(m1, ANY, state, &a, NULL);
265 randoms_of_len(m2, ANY, state, &b, NULL);
266 randoms_of_len(m3, ANY, state, &c, NULL);
267 randoms_of_len(m1 + 1, ANY, state, &r1, &r2, NULL);
268
269 r1[m1] = nn_add(r1, a, m1, b, m2);
270 r1[m1] += nn_add(r1, r1, m1, c, m3);
271
272 r2[m1] = nn_add(r2, a, m1, c, m3);
273 r2[m1] += nn_add(r2, r2, m1, b, m2);
274
275 result = nn_equal_m(r1, r2, m1 + 1);
276
277 if (!result)
278 {
279 print_debug(a, m1); print_debug(b, m2); print_debug(c, m3);
280 print_debug_diff(r1, r2, m1 + 1);
281 }
282 } TEST_END;
283
284 /* test chaining of addition */
285 TEST_START(chaining, ITER)
286 {
287 randoms_upto(100, ANY, state, &m1, &m2, &m3, NULL);
288
289 randoms_of_len(m1 + m2 + m3, ANY, state, &a, NULL);
290 randoms_of_len(m2 + m3, ANY, state, &b, NULL);
291 randoms_of_len(m1 + m2 + m3 + 1, ANY, state, &r1, &r2, NULL);
292
293 ci = nn_add(r1, a, m3, b, m3);
294 r1[m1 + m2 + m3] = nn_add_c(r1 + m3, a + m3, m1 + m2, b + m3, m2, ci);
295
296 r2[m1 + m2 + m3] = nn_add(r2, a, m1 + m2 + m3, b, m2 + m3);
297
298 result = nn_equal_m(r1, r2, m1 + m2 + m3 + 1);
299
300 if (!result)
301 {
302 bsdnt_printf("m1 = %m, m2 = %m, m3 = %m\n", m1, m2, m3);
303 print_debug(a, m1 + m2 + m3); print_debug(b, m2 + m3);
304 print_debug_diff(r1, r2, m1 + m2 + m3 + 1);
305 }
306 } TEST_END;
307
308 return result;
309 }
310
test_sub_m(void)311 int test_sub_m(void)
312 {
313 int result = 1;
314 nn_t a, b, c, r1, r2;
315 len_t m, n;
316 word_t ci;
317
318 printf("nn_sub_m...");
319
320 /* test (a - b) - c = (a - c) - b */
321 TEST_START(1, ITER)
322 {
323 randoms_upto(100, ANY, state, &m, NULL);
324
325 randoms_of_len(m, ANY, state, &a, &b, &c, NULL);
326 randoms_of_len(m + 1, ANY, state, &r1, &r2, NULL);
327
328 r1[m] = -nn_sub_m(r1, a, b, m);
329 r1[m] -= nn_sub_m(r1, r1, c, m);
330
331 r2[m] = -nn_sub_m(r2, a, c, m);
332 r2[m] -= nn_sub_m(r2, r2, b, m);
333
334 result = nn_equal_m(r1, r2, m + 1);
335
336 if (!result)
337 {
338 print_debug(a, m); print_debug(b, m); print_debug(c, m);
339 print_debug_diff(r1, r2, m + 1);
340 }
341 } TEST_END;
342
343 /* test chaining of subtraction */
344 TEST_START(chaining, ITER)
345 {
346 randoms_upto(100, ANY, state, &m, &n, NULL);
347
348 randoms_of_len(m + n, ANY, state, &a, &b, NULL);
349 randoms_of_len(m + n + 1, ANY, state, &r1, &r2, NULL);
350
351 ci = nn_sub_m(r1, a, b, m);
352 r1[m + n] = -nn_sub_mc(r1 + m, a + m, b + m, n, ci);
353
354 r2[m + n] = -nn_sub_m(r2, a, b, m + n);
355
356 result = nn_equal_m(r1, r2, m + n + 1);
357
358 if (!result)
359 {
360 bsdnt_printf("m = %m, n = %m\n", m, n);
361 print_debug(a, m + n); print_debug(b, m + n);
362 print_debug_diff(r1, r2, m + n + 1);
363 }
364 } TEST_END;
365
366 /* test (a + b) - b = a */
367 TEST_START(2, ITER)
368 {
369 randoms_upto(100, ANY, state, &m, NULL);
370
371 randoms_of_len(m, ANY, state, &a, &b, NULL);
372 randoms_of_len(m + 1, ANY, state, &r1, NULL);
373
374 r1[m] = nn_add_m(r1, a, b, m);
375 r1[m] -= nn_sub_m(r1, r1, b, m);
376
377 result = (nn_equal_m(r1, a, m) && (r1[m] == 0));
378
379 if (!result)
380 {
381 print_debug(a, m); print_debug(b, m);
382 print_debug_diff(r1, a, m);
383 bsdnt_printf("r1[%m] = %wx\n", m, r1[m]);
384 }
385 } TEST_END;
386
387 /* test a - b = a + (-b) */
388 TEST_START(3, ITER)
389 {
390 randoms_upto(100, ANY, state, &m, NULL);
391
392 randoms_of_len(m, ANY, state, &a, &b, NULL);
393 randoms_of_len(m + 1, ANY, state, &r1, &r2, NULL);
394
395 r1[m] = -nn_neg(r1, b, m);
396 r1[m] += nn_add_m(r1, r1, a, m);
397
398 r2[m] = -nn_sub_m(r2, a, b, m);
399
400 result = nn_equal_m(r1, r2, m + 1);
401
402 if (!result)
403 {
404 print_debug(a, m); print_debug(b, m);
405 print_debug_diff(r1, r2, m + 1);
406 }
407 } TEST_END;
408
409 return result;
410 }
411
test_sub(void)412 int test_sub(void)
413 {
414 int result = 1;
415 nn_t a, b, c, r1, r2;
416 len_t m1, m2, m3;
417 word_t ci;
418
419 printf("nn_sub...");
420
421 /* test (a - b) - c = (a - c) - b */
422 TEST_START(1, ITER)
423 {
424 randoms_upto(100, NONZERO, state, &m1, NULL);
425 randoms_upto(m1, ANY, state, &m2, &m3, NULL);
426
427 randoms_of_len(m1, ANY, state, &a, NULL);
428 randoms_of_len(m2, ANY, state, &b, NULL);
429 randoms_of_len(m3, ANY, state, &c, NULL);
430 randoms_of_len(m1 + 1, ANY, state, &r1, &r2, NULL);
431
432 r1[m1] = -nn_sub(r1, a, m1, b, m2);
433 r1[m1] -= nn_sub(r1, r1, m1, c, m3);
434
435 r2[m1] = -nn_sub(r2, a, m1, c, m3);
436 r2[m1] -= nn_sub(r2, r2, m1, b, m2);
437
438 result = nn_equal_m(r1, r2, m1 + 1);
439
440 if (!result)
441 {
442 print_debug(a, m1); print_debug(b, m2); print_debug(c, m3);
443 print_debug_diff(r1, r2, m1 + 1);
444 }
445 } TEST_END;
446
447 /* test chaining of subtraction */
448 TEST_START(chaining, ITER)
449 {
450 randoms_upto(100, ANY, state, &m1, &m2, &m3, NULL);
451
452 randoms_of_len(m1 + m2 + m3, ANY, state, &a, NULL);
453 randoms_of_len(m2 + m3, ANY, state, &b, NULL);
454 randoms_of_len(m1 + m2 + m3 + 1, ANY, state, &r1, &r2, NULL);
455
456 ci = nn_sub(r1, a, m3, b, m3);
457 r1[m1 + m2 + m3] = -nn_sub_c(r1 + m3, a + m3, m1 + m2, b + m3, m2, ci);
458
459 r2[m1 + m2 + m3] = -nn_sub(r2, a, m1 + m2 + m3, b, m2 + m3);
460
461 result = nn_equal_m(r1, r2, m1 + m2 + m3 + 1);
462
463 if (!result)
464 {
465 bsdnt_printf("m1 = %m, m2 = %m, m3 = %m\n", m1, m2, m3);
466 print_debug(a, m1 + m2 + m3); print_debug(b, m2 + m3);
467 print_debug_diff(r1, r2, m1 + m2 + m3 + 1);
468 }
469 } TEST_END;
470
471 return result;
472 }
473
test_shl(void)474 int test_shl(void)
475 {
476 int result = 1;
477 nn_t a, r1, r2;
478 bits_t sh1, sh2;
479 len_t m, n;
480 word_t ci;
481
482 printf("nn_shl...");
483
484 /* test (a << sh1) << sh2 = (a << sh2) << sh1 */
485 TEST_START(1, ITER)
486 {
487 randoms_upto(100, ANY, state, &m, NULL);
488 randoms_upto(WORD_BITS, ANY, state, &sh1, NULL);
489 randoms_upto(WORD_BITS - sh1, ANY, state, &sh2, NULL);
490
491 randoms_of_len(m, ANY, state, &a, NULL);
492 randoms_of_len(m + 1, ANY, state, &r1, &r2, NULL);
493
494 r1[m] = nn_shl(r1, a, m, sh1);
495 nn_shl(r1, r1, m + 1, sh2);
496
497 r2[m] = nn_shl(r2, a, m, sh2);
498 nn_shl(r2, r2, m + 1, sh1);
499
500 result = nn_equal_m(r1, r2, m + 1);
501
502 if (!result)
503 {
504 bsdnt_printf("m = %m, sh1 = %b, sh2 = %b\n", m, sh1, sh2);
505 print_debug(a, m);
506 print_debug_diff(r1, r2, m + 1);
507 }
508 } TEST_END;
509
510 /* test chaining of shl */
511 TEST_START(chaining, ITER)
512 {
513 randoms_upto(100, ANY, state, &m, &n, NULL);
514 randoms_upto(WORD_BITS, ANY, state, &sh1, NULL);
515
516 randoms_of_len(m + n, ANY, state, &a, NULL);
517 randoms_of_len(m + n + 1, ANY, state, &r1, &r2, NULL);
518
519 ci = nn_shl(r1, a, m, sh1);
520 r1[m + n] = nn_shl_c(r1 + m, a + m, n, sh1, ci);
521
522 r2[m + n] = nn_shl(r2, a, m + n, sh1);
523
524 result = nn_equal_m(r1, r2, m + n + 1);
525
526 if (!result)
527 {
528 bsdnt_printf("m = %m, n = %m, sh1 = %b\n", m, n, sh1);
529 print_debug(a, m + n);
530 print_debug_diff(r1, r2, m + n + 1);
531 }
532 } TEST_END;
533
534 /* test a << 1 = a + a */
535 TEST_START(2, ITER)
536 {
537 randoms_upto(100, ANY, state, &m, NULL);
538
539 randoms_of_len(m, ANY, state, &a, NULL);
540 randoms_of_len(m + 1, ANY, state, &r1, &r2, NULL);
541
542 r1[m] = nn_shl(r1, a, m, 1);
543
544 r2[m] = nn_add_m(r2, a, a, m);
545
546 result = nn_equal_m(r1, r2, m + 1);
547
548 if (!result)
549 {
550 print_debug(a, m);
551 print_debug_diff(r1, r2, m + 1);
552 }
553 } TEST_END;
554
555 return result;
556 }
557
test_shr(void)558 int test_shr(void)
559 {
560 int result = 1;
561 nn_t a, r1, r2;
562 bits_t sh1, sh2;
563 len_t m, n;
564 word_t ci;
565
566 printf("nn_shr...");
567
568 /* test (a >> sh1) >> sh2 = (a >> sh2) >> sh1 */
569 TEST_START(1, ITER)
570 {
571 randoms_upto(100, ANY, state, &m, NULL);
572 randoms_upto(WORD_BITS, ANY, state, &sh1, NULL);
573 randoms_upto(WORD_BITS - sh1, ANY, state, &sh2, NULL);
574
575 randoms_of_len(m, ANY, state, &a, &r1, &r2, NULL);
576
577 nn_shr(r1, a, m, sh1);
578 nn_shr(r1, r1, m, sh2);
579
580 nn_shr(r2, a, m, sh2);
581 nn_shr(r2, r2, m, sh1);
582
583 result = nn_equal_m(r1, r2, m);
584
585 if (!result)
586 {
587 print_debug(a, m);
588 print_debug_diff(r1, r2, m);
589 }
590 } TEST_END;
591
592 /* test chaining of shr */
593 TEST_START(chaining, ITER)
594 {
595 randoms_upto(100, ANY, state, &m, &n, NULL);
596 randoms_upto(WORD_BITS, ANY, state, &sh1, NULL);
597
598 randoms_of_len(m + n, ANY, state, &a, &r1, &r2, NULL);
599
600 ci = nn_shr(r1 + n, a + n, m, sh1);
601 nn_shr_c(r1, a, n, sh1, ci);
602
603 nn_shr(r2, a, m + n, sh1);
604
605 result = nn_equal_m(r1, r2, m + n);
606
607 if (!result)
608 {
609 bsdnt_printf("m = %m, n = %m, sh1 = %b\n", m, n, sh1);
610 print_debug(a, m + n);
611 print_debug_diff(r1, r2, m + n + 1);
612 }
613 } TEST_END;
614
615 /* test (a << sh1) >> sh1 = a */
616 TEST_START(2, ITER)
617 {
618 randoms_upto(100, ANY, state, &m, NULL);
619 randoms_upto(WORD_BITS, ANY, state, &sh1, NULL);
620
621 randoms_of_len(m, ANY, state, &a, &r2, NULL);
622 randoms_of_len(m + 1, ANY, state, &r1, NULL);
623
624 r1[m] = nn_shl(r1, a, m, sh1);
625
626 nn_shr_c(r2, r1, m, sh1, sh1 == 0 ? 0 : r1[m] << (WORD_BITS - sh1));
627
628 result = nn_equal_m(a, r2, m);
629
630 if (!result)
631 {
632 bsdnt_printf("m = %m, sh1 = %b\n", m, sh1);
633 print_debug(a, m); print_debug(r1, m + 1);
634 print_debug_diff(a, r2, m);
635 }
636 } TEST_END;
637
638 return result;
639 }
640
test_copy(void)641 int test_copy(void)
642 {
643 int result = 1;
644 nn_t a, r1;
645 len_t m;
646
647 printf("nn_copy...");
648
649 TEST_START(1, ITER)
650 {
651 randoms_upto(100, ANY, state, &m, NULL);
652
653 randoms_of_len(m, ANY, state, &a, &r1, NULL);
654
655 nn_copy(r1, a, m);
656
657 result = nn_equal_m(r1, a, m);
658
659 if (!result)
660 {
661 print_debug(a, m);
662 print_debug_diff(a, r1, m);
663 }
664 } TEST_END;
665
666 return result;
667 }
668
test_equal_m(void)669 int test_equal_m(void)
670 {
671 int result = 1;
672 nn_t a, r1;
673 len_t m, s;
674
675 printf("nn_equal_m...");
676
677 /* test copying and then modifiying yields non-equal integer */
678 TEST_START(1, ITER)
679 {
680 randoms_upto(100, NONZERO, state, &m, NULL);
681 randoms_upto(m, ANY, state, &s, NULL);
682
683 randoms_of_len(m, ANY, state, &a, &r1, NULL);
684
685 nn_copy(r1, a, m);
686 a[s] += 1;
687
688 result = !nn_equal_m(r1, a, m);
689
690 if (!result)
691 {
692 print_debug(a, m);
693 print_debug_diff(a, r1, m);
694 }
695 } TEST_END;
696
697 return result;
698 }
699
test_equal(void)700 int test_equal(void)
701 {
702 int result = 1;
703 nn_t a, b, r1, r2;
704 len_t m1, m2;
705
706 printf("nn_equal...");
707
708 /* test that equal things compare equal */
709 TEST_START(1, ITER)
710 {
711 randoms_upto(100, ANY, state, &m1, NULL);
712
713 randoms_of_len(m1, ANY, state, &r1, &r2, NULL);
714
715 nn_copy(r2, r1, m1);
716
717 result = nn_equal(r1, m1, r2, m1);
718
719 if (!result)
720 {
721 print_debug(r1, m1); print_debug(r2, m1);
722 print_debug_diff(r1, r2, m1);
723 }
724 } TEST_END;
725
726 /* test that not equal lengths compare not equal */
727 TEST_START(2, ITER)
728 {
729 randoms_upto(100, NONZERO, state, &m1, NULL);
730 randoms_upto(m1, ANY, state, &m2, NULL);
731
732 randoms_of_len(m1, FULL, state, &r1, NULL);
733 randoms_of_len(m2, FULL, state, &r2, NULL);
734
735 result = !nn_equal(r1, m1, r2, m2);
736
737 if (!result)
738 {
739 print_debug(r1, m1); print_debug(r2, m2);
740 }
741 } TEST_END;
742
743 /* test that not equal values compare not equal */
744 TEST_START(3, ITER)
745 {
746 randoms_upto(100, NONZERO, state, &m1, NULL);
747
748 randoms_of_len(m1 + 1, ANY, state, &r1, NULL);
749
750 do {
751 randoms_of_len(m1, FULL, state, &a, &b, NULL);
752 r1[m1] = nn_add_m(r1, a, b, m1);
753 } while (r1[m1]);
754
755 result = !nn_equal(r1, m1, a, m1);
756
757 if (!result)
758 {
759 print_debug(r1, m1); print_debug(a, m1); print_debug(b, m1);
760 print_debug_diff(r1, a, m1);
761 }
762 } TEST_END;
763
764 return result;
765 }
766
test_zero(void)767 int test_zero(void)
768 {
769 int result = 1;
770 nn_t a;
771 len_t m;
772
773 printf("nn_zero...");
774
775 /* test zeroing */
776 TEST_START(1, ITER)
777 {
778 randoms_upto(100, ANY, state, &m, NULL);
779
780 randoms_of_len(m, ANY, state, &a, NULL);
781
782 nn_zero(a, m);
783
784 result = (nn_normalise(a, m) == 0);
785
786 if (!result)
787 {
788 print_debug(a, m);
789 }
790 } TEST_END;
791
792 return result;
793 }
794
test_normalise(void)795 int test_normalise(void)
796 {
797 int result = 1;
798 nn_t a, r1;
799 len_t m, s1, s2;
800
801 printf("nn_normalise...");
802
803 /* test normalising then copying normalised part yields same integer */
804 TEST_START(1, ITER)
805 {
806 randoms_upto(100, NONZERO, state, &m, NULL);
807 randoms_upto(m, ANY, state, &s1, NULL);
808
809 randoms_of_len(m, ANY, state, &a, &r1, NULL);
810
811 nn_zero(a + s1, m - s1);
812 s2 = nn_normalise(a, m);
813
814 nn_zero(r1, m);
815 nn_copy(r1, a, s2);
816
817 result = ((s1 >= s2) && ((s2 == 0) || (a[s2 - 1] != 0))
818 && nn_equal_m(a, r1, m));
819
820 if (!result)
821 {
822 bsdnt_printf("m = %m, s1 = %m, s2 = %m\n", m, s1, s2);
823 print_debug(r1, m); print_debug(a, m);
824 print_debug_diff(r1, a, m);
825 }
826 } TEST_END;
827
828 return result;
829 }
830
test_mul1(void)831 int test_mul1(void)
832 {
833 int result = 1;
834 nn_t a, r1, r2, t1;
835 word_t c1, c2, ci;
836 len_t m, n;
837
838 printf("nn_mul1...");
839
840 /* test a * (c1 + c2) = a * c1 + a * c2 */
841 TEST_START(1, ITER)
842 {
843 randoms_upto(100, ANY, state, &m, NULL);
844
845 randoms_of_len(m, ANY, state, &a, NULL);
846 randoms_of_len(m + 1, ANY, state, &t1, &r1, &r2, NULL);
847
848 do randoms(ANY, state, &c1, &c2, NULL);
849 while (c1 + c2 < c1);
850
851 t1[m] = nn_mul1(t1, a, m, c1);
852 r1[m] = nn_mul1(r1, a, m, c2);
853 nn_add_m(r1, r1, t1, m + 1);
854
855 r2[m] = nn_mul1(r2, a, m, c1 + c2);
856
857 result = nn_equal_m(r1, r2, m + 1);
858
859 if (!result)
860 {
861 bsdnt_printf("m = %m, c1 = %wx, c2 = %wx\n", m, c1, c2);
862 print_debug(a, m); print_debug(t1, m + 1);
863 print_debug_diff(r1, r2, m + 1);
864 }
865 } TEST_END;
866
867 /* test chaining of mul1 */
868 TEST_START(chaining, ITER)
869 {
870 randoms_upto(100, ANY, state, &m, &n, NULL);
871
872 randoms_of_len(m + n, ANY, state, &a, NULL);
873 randoms_of_len(m + n + 1, ANY, state, &r1, &r2, NULL);
874
875 randoms(ANY, state, &c1, NULL);
876
877 ci = nn_mul1(r1, a, m, c1);
878 r1[m + n] = nn_mul1_c(r1 + m, a + m, n, c1, ci);
879
880 r2[m + n] = nn_mul1(r2, a, m + n, c1);
881
882 result = nn_equal_m(r1, r2, m + n + 1);
883
884 if (!result)
885 {
886 bsdnt_printf("m = %m, n = %m, c1 = %wx\n", m, n, c1);
887 print_debug(a, m + n);
888 print_debug_diff(r1, r2, m + n + 1);
889 }
890 } TEST_END;
891
892 return result;
893 }
894
test_addmul1(void)895 int test_addmul1(void)
896 {
897 int result = 1;
898 nn_t a, b, r1, r2;
899 word_t c1, c2, ci;
900 len_t m, n;
901
902 printf("nn_addmul1...");
903
904 /* test a + b * (c1 + c2) = a + b * c1 + b * c2 */
905 TEST_START(1, ITER)
906 {
907 randoms_upto(100, ANY, state, &m, NULL);
908
909 randoms_of_len(m, ANY, state, &a, &b, NULL);
910 randoms_of_len(m + 1, ANY, state, &r1, &r2, NULL);
911
912 do randoms(ANY, state, &c1, &c2, NULL);
913 while (c1 + c2 < c1);
914
915 nn_copy(r1, a, m);
916 nn_copy(r2, a, m);
917
918 r1[m] = nn_addmul1(r1, b, m, c1);
919 r1[m] += nn_addmul1(r1, b, m, c2);
920
921 r2[m] = nn_addmul1(r2, b, m, c1 + c2);
922
923 result = nn_equal_m(r1, r2, m + 1);
924
925 if (!result)
926 {
927 bsdnt_printf("m = %m, c1 = %wx, c2 = %wx\n", m, c1, c2);
928 print_debug(a, m); print_debug(b, m);
929 print_debug_diff(r1, r2, m + 1);
930 }
931 } TEST_END;
932
933 /* test chaining of addmul1 */
934 TEST_START(chaining, ITER)
935 {
936 randoms_upto(100, ANY, state, &m, &n, NULL);
937
938 randoms_of_len(m + n, ANY, state, &a, NULL);
939 randoms_of_len(m + n + 1, ANY, state, &r1, &r2, NULL);
940
941 nn_copy(r2, r1, m + n);
942
943 randoms(ANY, state, &c1, NULL);
944
945 ci = nn_addmul1(r1, a, m, c1);
946 r1[m + n] = nn_addmul1_c(r1 + m, a + m, n, c1, ci);
947
948 r2[m + n] = nn_addmul1(r2, a, m + n, c1);
949
950 result = nn_equal_m(r1, r2, m + n + 1);
951
952 if (!result)
953 {
954 bsdnt_printf("m = %m, n = %m, c1 = %wx\n", m, n, c1);
955 print_debug(a, m + n);
956 print_debug_diff(r1, r2, m + n + 1);
957 }
958 } TEST_END;
959
960 return result;
961 }
962
test_submul1(void)963 int test_submul1(void)
964 {
965 int result = 1;
966 nn_t a, b, r1, r2;
967 word_t c1, c2, ci;
968 len_t m, n;
969
970 printf("nn_submul1...");
971
972 /* test a - b * (c1 + c2) = a - b * c1 - b * c2 */
973 TEST_START(1, ITER)
974 {
975 randoms_upto(100, ANY, state, &m, NULL);
976
977 randoms_of_len(m, ANY, state, &a, &b, NULL);
978 randoms_of_len(m + 1, ANY, state, &r1, &r2, NULL);
979
980 do randoms(ANY, state, &c1, &c2, NULL);
981 while (c1 + c2 < c1);
982
983 nn_copy(r1, a, m);
984 nn_copy(r2, a, m);
985
986 r1[m] = -nn_submul1(r1, b, m, c1);
987 r1[m] -= nn_submul1(r1, b, m, c2);
988
989 r2[m] = -nn_submul1(r2, b, m, c1 + c2);
990
991 result = nn_equal_m(r1, r2, m + 1);
992
993 if (!result)
994 {
995 bsdnt_printf("m = %m, c1 = %wx, c2 = %wx\n", m, c1, c2);
996 print_debug(a, m); print_debug(b, m);
997 print_debug_diff(r1, r2, m + 1);
998 }
999 } TEST_END;
1000
1001 /* test chaining of submul1 */
1002 TEST_START(chaining, ITER)
1003 {
1004 randoms_upto(100, ANY, state, &m, &n, NULL);
1005
1006 randoms_of_len(m + n, ANY, state, &a, NULL);
1007 randoms_of_len(m + n + 1, ANY, state, &r1, &r2, NULL);
1008
1009 nn_copy(r2, r1, m + n);
1010
1011 randoms(ANY, state, &c1, NULL);
1012
1013 ci = nn_submul1(r1, a, m, c1);
1014 r1[m + n] = -nn_submul1_c(r1 + m, a + m, n, c1, ci);
1015
1016 r2[m + n] = -nn_submul1(r2, a, m + n, c1);
1017
1018 result = nn_equal_m(r1, r2, m + n + 1);
1019
1020 if (!result)
1021 {
1022 bsdnt_printf("m = %m, n = %m, c1 = %wx\n", m, n, c1);
1023 print_debug(a, m + n);
1024 print_debug_diff(r1, r2, m + n + 1);
1025 }
1026 } TEST_END;
1027
1028 return result;
1029 }
1030
test_add1(void)1031 int test_add1(void)
1032 {
1033 int result = 1;
1034 nn_t a, r1, r2;
1035 word_t c1, c2, ci;
1036 len_t m, n;
1037
1038 printf("nn_add1...");
1039
1040 /* test a + c1 + c2 = a + c2 + c1 */
1041 TEST_START(1, ITER)
1042 {
1043 randoms_upto(100, ANY, state, &m, NULL);
1044
1045 randoms_of_len(m, ANY, state, &a, NULL);
1046 randoms_of_len(m + 1, ANY, state, &r1, &r2, NULL);
1047
1048 randoms(ANY, state, &c1, &c2, NULL);
1049
1050 r1[m] = nn_add1(r1, a, m, c1);
1051 r1[m] += nn_add1(r1, r1, m, c2);
1052
1053 r2[m] = nn_add1(r2, a, m, c2);
1054 r2[m] += nn_add1(r2, r2, m, c1);
1055
1056 result = nn_equal_m(r1, r2, m + 1);
1057
1058 if (!result)
1059 {
1060 bsdnt_printf("m = %m, c1 = %wx, c2 = %wx\n", m, c1, c2);
1061 print_debug(a, m);
1062 print_debug_diff(r1, r2, m + 1);
1063 }
1064 } TEST_END;
1065
1066 /* test chaining of add1 */
1067 TEST_START(chaining, ITER)
1068 {
1069 randoms_upto(100, ANY, state, &m, &n, NULL);
1070
1071 randoms_of_len(m + n, ANY, state, &a, NULL);
1072 randoms_of_len(m + n + 1, ANY, state, &r1, &r2, NULL);
1073
1074 randoms(ANY, state, &c1, NULL);
1075
1076 ci = nn_add1(r1, a, m, c1);
1077 r1[m + n] = nn_add1(r1 + m, a + m, n, ci);
1078
1079 r2[m + n] = nn_add1(r2, a, m + n, c1);
1080
1081 result = nn_equal_m(r1, r2, m + n + 1);
1082
1083 if (!result)
1084 {
1085 bsdnt_printf("m = %m, n = %m, c1 = %wx\n", m, n, c1);
1086 print_debug(a, m + n);
1087 print_debug_diff(r1, r2, m + n + 1);
1088 }
1089 } TEST_END;
1090
1091 return result;
1092 }
1093
test_sub1(void)1094 int test_sub1(void)
1095 {
1096 int result = 1;
1097 nn_t a, r1, r2;
1098 word_t c1, c2, ci;
1099 len_t m, n;
1100
1101 printf("nn_sub1...");
1102
1103 /* test a - c1 - c2 = a - c2 - c1 */
1104 TEST_START(1, ITER)
1105 {
1106 randoms_upto(100, ANY, state, &m, NULL);
1107
1108 randoms_of_len(m, ANY, state, &a, NULL);
1109 randoms_of_len(m + 1, ANY, state, &r1, &r2, NULL);
1110
1111 randoms(ANY, state, &c1, &c2, NULL);
1112
1113 r1[m] = -nn_sub1(r1, a, m, c1);
1114 r1[m] -= nn_sub1(r1, r1, m, c2);
1115
1116 r2[m] = -nn_sub1(r2, a, m, c2);
1117 r2[m] -= nn_sub1(r2, r2, m, c1);
1118
1119 result = nn_equal_m(r1, r2, m + 1);
1120
1121 if (!result)
1122 {
1123 bsdnt_printf("m = %m, c1 = %wx, c2 = %wx\n", m, c1, c2);
1124 print_debug(a, m);
1125 print_debug_diff(r1, r2, m + 1);
1126 }
1127 } TEST_END;
1128
1129 /* test chaining of sub1 */
1130 TEST_START(chaining, ITER)
1131 {
1132 randoms_upto(100, ANY, state, &m, &n, NULL);
1133
1134 randoms_of_len(m + n, ANY, state, &a, NULL);
1135 randoms_of_len(m + n + 1, ANY, state, &r1, &r2, NULL);
1136
1137 randoms(ANY, state, &c1, NULL);
1138
1139 ci = nn_sub1(r1, a, m, c1);
1140 r1[m + n] = -nn_sub1(r1 + m, a + m, n, ci);
1141
1142 r2[m + n] = -nn_sub1(r2, a, m + n, c1);
1143
1144 result = nn_equal_m(r1, r2, m + n + 1);
1145
1146 if (!result)
1147 {
1148 bsdnt_printf("m = %m, n = %m, c1 = %wx\n", m, n, c1);
1149 print_debug(a, m + n);
1150 print_debug_diff(r1, r2, m + n + 1);
1151 }
1152 } TEST_END;
1153
1154 /* test a + c1 - c1 = a */
1155 TEST_START(2, ITER)
1156 {
1157 randoms_upto(100, ANY, state, &m, NULL);
1158
1159 randoms_of_len(m + 1, ANY, state, &a, &r1, NULL);
1160 a[m] = 0;
1161
1162 randoms(ANY, state, &c1, NULL);
1163
1164 r1[m] = nn_add1(r1, a, m, c1);
1165 r1[m] -= nn_sub1(r1, r1, m, c1);
1166
1167 result = nn_equal_m(r1, a, m + 1);
1168
1169 if (!result)
1170 {
1171 bsdnt_printf("m = %m, c1 = %wx\n", m, c1);
1172 print_debug(a, m + 1);
1173 print_debug_diff(r1, a, m + 1);
1174 }
1175 } TEST_END;
1176
1177 return result;
1178 }
1179
test_not(void)1180 int test_not(void)
1181 {
1182 int result = 1;
1183 nn_t a, r1;
1184 len_t m;
1185
1186 printf("nn_not...");
1187
1188 /* test not not a = a */
1189 TEST_START(1, ITER)
1190 {
1191 randoms_upto(100, ANY, state, &m, NULL);
1192
1193 randoms_of_len(m, ANY, state, &a, &r1, NULL);
1194
1195 nn_not(r1, a, m);
1196 nn_not(r1, r1, m);
1197
1198 result = nn_equal_m(r1, a, m);
1199
1200 if (!result)
1201 {
1202 print_debug(a, m);
1203 print_debug_diff(r1, a, m);
1204 }
1205 } TEST_END;
1206
1207 return result;
1208 }
1209
test_popcount(void)1210 int test_popcount(void)
1211 {
1212 int result = 1;
1213 nn_t a;
1214 len_t m;
1215 bits_t i, count1, count2;
1216
1217 printf("nn_popcount...");
1218
1219 /* test popcount against naive nn_bit_test algorithm */
1220 TEST_START(1, ITER)
1221 {
1222 randoms_upto(100, ANY, state, &m, NULL);
1223 randoms_of_len(m, ANY, state, &a, NULL);
1224
1225 count1 = nn_popcount(a, m);
1226 count2 = 0;
1227 for (i = 0; i < m * WORD_BITS; i++)
1228 count2 += !!nn_bit_test(a, i);
1229
1230 result = (count1 == count2);
1231 if (!result)
1232 print_debug(a, m);
1233 } TEST_END;
1234
1235 return result;
1236 }
1237
test_scan1(void)1238 int test_scan1(void)
1239 {
1240 int result = 1;
1241 nn_t a;
1242 len_t m;
1243 bits_t skip, b1, b2;
1244
1245 printf("nn_scan1...");
1246
1247 /* test scan1 against naive nn_bit_test algorithm */
1248 TEST_START(1, ITER)
1249 {
1250 randoms_upto(100, NONZERO, state, &m, NULL);
1251 randoms_upto(m * WORD_BITS, ANY, state, &skip, NULL);
1252 randoms_of_len(m, ANY, state, &a, NULL);
1253
1254 b1 = nn_scan1(skip, a, m);
1255 for (b2 = skip; b2 < m * WORD_BITS; b2++)
1256 {
1257 if (nn_bit_test(a, b2))
1258 break;
1259 }
1260 if (b2 == m * WORD_BITS)
1261 b2 = -1;
1262
1263 result = (b1 == b2);
1264 if (!result)
1265 {
1266 printf(BITS_FMT " " BITS_FMT "\n", b1, b2);
1267 print_debug(a, m);
1268 }
1269 } TEST_END;
1270
1271 return result;
1272 }
1273
test_hamdist_m(void)1274 int test_hamdist_m(void)
1275 {
1276 int result = 1;
1277 nn_t a, b, r1;
1278 len_t m;
1279 bits_t dist1, dist2;
1280
1281 printf("nn_hamdist_m...");
1282
1283 /* test hamdist against xor & popcount */
1284 TEST_START(1, ITER)
1285 {
1286 randoms_upto(100, ANY, state, &m, NULL);
1287 randoms_of_len(m, ANY, state, &a, &b, &r1, NULL);
1288
1289 dist1 = nn_hamdist_m(a, b, m);
1290 nn_xor_m(r1, a, b, m);
1291 dist2 = nn_popcount(r1, m);
1292
1293 result = (dist1 == dist2);
1294 if (!result)
1295 {
1296 print_debug(a, m);
1297 print_debug_diff(r1, a, m);
1298 }
1299 } TEST_END;
1300
1301 return result;
1302 }
1303
test_neg(void)1304 int test_neg(void)
1305 {
1306 int result = 1;
1307 nn_t a, r1, r2;
1308 len_t m, n;
1309 word_t ci;
1310
1311 printf("nn_neg...");
1312
1313 /* test neg a = (not a) + 1 */
1314 TEST_START(1, ITER)
1315 {
1316 randoms_upto(100, ANY, state, &m, NULL);
1317
1318 randoms_of_len(m, ANY, state, &a, NULL);
1319 randoms_of_len(m + 1, ANY, state, &r1, &r2, NULL);
1320
1321 r1[m] = -nn_neg(r1, a, m);
1322
1323 nn_not(r2, a, m);
1324 r2[m] = ~ (word_t) 0;
1325 r2[m] += nn_add1(r2, r2, m, 1);
1326
1327 result = nn_equal_m(r1, r2, m + 1);
1328
1329 if (!result)
1330 {
1331 print_debug(a, m);
1332 print_debug_diff(r1, r2, m + 1);
1333 }
1334 } TEST_END;
1335
1336 /* test chaining of neg */
1337 TEST_START(chaining, ITER)
1338 {
1339 randoms_upto(100, ANY, state, &m, &n, NULL);
1340
1341 randoms_of_len(m + n, ANY, state, &a, NULL);
1342 randoms_of_len(m + n + 1, ANY, state, &r1, &r2, NULL);
1343
1344 r1[m + n] = -nn_neg(r1, a, m + n);
1345
1346 ci = nn_neg(r2, a, m);
1347 r2[m + n] = -nn_neg_c(r2 + m, a + m, n, ci);
1348
1349 result = nn_equal_m(r1, r2, m + n + 1);
1350
1351 if (!result)
1352 {
1353 bsdnt_printf("m = %m, n = %m\n", m, n);
1354 print_debug(a, m + n);
1355 print_debug_diff(r1, r2, m + n + 1);
1356 }
1357 } TEST_END;
1358
1359 return result;
1360 }
1361
test_cmp_m(void)1362 int test_cmp_m(void)
1363 {
1364 int result = 1;
1365 nn_t a, b, r1, r2;
1366 len_t m1;
1367
1368 printf("nn_cmp_m...");
1369
1370 /* test that equal things compare equal */
1371 TEST_START(1, ITER)
1372 {
1373 randoms_upto(100, ANY, state, &m1, NULL);
1374
1375 randoms_of_len(m1, ANY, state, &r1, &r2, NULL);
1376
1377 nn_copy(r2, r1, m1);
1378
1379 result = (nn_cmp_m(r1, r2, m1) == 0);
1380
1381 if (!result)
1382 {
1383 print_debug(r1, m1);
1384 print_debug_diff(r1, r2, m1);
1385 }
1386 } TEST_END;
1387
1388 /* test that not equal values compare in the correct way */
1389 TEST_START(2, ITER)
1390 {
1391 randoms_upto(100, NONZERO, state, &m1, NULL);
1392
1393 randoms_of_len(m1 + 1, ANY, state, &r1, NULL);
1394
1395 do {
1396 randoms_of_len(m1, FULL, state, &a, &b, NULL);
1397 r1[m1] = nn_add_m(r1, a, b, m1);
1398 } while (r1[m1]);
1399
1400 result = (nn_cmp_m(r1, a, m1) > 0 && nn_cmp_m(a, r1, m1) < 0);
1401
1402 if (!result)
1403 {
1404 print_debug(a, m1); print_debug(b, m1); print_debug(r1, m1);
1405 print_debug_diff(r1, a, m1);
1406 }
1407 } TEST_END;
1408
1409 return result;
1410 }
1411
test_cmp(void)1412 int test_cmp(void)
1413 {
1414 int result = 1;
1415 nn_t a, b, r1, r2;
1416 len_t m1, m2;
1417
1418 printf("nn_cmp...");
1419
1420 /* test that equal things compare equal */
1421 TEST_START(1, ITER)
1422 {
1423 randoms_upto(100, ANY, state, &m1, NULL);
1424
1425 randoms_of_len(m1, ANY, state, &r1, &r2, NULL);
1426
1427 nn_copy(r2, r1, m1);
1428
1429 result = (nn_cmp(r1, m1, r2, m1) == 0);
1430
1431 if (!result)
1432 {
1433 print_debug(r1, m1);
1434 print_debug_diff(r1, r2, m1);
1435 }
1436 } TEST_END;
1437
1438 /* test that not equal lengths compare in the correct way */
1439 TEST_START(2, ITER)
1440 {
1441 randoms_upto(100, NONZERO, state, &m1, NULL);
1442 randoms_upto(m1, ANY, state, &m2, NULL);
1443
1444 randoms_of_len(m1, FULL, state, &r1, NULL);
1445 randoms_of_len(m2, FULL, state, &r2, NULL);
1446
1447 result = (nn_cmp(r1, m1, r2, m2) > 0 && nn_cmp(r2, m2, r1, m1) < 0);
1448
1449 if (!result)
1450 {
1451 print_debug(r1, m1); print_debug(r2, m1);
1452 }
1453 } TEST_END;
1454
1455 /* test that not equal values compare in the correct way */
1456 TEST_START(3, ITER)
1457 {
1458 randoms_upto(100, NONZERO, state, &m1, NULL);
1459
1460 randoms_of_len(m1 + 1, ANY, state, &r1, NULL);
1461
1462 do {
1463 randoms_of_len(m1, FULL, state, &a, &b, NULL);
1464 r1[m1] = nn_add_m(r1, a, b, m1);
1465 } while (r1[m1]);
1466
1467 result = (nn_cmp(r1, m1, a, m1) > 0 && nn_cmp(a, m1, r1, m1) < 0);
1468
1469 if (!result)
1470 {
1471 print_debug(a, m1); print_debug(b, m1); print_debug(r1, m1);
1472 print_debug_diff(r1, a, m1);
1473 }
1474 } TEST_END;
1475
1476 return result;
1477 }
1478
test_divrem1_simple(void)1479 int test_divrem1_simple(void)
1480 {
1481 int result = 1;
1482 nn_t a, q, r1, r2;
1483 len_t m, n;
1484 word_t d, ci, r;
1485
1486 printf("nn_divrem1_simple...");
1487
1488 /* test that a = q * d + r */
1489 TEST_START(1, ITER)
1490 {
1491 randoms_upto(100, ANY, state, &m, NULL);
1492
1493 randoms_of_len(m, ANY, state, &r1, &a, &q, NULL);
1494
1495 randoms(NONZERO, state, &d, NULL);
1496
1497 r = nn_divrem1_simple(q, a, m, d);
1498
1499 ci = nn_mul1_c(r1, q, m, d, r);
1500
1501 result = (nn_equal_m(r1, a, m) && ci == 0);
1502
1503 if (!result)
1504 {
1505 bsdnt_printf("ci = %wx, d = %wx\n", ci, d);
1506 print_debug(a, m); print_debug(q, m); print_debug(r1, m);
1507 print_debug_diff(r1, a, m);
1508 }
1509 } TEST_END;
1510
1511 /* test chaining of divrem1_simple */
1512 TEST_START(chaining, ITER)
1513 {
1514 randoms_upto(100, ANY, state, &m, &n, NULL);
1515
1516 randoms_of_len(m + n, ANY, state, &r1, &r2, &a, NULL);
1517
1518 randoms(NONZERO, state, &d, NULL);
1519
1520
1521 ci = nn_divrem1_simple(r1 + n, a + n, m, d);
1522 nn_divrem1_simple_c(r1, a, n, d, ci);
1523
1524 nn_divrem1_simple(r2, a, m + n, d);
1525
1526 result = nn_equal_m(r1, r2, m + n);
1527
1528 if (!result)
1529 {
1530 bsdnt_printf("ci = %wx, d = %wx, m = %m, n = %m\n", ci, d, m, n);
1531 print_debug(a, m + n);
1532 print_debug_diff(r1, r2, m + n);
1533 }
1534 } TEST_END;
1535
1536 return result;
1537 }
1538
test_divrem1_preinv(void)1539 int test_divrem1_preinv(void)
1540 {
1541 int result = 1;
1542 nn_t a, q, r1, r2;
1543 len_t m, n;
1544 word_t d, ci, r, rem1, rem2;
1545 preinv1_t inv;
1546
1547 printf("nn_divrem1_preinv...");
1548
1549 /* test that a = q * d + r */
1550 TEST_START(1, ITER)
1551 {
1552 randoms_upto(100, ANY, state, &m, NULL);
1553
1554 randoms_of_len(m, ANY, state, &r1, &a, &q, NULL);
1555
1556 randoms(NORMALISED, state, &d, NULL);
1557
1558 inv = precompute_inverse1(d);
1559
1560 r = nn_divrem1_preinv(q, a, m, d, inv);
1561
1562 ci = nn_mul1_c(r1, q, m, d, r);
1563
1564 result = (nn_equal_m(r1, a, m) && ci == 0);
1565
1566 if (!result)
1567 {
1568 bsdnt_printf("ci = %wx, r = %wx\n", ci, r);
1569 print_debug(a, m); print_debug(q, m);
1570 print_debug_diff(r1, a, m);
1571 }
1572 } TEST_END;
1573
1574 /* test chaining of divrem1_preinv */
1575 TEST_START(chaining, ITER)
1576 {
1577 randoms_upto(100, ANY, state, &m, &n, NULL);
1578
1579 randoms_of_len(m + n, ANY, state, &r1, &r2, &a, NULL);
1580
1581 randoms(NORMALISED, state, &d, NULL);
1582
1583 inv = precompute_inverse1(d);
1584
1585 nn_random(a, state, m + n);
1586
1587 ci = nn_divrem1_preinv(r1 + n, a + n, m, d, inv);
1588 rem1 = nn_divrem1_preinv_c(r1, a, n, d, inv, ci);
1589
1590 rem2 = nn_divrem1_preinv(r2, a, m + n, d, inv);
1591
1592 result = (nn_equal_m(r1, r2, m + n) && rem1 == rem2);
1593
1594 if (!result)
1595 {
1596 bsdnt_printf("ci = %wx, rem1 = %wx, rem2 = %wx, m = %m, n = %m\n",
1597 ci, rem1, rem2, m, n);
1598 print_debug(a, m + n);
1599 print_debug_diff(r1, r2, m + n);
1600 }
1601 } TEST_END;
1602
1603 return result;
1604 }
1605
test_divrem_hensel1_preinv(void)1606 int test_divrem_hensel1_preinv(void)
1607 {
1608 int result = 1;
1609 nn_t a, q, r1, r2;
1610 len_t m, n;
1611 word_t d, ci, r, rem1, rem2;
1612 hensel_preinv1_t inv;
1613
1614 printf("nn_divrem_hensel1_preinv...");
1615
1616 /* test that a + B^m * r = q * d */
1617 TEST_START(1, ITER)
1618 {
1619 randoms_upto(100, ANY, state, &m, NULL);
1620
1621 randoms_of_len(m, ANY, state, &r1, &a, &q, NULL);
1622
1623 randoms(ODD, state, &d, NULL);
1624
1625 precompute_hensel_inverse1(&inv, d);
1626
1627 r = nn_divrem_hensel1_preinv(q, a, m, d, inv);
1628
1629 ci = nn_mul1(r1, q, m, d);
1630
1631 result = (nn_equal_m(r1, a, m) && ci == r);
1632
1633 if (!result)
1634 {
1635 bsdnt_printf("ci = %wx, r = %wx\n, inv = %wx", ci, r, inv);
1636 print_debug(a, m); print_debug(q, m);
1637 print_debug_diff(r1, a, m);
1638 }
1639 } TEST_END;
1640
1641 /* test chaining of divrem_hensel1_preinv */
1642 TEST_START(chaining, ITER)
1643 {
1644 randoms_upto(100, ANY, state, &m, &n, NULL);
1645
1646 randoms_of_len(m + n, ANY, state, &r1, &r2, &a, NULL);
1647
1648 randoms(ODD, state, &d, NULL);
1649
1650 precompute_hensel_inverse1(&inv, d);
1651 ci = nn_divrem_hensel1_preinv(r1, a, m, d, inv);
1652 rem1 = nn_divrem_hensel1_preinv_c(r1 + m, a + m, n, d, inv, ci);
1653
1654 rem2 = nn_divrem_hensel1_preinv(r2, a, m + n, d, inv);
1655
1656 result = (nn_equal_m(r1, r2, m + n) && (rem1 == rem2));
1657
1658 if (!result)
1659 {
1660 bsdnt_printf("ci = %wx, rem1 = %wx, rem2 = %wx, m = %m, n = %m, d = %wx, inv = %wx\n",
1661 ci, rem1, rem2, m, n, d, inv);
1662 print_debug(a, m + n);
1663 print_debug_diff(r1, r2, m + n);
1664 }
1665 } TEST_END;
1666
1667 return result;
1668 }
1669
test_mod1_preinv(void)1670 int test_mod1_preinv(void)
1671 {
1672 int result = 1;
1673 nn_t a, a2, q;
1674 len_t m, n;
1675 word_t d, ci, rem1, rem2;
1676 preinv1_t inv;
1677 mod_preinv1_t minv;
1678 bits_t norm;
1679
1680 printf("nn_mod1_preinv...");
1681
1682 /* test that divrem1 and mod1 return same remainder */
1683 TEST_START(1, ITER)
1684 {
1685 randoms_upto(100, ANY, state, &m, NULL);
1686
1687 randoms_of_len(m, ANY, state, &a, &a2, &q, NULL);
1688
1689 randoms(NONZERO, state, &d, NULL);
1690
1691 norm = high_zero_bits(d);
1692 ci = nn_shl(a2, a, m, norm);
1693
1694 inv = precompute_inverse1(d << norm);
1695 rem1 = nn_divrem1_preinv_c(q, a2, m, d << norm, inv, ci) >> norm;
1696
1697 precompute_mod_inverse1(&minv, d);
1698 rem2 = nn_mod1_preinv(a, m, d, minv);
1699
1700 result = (rem1 == rem2);
1701
1702 if (!result)
1703 {
1704 bsdnt_printf("rem1 = %wx, rem2 = %wx, m = %m, d = %wx, "
1705 "minv.b1 = %wx, minv.b2 = %wx, minv.b3 = %wx\n",
1706 rem1, rem2, m, d, minv.b1, minv.b2, minv.b3);
1707 print_debug(a, m); print_debug(q, m);
1708 }
1709 } TEST_END;
1710
1711 /* test chaining of mod1_preinv */
1712 TEST_START(chaining, ITER)
1713 {
1714 randoms_upto(100, ANY, state, &m, &n, NULL);
1715
1716 randoms_of_len(m + n, ANY, state, &a, &q, NULL);
1717
1718 randoms(NONZERO, state, &d, NULL);
1719
1720 precompute_mod_inverse1(&minv, d);
1721 ci = nn_mod1_preinv(a + n, m, d, minv);
1722 rem1 = nn_mod1_preinv_c(a, n, d, minv, ci);
1723
1724 rem2 = nn_mod1_preinv(a, m + n, d, minv);
1725
1726 result = (rem1 == rem2);
1727
1728 if (!result)
1729 {
1730 bsdnt_printf("ci = %wx, rem1 = %wx, rem2 = %wx, m = %m, n = %m, d = %wx, "
1731 "minv.b1 = %wx, minv.b2 = %wx, minv.b3 = %wx\n",
1732 ci, rem1, rem2, m, n, d, minv.b1, minv.b2, minv.b3);
1733 print_debug(a, m + n);
1734 }
1735 } TEST_END;
1736
1737 return result;
1738 }
1739
test_linear(void)1740 int test_linear(void)
1741 {
1742 long pass = 0;
1743 long fail = 0;
1744
1745 RUN(test_gc);
1746 RUN(test_tmp);
1747 RUN(test_bit_set);
1748 RUN(test_bit_clear);
1749 RUN(test_not);
1750 RUN(test_popcount);
1751 RUN(test_scan1);
1752 RUN(test_hamdist_m);
1753 RUN(test_neg);
1754 RUN(test_add1);
1755 RUN(test_add_m);
1756 RUN(test_add);
1757 RUN(test_sub1);
1758 RUN(test_sub_m);
1759 RUN(test_sub);
1760 RUN(test_shl);
1761 RUN(test_shr);
1762 RUN(test_copy);
1763 RUN(test_equal_m);
1764 RUN(test_equal);
1765 RUN(test_zero);
1766 RUN(test_normalise);
1767 RUN(test_mul1);
1768 RUN(test_addmul1);
1769 RUN(test_submul1);
1770 RUN(test_cmp_m);
1771 RUN(test_cmp);
1772 RUN(test_divrem1_simple);
1773 RUN(test_divrem1_preinv);
1774 RUN(test_divrem_hensel1_preinv);
1775 RUN(test_mod1_preinv);
1776
1777 printf("%ld of %ld tests pass.\n", pass, pass + fail);
1778
1779 return (fail != 0);
1780 }
1781
main(void)1782 int main(void)
1783 {
1784 int ret = 0;
1785
1786 printf("\nTesting nn_linear functions:\n");
1787
1788 randinit(&state);
1789 checkpoint_rand("First Random Word: ");
1790
1791 ret = test_linear();
1792
1793 randclear(state);
1794
1795 return ret;
1796 }
1797