1 | /* |
2 | * Copyright 1995-2016 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 | BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) |
14 | { |
15 | #ifndef BN_LLONG |
16 | BN_ULONG ret = 0; |
17 | #else |
18 | BN_ULLONG ret = 0; |
19 | #endif |
20 | int i; |
21 | |
22 | if (w == 0) |
23 | return (BN_ULONG)-1; |
24 | |
25 | #ifndef BN_LLONG |
26 | /* |
27 | * If |w| is too long and we don't have BN_ULLONG then we need to fall |
28 | * back to using BN_div_word |
29 | */ |
30 | if (w > ((BN_ULONG)1 << BN_BITS4)) { |
31 | BIGNUM *tmp = BN_dup(a); |
32 | if (tmp == NULL) |
33 | return (BN_ULONG)-1; |
34 | |
35 | ret = BN_div_word(tmp, w); |
36 | BN_free(tmp); |
37 | |
38 | return ret; |
39 | } |
40 | #endif |
41 | |
42 | bn_check_top(a); |
43 | w &= BN_MASK2; |
44 | for (i = a->top - 1; i >= 0; i--) { |
45 | #ifndef BN_LLONG |
46 | /* |
47 | * We can assume here that | w <= ((BN_ULONG)1 << BN_BITS4) | and so |
48 | * | ret < ((BN_ULONG)1 << BN_BITS4) | and therefore the shifts here are |
49 | * safe and will not overflow |
50 | */ |
51 | ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w; |
52 | ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w; |
53 | #else |
54 | ret = (BN_ULLONG) (((ret << (BN_ULLONG) BN_BITS2) | a->d[i]) % |
55 | (BN_ULLONG) w); |
56 | #endif |
57 | } |
58 | return (BN_ULONG)ret; |
59 | } |
60 | |
61 | BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w) |
62 | { |
63 | BN_ULONG ret = 0; |
64 | int i, j; |
65 | |
66 | bn_check_top(a); |
67 | w &= BN_MASK2; |
68 | |
69 | if (!w) |
70 | /* actually this an error (division by zero) */ |
71 | return (BN_ULONG)-1; |
72 | if (a->top == 0) |
73 | return 0; |
74 | |
75 | /* normalize input (so bn_div_words doesn't complain) */ |
76 | j = BN_BITS2 - BN_num_bits_word(w); |
77 | w <<= j; |
78 | if (!BN_lshift(a, a, j)) |
79 | return (BN_ULONG)-1; |
80 | |
81 | for (i = a->top - 1; i >= 0; i--) { |
82 | BN_ULONG l, d; |
83 | |
84 | l = a->d[i]; |
85 | d = bn_div_words(ret, l, w); |
86 | ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2; |
87 | a->d[i] = d; |
88 | } |
89 | if ((a->top > 0) && (a->d[a->top - 1] == 0)) |
90 | a->top--; |
91 | ret >>= j; |
92 | if (!a->top) |
93 | a->neg = 0; /* don't allow negative zero */ |
94 | bn_check_top(a); |
95 | return ret; |
96 | } |
97 | |
98 | int BN_add_word(BIGNUM *a, BN_ULONG w) |
99 | { |
100 | BN_ULONG l; |
101 | int i; |
102 | |
103 | bn_check_top(a); |
104 | w &= BN_MASK2; |
105 | |
106 | /* degenerate case: w is zero */ |
107 | if (!w) |
108 | return 1; |
109 | /* degenerate case: a is zero */ |
110 | if (BN_is_zero(a)) |
111 | return BN_set_word(a, w); |
112 | /* handle 'a' when negative */ |
113 | if (a->neg) { |
114 | a->neg = 0; |
115 | i = BN_sub_word(a, w); |
116 | if (!BN_is_zero(a)) |
117 | a->neg = !(a->neg); |
118 | return i; |
119 | } |
120 | for (i = 0; w != 0 && i < a->top; i++) { |
121 | a->d[i] = l = (a->d[i] + w) & BN_MASK2; |
122 | w = (w > l) ? 1 : 0; |
123 | } |
124 | if (w && i == a->top) { |
125 | if (bn_wexpand(a, a->top + 1) == NULL) |
126 | return 0; |
127 | a->top++; |
128 | a->d[i] = w; |
129 | } |
130 | bn_check_top(a); |
131 | return 1; |
132 | } |
133 | |
134 | int BN_sub_word(BIGNUM *a, BN_ULONG w) |
135 | { |
136 | int i; |
137 | |
138 | bn_check_top(a); |
139 | w &= BN_MASK2; |
140 | |
141 | /* degenerate case: w is zero */ |
142 | if (!w) |
143 | return 1; |
144 | /* degenerate case: a is zero */ |
145 | if (BN_is_zero(a)) { |
146 | i = BN_set_word(a, w); |
147 | if (i != 0) |
148 | BN_set_negative(a, 1); |
149 | return i; |
150 | } |
151 | /* handle 'a' when negative */ |
152 | if (a->neg) { |
153 | a->neg = 0; |
154 | i = BN_add_word(a, w); |
155 | a->neg = 1; |
156 | return i; |
157 | } |
158 | |
159 | if ((a->top == 1) && (a->d[0] < w)) { |
160 | a->d[0] = w - a->d[0]; |
161 | a->neg = 1; |
162 | return 1; |
163 | } |
164 | i = 0; |
165 | for (;;) { |
166 | if (a->d[i] >= w) { |
167 | a->d[i] -= w; |
168 | break; |
169 | } else { |
170 | a->d[i] = (a->d[i] - w) & BN_MASK2; |
171 | i++; |
172 | w = 1; |
173 | } |
174 | } |
175 | if ((a->d[i] == 0) && (i == (a->top - 1))) |
176 | a->top--; |
177 | bn_check_top(a); |
178 | return 1; |
179 | } |
180 | |
181 | int BN_mul_word(BIGNUM *a, BN_ULONG w) |
182 | { |
183 | BN_ULONG ll; |
184 | |
185 | bn_check_top(a); |
186 | w &= BN_MASK2; |
187 | if (a->top) { |
188 | if (w == 0) |
189 | BN_zero(a); |
190 | else { |
191 | ll = bn_mul_words(a->d, a->d, a->top, w); |
192 | if (ll) { |
193 | if (bn_wexpand(a, a->top + 1) == NULL) |
194 | return 0; |
195 | a->d[a->top++] = ll; |
196 | } |
197 | } |
198 | } |
199 | bn_check_top(a); |
200 | return 1; |
201 | } |
202 | |