1/*
2 * Copyright (c) 1998,2011,2014 Apple Inc. All Rights Reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23
24
25#include "giantIntegers.h"
26#include "ckutilities.h"
27#include "feeFunctions.h"
28#include "feeDebug.h"
29#include <stdlib.h>
30#include "ckutilsPlatform.h"
31#include <stdio.h>
32#include <time.h>
33
34#define LOOPS_DEF	100
35#define MAX_SIZE_DEF	32
36#define LOOP_NOTIFY	100
37
38/* quick test to show modg(1,g) broken */
39#define MODG1_TEST_ENABLE	1
40
41static void usage(char **argv)
42{
43	printf("usage: %s [options]\n", argv[0]);
44	printf("   Options:\n");
45	printf("   l=loops    (default = %d)\n", LOOPS_DEF);
46	printf("   x=maxBytes (default = %d)\n", MAX_SIZE_DEF);
47	printf("   s=seed\n");
48	printf("   h(elp)\n");
49	exit(1);
50}
51
52/*
53 * ...min <= return <= max
54 */
55static int genRand(int min, int max)
56{
57
58    /* note random() only yields a 31-bit number... */
59
60    if(max == min)			/* avoid % 1 ! */
61	return(max);
62    else
63	return(min + (RAND() % (max-min+1)));
64}
65
66/*
67 * Fill buffer with random data, random size from 1 to maxSize.
68 * Returns size of random data generated.
69 */
70static unsigned fillData(unsigned maxSize,
71	unsigned char *data,
72	int evenOnly)
73{
74	unsigned 	*ip;
75	unsigned 	intCount;
76	unsigned 	residue;
77	unsigned char	*cp;
78	int 		i;
79	unsigned	size;
80
81	size = genRand(1, maxSize);
82	if(evenOnly) {
83		size &= ~1;
84		if(size == 1) {
85			size = 2;
86		}
87	}
88	intCount = size >> 2;
89	ip = (unsigned *)data;
90	for(i=0; i<intCount; i++) {
91		*ip++ = RAND();
92	}
93
94	residue = size & 0x3;
95	cp = (unsigned char *)ip;
96	for(i=0; i<residue; i++) {
97		*cp++ = (unsigned char)RAND();
98	}
99	return size;
100}
101
102/*
103 * create a giant with random size and data. *Buf is mallocd and
104 * uninitialized and will change here.
105 */
106static giant genGiant(unsigned maxBytes, unsigned char *buf)
107{
108	int size = fillData(maxBytes, buf, 0);
109	int i;
110	giant g;
111
112	g = giant_with_data(buf, size);
113
114	/* set random sign; giant_with_data() is always positive */
115	i = RAND();
116	if(i & 1) {
117		g->sign = -g->sign;
118	}
119
120	/* avoid zero data - too many pitfalls with mod and div */
121	if(isZero(g)) {
122		g->sign = 1;
123		g->n[0] = 0x77;
124	}
125	return g;
126}
127
128static int testError()
129{
130	char resp[100];
131
132	printf("Attach via debugger for more info.\n");
133	printf("a to abort, c to continue: ");
134	gets(resp);
135	return (resp[0] != 'c');
136}
137
138/* g := |g1| */
139static void gabs(giant g)
140{
141	if(g->sign < 0) {
142	    g->sign = -g->sign;
143	}
144}
145
146/*
147 * Individual tests. API is identical for all tests.
148 *
149 * g1, g2 : giants with random data, size, and sign. Tests do not modify
150 *           these.
151 * scr1, scr2 : scratch giants, big enough for all conceivable ops. Can
152 *           be modified at will.
153 * Return : 0 for sucess, 1 on error.
154 */
155
156static int compTest(giant g1, giant g2, giant scr1, giant scr2)
157{
158	gtog(g1, scr1);		// scr1 := g1
159	gtog(scr1, scr2);
160	if(gcompg(g1, scr2)) {
161		printf("gtog/gcompg error\n");
162		return testError();
163	}
164	return 0;
165}
166
167static int addSubTest(giant g1, giant g2, giant scr1, giant scr2)
168{
169	gtog(g1, scr1);		// scr1 := g1
170	addg(g2, scr1);		// scr1 := g1 + g2
171	subg(g1, scr1);		// scr1 := g1 + g2 - g1 =? g2
172	if(gcompg(g2, scr1)) {
173		printf("addg/subg error\n");
174		return testError();
175	}
176	return 0;
177}
178
179#define LARGEST_MUL	0xffff
180
181static int mulTest(giant g1, giant g2, giant scr1, giant scr2)
182{
183	int randInt = genRand(1, LARGEST_MUL);
184	int i;
185	int rtn = 0;
186
187	int_to_giant(randInt, scr1);	// scr1 := randInt
188	gtog(g1, scr2);			// scr2 := g1
189	mulg(scr1, scr2);		// scr2 := g1 * randInt
190
191	/* now do the same thing with multiple adds */
192	int_to_giant(0, scr1);		// scr1 := 0
193	for(i=0; i<randInt; i++) {
194		addg(g1, scr1);		// scr1 += g1
195	}				// scr1 =? g1 * randInt
196	if(gcompg(scr1, scr2)) {
197		printf("g1        : "); printGiantHex(g1);
198		printf("randInt   : 0x%x\n", randInt);
199		printf("good prod : "); printGiantHex(scr1);
200		printf("bad prod  : "); printGiantHex(scr2);
201		printf("mulg error\n");
202		rtn = testError();
203	}
204	return rtn;
205
206}
207
208static int squareTest(giant g1, giant g2, giant scr1, giant scr2)
209{
210	gtog(g1, scr1);
211	mulg(g1, scr1);			// scr1 := g1 * g1
212	gtog(g1, scr2);
213	gsquare(scr2);			// scr2 =? g1 * g1
214	if(gcompg(scr1, scr2)) {
215		printf("gsquare error\n");
216		return testError();
217	}
218	return 0;
219}
220
221static int lshiftTest(giant g1, giant g2, giant scr1, giant scr2)
222{
223    	int maxShift = (scr1->capacity - abs(g1->sign) - 1) *
224			 GIANT_BITS_PER_DIGIT;
225	int shiftCnt = genRand(1, maxShift);
226	giant scr3 = borrowGiant(scr1->capacity);
227	int rtn = 0;
228
229	gtog(g1, scr1);			// scr1 := g1
230	gshiftleft(shiftCnt, scr1);	// scr1 := (g1 << shiftCnt)
231
232	gtog(g1, scr2);			// scr2 := g1
233	if(shiftCnt <= 30) {
234	    int multInt = (1 << shiftCnt);
235	    int_to_giant(multInt, scr3);   // scr3 := (1 << shiftCnt)
236	}
237	else {
238	    int_to_giant(1, scr3);	// scr3 := 1;
239	    gshiftleft(shiftCnt, scr3);	// scr3 := (1 << shiftCnt)
240	}
241	mulg(scr3, scr2);		// scr2 := g1 * (1 << shiftCnt);
242	if(gcompg(scr1, scr2)) {
243		printf("shiftCnt %d 0x%x\n", shiftCnt, shiftCnt);
244		printf("g1   : "); printGiantHex(g1);
245		printf("scr1 : "); printGiantHex(scr1);
246		printf("scr2 : "); printGiantHex(scr2);
247		printf("gshiftleft error\n");
248		rtn = testError();
249	}
250	returnGiant(scr3);
251	return rtn;
252}
253
254static int rshiftTest(giant g1, giant g2, giant scr1, giant scr2)
255{
256    	int maxShift = bitlen(g1) - 1;
257	int shiftCnt;
258	giant scr3 = borrowGiant(scr1->capacity);
259	int rtn = 0;
260
261	/* special case, can't have g1 = 1 */
262	if(maxShift == 0) {
263		#if	FEE_DEBUG
264		printf("...rshiftTest: tweaking g1 = 1\n");
265		#endif
266		g1->n[0] = 2;
267		shiftCnt = 1;
268	}
269	else {
270		shiftCnt = genRand(1, maxShift);
271	}
272	gtog(g1, scr1);			// scr1 := g1
273	gabs(scr1);			// scr1 := |g1|
274	gtog(scr1, scr2);		// scr2 := |g1|
275	gshiftright(shiftCnt, scr1);	// scr1 := (|g1| >> shiftCnt)
276
277	if(shiftCnt <= 30) {
278	    int multInt = (1 << shiftCnt);
279	    int_to_giant(multInt, scr3);   // scr3 := (1 << shiftCnt)
280	}
281	else {
282	    int_to_giant(1, scr3);	// scr3 := 1;
283	    gshiftleft(shiftCnt, scr3);	// scr3 := (1 << shiftCnt)
284	}
285	divg(scr3, scr2);		// scr2 := g1 / (1 << shiftCnt);
286	if(gcompg(scr1, scr2)) {
287		printf("shiftCnt %d 0x%x\n", shiftCnt, shiftCnt);
288		printf("g1   : "); printGiantHex(g1);
289		printf("scr1 : "); printGiantHex(scr1);
290		printf("scr2 : "); printGiantHex(scr2);
291		printf("gshiftright error\n");
292		rtn = testError();
293	}
294	returnGiant(scr3);
295	return rtn;
296}
297
298static int divTest(giant g1, giant g2, giant scr1, giant scr2)
299{
300	gtog(g1, scr1);		// scr1 := g1
301	mulg(g2, scr1);		// scr1 := g1 * g2
302	gtog(g2, scr2);		// scr2 := g2
303	gabs(scr2);		// scr2 := |g2|
304	divg(scr2, scr1);	// scr1 := (g1 * g2) / |g2|
305
306	/* weird case - if g2 is negative, this result is -g1! */
307	if(g2->sign < 0) {
308	    scr1->sign = -scr1->sign;
309	}
310	if(gcompg(scr1, g1)) {
311	    printf("g1 : "); printGiantHex(g1);
312	    printf("g2 : "); printGiantHex(g1);
313	    printf("scr1 : "); printGiantHex(scr1);
314	    printf("divTest error\n");
315	    return testError();
316	}
317	return 0;
318}
319
320#define LARGEST_MOD_MUL	0x40
321
322static int modTest(giant g1, giant g2, giant scr1, giant scr2)
323{
324	int randInt = genRand(1, LARGEST_MOD_MUL);
325	giant scr3 = borrowGiant(scr1->capacity);
326	/* debug only */
327	giant scr4 = borrowGiant(scr1->capacity);
328	/* end debug */
329	int rtn = 0;
330
331	int_to_giant(randInt, scr1);	// scr1 := rand
332	gtog(g1, scr2);
333	gabs(scr2);			// scr2 := |g1|
334
335	/* current modg can't deal with g mod 1 ! */
336	if((scr2->sign == 1) && (scr2->n[0] == 1)) {
337		#if	MODG1_TEST_ENABLE
338		/* assume that this is legal... */
339		#if	FEE_DEBUG
340		printf("..modTest: g1 = 1, no tweak\n");
341		#endif
342		#else
343		printf("..modTest: tweaking g1 = 1\n");
344		scr2->n[0] = 0x54;
345		#endif	MODG1_TEST_ENABLE
346	}
347	/* end modg workaround */
348
349	gtog(g2, scr3);
350	gabs(scr3);			// scr3 := |g2|
351
352	/* this will only work if randInt < |g1| */
353	if(gcompg(scr1, scr2) >= 0) {
354	    #if	FEE_DEBUG
355	    printf("..modTest: tweaking rand, > g1 = "); printGiantHex(g1);
356	    printf("                            g2 = "); printGiantHex(g2);
357	    printf("                          rand = "); printGiantHex(scr1);
358	    #endif
359	    modg(scr2, scr1);		// scr1 := rand mod g1
360	    if(gcompg(scr1, scr2) >= 0) {
361		printf("simple modg error\n");
362		return testError();
363	    }
364	}
365
366	mulg(scr2, scr3);		// scr3 := |g1 * g2|
367	addg(scr1, scr3);		// scr3 := (|g1 * g2|) + rand
368	gtog(scr3, scr4);
369	modg(scr2, scr3);		// scr3 := scr3 mod |g1| =? rand
370	if(gcompg(scr1, scr3)) {
371		printf("g1 : "); printGiantHex(g1);
372		printf("g2 : "); printGiantHex(g2);
373		printf("rand : 0x%x\n", randInt);
374		printf("randG : "); printGiantHex(scr1);
375		printf("scr4 : "); printGiantHex(scr4);
376		printf("mod  : "); printGiantHex(scr3);
377		printf("modTest error\n");
378		rtn = testError();
379	}
380	returnGiant(scr3);
381	returnGiant(scr4);
382	return rtn;
383
384
385}
386
387#if	MODG1_TEST_ENABLE
388/* quickie test to demonstrate failure of modg(1, g). Known failure
389 * as of 10 Apr 1998.
390 * modg(1,g) fixed on 13 Apr 1998, so this should now work.
391 */
392static int modg1Test(giant g1, giant scr1, giant scr2)
393{
394	/* test mod(x, 1) */
395	scr1->n[0] = 1;
396	scr1->sign = 1;
397	gtog(g1, scr2);
398	modg(scr1, scr2);
399	if(!isZero(scr2)) {
400		printf("g1 : "); printGiantHex(g1);
401		printf("g1 mod 1 : "); printGiantHex(scr2);
402		return testError();
403	}
404	return 0;
405}
406#endif	MODG1_TEST_ENABLE
407
408static int mulOnesTest(giant g1, giant g2, giant scr1, giant scr2)
409{
410	int i;
411	int rtn = 0;
412	giant gOnes = borrowGiant(scr1->capacity);
413
414	/* set up a giant with all ones data */
415	gOnes->sign = abs(g1->sign);
416	for(i=0; i<gOnes->sign; i++) {
417		gOnes->n[i] = (giantDigit)(-1);
418	}
419
420	gtog(gOnes, scr1);		// scr1 := gOnes
421	mulg(g1, scr1);			// scr1 := gOnes * g1
422
423	gtog(g1, scr2);
424	mulg(gOnes, scr2);
425
426	if(gcompg(scr1, scr2)) {
427		printf("good prod : "); printGiantHex(scr1);
428		printf("bad prod  : "); printGiantHex(scr2);
429		printf("mulOnesTest error\n");
430		rtn = testError();
431	}
432	return rtn;
433
434}
435
436int main(int argc, char **argv)
437{
438	int		arg;
439	char		*argp;
440	giant		g1;		// init'd randomly
441	giant		g2;		// ditto
442	giant		scr1;		// scratch
443	giant		scr2;		// ditto
444	unsigned char	*buf;
445	int		loop;
446
447	int 		loops = LOOPS_DEF;
448	int		seedSpec = 0;
449	unsigned	seed = 0;
450	unsigned	maxSize = MAX_SIZE_DEF;
451
452	initCryptKit();
453
454	#ifdef	macintosh
455	seedSpec = 1;
456	seed = 0;
457	argc = 1;
458	maxSize = 8;
459	#endif
460
461	for(arg=1; arg<argc; arg++) {
462		argp = argv[arg];
463		switch(argp[0]) {
464		    case 'x':
465		    	maxSize = atoi(&argp[2]);
466			break;
467		    case 'l':
468		    	loops = atoi(&argp[2]);
469			break;
470		    case 's':
471			seed = atoi(&argp[2]);
472			seedSpec = 1;
473			break;
474		    case 'h':
475		    default:
476		    	usage(argv);
477		}
478	}
479	buf = malloc(maxSize);
480
481	if(!seedSpec) {
482		time_t	tim;
483		time(&tim);
484		seed = (unsigned)tim;
485	}
486	SRAND(seed);
487
488	/*
489	 * Scratch giants, big enough for anything
490	 */
491	scr1 = newGiant(4 * maxSize * GIANT_BYTES_PER_DIGIT);
492	scr2 = newGiant(4 * maxSize * GIANT_BYTES_PER_DIGIT);
493
494	printf("Starting giants test: seed %d\n", seed);
495	for(loop=0; loop<loops; loop++) {
496
497	    if((loop % LOOP_NOTIFY) == 0) {
498	    	printf("..loop %d\n", loop);
499	    }
500
501	    g1 = genGiant(maxSize, buf);
502	    g2 = genGiant(maxSize, buf);
503
504	    #if 1
505	    if(compTest(g1, g2, scr1, scr2)) {
506		    exit(1);
507	    }
508	    if(addSubTest(g1, g2, scr1, scr2)) {
509		    exit(1);
510	    }
511	    #endif
512	    #if 1
513	    if(mulTest(g1, g2, scr1, scr2)) {
514		    exit(1);
515	    }
516	    #endif
517	    #if 1
518	    if(squareTest(g1, g2, scr1, scr2)) {
519		    exit(1);
520	    }
521	    if(lshiftTest(g1, g2, scr1, scr2)) {
522		    exit(1);
523	    }
524	    if(modTest(g1, g2, scr1, scr2)) {
525		    exit(1);
526	    }
527	    if(rshiftTest(g1, g2, scr1, scr2)) {
528		    exit(1);
529	    }
530	    /* these all use divide....*/
531	    if(divTest(g1, g2, scr1, scr2)) {
532		    exit(1);
533	    }
534	    #if MODG1_TEST_ENABLE
535	    if(modg1Test(g1, scr1, scr2)) {
536	    	exit(1);
537	    }
538	    #endif
539	    #endif 0
540	    if(mulOnesTest(g1, g2, scr1, scr2)) {
541	    	exit(1);
542	    }
543	    freeGiant(g1);
544	    freeGiant(g2);
545	}
546
547	printf("...giantDvt complete\n");
548	return 0;
549}
550