Botan  1.10.9
big_ops3.cpp
Go to the documentation of this file.
1 /*
2 * BigInt Binary Operators
3 * (C) 1999-2007 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/bigint.h>
9 #include <botan/divide.h>
10 #include <botan/internal/mp_core.h>
11 #include <botan/internal/bit_ops.h>
12 #include <algorithm>
13 
14 namespace Botan {
15 
16 /*
17 * Addition Operator
18 */
19 BigInt operator+(const BigInt& x, const BigInt& y)
20  {
21  const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
22 
23  BigInt z(x.sign(), std::max(x_sw, y_sw) + 1);
24 
25  if((x.sign() == y.sign()))
26  bigint_add3(z.get_reg(), x.data(), x_sw, y.data(), y_sw);
27  else
28  {
29  s32bit relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
30 
31  if(relative_size < 0)
32  {
33  bigint_sub3(z.get_reg(), y.data(), y_sw, x.data(), x_sw);
34  z.set_sign(y.sign());
35  }
36  else if(relative_size == 0)
37  z.set_sign(BigInt::Positive);
38  else if(relative_size > 0)
39  bigint_sub3(z.get_reg(), x.data(), x_sw, y.data(), y_sw);
40  }
41 
42  return z;
43  }
44 
45 /*
46 * Subtraction Operator
47 */
48 BigInt operator-(const BigInt& x, const BigInt& y)
49  {
50  const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
51 
52  s32bit relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
53 
54  BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1);
55 
56  if(relative_size < 0)
57  {
58  if(x.sign() == y.sign())
59  bigint_sub3(z.get_reg(), y.data(), y_sw, x.data(), x_sw);
60  else
61  bigint_add3(z.get_reg(), x.data(), x_sw, y.data(), y_sw);
62  z.set_sign(y.reverse_sign());
63  }
64  else if(relative_size == 0)
65  {
66  if(x.sign() != y.sign())
67  bigint_shl2(z.get_reg(), x.data(), x_sw, 0, 1);
68  }
69  else if(relative_size > 0)
70  {
71  if(x.sign() == y.sign())
72  bigint_sub3(z.get_reg(), x.data(), x_sw, y.data(), y_sw);
73  else
74  bigint_add3(z.get_reg(), x.data(), x_sw, y.data(), y_sw);
75  z.set_sign(x.sign());
76  }
77  return z;
78  }
79 
80 /*
81 * Multiplication Operator
82 */
83 BigInt operator*(const BigInt& x, const BigInt& y)
84  {
85  const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
86 
87  BigInt z(BigInt::Positive, x.size() + y.size());
88 
89  if(x_sw == 1 && y_sw)
90  bigint_linmul3(z.get_reg(), y.data(), y_sw, x.word_at(0));
91  else if(y_sw == 1 && x_sw)
92  bigint_linmul3(z.get_reg(), x.data(), x_sw, y.word_at(0));
93  else if(x_sw && y_sw)
94  {
95  SecureVector<word> workspace(z.size());
96  bigint_mul(z.get_reg(), z.size(), workspace,
97  x.data(), x.size(), x_sw,
98  y.data(), y.size(), y_sw);
99  }
100 
101  if(x_sw && y_sw && x.sign() != y.sign())
102  z.flip_sign();
103  return z;
104  }
105 
106 /*
107 * Division Operator
108 */
109 BigInt operator/(const BigInt& x, const BigInt& y)
110  {
111  BigInt q, r;
112  divide(x, y, q, r);
113  return q;
114  }
115 
116 /*
117 * Modulo Operator
118 */
120  {
121  if(mod.is_zero())
122  throw BigInt::DivideByZero();
123  if(mod.is_negative())
124  throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
125  if(n.is_positive() && mod.is_positive() && n < mod)
126  return n;
127 
128  BigInt q, r;
129  divide(n, mod, q, r);
130  return r;
131  }
132 
133 /*
134 * Modulo Operator
135 */
136 word operator%(const BigInt& n, word mod)
137  {
138  if(mod == 0)
139  throw BigInt::DivideByZero();
140  if(power_of_2(mod))
141  return (n.word_at(0) & (mod - 1));
142 
143  word remainder = 0;
144 
145  for(size_t j = n.sig_words(); j > 0; --j)
146  remainder = bigint_modop(remainder, n.word_at(j-1), mod);
147 
148  if(remainder && n.sign() == BigInt::Negative)
149  return mod - remainder;
150  return remainder;
151  }
152 
153 /*
154 * Left Shift Operator
155 */
156 BigInt operator<<(const BigInt& x, size_t shift)
157  {
158  if(shift == 0)
159  return x;
160 
161  const size_t shift_words = shift / MP_WORD_BITS,
162  shift_bits = shift % MP_WORD_BITS;
163 
164  const size_t x_sw = x.sig_words();
165 
166  BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
167  bigint_shl2(y.get_reg(), x.data(), x_sw, shift_words, shift_bits);
168  return y;
169  }
170 
171 /*
172 * Right Shift Operator
173 */
174 BigInt operator>>(const BigInt& x, size_t shift)
175  {
176  if(shift == 0)
177  return x;
178  if(x.bits() <= shift)
179  return 0;
180 
181  const size_t shift_words = shift / MP_WORD_BITS,
182  shift_bits = shift % MP_WORD_BITS,
183  x_sw = x.sig_words();
184 
185  BigInt y(x.sign(), x_sw - shift_words);
186  bigint_shr2(y.get_reg(), x.data(), x_sw, shift_words, shift_bits);
187  return y;
188  }
189 
190 }
word word_at(size_t n) const
Definition: bigint.h:238
size_t sig_words() const
Definition: bigint.h:290
void divide(const BigInt &x, const BigInt &y_arg, BigInt &q, BigInt &r)
Definition: divide.cpp:34
BigInt n
Definition: numthry.cpp:26
void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_shift.cpp:117
Sign reverse_sign() const
Definition: bigint.cpp:310
SecureVector< word > & get_reg()
Definition: bigint.h:325
bool is_negative() const
Definition: bigint.h:245
std::invalid_argument Invalid_Argument
Definition: exceptn.h:20
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_asm.cpp:127
size_t size() const
Definition: bigint.h:284
int operator>>(int fd, Pipe &pipe)
Definition: fd_unix.cpp:39
signed int s32bit
Definition: types.h:37
BigInt operator%(const BigInt &n, const BigInt &mod)
Definition: big_ops3.cpp:119
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_asm.cpp:167
int operator<<(int fd, Pipe &pipe)
Definition: fd_unix.cpp:17
size_t bits() const
Definition: bigint.cpp:253
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition: symkey.cpp:114
const word * data() const
Definition: bigint.h:317
GMP_MPZ mod
Definition: gmp_powm.cpp:29
BigInt operator*(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:83
void bigint_shl2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_shift.cpp:97
bool power_of_2(T arg)
Definition: bit_ops.h:21
void bigint_mul(word z[], size_t z_size, word workspace[], const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw)
Definition: mp_karat.cpp:248
bool is_positive() const
Definition: bigint.h:251
BigInt r
Definition: numthry.cpp:26
bool is_zero() const
Definition: bigint.h:176
BigInt operator-(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:48
s32bit bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_misc.cpp:41
void bigint_add3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_asm.cpp:77
BigInt operator/(const BigInt &x, const BigInt &y)
Definition: big_ops3.cpp:109
word bigint_modop(word n1, word n0, word d)
Definition: mp_misc.cpp:92
const size_t MP_WORD_BITS
Definition: mp_core.h:18
Sign sign() const
Definition: bigint.h:257