aboutsummaryrefslogtreecommitdiffstats
path: root/lib/mpi
diff options
context:
space:
mode:
Diffstat (limited to 'lib/mpi')
-rw-r--r--lib/mpi/Makefile11
-rw-r--r--lib/mpi/generic_mpi-asm-defs.h4
-rw-r--r--lib/mpi/mpi-add.c234
-rw-r--r--lib/mpi/mpi-bit.c162
-rw-r--r--lib/mpi/mpi-cmp.c68
-rw-r--r--lib/mpi/mpi-div.c338
-rw-r--r--lib/mpi/mpi-gcd.c59
-rw-r--r--lib/mpi/mpi-inline.c31
-rw-r--r--lib/mpi/mpi-inv.c187
-rw-r--r--lib/mpi/mpi-mpow.c134
-rw-r--r--lib/mpi/mpi-mul.c194
-rw-r--r--lib/mpi/mpi-scan.c136
-rw-r--r--lib/mpi/mpicoder.c75
-rw-r--r--lib/mpi/mpih-div.c309
-rw-r--r--lib/mpi/mpih-mul.c30
-rw-r--r--lib/mpi/mpiutil.c88
16 files changed, 0 insertions, 2060 deletions
diff --git a/lib/mpi/Makefile b/lib/mpi/Makefile
index 567d52e74d77..45ca90a8639c 100644
--- a/lib/mpi/Makefile
+++ b/lib/mpi/Makefile
@@ -19,14 +19,3 @@ mpi-y = \
19 mpih-mul.o \ 19 mpih-mul.o \
20 mpi-pow.o \ 20 mpi-pow.o \
21 mpiutil.o 21 mpiutil.o
22
23mpi-$(CONFIG_MPILIB_EXTRA) += \
24 mpi-add.o \
25 mpi-div.o \
26 mpi-cmp.o \
27 mpi-gcd.o \
28 mpi-inline.o \
29 mpi-inv.o \
30 mpi-mpow.o \
31 mpi-mul.o \
32 mpi-scan.o
diff --git a/lib/mpi/generic_mpi-asm-defs.h b/lib/mpi/generic_mpi-asm-defs.h
deleted file mode 100644
index 047d1f5a7249..000000000000
--- a/lib/mpi/generic_mpi-asm-defs.h
+++ /dev/null
@@ -1,4 +0,0 @@
1/* This file defines some basic constants for the MPI machinery. We
2 * need to define the types on a per-CPU basis, so it is done with
3 * this file here. */
4#define BYTES_PER_MPI_LIMB (SIZEOF_UNSIGNED_LONG)
diff --git a/lib/mpi/mpi-add.c b/lib/mpi/mpi-add.c
deleted file mode 100644
index f56b9ba295e6..000000000000
--- a/lib/mpi/mpi-add.c
+++ /dev/null
@@ -1,234 +0,0 @@
1/* mpi-add.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 * Copyright (C) 1994, 1996 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/****************
33 * Add the unsigned integer V to the mpi-integer U and store the
34 * result in W. U and V may be the same.
35 */
36int mpi_add_ui(MPI w, const MPI u, unsigned long v)
37{
38 mpi_ptr_t wp, up;
39 mpi_size_t usize, wsize;
40 int usign, wsign;
41
42 usize = u->nlimbs;
43 usign = u->sign;
44 wsign = 0;
45
46 /* If not space for W (and possible carry), increase space. */
47 wsize = usize + 1;
48 if (w->alloced < wsize)
49 if (mpi_resize(w, wsize) < 0)
50 return -ENOMEM;
51
52 /* These must be after realloc (U may be the same as W). */
53 up = u->d;
54 wp = w->d;
55
56 if (!usize) { /* simple */
57 wp[0] = v;
58 wsize = v ? 1 : 0;
59 } else if (!usign) { /* mpi is not negative */
60 mpi_limb_t cy;
61 cy = mpihelp_add_1(wp, up, usize, v);
62 wp[usize] = cy;
63 wsize = usize + cy;
64 } else { /* The signs are different. Need exact comparison to determine
65 * which operand to subtract from which. */
66 if (usize == 1 && up[0] < v) {
67 wp[0] = v - up[0];
68 wsize = 1;
69 } else {
70 mpihelp_sub_1(wp, up, usize, v);
71 /* Size can decrease with at most one limb. */
72 wsize = usize - (wp[usize - 1] == 0);
73 wsign = 1;
74 }
75 }
76
77 w->nlimbs = wsize;
78 w->sign = wsign;
79 return 0;
80}
81
82int mpi_add(MPI w, MPI u, MPI v)
83{
84 mpi_ptr_t wp, up, vp;
85 mpi_size_t usize, vsize, wsize;
86 int usign, vsign, wsign;
87
88 if (u->nlimbs < v->nlimbs) { /* Swap U and V. */
89 usize = v->nlimbs;
90 usign = v->sign;
91 vsize = u->nlimbs;
92 vsign = u->sign;
93 wsize = usize + 1;
94 if (RESIZE_IF_NEEDED(w, wsize) < 0)
95 return -ENOMEM;
96 /* These must be after realloc (u or v may be the same as w). */
97 up = v->d;
98 vp = u->d;
99 } else {
100 usize = u->nlimbs;
101 usign = u->sign;
102 vsize = v->nlimbs;
103 vsign = v->sign;
104 wsize = usize + 1;
105 if (RESIZE_IF_NEEDED(w, wsize) < 0)
106 return -ENOMEM;
107 /* These must be after realloc (u or v may be the same as w). */
108 up = u->d;
109 vp = v->d;
110 }
111 wp = w->d;
112 wsign = 0;
113
114 if (!vsize) { /* simple */
115 MPN_COPY(wp, up, usize);
116 wsize = usize;
117 wsign = usign;
118 } else if (usign != vsign) { /* different sign */
119 /* This test is right since USIZE >= VSIZE */
120 if (usize != vsize) {
121 mpihelp_sub(wp, up, usize, vp, vsize);
122 wsize = usize;
123 MPN_NORMALIZE(wp, wsize);
124 wsign = usign;
125 } else if (mpihelp_cmp(up, vp, usize) < 0) {
126 mpihelp_sub_n(wp, vp, up, usize);
127 wsize = usize;
128 MPN_NORMALIZE(wp, wsize);
129 if (!usign)
130 wsign = 1;
131 } else {
132 mpihelp_sub_n(wp, up, vp, usize);
133 wsize = usize;
134 MPN_NORMALIZE(wp, wsize);
135 if (usign)
136 wsign = 1;
137 }
138 } else { /* U and V have same sign. Add them. */
139 mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize);
140 wp[usize] = cy;
141 wsize = usize + cy;
142 if (usign)
143 wsign = 1;
144 }
145
146 w->nlimbs = wsize;
147 w->sign = wsign;
148 return 0;
149}
150
151/****************
152 * Subtract the unsigned integer V from the mpi-integer U and store the
153 * result in W.
154 */
155int mpi_sub_ui(MPI w, MPI u, unsigned long v)
156{
157 mpi_ptr_t wp, up;
158 mpi_size_t usize, wsize;
159 int usign, wsign;
160
161 usize = u->nlimbs;
162 usign = u->sign;
163 wsign = 0;
164
165 /* If not space for W (and possible carry), increase space. */
166 wsize = usize + 1;
167 if (w->alloced < wsize)
168 if (mpi_resize(w, wsize) < 0)
169 return -ENOMEM;
170
171 /* These must be after realloc (U may be the same as W). */
172 up = u->d;
173 wp = w->d;
174
175 if (!usize) { /* simple */
176 wp[0] = v;
177 wsize = v ? 1 : 0;
178 wsign = 1;
179 } else if (usign) { /* mpi and v are negative */
180 mpi_limb_t cy;
181 cy = mpihelp_add_1(wp, up, usize, v);
182 wp[usize] = cy;
183 wsize = usize + cy;
184 } else { /* The signs are different. Need exact comparison to determine
185 * which operand to subtract from which. */
186 if (usize == 1 && up[0] < v) {
187 wp[0] = v - up[0];
188 wsize = 1;
189 wsign = 1;
190 } else {
191 mpihelp_sub_1(wp, up, usize, v);
192 /* Size can decrease with at most one limb. */
193 wsize = usize - (wp[usize - 1] == 0);
194 }
195 }
196
197 w->nlimbs = wsize;
198 w->sign = wsign;
199 return 0;
200}
201
202int mpi_sub(MPI w, MPI u, MPI v)
203{
204 int rc;
205
206 if (w == v) {
207 MPI vv;
208 if (mpi_copy(&vv, v) < 0)
209 return -ENOMEM;
210 vv->sign = !vv->sign;
211 rc = mpi_add(w, u, vv);
212 mpi_free(vv);
213 } else {
214 /* fixme: this is not thread-save (we temp. modify v) */
215 v->sign = !v->sign;
216 rc = mpi_add(w, u, v);
217 v->sign = !v->sign;
218 }
219 return rc;
220}
221
222int mpi_addm(MPI w, MPI u, MPI v, MPI m)
223{
224 if (mpi_add(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0)
225 return -ENOMEM;
226 return 0;
227}
228
229int mpi_subm(MPI w, MPI u, MPI v, MPI m)
230{
231 if (mpi_sub(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0)
232 return -ENOMEM;
233 return 0;
234}
diff --git a/lib/mpi/mpi-bit.c b/lib/mpi/mpi-bit.c
index 0c505361da19..568724804f29 100644
--- a/lib/mpi/mpi-bit.c
+++ b/lib/mpi/mpi-bit.c
@@ -54,165 +54,3 @@ unsigned mpi_get_nbits(MPI a)
54 return n; 54 return n;
55} 55}
56EXPORT_SYMBOL_GPL(mpi_get_nbits); 56EXPORT_SYMBOL_GPL(mpi_get_nbits);
57
58/****************
59 * Test whether bit N is set.
60 */
61int mpi_test_bit(MPI a, unsigned n)
62{
63 unsigned limbno, bitno;
64 mpi_limb_t limb;
65
66 limbno = n / BITS_PER_MPI_LIMB;
67 bitno = n % BITS_PER_MPI_LIMB;
68
69 if (limbno >= a->nlimbs)
70 return 0; /* too far left: this is a 0 */
71 limb = a->d[limbno];
72 return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
73}
74
75/****************
76 * Set bit N of A.
77 */
78int mpi_set_bit(MPI a, unsigned n)
79{
80 unsigned limbno, bitno;
81
82 limbno = n / BITS_PER_MPI_LIMB;
83 bitno = n % BITS_PER_MPI_LIMB;
84
85 if (limbno >= a->nlimbs) { /* resize */
86 if (a->alloced >= limbno)
87 if (mpi_resize(a, limbno + 1) < 0)
88 return -ENOMEM;
89 a->nlimbs = limbno + 1;
90 }
91 a->d[limbno] |= (A_LIMB_1 << bitno);
92 return 0;
93}
94
95/****************
96 * Set bit N of A. and clear all bits above
97 */
98int mpi_set_highbit(MPI a, unsigned n)
99{
100 unsigned limbno, bitno;
101
102 limbno = n / BITS_PER_MPI_LIMB;
103 bitno = n % BITS_PER_MPI_LIMB;
104
105 if (limbno >= a->nlimbs) { /* resize */
106 if (a->alloced >= limbno)
107 if (mpi_resize(a, limbno + 1) < 0)
108 return -ENOMEM;
109 a->nlimbs = limbno + 1;
110 }
111 a->d[limbno] |= (A_LIMB_1 << bitno);
112 for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
113 a->d[limbno] &= ~(A_LIMB_1 << bitno);
114 a->nlimbs = limbno + 1;
115 return 0;
116}
117
118/****************
119 * clear bit N of A and all bits above
120 */
121void mpi_clear_highbit(MPI a, unsigned n)
122{
123 unsigned limbno, bitno;
124
125 limbno = n / BITS_PER_MPI_LIMB;
126 bitno = n % BITS_PER_MPI_LIMB;
127
128 if (limbno >= a->nlimbs)
129 return; /* not allocated, so need to clear bits :-) */
130
131 for (; bitno < BITS_PER_MPI_LIMB; bitno++)
132 a->d[limbno] &= ~(A_LIMB_1 << bitno);
133 a->nlimbs = limbno + 1;
134}
135
136/****************
137 * Clear bit N of A.
138 */
139void mpi_clear_bit(MPI a, unsigned n)
140{
141 unsigned limbno, bitno;
142
143 limbno = n / BITS_PER_MPI_LIMB;
144 bitno = n % BITS_PER_MPI_LIMB;
145
146 if (limbno >= a->nlimbs)
147 return; /* don't need to clear this bit, it's to far to left */
148 a->d[limbno] &= ~(A_LIMB_1 << bitno);
149}
150
151/****************
152 * Shift A by N bits to the right
153 * FIXME: should use alloc_limb if X and A are same.
154 */
155int mpi_rshift(MPI x, MPI a, unsigned n)
156{
157 mpi_ptr_t xp;
158 mpi_size_t xsize;
159
160 xsize = a->nlimbs;
161 x->sign = a->sign;
162 if (RESIZE_IF_NEEDED(x, (size_t) xsize) < 0)
163 return -ENOMEM;
164 xp = x->d;
165
166 if (xsize) {
167 mpihelp_rshift(xp, a->d, xsize, n);
168 MPN_NORMALIZE(xp, xsize);
169 }
170 x->nlimbs = xsize;
171 return 0;
172}
173
174/****************
175 * Shift A by COUNT limbs to the left
176 * This is used only within the MPI library
177 */
178int mpi_lshift_limbs(MPI a, unsigned int count)
179{
180 const int n = a->nlimbs;
181 mpi_ptr_t ap;
182 int i;
183
184 if (!count || !n)
185 return 0;
186
187 if (RESIZE_IF_NEEDED(a, n + count) < 0)
188 return -ENOMEM;
189
190 ap = a->d;
191 for (i = n - 1; i >= 0; i--)
192 ap[i + count] = ap[i];
193 for (i = 0; i < count; i++)
194 ap[i] = 0;
195 a->nlimbs += count;
196 return 0;
197}
198
199/****************
200 * Shift A by COUNT limbs to the right
201 * This is used only within the MPI library
202 */
203void mpi_rshift_limbs(MPI a, unsigned int count)
204{
205 mpi_ptr_t ap = a->d;
206 mpi_size_t n = a->nlimbs;
207 unsigned int i;
208
209 if (count >= n) {
210 a->nlimbs = 0;
211 return;
212 }
213
214 for (i = 0; i < n - count; i++)
215 ap[i] = ap[i + count];
216 ap[i] = 0;
217 a->nlimbs -= count;
218}
diff --git a/lib/mpi/mpi-cmp.c b/lib/mpi/mpi-cmp.c
deleted file mode 100644
index 914bc42a8a80..000000000000
--- a/lib/mpi/mpi-cmp.c
+++ /dev/null
@@ -1,68 +0,0 @@
1/* mpi-cmp.c - MPI functions
2 * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG 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 * GnuPG 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 "mpi-internal.h"
22
23int mpi_cmp_ui(MPI u, unsigned long v)
24{
25 mpi_limb_t limb = v;
26
27 mpi_normalize(u);
28 if (!u->nlimbs && !limb)
29 return 0;
30 if (u->sign)
31 return -1;
32 if (u->nlimbs > 1)
33 return 1;
34
35 if (u->d[0] == limb)
36 return 0;
37 else if (u->d[0] > limb)
38 return 1;
39 else
40 return -1;
41}
42
43int mpi_cmp(MPI u, MPI v)
44{
45 mpi_size_t usize, vsize;
46 int cmp;
47
48 mpi_normalize(u);
49 mpi_normalize(v);
50 usize = u->nlimbs;
51 vsize = v->nlimbs;
52 if (!u->sign && v->sign)
53 return 1;
54 if (u->sign && !v->sign)
55 return -1;
56 if (usize != vsize && !u->sign && !v->sign)
57 return usize - vsize;
58 if (usize != vsize && u->sign && v->sign)
59 return vsize + usize;
60 if (!usize)
61 return 0;
62 cmp = mpihelp_cmp(u->d, v->d, usize);
63 if (!cmp)
64 return 0;
65 if ((cmp < 0 ? 1 : 0) == (u->sign ? 1 : 0))
66 return 1;
67 return -1;
68}
diff --git a/lib/mpi/mpi-div.c b/lib/mpi/mpi-div.c
deleted file mode 100644
index f68cbbb4d4a4..000000000000
--- a/lib/mpi/mpi-div.c
+++ /dev/null
@@ -1,338 +0,0 @@
1/* mpi-div.c - MPI functions
2 * Copyright (C) 1994, 1996 Free Software Foundation, Inc.
3 * Copyright (C) 1998, 1999, 2000, 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 <linux/string.h>
31#include "mpi-internal.h"
32#include "longlong.h"
33
34int mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor)
35{
36 int rc = -ENOMEM;
37 int divisor_sign = divisor->sign;
38 MPI temp_divisor = NULL;
39
40 /* We need the original value of the divisor after the remainder has been
41 * preliminary calculated. We have to copy it to temporary space if it's
42 * the same variable as REM. */
43 if (rem == divisor) {
44 if (mpi_copy(&temp_divisor, divisor) < 0)
45 goto nomem;
46 divisor = temp_divisor;
47 }
48
49 if (mpi_tdiv_qr(NULL, rem, dividend, divisor) < 0)
50 goto nomem;
51 if (((divisor_sign ? 1 : 0) ^ (dividend->sign ? 1 : 0)) && rem->nlimbs)
52 if (mpi_add(rem, rem, divisor) < 0)
53 goto nomem;
54
55 rc = 0;
56
57nomem:
58 if (temp_divisor)
59 mpi_free(temp_divisor);
60 return rc;
61}
62
63/****************
64 * Division rounding the quotient towards -infinity.
65 * The remainder gets the same sign as the denominator.
66 * rem is optional
67 */
68
69ulong mpi_fdiv_r_ui(MPI rem, MPI dividend, ulong divisor)
70{
71 mpi_limb_t rlimb;
72
73 rlimb = mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor);
74 if (rlimb && dividend->sign)
75 rlimb = divisor - rlimb;
76
77 if (rem) {
78 rem->d[0] = rlimb;
79 rem->nlimbs = rlimb ? 1 : 0;
80 }
81 return rlimb;
82}
83
84int mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor)
85{
86 MPI tmp = mpi_alloc(mpi_get_nlimbs(quot));
87 if (!tmp)
88 return -ENOMEM;
89 mpi_fdiv_qr(quot, tmp, dividend, divisor);
90 mpi_free(tmp);
91 return 0;
92}
93
94int mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor)
95{
96 int divisor_sign = divisor->sign;
97 MPI temp_divisor = NULL;
98
99 if (quot == divisor || rem == divisor) {
100 if (mpi_copy(&temp_divisor, divisor) < 0)
101 return -ENOMEM;
102 divisor = temp_divisor;
103 }
104
105 if (mpi_tdiv_qr(quot, rem, dividend, divisor) < 0)
106 goto nomem;
107
108 if ((divisor_sign ^ dividend->sign) && rem->nlimbs) {
109 if (mpi_sub_ui(quot, quot, 1) < 0)
110 goto nomem;
111 if (mpi_add(rem, rem, divisor) < 0)
112 goto nomem;
113 }
114
115 if (temp_divisor)
116 mpi_free(temp_divisor);
117
118 return 0;
119
120nomem:
121 mpi_free(temp_divisor);
122 return -ENOMEM;
123}
124
125/* If den == quot, den needs temporary storage.
126 * If den == rem, den needs temporary storage.
127 * If num == quot, num needs temporary storage.
128 * If den has temporary storage, it can be normalized while being copied,
129 * i.e no extra storage should be allocated.
130 */
131
132int mpi_tdiv_r(MPI rem, MPI num, MPI den)
133{
134 return mpi_tdiv_qr(NULL, rem, num, den);
135}
136
137int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den)
138{
139 int rc = -ENOMEM;
140 mpi_ptr_t np, dp;
141 mpi_ptr_t qp, rp;
142 mpi_size_t nsize = num->nlimbs;
143 mpi_size_t dsize = den->nlimbs;
144 mpi_size_t qsize, rsize;
145 mpi_size_t sign_remainder = num->sign;
146 mpi_size_t sign_quotient = num->sign ^ den->sign;
147 unsigned normalization_steps;
148 mpi_limb_t q_limb;
149 mpi_ptr_t marker[5];
150 int markidx = 0;
151
152 if (!dsize)
153 return -EINVAL;
154
155 memset(marker, 0, sizeof(marker));
156
157 /* Ensure space is enough for quotient and remainder.
158 * We need space for an extra limb in the remainder, because it's
159 * up-shifted (normalized) below. */
160 rsize = nsize + 1;
161 if (mpi_resize(rem, rsize) < 0)
162 goto nomem;
163
164 qsize = rsize - dsize; /* qsize cannot be bigger than this. */
165 if (qsize <= 0) {
166 if (num != rem) {
167 rem->nlimbs = num->nlimbs;
168 rem->sign = num->sign;
169 MPN_COPY(rem->d, num->d, nsize);
170 }
171 if (quot) {
172 /* This needs to follow the assignment to rem, in case the
173 * numerator and quotient are the same. */
174 quot->nlimbs = 0;
175 quot->sign = 0;
176 }
177 return 0;
178 }
179
180 if (quot)
181 if (mpi_resize(quot, qsize) < 0)
182 goto nomem;
183
184 /* Read pointers here, when reallocation is finished. */
185 np = num->d;
186 dp = den->d;
187 rp = rem->d;
188
189 /* Optimize division by a single-limb divisor. */
190 if (dsize == 1) {
191 mpi_limb_t rlimb;
192 if (quot) {
193 qp = quot->d;
194 rlimb = mpihelp_divmod_1(qp, np, nsize, dp[0]);
195 qsize -= qp[qsize - 1] == 0;
196 quot->nlimbs = qsize;
197 quot->sign = sign_quotient;
198 } else
199 rlimb = mpihelp_mod_1(np, nsize, dp[0]);
200 rp[0] = rlimb;
201 rsize = rlimb != 0 ? 1 : 0;
202 rem->nlimbs = rsize;
203 rem->sign = sign_remainder;
204 return 0;
205 }
206
207 if (quot) {
208 qp = quot->d;
209 /* Make sure QP and NP point to different objects. Otherwise the
210 * numerator would be gradually overwritten by the quotient limbs. */
211 if (qp == np) { /* Copy NP object to temporary space. */
212 np = marker[markidx++] = mpi_alloc_limb_space(nsize);
213 if (!np)
214 goto nomem;
215 MPN_COPY(np, qp, nsize);
216 }
217 } else /* Put quotient at top of remainder. */
218 qp = rp + dsize;
219
220 count_leading_zeros(normalization_steps, dp[dsize - 1]);
221
222 /* Normalize the denominator, i.e. make its most significant bit set by
223 * shifting it NORMALIZATION_STEPS bits to the left. Also shift the
224 * numerator the same number of steps (to keep the quotient the same!).
225 */
226 if (normalization_steps) {
227 mpi_ptr_t tp;
228 mpi_limb_t nlimb;
229
230 /* Shift up the denominator setting the most significant bit of
231 * the most significant word. Use temporary storage not to clobber
232 * the original contents of the denominator. */
233 tp = marker[markidx++] = mpi_alloc_limb_space(dsize);
234 if (!tp)
235 goto nomem;
236 mpihelp_lshift(tp, dp, dsize, normalization_steps);
237 dp = tp;
238
239 /* Shift up the numerator, possibly introducing a new most
240 * significant word. Move the shifted numerator in the remainder
241 * meanwhile. */
242 nlimb = mpihelp_lshift(rp, np, nsize, normalization_steps);
243 if (nlimb) {
244 rp[nsize] = nlimb;
245 rsize = nsize + 1;
246 } else
247 rsize = nsize;
248 } else {
249 /* The denominator is already normalized, as required. Copy it to
250 * temporary space if it overlaps with the quotient or remainder. */
251 if (dp == rp || (quot && (dp == qp))) {
252 mpi_ptr_t tp;
253
254 tp = marker[markidx++] = mpi_alloc_limb_space(dsize);
255 if (!tp)
256 goto nomem;
257 MPN_COPY(tp, dp, dsize);
258 dp = tp;
259 }
260
261 /* Move the numerator to the remainder. */
262 if (rp != np)
263 MPN_COPY(rp, np, nsize);
264
265 rsize = nsize;
266 }
267
268 q_limb = mpihelp_divrem(qp, 0, rp, rsize, dp, dsize);
269
270 if (quot) {
271 qsize = rsize - dsize;
272 if (q_limb) {
273 qp[qsize] = q_limb;
274 qsize += 1;
275 }
276
277 quot->nlimbs = qsize;
278 quot->sign = sign_quotient;
279 }
280
281 rsize = dsize;
282 MPN_NORMALIZE(rp, rsize);
283
284 if (normalization_steps && rsize) {
285 mpihelp_rshift(rp, rp, rsize, normalization_steps);
286 rsize -= rp[rsize - 1] == 0 ? 1 : 0;
287 }
288
289 rem->nlimbs = rsize;
290 rem->sign = sign_remainder;
291
292 rc = 0;
293nomem:
294 while (markidx)
295 mpi_free_limb_space(marker[--markidx]);
296 return rc;
297}
298
299int mpi_tdiv_q_2exp(MPI w, MPI u, unsigned count)
300{
301 mpi_size_t usize, wsize;
302 mpi_size_t limb_cnt;
303
304 usize = u->nlimbs;
305 limb_cnt = count / BITS_PER_MPI_LIMB;
306 wsize = usize - limb_cnt;
307 if (limb_cnt >= usize)
308 w->nlimbs = 0;
309 else {
310 mpi_ptr_t wp;
311 mpi_ptr_t up;
312
313 if (RESIZE_IF_NEEDED(w, wsize) < 0)
314 return -ENOMEM;
315 wp = w->d;
316 up = u->d;
317
318 count %= BITS_PER_MPI_LIMB;
319 if (count) {
320 mpihelp_rshift(wp, up + limb_cnt, wsize, count);
321 wsize -= !wp[wsize - 1];
322 } else {
323 MPN_COPY_INCR(wp, up + limb_cnt, wsize);
324 }
325
326 w->nlimbs = wsize;
327 }
328 return 0;
329}
330
331/****************
332 * Check whether dividend is divisible by divisor
333 * (note: divisor must fit into a limb)
334 */
335int mpi_divisible_ui(MPI dividend, ulong divisor)
336{
337 return !mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor);
338}
diff --git a/lib/mpi/mpi-gcd.c b/lib/mpi/mpi-gcd.c
deleted file mode 100644
index 13c48aef9c4e..000000000000
--- a/lib/mpi/mpi-gcd.c
+++ /dev/null
@@ -1,59 +0,0 @@
1/* mpi-gcd.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG 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 * GnuPG 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 "mpi-internal.h"
22
23/****************
24 * Find the greatest common divisor G of A and B.
25 * Return: true if this 1, false in all other cases
26 */
27int mpi_gcd(MPI g, const MPI xa, const MPI xb)
28{
29 MPI a = NULL, b = NULL;
30
31 if (mpi_copy(&a, xa) < 0)
32 goto nomem;
33
34 if (mpi_copy(&b, xb) < 0)
35 goto nomem;
36
37 /* TAOCP Vol II, 4.5.2, Algorithm A */
38 a->sign = 0;
39 b->sign = 0;
40 while (mpi_cmp_ui(b, 0)) {
41 if (mpi_fdiv_r(g, a, b) < 0) /* g used as temorary variable */
42 goto nomem;
43 if (mpi_set(a, b) < 0)
44 goto nomem;
45 if (mpi_set(b, g) < 0)
46 goto nomem;
47 }
48 if (mpi_set(g, a) < 0)
49 goto nomem;
50
51 mpi_free(a);
52 mpi_free(b);
53 return !mpi_cmp_ui(g, 1);
54
55nomem:
56 mpi_free(a);
57 mpi_free(b);
58 return -ENOMEM;
59}
diff --git a/lib/mpi/mpi-inline.c b/lib/mpi/mpi-inline.c
deleted file mode 100644
index 654f68aeed8b..000000000000
--- a/lib/mpi/mpi-inline.c
+++ /dev/null
@@ -1,31 +0,0 @@
1/* mpi-inline.c
2 * Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG 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 * GnuPG 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/* put the inline functions as real functions into the lib */
22#define G10_MPI_INLINE_DECL
23
24#include "mpi-internal.h"
25
26/* always include the header becuase it is only
27 * included by mpi-internal if __GCC__ is defined but we
28 * need it here in all cases and the above definition of
29 * of the macro allows us to do so
30 */
31#include "mpi-inline.h"
diff --git a/lib/mpi/mpi-inv.c b/lib/mpi/mpi-inv.c
deleted file mode 100644
index 0951f9847745..000000000000
--- a/lib/mpi/mpi-inv.c
+++ /dev/null
@@ -1,187 +0,0 @@
1/* mpi-inv.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG 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 * GnuPG 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 "mpi-internal.h"
22
23/****************
24 * Calculate the multiplicative inverse X of A mod N
25 * That is: Find the solution x for
26 * 1 = (a*x) mod n
27 */
28int mpi_invm(MPI x, const MPI a, const MPI n)
29{
30 /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
31 * modified according to Michael Penk's solution for Exercice 35
32 * with further enhancement */
33 MPI u = NULL, v = NULL;
34 MPI u1 = NULL, u2 = NULL, u3 = NULL;
35 MPI v1 = NULL, v2 = NULL, v3 = NULL;
36 MPI t1 = NULL, t2 = NULL, t3 = NULL;
37 unsigned k;
38 int sign;
39 int odd = 0;
40 int rc = -ENOMEM;
41
42 if (mpi_copy(&u, a) < 0)
43 goto cleanup;
44 if (mpi_copy(&v, n) < 0)
45 goto cleanup;
46
47 for (k = 0; !mpi_test_bit(u, 0) && !mpi_test_bit(v, 0); k++) {
48 if (mpi_rshift(u, u, 1) < 0)
49 goto cleanup;
50 if (mpi_rshift(v, v, 1) < 0)
51 goto cleanup;
52 }
53 odd = mpi_test_bit(v, 0);
54
55 u1 = mpi_alloc_set_ui(1);
56 if (!u1)
57 goto cleanup;
58 if (!odd) {
59 u2 = mpi_alloc_set_ui(0);
60 if (!u2)
61 goto cleanup;
62 }
63 if (mpi_copy(&u3, u) < 0)
64 goto cleanup;
65 if (mpi_copy(&v1, v) < 0)
66 goto cleanup;
67 if (!odd) {
68 v2 = mpi_alloc(mpi_get_nlimbs(u));
69 if (!v2)
70 goto cleanup;
71 if (mpi_sub(v2, u1, u) < 0)
72 goto cleanup; /* U is used as const 1 */
73 }
74 if (mpi_copy(&v3, v) < 0)
75 goto cleanup;
76 if (mpi_test_bit(u, 0)) { /* u is odd */
77 t1 = mpi_alloc_set_ui(0);
78 if (!t1)
79 goto cleanup;
80 if (!odd) {
81 t2 = mpi_alloc_set_ui(1);
82 if (!t2)
83 goto cleanup;
84 t2->sign = 1;
85 }
86 if (mpi_copy(&t3, v) < 0)
87 goto cleanup;
88 t3->sign = !t3->sign;
89 goto Y4;
90 } else {
91 t1 = mpi_alloc_set_ui(1);
92 if (!t1)
93 goto cleanup;
94 if (!odd) {
95 t2 = mpi_alloc_set_ui(0);
96 if (!t2)
97 goto cleanup;
98 }
99 if (mpi_copy(&t3, u) < 0)
100 goto cleanup;
101 }
102 do {
103 do {
104 if (!odd) {
105 if (mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0)) { /* one is odd */
106 if (mpi_add(t1, t1, v) < 0)
107 goto cleanup;
108 if (mpi_sub(t2, t2, u) < 0)
109 goto cleanup;
110 }
111 if (mpi_rshift(t1, t1, 1) < 0)
112 goto cleanup;
113 if (mpi_rshift(t2, t2, 1) < 0)
114 goto cleanup;
115 if (mpi_rshift(t3, t3, 1) < 0)
116 goto cleanup;
117 } else {
118 if (mpi_test_bit(t1, 0))
119 if (mpi_add(t1, t1, v) < 0)
120 goto cleanup;
121 if (mpi_rshift(t1, t1, 1) < 0)
122 goto cleanup;
123 if (mpi_rshift(t3, t3, 1) < 0)
124 goto cleanup;
125 }
126Y4:
127 ;
128 } while (!mpi_test_bit(t3, 0)); /* while t3 is even */
129
130 if (!t3->sign) {
131 if (mpi_set(u1, t1) < 0)
132 goto cleanup;
133 if (!odd)
134 if (mpi_set(u2, t2) < 0)
135 goto cleanup;
136 if (mpi_set(u3, t3) < 0)
137 goto cleanup;
138 } else {
139 if (mpi_sub(v1, v, t1) < 0)
140 goto cleanup;
141 sign = u->sign;
142 u->sign = !u->sign;
143 if (!odd)
144 if (mpi_sub(v2, u, t2) < 0)
145 goto cleanup;
146 u->sign = sign;
147 sign = t3->sign;
148 t3->sign = !t3->sign;
149 if (mpi_set(v3, t3) < 0)
150 goto cleanup;
151 t3->sign = sign;
152 }
153 if (mpi_sub(t1, u1, v1) < 0)
154 goto cleanup;
155 if (!odd)
156 if (mpi_sub(t2, u2, v2) < 0)
157 goto cleanup;
158 if (mpi_sub(t3, u3, v3) < 0)
159 goto cleanup;
160 if (t1->sign) {
161 if (mpi_add(t1, t1, v) < 0)
162 goto cleanup;
163 if (!odd)
164 if (mpi_sub(t2, t2, u) < 0)
165 goto cleanup;
166 }
167 } while (mpi_cmp_ui(t3, 0)); /* while t3 != 0 */
168 /* mpi_lshift( u3, k ); */
169 rc = mpi_set(x, u1);
170
171cleanup:
172 mpi_free(u1);
173 mpi_free(v1);
174 mpi_free(t1);
175 if (!odd) {
176 mpi_free(u2);
177 mpi_free(v2);
178 mpi_free(t2);
179 }
180 mpi_free(u3);
181 mpi_free(v3);
182 mpi_free(t3);
183
184 mpi_free(u);
185 mpi_free(v);
186 return rc;
187}
diff --git a/lib/mpi/mpi-mpow.c b/lib/mpi/mpi-mpow.c
deleted file mode 100644
index 7328d0d6c748..000000000000
--- a/lib/mpi/mpi-mpow.c
+++ /dev/null
@@ -1,134 +0,0 @@
1/* mpi-mpow.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG 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 * GnuPG 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 "mpi-internal.h"
22#include "longlong.h"
23
24static int build_index(const MPI *exparray, int k, int i, int t)
25{
26 int j, bitno;
27 int index = 0;
28
29 bitno = t - i;
30 for (j = k - 1; j >= 0; j--) {
31 index <<= 1;
32 if (mpi_test_bit(exparray[j], bitno))
33 index |= 1;
34 }
35 return index;
36}
37
38/****************
39 * RES = (BASE[0] ^ EXP[0]) * (BASE[1] ^ EXP[1]) * ... * mod M
40 */
41int mpi_mulpowm(MPI res, MPI *basearray, MPI *exparray, MPI m)
42{
43 int rc = -ENOMEM;
44 int k; /* number of elements */
45 int t; /* bit size of largest exponent */
46 int i, j, idx;
47 MPI *G = NULL; /* table with precomputed values of size 2^k */
48 MPI tmp = NULL;
49
50 for (k = 0; basearray[k]; k++)
51 ;
52 if (!k) {
53 pr_emerg("mpi_mulpowm: assert(k) failed\n");
54 BUG();
55 }
56 for (t = 0, i = 0; (tmp = exparray[i]); i++) {
57 j = mpi_get_nbits(tmp);
58 if (j > t)
59 t = j;
60 }
61 if (i != k) {
62 pr_emerg("mpi_mulpowm: assert(i==k) failed\n");
63 BUG();
64 }
65 if (!t) {
66 pr_emerg("mpi_mulpowm: assert(t) failed\n");
67 BUG();
68 }
69 if (k >= 10) {
70 pr_emerg("mpi_mulpowm: assert(k<10) failed\n");
71 BUG();
72 }
73
74 G = kzalloc((1 << k) * sizeof *G, GFP_KERNEL);
75 if (!G)
76 goto err_out;
77
78 /* and calculate */
79 tmp = mpi_alloc(mpi_get_nlimbs(m) + 1);
80 if (!tmp)
81 goto nomem;
82 if (mpi_set_ui(res, 1) < 0)
83 goto nomem;
84 for (i = 1; i <= t; i++) {
85 if (mpi_mulm(tmp, res, res, m) < 0)
86 goto nomem;
87 idx = build_index(exparray, k, i, t);
88 if (!(idx >= 0 && idx < (1 << k))) {
89 pr_emerg("mpi_mulpowm: assert(idx >= 0 && idx < (1<<k)) failed\n");
90 BUG();
91 }
92 if (!G[idx]) {
93 if (!idx) {
94 G[0] = mpi_alloc_set_ui(1);
95 if (!G[0])
96 goto nomem;
97 } else {
98 for (j = 0; j < k; j++) {
99 if ((idx & (1 << j))) {
100 if (!G[idx]) {
101 if (mpi_copy
102 (&G[idx],
103 basearray[j]) < 0)
104 goto nomem;
105 } else {
106 if (mpi_mulm
107 (G[idx], G[idx],
108 basearray[j],
109 m) < 0)
110 goto nomem;
111 }
112 }
113 }
114 if (!G[idx]) {
115 G[idx] = mpi_alloc(0);
116 if (!G[idx])
117 goto nomem;
118 }
119 }
120 }
121 if (mpi_mulm(res, tmp, G[idx], m) < 0)
122 goto nomem;
123 }
124
125 rc = 0;
126nomem:
127 /* cleanup */
128 mpi_free(tmp);
129 for (i = 0; i < (1 << k); i++)
130 mpi_free(G[i]);
131 kfree(G);
132err_out:
133 return rc;
134}
diff --git a/lib/mpi/mpi-mul.c b/lib/mpi/mpi-mul.c
deleted file mode 100644
index 1f3219e27292..000000000000
--- a/lib/mpi/mpi-mul.c
+++ /dev/null
@@ -1,194 +0,0 @@
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
32int 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
62int 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
107int 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;
183nomem:
184 if (tmp_limb)
185 mpi_free_limb_space(tmp_limb);
186 return rc;
187}
188
189int 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}
diff --git a/lib/mpi/mpi-scan.c b/lib/mpi/mpi-scan.c
deleted file mode 100644
index b2da5ad96199..000000000000
--- a/lib/mpi/mpi-scan.c
+++ /dev/null
@@ -1,136 +0,0 @@
1/* mpi-scan.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 *
4 * This file is part of GnuPG.
5 *
6 * GnuPG 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 * GnuPG 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 "mpi-internal.h"
22#include "longlong.h"
23
24/****************
25 * Scan through an mpi and return byte for byte. a -1 is returned to indicate
26 * the end of the mpi. Scanning is done from the lsb to the msb, returned
27 * values are in the range of 0 .. 255.
28 *
29 * FIXME: This code is VERY ugly!
30 */
31int mpi_getbyte(const MPI a, unsigned idx)
32{
33 int i, j;
34 unsigned n;
35 mpi_ptr_t ap;
36 mpi_limb_t limb;
37
38 ap = a->d;
39 for (n = 0, i = 0; i < a->nlimbs; i++) {
40 limb = ap[i];
41 for (j = 0; j < BYTES_PER_MPI_LIMB; j++, n++)
42 if (n == idx)
43 return (limb >> j * 8) & 0xff;
44 }
45 return -1;
46}
47
48/****************
49 * Put a value at position IDX into A. idx counts from lsb to msb
50 */
51void mpi_putbyte(MPI a, unsigned idx, int xc)
52{
53 int i, j;
54 unsigned n;
55 mpi_ptr_t ap;
56 mpi_limb_t limb, c;
57
58 c = xc & 0xff;
59 ap = a->d;
60 for (n = 0, i = 0; i < a->alloced; i++) {
61 limb = ap[i];
62 for (j = 0; j < BYTES_PER_MPI_LIMB; j++, n++)
63 if (n == idx) {
64#if BYTES_PER_MPI_LIMB == 4
65 if (j == 0)
66 limb = (limb & 0xffffff00) | c;
67 else if (j == 1)
68 limb = (limb & 0xffff00ff) | (c << 8);
69 else if (j == 2)
70 limb = (limb & 0xff00ffff) | (c << 16);
71 else
72 limb = (limb & 0x00ffffff) | (c << 24);
73#elif BYTES_PER_MPI_LIMB == 8
74 if (j == 0)
75 limb = (limb & 0xffffffffffffff00) | c;
76 else if (j == 1)
77 limb =
78 (limb & 0xffffffffffff00ff) | (c <<
79 8);
80 else if (j == 2)
81 limb =
82 (limb & 0xffffffffff00ffff) | (c <<
83 16);
84 else if (j == 3)
85 limb =
86 (limb & 0xffffffff00ffffff) | (c <<
87 24);
88 else if (j == 4)
89 limb =
90 (limb & 0xffffff00ffffffff) | (c <<
91 32);
92 else if (j == 5)
93 limb =
94 (limb & 0xffff00ffffffffff) | (c <<
95 40);
96 else if (j == 6)
97 limb =
98 (limb & 0xff00ffffffffffff) | (c <<
99 48);
100 else
101 limb =
102 (limb & 0x00ffffffffffffff) | (c <<
103 56);
104#else
105#error please enhance this function, its ugly - i know.
106#endif
107 if (a->nlimbs <= i)
108 a->nlimbs = i + 1;
109 ap[i] = limb;
110 return;
111 }
112 }
113 log_bug("index out of range\n");
114}
115
116/****************
117 * Count the number of zerobits at the low end of A
118 */
119unsigned mpi_trailing_zeros(const MPI a)
120{
121 unsigned n, count = 0;
122
123 for (n = 0; n < a->nlimbs; n++) {
124 if (a->d[n]) {
125 unsigned nn;
126 mpi_limb_t alimb = a->d[n];
127
128 count_trailing_zeros(nn, alimb);
129 count += nn;
130 break;
131 }
132 count += BITS_PER_MPI_LIMB;
133 }
134 return count;
135
136}
diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c
index f26b41fcb48c..f0fa65995800 100644
--- a/lib/mpi/mpicoder.c
+++ b/lib/mpi/mpicoder.c
@@ -74,81 +74,6 @@ leave:
74EXPORT_SYMBOL_GPL(mpi_read_from_buffer); 74EXPORT_SYMBOL_GPL(mpi_read_from_buffer);
75 75
76/**************** 76/****************
77 * Make an mpi from a character string.
78 */
79int mpi_fromstr(MPI val, const char *str)
80{
81 int hexmode = 0, sign = 0, prepend_zero = 0, i, j, c, c1, c2;
82 unsigned nbits, nbytes, nlimbs;
83 mpi_limb_t a;
84
85 if (*str == '-') {
86 sign = 1;
87 str++;
88 }
89 if (*str == '0' && str[1] == 'x')
90 hexmode = 1;
91 else
92 return -EINVAL; /* other bases are not yet supported */
93 str += 2;
94
95 nbits = strlen(str) * 4;
96 if (nbits % 8)
97 prepend_zero = 1;
98 nbytes = (nbits + 7) / 8;
99 nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
100 if (val->alloced < nlimbs)
101 if (!mpi_resize(val, nlimbs))
102 return -ENOMEM;
103 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
104 i %= BYTES_PER_MPI_LIMB;
105 j = val->nlimbs = nlimbs;
106 val->sign = sign;
107 for (; j > 0; j--) {
108 a = 0;
109 for (; i < BYTES_PER_MPI_LIMB; i++) {
110 if (prepend_zero) {
111 c1 = '0';
112 prepend_zero = 0;
113 } else
114 c1 = *str++;
115 assert(c1);
116 c2 = *str++;
117 assert(c2);
118 if (c1 >= '0' && c1 <= '9')
119 c = c1 - '0';
120 else if (c1 >= 'a' && c1 <= 'f')
121 c = c1 - 'a' + 10;
122 else if (c1 >= 'A' && c1 <= 'F')
123 c = c1 - 'A' + 10;
124 else {
125 mpi_clear(val);
126 return 1;
127 }
128 c <<= 4;
129 if (c2 >= '0' && c2 <= '9')
130 c |= c2 - '0';
131 else if (c2 >= 'a' && c2 <= 'f')
132 c |= c2 - 'a' + 10;
133 else if (c2 >= 'A' && c2 <= 'F')
134 c |= c2 - 'A' + 10;
135 else {
136 mpi_clear(val);
137 return 1;
138 }
139 a <<= 8;
140 a |= c;
141 }
142 i = 0;
143
144 val->d[j - 1] = a;
145 }
146
147 return 0;
148}
149EXPORT_SYMBOL_GPL(mpi_fromstr);
150
151/****************
152 * Return an allocated buffer with the MPI (msb first). 77 * Return an allocated buffer with the MPI (msb first).
153 * NBYTES receives the length of this buffer. Caller must free the 78 * NBYTES receives the length of this buffer. Caller must free the
154 * return string (This function does return a 0 byte buffer with NBYTES 79 * return string (This function does return a 0 byte buffer with NBYTES
diff --git a/lib/mpi/mpih-div.c b/lib/mpi/mpih-div.c
index cde1aaec18da..c57d1d46295e 100644
--- a/lib/mpi/mpih-div.c
+++ b/lib/mpi/mpih-div.c
@@ -37,159 +37,6 @@
37#define UDIV_TIME UMUL_TIME 37#define UDIV_TIME UMUL_TIME
38#endif 38#endif
39 39
40/* FIXME: We should be using invert_limb (or invert_normalized_limb)
41 * here (not udiv_qrnnd).
42 */
43
44mpi_limb_t
45mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
46 mpi_limb_t divisor_limb)
47{
48 mpi_size_t i;
49 mpi_limb_t n1, n0, r;
50 int dummy;
51
52 /* Botch: Should this be handled at all? Rely on callers? */
53 if (!dividend_size)
54 return 0;
55
56 /* If multiplication is much faster than division, and the
57 * dividend is large, pre-invert the divisor, and use
58 * only multiplications in the inner loop.
59 *
60 * This test should be read:
61 * Does it ever help to use udiv_qrnnd_preinv?
62 * && Does what we save compensate for the inversion overhead?
63 */
64 if (UDIV_TIME > (2 * UMUL_TIME + 6)
65 && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
66 int normalization_steps;
67
68 count_leading_zeros(normalization_steps, divisor_limb);
69 if (normalization_steps) {
70 mpi_limb_t divisor_limb_inverted;
71
72 divisor_limb <<= normalization_steps;
73
74 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
75 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
76 * most significant bit (with weight 2**N) implicit.
77 *
78 * Special case for DIVISOR_LIMB == 100...000.
79 */
80 if (!(divisor_limb << 1))
81 divisor_limb_inverted = ~(mpi_limb_t) 0;
82 else
83 udiv_qrnnd(divisor_limb_inverted, dummy,
84 -divisor_limb, 0, divisor_limb);
85
86 n1 = dividend_ptr[dividend_size - 1];
87 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
88
89 /* Possible optimization:
90 * if (r == 0
91 * && divisor_limb > ((n1 << normalization_steps)
92 * | (dividend_ptr[dividend_size - 2] >> ...)))
93 * ...one division less...
94 */
95 for (i = dividend_size - 2; i >= 0; i--) {
96 n0 = dividend_ptr[i];
97 UDIV_QRNND_PREINV(dummy, r, r,
98 ((n1 << normalization_steps)
99 | (n0 >>
100 (BITS_PER_MPI_LIMB -
101 normalization_steps))),
102 divisor_limb,
103 divisor_limb_inverted);
104 n1 = n0;
105 }
106 UDIV_QRNND_PREINV(dummy, r, r,
107 n1 << normalization_steps,
108 divisor_limb, divisor_limb_inverted);
109 return r >> normalization_steps;
110 } else {
111 mpi_limb_t divisor_limb_inverted;
112
113 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
114 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
115 * most significant bit (with weight 2**N) implicit.
116 *
117 * Special case for DIVISOR_LIMB == 100...000.
118 */
119 if (!(divisor_limb << 1))
120 divisor_limb_inverted = ~(mpi_limb_t) 0;
121 else
122 udiv_qrnnd(divisor_limb_inverted, dummy,
123 -divisor_limb, 0, divisor_limb);
124
125 i = dividend_size - 1;
126 r = dividend_ptr[i];
127
128 if (r >= divisor_limb)
129 r = 0;
130 else
131 i--;
132
133 for (; i >= 0; i--) {
134 n0 = dividend_ptr[i];
135 UDIV_QRNND_PREINV(dummy, r, r,
136 n0, divisor_limb,
137 divisor_limb_inverted);
138 }
139 return r;
140 }
141 } else {
142 if (UDIV_NEEDS_NORMALIZATION) {
143 int normalization_steps;
144
145 count_leading_zeros(normalization_steps, divisor_limb);
146 if (normalization_steps) {
147 divisor_limb <<= normalization_steps;
148
149 n1 = dividend_ptr[dividend_size - 1];
150 r = n1 >> (BITS_PER_MPI_LIMB -
151 normalization_steps);
152
153 /* Possible optimization:
154 * if (r == 0
155 * && divisor_limb > ((n1 << normalization_steps)
156 * | (dividend_ptr[dividend_size - 2] >> ...)))
157 * ...one division less...
158 */
159 for (i = dividend_size - 2; i >= 0; i--) {
160 n0 = dividend_ptr[i];
161 udiv_qrnnd(dummy, r, r,
162 ((n1 << normalization_steps)
163 | (n0 >>
164 (BITS_PER_MPI_LIMB -
165 normalization_steps))),
166 divisor_limb);
167 n1 = n0;
168 }
169 udiv_qrnnd(dummy, r, r,
170 n1 << normalization_steps,
171 divisor_limb);
172 return r >> normalization_steps;
173 }
174 }
175 /* No normalization needed, either because udiv_qrnnd doesn't require
176 * it, or because DIVISOR_LIMB is already normalized. */
177 i = dividend_size - 1;
178 r = dividend_ptr[i];
179
180 if (r >= divisor_limb)
181 r = 0;
182 else
183 i--;
184
185 for (; i >= 0; i--) {
186 n0 = dividend_ptr[i];
187 udiv_qrnnd(dummy, r, r, n0, divisor_limb);
188 }
189 return r;
190 }
191}
192
193/* Divide num (NP/NSIZE) by den (DP/DSIZE) and write 40/* Divide num (NP/NSIZE) by den (DP/DSIZE) and write
194 * the NSIZE-DSIZE least significant quotient limbs at QP 41 * the NSIZE-DSIZE least significant quotient limbs at QP
195 * and the DSIZE long remainder at NP. If QEXTRA_LIMBS is 42 * and the DSIZE long remainder at NP. If QEXTRA_LIMBS is
@@ -387,159 +234,3 @@ q_test:
387 234
388 return most_significant_q_limb; 235 return most_significant_q_limb;
389} 236}
390
391/****************
392 * Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
393 * Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR.
394 * Return the single-limb remainder.
395 * There are no constraints on the value of the divisor.
396 *
397 * QUOT_PTR and DIVIDEND_PTR might point to the same limb.
398 */
399
400mpi_limb_t
401mpihelp_divmod_1(mpi_ptr_t quot_ptr,
402 mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
403 mpi_limb_t divisor_limb)
404{
405 mpi_size_t i;
406 mpi_limb_t n1, n0, r;
407 int dummy;
408
409 if (!dividend_size)
410 return 0;
411
412 /* If multiplication is much faster than division, and the
413 * dividend is large, pre-invert the divisor, and use
414 * only multiplications in the inner loop.
415 *
416 * This test should be read:
417 * Does it ever help to use udiv_qrnnd_preinv?
418 * && Does what we save compensate for the inversion overhead?
419 */
420 if (UDIV_TIME > (2 * UMUL_TIME + 6)
421 && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
422 int normalization_steps;
423
424 count_leading_zeros(normalization_steps, divisor_limb);
425 if (normalization_steps) {
426 mpi_limb_t divisor_limb_inverted;
427
428 divisor_limb <<= normalization_steps;
429
430 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
431 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
432 * most significant bit (with weight 2**N) implicit.
433 */
434 /* Special case for DIVISOR_LIMB == 100...000. */
435 if (!(divisor_limb << 1))
436 divisor_limb_inverted = ~(mpi_limb_t) 0;
437 else
438 udiv_qrnnd(divisor_limb_inverted, dummy,
439 -divisor_limb, 0, divisor_limb);
440
441 n1 = dividend_ptr[dividend_size - 1];
442 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
443
444 /* Possible optimization:
445 * if (r == 0
446 * && divisor_limb > ((n1 << normalization_steps)
447 * | (dividend_ptr[dividend_size - 2] >> ...)))
448 * ...one division less...
449 */
450 for (i = dividend_size - 2; i >= 0; i--) {
451 n0 = dividend_ptr[i];
452 UDIV_QRNND_PREINV(quot_ptr[i + 1], r, r,
453 ((n1 << normalization_steps)
454 | (n0 >>
455 (BITS_PER_MPI_LIMB -
456 normalization_steps))),
457 divisor_limb,
458 divisor_limb_inverted);
459 n1 = n0;
460 }
461 UDIV_QRNND_PREINV(quot_ptr[0], r, r,
462 n1 << normalization_steps,
463 divisor_limb, divisor_limb_inverted);
464 return r >> normalization_steps;
465 } else {
466 mpi_limb_t divisor_limb_inverted;
467
468 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
469 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
470 * most significant bit (with weight 2**N) implicit.
471 */
472 /* Special case for DIVISOR_LIMB == 100...000. */
473 if (!(divisor_limb << 1))
474 divisor_limb_inverted = ~(mpi_limb_t) 0;
475 else
476 udiv_qrnnd(divisor_limb_inverted, dummy,
477 -divisor_limb, 0, divisor_limb);
478
479 i = dividend_size - 1;
480 r = dividend_ptr[i];
481
482 if (r >= divisor_limb)
483 r = 0;
484 else
485 quot_ptr[i--] = 0;
486
487 for (; i >= 0; i--) {
488 n0 = dividend_ptr[i];
489 UDIV_QRNND_PREINV(quot_ptr[i], r, r,
490 n0, divisor_limb,
491 divisor_limb_inverted);
492 }
493 return r;
494 }
495 } else {
496 if (UDIV_NEEDS_NORMALIZATION) {
497 int normalization_steps;
498
499 count_leading_zeros(normalization_steps, divisor_limb);
500 if (normalization_steps) {
501 divisor_limb <<= normalization_steps;
502
503 n1 = dividend_ptr[dividend_size - 1];
504 r = n1 >> (BITS_PER_MPI_LIMB -
505 normalization_steps);
506
507 /* Possible optimization:
508 * if (r == 0
509 * && divisor_limb > ((n1 << normalization_steps)
510 * | (dividend_ptr[dividend_size - 2] >> ...)))
511 * ...one division less...
512 */
513 for (i = dividend_size - 2; i >= 0; i--) {
514 n0 = dividend_ptr[i];
515 udiv_qrnnd(quot_ptr[i + 1], r, r,
516 ((n1 << normalization_steps)
517 | (n0 >>
518 (BITS_PER_MPI_LIMB -
519 normalization_steps))),
520 divisor_limb);
521 n1 = n0;
522 }
523 udiv_qrnnd(quot_ptr[0], r, r,
524 n1 << normalization_steps,
525 divisor_limb);
526 return r >> normalization_steps;
527 }
528 }
529 /* No normalization needed, either because udiv_qrnnd doesn't require
530 * it, or because DIVISOR_LIMB is already normalized. */
531 i = dividend_size - 1;
532 r = dividend_ptr[i];
533
534 if (r >= divisor_limb)
535 r = 0;
536 else
537 quot_ptr[i--] = 0;
538
539 for (; i >= 0; i--) {
540 n0 = dividend_ptr[i];
541 udiv_qrnnd(quot_ptr[i], r, r, n0, divisor_limb);
542 }
543 return r;
544 }
545}
diff --git a/lib/mpi/mpih-mul.c b/lib/mpi/mpih-mul.c
index c69c5eef233b..7c841719fdfb 100644
--- a/lib/mpi/mpih-mul.c
+++ b/lib/mpi/mpih-mul.c
@@ -330,36 +330,6 @@ mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace)
330 } 330 }
331} 331}
332 332
333/* This should be made into an inline function in gmp.h. */
334int mpihelp_mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
335{
336 if (up == vp) {
337 if (size < KARATSUBA_THRESHOLD)
338 mpih_sqr_n_basecase(prodp, up, size);
339 else {
340 mpi_ptr_t tspace;
341 tspace = mpi_alloc_limb_space(2 * size);
342 if (!tspace)
343 return -ENOMEM;
344 mpih_sqr_n(prodp, up, size, tspace);
345 mpi_free_limb_space(tspace);
346 }
347 } else {
348 if (size < KARATSUBA_THRESHOLD)
349 mul_n_basecase(prodp, up, vp, size);
350 else {
351 mpi_ptr_t tspace;
352 tspace = mpi_alloc_limb_space(2 * size);
353 if (!tspace)
354 return -ENOMEM;
355 mul_n(prodp, up, vp, size, tspace);
356 mpi_free_limb_space(tspace);
357 }
358 }
359
360 return 0;
361}
362
363int 333int
364mpihelp_mul_karatsuba_case(mpi_ptr_t prodp, 334mpihelp_mul_karatsuba_case(mpi_ptr_t prodp,
365 mpi_ptr_t up, mpi_size_t usize, 335 mpi_ptr_t up, mpi_size_t usize,
diff --git a/lib/mpi/mpiutil.c b/lib/mpi/mpiutil.c
index 26e4ed31e256..657979f71bef 100644
--- a/lib/mpi/mpiutil.c
+++ b/lib/mpi/mpiutil.c
@@ -106,13 +106,6 @@ int mpi_resize(MPI a, unsigned nlimbs)
106 return 0; 106 return 0;
107} 107}
108 108
109void mpi_clear(MPI a)
110{
111 a->nlimbs = 0;
112 a->nbits = 0;
113 a->flags = 0;
114}
115
116void mpi_free(MPI a) 109void mpi_free(MPI a)
117{ 110{
118 if (!a) 111 if (!a)
@@ -128,84 +121,3 @@ void mpi_free(MPI a)
128 kfree(a); 121 kfree(a);
129} 122}
130EXPORT_SYMBOL_GPL(mpi_free); 123EXPORT_SYMBOL_GPL(mpi_free);
131
132/****************
133 * Note: This copy function should not interpret the MPI
134 * but copy it transparently.
135 */
136int mpi_copy(MPI *copied, const MPI a)
137{
138 size_t i;
139 MPI b;
140
141 *copied = NULL;
142
143 if (a) {
144 b = mpi_alloc(a->nlimbs);
145 if (!b)
146 return -ENOMEM;
147
148 b->nlimbs = a->nlimbs;
149 b->sign = a->sign;
150 b->flags = a->flags;
151 b->nbits = a->nbits;
152
153 for (i = 0; i < b->nlimbs; i++)
154 b->d[i] = a->d[i];
155
156 *copied = b;
157 }
158
159 return 0;
160}
161
162int mpi_set(MPI w, const MPI u)
163{
164 mpi_ptr_t wp, up;
165 mpi_size_t usize = u->nlimbs;
166 int usign = u->sign;
167
168 if (RESIZE_IF_NEEDED(w, (size_t) usize) < 0)
169 return -ENOMEM;
170
171 wp = w->d;
172 up = u->d;
173 MPN_COPY(wp, up, usize);
174 w->nlimbs = usize;
175 w->nbits = u->nbits;
176 w->flags = u->flags;
177 w->sign = usign;
178 return 0;
179}
180
181int mpi_set_ui(MPI w, unsigned long u)
182{
183 if (RESIZE_IF_NEEDED(w, 1) < 0)
184 return -ENOMEM;
185 w->d[0] = u;
186 w->nlimbs = u ? 1 : 0;
187 w->sign = 0;
188 w->nbits = 0;
189 w->flags = 0;
190 return 0;
191}
192
193MPI mpi_alloc_set_ui(unsigned long u)
194{
195 MPI w = mpi_alloc(1);
196 if (!w)
197 return w;
198 w->d[0] = u;
199 w->nlimbs = u ? 1 : 0;
200 w->sign = 0;
201 return w;
202}
203
204void mpi_swap(MPI a, MPI b)
205{
206 struct gcry_mpi tmp;
207
208 tmp = *a;
209 *a = *b;
210 *b = tmp;
211}
generated by cgit v1.2.2 (git 2.25.0) at 2025-11-27 23:17:36 -0500