GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcrypto/bn/bn_add.c Lines: 104 115 90.4 %
Date: 2017-11-13 Branches: 73 84 86.9 %

Line Branch Exec Source
1
/* $OpenBSD: bn_add.c,v 1.11 2017/01/29 17:49:22 beck Exp $ */
2
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3
 * All rights reserved.
4
 *
5
 * This package is an SSL implementation written
6
 * by Eric Young (eay@cryptsoft.com).
7
 * The implementation was written so as to conform with Netscapes SSL.
8
 *
9
 * This library is free for commercial and non-commercial use as long as
10
 * the following conditions are aheared to.  The following conditions
11
 * apply to all code found in this distribution, be it the RC4, RSA,
12
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
13
 * included with this distribution is covered by the same copyright terms
14
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15
 *
16
 * Copyright remains Eric Young's, and as such any Copyright notices in
17
 * the code are not to be removed.
18
 * If this package is used in a product, Eric Young should be given attribution
19
 * as the author of the parts of the library used.
20
 * This can be in the form of a textual message at program startup or
21
 * in documentation (online or textual) provided with the package.
22
 *
23
 * Redistribution and use in source and binary forms, with or without
24
 * modification, are permitted provided that the following conditions
25
 * are met:
26
 * 1. Redistributions of source code must retain the copyright
27
 *    notice, this list of conditions and the following disclaimer.
28
 * 2. Redistributions in binary form must reproduce the above copyright
29
 *    notice, this list of conditions and the following disclaimer in the
30
 *    documentation and/or other materials provided with the distribution.
31
 * 3. All advertising materials mentioning features or use of this software
32
 *    must display the following acknowledgement:
33
 *    "This product includes cryptographic software written by
34
 *     Eric Young (eay@cryptsoft.com)"
35
 *    The word 'cryptographic' can be left out if the rouines from the library
36
 *    being used are not cryptographic related :-).
37
 * 4. If you include any Windows specific code (or a derivative thereof) from
38
 *    the apps directory (application code) you must include an acknowledgement:
39
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40
 *
41
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51
 * SUCH DAMAGE.
52
 *
53
 * The licence and distribution terms for any publically available version or
54
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
55
 * copied and put under another distribution licence
56
 * [including the GNU Public Licence.]
57
 */
58
59
#include <stdio.h>
60
61
#include <openssl/err.h>
62
63
#include "bn_lcl.h"
64
65
/* r can == a or b */
66
int
67
BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
68
{
69
	const BIGNUM *tmp;
70
16327132
	int a_neg = a->neg, ret;
71
72
	bn_check_top(a);
73
	bn_check_top(b);
74
75
	/*  a +  b	a+b
76
	 *  a + -b	a-b
77
	 * -a +  b	b-a
78
	 * -a + -b	-(a+b)
79
	 */
80
8163566
	if (a_neg ^ b->neg) {
81
		/* only one is negative */
82
3017481
		if (a_neg)
83
				{ tmp = a;
84
			a = b;
85
			b = tmp;
86
3016333
		}
87
88
		/* we are now a - b */
89
90
3017481
		if (BN_ucmp(a, b) < 0) {
91
959
			if (!BN_usub(r, b, a))
92
				return (0);
93
			r->neg = 1;
94
959
		} else {
95
3016522
			if (!BN_usub(r, a, b))
96
				return (0);
97
			r->neg = 0;
98
		}
99
3017481
		return (1);
100
	}
101
102
5146085
	ret = BN_uadd(r, a, b);
103
5146085
	r->neg = a_neg;
104
	bn_check_top(r);
105
5146085
	return ret;
106
8163566
}
107
108
/* unsigned add of b to a */
109
int
110
BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
111
{
112
	int max, min, dif;
113
	BN_ULONG *ap, *bp, *rp, carry, t1, t2;
114
	const BIGNUM *tmp;
115
116
	bn_check_top(a);
117
	bn_check_top(b);
118
119
16218862
	if (a->top < b->top) {
120
		tmp = a;
121
		a = b;
122
		b = tmp;
123
50681
	}
124
8109431
	max = a->top;
125
8109431
	min = b->top;
126
8109431
	dif = max - min;
127
128

16275630
	if (bn_wexpand(r, max + 1) == NULL)
129
		return 0;
130
131
8109431
	r->top = max;
132
133
8109431
	ap = a->d;
134
8109431
	bp = b->d;
135
8109431
	rp = r->d;
136
137
8109431
	carry = bn_add_words(rp, ap, bp, min);
138
8109431
	rp += min;
139
8109431
	ap += min;
140
	bp += min;
141
142
8109431
	if (carry) {
143
2363144
		while (dif) {
144
46961
			dif--;
145
46961
			t1 = *(ap++);
146
46961
			t2 = (t1 + 1) & BN_MASK2;
147
46961
			*(rp++) = t2;
148
46961
			if (t2) {
149
				carry = 0;
150
46251
				break;
151
			}
152
		}
153
1180862
		if (carry) {
154
			/* carry != 0 => dif == 0 */
155
1134611
			*rp = 1;
156
1134611
			r->top++;
157
1134611
		}
158
	}
159

9599626
	if (dif && rp != ap)
160
1158024
		while (dif--)
161
			/* copy remaining words if ap != rp */
162
503122
			*(rp++) = *(ap++);
163
8109431
	r->neg = 0;
164
	bn_check_top(r);
165
8109431
	return 1;
166
8109431
}
167
168
/* unsigned subtraction of b from a, a must be larger than b. */
169
int
170
BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
171
{
172
	int max, min, dif;
173
	BN_ULONG t1, t2, *ap, *bp, *rp;
174
	int i, carry;
175
176
	bn_check_top(a);
177
	bn_check_top(b);
178
179
32905790
	max = a->top;
180
16452895
	min = b->top;
181
16452895
	dif = max - min;
182
183
16452895
	if (dif < 0)	/* hmm... should not be happening */
184
	{
185
		BNerror(BN_R_ARG2_LT_ARG3);
186
		return (0);
187
	}
188
189

32909205
	if (bn_wexpand(r, max) == NULL)
190
		return (0);
191
192
16452895
	ap = a->d;
193
16452895
	bp = b->d;
194
16452895
	rp = r->d;
195
196
#if 1
197
	carry = 0;
198
196084194
	for (i = min; i != 0; i--) {
199
81589202
		t1= *(ap++);
200
81589202
		t2= *(bp++);
201
81589202
		if (carry) {
202
30784297
			carry = (t1 <= t2);
203
30784297
			t1 = (t1 - t2 - 1)&BN_MASK2;
204
30784297
		} else {
205
50804905
			carry = (t1 < t2);
206
50804905
			t1 = (t1 - t2)&BN_MASK2;
207
		}
208
81589202
		*(rp++) = t1&BN_MASK2;
209
	}
210
#else
211
	carry = bn_sub_words(rp, ap, bp, min);
212
	ap += min;
213
	bp += min;
214
	rp += min;
215
#endif
216
16452895
	if (carry) /* subtracted */
217
	{
218
4728780
		if (!dif)
219
			/* error: a < b */
220
			return 0;
221
9458338
		while (dif) {
222
4729169
			dif--;
223
4729169
			t1 = *(ap++);
224
4729169
			t2 = (t1 - 1)&BN_MASK2;
225
4729169
			*(rp++) = t2;
226
4729169
			if (t1)
227
				break;
228
		}
229
	}
230
#if 0
231
	memcpy(rp, ap, sizeof(*rp)*(max - i));
232
#else
233
16452895
	if (rp != ap) {
234
8773951
		for (;;) {
235
8773951
			if (!dif--)
236
				break;
237
17419
			rp[0] = ap[0];
238
17419
			if (!dif--)
239
				break;
240
10647
			rp[1] = ap[1];
241
10647
			if (!dif--)
242
				break;
243
7843
			rp[2] = ap[2];
244
7843
			if (!dif--)
245
				break;
246
6779
			rp[3] = ap[3];
247
6779
			rp += 4;
248
6779
			ap += 4;
249
		}
250
	}
251
#endif
252
253
16452895
	r->top = max;
254
16452895
	r->neg = 0;
255

107191207
	bn_correct_top(r);
256
16452895
	return (1);
257
16452895
}
258
259
int
260
BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
261
{
262
	int max;
263
	int add = 0, neg = 0;
264
	const BIGNUM *tmp;
265
266
	bn_check_top(a);
267
	bn_check_top(b);
268
269
	/*  a -  b	a-b
270
	 *  a - -b	a+b
271
	 * -a -  b	-(a+b)
272
	 * -a - -b	b-a
273
	 */
274
22206686
	if (a->neg) {
275
5624
		if (b->neg) {
276
			tmp = a;
277
			a = b;
278
			b = tmp;
279
4555
		} else {
280
			add = 1;
281
			neg = 1;
282
		}
283
	} else {
284
11097719
		if (b->neg) {
285
			add = 1;
286
			neg = 0;
287
897
		}
288
	}
289
290
11103343
	if (add) {
291
1966
		if (!BN_uadd(r, a, b))
292
			return (0);
293
1966
		r->neg = neg;
294
1966
		return (1);
295
	}
296
297
	/* We are actually doing a - b :-) */
298
299
11101377
	max = (a->top > b->top) ? a->top : b->top;
300

22274106
	if (bn_wexpand(r, max) == NULL)
301
		return (0);
302
11101377
	if (BN_ucmp(a, b) < 0) {
303
3030824
		if (!BN_usub(r, b, a))
304
			return (0);
305
		r->neg = 1;
306
3030824
	} else {
307
8070553
		if (!BN_usub(r, a, b))
308
			return (0);
309
		r->neg = 0;
310
	}
311
	bn_check_top(r);
312
11101377
	return (1);
313
11103343
}