bninternal(3) OpenSSL bninternal(3)

NAME
       bnmulwords, bnmuladdwords, bnsqrwords, bndivwords,
       bnaddwords, bnsubwords, bnmulcomba4, bnmulcomba8,
       bnsqrcomba4, bnsqrcomba8, bncmpwords, bnmulnormal,
       bnmullownormal, bnmulrecursive, bnmulpartrecursive,
       bnmullowrecursive, bnmulhigh, bnsqrnormal, bnsqrrecursive,
       bnexpand, bnwexpand, bnexpand2, bnfixtop, bnchecktop, bnprint,
       bndump, bnsetmax, bnsethigh, bnsetlow - BIGNUM library internal
       functions

SYNOPSIS
        BNULONG bnmulwords(BNULONG *rp, BNULONG *ap, int num, BNULONG w);
        BNULONG bnmuladdwords(BNULONG *rp, BNULONG *ap, int num,
          BNULONG w);
        void     bnsqrwords(BNULONG *rp, BNULONG *ap, int num);
        BNULONG bndivwords(BNULONG h, BNULONG l, BNULONG d);
        BNULONG bnaddwords(BNULONG *rp, BNULONG *ap, BNULONG *bp,
          int num);
        BNULONG bnsubwords(BNULONG *rp, BNULONG *ap, BNULONG *bp,
          int num);

        void bnmulcomba4(BNULONG *r, BNULONG *a, BNULONG *b);
        void bnmulcomba8(BNULONG *r, BNULONG *a, BNULONG *b);
        void bnsqrcomba4(BNULONG *r, BNULONG *a);
        void bnsqrcomba8(BNULONG *r, BNULONG *a);

        int bncmpwords(BNULONG *a, BNULONG *b, int n);

        void bnmulnormal(BNULONG *r, BNULONG *a, int na, BNULONG *b,
          int nb);
        void bnmullownormal(BNULONG *r, BNULONG *a, BNULONG *b, int n);
        void bnmulrecursive(BNULONG *r, BNULONG *a, BNULONG *b, int n2,
          int dna,int dnb,BNULONG *tmp);
        void bnmulpartrecursive(BNULONG *r, BNULONG *a, BNULONG *b,
          int n, int tna,int tnb, BNULONG *tmp);
        void bnmullowrecursive(BNULONG *r, BNULONG *a, BNULONG *b,
          int n2, BNULONG *tmp);
        void bnmulhigh(BNULONG *r, BNULONG *a, BNULONG *b, BNULONG *l,
          int n2, BNULONG *tmp);

        void bnsqrnormal(BNULONG *r, BNULONG *a, int n, BNULONG *tmp);
        void bnsqrrecursive(BNULONG *r, BNULONG *a, int n2, BNULONG *tmp);

        void mul(BNULONG r, BNULONG a, BNULONG w, BNULONG c);
        void muladd(BNULONG r, BNULONG a, BNULONG w, BNULONG c);
        void sqr(BNULONG r0, BNULONG r1, BNULONG a);

        BIGNUM *bnexpand(BIGNUM *a, int bits);
        BIGNUM *bnwexpand(BIGNUM *a, int n);
        BIGNUM *bnexpand2(BIGNUM *a, int n);
        void bnfixtop(BIGNUM *a);

        void bnchecktop(BIGNUM *a);
        void bnprint(BIGNUM *a);
        void bndump(BNULONG *d, int n);
        void bnsetmax(BIGNUM *a);
        void bnsethigh(BIGNUM *r, BIGNUM *a, int n);
        void bnsetlow(BIGNUM *r, BIGNUM *a, int n);

DESCRIPTION
       This page documents the internal functions used by the OpenSSL BBIIGGNNUUMM
       implementation. They are described here to facilitate debugging and
       extending the library. They are not to be used by applications.

       The BIGNUM structure
        typedef struct bignumst
               {
               int top;      /* index of last used d (most significant word) */
               BNULONG *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 dd, a malloc()ed array of BBNNUULLOONNGGs, least
       significant first. A BBNNUULLOONNGG can be either 16, 32 or 64 bits in size
       (BBIITTSS22), depending on the 'number of bits' specified in "openssl/bn.h".

       mmaaxx is the size of the dd array that has been allocated.  ttoopp is the
       'last' entry being used, so for a value of 4, bn.d[0]=4 and bn.top=1.
       nneegg is 1 if the number is negative.  When a BBIIGGNNUUMM is 00, the dd field
       can be NNUULLLL and ttoopp == 00.

       Various routines in this library require the use of temporary BBIIGGNNUUMM
       variables during their execution.  Since dynamic memory allocation to
       create BBIIGGNNUUMMs is rather expensive when used in conjunction with
       repeated subroutine calls, the BBNNCCTTXX structure is used.  This
       structure contains BBNNCCTTXXNNUUMM BBIIGGNNUUMMs, see BNCTXstart(3).

       LLooww-lleevveell aarriitthhmmeettiicc ooppeerraattiioonnss

       These functions are implemented in C and for several platforms in
       assembly language:

       bnmulwords(rrpp, aapp, nnuumm, ww) operates on the nnuumm word arrays rrpp and aapp.
       It computes aapp * ww, places the result in rrpp, and returns the high word
       (carry).

       bnmuladdwords(rrpp, aapp, nnuumm, ww) operates on the nnuumm word arrays rrpp and
       aapp.  It computes aapp * ww + rrpp, places the result in rrpp, and returns the
       high word (carry).

       bnsqrwords(rrpp, aapp, nn) operates on the nnuumm word array aapp and the 2*nnuumm
       word array aapp.  It computes aapp * aapp word-wise, and places the low and
       high bytes of the result in rrpp.

       bndivwords(hh, ll, dd) divides the two word number (hh,ll) by dd and
       returns the result.

       bnaddwords(rrpp, aapp, bbpp, nnuumm) operates on the nnuumm word arrays aapp, bbpp
       and rrpp.  It computes aapp + bbpp, places the result in rrpp, and returns the
       high word (carry).

       bnsubwords(rrpp, aapp, bbpp, nnuumm) operates on the nnuumm word arrays aapp, bbpp
       and rrpp.  It computes aapp - bbpp, places the result in rrpp, and returns the
       carry (1 if bbpp > aapp, 0 otherwise).

       bnmulcomba4(rr, aa, bb) operates on the 4 word arrays aa and bb and the 8
       word array rr.  It computes aa*bb and places the result in rr.

       bnmulcomba8(rr, aa, bb) operates on the 8 word arrays aa and bb and the 16
       word array rr.  It computes aa*bb and places the result in rr.

       bnsqrcomba4(rr, aa, bb) operates on the 4 word arrays aa and bb and the 8
       word array rr.

       bnsqrcomba8(rr, aa, bb) operates on the 8 word arrays aa and bb and the 16
       word array rr.

       The following functions are implemented in C:

       bncmpwords(aa, bb, nn) operates on the nn word arrays aa and bb.  It
       returns 1, 0 and -1 if aa is greater than, equal and less than bb.

       bnmulnormal(rr, aa, nnaa, bb, nnbb) operates on the nnaa word array aa, the nnbb
       word array bb and the nnaa+nnbb word array rr.  It computes aa*bb and places
       the result in rr.

       bnmullownormal(rr, aa, bb, nn) operates on the nn word arrays rr, aa and bb.
       It computes the nn low words of aa*bb and places the result in rr.

       bnmulrecursive(rr, aa, bb, nn22, ddnnaa, ddnnbb, tt) operates on the word arrays
       aa and bb of length nn22+ddnnaa and nn22+ddnnbb (ddnnaa and ddnnbb are currently allowed
       to be 0 or negative) and the 2*nn22 word arrays rr and tt.  nn22 must be a
       power of 2.  It computes aa*bb and places the result in rr.

       bnmulpartrecursive(rr, aa, bb, nn, ttnnaa, ttnnbb, ttmmpp) operates on the word
       arrays aa and bb of length nn+ttnnaa and nn+ttnnbb and the 4*nn word arrays rr and
       ttmmpp.

       bnmullowrecursive(rr, aa, bb, nn22, ttmmpp) operates on the nn22 word arrays rr
       and ttmmpp and the nn22/2 word arrays aa and bb.

       bnmulhigh(rr, aa, bb, ll, nn22, ttmmpp) operates on the nn22 word arrays rr, aa, bb
       and ll (?) and the 3*nn22 word array ttmmpp.

       BNmul() calls bnmulnormal(), or an optimized implementation if the
       factors have the same size: bnmulcomba8() is used if they are 8 words
       long, bnmulrecursive() if they are larger than BBNNMMUULLLLSSIIZZEENNOORRMMAALL
       and the size is an exact multiple of the word size, and
       bnmulpartrecursive() for others that are larger than
       BBNNMMUULLLLSSIIZZEENNOORRMMAALL.

       bnsqrnormal(rr, aa, nn, ttmmpp) operates on the nn word array aa and the 2*nn
       word arrays ttmmpp and rr.

       The implementations use the following macros which, depending on the
       architecture, may use "long long" C operations or inline assembler.
       They are defined in "bnlcl.h".

       mul(rr, aa, ww, cc) computes ww*aa+cc and places the low word of the result in
       rr and the high word in cc.

       muladd(rr, aa, ww, cc) computes ww*aa+rr+cc and places the low word of the
       result in rr and the high word in cc.

       sqr(rr00, rr11, aa) computes aa*aa and places the low word of the result in rr00
       and the high word in rr11.

       SSiizzee cchhaannggeess

       bnexpand() ensures that bb has enough space for a bbiittss bit number.
       bnwexpand() ensures that bb has enough space for an nn word number.  If
       the number has to be expanded, both macros call bnexpand2(), which
       allocates a new dd array and copies the data.  They return NNUULLLL on
       error, bb otherwise.

       The bnfixtop() macro reduces aa->>ttoopp to point to the most significant
       non-zero word when aa has shrunk.

       DDeebbuuggggiinngg

       bnchecktop() verifies that "((a)->top >= 0 && (a)->top <= (a)->max)".
       A violation will cause the program to abort.

       bnprint() prints aa to stderr. bndump() prints nn words at dd (in
       reverse order, i.e. most significant word first) to stderr.

       bnsetmax() makes aa a static number with a mmaaxx of its current size.
       This is used by bnsetlow() and bnsethigh() to make rr a read-only
       BBIIGGNNUUMM that contains the nn low or high words of aa.

       If BBNNDDEEBBUUGG is not defined, bnchecktop(), bnprint(), bndump() and
       bnsetmax() are defined as empty macros.

SEE ALSO
       bn(3)



0.9.7l                            2002-05-30                    bninternal(3)