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