11 files changed, 303 insertions, 15 deletions

diff --git a/.github/workflows/perf.yml b/.github/workflows/perf.yml
new file mode 100644
index 0000000..b4a2693
--- /dev/null
+++ b/.github/workflows/perf.yml
@@ -0,0 +1,63 @@
+name: Perf
+
+on: [push, pull_request]
+
+env:
+  LLVM_CONFIG: /usr/bin/llvm-config-10
+  PS_PACKAGES: libps4000 libps5000 libps6000
+  GMP_PACKAGES: libgmp-dev libmpfr-dev libmpc-dev
+  OTHER_PACKAGES: swig gcc libpcsclite-dev llvm-10 libllvm10 llvm-10-dev
+
+jobs:
+  perf:
+    runs-on: ubuntu-20.04
+    strategy:
+      matrix:
+        python-version: [3.8, 3.9]
+        gmp: [0, 1]
+    env:
+      PYTHON: ${{ matrix.python-version }}
+      USE_GMP: ${{ matrix.gmp }}
+    steps:
+      - uses: actions/checkout@v2
+        with:
+          submodules: true
+      - uses: actions/cache@v2
+        with:
+          path: ~/.cache/pip
+          key: pip-${{ runner.os }}-${{ matrix.gmp }}-${{ matrix.python-version }}-${{ hashFiles('setup.py') }}
+          restore-keys: |
+            pip-${{ runner.os }}-${{ matrix.gmp }}-${{ matrix.python-version }}-
+            pip-${{ runner.os }}-${{ matrix.gmp }}-
+            pip-${{ runner.os }}-
+      - name: Setup Python ${{ matrix.python-version }}
+        uses: actions/setup-python@v2
+        with:
+          python-version: ${{ matrix.python-version }}
+      - name: Add picoscope repository
+        run: |
+          curl "https://labs.picotech.com/debian/dists/picoscope/Release.gpg.key" | sudo apt-key add
+          sudo echo "deb https://labs.picotech.com/debian/ picoscope main" | sudo tee /etc/apt/sources.list.d/picoscope.list
+          sudo apt-get update
+      - name: Install system dependencies
+        run: |
+          sudo apt-get install -y $PS_PACKAGES $OTHER_PACKAGES
+          if [ $USE_GMP == 1 ]; then sudo apt-get install -y $GMP_PACKAGES; fi
+      - name: Install picoscope bindings
+        run: |
+          git clone https://github.com/colinoflynn/pico-python && cd pico-python && python setup.py install && cd ..
+          git clone https://github.com/picotech/picosdk-python-wrappers && cd picosdk-python-wrappers && python setup.py install && cd ..
+      - name: Install dependencies
+        run: |
+          python -m pip install -U pip setuptools wheel
+          if [ $USE_GMP == 1 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, gmp, test, dev]"; fi
+          if [ $USE_GMP == 0 ]; then pip install -e ".[picoscope_sdk, picoscope_alt, chipwhisperer, smartcard, test, dev]"; fi
+      - name: Perf
+        run: |
+          make perf
+      - name: Archive perf results
+        uses: actions/upload-artifact@v2
+        with:
+          name: perf-results
+          path:
+            .perf
\ No newline at end of file
diff --git a/.gitignore b/.gitignore
index 65292a0..7aefd0d 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,6 +1,7 @@
 /*.trs
 
 pyecsca.egg-info
+.perf/
 .coverage
 .mypy_cache/
 /.pytest_cache/
diff --git a/Makefile b/Makefile
index c22cf87..9acd9c6 100644
--- a/Makefile
+++ b/Makefile
@@ -7,6 +7,8 @@ sca.test_sampling sca.test_target sca.test_test sca.test_trace sca.test_traceset
 
 TESTS = ${EC_TESTS} ${SCA_TESTS}
 
+PERF_SCRIPTS = test/ec/perf_mod.py test/ec/perf_formula.py test/ec/perf_mult.py
+
 test:
 	nose2 -s test -E "not slow and not disabled" -C -v ${TESTS}
 
@@ -28,6 +30,10 @@ codestyle:
 codestyle-all:
 	flake8 --ignore=E501,F405,F403,F401,E126 pyecsca test
 
+perf: ${PERF_SCRIPTS}
+	mkdir -p .perf
+	echo $^ | env DIR=".perf" xargs -n 1 python
+
 doc-coverage:
 	interrogate -vv -nmps -e pyecsca/ec/std/.github/ -f 55 pyecsca
 
@@ -35,4 +41,4 @@ docs:
 	$(MAKE) -C docs apidoc
 	$(MAKE) -C docs html
 
-.PHONY: test test-plots test-all typecheck typecheck-all codestyle codestyle-all doc-coverage docs
\ No newline at end of file
+.PHONY: test test-plots test-all typecheck typecheck-all codestyle codestyle-all perf doc-coverage docs
diff --git a/README.md b/README.md
index 429e28d..f8cd057 100644
--- a/README.md
+++ b/README.md
@@ -66,6 +66,8 @@ It also supports working with [Riscure](https://www.riscure.com) Inspector trace
  - [parameterized](https://github.com/wolever/parameterized)
  - [flake8](https://flake8.pycqa.org/)
  - [coverage](https://coverage.readthedocs.io/)
+ - [interrogate](https://interrogate.readthedocs.io/)
+ - [pyinstrument](https://github.com/joerick/pyinstrument/)
 
 ### Docs
 
@@ -78,7 +80,7 @@ It also supports working with [Riscure](https://www.riscure.com) Inspector trace
 
     MIT License
 
-    Copyright (c) 2018-2020 Jan Jancar
+    Copyright (c) 2018-2021 Jan Jancar
     
     Permission is hereby granted, free of charge, to any person obtaining a copy
     of this software and associated documentation files (the "Software"), to deal
diff --git a/docs/index.rst b/docs/index.rst
index 76c201d..4ec985c 100644
--- a/docs/index.rst
+++ b/docs/index.rst
@@ -105,6 +105,8 @@ Testing
  - mypy_
  - flake8_
  - coverage_
+ - interrogate_
+ - pyinstrument_
 
 Docs
 ----
@@ -118,7 +120,7 @@ License
 
     MIT License
 
-    Copyright (c) 2018-2020 Jan Jancar
+    Copyright (c) 2018-2021 Jan Jancar
 
     Permission is hereby granted, free of charge, to any person obtaining a copy
     of this software and associated documentation files (the "Software"), to deal
@@ -165,6 +167,8 @@ this support is very appreciated.
 .. _mypy: http://mypy-lang.org/
 .. _flake8: https://flake8.pycqa.org/
 .. _coverage: https://coverage.readthedocs.io/
+.. _interrogate: https://interrogate.readthedocs.io/
+.. _pyinstrument: https://github.com/joerick/pyinstrument/
 .. _sphinx: https://www.sphinx-doc.org/
 .. _sphinx-autodoc-typehints: https://pypi.org/project/sphinx-autodoc-typehints/
 .. _nbsphinx: https://nbsphinx.readthedocs.io/
diff --git a/pyecsca/ec/mod.py b/pyecsca/ec/mod.py
index cfe0748..cb9ef7e 100644
--- a/pyecsca/ec/mod.py
+++ b/pyecsca/ec/mod.py
@@ -8,7 +8,7 @@ dispatches to the implementation chosen by the runtime configuration of the libr
 import random
 import secrets
 from functools import wraps, lru_cache
-from typing import Type, Dict
+from typing import Type, Dict, Any
 
 from public import public
 from sympy import Expr, FF
@@ -119,6 +119,8 @@ _mod_classes: Dict[str, Type] = {}
 @public
 class Mod(object):
     """An element x of ℤₙ."""
+    x: Any
+    n: Any
 
     def __new__(cls, *args, **kwargs):
         if cls != Mod:
@@ -131,10 +133,6 @@ class Mod(object):
             selected_class = next(iter(_mod_classes.keys()))
         return _mod_classes[selected_class].__new__(_mod_classes[selected_class], *args, **kwargs)
 
-    def __init__(self, x, n):
-        self.x = x
-        self.n = n
-
     @_check
     def __add__(self, other):
         return self.__class__((self.x + other.x) % self.n, self.n)
@@ -241,7 +239,8 @@ class RawMod(Mod):
         return object.__new__(cls)
 
     def __init__(self, x: int, n: int):
-        super().__init__(x % n, n)
+        self.x = x % n
+        self.n = n
 
     def inverse(self):
         if self.x == 0:
@@ -344,7 +343,8 @@ class Undefined(Mod):
         return object.__new__(cls)
 
     def __init__(self):
-        super().__init__(None, None)
+        self.x = None
+        self.n = None
 
     def __add__(self, other):
         raise NotImplementedError
@@ -447,7 +447,8 @@ class SymbolicMod(Mod):
         return object.__new__(cls)
 
     def __init__(self, x: Expr, n: int):
-        super().__init__(x, n)
+        self.x = x
+        self.n = n
 
     @_symbolic_check
     def __add__(self, other):
@@ -539,6 +540,10 @@ class SymbolicMod(Mod):
 
 if has_gmp:
 
+    @lru_cache
+    def _is_prime(x) -> bool:
+        return gmpy2.is_prime(x)
+
     @public
     class GMPMod(Mod):
         """An element x of ℤₙ. Implemented by GMP."""
@@ -549,7 +554,8 @@ if has_gmp:
             return object.__new__(cls)
 
         def __init__(self, x: int, n: int):
-            super().__init__(gmpy2.mpz(x % n), gmpy2.mpz(n))
+            self.x = gmpy2.mpz(x % n)
+            self.n = gmpy2.mpz(n)
 
         def inverse(self):
             if self.x == 0:
@@ -565,7 +571,7 @@ if has_gmp:
 
         def is_residue(self):
             """Whether this element is a quadratic residue (only implemented for prime modulus)."""
-            if not gmpy2.is_prime(self.n):
+            if not _is_prime(self.n):
                 raise NotImplementedError
             if self.x == 0:
                 return True
@@ -579,7 +585,7 @@ if has_gmp:
 
             Uses the `Tonelli-Shanks <https://en.wikipedia.org/wiki/Tonelli–Shanks_algorithm>`_ algorithm.
             """
-            if not gmpy2.is_prime(self.n):
+            if not _is_prime(self.n):
                 raise NotImplementedError
             if self.x == 0:
                 return GMPMod(0, self.n)
diff --git a/setup.py b/setup.py
index fa90ccd..0ece313 100644
--- a/setup.py
+++ b/setup.py
@@ -48,7 +48,7 @@ setup(
         "chipwhisperer": ["chipwhisperer"],
         "smartcard": ["pyscard"],
         "gmp": ["gmpy2"],
-        "dev": ["mypy", "flake8", "interrogate"],
+        "dev": ["mypy", "flake8", "interrogate", "pyinstrument"],
         "test": ["nose2", "parameterized", "coverage"],
         "doc": ["sphinx", "sphinx-autodoc-typehints", "nbsphinx"]
     }
diff --git a/test/ec/perf_formula.py b/test/ec/perf_formula.py
new file mode 100755
index 0000000..9e651ae
--- /dev/null
+++ b/test/ec/perf_formula.py
@@ -0,0 +1,43 @@
+#!/usr/bin/env python
+import click
+
+from pyecsca.ec.mod import has_gmp
+from pyecsca.ec.params import get_params
+from pyecsca.misc.cfg import TemporaryConfig
+from utils import Profiler
+
+
+@click.command()
+@click.option("-p", "--profiler", type=click.Choice(("py", "c")), default="py")
+@click.option("-m", "--mod", type=click.Choice(("python", "gmp")), default="gmp" if has_gmp else "python")
+@click.option("-o", "--operations", type=click.INT, default=5000)
+@click.option("-d", "--directory", type=click.Path(file_okay=False, dir_okay=True), default=None, envvar="DIR")
+def main(profiler, mod, operations, directory):
+    with TemporaryConfig() as cfg:
+        cfg.ec.mod_implementation = mod
+        p256 = get_params("secg", "secp256r1", "projective")
+        coords = p256.curve.coordinate_model
+        add = coords.formulas["add-2016-rcb"]
+        dbl = coords.formulas["dbl-2016-rcb"]
+        click.echo(f"Profiling {operations} {p256.curve.prime.bit_length()}-bit doubling formula executions...")
+        one_point = p256.generator
+        with Profiler(profiler, directory, f"formula_dbl2016rcb_p256_{operations}_{mod}"):
+            for _ in range(operations):
+                one_point = dbl(p256.curve.prime, one_point, **p256.curve.parameters)[0]
+        click.echo(f"Profiling {operations} {p256.curve.prime.bit_length()}-bit addition formula executions...")
+        other_point = p256.generator
+        with Profiler(profiler, directory, f"formula_add2016rcb_p256_{operations}_{mod}"):
+            for _ in range(operations):
+                one_point = add(p256.curve.prime, one_point, other_point, **p256.curve.parameters)[0]
+        ed25519 = get_params("other", "Ed25519", "extended")
+        ecoords = ed25519.curve.coordinate_model
+        dblg = ecoords.formulas["mdbl-2008-hwcd"]
+        click.echo(f"Profiling {operations} {ed25519.curve.prime.bit_length()}-bit doubling formula executions (with assumption)...")
+        eone_point = ed25519.generator
+        with Profiler(profiler, directory, f"formula_mdbl2008hwcd_ed25519_{operations}_{mod}"):
+            for _ in range(operations):
+                dblg(ed25519.curve.prime, eone_point, **ed25519.curve.parameters)
+
+
+if __name__ == "__main__":
+    main()
diff --git a/test/ec/perf_mod.py b/test/ec/perf_mod.py
new file mode 100755
index 0000000..37cf41b
--- /dev/null
+++ b/test/ec/perf_mod.py
@@ -0,0 +1,64 @@
+#!/usr/bin/env python
+import click
+
+from pyecsca.ec.mod import Mod, has_gmp
+from pyecsca.misc.cfg import TemporaryConfig
+from utils import Profiler
+
+
+@click.command()
+@click.option("-p", "--profiler", type=click.Choice(("py", "c")), default="py")
+@click.option("-m", "--mod", type=click.Choice(("python", "gmp")), default="gmp" if has_gmp else "python")
+@click.option("-o", "--operations", type=click.INT, default=100000)
+@click.option("-d", "--directory", type=click.Path(file_okay=False, dir_okay=True), default=None, envvar="DIR")
+def main(profiler, mod, operations, directory):
+    with TemporaryConfig() as cfg:
+        cfg.ec.mod_implementation = mod
+        n = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
+        a = Mod(0x11111111111111111111111111111111, n)
+        b = Mod(0xbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb, n)
+        click.echo(f"Profiling {operations} {n.bit_length()}-bit modular inverse...")
+        with Profiler(profiler, directory, f"mod_256b_inverse_{operations}_{mod}"):
+            for _ in range(operations):
+                a.inverse()
+        click.echo(f"Profiling {operations} {n.bit_length()}-bit modular square root...")
+        with Profiler(profiler, directory, f"mod_256b_sqrt_{operations}_{mod}"):
+            for _ in range(operations):
+                a.sqrt()
+        click.echo(f"Profiling {operations} {n.bit_length()}-bit modular multiply...")
+        c = a
+        with Profiler(profiler, directory, f"mod_256b_multiply_{operations}_{mod}"):
+            for _ in range(operations):
+                c = c * b
+        click.echo(f"Profiling {operations} {n.bit_length()}-bit constant modular multiply...")
+        c = a
+        with Profiler(profiler, directory, f"mod_256b_constmultiply_{operations}_{mod}"):
+            for _ in range(operations):
+                c = c * 48006
+        click.echo(f"Profiling {operations} {n.bit_length()}-bit modular square...")
+        c = a
+        with Profiler(profiler, directory, f"mod_256b_square_{operations}_{mod}"):
+            for _ in range(operations):
+                c = c**2
+        click.echo(f"Profiling {operations} {n.bit_length()}-bit modular add...")
+        c = a
+        with Profiler(profiler, directory, f"mod_256b_add_{operations}_{mod}"):
+            for _ in range(operations):
+                c = c + b
+        click.echo(f"Profiling {operations} {n.bit_length()}-bit modular subtract...")
+        c = a
+        with Profiler(profiler, directory, f"mod_256b_subtract_{operations}_{mod}"):
+            for _ in range(operations):
+                c = c - b
+        click.echo(f"Profiling {operations} {n.bit_length()}-bit modular quadratic residue checks...")
+        with Profiler(profiler, directory, f"mod_256b_isresidue_{operations}_{mod}"):
+            for _ in range(operations):
+                a.is_residue()
+        click.echo(f"Profiling {operations} {n.bit_length()}-bit modular random...")
+        with Profiler(profiler, directory, f"mod_256b_random_{operations}_{mod}"):
+            for _ in range(operations):
+                Mod.random(n)
+
+
+if __name__ == "__main__":
+    main()
diff --git a/test/ec/perf_mult.py b/test/ec/perf_mult.py
new file mode 100755
index 0000000..2ec82b0
--- /dev/null
+++ b/test/ec/perf_mult.py
@@ -0,0 +1,41 @@
+#!/usr/bin/env python
+import click
+
+from pyecsca.ec.mod import has_gmp
+from pyecsca.ec.mult import LTRMultiplier
+from pyecsca.ec.params import get_params
+from pyecsca.misc.cfg import TemporaryConfig
+from utils import Profiler
+
+
+@click.command()
+@click.option("-p", "--profiler", type=click.Choice(("py", "c")), default="py")
+@click.option("-m", "--mod", type=click.Choice(("python", "gmp")), default="gmp" if has_gmp else "python")
+@click.option("-o", "--operations", type=click.INT, default=50)
+@click.option("-d", "--directory", type=click.Path(file_okay=False, dir_okay=True), default=None, envvar="DIR")
+def main(profiler, mod, operations, directory):
+    with TemporaryConfig() as cfg:
+        cfg.ec.mod_implementation = mod
+        p256 = get_params("secg", "secp256r1", "projective")
+        coords = p256.curve.coordinate_model
+        add = coords.formulas["add-2016-rcb"]
+        dbl = coords.formulas["dbl-2016-rcb"]
+        mult = LTRMultiplier(add, dbl)
+        click.echo(f"Profiling {operations} {p256.curve.prime.bit_length()}-bit scalar multiplication executions...")
+        one_point = p256.generator
+        with Profiler(profiler, directory, f"mult_ltr_rcb_p256_{operations}_{mod}"):
+            for _ in range(operations):
+                mult.init(p256, one_point)
+                one_point = mult.multiply(0x71a55e0c1abb3a0e069419e0f837bc195f1b9545e69fc51e53c4d48d7fea3b1a)
+        # ed25519 = get_params("other", "Ed25519", "extended")
+        # ecoords = ed25519.curve.coordinate_model
+        # dblg = ecoords.formulas["mdbl-2008-hwcd"]
+        # click.echo(f"Profiling {operations} {ed25519.curve.prime.bit_length()}-bit doubling formula executions (with assumption)...")
+        # eone_point = ed25519.generator
+        # with Profiler(profiler) as pr:
+        #     for _ in range(operations):
+        #         dblg(ed25519.curve.prime, eone_point, **ed25519.curve.parameters)
+
+
+if __name__ == "__main__":
+    main()
diff --git a/test/ec/utils.py b/test/ec/utils.py
index 67a9cc0..6429ac9 100644
--- a/test/ec/utils.py
+++ b/test/ec/utils.py
@@ -1,5 +1,12 @@
+import pstats
+import sys
+
+from pathlib import Path
+from subprocess import run, PIPE, DEVNULL
 from itertools import product
 from functools import reduce
+from pyinstrument import Profiler as PyProfiler
+from cProfile import Profile as cProfiler
 
 
 def slow(func):
@@ -10,3 +17,54 @@ def slow(func):
 def cartesian(*items):
     for cart in product(*items):
         yield reduce(lambda x, y: x + y, cart)
+
+
+class Profiler(object):
+    def __init__(self, prof_type, output_directory, benchmark_name):
+        self._prof = PyProfiler() if prof_type == "py" else cProfiler()
+        self._prof_type = prof_type
+        self._root_frame = None
+        self._state = None
+        self._output_directory = output_directory
+        self._benchmark_name = benchmark_name
+
+    def __enter__(self):
+        self._prof.__enter__()
+        self._state = "in"
+        return self
+
+    def __exit__(self, exc_type, exc_val, exc_tb):
+        self._prof.__exit__(exc_type, exc_val, exc_tb)
+        if self._prof_type == "py":
+            self._root_frame = self._prof.last_session.root_frame()
+        self._state = "out"
+        self.output()
+        self.save()
+
+    def save(self):
+        if self._state != "out":
+            raise ValueError
+        if self._output_directory is None or self._benchmark_name is None:
+            return
+        git_commit = run(["git", "rev-parse", "--short", "HEAD"], stdout=PIPE, stderr=DEVNULL).stdout.strip().decode()
+        git_dirty = run(["git", "diff", "--quiet"], stdout=DEVNULL, stderr=DEVNULL).returncode != 0
+        version = git_commit + ("-dirty" if git_dirty else "")
+        output_path = Path(self._output_directory) / (self._benchmark_name + ".csv")
+        with output_path.open("a") as f:
+            f.write(f"{version},{'.'.join(map(str, sys.version_info[:3]))},{self.get_time()}\n")
+
+    def output(self):
+        if self._state != "out":
+            raise ValueError
+        if self._prof_type == "py":
+            print(self._prof.output_text(unicode=True, color=True))
+        else:
+            self._prof.print_stats("cumtime")
+
+    def get_time(self):
+        if self._state != "out":
+            raise ValueError
+        if self._prof_type == "py":
+            return self._root_frame.time()
+        else:
+            return pstats.Stats(self._prof).total_tt