xref: /illumos-gate/usr/src/common/mpi/mpi.c (revision 6a634c9d)
1*f2ba9e96SDina K Nimeh /* BEGIN CSTYLED */
2f9fbec18Smcpowers /*
3f9fbec18Smcpowers  *  mpi.c
4f9fbec18Smcpowers  *
5f9fbec18Smcpowers  *  Arbitrary precision integer arithmetic library
6f9fbec18Smcpowers  *
7f9fbec18Smcpowers  * ***** BEGIN LICENSE BLOCK *****
8f9fbec18Smcpowers  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
9f9fbec18Smcpowers  *
10f9fbec18Smcpowers  * The contents of this file are subject to the Mozilla Public License Version
11f9fbec18Smcpowers  * 1.1 (the "License"); you may not use this file except in compliance with
12f9fbec18Smcpowers  * the License. You may obtain a copy of the License at
13f9fbec18Smcpowers  * http://www.mozilla.org/MPL/
14f9fbec18Smcpowers  *
15f9fbec18Smcpowers  * Software distributed under the License is distributed on an "AS IS" basis,
16f9fbec18Smcpowers  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
17f9fbec18Smcpowers  * for the specific language governing rights and limitations under the
18f9fbec18Smcpowers  * License.
19f9fbec18Smcpowers  *
20f9fbec18Smcpowers  * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.
21f9fbec18Smcpowers  *
22f9fbec18Smcpowers  * The Initial Developer of the Original Code is
23f9fbec18Smcpowers  * Michael J. Fromberger.
24f9fbec18Smcpowers  * Portions created by the Initial Developer are Copyright (C) 1998
25f9fbec18Smcpowers  * the Initial Developer. All Rights Reserved.
26f9fbec18Smcpowers  *
27f9fbec18Smcpowers  * Contributor(s):
28f9fbec18Smcpowers  *   Netscape Communications Corporation
29f9fbec18Smcpowers  *   Douglas Stebila <douglas@stebila.ca> of Sun Laboratories.
30f9fbec18Smcpowers  *
31f9fbec18Smcpowers  * Alternatively, the contents of this file may be used under the terms of
32f9fbec18Smcpowers  * either the GNU General Public License Version 2 or later (the "GPL"), or
33f9fbec18Smcpowers  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
34f9fbec18Smcpowers  * in which case the provisions of the GPL or the LGPL are applicable instead
35f9fbec18Smcpowers  * of those above. If you wish to allow use of your version of this file only
36f9fbec18Smcpowers  * under the terms of either the GPL or the LGPL, and not to allow others to
37f9fbec18Smcpowers  * use your version of this file under the terms of the MPL, indicate your
38f9fbec18Smcpowers  * decision by deleting the provisions above and replace them with the notice
39f9fbec18Smcpowers  * and other provisions required by the GPL or the LGPL. If you do not delete
40f9fbec18Smcpowers  * the provisions above, a recipient may use your version of this file under
41f9fbec18Smcpowers  * the terms of any one of the MPL, the GPL or the LGPL.
42f9fbec18Smcpowers  *
43f9fbec18Smcpowers  * ***** END LICENSE BLOCK ***** */
44f9fbec18Smcpowers /*
45*f2ba9e96SDina K Nimeh  * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
46f9fbec18Smcpowers  *
47f9fbec18Smcpowers  * Sun elects to use this software under the MPL license.
48f9fbec18Smcpowers  */
49f9fbec18Smcpowers 
50f9fbec18Smcpowers /* $Id: mpi.c,v 1.45 2006/09/29 20:12:21 alexei.volkov.bugs%sun.com Exp $ */
51f9fbec18Smcpowers 
52f9fbec18Smcpowers #include "mpi-priv.h"
53f9fbec18Smcpowers #if defined(OSF1)
54f9fbec18Smcpowers #include <c_asm.h>
55f9fbec18Smcpowers #endif
56f9fbec18Smcpowers 
57f9fbec18Smcpowers #if MP_LOGTAB
58f9fbec18Smcpowers /*
59f9fbec18Smcpowers   A table of the logs of 2 for various bases (the 0 and 1 entries of
60f9fbec18Smcpowers   this table are meaningless and should not be referenced).
61f9fbec18Smcpowers 
62f9fbec18Smcpowers   This table is used to compute output lengths for the mp_toradix()
63f9fbec18Smcpowers   function.  Since a number n in radix r takes up about log_r(n)
64f9fbec18Smcpowers   digits, we estimate the output size by taking the least integer
65f9fbec18Smcpowers   greater than log_r(n), where:
66f9fbec18Smcpowers 
67f9fbec18Smcpowers   log_r(n) = log_2(n) * log_r(2)
68f9fbec18Smcpowers 
69f9fbec18Smcpowers   This table, therefore, is a table of log_r(2) for 2 <= r <= 36,
70f9fbec18Smcpowers   which are the output bases supported.
71f9fbec18Smcpowers  */
72f9fbec18Smcpowers #include "logtab.h"
73f9fbec18Smcpowers #endif
74f9fbec18Smcpowers 
75f9fbec18Smcpowers /* {{{ Constant strings */
76f9fbec18Smcpowers 
77f9fbec18Smcpowers /* Constant strings returned by mp_strerror() */
78f9fbec18Smcpowers static const char *mp_err_string[] = {
79f9fbec18Smcpowers   "unknown result code",     /* say what?            */
80f9fbec18Smcpowers   "boolean true",            /* MP_OKAY, MP_YES      */
81f9fbec18Smcpowers   "boolean false",           /* MP_NO                */
82f9fbec18Smcpowers   "out of memory",           /* MP_MEM               */
83f9fbec18Smcpowers   "argument out of range",   /* MP_RANGE             */
84f9fbec18Smcpowers   "invalid input parameter", /* MP_BADARG            */
85f9fbec18Smcpowers   "result is undefined"      /* MP_UNDEF             */
86f9fbec18Smcpowers };
87f9fbec18Smcpowers 
88f9fbec18Smcpowers /* Value to digit maps for radix conversion   */
89f9fbec18Smcpowers 
90f9fbec18Smcpowers /* s_dmap_1 - standard digits and letters */
91f9fbec18Smcpowers static const char *s_dmap_1 =
92f9fbec18Smcpowers   "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
93f9fbec18Smcpowers 
94f9fbec18Smcpowers /* }}} */
95f9fbec18Smcpowers 
96f9fbec18Smcpowers unsigned long mp_allocs;
97f9fbec18Smcpowers unsigned long mp_frees;
98f9fbec18Smcpowers unsigned long mp_copies;
99f9fbec18Smcpowers 
100f9fbec18Smcpowers /* {{{ Default precision manipulation */
101f9fbec18Smcpowers 
102f9fbec18Smcpowers /* Default precision for newly created mp_int's      */
103f9fbec18Smcpowers static mp_size s_mp_defprec = MP_DEFPREC;
104f9fbec18Smcpowers 
mp_get_prec(void)105f9fbec18Smcpowers mp_size mp_get_prec(void)
106f9fbec18Smcpowers {
107f9fbec18Smcpowers   return s_mp_defprec;
108f9fbec18Smcpowers 
109f9fbec18Smcpowers } /* end mp_get_prec() */
110f9fbec18Smcpowers 
mp_set_prec(mp_size prec)111f9fbec18Smcpowers void         mp_set_prec(mp_size prec)
112f9fbec18Smcpowers {
113f9fbec18Smcpowers   if(prec == 0)
114f9fbec18Smcpowers     s_mp_defprec = MP_DEFPREC;
115f9fbec18Smcpowers   else
116f9fbec18Smcpowers     s_mp_defprec = prec;
117f9fbec18Smcpowers 
118f9fbec18Smcpowers } /* end mp_set_prec() */
119f9fbec18Smcpowers 
120f9fbec18Smcpowers /* }}} */
121f9fbec18Smcpowers 
122f9fbec18Smcpowers /*------------------------------------------------------------------------*/
123f9fbec18Smcpowers /* {{{ mp_init(mp, kmflag) */
124f9fbec18Smcpowers 
125f9fbec18Smcpowers /*
126f9fbec18Smcpowers   mp_init(mp, kmflag)
127f9fbec18Smcpowers 
128f9fbec18Smcpowers   Initialize a new zero-valued mp_int.  Returns MP_OKAY if successful,
129f9fbec18Smcpowers   MP_MEM if memory could not be allocated for the structure.
130f9fbec18Smcpowers  */
131f9fbec18Smcpowers 
mp_init(mp_int * mp,int kmflag)132f9fbec18Smcpowers mp_err mp_init(mp_int *mp, int kmflag)
133f9fbec18Smcpowers {
134f9fbec18Smcpowers   return mp_init_size(mp, s_mp_defprec, kmflag);
135f9fbec18Smcpowers 
136f9fbec18Smcpowers } /* end mp_init() */
137f9fbec18Smcpowers 
138f9fbec18Smcpowers /* }}} */
139f9fbec18Smcpowers 
140f9fbec18Smcpowers /* {{{ mp_init_size(mp, prec, kmflag) */
141f9fbec18Smcpowers 
142f9fbec18Smcpowers /*
143f9fbec18Smcpowers   mp_init_size(mp, prec, kmflag)
144f9fbec18Smcpowers 
145f9fbec18Smcpowers   Initialize a new zero-valued mp_int with at least the given
146f9fbec18Smcpowers   precision; returns MP_OKAY if successful, or MP_MEM if memory could
147f9fbec18Smcpowers   not be allocated for the structure.
148f9fbec18Smcpowers  */
149f9fbec18Smcpowers 
mp_init_size(mp_int * mp,mp_size prec,int kmflag)150f9fbec18Smcpowers mp_err mp_init_size(mp_int *mp, mp_size prec, int kmflag)
151f9fbec18Smcpowers {
152f9fbec18Smcpowers   ARGCHK(mp != NULL && prec > 0, MP_BADARG);
153f9fbec18Smcpowers 
154f9fbec18Smcpowers   prec = MP_ROUNDUP(prec, s_mp_defprec);
155f9fbec18Smcpowers   if((DIGITS(mp) = s_mp_alloc(prec, sizeof(mp_digit), kmflag)) == NULL)
156f9fbec18Smcpowers     return MP_MEM;
157f9fbec18Smcpowers 
158f9fbec18Smcpowers   SIGN(mp) = ZPOS;
159f9fbec18Smcpowers   USED(mp) = 1;
160f9fbec18Smcpowers   ALLOC(mp) = prec;
161*f2ba9e96SDina K Nimeh   FLAG(mp) = kmflag;
162f9fbec18Smcpowers 
163f9fbec18Smcpowers   return MP_OKAY;
164f9fbec18Smcpowers 
165f9fbec18Smcpowers } /* end mp_init_size() */
166f9fbec18Smcpowers 
167f9fbec18Smcpowers /* }}} */
168f9fbec18Smcpowers 
169f9fbec18Smcpowers /* {{{ mp_init_copy(mp, from) */
170f9fbec18Smcpowers 
171f9fbec18Smcpowers /*
172f9fbec18Smcpowers   mp_init_copy(mp, from)
173f9fbec18Smcpowers 
174f9fbec18Smcpowers   Initialize mp as an exact copy of from.  Returns MP_OKAY if
175f9fbec18Smcpowers   successful, MP_MEM if memory could not be allocated for the new
176f9fbec18Smcpowers   structure.
177f9fbec18Smcpowers  */
178f9fbec18Smcpowers 
mp_init_copy(mp_int * mp,const mp_int * from)179f9fbec18Smcpowers mp_err mp_init_copy(mp_int *mp, const mp_int *from)
180f9fbec18Smcpowers {
181f9fbec18Smcpowers   ARGCHK(mp != NULL && from != NULL, MP_BADARG);
182f9fbec18Smcpowers 
183f9fbec18Smcpowers   if(mp == from)
184f9fbec18Smcpowers     return MP_OKAY;
185f9fbec18Smcpowers 
186f9fbec18Smcpowers   if((DIGITS(mp) = s_mp_alloc(ALLOC(from), sizeof(mp_digit), FLAG(from))) == NULL)
187f9fbec18Smcpowers     return MP_MEM;
188f9fbec18Smcpowers 
189f9fbec18Smcpowers   s_mp_copy(DIGITS(from), DIGITS(mp), USED(from));
190f9fbec18Smcpowers   USED(mp) = USED(from);
191f9fbec18Smcpowers   ALLOC(mp) = ALLOC(from);
192f9fbec18Smcpowers   SIGN(mp) = SIGN(from);
193f9fbec18Smcpowers   FLAG(mp) = FLAG(from);
194f9fbec18Smcpowers 
195f9fbec18Smcpowers   return MP_OKAY;
196f9fbec18Smcpowers 
197f9fbec18Smcpowers } /* end mp_init_copy() */
198f9fbec18Smcpowers 
199f9fbec18Smcpowers /* }}} */
200f9fbec18Smcpowers 
201f9fbec18Smcpowers /* {{{ mp_copy(from, to) */
202f9fbec18Smcpowers 
203f9fbec18Smcpowers /*
204f9fbec18Smcpowers   mp_copy(from, to)
205f9fbec18Smcpowers 
206f9fbec18Smcpowers   Copies the mp_int 'from' to the mp_int 'to'.  It is presumed that
207f9fbec18Smcpowers   'to' has already been initialized (if not, use mp_init_copy()
208f9fbec18Smcpowers   instead). If 'from' and 'to' are identical, nothing happens.
209f9fbec18Smcpowers  */
210f9fbec18Smcpowers 
mp_copy(const mp_int * from,mp_int * to)211f9fbec18Smcpowers mp_err mp_copy(const mp_int *from, mp_int *to)
212f9fbec18Smcpowers {
213f9fbec18Smcpowers   ARGCHK(from != NULL && to != NULL, MP_BADARG);
214f9fbec18Smcpowers 
215f9fbec18Smcpowers   if(from == to)
216f9fbec18Smcpowers     return MP_OKAY;
217f9fbec18Smcpowers 
218f9fbec18Smcpowers   ++mp_copies;
219f9fbec18Smcpowers   { /* copy */
220f9fbec18Smcpowers     mp_digit   *tmp;
221f9fbec18Smcpowers 
222f9fbec18Smcpowers     /*
223f9fbec18Smcpowers       If the allocated buffer in 'to' already has enough space to hold
224f9fbec18Smcpowers       all the used digits of 'from', we'll re-use it to avoid hitting
225f9fbec18Smcpowers       the memory allocater more than necessary; otherwise, we'd have
226f9fbec18Smcpowers       to grow anyway, so we just allocate a hunk and make the copy as
227f9fbec18Smcpowers       usual
228f9fbec18Smcpowers      */
229f9fbec18Smcpowers     if(ALLOC(to) >= USED(from)) {
230f9fbec18Smcpowers       s_mp_setz(DIGITS(to) + USED(from), ALLOC(to) - USED(from));
231f9fbec18Smcpowers       s_mp_copy(DIGITS(from), DIGITS(to), USED(from));
232f9fbec18Smcpowers 
233f9fbec18Smcpowers     } else {
234f9fbec18Smcpowers       if((tmp = s_mp_alloc(ALLOC(from), sizeof(mp_digit), FLAG(from))) == NULL)
235f9fbec18Smcpowers 	return MP_MEM;
236f9fbec18Smcpowers 
237f9fbec18Smcpowers       s_mp_copy(DIGITS(from), tmp, USED(from));
238f9fbec18Smcpowers 
239f9fbec18Smcpowers       if(DIGITS(to) != NULL) {
240f9fbec18Smcpowers #if MP_CRYPTO
241f9fbec18Smcpowers 	s_mp_setz(DIGITS(to), ALLOC(to));
242f9fbec18Smcpowers #endif
243f9fbec18Smcpowers 	s_mp_free(DIGITS(to), ALLOC(to));
244f9fbec18Smcpowers       }
245f9fbec18Smcpowers 
246f9fbec18Smcpowers       DIGITS(to) = tmp;
247f9fbec18Smcpowers       ALLOC(to) = ALLOC(from);
248f9fbec18Smcpowers     }
249f9fbec18Smcpowers 
250f9fbec18Smcpowers     /* Copy the precision and sign from the original */
251f9fbec18Smcpowers     USED(to) = USED(from);
252f9fbec18Smcpowers     SIGN(to) = SIGN(from);
253*f2ba9e96SDina K Nimeh     FLAG(to) = FLAG(from);
254f9fbec18Smcpowers   } /* end copy */
255f9fbec18Smcpowers 
256f9fbec18Smcpowers   return MP_OKAY;
257f9fbec18Smcpowers 
258f9fbec18Smcpowers } /* end mp_copy() */
259f9fbec18Smcpowers 
260f9fbec18Smcpowers /* }}} */
261f9fbec18Smcpowers 
262f9fbec18Smcpowers /* {{{ mp_exch(mp1, mp2) */
263f9fbec18Smcpowers 
264f9fbec18Smcpowers /*
265f9fbec18Smcpowers   mp_exch(mp1, mp2)
266f9fbec18Smcpowers 
267f9fbec18Smcpowers   Exchange mp1 and mp2 without allocating any intermediate memory
268f9fbec18Smcpowers   (well, unless you count the stack space needed for this call and the
269f9fbec18Smcpowers   locals it creates...).  This cannot fail.
270f9fbec18Smcpowers  */
271f9fbec18Smcpowers 
mp_exch(mp_int * mp1,mp_int * mp2)272f9fbec18Smcpowers void mp_exch(mp_int *mp1, mp_int *mp2)
273f9fbec18Smcpowers {
274f9fbec18Smcpowers #if MP_ARGCHK == 2
275f9fbec18Smcpowers   assert(mp1 != NULL && mp2 != NULL);
276f9fbec18Smcpowers #else
277f9fbec18Smcpowers   if(mp1 == NULL || mp2 == NULL)
278f9fbec18Smcpowers     return;
279f9fbec18Smcpowers #endif
280f9fbec18Smcpowers 
281f9fbec18Smcpowers   s_mp_exch(mp1, mp2);
282f9fbec18Smcpowers 
283f9fbec18Smcpowers } /* end mp_exch() */
284f9fbec18Smcpowers 
285f9fbec18Smcpowers /* }}} */
286f9fbec18Smcpowers 
287f9fbec18Smcpowers /* {{{ mp_clear(mp) */
288f9fbec18Smcpowers 
289f9fbec18Smcpowers /*
290f9fbec18Smcpowers   mp_clear(mp)
291f9fbec18Smcpowers 
292f9fbec18Smcpowers   Release the storage used by an mp_int, and void its fields so that
293f9fbec18Smcpowers   if someone calls mp_clear() again for the same int later, we won't
294f9fbec18Smcpowers   get tollchocked.
295f9fbec18Smcpowers  */
296f9fbec18Smcpowers 
mp_clear(mp_int * mp)297f9fbec18Smcpowers void   mp_clear(mp_int *mp)
298f9fbec18Smcpowers {
299f9fbec18Smcpowers   if(mp == NULL)
300f9fbec18Smcpowers     return;
301f9fbec18Smcpowers 
302f9fbec18Smcpowers   if(DIGITS(mp) != NULL) {
303f9fbec18Smcpowers #if MP_CRYPTO
304f9fbec18Smcpowers     s_mp_setz(DIGITS(mp), ALLOC(mp));
305f9fbec18Smcpowers #endif
306f9fbec18Smcpowers     s_mp_free(DIGITS(mp), ALLOC(mp));
307f9fbec18Smcpowers     DIGITS(mp) = NULL;
308f9fbec18Smcpowers   }
309f9fbec18Smcpowers 
310f9fbec18Smcpowers   USED(mp) = 0;
311f9fbec18Smcpowers   ALLOC(mp) = 0;
312f9fbec18Smcpowers 
313f9fbec18Smcpowers } /* end mp_clear() */
314f9fbec18Smcpowers 
315f9fbec18Smcpowers /* }}} */
316f9fbec18Smcpowers 
317f9fbec18Smcpowers /* {{{ mp_zero(mp) */
318f9fbec18Smcpowers 
319f9fbec18Smcpowers /*
320f9fbec18Smcpowers   mp_zero(mp)
321f9fbec18Smcpowers 
322f9fbec18Smcpowers   Set mp to zero.  Does not change the allocated size of the structure,
323f9fbec18Smcpowers   and therefore cannot fail (except on a bad argument, which we ignore)
324f9fbec18Smcpowers  */
mp_zero(mp_int * mp)325f9fbec18Smcpowers void   mp_zero(mp_int *mp)
326f9fbec18Smcpowers {
327f9fbec18Smcpowers   if(mp == NULL)
328f9fbec18Smcpowers     return;
329f9fbec18Smcpowers 
330f9fbec18Smcpowers   s_mp_setz(DIGITS(mp), ALLOC(mp));
331f9fbec18Smcpowers   USED(mp) = 1;
332f9fbec18Smcpowers   SIGN(mp) = ZPOS;
333f9fbec18Smcpowers 
334f9fbec18Smcpowers } /* end mp_zero() */
335f9fbec18Smcpowers 
336f9fbec18Smcpowers /* }}} */
337f9fbec18Smcpowers 
338f9fbec18Smcpowers /* {{{ mp_set(mp, d) */
339f9fbec18Smcpowers 
mp_set(mp_int * mp,mp_digit d)340f9fbec18Smcpowers void   mp_set(mp_int *mp, mp_digit d)
341f9fbec18Smcpowers {
342f9fbec18Smcpowers   if(mp == NULL)
343f9fbec18Smcpowers     return;
344f9fbec18Smcpowers 
345f9fbec18Smcpowers   mp_zero(mp);
346f9fbec18Smcpowers   DIGIT(mp, 0) = d;
347f9fbec18Smcpowers 
348f9fbec18Smcpowers } /* end mp_set() */
349f9fbec18Smcpowers 
350f9fbec18Smcpowers /* }}} */
351f9fbec18Smcpowers 
352f9fbec18Smcpowers /* {{{ mp_set_int(mp, z) */
353f9fbec18Smcpowers 
mp_set_int(mp_int * mp,long z)354f9fbec18Smcpowers mp_err mp_set_int(mp_int *mp, long z)
355f9fbec18Smcpowers {
356f9fbec18Smcpowers   int            ix;
357f9fbec18Smcpowers   unsigned long  v = labs(z);
358f9fbec18Smcpowers   mp_err         res;
359f9fbec18Smcpowers 
360f9fbec18Smcpowers   ARGCHK(mp != NULL, MP_BADARG);
361f9fbec18Smcpowers 
362f9fbec18Smcpowers   mp_zero(mp);
363f9fbec18Smcpowers   if(z == 0)
364f9fbec18Smcpowers     return MP_OKAY;  /* shortcut for zero */
365f9fbec18Smcpowers 
366f9fbec18Smcpowers   if (sizeof v <= sizeof(mp_digit)) {
367f9fbec18Smcpowers     DIGIT(mp,0) = v;
368f9fbec18Smcpowers   } else {
369f9fbec18Smcpowers     for (ix = sizeof(long) - 1; ix >= 0; ix--) {
370f9fbec18Smcpowers       if ((res = s_mp_mul_d(mp, (UCHAR_MAX + 1))) != MP_OKAY)
371f9fbec18Smcpowers 	return res;
372f9fbec18Smcpowers 
373f9fbec18Smcpowers       res = s_mp_add_d(mp, (mp_digit)((v >> (ix * CHAR_BIT)) & UCHAR_MAX));
374f9fbec18Smcpowers       if (res != MP_OKAY)
375f9fbec18Smcpowers 	return res;
376f9fbec18Smcpowers     }
377f9fbec18Smcpowers   }
378f9fbec18Smcpowers   if(z < 0)
379f9fbec18Smcpowers     SIGN(mp) = NEG;
380f9fbec18Smcpowers 
381f9fbec18Smcpowers   return MP_OKAY;
382f9fbec18Smcpowers 
383f9fbec18Smcpowers } /* end mp_set_int() */
384f9fbec18Smcpowers 
385f9fbec18Smcpowers /* }}} */
386f9fbec18Smcpowers 
387f9fbec18Smcpowers /* {{{ mp_set_ulong(mp, z) */
388f9fbec18Smcpowers 
mp_set_ulong(mp_int * mp,unsigned long z)389f9fbec18Smcpowers mp_err mp_set_ulong(mp_int *mp, unsigned long z)
390f9fbec18Smcpowers {
391f9fbec18Smcpowers   int            ix;
392f9fbec18Smcpowers   mp_err         res;
393f9fbec18Smcpowers 
394f9fbec18Smcpowers   ARGCHK(mp != NULL, MP_BADARG);
395f9fbec18Smcpowers 
396f9fbec18Smcpowers   mp_zero(mp);
397f9fbec18Smcpowers   if(z == 0)
398f9fbec18Smcpowers     return MP_OKAY;  /* shortcut for zero */
399f9fbec18Smcpowers 
400f9fbec18Smcpowers   if (sizeof z <= sizeof(mp_digit)) {
401f9fbec18Smcpowers     DIGIT(mp,0) = z;
402f9fbec18Smcpowers   } else {
403f9fbec18Smcpowers     for (ix = sizeof(long) - 1; ix >= 0; ix--) {
404f9fbec18Smcpowers       if ((res = s_mp_mul_d(mp, (UCHAR_MAX + 1))) != MP_OKAY)
405f9fbec18Smcpowers 	return res;
406f9fbec18Smcpowers 
407f9fbec18Smcpowers       res = s_mp_add_d(mp, (mp_digit)((z >> (ix * CHAR_BIT)) & UCHAR_MAX));
408f9fbec18Smcpowers       if (res != MP_OKAY)
409f9fbec18Smcpowers 	return res;
410f9fbec18Smcpowers     }
411f9fbec18Smcpowers   }
412f9fbec18Smcpowers   return MP_OKAY;
413f9fbec18Smcpowers } /* end mp_set_ulong() */
414f9fbec18Smcpowers 
415f9fbec18Smcpowers /* }}} */
416f9fbec18Smcpowers 
417f9fbec18Smcpowers /*------------------------------------------------------------------------*/
418f9fbec18Smcpowers /* {{{ Digit arithmetic */
419f9fbec18Smcpowers 
420f9fbec18Smcpowers /* {{{ mp_add_d(a, d, b) */
421f9fbec18Smcpowers 
422f9fbec18Smcpowers /*
423f9fbec18Smcpowers   mp_add_d(a, d, b)
424f9fbec18Smcpowers 
425f9fbec18Smcpowers   Compute the sum b = a + d, for a single digit d.  Respects the sign of
426f9fbec18Smcpowers   its primary addend (single digits are unsigned anyway).
427f9fbec18Smcpowers  */
428f9fbec18Smcpowers 
mp_add_d(const mp_int * a,mp_digit d,mp_int * b)429f9fbec18Smcpowers mp_err mp_add_d(const mp_int *a, mp_digit d, mp_int *b)
430f9fbec18Smcpowers {
431f9fbec18Smcpowers   mp_int   tmp;
432f9fbec18Smcpowers   mp_err   res;
433f9fbec18Smcpowers 
434f9fbec18Smcpowers   ARGCHK(a != NULL && b != NULL, MP_BADARG);
435f9fbec18Smcpowers 
436f9fbec18Smcpowers   if((res = mp_init_copy(&tmp, a)) != MP_OKAY)
437f9fbec18Smcpowers     return res;
438f9fbec18Smcpowers 
439f9fbec18Smcpowers   if(SIGN(&tmp) == ZPOS) {
440f9fbec18Smcpowers     if((res = s_mp_add_d(&tmp, d)) != MP_OKAY)
441f9fbec18Smcpowers       goto CLEANUP;
442f9fbec18Smcpowers   } else if(s_mp_cmp_d(&tmp, d) >= 0) {
443f9fbec18Smcpowers     if((res = s_mp_sub_d(&tmp, d)) != MP_OKAY)
444f9fbec18Smcpowers       goto CLEANUP;
445f9fbec18Smcpowers   } else {
446f9fbec18Smcpowers     mp_neg(&tmp, &tmp);
447f9fbec18Smcpowers 
448f9fbec18Smcpowers     DIGIT(&tmp, 0) = d - DIGIT(&tmp, 0);
449f9fbec18Smcpowers   }
450f9fbec18Smcpowers 
451f9fbec18Smcpowers   if(s_mp_cmp_d(&tmp, 0) == 0)
452f9fbec18Smcpowers     SIGN(&tmp) = ZPOS;
453f9fbec18Smcpowers 
454f9fbec18Smcpowers   s_mp_exch(&tmp, b);
455f9fbec18Smcpowers 
456f9fbec18Smcpowers CLEANUP:
457f9fbec18Smcpowers   mp_clear(&tmp);
458f9fbec18Smcpowers   return res;
459f9fbec18Smcpowers 
460f9fbec18Smcpowers } /* end mp_add_d() */
461f9fbec18Smcpowers 
462f9fbec18Smcpowers /* }}} */
463f9fbec18Smcpowers 
464f9fbec18Smcpowers /* {{{ mp_sub_d(a, d, b) */
465f9fbec18Smcpowers 
466f9fbec18Smcpowers /*
467f9fbec18Smcpowers   mp_sub_d(a, d, b)
468f9fbec18Smcpowers 
469f9fbec18Smcpowers   Compute the difference b = a - d, for a single digit d.  Respects the
470f9fbec18Smcpowers   sign of its subtrahend (single digits are unsigned anyway).
471f9fbec18Smcpowers  */
472f9fbec18Smcpowers 
mp_sub_d(const mp_int * a,mp_digit d,mp_int * b)473f9fbec18Smcpowers mp_err mp_sub_d(const mp_int *a, mp_digit d, mp_int *b)
474f9fbec18Smcpowers {
475f9fbec18Smcpowers   mp_int   tmp;
476f9fbec18Smcpowers   mp_err   res;
477f9fbec18Smcpowers 
478f9fbec18Smcpowers   ARGCHK(a != NULL && b != NULL, MP_BADARG);
479f9fbec18Smcpowers 
480f9fbec18Smcpowers   if((res = mp_init_copy(&tmp, a)) != MP_OKAY)
481f9fbec18Smcpowers     return res;
482f9fbec18Smcpowers 
483f9fbec18Smcpowers   if(SIGN(&tmp) == NEG) {
484f9fbec18Smcpowers     if((res = s_mp_add_d(&tmp, d)) != MP_OKAY)
485f9fbec18Smcpowers       goto CLEANUP;
486f9fbec18Smcpowers   } else if(s_mp_cmp_d(&tmp, d) >= 0) {
487f9fbec18Smcpowers     if((res = s_mp_sub_d(&tmp, d)) != MP_OKAY)
488f9fbec18Smcpowers       goto CLEANUP;
489f9fbec18Smcpowers   } else {
490f9fbec18Smcpowers     mp_neg(&tmp, &tmp);
491f9fbec18Smcpowers 
492f9fbec18Smcpowers     DIGIT(&tmp, 0) = d - DIGIT(&tmp, 0);
493f9fbec18Smcpowers     SIGN(&tmp) = NEG;
494f9fbec18Smcpowers   }
495f9fbec18Smcpowers 
496f9fbec18Smcpowers   if(s_mp_cmp_d(&tmp, 0) == 0)
497f9fbec18Smcpowers     SIGN(&tmp) = ZPOS;
498f9fbec18Smcpowers 
499f9fbec18Smcpowers   s_mp_exch(&tmp, b);
500f9fbec18Smcpowers 
501f9fbec18Smcpowers CLEANUP:
502f9fbec18Smcpowers   mp_clear(&tmp);
503f9fbec18Smcpowers   return res;
504f9fbec18Smcpowers 
505f9fbec18Smcpowers } /* end mp_sub_d() */
506f9fbec18Smcpowers 
507f9fbec18Smcpowers /* }}} */
508f9fbec18Smcpowers 
509f9fbec18Smcpowers /* {{{ mp_mul_d(a, d, b) */
510f9fbec18Smcpowers 
511f9fbec18Smcpowers /*
512f9fbec18Smcpowers   mp_mul_d(a, d, b)
513f9fbec18Smcpowers 
514f9fbec18Smcpowers   Compute the product b = a * d, for a single digit d.  Respects the sign
515f9fbec18Smcpowers   of its multiplicand (single digits are unsigned anyway)
516f9fbec18Smcpowers  */
517f9fbec18Smcpowers 
mp_mul_d(const mp_int * a,mp_digit d,mp_int * b)518f9fbec18Smcpowers mp_err mp_mul_d(const mp_int *a, mp_digit d, mp_int *b)
519f9fbec18Smcpowers {
520f9fbec18Smcpowers   mp_err  res;
521f9fbec18Smcpowers 
522f9fbec18Smcpowers   ARGCHK(a != NULL && b != NULL, MP_BADARG);
523f9fbec18Smcpowers 
524f9fbec18Smcpowers   if(d == 0) {
525f9fbec18Smcpowers     mp_zero(b);
526f9fbec18Smcpowers     return MP_OKAY;
527f9fbec18Smcpowers   }
528f9fbec18Smcpowers 
529f9fbec18Smcpowers   if((res = mp_copy(a, b)) != MP_OKAY)
530f9fbec18Smcpowers     return res;
531f9fbec18Smcpowers 
532f9fbec18Smcpowers   res = s_mp_mul_d(b, d);
533f9fbec18Smcpowers 
534f9fbec18Smcpowers   return res;
535f9fbec18Smcpowers 
536f9fbec18Smcpowers } /* end mp_mul_d() */
537f9fbec18Smcpowers 
538f9fbec18Smcpowers /* }}} */
539f9fbec18Smcpowers 
540f9fbec18Smcpowers /* {{{ mp_mul_2(a, c) */
541f9fbec18Smcpowers 
mp_mul_2(const mp_int * a,mp_int * c)542f9fbec18Smcpowers mp_err mp_mul_2(const mp_int *a, mp_int *c)
543f9fbec18Smcpowers {
544f9fbec18Smcpowers   mp_err  res;
545f9fbec18Smcpowers 
546f9fbec18Smcpowers   ARGCHK(a != NULL && c != NULL, MP_BADARG);
547f9fbec18Smcpowers 
548f9fbec18Smcpowers   if((res = mp_copy(a, c)) != MP_OKAY)
549f9fbec18Smcpowers     return res;
550f9fbec18Smcpowers 
551f9fbec18Smcpowers   return s_mp_mul_2(c);
552f9fbec18Smcpowers 
553f9fbec18Smcpowers } /* end mp_mul_2() */
554f9fbec18Smcpowers 
555f9fbec18Smcpowers /* }}} */
556f9fbec18Smcpowers 
557f9fbec18Smcpowers /* {{{ mp_div_d(a, d, q, r) */
558f9fbec18Smcpowers 
559f9fbec18Smcpowers /*
560f9fbec18Smcpowers   mp_div_d(a, d, q, r)
561f9fbec18Smcpowers 
562f9fbec18Smcpowers   Compute the quotient q = a / d and remainder r = a mod d, for a
563f9fbec18Smcpowers   single digit d.  Respects the sign of its divisor (single digits are
564f9fbec18Smcpowers   unsigned anyway).
565f9fbec18Smcpowers  */
566f9fbec18Smcpowers 
mp_div_d(const mp_int * a,mp_digit d,mp_int * q,mp_digit * r)567f9fbec18Smcpowers mp_err mp_div_d(const mp_int *a, mp_digit d, mp_int *q, mp_digit *r)
568f9fbec18Smcpowers {
569f9fbec18Smcpowers   mp_err   res;
570f9fbec18Smcpowers   mp_int   qp;
571f9fbec18Smcpowers   mp_digit rem;
572f9fbec18Smcpowers   int      pow;
573f9fbec18Smcpowers 
574f9fbec18Smcpowers   ARGCHK(a != NULL, MP_BADARG);
575f9fbec18Smcpowers 
576f9fbec18Smcpowers   if(d == 0)
577f9fbec18Smcpowers     return MP_RANGE;
578f9fbec18Smcpowers 
579f9fbec18Smcpowers   /* Shortcut for powers of two ... */
580f9fbec18Smcpowers   if((pow = s_mp_ispow2d(d)) >= 0) {
581f9fbec18Smcpowers     mp_digit  mask;
582f9fbec18Smcpowers 
583f9fbec18Smcpowers     mask = ((mp_digit)1 << pow) - 1;
584f9fbec18Smcpowers     rem = DIGIT(a, 0) & mask;
585f9fbec18Smcpowers 
586f9fbec18Smcpowers     if(q) {
587f9fbec18Smcpowers       mp_copy(a, q);
588f9fbec18Smcpowers       s_mp_div_2d(q, pow);
589f9fbec18Smcpowers     }
590f9fbec18Smcpowers 
591f9fbec18Smcpowers     if(r)
592f9fbec18Smcpowers       *r = rem;
593f9fbec18Smcpowers 
594f9fbec18Smcpowers     return MP_OKAY;
595f9fbec18Smcpowers   }
596f9fbec18Smcpowers 
597f9fbec18Smcpowers   if((res = mp_init_copy(&qp, a)) != MP_OKAY)
598f9fbec18Smcpowers     return res;
599f9fbec18Smcpowers 
600f9fbec18Smcpowers   res = s_mp_div_d(&qp, d, &rem);
601f9fbec18Smcpowers 
602f9fbec18Smcpowers   if(s_mp_cmp_d(&qp, 0) == 0)
603f9fbec18Smcpowers     SIGN(q) = ZPOS;
604f9fbec18Smcpowers 
605f9fbec18Smcpowers   if(r)
606f9fbec18Smcpowers     *r = rem;
607f9fbec18Smcpowers 
608f9fbec18Smcpowers   if(q)
609f9fbec18Smcpowers     s_mp_exch(&qp, q);
610f9fbec18Smcpowers 
611f9fbec18Smcpowers   mp_clear(&qp);
612f9fbec18Smcpowers   return res;
613f9fbec18Smcpowers 
614f9fbec18Smcpowers } /* end mp_div_d() */
615f9fbec18Smcpowers 
616f9fbec18Smcpowers /* }}} */
617f9fbec18Smcpowers 
618f9fbec18Smcpowers /* {{{ mp_div_2(a, c) */
619f9fbec18Smcpowers 
620f9fbec18Smcpowers /*
621f9fbec18Smcpowers   mp_div_2(a, c)
622f9fbec18Smcpowers 
623f9fbec18Smcpowers   Compute c = a / 2, disregarding the remainder.
624f9fbec18Smcpowers  */
625f9fbec18Smcpowers 
mp_div_2(const mp_int * a,mp_int * c)626f9fbec18Smcpowers mp_err mp_div_2(const mp_int *a, mp_int *c)
627f9fbec18Smcpowers {
628f9fbec18Smcpowers   mp_err  res;
629f9fbec18Smcpowers 
630f9fbec18Smcpowers   ARGCHK(a != NULL && c != NULL, MP_BADARG);
631f9fbec18Smcpowers 
632f9fbec18Smcpowers   if((res = mp_copy(a, c)) != MP_OKAY)
633f9fbec18Smcpowers     return res;
634f9fbec18Smcpowers 
635f9fbec18Smcpowers   s_mp_div_2(c);
636f9fbec18Smcpowers 
637f9fbec18Smcpowers   return MP_OKAY;
638f9fbec18Smcpowers 
639f9fbec18Smcpowers } /* end mp_div_2() */
640f9fbec18Smcpowers 
641f9fbec18Smcpowers /* }}} */
642f9fbec18Smcpowers 
643f9fbec18Smcpowers /* {{{ mp_expt_d(a, d, b) */
644f9fbec18Smcpowers 
mp_expt_d(const mp_int * a,mp_digit d,mp_int * c)645f9fbec18Smcpowers mp_err mp_expt_d(const mp_int *a, mp_digit d, mp_int *c)
646f9fbec18Smcpowers {
647f9fbec18Smcpowers   mp_int   s, x;
648f9fbec18Smcpowers   mp_err   res;
649f9fbec18Smcpowers 
650f9fbec18Smcpowers   ARGCHK(a != NULL && c != NULL, MP_BADARG);
651f9fbec18Smcpowers 
652f9fbec18Smcpowers   if((res = mp_init(&s, FLAG(a))) != MP_OKAY)
653f9fbec18Smcpowers     return res;
654f9fbec18Smcpowers   if((res = mp_init_copy(&x, a)) != MP_OKAY)
655f9fbec18Smcpowers     goto X;
656f9fbec18Smcpowers 
657f9fbec18Smcpowers   DIGIT(&s, 0) = 1;
658f9fbec18Smcpowers 
659f9fbec18Smcpowers   while(d != 0) {
660f9fbec18Smcpowers     if(d & 1) {
661f9fbec18Smcpowers       if((res = s_mp_mul(&s, &x)) != MP_OKAY)
662f9fbec18Smcpowers 	goto CLEANUP;
663f9fbec18Smcpowers     }
664f9fbec18Smcpowers 
665f9fbec18Smcpowers     d /= 2;
666f9fbec18Smcpowers 
667f9fbec18Smcpowers     if((res = s_mp_sqr(&x)) != MP_OKAY)
668f9fbec18Smcpowers       goto CLEANUP;
669f9fbec18Smcpowers   }
670f9fbec18Smcpowers 
671f9fbec18Smcpowers   s_mp_exch(&s, c);
672f9fbec18Smcpowers 
673f9fbec18Smcpowers CLEANUP:
674f9fbec18Smcpowers   mp_clear(&x);
675f9fbec18Smcpowers X:
676f9fbec18Smcpowers   mp_clear(&s);
677f9fbec18Smcpowers 
678f9fbec18Smcpowers   return res;
679f9fbec18Smcpowers 
680f9fbec18Smcpowers } /* end mp_expt_d() */
681f9fbec18Smcpowers 
682f9fbec18Smcpowers /* }}} */
683f9fbec18Smcpowers 
684f9fbec18Smcpowers /* }}} */
685f9fbec18Smcpowers 
686f9fbec18Smcpowers /*------------------------------------------------------------------------*/
687f9fbec18Smcpowers /* {{{ Full arithmetic */
688f9fbec18Smcpowers 
689f9fbec18Smcpowers /* {{{ mp_abs(a, b) */
690f9fbec18Smcpowers 
691f9fbec18Smcpowers /*
692f9fbec18Smcpowers   mp_abs(a, b)
693f9fbec18Smcpowers 
694f9fbec18Smcpowers   Compute b = |a|.  'a' and 'b' may be identical.
695f9fbec18Smcpowers  */
696f9fbec18Smcpowers 
mp_abs(const mp_int * a,mp_int * b)697f9fbec18Smcpowers mp_err mp_abs(const mp_int *a, mp_int *b)
698f9fbec18Smcpowers {
699f9fbec18Smcpowers   mp_err   res;
700f9fbec18Smcpowers 
701f9fbec18Smcpowers   ARGCHK(a != NULL && b != NULL, MP_BADARG);
702f9fbec18Smcpowers 
703f9fbec18Smcpowers   if((res = mp_copy(a, b)) != MP_OKAY)
704f9fbec18Smcpowers     return res;
705f9fbec18Smcpowers 
706f9fbec18Smcpowers   SIGN(b) = ZPOS;
707f9fbec18Smcpowers 
708f9fbec18Smcpowers   return MP_OKAY;
709f9fbec18Smcpowers 
710f9fbec18Smcpowers } /* end mp_abs() */
711f9fbec18Smcpowers 
712f9fbec18Smcpowers /* }}} */
713f9fbec18Smcpowers 
714f9fbec18Smcpowers /* {{{ mp_neg(a, b) */
715f9fbec18Smcpowers 
716f9fbec18Smcpowers /*
717f9fbec18Smcpowers   mp_neg(a, b)
718f9fbec18Smcpowers 
719f9fbec18Smcpowers   Compute b = -a.  'a' and 'b' may be identical.
720f9fbec18Smcpowers  */
721f9fbec18Smcpowers 
mp_neg(const mp_int * a,mp_int * b)722f9fbec18Smcpowers mp_err mp_neg(const mp_int *a, mp_int *b)
723f9fbec18Smcpowers {
724f9fbec18Smcpowers   mp_err   res;
725f9fbec18Smcpowers 
726f9fbec18Smcpowers   ARGCHK(a != NULL && b != NULL, MP_BADARG);
727f9fbec18Smcpowers 
728f9fbec18Smcpowers   if((res = mp_copy(a, b)) != MP_OKAY)
729f9fbec18Smcpowers     return res;
730f9fbec18Smcpowers 
731f9fbec18Smcpowers   if(s_mp_cmp_d(b, 0) == MP_EQ)
732f9fbec18Smcpowers     SIGN(b) = ZPOS;
733f9fbec18Smcpowers   else
734f9fbec18Smcpowers     SIGN(b) = (SIGN(b) == NEG) ? ZPOS : NEG;
735f9fbec18Smcpowers 
736f9fbec18Smcpowers   return MP_OKAY;
737f9fbec18Smcpowers 
738f9fbec18Smcpowers } /* end mp_neg() */
739f9fbec18Smcpowers 
740f9fbec18Smcpowers /* }}} */
741f9fbec18Smcpowers 
742f9fbec18Smcpowers /* {{{ mp_add(a, b, c) */
743f9fbec18Smcpowers 
744f9fbec18Smcpowers /*
745f9fbec18Smcpowers   mp_add(a, b, c)
746f9fbec18Smcpowers 
747f9fbec18Smcpowers   Compute c = a + b.  All parameters may be identical.
748f9fbec18Smcpowers  */
749f9fbec18Smcpowers 
mp_add(const mp_int * a,const mp_int * b,mp_int * c)750f9fbec18Smcpowers mp_err mp_add(const mp_int *a, const mp_int *b, mp_int *c)
751f9fbec18Smcpowers {
752f9fbec18Smcpowers   mp_err  res;
753f9fbec18Smcpowers 
754f9fbec18Smcpowers   ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
755f9fbec18Smcpowers 
756f9fbec18Smcpowers   if(SIGN(a) == SIGN(b)) { /* same sign:  add values, keep sign */
757f9fbec18Smcpowers     MP_CHECKOK( s_mp_add_3arg(a, b, c) );
758f9fbec18Smcpowers   } else if(s_mp_cmp(a, b) >= 0) {  /* different sign: |a| >= |b|   */
759f9fbec18Smcpowers     MP_CHECKOK( s_mp_sub_3arg(a, b, c) );
760f9fbec18Smcpowers   } else {                          /* different sign: |a|  < |b|   */
761f9fbec18Smcpowers     MP_CHECKOK( s_mp_sub_3arg(b, a, c) );
762f9fbec18Smcpowers   }
763f9fbec18Smcpowers 
764f9fbec18Smcpowers   if (s_mp_cmp_d(c, 0) == MP_EQ)
765f9fbec18Smcpowers     SIGN(c) = ZPOS;
766f9fbec18Smcpowers 
767f9fbec18Smcpowers CLEANUP:
768f9fbec18Smcpowers   return res;
769f9fbec18Smcpowers 
770f9fbec18Smcpowers } /* end mp_add() */
771f9fbec18Smcpowers 
772f9fbec18Smcpowers /* }}} */
773f9fbec18Smcpowers 
774f9fbec18Smcpowers /* {{{ mp_sub(a, b, c) */
775f9fbec18Smcpowers 
776f9fbec18Smcpowers /*
777f9fbec18Smcpowers   mp_sub(a, b, c)
778f9fbec18Smcpowers 
779f9fbec18Smcpowers   Compute c = a - b.  All parameters may be identical.
780f9fbec18Smcpowers  */
781f9fbec18Smcpowers 
mp_sub(const mp_int * a,const mp_int * b,mp_int * c)782f9fbec18Smcpowers mp_err mp_sub(const mp_int *a, const mp_int *b, mp_int *c)
783f9fbec18Smcpowers {
784f9fbec18Smcpowers   mp_err  res;
785f9fbec18Smcpowers   int     magDiff;
786f9fbec18Smcpowers 
787f9fbec18Smcpowers   ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
788f9fbec18Smcpowers 
789f9fbec18Smcpowers   if (a == b) {
790f9fbec18Smcpowers     mp_zero(c);
791f9fbec18Smcpowers     return MP_OKAY;
792f9fbec18Smcpowers   }
793f9fbec18Smcpowers 
794f9fbec18Smcpowers   if (MP_SIGN(a) != MP_SIGN(b)) {
795f9fbec18Smcpowers     MP_CHECKOK( s_mp_add_3arg(a, b, c) );
796f9fbec18Smcpowers   } else if (!(magDiff = s_mp_cmp(a, b))) {
797f9fbec18Smcpowers     mp_zero(c);
798f9fbec18Smcpowers     res = MP_OKAY;
799f9fbec18Smcpowers   } else if (magDiff > 0) {
800f9fbec18Smcpowers     MP_CHECKOK( s_mp_sub_3arg(a, b, c) );
801f9fbec18Smcpowers   } else {
802f9fbec18Smcpowers     MP_CHECKOK( s_mp_sub_3arg(b, a, c) );
803f9fbec18Smcpowers     MP_SIGN(c) = !MP_SIGN(a);
804f9fbec18Smcpowers   }
805f9fbec18Smcpowers 
806f9fbec18Smcpowers   if (s_mp_cmp_d(c, 0) == MP_EQ)
807f9fbec18Smcpowers     MP_SIGN(c) = MP_ZPOS;
808f9fbec18Smcpowers 
809f9fbec18Smcpowers CLEANUP:
810f9fbec18Smcpowers   return res;
811f9fbec18Smcpowers 
812f9fbec18Smcpowers } /* end mp_sub() */
813f9fbec18Smcpowers 
814f9fbec18Smcpowers /* }}} */
815f9fbec18Smcpowers 
816f9fbec18Smcpowers /* {{{ mp_mul(a, b, c) */
817f9fbec18Smcpowers 
818f9fbec18Smcpowers /*
819f9fbec18Smcpowers   mp_mul(a, b, c)
820f9fbec18Smcpowers 
821f9fbec18Smcpowers   Compute c = a * b.  All parameters may be identical.
822f9fbec18Smcpowers  */
mp_mul(const mp_int * a,const mp_int * b,mp_int * c)823f9fbec18Smcpowers mp_err   mp_mul(const mp_int *a, const mp_int *b, mp_int * c)
824f9fbec18Smcpowers {
825f9fbec18Smcpowers   mp_digit *pb;
826f9fbec18Smcpowers   mp_int   tmp;
827f9fbec18Smcpowers   mp_err   res;
828f9fbec18Smcpowers   mp_size  ib;
829f9fbec18Smcpowers   mp_size  useda, usedb;
830f9fbec18Smcpowers 
831f9fbec18Smcpowers   ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
832f9fbec18Smcpowers 
833f9fbec18Smcpowers   if (a == c) {
834f9fbec18Smcpowers     if ((res = mp_init_copy(&tmp, a)) != MP_OKAY)
835f9fbec18Smcpowers       return res;
836f9fbec18Smcpowers     if (a == b)
837f9fbec18Smcpowers       b = &tmp;
838f9fbec18Smcpowers     a = &tmp;
839f9fbec18Smcpowers   } else if (b == c) {
840f9fbec18Smcpowers     if ((res = mp_init_copy(&tmp, b)) != MP_OKAY)
841f9fbec18Smcpowers       return res;
842f9fbec18Smcpowers     b = &tmp;
843f9fbec18Smcpowers   } else {
844f9fbec18Smcpowers     MP_DIGITS(&tmp) = 0;
845f9fbec18Smcpowers   }
846f9fbec18Smcpowers 
847f9fbec18Smcpowers   if (MP_USED(a) < MP_USED(b)) {
848f9fbec18Smcpowers     const mp_int *xch = b;	/* switch a and b, to do fewer outer loops */
849f9fbec18Smcpowers     b = a;
850f9fbec18Smcpowers     a = xch;
851f9fbec18Smcpowers   }
852f9fbec18Smcpowers 
853f9fbec18Smcpowers   MP_USED(c) = 1; MP_DIGIT(c, 0) = 0;
854f9fbec18Smcpowers   if((res = s_mp_pad(c, USED(a) + USED(b))) != MP_OKAY)
855f9fbec18Smcpowers     goto CLEANUP;
856f9fbec18Smcpowers 
857f9fbec18Smcpowers #ifdef NSS_USE_COMBA
858f9fbec18Smcpowers   if ((MP_USED(a) == MP_USED(b)) && IS_POWER_OF_2(MP_USED(b))) {
859f9fbec18Smcpowers       if (MP_USED(a) == 4) {
860f9fbec18Smcpowers           s_mp_mul_comba_4(a, b, c);
861f9fbec18Smcpowers           goto CLEANUP;
862f9fbec18Smcpowers       }
863f9fbec18Smcpowers       if (MP_USED(a) == 8) {
864f9fbec18Smcpowers           s_mp_mul_comba_8(a, b, c);
865f9fbec18Smcpowers           goto CLEANUP;
866f9fbec18Smcpowers       }
867f9fbec18Smcpowers       if (MP_USED(a) == 16) {
868f9fbec18Smcpowers           s_mp_mul_comba_16(a, b, c);
869f9fbec18Smcpowers           goto CLEANUP;
870f9fbec18Smcpowers       }
871f9fbec18Smcpowers       if (MP_USED(a) == 32) {
872f9fbec18Smcpowers           s_mp_mul_comba_32(a, b, c);
873f9fbec18Smcpowers           goto CLEANUP;
874f9fbec18Smcpowers       }
875f9fbec18Smcpowers   }
876f9fbec18Smcpowers #endif
877f9fbec18Smcpowers 
878f9fbec18Smcpowers   pb = MP_DIGITS(b);
879f9fbec18Smcpowers   s_mpv_mul_d(MP_DIGITS(a), MP_USED(a), *pb++, MP_DIGITS(c));
880f9fbec18Smcpowers 
881f9fbec18Smcpowers   /* Outer loop:  Digits of b */
882f9fbec18Smcpowers   useda = MP_USED(a);
883f9fbec18Smcpowers   usedb = MP_USED(b);
884f9fbec18Smcpowers   for (ib = 1; ib < usedb; ib++) {
885f9fbec18Smcpowers     mp_digit b_i    = *pb++;
886f9fbec18Smcpowers 
887f9fbec18Smcpowers     /* Inner product:  Digits of a */
888f9fbec18Smcpowers     if (b_i)
889f9fbec18Smcpowers       s_mpv_mul_d_add(MP_DIGITS(a), useda, b_i, MP_DIGITS(c) + ib);
890f9fbec18Smcpowers     else
891f9fbec18Smcpowers       MP_DIGIT(c,