Mercurial > dropbear

comparison libtommath/demo/timing.c @ 1436:60fc6476e044

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update to libtommath v1.0
author Matt Johnston <matt@ucc.asn.au>
date Sat, 24 Jun 2017 22:37:14 +0800
parents 5ff8218bcee9
children 8bba51a55704
comparison
equal deleted inserted replaced
1435:f849a5ca2efc 1436:60fc6476e044
1 #include <tommath.h> 1 #include <tommath.h>
2 #include <time.h> 2 #include <time.h>
3 3 #include <unistd.h>
4 ulong64 _tt; 4 #include <stdint.h>
5
6 uint64_t _tt;
5 7
6 #ifdef IOWNANATHLON 8 #ifdef IOWNANATHLON
7 #include <unistd.h> 9 #include <unistd.h>
8 #define SLEEP sleep(4) 10 #define SLEEP sleep(4)
9 #else 11 #else
10 #define SLEEP 12 #define SLEEP
13 #endif
14
15 #ifdef LTM_TIMING_REAL_RAND
16 #define LTM_TIMING_RAND_SEED time(NULL)
17 #else
18 #define LTM_TIMING_RAND_SEED 23
11 #endif 19 #endif
12 20
13 21
14 void ndraw(mp_int * a, char *name) 22 void ndraw(mp_int * a, char *name)
15 { 23 {
38 return 0; 46 return 0;
39 } 47 }
40 } 48 }
41 49
42 /* RDTSC from Scott Duplichan */ 50 /* RDTSC from Scott Duplichan */
43 static ulong64 TIMFUNC(void) 51 static uint64_t TIMFUNC(void)
44 { 52 {
45 #if defined __GNUC__ 53 #if defined __GNUC__
46 #if defined(__i386__) || defined(__x86_64__) 54 #if defined(__i386__) || defined(__x86_64__)
47 unsigned long long a; 55 /* version from http://www.mcs.anl.gov/~kazutomo/rdtsc.html
48 __asm__ __volatile__("rdtsc\nmovl %%eax,%0\nmovl %%edx,4+%0\n":: 56 * the old code always got a warning issued by gcc, clang did not complain...
49 "m"(a):"%eax", "%edx"); 57 */
50 return a; 58 unsigned hi, lo;
59 __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
60 return ((uint64_t)lo)|( ((uint64_t)hi)<<32);
51 #else /* gcc-IA64 version */ 61 #else /* gcc-IA64 version */
52 unsigned long result; 62 unsigned long result;
53 __asm__ __volatile__("mov %0=ar.itc":"=r"(result)::"memory"); 63 __asm__ __volatile__("mov %0=ar.itc":"=r"(result)::"memory");
54 64
55 while (__builtin_expect((int) result == -1, 0)) 65 while (__builtin_expect((int) result == -1, 0))
76 #define DO(x) x; x; 86 #define DO(x) x; x;
77 //#define DO4(x) DO2(x); DO2(x); 87 //#define DO4(x) DO2(x); DO2(x);
78 //#define DO8(x) DO4(x); DO4(x); 88 //#define DO8(x) DO4(x); DO4(x);
79 //#define DO(x) DO8(x); DO8(x); 89 //#define DO(x) DO8(x); DO8(x);
80 90
91 #ifdef TIMING_NO_LOGS
92 #define FOPEN(a, b) NULL
93 #define FPRINTF(a,b,c,d)
94 #define FFLUSH(a)
95 #define FCLOSE(a) (void)(a)
96 #else
97 #define FOPEN(a,b) fopen(a,b)
98 #define FPRINTF(a,b,c,d) fprintf(a,b,c,d)
99 #define FFLUSH(a) fflush(a)
100 #define FCLOSE(a) fclose(a)
101 #endif
102
81 int main(void) 103 int main(void)
82 { 104 {
83 ulong64 tt, gg, CLK_PER_SEC; 105 uint64_t tt, gg, CLK_PER_SEC;
84 FILE *log, *logb, *logc, *logd; 106 FILE *log, *logb, *logc, *logd;
85 mp_int a, b, c, d, e, f; 107 mp_int a, b, c, d, e, f;
86 int n, cnt, ix, old_kara_m, old_kara_s; 108 int n, cnt, ix, old_kara_m, old_kara_s, old_toom_m, old_toom_s;
87 unsigned rr; 109 unsigned rr;
88 110
89 mp_init(&a); 111 mp_init(&a);
90 mp_init(&b); 112 mp_init(&b);
91 mp_init(&c); 113 mp_init(&c);
92 mp_init(&d); 114 mp_init(&d);
93 mp_init(&e); 115 mp_init(&e);
94 mp_init(&f); 116 mp_init(&f);
95 117
96 srand(time(NULL)); 118 srand(LTM_TIMING_RAND_SEED);
97 119
98
99 /* temp. turn off TOOM */
100 TOOM_MUL_CUTOFF = TOOM_SQR_CUTOFF = 100000;
101 120
102 CLK_PER_SEC = TIMFUNC(); 121 CLK_PER_SEC = TIMFUNC();
103 sleep(1); 122 sleep(1);
104 CLK_PER_SEC = TIMFUNC() - CLK_PER_SEC; 123 CLK_PER_SEC = TIMFUNC() - CLK_PER_SEC;
105 124
106 printf("CLK_PER_SEC == %llu\n", CLK_PER_SEC); 125 printf("CLK_PER_SEC == %llu\n", CLK_PER_SEC);
107 goto exptmod; 126 log = FOPEN("logs/add.log", "w");
108 log = fopen("logs/add.log", "w");
109 for (cnt = 8; cnt <= 128; cnt += 8) { 127 for (cnt = 8; cnt <= 128; cnt += 8) {
110 SLEEP; 128 SLEEP;
111 mp_rand(&a, cnt); 129 mp_rand(&a, cnt);
112 mp_rand(&b, cnt); 130 mp_rand(&b, cnt);
113 rr = 0; 131 rr = 0;
119 if (tt > gg) 137 if (tt > gg)
120 tt = gg; 138 tt = gg;
121 } while (++rr < 100000); 139 } while (++rr < 100000);
122 printf("Adding\t\t%4d-bit => %9llu/sec, %9llu cycles\n", 140 printf("Adding\t\t%4d-bit => %9llu/sec, %9llu cycles\n",
123 mp_count_bits(&a), CLK_PER_SEC / tt, tt); 141 mp_count_bits(&a), CLK_PER_SEC / tt, tt);
124 fprintf(log, "%d %9llu\n", cnt * DIGIT_BIT, tt); 142 FPRINTF(log, "%d %9llu\n", cnt * DIGIT_BIT, tt);
125 fflush(log); 143 FFLUSH(log);
126 } 144 }
127 fclose(log); 145 FCLOSE(log);
128 146
129 log = fopen("logs/sub.log", "w"); 147 log = FOPEN("logs/sub.log", "w");
130 for (cnt = 8; cnt <= 128; cnt += 8) { 148 for (cnt = 8; cnt <= 128; cnt += 8) {
131 SLEEP; 149 SLEEP;
132 mp_rand(&a, cnt); 150 mp_rand(&a, cnt);
133 mp_rand(&b, cnt); 151 mp_rand(&b, cnt);
134 rr = 0; 152 rr = 0;
141 tt = gg; 159 tt = gg;
142 } while (++rr < 100000); 160 } while (++rr < 100000);
143 161
144 printf("Subtracting\t\t%4d-bit => %9llu/sec, %9llu cycles\n", 162 printf("Subtracting\t\t%4d-bit => %9llu/sec, %9llu cycles\n",
145 mp_count_bits(&a), CLK_PER_SEC / tt, tt); 163 mp_count_bits(&a), CLK_PER_SEC / tt, tt);
146 fprintf(log, "%d %9llu\n", cnt * DIGIT_BIT, tt); 164 FPRINTF(log, "%d %9llu\n", cnt * DIGIT_BIT, tt);
147 fflush(log); 165 FFLUSH(log);
148 } 166 }
149 fclose(log); 167 FCLOSE(log);
150 168
151 /* do mult/square twice, first without karatsuba and second with */ 169 /* do mult/square twice, first without karatsuba and second with */
152 multtest:
153 old_kara_m = KARATSUBA_MUL_CUTOFF; 170 old_kara_m = KARATSUBA_MUL_CUTOFF;
154 old_kara_s = KARATSUBA_SQR_CUTOFF; 171 old_kara_s = KARATSUBA_SQR_CUTOFF;
155 for (ix = 0; ix < 2; ix++) { 172 /* currently toom-cook cut-off is too high to kick in, so we just use the karatsuba values */
156 printf("With%s Karatsuba\n", (ix == 0) ? "out" : ""); 173 old_toom_m = old_kara_m;
157 174 old_toom_s = old_kara_m;
158 KARATSUBA_MUL_CUTOFF = (ix == 0) ? 9999 : old_kara_m; 175 for (ix = 0; ix < 3; ix++) {
159 KARATSUBA_SQR_CUTOFF = (ix == 0) ? 9999 : old_kara_s; 176 printf("With%s Karatsuba, With%s Toom\n", (ix == 0) ? "out" : "", (ix == 1) ? "out" : "");
160 177
161 log = fopen((ix == 0) ? "logs/mult.log" : "logs/mult_kara.log", "w"); 178 KARATSUBA_MUL_CUTOFF = (ix == 1) ? old_kara_m : 9999;
179 KARATSUBA_SQR_CUTOFF = (ix == 1) ? old_kara_s : 9999;
180 TOOM_MUL_CUTOFF = (ix == 2) ? old_toom_m : 9999;
181 TOOM_SQR_CUTOFF = (ix == 2) ? old_toom_s : 9999;
182
183 log = FOPEN((ix == 0) ? "logs/mult.log" : (ix == 1) ? "logs/mult_kara.log" : "logs/mult_toom.log", "w");
162 for (cnt = 4; cnt <= 10240 / DIGIT_BIT; cnt += 2) { 184 for (cnt = 4; cnt <= 10240 / DIGIT_BIT; cnt += 2) {
163 SLEEP; 185 SLEEP;
164 mp_rand(&a, cnt); 186 mp_rand(&a, cnt);
165 mp_rand(&b, cnt); 187 mp_rand(&b, cnt);
166 rr = 0; 188 rr = 0;
172 if (tt > gg) 194 if (tt > gg)
173 tt = gg; 195 tt = gg;
174 } while (++rr < 100); 196 } while (++rr < 100);
175 printf("Multiplying\t%4d-bit => %9llu/sec, %9llu cycles\n", 197 printf("Multiplying\t%4d-bit => %9llu/sec, %9llu cycles\n",
176 mp_count_bits(&a), CLK_PER_SEC / tt, tt); 198 mp_count_bits(&a), CLK_PER_SEC / tt, tt);
177 fprintf(log, "%d %9llu\n", mp_count_bits(&a), tt); 199 FPRINTF(log, "%d %9llu\n", mp_count_bits(&a), tt);
178 fflush(log); 200 FFLUSH(log);
179 } 201 }
180 fclose(log); 202 FCLOSE(log);
181 203
182 log = fopen((ix == 0) ? "logs/sqr.log" : "logs/sqr_kara.log", "w"); 204 log = FOPEN((ix == 0) ? "logs/sqr.log" : (ix == 1) ? "logs/sqr_kara.log" : "logs/sqr_toom.log", "w");
183 for (cnt = 4; cnt <= 10240 / DIGIT_BIT; cnt += 2) { 205 for (cnt = 4; cnt <= 10240 / DIGIT_BIT; cnt += 2) {
184 SLEEP; 206 SLEEP;
185 mp_rand(&a, cnt); 207 mp_rand(&a, cnt);
186 rr = 0; 208 rr = 0;
187 tt = -1; 209 tt = -1;
192 if (tt > gg) 214 if (tt > gg)
193 tt = gg; 215 tt = gg;
194 } while (++rr < 100); 216 } while (++rr < 100);
195 printf("Squaring\t%4d-bit => %9llu/sec, %9llu cycles\n", 217 printf("Squaring\t%4d-bit => %9llu/sec, %9llu cycles\n",
196 mp_count_bits(&a), CLK_PER_SEC / tt, tt); 218 mp_count_bits(&a), CLK_PER_SEC / tt, tt);
197 fprintf(log, "%d %9llu\n", mp_count_bits(&a), tt); 219 FPRINTF(log, "%d %9llu\n", mp_count_bits(&a), tt);
198 fflush(log); 220 FFLUSH(log);
199 } 221 }
200 fclose(log); 222 FCLOSE(log);
201 223
202 } 224 }
203 exptmod:
204 225
205 { 226 {
206 char *primes[] = { 227 char *primes[] = {
207 /* 2K large moduli */ 228 /* 2K large moduli */
208 "179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586239334100047359817950870678242457666208137217", 229 "179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586239334100047359817950870678242457666208137217",
233 "436463808505957768574894870394349739623346440601945961161254440072143298152040105676491048248110146278752857839930515766167441407021501229924721335644557342265864606569000117714935185566842453630868849121480179691838399545644365571106757731317371758557990781880691336695584799313313687287468894148823761785582982549586183756806449017542622267874275103877481475534991201849912222670102069951687572917937634467778042874315463238062009202992087620963771759666448266532858079402669920025224220613419441069718482837399612644978839925207109870840278194042158748845445131729137117098529028886770063736487420613144045836803985635654192482395882603511950547826439092832800532152534003936926017612446606135655146445620623395788978726744728503058670046885876251527122350275750995227", 254 "436463808505957768574894870394349739623346440601945961161254440072143298152040105676491048248110146278752857839930515766167441407021501229924721335644557342265864606569000117714935185566842453630868849121480179691838399545644365571106757731317371758557990781880691336695584799313313687287468894148823761785582982549586183756806449017542622267874275103877481475534991201849912222670102069951687572917937634467778042874315463238062009202992087620963771759666448266532858079402669920025224220613419441069718482837399612644978839925207109870840278194042158748845445131729137117098529028886770063736487420613144045836803985635654192482395882603511950547826439092832800532152534003936926017612446606135655146445620623395788978726744728503058670046885876251527122350275750995227",
234 "11424167473351836398078306042624362277956429440521137061889702611766348760692206243140413411077394583180726863277012016602279290144126785129569474909173584789822341986742719230331946072730319555984484911716797058875905400999504305877245849119687509023232790273637466821052576859232452982061831009770786031785669030271542286603956118755585683996118896215213488875253101894663403069677745948305893849505434201763745232895780711972432011344857521691017896316861403206449421332243658855453435784006517202894181640562433575390821384210960117518650374602256601091379644034244332285065935413233557998331562749140202965844219336298970011513882564935538704289446968322281451907487362046511461221329799897350993370560697505809686438782036235372137015731304779072430260986460269894522159103008260495503005267165927542949439526272736586626709581721032189532726389643625590680105784844246152702670169304203783072275089194754889511973916207", 255 "11424167473351836398078306042624362277956429440521137061889702611766348760692206243140413411077394583180726863277012016602279290144126785129569474909173584789822341986742719230331946072730319555984484911716797058875905400999504305877245849119687509023232790273637466821052576859232452982061831009770786031785669030271542286603956118755585683996118896215213488875253101894663403069677745948305893849505434201763745232895780711972432011344857521691017896316861403206449421332243658855453435784006517202894181640562433575390821384210960117518650374602256601091379644034244332285065935413233557998331562749140202965844219336298970011513882564935538704289446968322281451907487362046511461221329799897350993370560697505809686438782036235372137015731304779072430260986460269894522159103008260495503005267165927542949439526272736586626709581721032189532726389643625590680105784844246152702670169304203783072275089194754889511973916207",
235 "1214855636816562637502584060163403830270705000634713483015101384881871978446801224798536155406895823305035467591632531067547890948695117172076954220727075688048751022421198712032848890056357845974246560748347918630050853933697792254955890439720297560693579400297062396904306270145886830719309296352765295712183040773146419022875165382778007040109957609739589875590885701126197906063620133954893216612678838507540777138437797705602453719559017633986486649523611975865005712371194067612263330335590526176087004421363598470302731349138773205901447704682181517904064735636518462452242791676541725292378925568296858010151852326316777511935037531017413910506921922450666933202278489024521263798482237150056835746454842662048692127173834433089016107854491097456725016327709663199738238442164843147132789153725513257167915555162094970853584447993125488607696008169807374736711297007473812256272245489405898470297178738029484459690836250560495461579533254473316340608217876781986188705928270735695752830825527963838355419762516246028680280988020401914551825487349990306976304093109384451438813251211051597392127491464898797406789175453067960072008590614886532333015881171367104445044718144312416815712216611576221546455968770801413440778423979", 256 "1214855636816562637502584060163403830270705000634713483015101384881871978446801224798536155406895823305035467591632531067547890948695117172076954220727075688048751022421198712032848890056357845974246560748347918630050853933697792254955890439720297560693579400297062396904306270145886830719309296352765295712183040773146419022875165382778007040109957609739589875590885701126197906063620133954893216612678838507540777138437797705602453719559017633986486649523611975865005712371194067612263330335590526176087004421363598470302731349138773205901447704682181517904064735636518462452242791676541725292378925568296858010151852326316777511935037531017413910506921922450666933202278489024521263798482237150056835746454842662048692127173834433089016107854491097456725016327709663199738238442164843147132789153725513257167915555162094970853584447993125488607696008169807374736711297007473812256272245489405898470297178738029484459690836250560495461579533254473316340608217876781986188705928270735695752830825527963838355419762516246028680280988020401914551825487349990306976304093109384451438813251211051597392127491464898797406789175453067960072008590614886532333015881171367104445044718144312416815712216611576221546455968770801413440778423979",
236 NULL 257 NULL
237 }; 258 };
238 log = fopen("logs/expt.log", "w"); 259 log = FOPEN("logs/expt.log", "w");
239 logb = fopen("logs/expt_dr.log", "w"); 260 logb = FOPEN("logs/expt_dr.log", "w");
240 logc = fopen("logs/expt_2k.log", "w"); 261 logc = FOPEN("logs/expt_2k.log", "w");
241 logd = fopen("logs/expt_2kl.log", "w"); 262 logd = FOPEN("logs/expt_2kl.log", "w");
242 for (n = 0; primes[n]; n++) { 263 for (n = 0; primes[n]; n++) {
243 SLEEP; 264 SLEEP;
244 mp_read_radix(&a, primes[n], 10); 265 mp_read_radix(&a, primes[n], 10);
245 mp_zero(&b); 266 mp_zero(&b);
246 for (rr = 0; rr < (unsigned) mp_count_bits(&a); rr++) { 267 for (rr = 0; rr < (unsigned) mp_count_bits(&a); rr++) {
269 draw(&d); 290 draw(&d);
270 exit(0); 291 exit(0);
271 } 292 }
272 printf("Exponentiating\t%4d-bit => %9llu/sec, %9llu cycles\n", 293 printf("Exponentiating\t%4d-bit => %9llu/sec, %9llu cycles\n",
273 mp_count_bits(&a), CLK_PER_SEC / tt, tt); 294 mp_count_bits(&a), CLK_PER_SEC / tt, tt);
274 fprintf(n < 4 ? logd : (n < 9) ? logc : (n < 16) ? logb : log, 295 FPRINTF(n < 4 ? logd : (n < 9) ? logc : (n < 16) ? logb : log,
275 "%d %9llu\n", mp_count_bits(&a), tt); 296 "%d %9llu\n", mp_count_bits(&a), tt);
276 } 297 }
277 } 298 }
278 fclose(log); 299 FCLOSE(log);
279 fclose(logb); 300 FCLOSE(logb);
280 fclose(logc); 301 FCLOSE(logc);
281 fclose(logd); 302 FCLOSE(logd);
282 303
283 log = fopen("logs/invmod.log", "w"); 304 log = FOPEN("logs/invmod.log", "w");
284 for (cnt = 4; cnt <= 128; cnt += 4) { 305 for (cnt = 4; cnt <= 32; cnt += 4) {
285 SLEEP; 306 SLEEP;
286 mp_rand(&a, cnt); 307 mp_rand(&a, cnt);
287 mp_rand(&b, cnt); 308 mp_rand(&b, cnt);
288 309
289 do { 310 do {
305 printf("Failed to invert\n"); 326 printf("Failed to invert\n");
306 return 0; 327 return 0;
307 } 328 }
308 printf("Inverting mod\t%4d-bit => %9llu/sec, %9llu cycles\n", 329 printf("Inverting mod\t%4d-bit => %9llu/sec, %9llu cycles\n",
309 mp_count_bits(&a), CLK_PER_SEC / tt, tt); 330 mp_count_bits(&a), CLK_PER_SEC / tt, tt);
310 fprintf(log, "%d %9llu\n", cnt * DIGIT_BIT, tt); 331 FPRINTF(log, "%d %9llu\n", cnt * DIGIT_BIT, tt);
311 } 332 }
312 fclose(log); 333 FCLOSE(log);
313 334
314 return 0; 335 return 0;
315 } 336 }
316 337
317 /* $Source: /cvs/libtom/libtommath/demo/timing.c,v $ */ 338 /* $Source$ */
318 /* $Revision: 1.2 $ */ 339 /* $Revision$ */
319 /* $Date: 2005/05/05 14:38:47 $ */ 340 /* $Date$ */