Add fliparoos

4 files changed, 704 insertions, 0 deletions

diff --git a/pyecsca/ec/formula_gen/__init__.py b/pyecsca/ec/formula_gen/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/pyecsca/ec/formula_gen/__init__.py
diff --git a/pyecsca/ec/formula_gen/fliparoo.py b/pyecsca/ec/formula_gen/fliparoo.py
new file mode 100644
index 0000000..1a737c8
--- /dev/null
+++ b/pyecsca/ec/formula_gen/fliparoo.py
@@ -0,0 +1,250 @@
+from pyecsca.ec.op import CodeOp
+from typing import Dict, Set
+from ast import parse
+from pyecsca.ec.op import OpType
+from pyecsca.ec.formula_gen.formula_graph import *
+
+
+def greedy_fliparoo(formula, metric):
+    original_state = metric(formula)
+    before_fliparoo = deepcopy(formula)
+    counter = 0
+    while True:
+        before_fliparoo_state = metric(before_fliparoo)
+        max_fliparood = before_fliparoo
+        max_fliparood_state = before_fliparoo_state
+        for fliparood in generate_fliparood_formulas(before_fliparoo):
+            after_fliparoo_state = metric(fliparood)
+            if after_fliparoo_state > max_fliparood_state:
+                max_fliparood = fliparood
+                max_fliparood_state = after_fliparoo_state
+        if max_fliparood_state <= before_fliparoo_state:
+            break
+        counter += 1
+        before_fliparoo = max_fliparood
+    return counter, before_fliparoo, metric(before_fliparoo)
+
+
+def brute_force_fliparoo(formula, metric, depth):
+    found = recursive_fliparoo(formula, depth)
+    measured = [(num_f, flip_f, metric(flip_f)) for num_f, flip_f in found]
+    measured = list(filter(lambda x: x[0] > 0, measured))
+    best_found = max(measured, key=lambda x: x[2])
+    if best_found[2] == metric(formula):
+        return None
+    return best_found
+
+
+def recursive_fliparoo(formula, depth=3):
+    all_fliparoos = [(0, formula)]
+    counter = 0
+    while depth > counter:
+        counter += 1
+        flips = []
+        for _, fliped_formula in all_fliparoos:
+            for fliparood in generate_fliparood_formulas(fliped_formula):
+                flips.append((counter, fliparood))
+        all_fliparoos.extend(flips)
+    return all_fliparoos
+
+
+def generate_fliparood_formulas(formula):
+    Gr = EFDFormulaGraph()
+    Gr.construct_graph(formula)
+    chains = find_fliparoo_chains(Gr)
+    for chain in generate_subchains(chains):
+        if chain[0].is_mul:
+            yield make_fliparoo(Gr, chain, 0).to_EFDFormula()
+            yield make_fliparoo(Gr, chain, 1).to_EFDFormula()
+        if chain[0].is_add or chain[0].is_sub:
+            try:
+                yield make_fliparoo_sub(Gr, chain, 0).to_EFDFormula()
+            except BadFliparoo:
+                pass
+            try:
+                yield make_fliparoo_sub(Gr, chain, 1).to_EFDFormula()
+            except BadFliparoo:
+                pass
+
+
+def find_fliparoo_chains(graph: EFDFormulaGraph) -> Set[Tuple[Node]]:
+
+    # find largest operation chain
+    fliparoos = set()
+    for ilong_path in graph.find_all_paths():
+        long_path = ilong_path[1:]  # get rid of the input variables
+        chain = largest_fliparoo_chain(long_path)
+        if chain:
+            fliparoos.add(chain)
+
+    # remove duplicities and chains in inclusion
+    fliparoos = sorted(fliparoos, key=len, reverse=True)
+    longest_fliparoos = set()
+    for fliparoo in fliparoos:
+        if not is_subfliparoo(fliparoo, longest_fliparoos):
+            longest_fliparoos.add(fliparoo)
+    return longest_fliparoos
+
+
+def generate_subchains(chains):
+    for chain in chains:
+        l = len(chain)
+        for i in range(l):
+            for j in range(i + 2, l + 1):
+                yield chain[i:j]
+
+
+def is_subfliparoo(fliparoo: Tuple[Node], longest_fliparoos: Set[Tuple[Node]]) -> bool:
+    for other_fliparoo in longest_fliparoos:
+        l1, l2 = len(fliparoo), len(other_fliparoo)
+        for i in range(l2 - l1):
+            if other_fliparoo[i : i + l1] == fliparoo:
+                return True
+    return False
+
+
+def largest_fliparoo_chain(chain: List[Node]) -> Tuple[Node]:
+    for i in range(len(chain) - 1):
+        for j in range(len(chain) - 1, i, -1):
+            subchain = chain[i : j + 1]
+            if is_fliparoo_chain(subchain):
+                return tuple(subchain)
+    return ()
+
+
+def is_fliparoo_chain(nodes: List[Node]) -> bool:
+    for i, node in enumerate(nodes[:-1]):
+        if node.outgoing_nodes != [nodes[i + 1]]:
+            return False
+        if node.output_node:
+            return False
+    operations = set(node.op.operator for node in nodes)
+    if operations == set([OpType.Mult]):
+        return True
+    if operations.issubset(set([OpType.Add, OpType.Sub])):
+        return True
+    return False
+
+
+def make_fliparoo(
+    graph: EFDFormulaGraph, chain: List[Node], side: bool
+) -> EFDFormulaGraph:
+    i0, i1, i1par = (
+        graph.node_index(chain[0]),
+        graph.node_index(chain[-1]),
+        graph.node_index(chain[-2]),
+    )
+    graph = deepcopy(graph)
+    node0, node1, node1par = graph.nodes[i0], graph.nodes[i1], graph.nodes[i1par]
+
+    node0par = node0.incoming_nodes[side]
+    node1par2_side = 1 - node1.incoming_nodes.index(node1par)
+    node1par = node1.incoming_nodes[node1par2_side]
+
+    node0.op = opcode_fliparoo(node0.op, node0par.result, node1par.result, side=side)
+    node1.op = opcode_fliparoo(
+        node1.op, node1par.result, node0par.result, side=node1par2_side
+    )
+
+    node0par.outgoing_nodes.remove(node0)
+    node1par.outgoing_nodes.remove(node1)
+    node0par.outgoing_nodes.append(node1)
+    node1par.outgoing_nodes.append(node0)
+    node0.incoming_nodes[side] = node1par
+    node1.incoming_nodes[node1par2_side] = node0par
+
+    graph.reorder()
+    # print(node0.result,node1.result)
+    return graph
+
+
+class BadFliparoo(Exception):
+    pass
+
+
+def make_fliparoo_sub(
+    graph: EFDFormulaGraph, chain: List[Node], side: bool
+) -> EFDFormulaGraph:
+    i0, i1, i1par = (
+        graph.node_index(chain[0]),
+        graph.node_index(chain[-1]),
+        graph.node_index(chain[-2]),
+    )
+    graph = deepcopy(graph)
+    node0, node1, node1par = graph.nodes[i0], graph.nodes[i1], graph.nodes[i1par]
+
+    node0par = node0.incoming_nodes[side]
+    node1par2_side = 1 - node1.incoming_nodes.index(node1par)
+    node1par2 = node1.incoming_nodes[node1par2_side]
+
+    if side == 0 and node1par2_side == 0:
+        sign_diff = sum(1 for node in chain[1:] if node.is_sub) % 2
+        if sign_diff:
+            raise BadFliparoo
+        node0.op = opcode_fliparoo(
+            node0.op, node0par.result, node1par2.result, side=side
+        )
+        node1.op = opcode_fliparoo(
+            node1.op, node1par2.result, node0par.result, side=node1par2_side
+        )
+    elif side == 1 and node1par2_side == 1:
+        sign_diff = sum(1 for node in chain if node.is_sub) % 2
+        node0.op = opcode_fliparoo(
+            node0.op,
+            node0par.result,
+            node1par2.result,
+            side=side,
+            switch_sign=sign_diff,
+        )
+        node1.op = opcode_fliparoo(
+            node1.op,
+            node1par2.result,
+            node0par.result,
+            side=node1par2_side,
+            switch_sign=sign_diff,
+        )
+    elif side == 0 and node1par2_side == 1:
+        sign_diff = sum(1 for node in chain[1:] if node.is_sub) % 2
+        if sign_diff:
+            raise BadFliparoo
+        node0.op = opcode_fliparoo(
+            node0.op, node0par.result, node1par2.result, side=side
+        )
+        node1.op = opcode_fliparoo(
+            node1.op, node1par2.result, node0par.result, side=node1par2_side
+        )
+    elif side == 1 and node1par2_side == 0:
+        sign_diff = sum(1 for node in chain if node.is_sub) % 2
+        if sign_diff:
+            raise BadFliparoo
+        node0.op = opcode_fliparoo(
+            node0.op, node0par.result, node1par2.result, side=side
+        )
+        node1.op = opcode_fliparoo(
+            node1.op, node1par2.result, node0par.result, side=node1par2_side
+        )
+
+    node0par.outgoing_nodes.remove(node0)
+    node1par2.outgoing_nodes.remove(node1)
+    node0par.outgoing_nodes.append(node1)
+    node1par2.outgoing_nodes.append(node0)
+    node0.incoming_nodes[side] = node1par2
+    node1.incoming_nodes[node1par2_side] = node0par
+
+    graph.reorder()
+    # print(node0.result,node1.result)
+    return graph
+
+
+def opcode_fliparoo(op, orig_var, new_var, side=int, switch_sign=False):
+    result, left, operator, right = op.result, op.left, op.operator.op_str, op.right
+    if side == 0:
+        left = new_var
+    if side == 1:
+        right = new_var
+    if switch_sign and op.operator == OpType.Add:
+        operator = OpType.Sub.op_str
+    if switch_sign and op.operator == OpType.Sub:
+        operator = OpType.Add.op_str
+    opstr = f"{result} = {left if left is not None else ''}{operator}{right if right is not None else ''}"
+    return CodeOp(parse(opstr.replace("^", "**")))
diff --git a/pyecsca/ec/formula_gen/formula_graph.py b/pyecsca/ec/formula_gen/formula_graph.py
new file mode 100644
index 0000000..402e77f
--- /dev/null
+++ b/pyecsca/ec/formula_gen/formula_graph.py
@@ -0,0 +1,310 @@
+from pyecsca.ec.formula import EFDFormula
+from pyecsca.ec.op import CodeOp, OpType
+import matplotlib.pyplot as plt
+import networkx as nx
+import functools
+from ast import parse
+from typing import Dict, List, Tuple, Set
+from copy import deepcopy
+from abc import ABC, abstractmethod
+
+
+class Node(ABC):
+    def __init__(self):
+        self.incoming_nodes = []
+        self.outgoing_nodes = []
+        self.output_node = False
+        self.input_node = False
+
+    @abstractmethod
+    def label(self) -> str:
+        pass
+
+    @abstractmethod
+    def result(self) -> str:
+        pass
+
+    @abstractmethod
+    def __repr__(self) -> str:
+        pass
+
+
+class ConstantNode(Node):
+
+    color = "#b41f44"
+
+    def __init__(self, i: int):
+        super().__init__()
+        self.value = i
+
+    @property
+    def label(self) -> str:
+        return str(self.value)
+
+    @property
+    def result(self) -> str:
+        return self.value
+
+    def __repr__(self) -> str:
+        return f"Node({self.name})"
+
+
+class CodeOpNode(Node):
+
+    color = "#1f78b4"
+
+    def __init__(self, op: CodeOp):
+        super().__init__()
+        self.op = op
+        assert self.op.operator in [
+            OpType.Sub,
+            OpType.Add,
+            OpType.Id,
+            OpType.Sqr,
+            OpType.Mult,
+            OpType.Div,
+            OpType.Pow,
+            OpType.Inv,
+            OpType.Neg,
+        ], self.op.operator
+
+    @property
+    def label(self) -> str:
+        return f"{self.op.result}:{self.op.operator.op_str}"
+
+    @property
+    def result(self) -> str:
+        return str(self.op.result)
+
+    @property
+    def optype(self) -> OpType:
+        return self.op.operator
+
+    @property
+    def is_sub(self) -> bool:
+        return self.optype == OpType.Sub
+
+    @property
+    def is_mul(self) -> bool:
+        return self.optype == OpType.Mult
+
+    @property
+    def is_add(self) -> bool:
+        return self.optype == OpType.Add
+
+    @property
+    def is_id(self) -> bool:
+        return self.optype == OpType.Id
+
+    @property
+    def is_sqr(self) -> bool:
+        return self.optype == OpType.Sqr
+
+    @property
+    def is_pow(self) -> bool:
+        return self.optype == OpType.Pow
+
+    @property
+    def is_inv(self) -> bool:
+        return self.optype == OpType.Inv
+
+    @property
+    def is_div(self) -> bool:
+        return self.optype == OpType.Div
+
+    @property
+    def is_neg(self) -> bool:
+        return self.optype == OpType.Neg
+
+    def __repr__(self) -> str:
+        return f"Node({self.op})"
+
+
+class InputNode(Node):
+
+    color = "#b41f44"
+
+    def __init__(self, input: str):
+        super().__init__()
+        self.input = input
+        self.input_node = True
+
+    @property
+    def label(self) -> str:
+        return self.input
+
+    @property
+    def result(self) -> str:
+        return self.input
+
+    def __repr__(self) -> str:
+        return f"Node({self.input})"
+
+
+def formula_input_variables(formula: EFDFormula) -> List[str]:
+    return (
+        list(formula.inputs)
+        + formula.parameters
+        + formula.coordinate_model.curve_model.parameter_names
+    )
+
+
+class EFDFormulaGraph:
+    def __init__(self):
+        self.nodes: List = None
+        self.input_nodes: Dict = None
+        self.output_names: Set = None
+        self.roots: List = None
+
+    def construct_graph(self, formula: EFDFormula):
+        self._formula = formula  # TODO remove, its here only for to_EFDFormula
+        self.output_names = formula.outputs
+        self.input_nodes = {v: InputNode(v) for v in formula_input_variables(formula)}
+        self.roots = list(self.input_nodes.values())
+        self.nodes = self.roots.copy()
+        discovered_nodes = self.input_nodes.copy()
+        for op in formula.code:
+            node = CodeOpNode(op)
+            for side in (op.left, op.right):
+                if side is None:
+                    continue
+                if isinstance(side, int):
+                    parent_node = ConstantNode(side)
+                    self.nodes.append(parent_node)
+                    self.roots.append(parent_node)
+                else:
+                    parent_node = discovered_nodes[side]
+                parent_node.outgoing_nodes.append(node)
+                node.incoming_nodes.append(parent_node)
+            self.nodes.append(node)
+            discovered_nodes[op.result] = node
+        # flag output nodes
+        for output_name in self.output_names:
+            discovered_nodes[output_name].output_node = True
+
+        # go through the nodes and make sure that every node is root or has parents
+        for node in self.nodes:
+            if not node.incoming_nodes and not node in self.roots:
+                self.roots.append(node)
+        self.reindex()
+
+    def node_index(self, node: CodeOpNode) -> int:
+        return self.nodes.index(node)
+
+    def to_EFDFormula(self) -> EFDFormula:
+        # TODO rewrite
+        new_graph = deepcopy(self)
+        new_formula = new_graph._formula
+        new_formula.code = list(
+            map(
+                lambda x: x.op,
+                filter(lambda n: n not in new_graph.roots, new_graph.nodes),
+            )
+        )
+        return new_formula
+
+    @functools.cache
+    def networkx_graph(self) -> nx.DiGraph:
+        graph = nx.DiGraph()
+        vertices = list(range(len(self.nodes)))
+        graph.add_nodes_from(vertices)
+        stack = self.roots.copy()
+        while stack:
+            node = stack.pop()
+            for out in node.outgoing_nodes:
+                stack.append(out)
+                graph.add_edge(self.node_index(node), self.node_index(out))
+        return graph
+
+    def levels(self) -> List[List[Node]]:
+        stack = self.roots.copy()
+        levels = {n: 0 for n in stack}
+        level_counter = 1
+        while stack:
+            tmp_stack = []
+            while stack:
+                node = stack.pop()
+                levels[node] = level_counter
+                for out in node.outgoing_nodes:
+                    tmp_stack.append(out)
+            stack = tmp_stack
+            level_counter += 1
+        # separate into lists
+
+        level_lists = [[] for _ in range(level_counter)]
+        for node, l in levels.items():
+            level_lists[l].append(node)
+        return level_lists
+
+    @functools.cache
+    def ending_nodes(self) -> List[Node]:
+        return list(filter(lambda x: not x.outgoing_nodes, self.nodes))
+
+    def planar_positions(self) -> Dict[int, Tuple[float, float]]:
+        positions = {}
+        for i, level in enumerate(self.levels()):
+            for j, node in enumerate(level):
+                positions[self.node_index(node)] = (
+                    0.1 * float(i**2) + 3 * float(j),
+                    -6 * float(i),
+                )
+        return positions
+
+    def draw(self, filename: str = None, figsize: Tuple[int, int] = (12, 12)):
+        gnx = self.networkx_graph()
+        pos = nx.rescale_layout_dict(self.planar_positions())
+        plt.figure(figsize=figsize)
+        colors = [self.nodes[n].color for n in gnx.nodes]
+        labels = {n: self.nodes[n].label for n in gnx.nodes}
+        nx.draw(gnx, pos, node_color=colors, node_size=2000, labels=labels)
+        if filename:
+            plt.savefig(filename)
+            plt.close()
+        else:
+            plt.show()
+
+    def find_all_paths(self) -> List[List[Node]]:
+        gnx = self.networkx_graph()
+        index_paths = []
+        for u in self.roots:
+            iu = self.node_index(u)
+            for v in self.ending_nodes():
+                iv = self.node_index(v)
+                index_paths.extend(nx.all_simple_paths(gnx, iu, iv))
+        paths = []
+        for p in index_paths:
+            paths.append([self.nodes[v] for v in p])
+        return paths
+
+    def reorder(self):
+        self.nodes = sum(self.levels(), [])
+
+    def reindex(self):
+        results = {}
+        counter = 0
+        for node in self.nodes:
+            if node.input_node or isinstance(node, ConstantNode):
+                continue
+            op = node.op
+            result, left, operator, right = (
+                op.result,
+                op.left,
+                op.operator.op_str,
+                op.right,
+            )
+            if left in results:
+                left = results[left]
+            if right in results:
+                right = results[right]
+            if not node.output_node:
+                new_result = f"iv{counter}"
+                counter += 1
+            else:
+                new_result = result
+            opstr = f"{new_result} = {left if left is not None else ''}{operator}{right if right is not None else ''}"
+            results[result] = new_result
+            node.op = CodeOp(parse(opstr.replace("^", "**")))
+
+    def print(self):
+        for node in self.nodes:
+            print(node)
diff --git a/pyecsca/ec/formula_gen/metrics.py b/pyecsca/ec/formula_gen/metrics.py
new file mode 100644
index 0000000..5e5093d
--- /dev/null
+++ b/pyecsca/ec/formula_gen/metrics.py
@@ -0,0 +1,144 @@
+from pyecsca.sca.re.zvp import unroll_formula
+from pyecsca.ec.formula import (
+    EFDFormula,
+    AdditionEFDFormula,
+    Formula,
+    LadderEFDFormula,
+    DoublingEFDFormula,
+)
+import warnings
+from typing import Dict
+from operator import itemgetter, attrgetter
+from pyecsca.ec.curve import EllipticCurve
+from pyecsca.ec.context import DefaultContext, local
+
+
+def formula_similarity(one: Formula, other: Formula) -> Dict[str, float]:
+    if one.coordinate_model != other.coordinate_model:
+        warnings.warn("Mismatched coordinate model.")
+
+    one_unroll = unroll_formula(one)
+    other_unroll = unroll_formula(other)
+    one_results = {}
+    for name, value in one_unroll:
+        if name in one.outputs:
+            one_results[name] = value
+    other_results = {}
+    for name, value in other_unroll:
+        if name in other.outputs:
+            other_results[name] = value
+    one_result_polys = set(one_results.values())
+    other_result_polys = set(other_results.values())
+    one_polys = set(map(itemgetter(1), one_unroll))
+    other_polys = set(map(itemgetter(1), other_unroll))
+    return {
+        "output": len(one_result_polys.intersection(other_result_polys))
+        / max(len(one_result_polys), len(other_result_polys)),
+        "ivs": len(one_polys.intersection(other_polys))
+        / max(len(one_polys), len(other_polys)),
+    }
+
+
+def formula_similarity_abs(one: Formula, other: Formula) -> Dict[str, float]:
+    if one.coordinate_model != other.coordinate_model:
+        warnings.warn("Mismatched coordinate model.")
+
+    one_unroll = unroll_formula(one)
+    other_unroll = unroll_formula(other)
+    one_results = {}
+    for name, value in one_unroll:
+        if name in one.outputs:
+            one_results[name] = value
+    other_results = {}
+    for name, value in other_unroll:
+        if name in other.outputs:
+            other_results[name] = value
+    one_result_polys = set(one_results.values())
+    other_result_polys = set(other_results.values())
+    one_polys = set(map(itemgetter(1), one_unroll))
+    other_polys = set(map(itemgetter(1), other_unroll))
+
+    one_polys = set([f if f.LC() > 0 else -f for f in one_polys])
+    # one_polys.update(set(-f for f in one_polys))
+    other_polys = set([f if f.LC() > 0 else -f for f in other_polys])
+    # other_polys.update(set(-f for f in other_polys))
+
+    return {
+        "output": len(one_result_polys.intersection(other_result_polys))
+        / max(len(one_result_polys), len(other_result_polys)),
+        "ivs": len(one_polys.intersection(other_polys))
+        / max(len(one_polys), len(other_polys)),
+    }
+
+
+def formula_similarity_fuzz(
+    one: Formula, other: Formula, curve: EllipticCurve, samples: int = 1000
+) -> Dict[str, float]:
+    if one.coordinate_model != other.coordinate_model:
+        raise ValueError("Mismatched coordinate model.")
+
+    output_matches = 0.0
+    iv_matches = 0.0
+    for _ in range(samples):
+        P = curve.affine_random().to_model(one.coordinate_model, curve)
+        Q = curve.affine_random().to_model(other.coordinate_model, curve)
+        with local(DefaultContext()) as ctx:
+            res_one = one(curve.prime, P, Q, **curve.parameters)
+        action_one = ctx.actions.get_by_index([0])
+        ivs_one = set(
+            map(attrgetter("value"), sum(action_one[0].intermediates.values(), []))
+        )
+        with local(DefaultContext()) as ctx:
+            res_other = other(curve.prime, P, Q, **curve.parameters)
+        action_other = ctx.actions.get_by_index([0])
+        ivs_other = set(
+            map(attrgetter("value"), sum(action_other[0].intermediates.values(), []))
+        )
+        iv_matches += len(ivs_one.intersection(ivs_other)) / max(
+            len(ivs_one), len(ivs_other)
+        )
+        one_coords = set(res_one)
+        other_coords = set(res_other)
+        output_matches += len(one_coords.intersection(other_coords)) / max(
+            len(one_coords), len(other_coords)
+        )
+    return {"output": output_matches / samples, "ivs": iv_matches / samples}
+
+
+def formula_similarity_fuzz2(
+    one: Formula, other: Formula, curve: EllipticCurve, samples: int = 1000
+) -> Dict[str, float]:
+    if one.coordinate_model != other.coordinate_model:
+        raise ValueError("Mismatched coordinate model.")
+
+    output_matches = 0.0
+    iv_matches = 0.0
+    for _ in range(samples):
+        Paff = curve.affine_random()
+        Qaff = curve.affine_random()
+        Raff = curve.affine_add(Paff, Qaff)
+        P = Paff.to_model(one.coordinate_model, curve)
+        Q = Qaff.to_model(one.coordinate_model, curve)
+        R = Raff.to_model(one.coordinate_model, curve)
+        inputs = (P, Q, R)[: one.num_inputs]
+        with local(DefaultContext()) as ctx:
+            res_one = one(curve.prime, *inputs, **curve.parameters)
+        action_one = ctx.actions.get_by_index([0])
+        ivs_one = set(
+            map(attrgetter("value"), sum(action_one[0].intermediates.values(), []))
+        )
+        with local(DefaultContext()) as ctx:
+            res_other = other(curve.prime, *inputs, **curve.parameters)
+        action_other = ctx.actions.get_by_index([0])
+        ivs_other = set(
+            map(attrgetter("value"), sum(action_other[0].intermediates.values(), []))
+        )
+        iv_matches += len(ivs_one.intersection(ivs_other)) / max(
+            len(ivs_one), len(ivs_other)
+        )
+        one_coords = set(res_one)
+        other_coords = set(res_other)
+        output_matches += len(one_coords.intersection(other_coords)) / max(
+            len(one_coords), len(other_coords)
+        )
+    return {"output": output_matches / samples, "ivs": iv_matches / samples}