xref: /onnv-gate/usr/src/common/mpi/mpi-priv.h (revision 5697:324be5104707)
1*5697Smcpowers /*
2*5697Smcpowers  *  mpi-priv.h	- Private header file for MPI
3*5697Smcpowers  *  Arbitrary precision integer arithmetic library
4*5697Smcpowers  *
5*5697Smcpowers  *  NOTE WELL: the content of this header file is NOT part of the "public"
6*5697Smcpowers  *  API for the MPI library, and may change at any time.
7*5697Smcpowers  *  Application programs that use libmpi should NOT include this header file.
8*5697Smcpowers  *
9*5697Smcpowers  * ***** BEGIN LICENSE BLOCK *****
10*5697Smcpowers  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
11*5697Smcpowers  *
12*5697Smcpowers  * The contents of this file are subject to the Mozilla Public License Version
13*5697Smcpowers  * 1.1 (the "License"); you may not use this file except in compliance with
14*5697Smcpowers  * the License. You may obtain a copy of the License at
15*5697Smcpowers  * http://www.mozilla.org/MPL/
16*5697Smcpowers  *
17*5697Smcpowers  * Software distributed under the License is distributed on an "AS IS" basis,
18*5697Smcpowers  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
19*5697Smcpowers  * for the specific language governing rights and limitations under the
20*5697Smcpowers  * License.
21*5697Smcpowers  *
22*5697Smcpowers  * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.
23*5697Smcpowers  *
24*5697Smcpowers  * The Initial Developer of the Original Code is
25*5697Smcpowers  * Michael J. Fromberger.
26*5697Smcpowers  * Portions created by the Initial Developer are Copyright (C) 1998
27*5697Smcpowers  * the Initial Developer. All Rights Reserved.
28*5697Smcpowers  *
29*5697Smcpowers  * Contributor(s):
30*5697Smcpowers  *   Netscape Communications Corporation
31*5697Smcpowers  *
32*5697Smcpowers  * Alternatively, the contents of this file may be used under the terms of
33*5697Smcpowers  * either the GNU General Public License Version 2 or later (the "GPL"), or
34*5697Smcpowers  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
35*5697Smcpowers  * in which case the provisions of the GPL or the LGPL are applicable instead
36*5697Smcpowers  * of those above. If you wish to allow use of your version of this file only
37*5697Smcpowers  * under the terms of either the GPL or the LGPL, and not to allow others to
38*5697Smcpowers  * use your version of this file under the terms of the MPL, indicate your
39*5697Smcpowers  * decision by deleting the provisions above and replace them with the notice
40*5697Smcpowers  * and other provisions required by the GPL or the LGPL. If you do not delete
41*5697Smcpowers  * the provisions above, a recipient may use your version of this file under
42*5697Smcpowers  * the terms of any one of the MPL, the GPL or the LGPL.
43*5697Smcpowers  *
44*5697Smcpowers  * ***** END LICENSE BLOCK ***** */
45*5697Smcpowers /*
46*5697Smcpowers  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
47*5697Smcpowers  * Use is subject to license terms.
48*5697Smcpowers  *
49*5697Smcpowers  * Sun elects to use this software under the MPL license.
50*5697Smcpowers  */
51*5697Smcpowers 
52*5697Smcpowers #ifndef _MPI_PRIV_H
53*5697Smcpowers #define _MPI_PRIV_H
54*5697Smcpowers 
55*5697Smcpowers #pragma ident	"%Z%%M%	%I%	%E% SMI"
56*5697Smcpowers 
57*5697Smcpowers /* $Id: mpi-priv.h,v 1.20 2005/11/22 07:16:43 relyea%netscape.com Exp $ */
58*5697Smcpowers 
59*5697Smcpowers #include "mpi.h"
60*5697Smcpowers #ifndef _KERNEL
61*5697Smcpowers #include <stdlib.h>
62*5697Smcpowers #include <string.h>
63*5697Smcpowers #include <ctype.h>
64*5697Smcpowers #endif /* _KERNEL */
65*5697Smcpowers 
66*5697Smcpowers #if MP_DEBUG
67*5697Smcpowers #include <stdio.h>
68*5697Smcpowers 
69*5697Smcpowers #define DIAG(T,V) {fprintf(stderr,T);mp_print(V,stderr);fputc('\n',stderr);}
70*5697Smcpowers #else
71*5697Smcpowers #define DIAG(T,V)
72*5697Smcpowers #endif
73*5697Smcpowers 
74*5697Smcpowers /* If we aren't using a wired-in logarithm table, we need to include
75*5697Smcpowers    the math library to get the log() function
76*5697Smcpowers  */
77*5697Smcpowers 
78*5697Smcpowers /* {{{ s_logv_2[] - log table for 2 in various bases */
79*5697Smcpowers 
80*5697Smcpowers #if MP_LOGTAB
81*5697Smcpowers /*
82*5697Smcpowers   A table of the logs of 2 for various bases (the 0 and 1 entries of
83*5697Smcpowers   this table are meaningless and should not be referenced).
84*5697Smcpowers 
85*5697Smcpowers   This table is used to compute output lengths for the mp_toradix()
86*5697Smcpowers   function.  Since a number n in radix r takes up about log_r(n)
87*5697Smcpowers   digits, we estimate the output size by taking the least integer
88*5697Smcpowers   greater than log_r(n), where:
89*5697Smcpowers 
90*5697Smcpowers   log_r(n) = log_2(n) * log_r(2)
91*5697Smcpowers 
92*5697Smcpowers   This table, therefore, is a table of log_r(2) for 2 <= r <= 36,
93*5697Smcpowers   which are the output bases supported.
94*5697Smcpowers  */
95*5697Smcpowers 
96*5697Smcpowers extern const float s_logv_2[];
97*5697Smcpowers #define LOG_V_2(R)  s_logv_2[(R)]
98*5697Smcpowers 
99*5697Smcpowers #else
100*5697Smcpowers 
101*5697Smcpowers /*
102*5697Smcpowers    If MP_LOGTAB is not defined, use the math library to compute the
103*5697Smcpowers    logarithms on the fly.  Otherwise, use the table.
104*5697Smcpowers    Pick which works best for your system.
105*5697Smcpowers  */
106*5697Smcpowers 
107*5697Smcpowers #include <math.h>
108*5697Smcpowers #define LOG_V_2(R)  (log(2.0)/log(R))
109*5697Smcpowers 
110*5697Smcpowers #endif /* if MP_LOGTAB */
111*5697Smcpowers 
112*5697Smcpowers /* }}} */
113*5697Smcpowers 
114*5697Smcpowers /* {{{ Digit arithmetic macros */
115*5697Smcpowers 
116*5697Smcpowers /*
117*5697Smcpowers   When adding and multiplying digits, the results can be larger than
118*5697Smcpowers   can be contained in an mp_digit.  Thus, an mp_word is used.  These
119*5697Smcpowers   macros mask off the upper and lower digits of the mp_word (the
120*5697Smcpowers   mp_word may be more than 2 mp_digits wide, but we only concern
121*5697Smcpowers   ourselves with the low-order 2 mp_digits)
122*5697Smcpowers  */
123*5697Smcpowers 
124*5697Smcpowers #define  CARRYOUT(W)  (mp_digit)((W)>>DIGIT_BIT)
125*5697Smcpowers #define  ACCUM(W)     (mp_digit)(W)
126*5697Smcpowers 
127*5697Smcpowers #define MP_MIN(a,b)   (((a) < (b)) ? (a) : (b))
128*5697Smcpowers #define MP_MAX(a,b)   (((a) > (b)) ? (a) : (b))
129*5697Smcpowers #define MP_HOWMANY(a,b) (((a) + (b) - 1)/(b))
130*5697Smcpowers #define MP_ROUNDUP(a,b) (MP_HOWMANY(a,b) * (b))
131*5697Smcpowers 
132*5697Smcpowers /* }}} */
133*5697Smcpowers 
134*5697Smcpowers /* {{{ Comparison constants */
135*5697Smcpowers 
136*5697Smcpowers #define  MP_LT       -1
137*5697Smcpowers #define  MP_EQ        0
138*5697Smcpowers #define  MP_GT        1
139*5697Smcpowers 
140*5697Smcpowers /* }}} */
141*5697Smcpowers 
142*5697Smcpowers /* {{{ private function declarations */
143*5697Smcpowers 
144*5697Smcpowers /*
145*5697Smcpowers    If MP_MACRO is false, these will be defined as actual functions;
146*5697Smcpowers    otherwise, suitable macro definitions will be used.  This works
147*5697Smcpowers    around the fact that ANSI C89 doesn't support an 'inline' keyword
148*5697Smcpowers    (although I hear C9x will ... about bloody time).  At present, the
149*5697Smcpowers    macro definitions are identical to the function bodies, but they'll
150*5697Smcpowers    expand in place, instead of generating a function call.
151*5697Smcpowers 
152*5697Smcpowers    I chose these particular functions to be made into macros because
153*5697Smcpowers    some profiling showed they are called a lot on a typical workload,
154*5697Smcpowers    and yet they are primarily housekeeping.
155*5697Smcpowers  */
156*5697Smcpowers #if MP_MACRO == 0
157*5697Smcpowers  void     s_mp_setz(mp_digit *dp, mp_size count); /* zero digits           */
158*5697Smcpowers  void     s_mp_copy(const mp_digit *sp, mp_digit *dp, mp_size count); /* copy */
159*5697Smcpowers  void    *s_mp_alloc(size_t nb, size_t ni, int flag); /* general allocator    */
160*5697Smcpowers  void     s_mp_free(void *ptr, mp_size);          /* general free function */
161*5697Smcpowers extern unsigned long mp_allocs;
162*5697Smcpowers extern unsigned long mp_frees;
163*5697Smcpowers extern unsigned long mp_copies;
164*5697Smcpowers #else
165*5697Smcpowers 
166*5697Smcpowers  /* Even if these are defined as macros, we need to respect the settings
167*5697Smcpowers     of the MP_MEMSET and MP_MEMCPY configuration options...
168*5697Smcpowers   */
169*5697Smcpowers  #if MP_MEMSET == 0
170*5697Smcpowers   #define  s_mp_setz(dp, count) \
171*5697Smcpowers        {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=0;}
172*5697Smcpowers  #else
173*5697Smcpowers   #define  s_mp_setz(dp, count) memset(dp, 0, (count) * sizeof(mp_digit))
174*5697Smcpowers  #endif /* MP_MEMSET */
175*5697Smcpowers 
176*5697Smcpowers  #if MP_MEMCPY == 0
177*5697Smcpowers   #define  s_mp_copy(sp, dp, count) \
178*5697Smcpowers        {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=(sp)[ix];}
179*5697Smcpowers  #else
180*5697Smcpowers   #define  s_mp_copy(sp, dp, count) memcpy(dp, sp, (count) * sizeof(mp_digit))
181*5697Smcpowers  #endif /* MP_MEMCPY */
182*5697Smcpowers 
183*5697Smcpowers  #define  s_mp_alloc(nb, ni)  calloc(nb, ni)
184*5697Smcpowers  #define  s_mp_free(ptr) {if(ptr) free(ptr);}
185*5697Smcpowers #endif /* MP_MACRO */
186*5697Smcpowers 
187*5697Smcpowers mp_err   s_mp_grow(mp_int *mp, mp_size min);   /* increase allocated size */
188*5697Smcpowers mp_err   s_mp_pad(mp_int *mp, mp_size min);    /* left pad with zeroes    */
189*5697Smcpowers 
190*5697Smcpowers #if MP_MACRO == 0
191*5697Smcpowers  void     s_mp_clamp(mp_int *mp);               /* clip leading zeroes     */
192*5697Smcpowers #else
193*5697Smcpowers  #define  s_mp_clamp(mp)\
194*5697Smcpowers   { mp_size used = MP_USED(mp); \
195*5697Smcpowers     while (used > 1 && DIGIT(mp, used - 1) == 0) --used; \
196*5697Smcpowers     MP_USED(mp) = used; \
197*5697Smcpowers   }
198*5697Smcpowers #endif /* MP_MACRO */
199*5697Smcpowers 
200*5697Smcpowers void     s_mp_exch(mp_int *a, mp_int *b);      /* swap a and b in place   */
201*5697Smcpowers 
202*5697Smcpowers mp_err   s_mp_lshd(mp_int *mp, mp_size p);     /* left-shift by p digits  */
203*5697Smcpowers void     s_mp_rshd(mp_int *mp, mp_size p);     /* right-shift by p digits */
204*5697Smcpowers mp_err   s_mp_mul_2d(mp_int *mp, mp_digit d);  /* multiply by 2^d in place */
205*5697Smcpowers void     s_mp_div_2d(mp_int *mp, mp_digit d);  /* divide by 2^d in place  */
206*5697Smcpowers void     s_mp_mod_2d(mp_int *mp, mp_digit d);  /* modulo 2^d in place     */
207*5697Smcpowers void     s_mp_div_2(mp_int *mp);               /* divide by 2 in place    */
208*5697Smcpowers mp_err   s_mp_mul_2(mp_int *mp);               /* multiply by 2 in place  */
209*5697Smcpowers mp_err   s_mp_norm(mp_int *a, mp_int *b, mp_digit *pd);
210*5697Smcpowers                                                /* normalize for division  */
211*5697Smcpowers mp_err   s_mp_add_d(mp_int *mp, mp_digit d);   /* unsigned digit addition */
212*5697Smcpowers mp_err   s_mp_sub_d(mp_int *mp, mp_digit d);   /* unsigned digit subtract */
213*5697Smcpowers mp_err   s_mp_mul_d(mp_int *mp, mp_digit d);   /* unsigned digit multiply */
214*5697Smcpowers mp_err   s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r);
215*5697Smcpowers 		                               /* unsigned digit divide   */
216*5697Smcpowers mp_err   s_mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu);
217*5697Smcpowers                                                /* Barrett reduction       */
218*5697Smcpowers mp_err   s_mp_add(mp_int *a, const mp_int *b); /* magnitude addition      */
219*5697Smcpowers mp_err   s_mp_add_3arg(const mp_int *a, const mp_int *b, mp_int *c);
220*5697Smcpowers mp_err   s_mp_sub(mp_int *a, const mp_int *b); /* magnitude subtract      */
221*5697Smcpowers mp_err   s_mp_sub_3arg(const mp_int *a, const mp_int *b, mp_int *c);
222*5697Smcpowers mp_err   s_mp_add_offset(mp_int *a, mp_int *b, mp_size offset);
223*5697Smcpowers                                                /* a += b * RADIX^offset   */
224*5697Smcpowers mp_err   s_mp_mul(mp_int *a, const mp_int *b); /* magnitude multiply      */
225*5697Smcpowers #if MP_SQUARE
226*5697Smcpowers mp_err   s_mp_sqr(mp_int *a);                  /* magnitude square        */
227*5697Smcpowers #else
228*5697Smcpowers #define  s_mp_sqr(a) s_mp_mul(a, a)
229*5697Smcpowers #endif
230*5697Smcpowers mp_err   s_mp_div(mp_int *rem, mp_int *div, mp_int *quot); /* magnitude div */
231*5697Smcpowers mp_err   s_mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
232*5697Smcpowers mp_err   s_mp_2expt(mp_int *a, mp_digit k);    /* a = 2^k                 */
233*5697Smcpowers int      s_mp_cmp(const mp_int *a, const mp_int *b); /* magnitude comparison */
234*5697Smcpowers int      s_mp_cmp_d(const mp_int *a, mp_digit d); /* magnitude digit compare */
235*5697Smcpowers int      s_mp_ispow2(const mp_int *v);         /* is v a power of 2?      */
236*5697Smcpowers int      s_mp_ispow2d(mp_digit d);             /* is d a power of 2?      */
237*5697Smcpowers 
238*5697Smcpowers int      s_mp_tovalue(char ch, int r);          /* convert ch to value    */
239*5697Smcpowers char     s_mp_todigit(mp_digit val, int r, int low); /* convert val to digit */
240*5697Smcpowers int      s_mp_outlen(int bits, int r);          /* output length in bytes */
241*5697Smcpowers mp_digit s_mp_invmod_radix(mp_digit P);   /* returns (P ** -1) mod RADIX */
242*5697Smcpowers mp_err   s_mp_invmod_odd_m( const mp_int *a, const mp_int *m, mp_int *c);
243*5697Smcpowers mp_err   s_mp_invmod_2d(    const mp_int *a, mp_size k,       mp_int *c);
244*5697Smcpowers mp_err   s_mp_invmod_even_m(const mp_int *a, const mp_int *m, mp_int *c);
245*5697Smcpowers 
246*5697Smcpowers #ifdef NSS_USE_COMBA
247*5697Smcpowers 
248*5697Smcpowers #define IS_POWER_OF_2(a) ((a) && !((a) & ((a)-1)))
249*5697Smcpowers 
250*5697Smcpowers void s_mp_mul_comba_4(const mp_int *A, const mp_int *B, mp_int *C);
251*5697Smcpowers void s_mp_mul_comba_8(const mp_int *A, const mp_int *B, mp_int *C);
252*5697Smcpowers void s_mp_mul_comba_16(const mp_int *A, const mp_int *B, mp_int *C);
253*5697Smcpowers void s_mp_mul_comba_32(const mp_int *A, const mp_int *B, mp_int *C);
254*5697Smcpowers 
255*5697Smcpowers void s_mp_sqr_comba_4(const mp_int *A, mp_int *B);
256*5697Smcpowers void s_mp_sqr_comba_8(const mp_int *A, mp_int *B);
257*5697Smcpowers void s_mp_sqr_comba_16(const mp_int *A, mp_int *B);
258*5697Smcpowers void s_mp_sqr_comba_32(const mp_int *A, mp_int *B);
259*5697Smcpowers 
260*5697Smcpowers #endif /* end NSS_USE_COMBA */
261*5697Smcpowers 
262*5697Smcpowers /* ------ mpv functions, operate on arrays of digits, not on mp_int's ------ */
263*5697Smcpowers #if defined (__OS2__) && defined (__IBMC__)
264*5697Smcpowers #define MPI_ASM_DECL __cdecl
265*5697Smcpowers #else
266*5697Smcpowers #define MPI_ASM_DECL
267*5697Smcpowers #endif
268*5697Smcpowers 
269*5697Smcpowers #ifdef MPI_AMD64
270*5697Smcpowers 
271*5697Smcpowers mp_digit MPI_ASM_DECL s_mpv_mul_set_vec64(mp_digit*, mp_digit *, mp_size, mp_digit);
272*5697Smcpowers mp_digit MPI_ASM_DECL s_mpv_mul_add_vec64(mp_digit*, const mp_digit*, mp_size, mp_digit);
273*5697Smcpowers 
274*5697Smcpowers /* c = a * b */
275*5697Smcpowers #define s_mpv_mul_d(a, a_len, b, c) \
276*5697Smcpowers 	((unsigned long*)c)[a_len] = s_mpv_mul_set_vec64(c, a, a_len, b)
277*5697Smcpowers 
278*5697Smcpowers /* c += a * b */
279*5697Smcpowers #define s_mpv_mul_d_add(a, a_len, b, c) \
280*5697Smcpowers 	((unsigned long*)c)[a_len] = s_mpv_mul_add_vec64(c, a, a_len, b)
281*5697Smcpowers 
282*5697Smcpowers #else
283*5697Smcpowers 
284*5697Smcpowers void     MPI_ASM_DECL s_mpv_mul_d(const mp_digit *a, mp_size a_len,
285*5697Smcpowers                                         mp_digit b, mp_digit *c);
286*5697Smcpowers void     MPI_ASM_DECL s_mpv_mul_d_add(const mp_digit *a, mp_size a_len,
287*5697Smcpowers                                             mp_digit b, mp_digit *c);
288*5697Smcpowers 
289*5697Smcpowers #endif
290*5697Smcpowers 
291*5697Smcpowers void     MPI_ASM_DECL s_mpv_mul_d_add_prop(const mp_digit *a,
292*5697Smcpowers                                                 mp_size a_len, mp_digit b,
293*5697Smcpowers 			                        mp_digit *c);
294*5697Smcpowers void     MPI_ASM_DECL s_mpv_sqr_add_prop(const mp_digit *a,
295*5697Smcpowers                                                 mp_size a_len,
296*5697Smcpowers                                                 mp_digit *sqrs);
297*5697Smcpowers 
298*5697Smcpowers mp_err   MPI_ASM_DECL s_mpv_div_2dx1d(mp_digit Nhi, mp_digit Nlo,
299*5697Smcpowers                             mp_digit divisor, mp_digit *quot, mp_digit *rem);
300*5697Smcpowers 
301*5697Smcpowers /* c += a * b * (MP_RADIX ** offset);  */
302*5697Smcpowers #define s_mp_mul_d_add_offset(a, b, c, off) \
303*5697Smcpowers (s_mpv_mul_d_add_prop(MP_DIGITS(a), MP_USED(a), b, MP_DIGITS(c) + off), MP_OKAY)
304*5697Smcpowers 
305*5697Smcpowers typedef struct {
306*5697Smcpowers   mp_int       N;	/* modulus N */
307*5697Smcpowers   mp_digit     n0prime; /* n0' = - (n0 ** -1) mod MP_RADIX */
308*5697Smcpowers   mp_size      b;	/* R == 2 ** b,  also b = # significant bits in N */
309*5697Smcpowers } mp_mont_modulus;
310*5697Smcpowers 
311*5697Smcpowers mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c,
312*5697Smcpowers 	               mp_mont_modulus *mmm);
313*5697Smcpowers mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm);
314*5697Smcpowers 
315*5697Smcpowers /*
316*5697Smcpowers  * s_mpi_getProcessorLineSize() returns the size in bytes of the cache line
317*5697Smcpowers  * if a cache exists, or zero if there is no cache. If more than one
318*5697Smcpowers  * cache line exists, it should return the smallest line size (which is
319*5697Smcpowers  * usually the L1 cache).
320*5697Smcpowers  *
321*5697Smcpowers  * mp_modexp uses this information to make sure that private key information
322*5697Smcpowers  * isn't being leaked through the cache.
323*5697Smcpowers  *
324*5697Smcpowers  * see mpcpucache.c for the implementation.
325*5697Smcpowers  */
326*5697Smcpowers unsigned long s_mpi_getProcessorLineSize();
327*5697Smcpowers 
328*5697Smcpowers /* }}} */
329*5697Smcpowers #endif /* _MPI_PRIV_H */
330