Back to index

lightning-sunbird  0.9+nobinonly
mpi-priv.h
Go to the documentation of this file.
00001 /*
00002  *  mpi-priv.h       - Private header file for MPI 
00003  *  Arbitrary precision integer arithmetic library
00004  *
00005  *  NOTE WELL: the content of this header file is NOT part of the "public"
00006  *  API for the MPI library, and may change at any time.  
00007  *  Application programs that use libmpi should NOT include this header file.
00008  *
00009  * ***** BEGIN LICENSE BLOCK *****
00010  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00011  *
00012  * The contents of this file are subject to the Mozilla Public License Version
00013  * 1.1 (the "License"); you may not use this file except in compliance with
00014  * the License. You may obtain a copy of the License at
00015  * http://www.mozilla.org/MPL/
00016  *
00017  * Software distributed under the License is distributed on an "AS IS" basis,
00018  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00019  * for the specific language governing rights and limitations under the
00020  * License.
00021  *
00022  * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.
00023  *
00024  * The Initial Developer of the Original Code is
00025  * Michael J. Fromberger.
00026  * Portions created by the Initial Developer are Copyright (C) 1998
00027  * the Initial Developer. All Rights Reserved.
00028  *
00029  * Contributor(s):
00030  *   Netscape Communications Corporation
00031  *
00032  * Alternatively, the contents of this file may be used under the terms of
00033  * either the GNU General Public License Version 2 or later (the "GPL"), or
00034  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00035  * in which case the provisions of the GPL or the LGPL are applicable instead
00036  * of those above. If you wish to allow use of your version of this file only
00037  * under the terms of either the GPL or the LGPL, and not to allow others to
00038  * use your version of this file under the terms of the MPL, indicate your
00039  * decision by deleting the provisions above and replace them with the notice
00040  * and other provisions required by the GPL or the LGPL. If you do not delete
00041  * the provisions above, a recipient may use your version of this file under
00042  * the terms of any one of the MPL, the GPL or the LGPL.
00043  *
00044  * ***** END LICENSE BLOCK ***** */
00045 /* $Id: mpi-priv.h,v 1.20 2005/11/22 07:16:43 relyea%netscape.com Exp $ */
00046 #ifndef _MPI_PRIV_H_
00047 #define _MPI_PRIV_H_ 1
00048 
00049 #include "mpi.h"
00050 #include <stdlib.h>
00051 #include <string.h>
00052 #include <ctype.h>
00053 
00054 #if MP_DEBUG
00055 #include <stdio.h>
00056 
00057 #define DIAG(T,V) {fprintf(stderr,T);mp_print(V,stderr);fputc('\n',stderr);}
00058 #else
00059 #define DIAG(T,V)
00060 #endif
00061 
00062 /* If we aren't using a wired-in logarithm table, we need to include
00063    the math library to get the log() function
00064  */
00065 
00066 /* {{{ s_logv_2[] - log table for 2 in various bases */
00067 
00068 #if MP_LOGTAB
00069 /*
00070   A table of the logs of 2 for various bases (the 0 and 1 entries of
00071   this table are meaningless and should not be referenced).  
00072 
00073   This table is used to compute output lengths for the mp_toradix()
00074   function.  Since a number n in radix r takes up about log_r(n)
00075   digits, we estimate the output size by taking the least integer
00076   greater than log_r(n), where:
00077 
00078   log_r(n) = log_2(n) * log_r(2)
00079 
00080   This table, therefore, is a table of log_r(2) for 2 <= r <= 36,
00081   which are the output bases supported.  
00082  */
00083 
00084 extern const float s_logv_2[];
00085 #define LOG_V_2(R)  s_logv_2[(R)]
00086 
00087 #else
00088 
00089 /* 
00090    If MP_LOGTAB is not defined, use the math library to compute the
00091    logarithms on the fly.  Otherwise, use the table.
00092    Pick which works best for your system.
00093  */
00094 
00095 #include <math.h>
00096 #define LOG_V_2(R)  (log(2.0)/log(R))
00097 
00098 #endif /* if MP_LOGTAB */
00099 
00100 /* }}} */
00101 
00102 /* {{{ Digit arithmetic macros */
00103 
00104 /*
00105   When adding and multiplying digits, the results can be larger than
00106   can be contained in an mp_digit.  Thus, an mp_word is used.  These
00107   macros mask off the upper and lower digits of the mp_word (the
00108   mp_word may be more than 2 mp_digits wide, but we only concern
00109   ourselves with the low-order 2 mp_digits)
00110  */
00111 
00112 #define  CARRYOUT(W)  (mp_digit)((W)>>DIGIT_BIT)
00113 #define  ACCUM(W)     (mp_digit)(W)
00114 
00115 #define MP_MIN(a,b)   (((a) < (b)) ? (a) : (b))
00116 #define MP_MAX(a,b)   (((a) > (b)) ? (a) : (b))
00117 #define MP_HOWMANY(a,b) (((a) + (b) - 1)/(b))
00118 #define MP_ROUNDUP(a,b) (MP_HOWMANY(a,b) * (b))
00119 
00120 /* }}} */
00121 
00122 /* {{{ Comparison constants */
00123 
00124 #define  MP_LT       -1
00125 #define  MP_EQ        0
00126 #define  MP_GT        1
00127 
00128 /* }}} */
00129 
00130 /* {{{ private function declarations */
00131 
00132 /* 
00133    If MP_MACRO is false, these will be defined as actual functions;
00134    otherwise, suitable macro definitions will be used.  This works
00135    around the fact that ANSI C89 doesn't support an 'inline' keyword
00136    (although I hear C9x will ... about bloody time).  At present, the
00137    macro definitions are identical to the function bodies, but they'll
00138    expand in place, instead of generating a function call.
00139 
00140    I chose these particular functions to be made into macros because
00141    some profiling showed they are called a lot on a typical workload,
00142    and yet they are primarily housekeeping.
00143  */
00144 #if MP_MACRO == 0
00145  void     s_mp_setz(mp_digit *dp, mp_size count); /* zero digits           */
00146  void     s_mp_copy(const mp_digit *sp, mp_digit *dp, mp_size count); /* copy */
00147  void    *s_mp_alloc(size_t nb, size_t ni);       /* general allocator     */
00148  void     s_mp_free(void *ptr);                   /* general free function */
00149 extern unsigned long mp_allocs;
00150 extern unsigned long mp_frees;
00151 extern unsigned long mp_copies;
00152 #else
00153 
00154  /* Even if these are defined as macros, we need to respect the settings
00155     of the MP_MEMSET and MP_MEMCPY configuration options...
00156   */
00157  #if MP_MEMSET == 0
00158   #define  s_mp_setz(dp, count) \
00159        {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=0;}
00160  #else
00161   #define  s_mp_setz(dp, count) memset(dp, 0, (count) * sizeof(mp_digit))
00162  #endif /* MP_MEMSET */
00163 
00164  #if MP_MEMCPY == 0
00165   #define  s_mp_copy(sp, dp, count) \
00166        {int ix;for(ix=0;ix<(count);ix++)(dp)[ix]=(sp)[ix];}
00167  #else
00168   #define  s_mp_copy(sp, dp, count) memcpy(dp, sp, (count) * sizeof(mp_digit))
00169  #endif /* MP_MEMCPY */
00170 
00171  #define  s_mp_alloc(nb, ni)  calloc(nb, ni)
00172  #define  s_mp_free(ptr) {if(ptr) free(ptr);}
00173 #endif /* MP_MACRO */
00174 
00175 mp_err   s_mp_grow(mp_int *mp, mp_size min);   /* increase allocated size */
00176 mp_err   s_mp_pad(mp_int *mp, mp_size min);    /* left pad with zeroes    */
00177 
00178 #if MP_MACRO == 0
00179  void     s_mp_clamp(mp_int *mp);               /* clip leading zeroes     */
00180 #else
00181  #define  s_mp_clamp(mp)\
00182   { mp_size used = MP_USED(mp); \
00183     while (used > 1 && DIGIT(mp, used - 1) == 0) --used; \
00184     MP_USED(mp) = used; \
00185   } 
00186 #endif /* MP_MACRO */
00187 
00188 void     s_mp_exch(mp_int *a, mp_int *b);      /* swap a and b in place   */
00189 
00190 mp_err   s_mp_lshd(mp_int *mp, mp_size p);     /* left-shift by p digits  */
00191 void     s_mp_rshd(mp_int *mp, mp_size p);     /* right-shift by p digits */
00192 mp_err   s_mp_mul_2d(mp_int *mp, mp_digit d);  /* multiply by 2^d in place */
00193 void     s_mp_div_2d(mp_int *mp, mp_digit d);  /* divide by 2^d in place  */
00194 void     s_mp_mod_2d(mp_int *mp, mp_digit d);  /* modulo 2^d in place     */
00195 void     s_mp_div_2(mp_int *mp);               /* divide by 2 in place    */
00196 mp_err   s_mp_mul_2(mp_int *mp);               /* multiply by 2 in place  */
00197 mp_err   s_mp_norm(mp_int *a, mp_int *b, mp_digit *pd); 
00198                                                /* normalize for division  */
00199 mp_err   s_mp_add_d(mp_int *mp, mp_digit d);   /* unsigned digit addition */
00200 mp_err   s_mp_sub_d(mp_int *mp, mp_digit d);   /* unsigned digit subtract */
00201 mp_err   s_mp_mul_d(mp_int *mp, mp_digit d);   /* unsigned digit multiply */
00202 mp_err   s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r);
00203                                              /* unsigned digit divide   */
00204 mp_err   s_mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu);
00205                                                /* Barrett reduction       */
00206 mp_err   s_mp_add(mp_int *a, const mp_int *b); /* magnitude addition      */
00207 mp_err   s_mp_add_3arg(const mp_int *a, const mp_int *b, mp_int *c);
00208 mp_err   s_mp_sub(mp_int *a, const mp_int *b); /* magnitude subtract      */
00209 mp_err   s_mp_sub_3arg(const mp_int *a, const mp_int *b, mp_int *c);
00210 mp_err   s_mp_add_offset(mp_int *a, mp_int *b, mp_size offset);
00211                                                /* a += b * RADIX^offset   */
00212 mp_err   s_mp_mul(mp_int *a, const mp_int *b); /* magnitude multiply      */
00213 #if MP_SQUARE
00214 mp_err   s_mp_sqr(mp_int *a);                  /* magnitude square        */
00215 #else
00216 #define  s_mp_sqr(a) s_mp_mul(a, a)
00217 #endif
00218 mp_err   s_mp_div(mp_int *rem, mp_int *div, mp_int *quot); /* magnitude div */
00219 mp_err   s_mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c);
00220 mp_err   s_mp_2expt(mp_int *a, mp_digit k);    /* a = 2^k                 */
00221 int      s_mp_cmp(const mp_int *a, const mp_int *b); /* magnitude comparison */
00222 int      s_mp_cmp_d(const mp_int *a, mp_digit d); /* magnitude digit compare */
00223 int      s_mp_ispow2(const mp_int *v);         /* is v a power of 2?      */
00224 int      s_mp_ispow2d(mp_digit d);             /* is d a power of 2?      */
00225 
00226 int      s_mp_tovalue(char ch, int r);          /* convert ch to value    */
00227 char     s_mp_todigit(mp_digit val, int r, int low); /* convert val to digit */
00228 int      s_mp_outlen(int bits, int r);          /* output length in bytes */
00229 mp_digit s_mp_invmod_radix(mp_digit P);   /* returns (P ** -1) mod RADIX */
00230 mp_err   s_mp_invmod_odd_m( const mp_int *a, const mp_int *m, mp_int *c);
00231 mp_err   s_mp_invmod_2d(    const mp_int *a, mp_size k,       mp_int *c);
00232 mp_err   s_mp_invmod_even_m(const mp_int *a, const mp_int *m, mp_int *c);
00233 
00234 #ifdef NSS_USE_COMBA
00235 
00236 #define IS_POWER_OF_2(a) ((a) && !((a) & ((a)-1)))
00237 
00238 void s_mp_mul_comba_4(const mp_int *A, const mp_int *B, mp_int *C);
00239 void s_mp_mul_comba_8(const mp_int *A, const mp_int *B, mp_int *C);
00240 void s_mp_mul_comba_16(const mp_int *A, const mp_int *B, mp_int *C);
00241 void s_mp_mul_comba_32(const mp_int *A, const mp_int *B, mp_int *C);
00242 
00243 void s_mp_sqr_comba_4(const mp_int *A, mp_int *B);
00244 void s_mp_sqr_comba_8(const mp_int *A, mp_int *B);
00245 void s_mp_sqr_comba_16(const mp_int *A, mp_int *B);
00246 void s_mp_sqr_comba_32(const mp_int *A, mp_int *B);
00247 
00248 #endif /* end NSS_USE_COMBA */
00249 
00250 /* ------ mpv functions, operate on arrays of digits, not on mp_int's ------ */
00251 #if defined (__OS2__) && defined (__IBMC__)
00252 #define MPI_ASM_DECL __cdecl
00253 #else
00254 #define MPI_ASM_DECL
00255 #endif
00256 
00257 #ifdef MPI_AMD64
00258 
00259 mp_digit MPI_ASM_DECL s_mpv_mul_set_vec64(mp_digit*, mp_digit *, mp_size, mp_digit);
00260 mp_digit MPI_ASM_DECL s_mpv_mul_add_vec64(mp_digit*, const mp_digit*, mp_size, mp_digit);
00261 
00262 /* c = a * b */
00263 #define s_mpv_mul_d(a, a_len, b, c) \
00264        ((unsigned long*)c)[a_len] = s_mpv_mul_set_vec64(c, a, a_len, b)
00265 
00266 /* c += a * b */
00267 #define s_mpv_mul_d_add(a, a_len, b, c) \
00268        ((unsigned long*)c)[a_len] = s_mpv_mul_add_vec64(c, a, a_len, b)
00269 
00270 #else
00271 
00272 void     MPI_ASM_DECL s_mpv_mul_d(const mp_digit *a, mp_size a_len,
00273                                         mp_digit b, mp_digit *c);
00274 void     MPI_ASM_DECL s_mpv_mul_d_add(const mp_digit *a, mp_size a_len,
00275                                             mp_digit b, mp_digit *c);
00276 
00277 #endif
00278 
00279 void     MPI_ASM_DECL s_mpv_mul_d_add_prop(const mp_digit *a,
00280                                                 mp_size a_len, mp_digit b, 
00281                                              mp_digit *c);
00282 void     MPI_ASM_DECL s_mpv_sqr_add_prop(const mp_digit *a,
00283                                                 mp_size a_len,
00284                                                 mp_digit *sqrs);
00285 
00286 mp_err   MPI_ASM_DECL s_mpv_div_2dx1d(mp_digit Nhi, mp_digit Nlo,
00287                             mp_digit divisor, mp_digit *quot, mp_digit *rem);
00288 
00289 /* c += a * b * (MP_RADIX ** offset);  */
00290 #define s_mp_mul_d_add_offset(a, b, c, off) \
00291 (s_mpv_mul_d_add_prop(MP_DIGITS(a), MP_USED(a), b, MP_DIGITS(c) + off), MP_OKAY)
00292 
00293 typedef struct {
00294   mp_int       N;    /* modulus N */
00295   mp_digit     n0prime; /* n0' = - (n0 ** -1) mod MP_RADIX */
00296   mp_size      b;    /* R == 2 ** b,  also b = # significant bits in N */
00297 } mp_mont_modulus;
00298 
00299 mp_err s_mp_mul_mont(const mp_int *a, const mp_int *b, mp_int *c, 
00300                       mp_mont_modulus *mmm);
00301 mp_err s_mp_redc(mp_int *T, mp_mont_modulus *mmm);
00302 
00303 /*
00304  * s_mpi_getProcessorLineSize() returns the size in bytes of the cache line
00305  * if a cache exists, or zero if there is no cache. If more than one
00306  * cache line exists, it should return the smallest line size (which is
00307  * usually the L1 cache).
00308  *
00309  * mp_modexp uses this information to make sure that private key information
00310  * isn't being leaked through the cache.
00311  *
00312  * see mpcpucache.c for the implementation.
00313  */
00314 unsigned long s_mpi_getProcessorLineSize();
00315 
00316 /* }}} */
00317 #endif
00318