libsecurity_cryptkit/ckutils/giantDvt/giantDvt.c

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