[Gmp-commit] /var/hg/gmp: Add side-channel silent mpn division.
mercurial at gmplib.org
mercurial at gmplib.org
Fri Nov 16 18:00:14 CET 2012
details: /var/hg/gmp/rev/63c0ee6b80e1
changeset: 15116:63c0ee6b80e1
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Nov 16 18:00:09 2012 +0100
description:
Add side-channel silent mpn division.
diffstat:
ChangeLog | 7 ++
configure.in | 5 +
gmp-impl.h | 10 ++
mpn/generic/sb_div_sec.c | 112 ++++++++++++++++++++++++++++++++
mpn/generic/sbpi1_div_sec.c | 151 ++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 285 insertions(+), 0 deletions(-)
diffs (truncated from 327 to 300 lines):
diff -r f004194fc431 -r 63c0ee6b80e1 ChangeLog
--- a/ChangeLog Thu Nov 15 19:31:01 2012 +0100
+++ b/ChangeLog Fri Nov 16 18:00:09 2012 +0100
@@ -1,3 +1,10 @@
+2012-11-16 Torbjorn Granlund <tege at gmplib.org>
+
+ * mpn/generic/sb_div_sec.c: New file.
+ * mpn/generic/sbpi1_div_sec.c: New file.
+ * configure.in (gmp_mpn_functions): Add new files.
+ * gmp-impl.h: Declare new functions.
+
2012-11-12 Torbjorn Granlund <tege at gmplib.org>
* longlong.h: Add ARM64 support.
diff -r f004194fc431 -r 63c0ee6b80e1 configure.in
--- a/configure.in Thu Nov 15 19:31:01 2012 +0100
+++ b/configure.in Fri Nov 16 18:00:09 2012 +0100
@@ -2681,6 +2681,7 @@
mu_bdiv_q mu_bdiv_qr \
bdiv_q bdiv_qr broot brootinv bsqrt bsqrtinv \
divexact bdiv_dbm1c redc_1 redc_2 redc_n powm powlo powm_sec \
+ sb_div_qr_sec sb_div_r_sec sbpi1_div_qr_sec sbpi1_div_r_sec \
trialdiv remove \
and_n andn_n nand_n ior_n iorn_n nior_n xor_n xnor_n \
copyi copyd zero tabselect \
@@ -2724,6 +2725,10 @@
tmp_mulfunc="aorrlsh_n sorrlsh_n";;
rsh1add_n|rsh1sub_n)
tmp_mulfunc="rsh1aors_n";;
+ sb_div_qr_sec|sb_div_r_sec)
+ tmp_mulfunc="sb_div_sec";;
+ sbpi1_div_qr_sec|sbpi1_div_r_sec)
+ tmp_mulfunc="sbpi1_div_sec";;
esac
])
diff -r f004194fc431 -r 63c0ee6b80e1 gmp-impl.h
--- a/gmp-impl.h Thu Nov 15 19:31:01 2012 +0100
+++ b/gmp-impl.h Fri Nov 16 18:00:09 2012 +0100
@@ -1559,6 +1559,16 @@
#define mpn_subcnd_n __MPN(subcnd_n)
__GMP_DECLSPEC mp_limb_t mpn_subcnd_n (mp_ptr, mp_srcptr, mp_srcptr, mp_size_t, mp_limb_t);
+#define mpn_sb_div_qr_sec __MPN(sb_div_qr_sec)
+__GMP_DECLSPEC void mpn_sb_div_qr_sec (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
+#define mpn_sbpi1_div_qr_sec __MPN(sbpi1_div_qr_sec)
+__GMP_DECLSPEC mp_limb_t mpn_sbpi1_div_qr_sec (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr);
+#define mpn_sb_div_r_sec __MPN(sb_div_r_sec)
+__GMP_DECLSPEC void mpn_sb_div_r_sec (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
+#define mpn_sbpi1_div_r_sec __MPN(sbpi1_div_r_sec)
+__GMP_DECLSPEC void mpn_sbpi1_div_r_sec (mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_limb_t, mp_ptr);
+
+
#ifndef DIVEXACT_BY3_METHOD
#if GMP_NUMB_BITS % 2 == 0 && ! defined (HAVE_NATIVE_mpn_divexact_by3c)
#define DIVEXACT_BY3_METHOD 0 /* default to using mpn_bdiv_dbm1c */
diff -r f004194fc431 -r 63c0ee6b80e1 mpn/generic/sb_div_sec.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/sb_div_sec.c Fri Nov 16 18:00:09 2012 +0100
@@ -0,0 +1,112 @@
+/* mpn_sb_div_qr_sec, mpn_sb_div_r_sec -- Compute Q = floor(U / V), U = U mod
+ V. Side-channel silent under the assumption that the used instructions are
+ side-channel silent.
+
+ Contributed to the GNU project by Torbjorn Granlund.
+
+ THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES. IT IS ONLY
+ SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
+ GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
+
+Copyright 2011, 2012 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify it
+under the terms of the GNU Lesser General Public License as published by the
+Free Software Foundation; either version 3 of the License, or (at your option)
+any later version.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
+for more details.
+
+You should have received a copy of the GNU Lesser General Public License along
+with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+#include "longlong.h"
+
+#if OPERATION_sb_div_qr_sec
+/* Needs (nn + dn + 1) + mpn_sbpi1_div_qr_sec's needs of (2nn' - dn + 1) for a
+ total of 3nn + 4 limbs at tp. Note that mpn_sbpi1_div_qr_sec's nn is one
+ greater than ours, therefore +4 and not just +2. */
+#define FNAME mpn_sb_div_qr_sec
+#define Q(q) q,
+#endif
+#if OPERATION_sb_div_r_sec
+/* Needs (nn + dn + 1) + mpn_sbpi1_div_r_sec's needs of (dn + 1) for a total of
+ nn + 2dn + 2 limbs at tp. */
+#define FNAME mpn_sb_div_r_sec
+#define Q(q)
+#endif
+
+void
+FNAME (Q(mp_ptr qp)
+ mp_ptr np, mp_size_t nn,
+ mp_srcptr dp, mp_size_t dn,
+ mp_ptr tp)
+{
+ mp_limb_t d1, d0, qh;
+ unsigned int cnt;
+ mp_ptr np2, dp2;
+ gmp_pi1_t dinv;
+ mp_limb_t inv32;
+ mp_limb_t cy;
+
+ ASSERT (dn >= 1);
+ ASSERT (nn >= dn);
+ ASSERT (dp[dn - 1] != 0);
+
+ d1 = dp[dn - 1];
+ count_leading_zeros (cnt, d1);
+
+ if (cnt != 0)
+ {
+ dp2 = tp; /* dn limbs */
+ mpn_lshift (dp2, dp, dn, cnt);
+
+ np2 = tp + dn; /* (nn + 1) limbs */
+ cy = mpn_lshift (np2, np, nn, cnt);
+ np2[nn++] = cy;
+ }
+ else
+ {
+ /* FIXME: Consider copying np->np2 here, adding a 0-limb at the top.
+ That would simplify the underlying sbpi1 function, since then it
+ could assume nn > dn. */
+ dp2 = (mp_ptr) dp;
+ np2 = np;
+ }
+
+ if (dn == 1)
+ {
+ d0 = dp2[dn - 1];
+ invert_limb (inv32, d0);
+ }
+ else
+ {
+ d1 = dp2[dn - 1];
+ d0 = dp2[dn - 2];
+ invert_pi1 (dinv, d1, d0);
+ inv32 = dinv.inv32;
+ }
+
+#if OPERATION_sb_div_qr_sec
+ qh = mpn_sbpi1_div_qr_sec (qp, np2, nn, dp2, dn, inv32, tp + nn + dn + 1);
+#else
+ mpn_sbpi1_div_r_sec (np2, nn, dp2, dn, inv32, tp + nn + dn + 1);
+#endif
+
+ if (cnt == 0)
+ ; /* we have np = np2 here. */
+ else
+ mpn_rshift (np, np2, dn, cnt);
+
+#if OPERATION_sb_div_qr_sec
+ if (cnt == 0)
+ qp[nn - dn] = qh;
+#endif
+}
diff -r f004194fc431 -r 63c0ee6b80e1 mpn/generic/sbpi1_div_sec.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/sbpi1_div_sec.c Fri Nov 16 18:00:09 2012 +0100
@@ -0,0 +1,151 @@
+/* mpn_sbpi1_div_qr_sec, mpn_sbpi1_div_r_sec -- Compute Q = floor(U / V), U = U
+ mod V. Side-channel silent under the assumption that the used instructions
+ are side-channel silent.
+
+ Contributed to the GNU project by Torbjorn Granlund.
+
+ THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES. IT IS ONLY
+ SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
+ GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
+
+Copyright 2011, 2012 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify it
+under the terms of the GNU Lesser General Public License as published by the
+Free Software Foundation; either version 3 of the License, or (at your option)
+any later version.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
+for more details.
+
+You should have received a copy of the GNU Lesser General Public License along
+with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+#include "longlong.h"
+
+#if OPERATION_sbpi1_div_qr_sec
+/* Needs (dn + 1) + (nn - dn) + (nn - dn) = 2nn - dn + 1 limbs at tp. */
+#define FNAME mpn_sbpi1_div_qr_sec
+#define Q(q) q,
+#define RETTYPE mp_limb_t
+#endif
+#if OPERATION_sbpi1_div_r_sec
+/* Needs (dn + 1) limbs at tp. */
+#define FNAME mpn_sbpi1_div_r_sec
+#define Q(q)
+#define RETTYPE void
+#endif
+
+RETTYPE
+FNAME (Q(mp_ptr qp)
+ mp_ptr np, mp_size_t nn,
+ mp_srcptr dp, mp_size_t dn,
+ mp_limb_t dinv,
+ mp_ptr tp)
+{
+ mp_limb_t nh, cy, q1h, q0h, dummy, h;
+ mp_size_t i;
+ mp_ptr hp;
+#if OPERATION_sbpi1_div_qr_sec
+ mp_limb_t qh;
+ mp_ptr qlp, qhp;
+#endif
+
+ ASSERT (dn >= 1);
+ ASSERT (nn >= dn);
+ ASSERT ((dp[dn - 1] & GMP_NUMB_HIGHBIT) != 0);
+
+ if (nn == dn)
+ {
+ cy = mpn_sub_n (np, np, dp, dn);
+ mpn_addcnd_n (np, np, dp, dn, cy);
+#if OPERATION_sbpi1_div_qr_sec
+ return 1 - cy;
+#else
+ return;
+#endif
+ }
+
+ /* Create a divisor copy shifted half a limb. */
+ hp = tp; /* (dn + 1) limbs */
+ cy = mpn_lshift (hp, dp, dn, GMP_NUMB_BITS / 2);
+ hp[dn] = dp[dn - 1] >> GMP_NUMB_BITS / 2;
+
+#if OPERATION_sbpi1_div_qr_sec
+ qlp = tp + (dn + 1); /* (nn - dn) limbs */
+ qhp = tp + (nn + 1); /* (nn - dn) limbs */
+#endif
+
+ np += nn;
+
+ /* Main loop. Develop one full limb per iteration, but do it in two steps in
+ order to avoid conditionals. Quotient bits will be either correct or
+ underestimates. When a quotient is underestimated, the next quotient will
+ compensate, since quotients are to be added at consecutive weight distance
+ GMP_NUMB_BITS/2. We make two quotient arrays, each with GMP_NUMB_BITS/2+2
+ bits per entry. The arrays are added late after the loop. Separate
+ arrays avoid data-dependent carry propagation. */
+ nh = 0;
+ for (i = nn - dn - 1; i >= 0; i--)
+ {
+ np--;
+
+ nh = (nh << GMP_NUMB_BITS/2) + (np[0] >> GMP_NUMB_BITS/2);
+ umul_ppmm (q1h, dummy, nh, dinv);
+ q1h += nh;
+#if OPERATION_sbpi1_div_qr_sec
+ qhp[i] = q1h;
+#endif
+ cy = mpn_submul_1 (np - dn, hp, dn + 1, q1h);
+
+ nh = np[0];
+ umul_ppmm (q0h, dummy, nh, dinv);
+ q0h += nh;
+#if OPERATION_sbpi1_div_qr_sec
+ qlp[i] = q0h;
+#endif
+ cy = mpn_submul_1 (np - dn, dp, dn, q0h);
+
+ nh -= cy;
+ }
+
+ np[0] = nh;
+
+ np -= dn;
+
+ /* 1st adjustment depends on extra high remainder limb. */
+ h = np[dn];
+#if OPERATION_sbpi1_div_qr_sec
More information about the gmp-commit
mailing list