--- /dev/null
+/*
+ * atomTime.c - measure performance of mulg, gsquare, feemod,
+ * gshift{left,right}, elliptic, ellMulProj
+ */
+
+#include "ckconfig.h"
+#include "ckutilsPlatform.h"
+#include "CryptKitSA.h"
+#include "ckutilities.h" /* needs private headers */
+#include "curveParams.h" /* ditto */
+#include "falloc.h" /* ditto */
+#include "elliptic.h"
+#include "ellipticProj.h"
+#include <stdlib.h>
+#include <stdio.h>
+#include <time.h>
+
+/* default loops for "fast" and "slow" ops respecitively */
+#define LOOPS_DEF_FAST 10000
+#define LOOPS_DEF_SLOW 100
+
+#define NUM_BORROW 100
+
+/* individual enables - normally all on, disable to zero in on one test */
+#define MULG_ENABLE 1
+#define GSQUARE_ENABLE 1
+#define FEEMOD_ENABLE 1
+#define BORROW_ENABLE 1
+#define SHIFT_ENABLE 1
+#define BINVAUX_ENABLE 1
+#define MAKE_RECIP_ENABLE 1
+#define MODGRECIP_ENABLE 1
+#define KEYGEN_ENABLE 1
+#define ELLIPTIC_ENABLE 1
+#define ELL_SIMPLE_ENABLE 1
+
+static void usage(char **argv)
+{
+ printf("Usage: %s [l=loops_fast] [L=loops_slow] [q(uick)] [D=depth]\n", argv[0]);
+ exit(1);
+}
+
+/*
+ * Fill numGiants with random data of length bits.
+ */
+static void genRandGiants(giant *giants,
+ unsigned numGiants,
+ unsigned bits,
+ feeRand rand)
+{
+ int i;
+ giant g;
+ unsigned char *rdata;
+ unsigned bytes = (bits + 7) / 8;
+ giantDigit mask = 0;
+ unsigned giantMsd = 0; // index of MSD
+ unsigned log2BitsPerDigit;
+ unsigned bitsPerDigit;
+
+ /* just to satisfy compiler - make sure it's always called */
+ if(giants == NULL) {
+ return;
+ }
+
+ log2BitsPerDigit = GIANT_LOG2_BITS_PER_DIGIT;
+ bitsPerDigit = GIANT_BITS_PER_DIGIT;
+
+ if((bits & 7) != 0) {
+ /*
+ * deserializeGiant() has a resolution of one byte. We
+ * need more resolution - that is, we'll be creating
+ * giants a little larger than we need, and we'll mask off
+ * some bits in the giants' m.s. digit.
+ * This assumes that data fills the giantDigits such
+ * that if bytes mod GIANT_BYTES_PER_DIGIT != 0, the
+ * empty byte(s) in the MSD are in the m.s. byte(s).
+ */
+ giantMsd = bits >> log2BitsPerDigit;
+ mask = (1 << (bits & (bitsPerDigit - 1))) - 1;
+ }
+ rdata = fmalloc(bytes);
+ for(i=0; i<numGiants; i++) {
+ g = giants[i];
+ feeRandBytes(rand, rdata, bytes);
+ deserializeGiant(rdata, g, bytes);
+ if(mask != 0) {
+ int j;
+
+ g->n[giantMsd] &= mask;
+
+ /*
+ * We've zeroed out some bits; we might have to
+ * adjust the sign of the giant as well. Note that
+ * deserializeGiant always yields positive
+ * giants....
+ */
+ for(j=(g->sign - 1); j!=0; j--) {
+ if(g->n[j] == 0) {
+ (g->sign)--;
+ }
+ else {
+ break;
+ }
+ }
+ }
+ }
+ ffree(rdata);
+ return;
+}
+
+#if CRYPTKIT_ELL_PROJ_ENABLE
+/*
+ * Assumes the presence of numEllPoints items in *points, and that the
+ * x coordinate in each point is init'd to a random giant. Uses the x
+ * coords as seeds to make normalized points of the entire *points array.
+ */
+static void makePoints(pointProjStruct *points,
+ unsigned numEllPoints,
+ curveParams *cp)
+{
+ int i;
+ giant seed = newGiant(cp->maxDigits);
+
+ for(i=0; i<numEllPoints; i++) {
+ gtog(points[i].x, seed);
+ findPointProj(&points[i], seed, cp);
+ }
+ freeGiant(seed);
+}
+
+#endif /* CRYPTKIT_ELL_PROJ_ENABLE */
+
+int main(int argc, char **argv)
+{
+ int arg;
+ char *argp;
+ unsigned loopsFast = LOOPS_DEF_FAST;
+ unsigned loopsSlow = LOOPS_DEF_SLOW;
+ unsigned maxLoops;
+ unsigned depth;
+ feeRand rand;
+ giant *giants;
+ unsigned seed;
+ int i;
+ int j;
+ PLAT_TIME startTime;
+ PLAT_TIME endTime;
+ double elapsed;
+ unsigned numGiants;
+ #if CRYPTKIT_ELL_PROJ_ENABLE
+ unsigned numEllGiants; // for elliptic ops
+ unsigned numEllPoints; // for elliptic ops
+ #endif
+ curveParams *cp;
+ unsigned quick = 0;
+ unsigned minDepth = 0;
+ unsigned maxDepth = FEE_DEPTH_MAX;
+ unsigned basePrimeLen;
+ int *shiftCnt;
+ char *curveType;
+ #if CRYPTKIT_ELL_PROJ_ENABLE
+ pointProjStruct *points;
+ #endif
+ giant z = NULL;
+ giant modGiant = NULL;
+ giant recip = NULL;
+ feePubKey *keyArray = NULL;
+ giant gborrow[NUM_BORROW];
+
+ /* just to satisfy compiler - make sure it's always called */
+ genRandGiants(NULL, 0, 0, 0);
+
+ for(arg=1; arg<argc; arg++) {
+ argp = argv[arg];
+ switch(argp[0]) {
+ case 'l':
+ loopsFast = atoi(&argp[2]);
+ break;
+ case 'L':
+ loopsSlow = atoi(&argp[2]);
+ break;
+ case 'q':
+ quick = 1;
+ break;
+ case 'D':
+ minDepth = maxDepth = atoi(&argp[2]);
+ break;
+ default:
+ usage(argv);
+ break;
+ }
+ }
+
+ /*
+ * Common random generator
+ */
+ time((unsigned long *)&seed);
+ rand = feeRandAllocWithSeed(seed);
+
+ maxLoops = loopsFast;
+ if(loopsSlow > maxLoops) {
+ maxLoops = loopsSlow;
+ }
+
+ /*
+ * Alloc array of giants big enough for squaring at the largest
+ * key size, enough of them for 'loops' mulgs
+ */
+ cp = curveParamsForDepth(FEE_DEPTH_LARGEST);
+ numGiants = maxLoops * 2; // 2 giants per loop
+ if(loopsSlow > (maxLoops / 4)) {
+ /* findPointProj needs 4 giants per loop */
+ numGiants *= 4;
+ }
+ #if CRYPTKIT_ELL_PROJ_ENABLE
+ numEllGiants = loopsSlow * 2;
+ numEllPoints = loopsSlow * 2;
+ #endif
+ giants = fmalloc(numGiants * sizeof(giant));
+ if(giants == NULL) {
+ printf("malloc failure\n");
+ exit(1);
+ }
+ for(i=0; i<numGiants; i++) {
+ giants[i] = newGiant(cp->maxDigits);
+ if(giants[i] == NULL) {
+ printf("malloc failure\n");
+ exit(1);
+ }
+ }
+ freeCurveParams(cp);
+
+ #if CRYPTKIT_ELL_PROJ_ENABLE
+ /*
+ * Projective points - two per ellLoop. The giants come from
+ * giants[]. We reserve an extra giant per point.
+ * We're assuming that numEllPoints < (4 * numGiants).
+ */
+ points = fmalloc(numEllPoints * sizeof(pointProjStruct));
+ if(points == NULL) {
+ printf("malloc failure\n");
+ exit(1);
+ }
+ j=0;
+ for(i=0; i<numEllPoints; i++) {
+ points[i].x = giants[j++];
+ points[i].y = giants[j++];
+ points[i].z = giants[j++];
+ j++; // skip a giant
+ }
+ #endif
+
+ /* feePubKey array */
+ keyArray = fmalloc(sizeof(feePubKey) * loopsSlow);
+ if(keyArray == NULL) {
+ printf("malloc failure\n");
+ exit(1);
+ }
+
+ /*
+ * Alloc an array of shiftCnt ints
+ */
+ shiftCnt = fmalloc(maxLoops * sizeof(int));
+ if(shiftCnt == NULL) {
+ printf("malloc failure\n");
+ exit(1);
+ }
+
+ for(depth=minDepth; depth<=maxDepth; depth++) {
+
+ if(quick) {
+ if((depth != FEE_DEPTH_127M) &&
+ (depth != FEE_DEPTH_161W)) {
+ continue;
+ }
+ }
+
+ /*
+ * Get curve params for this depth
+ */
+ cp = curveParamsForDepth(depth);
+ if(cp == NULL) {
+ printf("malloc failure\n");
+ exit(1);
+ }
+ switch(cp->curveType) {
+ case FCT_Montgomery:
+ curveType = "FCT_Montgomery";
+ break;
+ case FCT_Weierstrass:
+ curveType = "FCT_Weierstrass";
+ break;
+ case FCT_General:
+ curveType = "FCT_General";
+ break;
+ default:
+ printf("***Unknown curveType!\n");
+ exit(1);
+ }
+
+ switch(cp->primeType) {
+ case FPT_General:
+ printf("depth=%d; FPT_General, %s; keysize=%d;\n",
+ depth, curveType, bitlen(cp->basePrime));
+ break;
+ case FPT_Mersenne:
+ printf("depth=%d; FPT_Mersenne, %s; q=%d\n",
+ depth, curveType, cp->q);
+ break;
+ default:
+ printf("depth=%d; FPT_FEE, %s; q=%d k=%d\n",
+ depth, curveType, cp->q, cp->k);
+ break;
+ }
+ basePrimeLen = bitlen(cp->basePrime);
+
+ /*
+ * mulg test
+ * bitlen(giant) <= bitlen(basePrime);
+ * giants[n+1] *= giants[n]
+ */
+ #if MULG_ENABLE
+ genRandGiants(giants, numGiants, basePrimeLen, rand);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<numGiants; i+=2) {
+ mulg(giants[i], giants[i+1]);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_NS(startTime, endTime);
+ printf(" mulg: %12.2f ns per op\n",
+ elapsed / (numGiants / 2));
+ #endif /* MULG_ENABLE */
+
+ /*
+ * gsquare test
+ * bitlen(giant) <= bitlen(basePrime);
+ * gsquare(giants[n])
+ */
+ #if GSQUARE_ENABLE
+ genRandGiants(giants, numGiants, basePrimeLen, rand);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsFast; i++) {
+ gsquare(giants[i]);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_NS(startTime, endTime);
+ printf(" gsquare: %12.2f ns per op\n", elapsed / loopsFast);
+ #endif /* GSQUARE_ENABLE */
+
+ /*
+ * feemod test
+ * bitlen(giant) <= ((2 * bitlen(basePrime) - 2);
+ * feemod(giants[n])
+ */
+ #if FEEMOD_ENABLE
+ genRandGiants(giants, numGiants, (basePrimeLen * 2) - 2,
+ rand);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsFast; i++) {
+ feemod(cp, giants[i]);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_NS(startTime, endTime);
+ printf(" feemod: %12.2f ns per op\n", elapsed / loopsFast);
+ #endif /* FEEMOD_ENABLE */
+
+
+ /*
+ * borrowGiant test
+ */
+ #if BORROW_ENABLE
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsFast; i++) {
+ for(j=0; j<NUM_BORROW; j++) {
+ gborrow[j] = borrowGiant(cp->maxDigits);
+ }
+ for(j=0; j<NUM_BORROW; j++) {
+ returnGiant(gborrow[j]);
+ }
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_NS(startTime, endTime);
+ printf(" borrow/return: %12.2f ns per op\n",
+ elapsed / (loopsFast * NUM_BORROW));
+ #endif /* BORROW_ENABLE */
+
+ /*
+ * shiftright test
+ * bitlen(giant) <= bitlen(basePrime)
+ * 0 <= shiftCnt <= bitlen(basePrime)
+ * gshiftright(giants[i])
+ */
+ #if SHIFT_ENABLE
+ genRandGiants(giants, numGiants, basePrimeLen, rand);
+ for(i=0; i<loopsFast; i++) {
+ shiftCnt[i] = feeRandNextNum(rand) % basePrimeLen;
+ }
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsFast; i++) {
+ gshiftright(shiftCnt[i], giants[i]);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_NS(startTime, endTime);
+ printf(" gshiftright: %12.2f ns per op\n", elapsed / loopsFast);
+
+ /*
+ * shiftleft test
+ * bitlen(giant) <= bitlen(basePrime)
+ * 1 <= shiftCnt <= bitlen(basePrime)
+ * gshiftleft(giants[i]
+ */
+ genRandGiants(giants, numGiants, basePrimeLen, rand);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsFast; i++) {
+ gshiftright(shiftCnt[i], giants[i]);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_NS(startTime, endTime);
+ printf(" gshiftleft: %12.2f ns per op\n", elapsed / loopsFast);
+ #endif /* SHIFT_ENABLE */
+
+ /*
+ * binvaux test
+ * bitlen(giant) <= bitlen(basePrime);
+ * binvaux(basePrime, giants[n+1])
+ */
+ #if BINVAUX_ENABLE
+ genRandGiants(giants, loopsSlow, basePrimeLen, rand);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow; i++) {
+ binvaux(cp->basePrime, giants[i]);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_US(startTime, endTime);
+ printf(" binvaux: %12.2f us per op\n",
+ elapsed / loopsSlow);
+ #endif /* BINVAUX_ENABLE */
+
+ /*
+ * make_recip test
+ * bitlen(giant) <= bitlen(basePrime);
+ * make_recip(giants[n], giants[n+1]
+ */
+ #if MAKE_RECIP_ENABLE
+ genRandGiants(giants, numGiants, basePrimeLen, rand);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow*2; i+=2) {
+ make_recip(giants[i], giants[i+1]);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_US(startTime, endTime);
+ printf(" make_recip: %12.2f us per op\n",
+ elapsed / loopsSlow);
+ #endif /* MAKE_RECIP_ENABLE */
+
+ /*
+ * modg_via_recip test
+ * bitlen(giant) <= ((2 * bitlen(basePrime) - 2);
+ * bitlen(modGiant) <= bitlen(basePrime)
+ * calc recip of modGiant
+ * modg_via_recip(giants[i])
+ */
+ #if MODGRECIP_ENABLE
+ genRandGiants(giants, numGiants, (basePrimeLen * 2) - 2,
+ rand);
+ modGiant = borrowGiant(cp->maxDigits);
+ recip = borrowGiant(cp->maxDigits);
+ genRandGiants(&modGiant, 1, basePrimeLen, rand);
+ make_recip(modGiant, recip);
+
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow; i++) {
+ modg_via_recip(modGiant, recip, giants[i]);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_NS(startTime, endTime);
+ printf(" modg_via_recip: %12.2f ns per op\n",
+ elapsed / loopsSlow);
+ returnGiant(modGiant);
+ modGiant = NULL;
+ returnGiant(recip);
+ recip = NULL;
+ #endif /* MODGRECIP_ENABLE */
+
+ /*
+ * key generate test
+ * keyArray[n] = feePubKeyAlloc();
+ * feePubKeyInitFromPrivData(keyArray[n] );
+ */
+ #if KEYGEN_ENABLE
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow; i++) {
+ keyArray[i] = feePubKeyAlloc();
+ if(keyArray[i] == NULL) {
+ printf("malloc failure\n");
+ exit(1);
+ }
+ /* fixme how about some better seed data */
+ feePubKeyInitFromPrivDataDepth(keyArray[i],
+ (unsigned char *)"somePrivData",
+ 12,
+ depth,
+ 1);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_US(startTime, endTime);
+ printf(" keygen: %12.2f us per op\n",
+ elapsed / loopsSlow);
+ for(i=0; i<loopsSlow; i++) {
+ feePubKeyFree(keyArray[i]);
+ }
+ #endif /* KEYGEN_ENABLE*/
+
+ /*
+ * elliptic test
+ * bitlen(giant) <= bitlen(basePrime);
+ * {giants[n], 1} *= giants[n+1] (elliptic mult)
+ */
+ #if ELLIPTIC_ENABLE
+ genRandGiants(giants, numGiants, basePrimeLen, rand);
+ z = borrowGiant(cp->maxDigits);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow; i+=2) {
+ /* superoptimized int_to_giant(1) */
+ z->n[0] = 1;
+ z->sign = 1;
+ elliptic(giants[i], z, giants[i+1], cp);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_US(startTime, endTime);
+ printf(" elliptic: %12.2f us per op\n",
+ elapsed / (loopsSlow / 2));
+ #endif /* ELLIPTIC_ENABLE*/
+
+ /*
+ * elliptic_simple test
+ * bitlen(giant) <= bitlen(basePrime);
+ * giants[n] *= giants[n+1] (elliptic mult)
+ */
+ #if ELL_SIMPLE_ENABLE
+ genRandGiants(giants, numGiants, basePrimeLen, rand);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow*2; i+=2) {
+ elliptic_simple(giants[i], giants[i+1], cp);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_US(startTime, endTime);
+ printf(" elliptic_simple: %12.2f us per op\n",
+ elapsed / loopsSlow);
+ #endif /* ELL_SIMPLE_ENABLE */
+
+ if(cp->curveType != FCT_Weierstrass) {
+ goto loopEnd;
+ }
+
+ #if CRYPTKIT_ELL_PROJ_ENABLE
+ /*
+ * ellMulProj test
+ * bitlen(giant) <= bitlen(basePrime);
+ * point[n+1] = point[n] * giants[4n+3]
+ *
+ * note we're cooking up way more giants than we have to;
+ * we really only need the x's and k's. But what the heck.
+ */
+ genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand);
+ makePoints(points, numEllPoints, cp);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow; i+=2) {
+ ellMulProj(&points[i], &points[i+1],
+ giants[4*i+3], cp);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_US(startTime, endTime);
+ printf(" ellMulProj: %12.2f us per op\n",
+ elapsed / (loopsSlow / 2));
+
+ /*
+ * ellMulProjSimple test
+ * bitlen(giant) <= bitlen(basePrime);
+ * point[n] *= giants[4n+3] (projective elliptic mult)
+ */
+ genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand);
+ makePoints(points, numEllPoints, cp);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow; i++) {
+ ellMulProjSimple(&points[i], giants[4*i+3], cp);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_US(startTime, endTime);
+ printf(" ellMulProjSimple: %12.2f us per op\n",
+ elapsed / loopsSlow);
+
+ /*
+ * ellAddProj test
+ * bitlen(giant) <= bitlen(basePrime);
+ * point[n] += point[n+1] (projective elliptic add)
+ */
+ genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand);
+ makePoints(points, numEllPoints, cp);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow; i+=2) {
+ ellAddProj(&points[i], &points[i+1], cp);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_NS(startTime, endTime);
+ printf(" ellAddProj: %12.2f ns per op\n",
+ elapsed / loopsSlow);
+
+ /*
+ * ellDoubleProj test
+ * bitlen(giant) <= bitlen(basePrime);
+ * ellDoubleProj(point[n])
+ */
+ genRandGiants(giants, 4 * numEllPoints, basePrimeLen, rand);
+ makePoints(points, numEllPoints, cp);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow; i++) {
+ ellDoubleProj(&points[i], cp);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_NS(startTime, endTime);
+ printf(" ellDoubleProj: %12.2f ns per op\n",
+ elapsed / loopsSlow);
+
+ /*
+ * findPointProj test
+ * bitlen(giant) <= bitlen(basePrime);
+ * findPointProj(point[n], giants[4n+3])
+ */
+ genRandGiants(giants, 4 * loopsSlow, basePrimeLen, rand);
+ PLAT_GET_TIME(startTime);
+ for(i=0; i<loopsSlow; i++) {
+ findPointProj(&points[i], giants[4*i + 3], cp);
+ }
+ PLAT_GET_TIME(endTime);
+ elapsed = PLAT_GET_US(startTime, endTime);
+ printf(" findPointProj: %12.2f us per op\n",
+ elapsed / loopsSlow);
+
+ #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
+
+loopEnd:
+ freeCurveParams(cp);
+ }
+
+ feeRandFree(rand);
+ for(i=0; i<numGiants; i++) {
+ freeGiant(giants[i]);
+ }
+ ffree(giants);
+ if(z) {
+ freeGiant(z);
+ }
+ if(recip) {
+ freeGiant(recip);
+ }
+ if(modGiant) {
+ freeGiant(modGiant);
+ }
+ return 0;
+}
+
projects / apple / security.git / blobdiff