Msm_pippenger.Scalar_transformationModule to transform scalars to a signed-digit representation, which is expected by the downstream FPGA logic.
The main transform currently implemented transforms the input scalar from unsigned digits in the range \([0,2^b-1]\) to signed digits in the range \([-2^{b-1}, 2^{b-1}-1]\) .
It does this as follows: suppose we have a B-bit scalar \(k\), split into \(N\) windows of size \(b_i\) , where \(\sum_{i=0}^{N-1}{b_i} = B\) . Then, letting \(o_i = \sum_{j=0}^{i-1}{b_i}\) be the offsets of each digit, we can write $$ k = \sum_{i=0}^{N-1}{2^{o_i}d_i},\;\; d_i\in[0,2^b_i-1]\;\forall i $$ as a normal unsigned representation of \(k\) (derived by just directly windowing the bits in its binary representation).
Then, we perform the following iterative transform from \(i = 0\) to \(N-2\) .
$$ \text{If } d_i \geq 2^{b_i-1}: (d_i, d_{i+1}) \leftarrow (d_i - 2^{b_i}, d_{i+1} + 1) $$After performing this transform, digits \(d_i\in[-2^{b_i-1}, 2^{b_i-1}-1]\) for \(i\in[0,N-2]\) .
The downstream point adder can exploit this new digit base because point negation is extremely cheap (on the Twisted Edwards affine space, it just corresponds to negative the x-coordinate). So, for all but the final window, we can halve the number of buckets and use point subtraction for all the negative buckets.
The module implements this transform as a fully unrolled (N-1)-stage pipeline, with optional skid buffers in order to cut combinational ready signal paths. It is designed in a modular way so that the overall scalar transformation can be extended to include many further transforms using other scalars (i.e. 2, 3, etc.), if point multiples were precomputed and loaded in the FPGA.
module Axi512 = Hardcaml_axi.Axi512