]> git.saurik.com Git - apple/security.git/blob - OSX/libsecurity_cryptkit/ckutils/atomTime/atomTime.c
projects / apple / security.git / blob
? search:


d4eec12752553e0951a705758a7b394438f98dbb
[apple/security.git] / OSX / libsecurity_cryptkit / ckutils / atomTime / atomTime.c
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
37 static 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 */
46 static 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 */
117 static 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
133 int 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
642 loopEnd:
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
mirror of Security