/src/botan/src/lib/math/bigint/big_ops3.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * BigInt Binary Operators |
3 | | * (C) 1999-2007,2018 Jack Lloyd |
4 | | * 2016 Matthias Gierlings |
5 | | * |
6 | | * Botan is released under the Simplified BSD License (see license.txt) |
7 | | */ |
8 | | |
9 | | #include <botan/bigint.h> |
10 | | #include <botan/internal/divide.h> |
11 | | #include <botan/internal/mp_core.h> |
12 | | #include <botan/internal/bit_ops.h> |
13 | | #include <algorithm> |
14 | | |
15 | | namespace Botan { |
16 | | |
17 | | //static |
18 | | BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_words, BigInt::Sign y_sign) |
19 | 4.90M | { |
20 | 4.90M | const size_t x_sw = x.sig_words(); |
21 | | |
22 | 4.90M | BigInt z = BigInt::with_capacity(std::max(x_sw, y_words) + 1); |
23 | | |
24 | 4.90M | if(x.sign() == y_sign) |
25 | 2.75M | { |
26 | 2.75M | bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words); |
27 | 2.75M | z.set_sign(x.sign()); |
28 | 2.75M | } |
29 | 2.14M | else |
30 | 2.14M | { |
31 | 2.14M | const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words); |
32 | | |
33 | | //z.sign_fixup(relative_size, y_sign); |
34 | 2.14M | if(relative_size < 0) |
35 | 408k | z.set_sign(y_sign); |
36 | 1.74M | else if(relative_size == 0) |
37 | 495 | z.set_sign(BigInt::Positive); |
38 | 1.74M | else |
39 | 1.74M | z.set_sign(x.sign()); |
40 | 2.14M | } |
41 | | |
42 | 4.90M | return z; |
43 | 4.90M | } |
44 | | |
45 | | /* |
46 | | * Multiplication Operator |
47 | | */ |
48 | | BigInt operator*(const BigInt& x, const BigInt& y) |
49 | 3.08M | { |
50 | 3.08M | const size_t x_sw = x.sig_words(); |
51 | 3.08M | const size_t y_sw = y.sig_words(); |
52 | | |
53 | 3.08M | BigInt z = BigInt::with_capacity(x.size() + y.size()); |
54 | | |
55 | 3.08M | if(x_sw == 1 && y_sw) |
56 | 826k | bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0)); |
57 | 2.26M | else if(y_sw == 1 && x_sw) |
58 | 717k | bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0)); |
59 | 1.54M | else if(x_sw && y_sw) |
60 | 1.45M | { |
61 | 1.45M | secure_vector<word> workspace(z.size()); |
62 | | |
63 | 1.45M | bigint_mul(z.mutable_data(), z.size(), |
64 | 1.45M | x.data(), x.size(), x_sw, |
65 | 1.45M | y.data(), y.size(), y_sw, |
66 | 1.45M | workspace.data(), workspace.size()); |
67 | 1.45M | } |
68 | | |
69 | 3.08M | z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign()); |
70 | | |
71 | 3.08M | return z; |
72 | 3.08M | } |
73 | | |
74 | | /* |
75 | | * Multiplication Operator |
76 | | */ |
77 | | BigInt operator*(const BigInt& x, word y) |
78 | 6.79M | { |
79 | 6.79M | const size_t x_sw = x.sig_words(); |
80 | | |
81 | 6.79M | BigInt z = BigInt::with_capacity(x_sw + 1); |
82 | | |
83 | 6.79M | if(x_sw && y) |
84 | 3.39M | { |
85 | 3.39M | bigint_linmul3(z.mutable_data(), x.data(), x_sw, y); |
86 | 3.39M | z.set_sign(x.sign()); |
87 | 3.39M | } |
88 | | |
89 | 6.79M | return z; |
90 | 6.79M | } |
91 | | |
92 | | /* |
93 | | * Division Operator |
94 | | */ |
95 | | BigInt operator/(const BigInt& x, const BigInt& y) |
96 | 1.63k | { |
97 | 1.63k | if(y.sig_words() == 1) |
98 | 338 | { |
99 | 338 | return x / y.word_at(0); |
100 | 338 | } |
101 | | |
102 | 1.29k | BigInt q, r; |
103 | 1.29k | vartime_divide(x, y, q, r); |
104 | 1.29k | return q; |
105 | 1.63k | } |
106 | | |
107 | | /* |
108 | | * Division Operator |
109 | | */ |
110 | | BigInt operator/(const BigInt& x, word y) |
111 | 3.65M | { |
112 | 3.65M | if(y == 0) |
113 | 0 | throw Invalid_Argument("BigInt::operator/ divide by zero"); |
114 | | |
115 | 3.65M | BigInt q; |
116 | 3.65M | word r; |
117 | 3.65M | ct_divide_word(x, y, q, r); |
118 | 3.65M | return q; |
119 | 3.65M | } |
120 | | |
121 | | /* |
122 | | * Modulo Operator |
123 | | */ |
124 | | BigInt operator%(const BigInt& n, const BigInt& mod) |
125 | 3.82M | { |
126 | 3.82M | if(mod.is_zero()) |
127 | 0 | throw Invalid_Argument("BigInt::operator% divide by zero"); |
128 | 3.82M | if(mod.is_negative()) |
129 | 0 | throw Invalid_Argument("BigInt::operator% modulus must be > 0"); |
130 | 3.82M | if(n.is_positive() && mod.is_positive() && n < mod) |
131 | 122k | return n; |
132 | | |
133 | 3.70M | if(mod.sig_words() == 1) |
134 | 680k | { |
135 | 680k | return BigInt::from_word(n % mod.word_at(0)); |
136 | 680k | } |
137 | | |
138 | 3.02M | BigInt q, r; |
139 | 3.02M | vartime_divide(n, mod, q, r); |
140 | 3.02M | return r; |
141 | 3.70M | } |
142 | | |
143 | | /* |
144 | | * Modulo Operator |
145 | | */ |
146 | | word operator%(const BigInt& n, word mod) |
147 | 9.02M | { |
148 | 9.02M | if(mod == 0) |
149 | 0 | throw Invalid_Argument("BigInt::operator% divide by zero"); |
150 | | |
151 | 9.02M | if(mod == 1) |
152 | 812 | return 0; |
153 | | |
154 | 9.02M | word remainder = 0; |
155 | | |
156 | 9.02M | if(is_power_of_2(mod)) |
157 | 8.34M | { |
158 | 8.34M | remainder = (n.word_at(0) & (mod - 1)); |
159 | 8.34M | } |
160 | 678k | else |
161 | 678k | { |
162 | 678k | const size_t sw = n.sig_words(); |
163 | 1.47M | for(size_t i = sw; i > 0; --i) |
164 | 791k | { |
165 | 791k | remainder = bigint_modop(remainder, n.word_at(i-1), mod); |
166 | 791k | } |
167 | 678k | } |
168 | | |
169 | 9.02M | if(remainder && n.sign() == BigInt::Negative) |
170 | 607 | return mod - remainder; |
171 | 9.02M | return remainder; |
172 | 9.02M | } |
173 | | |
174 | | /* |
175 | | * Left Shift Operator |
176 | | */ |
177 | | BigInt operator<<(const BigInt& x, size_t shift) |
178 | 3.02M | { |
179 | 3.02M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS, |
180 | 3.02M | shift_bits = shift % BOTAN_MP_WORD_BITS; |
181 | | |
182 | 3.02M | const size_t x_sw = x.sig_words(); |
183 | | |
184 | 3.02M | BigInt y = BigInt::with_capacity(x_sw + shift_words + (shift_bits ? 1 : 0)); |
185 | 3.02M | bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); |
186 | 3.02M | y.set_sign(x.sign()); |
187 | 3.02M | return y; |
188 | 3.02M | } |
189 | | |
190 | | /* |
191 | | * Right Shift Operator |
192 | | */ |
193 | | BigInt operator>>(const BigInt& x, size_t shift) |
194 | 25.1k | { |
195 | 25.1k | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
196 | 25.1k | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
197 | 25.1k | const size_t x_sw = x.sig_words(); |
198 | | |
199 | 25.1k | if(shift_words >= x_sw) |
200 | 0 | return BigInt::zero(); |
201 | | |
202 | 25.1k | BigInt y = BigInt::with_capacity(x_sw - shift_words); |
203 | 25.1k | bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); |
204 | | |
205 | 25.1k | if(x.is_negative() && y.is_zero()) |
206 | 0 | y.set_sign(BigInt::Positive); |
207 | 25.1k | else |
208 | 25.1k | y.set_sign(x.sign()); |
209 | | |
210 | 25.1k | return y; |
211 | 25.1k | } |
212 | | |
213 | | } |