bug fixes
authorWerner Koch <wk@gnupg.org>
Wed, 11 Feb 1998 23:22:05 +0000 (23:22 +0000)
committerWerner Koch <wk@gnupg.org>
Wed, 11 Feb 1998 23:22:05 +0000 (23:22 +0000)
cipher/elgamal.c
cipher/md.c
cipher/md.h
mpi/alpha/README [new file with mode: 0644]
mpi/alpha/distfiles
mpi/alpha/mpih-add1.S [new file with mode: 0644]
mpi/alpha/mpih-shift.S [new file with mode: 0644]

index 13b8579..6defbc5 100644 (file)
@@ -322,6 +322,16 @@ elg_verify(MPI a, MPI b, MPI input, ELG_public_key *pkey )
 
   #if 0
     /* t1 = (y^a mod p) * (a^b mod p) mod p */
+    mpi_powm( t1, pkey->y, a, pkey->p );
+    mpi_powm( t2, a, b, pkey->p );
+    mpi_mulm( t1, t1, t2, pkey->p );
+
+    /* t2 = g ^ input mod p */
+    mpi_powm( t2, pkey->g, input, pkey->p );
+
+    rc = !mpi_cmp( t1, t2 );
+  #elif 0
+    /* t1 = (y^a mod p) * (a^b mod p) mod p */
     base[0] = pkey->y; exp[0] = a;
     base[1] = a;       exp[1] = b;
     base[2] = NULL;    exp[2] = NULL;
index c89c8bb..c87f328 100644 (file)
@@ -28,7 +28,7 @@
 #include "errors.h"
 
 
-static FILE *dumpfp;
+/*static FILE *dumpfp;*/
 
 /****************
  * Open a message digest handle for use with algorithm ALGO.
@@ -40,14 +40,16 @@ md_open( int algo, int secure )
 {
     MD_HANDLE hd;
 
+   #if 0
     if( !dumpfp )
        dumpfp = fopen("md.out", "w");
     if( !dumpfp )
        BUG();
     { int i; for(i=0; i < 16; i++ ) putc('\xff', dumpfp ); }
-
+   #endif
     hd = secure ? m_alloc_secure_clear( sizeof *hd )
                : m_alloc_clear( sizeof *hd );
+    hd->secure = secure;
     if( algo )
        md_enable( hd, algo );
     return hd;
@@ -78,9 +80,9 @@ md_copy( MD_HANDLE a )
 {
     MD_HANDLE b;
 
-    { int i; for(i=0; i < 16; i++ ) putc('\xee', dumpfp ); }
-    b = m_is_secure(a)? m_alloc_secure( sizeof *b )
-                     : m_alloc( sizeof *b );
+    /*{ int i; for(i=0; i < 16; i++ ) putc('\xee', dumpfp ); }*/
+    b = a->secure ? m_alloc_secure( sizeof *b )
+                 : m_alloc( sizeof *b );
     memcpy( b, a, sizeof *a );
     return b;
 }
@@ -98,10 +100,10 @@ md_close(MD_HANDLE a)
 void
 md_write( MD_HANDLE a, byte *inbuf, size_t inlen)
 {
-    if( a->bufcount && fwrite(a->buffer, a->bufcount, 1, dumpfp ) != 1 )
+  /*  if( a->bufcount && fwrite(a->buffer, a->bufcount, 1, dumpfp ) != 1 )
        BUG();
     if( inlen && fwrite(inbuf, inlen, 1, dumpfp ) != 1 )
-       BUG();
+       BUG(); */
     if( a->use_rmd160 ) {
        rmd160_write( &a->rmd160, a->buffer, a->bufcount );
        rmd160_write( &a->rmd160, inbuf, inlen  );
@@ -124,7 +126,7 @@ md_final(MD_HANDLE a)
 {
     if( a->bufcount )
        md_write( a, NULL, 0 );
-    { int i; for(i=0; i < 16; i++ ) putc('\xcc', dumpfp ); }
+    /*{ int i; for(i=0; i < 16; i++ ) putc('\xcc', dumpfp ); }*/
     if( a->use_rmd160 ) {
        byte *p;
        rmd160_final( &a->rmd160 );
index 8a7886d..7a710e7 100644 (file)
@@ -36,6 +36,7 @@ typedef struct {
     MD5_CONTEXT md5;
     byte buffer[MD_BUFFER_SIZE]; /* primary buffer */
     int  bufcount;
+    int  secure;
 } *MD_HANDLE;
 
 
@@ -55,6 +56,6 @@ void md_write( MD_HANDLE a, byte *inbuf, size_t inlen);
 void md_final(MD_HANDLE a);
 byte *md_read( MD_HANDLE a, int algo );
 int md_get_algo( MD_HANDLE a );
-
+#define md_is_secure(a) ((a)->secure)
 
 #endif /*G10_MD_H*/
diff --git a/mpi/alpha/README b/mpi/alpha/README
new file mode 100644 (file)
index 0000000..55c0a29
--- /dev/null
@@ -0,0 +1,53 @@
+This directory contains mpn functions optimized for DEC Alpha processors.
+
+RELEVANT OPTIMIZATION ISSUES
+
+EV4
+
+1. This chip has very limited store bandwidth.  The on-chip L1 cache is
+write-through, and a cache line is transfered from the store buffer to the
+off-chip L2 in as much 15 cycles on most systems.  This delay hurts
+mpn_add_n, mpn_sub_n, mpn_lshift, and mpn_rshift.
+
+2. Pairing is possible between memory instructions and integer arithmetic
+instructions.
+
+3. mulq and umulh is documented to have a latency of 23 cycles, but 2 of
+these cycles are pipelined.  Thus, multiply instructions can be issued at a
+rate of one each 21nd cycle.
+
+EV5
+
+1. The memory bandwidth of this chip seems excellent, both for loads and
+stores.  Even when the working set is larger than the on-chip L1 and L2
+caches, the perfromance remain almost unaffected.
+
+2. mulq has a measured latency of 13 cycles and an issue rate of 1 each 8th
+cycle.  umulh has a measured latency of 15 cycles and an issue rate of 1
+each 10th cycle.  But the exact timing is somewhat confusing.
+
+3. mpn_add_n.  With 4-fold unrolling, we need 37 instructions, whereof 12
+   are memory operations.  This will take at least
+       ceil(37/2) [dual issue] + 1 [taken branch] = 20 cycles
+   We have 12 memory cycles, plus 4 after-store conflict cycles, or 16 data
+   cache cycles, which should be completely hidden in the 20 issue cycles.
+   The computation is inherently serial, with these dependencies:
+     addq
+     /   \
+   addq  cmpult
+     |     |
+   cmpult  |
+       \  /
+        or
+   I.e., there is a 4 cycle path for each limb, making 16 cycles the absolute
+   minimum.  We could replace the `or' with a cmoveq/cmovne, which would save
+   a cycle on EV5, but that might waste a cycle on EV4.  Also, cmov takes 2
+   cycles.
+     addq
+     /   \
+   addq  cmpult
+     |      \
+   cmpult -> cmovne
+
+STATUS
+
index 4dd0ffe..e92d183 100644 (file)
@@ -1,3 +1,6 @@
+README
+mpih-add1.S
+mpih-shift.S
 
 udiv-qrnnd.S
 
diff --git a/mpi/alpha/mpih-add1.S b/mpi/alpha/mpih-add1.S
new file mode 100644 (file)
index 0000000..6f88499
--- /dev/null
@@ -0,0 +1,134 @@
+/* alpha  add_n -- Add two limb vectors of the same length > 0 and store
+ *                sum in a third limb vector.
+ *
+ *     Copyright (C) 1995 Free Software Foundation, Inc.
+ *     Copyright (c) 1997 by Werner Koch (dd9jn)
+ *
+ * This file is part of G10.
+ *
+ * G10 is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * G10 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+
+
+/*******************
+ *  mpi_limb_t
+ *  mpihelp_add_n( mpi_ptr_t res_ptr,  ($16)
+ *                mpi_ptr_t s1_ptr,    ($17)
+ *                mpi_ptr_t s2_ptr,    ($18)
+ *                mpi_size_t size)     ($19)
+ */
+
+
+       .set    noreorder
+       .set    noat
+.text
+       .align  3
+       .globl  mpihelp_add_n
+       .ent    mpihelp_add_n
+mpihelp_add_n:
+       .frame  $30,0,$26,0
+
+       ldq     $3,0($17)
+       ldq     $4,0($18)
+
+       subq    $19,1,$19
+       and     $19,4-1,$2      # number of limbs in first loop
+       bis     $31,$31,$0
+       beq     $2,.L0          # if multiple of 4 limbs, skip first loop
+
+       subq    $19,$2,$19
+
+.Loop0: subq   $2,1,$2
+       ldq     $5,8($17)
+       addq    $4,$0,$4
+       ldq     $6,8($18)
+       cmpult  $4,$0,$1
+       addq    $3,$4,$4
+       cmpult  $4,$3,$0
+       stq     $4,0($16)
+       or      $0,$1,$0
+
+       addq    $17,8,$17
+       addq    $18,8,$18
+       bis     $5,$5,$3
+       bis     $6,$6,$4
+       addq    $16,8,$16
+       bne     $2,.Loop0
+
+.L0:   beq     $19,.Lend
+
+       .align  3
+.Loop: subq    $19,4,$19
+
+       ldq     $5,8($17)
+       addq    $4,$0,$4
+       ldq     $6,8($18)
+       cmpult  $4,$0,$1
+       addq    $3,$4,$4
+       cmpult  $4,$3,$0
+       stq     $4,0($16)
+       or      $0,$1,$0
+
+       ldq     $3,16($17)
+       addq    $6,$0,$6
+       ldq     $4,16($18)
+       cmpult  $6,$0,$1
+       addq    $5,$6,$6
+       cmpult  $6,$5,$0
+       stq     $6,8($16)
+       or      $0,$1,$0
+
+       ldq     $5,24($17)
+       addq    $4,$0,$4
+       ldq     $6,24($18)
+       cmpult  $4,$0,$1
+       addq    $3,$4,$4
+       cmpult  $4,$3,$0
+       stq     $4,16($16)
+       or      $0,$1,$0
+
+       ldq     $3,32($17)
+       addq    $6,$0,$6
+       ldq     $4,32($18)
+       cmpult  $6,$0,$1
+       addq    $5,$6,$6
+       cmpult  $6,$5,$0
+       stq     $6,24($16)
+       or      $0,$1,$0
+
+       addq    $17,32,$17
+       addq    $18,32,$18
+       addq    $16,32,$16
+       bne     $19,.Loop
+
+.Lend: addq    $4,$0,$4
+       cmpult  $4,$0,$1
+       addq    $3,$4,$4
+       cmpult  $4,$3,$0
+       stq     $4,0($16)
+       or      $0,$1,$0
+       ret     $31,($26),1
+
+       .end    mpihelp_add_n
+
diff --git a/mpi/alpha/mpih-shift.S b/mpi/alpha/mpih-shift.S
new file mode 100644 (file)
index 0000000..dcf0a1f
--- /dev/null
@@ -0,0 +1,213 @@
+/* alpha    rshift, lshift
+ *     Copyright (C) 1994, 1995 Free Software Foundation, Inc.
+ *     Copyright (c) 1997 by Werner Koch (dd9jn)
+ *
+ * This file is part of G10.
+ *
+ * G10 is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * G10 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+ *
+ * Note: This code is heavily based on the GNU MP Library.
+ *      Actually it's the same code with only minor changes in the
+ *      way the data is stored; this is to support the abstraction
+ *      of an optional secure memory allocation which may be used
+ *      to avoid revealing of sensitive data due to paging etc.
+ *      The GNU MP Library itself is published under the LGPL;
+ *      however I decided to publish this code under the plain GPL.
+ */
+
+
+
+/*******************
+ * mpi_limb_t
+ * mpihelp_lshift( mpi_ptr_t wp,       (r16)
+ *                mpi_ptr_t up,        (r17)
+ *                mpi_size_t usize,    (r18)
+ *                unsigned cnt)        (r19)
+ *
+ * This code runs at 4.8 cycles/limb on the 21064.  With infinite unrolling,
+ * it would take 4 cycles/limb.  It should be possible to get down to 3
+ * cycles/limb since both ldq and stq can be paired with the other used
+ * instructions.  But there are many restrictions in the 21064 pipeline that
+ * makes it hard, if not impossible, to get down to 3 cycles/limb:
+ *
+ * 1. ldq has a 3 cycle delay, srl and sll have a 2 cycle delay.
+ * 2. Only aligned instruction pairs can be paired.
+ * 3. The store buffer or silo might not be able to deal with the bandwidth.
+ */
+
+       .set    noreorder
+       .set    noat
+.text
+       .align  3
+       .globl  mpihelp_lshift
+       .ent    mpihelp_lshift
+mpihelp_lshift:
+       .frame  $30,0,$26,0
+
+       s8addq  $18,$17,$17     # make r17 point at end of s1
+       ldq     $4,-8($17)      # load first limb
+       subq    $17,8,$17
+       subq    $31,$19,$7
+       s8addq  $18,$16,$16     # make r16 point at end of RES
+       subq    $18,1,$18
+       and     $18,4-1,$20     # number of limbs in first loop
+       srl     $4,$7,$0        # compute function result
+
+       beq     $20,.L0
+       subq    $18,$20,$18
+
+       .align  3
+.Loop0:
+       ldq     $3,-8($17)
+       subq    $16,8,$16
+       subq    $17,8,$17
+       subq    $20,1,$20
+       sll     $4,$19,$5
+       srl     $3,$7,$6
+       bis     $3,$3,$4
+       bis     $5,$6,$8
+       stq     $8,0($16)
+       bne     $20,.Loop0
+
+.L0:   beq     $18,.Lend
+
+       .align  3
+.Loop: ldq     $3,-8($17)
+       subq    $16,32,$16
+       subq    $18,4,$18
+       sll     $4,$19,$5
+       srl     $3,$7,$6
+
+       ldq     $4,-16($17)
+       sll     $3,$19,$1
+       bis     $5,$6,$8
+       stq     $8,24($16)
+       srl     $4,$7,$2
+
+       ldq     $3,-24($17)
+       sll     $4,$19,$5
+       bis     $1,$2,$8
+       stq     $8,16($16)
+       srl     $3,$7,$6
+
+       ldq     $4,-32($17)
+       sll     $3,$19,$1
+       bis     $5,$6,$8
+       stq     $8,8($16)
+       srl     $4,$7,$2
+
+       subq    $17,32,$17
+       bis     $1,$2,$8
+       stq     $8,0($16)
+
+       bgt     $18,.Loop
+
+.Lend: sll     $4,$19,$8
+       stq     $8,-8($16)
+       ret     $31,($26),1
+       .end    mpihelp_lshift
+
+
+
+
+
+/*******************
+ * mpi_limb_t
+ * mpihelp_rshift( mpi_ptr_t wp,       (r16)
+ *                mpi_ptr_t up,        (r17)
+ *                mpi_size_t usize,    (r18)
+ *                unsigned cnt)        (r19)
+ *
+ * This code runs at 4.8 cycles/limb on the 21064.  With infinite unrolling,
+ * it would take 4 cycles/limb.  It should be possible to get down to 3
+ * cycles/limb since both ldq and stq can be paired with the other used
+ * instructions.  But there are many restrictions in the 21064 pipeline that
+ * makes it hard, if not impossible, to get down to 3 cycles/limb:
+ *
+ * 1. ldq has a 3 cycle delay, srl and sll have a 2 cycle delay.
+ * 2. Only aligned instruction pairs can be paired.
+ * 3. The store buffer or silo might not be able to deal with the bandwidth.
+ */
+
+       .set    noreorder
+       .set    noat
+.text
+       .align  3
+       .globl  mpihelp_rshift
+       .ent    mpihelp_rshift
+mpihelp_rshift:
+       .frame  $30,0,$26,0
+
+       ldq     $4,0($17)       # load first limb
+       addq    $17,8,$17
+       subq    $31,$19,$7
+       subq    $18,1,$18
+       and     $18,4-1,$20     # number of limbs in first loop
+       sll     $4,$7,$0        # compute function result
+
+       beq     $20,.R0
+       subq    $18,$20,$18
+
+       .align  3
+.Roop0:
+       ldq     $3,0($17)
+       addq    $16,8,$16
+       addq    $17,8,$17
+       subq    $20,1,$20
+       srl     $4,$19,$5
+       sll     $3,$7,$6
+       bis     $3,$3,$4
+       bis     $5,$6,$8
+       stq     $8,-8($16)
+       bne     $20,.Roop0
+
+.R0:   beq     $18,.Rend
+
+       .align  3
+.Roop: ldq     $3,0($17)
+       addq    $16,32,$16
+       subq    $18,4,$18
+       srl     $4,$19,$5
+       sll     $3,$7,$6
+
+       ldq     $4,8($17)
+       srl     $3,$19,$1
+       bis     $5,$6,$8
+       stq     $8,-32($16)
+       sll     $4,$7,$2
+
+       ldq     $3,16($17)
+       srl     $4,$19,$5
+       bis     $1,$2,$8
+       stq     $8,-24($16)
+       sll     $3,$7,$6
+
+       ldq     $4,24($17)
+       srl     $3,$19,$1
+       bis     $5,$6,$8
+       stq     $8,-16($16)
+       sll     $4,$7,$2
+
+       addq    $17,32,$17
+       bis     $1,$2,$8
+       stq     $8,-8($16)
+
+       bgt     $18,.Roop
+
+.Rend: srl     $4,$19,$8
+       stq     $8,0($16)
+       ret     $31,($26),1
+       .end    mpihelp_rshift
+