3 files changed, 202 insertions, 8 deletions

diff --git a/pyecsca/ec/mult/comb.py b/pyecsca/ec/mult/comb.py
index 958d089..84ec27a 100644
--- a/pyecsca/ec/mult/comb.py
+++ b/pyecsca/ec/mult/comb.py
@@ -1 +1,183 @@
 """Provides Comb-like scalar multipliers, such as BGMW or Lim-Lee."""
+from copy import copy
+from math import ceil
+from typing import MutableMapping, Optional
+
+from public import public
+
+from ..formula import AdditionFormula, DoublingFormula, ScalingFormula
+from ..mult import (
+    AccumulatorMultiplier,
+    ScalarMultiplier,
+    ProcessingDirection,
+    AccumulationOrder,
+    PrecomputationAction,
+    ScalarMultiplicationAction,
+)
+from ..params import DomainParameters
+from ..point import Point
+from ..scalar import convert_base
+
+
+@public
+class BGMWMultiplier(AccumulatorMultiplier, ScalarMultiplier):
+    """
+    Brickell, Gordon, McCurley and Wilson (BGMW) scalar multiplier,
+    or rather, its one parametrization.
+
+    Algorithm 3.41 from [GECC]_
+
+    :param width: Window width.
+    :param direction: Whether it is LTR or RTL.
+    :param accumulation_order: The order of accumulation of points.
+    """
+
+    requires = {AdditionFormula, DoublingFormula}
+    optionals = {ScalingFormula}
+    direction: ProcessingDirection
+    """Whether it is LTR or RTL."""
+    width: int
+    """Window width."""
+    _points: MutableMapping[int, Point]
+
+    def __init__(
+        self,
+        add: AdditionFormula,
+        dbl: DoublingFormula,
+        width: int,
+        scl: Optional[ScalingFormula] = None,
+        direction: ProcessingDirection = ProcessingDirection.LTR,
+        accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR,
+        short_circuit: bool = True,
+    ):
+        super().__init__(
+            short_circuit=short_circuit,
+            accumulation_order=accumulation_order,
+            add=add,
+            dbl=dbl,
+            scl=scl,
+        )
+        self.direction = direction
+        self.width = width
+
+    def init(self, params: DomainParameters, point: Point):
+        with PrecomputationAction(params, point):
+            super().init(params, point)
+            d = ceil(params.order.bit_length() / self.width)
+            self._points = {}
+            current_point = point
+            for i in range(d):
+                self._points[i] = current_point
+                if i != d - 1:
+                    for _ in range(self.width):
+                        current_point = self._dbl(current_point)
+
+    def multiply(self, scalar: int) -> Point:
+        if not self._initialized:
+            raise ValueError("ScalarMultiplier not initialized.")
+        with ScalarMultiplicationAction(self._point, scalar) as action:
+            if scalar == 0:
+                return action.exit(copy(self._params.curve.neutral))
+            a = copy(self._params.curve.neutral)
+            b = copy(self._params.curve.neutral)
+            recoded = convert_base(scalar, 2**self.width)
+            for j in range(2**self.width - 1, 0, -1):
+                if self.direction == ProcessingDirection.RTL:
+                    for i, ki in enumerate(recoded):
+                        if ki == j:
+                            b = self._accumulate(b, self._points[i])
+                elif self.direction == ProcessingDirection.LTR:
+                    for i, ki in reversed(list(enumerate(recoded))):
+                        if ki == j:
+                            b = self._accumulate(b, self._points[i])
+                if self.short_circuit and a == b:
+                    # TODO: Double necessary here for incomplete formulas, maybe another param and not reuse short_cirtuit?
+                    a = self._dbl(b)
+                else:
+                    a = self._accumulate(a, b)
+            if "scl" in self.formulas:
+                a = self._scl(a)
+            return action.exit(a)
+
+
+@public
+class CombMultiplier(AccumulatorMultiplier, ScalarMultiplier):
+    """
+    Comb multiplier.
+
+    Algorithm 3.44 from [GECC]_
+
+    :param width: Window width (number of comb teeth).
+    :param accumulation_order: The order of accumulation of points.
+    """
+
+    requires = {AdditionFormula, DoublingFormula}
+    optionals = {ScalingFormula}
+    width: int
+    """Window width."""
+    _points: MutableMapping[int, Point]
+
+    def __init__(
+        self,
+        add: AdditionFormula,
+        dbl: DoublingFormula,
+        width: int,
+        scl: Optional[ScalingFormula] = None,
+        accumulation_order: AccumulationOrder = AccumulationOrder.PeqPR,
+        short_circuit: bool = True,
+    ):
+        super().__init__(
+            short_circuit=short_circuit,
+            accumulation_order=accumulation_order,
+            add=add,
+            dbl=dbl,
+            scl=scl,
+        )
+        self.width = width
+
+    def init(self, params: DomainParameters, point: Point):
+        with PrecomputationAction(params, point):
+            super().init(params, point)
+            d = ceil(params.order.bit_length() / self.width)
+            base_points = {}
+            current_point = point
+            for i in range(self.width):
+                base_points[i] = current_point
+                if i != d - 1:
+                    for _ in range(d):
+                        current_point = self._dbl(current_point)
+            self._points = {}
+            for j in range(1, 2**self.width):
+                points = []
+                for i in range(self.width):
+                    if j & (1 << i):
+                        points.append(base_points[i])
+                self._points[j] = points[0]
+                for point in points[1:]:
+                    self._points[j] = self._accumulate(self._points[j], point)
+
+    def multiply(self, scalar: int) -> Point:
+        if not self._initialized:
+            raise ValueError("ScalarMultiplier not initialized.")
+        with ScalarMultiplicationAction(self._point, scalar) as action:
+            if scalar == 0:
+                return action.exit(copy(self._params.curve.neutral))
+            q = copy(self._params.curve.neutral)
+            d = ceil(self._params.order.bit_length() / self.width)
+            recoded = convert_base(scalar, 2**d)
+            if len(recoded) != self.width:
+                recoded.extend([0] * (self.width - len(recoded)))
+            for i in range(d - 1, -1, -1):
+                q = self._dbl(q)
+                word = 0
+                for j in range(self.width):
+                    # get i-th bit of recoded[j] and set it into the j-th bit of word
+                    bit = (recoded[j] >> i) & 1
+                    word |= bit << j
+                if word:
+                    q = self._accumulate(q, self._points[word])
+                # TODO always
+
+            if "scl" in self.formulas:
+                q = self._scl(q)
+            return action.exit(q)
diff --git a/pyecsca/ec/mult/fixed.py b/pyecsca/ec/mult/fixed.py
index cd44e3a..010767b 100644
--- a/pyecsca/ec/mult/fixed.py
+++ b/pyecsca/ec/mult/fixed.py
@@ -4,11 +4,11 @@ from typing import MutableMapping, Optional
 
 from public import public
 
-from pyecsca.ec.formula import AdditionFormula, DoublingFormula, ScalingFormula
-from pyecsca.ec.mult import AccumulatorMultiplier, ScalarMultiplier, ProcessingDirection, AccumulationOrder, \
+from ..formula import AdditionFormula, DoublingFormula, ScalingFormula
+from ..mult import AccumulatorMultiplier, ScalarMultiplier, ProcessingDirection, AccumulationOrder, \
     PrecomputationAction, ScalarMultiplicationAction
-from pyecsca.ec.params import DomainParameters
-from pyecsca.ec.point import Point
+from ..params import DomainParameters
+from ..point import Point
 
 
 @public
@@ -22,6 +22,7 @@ class FullPrecompMultiplier(AccumulatorMultiplier, ScalarMultiplier):
 
     :param always: Whether the addition is always performed.
     :param direction: Whether it is LTR or RTL.
+    :param accumulation_order: The order of accumulation of points.
     :param complete: Whether it starts processing at full order-bit-length.
     """
 
@@ -71,7 +72,8 @@ class FullPrecompMultiplier(AccumulatorMultiplier, ScalarMultiplier):
             current_point = point
             for i in range(params.order.bit_length() + 1):
                 self._points[i] = current_point
-                current_point = self._dbl(current_point)
+                if i != params.order.bit_length():
+                    current_point = self._dbl(current_point)
 
     def _ltr(self, scalar: int) -> Point:
         if self.complete:
diff --git a/pyecsca/ec/mult/window.py b/pyecsca/ec/mult/window.py
index 3ee8c50..8317965 100644
--- a/pyecsca/ec/mult/window.py
+++ b/pyecsca/ec/mult/window.py
@@ -17,13 +17,20 @@ from ..scalar import convert_base, sliding_window_rtl, sliding_window_ltr
 
 @public
 class SlidingWindowMultiplier(AccumulatorMultiplier, ScalarMultiplier):
-    """Sliding window scalar multiplier."""
+    """
+    Sliding window scalar multiplier.
+
+    :param width: The width of the sliding-window recoding.
+    :param recoding_direction: The direction for the sliding-window recoding.
+    :param accumulation_order: The order of accumulation of points.
+    """
 
     requires = {AdditionFormula, DoublingFormula}
     optionals = {ScalingFormula}
-    complete: bool
     width: int
+    """The width of the sliding-window recoding."""
     recoding_direction: ProcessingDirection
+    """The direction for the sliding-window recoding."""
     _points: MutableMapping[int, Point]
 
     def __init__(
@@ -93,12 +100,15 @@ class FixedWindowLTRMultiplier(AccumulatorMultiplier, ScalarMultiplier):
     to perform the multiplication-by-m between each window addition.
 
     For other `m` values, this is the m-ary multiplier.
+
+    :param m: The arity of the multiplier.
+    :param accumulation_order: The order of accumulation of points.
     """
 
     requires = {AdditionFormula, DoublingFormula}
     optionals = {ScalingFormula}
-    complete: bool
     m: int
+    """The arity of the multiplier."""
     _points: MutableMapping[int, Point]
 
     def __init__(