The first libgcrypt only release.
[libgcrypt.git] / mpi / mpi-mul.c
1 /* mpi-mul.c  -  MPI functions
2  *      Copyright (C) 1994, 1996, 1998, 2001 Free Software Foundation, Inc.
3  *
4  * This file is part of Libgcrypt.
5  *
6  * Libgcrypt is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * Libgcrypt is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  *
20  * Note: This code is heavily based on the GNU MP Library.
21  *       Actually it's the same code with only minor changes in the
22  *       way the data is stored; this is to support the abstraction
23  *       of an optional secure memory allocation which may be used
24  *       to avoid revealing of sensitive data due to paging etc.
25  *       The GNU MP Library itself is published under the LGPL;
26  *       however I decided to publish this code under the plain GPL.
27  */
28
29 #include <config.h>
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include "mpi-internal.h"
33
34
35 void
36 gcry_mpi_mul_ui( MPI prod, MPI mult, unsigned long small_mult )
37 {
38     mpi_size_t size, prod_size;
39     mpi_ptr_t  prod_ptr;
40     mpi_limb_t cy;
41     int sign;
42
43     size = mult->nlimbs;
44     sign = mult->sign;
45
46     if( !size || !small_mult ) {
47         prod->nlimbs = 0;
48         prod->sign = 0;
49         return;
50     }
51
52     prod_size = size + 1;
53     if( prod->alloced < prod_size )
54         mpi_resize( prod, prod_size );
55     prod_ptr = prod->d;
56
57     cy = _gcry_mpih_mul_1( prod_ptr, mult->d, size, (mpi_limb_t)small_mult );
58     if( cy )
59         prod_ptr[size++] = cy;
60     prod->nlimbs = size;
61     prod->sign = sign;
62 }
63
64
65 void
66 _gcry_mpi_mul_2exp( MPI w, MPI u, unsigned long cnt)
67 {
68     mpi_size_t usize, wsize, limb_cnt;
69     mpi_ptr_t wp;
70     mpi_limb_t wlimb;
71     int usign, wsign;
72
73     usize = u->nlimbs;
74     usign = u->sign;
75
76     if( !usize ) {
77         w->nlimbs = 0;
78         w->sign = 0;
79         return;
80     }
81
82     limb_cnt = cnt / BITS_PER_MPI_LIMB;
83     wsize = usize + limb_cnt + 1;
84     if( w->alloced < wsize )
85         mpi_resize(w, wsize );
86     wp = w->d;
87     wsize = usize + limb_cnt;
88     wsign = usign;
89
90     cnt %= BITS_PER_MPI_LIMB;
91     if( cnt ) {
92         wlimb = _gcry_mpih_lshift( wp + limb_cnt, u->d, usize, cnt );
93         if( wlimb ) {
94             wp[wsize] = wlimb;
95             wsize++;
96         }
97     }
98     else {
99         MPN_COPY_DECR( wp + limb_cnt, u->d, usize );
100     }
101
102     /* Zero all whole limbs at low end.  Do it here and not before calling
103      * mpn_lshift, not to lose for U == W.  */
104     MPN_ZERO( wp, limb_cnt );
105
106     w->nlimbs = wsize;
107     w->sign = wsign;
108 }
109
110
111
112 void
113 gcry_mpi_mul( MPI w, MPI u, MPI v)
114 {
115     mpi_size_t usize, vsize, wsize;
116     mpi_ptr_t up, vp, wp;
117     mpi_limb_t cy;
118     int usign, vsign, usecure, vsecure, sign_product;
119     int assign_wp=0;
120     mpi_ptr_t tmp_limb=NULL;
121
122
123     if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */
124         usize = v->nlimbs;
125         usign = v->sign;
126         usecure = mpi_is_secure(v);
127         up    = v->d;
128         vsize = u->nlimbs;
129         vsign = u->sign;
130         vsecure = mpi_is_secure(u);
131         vp    = u->d;
132     }
133     else {
134         usize = u->nlimbs;
135         usign = u->sign;
136         usecure = mpi_is_secure(u);
137         up    = u->d;
138         vsize = v->nlimbs;
139         vsign = v->sign;
140         vsecure = mpi_is_secure(v);
141         vp    = v->d;
142     }
143     sign_product = usign ^ vsign;
144     wp = w->d;
145
146     /* Ensure W has space enough to store the result.  */
147     wsize = usize + vsize;
148     if ( !mpi_is_secure (w) && (mpi_is_secure (u) || mpi_is_secure (v)) ) {
149         /* w is not allocated in secure space but u or v is.  To make sure
150          * that no temporray results are stored in w, we temporary use 
151          * a newly allocated limb space for w */
152         wp = mpi_alloc_limb_space( wsize, 1 );
153         assign_wp = 2; /* mark it as 2 so that we can later copy it back to
154                         * mormal memory */
155     }
156     else if( w->alloced < wsize ) {
157         if( wp == up || wp == vp ) {
158             wp = mpi_alloc_limb_space( wsize, mpi_is_secure(w) );
159             assign_wp = 1;
160         }
161         else {
162             mpi_resize(w, wsize );
163             wp = w->d;
164         }
165     }
166     else { /* Make U and V not overlap with W.  */
167         if( wp == up ) {
168             /* W and U are identical.  Allocate temporary space for U.  */
169             up = tmp_limb = mpi_alloc_limb_space( usize, usecure  );
170             /* Is V identical too?  Keep it identical with U.  */
171             if( wp == vp )
172                 vp = up;
173             /* Copy to the temporary space.  */
174             MPN_COPY( up, wp, usize );
175         }
176         else if( wp == vp ) {
177             /* W and V are identical.  Allocate temporary space for V.  */
178             vp = tmp_limb = mpi_alloc_limb_space( vsize, vsecure );
179             /* Copy to the temporary space.  */
180             MPN_COPY( vp, wp, vsize );
181         }
182     }
183
184     if( !vsize )
185         wsize = 0;
186     else {
187         cy = _gcry_mpih_mul( wp, up, usize, vp, vsize );
188         wsize -= cy? 0:1;
189     }
190
191     if( assign_wp ) {
192         if (assign_wp == 2) {
193             /* copy the temp wp from secure memory back to normal memory */
194             mpi_ptr_t tmp_wp = mpi_alloc_limb_space (wsize, 0);
195             MPN_COPY (tmp_wp, wp, wsize);
196             mpi_free_limb_space (wp);
197             wp = tmp_wp;
198         }
199         _gcry_mpi_assign_limb_space( w, wp, wsize );
200     }
201     w->nlimbs = wsize;
202     w->sign = sign_product;
203     if( tmp_limb )
204         mpi_free_limb_space( tmp_limb );
205 }
206
207
208 void
209 gcry_mpi_mulm( MPI w, MPI u, MPI v, MPI m)
210 {
211     gcry_mpi_mul(w, u, v);
212     _gcry_mpi_fdiv_r( w, w, m );
213 }
214