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