Botan
1.11.15
|
00001 /* 00002 * BigInt Binary 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/divide.h> 00010 #include <botan/internal/mp_core.h> 00011 #include <botan/internal/bit_ops.h> 00012 #include <algorithm> 00013 00014 namespace Botan { 00015 00016 /* 00017 * Addition Operator 00018 */ 00019 BigInt operator+(const BigInt& x, const BigInt& y) 00020 { 00021 const size_t x_sw = x.sig_words(), y_sw = y.sig_words(); 00022 00023 BigInt z(x.sign(), std::max(x_sw, y_sw) + 1); 00024 00025 if((x.sign() == y.sign())) 00026 bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); 00027 else 00028 { 00029 s32bit relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw); 00030 00031 if(relative_size < 0) 00032 { 00033 bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw); 00034 z.set_sign(y.sign()); 00035 } 00036 else if(relative_size == 0) 00037 z.set_sign(BigInt::Positive); 00038 else if(relative_size > 0) 00039 bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); 00040 } 00041 00042 return z; 00043 } 00044 00045 /* 00046 * Subtraction Operator 00047 */ 00048 BigInt operator-(const BigInt& x, const BigInt& y) 00049 { 00050 const size_t x_sw = x.sig_words(), y_sw = y.sig_words(); 00051 00052 s32bit relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw); 00053 00054 BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1); 00055 00056 if(relative_size < 0) 00057 { 00058 if(x.sign() == y.sign()) 00059 bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw); 00060 else 00061 bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); 00062 z.set_sign(y.reverse_sign()); 00063 } 00064 else if(relative_size == 0) 00065 { 00066 if(x.sign() != y.sign()) 00067 bigint_shl2(z.mutable_data(), x.data(), x_sw, 0, 1); 00068 } 00069 else if(relative_size > 0) 00070 { 00071 if(x.sign() == y.sign()) 00072 bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); 00073 else 00074 bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw); 00075 z.set_sign(x.sign()); 00076 } 00077 return z; 00078 } 00079 00080 /* 00081 * Multiplication Operator 00082 */ 00083 BigInt operator*(const BigInt& x, const BigInt& y) 00084 { 00085 const size_t x_sw = x.sig_words(), y_sw = y.sig_words(); 00086 00087 BigInt z(BigInt::Positive, x.size() + y.size()); 00088 00089 if(x_sw == 1 && y_sw) 00090 bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0)); 00091 else if(y_sw == 1 && x_sw) 00092 bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0)); 00093 else if(x_sw && y_sw) 00094 { 00095 secure_vector<word> workspace(z.size()); 00096 bigint_mul(z.mutable_data(), z.size(), &workspace[0], 00097 x.data(), x.size(), x_sw, 00098 y.data(), y.size(), y_sw); 00099 } 00100 00101 if(x_sw && y_sw && x.sign() != y.sign()) 00102 z.flip_sign(); 00103 return z; 00104 } 00105 00106 /* 00107 * Division Operator 00108 */ 00109 BigInt operator/(const BigInt& x, const BigInt& y) 00110 { 00111 BigInt q, r; 00112 divide(x, y, q, r); 00113 return q; 00114 } 00115 00116 /* 00117 * Modulo Operator 00118 */ 00119 BigInt operator%(const BigInt& n, const BigInt& mod) 00120 { 00121 if(mod.is_zero()) 00122 throw BigInt::DivideByZero(); 00123 if(mod.is_negative()) 00124 throw Invalid_Argument("BigInt::operator%: modulus must be > 0"); 00125 if(n.is_positive() && mod.is_positive() && n < mod) 00126 return n; 00127 00128 BigInt q, r; 00129 divide(n, mod, q, r); 00130 return r; 00131 } 00132 00133 /* 00134 * Modulo Operator 00135 */ 00136 word operator%(const BigInt& n, word mod) 00137 { 00138 if(mod == 0) 00139 throw BigInt::DivideByZero(); 00140 00141 if(is_power_of_2(mod)) 00142 return (n.word_at(0) & (mod - 1)); 00143 00144 word remainder = 0; 00145 00146 for(size_t j = n.sig_words(); j > 0; --j) 00147 remainder = bigint_modop(remainder, n.word_at(j-1), mod); 00148 00149 if(remainder && n.sign() == BigInt::Negative) 00150 return mod - remainder; 00151 return remainder; 00152 } 00153 00154 /* 00155 * Left Shift Operator 00156 */ 00157 BigInt operator<<(const BigInt& x, size_t shift) 00158 { 00159 if(shift == 0) 00160 return x; 00161 00162 const size_t shift_words = shift / MP_WORD_BITS, 00163 shift_bits = shift % MP_WORD_BITS; 00164 00165 const size_t x_sw = x.sig_words(); 00166 00167 BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0)); 00168 bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); 00169 return y; 00170 } 00171 00172 /* 00173 * Right Shift Operator 00174 */ 00175 BigInt operator>>(const BigInt& x, size_t shift) 00176 { 00177 if(shift == 0) 00178 return x; 00179 if(x.bits() <= shift) 00180 return 0; 00181 00182 const size_t shift_words = shift / MP_WORD_BITS, 00183 shift_bits = shift % MP_WORD_BITS, 00184 x_sw = x.sig_words(); 00185 00186 BigInt y(x.sign(), x_sw - shift_words); 00187 bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits); 00188 return y; 00189 } 00190 00191 }