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