/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/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 | 3.03M | { |
20 | 3.03M | const size_t x_sw = x.sig_words(); |
21 | 3.03M | |
22 | 3.03M | BigInt z(x.sign(), std::max(x_sw, y_words) + 1); |
23 | 3.03M | |
24 | 3.03M | if(x.sign() == y_sign) |
25 | 1.59M | { |
26 | 1.59M | bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words); |
27 | 1.59M | } |
28 | 1.44M | else |
29 | 1.44M | { |
30 | 1.44M | const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words); |
31 | 1.44M | |
32 | | //z.sign_fixup(relative_size, y_sign); |
33 | 1.44M | if(relative_size < 0) |
34 | 188k | z.set_sign(y_sign); |
35 | 1.25M | else if(relative_size == 0) |
36 | 313 | z.set_sign(BigInt::Positive); |
37 | 1.44M | } |
38 | 3.03M | |
39 | 3.03M | return z; |
40 | 3.03M | } |
41 | | |
42 | | /* |
43 | | * Multiplication Operator |
44 | | */ |
45 | | BigInt operator*(const BigInt& x, const BigInt& y) |
46 | 1.78M | { |
47 | 1.78M | const size_t x_sw = x.sig_words(); |
48 | 1.78M | const size_t y_sw = y.sig_words(); |
49 | 1.78M | |
50 | 1.78M | BigInt z(BigInt::Positive, x.size() + y.size()); |
51 | 1.78M | |
52 | 1.78M | if(x_sw == 1 && y_sw) |
53 | 374k | bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0)); |
54 | 1.40M | else if(y_sw == 1 && x_sw) |
55 | 327k | bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0)); |
56 | 1.07M | else if(x_sw && y_sw) |
57 | 1.01M | { |
58 | 1.01M | secure_vector<word> workspace(z.size()); |
59 | 1.01M | |
60 | 1.01M | bigint_mul(z.mutable_data(), z.size(), |
61 | 1.01M | x.data(), x.size(), x_sw, |
62 | 1.01M | y.data(), y.size(), y_sw, |
63 | 1.01M | workspace.data(), workspace.size()); |
64 | 1.01M | } |
65 | 1.78M | |
66 | 1.78M | z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign()); |
67 | 1.78M | |
68 | 1.78M | return z; |
69 | 1.78M | } |
70 | | |
71 | | /* |
72 | | * Multiplication Operator |
73 | | */ |
74 | | BigInt operator*(const BigInt& x, word y) |
75 | 6.02M | { |
76 | 6.02M | const size_t x_sw = x.sig_words(); |
77 | 6.02M | |
78 | 6.02M | BigInt z(BigInt::Positive, x_sw + 1); |
79 | 6.02M | |
80 | 6.02M | if(x_sw && y) |
81 | 3.00M | { |
82 | 3.00M | bigint_linmul3(z.mutable_data(), x.data(), x_sw, y); |
83 | 3.00M | z.set_sign(x.sign()); |
84 | 3.00M | } |
85 | 6.02M | |
86 | 6.02M | return z; |
87 | 6.02M | } |
88 | | |
89 | | /* |
90 | | * Division Operator |
91 | | */ |
92 | | BigInt operator/(const BigInt& x, const BigInt& y) |
93 | 2.62M | { |
94 | 2.62M | if(y.sig_words() == 1 && is_power_of_2(y.word_at(0))) |
95 | 2.62M | return (x >> (y.bits() - 1)); |
96 | 479 | |
97 | 479 | BigInt q, r; |
98 | 479 | divide(x, y, q, r); |
99 | 479 | return q; |
100 | 479 | } |
101 | | |
102 | | /* |
103 | | * Modulo Operator |
104 | | */ |
105 | | BigInt operator%(const BigInt& n, const BigInt& mod) |
106 | 2.68M | { |
107 | 2.68M | if(mod.is_zero()) |
108 | 0 | throw BigInt::DivideByZero(); |
109 | 2.68M | if(mod.is_negative()) |
110 | 0 | throw Invalid_Argument("BigInt::operator%: modulus must be > 0"); |
111 | 2.68M | if(n.is_positive() && mod.is_positive() && n < mod) |
112 | 74.4k | return n; |
113 | 2.60M | |
114 | 2.60M | BigInt q, r; |
115 | 2.60M | divide(n, mod, q, r); |
116 | 2.60M | return r; |
117 | 2.60M | } |
118 | | |
119 | | /* |
120 | | * Modulo Operator |
121 | | */ |
122 | | word operator%(const BigInt& n, word mod) |
123 | 5.96M | { |
124 | 5.96M | if(mod == 0) |
125 | 0 | throw BigInt::DivideByZero(); |
126 | 5.96M | |
127 | 5.96M | if(mod == 1) |
128 | 0 | return 0; |
129 | 5.96M | |
130 | 5.96M | word remainder = 0; |
131 | 5.96M | |
132 | 5.96M | if(is_power_of_2(mod)) |
133 | 5.96M | { |
134 | 5.96M | remainder = (n.word_at(0) & (mod - 1)); |
135 | 5.96M | } |
136 | 256 | else |
137 | 256 | { |
138 | 256 | const size_t sw = n.sig_words(); |
139 | 1.28k | for(size_t i = sw; i > 0; --i) |
140 | 1.02k | { |
141 | 1.02k | remainder = bigint_modop(remainder, n.word_at(i-1), mod); |
142 | 1.02k | } |
143 | 256 | } |
144 | 5.96M | |
145 | 5.96M | if(remainder && n.sign() == BigInt::Negative) |
146 | 0 | return mod - remainder; |
147 | 5.96M | return remainder; |
148 | 5.96M | } |
149 | | |
150 | | /* |
151 | | * Left Shift Operator |
152 | | */ |
153 | | BigInt operator<<(const BigInt& x, size_t shift) |
154 | 2.60M | { |
155 | 2.60M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS, |
156 | 2.60M | shift_bits = shift % BOTAN_MP_WORD_BITS; |
157 | 2.60M | |
158 | 2.60M | const size_t x_sw = x.sig_words(); |
159 | 2.60M | |
160 | 2.60M | BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0)); |
161 | 2.60M | bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); |
162 | 2.60M | return y; |
163 | 2.60M | } |
164 | | |
165 | | /* |
166 | | * Right Shift Operator |
167 | | */ |
168 | | BigInt operator>>(const BigInt& x, size_t shift) |
169 | 2.65M | { |
170 | 2.65M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
171 | 2.65M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
172 | 2.65M | const size_t x_sw = x.sig_words(); |
173 | 2.65M | |
174 | 2.65M | BigInt y(x.sign(), x_sw - shift_words); |
175 | 2.65M | bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); |
176 | 2.65M | |
177 | 2.65M | if(x.is_negative() && y.is_zero()) |
178 | 0 | y.set_sign(BigInt::Positive); |
179 | 2.65M | |
180 | 2.65M | return y; |
181 | 2.65M | } |
182 | | |
183 | | } |