diff options
author | Ulf Möller <ulf@openssl.org> | 2000-02-26 22:16:47 +0000 |
---|---|---|
committer | Ulf Möller <ulf@openssl.org> | 2000-02-26 22:16:47 +0000 |
commit | 775c63fc023cbe1f2f6c2f512482a52986f55753 (patch) | |
tree | 5e8a75113643d514a70bdcd813b784927f009f8c /doc/crypto/bn_internal.pod | |
parent | db209ec295c358b45332ae48d3041c5b1b25c929 (diff) |
Reorganize bn_mul.c (no bugfix yet), remove obsolete files in BN library.
Diffstat (limited to 'doc/crypto/bn_internal.pod')
-rw-r--r-- | doc/crypto/bn_internal.pod | 228 |
1 files changed, 228 insertions, 0 deletions
diff --git a/doc/crypto/bn_internal.pod b/doc/crypto/bn_internal.pod new file mode 100644 index 0000000000..588874f524 --- /dev/null +++ b/doc/crypto/bn_internal.pod @@ -0,0 +1,228 @@ +=pod + +=head1 NAME + +bn_internal - BIGNUM library internal functions + +=head1 SYNOPSIS + + BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w); + BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, + BN_ULONG w); + void bn_sqr_words(BN_ULONG *rp, BN_ULONG *ap, int num); + BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d); + BN_ULONG bn_add_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp, + int num); + BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp, + int num); + + void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b); + void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b); + void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a); + void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a); + + int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n); + + void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, + int nb); + void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n); + void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, + BN_ULONG *tmp); + void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, + int tn, int n, BN_ULONG *tmp); + void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, + int n2, BN_ULONG *tmp); + void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, + int n2, BN_ULONG *tmp); + + void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp); + void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *tmp); + + void mul(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c); + void mul_add(BN_ULONG r, BN_ULONG a, BN_ULONG w, BN_ULONG c); + void sqr(BN_ULONG r0, BN_ULONG r1, BN_ULONG a); + + BIGNUM *bn_expand(BIGNUM *a, int bits); + BIGNUM *bn_wexpand(BIGNUM *a, int n); + BIGNUM *bn_expand2(BIGNUM *a, int n); + void bn_fix_top(BIGNUM *a); + + void bn_check_top(BIGNUM *a); + void bn_print(BIGNUM *a); + void bn_dump(BN_ULONG *d, int n); + void bn_set_max(BIGNUM *a); + void bn_set_high(BIGNUM *r, BIGNUM *a, int n); + void bn_set_low(BIGNUM *r, BIGNUM *a, int n); + +=head1 DESCRIPTION + +This page documents the internal functions used by the OpenSSL +B<BIGNUM> implementation. They are described here to facilitate +debugging and extending the library. They are I<not> to be used by +applications. + +=head2 The BIGNUM structure + + typedef struct bignum_st + { + int top; /* index of last used d (most significant word) */ + BN_ULONG *d; /* pointer to an array of 'BITS2' bit chunks */ + int max; /* size of the d array */ + int neg; /* sign */ + } BIGNUM; + +The big number is stored in B<d>, a malloc()ed array of B<BN_ULONG>s, +least significant first. A B<BN_ULONG> can be either 16, 32 or 64 bits +in size (B<BITS2>), depending on the 'number of bits' specified in +C<openssl/bn.h>. + +B<max> is the size of the B<d> array that has been allocated. B<top> +is the 'last' entry being used, so for a value of 4, bn.d[0]=4 and +bn.top=1. B<neg> is 1 if the number is negative. When a B<BIGNUM> is +B<0>, the B<d> field can be B<NULL> and B<top> == B<0>. + +Various routines in this library require the use of temporary +B<BIGNUM> variables during their execution. Since dynamic memory +allocation to create B<BIGNUM>s is rather expensive when used in +conjunction with repeated subroutine calls, the B<BN_CTX> structure is +used. This structure contains B<BN_CTX_NUM> B<BIGNUM>s. +B<BN_CTX_NUM> is the maximum number of temporary B<BIGNUM>s any +publicly exported function will use. + + #define BN_CTX_NUM 12 + typedef struct bignum_ctx + { + int tos; /* top of stack */ + BIGNUM *bn[BN_CTX_NUM]; /* The variables */ + } BN_CTX; + +B<tos> is the index of the first unused B<BIGNUM> in the B<bn> array. + +=head2 Low-level arithmetic operations + +These functions are implemented in C and for several platforms in +assembly language: + +bn_mul_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num> word +arrays B<rp> and B<ap>. It computes B<ap> * B<w>, places the result +in B<rp>, and returns the high word (carry). + +bn_mul_add_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num> +word arrays B<rp> and B<ap>. It computes B<ap> * B<w> + B<rp>, places +the result in B<rp>, and returns the high word (carry). + +bn_sqr_words(B<rp>, B<ap>, B<n>) operates on the B<num> word array +B<ap> and the 2*B<num> word array B<ap>. It computes B<ap> * B<ap> +word-wise, and places the low and high bytes of the result in B<rp>. + +bn_div_words(B<h>, B<l>, B<d>) divides the two word number (B<h>,B<l>) +by B<d> and returns the result. + +bn_add_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word +arrays B<ap>, B<bp> and B<rp>. It computes B<ap> + B<bp>, places the +result in B<rp>, and returns the high word (carry). + +bn_sub_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word +arrays B<ap>, B<bp> and B<rp>. It computes B<ap> - B<bp>, places the +result in B<rp>, and returns the carry (1 if B<bp> E<gt> B<ap>, 0 +otherwise). + +bn_mul_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and +B<b> and the 8 word array B<r>. It computes B<a>*B<b> and places the +result in B<r>. + +bn_mul_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and +B<b> and the 16 word array B<r>. It computes B<a>*B<b> and places the +result in B<r>. + +bn_sqr_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and +B<b> and the 8 word array B<r>. + +bn_sqr_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and +B<b> and the 16 word array B<r>. + +The following functions are implemented in C: + +bn_cmp_words(B<a>, B<b>, B<n>) operates on the B<n> word arrays B<a> +and B<b>. It returns 1, 0 and -1 if B<a> is greater than, equal and +less than B<b>. + +bn_mul_normal(B<r>, B<a>, B<na>, B<b>, B<nb>) operates on the B<na> +word array B<a>, the B<nb> word array B<b> and the B<na>+B<nb> word +array B<r>. It computes B<a>*B<b> and places the result in B<r>. + +bn_mul_low_normal(B<r>, B<a>, B<b>, B<n>) operates on the B<n> word +arrays B<r>, B<a> und B<b>. It computes the B<n> low words of +B<a>*B<b> and places the result in B<r>. + +bn_mul_recursive(B<r>, B<a>, B<b>, B<n2>, B<t>) operates on the B<n2> +word arrays B<a> and B<b> and the 2*B<n2> word arrays B<r> and B<t>. +B<n2> must be a power of 2. It computes B<a>*B<b> and places the +result in B<r>. + +bn_mul_part_recursive(B<r>, B<a>, B<b>, B<tn>, B<n>, B<tmp>) operates +on the B<n>+B<tn> word arrays B<a> and B<b> and the 4*B<n> word arrays +B<r> and B<tmp>. + +bn_mul_low_recursive(B<r>, B<a>, B<b>, B<n2>, B<tmp>) operates on the +B<n2> word arrays B<r> and B<tmp> and the B<n2>/2 word arrays B<a> +and B<b>. + +bn_mul_high(B<r>, B<a>, B<b>, B<l>, B<n2>, B<tmp>) operates on the +B<n2> word arrays B<r>, B<a>, B<b> and B<l> (?) and the 3*B<n2> word +array B<tmp>. + +BN_mul() calls bn_mul_normal(), or an optimized implementation if the +factors have the same size: bn_mul_comba8() is used if they are 8 +words long, bn_mul_recursive() if they are larger than +B<BN_MULL_SIZE_NORMAL> and the size is an exact multiple of the word +size, and bn_mul_part_recursive() for others that are larger than +B<BN_MULL_SIZE_NORMAL>. + +bn_sqr_normal(B<r>, B<a>, B<n>, B<tmp>) operates on the B<n> word array +B<a> and the 2*B<n> word arrays B<tmp> and B<r>. + +The implementations use the following macros which, depending on the +architecture, may use "long long" C operations or inline assembler. +They are defined in C<bn_lcl.h>. + +mul(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<c> and places the +low word of the result in B<r> and the high word in B<c>. + +mul_add(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<r>+B<c> and +places the low word of the result in B<r> and the high word in B<c>. + +sqr(B<r0>, B<r1>, B<a>) computes B<a>*B<a> and places the low word +of the result in B<r0> and the high word in B<r1>. + +=head2 Size changes + +bn_expand() ensures that B<b> has enough space for a B<bits> bit +number. bn_wexpand() ensures that B<b> has enough space for an +B<n> word number. If the number has to be expanded, both macros +call bn_expand2(), which allocates a new B<d> array and copies the +data. They return B<NULL> on error, B<b> otherwise. + +The bn_fix_top() macro reduces B<a-E<gt>top> to most significant +non-zero word when B<a> has shrunk. + +=head2 Debugging + +bn_check_top() verifies that C<((a)->top E<gt>= 0 && (a)-E<gt>top +E<lt>= (a)-E<gt>max)>. A violation will cause the program to abort. + +bn_print() prints B<a> to stderr. bn_dump() prints B<n> words at B<d> +(in reverse order, i.e. most significant word first) to stderr. + +bn_set_max() makes B<a> a static number with a B<max> of its current size. +This is used by bn_set_low() and bn_set_high() to make B<r> a read-only +B<BIGNUM> that contains the B<n> lower or higher words of B<a>. + +If B<BN_DEBUG> is not defined, bn_check_top(), bn_print(), bn_dump() +and bn_set_max() are defined as empty macros. + +=head1 SEE ALSO + +L<bn(3)|bn(3)> + +=cut |