/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 | | |
11 | | #include <botan/internal/bit_ops.h> |
12 | | #include <botan/internal/divide.h> |
13 | | #include <botan/internal/mp_core.h> |
14 | | #include <algorithm> |
15 | | |
16 | | namespace Botan { |
17 | | |
18 | | //static |
19 | 2.32k | BigInt BigInt::add2(const BigInt& x, const word y[], size_t y_words, BigInt::Sign y_sign) { |
20 | 2.32k | const size_t x_sw = x.sig_words(); |
21 | | |
22 | 2.32k | BigInt z = BigInt::with_capacity(std::max(x_sw, y_words) + 1); |
23 | | |
24 | 2.32k | if(x.sign() == y_sign) { |
25 | 2.32k | bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words); |
26 | 2.32k | z.set_sign(x.sign()); |
27 | 2.32k | } else { |
28 | 0 | const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words); |
29 | | |
30 | | //z.sign_fixup(relative_size, y_sign); |
31 | 0 | if(relative_size < 0) { |
32 | 0 | z.set_sign(y_sign); |
33 | 0 | } else if(relative_size == 0) { |
34 | 0 | z.set_sign(BigInt::Positive); |
35 | 0 | } else { |
36 | 0 | z.set_sign(x.sign()); |
37 | 0 | } |
38 | 0 | } |
39 | | |
40 | 2.32k | return z; |
41 | 2.32k | } |
42 | | |
43 | | /* |
44 | | * Multiplication Operator |
45 | | */ |
46 | 2.32k | BigInt operator*(const BigInt& x, const BigInt& y) { |
47 | 2.32k | const size_t x_sw = x.sig_words(); |
48 | 2.32k | const size_t y_sw = y.sig_words(); |
49 | | |
50 | 2.32k | BigInt z = BigInt::with_capacity(x.size() + y.size()); |
51 | | |
52 | 2.32k | if(x_sw == 1 && y_sw) { |
53 | 842 | bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0)); |
54 | 1.48k | } else if(y_sw == 1 && x_sw) { |
55 | 620 | bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0)); |
56 | 863 | } else if(x_sw && y_sw) { |
57 | 230 | secure_vector<word> workspace(z.size()); |
58 | | |
59 | 230 | bigint_mul(z.mutable_data(), |
60 | 230 | z.size(), |
61 | 230 | x.data(), |
62 | 230 | x.size(), |
63 | 230 | x_sw, |
64 | 230 | y.data(), |
65 | 230 | y.size(), |
66 | 230 | y_sw, |
67 | 230 | workspace.data(), |
68 | 230 | workspace.size()); |
69 | 230 | } |
70 | | |
71 | 2.32k | z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign()); |
72 | | |
73 | 2.32k | return z; |
74 | 2.32k | } |
75 | | |
76 | | /* |
77 | | * Multiplication Operator |
78 | | */ |
79 | 30.0k | BigInt operator*(const BigInt& x, word y) { |
80 | 30.0k | const size_t x_sw = x.sig_words(); |
81 | | |
82 | 30.0k | BigInt z = BigInt::with_capacity(x_sw + 1); |
83 | | |
84 | 30.0k | if(x_sw && y) { |
85 | 12.7k | bigint_linmul3(z.mutable_data(), x.data(), x_sw, y); |
86 | 12.7k | z.set_sign(x.sign()); |
87 | 12.7k | } |
88 | | |
89 | 30.0k | return z; |
90 | 30.0k | } |
91 | | |
92 | | /* |
93 | | * Division Operator |
94 | | */ |
95 | 0 | BigInt operator/(const BigInt& x, const BigInt& y) { |
96 | 0 | if(y.sig_words() == 1) { |
97 | 0 | return x / y.word_at(0); |
98 | 0 | } |
99 | | |
100 | 0 | BigInt q, r; |
101 | 0 | vartime_divide(x, y, q, r); |
102 | 0 | return q; |
103 | 0 | } |
104 | | |
105 | | /* |
106 | | * Division Operator |
107 | | */ |
108 | 0 | BigInt operator/(const BigInt& x, word y) { |
109 | 0 | if(y == 0) { |
110 | 0 | throw Invalid_Argument("BigInt::operator/ divide by zero"); |
111 | 0 | } |
112 | | |
113 | 0 | BigInt q; |
114 | 0 | word r; |
115 | 0 | ct_divide_word(x, y, q, r); |
116 | 0 | return q; |
117 | 0 | } |
118 | | |
119 | | /* |
120 | | * Modulo Operator |
121 | | */ |
122 | 0 | BigInt operator%(const BigInt& n, const BigInt& mod) { |
123 | 0 | if(mod.is_zero()) { |
124 | 0 | throw Invalid_Argument("BigInt::operator% divide by zero"); |
125 | 0 | } |
126 | 0 | if(mod.is_negative()) { |
127 | 0 | throw Invalid_Argument("BigInt::operator% modulus must be > 0"); |
128 | 0 | } |
129 | 0 | if(n.is_positive() && mod.is_positive() && n < mod) { |
130 | 0 | return n; |
131 | 0 | } |
132 | | |
133 | 0 | if(mod.sig_words() == 1) { |
134 | 0 | return BigInt::from_word(n % mod.word_at(0)); |
135 | 0 | } |
136 | | |
137 | 0 | BigInt q, r; |
138 | 0 | vartime_divide(n, mod, q, r); |
139 | 0 | return r; |
140 | 0 | } |
141 | | |
142 | | /* |
143 | | * Modulo Operator |
144 | | */ |
145 | 0 | word operator%(const BigInt& n, word mod) { |
146 | 0 | if(mod == 0) { |
147 | 0 | throw Invalid_Argument("BigInt::operator% divide by zero"); |
148 | 0 | } |
149 | | |
150 | 0 | if(mod == 1) { |
151 | 0 | return 0; |
152 | 0 | } |
153 | | |
154 | 0 | word remainder = 0; |
155 | |
|
156 | 0 | if(is_power_of_2(mod)) { |
157 | 0 | remainder = (n.word_at(0) & (mod - 1)); |
158 | 0 | } else { |
159 | 0 | const size_t sw = n.sig_words(); |
160 | 0 | for(size_t i = sw; i > 0; --i) { |
161 | 0 | remainder = bigint_modop(remainder, n.word_at(i - 1), mod); |
162 | 0 | } |
163 | 0 | } |
164 | |
|
165 | 0 | if(remainder && n.sign() == BigInt::Negative) { |
166 | 0 | return mod - remainder; |
167 | 0 | } |
168 | 0 | return remainder; |
169 | 0 | } |
170 | | |
171 | | /* |
172 | | * Left Shift Operator |
173 | | */ |
174 | 2.32k | BigInt operator<<(const BigInt& x, size_t shift) { |
175 | 2.32k | const size_t shift_words = shift / BOTAN_MP_WORD_BITS, shift_bits = shift % BOTAN_MP_WORD_BITS; |
176 | | |
177 | 2.32k | const size_t x_sw = x.sig_words(); |
178 | | |
179 | 2.32k | BigInt y = BigInt::with_capacity(x_sw + shift_words + (shift_bits ? 1 : 0)); |
180 | 2.32k | bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); |
181 | 2.32k | y.set_sign(x.sign()); |
182 | 2.32k | return y; |
183 | 2.32k | } |
184 | | |
185 | | /* |
186 | | * Right Shift Operator |
187 | | */ |
188 | 0 | BigInt operator>>(const BigInt& x, size_t shift) { |
189 | 0 | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
190 | 0 | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
191 | 0 | const size_t x_sw = x.sig_words(); |
192 | |
|
193 | 0 | if(shift_words >= x_sw) { |
194 | 0 | return BigInt::zero(); |
195 | 0 | } |
196 | | |
197 | 0 | BigInt y = BigInt::with_capacity(x_sw - shift_words); |
198 | 0 | bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); |
199 | |
|
200 | 0 | if(x.is_negative() && y.is_zero()) { |
201 | 0 | y.set_sign(BigInt::Positive); |
202 | 0 | } else { |
203 | 0 | y.set_sign(x.sign()); |
204 | 0 | } |
205 | |
|
206 | 0 | return y; |
207 | 0 | } |
208 | | |
209 | | } // namespace Botan |