1*ca1d80d6Sbeck /* $OpenBSD: bn_mul.c,v 1.39 2023/07/08 12:21:58 beck Exp $ */
25b37fcf3Sryker /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
35b37fcf3Sryker * All rights reserved.
45b37fcf3Sryker *
55b37fcf3Sryker * This package is an SSL implementation written
65b37fcf3Sryker * by Eric Young (eay@cryptsoft.com).
75b37fcf3Sryker * The implementation was written so as to conform with Netscapes SSL.
85b37fcf3Sryker *
95b37fcf3Sryker * This library is free for commercial and non-commercial use as long as
105b37fcf3Sryker * the following conditions are aheared to. The following conditions
115b37fcf3Sryker * apply to all code found in this distribution, be it the RC4, RSA,
125b37fcf3Sryker * lhash, DES, etc., code; not just the SSL code. The SSL documentation
135b37fcf3Sryker * included with this distribution is covered by the same copyright terms
145b37fcf3Sryker * except that the holder is Tim Hudson (tjh@cryptsoft.com).
155b37fcf3Sryker *
165b37fcf3Sryker * Copyright remains Eric Young's, and as such any Copyright notices in
175b37fcf3Sryker * the code are not to be removed.
185b37fcf3Sryker * If this package is used in a product, Eric Young should be given attribution
195b37fcf3Sryker * as the author of the parts of the library used.
205b37fcf3Sryker * This can be in the form of a textual message at program startup or
215b37fcf3Sryker * in documentation (online or textual) provided with the package.
225b37fcf3Sryker *
235b37fcf3Sryker * Redistribution and use in source and binary forms, with or without
245b37fcf3Sryker * modification, are permitted provided that the following conditions
255b37fcf3Sryker * are met:
265b37fcf3Sryker * 1. Redistributions of source code must retain the copyright
275b37fcf3Sryker * notice, this list of conditions and the following disclaimer.
285b37fcf3Sryker * 2. Redistributions in binary form must reproduce the above copyright
295b37fcf3Sryker * notice, this list of conditions and the following disclaimer in the
305b37fcf3Sryker * documentation and/or other materials provided with the distribution.
315b37fcf3Sryker * 3. All advertising materials mentioning features or use of this software
325b37fcf3Sryker * must display the following acknowledgement:
335b37fcf3Sryker * "This product includes cryptographic software written by
345b37fcf3Sryker * Eric Young (eay@cryptsoft.com)"
355b37fcf3Sryker * The word 'cryptographic' can be left out if the rouines from the library
365b37fcf3Sryker * being used are not cryptographic related :-).
375b37fcf3Sryker * 4. If you include any Windows specific code (or a derivative thereof) from
385b37fcf3Sryker * the apps directory (application code) you must include an acknowledgement:
395b37fcf3Sryker * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
405b37fcf3Sryker *
415b37fcf3Sryker * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
425b37fcf3Sryker * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
435b37fcf3Sryker * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
445b37fcf3Sryker * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
455b37fcf3Sryker * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
465b37fcf3Sryker * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
475b37fcf3Sryker * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
485b37fcf3Sryker * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
495b37fcf3Sryker * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
505b37fcf3Sryker * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
515b37fcf3Sryker * SUCH DAMAGE.
525b37fcf3Sryker *
535b37fcf3Sryker * The licence and distribution terms for any publically available version or
545b37fcf3Sryker * derivative of this code cannot be changed. i.e. this code cannot simply be
555b37fcf3Sryker * copied and put under another distribution licence
565b37fcf3Sryker * [including the GNU Public Licence.]
575b37fcf3Sryker */
585b37fcf3Sryker
594fcf65c5Sdjm #include <assert.h>
60a8913c44Sjsing #include <stdio.h>
61a8913c44Sjsing #include <string.h>
62a8913c44Sjsing
638cf4d6a6Sjsing #include <openssl/opensslconf.h>
648cf4d6a6Sjsing
65de344ea3Sjsing #include "bn_arch.h"
66df1d0ed5Sjsing #include "bn_internal.h"
67c9675a23Stb #include "bn_local.h"
685b37fcf3Sryker
69df1d0ed5Sjsing /*
70df1d0ed5Sjsing * bn_mul_comba4() computes r[] = a[] * b[] using Comba multiplication
71df1d0ed5Sjsing * (https://everything2.com/title/Comba+multiplication), where a and b are both
72df1d0ed5Sjsing * four word arrays, producing an eight word array result.
73df1d0ed5Sjsing */
74de344ea3Sjsing #ifndef HAVE_BN_MUL_COMBA4
75de344ea3Sjsing void
bn_mul_comba4(BN_ULONG * r,BN_ULONG * a,BN_ULONG * b)76de344ea3Sjsing bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
77de344ea3Sjsing {
78df1d0ed5Sjsing BN_ULONG c0, c1, c2;
79de344ea3Sjsing
80df1d0ed5Sjsing bn_mulw_addtw(a[0], b[0], 0, 0, 0, &c2, &c1, &r[0]);
81df1d0ed5Sjsing
82df1d0ed5Sjsing bn_mulw_addtw(a[0], b[1], 0, c2, c1, &c2, &c1, &c0);
83df1d0ed5Sjsing bn_mulw_addtw(a[1], b[0], c2, c1, c0, &c2, &c1, &r[1]);
84df1d0ed5Sjsing
85df1d0ed5Sjsing bn_mulw_addtw(a[2], b[0], 0, c2, c1, &c2, &c1, &c0);
86df1d0ed5Sjsing bn_mulw_addtw(a[1], b[1], c2, c1, c0, &c2, &c1, &c0);
87df1d0ed5Sjsing bn_mulw_addtw(a[0], b[2], c2, c1, c0, &c2, &c1, &r[2]);
88df1d0ed5Sjsing
89df1d0ed5Sjsing bn_mulw_addtw(a[0], b[3], 0, c2, c1, &c2, &c1, &c0);
90df1d0ed5Sjsing bn_mulw_addtw(a[1], b[2], c2, c1, c0, &c2, &c1, &c0);
91df1d0ed5Sjsing bn_mulw_addtw(a[2], b[1], c2, c1, c0, &c2, &c1, &c0);
92df1d0ed5Sjsing bn_mulw_addtw(a[3], b[0], c2, c1, c0, &c2, &c1, &r[3]);
93df1d0ed5Sjsing
94df1d0ed5Sjsing bn_mulw_addtw(a[3], b[1], 0, c2, c1, &c2, &c1, &c0);
95df1d0ed5Sjsing bn_mulw_addtw(a[2], b[2], c2, c1, c0, &c2, &c1, &c0);
96df1d0ed5Sjsing bn_mulw_addtw(a[1], b[3], c2, c1, c0, &c2, &c1, &r[4]);
97df1d0ed5Sjsing
98df1d0ed5Sjsing bn_mulw_addtw(a[2], b[3], 0, c2, c1, &c2, &c1, &c0);
99df1d0ed5Sjsing bn_mulw_addtw(a[3], b[2], c2, c1, c0, &c2, &c1, &r[5]);
100df1d0ed5Sjsing
101df1d0ed5Sjsing bn_mulw_addtw(a[3], b[3], 0, c2, c1, &c2, &r[7], &r[6]);
102de344ea3Sjsing }
103de344ea3Sjsing #endif
104de344ea3Sjsing
105df1d0ed5Sjsing /*
106df1d0ed5Sjsing * bn_mul_comba8() computes r[] = a[] * b[] using Comba multiplication
107df1d0ed5Sjsing * (https://everything2.com/title/Comba+multiplication), where a and b are both
108df1d0ed5Sjsing * eight word arrays, producing a 16 word array result.
109df1d0ed5Sjsing */
110de344ea3Sjsing #ifndef HAVE_BN_MUL_COMBA8
111de344ea3Sjsing void
bn_mul_comba8(BN_ULONG * r,BN_ULONG * a,BN_ULONG * b)112de344ea3Sjsing bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
113de344ea3Sjsing {
114df1d0ed5Sjsing BN_ULONG c0, c1, c2;
115de344ea3Sjsing
116df1d0ed5Sjsing bn_mulw_addtw(a[0], b[0], 0, 0, 0, &c2, &c1, &r[0]);
117df1d0ed5Sjsing
118df1d0ed5Sjsing bn_mulw_addtw(a[0], b[1], 0, c2, c1, &c2, &c1, &c0);
119df1d0ed5Sjsing bn_mulw_addtw(a[1], b[0], c2, c1, c0, &c2, &c1, &r[1]);
120df1d0ed5Sjsing
121df1d0ed5Sjsing bn_mulw_addtw(a[2], b[0], 0, c2, c1, &c2, &c1, &c0);
122df1d0ed5Sjsing bn_mulw_addtw(a[1], b[1], c2, c1, c0, &c2, &c1, &c0);
123df1d0ed5Sjsing bn_mulw_addtw(a[0], b[2], c2, c1, c0, &c2, &c1, &r[2]);
124df1d0ed5Sjsing
125df1d0ed5Sjsing bn_mulw_addtw(a[0], b[3], 0, c2, c1, &c2, &c1, &c0);
126df1d0ed5Sjsing bn_mulw_addtw(a[1], b[2], c2, c1, c0, &c2, &c1, &c0);
127df1d0ed5Sjsing bn_mulw_addtw(a[2], b[1], c2, c1, c0, &c2, &c1, &c0);
128df1d0ed5Sjsing bn_mulw_addtw(a[3], b[0], c2, c1, c0, &c2, &c1, &r[3]);
129df1d0ed5Sjsing
130df1d0ed5Sjsing bn_mulw_addtw(a[4], b[0], 0, c2, c1, &c2, &c1, &c0);
131df1d0ed5Sjsing bn_mulw_addtw(a[3], b[1], c2, c1, c0, &c2, &c1, &c0);
132df1d0ed5Sjsing bn_mulw_addtw(a[2], b[2], c2, c1, c0, &c2, &c1, &c0);
133df1d0ed5Sjsing bn_mulw_addtw(a[1], b[3], c2, c1, c0, &c2, &c1, &c0);
134df1d0ed5Sjsing bn_mulw_addtw(a[0], b[4], c2, c1, c0, &c2, &c1, &r[4]);
135df1d0ed5Sjsing
136df1d0ed5Sjsing bn_mulw_addtw(a[0], b[5], 0, c2, c1, &c2, &c1, &c0);
137df1d0ed5Sjsing bn_mulw_addtw(a[1], b[4], c2, c1, c0, &c2, &c1, &c0);
138df1d0ed5Sjsing bn_mulw_addtw(a[2], b[3], c2, c1, c0, &c2, &c1, &c0);
139df1d0ed5Sjsing bn_mulw_addtw(a[3], b[2], c2, c1, c0, &c2, &c1, &c0);
140df1d0ed5Sjsing bn_mulw_addtw(a[4], b[1], c2, c1, c0, &c2, &c1, &c0);
141df1d0ed5Sjsing bn_mulw_addtw(a[5], b[0], c2, c1, c0, &c2, &c1, &r[5]);
142df1d0ed5Sjsing
143df1d0ed5Sjsing bn_mulw_addtw(a[6], b[0], 0, c2, c1, &c2, &c1, &c0);
144df1d0ed5Sjsing bn_mulw_addtw(a[5], b[1], c2, c1, c0, &c2, &c1, &c0);
145df1d0ed5Sjsing bn_mulw_addtw(a[4], b[2], c2, c1, c0, &c2, &c1, &c0);
146df1d0ed5Sjsing bn_mulw_addtw(a[3], b[3], c2, c1, c0, &c2, &c1, &c0);
147df1d0ed5Sjsing bn_mulw_addtw(a[2], b[4], c2, c1, c0, &c2, &c1, &c0);
148df1d0ed5Sjsing bn_mulw_addtw(a[1], b[5], c2, c1, c0, &c2, &c1, &c0);
149df1d0ed5Sjsing bn_mulw_addtw(a[0], b[6], c2, c1, c0, &c2, &c1, &r[6]);
150df1d0ed5Sjsing
151df1d0ed5Sjsing bn_mulw_addtw(a[0], b[7], 0, c2, c1, &c2, &c1, &c0);
152df1d0ed5Sjsing bn_mulw_addtw(a[1], b[6], c2, c1, c0, &c2, &c1, &c0);
153df1d0ed5Sjsing bn_mulw_addtw(a[2], b[5], c2, c1, c0, &c2, &c1, &c0);
154df1d0ed5Sjsing bn_mulw_addtw(a[3], b[4], c2, c1, c0, &c2, &c1, &c0);
155df1d0ed5Sjsing bn_mulw_addtw(a[4], b[3], c2, c1, c0, &c2, &c1, &c0);
156df1d0ed5Sjsing bn_mulw_addtw(a[5], b[2], c2, c1, c0, &c2, &c1, &c0);
157df1d0ed5Sjsing bn_mulw_addtw(a[6], b[1], c2, c1, c0, &c2, &c1, &c0);
158df1d0ed5Sjsing bn_mulw_addtw(a[7], b[0], c2, c1, c0, &c2, &c1, &r[7]);
159df1d0ed5Sjsing
160df1d0ed5Sjsing bn_mulw_addtw(a[7], b[1], 0, c2, c1, &c2, &c1, &c0);
161df1d0ed5Sjsing bn_mulw_addtw(a[6], b[2], c2, c1, c0, &c2, &c1, &c0);
162df1d0ed5Sjsing bn_mulw_addtw(a[5], b[3], c2, c1, c0, &c2, &c1, &c0);
163df1d0ed5Sjsing bn_mulw_addtw(a[4], b[4], c2, c1, c0, &c2, &c1, &c0);
164df1d0ed5Sjsing bn_mulw_addtw(a[3], b[5], c2, c1, c0, &c2, &c1, &c0);
165df1d0ed5Sjsing bn_mulw_addtw(a[2], b[6], c2, c1, c0, &c2, &c1, &c0);
166df1d0ed5Sjsing bn_mulw_addtw(a[1], b[7], c2, c1, c0, &c2, &c1, &r[8]);
167df1d0ed5Sjsing
168df1d0ed5Sjsing bn_mulw_addtw(a[2], b[7], 0, c2, c1, &c2, &c1, &c0);
169df1d0ed5Sjsing bn_mulw_addtw(a[3], b[6], c2, c1, c0, &c2, &c1, &c0);
170df1d0ed5Sjsing bn_mulw_addtw(a[4], b[5], c2, c1, c0, &c2, &c1, &c0);
171df1d0ed5Sjsing bn_mulw_addtw(a[5], b[4], c2, c1, c0, &c2, &c1, &c0);
172df1d0ed5Sjsing bn_mulw_addtw(a[6], b[3], c2, c1, c0, &c2, &c1, &c0);
173df1d0ed5Sjsing bn_mulw_addtw(a[7], b[2], c2, c1, c0, &c2, &c1, &r[9]);
174df1d0ed5Sjsing
175df1d0ed5Sjsing bn_mulw_addtw(a[7], b[3], 0, c2, c1, &c2, &c1, &c0);
176df1d0ed5Sjsing bn_mulw_addtw(a[6], b[4], c2, c1, c0, &c2, &c1, &c0);
177df1d0ed5Sjsing bn_mulw_addtw(a[5], b[5], c2, c1, c0, &c2, &c1, &c0);
178df1d0ed5Sjsing bn_mulw_addtw(a[4], b[6], c2, c1, c0, &c2, &c1, &c0);
179df1d0ed5Sjsing bn_mulw_addtw(a[3], b[7], c2, c1, c0, &c2, &c1, &r[10]);
180df1d0ed5Sjsing
181df1d0ed5Sjsing bn_mulw_addtw(a[4], b[7], 0, c2, c1, &c2, &c1, &c0);
182df1d0ed5Sjsing bn_mulw_addtw(a[5], b[6], c2, c1, c0, &c2, &c1, &c0);
183df1d0ed5Sjsing bn_mulw_addtw(a[6], b[5], c2, c1, c0, &c2, &c1, &c0);
184df1d0ed5Sjsing bn_mulw_addtw(a[7], b[4], c2, c1, c0, &c2, &c1, &r[11]);
185df1d0ed5Sjsing
186df1d0ed5Sjsing bn_mulw_addtw(a[7], b[5], 0, c2, c1, &c2, &c1, &c0);
187df1d0ed5Sjsing bn_mulw_addtw(a[6], b[6], c2, c1, c0, &c2, &c1, &c0);
188df1d0ed5Sjsing bn_mulw_addtw(a[5], b[7], c2, c1, c0, &c2, &c1, &r[12]);
189df1d0ed5Sjsing
190df1d0ed5Sjsing bn_mulw_addtw(a[6], b[7], 0, c2, c1, &c2, &c1, &c0);
191df1d0ed5Sjsing bn_mulw_addtw(a[7], b[6], c2, c1, c0, &c2, &c1, &r[13]);
192df1d0ed5Sjsing
193df1d0ed5Sjsing bn_mulw_addtw(a[7], b[7], 0, c2, c1, &c2, &r[15], &r[14]);
194de344ea3Sjsing }
195de344ea3Sjsing #endif
196de344ea3Sjsing
197df1d0ed5Sjsing /*
198df1d0ed5Sjsing * bn_mul_words() computes (carry:r[i]) = a[i] * w + carry, where a is an array
199df1d0ed5Sjsing * of words and w is a single word. This should really be called bn_mulw_words()
200df1d0ed5Sjsing * since only one input is an array. This is used as a step in the multiplication
201df1d0ed5Sjsing * of word arrays.
202df1d0ed5Sjsing */
2038889fb99Sjsing #ifndef HAVE_BN_MUL_WORDS
2048889fb99Sjsing BN_ULONG
bn_mul_words(BN_ULONG * r,const BN_ULONG * a,int num,BN_ULONG w)205df1d0ed5Sjsing bn_mul_words(BN_ULONG *r, const BN_ULONG *a, int num, BN_ULONG w)
2068889fb99Sjsing {
2078889fb99Sjsing BN_ULONG carry = 0;
2088889fb99Sjsing
2098889fb99Sjsing assert(num >= 0);
2108889fb99Sjsing if (num <= 0)
211df1d0ed5Sjsing return 0;
2128889fb99Sjsing
2138889fb99Sjsing while (num & ~3) {
21473e8eea7Sjsing bn_qwmulw_addw(a[3], a[2], a[1], a[0], w, carry, &carry,
21573e8eea7Sjsing &r[3], &r[2], &r[1], &r[0]);
216df1d0ed5Sjsing a += 4;
217df1d0ed5Sjsing r += 4;
2188889fb99Sjsing num -= 4;
2198889fb99Sjsing }
2208889fb99Sjsing while (num) {
221df1d0ed5Sjsing bn_mulw_addw(a[0], w, carry, &carry, &r[0]);
222df1d0ed5Sjsing a++;
223df1d0ed5Sjsing r++;
2248889fb99Sjsing num--;
2258889fb99Sjsing }
226df1d0ed5Sjsing return carry;
2278889fb99Sjsing }
2288889fb99Sjsing #endif
2298889fb99Sjsing
23003b14b3bSjsing /*
23103b14b3bSjsing * bn_mul_add_words() computes (carry:r[i]) = a[i] * w + r[i] + carry, where
23203b14b3bSjsing * a is an array of words and w is a single word. This should really be called
23303b14b3bSjsing * bn_mulw_add_words() since only one input is an array. This is used as a step
23403b14b3bSjsing * in the multiplication of word arrays.
23503b14b3bSjsing */
23603b14b3bSjsing #ifndef HAVE_BN_MUL_ADD_WORDS
23703b14b3bSjsing BN_ULONG
bn_mul_add_words(BN_ULONG * r,const BN_ULONG * a,int num,BN_ULONG w)23803b14b3bSjsing bn_mul_add_words(BN_ULONG *r, const BN_ULONG *a, int num, BN_ULONG w)
23903b14b3bSjsing {
24003b14b3bSjsing BN_ULONG carry = 0;
24103b14b3bSjsing
24203b14b3bSjsing assert(num >= 0);
24303b14b3bSjsing if (num <= 0)
24403b14b3bSjsing return 0;
24503b14b3bSjsing
24603b14b3bSjsing while (num & ~3) {
24773e8eea7Sjsing bn_qwmulw_addqw_addw(a[3], a[2], a[1], a[0], w,
24873e8eea7Sjsing r[3], r[2], r[1], r[0], carry, &carry,
24973e8eea7Sjsing &r[3], &r[2], &r[1], &r[0]);
25003b14b3bSjsing a += 4;
25103b14b3bSjsing r += 4;
25203b14b3bSjsing num -= 4;
25303b14b3bSjsing }
25403b14b3bSjsing while (num) {
25503b14b3bSjsing bn_mulw_addw_addw(a[0], w, r[0], carry, &carry, &r[0]);
25603b14b3bSjsing a++;
25703b14b3bSjsing r++;
25803b14b3bSjsing num--;
25903b14b3bSjsing }
26003b14b3bSjsing
26103b14b3bSjsing return carry;
26203b14b3bSjsing }
26303b14b3bSjsing #endif
26403b14b3bSjsing
265e8d08ebaSjsing void
bn_mul_normal(BN_ULONG * r,BN_ULONG * a,int na,BN_ULONG * b,int nb)266e8d08ebaSjsing bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
267e8d08ebaSjsing {
268e8d08ebaSjsing BN_ULONG *rr;
269e8d08ebaSjsing
270e8d08ebaSjsing
271e8d08ebaSjsing if (na < nb) {
272e8d08ebaSjsing int itmp;
273e8d08ebaSjsing BN_ULONG *ltmp;
274e8d08ebaSjsing
275e8d08ebaSjsing itmp = na;
276e8d08ebaSjsing na = nb;
277e8d08ebaSjsing nb = itmp;
278e8d08ebaSjsing ltmp = a;
279e8d08ebaSjsing a = b;
280e8d08ebaSjsing b = ltmp;
281e8d08ebaSjsing
282e8d08ebaSjsing }
283e8d08ebaSjsing rr = &(r[na]);
284e8d08ebaSjsing if (nb <= 0) {
285e8d08ebaSjsing (void)bn_mul_words(r, a, na, 0);
286e8d08ebaSjsing return;
287e8d08ebaSjsing } else
288e8d08ebaSjsing rr[0] = bn_mul_words(r, a, na, b[0]);
289e8d08ebaSjsing
290e8d08ebaSjsing for (;;) {
291e8d08ebaSjsing if (--nb <= 0)
292e8d08ebaSjsing return;
293e8d08ebaSjsing rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
294e8d08ebaSjsing if (--nb <= 0)
295e8d08ebaSjsing return;
296e8d08ebaSjsing rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
297e8d08ebaSjsing if (--nb <= 0)
298e8d08ebaSjsing return;
299e8d08ebaSjsing rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
300e8d08ebaSjsing if (--nb <= 0)
301e8d08ebaSjsing return;
302e8d08ebaSjsing rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
303e8d08ebaSjsing rr += 4;
304e8d08ebaSjsing r += 4;
305e8d08ebaSjsing b += 4;
306e8d08ebaSjsing }
307e8d08ebaSjsing }
308e8d08ebaSjsing
309913ec974Sbeck
3109554b5edSjsing #ifndef HAVE_BN_MUL
3112bd9bb84Sjsing int
bn_mul(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,int rn,BN_CTX * ctx)3129554b5edSjsing bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx)
313913ec974Sbeck {
3149554b5edSjsing bn_mul_normal(r->d, a->d, a->top, b->d, b->top);
3159554b5edSjsing
3169554b5edSjsing return 1;
3179554b5edSjsing }
3189554b5edSjsing
3199554b5edSjsing #endif /* HAVE_BN_MUL */
3209554b5edSjsing
3219554b5edSjsing int
BN_mul(BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)3229554b5edSjsing BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
3239554b5edSjsing {
3249554b5edSjsing BIGNUM *rr;
3259554b5edSjsing int rn;
3269554b5edSjsing int ret = 0;
3279554b5edSjsing
3289554b5edSjsing BN_CTX_start(ctx);
3299554b5edSjsing
3309554b5edSjsing if (BN_is_zero(a) || BN_is_zero(b)) {
3319554b5edSjsing BN_zero(r);
3329554b5edSjsing goto done;
3339554b5edSjsing }
3349554b5edSjsing
3359554b5edSjsing rr = r;
3369554b5edSjsing if (rr == a || rr == b)
3379554b5edSjsing rr = BN_CTX_get(ctx);
3389554b5edSjsing if (rr == NULL)
3399554b5edSjsing goto err;
3409554b5edSjsing
3419554b5edSjsing rn = a->top + b->top;
3429554b5edSjsing if (rn < a->top)
3439554b5edSjsing goto err;
3449554b5edSjsing if (!bn_wexpand(rr, rn))
3459554b5edSjsing goto err;
3469554b5edSjsing
3479554b5edSjsing if (a->top == 4 && b->top == 4) {
3489554b5edSjsing bn_mul_comba4(rr->d, a->d, b->d);
3499554b5edSjsing } else if (a->top == 8 && b->top == 8) {
3509554b5edSjsing bn_mul_comba8(rr->d, a->d, b->d);
3519554b5edSjsing } else {
3529554b5edSjsing if (!bn_mul(rr, a, b, rn, ctx))
3539554b5edSjsing goto err;
3549554b5edSjsing }
3559554b5edSjsing
3569554b5edSjsing rr->top = rn;
3579554b5edSjsing bn_correct_top(rr);
3589554b5edSjsing
359896da13fSjsing BN_set_negative(rr, a->neg ^ b->neg);
360896da13fSjsing
361363923baStb if (!bn_copy(r, rr))
362363923baStb goto err;
3639554b5edSjsing done:
3649554b5edSjsing ret = 1;
3659554b5edSjsing err:
3669554b5edSjsing BN_CTX_end(ctx);
3679554b5edSjsing
3689554b5edSjsing return ret;
369913ec974Sbeck }
370*ca1d80d6Sbeck LCRYPTO_ALIAS(BN_mul);
371