examples/ecc-benchmark.c

   1 /* ecc-benchmark.c */
   2
   3 /* nettle, low-level cryptographics library
   4  *
   5  * Copyright (C) 2013 Niels Möller
   6  *
   7  * The nettle library is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU Lesser General Public License as published by
   9  * the Free Software Foundation; either version 2.1 of the License, or (at your
  10  * option) any later version.
  11  *
  12  * The nettle library is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15  * License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public License
  18  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  20  * MA 02111-1301, USA.
  21  */
  22
  23 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  24
  25 #if HAVE_CONFIG_H
  26 # include "config.h"
  27 #endif
  28
  29 #include <stdarg.h>
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 #include <errno.h>
  35
  36 #include <time.h>
  37
  38 #include "timing.h"
  39
  40 #include "../ecc.h"
  41 #include "../ecc-internal.h"
  42 #include "../gmp-glue.h"
  43
  44 #define BENCH_INTERVAL 0.1
  45
  46 static void NORETURN PRINTF_STYLE(1,2)
  47 die(const char *format, ...)
  48 {
  49   va_list args;
  50   va_start(args, format);
  51   vfprintf(stderr, format, args);
  52   va_end(args);
  53
  54   exit(EXIT_FAILURE);
  55 }
  56
  57 static void *
  58 xalloc (size_t size)
  59 {
  60   void *p = malloc (size);
  61   if (!p)
  62     {
  63       fprintf (stderr, "Virtual memory exhausted\n");
  64       abort ();
  65     }
  66   return p;
  67 }
  68
  69 static mp_limb_t *
  70 xalloc_limbs (mp_size_t size)
  71 {
  72   return xalloc (size * sizeof(mp_limb_t));
  73 }
  74
  75 /* Returns second per function call */
  76 static double
  77 time_function(void (*f)(void *arg), void *arg)
  78 {
  79   unsigned ncalls;
  80   double elapsed;
  81
  82   /* Warm up */
  83   f(arg);
  84   for (ncalls = 10 ;;)
  85     {
  86       unsigned i;
  87
  88       time_start();
  89       for (i = 0; i < ncalls; i++)
  90         f(arg);
  91       elapsed = time_end();
  92       if (elapsed > BENCH_INTERVAL)
  93         break;
  94       else if (elapsed < BENCH_INTERVAL / 10)
  95         ncalls *= 10;
  96       else
  97         ncalls *= 2;
  98     }
  99   return elapsed / ncalls;
 100 }
 101
 102 static int
 103 modinv_gcd (const struct ecc_curve *ecc,
 104             mp_limb_t *rp, mp_limb_t *ap, mp_limb_t *tp)
 105 {
 106   mp_size_t size = ecc->size;
 107   mp_limb_t *up = tp;
 108   mp_limb_t *vp = tp + size+1;
 109   mp_limb_t *gp = tp + 2*(size+1);
 110   mp_limb_t *sp = tp + 3*(size+1);
 111   mp_size_t gn, sn;
 112
 113   mpn_copyi (up, ap, size);
 114   mpn_copyi (vp, ecc->p, size);
 115   gn = mpn_gcdext (gp, sp, &sn, up, size, vp, size);
 116   if (gn != 1 || gp[0] != 1)
 117     return 0;
 118
 119   if (sn < 0)
 120     mpn_sub (sp, ecc->p, size, sp, -sn);
 121   else if (sn < size)
 122     /* Zero-pad. */
 123     mpn_zero (sp + sn, size - sn);
 124
 125   mpn_copyi (rp, sp, size);
 126   return 1;
 127 }
 128
 129 struct ecc_ctx {
 130   const struct ecc_curve *ecc;
 131   mp_limb_t *rp;
 132   mp_limb_t *ap;
 133   mp_limb_t *bp;
 134   mp_limb_t *tp;
 135 };
 136
 137 static void
 138 bench_modp (void *p)
 139 {
 140   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 141   mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->size);
 142   ctx->ecc->modp (ctx->ecc, ctx->rp);
 143 }
 144
 145 static void
 146 bench_redc (void *p)
 147 {
 148   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 149   mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->size);
 150   ctx->ecc->redc (ctx->ecc, ctx->rp);
 151 }
 152
 153 static void
 154 bench_modq (void *p)
 155 {
 156   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 157   mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->size);
 158   ctx->ecc->modq (ctx->ecc, ctx->rp);
 159 }
 160
 161 static void
 162 bench_modinv (void *p)
 163 {
 164   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 165   mpn_copyi (ctx->rp + ctx->ecc->size, ctx->ap, ctx->ecc->size);
 166   ecc_modp_inv (ctx->ecc, ctx->rp, ctx->rp + ctx->ecc->size, ctx->tp);
 167 }
 168
 169 static void
 170 bench_modinv_gcd (void *p)
 171 {
 172   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 173   mpn_copyi (ctx->rp + ctx->ecc->size, ctx->ap, ctx->ecc->size);
 174   modinv_gcd (ctx->ecc, ctx->rp, ctx->rp + ctx->ecc->size, ctx->tp);
 175 }
 176
 177 static void
 178 bench_dup_jj (void *p)
 179 {
 180   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 181   ecc_dup_jj (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
 182 }
 183
 184 static void
 185 bench_add_jja (void *p)
 186 {
 187   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 188   ecc_add_jja (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
 189 }
 190
 191 static void
 192 bench_add_jjj (void *p)
 193 {
 194   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 195   ecc_add_jjj (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
 196 }
 197
 198 static void
 199 bench_mul_g (void *p)
 200 {
 201   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 202   ecc_mul_g (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
 203 }
 204
 205 static void
 206 bench_mul_a (void *p)
 207 {
 208   struct ecc_ctx *ctx = (struct ecc_ctx *) p;
 209   ecc_mul_a (ctx->ecc, 1, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
 210 }
 211
 212 static void
 213 bench_curve (const struct ecc_curve *ecc)
 214 {
 215   struct ecc_ctx ctx;
 216   double modp, redc, modq, modinv, modinv_gcd,
 217     dup_jj, add_jja, add_jjj,
 218     mul_g, mul_a;
 219
 220   mp_limb_t mask;
 221
 222   ctx.ecc = ecc;
 223   ctx.rp = xalloc_limbs (3*ecc->size);
 224   ctx.ap = xalloc_limbs (3*ecc->size);
 225   ctx.bp = xalloc_limbs (3*ecc->size);
 226   ctx.tp = xalloc_limbs (ECC_MUL_A_ITCH (ecc->size));
 227
 228   mpn_random (ctx.ap, 3*ecc->size);
 229   mpn_random (ctx.bp, 3*ecc->size);
 230
 231   mask = (~(mp_limb_t) 0) >> (ecc->size * GMP_NUMB_BITS - ecc->bit_size);
 232   ctx.ap[ecc->size - 1] &= mask;
 233   ctx.ap[2*ecc->size - 1] &= mask;
 234   ctx.ap[3*ecc->size - 1] &= mask;
 235   ctx.bp[ecc->size - 1] &= mask;
 236   ctx.bp[2*ecc->size - 1] &= mask;
 237   ctx.bp[3*ecc->size - 1] &= mask;
 238
 239   modp = time_function (bench_modp, &ctx);
 240   redc = ecc->redc ? time_function (bench_redc, &ctx) : 0;
 241
 242   modq = time_function (bench_modq, &ctx);
 243
 244   modinv = time_function (bench_modinv, &ctx);
 245   modinv_gcd = time_function (bench_modinv_gcd, &ctx);
 246   dup_jj = time_function (bench_dup_jj, &ctx);
 247   add_jja = time_function (bench_add_jja, &ctx);
 248   add_jjj = time_function (bench_add_jjj, &ctx);
 249   mul_g = time_function (bench_mul_g, &ctx);
 250   mul_a = time_function (bench_mul_a, &ctx);
 251
 252   free (ctx.rp);
 253   free (ctx.ap);
 254   free (ctx.bp);
 255   free (ctx.tp);
 256
 257   printf ("%4d %6.4f %6.4f %6.4f %6.2f %6.3f %6.3f %6.3f %6.3f %6.1f %6.1f\n",
 258           ecc->bit_size, 1e6 * modp, 1e6 * redc, 1e6 * modq,
 259           1e6 * modinv, 1e6 * modinv_gcd,
 260           1e6 * dup_jj, 1e6 * add_jja, 1e6 * add_jjj,
 261           1e6 * mul_g, 1e6 * mul_a);
 262 }
 263
 264 const struct ecc_curve * const curves[] = {
 265   &nettle_secp_192r1,
 266   &nettle_secp_224r1,
 267   &nettle_secp_256r1,
 268   &nettle_secp_384r1,
 269   &nettle_secp_521r1,
 270 };
 271
 272 #define numberof(x)  (sizeof (x) / sizeof ((x)[0]))
 273
 274 int
 275 main (int argc UNUSED, char **argv UNUSED)
 276 {
 277   unsigned i;
 278
 279   time_init();
 280   printf ("%4s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s (us)\n",
 281           "size", "modp", "redc", "modq", "modinv", "mi_gcd",
 282           "dup_jj", "ad_jja", "ad_jjj",
 283           "mul_g", "mul_a");
 284   for (i = 0; i < numberof (curves); i++)
 285     bench_curve (curves[i]);
 286
 287   return EXIT_SUCCESS;
 288 }