Github Action WIndows failure

[mratsim]

From #29

32-bit

• Incorrect modulo / reduce on 32-bit

64-bit

• Modular inversion fails post condition

[mratsim]

For reference:

[mratsim]

The wrong values seem to be stable across CI runs:

So we can rule out unitialized memory.

Looking into the reduction code:

constantine/constantine/arithmetic/limbs_modular.nim

Lines 243 to 380 in 608d26e

	func shlAddMod_estimate(a: LimbsViewMut, aLen: int,
	c: SecretWord, M: LimbsViewConst, mBits: int
	): tuple[neg, tooBig: SecretBool] =
	## Estimate a <- a shl 2^w + c (mod M)
	##
	## with w the base word width, usually 32 on 32-bit platforms and 64 on 64-bit platforms
	##
	## Updates ``a`` and returns ``neg`` and ``tooBig``
	## If ``neg``, the estimate in ``a`` is negative and ``M`` must be added to it.
	## If ``tooBig``, the estimate in ``a`` overflowed and ``M`` must be substracted from it.
	# Aliases
	# ----------------------------------------------------------------------
	let MLen = numWordsFromBits(mBits)
	# Captures aLen and MLen
	template `[]`(v: untyped, limbIdxFromEnd: BackwardsIndex): SecretWord {.dirty.}=
	v[`v Len` - limbIdxFromEnd.int]
	# ----------------------------------------------------------------------
	# Assuming 64-bit words
	let hi = a[^1] # Save the high word to detect carries
	let R = mBits and (WordBitWidth - 1) # R = mBits mod 64
	var a0, a1, m0: SecretWord
	if R == 0: # If the number of mBits is a multiple of 64
	a0 = a[^1] #
	moveMem(a[1].addr, a[0].addr, (aLen-1) * SecretWord.sizeof) # we can just shift words
	a[0] = c # and replace the first one by c
	a1 = a[^1]
	m0 = M[^1]
	else: # Else: need to deal with partial word shifts at the edge.
	a0 = (a[^1] shl (WordBitWidth-R)) or (a[^2] shr R)
	moveMem(a[1].addr, a[0].addr, (aLen-1) * SecretWord.sizeof)
	a[0] = c
	a1 = (a[^1] shl (WordBitWidth-R)) or (a[^2] shr R)
	m0 = (M[^1] shl (WordBitWidth-R)) or (M[^2] shr R)
	# m0 has its high bit set. (a0, a1)/p0 fits in a limb.
	# Get a quotient q, at most we will be 2 iterations off
	# from the true quotient
	var q, r: SecretWord
	unsafeDiv2n1n(q, r, a0, a1, m0) # Estimate quotient
	q = mux( # If n_hi == divisor
	a0 == m0, MaxWord, # Quotient == MaxWord (0b1111...1111)
	mux(
	q.isZero, Zero, # elif q == 0, true quotient = 0
	q - One # else instead of being of by 0, 1 or 2
	) # we returning q-1 to be off by -1, 0 or 1
	)
	# Now substract a*2^64 - q*p
	var carry = Zero
	var over_p = CtTrue # Track if quotient greater than the modulus
	for i in 0 ..< MLen:
	var qp_lo: SecretWord
	block: # q*p
	# q * p + carry (doubleword) carry from previous limb
	muladd1(carry, qp_lo, q, M[i], carry)
	block: # a*2^64 - q*p
	var borrow: Borrow
	subB(borrow, a[i], a[i], qp_lo, Borrow(0))
	carry += SecretWord(borrow) # Adjust if borrow
	over_p = mux(
	a[i] == M[i], over_p,
	a[i] > M[i]
	)
	# Fix quotient, the true quotient is either q-1, q or q+1
	#
	# if carry < q or carry == q and over_p we must do "a -= p"
	# if carry > hi (negative result) we must do "a += p"
	result.neg = carry > hi
	result.tooBig = not(result.neg) and (over_p or (carry < hi))
	func shlAddMod(a: LimbsViewMut, aLen: int,
	c: SecretWord, M: LimbsViewConst, mBits: int) =
	## Fused modular left-shift + add
	## Shift input `a` by a word and add `c` modulo `M`
	##
	## With a word W = 2^WordBitSize and a modulus M
	## Does a <- a * W + c (mod M)
	##
	## The modulus `M` most-significant bit at `mBits` MUST be set.
	if mBits <= WordBitWidth:
	# If M fits in a single limb
	# We normalize M with R so that the MSB is set
	# And normalize (a * 2^64 + c) by R as well to maintain the result
	# This ensures that (a0, a1)/p0 fits in a limb.
	let R = mBits and (WordBitWidth - 1)
	# (hi, lo) = a * 2^64 + c
	let hi = (a[0] shl (WordBitWidth-R)) or (c shr R)
	let lo = c shl (WordBitWidth-R)
	let m0 = M[0] shl (WordBitWidth-R)
	var q, r: SecretWord
	unsafeDiv2n1n(q, r, hi, lo, m0) # (hi, lo) mod M
	a[0] = r shr (WordBitWidth-R)
	else:
	## Multiple limbs
	let (neg, tooBig) = shlAddMod_estimate(a, aLen, c, M, mBits)
	discard a.cadd(M, ctl = neg, aLen)
	discard a.csub(M, ctl = tooBig, aLen)
	func reduce(r: LimbsViewMut,
	a: LimbsViewAny, aBits: int,
	M: LimbsViewConst, mBits: int) =
	## Reduce `a` modulo `M` and store the result in `r`
	let aLen = numWordsFromBits(aBits)
	let mLen = numWordsFromBits(mBits)
	let rLen = mLen
	if aBits < mBits:
	# if a uses less bits than the modulus,
	# it is guaranteed < modulus.
	# This relies on the precondition that the modulus uses all declared bits
	copyMem(r[0].addr, a[0].unsafeAddr, aLen * sizeof(SecretWord))
	for i in aLen ..< mLen:
	r[i] = Zero
	else:
	# a length i at least equal to the modulus.
	# we can copy modulus.limbs-1 words
	# and modular shift-left-add the rest
	let aOffset = aLen - mLen
	copyMem(r[0].addr, a[aOffset+1].unsafeAddr, (mLen-1) * sizeof(SecretWord))
	r[rLen - 1] = Zero
	# Now shift-left the copied words while adding the new word modulo M
	for i in countdown(aOffset, 0):
	shlAddMod(r, rLen, a[i], M, mBits)

I have a feeling that there is a moveMem bug in Windows 32-bit, as it doesn't happen in Linux 32-bit or Windows 64-bit.

[mratsim]

Seems like it wasn't copyMem/moveMem:

b509eea

[mratsim]

Closed by:

• Constant time #185, software-based division/remainder for uint32/uint64, for all platforms
• Fast modular inversion #172, old modular inversion is removed, works even for BigInt that fit in a single word
• try 1.6 CI #170, CI coverage of 32~64-bit and Linux/Windows/Mac and all Nim compilers