Commit | Line | Data |
---|---|---|
7e8dec91 DK |
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 | ||
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 | ||
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 | ||
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 | ||
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 | } |