Botan
1.11.15
|
00001 /* 00002 * BigInt Assignment Operators 00003 * (C) 1999-2007 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/bigint.h> 00009 #include <botan/internal/mp_core.h> 00010 #include <botan/internal/bit_ops.h> 00011 #include <algorithm> 00012 00013 namespace Botan { 00014 00015 /* 00016 * Addition Operator 00017 */ 00018 BigInt& BigInt::operator+=(const BigInt& y) 00019 { 00020 const size_t x_sw = sig_words(), y_sw = y.sig_words(); 00021 00022 const size_t reg_size = std::max(x_sw, y_sw) + 1; 00023 grow_to(reg_size); 00024 00025 if(sign() == y.sign()) 00026 bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw); 00027 else 00028 { 00029 s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw); 00030 00031 if(relative_size < 0) 00032 { 00033 secure_vector<word> z(reg_size - 1); 00034 bigint_sub3(&z[0], y.data(), reg_size - 1, data(), x_sw); 00035 std::swap(m_reg, z); 00036 set_sign(y.sign()); 00037 } 00038 else if(relative_size == 0) 00039 { 00040 zeroise(m_reg); 00041 set_sign(Positive); 00042 } 00043 else if(relative_size > 0) 00044 bigint_sub2(mutable_data(), x_sw, y.data(), y_sw); 00045 } 00046 00047 return (*this); 00048 } 00049 00050 /* 00051 * Subtraction Operator 00052 */ 00053 BigInt& BigInt::operator-=(const BigInt& y) 00054 { 00055 const size_t x_sw = sig_words(), y_sw = y.sig_words(); 00056 00057 s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw); 00058 00059 const size_t reg_size = std::max(x_sw, y_sw) + 1; 00060 grow_to(reg_size); 00061 00062 if(relative_size < 0) 00063 { 00064 if(sign() == y.sign()) 00065 bigint_sub2_rev(mutable_data(), y.data(), y_sw); 00066 else 00067 bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw); 00068 00069 set_sign(y.reverse_sign()); 00070 } 00071 else if(relative_size == 0) 00072 { 00073 if(sign() == y.sign()) 00074 { 00075 clear(); 00076 set_sign(Positive); 00077 } 00078 else 00079 bigint_shl1(mutable_data(), x_sw, 0, 1); 00080 } 00081 else if(relative_size > 0) 00082 { 00083 if(sign() == y.sign()) 00084 bigint_sub2(mutable_data(), x_sw, y.data(), y_sw); 00085 else 00086 bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw); 00087 } 00088 00089 return (*this); 00090 } 00091 00092 /* 00093 * Multiplication Operator 00094 */ 00095 BigInt& BigInt::operator*=(const BigInt& y) 00096 { 00097 const size_t x_sw = sig_words(), y_sw = y.sig_words(); 00098 set_sign((sign() == y.sign()) ? Positive : Negative); 00099 00100 if(x_sw == 0 || y_sw == 0) 00101 { 00102 clear(); 00103 set_sign(Positive); 00104 } 00105 else if(x_sw == 1 && y_sw) 00106 { 00107 grow_to(y_sw + 2); 00108 bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0)); 00109 } 00110 else if(y_sw == 1 && x_sw) 00111 { 00112 grow_to(x_sw + 2); 00113 bigint_linmul2(mutable_data(), x_sw, y.word_at(0)); 00114 } 00115 else 00116 { 00117 grow_to(size() + y.size()); 00118 00119 secure_vector<word> z(data(), data() + x_sw); 00120 secure_vector<word> workspace(size()); 00121 00122 bigint_mul(mutable_data(), size(), &workspace[0], 00123 &z[0], z.size(), x_sw, 00124 y.data(), y.size(), y_sw); 00125 } 00126 00127 return (*this); 00128 } 00129 00130 /* 00131 * Division Operator 00132 */ 00133 BigInt& BigInt::operator/=(const BigInt& y) 00134 { 00135 if(y.sig_words() == 1 && is_power_of_2(y.word_at(0))) 00136 (*this) >>= (y.bits() - 1); 00137 else 00138 (*this) = (*this) / y; 00139 return (*this); 00140 } 00141 00142 /* 00143 * Modulo Operator 00144 */ 00145 BigInt& BigInt::operator%=(const BigInt& mod) 00146 { 00147 return (*this = (*this) % mod); 00148 } 00149 00150 /* 00151 * Modulo Operator 00152 */ 00153 word BigInt::operator%=(word mod) 00154 { 00155 if(mod == 0) 00156 throw BigInt::DivideByZero(); 00157 00158 if(is_power_of_2(mod)) 00159 { 00160 word result = (word_at(0) & (mod - 1)); 00161 clear(); 00162 grow_to(2); 00163 m_reg[0] = result; 00164 return result; 00165 } 00166 00167 word remainder = 0; 00168 00169 for(size_t j = sig_words(); j > 0; --j) 00170 remainder = bigint_modop(remainder, word_at(j-1), mod); 00171 clear(); 00172 grow_to(2); 00173 00174 if(remainder && sign() == BigInt::Negative) 00175 m_reg[0] = mod - remainder; 00176 else 00177 m_reg[0] = remainder; 00178 00179 set_sign(BigInt::Positive); 00180 00181 return word_at(0); 00182 } 00183 00184 /* 00185 * Left Shift Operator 00186 */ 00187 BigInt& BigInt::operator<<=(size_t shift) 00188 { 00189 if(shift) 00190 { 00191 const size_t shift_words = shift / MP_WORD_BITS, 00192 shift_bits = shift % MP_WORD_BITS, 00193 words = sig_words(); 00194 00195 grow_to(words + shift_words + (shift_bits ? 1 : 0)); 00196 bigint_shl1(mutable_data(), words, shift_words, shift_bits); 00197 } 00198 00199 return (*this); 00200 } 00201 00202 /* 00203 * Right Shift Operator 00204 */ 00205 BigInt& BigInt::operator>>=(size_t shift) 00206 { 00207 if(shift) 00208 { 00209 const size_t shift_words = shift / MP_WORD_BITS, 00210 shift_bits = shift % MP_WORD_BITS; 00211 00212 bigint_shr1(mutable_data(), sig_words(), shift_words, shift_bits); 00213 00214 if(is_zero()) 00215 set_sign(Positive); 00216 } 00217 00218 return (*this); 00219 } 00220 00221 }