Botan 2.19.5 Crypto and TLS for C&

big_ops3.cpp
Go to the documentation of this file.
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 {
20 const size_t x_sw = x.sig_words();
21
22 BigInt z(x.sign(), std::max(x_sw, y_words) + 1);
23
24 if(x.sign() == y_sign)
25 {
26 bigint_add3(z.mutable_data(), x.data(), x_sw, y, y_words);
27 }
28 else
29 {
30 const int32_t relative_size = bigint_sub_abs(z.mutable_data(), x.data(), x_sw, y, y_words);
31
32 //z.sign_fixup(relative_size, y_sign);
33 if(relative_size < 0)
34 z.set_sign(y_sign);
35 else if(relative_size == 0)
36 z.set_sign(BigInt::Positive);
37 }
38
39 return z;
40 }
41
42/*
43* Multiplication Operator
44*/
45 BigInt operator*(const BigInt& x, const BigInt& y)
46 {
47 const size_t x_sw = x.sig_words();
48 const size_t y_sw = y.sig_words();
49
50 BigInt z(BigInt::Positive, x.size() + y.size());
51
52 if(x_sw == 1 && y_sw)
53 bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
54 else if(y_sw == 1 && x_sw)
55 bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
56 else if(x_sw && y_sw)
57 {
58 secure_vector<word> workspace(z.size());
59
60 bigint_mul(z.mutable_data(), z.size(),
61 x.data(), x.size(), x_sw,
62 y.data(), y.size(), y_sw,
63 workspace.data(), workspace.size());
64 }
65
66 z.cond_flip_sign(x_sw > 0 && y_sw > 0 && x.sign() != y.sign());
67
68 return z;
69 }
70
71/*
72* Multiplication Operator
73*/
74 BigInt operator*(const BigInt& x, word y)
75 {
76 const size_t x_sw = x.sig_words();
77
78 BigInt z(BigInt::Positive, x_sw + 1);
79
80 if(x_sw && y)
81 {
82 bigint_linmul3(z.mutable_data(), x.data(), x_sw, y);
83 z.set_sign(x.sign());
84 }
85
86 return z;
87 }
88
89/*
90* Division Operator
91*/
92 BigInt operator/(const BigInt& x, const BigInt& y)
93 {
94 if(y.sig_words() == 1)
95 {
96 return x / y.word_at(0);
97 }
98
99 BigInt q, r;
100 vartime_divide(x, y, q, r);
101 return q;
102 }
103
104/*
105* Division Operator
106*/
107 BigInt operator/(const BigInt& x, word y)
108 {
109 if(y == 0)
110 throw BigInt::DivideByZero();
111 else if(y == 1)
112 return x;
113 else if(y == 2)
114 return (x >> 1);
115 else if(y <= 255)
116 {
117 BigInt q;
118 uint8_t r;
119 ct_divide_u8(x, static_cast<uint8_t>(y), q, r);
120 return q;
121 }
122
123 BigInt q, r;
124 vartime_divide(x, y, q, r);
125 return q;
126 }
127
128/*
129* Modulo Operator
130*/
131 BigInt operator%(const BigInt& n, const BigInt& mod)
132 {
133 if(mod.is_zero())
134 throw BigInt::DivideByZero();
135 if(mod.is_negative())
136 throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
137 if(n.is_positive() && mod.is_positive() && n < mod)
138 return n;
139
140 if(mod.sig_words() == 1)
141 {
142 return n % mod.word_at(0);
143 }
144
145 BigInt q, r;
146 vartime_divide(n, mod, q, r);
147 return r;
148 }
149
150/*
151* Modulo Operator
152*/
153word operator%(const BigInt& n, word mod)
154 {
155 if(mod == 0)
156 throw BigInt::DivideByZero();
157
158 if(mod == 1)
159 return 0;
160
161 word remainder = 0;
162
163 if(is_power_of_2(mod))
164 {
165 remainder = (n.word_at(0) & (mod - 1));
166 }
167 else
168 {
169 const size_t sw = n.sig_words();
170 for(size_t i = sw; i > 0; --i)
171 {
172 remainder = bigint_modop(remainder, n.word_at(i-1), mod);
173 }
174 }
175
176 if(remainder && n.sign() == BigInt::Negative)
177 return mod - remainder;
178 return remainder;
179 }
180
181/*
182* Left Shift Operator
183*/
184 BigInt operator<<(const BigInt& x, size_t shift)
185 {
186 const size_t shift_words = shift / BOTAN_MP_WORD_BITS,
187 shift_bits = shift % BOTAN_MP_WORD_BITS;
188
189 const size_t x_sw = x.sig_words();
190
191 BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
192 bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
193 return y;
194 }
195
196/*
197* Right Shift Operator
198*/
199 BigInt operator>>(const BigInt& x, size_t shift)
200 {
201 const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
202 const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
203 const size_t x_sw = x.sig_words();
204
205 BigInt y(x.sign(), x_sw - shift_words);
206 bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
207
208 if(x.is_negative() && y.is_zero())
209 y.set_sign(BigInt::Positive);
210
211 return y;
212 }
213
214}
Botan::BigInt::DivideByZero
Definition: bigint.h:44
Botan::BigInt
Definition: bigint.h:25
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:592
Botan::BigInt::mutable_data
word * mutable_data()
Definition: bigint.h:620
Botan::BigInt::size
size_t size() const
Definition: bigint.h:586
Botan::BigInt::add2
static BigInt add2(const BigInt &x, const word y[], size_t y_words, Sign y_sign)
Definition: big_ops3.cpp:18
Botan::BigInt::data
const word * data() const
Definition: bigint.h:626
Botan::BigInt::word_at
word word_at(size_t n) const
Definition: bigint.h:514
Botan::BigInt::cond_flip_sign
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:517
Botan::BigInt::sign
Sign sign() const
Definition: bigint.h:545
Botan::BigInt::Sign
Sign
Definition: bigint.h:35
Botan::BigInt::Positive
@ Positive
Definition: bigint.h:35
Botan::BigInt::Negative
@ Negative
Definition: bigint.h:35
Botan::BigInt::is_zero
bool is_zero() const
Definition: bigint.h:427
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:533
Botan::BigInt::is_positive
bool is_positive() const
Definition: bigint.h:539
Botan::BigInt::set_sign
void set_sign(Sign sign)
Definition: bigint.h:569
Botan::Invalid_Argument
Definition: exceptn.h:137
Botan
Definition: alg_id.cpp:13
Botan::bigint_linmul3
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:504
Botan::operator*
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:45
Botan::bigint_add3
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:289
Botan::ct_divide_u8
void ct_divide_u8(const BigInt &x, uint8_t y, BigInt &q_out, uint8_t &r_out)
Definition: divide.cpp:82
Botan::bigint_sub_abs
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.h:377
Botan::bigint_mul
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:298
Botan::operator/
BigInt operator/(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:92
Botan::operator%
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition: big_ops3.cpp:131
Botan::bigint_shl2
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:449
Botan::operator>>
int operator>>(int fd, Pipe &pipe)
Definition: fd_unix.cpp:40
Botan::operator<<
int operator<<(int fd, Pipe &pipe)
Definition: fd_unix.cpp:17
Botan::bigint_shr2
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:466
Botan::bigint_modop
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:755
Botan::vartime_divide
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:159
Botan::secure_vector
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
Botan::is_power_of_2
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43