5 bn_mul_words, bn_mul_add_words, bn_sqr_words, bn_div_words,
6 bn_add_words, bn_sub_words, bn_mul_comba4, bn_mul_comba8,
7 bn_sqr_comba4, bn_sqr_comba8, bn_cmp_words, bn_mul_normal,
8 bn_mul_low_normal, bn_mul_recursive, bn_mul_part_recursive,
9 bn_mul_low_recursive, bn_mul_high, bn_sqr_normal, bn_sqr_recursive,
10 bn_expand, bn_wexpand, bn_expand2, bn_fix_top, bn_check_top,
11 bn_print, bn_dump, bn_set_max, bn_set_high, bn_set_low - BIGNUM
12 library internal functions
16 #include <openssl/bn.h>
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,
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,
25 BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,
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);
33 int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n);
35 void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b,
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);
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);
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);
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);
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);
68 This page documents the internal functions used by the OpenSSL
69 B<BIGNUM> implementation. They are described here to facilitate
70 debugging and extending the library. They are I<not> to be used by
73 =head2 The BIGNUM structure
75 typedef struct bignum_st BIGNUM;
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 */
88 The integer value is stored in B<d>, a malloc()ed array of words (B<BN_ULONG>),
89 least significant word first. A B<BN_ULONG> can be either 16, 32 or 64 bits
90 in size, depending on the 'number of bits' (B<BITS2>) specified in
93 B<dmax> is the size of the B<d> array that has been allocated. B<top>
94 is the number of words being used, so for a value of 4, bn.d[0]=4 and
95 bn.top=1. B<neg> is 1 if the number is negative. When a B<BIGNUM> is
96 B<0>, the B<d> field can be B<NULL> and B<top> == B<0>.
98 B<flags> is a bit field of flags which are defined in C<openssl/bn.h>. The
99 flags begin with B<BN_FLG_>. The macros BN_set_flags(b, n) and
100 BN_get_flags(b, n) exist to enable or fetch flag(s) B<n> from B<BIGNUM>
103 Various routines in this library require the use of temporary
104 B<BIGNUM> variables during their execution. Since dynamic memory
105 allocation to create B<BIGNUM>s is rather expensive when used in
106 conjunction with repeated subroutine calls, the B<BN_CTX> structure is
107 used. This structure contains B<BN_CTX_NUM> B<BIGNUM>s, see
110 =head2 Low-level arithmetic operations
112 These functions are implemented in C and for several platforms in
115 bn_mul_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num> word
116 arrays B<rp> and B<ap>. It computes B<ap> * B<w>, places the result
117 in B<rp>, and returns the high word (carry).
119 bn_mul_add_words(B<rp>, B<ap>, B<num>, B<w>) operates on the B<num>
120 word arrays B<rp> and B<ap>. It computes B<ap> * B<w> + B<rp>, places
121 the result in B<rp>, and returns the high word (carry).
123 bn_sqr_words(B<rp>, B<ap>, B<n>) operates on the B<num> word array
124 B<ap> and the 2*B<num> word array B<ap>. It computes B<ap> * B<ap>
125 word-wise, and places the low and high bytes of the result in B<rp>.
127 bn_div_words(B<h>, B<l>, B<d>) divides the two word number (B<h>, B<l>)
128 by B<d> and returns the result.
130 bn_add_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word
131 arrays B<ap>, B<bp> and B<rp>. It computes B<ap> + B<bp>, places the
132 result in B<rp>, and returns the high word (carry).
134 bn_sub_words(B<rp>, B<ap>, B<bp>, B<num>) operates on the B<num> word
135 arrays B<ap>, B<bp> and B<rp>. It computes B<ap> - B<bp>, places the
136 result in B<rp>, and returns the carry (1 if B<bp> E<gt> B<ap>, 0
139 bn_mul_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and
140 B<b> and the 8 word array B<r>. It computes B<a>*B<b> and places the
143 bn_mul_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and
144 B<b> and the 16 word array B<r>. It computes B<a>*B<b> and places the
147 bn_sqr_comba4(B<r>, B<a>, B<b>) operates on the 4 word arrays B<a> and
148 B<b> and the 8 word array B<r>.
150 bn_sqr_comba8(B<r>, B<a>, B<b>) operates on the 8 word arrays B<a> and
151 B<b> and the 16 word array B<r>.
153 The following functions are implemented in C:
155 bn_cmp_words(B<a>, B<b>, B<n>) operates on the B<n> word arrays B<a>
156 and B<b>. It returns 1, 0 and -1 if B<a> is greater than, equal and
159 bn_mul_normal(B<r>, B<a>, B<na>, B<b>, B<nb>) operates on the B<na>
160 word array B<a>, the B<nb> word array B<b> and the B<na>+B<nb> word
161 array B<r>. It computes B<a>*B<b> and places the result in B<r>.
163 bn_mul_low_normal(B<r>, B<a>, B<b>, B<n>) operates on the B<n> word
164 arrays B<r>, B<a> and B<b>. It computes the B<n> low words of
165 B<a>*B<b> and places the result in B<r>.
167 bn_mul_recursive(B<r>, B<a>, B<b>, B<n2>, B<dna>, B<dnb>, B<t>) operates
168 on 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>
170 word arrays B<r> and B<t>. B<n2> must be a power of 2. It computes
171 B<a>*B<b> and places the result in B<r>.
173 bn_mul_part_recursive(B<r>, B<a>, B<b>, B<n>, B<tna>, B<tnb>, B<tmp>)
174 operates on the word arrays B<a> and B<b> of length B<n>+B<tna> and
175 B<n>+B<tnb> and the 4*B<n> word arrays B<r> and B<tmp>.
177 bn_mul_low_recursive(B<r>, B<a>, B<b>, B<n2>, B<tmp>) operates on the
178 B<n2> word arrays B<r> and B<tmp> and the B<n2>/2 word arrays B<a>
181 bn_mul_high(B<r>, B<a>, B<b>, B<l>, B<n2>, B<tmp>) operates on the
182 B<n2> word arrays B<r>, B<a>, B<b> and B<l> (?) and the 3*B<n2> word
185 BN_mul() calls bn_mul_normal(), or an optimized implementation if the
186 factors have the same size: bn_mul_comba8() is used if they are 8
187 words long, bn_mul_recursive() if they are larger than
188 B<BN_MULL_SIZE_NORMAL> and the size is an exact multiple of the word
189 size, and bn_mul_part_recursive() for others that are larger than
190 B<BN_MULL_SIZE_NORMAL>.
192 bn_sqr_normal(B<r>, B<a>, B<n>, B<tmp>) operates on the B<n> word array
193 B<a> and the 2*B<n> word arrays B<tmp> and B<r>.
195 The implementations use the following macros which, depending on the
196 architecture, may use "long long" C operations or inline assembler.
197 They are defined in C<bn_lcl.h>.
199 mul(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<c> and places the
200 low word of the result in B<r> and the high word in B<c>.
202 mul_add(B<r>, B<a>, B<w>, B<c>) computes B<w>*B<a>+B<r>+B<c> and
203 places the low word of the result in B<r> and the high word in B<c>.
205 sqr(B<r0>, B<r1>, B<a>) computes B<a>*B<a> and places the low word
206 of the result in B<r0> and the high word in B<r1>.
210 bn_expand() ensures that B<b> has enough space for a B<bits> bit
211 number. bn_wexpand() ensures that B<b> has enough space for an
212 B<n> word number. If the number has to be expanded, both macros
213 call bn_expand2(), which allocates a new B<d> array and copies the
214 data. They return B<NULL> on error, B<b> otherwise.
216 The bn_fix_top() macro reduces B<a-E<gt>top> to point to the most
217 significant non-zero word plus one when B<a> has shrunk.
221 bn_check_top() verifies that C<((a)-E<gt>top E<gt>= 0 && (a)-E<gt>top
222 E<lt>= (a)-E<gt>dmax)>. A violation will cause the program to abort.
224 bn_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.
227 bn_set_max() makes B<a> a static number with a B<dmax> of its current size.
228 This is used by bn_set_low() and bn_set_high() to make B<r> a read-only
229 B<BIGNUM> that contains the B<n> low or high words of B<a>.
231 If B<BN_DEBUG> is not defined, bn_check_top(), bn_print(), bn_dump()
232 and bn_set_max() are defined as empty macros.
240 Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
242 Licensed under the OpenSSL license (the "License"). You may not use
243 this file except in compliance with the License. You can obtain a copy
244 in the file LICENSE in the source distribution or at
245 L<https://www.openssl.org/source/license.html>.