1=pod 2 3=head1 NAME 4 5bn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words, 6bn_add_words, bn_sub_words, bn_mul_comba4, bn_mul_comba8, 7bn_sqr_comba4, bn_sqr_comba8, bn_cmp_words, bn_mul_normal, 8bn_mul_low_normal, bn_mul_recursive, bn_mul_part_recursive, 9bn_mul_low_recursive, bn_mul_high, bn_sqr_normal, bn_sqr_recursive, 10bn_expand, bn_wexpand, bn_expand2, bn_fix_top, bn_check_top, 11BN_print, bn_dump, bn_set_max, bn_set_high, bn_set_low - BIGNUM 12library internal functions 13 14=head1 SYNOPSIS 15 16 #include <openssl/bn.h> 17 18 BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w); 19 BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, 20 BN_ULONG w); 21 void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num); 22 BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d); 23 BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp, 24 int num); 25 BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp, 26 int num); 27 28 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b); 29 void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b); 30 void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a); 31 void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a); 32 33 int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n); 34 35 void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, 36 int nb); 37 void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n); 38 void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 39 int dna,int dnb,BN_ULONG *tmp); 40 void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, 41 int n, int tna,int tnb, BN_ULONG *tmp); 42 void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, 43 int n2, BN_ULONG *tmp); 44 void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, 45 int n2, BN_ULONG *tmp); 46 47 void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp); 48 void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp); 49 50 void mul(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c); 51 void mul_add(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c); 52 void sqr(BN_ULONG r0, BN_ULONG r1, BN_ULONG a); 53 54 BIGNUM *bn_expand(BIGNUM *a, int bits); 55 BIGNUM *bn_wexpand(BIGNUM *a, int n); 56 BIGNUM *bn_expand2(BIGNUM *a, int n); 57 void bn_fix_top(BIGNUM *a); 58 59 void bn_check_top(BIGNUM *a); 60 void BN_print(BIGNUM *a); 61 void bn_dump(BN_ULONG *d, int n); 62 void bn_set_max(BIGNUM *a); 63 void bn_set_high(BIGNUM *r, BIGNUM *a, int n); 64 void bn_set_low(BIGNUM *r, BIGNUM *a, int n); 65 66=head1 DESCRIPTION 67 68This page documents the internal functions used by the OpenSSL 69B<BIGNUM> implementation. They are described here to facilitate 70debugging and extending the library. They are I<not> to be used by 71applications. 72 73=head2 The BIGNUM structure 74 75 typedef struct bignum_st BIGNUM; 76 77 struct bignum_st 78 { 79 BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */ 80 int top; /* Index of last used d +1. */ 81 /* The next are internal book keeping for bn_expand. */ 82 int dmax; /* Size of the d array. */ 83 int neg; /* one if the number is negative */ 84 int flags; 85 }; 86 87 88The integer value is stored in B<d>, a malloc()ed array of words (B<BN_ULONG>), 89least significant word first. A B<BN_ULONG> can be either 16, 32 or 64 bits 90in size, depending on the 'number of bits' (B<BITS2>) specified in 91C<openssl/bn.h>. 92 93B<dmax> is the size of the B<d> array that has been allocated. B<top> 94is the number of words being used, so for a value of 4, bn.d[0]=4 and 95bn.top=1. B<neg> is 1 if the number is negative. When a B<BIGNUM> is 96B<0>, the B<d> field can be B<NULL> and B<top> == B<0>. 97 98B<flags> is a bit field of flags which are defined in C<openssl/bn.h>. The 99flags begin with B<BN_FLG_>. The macros BN_set_flags(b,n) and 100BN_get_flags(b,n) exist to enable or fetch flag(s) B<n> from B<BIGNUM> 101structure B<b>. 102 103Various routines in this library require the use of temporary 104B<BIGNUM> variables during their execution. Since dynamic memory 105allocation to create B<BIGNUM>s is rather expensive when used in 106conjunction with repeated subroutine calls, the B<BN_CTX> structure is 107used. This structure contains B<BN_CTX_NUM> B<BIGNUM>s, see 108L<BN_CTX_start(3)|BN_CTX_start(3)>. 109 110=head2 Low-level arithmetic operations 111 112These functions are implemented in C and for several platforms in 113assembly language: 114 115bn_mul_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num> word 116arrays B<rp> and B<ap>. It computes B<ap> * B<w>, places the result 117in B<rp>, and returns the high word (carry). 118 119bn_mul_add_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num> 120word arrays B<rp> and B<ap>. It computes B<ap> * B<w> + B<rp>, places 121the result in B<rp>, and returns the high word (carry). 122 123bn_sqr_words(B<rp>, B<ap>, B<n>) operates on the B<num> word array 124B<ap> and the 2*B<num> word array B<ap>. It computes B<ap> * B<ap> 125word-wise, and places the low and high bytes of the result in B<rp>. 126 127bn_div_words(B<h>, B<l>, B<d>) divides the two word number (B<h>,B<l>) 128by B<d> and returns the result. 129 130bn_add_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word 131arrays B<ap>, B<bp> and B<rp>. It computes B<ap> + B<bp>, places the 132result in B<rp>, and returns the high word (carry). 133 134bn_sub_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word 135arrays B<ap>, B<bp> and B<rp>. It computes B<ap> - B<bp>, places the 136result in B<rp>, and returns the carry (1 if B<bp> E<gt> B<ap>, 0 137otherwise). 138 139bn_mul_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and 140B<b> and the 8 word array B<r>. It computes B<a>*B<b> and places the 141result in B<r>. 142 143bn_mul_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and 144B<b> and the 16 word array B<r>. It computes B<a>*B<b> and places the 145result in B<r>. 146 147bn_sqr_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and 148B<b> and the 8 word array B<r>. 149 150bn_sqr_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and 151B<b> and the 16 word array B<r>. 152 153The following functions are implemented in C: 154 155bn_cmp_words(B<a>, B<b>, B<n>) operates on the B<n> word arrays B<a> 156and B<b>. It returns 1, 0 and -1 if B<a> is greater than, equal and 157less than B<b>. 158 159bn_mul_normal(B<r>, B<a>, B<na>, B<b>, B<nb>) operates on the B<na> 160word array B<a>, the B<nb> word array B<b> and the B<na>+B<nb> word 161array B<r>. It computes B<a>*B<b> and places the result in B<r>. 162 163bn_mul_low_normal(B<r>, B<a>, B<b>, B<n>) operates on the B<n> word 164arrays B<r>, B<a> and B<b>. It computes the B<n> low words of 165B<a>*B<b> and places the result in B<r>. 166 167bn_mul_recursive(B<r>, B<a>, B<b>, B<n2>, B<dna>, B<dnb>, B<t>) operates 168on the word arrays B<a> and B<b> of length B<n2>+B<dna> and B<n2>+B<dnb> 169(B<dna> and B<dnb> are currently allowed to be 0 or negative) and the 2*B<n2> 170word arrays B<r> and B<t>. B<n2> must be a power of 2. It computes 171B<a>*B<b> and places the result in B<r>. 172 173bn_mul_part_recursive(B<r>, B<a>, B<b>, B<n>, B<tna>, B<tnb>, B<tmp>) 174operates on the word arrays B<a> and B<b> of length B<n>+B<tna> and 175B<n>+B<tnb> and the 4*B<n> word arrays B<r> and B<tmp>. 176 177bn_mul_low_recursive(B<r>, B<a>, B<b>, B<n2>, B<tmp>) operates on the 178B<n2> word arrays B<r> and B<tmp> and the B<n2>/2 word arrays B<a> 179and B<b>. 180 181bn_mul_high(B<r>, B<a>, B<b>, B<l>, B<n2>, B<tmp>) operates on the 182B<n2> word arrays B<r>, B<a>, B<b> and B<l> (?) and the 3*B<n2> word 183array B<tmp>. 184 185BN_mul() calls bn_mul_normal(), or an optimized implementation if the 186factors have the same size: bn_mul_comba8() is used if they are 8 187words long, bn_mul_recursive() if they are larger than 188B<BN_MULL_SIZE_NORMAL> and the size is an exact multiple of the word 189size, and bn_mul_part_recursive() for others that are larger than 190B<BN_MULL_SIZE_NORMAL>. 191 192bn_sqr_normal(B<r>, B<a>, B<n>, B<tmp>) operates on the B<n> word array 193B<a> and the 2*B<n> word arrays B<tmp> and B<r>. 194 195The implementations use the following macros which, depending on the 196architecture, may use "long long" C operations or inline assembler. 197They are defined in C<bn_lcl.h>. 198 199mul(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<c> and places the 200low word of the result in B<r> and the high word in B<c>. 201 202mul_add(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<r>+B<c> and 203places the low word of the result in B<r> and the high word in B<c>. 204 205sqr(B<r0>, B<r1>, B<a>) computes B<a>*B<a> and places the low word 206of the result in B<r0> and the high word in B<r1>. 207 208=head2 Size changes 209 210bn_expand() ensures that B<b> has enough space for a B<bits> bit 211number. bn_wexpand() ensures that B<b> has enough space for an 212B<n> word number. If the number has to be expanded, both macros 213call bn_expand2(), which allocates a new B<d> array and copies the 214data. They return B<NULL> on error, B<b> otherwise. 215 216The bn_fix_top() macro reduces B<a-E<gt>top> to point to the most 217significant non-zero word plus one when B<a> has shrunk. 218 219=head2 Debugging 220 221bn_check_top() verifies that C<((a)-E<gt>top E<gt>= 0 && (a)-E<gt>top 222E<lt>= (a)-E<gt>dmax)>. A violation will cause the program to abort. 223 224BN_print() prints B<a> to stderr. bn_dump() prints B<n> words at B<d> 225(in reverse order, i.e. most significant word first) to stderr. 226 227bn_set_max() makes B<a> a static number with a B<dmax> of its current size. 228This is used by bn_set_low() and bn_set_high() to make B<r> a read-only 229B<BIGNUM> that contains the B<n> low or high words of B<a>. 230 231If B<BN_DEBUG> is not defined, bn_check_top(), BN_print(), bn_dump() 232and bn_set_max() are defined as empty macros. 233 234=head1 SEE ALSO 235 236L<bn(3)|bn(3)> 237 238=cut 239