TODO for 5.2 v3
Niels Möller
nisse at lysator.liu.se
Tue Jan 7 15:58:45 UTC 2014
Torbjorn Granlund <tg at gmplib.org> writes:
> * Make some other sec functions from Niels' list public?
Here's a first patch adding a couple of other functions. Benchmarking
and testing is missing (except that the sec_minvert tests still pass).
One interface question: Return value of cnd_neg. Currently, the
intention is that it should return output borrow if the condition is
true, otherwise zero. Which means that it returns 1 iff cnd != 0 and x
!= 0. It's not clear if that's of any use. Maybe drop the return value?
Regards,
/Niels
diff -r 84343784aa3d configure.ac
--- a/configure.ac Sun Jan 05 18:22:40 2014 +0100
+++ b/configure.ac Tue Jan 07 15:13:37 2014 +0100
@@ -2835,7 +2835,7 @@
bdiv_q bdiv_qr broot brootinv bsqrt bsqrtinv \
divexact bdiv_dbm1c redc_1 redc_2 redc_n powm powlo sec_powm \
sec_mul sec_sqr sec_div_qr sec_div_r sec_pi1_div_qr sec_pi1_div_r \
- sec_minvert \
+ sec_add_1 sec_sub_1 cnd_neg cnd_swap sec_minvert \
trialdiv remove \
and_n andn_n nand_n ior_n iorn_n nior_n xor_n xnor_n \
copyi copyd zero sec_tabselect \
diff -r 84343784aa3d gmp-h.in
--- a/gmp-h.in Sun Jan 05 18:22:40 2014 +0100
+++ b/gmp-h.in Tue Jan 07 15:13:37 2014 +0100
@@ -1629,6 +1629,24 @@
#define mpn_cnd_sub_n __MPN(cnd_sub_n)
__GMP_DECLSPEC mp_limb_t mpn_cnd_sub_n (mp_limb_t, mp_ptr, mp_srcptr, mp_srcptr, mp_size_t);
+#define mpn_cnd_neg __MPN(cnd_neg)
+__GMP_DECLSPEC mp_limb_t mpn_cnd_neg (mp_limb_t, mp_ptr, mp_srcptr, mp_size_t);
+#define mpn_cnd_neg_itch __MPN(cnd_neg_itch)
+__GMP_DECLSPEC mp_size_t mpn_sec_neg_itch (mp_size_t) __GMP_ATTRIBUTE_PURE;
+
+#define mpn_cnd_swap __MPN(cnd_swap)
+__GMP_DECLSPEC void mpn_cnd_swap (mp_limb_t, mp_ptr, mp_ptr, mp_size_t);
+
+#define mpn_sec_add_1 __MPN(sec_add_1)
+__GMP_DECLSPEC mp_limb_t mpn_sec_add_1 (mp_limb_t *, mp_limb_t *, mp_size_t, mp_limb_t, mp_ptr);
+#define mpn_sec_add_1_itch __MPN(sec_add_1_itch)
+__GMP_DECLSPEC mp_size_t mpn_sec_add_1_itch (mp_size_t) __GMP_ATTRIBUTE_PURE;
+
+#define mpn_sec_sub_1 __MPN(sec_sub_1)
+__GMP_DECLSPEC mp_limb_t mpn_sec_sub_1 (mp_limb_t *, mp_limb_t *, mp_size_t, mp_limb_t, mp_ptr);
+#define mpn_sec_sub_1_itch __MPN(sec_sub_1_itch)
+__GMP_DECLSPEC mp_size_t mpn_sec_sub_1_itch (mp_size_t) __GMP_ATTRIBUTE_PURE;
+
#define mpn_sec_mul __MPN(sec_mul)
__GMP_DECLSPEC void mpn_sec_mul (mp_ptr, mp_srcptr, mp_size_t, mp_srcptr, mp_size_t, mp_ptr);
#define mpn_sec_mul_itch __MPN(sec_mul_itch)
diff -r 84343784aa3d mpn/asm-defs.m4
--- a/mpn/asm-defs.m4 Sun Jan 05 18:22:40 2014 +0100
+++ b/mpn/asm-defs.m4 Tue Jan 07 15:13:37 2014 +0100
@@ -1361,6 +1361,8 @@
define_mpn(cmp)
define_mpn(cnd_add_n)
define_mpn(cnd_sub_n)
+define_mpn(cnd_neg)
+define_mpn(cnd_swap)
define_mpn(com)
define_mpn(copyd)
define_mpn(copyi)
@@ -1471,6 +1473,8 @@
define_mpn(sub_nc)
define_mpn(submul_1)
define_mpn(submul_1c)
+define_mpn(sec_add_1)
+define_mpn(sec_sub_1)
define_mpn(sec_tabselect)
define_mpn(umul_ppmm)
define_mpn(umul_ppmm_r)
diff -r 84343784aa3d mpn/generic/cnd_neg.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/cnd_neg.c Tue Jan 07 15:13:37 2014 +0100
@@ -0,0 +1,38 @@
+/* mpn_cnd_neg
+
+ Contributed to the GNU project by Niels Möller
+
+Copyright 2013, 2014 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 https://www.gnu.org/licenses/. */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+
+mp_size_t
+mpn_cnd_neg_itch (mp_size_t n)
+{
+ return n;
+}
+
+mp_limb_t
+mpn_cnd_neg (mp_limb_t cnd, mp_ptr rp, mp_srcptr ap, mp_size_t n,
+ mp_ptr scratch)
+{
+ mp_limb_t hi = mpn_lshift (scratch, ap, n, 1);
+ mp_limb_t cy = mpn_cnd_sub_n (cnd, rp, ap, scratch, n);
+ return cy + (hi & (cnd != 0));
+}
diff -r 84343784aa3d mpn/generic/cnd_swap.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/cnd_swap.c Tue Jan 07 15:13:37 2014 +0100
@@ -0,0 +1,40 @@
+/* mpn_cnd_swap
+
+ Contributed to the GNU project by Niels Möller
+
+Copyright 2013, 2014 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 https://www.gnu.org/licenses/. */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+
+void
+mpn_cnd_swap (mp_limb_t cnd,
+ volatile mp_limb_t *ap, volatile mp_limb_t *bp, mp_size_t n)
+{
+ mp_limb_t mask = - (mp_limb_t) (cnd != 0);
+ mp_size_t i;
+ for (i = 0; i < n; i++)
+ {
+ mp_limb_t a, b, t;
+ a = ap[i];
+ b = bp[i];
+ t = (a ^ b) & mask;
+ ap[i] = a ^ t;
+ bp[i] = b ^ t;
+ }
+}
diff -r 84343784aa3d mpn/generic/sec_add_1.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/sec_add_1.c Tue Jan 07 15:13:37 2014 +0100
@@ -0,0 +1,39 @@
+/* mpn_sec_add_1
+
+ Contributed to the GNU project by Niels Möller
+
+Copyright 2013, 2014 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 https://www.gnu.org/licenses/. */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+
+/* It's annoying to that we need scratch space */
+mp_size_t
+mpn_sec_add_1_itch (mp_size_t n)
+{
+ return n;
+}
+
+mp_limb_t
+mpn_sec_add_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b,
+ mp_ptr scratch)
+{
+ scratch[0] = b;
+ MPN_ZERO (scratch + 1, n-1);
+ return mpn_add_n (rp, ap, scratch, n);
+}
diff -r 84343784aa3d mpn/generic/sec_minvert.c
--- a/mpn/generic/sec_minvert.c Sun Jan 05 18:22:40 2014 +0100
+++ b/mpn/generic/sec_minvert.c Tue Jan 07 15:13:37 2014 +0100
@@ -22,54 +22,8 @@
#include "gmp.h"
#include "gmp-impl.h"
-static mp_size_t
-mpn_sec_add_1_itch (mp_size_t n)
-{
- return n;
-}
-
-static mp_limb_t
-mpn_sec_add_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b,
- mp_ptr scratch)
-{
- scratch[0] = b;
- MPN_ZERO (scratch + 1, n-1);
- return mpn_add_n (rp, ap, scratch, n);
-}
-
-static mp_size_t
-mpn_cnd_neg_itch (mp_size_t n)
-{
- return n;
-}
-
-/* FIXME: Ought to return carry */
-static void
-mpn_cnd_neg (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n,
- mp_ptr scratch)
-{
- mpn_lshift (scratch, ap, n, 1);
- mpn_cnd_sub_n (cnd, rp, ap, scratch, n);
-}
-
-static void
-mpn_cnd_swap (int cnd, mp_limb_t *ap, mp_limb_t *bp, mp_size_t n)
-{
- mp_limb_t mask = - (mp_limb_t) (cnd != 0);
- mp_size_t i;
- for (i = 0; i < n; i++)
- {
- mp_limb_t a, b, t;
- a = ap[i];
- b = bp[i];
- t = (a ^ b) & mask;
- ap[i] = a ^ t;
- bp[i] = b ^ t;
- }
-}
-
static int
-mpn_sec_eq_ui (mp_srcptr ap, mp_size_t n, mp_limb_t b)
+mpn_sec_eq_ui (volatile const mp_limb_t *ap, mp_size_t n, mp_limb_t b)
{
mp_limb_t d;
ASSERT (n > 0);
diff -r 84343784aa3d mpn/generic/sec_sub_1.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/sec_sub_1.c Tue Jan 07 15:13:37 2014 +0100
@@ -0,0 +1,39 @@
+/* mpn_sec_sub_1
+
+ Contributed to the GNU project by Niels Möller
+
+Copyright 2013, 2014 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 https://www.gnu.org/licenses/. */
+
+#include "gmp.h"
+#include "gmp-impl.h"
+
+/* It's annoying to that we need scratch space */
+mp_size_t
+mpn_sec_sub_1_itch (mp_size_t n)
+{
+ return n;
+}
+
+mp_limb_t
+mpn_sec_sub_1 (mp_limb_t *rp, mp_limb_t *ap, mp_size_t n, mp_limb_t b,
+ mp_ptr scratch)
+{
+ scratch[0] = b;
+ MPN_ZERO (scratch + 1, n-1);
+ return mpn_sub_n (rp, ap, scratch, n);
+}
diff -r 84343784aa3d mpn/x86_64/cnd_neg.asm
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/x86_64/cnd_neg.asm Tue Jan 07 15:13:37 2014 +0100
@@ -0,0 +1,66 @@
+dnl AMD64 mpn_cnd_neg
+
+dnl Copyright 2014 Free Software Foundation, Inc.
+
+dnl This file is part of the GNU MP Library.
+
+dnl The GNU MP Library is free software; you can redistribute it and/or modify
+dnl it under the terms of the GNU Lesser General Public License as published
+dnl by the Free Software Foundation; either version 3 of the License, or (at
+dnl your option) any later version.
+
+dnl The GNU MP Library is distributed in the hope that it will be useful, but
+dnl WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+dnl or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+dnl License for more details.
+
+dnl You should have received a copy of the GNU Lesser General Public License
+dnl along with the GNU MP Library. If not, see https://www.gnu.org/licenses/.
+
+include(`../config.m4')
+
+C INPUT PARAMETERS
+define(`cnd', `%rdi') dnl rcx
+define(`rp', `%rsi') dnl rdx
+define(`up', `%rdx') dnl r8
+define(`n', `%rcx') dnl r9
+C scratch parameter is ignored
+
+ABI_SUPPORT(DOS64)
+ABI_SUPPORT(STD64)
+
+ASM_START()
+ TEXT
+ ALIGN(16)
+PROLOGUE(mpn_cnd_neg)
+ FUNC_ENTRY(4)
+
+ lea (up,n,8), up
+ lea (rp,n,8), rp
+
+ neg n
+
+ neg cnd
+ sbb cnd, cnd C make cnd mask, also copy to cy
+
+L(loop):
+ mov (up, n, 8), %r8
+ sbb R32(%rax), R32(%rax) C Save carry
+ xor cnd, %r8 C Clears carry, very annoying.
+ add R32(%rax), R32(%rax) C Restore carry
+ adc $0, %r8
+ mov %r8, (rp, n, 8)
+ inc n
+ jne L(loop)
+ C Generate carry out, if cnd and x != 0
+ inc R32(%rax)
+ and R32(cnd), R32(%rax)
+ FUNC_EXIT()
+ ret
+EPILOGUE()
+
+
+PROLOGUE(mpn_cnd_neg_itch)
+ xor R32(%rax), R32(%rax)
+ ret
+EPILOGUE()
diff -r 84343784aa3d mpn/x86_64/cnd_swap.asm
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/x86_64/cnd_swap.asm Tue Jan 07 15:13:37 2014 +0100
@@ -0,0 +1,61 @@
+dnl AMD64 mpn_cnd_swap
+
+dnl Copyright 2014 Free Software Foundation, Inc.
+
+dnl This file is part of the GNU MP Library.
+
+dnl The GNU MP Library is free software; you can redistribute it and/or modify
+dnl it under the terms of the GNU Lesser General Public License as published
+dnl by the Free Software Foundation; either version 3 of the License, or (at
+dnl your option) any later version.
+
+dnl The GNU MP Library is distributed in the hope that it will be useful, but
+dnl WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+dnl or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+dnl License for more details.
+
+dnl You should have received a copy of the GNU Lesser General Public License
+dnl along with the GNU MP Library. If not, see https://www.gnu.org/licenses/.
+
+include(`../config.m4')
+
+C INPUT PARAMETERS
+define(`cnd', `%rdi') dnl rcx
+define(`up', `%rsi') dnl rdx
+define(`vp', `%rdx') dnl r8
+define(`n', `%rcx') dnl r9
+C scratch parameter is ignored
+
+ABI_SUPPORT(DOS64)
+ABI_SUPPORT(STD64)
+
+ASM_START()
+ TEXT
+ ALIGN(16)
+PROLOGUE(mpn_cnd_swap)
+ FUNC_ENTRY(4)
+
+ neg cnd
+ sbb cnd, cnd C make cnd mask
+
+ lea (up,n,8), up
+ lea (vp,n,8), vp
+
+ neg n
+
+L(loop):
+ mov (up, n, 8), %r8
+ mov (vp, n, 8), %r9
+ mov %r8, %r10
+ xor %r9, %r8
+ and cnd, %r8
+ xor %r8, %r10
+ xor %r8, %r9
+ mov %r10, (up, n, 8)
+ mov %r9, (vp, n, 8)
+ inc n
+ jne L(loop)
+
+ FUNC_EXIT()
+ ret
+EPILOGUE()
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list