monotone

monotone Mtn Source Tree

Root/botan/big_ops2.cpp

1/*************************************************
2* BigInt Assignment Operators Source File *
3* (C) 1999-2007 The Botan Project *
4*************************************************/
5
6#include <botan/bigint.h>
7#include <botan/mp_core.h>
8#include <botan/bit_ops.h>
9#include <algorithm>
10
11namespace Botan {
12
13/*************************************************
14* Addition Operator *
15*************************************************/
16BigInt& BigInt::operator+=(const BigInt& y)
17 {
18 const u32bit x_sw = sig_words(), y_sw = y.sig_words();
19
20 const u32bit reg_size = std::max(x_sw, y_sw) + 1;
21 grow_to(reg_size);
22
23 if((sign() == y.sign()))
24 bigint_add2(get_reg(), reg_size - 1, y.data(), y_sw);
25 else
26 {
27 s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
28
29 if(relative_size < 0)
30 {
31 SecureVector<word> z(reg_size - 1);
32 bigint_sub3(z, y.data(), reg_size - 1, data(), x_sw);
33 copy_mem(reg.begin(), z.begin(), z.size());
34 set_sign(y.sign());
35 }
36 else if(relative_size == 0)
37 {
38 reg.clear();
39 set_sign(Positive);
40 }
41 else if(relative_size > 0)
42 bigint_sub2(get_reg(), x_sw, y.data(), y_sw);
43 }
44
45 return (*this);
46 }
47
48/*************************************************
49* Subtraction Operator *
50*************************************************/
51BigInt& BigInt::operator-=(const BigInt& y)
52 {
53 const u32bit x_sw = sig_words(), y_sw = y.sig_words();
54
55 s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
56
57 const u32bit reg_size = std::max(x_sw, y_sw) + 1;
58 grow_to(reg_size);
59
60 if(relative_size < 0)
61 {
62 if(sign() == y.sign())
63 {
64 SecureVector<word> z(reg_size - 1);
65 bigint_sub3(z, y.data(), reg_size - 1, data(), x_sw);
66 copy_mem(reg.begin(), z.begin(), z.size());
67 }
68 else
69 bigint_add2(get_reg(), reg_size - 1, y.data(), y_sw);
70
71 set_sign(y.reverse_sign());
72 }
73 else if(relative_size == 0)
74 {
75 if(sign() == y.sign())
76 {
77 reg.clear();
78 set_sign(Positive);
79 }
80 else
81 bigint_shl1(get_reg(), x_sw, 0, 1);
82 }
83 else if(relative_size > 0)
84 {
85 if(sign() == y.sign())
86 bigint_sub2(get_reg(), x_sw, y.data(), y_sw);
87 else
88 bigint_add2(get_reg(), reg_size - 1, y.data(), y_sw);
89 }
90
91 return (*this);
92 }
93
94/*************************************************
95* Multiplication Operator *
96*************************************************/
97BigInt& BigInt::operator*=(const BigInt& y)
98 {
99 const u32bit x_sw = sig_words(), y_sw = y.sig_words();
100 set_sign((sign() == y.sign()) ? Positive : Negative);
101
102 if(x_sw == 0 || y_sw == 0)
103 {
104 reg.clear();
105 set_sign(Positive);
106 }
107 else if(x_sw == 1 && y_sw)
108 {
109 grow_to(y_sw + 2);
110 bigint_linmul3(get_reg(), y.data(), y_sw, word_at(0));
111 }
112 else if(y_sw == 1 && x_sw)
113 {
114 grow_to(x_sw + 2);
115 bigint_linmul2(get_reg(), x_sw, y.word_at(0));
116 }
117 else
118 {
119 grow_to(size() + y.size());
120
121 SecureVector<word> z(data(), x_sw);
122 SecureVector<word> workspace(size());
123
124 bigint_mul(get_reg(), size(), workspace,
125 z, z.size(), x_sw,
126 y.data(), y.size(), y_sw);
127 }
128
129 return (*this);
130 }
131
132/*************************************************
133* Division Operator *
134*************************************************/
135BigInt& BigInt::operator/=(const BigInt& y)
136 {
137 if(y.sig_words() == 1 && power_of_2(y.word_at(0)))
138 (*this) >>= (y.bits() - 1);
139 else
140 (*this) = (*this) / y;
141 return (*this);
142 }
143
144/*************************************************
145* Modulo Operator *
146*************************************************/
147BigInt& BigInt::operator%=(const BigInt& mod)
148 {
149 return (*this = (*this) % mod);
150 }
151
152/*************************************************
153* Modulo Operator *
154*************************************************/
155word BigInt::operator%=(word mod)
156 {
157 if(mod == 0)
158 throw BigInt::DivideByZero();
159 if(power_of_2(mod))
160 {
161 word result = (word_at(0) & (mod - 1));
162 clear();
163 grow_to(2);
164 reg[0] = result;
165 return result;
166 }
167
168 word remainder = 0;
169
170 for(u32bit j = sig_words(); j > 0; --j)
171 remainder = bigint_modop(remainder, word_at(j-1), mod);
172 clear();
173 grow_to(2);
174
175 if(remainder && sign() == BigInt::Negative)
176 reg[0] = mod - remainder;
177 else
178 reg[0] = remainder;
179
180 set_sign(BigInt::Positive);
181
182 return word_at(0);
183 }
184
185/*************************************************
186* Left Shift Operator *
187*************************************************/
188BigInt& BigInt::operator<<=(u32bit shift)
189 {
190 if(shift)
191 {
192 const u32bit shift_words = shift / MP_WORD_BITS,
193 shift_bits = shift % MP_WORD_BITS,
194 words = sig_words();
195
196 grow_to(words + shift_words + (shift_bits ? 1 : 0));
197 bigint_shl1(get_reg(), words, shift_words, shift_bits);
198 }
199
200 return (*this);
201 }
202
203/*************************************************
204* Right Shift Operator *
205*************************************************/
206BigInt& BigInt::operator>>=(u32bit shift)
207 {
208 if(shift)
209 {
210 const u32bit shift_words = shift / MP_WORD_BITS,
211 shift_bits = shift % MP_WORD_BITS;
212
213 bigint_shr1(get_reg(), sig_words(), shift_words, shift_bits);
214
215 if(is_zero())
216 set_sign(Positive);
217 }
218
219 return (*this);
220 }
221
222}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status