-rw-r--r-- 2793 high-ctidh-20210504/tunecycles.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mont.h"
#include "steps.h"
#include "cpucycles.h"
#include "primes.h"
int comparelonglong(const void *uptr,const void *vptr)
{
long long u = *(const long long *) uptr;
long long v = *(const long long *) vptr;
if (u < v) return -1;
if (u > v) return 1;
return 0;
}
long long median(long long *x,long long xlen)
{
if (xlen <= 0) return 0;
qsort(x,xlen,sizeof(long long),comparelonglong);
if (xlen&1) return x[xlen/2];
return (x[xlen/2-1]+x[xlen/2])/2;
}
void isog_setup(proj *A,proj *P,proj *K,long long k)
{
A->x = fp_0;
A->z = fp_1;
for (;;) {
fp_random(&P->x);
fp_random(&P->z);
uintbig cof = uintbig_1;
uintbig_mul3_64(&cof, &cof, 4);
for (long long i = 0;i < primes_num;++i)
if (primes[i] != k)
uintbig_mul3_64(&cof, &cof, primes[i]);
xMUL_vartime(K,A,0,P,&cof);
if (memcmp(&K->z, &fp_0, sizeof(fp))) break;
}
uintbig cof = uintbig_1;
uintbig_mul3_64(&cof, &cof, k);
xMUL_vartime(P,A,0,K,&cof);
if (memcmp(&P->z, &fp_0, sizeof(fp))) abort();
fp_random(&P->x);
fp_random(&P->z);
}
#define TIMINGS 31
int main()
{
proj A[TIMINGS];
proj P[TIMINGS];
proj K[TIMINGS];
long long baseline[TIMINGS];
long long bench[TIMINGS];
for (long long lpos = 0;lpos < primes_num;++lpos) {
long long l = primes[lpos];
for (long long t = 0;t < TIMINGS;++t)
isog_setup(&A[t],&P[t],&K[t],l);
for (long long t = 0;t < TIMINGS;++t) {
baseline[t] = cpucycles();
xISOG_old(&A[t],&P[t],&K[t],l);
baseline[t] = cpucycles() - baseline[t];
}
long long baselinemedian = median(baseline,TIMINGS);
long long bestbs = 0;
long long bestgs = 0;
long long bestbenchmedian = -1;
for (long long bs = 0;bs <= 32;bs += 2) {
for (long long gs = 0;;++gs) {
if (!gs) if (bs) continue;
if (!bs) if (gs) break;
if (2*bs*gs > (l-1)/2) break;
if (gs > bs*2) continue;
if (bs > gs*3) continue;
steps_override(bs,gs);
for (long long t = 0;t < TIMINGS;++t)
isog_setup(&A[t],&P[t],&K[t],l);
for (long long t = 0;t < TIMINGS;++t) {
bench[t] = cpucycles();
xISOG(&A[t],&P[t],1,&K[t],l);
bench[t] = cpucycles() - bench[t];
}
/* XXX: check for stability, re-run if necessary */
long long benchmedian = median(bench,TIMINGS);
if (benchmedian > 0)
if (bestbenchmedian < 0 || benchmedian < bestbenchmedian) {
bestbs = bs;
bestgs = gs;
bestbenchmedian = benchmedian;
}
}
}
printf("%lld %lld %lld %lld %lld\n",l,bestbs,bestgs,bestbenchmedian,baselinemedian);
fflush(stdout);
}
return 0;
}