Module fe17 

Radix-2^17 field arithmetic units for the field machines.

A Fe17 holds fifteen 17-bit digits, least significant first, and is always canonical (strictly below p = 2^255 - 19) at unit boundaries. Fifteen digits of 17 bits are exactly 255 bits, so 2^255 = 19 (mod p) folds column k + 15 onto column k with a factor of 19.

FieldMulPar computes the fifteen folded columns c_k = sum_i a_i * b'_{k-i} with b'_j = b_j or 19 b_j (wrapped), as fifteen 15-deep multiply-accumulate chains. Every product is 17 x 22 bits, which fits the DSP48E2’s 18 x 27 signed multiplier, and every chain stage has the shape P = PCIN + A * B, which maps to a DSP cascade without fabric adders. Operands are skewed by delay registers so chain stage i sees its operands exactly i cycles after stage 0. Three lazy carry passes, one 256-bit carry-propagate, and a two-candidate final reduction return a canonical result after MUL_LATENCY cycles.

FieldAddSub adds or subtracts two canonical elements in ADD_LATENCY cycles. Subtraction adds p - b instead of negating, so both operations share one adder and one final reduction.

Both units accept a new request every clock and have a fixed latency with no stalls. Each request carries an opaque 16-bit tag that comes back with its result, which is how the field machine routes write-backs.

Structs

Fe17

Canonical field element in fifteen 17-bit digits (255 bits).

FieldAddIn

Add/subtract request, sampled every clock (initiation interval one).

FieldAddOut

Add/subtract result, ADD_LATENCY cycles after the request.

FieldAddSub

Five-cycle canonical modular add/subtract with no carry chain longer than one 85-bit limb per stage.

FieldMulIn

Multiplier request, sampled every clock (no handshake: the unit is initiation-interval one).

FieldMulOut

Multiplier result, MUL_LATENCY cycles after the request.

FieldMulPar

Initiation-interval-one, 225-DSP canonical field multiplier.

MulChain7

Seven chained MulStages (kept small so every kernel’s port bundle lowers to Verilog constants that common front ends can scan).

MulNorm

Carry normalization and canonical reduction of the fifteen column sums.

MulRow

Operand row held by one chain stage: a[0] is this stage’s multiplier digit, v[k] the factor for column k, and w the 19-fold digits that rotate in at column 0 as the stages advance.

MulStage

One multiply-accumulate stage of all fifteen column chains.

MulStageIo

Input and output of one MulStage: the previous stage’s registered row and partial sums.

Constants

ADD_LATENCY

Fixed add/subtract latency, counted the same way as MUL_LATENCY: five register stages, so a request captured at edge t is on the output after edge t + 4. The field machine routes results by tag and its barrel (32 contexts) hides any latency up to the multiplier’s, so this is free.

MUL_LATENCY

Multiplier latency in clock edges: a request presented to FieldMulPar before clock edge t (captured at t) is visible on the output after edge t + 22, i.e. it occupies 23 register stages. The field machine relies on this being fixed, because it routes results only by tag and never waits for them.

Functions

add255

255-bit addition of limb vectors; returns the sum modulo 2^255 and bit 255.

add_limb

One limb step of a 255-bit addition: x + y + c over 85 bits, with the carry out. Combinational; one 85-bit carry chain.

canonical255

Canonical value of lo + hi * 2^255 for lo + 19 * hi < 2p.

digits_from_limbs

Inverse of limbs_from_digits (also pure rewiring).

field_add_sub_kernel

State transition for FieldAddSub.

field_mul_par_kernel

State transition for FieldMulPar.

limbs_from_digits

Three 85-bit limbs (five digits each) of a 255-bit integer.

mul_chain7_kernel

Wiring for MulChain7: each stage feeds the next, and the last stage’s output is the chain output.

mul_norm_kernel

State transition for MulNorm: three lazy carry passes (column 14 wraps with a factor of 19), then a limb-serial carry-propagate and canonical result.

mul_stage_kernel

State transition for MulStage.

nb19_const

A limb of the constant added to x to form nb + 19: !b + 1 = 2^255 - b = p - b + 19, or b + 19.

nb_const

A limb (the low one or a higher one) of the constant added to x (b, or !b for subtraction) to form nb: !b + (2^255 - 18) = p - b mod 2^255, or b + 0.

p_minus

p - b for canonical b, computed as !b - 18 over 255 bits.

times19_digit

x * 19 for a 17-bit digit, as 16x + 2x + x (shifts and adds, no DSP). The result is below 2^22.