Re: TODO for 5.2 v3

2014-01-16 Thread Torbjorn Granlund 
ni...@lysator.liu.se (Niels Möller) writes:

  Question is, when is it useful for our purposes? First example,
  mpn_sec_add_1:
  
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);
}
  
  volatile probably makes no difference here, as far as I see (except
  possibly if there's some global optimization which inlines mpn_add_n).

I suppose such a hypothetical inline could mess up things, since
mpn_add_n is not required to treat its reads and writes as 'volatile'; A
clever ompiler could analyse the state of {scratch,n} and replace
mpn_add_n by mpn_add_1...

  But maybe we should still declare some or all of the parameters (rp, ap,
  scratch) as pointing to volatile data?
  
I don't see tat making a difference.

  Second example,
  
void
mpn_cnd_swap (mp_limb_t 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;
}
}
  
  Here a compiler might be tempted to do an initial branch on cnd != 0,
  and skip the loop if cnd is false. Using volatile for ap and bp gives it
  less reason to do so, but I guess even with volatile it may still
  generate code equivalent to
  
if (cnd)
  for (i = 0; i  n; i++)
{
  mp_limb_t a, b, t;
  a = ap[i];
  b = bp[i];
  ap[i] = b;
  bp[i] = a;
}
else
  for (i = 0; i  n; i++)
{
  mp_limb_t a, b, t;
  a = ap[i];
  b = bp[i];
  ap[i] = a;
  bp[i] = b;
}
  
  which leaks through the cache.
  
Yes, it leaks through the branch prediction state and the instruction
cache.

  So is it useful or not to volatile-declare ap and bp here?
  
I think so, even if Marc's hypothetical scenario is possible.

In practice, the only real problem is condition-to-mask.  We could solve
that with trivial asm functions (but then, how to we handle
--disable-assembly?).

We might want to bring these issues up with the gcc team.  While
side-channel problems might not be generally appreciated among compiler
hackers, some of them surely will have some understanding of this area.


Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: TODO for 5.2 v3

2014-01-15 Thread Marc Glisse 

On Wed, 15 Jan 2014, Niels Möller wrote:


Torbjorn Granlund t...@gmplib.org writes:


The volatile qualifier makes sure the number of memory reads and memory
writes remain unchanged from the source code.


Question is, when is it useful for our purposes? First example,
mpn_sec_add_1:

 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);
 }

volatile probably makes no difference here, as far as I see (except
possibly if there's some global optimization which inlines mpn_add_n).
But maybe we should still declare some or all of the parameters (rp, ap,
scratch) as pointing to volatile data?


I doubt that it would help, but I could be wrong.


Or would that give type conversion warnings when calling mpn_add_n, with
parameters which aren't volatile-declared? I'm not entirely sure what
volatile means, if it's only giving the compiler some constraints for
the *implementation* of a function, or if volatile in a function
*prototype* also affects type checking or code generation in callers in
some way.



From a type POV, volatile works like 'const', you can't strip it away.



Second example,

 void
 mpn_cnd_swap (mp_limb_t 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;
 }
 }

Here a compiler might be tempted to do an initial branch on cnd != 0,
and skip the loop if cnd is false. Using volatile for ap and bp gives it
less reason to do so, but I guess even with volatile it may still
generate code equivalent to

 if (cnd)
   for (i = 0; i  n; i++)
 {
   mp_limb_t a, b, t;
   a = ap[i];
   b = bp[i];
   ap[i] = b;
   bp[i] = a;
 }
 else
   for (i = 0; i  n; i++)
 {
   mp_limb_t a, b, t;
   a = ap[i];
   b = bp[i];
   ap[i] = a;
   bp[i] = b;
 }

which leaks through the cache.

So is it useful or not to volatile-declare ap and bp here?


volatile mp_limb_t b = cnd != 0;
mp_limb_t mask = -b;

The compiler is still allowed to do b=cnd?1:0 with a branch, but the 
volatile blocks any kind of constant propagation, the compiler can't 
assume that the value it reads from b is in any way related to what it 
just wrote there.


Note that even if mask doesn't come from a condition, the compiler is 
allowed to test if mask is 0 or -1 and generate special code for those 
cases, so you can't escape either writing asm or compiling with 
not-too-extreme optimizations with your fingers crossed.


--
Marc Glisse
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: TODO for 5.2 v3

2014-01-13 Thread Niels Möller 
bodr...@mail.dm.unipi.it writes:

 Ciao,

 Il Mar, 7 Gennaio 2014 4:58 pm, Niels Möller ha scritto:
 Here's a first patch adding a couple of other functions. Benchmarking
 and testing is missing (except that the sec_minvert tests still pass).

 Interesting...

Another thing I was about to ask, but forgot, is use of volatile.

I added it to the mpn_cnd_swap and mpn_sec_eq_ui prototypes, in an
attempt to tell the compiler to not be too clever. But I'm not entirely
sure where it is useful.

 diff -r 84343784aa3d mpn/x86_64/cnd_neg.asm
 --- /dev/nullThu Jan 01 00:00:00 1970 +
 +++ b/mpn/x86_64/cnd_neg.asm Tue Jan 07 15:13:37 2014 +0100

 What about _itch functions when the .asm source is used?

They're supposed to exist, and return zero. E.g.,

+PROLOGUE(mpn_cnd_neg_itch)
+   xor R32(%rax), R32(%rax)
+   ret
+EPILOGUE()

 +C scratch parameter is ignored

 _itch should return 0...

 And some obvious patch like the following would take advantage of this.

Nice, but won't make any difference until we have mpn_sec_add_1
assembly, right?

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: TODO for 5.2 v3

2014-01-07 Thread Niels Möller 
Torbjorn Granlund t...@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 +
+++ 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 +
+++ b/mpn/generic/cnd_swap.cTue 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

Re: TODO for 5.2 v3

2014-01-07 Thread Torbjorn Granlund 
ni...@lysator.liu.se (Niels Möller) writes:

  Torbjorn Granlund t...@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).
  
Thanks!

  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?
  
The return value indeed seems pretty useless, but I am not sure.

A related issue is that we should be nervious about the leakyness of
plain type conditionals such as (cnd != 0) which we use for creating
masks and for forming the mpn_cnd_neg return value.  We might want to
require the cnd arguments to be either 0 or 1.  To some extent this
moves the problem to the caller, but often this will be less of a
problem there.  It may also very slightly reduce overhead.

Torbjörn
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: TODO for 5.2

2014-01-02 Thread Marc Glisse 

Hello,

on my machine, I am getting:

doc/gmp.texi:5807: must be after `@deftypefun' to use `@deftypefunx'

(that's mpn_sec_minvert_itch)
though it looks like it works fine on shell. It is happier if we remove 
the newline in the middle of the @deftypefun.


--
Marc Glisse
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: TODO for 5.2

2013-12-30 Thread Torbjorn Granlund 
ni...@lysator.liu.se (Niels Möller) writes:

  Torbjorn Granlund t...@gmplib.org writes:
  
   I notice you make this non-public.  Is it premature to make it part of
   the public interface?
  
  Pushed now, with declarations moved to gmp-h.in.
  
And now some 450 nightly builds have run successfully.

  I noticed one peculiarity when testing: for m = 1, mpz_invert considers
  every a uninvertible, while mpn_sec_minvert considers every a
  invertible, with inverse 0. The latter is consistent with gcd (a, 1) = 1
  for all a.
  
  Not sure what the common mathematic convention is for the trivial ring
  Z_1 with only a single element, 0 (mod 1).
  
According to http://en.wikipedia.org/wiki/Zero_ring element 0 is a unit.
After all 0 * 0 = 1 ( = 0) which is precicely what ask for from an
inverse.  And since every integer is congruent to 0 in this ring, it
seems that mpn_sec_minvert is right.

Torbjörn
Please encrypt, key id 0xC8601622
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: TODO for 5.2

2013-12-29 Thread Torbjorn Granlund 
ni...@lysator.liu.se (Niels Möller) writes:

   * Finalise and commit mpn_sec_minvert.
  
  Here's a new version, including tests. Seems to work. I'll try to get
  this committed fairly soon.
  
Nice!

I notice you make this non-public.  Is it premature to make it part of
the public interface?

  It would be good to also add some support in speed, so performance can
  be compared easily to gcdext and powm.
  
tune/speed and tests/devel/try support is always good.

The latter tends to find some out-of-bounds writes.

Unfortunately, try.c is messy.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: TODO for 5.2

2013-12-29 Thread Niels Möller 
Torbjorn Granlund t...@gmplib.org writes:

 I notice you make this non-public.  Is it premature to make it part of
 the public interface?

I just put the declarations together with the other mpn_sec_* functions.
I think it makes sense to make mpn_sec_div_*, mpn_sec_minvert and
mpn_sec_powm public together. Does mpn_sec_powm need more work (besides
the rename) before made public?

Also about naming, I noticed the inconsistency between mpz_invert and
mpn_invert, which do very different things. If/when we add an mpz
function corresponding to mpn_sec_minvert, I guess that would be named
mpz_sec_invert?

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel

Re: TODO for 5.2

2013-12-29 Thread Torbjorn Granlund 
ni...@lysator.liu.se (Niels Möller) writes:

  I just put the declarations together with the other mpn_sec_* functions.
  I think it makes sense to make mpn_sec_div_*, mpn_sec_minvert and
  mpn_sec_powm public together. Does mpn_sec_powm need more work (besides
  the rename) before made public?
  
I made it public the other day.  I think its interface need no more
work.  Please pull.

  Also about naming, I noticed the inconsistency between mpz_invert and
  mpn_invert, which do very different things.

Indeed.  But only mpz_invert is public.  (It would have been nice to
have had some mod stuck in there.)

  If/when we add an mpz function corresponding to mpn_sec_minvert, I
  guess that would be named mpz_sec_invert?
  
I suppose.  We should probably already now make mpz_sec_powm and
mpz_powm_sec be aliases.


Torbjörn

___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel