1 | /* |
2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. |
3 | * |
4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
5 | * this file except in compliance with the License. You can obtain a copy |
6 | * in the file LICENSE in the source distribution or at |
7 | * https://www.openssl.org/source/license.html |
8 | */ |
9 | |
10 | #include "internal/cryptlib.h" |
11 | #include "bn_local.h" |
12 | |
13 | /* signed add of b to a. */ |
14 | int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) |
15 | { |
16 | int ret, r_neg, cmp_res; |
17 | |
18 | bn_check_top(a); |
19 | bn_check_top(b); |
20 | |
21 | if (a->neg == b->neg) { |
22 | r_neg = a->neg; |
23 | ret = BN_uadd(r, a, b); |
24 | } else { |
25 | cmp_res = BN_ucmp(a, b); |
26 | if (cmp_res > 0) { |
27 | r_neg = a->neg; |
28 | ret = BN_usub(r, a, b); |
29 | } else if (cmp_res < 0) { |
30 | r_neg = b->neg; |
31 | ret = BN_usub(r, b, a); |
32 | } else { |
33 | r_neg = 0; |
34 | BN_zero(r); |
35 | ret = 1; |
36 | } |
37 | } |
38 | |
39 | r->neg = r_neg; |
40 | bn_check_top(r); |
41 | return ret; |
42 | } |
43 | |
44 | /* signed sub of b from a. */ |
45 | int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) |
46 | { |
47 | int ret, r_neg, cmp_res; |
48 | |
49 | bn_check_top(a); |
50 | bn_check_top(b); |
51 | |
52 | if (a->neg != b->neg) { |
53 | r_neg = a->neg; |
54 | ret = BN_uadd(r, a, b); |
55 | } else { |
56 | cmp_res = BN_ucmp(a, b); |
57 | if (cmp_res > 0) { |
58 | r_neg = a->neg; |
59 | ret = BN_usub(r, a, b); |
60 | } else if (cmp_res < 0) { |
61 | r_neg = !b->neg; |
62 | ret = BN_usub(r, b, a); |
63 | } else { |
64 | r_neg = 0; |
65 | BN_zero(r); |
66 | ret = 1; |
67 | } |
68 | } |
69 | |
70 | r->neg = r_neg; |
71 | bn_check_top(r); |
72 | return ret; |
73 | } |
74 | |
75 | /* unsigned add of b to a, r can be equal to a or b. */ |
76 | int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) |
77 | { |
78 | int max, min, dif; |
79 | const BN_ULONG *ap, *bp; |
80 | BN_ULONG *rp, carry, t1, t2; |
81 | |
82 | bn_check_top(a); |
83 | bn_check_top(b); |
84 | |
85 | if (a->top < b->top) { |
86 | const BIGNUM *tmp; |
87 | |
88 | tmp = a; |
89 | a = b; |
90 | b = tmp; |
91 | } |
92 | max = a->top; |
93 | min = b->top; |
94 | dif = max - min; |
95 | |
96 | if (bn_wexpand(r, max + 1) == NULL) |
97 | return 0; |
98 | |
99 | r->top = max; |
100 | |
101 | ap = a->d; |
102 | bp = b->d; |
103 | rp = r->d; |
104 | |
105 | carry = bn_add_words(rp, ap, bp, min); |
106 | rp += min; |
107 | ap += min; |
108 | |
109 | while (dif) { |
110 | dif--; |
111 | t1 = *(ap++); |
112 | t2 = (t1 + carry) & BN_MASK2; |
113 | *(rp++) = t2; |
114 | carry &= (t2 == 0); |
115 | } |
116 | *rp = carry; |
117 | r->top += carry; |
118 | |
119 | r->neg = 0; |
120 | bn_check_top(r); |
121 | return 1; |
122 | } |
123 | |
124 | /* unsigned subtraction of b from a, a must be larger than b. */ |
125 | int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) |
126 | { |
127 | int max, min, dif; |
128 | BN_ULONG t1, t2, borrow, *rp; |
129 | const BN_ULONG *ap, *bp; |
130 | |
131 | bn_check_top(a); |
132 | bn_check_top(b); |
133 | |
134 | max = a->top; |
135 | min = b->top; |
136 | dif = max - min; |
137 | |
138 | if (dif < 0) { /* hmm... should not be happening */ |
139 | BNerr(BN_F_BN_USUB, BN_R_ARG2_LT_ARG3); |
140 | return 0; |
141 | } |
142 | |
143 | if (bn_wexpand(r, max) == NULL) |
144 | return 0; |
145 | |
146 | ap = a->d; |
147 | bp = b->d; |
148 | rp = r->d; |
149 | |
150 | borrow = bn_sub_words(rp, ap, bp, min); |
151 | ap += min; |
152 | rp += min; |
153 | |
154 | while (dif) { |
155 | dif--; |
156 | t1 = *(ap++); |
157 | t2 = (t1 - borrow) & BN_MASK2; |
158 | *(rp++) = t2; |
159 | borrow &= (t1 == 0); |
160 | } |
161 | |
162 | while (max && *--rp == 0) |
163 | max--; |
164 | |
165 | r->top = max; |
166 | r->neg = 0; |
167 | bn_pollute(r); |
168 | |
169 | return 1; |
170 | } |
171 | |
172 | |