speed.c
1 /*
2 * Speed benchmark code for Falcon implementation.
3 *
4 * ==========================(LICENSE BEGIN)============================
5 *
6 * Copyright (c) 2017-2019 Falcon Project
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining
9 * a copy of this software and associated documentation files (the
10 * "Software"), to deal in the Software without restriction, including
11 * without limitation the rights to use, copy, modify, merge, publish,
12 * distribute, sublicense, and/or sell copies of the Software, and to
13 * permit persons to whom the Software is furnished to do so, subject to
14 * the following conditions:
15 *
16 * The above copyright notice and this permission notice shall be
17 * included in all copies or substantial portions of the Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
22 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
23 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
24 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
25 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 *
27 * ===========================(LICENSE END)=============================
28 *
29 * @author Thomas Pornin <thomas.pornin@nccgroup.com>
30 */
31
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <time.h>
36
37 /*
38 * This code uses only the external API.
39 */
40
41 #include "falcon.h"
42
43 static void *
44 xmalloc(size_t len)
45 {
46 void *buf;
47
48 if (len == 0) {
49 return NULL;
50 }
51 buf = malloc(len);
52 if (buf == NULL) {
53 fprintf(stderr, "memory allocation error\n");
54 exit(EXIT_FAILURE);
55 }
56 return buf;
57 }
58
59 static void
60 xfree(void *buf)
61 {
62 if (buf != NULL) {
63 free(buf);
64 }
65 }
66
67 /*
68 * Benchmark function takes an opaque context and an iteration count;
69 * it returns 0 on success, a negative error code on error.
70 */
71 typedef int (*bench_fun)(void *ctx, unsigned long num);
72
73 /*
74 * Returned value is the time per iteration in nanoseconds. If the
75 * benchmark function reports an error, 0.0 is returned.
76 */
77 static double
78 do_bench(bench_fun bf, void *ctx, double threshold)
79 {
80 unsigned long num;
81 int r;
82
83 /*
84 * Alsways do a few blank runs to "train" the caches and branch
85 * prediction.
86 */
87 r = bf(ctx, 5);
88 if (r != 0) {
89 fprintf(stderr, "ERR: %d\n", r);
90 return 0.0;
91 }
92
93 num = 1;
94 for (;;) {
95 clock_t begin, end;
96 double tt;
97
98 begin = clock();
99 r = bf(ctx, num);
100 end = clock();
101 if (r != 0) {
102 fprintf(stderr, "ERR: %d\n", r);
103 return 0.0;
104 }
105 tt = (double)(end - begin) / (double)CLOCKS_PER_SEC;
106 if (tt >= threshold) {
107 return tt * 1000000000.0 / (double)num;
108 }
109
110 /*
111 * If the function ran for less than 0.1 seconds then
112 * we simply double the iteration number; otherwise, we
113 * use the run time to try to get a "correct" number of
114 * iterations quickly.
115 */
116 if (tt < 0.1) {
117 num <<= 1;
118 } else {
119 unsigned long num2;
120
121 num2 = (unsigned long)((double)num
122 * (threshold * 1.1) / tt);
123 if (num2 <= num) {
124 num2 = num + 1;
125 }
126 num = num2;
127 }
128 }
129 }
130
131 typedef struct {
132 unsigned logn;
133 shake256_context rng;
134 uint8_t *tmp;
135 size_t tmp_len;
136 uint8_t *pk;
137 uint8_t *sk;
138 uint8_t *esk;
139 uint8_t *sig;
140 size_t sig_len;
141 uint8_t *sigct;
142 size_t sigct_len;
143 } bench_context;
144
145 static inline size_t
146 maxsz(size_t a, size_t b)
147 {
148 return a > b ? a : b;
149 }
150
151 #define CC(x) do { \
152 int ccr = (x); \
153 if (ccr != 0) { \
154 return ccr; \
155 } \
156 } while (0)
157
158 static int
159 bench_keygen(void *ctx, unsigned long num)
160 {
161 bench_context *bc;
162
163 bc = ctx;
164 while (num -- > 0) {
165 CC(falcon_keygen_make(&bc->rng, bc->logn,
166 bc->sk, FALCON_PRIVKEY_SIZE(bc->logn),
167 bc->pk, FALCON_PUBKEY_SIZE(bc->logn),
168 bc->tmp, bc->tmp_len));
169 }
170 return 0;
171 }
172
173 static int
174 bench_sign_dyn(void *ctx, unsigned long num)
175 {
176 bench_context *bc;
177
178 bc = ctx;
179 while (num -- > 0) {
180 bc->sig_len = FALCON_SIG_COMPRESSED_MAXSIZE(bc->logn);
181 CC(falcon_sign_dyn(&bc->rng,
182 bc->sig, &bc->sig_len, FALCON_SIG_COMPRESSED,
183 bc->sk, FALCON_PRIVKEY_SIZE(bc->logn),
184 "data", 4, bc->tmp, bc->tmp_len));
185 }
186 return 0;
187 }
188
189 static int
190 bench_sign_dyn_ct(void *ctx, unsigned long num)
191 {
192 bench_context *bc;
193
194 bc = ctx;
195 while (num -- > 0) {
196 bc->sigct_len = FALCON_SIG_CT_SIZE(bc->logn);
197 CC(falcon_sign_dyn(&bc->rng,
198 bc->sigct, &bc->sigct_len, FALCON_SIG_CT,
199 bc->sk, FALCON_PRIVKEY_SIZE(bc->logn),
200 "data", 4, bc->tmp, bc->tmp_len));
201 }
202 return 0;
203 }
204
205 static int
206 bench_expand_privkey(void *ctx, unsigned long num)
207 {
208 bench_context *bc;
209
210 bc = ctx;
211 while (num -- > 0) {
212 CC(falcon_expand_privkey(
213 bc->esk, FALCON_EXPANDEDKEY_SIZE(bc->logn),
214 bc->sk, FALCON_PRIVKEY_SIZE(bc->logn),
215 bc->tmp, bc->tmp_len));
216 }
217 return 0;
218 }
219
220 static int
221 bench_sign_tree(void *ctx, unsigned long num)
222 {
223 bench_context *bc;
224
225 bc = ctx;
226 while (num -- > 0) {
227 bc->sig_len = FALCON_SIG_COMPRESSED_MAXSIZE(bc->logn);
228 CC(falcon_sign_tree(&bc->rng,
229 bc->sig, &bc->sig_len, FALCON_SIG_COMPRESSED,
230 bc->esk,
231 "data", 4, bc->tmp, bc->tmp_len));
232 }
233 return 0;
234 }
235
236 static int
237 bench_sign_tree_ct(void *ctx, unsigned long num)
238 {
239 bench_context *bc;
240
241 bc = ctx;
242 while (num -- > 0) {
243 bc->sigct_len = FALCON_SIG_CT_SIZE(bc->logn);
244 CC(falcon_sign_tree(&bc->rng,
245 bc->sigct, &bc->sigct_len, FALCON_SIG_CT,
246 bc->esk,
247 "data", 4, bc->tmp, bc->tmp_len));
248 }
249 return 0;
250 }
251
252 static int
253 bench_verify(void *ctx, unsigned long num)
254 {
255 bench_context *bc;
256 size_t pk_len;
257
258 bc = ctx;
259 pk_len = FALCON_PUBKEY_SIZE(bc->logn);
260 while (num -- > 0) {
261 CC(falcon_verify(
262 bc->sig, bc->sig_len, FALCON_SIG_COMPRESSED,
263 bc->pk, pk_len,
264 "data", 4, bc->tmp, bc->tmp_len));
265 }
266 return 0;
267 }
268
269 static int
270 bench_verify_ct(void *ctx, unsigned long num)
271 {
272 bench_context *bc;
273 size_t pk_len;
274
275 bc = ctx;
276 pk_len = FALCON_PUBKEY_SIZE(bc->logn);
277 while (num -- > 0) {
278 CC(falcon_verify(
279 bc->sigct, bc->sigct_len, FALCON_SIG_CT,
280 bc->pk, pk_len,
281 "data", 4, bc->tmp, bc->tmp_len));
282 }
283 return 0;
284 }
285
286 static void
287 test_speed_falcon(unsigned logn, double threshold)
288 {
289 bench_context bc;
290 size_t len;
291
292 printf("%4u:", 1u << logn);
293 fflush(stdout);
294
295 bc.logn = logn;
296 if (shake256_init_prng_from_system(&bc.rng) != 0) {
297 fprintf(stderr, "random seeding failed\n");
298 exit(EXIT_FAILURE);
299 }
300 len = FALCON_TMPSIZE_KEYGEN(logn);
301 len = maxsz(len, FALCON_TMPSIZE_SIGNDYN(logn));
302 len = maxsz(len, FALCON_TMPSIZE_SIGNTREE(logn));
303 len = maxsz(len, FALCON_TMPSIZE_EXPANDPRIV(logn));
304 len = maxsz(len, FALCON_TMPSIZE_VERIFY(logn));
305 bc.tmp = xmalloc(len);
306 bc.tmp_len = len;
307 bc.pk = xmalloc(FALCON_PUBKEY_SIZE(logn));
308 bc.sk = xmalloc(FALCON_PRIVKEY_SIZE(logn));
309 bc.esk = xmalloc(FALCON_EXPANDEDKEY_SIZE(logn));
310 bc.sig = xmalloc(FALCON_SIG_COMPRESSED_MAXSIZE(logn));
311 bc.sig_len = 0;
312 bc.sigct = xmalloc(FALCON_SIG_CT_SIZE(logn));
313 bc.sigct_len = 0;
314
315 printf(" %8.2f",
316 do_bench(&bench_keygen, &bc, threshold) / 1000000.0);
317 fflush(stdout);
318 printf(" %8.2f",
319 do_bench(&bench_expand_privkey, &bc, threshold) / 1000.0);
320 fflush(stdout);
321 printf(" %8.2f",
322 do_bench(&bench_sign_dyn, &bc, threshold) / 1000.0);
323 fflush(stdout);
324 printf(" %8.2f",
325 do_bench(&bench_sign_dyn_ct, &bc, threshold) / 1000.0);
326 fflush(stdout);
327 printf(" %8.2f",
328 do_bench(&bench_sign_tree, &bc, threshold) / 1000.0);
329 fflush(stdout);
330 printf(" %8.2f",
331 do_bench(&bench_sign_tree_ct, &bc, threshold) / 1000.0);
332 fflush(stdout);
333 printf(" %8.2f",
334 do_bench(&bench_verify, &bc, threshold) / 1000.0);
335 fflush(stdout);
336 printf(" %8.2f",
337 do_bench(&bench_verify_ct, &bc, threshold) / 1000.0);
338 fflush(stdout);
339
340 printf("\n");
341 fflush(stdout);
342
343 xfree(bc.tmp);
344 xfree(bc.pk);
345 xfree(bc.sk);
346 xfree(bc.esk);
347 xfree(bc.sig);
348 xfree(bc.sigct);
349 }
350
351 int
352 main(int argc, char *argv[])
353 {
354 double threshold;
355
356 if (argc < 2) {
357 threshold = 2.0;
358 } else if (argc == 2) {
359 threshold = atof(argv[1]);
360 } else {
361 threshold = -1.0;
362 }
363 if (threshold <= 0.0 || threshold > 60.0) {
364 fprintf(stderr,
365 "usage: speed [ threshold ]\n"
366 "'threshold' is the minimum time for a bench run, in seconds (must be\n"
367 "positive and less than 60).\n");
368 exit(EXIT_FAILURE);
369 }
370 printf("time threshold = %.4f s\n", threshold);
371 printf("kg = keygen, ek = expand private key, sd = sign (without expanded key)\n");
372 printf("st = sign (with expanded key), vv = verify\n");
373 printf("sdc, stc, vvc: like sd, st and vv, but with constant-time hash-to-point\n");
374 printf("keygen in milliseconds, other values in microseconds\n");
375 printf("\n");
376 printf("degree kg(ms) ek(us) sd(us) sdc(us) st(us) stc(us) vv(us) vvc(us)\n");
377 fflush(stdout);
378 test_speed_falcon(8, threshold);
379 test_speed_falcon(9, threshold);
380 test_speed_falcon(10, threshold);
381 return 0;
382 }