1/* 2 * atomTime.c - measure performance of mulg, gsquare, feemod, 3 * gshift{left,right}, elliptic, ellMulProj 4 */ 5 6#include "ckconfig.h" 7#include "ckutilsPlatform.h" 8#include "CryptKitSA.h" 9#include "ckutilities.h" /* needs private headers */ 10#include "curveParams.h" /* ditto */ 11#include "falloc.h" /* ditto */ 12#include "elliptic.h" 13#include "ellipticProj.h" 14#include <stdlib.h> 15#include <stdio.h> 16#include <time.h> 17 18/* default loops for "fast" and "slow" ops respecitively */ 19#define LOOPS_DEF_FAST 10000 20#define LOOPS_DEF_SLOW 100 21 22#define NUM_BORROW 100 23 24/* individual enables - normally all on, disable to zero in on one test */ 25#define MULG_ENABLE 1 26#define GSQUARE_ENABLE 1 27#define FEEMOD_ENABLE 1 28#define BORROW_ENABLE 1 29#define SHIFT_ENABLE 1 30#define BINVAUX_ENABLE 1 31#define MAKE_RECIP_ENABLE 1 32#define MODGRECIP_ENABLE 1 33#define KEYGEN_ENABLE 1 34#define ELLIPTIC_ENABLE 1 35#define ELL_SIMPLE_ENABLE 1 36 37static void usage(char **argv) 38{ 39 printf("Usage: %s [l=loops_fast] [L=loops_slow] [q(uick)] [D=depth]\n", argv[0]); 40 exit(1); 41} 42 43/* 44 * Fill numGiants with random data of length bits. 45 */ 46static void genRandGiants(giant *giants, 47 unsigned numGiants, 48 unsigned bits, 49 feeRand rand) 50{ 51 int i; 52 giant g; 53 unsigned char *rdata; 54 unsigned bytes = (bits + 7) / 8; 55 giantDigit mask = 0; 56 unsigned giantMsd = 0; // index of MSD 57 unsigned log2BitsPerDigit; 58 unsigned bitsPerDigit; 59 60 /* just to satisfy compiler - make sure it's always called */ 61 if(giants == NULL) { 62 return; 63 } 64 65 log2BitsPerDigit = GIANT_LOG2_BITS_PER_DIGIT; 66 bitsPerDigit = GIANT_BITS_PER_DIGIT; 67 68 if((bits & 7) != 0) { 69 /* 70 * deserializeGiant() has a resolution of one byte. We 71 * need more resolution - that is, we'll be creating 72 * giants a little larger than we need, and we'll mask off 73 * some bits in the giants' m.s. digit. 74 * This assumes that data fills the giantDigits such 75 * that if bytes mod GIANT_BYTES_PER_DIGIT != 0, the 76 * empty byte(s) in the MSD are in the m.s. byte(s). 77 */ 78 giantMsd = bits >> log2BitsPerDigit; 79 mask = (1 << (bits & (bitsPerDigit - 1))) - 1; 80 } 81 rdata = fmalloc(bytes); 82 for(i=0; i<numGiants; i++) { 83 g = giants[i]; 84 feeRandBytes(rand, rdata, bytes); 85 deserializeGiant(rdata, g, bytes); 86 if(mask != 0) { 87 int j; 88 89 g->n[giantMsd] &= mask; 90 91 /* 92 * We've zeroed out some bits; we might have to 93 * adjust the sign of the giant as well. Note that 94 * deserializeGiant always yields positive 95 * giants.... 96 */ 97 for(j=(g->sign - 1); j!=0; j--) { 98 if(g->n[j] == 0) { 99 (g->sign)--; 100 } 101 else { 102 break; 103 } 104 } 105 } 106 } 107 ffree(rdata); 108 return; 109} 110 111#if CRYPTKIT_ELL_PROJ_ENABLE 112/* 113 * Assumes the presence of numEllPoints items in *points, and that the 114 * x coordinate in each point is init'd to a random giant. Uses the x 115 * coords as seeds to make normalized points of the entire *points array. 116 */ 117static void makePoints(pointProjStruct *points, 118 unsigned numEllPoints, 119 curveParams *cp) 120{ 121 int i; 122 giant seed = newGiant(cp->maxDigits); 123 124 for(i=0; i<numEllPoints; i++) { 125 gtog(points[i].x, seed); 126 findPointProj(&points[i], seed, cp); 127 } 128 freeGiant(seed); 129} 130 131#endif /* CRYPTKIT_ELL_PROJ_ENABLE */ 132 133int main(int argc, char **argv) 134{ 135 int arg; 136 char *argp; 137 unsigned loopsFast = LOOPS_DEF_FAST; 138 unsigned loopsSlow = LOOPS_DEF_SLOW; 139 unsigned maxLoops; 140 unsigned depth; 141 feeRand rand; 142 giant *giants; 143 unsigned seed; 144 int i; 145 int j; 146 PLAT_TIME startTime; 147 PLAT_TIME endTime; 148 double elapsed; 149 unsigned numGiants; 150 #if CRYPTKIT_ELL_PROJ_ENABLE 151 unsigned numEllGiants; // for elliptic ops 152 unsigned numEllPoints; // for elliptic ops 153 #endif 154 curveParams *cp; 155 unsigned quick = 0; 156 unsigned minDepth = 0; 157 unsigned maxDepth = FEE_DEPTH_MAX; 158 unsigned basePrimeLen; 159 int *shiftCnt; 160 char *curveType; 161 #if CRYPTKIT_ELL_PROJ_ENABLE 162 pointProjStruct *points; 163 #endif 164 giant z = NULL; 165 giant modGiant = NULL; 166 giant recip = NULL; 167 feePubKey *keyArray = NULL; 168 giant gborrow[NUM_BORROW]; 169 170 /* just to satisfy compiler - make sure it's always called */ 171 genRandGiants(NULL, 0, 0, 0); 172 173 for(arg=1; arg<argc; arg++) { 174 argp = argv[arg]; 175 switch(argp[0]) { 176 case 'l': 177 loopsFast = atoi(&argp[2]); 178 break; 179 case 'L': 180 loopsSlow = atoi(&argp[2]); 181 break; 182 case 'q': 183 quick = 1; 184 break; 185 case 'D': 186 minDepth = maxDepth = atoi(&argp[2]); 187 break; 188 default: 189 usage(argv); 190 break; 191 } 192 } 193 194 /* 195 * Common random generator 196 */ 197 time((unsigned long *)&seed); 198 rand = feeRandAllocWithSeed(seed); 199 200 maxLoops = loopsFast; 201 if(loopsSlow > maxLoops) { 202 maxLoops = loopsSlow; 203 } 204 205 /* 206 * Alloc array of giants big enough for squaring at the largest 207 * key size, enough of them for 'loops' mulgs 208 */ 209 cp = curveParamsForDepth(FEE_DEPTH_LARGEST); 210 numGiants = maxLoops * 2; // 2 giants per loop 211 if(loopsSlow > (maxLoops / 4)) { 212 /* findPointProj needs 4 giants per loop */ 213 numGiants *= 4; 214 } 215 #if CRYPTKIT_ELL_PROJ_ENABLE 216 numEllGiants = loopsSlow * 2; 217 numEllPoints = loopsSlow * 2; 218 #endif 219 giants = fmalloc(numGiants * sizeof(giant)); 220 if(giants == NULL) { 221 printf("malloc failure\n"); 222 exit(1); 223 } 224 for(i=0; i<numGiants; i++) { 225 giants[i] = newGiant(cp->maxDigits); 226 if(giants[i] == NULL) { 227 printf("malloc failure\n"); 228 exit(1); 229 } 230 } 231 freeCurveParams(cp); 232 233 #if CRYPTKIT_ELL_PROJ_ENABLE 234 /* 235 * Projective points - two per ellLoop. The giants come from 236 * giants[]. We reserve an extra giant per point. 237 * We're assuming that numEllPoints < (4 * numGiants). 238 */ 239 points = fmalloc(numEllPoints * sizeof(pointProjStruct)); 240 if(points == NULL) { 241 printf("malloc failure\n"); 242 exit(1); 243 } 244 j=0; 245 for(i=0; i<numEllPoints; i++) { 246 points[i].x = giants[j++]; 247 points[i].y = giants[j++]; 248 points[i].z = giants[j++]; 249 j++; // skip a giant 250 } 251 #endif 252 253 /* feePubKey array */ 254 keyArray = fmalloc(sizeof(feePubKey) * loopsSlow); 255 if(keyArray == NULL) { 256 printf("malloc failure\n"); 257 exit(1); 258 } 259 260 /* 261 * Alloc an array of shiftCnt ints 262 */ 263 shiftCnt = fmalloc(maxLoops * sizeof(int)); 264 if(shiftCnt == NULL) { 265 printf("malloc failure\n"); 266 exit(1); 267 } 268 269 for(depth=minDepth; depth<=maxDepth; depth++) { 270 271 if(quick) { 272 if((depth != FEE_DEPTH_127M) && 273 (depth != FEE_DEPTH_161W)) { 274 continue; 275 } 276 } 277 278 /* 279 * Get curve params for this depth 280 */ 281 cp = curveParamsForDepth(depth); 282 if(cp == NULL) { 283 printf("malloc failure\n"); 284 exit(1); 285 } 286 switch(cp->curveType) { 287 case FCT_Montgomery: 288 curveType = "FCT_Montgomery"; 289 break; 290 case FCT_Weierstrass: 291 curveType = "FCT_Weierstrass"; 292 break; 293 case FCT_General: 294 curveType = "FCT_General"; 295 break; 296 default: 297 printf("***Unknown curveType!\n"); 298 exit(1); 299 } 300 301 switch(cp->primeType) { 302 case FPT_General: 303 printf("depth=%d; FPT_General, %s; keysize=%d;\n", 304 depth, curveType, bitlen(cp->basePrime)); 305 break; 306 case FPT_Mersenne: 307 printf("depth=%d; FPT_Mersenne, %s; q=%d\n", 308 depth, curveType, cp->q); 309 break; 310 default: 311 printf("depth=%d; FPT_FEE, %s; q=%d k=%d\n", 312 depth, curveType, cp->q, cp->k); 313 break; 314 } 315 basePrimeLen = bitlen(cp->basePrime); 316 317 /* 318 * mulg test 319 * bitlen(giant) <= bitlen(basePrime); 320 * giants[n+1] *= giants[n] 321 */ 322 #if MULG_ENABLE 323 genRandGiants(giants, numGiants, basePrimeLen, rand); 324 PLAT_GET_TIME(startTime); 325 for(i=0; i<numGiants; i+=2) { 326 mulg(giants[i], giants[i+1]); 327 } 328 PLAT_GET_TIME(endTime); 329 elapsed = PLAT_GET_NS(startTime, endTime); 330 printf(" mulg: %12.2f ns per op\n", 331 elapsed / (numGiants / 2)); 332 #endif /* MULG_ENABLE */ 333 334 /* 335 * gsquare test 336 * bitlen(giant) <= bitlen(basePrime); 337 * gsquare(giants[n]) 338 */ 339 #if GSQUARE_ENABLE 340 genRandGiants(giants, numGiants, basePrimeLen, rand); 341 PLAT_GET_TIME(startTime); 342 for(i=0; i<loopsFast; i++) { 343 gsquare(giants[i]); 344 } 345 PLAT_GET_TIME(endTime); 346 elapsed = PLAT_GET_NS(startTime, endTime); 347 printf(" gsquare: %12.2f ns per op\n", elapsed / loopsFast); 348 #endif /* GSQUARE_ENABLE */ 349 350 /* 351 * feemod test 352 * bitlen(giant) <= ((2 * bitlen(basePrime) - 2); 353 * feemod(giants[n]) 354 */ 355 #if FEEMOD_ENABLE 356 genRandGiants(giants, numGiants, (basePrimeLen * 2) - 2, 357 rand); 358 PLAT_GET_TIME(startTime); 359 for(i=0; i<loopsFast; i++) { 360 feemod(cp, giants[i]); 361 } 362 PLAT_GET_TIME(endTime); 363 elapsed = PLAT_GET_NS(startTime, endTime); 364 printf(" feemod: %12.2f ns per op\n", elapsed / loopsFast); 365 #endif /* FEEMOD_ENABLE */ 366 367 368 /* 369 * borrowGiant test 370 */ 371 #if BORROW_ENABLE 372 PLAT_GET_TIME(startTime); 373 for(i=0; i<loopsFast; i++) { 374 for(j=0; j<NUM_BORROW; j++) { 375 gborrow[j] = borrowGiant(cp->maxDigits); 376 } 377 for(j=0; j<NUM_BORROW; j++) { 378 returnGiant(gborrow[j]); 379 } 380 } 381 PLAT_GET_TIME(endTime); 382 elapsed = PLAT_GET_NS(startTime, endTime); 383 printf(" borrow/return: %12.2f ns per op\n", 384 elapsed / (loopsFast * NUM_BORROW)); 385 #endif /* BORROW_ENABLE */ 386 387 /* 388 * shiftright test 389 * bitlen(giant) <= bitlen(basePrime) 390 * 0 <= shiftCnt <= bitlen(basePrime) 391 * gshiftright(giants[i]) 392 */ 393 #if SHIFT_ENABLE 394 genRandGiants(giants, numGiants, basePrimeLen, rand); 395 for(i=0; i<loopsFast; i++) { 396 shiftCnt[i] = feeRandNextNum(rand) % basePrimeLen; 397 } 398 PLAT_GET_TIME(startTime); 399 for(i=0; i<loopsFast; i++) { 400 gshiftright(shiftCnt[i], giants[i]); 401 } 402 PLAT_GET_TIME(endTime); 403 elapsed = PLAT_GET_NS(startTime, endTime); 404 printf(" gshiftright: %12.2f ns per op\n", elapsed / loopsFast); 405 406 /* 407 * shiftleft test 408 * bitlen(giant) <= bitlen(basePrime) 409 * 1 <= shiftCnt <= bitlen(basePrime) 410 * gshiftleft(giants[i] 411 */ 412 genRandGiants(giants, numGiants, basePrimeLen, rand); 413 PLAT_GET_TIME(startTime); 414 for(i=0; i<loopsFast; i++) { 415 gshiftright(shiftCnt[i], giants[i]); 416 } 417 PLAT_GET_TIME(endTime); 418 elapsed = PLAT_GET_NS(startTime, endTime); 419 printf(" gshiftleft: %12.2f ns per op\n", elapsed / loopsFast); 420 #endif /* SHIFT_ENABLE */ 421 422 /* 423 * binvaux test 424 * bitlen(giant) <= bitlen(basePrime); 425 * binvaux(basePrime, giants[n+1]) 426 */ 427 #if BINVAUX_ENABLE 428 genRandGiants(giants, loopsSlow, basePrimeLen, rand); 429 PLAT_GET_TIME(startTime); 430 for(i=0; i<loopsSlow; i++) { 431 binvaux(cp->basePrime, giants[i]); 432 } 433 PLAT_GET_TIME(endTime); 434 elapsed = PLAT_GET_US(startTime, endTime); 435 printf(" binvaux: %12.2f us per op\n", 436 elapsed / loopsSlow); 437 #endif /* BINVAUX_ENABLE */ 438 439 /* 440 * make_recip test 441 * bitlen(giant) <= bitlen(basePrime); 442 * make_recip(giants[n], giants[n+1] 443 */ 444 #if MAKE_RECIP_ENABLE 445 genRandGiants(giants, numGiants, basePrimeLen, rand); 446 PLAT_GET_TIME(startTime); 447 for(i=0; i<loopsSlow*2; i+=2) { 448 make_recip(giants[i], giants[i+1]); 449 } 450 PLAT_GET_TIME(endTime); 451 elapsed = PLAT_GET_US(startTime, endTime); 452 printf(" make_recip: %12.2f us per op\n", 453 elapsed / loopsSlow); 454 #endif /* MAKE_RECIP_ENABLE */ 455 456 /* 457 * modg_via_recip test 458 * bitlen(giant) <= ((2 * bitlen(basePrime) - 2); 459 * bitlen(modGiant) <= bitlen(basePrime) 460 * calc recip of modGiant 461 * modg_via_recip(giants[i]) 462 */ 463 #if MODGRECIP_ENABLE 464 genRandGiants(giants, numGiants, (basePrimeLen * 2) - 2, 465 rand); 466 modGiant = borrowGiant(cp->maxDigits); 467 recip = borrowGiant(cp->maxDigits); 468 genRandGiants(&modGiant, 1, basePrimeLen, rand); 469 make_recip(modGiant, recip); 470 471 PLAT_GET_TIME(startTime); 472 for(i=0; i<loopsSlow; i++) { 473 modg_via_recip(modGiant, recip, giants[i]); 474 } 475 PLAT_GET_TIME(endTime); 476 elapsed = PLAT_GET_NS(startTime, endTime); 477 printf(" modg_via_recip: %12.2f ns per op\n", 478 elapsed / loopsSlow); 479 returnGiant(modGiant); 480 modGiant = NULL; 481 returnGiant(recip); 482 recip = NULL; 483 #endif /* MODGRECIP_ENABLE */ 484 485 /* 486 * key generate test 487 * keyArray[n] = feePubKeyAlloc(); 488 * feePubKeyInitFromPrivData(keyArray[n] ); 489 */ 490 #if KEYGEN_ENABLE 491 PLAT_GET_TIME(startTime); 492 for(i=0; i<loopsSlow; i++) { 493 keyArray[i] = feePubKeyAlloc(); 494 if(keyArray[i] == NULL) { 495 printf("malloc failure\n"); 496 exit(1); 497 } 498 /* fixme how about some better seed data */ 499 feePubKeyInitFromPrivDataDepth(keyArray[i], 500 (unsigned char *)"somePrivData", 501 12, 502 depth, 503 1); 504 } 505 PLAT_GET_TIME(endTime); 506 elapsed = PLAT_GET_US(startTime, endTime); 507 printf(" keygen: %12.2f us per op\n", 508 elapsed / loopsSlow); 509 for(i=0; i<loopsSlow; i++) { 510 feePubKeyFree(keyArray[i]); 511 } 512 #endif /* KEYGEN_ENABLE*/ 513 514 /* 515 * elliptic test 516 * bitlen(giant) <= bitlen(basePrime); 517 * {giants[n], 1} *= giants[n+1] (elliptic mult) 518 */ 519 #if ELLIPTIC_ENABLE 520 genRandGiants(giants, numGiants, basePrimeLen, rand); 521 z = borrowGiant(cp->maxDigits); 522 PLAT_GET_TIME(startTime); 523 for(i=0; i<loopsSlow; i+=2) { 524 /* superoptimized int_to_giant(1) */ 525 z->n[0] = 1; 526 z->sign = 1; 527 elliptic(giants[i], z, giants[i+1], cp); 528 } 529 PLAT_GET_TIME(endTime); 530 elapsed = PLAT_GET_US(startTime, endTime); 531 printf(" elliptic: %12.2f us per op\n", 532 elapsed / (loopsSlow / 2)); 533 #endif /* ELLIPTIC_ENABLE*/ 534 535 /* 536 * elliptic_simple test 537 * bitlen(giant) <= bitlen(basePrime); 538 * giants[n] *= giants[n+1] (elliptic mult) 539 */ 540 #if ELL_SIMPLE_ENABLE 541 genRandGiants(giants, numGiants, basePrimeLen, rand); 542 PLAT_GET_TIME(startTime); 543 for(i=0; i<loopsSlow*2; i+=2) { 544 elliptic_simple(giants[i], giants[i+1], cp); 545 } 546 PLAT_GET_TIME(endTime); 547 elapsed = PLAT_GET_US(startTime, endTime); 548 printf(" elliptic_simple: %12.2f us per op\n", 549 elapsed / loopsSlow); 550 #endif /* ELL_SIMPLE_ENABLE */ 551 552 if(cp->curveType != FCT_Weierstrass) { 553 goto loopEnd; 554 } 555 556 #if CRYPTKIT_ELL_PROJ_ENABLE 557 /* 558 * ellMulProj test 559 * bitlen(giant) <= bitlen(basePrime); 560 * point[n+1] = point[n] * giants[4n+3] 561 * 562 * note we're cooking up way more giants than we have to; 563 * we really only need the x's and k's. But what the heck. 564 */ 565 genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand); 566 makePoints(points, numEllPoints, cp); 567 PLAT_GET_TIME(startTime); 568 for(i=0; i<loopsSlow; i+=2) { 569 ellMulProj(&points[i], &points[i+1], 570 giants[4*i+3], cp); 571 } 572 PLAT_GET_TIME(endTime); 573 elapsed = PLAT_GET_US(startTime, endTime); 574 printf(" ellMulProj: %12.2f us per op\n", 575 elapsed / (loopsSlow / 2)); 576 577 /* 578 * ellMulProjSimple test 579 * bitlen(giant) <= bitlen(basePrime); 580 * point[n] *= giants[4n+3] (projective elliptic mult) 581 */ 582 genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand); 583 makePoints(points, numEllPoints, cp); 584 PLAT_GET_TIME(startTime); 585 for(i=0; i<loopsSlow; i++) { 586 ellMulProjSimple(&points[i], giants[4*i+3], cp); 587 } 588 PLAT_GET_TIME(endTime); 589 elapsed = PLAT_GET_US(startTime, endTime); 590 printf(" ellMulProjSimple: %12.2f us per op\n", 591 elapsed / loopsSlow); 592 593 /* 594 * ellAddProj test 595 * bitlen(giant) <= bitlen(basePrime); 596 * point[n] += point[n+1] (projective elliptic add) 597 */ 598 genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand); 599 makePoints(points, numEllPoints, cp); 600 PLAT_GET_TIME(startTime); 601 for(i=0; i<loopsSlow; i+=2) { 602 ellAddProj(&points[i], &points[i+1], cp); 603 } 604 PLAT_GET_TIME(endTime); 605 elapsed = PLAT_GET_NS(startTime, endTime); 606 printf(" ellAddProj: %12.2f ns per op\n", 607 elapsed / loopsSlow); 608 609 /* 610 * ellDoubleProj test 611 * bitlen(giant) <= bitlen(basePrime); 612 * ellDoubleProj(point[n]) 613 */ 614 genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand); 615 makePoints(points, numEllPoints, cp); 616 PLAT_GET_TIME(startTime); 617 for(i=0; i<loopsSlow; i++) { 618 ellDoubleProj(&points[i], cp); 619 } 620 PLAT_GET_TIME(endTime); 621 elapsed = PLAT_GET_NS(startTime, endTime); 622 printf(" ellDoubleProj: %12.2f ns per op\n", 623 elapsed / loopsSlow); 624 625 /* 626 * findPointProj test 627 * bitlen(giant) <= bitlen(basePrime); 628 * findPointProj(point[n], giants[4n+3]) 629 */ 630 genRandGiants(giants, 4 * loopsSlow, basePrimeLen, rand); 631 PLAT_GET_TIME(startTime); 632 for(i=0; i<loopsSlow; i++) { 633 findPointProj(&points[i], giants[4*i + 3], cp); 634 } 635 PLAT_GET_TIME(endTime); 636 elapsed = PLAT_GET_US(startTime, endTime); 637 printf(" findPointProj: %12.2f us per op\n", 638 elapsed / loopsSlow); 639 640 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */ 641 642loopEnd: 643 freeCurveParams(cp); 644 } 645 646 feeRandFree(rand); 647 for(i=0; i<numGiants; i++) { 648 freeGiant(giants[i]); 649 } 650 ffree(giants); 651 if(z) { 652 freeGiant(z); 653 } 654 if(recip) { 655 freeGiant(recip); 656 } 657 if(modGiant) { 658 freeGiant(modGiant); 659 } 660 return 0; 661} 662 663