Use SHL{8,32,64} in ed25519/ref10 to avoid left-shifting negative values

This helps us avoid undefined behavior. It's based on a patch from teor,
except that I wrote a perl script to regenerate the patch:

  #!/usr/bin/perl -p -w -i

  BEGIN { %vartypes = (); }

  if (/^[{}]/) {
      %vartypes = ();
  }

  if (/^ *crypto_int(\d+) +([a-zA-Z_][_a-zA-Z0-9]*)/) {
      $vartypes{$2} = $1;
  } elsif (/^ *(?:signed +)char +([a-zA-Z_][_a-zA-Z0-9]*)/) {
      $vartypes{$1} = '8';
  }

  # This fixes at most one shift per line. But that's all the code does.
  if (/([a-zA-Z_][a-zA-Z_0-9]*) *<< *(\d+)/) {
      $v = $1;
      if (exists $vartypes{$v}) {
  	s/$v *<< *(\d+)/SHL$vartypes{$v}($v,$1)/;
      }
  }

  # remove extra parenthesis
  s/\(SHL64\((.*)\)\)/SHL64\($1\)/;
  s/\(SHL32\((.*)\)\)/SHL32\($1\)/;
  s/\(SHL8\((.*)\)\)/SHL8\($1\)/;

1 files changed, 18 insertions, 18 deletions

diff --git a/src/ext/ed25519/ref10/fe_tobytes.c b/src/ext/ed25519/ref10/fe_tobytes.c
index 0a63baf9c1..3c7f389622 100644
--- a/src/ext/ed25519/ref10/fe_tobytes.c
+++ b/src/ext/ed25519/ref10/fe_tobytes.c
@@ -65,16 +65,16 @@ void fe_tobytes(unsigned char *s,const fe h)
   h0 += 19 * q;
   /* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */
 
-  carry0 = h0 >> 26; h1 += carry0; h0 -= carry0 << 26;
-  carry1 = h1 >> 25; h2 += carry1; h1 -= carry1 << 25;
-  carry2 = h2 >> 26; h3 += carry2; h2 -= carry2 << 26;
-  carry3 = h3 >> 25; h4 += carry3; h3 -= carry3 << 25;
-  carry4 = h4 >> 26; h5 += carry4; h4 -= carry4 << 26;
-  carry5 = h5 >> 25; h6 += carry5; h5 -= carry5 << 25;
-  carry6 = h6 >> 26; h7 += carry6; h6 -= carry6 << 26;
-  carry7 = h7 >> 25; h8 += carry7; h7 -= carry7 << 25;
-  carry8 = h8 >> 26; h9 += carry8; h8 -= carry8 << 26;
-  carry9 = h9 >> 25;               h9 -= carry9 << 25;
+  carry0 = h0 >> 26; h1 += carry0; h0 -= SHL32(carry0,26);
+  carry1 = h1 >> 25; h2 += carry1; h1 -= SHL32(carry1,25);
+  carry2 = h2 >> 26; h3 += carry2; h2 -= SHL32(carry2,26);
+  carry3 = h3 >> 25; h4 += carry3; h3 -= SHL32(carry3,25);
+  carry4 = h4 >> 26; h5 += carry4; h4 -= SHL32(carry4,26);
+  carry5 = h5 >> 25; h6 += carry5; h5 -= SHL32(carry5,25);
+  carry6 = h6 >> 26; h7 += carry6; h6 -= SHL32(carry6,26);
+  carry7 = h7 >> 25; h8 += carry7; h7 -= SHL32(carry7,25);
+  carry8 = h8 >> 26; h9 += carry8; h8 -= SHL32(carry8,26);
+  carry9 = h9 >> 25;               h9 -= SHL32(carry9,25);
                   /* h10 = carry9 */
 
   /*
@@ -87,32 +87,32 @@ void fe_tobytes(unsigned char *s,const fe h)
   s[0] = h0 >> 0;
   s[1] = h0 >> 8;
   s[2] = h0 >> 16;
-  s[3] = (h0 >> 24) | (h1 << 2);
+  s[3] = (h0 >> 24) | SHL32(h1,2);
   s[4] = h1 >> 6;
   s[5] = h1 >> 14;
-  s[6] = (h1 >> 22) | (h2 << 3);
+  s[6] = (h1 >> 22) | SHL32(h2,3);
   s[7] = h2 >> 5;
   s[8] = h2 >> 13;
-  s[9] = (h2 >> 21) | (h3 << 5);
+  s[9] = (h2 >> 21) | SHL32(h3,5);
   s[10] = h3 >> 3;
   s[11] = h3 >> 11;
-  s[12] = (h3 >> 19) | (h4 << 6);
+  s[12] = (h3 >> 19) | SHL32(h4,6);
   s[13] = h4 >> 2;
   s[14] = h4 >> 10;
   s[15] = h4 >> 18;
   s[16] = h5 >> 0;
   s[17] = h5 >> 8;
   s[18] = h5 >> 16;
-  s[19] = (h5 >> 24) | (h6 << 1);
+  s[19] = (h5 >> 24) | SHL32(h6,1);
   s[20] = h6 >> 7;
   s[21] = h6 >> 15;
-  s[22] = (h6 >> 23) | (h7 << 3);
+  s[22] = (h6 >> 23) | SHL32(h7,3);
   s[23] = h7 >> 5;
   s[24] = h7 >> 13;
-  s[25] = (h7 >> 21) | (h8 << 4);
+  s[25] = (h7 >> 21) | SHL32(h8,4);
   s[26] = h8 >> 4;
   s[27] = h8 >> 12;
-  s[28] = (h8 >> 20) | (h9 << 6);
+  s[28] = (h8 >> 20) | SHL32(h9,6);
   s[29] = h9 >> 2;
   s[30] = h9 >> 10;
   s[31] = h9 >> 18;