1  /* crypto/bn/bn_lcl.h */


2  /* Copyright (C) 19951998 Eric Young (eay@cryptsoft.com)


3  * All rights reserved.


4  *


5  * This package is an SSL implementation written


6  * by Eric Young (eay@cryptsoft.com).


7  * The implementation was written so as to conform with Netscapes SSL.


8  *


9  * This library is free for commercial and noncommercial use as long as


10  * the following conditions are aheared to. The following conditions


11  * apply to all code found in this distribution, be it the RC4, RSA,


12  * lhash, DES, etc., code; not just the SSL code. The SSL documentation


13  * included with this distribution is covered by the same copyright terms


14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).


15  *


16  * Copyright remains Eric Young's, and as such any Copyright notices in


17  * the code are not to be removed.


18  * If this package is used in a product, Eric Young should be given attribution


19  * as the author of the parts of the library used.


20  * This can be in the form of a textual message at program startup or


21  * in documentation (online or textual) provided with the package.


22  *


23  * Redistribution and use in source and binary forms, with or without


24  * modification, are permitted provided that the following conditions


25  * are met:


26  * 1. Redistributions of source code must retain the copyright


27  * notice, this list of conditions and the following disclaimer.


28  * 2. Redistributions in binary form must reproduce the above copyright


29  * notice, this list of conditions and the following disclaimer in the


30  * documentation and/or other materials provided with the distribution.


31  * 3. All advertising materials mentioning features or use of this software


32  * must display the following acknowledgement:


33  * "This product includes cryptographic software written by


34  * Eric Young (eay@cryptsoft.com)"


35  * The word 'cryptographic' can be left out if the rouines from the library


36  * being used are not cryptographic related :).


37  * 4. If you include any Windows specific code (or a derivative thereof) from


38  * the apps directory (application code) you must include an acknowledgement:


39  * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"


40  *


41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND


42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE


43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE


44  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE


45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL


46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS


47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)


48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT


49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY


50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF


51  * SUCH DAMAGE.


52  *


53  * The licence and distribution terms for any publically available version or


54  * derivative of this code cannot be changed. i.e. this code cannot simply be


55  * copied and put under another distribution licence


56  * [including the GNU Public Licence.]


57  */


58  /* ====================================================================


59  * Copyright (c) 19982000 The OpenSSL Project. All rights reserved.


60  *


61  * Redistribution and use in source and binary forms, with or without


62  * modification, are permitted provided that the following conditions


63  * are met:


64  *


65  * 1. Redistributions of source code must retain the above copyright


66  * notice, this list of conditions and the following disclaimer.


67  *


68  * 2. Redistributions in binary form must reproduce the above copyright


69  * notice, this list of conditions and the following disclaimer in


70  * the documentation and/or other materials provided with the


71  * distribution.


72  *


73  * 3. All advertising materials mentioning features or use of this


74  * software must display the following acknowledgment:


75  * "This product includes software developed by the OpenSSL Project


76  * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"


77  *


78  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to


79  * endorse or promote products derived from this software without


80  * prior written permission. For written permission, please contact


81  * opensslcore@openssl.org.


82  *


83  * 5. Products derived from this software may not be called "OpenSSL"


84  * nor may "OpenSSL" appear in their names without prior written


85  * permission of the OpenSSL Project.


86  *


87  * 6. Redistributions of any form whatsoever must retain the following


88  * acknowledgment:


89  * "This product includes software developed by the OpenSSL Project


90  * for use in the OpenSSL Toolkit (http://www.openssl.org/)"


91  *


92  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY


93  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE


94  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR


95  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR


96  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,


97  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT


98  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;


99  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)


100  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,


101  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)


102  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED


103  * OF THE POSSIBILITY OF SUCH DAMAGE.


104  * ====================================================================


105  *


106  * This product includes cryptographic software written by Eric Young


107  * (eay@cryptsoft.com). This product includes software written by Tim


108  * Hudson (tjh@cryptsoft.com).


109  *


110  */


111 


112  #ifndef HEADER_BN_LCL_H


113  #define HEADER_BN_LCL_H


114 


115  #include "bn.h"


116 


117  #ifdef __cplusplus


118  extern "C" {


119  #endif


120 


121 


122  /*


123  * BN_window_bits_for_exponent_size  macro for sliding window mod_exp functions


124  *


125  *


126  * For window size 'w' (w >= 2) and a random 'b' bits exponent,


127  * the number of multiplications is a constant plus on average


128  *


129  * 2^(w1) + (bw)/(w+1);


130  *


131  * here 2^(w1) is for precomputing the table (we actually need


132  * entries only for windows that have the lowest bit set), and


133  * (bw)/(w+1) is an approximation for the expected number of


134  * wbit windows, not counting the first one.


135  *


136  * Thus we should use


137  *


138  * w >= 6 if b > 671


139  * w = 5 if 671 > b > 239


140  * w = 4 if 239 > b > 79


141  * w = 3 if 79 > b > 23


142  * w <= 2 if 23 > b


143  *


144  * (with draws in between). Very small exponents are often selected


145  * with low Hamming weight, so we use w = 1 for b <= 23.


146  */


147  #if 1


148  #define BN_window_bits_for_exponent_size(b) \


149  ((b) > 671 ? 6 : \


150  (b) > 239 ? 5 : \


151  (b) > 79 ? 4 : \


152  (b) > 23 ? 3 : 1)


153  #else


154  /* Old SSLeay/OpenSSL table.


155  * Maximum window size was 5, so this table differs for b==1024;


156  * but it coincides for other interesting values (b==160, b==512).


157  */


158  #define BN_window_bits_for_exponent_size(b) \


159  ((b) > 255 ? 5 : \


160  (b) > 127 ? 4 : \


161  (b) > 17 ? 3 : 1)


162  #endif


163 


164 


165 


166  /* Pentium pro 16,16,16,32,64 */


167  /* Alpha 16,16,16,16.64 */


168  #define BN_MULL_SIZE_NORMAL (16) /* 32 */


169  #define BN_MUL_RECURSIVE_SIZE_NORMAL (16) /* 32 less than */


170  #define BN_SQR_RECURSIVE_SIZE_NORMAL (16) /* 32 */


171  #define BN_MUL_LOW_RECURSIVE_SIZE_NORMAL (32) /* 32 */


172  #define BN_MONT_CTX_SET_SIZE_WORD (64) /* 32 */


173 


174  #if !defined(NO_ASM) && !defined(NO_INLINE_ASM) && !defined(PEDANTIC)


175  /*


176  * BN_UMULT_HIGH section.


177  *


178  * No, I'm not trying to overwhelm you when stating that the


179  * product of Nbit numbers is 2*N bits wide:) No, I don't expect


180  * you to be impressed when I say that if the compiler doesn't


181  * support 2*N integer type, then you have to replace every N*N


182  * multiplication with 4 (N/2)*(N/2) accompanied by some shifts


183  * and additions which unavoidably results in severe performance


184  * penalties. Of course provided that the hardware is capable of


185  * producing 2*N result... That's when you normally start


186  * considering assembler implementation. However! It should be


187  * pointed out that some CPUs (most notably Alpha, PowerPC and


188  * upcoming IA64 family:) provide *separate* instruction


189  * calculating the upper half of the product placing the result


190  * into a general purpose register. Now *if* the compiler supports


191  * inline assembler, then it's not impossible to implement the


192  * "bignum" routines (and have the compiler optimize 'em)


193  * exhibiting "native" performance in C. That's what BN_UMULT_HIGH


194  * macro is about:)


195  *


196  * <appro@fy.chalmers.se>


197  */


198  # if defined(__alpha) && (defined(SIXTY_FOUR_BIT_LONG)  defined(SIXTY_FOUR_BIT))


199  # if defined(__DECC)


200  # include <c_asm.h>


201  # define BN_UMULT_HIGH(a,b) (BN_ULONG)asm("umulh %a0,%a1,%v0",(a),(b))


202  # elif defined(__GNUC__)


203  # define BN_UMULT_HIGH(a,b) ({ \


204  register BN_ULONG ret; \


205  asm ("umulh %1,%2,%0" \


206  : "=r"(ret) \


207  : "r"(a), "r"(b)); \


208  ret; })


209  # endif /* compiler */


210  # elif defined(_ARCH_PPC) && defined(__64BIT__) && defined(SIXTY_FOUR_BIT_LONG)


211  # if defined(__GNUC__)


212  # define BN_UMULT_HIGH(a,b) ({ \


213  register BN_ULONG ret; \


214  asm ("mulhdu %0,%1,%2" \


215  : "=r"(ret) \


216  : "r"(a), "r"(b)); \


217  ret; })


218  # endif /* compiler */


219  # endif /* cpu */


220  #endif /* NO_ASM */


221 


222  /*************************************************************


223  * Using the long long type


224  */


225  #define Lw(t) (((BN_ULONG)(t))&BN_MASK2)


226  #define Hw(t) (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2)


227 


228  /* This is used for internal error checking and is not normally used */


229  #ifdef BN_DEBUG


230  # include <assert.h>


231  # define bn_check_top(a) assert ((a)>top >= 0 && (a)>top <= (a)>dmax);


232  #else


233  # define bn_check_top(a)


234  #endif


235 


236  /* This macro is to add extra stuff for development checking */


237  #ifdef BN_DEBUG


238  #define bn_set_max(r) ((r)>max=(r)>top,BN_set_flags((r),BN_FLG_STATIC_DATA))


239  #else


240  #define bn_set_max(r)


241  #endif


242 


243  /* These macros are used to 'take' a section of a bignum for read only use */


244  #define bn_set_low(r,a,n) \


245  { \


246  (r)>top=((a)>top > (n))?(n):(a)>top; \


247  (r)>d=(a)>d; \


248  (r)>neg=(a)>neg; \


249  (r)>flags=BN_FLG_STATIC_DATA; \


250  bn_set_max(r); \


251  }


252 


253  #define bn_set_high(r,a,n) \


254  { \


255  if ((a)>top > (n)) \


256  { \


257  (r)>top=(a)>topn; \


258  (r)>d= &((a)>d[n]); \


259  } \


260  else \


261  (r)>top=0; \


262  (r)>neg=(a)>neg; \


263  (r)>flags=BN_FLG_STATIC_DATA; \


264  bn_set_max(r); \


265  }


266 


267  #ifdef BN_LLONG


268  #define mul_add(r,a,w,c) { \


269  BN_ULLONG t; \


270  t=(BN_ULLONG)w * (a) + (r) + (c); \


271  (r)= Lw(t); \


272  (c)= Hw(t); \


273  }


274 


275  #define mul(r,a,w,c) { \


276  BN_ULLONG t; \


277  t=(BN_ULLONG)w * (a) + (c); \


278  (r)= Lw(t); \


279  (c)= Hw(t); \


280  }


281 


282  #define sqr(r0,r1,a) { \


283  BN_ULLONG t; \


284  t=(BN_ULLONG)(a)*(a); \


285  (r0)=Lw(t); \


286  (r1)=Hw(t); \


287  }


288 


289  #elif defined(BN_UMULT_HIGH)


290  #define mul_add(r,a,w,c) { \


291  BN_ULONG high,low,ret,tmp=(a); \


292  ret = (r); \


293  high= BN_UMULT_HIGH(w,tmp); \


294  ret += (c); \


295  low = (w) * tmp; \


296  (c) = (ret<(c))?1:0; \


297  (c) += high; \


298  ret += low; \


299  (c) += (ret<low)?1:0; \


300  (r) = ret; \


301  }


302 


303  #define mul(r,a,w,c) { \


304  BN_ULONG high,low,ret,ta=(a); \


305  low = (w) * ta; \


306  high= BN_UMULT_HIGH(w,ta); \


307  ret = low + (c); \


308  (c) = high; \


309  (c) += (ret<low)?1:0; \


310  (r) = ret; \


311  }


312 


313  #define sqr(r0,r1,a) { \


314  BN_ULONG tmp=(a); \


315  (r0) = tmp * tmp; \


316  (r1) = BN_UMULT_HIGH(tmp,tmp); \


317  }


318 


319  #else


320  /*************************************************************


321  * No long long type


322  */


323 


324  #define LBITS(a) ((a)&BN_MASK2l)


325  #define HBITS(a) (((a)>>BN_BITS4)&BN_MASK2l)


326  #define L2HBITS(a) ((BN_ULONG)((a)&BN_MASK2l)<<BN_BITS4)


327 


328  #define LLBITS(a) ((a)&BN_MASKl)


329  #define LHBITS(a) (((a)>>BN_BITS2)&BN_MASKl)


330  #define LL2HBITS(a) ((BN_ULLONG)((a)&BN_MASKl)<<BN_BITS2)


331 


332  #define mul64(l,h,bl,bh) \


333  { \


334  BN_ULONG m,m1,lt,ht; \


335  \


336  lt=l; \


337  ht=h; \


338  m =(bh)*(lt); \


339  lt=(bl)*(lt); \


340  m1=(bl)*(ht); \


341  ht =(bh)*(ht); \


342  m=(m+m1)&BN_MASK2; if (m < m1) ht+=L2HBITS(1L); \


343  ht+=HBITS(m); \


344  m1=L2HBITS(m); \


345  lt=(lt+m1)&BN_MASK2; if (lt < m1) ht++; \


346  (l)=lt; \


347  (h)=ht; \


348  }


349 


350  #define sqr64(lo,ho,in) \


351  { \


352  BN_ULONG l,h,m; \


353  \


354  h=(in); \


355  l=LBITS(h); \


356  h=HBITS(h); \


357  m =(l)*(h); \


358  l*=l; \


359  h*=h; \


360  h+=(m&BN_MASK2h1)>>(BN_BITS41); \


361  m =(m&BN_MASK2l)<<(BN_BITS4+1); \


362  l=(l+m)&BN_MASK2; if (l < m) h++; \


363  (lo)=l; \


364  (ho)=h; \


365  }


366 


367  #define mul_add(r,a,bl,bh,c) { \


368  BN_ULONG l,h; \


369  \


370  h= (a); \


371  l=LBITS(h); \


372  h=HBITS(h); \


373  mul64(l,h,(bl),(bh)); \


374  \


375  /* nonmultiply part */ \


376  l=(l+(c))&BN_MASK2; if (l < (c)) h++; \


377  (c)=(r); \


378  l=(l+(c))&BN_MASK2; if (l < (c)) h++; \


379  (c)=h&BN_MASK2; \


380  (r)=l; \


381  }


382 


383  #define mul(r,a,bl,bh,c) { \


384  BN_ULONG l,h; \


385  \


386  h= (a); \


387  l=LBITS(h); \


388  h=HBITS(h); \


389  mul64(l,h,(bl),(bh)); \


390  \


391  /* nonmultiply part */ \


392  l+=(c); if ((l&BN_MASK2) < (c)) h++; \


393  (c)=h&BN_MASK2; \


394  (r)=l&BN_MASK2; \


395  }


396  #endif /* !BN_LLONG */


397 


398  void bn_mul_normal(BN_ULONG *r,BN_ULONG *a,int na,BN_ULONG *b,int nb);


399  void bn_mul_comba8(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b);


400  void bn_mul_comba4(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b);


401  void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp);


402  void bn_sqr_comba8(BN_ULONG *r,BN_ULONG *a);


403  void bn_sqr_comba4(BN_ULONG *r,BN_ULONG *a);


404  int bn_cmp_words(BN_ULONG *a,BN_ULONG *b,int n);


405  void bn_mul_recursive(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b,int n2,BN_ULONG *t);


406  void bn_mul_part_recursive(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b,


407  int tn, int n,BN_ULONG *t);


408  void bn_sqr_recursive(BN_ULONG *r,BN_ULONG *a, int n2, BN_ULONG *t);


409  void bn_mul_low_normal(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b, int n);


410  void bn_mul_low_recursive(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b,int n2,


411  BN_ULONG *t);


412  void bn_mul_high(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b,BN_ULONG *l,int n2,


413  BN_ULONG *t);


414 


415  #ifdef __cplusplus


416  }


417  #endif


418 


419  #endif

