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