aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorJames Morris <jmorris@namei.org>2012-01-08 20:16:48 -0500
committerJames Morris <jmorris@namei.org>2012-01-08 20:16:48 -0500
commit8fcc99549522fc7a0bbaeb5755855ab0d9a59ce8 (patch)
treea118eaef15d4ba22247f45ee01537ecc906cd161 /lib
parent805a6af8dba5dfdd35ec35dc52ec0122400b2610 (diff)
parent7b7e5916aa2f46e57f8bd8cb89c34620ebfda5da (diff)
Merge branch 'next' into for-linus
Conflicts: security/integrity/evm/evm_crypto.c Resolved upstream fix vs. next conflict manually. Signed-off-by: James Morris <jmorris@namei.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig25
-rw-r--r--lib/Makefile3
-rw-r--r--lib/digsig.c284
-rw-r--r--lib/mpi/Makefile32
-rw-r--r--lib/mpi/generic_mpi-asm-defs.h4
-rw-r--r--lib/mpi/generic_mpih-add1.c61
-rw-r--r--lib/mpi/generic_mpih-lshift.c63
-rw-r--r--lib/mpi/generic_mpih-mul1.c57
-rw-r--r--lib/mpi/generic_mpih-mul2.c60
-rw-r--r--lib/mpi/generic_mpih-mul3.c61
-rw-r--r--lib/mpi/generic_mpih-rshift.c63
-rw-r--r--lib/mpi/generic_mpih-sub1.c60
-rw-r--r--lib/mpi/longlong.h1478
-rw-r--r--lib/mpi/mpi-add.c234
-rw-r--r--lib/mpi/mpi-bit.c236
-rw-r--r--lib/mpi/mpi-cmp.c68
-rw-r--r--lib/mpi/mpi-div.c333
-rw-r--r--lib/mpi/mpi-gcd.c59
-rw-r--r--lib/mpi/mpi-inline.c31
-rw-r--r--lib/mpi/mpi-inline.h122
-rw-r--r--lib/mpi/mpi-internal.h261
-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-pow.c323
-rw-r--r--lib/mpi/mpi-scan.c136
-rw-r--r--lib/mpi/mpicoder.c365
-rw-r--r--lib/mpi/mpih-cmp.c56
-rw-r--r--lib/mpi/mpih-div.c541
-rw-r--r--lib/mpi/mpih-mul.c527
-rw-r--r--lib/mpi/mpiutil.c208
31 files changed, 6266 insertions, 0 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index 32f3e5ae2be5..5634e473ff6d 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -276,4 +276,29 @@ config CORDIC
276 so its calculations are in fixed point. Modules can select this 276 so its calculations are in fixed point. Modules can select this
277 when they require this function. Module will be called cordic. 277 when they require this function. Module will be called cordic.
278 278
279config MPILIB
280 tristate "Multiprecision maths library"
281 help
282 Multiprecision maths library from GnuPG.
283 It is used to implement RSA digital signature verification,
284 which is used by IMA/EVM digital signature extension.
285
286config MPILIB_EXTRA
287 bool "Multiprecision maths library - additional sources"
288 depends on MPILIB
289 help
290 Multiprecision maths library from GnuPG.
291 It is used to implement RSA digital signature verification,
292 which is used by IMA/EVM digital signature extension.
293 This code in unnecessary for RSA digital signature verification,
294 and can be compiled if needed.
295
296config DIGSIG
297 tristate "In-kernel signature checker"
298 depends on KEYS
299 select MPILIB
300 help
301 Digital signature verification. Currently only RSA is supported.
302 Implementation is done using GnuPG MPI library
303
279endmenu 304endmenu
diff --git a/lib/Makefile b/lib/Makefile
index a4da283f5dc0..0f5cff267aff 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -115,6 +115,9 @@ obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o
115 115
116obj-$(CONFIG_CORDIC) += cordic.o 116obj-$(CONFIG_CORDIC) += cordic.o
117 117
118obj-$(CONFIG_MPILIB) += mpi/
119obj-$(CONFIG_DIGSIG) += digsig.o
120
118hostprogs-y := gen_crc32table 121hostprogs-y := gen_crc32table
119clean-files := crc32table.h 122clean-files := crc32table.h
120 123
diff --git a/lib/digsig.c b/lib/digsig.c
new file mode 100644
index 000000000000..fd2402f67f89
--- /dev/null
+++ b/lib/digsig.c
@@ -0,0 +1,284 @@
1/*
2 * Copyright (C) 2011 Nokia Corporation
3 * Copyright (C) 2011 Intel Corporation
4 *
5 * Author:
6 * Dmitry Kasatkin <dmitry.kasatkin@nokia.com>
7 * <dmitry.kasatkin@intel.com>
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation, version 2 of the License.
12 *
13 * File: sign.c
14 * implements signature (RSA) verification
15 * pkcs decoding is based on LibTomCrypt code
16 */
17
18#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
19
20#include <linux/err.h>
21#include <linux/module.h>
22#include <linux/slab.h>
23#include <linux/key.h>
24#include <linux/crypto.h>
25#include <crypto/hash.h>
26#include <crypto/sha.h>
27#include <keys/user-type.h>
28#include <linux/mpi.h>
29#include <linux/digsig.h>
30
31static struct crypto_shash *shash;
32
33static int pkcs_1_v1_5_decode_emsa(const unsigned char *msg,
34 unsigned long msglen,
35 unsigned long modulus_bitlen,
36 unsigned char *out,
37 unsigned long *outlen,
38 int *is_valid)
39{
40 unsigned long modulus_len, ps_len, i;
41 int result;
42
43 /* default to invalid packet */
44 *is_valid = 0;
45
46 modulus_len = (modulus_bitlen >> 3) + (modulus_bitlen & 7 ? 1 : 0);
47
48 /* test message size */
49 if ((msglen > modulus_len) || (modulus_len < 11))
50 return -EINVAL;
51
52 /* separate encoded message */
53 if ((msg[0] != 0x00) || (msg[1] != (unsigned char)1)) {
54 result = -EINVAL;
55 goto bail;
56 }
57
58 for (i = 2; i < modulus_len - 1; i++)
59 if (msg[i] != 0xFF)
60 break;
61
62 /* separator check */
63 if (msg[i] != 0) {
64 /* There was no octet with hexadecimal value 0x00
65 to separate ps from m. */
66 result = -EINVAL;
67 goto bail;
68 }
69
70 ps_len = i - 2;
71
72 if (*outlen < (msglen - (2 + ps_len + 1))) {
73 *outlen = msglen - (2 + ps_len + 1);
74 result = -EOVERFLOW;
75 goto bail;
76 }
77
78 *outlen = (msglen - (2 + ps_len + 1));
79 memcpy(out, &msg[2 + ps_len + 1], *outlen);
80
81 /* valid packet */
82 *is_valid = 1;
83 result = 0;
84bail:
85 return result;
86}
87
88/*
89 * RSA Signature verification with public key
90 */
91static int digsig_verify_rsa(struct key *key,
92 const char *sig, int siglen,
93 const char *h, int hlen)
94{
95 int err = -EINVAL;
96 unsigned long len;
97 unsigned long mlen, mblen;
98 unsigned nret, l;
99 int valid, head, i;
100 unsigned char *out1 = NULL, *out2 = NULL;
101 MPI in = NULL, res = NULL, pkey[2];
102 uint8_t *p, *datap, *endp;
103 struct user_key_payload *ukp;
104 struct pubkey_hdr *pkh;
105
106 down_read(&key->sem);
107 ukp = key->payload.data;
108 pkh = (struct pubkey_hdr *)ukp->data;
109
110 if (pkh->version != 1)
111 goto err1;
112
113 if (pkh->algo != PUBKEY_ALGO_RSA)
114 goto err1;
115
116 if (pkh->nmpi != 2)
117 goto err1;
118
119 datap = pkh->mpi;
120 endp = datap + ukp->datalen;
121
122 for (i = 0; i < pkh->nmpi; i++) {
123 unsigned int remaining = endp - datap;
124 pkey[i] = mpi_read_from_buffer(datap, &remaining);
125 datap += remaining;
126 }
127
128 mblen = mpi_get_nbits(pkey[0]);
129 mlen = (mblen + 7)/8;
130
131 err = -ENOMEM;
132
133 out1 = kzalloc(mlen, GFP_KERNEL);
134 if (!out1)
135 goto err;
136
137 out2 = kzalloc(mlen, GFP_KERNEL);
138 if (!out2)
139 goto err;
140
141 nret = siglen;
142 in = mpi_read_from_buffer(sig, &nret);
143 if (!in)
144 goto err;
145
146 res = mpi_alloc(mpi_get_nlimbs(in) * 2);
147 if (!res)
148 goto err;
149
150 err = mpi_powm(res, in, pkey[1], pkey[0]);
151 if (err)
152 goto err;
153
154 if (mpi_get_nlimbs(res) * BYTES_PER_MPI_LIMB > mlen) {
155 err = -EINVAL;
156 goto err;
157 }
158
159 p = mpi_get_buffer(res, &l, NULL);
160 if (!p) {
161 err = -EINVAL;
162 goto err;
163 }
164
165 len = mlen;
166 head = len - l;
167 memset(out1, 0, head);
168 memcpy(out1 + head, p, l);
169
170 err = -EINVAL;
171 pkcs_1_v1_5_decode_emsa(out1, len, mblen, out2, &len, &valid);
172
173 if (valid && len == hlen)
174 err = memcmp(out2, h, hlen);
175
176err:
177 mpi_free(in);
178 mpi_free(res);
179 kfree(out1);
180 kfree(out2);
181 mpi_free(pkey[0]);
182 mpi_free(pkey[1]);
183err1:
184 up_read(&key->sem);
185
186 return err;
187}
188
189/**
190 * digsig_verify() - digital signature verification with public key
191 * @keyring: keyring to search key in
192 * @sig: digital signature
193 * @sigen: length of the signature
194 * @data: data
195 * @datalen: length of the data
196 * @return: 0 on success, -EINVAL otherwise
197 *
198 * Verifies data integrity against digital signature.
199 * Currently only RSA is supported.
200 * Normally hash of the content is used as a data for this function.
201 *
202 */
203int digsig_verify(struct key *keyring, const char *sig, int siglen,
204 const char *data, int datalen)
205{
206 int err = -ENOMEM;
207 struct signature_hdr *sh = (struct signature_hdr *)sig;
208 struct shash_desc *desc = NULL;
209 unsigned char hash[SHA1_DIGEST_SIZE];
210 struct key *key;
211 char name[20];
212
213 if (siglen < sizeof(*sh) + 2)
214 return -EINVAL;
215
216 if (sh->algo != PUBKEY_ALGO_RSA)
217 return -ENOTSUPP;
218
219 sprintf(name, "%llX", __be64_to_cpup((uint64_t *)sh->keyid));
220
221 if (keyring) {
222 /* search in specific keyring */
223 key_ref_t kref;
224 kref = keyring_search(make_key_ref(keyring, 1UL),
225 &key_type_user, name);
226 if (IS_ERR(kref))
227 key = ERR_PTR(PTR_ERR(kref));
228 else
229 key = key_ref_to_ptr(kref);
230 } else {
231 key = request_key(&key_type_user, name, NULL);
232 }
233 if (IS_ERR(key)) {
234 pr_err("key not found, id: %s\n", name);
235 return PTR_ERR(key);
236 }
237
238 desc = kzalloc(sizeof(*desc) + crypto_shash_descsize(shash),
239 GFP_KERNEL);
240 if (!desc)
241 goto err;
242
243 desc->tfm = shash;
244 desc->flags = CRYPTO_TFM_REQ_MAY_SLEEP;
245
246 crypto_shash_init(desc);
247 crypto_shash_update(desc, data, datalen);
248 crypto_shash_update(desc, sig, sizeof(*sh));
249 crypto_shash_final(desc, hash);
250
251 kfree(desc);
252
253 /* pass signature mpis address */
254 err = digsig_verify_rsa(key, sig + sizeof(*sh), siglen - sizeof(*sh),
255 hash, sizeof(hash));
256
257err:
258 key_put(key);
259
260 return err ? -EINVAL : 0;
261}
262EXPORT_SYMBOL_GPL(digsig_verify);
263
264static int __init digsig_init(void)
265{
266 shash = crypto_alloc_shash("sha1", 0, 0);
267 if (IS_ERR(shash)) {
268 pr_err("shash allocation failed\n");
269 return PTR_ERR(shash);
270 }
271
272 return 0;
273
274}
275
276static void __exit digsig_cleanup(void)
277{
278 crypto_free_shash(shash);
279}
280
281module_init(digsig_init);
282module_exit(digsig_cleanup);
283
284MODULE_LICENSE("GPL");
diff --git a/lib/mpi/Makefile b/lib/mpi/Makefile
new file mode 100644
index 000000000000..567d52e74d77
--- /dev/null
+++ b/lib/mpi/Makefile
@@ -0,0 +1,32 @@
1#
2# MPI multiprecision maths library (from gpg)
3#
4
5obj-$(CONFIG_MPILIB) = mpi.o
6
7mpi-y = \
8 generic_mpih-lshift.o \
9 generic_mpih-mul1.o \
10 generic_mpih-mul2.o \
11 generic_mpih-mul3.o \
12 generic_mpih-rshift.o \
13 generic_mpih-sub1.o \
14 generic_mpih-add1.o \
15 mpicoder.o \
16 mpi-bit.o \
17 mpih-cmp.o \
18 mpih-div.o \
19 mpih-mul.o \
20 mpi-pow.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
new file mode 100644
index 000000000000..047d1f5a7249
--- /dev/null
+++ b/lib/mpi/generic_mpi-asm-defs.h
@@ -0,0 +1,4 @@
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/generic_mpih-add1.c b/lib/mpi/generic_mpih-add1.c
new file mode 100644
index 000000000000..c94c7dd344b3
--- /dev/null
+++ b/lib/mpi/generic_mpih-add1.c
@@ -0,0 +1,61 @@
1/* mpihelp-add_1.c - MPI helper functions
2 * Copyright (C) 1994, 1996, 1997, 1998,
3 * 2000 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#include "longlong.h"
32
33mpi_limb_t
34mpihelp_add_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
35 mpi_ptr_t s2_ptr, mpi_size_t size)
36{
37 mpi_limb_t x, y, cy;
38 mpi_size_t j;
39
40 /* The loop counter and index J goes from -SIZE to -1. This way
41 the loop becomes faster. */
42 j = -size;
43
44 /* Offset the base pointers to compensate for the negative indices. */
45 s1_ptr -= j;
46 s2_ptr -= j;
47 res_ptr -= j;
48
49 cy = 0;
50 do {
51 y = s2_ptr[j];
52 x = s1_ptr[j];
53 y += cy; /* add previous carry to one addend */
54 cy = y < cy; /* get out carry from that addition */
55 y += x; /* add other addend */
56 cy += y < x; /* get out carry from that add, combine */
57 res_ptr[j] = y;
58 } while (++j);
59
60 return cy;
61}
diff --git a/lib/mpi/generic_mpih-lshift.c b/lib/mpi/generic_mpih-lshift.c
new file mode 100644
index 000000000000..86318927231a
--- /dev/null
+++ b/lib/mpi/generic_mpih-lshift.c
@@ -0,0 +1,63 @@
1/* mpihelp-lshift.c - MPI helper functions
2 * Copyright (C) 1994, 1996, 1998, 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 * 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 "mpi-internal.h"
30
31/* Shift U (pointed to by UP and USIZE digits long) CNT bits to the left
32 * and store the USIZE least significant digits of the result at WP.
33 * Return the bits shifted out from the most significant digit.
34 *
35 * Argument constraints:
36 * 1. 0 < CNT < BITS_PER_MP_LIMB
37 * 2. If the result is to be written over the input, WP must be >= UP.
38 */
39
40mpi_limb_t
41mpihelp_lshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned int cnt)
42{
43 mpi_limb_t high_limb, low_limb;
44 unsigned sh_1, sh_2;
45 mpi_size_t i;
46 mpi_limb_t retval;
47
48 sh_1 = cnt;
49 wp += 1;
50 sh_2 = BITS_PER_MPI_LIMB - sh_1;
51 i = usize - 1;
52 low_limb = up[i];
53 retval = low_limb >> sh_2;
54 high_limb = low_limb;
55 while (--i >= 0) {
56 low_limb = up[i];
57 wp[i] = (high_limb << sh_1) | (low_limb >> sh_2);
58 high_limb = low_limb;
59 }
60 wp[i] = high_limb << sh_1;
61
62 return retval;
63}
diff --git a/lib/mpi/generic_mpih-mul1.c b/lib/mpi/generic_mpih-mul1.c
new file mode 100644
index 000000000000..1668dfd9092c
--- /dev/null
+++ b/lib/mpi/generic_mpih-mul1.c
@@ -0,0 +1,57 @@
1/* mpihelp-mul_1.c - MPI helper functions
2 * Copyright (C) 1994, 1996, 1997, 1998, 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 * 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 "mpi-internal.h"
30#include "longlong.h"
31
32mpi_limb_t
33mpihelp_mul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
34 mpi_limb_t s2_limb)
35{
36 mpi_limb_t cy_limb;
37 mpi_size_t j;
38 mpi_limb_t prod_high, prod_low;
39
40 /* The loop counter and index J goes from -S1_SIZE to -1. This way
41 * the loop becomes faster. */
42 j = -s1_size;
43
44 /* Offset the base pointers to compensate for the negative indices. */
45 s1_ptr -= j;
46 res_ptr -= j;
47
48 cy_limb = 0;
49 do {
50 umul_ppmm(prod_high, prod_low, s1_ptr[j], s2_limb);
51 prod_low += cy_limb;
52 cy_limb = (prod_low < cy_limb ? 1 : 0) + prod_high;
53 res_ptr[j] = prod_low;
54 } while (++j);
55
56 return cy_limb;
57}
diff --git a/lib/mpi/generic_mpih-mul2.c b/lib/mpi/generic_mpih-mul2.c
new file mode 100644
index 000000000000..8a7b29ee1740
--- /dev/null
+++ b/lib/mpi/generic_mpih-mul2.c
@@ -0,0 +1,60 @@
1/* mpihelp-mul_2.c - MPI helper functions
2 * Copyright (C) 1994, 1996, 1997, 1998, 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 * 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 "mpi-internal.h"
30#include "longlong.h"
31
32mpi_limb_t
33mpihelp_addmul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
34 mpi_size_t s1_size, mpi_limb_t s2_limb)
35{
36 mpi_limb_t cy_limb;
37 mpi_size_t j;
38 mpi_limb_t prod_high, prod_low;
39 mpi_limb_t x;
40
41 /* The loop counter and index J goes from -SIZE to -1. This way
42 * the loop becomes faster. */
43 j = -s1_size;
44 res_ptr -= j;
45 s1_ptr -= j;
46
47 cy_limb = 0;
48 do {
49 umul_ppmm(prod_high, prod_low, s1_ptr[j], s2_limb);
50
51 prod_low += cy_limb;
52 cy_limb = (prod_low < cy_limb ? 1 : 0) + prod_high;
53
54 x = res_ptr[j];
55 prod_low = x + prod_low;
56 cy_limb += prod_low < x ? 1 : 0;
57 res_ptr[j] = prod_low;
58 } while (++j);
59 return cy_limb;
60}
diff --git a/lib/mpi/generic_mpih-mul3.c b/lib/mpi/generic_mpih-mul3.c
new file mode 100644
index 000000000000..f96df327be63
--- /dev/null
+++ b/lib/mpi/generic_mpih-mul3.c
@@ -0,0 +1,61 @@
1/* mpihelp-mul_3.c - MPI helper functions
2 * Copyright (C) 1994, 1996, 1997, 1998, 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 * 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 "mpi-internal.h"
30#include "longlong.h"
31
32mpi_limb_t
33mpihelp_submul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
34 mpi_size_t s1_size, mpi_limb_t s2_limb)
35{
36 mpi_limb_t cy_limb;
37 mpi_size_t j;
38 mpi_limb_t prod_high, prod_low;
39 mpi_limb_t x;
40
41 /* The loop counter and index J goes from -SIZE to -1. This way
42 * the loop becomes faster. */
43 j = -s1_size;
44 res_ptr -= j;
45 s1_ptr -= j;
46
47 cy_limb = 0;
48 do {
49 umul_ppmm(prod_high, prod_low, s1_ptr[j], s2_limb);
50
51 prod_low += cy_limb;
52 cy_limb = (prod_low < cy_limb ? 1 : 0) + prod_high;
53
54 x = res_ptr[j];
55 prod_low = x - prod_low;
56 cy_limb += prod_low > x ? 1 : 0;
57 res_ptr[j] = prod_low;
58 } while (++j);
59
60 return cy_limb;
61}
diff --git a/lib/mpi/generic_mpih-rshift.c b/lib/mpi/generic_mpih-rshift.c
new file mode 100644
index 000000000000..ffa328818ca6
--- /dev/null
+++ b/lib/mpi/generic_mpih-rshift.c
@@ -0,0 +1,63 @@
1/* mpih-rshift.c - MPI helper functions
2 * Copyright (C) 1994, 1996, 1998, 1999,
3 * 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 "mpi-internal.h"
31
32/* Shift U (pointed to by UP and USIZE limbs long) CNT bits to the right
33 * and store the USIZE least significant limbs of the result at WP.
34 * The bits shifted out to the right are returned.
35 *
36 * Argument constraints:
37 * 1. 0 < CNT < BITS_PER_MP_LIMB
38 * 2. If the result is to be written over the input, WP must be <= UP.
39 */
40
41mpi_limb_t
42mpihelp_rshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned cnt)
43{
44 mpi_limb_t high_limb, low_limb;
45 unsigned sh_1, sh_2;
46 mpi_size_t i;
47 mpi_limb_t retval;
48
49 sh_1 = cnt;
50 wp -= 1;
51 sh_2 = BITS_PER_MPI_LIMB - sh_1;
52 high_limb = up[0];
53 retval = high_limb << sh_2;
54 low_limb = high_limb;
55 for (i = 1; i < usize; i++) {
56 high_limb = up[i];
57 wp[i] = (low_limb >> sh_1) | (high_limb << sh_2);
58 low_limb = high_limb;
59 }
60 wp[i] = low_limb >> sh_1;
61
62 return retval;
63}
diff --git a/lib/mpi/generic_mpih-sub1.c b/lib/mpi/generic_mpih-sub1.c
new file mode 100644
index 000000000000..5d98ab7d6853
--- /dev/null
+++ b/lib/mpi/generic_mpih-sub1.c
@@ -0,0 +1,60 @@
1/* mpihelp-add_2.c - MPI helper functions
2 * Copyright (C) 1994, 1996, 1997, 1998, 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 * 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 "mpi-internal.h"
30#include "longlong.h"
31
32mpi_limb_t
33mpihelp_sub_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
34 mpi_ptr_t s2_ptr, mpi_size_t size)
35{
36 mpi_limb_t x, y, cy;
37 mpi_size_t j;
38
39 /* The loop counter and index J goes from -SIZE to -1. This way
40 the loop becomes faster. */
41 j = -size;
42
43 /* Offset the base pointers to compensate for the negative indices. */
44 s1_ptr -= j;
45 s2_ptr -= j;
46 res_ptr -= j;
47
48 cy = 0;
49 do {
50 y = s2_ptr[j];
51 x = s1_ptr[j];
52 y += cy; /* add previous carry to subtrahend */
53 cy = y < cy; /* get out carry from that addition */
54 y = x - y; /* main subtract */
55 cy += y > x; /* get out carry from the subtract, combine */
56 res_ptr[j] = y;
57 } while (++j);
58
59 return cy;
60}
diff --git a/lib/mpi/longlong.h b/lib/mpi/longlong.h
new file mode 100644
index 000000000000..b87487b40a8b
--- /dev/null
+++ b/lib/mpi/longlong.h
@@ -0,0 +1,1478 @@
1/* longlong.h -- definitions for mixed size 32/64 bit arithmetic.
2 * Note: I added some stuff for use with gnupg
3 *
4 * Copyright (C) 1991, 1992, 1993, 1994, 1996, 1998,
5 * 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
6 *
7 * This file is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU Library General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or (at your
10 * option) any later version.
11 *
12 * This file is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
15 * License for more details.
16 *
17 * You should have received a copy of the GNU Library General Public License
18 * along with this file; see the file COPYING.LIB. If not, write to
19 * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20 * MA 02111-1307, USA. */
21
22/* You have to define the following before including this file:
23 *
24 * UWtype -- An unsigned type, default type for operations (typically a "word")
25 * UHWtype -- An unsigned type, at least half the size of UWtype.
26 * UDWtype -- An unsigned type, at least twice as large a UWtype
27 * W_TYPE_SIZE -- size in bits of UWtype
28 *
29 * SItype, USItype -- Signed and unsigned 32 bit types.
30 * DItype, UDItype -- Signed and unsigned 64 bit types.
31 *
32 * On a 32 bit machine UWtype should typically be USItype;
33 * on a 64 bit machine, UWtype should typically be UDItype.
34*/
35
36#define __BITS4 (W_TYPE_SIZE / 4)
37#define __ll_B ((UWtype) 1 << (W_TYPE_SIZE / 2))
38#define __ll_lowpart(t) ((UWtype) (t) & (__ll_B - 1))
39#define __ll_highpart(t) ((UWtype) (t) >> (W_TYPE_SIZE / 2))
40
41/* This is used to make sure no undesirable sharing between different libraries
42 that use this file takes place. */
43#ifndef __MPN
44#define __MPN(x) __##x
45#endif
46
47/* Define auxiliary asm macros.
48 *
49 * 1) umul_ppmm(high_prod, low_prod, multipler, multiplicand) multiplies two
50 * UWtype integers MULTIPLER and MULTIPLICAND, and generates a two UWtype
51 * word product in HIGH_PROD and LOW_PROD.
52 *
53 * 2) __umulsidi3(a,b) multiplies two UWtype integers A and B, and returns a
54 * UDWtype product. This is just a variant of umul_ppmm.
55
56 * 3) udiv_qrnnd(quotient, remainder, high_numerator, low_numerator,
57 * denominator) divides a UDWtype, composed by the UWtype integers
58 * HIGH_NUMERATOR and LOW_NUMERATOR, by DENOMINATOR and places the quotient
59 * in QUOTIENT and the remainder in REMAINDER. HIGH_NUMERATOR must be less
60 * than DENOMINATOR for correct operation. If, in addition, the most
61 * significant bit of DENOMINATOR must be 1, then the pre-processor symbol
62 * UDIV_NEEDS_NORMALIZATION is defined to 1.
63 * 4) sdiv_qrnnd(quotient, remainder, high_numerator, low_numerator,
64 * denominator). Like udiv_qrnnd but the numbers are signed. The quotient
65 * is rounded towards 0.
66 *
67 * 5) count_leading_zeros(count, x) counts the number of zero-bits from the
68 * msb to the first non-zero bit in the UWtype X. This is the number of
69 * steps X needs to be shifted left to set the msb. Undefined for X == 0,
70 * unless the symbol COUNT_LEADING_ZEROS_0 is defined to some value.
71 *
72 * 6) count_trailing_zeros(count, x) like count_leading_zeros, but counts
73 * from the least significant end.
74 *
75 * 7) add_ssaaaa(high_sum, low_sum, high_addend_1, low_addend_1,
76 * high_addend_2, low_addend_2) adds two UWtype integers, composed by
77 * HIGH_ADDEND_1 and LOW_ADDEND_1, and HIGH_ADDEND_2 and LOW_ADDEND_2
78 * respectively. The result is placed in HIGH_SUM and LOW_SUM. Overflow
79 * (i.e. carry out) is not stored anywhere, and is lost.
80 *
81 * 8) sub_ddmmss(high_difference, low_difference, high_minuend, low_minuend,
82 * high_subtrahend, low_subtrahend) subtracts two two-word UWtype integers,
83 * composed by HIGH_MINUEND_1 and LOW_MINUEND_1, and HIGH_SUBTRAHEND_2 and
84 * LOW_SUBTRAHEND_2 respectively. The result is placed in HIGH_DIFFERENCE
85 * and LOW_DIFFERENCE. Overflow (i.e. carry out) is not stored anywhere,
86 * and is lost.
87 *
88 * If any of these macros are left undefined for a particular CPU,
89 * C macros are used. */
90
91/* The CPUs come in alphabetical order below.
92 *
93 * Please add support for more CPUs here, or improve the current support
94 * for the CPUs below! */
95
96#if defined(__GNUC__) && !defined(NO_ASM)
97
98/* We sometimes need to clobber "cc" with gcc2, but that would not be
99 understood by gcc1. Use cpp to avoid major code duplication. */
100#if __GNUC__ < 2
101#define __CLOBBER_CC
102#define __AND_CLOBBER_CC
103#else /* __GNUC__ >= 2 */
104#define __CLOBBER_CC : "cc"
105#define __AND_CLOBBER_CC , "cc"
106#endif /* __GNUC__ < 2 */
107
108/***************************************
109 ************** A29K *****************
110 ***************************************/
111#if (defined(__a29k__) || defined(_AM29K)) && W_TYPE_SIZE == 32
112#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
113 __asm__ ("add %1,%4,%5\n" \
114 "addc %0,%2,%3" \
115 : "=r" ((USItype)(sh)), \
116 "=&r" ((USItype)(sl)) \
117 : "%r" ((USItype)(ah)), \
118 "rI" ((USItype)(bh)), \
119 "%r" ((USItype)(al)), \
120 "rI" ((USItype)(bl)))
121#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
122 __asm__ ("sub %1,%4,%5\n" \
123 "subc %0,%2,%3" \
124 : "=r" ((USItype)(sh)), \
125 "=&r" ((USItype)(sl)) \
126 : "r" ((USItype)(ah)), \
127 "rI" ((USItype)(bh)), \
128 "r" ((USItype)(al)), \
129 "rI" ((USItype)(bl)))
130#define umul_ppmm(xh, xl, m0, m1) \
131do { \
132 USItype __m0 = (m0), __m1 = (m1); \
133 __asm__ ("multiplu %0,%1,%2" \
134 : "=r" ((USItype)(xl)) \
135 : "r" (__m0), \
136 "r" (__m1)); \
137 __asm__ ("multmu %0,%1,%2" \
138 : "=r" ((USItype)(xh)) \
139 : "r" (__m0), \
140 "r" (__m1)); \
141} while (0)
142#define udiv_qrnnd(q, r, n1, n0, d) \
143 __asm__ ("dividu %0,%3,%4" \
144 : "=r" ((USItype)(q)), \
145 "=q" ((USItype)(r)) \
146 : "1" ((USItype)(n1)), \
147 "r" ((USItype)(n0)), \
148 "r" ((USItype)(d)))
149
150#define count_leading_zeros(count, x) \
151 __asm__ ("clz %0,%1" \
152 : "=r" ((USItype)(count)) \
153 : "r" ((USItype)(x)))
154#define COUNT_LEADING_ZEROS_0 32
155#endif /* __a29k__ */
156
157#if defined(__alpha) && W_TYPE_SIZE == 64
158#define umul_ppmm(ph, pl, m0, m1) \
159do { \
160 UDItype __m0 = (m0), __m1 = (m1); \
161 __asm__ ("umulh %r1,%2,%0" \
162 : "=r" ((UDItype) ph) \
163 : "%rJ" (__m0), \
164 "rI" (__m1)); \
165 (pl) = __m0 * __m1; \
166 } while (0)
167#define UMUL_TIME 46
168#ifndef LONGLONG_STANDALONE
169#define udiv_qrnnd(q, r, n1, n0, d) \
170do { UDItype __r; \
171 (q) = __udiv_qrnnd(&__r, (n1), (n0), (d)); \
172 (r) = __r; \
173} while (0)
174extern UDItype __udiv_qrnnd();
175#define UDIV_TIME 220
176#endif /* LONGLONG_STANDALONE */
177#endif /* __alpha */
178
179/***************************************
180 ************** ARM ******************
181 ***************************************/
182#if defined(__arm__) && W_TYPE_SIZE == 32
183#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
184 __asm__ ("adds %1, %4, %5\n" \
185 "adc %0, %2, %3" \
186 : "=r" ((USItype)(sh)), \
187 "=&r" ((USItype)(sl)) \
188 : "%r" ((USItype)(ah)), \
189 "rI" ((USItype)(bh)), \
190 "%r" ((USItype)(al)), \
191 "rI" ((USItype)(bl)))
192#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
193 __asm__ ("subs %1, %4, %5\n" \
194 "sbc %0, %2, %3" \
195 : "=r" ((USItype)(sh)), \
196 "=&r" ((USItype)(sl)) \
197 : "r" ((USItype)(ah)), \
198 "rI" ((USItype)(bh)), \
199 "r" ((USItype)(al)), \
200 "rI" ((USItype)(bl)))
201#if defined __ARM_ARCH_2__ || defined __ARM_ARCH_3__
202#define umul_ppmm(xh, xl, a, b) \
203 __asm__ ("%@ Inlined umul_ppmm\n" \
204 "mov %|r0, %2, lsr #16 @ AAAA\n" \
205 "mov %|r2, %3, lsr #16 @ BBBB\n" \
206 "bic %|r1, %2, %|r0, lsl #16 @ aaaa\n" \
207 "bic %0, %3, %|r2, lsl #16 @ bbbb\n" \
208 "mul %1, %|r1, %|r2 @ aaaa * BBBB\n" \
209 "mul %|r2, %|r0, %|r2 @ AAAA * BBBB\n" \
210 "mul %|r1, %0, %|r1 @ aaaa * bbbb\n" \
211 "mul %0, %|r0, %0 @ AAAA * bbbb\n" \
212 "adds %|r0, %1, %0 @ central sum\n" \
213 "addcs %|r2, %|r2, #65536\n" \
214 "adds %1, %|r1, %|r0, lsl #16\n" \
215 "adc %0, %|r2, %|r0, lsr #16" \
216 : "=&r" ((USItype)(xh)), \
217 "=r" ((USItype)(xl)) \
218 : "r" ((USItype)(a)), \
219 "r" ((USItype)(b)) \
220 : "r0", "r1", "r2")
221#else
222#define umul_ppmm(xh, xl, a, b) \
223 __asm__ ("%@ Inlined umul_ppmm\n" \
224 "umull %r1, %r0, %r2, %r3" \
225 : "=&r" ((USItype)(xh)), \
226 "=r" ((USItype)(xl)) \
227 : "r" ((USItype)(a)), \
228 "r" ((USItype)(b)) \
229 : "r0", "r1")
230#endif
231#define UMUL_TIME 20
232#define UDIV_TIME 100
233#endif /* __arm__ */
234
235/***************************************
236 ************** CLIPPER **************
237 ***************************************/
238#if defined(__clipper__) && W_TYPE_SIZE == 32
239#define umul_ppmm(w1, w0, u, v) \
240 ({union {UDItype __ll; \
241 struct {USItype __l, __h; } __i; \
242 } __xx; \
243 __asm__ ("mulwux %2,%0" \
244 : "=r" (__xx.__ll) \
245 : "%0" ((USItype)(u)), \
246 "r" ((USItype)(v))); \
247 (w1) = __xx.__i.__h; (w0) = __xx.__i.__l; })
248#define smul_ppmm(w1, w0, u, v) \
249 ({union {DItype __ll; \
250 struct {SItype __l, __h; } __i; \
251 } __xx; \
252 __asm__ ("mulwx %2,%0" \
253 : "=r" (__xx.__ll) \
254 : "%0" ((SItype)(u)), \
255 "r" ((SItype)(v))); \
256 (w1) = __xx.__i.__h; (w0) = __xx.__i.__l; })
257#define __umulsidi3(u, v) \
258 ({UDItype __w; \
259 __asm__ ("mulwux %2,%0" \
260 : "=r" (__w) \
261 : "%0" ((USItype)(u)), \
262 "r" ((USItype)(v))); \
263 __w; })
264#endif /* __clipper__ */
265
266/***************************************
267 ************** GMICRO ***************
268 ***************************************/
269#if defined(__gmicro__) && W_TYPE_SIZE == 32
270#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
271 __asm__ ("add.w %5,%1\n" \
272 "addx %3,%0" \
273 : "=g" ((USItype)(sh)), \
274 "=&g" ((USItype)(sl)) \
275 : "%0" ((USItype)(ah)), \
276 "g" ((USItype)(bh)), \
277 "%1" ((USItype)(al)), \
278 "g" ((USItype)(bl)))
279#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
280 __asm__ ("sub.w %5,%1\n" \
281 "subx %3,%0" \
282 : "=g" ((USItype)(sh)), \
283 "=&g" ((USItype)(sl)) \
284 : "0" ((USItype)(ah)), \
285 "g" ((USItype)(bh)), \
286 "1" ((USItype)(al)), \
287 "g" ((USItype)(bl)))
288#define umul_ppmm(ph, pl, m0, m1) \
289 __asm__ ("mulx %3,%0,%1" \
290 : "=g" ((USItype)(ph)), \
291 "=r" ((USItype)(pl)) \
292 : "%0" ((USItype)(m0)), \
293 "g" ((USItype)(m1)))
294#define udiv_qrnnd(q, r, nh, nl, d) \
295 __asm__ ("divx %4,%0,%1" \
296 : "=g" ((USItype)(q)), \
297 "=r" ((USItype)(r)) \
298 : "1" ((USItype)(nh)), \
299 "0" ((USItype)(nl)), \
300 "g" ((USItype)(d)))
301#define count_leading_zeros(count, x) \
302 __asm__ ("bsch/1 %1,%0" \
303 : "=g" (count) \
304 : "g" ((USItype)(x)), \
305 "0" ((USItype)0))
306#endif
307
308/***************************************
309 ************** HPPA *****************
310 ***************************************/
311#if defined(__hppa) && W_TYPE_SIZE == 32
312#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
313 __asm__ ("add %4,%5,%1\n" \
314 "addc %2,%3,%0" \
315 : "=r" ((USItype)(sh)), \
316 "=&r" ((USItype)(sl)) \
317 : "%rM" ((USItype)(ah)), \
318 "rM" ((USItype)(bh)), \
319 "%rM" ((USItype)(al)), \
320 "rM" ((USItype)(bl)))
321#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
322 __asm__ ("sub %4,%5,%1\n" \
323 "subb %2,%3,%0" \
324 : "=r" ((USItype)(sh)), \
325 "=&r" ((USItype)(sl)) \
326 : "rM" ((USItype)(ah)), \
327 "rM" ((USItype)(bh)), \
328 "rM" ((USItype)(al)), \
329 "rM" ((USItype)(bl)))
330#if defined(_PA_RISC1_1)
331#define umul_ppmm(wh, wl, u, v) \
332do { \
333 union {UDItype __ll; \
334 struct {USItype __h, __l; } __i; \
335 } __xx; \
336 __asm__ ("xmpyu %1,%2,%0" \
337 : "=*f" (__xx.__ll) \
338 : "*f" ((USItype)(u)), \
339 "*f" ((USItype)(v))); \
340 (wh) = __xx.__i.__h; \
341 (wl) = __xx.__i.__l; \
342} while (0)
343#define UMUL_TIME 8
344#define UDIV_TIME 60
345#else
346#define UMUL_TIME 40
347#define UDIV_TIME 80
348#endif
349#ifndef LONGLONG_STANDALONE
350#define udiv_qrnnd(q, r, n1, n0, d) \
351do { USItype __r; \
352 (q) = __udiv_qrnnd(&__r, (n1), (n0), (d)); \
353 (r) = __r; \
354} while (0)
355extern USItype __udiv_qrnnd();
356#endif /* LONGLONG_STANDALONE */
357#define count_leading_zeros(count, x) \
358do { \
359 USItype __tmp; \
360 __asm__ ( \
361 "ldi 1,%0\n" \
362 "extru,= %1,15,16,%%r0 ; Bits 31..16 zero?\n" \
363 "extru,tr %1,15,16,%1 ; No. Shift down, skip add.\n" \
364 "ldo 16(%0),%0 ; Yes. Perform add.\n" \
365 "extru,= %1,23,8,%%r0 ; Bits 15..8 zero?\n" \
366 "extru,tr %1,23,8,%1 ; No. Shift down, skip add.\n" \
367 "ldo 8(%0),%0 ; Yes. Perform add.\n" \
368 "extru,= %1,27,4,%%r0 ; Bits 7..4 zero?\n" \
369 "extru,tr %1,27,4,%1 ; No. Shift down, skip add.\n" \
370 "ldo 4(%0),%0 ; Yes. Perform add.\n" \
371 "extru,= %1,29,2,%%r0 ; Bits 3..2 zero?\n" \
372 "extru,tr %1,29,2,%1 ; No. Shift down, skip add.\n" \
373 "ldo 2(%0),%0 ; Yes. Perform add.\n" \
374 "extru %1,30,1,%1 ; Extract bit 1.\n" \
375 "sub %0,%1,%0 ; Subtract it. " \
376 : "=r" (count), "=r" (__tmp) : "1" (x)); \
377} while (0)
378#endif /* hppa */
379
380/***************************************
381 ************** I370 *****************
382 ***************************************/
383#if (defined(__i370__) || defined(__mvs__)) && W_TYPE_SIZE == 32
384#define umul_ppmm(xh, xl, m0, m1) \
385do { \
386 union {UDItype __ll; \
387 struct {USItype __h, __l; } __i; \
388 } __xx; \
389 USItype __m0 = (m0), __m1 = (m1); \
390 __asm__ ("mr %0,%3" \
391 : "=r" (__xx.__i.__h), \
392 "=r" (__xx.__i.__l) \
393 : "%1" (__m0), \
394 "r" (__m1)); \
395 (xh) = __xx.__i.__h; (xl) = __xx.__i.__l; \
396 (xh) += ((((SItype) __m0 >> 31) & __m1) \
397 + (((SItype) __m1 >> 31) & __m0)); \
398} while (0)
399#define smul_ppmm(xh, xl, m0, m1) \
400do { \
401 union {DItype __ll; \
402 struct {USItype __h, __l; } __i; \
403 } __xx; \
404 __asm__ ("mr %0,%3" \
405 : "=r" (__xx.__i.__h), \
406 "=r" (__xx.__i.__l) \
407 : "%1" (m0), \
408 "r" (m1)); \
409 (xh) = __xx.__i.__h; (xl) = __xx.__i.__l; \
410} while (0)
411#define sdiv_qrnnd(q, r, n1, n0, d) \
412do { \
413 union {DItype __ll; \
414 struct {USItype __h, __l; } __i; \
415 } __xx; \
416 __xx.__i.__h = n1; __xx.__i.__l = n0; \
417 __asm__ ("dr %0,%2" \
418 : "=r" (__xx.__ll) \
419 : "0" (__xx.__ll), "r" (d)); \
420 (q) = __xx.__i.__l; (r) = __xx.__i.__h; \
421} while (0)
422#endif
423
424/***************************************
425 ************** I386 *****************
426 ***************************************/
427#undef __i386__
428#if (defined(__i386__) || defined(__i486__)) && W_TYPE_SIZE == 32
429#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
430 __asm__ ("addl %5,%1\n" \
431 "adcl %3,%0" \
432 : "=r" ((USItype)(sh)), \
433 "=&r" ((USItype)(sl)) \
434 : "%0" ((USItype)(ah)), \
435 "g" ((USItype)(bh)), \
436 "%1" ((USItype)(al)), \
437 "g" ((USItype)(bl)))
438#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
439 __asm__ ("subl %5,%1\n" \
440 "sbbl %3,%0" \
441 : "=r" ((USItype)(sh)), \
442 "=&r" ((USItype)(sl)) \
443 : "0" ((USItype)(ah)), \
444 "g" ((USItype)(bh)), \
445 "1" ((USItype)(al)), \
446 "g" ((USItype)(bl)))
447#define umul_ppmm(w1, w0, u, v) \
448 __asm__ ("mull %3" \
449 : "=a" ((USItype)(w0)), \
450 "=d" ((USItype)(w1)) \
451 : "%0" ((USItype)(u)), \
452 "rm" ((USItype)(v)))
453#define udiv_qrnnd(q, r, n1, n0, d) \
454 __asm__ ("divl %4" \
455 : "=a" ((USItype)(q)), \
456 "=d" ((USItype)(r)) \
457 : "0" ((USItype)(n0)), \
458 "1" ((USItype)(n1)), \
459 "rm" ((USItype)(d)))
460#define count_leading_zeros(count, x) \
461do { \
462 USItype __cbtmp; \
463 __asm__ ("bsrl %1,%0" \
464 : "=r" (__cbtmp) : "rm" ((USItype)(x))); \
465 (count) = __cbtmp ^ 31; \
466} while (0)
467#define count_trailing_zeros(count, x) \
468 __asm__ ("bsfl %1,%0" : "=r" (count) : "rm" ((USItype)(x)))
469#ifndef UMUL_TIME
470#define UMUL_TIME 40
471#endif
472#ifndef UDIV_TIME
473#define UDIV_TIME 40
474#endif
475#endif /* 80x86 */
476
477/***************************************
478 ************** I860 *****************
479 ***************************************/
480#if defined(__i860__) && W_TYPE_SIZE == 32
481#define rshift_rhlc(r, h, l, c) \
482 __asm__ ("shr %3,r0,r0\n" \
483 "shrd %1,%2,%0" \
484 "=r" (r) : "r" (h), "r" (l), "rn" (c))
485#endif /* i860 */
486
487/***************************************
488 ************** I960 *****************
489 ***************************************/
490#if defined(__i960__) && W_TYPE_SIZE == 32
491#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
492 __asm__ ("cmpo 1,0\n" \
493 "addc %5,%4,%1\n" \
494 "addc %3,%2,%0" \
495 : "=r" ((USItype)(sh)), \
496 "=&r" ((USItype)(sl)) \
497 : "%dI" ((USItype)(ah)), \
498 "dI" ((USItype)(bh)), \
499 "%dI" ((USItype)(al)), \
500 "dI" ((USItype)(bl)))
501#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
502 __asm__ ("cmpo 0,0\n" \
503 "subc %5,%4,%1\n" \
504 "subc %3,%2,%0" \
505 : "=r" ((USItype)(sh)), \
506 "=&r" ((USItype)(sl)) \
507 : "dI" ((USItype)(ah)), \
508 "dI" ((USItype)(bh)), \
509 "dI" ((USItype)(al)), \
510 "dI" ((USItype)(bl)))
511#define umul_ppmm(w1, w0, u, v) \
512 ({union {UDItype __ll; \
513 struct {USItype __l, __h; } __i; \
514 } __xx; \
515 __asm__ ("emul %2,%1,%0" \
516 : "=d" (__xx.__ll) \
517 : "%dI" ((USItype)(u)), \
518 "dI" ((USItype)(v))); \
519 (w1) = __xx.__i.__h; (w0) = __xx.__i.__l; })
520#define __umulsidi3(u, v) \
521 ({UDItype __w; \
522 __asm__ ("emul %2,%1,%0" \
523 : "=d" (__w) \
524 : "%dI" ((USItype)(u)), \
525 "dI" ((USItype)(v))); \
526 __w; })
527#define udiv_qrnnd(q, r, nh, nl, d) \
528do { \
529 union {UDItype __ll; \
530 struct {USItype __l, __h; } __i; \
531 } __nn; \
532 __nn.__i.__h = (nh); __nn.__i.__l = (nl); \
533 __asm__ ("ediv %d,%n,%0" \
534 : "=d" (__rq.__ll) \
535 : "dI" (__nn.__ll), \
536 "dI" ((USItype)(d))); \
537 (r) = __rq.__i.__l; (q) = __rq.__i.__h; \
538} while (0)
539#define count_leading_zeros(count, x) \
540do { \
541 USItype __cbtmp; \
542 __asm__ ("scanbit %1,%0" \
543 : "=r" (__cbtmp) \
544 : "r" ((USItype)(x))); \
545 (count) = __cbtmp ^ 31; \
546} while (0)
547#define COUNT_LEADING_ZEROS_0 (-32) /* sic */
548#if defined(__i960mx) /* what is the proper symbol to test??? */
549#define rshift_rhlc(r, h, l, c) \
550do { \
551 union {UDItype __ll; \
552 struct {USItype __l, __h; } __i; \
553 } __nn; \
554 __nn.__i.__h = (h); __nn.__i.__l = (l); \
555 __asm__ ("shre %2,%1,%0" \
556 : "=d" (r) : "dI" (__nn.__ll), "dI" (c)); \
557}
558#endif /* i960mx */
559#endif /* i960 */
560
561/***************************************
562 ************** 68000 ****************
563 ***************************************/
564#if (defined(__mc68000__) || defined(__mc68020__) || defined(__NeXT__) || defined(mc68020)) && W_TYPE_SIZE == 32
565#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
566 __asm__ ("add%.l %5,%1\n" \
567 "addx%.l %3,%0" \
568 : "=d" ((USItype)(sh)), \
569 "=&d" ((USItype)(sl)) \
570 : "%0" ((USItype)(ah)), \
571 "d" ((USItype)(bh)), \
572 "%1" ((USItype)(al)), \
573 "g" ((USItype)(bl)))
574#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
575 __asm__ ("sub%.l %5,%1\n" \
576 "subx%.l %3,%0" \
577 : "=d" ((USItype)(sh)), \
578 "=&d" ((USItype)(sl)) \
579 : "0" ((USItype)(ah)), \
580 "d" ((USItype)(bh)), \
581 "1" ((USItype)(al)), \
582 "g" ((USItype)(bl)))
583#if (defined(__mc68020__) || defined(__NeXT__) || defined(mc68020))
584#define umul_ppmm(w1, w0, u, v) \
585 __asm__ ("mulu%.l %3,%1:%0" \
586 : "=d" ((USItype)(w0)), \
587 "=d" ((USItype)(w1)) \
588 : "%0" ((USItype)(u)), \
589 "dmi" ((USItype)(v)))
590#define UMUL_TIME 45
591#define udiv_qrnnd(q, r, n1, n0, d) \
592 __asm__ ("divu%.l %4,%1:%0" \
593 : "=d" ((USItype)(q)), \
594 "=d" ((USItype)(r)) \
595 : "0" ((USItype)(n0)), \
596 "1" ((USItype)(n1)), \
597 "dmi" ((USItype)(d)))
598#define UDIV_TIME 90
599#define sdiv_qrnnd(q, r, n1, n0, d) \
600 __asm__ ("divs%.l %4,%1:%0" \
601 : "=d" ((USItype)(q)), \
602 "=d" ((USItype)(r)) \
603 : "0" ((USItype)(n0)), \
604 "1" ((USItype)(n1)), \
605 "dmi" ((USItype)(d)))
606#define count_leading_zeros(count, x) \
607 __asm__ ("bfffo %1{%b2:%b2},%0" \
608 : "=d" ((USItype)(count)) \
609 : "od" ((USItype)(x)), "n" (0))
610#define COUNT_LEADING_ZEROS_0 32
611#else /* not mc68020 */
612#define umul_ppmm(xh, xl, a, b) \
613do { USItype __umul_tmp1, __umul_tmp2; \
614 __asm__ ("| Inlined umul_ppmm\n" \
615 "move%.l %5,%3\n" \
616 "move%.l %2,%0\n" \
617 "move%.w %3,%1\n" \
618 "swap %3\n" \
619 "swap %0\n" \
620 "mulu %2,%1\n" \
621 "mulu %3,%0\n" \
622 "mulu %2,%3\n" \
623 "swap %2\n" \
624 "mulu %5,%2\n" \
625 "add%.l %3,%2\n" \
626 "jcc 1f\n" \
627 "add%.l %#0x10000,%0\n" \
628 "1: move%.l %2,%3\n" \
629 "clr%.w %2\n" \
630 "swap %2\n" \
631 "swap %3\n" \
632 "clr%.w %3\n" \
633 "add%.l %3,%1\n" \
634 "addx%.l %2,%0\n" \
635 "| End inlined umul_ppmm" \
636 : "=&d" ((USItype)(xh)), "=&d" ((USItype)(xl)), \
637 "=d" (__umul_tmp1), "=&d" (__umul_tmp2) \
638 : "%2" ((USItype)(a)), "d" ((USItype)(b))); \
639} while (0)
640#define UMUL_TIME 100
641#define UDIV_TIME 400
642#endif /* not mc68020 */
643#endif /* mc68000 */
644
645/***************************************
646 ************** 88000 ****************
647 ***************************************/
648#if defined(__m88000__) && W_TYPE_SIZE == 32
649#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
650 __asm__ ("addu.co %1,%r4,%r5\n" \
651 "addu.ci %0,%r2,%r3" \
652 : "=r" ((USItype)(sh)), \
653 "=&r" ((USItype)(sl)) \
654 : "%rJ" ((USItype)(ah)), \
655 "rJ" ((USItype)(bh)), \
656 "%rJ" ((USItype)(al)), \
657 "rJ" ((USItype)(bl)))
658#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
659 __asm__ ("subu.co %1,%r4,%r5\n" \
660 "subu.ci %0,%r2,%r3" \
661 : "=r" ((USItype)(sh)), \
662 "=&r" ((USItype)(sl)) \
663 : "rJ" ((USItype)(ah)), \
664 "rJ" ((USItype)(bh)), \
665 "rJ" ((USItype)(al)), \
666 "rJ" ((USItype)(bl)))
667#define count_leading_zeros(count, x) \
668do { \
669 USItype __cbtmp; \
670 __asm__ ("ff1 %0,%1" \
671 : "=r" (__cbtmp) \
672 : "r" ((USItype)(x))); \
673 (count) = __cbtmp ^ 31; \
674} while (0)
675#define COUNT_LEADING_ZEROS_0 63 /* sic */
676#if defined(__m88110__)
677#define umul_ppmm(wh, wl, u, v) \
678do { \
679 union {UDItype __ll; \
680 struct {USItype __h, __l; } __i; \
681 } __x; \
682 __asm__ ("mulu.d %0,%1,%2" : "=r" (__x.__ll) : "r" (u), "r" (v)); \
683 (wh) = __x.__i.__h; \
684 (wl) = __x.__i.__l; \
685} while (0)
686#define udiv_qrnnd(q, r, n1, n0, d) \
687 ({union {UDItype __ll; \
688 struct {USItype __h, __l; } __i; \
689 } __x, __q; \
690 __x.__i.__h = (n1); __x.__i.__l = (n0); \
691 __asm__ ("divu.d %0,%1,%2" \
692 : "=r" (__q.__ll) : "r" (__x.__ll), "r" (d)); \
693 (r) = (n0) - __q.__l * (d); (q) = __q.__l; })
694#define UMUL_TIME 5
695#define UDIV_TIME 25
696#else
697#define UMUL_TIME 17
698#define UDIV_TIME 150
699#endif /* __m88110__ */
700#endif /* __m88000__ */
701
702/***************************************
703 ************** MIPS *****************
704 ***************************************/
705#if defined(__mips__) && W_TYPE_SIZE == 32
706#if __GNUC__ > 2 || __GNUC_MINOR__ >= 7
707#define umul_ppmm(w1, w0, u, v) \
708 __asm__ ("multu %2,%3" \
709 : "=l" ((USItype)(w0)), \
710 "=h" ((USItype)(w1)) \
711 : "d" ((USItype)(u)), \
712 "d" ((USItype)(v)))
713#else
714#define umul_ppmm(w1, w0, u, v) \
715 __asm__ ("multu %2,%3\n" \
716 "mflo %0\n" \
717 "mfhi %1" \
718 : "=d" ((USItype)(w0)), \
719 "=d" ((USItype)(w1)) \
720 : "d" ((USItype)(u)), \
721 "d" ((USItype)(v)))
722#endif
723#define UMUL_TIME 10
724#define UDIV_TIME 100
725#endif /* __mips__ */
726
727/***************************************
728 ************** MIPS/64 **************
729 ***************************************/
730#if (defined(__mips) && __mips >= 3) && W_TYPE_SIZE == 64
731#if __GNUC__ > 2 || __GNUC_MINOR__ >= 7
732#define umul_ppmm(w1, w0, u, v) \
733 __asm__ ("dmultu %2,%3" \
734 : "=l" ((UDItype)(w0)), \
735 "=h" ((UDItype)(w1)) \
736 : "d" ((UDItype)(u)), \
737 "d" ((UDItype)(v)))
738#else
739#define umul_ppmm(w1, w0, u, v) \
740 __asm__ ("dmultu %2,%3\n" \
741 "mflo %0\n" \
742 "mfhi %1" \
743 : "=d" ((UDItype)(w0)), \
744 "=d" ((UDItype)(w1)) \
745 : "d" ((UDItype)(u)), \
746 "d" ((UDItype)(v)))
747#endif
748#define UMUL_TIME 20
749#define UDIV_TIME 140
750#endif /* __mips__ */
751
752/***************************************
753 ************** 32000 ****************
754 ***************************************/
755#if defined(__ns32000__) && W_TYPE_SIZE == 32
756#define umul_ppmm(w1, w0, u, v) \
757 ({union {UDItype __ll; \
758 struct {USItype __l, __h; } __i; \
759 } __xx; \
760 __asm__ ("meid %2,%0" \
761 : "=g" (__xx.__ll) \
762 : "%0" ((USItype)(u)), \
763 "g" ((USItype)(v))); \
764 (w1) = __xx.__i.__h; (w0) = __xx.__i.__l; })
765#define __umulsidi3(u, v) \
766 ({UDItype __w; \
767 __asm__ ("meid %2,%0" \
768 : "=g" (__w) \
769 : "%0" ((USItype)(u)), \
770 "g" ((USItype)(v))); \
771 __w; })
772#define udiv_qrnnd(q, r, n1, n0, d) \
773 ({union {UDItype __ll; \
774 struct {USItype __l, __h; } __i; \
775 } __xx; \
776 __xx.__i.__h = (n1); __xx.__i.__l = (n0); \
777 __asm__ ("deid %2,%0" \
778 : "=g" (__xx.__ll) \
779 : "0" (__xx.__ll), \
780 "g" ((USItype)(d))); \
781 (r) = __xx.__i.__l; (q) = __xx.__i.__h; })
782#define count_trailing_zeros(count, x) \
783do { \
784 __asm__("ffsd %2,%0" \
785 : "=r"((USItype) (count)) \
786 : "0"((USItype) 0), "r"((USItype) (x))); \
787 } while (0)
788#endif /* __ns32000__ */
789
790/***************************************
791 ************** PPC ******************
792 ***************************************/
793#if (defined(_ARCH_PPC) || defined(_IBMR2)) && W_TYPE_SIZE == 32
794#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
795do { \
796 if (__builtin_constant_p(bh) && (bh) == 0) \
797 __asm__ ("{a%I4|add%I4c} %1,%3,%4\n\t{aze|addze} %0,%2" \
798 : "=r" ((USItype)(sh)), \
799 "=&r" ((USItype)(sl)) \
800 : "%r" ((USItype)(ah)), \
801 "%r" ((USItype)(al)), \
802 "rI" ((USItype)(bl))); \
803 else if (__builtin_constant_p(bh) && (bh) == ~(USItype) 0) \
804 __asm__ ("{a%I4|add%I4c} %1,%3,%4\n\t{ame|addme} %0,%2" \
805 : "=r" ((USItype)(sh)), \
806 "=&r" ((USItype)(sl)) \
807 : "%r" ((USItype)(ah)), \
808 "%r" ((USItype)(al)), \
809 "rI" ((USItype)(bl))); \
810 else \
811 __asm__ ("{a%I5|add%I5c} %1,%4,%5\n\t{ae|adde} %0,%2,%3" \
812 : "=r" ((USItype)(sh)), \
813 "=&r" ((USItype)(sl)) \
814 : "%r" ((USItype)(ah)), \
815 "r" ((USItype)(bh)), \
816 "%r" ((USItype)(al)), \
817 "rI" ((USItype)(bl))); \
818} while (0)
819#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
820do { \
821 if (__builtin_constant_p(ah) && (ah) == 0) \
822 __asm__ ("{sf%I3|subf%I3c} %1,%4,%3\n\t{sfze|subfze} %0,%2" \
823 : "=r" ((USItype)(sh)), \
824 "=&r" ((USItype)(sl)) \
825 : "r" ((USItype)(bh)), \
826 "rI" ((USItype)(al)), \
827 "r" ((USItype)(bl))); \
828 else if (__builtin_constant_p(ah) && (ah) == ~(USItype) 0) \
829 __asm__ ("{sf%I3|subf%I3c} %1,%4,%3\n\t{sfme|subfme} %0,%2" \
830 : "=r" ((USItype)(sh)), \
831 "=&r" ((USItype)(sl)) \
832 : "r" ((USItype)(bh)), \
833 "rI" ((USItype)(al)), \
834 "r" ((USItype)(bl))); \
835 else if (__builtin_constant_p(bh) && (bh) == 0) \
836 __asm__ ("{sf%I3|subf%I3c} %1,%4,%3\n\t{ame|addme} %0,%2" \
837 : "=r" ((USItype)(sh)), \
838 "=&r" ((USItype)(sl)) \
839 : "r" ((USItype)(ah)), \
840 "rI" ((USItype)(al)), \
841 "r" ((USItype)(bl))); \
842 else if (__builtin_constant_p(bh) && (bh) == ~(USItype) 0) \
843 __asm__ ("{sf%I3|subf%I3c} %1,%4,%3\n\t{aze|addze} %0,%2" \
844 : "=r" ((USItype)(sh)), \
845 "=&r" ((USItype)(sl)) \
846 : "r" ((USItype)(ah)), \
847 "rI" ((USItype)(al)), \
848 "r" ((USItype)(bl))); \
849 else \
850 __asm__ ("{sf%I4|subf%I4c} %1,%5,%4\n\t{sfe|subfe} %0,%3,%2" \
851 : "=r" ((USItype)(sh)), \
852 "=&r" ((USItype)(sl)) \
853 : "r" ((USItype)(ah)), \
854 "r" ((USItype)(bh)), \
855 "rI" ((USItype)(al)), \
856 "r" ((USItype)(bl))); \
857} while (0)
858#define count_leading_zeros(count, x) \
859 __asm__ ("{cntlz|cntlzw} %0,%1" \
860 : "=r" ((USItype)(count)) \
861 : "r" ((USItype)(x)))
862#define COUNT_LEADING_ZEROS_0 32
863#if defined(_ARCH_PPC)
864#define umul_ppmm(ph, pl, m0, m1) \
865do { \
866 USItype __m0 = (m0), __m1 = (m1); \
867 __asm__ ("mulhwu %0,%1,%2" \
868 : "=r" ((USItype) ph) \
869 : "%r" (__m0), \
870 "r" (__m1)); \
871 (pl) = __m0 * __m1; \
872} while (0)
873#define UMUL_TIME 15
874#define smul_ppmm(ph, pl, m0, m1) \
875do { \
876 SItype __m0 = (m0), __m1 = (m1); \
877 __asm__ ("mulhw %0,%1,%2" \
878 : "=r" ((SItype) ph) \
879 : "%r" (__m0), \
880 "r" (__m1)); \
881 (pl) = __m0 * __m1; \
882} while (0)
883#define SMUL_TIME 14
884#define UDIV_TIME 120
885#else
886#define umul_ppmm(xh, xl, m0, m1) \
887do { \
888 USItype __m0 = (m0), __m1 = (m1); \
889 __asm__ ("mul %0,%2,%3" \
890 : "=r" ((USItype)(xh)), \
891 "=q" ((USItype)(xl)) \
892 : "r" (__m0), \
893 "r" (__m1)); \
894 (xh) += ((((SItype) __m0 >> 31) & __m1) \
895 + (((SItype) __m1 >> 31) & __m0)); \
896} while (0)
897#define UMUL_TIME 8
898#define smul_ppmm(xh, xl, m0, m1) \
899 __asm__ ("mul %0,%2,%3" \
900 : "=r" ((SItype)(xh)), \
901 "=q" ((SItype)(xl)) \
902 : "r" (m0), \
903 "r" (m1))
904#define SMUL_TIME 4
905#define sdiv_qrnnd(q, r, nh, nl, d) \
906 __asm__ ("div %0,%2,%4" \
907 : "=r" ((SItype)(q)), "=q" ((SItype)(r)) \
908 : "r" ((SItype)(nh)), "1" ((SItype)(nl)), "r" ((SItype)(d)))
909#define UDIV_TIME 100
910#endif
911#endif /* Power architecture variants. */
912
913/***************************************
914 ************** PYR ******************
915 ***************************************/
916#if defined(__pyr__) && W_TYPE_SIZE == 32
917#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
918 __asm__ ("addw %5,%1\n" \
919 "addwc %3,%0" \
920 : "=r" ((USItype)(sh)), \
921 "=&r" ((USItype)(sl)) \
922 : "%0" ((USItype)(ah)), \
923 "g" ((USItype)(bh)), \
924 "%1" ((USItype)(al)), \
925 "g" ((USItype)(bl)))
926#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
927 __asm__ ("subw %5,%1\n" \
928 "subwb %3,%0" \
929 : "=r" ((USItype)(sh)), \
930 "=&r" ((USItype)(sl)) \
931 : "0" ((USItype)(ah)), \
932 "g" ((USItype)(bh)), \
933 "1" ((USItype)(al)), \
934 "g" ((USItype)(bl)))
935 /* This insn works on Pyramids with AP, XP, or MI CPUs, but not with SP. */
936#define umul_ppmm(w1, w0, u, v) \
937 ({union {UDItype __ll; \
938 struct {USItype __h, __l; } __i; \
939 } __xx; \
940 __asm__ ("movw %1,%R0\n" \
941 "uemul %2,%0" \
942 : "=&r" (__xx.__ll) \
943 : "g" ((USItype) (u)), \
944 "g" ((USItype)(v))); \
945 (w1) = __xx.__i.__h; (w0) = __xx.__i.__l; })
946#endif /* __pyr__ */
947
948/***************************************
949 ************** RT/ROMP **************
950 ***************************************/
951#if defined(__ibm032__) /* RT/ROMP */ && W_TYPE_SIZE == 32
952#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
953 __asm__ ("a %1,%5\n" \
954 "ae %0,%3" \
955 : "=r" ((USItype)(sh)), \
956 "=&r" ((USItype)(sl)) \
957 : "%0" ((USItype)(ah)), \
958 "r" ((USItype)(bh)), \
959 "%1" ((USItype)(al)), \
960 "r" ((USItype)(bl)))
961#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
962 __asm__ ("s %1,%5\n" \
963 "se %0,%3" \
964 : "=r" ((USItype)(sh)), \
965 "=&r" ((USItype)(sl)) \
966 : "0" ((USItype)(ah)), \
967 "r" ((USItype)(bh)), \
968 "1" ((USItype)(al)), \
969 "r" ((USItype)(bl)))
970#define umul_ppmm(ph, pl, m0, m1) \
971do { \
972 USItype __m0 = (m0), __m1 = (m1); \
973 __asm__ ( \
974 "s r2,r2\n" \
975 "mts r10,%2\n" \
976 "m r2,%3\n" \
977 "m r2,%3\n" \
978 "m r2,%3\n" \
979 "m r2,%3\n" \
980 "m r2,%3\n" \
981 "m r2,%3\n" \
982 "m r2,%3\n" \
983 "m r2,%3\n" \
984 "m r2,%3\n" \
985 "m r2,%3\n" \
986 "m r2,%3\n" \
987 "m r2,%3\n" \
988 "m r2,%3\n" \
989 "m r2,%3\n" \
990 "m r2,%3\n" \
991 "m r2,%3\n" \
992 "cas %0,r2,r0\n" \
993 "mfs r10,%1" \
994 : "=r" ((USItype)(ph)), \
995 "=r" ((USItype)(pl)) \
996 : "%r" (__m0), \
997 "r" (__m1) \
998 : "r2"); \
999 (ph) += ((((SItype) __m0 >> 31) & __m1) \
1000 + (((SItype) __m1 >> 31) & __m0)); \
1001} while (0)
1002#define UMUL_TIME 20
1003#define UDIV_TIME 200
1004#define count_leading_zeros(count, x) \
1005do { \
1006 if ((x) >= 0x10000) \
1007 __asm__ ("clz %0,%1" \
1008 : "=r" ((USItype)(count)) \
1009 : "r" ((USItype)(x) >> 16)); \
1010 else { \
1011 __asm__ ("clz %0,%1" \
1012 : "=r" ((USItype)(count)) \
1013 : "r" ((USItype)(x))); \
1014 (count) += 16; \
1015 } \
1016} while (0)
1017#endif /* RT/ROMP */
1018
1019/***************************************
1020 ************** SH2 ******************
1021 ***************************************/
1022#if (defined(__sh2__) || defined(__sh3__) || defined(__SH4__)) \
1023 && W_TYPE_SIZE == 32
1024#define umul_ppmm(w1, w0, u, v) \
1025 __asm__ ( \
1026 "dmulu.l %2,%3\n" \
1027 "sts macl,%1\n" \
1028 "sts mach,%0" \
1029 : "=r" ((USItype)(w1)), \
1030 "=r" ((USItype)(w0)) \
1031 : "r" ((USItype)(u)), \
1032 "r" ((USItype)(v)) \
1033 : "macl", "mach")
1034#define UMUL_TIME 5
1035#endif
1036
1037/***************************************
1038 ************** SPARC ****************
1039 ***************************************/
1040#if defined(__sparc__) && W_TYPE_SIZE == 32
1041#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
1042 __asm__ ("addcc %r4,%5,%1\n" \
1043 "addx %r2,%3,%0" \
1044 : "=r" ((USItype)(sh)), \
1045 "=&r" ((USItype)(sl)) \
1046 : "%rJ" ((USItype)(ah)), \
1047 "rI" ((USItype)(bh)), \
1048 "%rJ" ((USItype)(al)), \
1049 "rI" ((USItype)(bl)) \
1050 __CLOBBER_CC)
1051#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
1052 __asm__ ("subcc %r4,%5,%1\n" \
1053 "subx %r2,%3,%0" \
1054 : "=r" ((USItype)(sh)), \
1055 "=&r" ((USItype)(sl)) \
1056 : "rJ" ((USItype)(ah)), \
1057 "rI" ((USItype)(bh)), \
1058 "rJ" ((USItype)(al)), \
1059 "rI" ((USItype)(bl)) \
1060 __CLOBBER_CC)
1061#if defined(__sparc_v8__)
1062/* Don't match immediate range because, 1) it is not often useful,
1063 2) the 'I' flag thinks of the range as a 13 bit signed interval,
1064 while we want to match a 13 bit interval, sign extended to 32 bits,
1065 but INTERPRETED AS UNSIGNED. */
1066#define umul_ppmm(w1, w0, u, v) \
1067 __asm__ ("umul %2,%3,%1;rd %%y,%0" \
1068 : "=r" ((USItype)(w1)), \
1069 "=r" ((USItype)(w0)) \
1070 : "r" ((USItype)(u)), \
1071 "r" ((USItype)(v)))
1072#define UMUL_TIME 5
1073#ifndef SUPERSPARC /* SuperSPARC's udiv only handles 53 bit dividends */
1074#define udiv_qrnnd(q, r, n1, n0, d) \
1075do { \
1076 USItype __q; \
1077 __asm__ ("mov %1,%%y;nop;nop;nop;udiv %2,%3,%0" \
1078 : "=r" ((USItype)(__q)) \
1079 : "r" ((USItype)(n1)), \
1080 "r" ((USItype)(n0)), \
1081 "r" ((USItype)(d))); \
1082 (r) = (n0) - __q * (d); \
1083 (q) = __q; \
1084} while (0)
1085#define UDIV_TIME 25
1086#endif /* SUPERSPARC */
1087#else /* ! __sparc_v8__ */
1088#if defined(__sparclite__)
1089/* This has hardware multiply but not divide. It also has two additional
1090 instructions scan (ffs from high bit) and divscc. */
1091#define umul_ppmm(w1, w0, u, v) \
1092 __asm__ ("umul %2,%3,%1;rd %%y,%0" \
1093 : "=r" ((USItype)(w1)), \
1094 "=r" ((USItype)(w0)) \
1095 : "r" ((USItype)(u)), \
1096 "r" ((USItype)(v)))
1097#define UMUL_TIME 5
1098#define udiv_qrnnd(q, r, n1, n0, d) \
1099 __asm__ ("! Inlined udiv_qrnnd\n" \
1100 "wr %%g0,%2,%%y ! Not a delayed write for sparclite\n" \
1101 "tst %%g0\n" \
1102 "divscc %3,%4,%%g1\n" \
1103 "divscc %%g1,%4,%%g1\n" \
1104 "divscc %%g1,%4,%%g1\n" \
1105 "divscc %%g1,%4,%%g1\n" \
1106 "divscc %%g1,%4,%%g1\n" \
1107 "divscc %%g1,%4,%%g1\n" \
1108 "divscc %%g1,%4,%%g1\n" \
1109 "divscc %%g1,%4,%%g1\n" \
1110 "divscc %%g1,%4,%%g1\n" \
1111 "divscc %%g1,%4,%%g1\n" \
1112 "divscc %%g1,%4,%%g1\n" \
1113 "divscc %%g1,%4,%%g1\n" \
1114 "divscc %%g1,%4,%%g1\n" \
1115 "divscc %%g1,%4,%%g1\n" \
1116 "divscc %%g1,%4,%%g1\n" \
1117 "divscc %%g1,%4,%%g1\n" \
1118 "divscc %%g1,%4,%%g1\n" \
1119 "divscc %%g1,%4,%%g1\n" \
1120 "divscc %%g1,%4,%%g1\n" \
1121 "divscc %%g1,%4,%%g1\n" \
1122 "divscc %%g1,%4,%%g1\n" \
1123 "divscc %%g1,%4,%%g1\n" \
1124 "divscc %%g1,%4,%%g1\n" \
1125 "divscc %%g1,%4,%%g1\n" \
1126 "divscc %%g1,%4,%%g1\n" \
1127 "divscc %%g1,%4,%%g1\n" \
1128 "divscc %%g1,%4,%%g1\n" \
1129 "divscc %%g1,%4,%%g1\n" \
1130 "divscc %%g1,%4,%%g1\n" \
1131 "divscc %%g1,%4,%%g1\n" \
1132 "divscc %%g1,%4,%%g1\n" \
1133 "divscc %%g1,%4,%0\n" \
1134 "rd %%y,%1\n" \
1135 "bl,a 1f\n" \
1136 "add %1,%4,%1\n" \
1137 "1: ! End of inline udiv_qrnnd" \
1138 : "=r" ((USItype)(q)), \
1139 "=r" ((USItype)(r)) \
1140 : "r" ((USItype)(n1)), \
1141 "r" ((USItype)(n0)), \
1142 "rI" ((USItype)(d)) \
1143 : "%g1" __AND_CLOBBER_CC)
1144#define UDIV_TIME 37
1145#define count_leading_zeros(count, x) \
1146 __asm__ ("scan %1,0,%0" \
1147 : "=r" ((USItype)(x)) \
1148 : "r" ((USItype)(count)))
1149/* Early sparclites return 63 for an argument of 0, but they warn that future
1150 implementations might change this. Therefore, leave COUNT_LEADING_ZEROS_0
1151 undefined. */
1152#endif /* __sparclite__ */
1153#endif /* __sparc_v8__ */
1154 /* Default to sparc v7 versions of umul_ppmm and udiv_qrnnd. */
1155#ifndef umul_ppmm
1156#define umul_ppmm(w1, w0, u, v) \
1157 __asm__ ("! Inlined umul_ppmm\n" \
1158 "wr %%g0,%2,%%y ! SPARC has 0-3 delay insn after a wr\n" \
1159 "sra %3,31,%%g2 ! Don't move this insn\n" \
1160 "and %2,%%g2,%%g2 ! Don't move this insn\n" \
1161 "andcc %%g0,0,%%g1 ! Don't move this insn\n" \
1162 "mulscc %%g1,%3,%%g1\n" \
1163 "mulscc %%g1,%3,%%g1\n" \
1164 "mulscc %%g1,%3,%%g1\n" \
1165 "mulscc %%g1,%3,%%g1\n" \
1166 "mulscc %%g1,%3,%%g1\n" \
1167 "mulscc %%g1,%3,%%g1\n" \
1168 "mulscc %%g1,%3,%%g1\n" \
1169 "mulscc %%g1,%3,%%g1\n" \
1170 "mulscc %%g1,%3,%%g1\n" \
1171 "mulscc %%g1,%3,%%g1\n" \
1172 "mulscc %%g1,%3,%%g1\n" \
1173 "mulscc %%g1,%3,%%g1\n" \
1174 "mulscc %%g1,%3,%%g1\n" \
1175 "mulscc %%g1,%3,%%g1\n" \
1176 "mulscc %%g1,%3,%%g1\n" \
1177 "mulscc %%g1,%3,%%g1\n" \
1178 "mulscc %%g1,%3,%%g1\n" \
1179 "mulscc %%g1,%3,%%g1\n" \
1180 "mulscc %%g1,%3,%%g1\n" \
1181 "mulscc %%g1,%3,%%g1\n" \
1182 "mulscc %%g1,%3,%%g1\n" \
1183 "mulscc %%g1,%3,%%g1\n" \
1184 "mulscc %%g1,%3,%%g1\n" \
1185 "mulscc %%g1,%3,%%g1\n" \
1186 "mulscc %%g1,%3,%%g1\n" \
1187 "mulscc %%g1,%3,%%g1\n" \
1188 "mulscc %%g1,%3,%%g1\n" \
1189 "mulscc %%g1,%3,%%g1\n" \
1190 "mulscc %%g1,%3,%%g1\n" \
1191 "mulscc %%g1,%3,%%g1\n" \
1192 "mulscc %%g1,%3,%%g1\n" \
1193 "mulscc %%g1,%3,%%g1\n" \
1194 "mulscc %%g1,0,%%g1\n" \
1195 "add %%g1,%%g2,%0\n" \
1196 "rd %%y,%1" \
1197 : "=r" ((USItype)(w1)), \
1198 "=r" ((USItype)(w0)) \
1199 : "%rI" ((USItype)(u)), \
1200 "r" ((USItype)(v)) \
1201 : "%g1", "%g2" __AND_CLOBBER_CC)
1202#define UMUL_TIME 39 /* 39 instructions */
1203#endif
1204#ifndef udiv_qrnnd
1205#ifndef LONGLONG_STANDALONE
1206#define udiv_qrnnd(q, r, n1, n0, d) \
1207do { USItype __r; \
1208 (q) = __udiv_qrnnd(&__r, (n1), (n0), (d)); \
1209 (r) = __r; \
1210} while (0)
1211 extern USItype __udiv_qrnnd();
1212#define UDIV_TIME 140
1213#endif /* LONGLONG_STANDALONE */
1214#endif /* udiv_qrnnd */
1215#endif /* __sparc__ */
1216
1217/***************************************
1218 ************** VAX ******************
1219 ***************************************/
1220#if defined(__vax__) && W_TYPE_SIZE == 32
1221#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
1222 __asm__ ("addl2 %5,%1\n" \
1223 "adwc %3,%0" \
1224 : "=g" ((USItype)(sh)), \
1225 "=&g" ((USItype)(sl)) \
1226 : "%0" ((USItype)(ah)), \
1227 "g" ((USItype)(bh)), \
1228 "%1" ((USItype)(al)), \
1229 "g" ((USItype)(bl)))
1230#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
1231 __asm__ ("subl2 %5,%1\n" \
1232 "sbwc %3,%0" \
1233 : "=g" ((USItype)(sh)), \
1234 "=&g" ((USItype)(sl)) \
1235 : "0" ((USItype)(ah)), \
1236 "g" ((USItype)(bh)), \
1237 "1" ((USItype)(al)), \
1238 "g" ((USItype)(bl)))
1239#define umul_ppmm(xh, xl, m0, m1) \
1240do { \
1241 union {UDItype __ll; \
1242 struct {USItype __l, __h; } __i; \
1243 } __xx; \
1244 USItype __m0 = (m0), __m1 = (m1); \
1245 __asm__ ("emul %1,%2,$0,%0" \
1246 : "=g" (__xx.__ll) \
1247 : "g" (__m0), \
1248 "g" (__m1)); \
1249 (xh) = __xx.__i.__h; (xl) = __xx.__i.__l; \
1250 (xh) += ((((SItype) __m0 >> 31) & __m1) \
1251 + (((SItype) __m1 >> 31) & __m0)); \
1252} while (0)
1253#define sdiv_qrnnd(q, r, n1, n0, d) \
1254do { \
1255 union {DItype __ll; \
1256 struct {SItype __l, __h; } __i; \
1257 } __xx; \
1258 __xx.__i.__h = n1; __xx.__i.__l = n0; \
1259 __asm__ ("ediv %3,%2,%0,%1" \
1260 : "=g" (q), "=g" (r) \
1261 : "g" (__xx.__ll), "g" (d)); \
1262} while (0)
1263#endif /* __vax__ */
1264
1265/***************************************
1266 ************** Z8000 ****************
1267 ***************************************/
1268#if defined(__z8000__) && W_TYPE_SIZE == 16
1269#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
1270 __asm__ ("add %H1,%H5\n\tadc %H0,%H3" \
1271 : "=r" ((unsigned int)(sh)), \
1272 "=&r" ((unsigned int)(sl)) \
1273 : "%0" ((unsigned int)(ah)), \
1274 "r" ((unsigned int)(bh)), \
1275 "%1" ((unsigned int)(al)), \
1276 "rQR" ((unsigned int)(bl)))
1277#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
1278 __asm__ ("sub %H1,%H5\n\tsbc %H0,%H3" \
1279 : "=r" ((unsigned int)(sh)), \
1280 "=&r" ((unsigned int)(sl)) \
1281 : "0" ((unsigned int)(ah)), \
1282 "r" ((unsigned int)(bh)), \
1283 "1" ((unsigned int)(al)), \
1284 "rQR" ((unsigned int)(bl)))
1285#define umul_ppmm(xh, xl, m0, m1) \
1286do { \
1287 union {long int __ll; \
1288 struct {unsigned int __h, __l; } __i; \
1289 } __xx; \
1290 unsigned int __m0 = (m0), __m1 = (m1); \
1291 __asm__ ("mult %S0,%H3" \
1292 : "=r" (__xx.__i.__h), \
1293 "=r" (__xx.__i.__l) \
1294 : "%1" (__m0), \
1295 "rQR" (__m1)); \
1296 (xh) = __xx.__i.__h; (xl) = __xx.__i.__l; \
1297 (xh) += ((((signed int) __m0 >> 15) & __m1) \
1298 + (((signed int) __m1 >> 15) & __m0)); \
1299} while (0)
1300#endif /* __z8000__ */
1301
1302#endif /* __GNUC__ */
1303
1304/***************************************
1305 *********** Generic Versions ********
1306 ***************************************/
1307#if !defined(umul_ppmm) && defined(__umulsidi3)
1308#define umul_ppmm(ph, pl, m0, m1) \
1309{ \
1310 UDWtype __ll = __umulsidi3(m0, m1); \
1311 ph = (UWtype) (__ll >> W_TYPE_SIZE); \
1312 pl = (UWtype) __ll; \
1313}
1314#endif
1315
1316#if !defined(__umulsidi3)
1317#define __umulsidi3(u, v) \
1318 ({UWtype __hi, __lo; \
1319 umul_ppmm(__hi, __lo, u, v); \
1320 ((UDWtype) __hi << W_TYPE_SIZE) | __lo; })
1321#endif
1322
1323 /* If this machine has no inline assembler, use C macros. */
1324
1325#if !defined(add_ssaaaa)
1326#define add_ssaaaa(sh, sl, ah, al, bh, bl) \
1327do { \
1328 UWtype __x; \
1329 __x = (al) + (bl); \
1330 (sh) = (ah) + (bh) + (__x < (al)); \
1331 (sl) = __x; \
1332} while (0)
1333#endif
1334
1335#if !defined(sub_ddmmss)
1336#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
1337do { \
1338 UWtype __x; \
1339 __x = (al) - (bl); \
1340 (sh) = (ah) - (bh) - (__x > (al)); \
1341 (sl) = __x; \
1342} while (0)
1343#endif
1344
1345#if !defined(umul_ppmm)
1346#define umul_ppmm(w1, w0, u, v) \
1347do { \
1348 UWtype __x0, __x1, __x2, __x3; \
1349 UHWtype __ul, __vl, __uh, __vh; \
1350 UWtype __u = (u), __v = (v); \
1351 \
1352 __ul = __ll_lowpart(__u); \
1353 __uh = __ll_highpart(__u); \
1354 __vl = __ll_lowpart(__v); \
1355 __vh = __ll_highpart(__v); \
1356 \
1357 __x0 = (UWtype) __ul * __vl; \
1358 __x1 = (UWtype) __ul * __vh; \
1359 __x2 = (UWtype) __uh * __vl; \
1360 __x3 = (UWtype) __uh * __vh; \
1361 \
1362 __x1 += __ll_highpart(__x0);/* this can't give carry */ \
1363 __x1 += __x2; /* but this indeed can */ \
1364 if (__x1 < __x2) /* did we get it? */ \
1365 __x3 += __ll_B; /* yes, add it in the proper pos. */ \
1366 \
1367 (w1) = __x3 + __ll_highpart(__x1); \
1368 (w0) = (__ll_lowpart(__x1) << W_TYPE_SIZE/2) + __ll_lowpart(__x0); \
1369} while (0)
1370#endif
1371
1372#if !defined(umul_ppmm)
1373#define smul_ppmm(w1, w0, u, v) \
1374do { \
1375 UWtype __w1; \
1376 UWtype __m0 = (u), __m1 = (v); \
1377 umul_ppmm(__w1, w0, __m0, __m1); \
1378 (w1) = __w1 - (-(__m0 >> (W_TYPE_SIZE - 1)) & __m1) \
1379 - (-(__m1 >> (W_TYPE_SIZE - 1)) & __m0); \
1380} while (0)
1381#endif
1382
1383 /* Define this unconditionally, so it can be used for debugging. */
1384#define __udiv_qrnnd_c(q, r, n1, n0, d) \
1385do { \
1386 UWtype __d1, __d0, __q1, __q0, __r1, __r0, __m; \
1387 __d1 = __ll_highpart(d); \
1388 __d0 = __ll_lowpart(d); \
1389 \
1390 __r1 = (n1) % __d1; \
1391 __q1 = (n1) / __d1; \
1392 __m = (UWtype) __q1 * __d0; \
1393 __r1 = __r1 * __ll_B | __ll_highpart(n0); \
1394 if (__r1 < __m) { \
1395 __q1--, __r1 += (d); \
1396 if (__r1 >= (d)) /* i.e. we didn't get carry when adding to __r1 */ \
1397 if (__r1 < __m) \
1398 __q1--, __r1 += (d); \
1399 } \
1400 __r1 -= __m; \
1401 \
1402 __r0 = __r1 % __d1; \
1403 __q0 = __r1 / __d1; \
1404 __m = (UWtype) __q0 * __d0; \
1405 __r0 = __r0 * __ll_B | __ll_lowpart(n0); \
1406 if (__r0 < __m) { \
1407 __q0--, __r0 += (d); \
1408 if (__r0 >= (d)) \
1409 if (__r0 < __m) \
1410 __q0--, __r0 += (d); \
1411 } \
1412 __r0 -= __m; \
1413 \
1414 (q) = (UWtype) __q1 * __ll_B | __q0; \
1415 (r) = __r0; \
1416} while (0)
1417
1418/* If the processor has no udiv_qrnnd but sdiv_qrnnd, go through
1419 __udiv_w_sdiv (defined in libgcc or elsewhere). */
1420#if !defined(udiv_qrnnd) && defined(sdiv_qrnnd)
1421#define udiv_qrnnd(q, r, nh, nl, d) \
1422do { \
1423 UWtype __r; \
1424 (q) = __MPN(udiv_w_sdiv) (&__r, nh, nl, d); \
1425 (r) = __r; \
1426} while (0)
1427#endif
1428
1429 /* If udiv_qrnnd was not defined for this processor, use __udiv_qrnnd_c. */
1430#if !defined(udiv_qrnnd)
1431#define UDIV_NEEDS_NORMALIZATION 1
1432#define udiv_qrnnd __udiv_qrnnd_c
1433#endif
1434
1435#undef count_leading_zeros
1436#if !defined(count_leading_zeros)
1437 extern
1438#ifdef __STDC__
1439 const
1440#endif
1441 unsigned char __clz_tab[];
1442#define count_leading_zeros(count, x) \
1443do { \
1444 UWtype __xr = (x); \
1445 UWtype __a; \
1446 \
1447 if (W_TYPE_SIZE <= 32) { \
1448 __a = __xr < ((UWtype) 1 << 2*__BITS4) \
1449 ? (__xr < ((UWtype) 1 << __BITS4) ? 0 : __BITS4) \
1450 : (__xr < ((UWtype) 1 << 3*__BITS4) ? 2*__BITS4 : 3*__BITS4); \
1451 } \
1452 else { \
1453 for (__a = W_TYPE_SIZE - 8; __a > 0; __a -= 8) \
1454 if (((__xr >> __a) & 0xff) != 0) \
1455 break; \
1456 } \
1457 \
1458 (count) = W_TYPE_SIZE - (__clz_tab[__xr >> __a] + __a); \
1459} while (0)
1460 /* This version gives a well-defined value for zero. */
1461#define COUNT_LEADING_ZEROS_0 W_TYPE_SIZE
1462#endif
1463
1464#if !defined(count_trailing_zeros)
1465/* Define count_trailing_zeros using count_leading_zeros. The latter might be
1466 defined in asm, but if it is not, the C version above is good enough. */
1467#define count_trailing_zeros(count, x) \
1468do { \
1469 UWtype __ctz_x = (x); \
1470 UWtype __ctz_c; \
1471 count_leading_zeros(__ctz_c, __ctz_x & -__ctz_x); \
1472 (count) = W_TYPE_SIZE - 1 - __ctz_c; \
1473} while (0)
1474#endif
1475
1476#ifndef UDIV_NEEDS_NORMALIZATION
1477#define UDIV_NEEDS_NORMALIZATION 0
1478#endif
diff --git a/lib/mpi/mpi-add.c b/lib/mpi/mpi-add.c
new file mode 100644
index 000000000000..f56b9ba295e6
--- /dev/null
+++ b/lib/mpi/mpi-add.c
@@ -0,0 +1,234 @@
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
new file mode 100644
index 000000000000..854c9c6da025
--- /dev/null
+++ b/lib/mpi/mpi-bit.c
@@ -0,0 +1,236 @@
1/* mpi-bit.c - MPI bit level fucntions
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#include "longlong.h"
23
24const unsigned char __clz_tab[] = {
25 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
26 5, 5, 5, 5, 5, 5, 5, 5,
27 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
28 6, 6, 6, 6, 6, 6, 6, 6,
29 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
30 7, 7, 7, 7, 7, 7, 7, 7,
31 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
32 7, 7, 7, 7, 7, 7, 7, 7,
33 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
34 8, 8, 8, 8, 8, 8, 8, 8,
35 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
36 8, 8, 8, 8, 8, 8, 8, 8,
37 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
38 8, 8, 8, 8, 8, 8, 8, 8,
39 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
40 8, 8, 8, 8, 8, 8, 8, 8,
41};
42
43#define A_LIMB_1 ((mpi_limb_t) 1)
44
45/****************
46 * Sometimes we have MSL (most significant limbs) which are 0;
47 * this is for some reasons not good, so this function removes them.
48 */
49void mpi_normalize(MPI a)
50{
51 for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)
52 ;
53}
54
55/****************
56 * Return the number of bits in A.
57 */
58unsigned mpi_get_nbits(MPI a)
59{
60 unsigned n;
61
62 mpi_normalize(a);
63
64 if (a->nlimbs) {
65 mpi_limb_t alimb = a->d[a->nlimbs - 1];
66 if (alimb)
67 count_leading_zeros(n, alimb);
68 else
69 n = BITS_PER_MPI_LIMB;
70 n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
71 } else
72 n = 0;
73 return n;
74}
75EXPORT_SYMBOL_GPL(mpi_get_nbits);
76
77/****************
78 * Test whether bit N is set.
79 */
80int mpi_test_bit(MPI a, unsigned n)
81{
82 unsigned limbno, bitno;
83 mpi_limb_t limb;
84
85 limbno = n / BITS_PER_MPI_LIMB;
86 bitno = n % BITS_PER_MPI_LIMB;
87
88 if (limbno >= a->nlimbs)
89 return 0; /* too far left: this is a 0 */
90 limb = a->d[limbno];
91 return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
92}
93
94/****************
95 * Set bit N of A.
96 */
97int mpi_set_bit(MPI a, unsigned n)
98{
99 unsigned limbno, bitno;
100
101 limbno = n / BITS_PER_MPI_LIMB;
102 bitno = n % BITS_PER_MPI_LIMB;
103
104 if (limbno >= a->nlimbs) { /* resize */
105 if (a->alloced >= limbno)
106 if (mpi_resize(a, limbno + 1) < 0)
107 return -ENOMEM;
108 a->nlimbs = limbno + 1;
109 }
110 a->d[limbno] |= (A_LIMB_1 << bitno);
111 return 0;
112}
113
114/****************
115 * Set bit N of A. and clear all bits above
116 */
117int mpi_set_highbit(MPI a, unsigned n)
118{
119 unsigned limbno, bitno;
120
121 limbno = n / BITS_PER_MPI_LIMB;
122 bitno = n % BITS_PER_MPI_LIMB;
123
124 if (limbno >= a->nlimbs) { /* resize */
125 if (a->alloced >= limbno)
126 if (mpi_resize(a, limbno + 1) < 0)
127 return -ENOMEM;
128 a->nlimbs = limbno + 1;
129 }
130 a->d[limbno] |= (A_LIMB_1 << bitno);
131 for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
132 a->d[limbno] &= ~(A_LIMB_1 << bitno);
133 a->nlimbs = limbno + 1;
134 return 0;
135}
136
137/****************
138 * clear bit N of A and all bits above
139 */
140void mpi_clear_highbit(MPI a, unsigned n)
141{
142 unsigned limbno, bitno;
143
144 limbno = n / BITS_PER_MPI_LIMB;
145 bitno = n % BITS_PER_MPI_LIMB;
146
147 if (limbno >= a->nlimbs)
148 return; /* not allocated, so need to clear bits :-) */
149
150 for (; bitno < BITS_PER_MPI_LIMB; bitno++)
151 a->d[limbno] &= ~(A_LIMB_1 << bitno);
152 a->nlimbs = limbno + 1;
153}
154
155/****************
156 * Clear bit N of A.
157 */
158void mpi_clear_bit(MPI a, unsigned n)
159{
160 unsigned limbno, bitno;
161
162 limbno = n / BITS_PER_MPI_LIMB;
163 bitno = n % BITS_PER_MPI_LIMB;
164
165 if (limbno >= a->nlimbs)
166 return; /* don't need to clear this bit, it's to far to left */
167 a->d[limbno] &= ~(A_LIMB_1 << bitno);
168}
169
170/****************
171 * Shift A by N bits to the right
172 * FIXME: should use alloc_limb if X and A are same.
173 */
174int mpi_rshift(MPI x, MPI a, unsigned n)
175{
176 mpi_ptr_t xp;
177 mpi_size_t xsize;
178
179 xsize = a->nlimbs;
180 x->sign = a->sign;
181 if (RESIZE_IF_NEEDED(x, (size_t) xsize) < 0)
182 return -ENOMEM;
183 xp = x->d;
184
185 if (xsize) {
186 mpihelp_rshift(xp, a->d, xsize, n);
187 MPN_NORMALIZE(xp, xsize);
188 }
189 x->nlimbs = xsize;
190 return 0;
191}
192
193/****************
194 * Shift A by COUNT limbs to the left
195 * This is used only within the MPI library
196 */
197int mpi_lshift_limbs(MPI a, unsigned int count)
198{
199 mpi_ptr_t ap = a->d;
200 int n = a->nlimbs;
201 int i;
202
203 if (!count || !n)
204 return 0;
205
206 if (RESIZE_IF_NEEDED(a, n + count) < 0)
207 return -ENOMEM;
208
209 for (i = n - 1; i >= 0; i--)
210 ap[i + count] = ap[i];
211 for (i = 0; i < count; i++)
212 ap[i] = 0;
213 a->nlimbs += count;
214 return 0;
215}
216
217/****************
218 * Shift A by COUNT limbs to the right
219 * This is used only within the MPI library
220 */
221void mpi_rshift_limbs(MPI a, unsigned int count)
222{
223 mpi_ptr_t ap = a->d;
224 mpi_size_t n = a->nlimbs;
225 unsigned int i;
226
227 if (count >= n) {
228 a->nlimbs = 0;
229 return;
230 }
231
232 for (i = 0; i < n - count; i++)
233 ap[i] = ap[i + count];
234 ap[i] = 0;
235 a->nlimbs -= count;
236}
diff --git a/lib/mpi/mpi-cmp.c b/lib/mpi/mpi-cmp.c
new file mode 100644
index 000000000000..914bc42a8a80
--- /dev/null
+++ b/lib/mpi/mpi-cmp.c
@@ -0,0 +1,68 @@
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
new file mode 100644
index 000000000000..c3087d1390ce
--- /dev/null
+++ b/lib/mpi/mpi-div.c
@@ -0,0 +1,333 @@
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 memset(marker, 0, sizeof(marker));
153
154 /* Ensure space is enough for quotient and remainder.
155 * We need space for an extra limb in the remainder, because it's
156 * up-shifted (normalized) below. */
157 rsize = nsize + 1;
158 if (mpi_resize(rem, rsize) < 0)
159 goto nomem;
160
161 qsize = rsize - dsize; /* qsize cannot be bigger than this. */
162 if (qsize <= 0) {
163 if (num != rem) {
164 rem->nlimbs = num->nlimbs;
165 rem->sign = num->sign;
166 MPN_COPY(rem->d, num->d, nsize);
167 }
168 if (quot) {
169 /* This needs to follow the assignment to rem, in case the
170 * numerator and quotient are the same. */
171 quot->nlimbs = 0;
172 quot->sign = 0;
173 }
174 return 0;
175 }
176
177 if (quot)
178 if (mpi_resize(quot, qsize) < 0)
179 goto nomem;
180
181 /* Read pointers here, when reallocation is finished. */
182 np = num->d;
183 dp = den->d;
184 rp = rem->d;
185
186 /* Optimize division by a single-limb divisor. */
187 if (dsize == 1) {
188 mpi_limb_t rlimb;
189 if (quot) {
190 qp = quot->d;
191 rlimb = mpihelp_divmod_1(qp, np, nsize, dp[0]);
192 qsize -= qp[qsize - 1] == 0;
193 quot->nlimbs = qsize;
194 quot->sign = sign_quotient;
195 } else
196 rlimb = mpihelp_mod_1(np, nsize, dp[0]);
197 rp[0] = rlimb;
198 rsize = rlimb != 0 ? 1 : 0;
199 rem->nlimbs = rsize;
200 rem->sign = sign_remainder;
201 return 0;
202 }
203
204 if (quot) {
205 qp = quot->d;
206 /* Make sure QP and NP point to different objects. Otherwise the
207 * numerator would be gradually overwritten by the quotient limbs. */
208 if (qp == np) { /* Copy NP object to temporary space. */
209 np = marker[markidx++] = mpi_alloc_limb_space(nsize);
210 MPN_COPY(np, qp, nsize);
211 }
212 } else /* Put quotient at top of remainder. */
213 qp = rp + dsize;
214
215 count_leading_zeros(normalization_steps, dp[dsize - 1]);
216
217 /* Normalize the denominator, i.e. make its most significant bit set by
218 * shifting it NORMALIZATION_STEPS bits to the left. Also shift the
219 * numerator the same number of steps (to keep the quotient the same!).
220 */
221 if (normalization_steps) {
222 mpi_ptr_t tp;
223 mpi_limb_t nlimb;
224
225 /* Shift up the denominator setting the most significant bit of
226 * the most significant word. Use temporary storage not to clobber
227 * the original contents of the denominator. */
228 tp = marker[markidx++] = mpi_alloc_limb_space(dsize);
229 if (!tp)
230 goto nomem;
231 mpihelp_lshift(tp, dp, dsize, normalization_steps);
232 dp = tp;
233
234 /* Shift up the numerator, possibly introducing a new most
235 * significant word. Move the shifted numerator in the remainder
236 * meanwhile. */
237 nlimb = mpihelp_lshift(rp, np, nsize, normalization_steps);
238 if (nlimb) {
239 rp[nsize] = nlimb;
240 rsize = nsize + 1;
241 } else
242 rsize = nsize;
243 } else {
244 /* The denominator is already normalized, as required. Copy it to
245 * temporary space if it overlaps with the quotient or remainder. */
246 if (dp == rp || (quot && (dp == qp))) {
247 mpi_ptr_t tp;
248
249 tp = marker[markidx++] = mpi_alloc_limb_space(dsize);
250 if (!tp)
251 goto nomem;
252 MPN_COPY(tp, dp, dsize);
253 dp = tp;
254 }
255
256 /* Move the numerator to the remainder. */
257 if (rp != np)
258 MPN_COPY(rp, np, nsize);
259
260 rsize = nsize;
261 }
262
263 q_limb = mpihelp_divrem(qp, 0, rp, rsize, dp, dsize);
264
265 if (quot) {
266 qsize = rsize - dsize;
267 if (q_limb) {
268 qp[qsize] = q_limb;
269 qsize += 1;
270 }
271
272 quot->nlimbs = qsize;
273 quot->sign = sign_quotient;
274 }
275
276 rsize = dsize;
277 MPN_NORMALIZE(rp, rsize);
278
279 if (normalization_steps && rsize) {
280 mpihelp_rshift(rp, rp, rsize, normalization_steps);
281 rsize -= rp[rsize - 1] == 0 ? 1 : 0;
282 }
283
284 rem->nlimbs = rsize;
285 rem->sign = sign_remainder;
286
287 rc = 0;
288nomem:
289 while (markidx)
290 mpi_free_limb_space(marker[--markidx]);
291 return rc;
292}
293
294int mpi_tdiv_q_2exp(MPI w, MPI u, unsigned count)
295{
296 mpi_size_t usize, wsize;
297 mpi_size_t limb_cnt;
298
299 usize = u->nlimbs;
300 limb_cnt = count / BITS_PER_MPI_LIMB;
301 wsize = usize - limb_cnt;
302 if (limb_cnt >= usize)
303 w->nlimbs = 0;
304 else {
305 mpi_ptr_t wp;
306 mpi_ptr_t up;
307
308 if (RESIZE_IF_NEEDED(w, wsize) < 0)
309 return -ENOMEM;
310 wp = w->d;
311 up = u->d;
312
313 count %= BITS_PER_MPI_LIMB;
314 if (count) {
315 mpihelp_rshift(wp, up + limb_cnt, wsize, count);
316 wsize -= !wp[wsize - 1];
317 } else {
318 MPN_COPY_INCR(wp, up + limb_cnt, wsize);
319 }
320
321 w->nlimbs = wsize;
322 }
323 return 0;
324}
325
326/****************
327 * Check whether dividend is divisible by divisor
328 * (note: divisor must fit into a limb)
329 */
330int mpi_divisible_ui(MPI dividend, ulong divisor)
331{
332 return !mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor);
333}
diff --git a/lib/mpi/mpi-gcd.c b/lib/mpi/mpi-gcd.c
new file mode 100644
index 000000000000..13c48aef9c4e
--- /dev/null
+++ b/lib/mpi/mpi-gcd.c
@@ -0,0 +1,59 @@
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
new file mode 100644
index 000000000000..654f68aeed8b
--- /dev/null
+++ b/lib/mpi/mpi-inline.c
@@ -0,0 +1,31 @@
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-inline.h b/lib/mpi/mpi-inline.h
new file mode 100644
index 000000000000..e2b39852b30a
--- /dev/null
+++ b/lib/mpi/mpi-inline.h
@@ -0,0 +1,122 @@
1/* mpi-inline.h - Internal to the Multi Precision Integers
2 * Copyright (C) 1994, 1996, 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 * 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#ifndef G10_MPI_INLINE_H
30#define G10_MPI_INLINE_H
31
32#ifndef G10_MPI_INLINE_DECL
33#define G10_MPI_INLINE_DECL extern inline
34#endif
35
36G10_MPI_INLINE_DECL mpi_limb_t
37mpihelp_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
38 mpi_size_t s1_size, mpi_limb_t s2_limb)
39{
40 mpi_limb_t x;
41
42 x = *s1_ptr++;
43 s2_limb += x;
44 *res_ptr++ = s2_limb;
45 if (s2_limb < x) { /* sum is less than the left operand: handle carry */
46 while (--s1_size) {
47 x = *s1_ptr++ + 1; /* add carry */
48 *res_ptr++ = x; /* and store */
49 if (x) /* not 0 (no overflow): we can stop */
50 goto leave;
51 }
52 return 1; /* return carry (size of s1 to small) */
53 }
54
55leave:
56 if (res_ptr != s1_ptr) { /* not the same variable */
57 mpi_size_t i; /* copy the rest */
58 for (i = 0; i < s1_size - 1; i++)
59 res_ptr[i] = s1_ptr[i];
60 }
61 return 0; /* no carry */
62}
63
64G10_MPI_INLINE_DECL mpi_limb_t
65mpihelp_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
66 mpi_ptr_t s2_ptr, mpi_size_t s2_size)
67{
68 mpi_limb_t cy = 0;
69
70 if (s2_size)
71 cy = mpihelp_add_n(res_ptr, s1_ptr, s2_ptr, s2_size);
72
73 if (s1_size - s2_size)
74 cy = mpihelp_add_1(res_ptr + s2_size, s1_ptr + s2_size,
75 s1_size - s2_size, cy);
76 return cy;
77}
78
79G10_MPI_INLINE_DECL mpi_limb_t
80mpihelp_sub_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
81 mpi_size_t s1_size, mpi_limb_t s2_limb)
82{
83 mpi_limb_t x;
84
85 x = *s1_ptr++;
86 s2_limb = x - s2_limb;
87 *res_ptr++ = s2_limb;
88 if (s2_limb > x) {
89 while (--s1_size) {
90 x = *s1_ptr++;
91 *res_ptr++ = x - 1;
92 if (x)
93 goto leave;
94 }
95 return 1;
96 }
97
98leave:
99 if (res_ptr != s1_ptr) {
100 mpi_size_t i;
101 for (i = 0; i < s1_size - 1; i++)
102 res_ptr[i] = s1_ptr[i];
103 }
104 return 0;
105}
106
107G10_MPI_INLINE_DECL mpi_limb_t
108mpihelp_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
109 mpi_ptr_t s2_ptr, mpi_size_t s2_size)
110{
111 mpi_limb_t cy = 0;
112
113 if (s2_size)
114 cy = mpihelp_sub_n(res_ptr, s1_ptr, s2_ptr, s2_size);
115
116 if (s1_size - s2_size)
117 cy = mpihelp_sub_1(res_ptr + s2_size, s1_ptr + s2_size,
118 s1_size - s2_size, cy);
119 return cy;
120}
121
122#endif /*G10_MPI_INLINE_H */
diff --git a/lib/mpi/mpi-internal.h b/lib/mpi/mpi-internal.h
new file mode 100644
index 000000000000..77adcf6bc257
--- /dev/null
+++ b/lib/mpi/mpi-internal.h
@@ -0,0 +1,261 @@
1/* mpi-internal.h - Internal to the Multi Precision Integers
2 * Copyright (C) 1994, 1996 Free Software Foundation, Inc.
3 * Copyright (C) 1998, 2000 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#ifndef G10_MPI_INTERNAL_H
31#define G10_MPI_INTERNAL_H
32
33#include <linux/module.h>
34#include <linux/kernel.h>
35#include <linux/slab.h>
36#include <linux/string.h>
37#include <linux/mpi.h>
38#include <linux/errno.h>
39
40#define log_debug printk
41#define log_bug printk
42
43#define assert(x) \
44 do { \
45 if (!x) \
46 log_bug("failed assertion\n"); \
47 } while (0);
48
49/* If KARATSUBA_THRESHOLD is not already defined, define it to a
50 * value which is good on most machines. */
51
52/* tested 4, 16, 32 and 64, where 16 gave the best performance when
53 * checking a 768 and a 1024 bit ElGamal signature.
54 * (wk 22.12.97) */
55#ifndef KARATSUBA_THRESHOLD
56#define KARATSUBA_THRESHOLD 16
57#endif
58
59/* The code can't handle KARATSUBA_THRESHOLD smaller than 2. */
60#if KARATSUBA_THRESHOLD < 2
61#undef KARATSUBA_THRESHOLD
62#define KARATSUBA_THRESHOLD 2
63#endif
64
65typedef mpi_limb_t *mpi_ptr_t; /* pointer to a limb */
66typedef int mpi_size_t; /* (must be a signed type) */
67
68#define ABS(x) (x >= 0 ? x : -x)
69#define MIN(l, o) ((l) < (o) ? (l) : (o))
70#define MAX(h, i) ((h) > (i) ? (h) : (i))
71
72static inline int RESIZE_IF_NEEDED(MPI a, unsigned b)
73{
74 if (a->alloced < b)
75 return mpi_resize(a, b);
76 return 0;
77}
78
79/* Copy N limbs from S to D. */
80#define MPN_COPY(d, s, n) \
81 do { \
82 mpi_size_t _i; \
83 for (_i = 0; _i < (n); _i++) \
84 (d)[_i] = (s)[_i]; \
85 } while (0)
86
87#define MPN_COPY_INCR(d, s, n) \
88 do { \
89 mpi_size_t _i; \
90 for (_i = 0; _i < (n); _i++) \
91 (d)[_i] = (d)[_i]; \
92 } while (0)
93
94#define MPN_COPY_DECR(d, s, n) \
95 do { \
96 mpi_size_t _i; \
97 for (_i = (n)-1; _i >= 0; _i--) \
98 (d)[_i] = (s)[_i]; \
99 } while (0)
100
101/* Zero N limbs at D */
102#define MPN_ZERO(d, n) \
103 do { \
104 int _i; \
105 for (_i = 0; _i < (n); _i++) \
106 (d)[_i] = 0; \
107 } while (0)
108
109#define MPN_NORMALIZE(d, n) \
110 do { \
111 while ((n) > 0) { \
112 if ((d)[(n)-1]) \
113 break; \
114 (n)--; \
115 } \
116 } while (0)
117
118#define MPN_NORMALIZE_NOT_ZERO(d, n) \
119 do { \
120 for (;;) { \
121 if ((d)[(n)-1]) \
122 break; \
123 (n)--; \
124 } \
125 } while (0)
126
127#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
128 do { \
129 if ((size) < KARATSUBA_THRESHOLD) \
130 mul_n_basecase(prodp, up, vp, size); \
131 else \
132 mul_n(prodp, up, vp, size, tspace); \
133 } while (0);
134
135/* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
136 * limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
137 * If this would yield overflow, DI should be the largest possible number
138 * (i.e., only ones). For correct operation, the most significant bit of D
139 * has to be set. Put the quotient in Q and the remainder in R.
140 */
141#define UDIV_QRNND_PREINV(q, r, nh, nl, d, di) \
142 do { \
143 mpi_limb_t _q, _ql, _r; \
144 mpi_limb_t _xh, _xl; \
145 umul_ppmm(_q, _ql, (nh), (di)); \
146 _q += (nh); /* DI is 2**BITS_PER_MPI_LIMB too small */ \
147 umul_ppmm(_xh, _xl, _q, (d)); \
148 sub_ddmmss(_xh, _r, (nh), (nl), _xh, _xl); \
149 if (_xh) { \
150 sub_ddmmss(_xh, _r, _xh, _r, 0, (d)); \
151 _q++; \
152 if (_xh) { \
153 sub_ddmmss(_xh, _r, _xh, _r, 0, (d)); \
154 _q++; \
155 } \
156 } \
157 if (_r >= (d)) { \
158 _r -= (d); \
159 _q++; \
160 } \
161 (r) = _r; \
162 (q) = _q; \
163 } while (0)
164
165/*-- mpiutil.c --*/
166mpi_ptr_t mpi_alloc_limb_space(unsigned nlimbs);
167void mpi_free_limb_space(mpi_ptr_t a);
168void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs);
169
170/*-- mpi-bit.c --*/
171void mpi_rshift_limbs(MPI a, unsigned int count);
172int mpi_lshift_limbs(MPI a, unsigned int count);
173
174/*-- mpihelp-add.c --*/
175mpi_limb_t mpihelp_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
176 mpi_size_t s1_size, mpi_limb_t s2_limb);
177mpi_limb_t mpihelp_add_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
178 mpi_ptr_t s2_ptr, mpi_size_t size);
179mpi_limb_t mpihelp_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
180 mpi_ptr_t s2_ptr, mpi_size_t s2_size);
181
182/*-- mpihelp-sub.c --*/
183mpi_limb_t mpihelp_sub_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
184 mpi_size_t s1_size, mpi_limb_t s2_limb);
185mpi_limb_t mpihelp_sub_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
186 mpi_ptr_t s2_ptr, mpi_size_t size);
187mpi_limb_t mpihelp_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
188 mpi_ptr_t s2_ptr, mpi_size_t s2_size);
189
190/*-- mpihelp-cmp.c --*/
191int mpihelp_cmp(mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size);
192
193/*-- mpihelp-mul.c --*/
194
195struct karatsuba_ctx {
196 struct karatsuba_ctx *next;
197 mpi_ptr_t tspace;
198 mpi_size_t tspace_size;
199 mpi_ptr_t tp;
200 mpi_size_t tp_size;
201};
202
203void mpihelp_release_karatsuba_ctx(struct karatsuba_ctx *ctx);
204
205mpi_limb_t mpihelp_addmul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
206 mpi_size_t s1_size, mpi_limb_t s2_limb);
207mpi_limb_t mpihelp_submul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
208 mpi_size_t s1_size, mpi_limb_t s2_limb);
209int mpihelp_mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size);
210int mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
211 mpi_ptr_t vp, mpi_size_t vsize, mpi_limb_t *_result);
212void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size);
213void mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size,
214 mpi_ptr_t tspace);
215
216int mpihelp_mul_karatsuba_case(mpi_ptr_t prodp,
217 mpi_ptr_t up, mpi_size_t usize,
218 mpi_ptr_t vp, mpi_size_t vsize,
219 struct karatsuba_ctx *ctx);
220
221/*-- mpihelp-mul_1.c (or xxx/cpu/ *.S) --*/
222mpi_limb_t mpihelp_mul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
223 mpi_size_t s1_size, mpi_limb_t s2_limb);
224
225/*-- mpihelp-div.c --*/
226mpi_limb_t mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
227 mpi_limb_t divisor_limb);
228mpi_limb_t mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs,
229 mpi_ptr_t np, mpi_size_t nsize,
230 mpi_ptr_t dp, mpi_size_t dsize);
231mpi_limb_t mpihelp_divmod_1(mpi_ptr_t quot_ptr,
232 mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
233 mpi_limb_t divisor_limb);
234
235/*-- mpihelp-shift.c --*/
236mpi_limb_t mpihelp_lshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
237 unsigned cnt);
238mpi_limb_t mpihelp_rshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
239 unsigned cnt);
240
241/* Define stuff for longlong.h. */
242#define W_TYPE_SIZE BITS_PER_MPI_LIMB
243typedef mpi_limb_t UWtype;
244typedef unsigned int UHWtype;
245#if defined(__GNUC__)
246typedef unsigned int UQItype __attribute__ ((mode(QI)));
247typedef int SItype __attribute__ ((mode(SI)));
248typedef unsigned int USItype __attribute__ ((mode(SI)));
249typedef int DItype __attribute__ ((mode(DI)));
250typedef unsigned int UDItype __attribute__ ((mode(DI)));
251#else
252typedef unsigned char UQItype;
253typedef long SItype;
254typedef unsigned long USItype;
255#endif
256
257#ifdef __GNUC__
258#include "mpi-inline.h"
259#endif
260
261#endif /*G10_MPI_INTERNAL_H */
diff --git a/lib/mpi/mpi-inv.c b/lib/mpi/mpi-inv.c
new file mode 100644
index 000000000000..0951f9847745
--- /dev/null
+++ b/lib/mpi/mpi-inv.c
@@ -0,0 +1,187 @@
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
new file mode 100644
index 000000000000..7328d0d6c748
--- /dev/null
+++ b/lib/mpi/mpi-mpow.c
@@ -0,0 +1,134 @@
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
new file mode 100644
index 000000000000..1f3219e27292
--- /dev/null
+++ b/lib/mpi/mpi-mul.c
@@ -0,0 +1,194 @@
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-pow.c b/lib/mpi/mpi-pow.c
new file mode 100644
index 000000000000..b04a3cf80080
--- /dev/null
+++ b/lib/mpi/mpi-pow.c
@@ -0,0 +1,323 @@
1/* mpi-pow.c - MPI functions
2 * Copyright (C) 1994, 1996, 1998, 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 * 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 <linux/string.h>
30#include "mpi-internal.h"
31#include "longlong.h"
32
33/****************
34 * RES = BASE ^ EXP mod MOD
35 */
36int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
37{
38 mpi_ptr_t mp_marker = NULL, bp_marker = NULL, ep_marker = NULL;
39 mpi_ptr_t xp_marker = NULL;
40 mpi_ptr_t tspace = NULL;
41 mpi_ptr_t rp, ep, mp, bp;
42 mpi_size_t esize, msize, bsize, rsize;
43 int esign, msign, bsign, rsign;
44 mpi_size_t size;
45 int mod_shift_cnt;
46 int negative_result;
47 int assign_rp = 0;
48 mpi_size_t tsize = 0; /* to avoid compiler warning */
49 /* fixme: we should check that the warning is void */
50 int rc = -ENOMEM;
51
52 esize = exp->nlimbs;
53 msize = mod->nlimbs;
54 size = 2 * msize;
55 esign = exp->sign;
56 msign = mod->sign;
57
58 rp = res->d;
59 ep = exp->d;
60
61 if (!msize)
62 msize = 1 / msize; /* provoke a signal */
63
64 if (!esize) {
65 /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0
66 * depending on if MOD equals 1. */
67 rp[0] = 1;
68 res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
69 res->sign = 0;
70 goto leave;
71 }
72
73 /* Normalize MOD (i.e. make its most significant bit set) as required by
74 * mpn_divrem. This will make the intermediate values in the calculation
75 * slightly larger, but the correct result is obtained after a final
76 * reduction using the original MOD value. */
77 mp = mp_marker = mpi_alloc_limb_space(msize);
78 if (!mp)
79 goto enomem;
80 count_leading_zeros(mod_shift_cnt, mod->d[msize - 1]);
81 if (mod_shift_cnt)
82 mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt);
83 else
84 MPN_COPY(mp, mod->d, msize);
85
86 bsize = base->nlimbs;
87 bsign = base->sign;
88 if (bsize > msize) { /* The base is larger than the module. Reduce it. */
89 /* Allocate (BSIZE + 1) with space for remainder and quotient.
90 * (The quotient is (bsize - msize + 1) limbs.) */
91 bp = bp_marker = mpi_alloc_limb_space(bsize + 1);
92 if (!bp)
93 goto enomem;
94 MPN_COPY(bp, base->d, bsize);
95 /* We don't care about the quotient, store it above the remainder,
96 * at BP + MSIZE. */
97 mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize);
98 bsize = msize;
99 /* Canonicalize the base, since we are going to multiply with it
100 * quite a few times. */
101 MPN_NORMALIZE(bp, bsize);
102 } else
103 bp = base->d;
104
105 if (!bsize) {
106 res->nlimbs = 0;
107 res->sign = 0;
108 goto leave;
109 }
110
111 if (res->alloced < size) {
112 /* We have to allocate more space for RES. If any of the input
113 * parameters are identical to RES, defer deallocation of the old
114 * space. */
115 if (rp == ep || rp == mp || rp == bp) {
116 rp = mpi_alloc_limb_space(size);
117 if (!rp)
118 goto enomem;
119 assign_rp = 1;
120 } else {
121 if (mpi_resize(res, size) < 0)
122 goto enomem;
123 rp = res->d;
124 }
125 } else { /* Make BASE, EXP and MOD not overlap with RES. */
126 if (rp == bp) {
127 /* RES and BASE are identical. Allocate temp. space for BASE. */
128 BUG_ON(bp_marker);
129 bp = bp_marker = mpi_alloc_limb_space(bsize);
130 if (!bp)
131 goto enomem;
132 MPN_COPY(bp, rp, bsize);
133 }
134 if (rp == ep) {
135 /* RES and EXP are identical. Allocate temp. space for EXP. */
136 ep = ep_marker = mpi_alloc_limb_space(esize);
137 if (!ep)
138 goto enomem;
139 MPN_COPY(ep, rp, esize);
140 }
141 if (rp == mp) {
142 /* RES and MOD are identical. Allocate temporary space for MOD. */
143 BUG_ON(mp_marker);
144 mp = mp_marker = mpi_alloc_limb_space(msize);
145 if (!mp)
146 goto enomem;
147 MPN_COPY(mp, rp, msize);
148 }
149 }
150
151 MPN_COPY(rp, bp, bsize);
152 rsize = bsize;
153 rsign = bsign;
154
155 {
156 mpi_size_t i;
157 mpi_ptr_t xp;
158 int c;
159 mpi_limb_t e;
160 mpi_limb_t carry_limb;
161 struct karatsuba_ctx karactx;
162
163 xp = xp_marker = mpi_alloc_limb_space(2 * (msize + 1));
164 if (!xp)
165 goto enomem;
166
167 memset(&karactx, 0, sizeof karactx);
168 negative_result = (ep[0] & 1) && base->sign;
169
170 i = esize - 1;
171 e = ep[i];
172 count_leading_zeros(c, e);
173 e = (e << c) << 1; /* shift the exp bits to the left, lose msb */
174 c = BITS_PER_MPI_LIMB - 1 - c;
175
176 /* Main loop.
177 *
178 * Make the result be pointed to alternately by XP and RP. This
179 * helps us avoid block copying, which would otherwise be necessary
180 * with the overlap restrictions of mpihelp_divmod. With 50% probability
181 * the result after this loop will be in the area originally pointed
182 * by RP (==RES->d), and with 50% probability in the area originally
183 * pointed to by XP.
184 */
185
186 for (;;) {
187 while (c) {
188 mpi_ptr_t tp;
189 mpi_size_t xsize;
190
191 /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */
192 if (rsize < KARATSUBA_THRESHOLD)
193 mpih_sqr_n_basecase(xp, rp, rsize);
194 else {
195 if (!tspace) {
196 tsize = 2 * rsize;
197 tspace =
198 mpi_alloc_limb_space(tsize);
199 if (!tspace)
200 goto enomem;
201 } else if (tsize < (2 * rsize)) {
202 mpi_free_limb_space(tspace);
203 tsize = 2 * rsize;
204 tspace =
205 mpi_alloc_limb_space(tsize);
206 if (!tspace)
207 goto enomem;
208 }
209 mpih_sqr_n(xp, rp, rsize, tspace);
210 }
211
212 xsize = 2 * rsize;
213 if (xsize > msize) {
214 mpihelp_divrem(xp + msize, 0, xp, xsize,
215 mp, msize);
216 xsize = msize;
217 }
218
219 tp = rp;
220 rp = xp;
221 xp = tp;
222 rsize = xsize;
223
224 if ((mpi_limb_signed_t) e < 0) {
225 /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */
226 if (bsize < KARATSUBA_THRESHOLD) {
227 mpi_limb_t tmp;
228 if (mpihelp_mul
229 (xp, rp, rsize, bp, bsize,
230 &tmp) < 0)
231 goto enomem;
232 } else {
233 if (mpihelp_mul_karatsuba_case
234 (xp, rp, rsize, bp, bsize,
235 &karactx) < 0)
236 goto enomem;
237 }
238
239 xsize = rsize + bsize;
240 if (xsize > msize) {
241 mpihelp_divrem(xp + msize, 0,
242 xp, xsize, mp,
243 msize);
244 xsize = msize;
245 }
246
247 tp = rp;
248 rp = xp;
249 xp = tp;
250 rsize = xsize;
251 }
252 e <<= 1;
253 c--;
254 }
255
256 i--;
257 if (i < 0)
258 break;
259 e = ep[i];
260 c = BITS_PER_MPI_LIMB;
261 }
262
263 /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT
264 * steps. Adjust the result by reducing it with the original MOD.
265 *
266 * Also make sure the result is put in RES->d (where it already
267 * might be, see above).
268 */
269 if (mod_shift_cnt) {
270 carry_limb =
271 mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt);
272 rp = res->d;
273 if (carry_limb) {
274 rp[rsize] = carry_limb;
275 rsize++;
276 }
277 } else {
278 MPN_COPY(res->d, rp, rsize);
279 rp = res->d;
280 }
281
282 if (rsize >= msize) {
283 mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize);
284 rsize = msize;
285 }
286
287 /* Remove any leading zero words from the result. */
288 if (mod_shift_cnt)
289 mpihelp_rshift(rp, rp, rsize, mod_shift_cnt);
290 MPN_NORMALIZE(rp, rsize);
291
292 mpihelp_release_karatsuba_ctx(&karactx);
293 }
294
295 if (negative_result && rsize) {
296 if (mod_shift_cnt)
297 mpihelp_rshift(mp, mp, msize, mod_shift_cnt);
298 mpihelp_sub(rp, mp, msize, rp, rsize);
299 rsize = msize;
300 rsign = msign;
301 MPN_NORMALIZE(rp, rsize);
302 }
303 res->nlimbs = rsize;
304 res->sign = rsign;
305
306leave:
307 rc = 0;
308enomem:
309 if (assign_rp)
310 mpi_assign_limb_space(res, rp, size);
311 if (mp_marker)
312 mpi_free_limb_space(mp_marker);
313 if (bp_marker)
314 mpi_free_limb_space(bp_marker);
315 if (ep_marker)
316 mpi_free_limb_space(ep_marker);
317 if (xp_marker)
318 mpi_free_limb_space(xp_marker);
319 if (tspace)
320 mpi_free_limb_space(tspace);
321 return rc;
322}
323EXPORT_SYMBOL_GPL(mpi_powm);
diff --git a/lib/mpi/mpi-scan.c b/lib/mpi/mpi-scan.c
new file mode 100644
index 000000000000..b2da5ad96199
--- /dev/null
+++ b/lib/mpi/mpi-scan.c
@@ -0,0 +1,136 @@
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
new file mode 100644
index 000000000000..fe84bb978e3b
--- /dev/null
+++ b/lib/mpi/mpicoder.c
@@ -0,0 +1,365 @@
1/* mpicoder.c - Coder for the external representation of MPIs
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
23#define DIM(v) (sizeof(v)/sizeof((v)[0]))
24#define MAX_EXTERN_MPI_BITS 16384
25
26static uint8_t asn[15] = /* Object ID is 1.3.14.3.2.26 */
27{ 0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03,
28 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14
29};
30
31MPI do_encode_md(const void *sha_buffer, unsigned nbits)
32{
33 int nframe = (nbits + 7) / 8;
34 uint8_t *frame, *fr_pt;
35 int i = 0, n;
36 size_t asnlen = DIM(asn);
37 MPI a = MPI_NULL;
38
39 if (SHA1_DIGEST_LENGTH + asnlen + 4 > nframe)
40 pr_info("MPI: can't encode a %d bit MD into a %d bits frame\n",
41 (int)(SHA1_DIGEST_LENGTH * 8), (int)nbits);
42
43 /* We encode the MD in this way:
44 *
45 * 0 A PAD(n bytes) 0 ASN(asnlen bytes) MD(len bytes)
46 *
47 * PAD consists of FF bytes.
48 */
49 frame = kmalloc(nframe, GFP_KERNEL);
50 if (!frame)
51 return MPI_NULL;
52 n = 0;
53 frame[n++] = 0;
54 frame[n++] = 1; /* block type */
55 i = nframe - SHA1_DIGEST_LENGTH - asnlen - 3;
56
57 if (i <= 1) {
58 pr_info("MPI: message digest encoding failed\n");
59 kfree(frame);
60 return a;
61 }
62
63 memset(frame + n, 0xff, i);
64 n += i;
65 frame[n++] = 0;
66 memcpy(frame + n, &asn, asnlen);
67 n += asnlen;
68 memcpy(frame + n, sha_buffer, SHA1_DIGEST_LENGTH);
69 n += SHA1_DIGEST_LENGTH;
70
71 i = nframe;
72 fr_pt = frame;
73
74 if (n != nframe) {
75 printk
76 ("MPI: message digest encoding failed, frame length is wrong\n");
77 kfree(frame);
78 return a;
79 }
80
81 a = mpi_alloc((nframe + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB);
82 mpi_set_buffer(a, frame, nframe, 0);
83 kfree(frame);
84
85 return a;
86}
87
88MPI mpi_read_from_buffer(const void *xbuffer, unsigned *ret_nread)
89{
90 const uint8_t *buffer = xbuffer;
91 int i, j;
92 unsigned nbits, nbytes, nlimbs, nread = 0;
93 mpi_limb_t a;
94 MPI val = MPI_NULL;
95
96 if (*ret_nread < 2)
97 goto leave;
98 nbits = buffer[0] << 8 | buffer[1];
99
100 if (nbits > MAX_EXTERN_MPI_BITS) {
101 pr_info("MPI: mpi too large (%u bits)\n", nbits);
102 goto leave;
103 }
104 buffer += 2;
105 nread = 2;
106
107 nbytes = (nbits + 7) / 8;
108 nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
109 val = mpi_alloc(nlimbs);
110 if (!val)
111 return MPI_NULL;
112 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
113 i %= BYTES_PER_MPI_LIMB;
114 val->nbits = nbits;
115 j = val->nlimbs = nlimbs;
116 val->sign = 0;
117 for (; j > 0; j--) {
118 a = 0;
119 for (; i < BYTES_PER_MPI_LIMB; i++) {
120 if (++nread > *ret_nread) {
121 printk
122 ("MPI: mpi larger than buffer nread=%d ret_nread=%d\n",
123 nread, *ret_nread);
124 goto leave;
125 }
126 a <<= 8;
127 a |= *buffer++;
128 }
129 i = 0;
130 val->d[j - 1] = a;
131 }
132
133leave:
134 *ret_nread = nread;
135 return val;
136}
137EXPORT_SYMBOL_GPL(mpi_read_from_buffer);
138
139/****************
140 * Make an mpi from a character string.
141 */
142int mpi_fromstr(MPI val, const char *str)
143{
144 int hexmode = 0, sign = 0, prepend_zero = 0, i, j, c, c1, c2;
145 unsigned nbits, nbytes, nlimbs;
146 mpi_limb_t a;
147
148 if (*str == '-') {
149 sign = 1;
150 str++;
151 }
152 if (*str == '0' && str[1] == 'x')
153 hexmode = 1;
154 else
155 return -EINVAL; /* other bases are not yet supported */
156 str += 2;
157
158 nbits = strlen(str) * 4;
159 if (nbits % 8)
160 prepend_zero = 1;
161 nbytes = (nbits + 7) / 8;
162 nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
163 if (val->alloced < nlimbs)
164 if (!mpi_resize(val, nlimbs))
165 return -ENOMEM;
166 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB;
167 i %= BYTES_PER_MPI_LIMB;
168 j = val->nlimbs = nlimbs;
169 val->sign = sign;
170 for (; j > 0; j--) {
171 a = 0;
172 for (; i < BYTES_PER_MPI_LIMB; i++) {
173 if (prepend_zero) {
174 c1 = '0';
175 prepend_zero = 0;
176 } else
177 c1 = *str++;
178 assert(c1);
179 c2 = *str++;
180 assert(c2);
181 if (c1 >= '0' && c1 <= '9')
182 c = c1 - '0';
183 else if (c1 >= 'a' && c1 <= 'f')
184 c = c1 - 'a' + 10;
185 else if (c1 >= 'A' && c1 <= 'F')
186 c = c1 - 'A' + 10;
187 else {
188 mpi_clear(val);
189 return 1;
190 }
191 c <<= 4;
192 if (c2 >= '0' && c2 <= '9')
193 c |= c2 - '0';
194 else if (c2 >= 'a' && c2 <= 'f')
195 c |= c2 - 'a' + 10;
196 else if (c2 >= 'A' && c2 <= 'F')
197 c |= c2 - 'A' + 10;
198 else {
199 mpi_clear(val);
200 return 1;
201 }
202 a <<= 8;
203 a |= c;
204 }
205 i = 0;
206
207 val->d[j - 1] = a;
208 }
209
210 return 0;
211}
212EXPORT_SYMBOL_GPL(mpi_fromstr);
213
214/****************
215 * Special function to get the low 8 bytes from an mpi.
216 * This can be used as a keyid; KEYID is an 2 element array.
217 * Return the low 4 bytes.
218 */
219u32 mpi_get_keyid(const MPI a, u32 *keyid)
220{
221#if BYTES_PER_MPI_LIMB == 4
222 if (keyid) {
223 keyid[0] = a->nlimbs >= 2 ? a->d[1] : 0;
224 keyid[1] = a->nlimbs >= 1 ? a->d[0] : 0;
225 }
226 return a->nlimbs >= 1 ? a->d[0] : 0;
227#elif BYTES_PER_MPI_LIMB == 8
228 if (keyid) {
229 keyid[0] = a->nlimbs ? (u32) (a->d[0] >> 32) : 0;
230 keyid[1] = a->nlimbs ? (u32) (a->d[0] & 0xffffffff) : 0;
231 }
232 return a->nlimbs ? (u32) (a->d[0] & 0xffffffff) : 0;
233#else
234#error Make this function work with other LIMB sizes
235#endif
236}
237
238/****************
239 * Return an allocated buffer with the MPI (msb first).
240 * NBYTES receives the length of this buffer. Caller must free the
241 * return string (This function does return a 0 byte buffer with NBYTES
242 * set to zero if the value of A is zero. If sign is not NULL, it will
243 * be set to the sign of the A.
244 */
245void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign)
246{
247 uint8_t *p, *buffer;
248 mpi_limb_t alimb;
249 int i;
250 unsigned int n;
251
252 if (sign)
253 *sign = a->sign;
254 *nbytes = n = a->nlimbs * BYTES_PER_MPI_LIMB;
255 if (!n)
256 n++; /* avoid zero length allocation */
257 p = buffer = kmalloc(n, GFP_KERNEL);
258
259 for (i = a->nlimbs - 1; i >= 0; i--) {
260 alimb = a->d[i];
261#if BYTES_PER_MPI_LIMB == 4
262 *p++ = alimb >> 24;
263 *p++ = alimb >> 16;
264 *p++ = alimb >> 8;
265 *p++ = alimb;
266#elif BYTES_PER_MPI_LIMB == 8
267 *p++ = alimb >> 56;
268 *p++ = alimb >> 48;
269 *p++ = alimb >> 40;
270 *p++ = alimb >> 32;
271 *p++ = alimb >> 24;
272 *p++ = alimb >> 16;
273 *p++ = alimb >> 8;
274 *p++ = alimb;
275#else
276#error please implement for this limb size.
277#endif
278 }
279
280 /* this is sub-optimal but we need to do the shift operation
281 * because the caller has to free the returned buffer */
282 for (p = buffer; !*p && *nbytes; p++, --*nbytes)
283 ;
284 if (p != buffer)
285 memmove(buffer, p, *nbytes);
286
287 return buffer;
288}
289EXPORT_SYMBOL_GPL(mpi_get_buffer);
290
291/****************
292 * Use BUFFER to update MPI.
293 */
294int mpi_set_buffer(MPI a, const void *xbuffer, unsigned nbytes, int sign)
295{
296 const uint8_t *buffer = xbuffer, *p;
297 mpi_limb_t alimb;
298 int nlimbs;
299 int i;
300
301 nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB;
302 if (RESIZE_IF_NEEDED(a, nlimbs) < 0)
303 return -ENOMEM;
304 a->sign = sign;
305
306 for (i = 0, p = buffer + nbytes - 1; p >= buffer + BYTES_PER_MPI_LIMB;) {
307#if BYTES_PER_MPI_LIMB == 4
308 alimb = (mpi_limb_t) *p--;
309 alimb |= (mpi_limb_t) *p-- << 8;
310 alimb |= (mpi_limb_t) *p-- << 16;
311 alimb |= (mpi_limb_t) *p-- << 24;
312#elif BYTES_PER_MPI_LIMB == 8
313 alimb = (mpi_limb_t) *p--;
314 alimb |= (mpi_limb_t) *p-- << 8;
315 alimb |= (mpi_limb_t) *p-- << 16;
316 alimb |= (mpi_limb_t) *p-- << 24;
317 alimb |= (mpi_limb_t) *p-- << 32;
318 alimb |= (mpi_limb_t) *p-- << 40;
319 alimb |= (mpi_limb_t) *p-- << 48;
320 alimb |= (mpi_limb_t) *p-- << 56;
321#else
322#error please implement for this limb size.
323#endif
324 a->d[i++] = alimb;
325 }
326 if (p >= buffer) {
327#if BYTES_PER_MPI_LIMB == 4
328 alimb = *p--;
329 if (p >= buffer)
330 alimb |= (mpi_limb_t) *p-- << 8;
331 if (p >= buffer)
332 alimb |= (mpi_limb_t) *p-- << 16;
333 if (p >= buffer)
334 alimb |= (mpi_limb_t) *p-- << 24;
335#elif BYTES_PER_MPI_LIMB == 8
336 alimb = (mpi_limb_t) *p--;
337 if (p >= buffer)
338 alimb |= (mpi_limb_t) *p-- << 8;
339 if (p >= buffer)
340 alimb |= (mpi_limb_t) *p-- << 16;
341 if (p >= buffer)
342 alimb |= (mpi_limb_t) *p-- << 24;
343 if (p >= buffer)
344 alimb |= (mpi_limb_t) *p-- << 32;
345 if (p >= buffer)
346 alimb |= (mpi_limb_t) *p-- << 40;
347 if (p >= buffer)
348 alimb |= (mpi_limb_t) *p-- << 48;
349 if (p >= buffer)
350 alimb |= (mpi_limb_t) *p-- << 56;
351#else
352#error please implement for this limb size.
353#endif
354 a->d[i++] = alimb;
355 }
356 a->nlimbs = i;
357
358 if (i != nlimbs) {
359 pr_emerg("MPI: mpi_set_buffer: Assertion failed (%d != %d)", i,
360 nlimbs);
361 BUG();
362 }
363 return 0;
364}
365EXPORT_SYMBOL_GPL(mpi_set_buffer);
diff --git a/lib/mpi/mpih-cmp.c b/lib/mpi/mpih-cmp.c
new file mode 100644
index 000000000000..b2fd39677f1b
--- /dev/null
+++ b/lib/mpi/mpih-cmp.c
@@ -0,0 +1,56 @@
1/* mpihelp-sub.c - MPI helper 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 "mpi-internal.h"
31
32/****************
33 * Compare OP1_PTR/OP1_SIZE with OP2_PTR/OP2_SIZE.
34 * There are no restrictions on the relative sizes of
35 * the two arguments.
36 * Return 1 if OP1 > OP2, 0 if they are equal, and -1 if OP1 < OP2.
37 */
38int mpihelp_cmp(mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size)
39{
40 mpi_size_t i;
41 mpi_limb_t op1_word, op2_word;
42
43 for (i = size - 1; i >= 0; i--) {
44 op1_word = op1_ptr[i];
45 op2_word = op2_ptr[i];
46 if (op1_word != op2_word)
47 goto diff;
48 }
49 return 0;
50
51diff:
52 /* This can *not* be simplified to
53 * op2_word - op2_word
54 * since that expression might give signed overflow. */
55 return (op1_word > op2_word) ? 1 : -1;
56}
diff --git a/lib/mpi/mpih-div.c b/lib/mpi/mpih-div.c
new file mode 100644
index 000000000000..87ede162dfab
--- /dev/null
+++ b/lib/mpi/mpih-div.c
@@ -0,0 +1,541 @@
1/* mpihelp-div.c - MPI helper functions
2 * Copyright (C) 1994, 1996 Free Software Foundation, Inc.
3 * Copyright (C) 1998, 1999 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#include "longlong.h"
32
33#ifndef UMUL_TIME
34#define UMUL_TIME 1
35#endif
36#ifndef UDIV_TIME
37#define UDIV_TIME UMUL_TIME
38#endif
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
194 * the NSIZE-DSIZE least significant quotient limbs at QP
195 * and the DSIZE long remainder at NP. If QEXTRA_LIMBS is
196 * non-zero, generate that many fraction bits and append them after the
197 * other quotient limbs.
198 * Return the most significant limb of the quotient, this is always 0 or 1.
199 *
200 * Preconditions:
201 * 0. NSIZE >= DSIZE.
202 * 1. The most significant bit of the divisor must be set.
203 * 2. QP must either not overlap with the input operands at all, or
204 * QP + DSIZE >= NP must hold true. (This means that it's
205 * possible to put the quotient in the high part of NUM, right after the
206 * remainder in NUM.
207 * 3. NSIZE >= DSIZE, even if QEXTRA_LIMBS is non-zero.
208 */
209
210mpi_limb_t
211mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs,
212 mpi_ptr_t np, mpi_size_t nsize, mpi_ptr_t dp, mpi_size_t dsize)
213{
214 mpi_limb_t most_significant_q_limb = 0;
215
216 switch (dsize) {
217 case 0:
218 /* We are asked to divide by zero, so go ahead and do it! (To make
219 the compiler not remove this statement, return the value.) */
220 return 1 / dsize;
221
222 case 1:
223 {
224 mpi_size_t i;
225 mpi_limb_t n1;
226 mpi_limb_t d;
227
228 d = dp[0];
229 n1 = np[nsize - 1];
230
231 if (n1 >= d) {
232 n1 -= d;
233 most_significant_q_limb = 1;
234 }
235
236 qp += qextra_limbs;
237 for (i = nsize - 2; i >= 0; i--)
238 udiv_qrnnd(qp[i], n1, n1, np[i], d);
239 qp -= qextra_limbs;
240
241 for (i = qextra_limbs - 1; i >= 0; i--)
242 udiv_qrnnd(qp[i], n1, n1, 0, d);
243
244 np[0] = n1;
245 }
246 break;
247
248 case 2:
249 {
250 mpi_size_t i;
251 mpi_limb_t n1, n0, n2;
252 mpi_limb_t d1, d0;
253
254 np += nsize - 2;
255 d1 = dp[1];
256 d0 = dp[0];
257 n1 = np[1];
258 n0 = np[0];
259
260 if (n1 >= d1 && (n1 > d1 || n0 >= d0)) {
261 sub_ddmmss(n1, n0, n1, n0, d1, d0);
262 most_significant_q_limb = 1;
263 }
264
265 for (i = qextra_limbs + nsize - 2 - 1; i >= 0; i--) {
266 mpi_limb_t q;
267 mpi_limb_t r;
268
269 if (i >= qextra_limbs)
270 np--;
271 else
272 np[0] = 0;
273
274 if (n1 == d1) {
275 /* Q should be either 111..111 or 111..110. Need special
276 * treatment of this rare case as normal division would
277 * give overflow. */
278 q = ~(mpi_limb_t) 0;
279
280 r = n0 + d1;
281 if (r < d1) { /* Carry in the addition? */
282 add_ssaaaa(n1, n0, r - d0,
283 np[0], 0, d0);
284 qp[i] = q;
285 continue;
286 }
287 n1 = d0 - (d0 != 0 ? 1 : 0);
288 n0 = -d0;
289 } else {
290 udiv_qrnnd(q, r, n1, n0, d1);
291 umul_ppmm(n1, n0, d0, q);
292 }
293
294 n2 = np[0];
295q_test:
296 if (n1 > r || (n1 == r && n0 > n2)) {
297 /* The estimated Q was too large. */
298 q--;
299 sub_ddmmss(n1, n0, n1, n0, 0, d0);
300 r += d1;
301 if (r >= d1) /* If not carry, test Q again. */
302 goto q_test;
303 }
304
305 qp[i] = q;
306 sub_ddmmss(n1, n0, r, n2, n1, n0);
307 }
308 np[1] = n1;
309 np[0] = n0;
310 }
311 break;
312
313 default:
314 {
315 mpi_size_t i;
316 mpi_limb_t dX, d1, n0;
317
318 np += nsize - dsize;
319 dX = dp[dsize - 1];
320 d1 = dp[dsize - 2];
321 n0 = np[dsize - 1];
322
323 if (n0 >= dX) {
324 if (n0 > dX
325 || mpihelp_cmp(np, dp, dsize - 1) >= 0) {
326 mpihelp_sub_n(np, np, dp, dsize);
327 n0 = np[dsize - 1];
328 most_significant_q_limb = 1;
329 }
330 }
331
332 for (i = qextra_limbs + nsize - dsize - 1; i >= 0; i--) {
333 mpi_limb_t q;
334 mpi_limb_t n1, n2;
335 mpi_limb_t cy_limb;
336
337 if (i >= qextra_limbs) {
338 np--;
339 n2 = np[dsize];
340 } else {
341 n2 = np[dsize - 1];
342 MPN_COPY_DECR(np + 1, np, dsize - 1);
343 np[0] = 0;
344 }
345
346 if (n0 == dX) {
347 /* This might over-estimate q, but it's probably not worth
348 * the extra code here to find out. */
349 q = ~(mpi_limb_t) 0;
350 } else {
351 mpi_limb_t r;
352
353 udiv_qrnnd(q, r, n0, np[dsize - 1], dX);
354 umul_ppmm(n1, n0, d1, q);
355
356 while (n1 > r
357 || (n1 == r
358 && n0 > np[dsize - 2])) {
359 q--;
360 r += dX;
361 if (r < dX) /* I.e. "carry in previous addition?" */
362 break;
363 n1 -= n0 < d1;
364 n0 -= d1;
365 }
366 }
367
368 /* Possible optimization: We already have (q * n0) and (1 * n1)
369 * after the calculation of q. Taking advantage of that, we
370 * could make this loop make two iterations less. */
371 cy_limb = mpihelp_submul_1(np, dp, dsize, q);
372
373 if (n2 != cy_limb) {
374 mpihelp_add_n(np, np, dp, dsize);
375 q--;
376 }
377
378 qp[i] = q;
379 n0 = np[dsize - 1];
380 }
381 }
382 }
383
384 return most_significant_q_limb;
385}
386
387/****************
388 * Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
389 * Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR.
390 * Return the single-limb remainder.
391 * There are no constraints on the value of the divisor.
392 *
393 * QUOT_PTR and DIVIDEND_PTR might point to the same limb.
394 */
395
396mpi_limb_t
397mpihelp_divmod_1(mpi_ptr_t quot_ptr,
398 mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
399 mpi_limb_t divisor_limb)
400{
401 mpi_size_t i;
402 mpi_limb_t n1, n0, r;
403 int dummy;
404
405 if (!dividend_size)
406 return 0;
407
408 /* If multiplication is much faster than division, and the
409 * dividend is large, pre-invert the divisor, and use
410 * only multiplications in the inner loop.
411 *
412 * This test should be read:
413 * Does it ever help to use udiv_qrnnd_preinv?
414 * && Does what we save compensate for the inversion overhead?
415 */
416 if (UDIV_TIME > (2 * UMUL_TIME + 6)
417 && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
418 int normalization_steps;
419
420 count_leading_zeros(normalization_steps, divisor_limb);
421 if (normalization_steps) {
422 mpi_limb_t divisor_limb_inverted;
423
424 divisor_limb <<= normalization_steps;
425
426 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
427 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
428 * most significant bit (with weight 2**N) implicit.
429 */
430 /* Special case for DIVISOR_LIMB == 100...000. */
431 if (!(divisor_limb << 1))
432 divisor_limb_inverted = ~(mpi_limb_t) 0;
433 else
434 udiv_qrnnd(divisor_limb_inverted, dummy,
435 -divisor_limb, 0, divisor_limb);
436
437 n1 = dividend_ptr[dividend_size - 1];
438 r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
439
440 /* Possible optimization:
441 * if (r == 0
442 * && divisor_limb > ((n1 << normalization_steps)
443 * | (dividend_ptr[dividend_size - 2] >> ...)))
444 * ...one division less...
445 */
446 for (i = dividend_size - 2; i >= 0; i--) {
447 n0 = dividend_ptr[i];
448 UDIV_QRNND_PREINV(quot_ptr[i + 1], r, r,
449 ((n1 << normalization_steps)
450 | (n0 >>
451 (BITS_PER_MPI_LIMB -
452 normalization_steps))),
453 divisor_limb,
454 divisor_limb_inverted);
455 n1 = n0;
456 }
457 UDIV_QRNND_PREINV(quot_ptr[0], r, r,
458 n1 << normalization_steps,
459 divisor_limb, divisor_limb_inverted);
460 return r >> normalization_steps;
461 } else {
462 mpi_limb_t divisor_limb_inverted;
463
464 /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB. The
465 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
466 * most significant bit (with weight 2**N) implicit.
467 */
468 /* Special case for DIVISOR_LIMB == 100...000. */
469 if (!(divisor_limb << 1))
470 divisor_limb_inverted = ~(mpi_limb_t) 0;
471 else
472 udiv_qrnnd(divisor_limb_inverted, dummy,
473 -divisor_limb, 0, divisor_limb);
474
475 i = dividend_size - 1;
476 r = dividend_ptr[i];
477
478 if (r >= divisor_limb)
479 r = 0;
480 else
481 quot_ptr[i--] = 0;
482
483 for (; i >= 0; i--) {
484 n0 = dividend_ptr[i];
485 UDIV_QRNND_PREINV(quot_ptr[i], r, r,
486 n0, divisor_limb,
487 divisor_limb_inverted);
488 }
489 return r;
490 }
491 } else {
492 if (UDIV_NEEDS_NORMALIZATION) {
493 int normalization_steps;
494
495 count_leading_zeros(normalization_steps, divisor_limb);
496 if (normalization_steps) {
497 divisor_limb <<= normalization_steps;
498
499 n1 = dividend_ptr[dividend_size - 1];
500 r = n1 >> (BITS_PER_MPI_LIMB -
501 normalization_steps);
502
503 /* Possible optimization:
504 * if (r == 0
505 * && divisor_limb > ((n1 << normalization_steps)
506 * | (dividend_ptr[dividend_size - 2] >> ...)))
507 * ...one division less...
508 */
509 for (i = dividend_size - 2; i >= 0; i--) {
510 n0 = dividend_ptr[i];
511 udiv_qrnnd(quot_ptr[i + 1], r, r,
512 ((n1 << normalization_steps)
513 | (n0 >>
514 (BITS_PER_MPI_LIMB -
515 normalization_steps))),
516 divisor_limb);
517 n1 = n0;
518 }
519 udiv_qrnnd(quot_ptr[0], r, r,
520 n1 << normalization_steps,
521 divisor_limb);
522 return r >> normalization_steps;
523 }
524 }
525 /* No normalization needed, either because udiv_qrnnd doesn't require
526 * it, or because DIVISOR_LIMB is already normalized. */
527 i = dividend_size - 1;
528 r = dividend_ptr[i];
529
530 if (r >= divisor_limb)
531 r = 0;
532 else
533 quot_ptr[i--] = 0;
534
535 for (; i >= 0; i--) {
536 n0 = dividend_ptr[i];
537 udiv_qrnnd(quot_ptr[i], r, r, n0, divisor_limb);
538 }
539 return r;
540 }
541}
diff --git a/lib/mpi/mpih-mul.c b/lib/mpi/mpih-mul.c
new file mode 100644
index 000000000000..c69c5eef233b
--- /dev/null
+++ b/lib/mpi/mpih-mul.c
@@ -0,0 +1,527 @@
1/* mpihelp-mul.c - MPI helper functions
2 * Copyright (C) 1994, 1996, 1998, 1999,
3 * 2000 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
34#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
35 do { \
36 if ((size) < KARATSUBA_THRESHOLD) \
37 mul_n_basecase(prodp, up, vp, size); \
38 else \
39 mul_n(prodp, up, vp, size, tspace); \
40 } while (0);
41
42#define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
43 do { \
44 if ((size) < KARATSUBA_THRESHOLD) \
45 mpih_sqr_n_basecase(prodp, up, size); \
46 else \
47 mpih_sqr_n(prodp, up, size, tspace); \
48 } while (0);
49
50/* Multiply the natural numbers u (pointed to by UP) and v (pointed to by VP),
51 * both with SIZE limbs, and store the result at PRODP. 2 * SIZE limbs are
52 * always stored. Return the most significant limb.
53 *
54 * Argument constraints:
55 * 1. PRODP != UP and PRODP != VP, i.e. the destination
56 * must be distinct from the multiplier and the multiplicand.
57 *
58 *
59 * Handle simple cases with traditional multiplication.
60 *
61 * This is the most critical code of multiplication. All multiplies rely
62 * on this, both small and huge. Small ones arrive here immediately. Huge
63 * ones arrive here as this is the base case for Karatsuba's recursive
64 * algorithm below.
65 */
66
67static mpi_limb_t
68mul_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
69{
70 mpi_size_t i;
71 mpi_limb_t cy;
72 mpi_limb_t v_limb;
73
74 /* Multiply by the first limb in V separately, as the result can be
75 * stored (not added) to PROD. We also avoid a loop for zeroing. */
76 v_limb = vp[0];
77 if (v_limb <= 1) {
78 if (v_limb == 1)
79 MPN_COPY(prodp, up, size);
80 else
81 MPN_ZERO(prodp, size);
82 cy = 0;
83 } else
84 cy = mpihelp_mul_1(prodp, up, size, v_limb);
85
86 prodp[size] = cy;
87 prodp++;
88
89 /* For each iteration in the outer loop, multiply one limb from
90 * U with one limb from V, and add it to PROD. */
91 for (i = 1; i < size; i++) {
92 v_limb = vp[i];
93 if (v_limb <= 1) {
94 cy = 0;
95 if (v_limb == 1)
96 cy = mpihelp_add_n(prodp, prodp, up, size);
97 } else
98 cy = mpihelp_addmul_1(prodp, up, size, v_limb);
99
100 prodp[size] = cy;
101 prodp++;
102 }
103
104 return cy;
105}
106
107static void
108mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
109 mpi_size_t size, mpi_ptr_t tspace)
110{
111 if (size & 1) {
112 /* The size is odd, and the code below doesn't handle that.
113 * Multiply the least significant (size - 1) limbs with a recursive
114 * call, and handle the most significant limb of S1 and S2
115 * separately.
116 * A slightly faster way to do this would be to make the Karatsuba
117 * code below behave as if the size were even, and let it check for
118 * odd size in the end. I.e., in essence move this code to the end.
119 * Doing so would save us a recursive call, and potentially make the
120 * stack grow a lot less.
121 */
122 mpi_size_t esize = size - 1; /* even size */
123 mpi_limb_t cy_limb;
124
125 MPN_MUL_N_RECURSE(prodp, up, vp, esize, tspace);
126 cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, vp[esize]);
127 prodp[esize + esize] = cy_limb;
128 cy_limb = mpihelp_addmul_1(prodp + esize, vp, size, up[esize]);
129 prodp[esize + size] = cy_limb;
130 } else {
131 /* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm.
132 *
133 * Split U in two pieces, U1 and U0, such that
134 * U = U0 + U1*(B**n),
135 * and V in V1 and V0, such that
136 * V = V0 + V1*(B**n).
137 *
138 * UV is then computed recursively using the identity
139 *
140 * 2n n n n
141 * UV = (B + B )U V + B (U -U )(V -V ) + (B + 1)U V
142 * 1 1 1 0 0 1 0 0
143 *
144 * Where B = 2**BITS_PER_MP_LIMB.
145 */
146 mpi_size_t hsize = size >> 1;
147 mpi_limb_t cy;
148 int negflg;
149
150 /* Product H. ________________ ________________
151 * |_____U1 x V1____||____U0 x V0_____|
152 * Put result in upper part of PROD and pass low part of TSPACE
153 * as new TSPACE.
154 */
155 MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize,
156 tspace);
157
158 /* Product M. ________________
159 * |_(U1-U0)(V0-V1)_|
160 */
161 if (mpihelp_cmp(up + hsize, up, hsize) >= 0) {
162 mpihelp_sub_n(prodp, up + hsize, up, hsize);
163 negflg = 0;
164 } else {
165 mpihelp_sub_n(prodp, up, up + hsize, hsize);
166 negflg = 1;
167 }
168 if (mpihelp_cmp(vp + hsize, vp, hsize) >= 0) {
169 mpihelp_sub_n(prodp + hsize, vp + hsize, vp, hsize);
170 negflg ^= 1;
171 } else {
172 mpihelp_sub_n(prodp + hsize, vp, vp + hsize, hsize);
173 /* No change of NEGFLG. */
174 }
175 /* Read temporary operands from low part of PROD.
176 * Put result in low part of TSPACE using upper part of TSPACE
177 * as new TSPACE.
178 */
179 MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize,
180 tspace + size);
181
182 /* Add/copy product H. */
183 MPN_COPY(prodp + hsize, prodp + size, hsize);
184 cy = mpihelp_add_n(prodp + size, prodp + size,
185 prodp + size + hsize, hsize);
186
187 /* Add product M (if NEGFLG M is a negative number) */
188 if (negflg)
189 cy -=
190 mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace,
191 size);
192 else
193 cy +=
194 mpihelp_add_n(prodp + hsize, prodp + hsize, tspace,
195 size);
196
197 /* Product L. ________________ ________________
198 * |________________||____U0 x V0_____|
199 * Read temporary operands from low part of PROD.
200 * Put result in low part of TSPACE using upper part of TSPACE
201 * as new TSPACE.
202 */
203 MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size);
204
205 /* Add/copy Product L (twice) */
206
207 cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
208 if (cy)
209 mpihelp_add_1(prodp + hsize + size,
210 prodp + hsize + size, hsize, cy);
211
212 MPN_COPY(prodp, tspace, hsize);
213 cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize,
214 hsize);
215 if (cy)
216 mpihelp_add_1(prodp + size, prodp + size, size, 1);
217 }
218}
219
220void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size)
221{
222 mpi_size_t i;
223 mpi_limb_t cy_limb;
224 mpi_limb_t v_limb;
225
226 /* Multiply by the first limb in V separately, as the result can be
227 * stored (not added) to PROD. We also avoid a loop for zeroing. */
228 v_limb = up[0];
229 if (v_limb <= 1) {
230 if (v_limb == 1)
231 MPN_COPY(prodp, up, size);
232 else
233 MPN_ZERO(prodp, size);
234 cy_limb = 0;
235 } else
236 cy_limb = mpihelp_mul_1(prodp, up, size, v_limb);
237
238 prodp[size] = cy_limb;
239 prodp++;
240
241 /* For each iteration in the outer loop, multiply one limb from
242 * U with one limb from V, and add it to PROD. */
243 for (i = 1; i < size; i++) {
244 v_limb = up[i];
245 if (v_limb <= 1) {
246 cy_limb = 0;
247 if (v_limb == 1)
248 cy_limb = mpihelp_add_n(prodp, prodp, up, size);
249 } else
250 cy_limb = mpihelp_addmul_1(prodp, up, size, v_limb);
251
252 prodp[size] = cy_limb;
253 prodp++;
254 }
255}
256
257void
258mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace)
259{
260 if (size & 1) {
261 /* The size is odd, and the code below doesn't handle that.
262 * Multiply the least significant (size - 1) limbs with a recursive
263 * call, and handle the most significant limb of S1 and S2
264 * separately.
265 * A slightly faster way to do this would be to make the Karatsuba
266 * code below behave as if the size were even, and let it check for
267 * odd size in the end. I.e., in essence move this code to the end.
268 * Doing so would save us a recursive call, and potentially make the
269 * stack grow a lot less.
270 */
271 mpi_size_t esize = size - 1; /* even size */
272 mpi_limb_t cy_limb;
273
274 MPN_SQR_N_RECURSE(prodp, up, esize, tspace);
275 cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, up[esize]);
276 prodp[esize + esize] = cy_limb;
277 cy_limb = mpihelp_addmul_1(prodp + esize, up, size, up[esize]);
278
279 prodp[esize + size] = cy_limb;
280 } else {
281 mpi_size_t hsize = size >> 1;
282 mpi_limb_t cy;
283
284 /* Product H. ________________ ________________
285 * |_____U1 x U1____||____U0 x U0_____|
286 * Put result in upper part of PROD and pass low part of TSPACE
287 * as new TSPACE.
288 */
289 MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace);
290
291 /* Product M. ________________
292 * |_(U1-U0)(U0-U1)_|
293 */
294 if (mpihelp_cmp(up + hsize, up, hsize) >= 0)
295 mpihelp_sub_n(prodp, up + hsize, up, hsize);
296 else
297 mpihelp_sub_n(prodp, up, up + hsize, hsize);
298
299 /* Read temporary operands from low part of PROD.
300 * Put result in low part of TSPACE using upper part of TSPACE
301 * as new TSPACE. */
302 MPN_SQR_N_RECURSE(tspace, prodp, hsize, tspace + size);
303
304 /* Add/copy product H */
305 MPN_COPY(prodp + hsize, prodp + size, hsize);
306 cy = mpihelp_add_n(prodp + size, prodp + size,
307 prodp + size + hsize, hsize);
308
309 /* Add product M (if NEGFLG M is a negative number). */
310 cy -= mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, size);
311
312 /* Product L. ________________ ________________
313 * |________________||____U0 x U0_____|
314 * Read temporary operands from low part of PROD.
315 * Put result in low part of TSPACE using upper part of TSPACE
316 * as new TSPACE. */
317 MPN_SQR_N_RECURSE(tspace, up, hsize, tspace + size);
318
319 /* Add/copy Product L (twice). */
320 cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
321 if (cy)
322 mpihelp_add_1(prodp + hsize + size,
323 prodp + hsize + size, hsize, cy);
324
325 MPN_COPY(prodp, tspace, hsize);
326 cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize,
327 hsize);
328 if (cy)
329 mpihelp_add_1(prodp + size, prodp + size, size, 1);
330 }
331}
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
364mpihelp_mul_karatsuba_case(mpi_ptr_t prodp,
365 mpi_ptr_t up, mpi_size_t usize,
366 mpi_ptr_t vp, mpi_size_t vsize,
367 struct karatsuba_ctx *ctx)
368{
369 mpi_limb_t cy;
370
371 if (!ctx->tspace || ctx->tspace_size < vsize) {
372 if (ctx->tspace)
373 mpi_free_limb_space(ctx->tspace);
374 ctx->tspace = mpi_alloc_limb_space(2 * vsize);
375 if (!ctx->tspace)
376 return -ENOMEM;
377 ctx->tspace_size = vsize;
378 }
379
380 MPN_MUL_N_RECURSE(prodp, up, vp, vsize, ctx->tspace);
381
382 prodp += vsize;
383 up += vsize;
384 usize -= vsize;
385 if (usize >= vsize) {
386 if (!ctx->tp || ctx->tp_size < vsize) {
387 if (ctx->tp)
388 mpi_free_limb_space(ctx->tp);
389 ctx->tp = mpi_alloc_limb_space(2 * vsize);
390 if (!ctx->tp) {
391 if (ctx->tspace)
392 mpi_free_limb_space(ctx->tspace);
393 ctx->tspace = NULL;
394 return -ENOMEM;
395 }
396 ctx->tp_size = vsize;
397 }
398
399 do {
400 MPN_MUL_N_RECURSE(ctx->tp, up, vp, vsize, ctx->tspace);
401 cy = mpihelp_add_n(prodp, prodp, ctx->tp, vsize);
402 mpihelp_add_1(prodp + vsize, ctx->tp + vsize, vsize,
403 cy);
404 prodp += vsize;
405 up += vsize;
406 usize -= vsize;
407 } while (usize >= vsize);
408 }
409
410 if (usize) {
411 if (usize < KARATSUBA_THRESHOLD) {
412 mpi_limb_t tmp;
413 if (mpihelp_mul(ctx->tspace, vp, vsize, up, usize, &tmp)
414 < 0)
415 return -ENOMEM;
416 } else {
417 if (!ctx->next) {
418 ctx->next = kzalloc(sizeof *ctx, GFP_KERNEL);
419 if (!ctx->next)
420 return -ENOMEM;
421 }
422 if (mpihelp_mul_karatsuba_case(ctx->tspace,
423 vp, vsize,
424 up, usize,
425 ctx->next) < 0)
426 return -ENOMEM;
427 }
428
429 cy = mpihelp_add_n(prodp, prodp, ctx->tspace, vsize);
430 mpihelp_add_1(prodp + vsize, ctx->tspace + vsize, usize, cy);
431 }
432
433 return 0;
434}
435
436void mpihelp_release_karatsuba_ctx(struct karatsuba_ctx *ctx)
437{
438 struct karatsuba_ctx *ctx2;
439
440 if (ctx->tp)
441 mpi_free_limb_space(ctx->tp);
442 if (ctx->tspace)
443 mpi_free_limb_space(ctx->tspace);
444 for (ctx = ctx->next; ctx; ctx = ctx2) {
445 ctx2 = ctx->next;
446 if (ctx->tp)
447 mpi_free_limb_space(ctx->tp);
448 if (ctx->tspace)
449 mpi_free_limb_space(ctx->tspace);
450 kfree(ctx);
451 }
452}
453
454/* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
455 * and v (pointed to by VP, with VSIZE limbs), and store the result at
456 * PRODP. USIZE + VSIZE limbs are always stored, but if the input
457 * operands are normalized. Return the most significant limb of the
458 * result.
459 *
460 * NOTE: The space pointed to by PRODP is overwritten before finished
461 * with U and V, so overlap is an error.
462 *
463 * Argument constraints:
464 * 1. USIZE >= VSIZE.
465 * 2. PRODP != UP and PRODP != VP, i.e. the destination
466 * must be distinct from the multiplier and the multiplicand.
467 */
468
469int
470mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
471 mpi_ptr_t vp, mpi_size_t vsize, mpi_limb_t *_result)
472{
473 mpi_ptr_t prod_endp = prodp + usize + vsize - 1;
474 mpi_limb_t cy;
475 struct karatsuba_ctx ctx;
476
477 if (vsize < KARATSUBA_THRESHOLD) {
478 mpi_size_t i;
479 mpi_limb_t v_limb;
480
481 if (!vsize) {
482 *_result = 0;
483 return 0;
484 }
485
486 /* Multiply by the first limb in V separately, as the result can be
487 * stored (not added) to PROD. We also avoid a loop for zeroing. */
488 v_limb = vp[0];
489 if (v_limb <= 1) {
490 if (v_limb == 1)
491 MPN_COPY(prodp, up, usize);
492 else
493 MPN_ZERO(prodp, usize);
494 cy = 0;
495 } else
496 cy = mpihelp_mul_1(prodp, up, usize, v_limb);
497
498 prodp[usize] = cy;
499 prodp++;
500
501 /* For each iteration in the outer loop, multiply one limb from
502 * U with one limb from V, and add it to PROD. */
503 for (i = 1; i < vsize; i++) {
504 v_limb = vp[i];
505 if (v_limb <= 1) {
506 cy = 0;
507 if (v_limb == 1)
508 cy = mpihelp_add_n(prodp, prodp, up,
509 usize);
510 } else
511 cy = mpihelp_addmul_1(prodp, up, usize, v_limb);
512
513 prodp[usize] = cy;
514 prodp++;
515 }
516
517 *_result = cy;
518 return 0;
519 }
520
521 memset(&ctx, 0, sizeof ctx);
522 if (mpihelp_mul_karatsuba_case(prodp, up, usize, vp, vsize, &ctx) < 0)
523 return -ENOMEM;
524 mpihelp_release_karatsuba_ctx(&ctx);
525 *_result = *prod_endp;
526 return 0;
527}
diff --git a/lib/mpi/mpiutil.c b/lib/mpi/mpiutil.c
new file mode 100644
index 000000000000..eefc55d6b7f5
--- /dev/null
+++ b/lib/mpi/mpiutil.c
@@ -0,0 +1,208 @@
1/* mpiutil.ac - Utility functions for MPI
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
23/****************
24 * Note: It was a bad idea to use the number of limbs to allocate
25 * because on a alpha the limbs are large but we normally need
26 * integers of n bits - So we should chnage this to bits (or bytes).
27 *
28 * But mpi_alloc is used in a lot of places :-)
29 */
30MPI mpi_alloc(unsigned nlimbs)
31{
32 MPI a;
33
34 a = kmalloc(sizeof *a, GFP_KERNEL);
35 if (!a)
36 return a;
37
38 if (nlimbs) {
39 a->d = mpi_alloc_limb_space(nlimbs);
40 if (!a->d) {
41 kfree(a);
42 return NULL;
43 }
44 } else {
45 a->d = NULL;
46 }
47
48 a->alloced = nlimbs;
49 a->nlimbs = 0;
50 a->sign = 0;
51 a->flags = 0;
52 a->nbits = 0;
53 return a;
54}
55EXPORT_SYMBOL_GPL(mpi_alloc);
56
57mpi_ptr_t mpi_alloc_limb_space(unsigned nlimbs)
58{
59 size_t len = nlimbs * sizeof(mpi_limb_t);
60
61 return kmalloc(len, GFP_KERNEL);
62}
63
64void mpi_free_limb_space(mpi_ptr_t a)
65{
66 if (!a)
67 return;
68
69 kfree(a);
70}
71
72void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs)
73{
74 mpi_free_limb_space(a->d);
75 a->d = ap;
76 a->alloced = nlimbs;
77}
78
79/****************
80 * Resize the array of A to NLIMBS. the additional space is cleared
81 * (set to 0) [done by m_realloc()]
82 */
83int mpi_resize(MPI a, unsigned nlimbs)
84{
85 void *p;
86
87 if (nlimbs <= a->alloced)
88 return 0; /* no need to do it */
89
90 if (a->d) {
91 p = kmalloc(nlimbs * sizeof(mpi_limb_t), GFP_KERNEL);
92 if (!p)
93 return -ENOMEM;
94 memcpy(p, a->d, a->alloced * sizeof(mpi_limb_t));
95 kfree(a->d);
96 a->d = p;
97 } else {
98 a->d = kzalloc(nlimbs * sizeof(mpi_limb_t), GFP_KERNEL);
99 if (!a->d)
100 return -ENOMEM;
101 }
102 a->alloced = nlimbs;
103 return 0;
104}
105
106void mpi_clear(MPI a)
107{
108 a->nlimbs = 0;
109 a->nbits = 0;
110 a->flags = 0;
111}
112
113void mpi_free(MPI a)
114{
115 if (!a)
116 return;
117
118 if (a->flags & 4)
119 kfree(a->d);
120 else
121 mpi_free_limb_space(a->d);
122
123 if (a->flags & ~7)
124 pr_info("invalid flag value in mpi\n");
125 kfree(a);
126}
127EXPORT_SYMBOL_GPL(mpi_free);
128
129/****************
130 * Note: This copy function should not interpret the MPI
131 * but copy it transparently.
132 */
133int mpi_copy(MPI *copied, const MPI a)
134{
135 size_t i;
136 MPI b;
137
138 *copied = MPI_NULL;
139
140 if (a) {
141 b = mpi_alloc(a->nlimbs);
142 if (!b)
143 return -ENOMEM;
144
145 b->nlimbs = a->nlimbs;
146 b->sign = a->sign;
147 b->flags = a->flags;
148 b->nbits = a->nbits;
149
150 for (i = 0; i < b->nlimbs; i++)
151 b->d[i] = a->d[i];
152
153 *copied = b;
154 }
155
156 return 0;
157}
158
159int mpi_set(MPI w, const MPI u)
160{
161 mpi_ptr_t wp, up;
162 mpi_size_t usize = u->nlimbs;
163 int usign = u->sign;
164
165 if (RESIZE_IF_NEEDED(w, (size_t) usize) < 0)
166 return -ENOMEM;
167
168 wp = w->d;
169 up = u->d;
170 MPN_COPY(wp, up, usize);
171 w->nlimbs = usize;
172 w->nbits = u->nbits;
173 w->flags = u->flags;
174 w->sign = usign;
175 return 0;
176}
177
178int mpi_set_ui(MPI w, unsigned long u)
179{
180 if (RESIZE_IF_NEEDED(w, 1) < 0)
181 return -ENOMEM;
182 w->d[0] = u;
183 w->nlimbs = u ? 1 : 0;
184 w->sign = 0;
185 w->nbits = 0;
186 w->flags = 0;
187 return 0;
188}
189
190MPI mpi_alloc_set_ui(unsigned long u)
191{
192 MPI w = mpi_alloc(1);
193 if (!w)
194 return w;
195 w->d[0] = u;
196 w->nlimbs = u ? 1 : 0;
197 w->sign = 0;
198 return w;
199}
200
201void mpi_swap(MPI a, MPI b)
202{
203 struct gcry_mpi tmp;
204
205 tmp = *a;
206 *a = *b;
207 *b = tmp;
208}
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-24 07:41:39 -0500