monotone

monotone Mtn Source Tree

Root/botan/big_ops2.cpp

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

Archive Download this file

Branches

Tags

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