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