#use wml::openssl-macros area=docs page=bn_internal

<title>Documents, bn_internal(3)</title>

<h1>bn_internal(3)</h1>

#use wml::imp::generic

{:
## What's this? [[s|(<STRONG>[^<].+?)</A>(</STRONG><DD>)|$1$2|sg]]
[[s|<P>\s+<P>|<P>|sg]]
[[s|<P>\s+</|</|sg]]
[[s|<DD>\s*<DT>|<DD>&nbsp;<DT>|sg]]
[[s|<DD>\s*</DL>|<DD>&nbsp;</DL>|sg]]
[[s|\[|&#91;|sg]]
[[s|\]|&#93;|sg]]

<!-- INDEX BEGIN -->

<UL>

	<LI><A HREF="#NAME">NAME</A>
	<LI><A HREF="#SYNOPSIS">SYNOPSIS</A>
	<LI><A HREF="#DESCRIPTION">DESCRIPTION</A>
	<UL>

		<LI><A HREF="#The_BIGNUM_structure">The BIGNUM structure</A>
		<LI><A HREF="#Low_level_arithmetic_operations">Low-level arithmetic operations</A>
		<LI><A HREF="#Size_changes">Size changes</A>
		<LI><A HREF="#Debugging">Debugging</A>
	</UL>

	<LI><A HREF="#SEE_ALSO">SEE ALSO</A>
</UL>
<!-- INDEX END -->

<HR>
<P>
<HR>
<H1><A NAME="NAME">NAME</A></H1>
<P>
bn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words, bn_add_words,
bn_sub_words, bn_mul_comba4, bn_mul_comba8, bn_sqr_comba4, bn_sqr_comba8,
bn_cmp_words, bn_mul_normal, bn_mul_low_normal, bn_mul_recursive,
bn_mul_part_recursive, bn_mul_low_recursive, bn_mul_high, bn_sqr_normal,
bn_sqr_recursive, bn_expand, bn_wexpand, bn_expand2, bn_fix_top,
bn_check_top, bn_print, bn_dump, bn_set_max, bn_set_high, bn_set_low -
BIGNUM library internal functions

</P>
<P>
<HR>
<H1><A NAME="SYNOPSIS">SYNOPSIS</A></H1>
<PRE> #include &lt;openssl/bn.h&gt;
</PRE>
<PRE> 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);
</PRE>
<PRE> 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);
</PRE>
<PRE> int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n);
</PRE>
<PRE> 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,
   int dna,int dnb,BN_ULONG *tmp);
 void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
   int n, int tna,int tnb, 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);
</PRE>
<PRE> 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);
</PRE>
<PRE> 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);
</PRE>
<PRE> 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);
</PRE>
<PRE> 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);
</PRE>
<P>
<HR>
<H1><A NAME="DESCRIPTION">DESCRIPTION</A></H1>
<P>
This page documents the internal functions used by the OpenSSL
<STRONG>BIGNUM</STRONG> implementation. They are described here to facilitate debugging and
extending the library. They are <EM>not</EM> to be used by applications.

</P>
<P>
<HR>
<H2><A NAME="The_BIGNUM_structure">The BIGNUM structure</A></H2>
<PRE> typedef struct bignum_st BIGNUM;
</PRE>
<PRE> struct bignum_st
        {
        BN_ULONG *d;    /* Pointer to an array of 'BN_BITS2' bit chunks. */
        int top;        /* Index of last used d +1. */
        /* The next are internal book keeping for bn_expand. */
        int dmax;       /* Size of the d array. */
        int neg;        /* one if the number is negative */
        int flags;
        };
</PRE>
<P>
The integer value is stored in <STRONG>d</STRONG>, a <CODE>malloc()ed</CODE> array of words (<STRONG>BN_ULONG</STRONG>), least significant word first. A <STRONG>BN_ULONG</STRONG> can be either 16, 32 or 64 bits in size, depending on the 'number of bits'
(<STRONG>BITS2</STRONG>) specified in
<CODE>openssl/bn.h</CODE>.

</P>
<P>
<STRONG>dmax</STRONG> is the size of the <STRONG>d</STRONG> array that has been allocated.  <STRONG>top</STRONG>
is the number of words being used, so for a value of 4, bn.d[0]=4 and
bn.top=1.  <STRONG>neg</STRONG> is 1 if the number is negative. When a <STRONG>BIGNUM</STRONG> is
<STRONG>0</STRONG>, the <STRONG>d</STRONG> field can be <STRONG>NULL</STRONG> and <STRONG>top</STRONG> == <STRONG>0</STRONG>.

</P>
<P>
<STRONG>flags</STRONG> is a bit field of flags which are defined in <CODE>openssl/bn.h</CODE>. The flags begin with <STRONG>BN_FLG_</STRONG>. The macros <CODE>BN_set_flags(b,n)</CODE> and
<CODE>BN_get_flags(b,n)</CODE> exist to enable or fetch
<CODE>flag(s)</CODE> <STRONG>n</STRONG> from <STRONG>BIGNUM</STRONG>
structure <STRONG>b</STRONG>.

</P>
<P>
Various routines in this library require the use of temporary
<STRONG>BIGNUM</STRONG> variables during their execution. Since dynamic memory allocation to create <STRONG>BIGNUM</STRONG>s is rather expensive when used in conjunction with repeated subroutine
calls, the <STRONG>BN_CTX</STRONG> structure is used. This structure contains <STRONG>BN_CTX_NUM</STRONG>  <STRONG>BIGNUM</STRONG>s, see
<A HREF="../crypto/BN_CTX_start.html#">BN_CTX_start(3)</A>.

</P>
<P>
<HR>
<H2><A NAME="Low_level_arithmetic_operations">Low-level arithmetic operations</A></H2>
<P>
These functions are implemented in C and for several platforms in assembly
language:

</P>
<P>
<CODE>bn_mul_words(</CODE><STRONG>rp</STRONG>, <STRONG>ap</STRONG>, <STRONG>num</STRONG>, <STRONG>w</STRONG>) operates on the <STRONG>num</STRONG> word arrays <STRONG>rp</STRONG> and <STRONG>ap</STRONG>. It computes <STRONG>ap</STRONG> * <STRONG>w</STRONG>, places the result in <STRONG>rp</STRONG>, and returns the high word (carry).

</P>
<P>
<CODE>bn_mul_add_words(</CODE><STRONG>rp</STRONG>, <STRONG>ap</STRONG>, <STRONG>num</STRONG>, <STRONG>w</STRONG>) operates on the <STRONG>num</STRONG>
word arrays <STRONG>rp</STRONG> and <STRONG>ap</STRONG>. It computes <STRONG>ap</STRONG> * <STRONG>w</STRONG> + <STRONG>rp</STRONG>, places the result in <STRONG>rp</STRONG>, and returns the high word (carry).

</P>
<P>
<CODE>bn_sqr_words(</CODE><STRONG>rp</STRONG>, <STRONG>ap</STRONG>, <STRONG>n</STRONG>) operates on the <STRONG>num</STRONG> word array
<STRONG>ap</STRONG> and the 2*<STRONG>num</STRONG> word array <STRONG>ap</STRONG>. It computes <STRONG>ap</STRONG> * <STRONG>ap</STRONG>
word-wise, and places the low and high bytes of the result in <STRONG>rp</STRONG>.

</P>
<P>
<CODE>bn_div_words(</CODE><STRONG>h</STRONG>, <STRONG>l</STRONG>, <STRONG>d</STRONG>) divides the two word number (<STRONG>h</STRONG>,<STRONG>l</STRONG>) by <STRONG>d</STRONG> and returns the result.

</P>
<P>
<CODE>bn_add_words(</CODE><STRONG>rp</STRONG>, <STRONG>ap</STRONG>, <STRONG>bp</STRONG>, <STRONG>num</STRONG>) operates on the <STRONG>num</STRONG> word arrays <STRONG>ap</STRONG>, <STRONG>bp</STRONG> and <STRONG>rp</STRONG>. It computes <STRONG>ap</STRONG> + <STRONG>bp</STRONG>, places the result in <STRONG>rp</STRONG>, and returns the high word (carry).

</P>
<P>
<CODE>bn_sub_words(</CODE><STRONG>rp</STRONG>, <STRONG>ap</STRONG>, <STRONG>bp</STRONG>, <STRONG>num</STRONG>) operates on the <STRONG>num</STRONG> word arrays <STRONG>ap</STRONG>, <STRONG>bp</STRONG> and <STRONG>rp</STRONG>. It computes <STRONG>ap</STRONG> - <STRONG>bp</STRONG>, places the result in <STRONG>rp</STRONG>, and returns the carry (1 if <STRONG>bp</STRONG>  &gt;  <STRONG>ap</STRONG>, 0 otherwise).

</P>
<P>
<CODE>bn_mul_comba4(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>b</STRONG>) operates on the 4 word arrays <STRONG>a</STRONG> and
<STRONG>b</STRONG> and the 8 word array <STRONG>r</STRONG>. It computes <STRONG>a</STRONG>*<STRONG>b</STRONG> and places the result in <STRONG>r</STRONG>.

</P>
<P>
<CODE>bn_mul_comba8(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>b</STRONG>) operates on the 8 word arrays <STRONG>a</STRONG> and
<STRONG>b</STRONG> and the 16 word array <STRONG>r</STRONG>. It computes <STRONG>a</STRONG>*<STRONG>b</STRONG> and places the result in <STRONG>r</STRONG>.

</P>
<P>
<CODE>bn_sqr_comba4(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>b</STRONG>) operates on the 4 word arrays <STRONG>a</STRONG> and
<STRONG>b</STRONG> and the 8 word array <STRONG>r</STRONG>.

</P>
<P>
<CODE>bn_sqr_comba8(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>b</STRONG>) operates on the 8 word arrays <STRONG>a</STRONG> and
<STRONG>b</STRONG> and the 16 word array <STRONG>r</STRONG>.

</P>
<P>
The following functions are implemented in C:

</P>
<P>
<CODE>bn_cmp_words(</CODE><STRONG>a</STRONG>, <STRONG>b</STRONG>, <STRONG>n</STRONG>) operates on the <STRONG>n</STRONG> word arrays <STRONG>a</STRONG>
and <STRONG>b</STRONG>. It returns 1, 0 and -1 if <STRONG>a</STRONG> is greater than, equal and less than <STRONG>b</STRONG>.

</P>
<P>
<CODE>bn_mul_normal(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>na</STRONG>, <STRONG>b</STRONG>, <STRONG>nb</STRONG>) operates on the <STRONG>na</STRONG>
word array <STRONG>a</STRONG>, the <STRONG>nb</STRONG> word array <STRONG>b</STRONG> and the <STRONG>na</STRONG>+<STRONG>nb</STRONG> word array <STRONG>r</STRONG>. It computes <STRONG>a</STRONG>*<STRONG>b</STRONG> and places the result in <STRONG>r</STRONG>.

</P>
<P>
<CODE>bn_mul_low_normal(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>b</STRONG>, <STRONG>n</STRONG>) operates on the <STRONG>n</STRONG> word arrays <STRONG>r</STRONG>, <STRONG>a</STRONG> and <STRONG>b</STRONG>. It computes the <STRONG>n</STRONG> low words of
<STRONG>a</STRONG>*<STRONG>b</STRONG> and places the result in <STRONG>r</STRONG>.

</P>
<P>
<CODE>bn_mul_recursive(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>b</STRONG>, <STRONG>n2</STRONG>, <STRONG>dna</STRONG>, <STRONG>dnb</STRONG>, <STRONG>t</STRONG>) operates on the word arrays <STRONG>a</STRONG> and <STRONG>b</STRONG> of length <STRONG>n2</STRONG>+<STRONG>dna</STRONG> and <STRONG>n2</STRONG>+<STRONG>dnb</STRONG>
(<STRONG>dna</STRONG> and <STRONG>dnb</STRONG> are currently allowed to be 0 or negative) and the 2*<STRONG>n2</STRONG>
word arrays <STRONG>r</STRONG> and <STRONG>t</STRONG>.  <STRONG>n2</STRONG> must be a power of 2. It computes
<STRONG>a</STRONG>*<STRONG>b</STRONG> and places the result in <STRONG>r</STRONG>.

</P>
<P>
<CODE>bn_mul_part_recursive(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>b</STRONG>, <STRONG>n</STRONG>, <STRONG>tna</STRONG>, <STRONG>tnb</STRONG>, <STRONG>tmp</STRONG>) operates on the word arrays <STRONG>a</STRONG> and <STRONG>b</STRONG> of length <STRONG>n</STRONG>+<STRONG>tna</STRONG> and
<STRONG>n</STRONG>+<STRONG>tnb</STRONG> and the 4*<STRONG>n</STRONG> word arrays <STRONG>r</STRONG> and <STRONG>tmp</STRONG>.

</P>
<P>
<CODE>bn_mul_low_recursive(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>b</STRONG>, <STRONG>n2</STRONG>, <STRONG>tmp</STRONG>) operates on the
<STRONG>n2</STRONG> word arrays <STRONG>r</STRONG> and <STRONG>tmp</STRONG> and the <STRONG>n2</STRONG>/2 word arrays <STRONG>a</STRONG>
and <STRONG>b</STRONG>.

</P>
<P>
<CODE>bn_mul_high(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>b</STRONG>, <STRONG>l</STRONG>, <STRONG>n2</STRONG>, <STRONG>tmp</STRONG>) operates on the
<STRONG>n2</STRONG> word arrays <STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>b</STRONG> and <STRONG>l</STRONG> (?) and the 3*<STRONG>n2</STRONG> word array <STRONG>tmp</STRONG>.

</P>
<P>
<CODE>BN_mul()</CODE> calls <CODE>bn_mul_normal(),</CODE> or an optimized
implementation if the factors have the same size:
<CODE>bn_mul_comba8()</CODE> is used if they are 8 words long,
<CODE>bn_mul_recursive()</CODE> if they are larger than
<STRONG>BN_MULL_SIZE_NORMAL</STRONG> and the size is an exact multiple of the word size, and
<CODE>bn_mul_part_recursive()</CODE> for others that are larger than
<STRONG>BN_MULL_SIZE_NORMAL</STRONG>.

</P>
<P>
<CODE>bn_sqr_normal(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>n</STRONG>, <STRONG>tmp</STRONG>) operates on the <STRONG>n</STRONG> word array
<STRONG>a</STRONG> and the 2*<STRONG>n</STRONG> word arrays <STRONG>tmp</STRONG> and <STRONG>r</STRONG>.

</P>
<P>
The implementations use the following macros which, depending on the
architecture, may use ``long long'' C operations or inline assembler. They
are defined in <CODE>bn_lcl.h</CODE>.

</P>
<P>
<CODE>mul(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>w</STRONG>, <STRONG>c</STRONG>) computes <STRONG>w</STRONG>*<STRONG>a</STRONG>+<STRONG>c</STRONG> and places the low word of the result in <STRONG>r</STRONG> and the high word in <STRONG>c</STRONG>.

</P>
<P>
<CODE>mul_add(</CODE><STRONG>r</STRONG>, <STRONG>a</STRONG>, <STRONG>w</STRONG>, <STRONG>c</STRONG>) computes <STRONG>w</STRONG>*<STRONG>a</STRONG>+<STRONG>r</STRONG>+<STRONG>c</STRONG> and places the low word of the result in <STRONG>r</STRONG> and the high word in <STRONG>c</STRONG>.

</P>
<P>
<CODE>sqr(</CODE><STRONG>r0</STRONG>, <STRONG>r1</STRONG>, <STRONG>a</STRONG>) computes <STRONG>a</STRONG>*<STRONG>a</STRONG> and places the low word of the result in <STRONG>r0</STRONG> and the high word in <STRONG>r1</STRONG>.

</P>
<P>
<HR>
<H2><A NAME="Size_changes">Size changes</A></H2>
<P>
<CODE>bn_expand()</CODE> ensures that <STRONG>b</STRONG> has enough space for a <STRONG>bits</STRONG> bit number. <CODE>bn_wexpand()</CODE> ensures that <STRONG>b</STRONG> has enough space for an
<STRONG>n</STRONG> word number. If the number has to be expanded, both macros call
<CODE>bn_expand2(),</CODE> which allocates a new <STRONG>d</STRONG> array and copies the data. They return <STRONG>NULL</STRONG> on error, <STRONG>b</STRONG> otherwise.

</P>
<P>
The <CODE>bn_fix_top()</CODE> macro reduces <STRONG>a-&gt;top</STRONG> to point to the most significant non-zero word plus one when <STRONG>a</STRONG> has shrunk.

</P>
<P>
<HR>
<H2><A NAME="Debugging">Debugging</A></H2>
<P>
<CODE>bn_check_top()</CODE> verifies that <CODE>((a)-&amp;gt;top &amp;gt;= 0 &amp;&amp; (a)-&amp;gt;top
&amp;lt;= (a)-&amp;gt;dmax)</CODE>. A violation will cause the program to abort.

</P>
<P>
<CODE>bn_print()</CODE> prints <STRONG>a</STRONG> to stderr. <CODE>bn_dump()</CODE> prints <STRONG>n</STRONG> words at <STRONG>d</STRONG>
(in reverse order, i.e. most significant word first) to stderr.

</P>
<P>
<CODE>bn_set_max()</CODE> makes <STRONG>a</STRONG> a static number with a <STRONG>dmax</STRONG> of its current size. This is used by <CODE>bn_set_low()</CODE> and
<CODE>bn_set_high()</CODE> to make <STRONG>r</STRONG> a read-only
<STRONG>BIGNUM</STRONG> that contains the <STRONG>n</STRONG> low or high words of <STRONG>a</STRONG>.

</P>
<P>
If <STRONG>BN_DEBUG</STRONG> is not defined, <CODE>bn_check_top(),</CODE> <CODE>bn_print(),</CODE>
<CODE>bn_dump()</CODE> and <CODE>bn_set_max()</CODE> are defined as empty
macros.

</P>
<P>
<HR>
<H1><A NAME="SEE_ALSO">SEE ALSO</A></H1>
<P>
<A HREF="../crypto/bn.html#">bn(3)</A>



</P>
:}