[Gmp-commit] /var/hg/gmp: 4 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Wed Jan 1 22:12:33 UTC 2014
details: /var/hg/gmp/rev/c8008b9007e1
changeset: 16141:c8008b9007e1
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Jan 01 22:50:17 2014 +0100
description:
Fix comment typo.
details: /var/hg/gmp/rev/e6d2867e0002
changeset: 16142:e6d2867e0002
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Jan 01 22:58:18 2014 +0100
description:
Make mpn_sec_div_qr return high quotient limb.
details: /var/hg/gmp/rev/6b0697edb69c
changeset: 16143:6b0697edb69c
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Jan 01 23:10:49 2014 +0100
description:
Doc updates.
details: /var/hg/gmp/rev/16b551cb84cc
changeset: 16144:16b551cb84cc
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Jan 01 23:12:18 2014 +0100
description:
Comment layout.
diffstat:
ChangeLog | 10 +++++++
doc/gmp.texi | 22 ++++++++-------
gmp-h.in | 4 +-
mpn/generic/broot.c | 5 +--
mpn/generic/sec_div.c | 63 ++++++++++++++++++++++++++--------------------
mpn/generic/sec_pi1_div.c | 2 +-
tests/mpn/t-div.c | 4 +-
7 files changed, 65 insertions(+), 45 deletions(-)
diffs (246 lines):
diff -r ffe8c8da8c90 -r 16b551cb84cc ChangeLog
--- a/ChangeLog Wed Jan 01 16:45:58 2014 +0100
+++ b/ChangeLog Wed Jan 01 23:12:18 2014 +0100
@@ -1,3 +1,13 @@
+2014-01-01 Torbjorn Granlund <tege at gmplib.org>
+
+ * doc/gmp.texi (Low-level Functions for cryptography): Update interface
+ for mpn_sec_div_qr and fix typos in mpn_sec_minvert text.
+
+ * mpn/generic/sec_div.c: Rewrite to make mpn_sec_div_qr return high
+ quotient limb.
+ * gmp-h.in (mpn_sec_div_qr): Update declaration.
+ * tests/mpn/t-div.c: Adapt.
+
2013-12-31 Niels Möller <nisse at lysator.liu.se>
* doc/gmp.texi (Low-level Functions for cryptography): Document
diff -r ffe8c8da8c90 -r 16b551cb84cc doc/gmp.texi
--- a/doc/gmp.texi Wed Jan 01 16:45:58 2014 +0100
+++ b/doc/gmp.texi Wed Jan 01 23:12:18 2014 +0100
@@ -5763,14 +5763,14 @@
This function reads the entire table to avoid side-channel information leaks.
@end deftypefun
- at deftypefun void mpn_sec_div_qr (mp_limb_t *@var{qp}, mp_limb_t *@var{np}, mp_size_t @var{nn}, const mp_limb_t *@var{dp}, mp_size_t @var{dn}, mp_limb_t *@var{tp})
+ at deftypefun mp_limb_t mpn_sec_div_qr (mp_limb_t *@var{qp}, mp_limb_t *@var{np}, mp_size_t @var{nn}, const mp_limb_t *@var{dp}, mp_size_t @var{dn}, mp_limb_t *@var{tp})
@deftypefunx mp_size_t mpn_sec_div_qr_itch (mp_size_t @var{nn}, mp_size_t @var{dn})
- at strong{This function's interface is preliminary.}
Set @var{Q} to @m{\lfloor @var{N} / @var{D}\rfloor, the truncated quotient
@var{N} / @var{D}} and @var{R} to @m{@var{N} \bmod @var{D}, @var{N} modulo
@var{D}}, where @var{N} = @{@var{np}, at var{nn}@}, @var{D} =
-@{@var{dp}, at var{dn}@}, @var{Q} = @{@var{qp}, at var{nn-dn+1}@}, and @var{R} =
+@{@var{dp}, at var{dn}@}, @var{Q}'s most significant limb is the function return
+value and the remaining limbs are @{@var{qp}, at var{nn-dn}@}, and @var{R} =
@{@var{np}, at var{dn}@}.
It is required that @math{@var{nn} @ge @var{dn} @ge 1}, and that
@@ -5803,14 +5803,15 @@
@var{dn})} limbs to be passed in the @var{tp} parameter.
@end deftypefun
- at deftypefun int (mp_limb_t *@var{rp}, mp_limb_t *@var{ap}, const mp_limb_t
+ at deftypefun int mpn_sec_minvert (mp_limb_t *@var{rp}, mp_limb_t *@var{ap}, const mp_limb_t
*@var{mp}, mp_size_t @var{n}, mp_bitcnt_t @var{bit_size}, mp_limb_t *@var{tp})
@deftypefunx mp_size_t mpn_sec_minvert_itch (mp_size_t @var{n})
-Set @var{R} to the inverse of @var{A} modulo @var{M}, where @var{R} =
-@{@var{rp}, at var{n}@}, @var{A} = @{@var{ap}, at var{n}@}, and @var{M} = @{@var{mp}, at var{n}@}.
- at strong{This function's interface is preliminary.}
-
-If an inverse exists, returns 1, otherwise returns 0 and leaves @var{R}
+Set @var{R} to @m{@var{A}^{-1} \bmod @var{M}, the inverse of @var{A} modulo
+ at var{M}}, where @var{R} = @{@var{rp}, at var{n}@}, @var{A} = @{@var{ap}, at var{n}@},
+and @var{M} = @{@var{mp}, at var{n}@}. @strong{This function's interface is
+preliminary.}
+
+If an inverse exists, return 1, otherwise return 0 and leave @var{R}
undefined. In either case, the input @var{A} is destroyed.
It is required that @var{M} is odd, and that @var{bit_size} is no smaller than
@@ -5818,7 +5819,8 @@
@var{n} * @code{GMP_NUMB_BITS} is always a safe choice, but smaller values can
be used if @var{M} or @var{A} are known to have leading zero bits.
-This function requires scratch space of @code{mpn_sec_minvert_itch(@var{n})} limbs to be passed in the @var{tp} parameter.
+This function requires scratch space of @code{mpn_sec_minvert_itch(@var{n})}
+limbs to be passed in the @var{tp} parameter.
@end deftypefun
diff -r ffe8c8da8c90 -r 16b551cb84cc gmp-h.in
--- a/gmp-h.in Wed Jan 01 16:45:58 2014 +0100
+++ b/gmp-h.in Wed Jan 01 23:12:18 2014 +0100
@@ -1,6 +1,6 @@
/* Definitions for GNU multiple precision functions. -*- mode: c -*-
-Copyright 1991, 1993-1997, 1999-2013 Free Software Foundation, Inc.
+Copyright 1991, 1993-1997, 1999-2014 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -1645,7 +1645,7 @@
__GMP_DECLSPEC void mpn_sec_tabselect (volatile mp_limb_t *, volatile mp_limb_t *, mp_size_t, mp_size_t, mp_size_t);
#define mpn_sec_div_qr __MPN(sec_div_qr)
-__GMP_DECLSPEC void mpn_sec_div_qr (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
+__GMP_DECLSPEC mp_limb_t mpn_sec_div_qr (mp_ptr, mp_ptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_sec_div_qr_itch __MPN(sec_div_qr_itch)
__GMP_DECLSPEC mp_size_t mpn_sec_div_qr_itch (mp_size_t, mp_size_t);
#define mpn_sec_div_r __MPN(sec_div_r)
diff -r ffe8c8da8c90 -r 16b551cb84cc mpn/generic/broot.c
--- a/mpn/generic/broot.c Wed Jan 01 16:45:58 2014 +0100
+++ b/mpn/generic/broot.c Wed Jan 01 23:12:18 2014 +0100
@@ -142,11 +142,10 @@
{
/* Compute x^{k+1}. */
mpn_sqr (ep, rp, rn); /* For odd n, writes n+1 limbs in the
- final iteration.*/
+ final iteration. */
mpn_powlo (rnp, ep, &kp1h, 1, sizes[i], tp);
- /* Multiply by a^{k-1}. Can use wraparound; low part equals
- r. */
+ /* Multiply by a^{k-1}. Can use wraparound; low part equals r. */
mpn_mullo_n (ep, rnp, akm1, sizes[i]);
ASSERT (mpn_cmp (ep, rp, rn) == 0);
diff -r ffe8c8da8c90 -r 16b551cb84cc mpn/generic/sec_div.c
--- a/mpn/generic/sec_div.c Wed Jan 01 16:45:58 2014 +0100
+++ b/mpn/generic/sec_div.c Wed Jan 01 23:12:18 2014 +0100
@@ -1,14 +1,10 @@
-/* mpn_sec_div_qr, mpn_sec_div_r -- Compute Q = floor(U / V), U = U mod
- V. Side-channel silent under the assumption that the used instructions are
+/* mpn_sec_div_qr, mpn_sec_div_r -- 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 Torbjörn 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-2013 Free Software Foundation, Inc.
+Copyright 2011-2014 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -33,11 +29,13 @@
#define FNAME mpn_sec_div_qr
#define FNAME_itch mpn_sec_div_qr_itch
#define Q(q) q,
+#define RETTYPE mp_limb_t
#endif
#if OPERATION_sec_div_r
#define FNAME mpn_sec_div_r
#define FNAME_itch mpn_sec_div_r_itch
#define Q(q)
+#define RETTYPE void
#endif
mp_size_t
@@ -56,7 +54,7 @@
#endif
}
-void
+RETTYPE
FNAME (Q(mp_ptr qp)
mp_ptr np, mp_size_t nn,
mp_srcptr dp, mp_size_t dn,
@@ -84,6 +82,23 @@
np2 = tp + dn; /* (nn + 1) limbs */
cy = mpn_lshift (np2, np, nn, cnt);
np2[nn++] = cy;
+
+ d0 = dp2[dn - 1];
+ d0 += (~d0 != 0);
+ invert_limb (inv32, d0);
+
+ /* We add nn + dn to tp here, not nn + 1 + dn, as expected. This is
+ since nn here will have been incremented. */
+#if OPERATION_sec_div_qr
+ qh = mpn_sec_pi1_div_qr (np2 + dn, np2, nn, dp2, dn, inv32, tp + nn + dn);
+ ASSERT (qh == 0); /* FIXME: this indicates inefficiency! */
+ MPN_COPY (qp, np2 + dn, nn - dn - 1);
+ qh = np2[nn - 1];
+#else
+ mpn_sec_pi1_div_r (np2, nn, dp2, dn, inv32, tp + nn + dn);
+#endif
+
+ mpn_rshift (np, np2, dn, cnt);
}
else
{
@@ -92,27 +107,21 @@
assume nn > dn. */
dp2 = (mp_ptr) dp;
np2 = np;
+
+ d0 = dp2[dn - 1];
+ d0 += (~d0 != 0);
+ invert_limb (inv32, d0);
+
+ /* We add nn + dn to tp here, not nn + 1 + dn, as expected. This is
+ since nn here will have been incremented. */
+#if OPERATION_sec_div_qr
+ qh = mpn_sec_pi1_div_qr (qp, np2, nn, dp2, dn, inv32, tp + nn + dn);
+#else
+ mpn_sec_pi1_div_r (np2, nn, dp2, dn, inv32, tp + nn + dn);
+#endif
}
- d0 = dp2[dn - 1];
- d0 += (~d0 != 0);
- invert_limb (inv32, d0);
-
- /* We add nn + dn to tp here, not nn + 1 + dn, as expected. This is since nn
- here will have been incremented. */
#if OPERATION_sec_div_qr
- qh = mpn_sec_pi1_div_qr (qp, np2, nn, dp2, dn, inv32, tp + nn + dn);
-#else
- mpn_sec_pi1_div_r (np2, nn, dp2, dn, inv32, tp + nn + dn);
-#endif
-
- if (cnt == 0)
- ; /* we have np = np2 here. */
- else
- mpn_rshift (np, np2, dn, cnt);
-
-#if OPERATION_sec_div_qr
- if (cnt == 0)
- qp[nn - dn] = qh;
+ return qh;
#endif
}
diff -r ffe8c8da8c90 -r 16b551cb84cc mpn/generic/sec_pi1_div.c
--- a/mpn/generic/sec_pi1_div.c Wed Jan 01 16:45:58 2014 +0100
+++ b/mpn/generic/sec_pi1_div.c Wed Jan 01 23:12:18 2014 +0100
@@ -31,7 +31,7 @@
/* This side-channel silent division algorithm reduces the partial remainder by
GMP_NUMB_BITS/2 bits at a time, compared to GMP_NUMB_BITS for the main
- division algorithm. We actually do not insists on reducing by exactly
+ division algorithm. We actually do not insist on reducing by exactly
GMP_NUMB_BITS/2, but may leave a partial remainder that is D*B^i to 3D*B^i
too large (B is the limb base, D is the divisor, and i is the induction
variable); the subsequent step will handle the extra partial remainder bits.
diff -r ffe8c8da8c90 -r 16b551cb84cc tests/mpn/t-div.c
--- a/tests/mpn/t-div.c Wed Jan 01 16:45:58 2014 +0100
+++ b/tests/mpn/t-div.c Wed Jan 01 23:12:18 2014 +0100
@@ -1,4 +1,4 @@
-/* Copyright 2006, 2007, 2009, 2010, 2013 Free Software Foundation, Inc.
+/* Copyright 2006, 2007, 2009, 2010, 2013, 2014 Free Software Foundation, Inc.
This file is part of the GNU MP Library test suite.
@@ -306,7 +306,7 @@
MPN_COPY (rp, np, nn);
if (nn >= dn)
MPN_COPY (qp, junkp, nn - dn + 1);
- mpn_sec_div_qr (qp, rp, nn, dup, dn, scratch);
+ qp[nn - dn] = mpn_sec_div_qr (qp, rp, nn, dup, dn, scratch);
ASSERT_ALWAYS (ran == scratch[itch]);
check_one (qp, rp, np, nn, dup, dn, "mpn_sec_div_qr", 0);
More information about the gmp-commit
mailing list