Benchmark program for ECC primitives.

4 files changed, 325 insertions, 4 deletions

diff --git a/ChangeLog b/ChangeLog
index b86b5f65..e62d748d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2013-02-18  Niels Möller  <nisse@lysator.liu.se>
+
+	* examples/Makefile.in (HOGWEED_TARGETS): Renamed, was
+	RSA_TARGETS. Added ecc-benchmark$(EXEEXT).
+	(SOURCES): Added ecc-benchmark.c.
+	(ecc-benchmark$(EXEEXT)): New target.
+
+	* examples/ecc-benchmark.c: New file, benchmarking ecc primitives.
+
 2013-02-15  Niels Möller  <nisse@lysator.liu.se>
 
 	Integrate ecc_mul_a.
diff --git a/examples/.gitignore b/examples/.gitignore
index c5a36156..edf31cf6 100644
--- a/examples/.gitignore
+++ b/examples/.gitignore
@@ -4,6 +4,7 @@
 /base16enc
 /base64dec
 /base64enc
+/ecc-benchmark
 /eratosthenes
 /nettle-benchmark
 /next-prime
diff --git a/examples/Makefile.in b/examples/Makefile.in
index 71af8d43..3754aa27 100644
--- a/examples/Makefile.in
+++ b/examples/Makefile.in
@@ -13,14 +13,17 @@ PRE_LDFLAGS = -L..
 OPENSSL_LIBFLAGS = @OPENSSL_LIBFLAGS@
 BENCH_LIBS = @BENCH_LIBS@ -lm
 
-RSA_TARGETS = rsa-keygen$(EXEEXT) rsa-sign$(EXEEXT) \
-	      rsa-verify$(EXEEXT) rsa-encrypt$(EXEEXT) rsa-decrypt$(EXEEXT)
+HOGWEED_TARGETS = rsa-keygen$(EXEEXT) rsa-sign$(EXEEXT) \
+	      rsa-verify$(EXEEXT) rsa-encrypt$(EXEEXT) rsa-decrypt$(EXEEXT) \
+	      next-prime$(EXEEXT) random-prime$(EXEEXT) ecc-benchmark$(EXEEXT)
 
 ENC_TARGETS = base16enc$(EXEEXT) base16dec$(EXEEXT) \
 	      base64enc$(EXEEXT) base64dec$(EXEEXT)
 TARGETS = nettle-benchmark$(EXEEXT) eratosthenes$(EXEEXT) \
-	  $(ENC_TARGETS) @IF_HOGWEED@ $(RSA_TARGETS) next-prime$(EXEEXT) random-prime$(EXEEXT)
-SOURCES = nettle-benchmark.c eratosthenes.c next-prime.c random-prime.c \
+	  $(ENC_TARGETS) @IF_HOGWEED@ $(HOGWEED_TARGETS)
+
+SOURCES = nettle-benchmark.c ecc-benchmark.c \
+	eratosthenes.c next-prime.c random-prime.c \
 	nettle-openssl.c \
 	io.c read_rsa_key.c \
 	rsa-encrypt.c rsa-decrypt.c rsa-keygen.c rsa-sign.c rsa-verify.c \
@@ -102,6 +105,10 @@ BENCH_OBJS = nettle-benchmark.$(OBJEXT) nettle-openssl.$(OBJEXT) \
 nettle-benchmark$(EXEEXT): $(BENCH_OBJS)
 	$(LINK) $(BENCH_OBJS) -lnettle $(BENCH_LIBS) $(OPENSSL_LIBFLAGS) -o nettle-benchmark$(EXEEXT)
 
+ecc-benchmark$(EXEEXT): ecc-benchmark.$(OBJEXT)
+	$(LINK) ecc-benchmark.$(OBJEXT) -lhogweed -lnettle $(BENCH_LIBS) $(LIBS) \
+	-o ecc-benchmark$(EXEEXT)
+
 $(TARGETS) : io.$(OBJEXT) ../libnettle.a
 
 
diff --git a/examples/ecc-benchmark.c b/examples/ecc-benchmark.c
new file mode 100644
index 00000000..6a49f369
--- /dev/null
+++ b/examples/ecc-benchmark.c
@@ -0,0 +1,304 @@
+/* ecc-benchmark.c */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+/* Development of Nettle's ECC support was funded by Internetfonden. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <errno.h>
+
+#include <time.h>
+
+#include "../ecc.h"
+#include "../ecc-internal.h"
+#include "../gmp-glue.h"
+
+#define BENCH_INTERVAL 0.1
+
+static void NORETURN PRINTF_STYLE(1,2)
+die(const char *format, ...)
+{
+  va_list args;
+  va_start(args, format);
+  vfprintf(stderr, format, args);
+  va_end(args);
+
+  exit(EXIT_FAILURE);
+}
+
+static void *
+xalloc (size_t size)
+{
+  void *p = malloc (size);
+  if (!p)
+    {
+      fprintf (stderr, "Virtual memory exhausted\n");
+      abort ();
+    }
+  return p;
+}
+
+static mp_limb_t *
+xalloc_limbs (mp_size_t size)
+{
+  return xalloc (size * sizeof(mp_limb_t));
+}
+
+inline static void
+time_start(struct timespec *start)
+{
+  if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, start) < 0)
+    die("clock_gettime failed: %s\n", strerror(errno));
+}
+
+static inline double
+time_end(struct timespec *start)
+{
+  struct timespec end;
+  if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end) < 0)
+    die("clock_gettime failed: %s\n", strerror(errno));
+
+  return end.tv_sec - start->tv_sec
+    + 1e-9 * (end.tv_nsec - start->tv_nsec);
+}
+
+/* Returns second per function call */
+static double
+time_function(void (*f)(void *arg), void *arg)
+{
+  unsigned ncalls;
+  double elapsed;
+
+  /* Warm up */
+  f(arg);
+  for (ncalls = 10 ;;)
+    {
+      unsigned i;
+      struct timespec t;
+
+      time_start(&t);
+      for (i = 0; i < ncalls; i++)
+	f(arg);
+      elapsed = time_end(&t);
+      if (elapsed > BENCH_INTERVAL)
+	break;
+      else if (elapsed < BENCH_INTERVAL / 10)
+	ncalls *= 10;
+      else
+	ncalls *= 2;
+    }
+  return elapsed / ncalls;
+}
+
+static int
+modinv_gcd (const struct ecc_curve *ecc,
+	    mp_limb_t *rp, mp_limb_t *ap, mp_limb_t *tp)
+{
+  mp_size_t size = ecc->size;
+  mp_limb_t *up = tp;
+  mp_limb_t *vp = tp + size+1;
+  mp_limb_t *gp = tp + 2*(size+1);
+  mp_limb_t *sp = tp + 3*(size+1);
+  mp_size_t gn, sn;
+
+  mpn_copyi (up, ap, size);
+  mpn_copyi (vp, ecc->p, size);
+  gn = mpn_gcdext (gp, sp, &sn, up, size, vp, size);
+  if (gn != 1 || gp[0] != 1)
+    return 0;
+  
+  if (sn < 0)
+    mpn_sub (sp, ecc->p, size, sp, -sn);
+  else if (sn < size)
+    /* Zero-pad. */
+    mpn_zero (sp + sn, size - sn);
+
+  mpn_copyi (rp, sp, size);
+  return 1;
+}
+
+struct ecc_ctx {
+  const struct ecc_curve *ecc;
+  mp_limb_t *rp;
+  mp_limb_t *ap;
+  mp_limb_t *bp;
+  mp_limb_t *tp;
+};
+
+static void
+bench_modp (void *p)
+{
+  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+  mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->size);
+  ctx->ecc->modp (ctx->ecc, ctx->rp);
+}
+
+static void
+bench_redc (void *p)
+{
+  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+  mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->size);
+  ctx->ecc->redc (ctx->ecc, ctx->rp);
+}
+
+static void
+bench_modq (void *p)
+{
+  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+  mpn_copyi (ctx->rp, ctx->ap, 2*ctx->ecc->size);
+  ctx->ecc->modq (ctx->ecc, ctx->rp);
+}
+
+static void
+bench_modinv (void *p)
+{
+  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+  mpn_copyi (ctx->rp + ctx->ecc->size, ctx->ap, ctx->ecc->size);
+  ecc_modp_inv (ctx->ecc, ctx->rp, ctx->rp + ctx->ecc->size, ctx->tp);
+}
+
+static void
+bench_modinv_gcd (void *p)
+{
+  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+  mpn_copyi (ctx->rp + ctx->ecc->size, ctx->ap, ctx->ecc->size);
+  modinv_gcd (ctx->ecc, ctx->rp, ctx->rp + ctx->ecc->size, ctx->tp);  
+}
+
+static void
+bench_dup_jj (void *p)
+{
+  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+  ecc_dup_jj (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
+}
+
+static void
+bench_add_jja (void *p)
+{
+  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+  ecc_add_jja (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
+}
+
+static void
+bench_add_jjj (void *p)
+{
+  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+  ecc_add_jja (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
+}
+
+static void
+bench_mul_g (void *p)
+{
+  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+  ecc_mul_g (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
+}
+
+static void
+bench_mul_a (void *p)
+{
+  struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+  ecc_mul_a (ctx->ecc, 1, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
+}
+
+static void
+bench_curve (const struct ecc_curve *ecc)
+{
+  struct ecc_ctx ctx;  
+  double modp, redc, modq, modinv, modinv_gcd,
+    dup_jj, add_jja, add_jjj,
+    mul_g, mul_a;
+
+  mp_limb_t mask;
+
+  ctx.ecc = ecc;
+  ctx.rp = xalloc_limbs (3*ecc->size);
+  ctx.ap = xalloc_limbs (3*ecc->size);
+  ctx.bp = xalloc_limbs (3*ecc->size);
+  ctx.tp = xalloc_limbs (ECC_MUL_A_ITCH (ecc->size));
+
+  mpn_random (ctx.ap, 3*ecc->size);
+  mpn_random (ctx.bp, 3*ecc->size);
+
+  mask = (~(mp_limb_t) 0) >> (ecc->size * GMP_NUMB_BITS - ecc->bit_size);
+  ctx.ap[ecc->size - 1] &= mask;
+  ctx.ap[2*ecc->size - 1] &= mask;
+  ctx.ap[3*ecc->size - 1] &= mask;
+  ctx.bp[ecc->size - 1] &= mask;
+  ctx.bp[2*ecc->size - 1] &= mask;
+  ctx.bp[3*ecc->size - 1] &= mask;
+
+  modp = time_function (bench_modp, &ctx);
+  redc = ecc->redc ? time_function (bench_redc, &ctx) : 0;
+
+  modq = time_function (bench_modq, &ctx);
+
+  modinv = time_function (bench_modinv, &ctx);
+  modinv_gcd = time_function (bench_modinv_gcd, &ctx);
+  dup_jj = time_function (bench_dup_jj, &ctx);
+  add_jja = time_function (bench_add_jja, &ctx);
+  add_jjj = time_function (bench_add_jjj, &ctx);
+  mul_g = time_function (bench_mul_g, &ctx);
+  mul_a = time_function (bench_mul_a, &ctx);
+
+  free (ctx.rp);
+  free (ctx.ap);
+  free (ctx.bp);
+  free (ctx.tp);
+
+  printf ("%4d %6.4f %6.4f %6.4f %6.2f %6.3f %6.3f %6.3f %6.3f %6.1f %6.1f\n",
+	  ecc->bit_size, 1e6 * modp, 1e6 * redc, 1e6 * modq,
+	  1e6 * modinv, 1e6 * modinv_gcd,
+	  1e6 * dup_jj, 1e6 * add_jja, 1e6 * add_jjj,
+	  1e6 * mul_g, 1e6 * mul_a);
+}
+
+const struct ecc_curve * const curves[] = {
+  &nettle_secp_192r1,
+  &nettle_secp_224r1,
+  &nettle_secp_256r1,
+  &nettle_secp_384r1,
+  &nettle_secp_521r1,
+};
+
+#define numberof(x)  (sizeof (x) / sizeof ((x)[0]))
+
+int
+main (int argc UNUSED, char **argv UNUSED)
+{
+  unsigned i;
+
+  printf ("%4s %6s %6s %6s %6s %6s %6s %6s %6s %6s %6s (us)\n",
+	  "size", "modp", "redc", "modq", "modinv", "mi_gcd",
+	  "dup_jj", "ad_jja", "ad_jjj",
+	  "mul_g", "mul_a");
+  for (i = 0; i < numberof (curves); i++)
+    bench_curve (curves[i]);
+
+  return EXIT_SUCCESS;
+}