[PATCH] MPI helper of addition one limb, Least Leak Intended

[Jacob Bachmeyer]

On 2/13/25 19:25, NIIBE Yutaka via Gcrypt-devel wrote:
> Hello,
>
> This change introduces a function _gcry_mpih_add_1_lli for one limb
> addition with least leak.
>
> diff --git a/mpi/mpi-inline.h b/mpi/mpi-inline.h
> index 090e8a94..6954affb 100644
> --- a/mpi/mpi-inline.h
> +++ b/mpi/mpi-inline.h
> @@ -68,6 +68,28 @@ _gcry_mpih_add_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
>   }
>   
>   
> +/* Do same calculation as _gcry_mpih_add_1 does (under the condition
> +   of RES_PTR == S1_PTR), Least Leak Intended.  */
> +static inline mpi_limb_t
> +_gcry_mpih_add_1_lli (mpi_ptr_t s1_ptr, mpi_size_t s1_size, mpi_limb_t s2_limb)
> +{
> +  mpi_limb_t x;
> +  mpi_limb_t cy;
> +
> +  x = *s1_ptr;
> +  s2_limb += x;
> +  *s1_ptr++ = s2_limb;
> +  cy = (s2_limb < x);
> +  while ( --s1_size )
> +    {
> +      x = *s1_ptr + cy;
> +      *s1_ptr++ = x;
> +      cy = mpih_limb_is_zero (x) & mpih_limb_is_not_zero (cy);
> +    }
> +
> +  return cy;
> +}
> +

Looking at this, I can now deduce that MPI values are stored in 
little-endian order, "x" is a working register, and "cy" is a carry flag.

If I read this correctly, the carry handling is depending on integer 
overflow wrapping around, which is not actually defined behavior in C, 
although most platforms do handle it that way.  Do we have an 
MPI_LIMB_MAX constant analogous to INT_MAX but for mpi_limb_t instead of 
int?

Also, if I understand correctly from the previous discussion, "<" is to 
be avoided because compilers can use a branch to implement it.  
Unfortunately, I am unsure if there is any way short of simulating an 
adder block to do this without using a relational operator and/or 
relying on undefined behavior.


-- Jacob