File indexing completed on 2024-05-12 04:45:13
0001 /* 0002 Copyright (C) 1999-2007 The Botan Project. All rights reserved. 0003 0004 Redistribution and use in source and binary forms, for any use, with or without 0005 modification, is permitted provided that the following conditions are met: 0006 0007 1. Redistributions of source code must retain the above copyright notice, this 0008 list of conditions, and the following disclaimer. 0009 0010 2. Redistributions in binary form must reproduce the above copyright notice, 0011 this list of conditions, and the following disclaimer in the documentation 0012 and/or other materials provided with the distribution. 0013 0014 THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY EXPRESS OR IMPLIED 0015 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 0016 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ARE DISCLAIMED. 0017 0018 IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTOR(S) BE LIABLE FOR ANY DIRECT, 0019 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 0020 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 0021 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 0022 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 0023 OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 0024 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 0025 */ 0026 // LICENSEHEADER_END 0027 namespace QCA { // WRAPNS_LINE 0028 /************************************************* 0029 * BigInt Assignment Operators Source File * 0030 * (C) 1999-2007 The Botan Project * 0031 *************************************************/ 0032 0033 } // WRAPNS_LINE 0034 #include <botan/bigint.h> 0035 namespace QCA { // WRAPNS_LINE 0036 } // WRAPNS_LINE 0037 #include <botan/numthry.h> 0038 namespace QCA { // WRAPNS_LINE 0039 } // WRAPNS_LINE 0040 #include <botan/mp_core.h> 0041 namespace QCA { // WRAPNS_LINE 0042 } // WRAPNS_LINE 0043 #include <botan/bit_ops.h> 0044 namespace QCA { // WRAPNS_LINE 0045 } // WRAPNS_LINE 0046 #include <botan/util.h> 0047 namespace QCA { // WRAPNS_LINE 0048 } // WRAPNS_LINE 0049 #include <algorithm> 0050 namespace QCA { // WRAPNS_LINE 0051 0052 namespace Botan { 0053 0054 /************************************************* 0055 * Addition Operator * 0056 *************************************************/ 0057 BigInt &BigInt::operator+=(const BigInt &y) 0058 { 0059 const u32bit x_sw = sig_words(), y_sw = y.sig_words(); 0060 0061 #ifdef BOTAN_TYPES_QT 0062 const u32bit reg_size = qMax(x_sw, y_sw) + 1; 0063 #else 0064 const u32bit reg_size = std::max(x_sw, y_sw) + 1; 0065 #endif 0066 grow_to(reg_size); 0067 0068 if ((sign() == y.sign())) 0069 bigint_add2(get_reg(), reg_size - 1, y.data(), y_sw); 0070 else { 0071 s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw); 0072 0073 if (relative_size < 0) { 0074 SecureVector<word> z(reg_size - 1); 0075 bigint_sub3(z, y.data(), reg_size - 1, data(), x_sw); 0076 copy_mem(reg.begin(), z.begin(), z.size()); 0077 set_sign(y.sign()); 0078 } else if (relative_size == 0) { 0079 reg.clear(); 0080 set_sign(Positive); 0081 } else if (relative_size > 0) 0082 bigint_sub2(get_reg(), x_sw, y.data(), y_sw); 0083 } 0084 0085 return (*this); 0086 } 0087 0088 /************************************************* 0089 * Subtraction Operator * 0090 *************************************************/ 0091 BigInt &BigInt::operator-=(const BigInt &y) 0092 { 0093 const u32bit x_sw = sig_words(), y_sw = y.sig_words(); 0094 0095 s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw); 0096 0097 #ifdef BOTAN_TYPES_QT 0098 const u32bit reg_size = qMax(x_sw, y_sw) + 1; 0099 #else 0100 const u32bit reg_size = std::max(x_sw, y_sw) + 1; 0101 #endif 0102 grow_to(reg_size); 0103 0104 if (relative_size < 0) { 0105 if (sign() == y.sign()) { 0106 SecureVector<word> z(reg_size - 1); 0107 bigint_sub3(z, y.data(), reg_size - 1, data(), x_sw); 0108 copy_mem(reg.begin(), z.begin(), z.size()); 0109 } else 0110 bigint_add2(get_reg(), reg_size - 1, y.data(), y_sw); 0111 0112 set_sign(y.reverse_sign()); 0113 } else if (relative_size == 0) { 0114 if (sign() == y.sign()) { 0115 reg.clear(); 0116 set_sign(Positive); 0117 } else 0118 bigint_shl1(get_reg(), x_sw, 0, 1); 0119 } else if (relative_size > 0) { 0120 if (sign() == y.sign()) 0121 bigint_sub2(get_reg(), x_sw, y.data(), y_sw); 0122 else 0123 bigint_add2(get_reg(), reg_size - 1, y.data(), y_sw); 0124 } 0125 0126 return (*this); 0127 } 0128 0129 /************************************************* 0130 * Multiplication Operator * 0131 *************************************************/ 0132 BigInt &BigInt::operator*=(const BigInt &y) 0133 { 0134 const u32bit x_sw = sig_words(), y_sw = y.sig_words(); 0135 set_sign((sign() == y.sign()) ? Positive : Negative); 0136 0137 if (x_sw == 0 || y_sw == 0) { 0138 reg.clear(); 0139 set_sign(Positive); 0140 } else if (x_sw == 1 && y_sw) { 0141 grow_to(y_sw + 2); 0142 bigint_linmul3(get_reg(), y.data(), y_sw, word_at(0)); 0143 } else if (y_sw == 1 && x_sw) { 0144 grow_to(x_sw + 2); 0145 bigint_linmul2(get_reg(), x_sw, y.word_at(0)); 0146 } else { 0147 grow_to(size() + y.size()); 0148 0149 SecureVector<word> z(data(), x_sw); 0150 SecureVector<word> workspace(size()); 0151 0152 bigint_mul(get_reg(), size(), workspace, z, z.size(), x_sw, y.data(), y.size(), y_sw); 0153 } 0154 0155 return (*this); 0156 } 0157 0158 /************************************************* 0159 * Division Operator * 0160 *************************************************/ 0161 BigInt &BigInt::operator/=(const BigInt &y) 0162 { 0163 if (y.sig_words() == 1 && power_of_2(y.word_at(0))) 0164 (*this) >>= (y.bits() - 1); 0165 else 0166 (*this) = (*this) / y; 0167 return (*this); 0168 } 0169 0170 /************************************************* 0171 * Modulo Operator * 0172 *************************************************/ 0173 BigInt &BigInt::operator%=(const BigInt &mod) 0174 { 0175 return (*this = (*this) % mod); 0176 } 0177 0178 /************************************************* 0179 * Modulo Operator * 0180 *************************************************/ 0181 word BigInt::operator%=(word mod) 0182 { 0183 if (mod == 0) 0184 throw BigInt::DivideByZero(); 0185 if (power_of_2(mod)) { 0186 word result = (word_at(0) & (mod - 1)); 0187 clear(); 0188 grow_to(2); 0189 reg[0] = result; 0190 return result; 0191 } 0192 0193 word remainder = 0; 0194 0195 for (u32bit j = sig_words(); j > 0; --j) 0196 remainder = bigint_modop(remainder, word_at(j - 1), mod); 0197 clear(); 0198 grow_to(2); 0199 0200 if (remainder && sign() == BigInt::Negative) 0201 reg[0] = mod - remainder; 0202 else 0203 reg[0] = remainder; 0204 0205 set_sign(BigInt::Positive); 0206 0207 return word_at(0); 0208 } 0209 0210 /************************************************* 0211 * Left Shift Operator * 0212 *************************************************/ 0213 BigInt &BigInt::operator<<=(u32bit shift) 0214 { 0215 if (shift) { 0216 const u32bit shift_words = shift / MP_WORD_BITS, shift_bits = shift % MP_WORD_BITS, words = sig_words(); 0217 0218 grow_to(words + shift_words + (shift_bits ? 1 : 0)); 0219 bigint_shl1(get_reg(), words, shift_words, shift_bits); 0220 } 0221 0222 return (*this); 0223 } 0224 0225 /************************************************* 0226 * Right Shift Operator * 0227 *************************************************/ 0228 BigInt &BigInt::operator>>=(u32bit shift) 0229 { 0230 if (shift) { 0231 const u32bit shift_words = shift / MP_WORD_BITS, shift_bits = shift % MP_WORD_BITS; 0232 0233 bigint_shr1(get_reg(), sig_words(), shift_words, shift_bits); 0234 0235 if (is_zero()) 0236 set_sign(Positive); 0237 } 0238 0239 return (*this); 0240 } 0241 0242 } 0243 } // WRAPNS_LINE