initially checkin
[gnupg.git] / mpi / mpi-mul.c
1 /* mpi-mul.c  -  MPI functions
2  *      Copyright (c) 1997 by Werner Koch (dd9jn)
3  *
4  * This file is part of G10.
5  *
6  * G10 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  * G10 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
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include "mpi-internal.h"
25
26
27 void
28 mpi_mul_ui( MPI prod, MPI mult, unsigned long small_mult )
29 {
30     mpi_size_t size, prod_size;
31     mpi_ptr_t  prod_ptr;
32     mpi_limb_t cy;
33     int sign;
34
35     size = mult->nlimbs;
36     sign = mult->sign;
37
38     if( !size || !small_mult ) {
39         prod->nlimbs = 0;
40         prod->sign = 0;
41         return;
42     }
43
44     prod_size = size + 1;
45     if( prod->alloced < prod_size )
46         mpi_resize( prod, prod_size );
47     prod_ptr = prod->d;
48
49     cy = mpihelp_mul_1( prod_ptr, mult->d, size, (mpi_limb_t)small_mult );
50     if( cy )
51         prod_ptr[size++] = cy;
52     prod->nlimbs = size;
53     prod->sign = sign;
54 }
55
56
57 void
58 mpi_mul_2exp( MPI w, MPI u, unsigned long cnt)
59 {
60     mpi_size_t usize, wsize, limb_cnt;
61     mpi_ptr_t wp;
62     mpi_limb_t wlimb;
63     int usign, wsign;
64
65     usize = u->nlimbs;
66     usign = u->sign;
67
68     if( !usize ) {
69         w->nlimbs = 0;
70         w->sign = 0;
71         return;
72     }
73
74     limb_cnt = cnt / BITS_PER_MPI_LIMB;
75     wsize = usize + limb_cnt + 1;
76     if( w->alloced < wsize )
77         mpi_resize(w, wsize );
78     wp = w->d;
79     wsize = usize + limb_cnt;
80     wsign = usign;
81
82     cnt %= BITS_PER_MPI_LIMB;
83     if( cnt ) {
84         wlimb = mpihelp_lshift( wp + limb_cnt, u->d, usize, cnt );
85         if( wlimb ) {
86             wp[wsize] = wlimb;
87             wsize++;
88         }
89     }
90     else {
91         MPN_COPY_DECR( wp + limb_cnt, u->d, usize );
92     }
93
94     /* Zero all whole limbs at low end.  Do it here and not before calling
95      * mpn_lshift, not to lose for U == W.  */
96     MPN_ZERO( wp, limb_cnt );
97
98     w->nlimbs = wsize;
99     w->sign = wsign;
100 }
101
102
103
104 void
105 mpi_mul( MPI w, MPI u, MPI v)
106 {
107     mpi_size_t usize, vsize, wsize;
108     mpi_ptr_t up, vp, wp;
109     mpi_limb_t cy;
110     int usign, vsign, sign_product;
111     int assign_wp=0;
112     mpi_ptr_t tmp_limb=NULL;
113
114     if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */
115         usize = v->nlimbs;
116         usign = v->sign;
117         up    = v->d;
118         vsize = u->nlimbs;
119         vsign = u->sign;
120         vp    = u->d;
121     }
122     else {
123         usize = u->nlimbs;
124         usign = u->sign;
125         up    = u->d;
126         vsize = v->nlimbs;
127         vsign = v->sign;
128         vp    = v->d;
129     }
130     sign_product = usign ^ vsign;
131     wp = w->d;
132
133     /* Ensure W has space enough to store the result.  */
134     wsize = usize + vsize;
135     if( w->alloced < wsize ) {
136         if( wp == up || wp == vp ) {
137             wp = mpi_alloc_limb_space( wsize );
138             assign_wp = 1;
139         }
140         else {
141             mpi_resize(w, wsize );
142             wp = w->d;
143         }
144     }
145     else { /* Make U and V not overlap with W.  */
146         if( wp == up ) {
147             /* W and U are identical.  Allocate temporary space for U.  */
148             up = tmp_limb = mpi_alloc_limb_space( usize );
149             /* Is V identical too?  Keep it identical with U.  */
150             if( wp == vp )
151                 vp = up;
152             /* Copy to the temporary space.  */
153             MPN_COPY( up, wp, usize );
154         }
155         else if( wp == vp ) {
156             /* W and V are identical.  Allocate temporary space for V.  */
157             vp = tmp_limb = mpi_alloc_limb_space( vsize );
158             /* Copy to the temporary space.  */
159             MPN_COPY( vp, wp, vsize );
160         }
161     }
162
163     if( !vsize )
164         wsize = 0;
165     else {
166         cy = mpihelp_mul( wp, up, usize, vp, vsize );
167         wsize -= cy? 0:1;
168     }
169
170     if( assign_wp )
171         mpi_assign_limb_space( w, wp, wsize );
172     w->nlimbs = wsize;
173     w->sign = sign_product;
174     if( tmp_limb )
175         mpi_free_limb_space( tmp_limb );
176 }
177
178