Botan  1.11.15
src/lib/math/bigint/big_ops2.cpp
Go to the documentation of this file.
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 }