|
Packit |
5c3484 |
/* mpn_sec_pi1_div_qr, mpn_sec_pi1_div_r -- Compute Q = floor(U / V), U = U
|
|
Packit |
5c3484 |
mod V. Side-channel silent under the assumption that the used instructions
|
|
Packit |
5c3484 |
are side-channel silent.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Contributed to the GNU project by Torbjörn Granlund.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES. IT IS ONLY
|
|
Packit |
5c3484 |
SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
|
|
Packit |
5c3484 |
GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Copyright 2011-2013 Free Software Foundation, Inc.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This file is part of the GNU MP Library.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is free software; you can redistribute it and/or modify
|
|
Packit |
5c3484 |
it under the terms of either:
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU Lesser General Public License as published by the Free
|
|
Packit |
5c3484 |
Software Foundation; either version 3 of the License, or (at your
|
|
Packit |
5c3484 |
option) any later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU General Public License as published by the Free Software
|
|
Packit |
5c3484 |
Foundation; either version 2 of the License, or (at your option) any
|
|
Packit |
5c3484 |
later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or both in parallel, as here.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is distributed in the hope that it will be useful, but
|
|
Packit |
5c3484 |
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
Packit |
5c3484 |
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
Packit |
5c3484 |
for more details.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
You should have received copies of the GNU General Public License and the
|
|
Packit |
5c3484 |
GNU Lesser General Public License along with the GNU MP Library. If not,
|
|
Packit |
5c3484 |
see https://www.gnu.org/licenses/. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include "gmp.h"
|
|
Packit |
5c3484 |
#include "gmp-impl.h"
|
|
Packit |
5c3484 |
#include "longlong.h"
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* This side-channel silent division algorithm reduces the partial remainder by
|
|
Packit |
5c3484 |
GMP_NUMB_BITS/2 bits at a time, compared to GMP_NUMB_BITS for the main
|
|
Packit |
5c3484 |
division algorithm. We actually do not insist on reducing by exactly
|
|
Packit |
5c3484 |
GMP_NUMB_BITS/2, but may leave a partial remainder that is D*B^i to 3D*B^i
|
|
Packit |
5c3484 |
too large (B is the limb base, D is the divisor, and i is the induction
|
|
Packit |
5c3484 |
variable); the subsequent step will handle the extra partial remainder bits.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
With that partial remainder reduction, each step generates a quotient "half
|
|
Packit |
5c3484 |
limb". The outer loop generates two quotient half limbs, an upper (q1h) and
|
|
Packit |
5c3484 |
a lower (q0h) which are stored sparsely in separate limb arrays. These
|
|
Packit |
5c3484 |
arrays are added at the end; using separate arrays avoids data-dependent
|
|
Packit |
5c3484 |
carry propagation which could else pose a side-channel leakage problem.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The quotient half limbs may be between -3 to 0 from the accurate value
|
|
Packit |
5c3484 |
("accurate" being the one which corresponds to a reduction to a principal
|
|
Packit |
5c3484 |
partial remainder). Too small quotient half limbs correspond to too large
|
|
Packit |
5c3484 |
remainders, which we reduce later, as described above.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
In order to keep quotients from getting too big, corresponding to a negative
|
|
Packit |
5c3484 |
partial remainder, we use an inverse which is slightly smaller than usually.
|
|
Packit |
5c3484 |
*/
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_qr
|
|
Packit |
5c3484 |
/* Needs (dn + 1) + (nn - dn) + (nn - dn) = 2nn - dn + 1 limbs at tp. */
|
|
Packit |
5c3484 |
#define FNAME mpn_sec_pi1_div_qr
|
|
Packit |
5c3484 |
#define Q(q) q,
|
|
Packit |
5c3484 |
#define RETTYPE mp_limb_t
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_r
|
|
Packit |
5c3484 |
/* Needs (dn + 1) limbs at tp. */
|
|
Packit |
5c3484 |
#define FNAME mpn_sec_pi1_div_r
|
|
Packit |
5c3484 |
#define Q(q)
|
|
Packit |
5c3484 |
#define RETTYPE void
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
RETTYPE
|
|
Packit |
5c3484 |
FNAME (Q(mp_ptr qp)
|
|
Packit |
5c3484 |
mp_ptr np, mp_size_t nn,
|
|
Packit |
5c3484 |
mp_srcptr dp, mp_size_t dn,
|
|
Packit |
5c3484 |
mp_limb_t dinv,
|
|
Packit |
5c3484 |
mp_ptr tp)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_limb_t nh, cy, q1h, q0h, dummy, cnd;
|
|
Packit |
5c3484 |
mp_size_t i;
|
|
Packit |
5c3484 |
mp_ptr hp;
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_qr
|
|
Packit |
5c3484 |
mp_limb_t qh;
|
|
Packit |
5c3484 |
mp_ptr qlp, qhp;
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ASSERT (dn >= 1);
|
|
Packit |
5c3484 |
ASSERT (nn >= dn);
|
|
Packit |
5c3484 |
ASSERT ((dp[dn - 1] & GMP_NUMB_HIGHBIT) != 0);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (nn == dn)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
cy = mpn_sub_n (np, np, dp, dn);
|
|
Packit |
5c3484 |
mpn_cnd_add_n (cy, np, np, dp, dn);
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_qr
|
|
Packit |
5c3484 |
return 1 - cy;
|
|
Packit |
5c3484 |
#else
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Create a divisor copy shifted half a limb. */
|
|
Packit |
5c3484 |
hp = tp; /* (dn + 1) limbs */
|
|
Packit |
5c3484 |
hp[dn] = mpn_lshift (hp, dp, dn, GMP_NUMB_BITS / 2);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_qr
|
|
Packit |
5c3484 |
qlp = tp + (dn + 1); /* (nn - dn) limbs */
|
|
Packit |
5c3484 |
qhp = tp + (nn + 1); /* (nn - dn) limbs */
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
np += nn - dn;
|
|
Packit |
5c3484 |
nh = 0;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
for (i = nn - dn - 1; i >= 0; i--)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
np--;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
nh = (nh << GMP_NUMB_BITS/2) + (np[dn] >> GMP_NUMB_BITS/2);
|
|
Packit |
5c3484 |
umul_ppmm (q1h, dummy, nh, dinv);
|
|
Packit |
5c3484 |
q1h += nh;
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_qr
|
|
Packit |
5c3484 |
qhp[i] = q1h;
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
mpn_submul_1 (np, hp, dn + 1, q1h);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
nh = np[dn];
|
|
Packit |
5c3484 |
umul_ppmm (q0h, dummy, nh, dinv);
|
|
Packit |
5c3484 |
q0h += nh;
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_qr
|
|
Packit |
5c3484 |
qlp[i] = q0h;
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
nh -= mpn_submul_1 (np, dp, dn, q0h);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* 1st adjustment depends on extra high remainder limb. */
|
|
Packit |
5c3484 |
cnd = nh != 0; /* FIXME: cmp-to-int */
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_qr
|
|
Packit |
5c3484 |
qlp[0] += cnd;
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
nh -= mpn_cnd_sub_n (cnd, np, np, dp, dn);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* 2nd adjustment depends on remainder/divisor comparison as well as whether
|
|
Packit |
5c3484 |
extra remainder limb was nullified by previous subtract. */
|
|
Packit |
5c3484 |
cy = mpn_sub_n (np, np, dp, dn);
|
|
Packit |
5c3484 |
cy = cy - nh;
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_qr
|
|
Packit |
5c3484 |
qlp[0] += 1 - cy;
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
mpn_cnd_add_n (cy, np, np, dp, dn);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* 3rd adjustment depends on remainder/divisor comparison. */
|
|
Packit |
5c3484 |
cy = mpn_sub_n (np, np, dp, dn);
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_qr
|
|
Packit |
5c3484 |
qlp[0] += 1 - cy;
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
mpn_cnd_add_n (cy, np, np, dp, dn);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if OPERATION_sec_pi1_div_qr
|
|
Packit |
5c3484 |
/* Combine quotient halves into final quotient. */
|
|
Packit |
5c3484 |
qh = mpn_lshift (qhp, qhp, nn - dn, GMP_NUMB_BITS/2);
|
|
Packit |
5c3484 |
qh += mpn_add_n (qp, qhp, qlp, nn - dn);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
return qh;
|
|
Packit |
5c3484 |
#else
|
|
Packit |
5c3484 |
return;
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
}
|