qca

divide.cpp

00001 /*
00002 Copyright (C) 1999-2007 The Botan Project. All rights reserved.
00003 
00004 Redistribution and use in source and binary forms, for any use, with or without
00005 modification, is permitted provided that the following conditions are met:
00006 
00007 1. Redistributions of source code must retain the above copyright notice, this
00008 list of conditions, and the following disclaimer.
00009 
00010 2. Redistributions in binary form must reproduce the above copyright notice,
00011 this list of conditions, and the following disclaimer in the documentation
00012 and/or other materials provided with the distribution.
00013 
00014 THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY EXPRESS OR IMPLIED
00015 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
00016 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ARE DISCLAIMED.
00017 
00018 IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTOR(S) BE LIABLE FOR ANY DIRECT,
00019 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
00020 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00021 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00022 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
00023 OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
00024 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00025 */
00026 // LICENSEHEADER_END
00027 namespace QCA { // WRAPNS_LINE
00028 /*************************************************
00029 * Division Algorithm Source File                 *
00030 * (C) 1999-2007 The Botan Project                *
00031 *************************************************/
00032 
00033 } // WRAPNS_LINE
00034 #include <botan/numthry.h>
00035 namespace QCA { // WRAPNS_LINE
00036 } // WRAPNS_LINE
00037 #include <botan/mp_core.h>
00038 namespace QCA { // WRAPNS_LINE
00039 
00040 namespace Botan {
00041 
00042 namespace {
00043 
00044 /*************************************************
00045 * Handle signed operands, if necessary           *
00046 *************************************************/
00047 void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r)
00048    {
00049    if(x.sign() == BigInt::Negative)
00050       {
00051       q.flip_sign();
00052       if(r.is_nonzero()) { --q; r = y.abs() - r; }
00053       }
00054    if(y.sign() == BigInt::Negative)
00055       q.flip_sign();
00056    }
00057 
00058 }
00059 
00060 /*************************************************
00061 * Solve x = q * y + r                            *
00062 *************************************************/
00063 void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r)
00064    {
00065    if(y_arg.is_zero())
00066       throw BigInt::DivideByZero();
00067 
00068    BigInt y = y_arg;
00069    const u32bit y_words = y.sig_words();
00070    r = x;
00071 
00072    r.set_sign(BigInt::Positive);
00073    y.set_sign(BigInt::Positive);
00074 
00075    s32bit compare = r.cmp(y);
00076 
00077    if(compare < 0)
00078       q = 0;
00079    else if(compare ==  0)
00080       {
00081       q = 1;
00082       r = 0;
00083       }
00084    else
00085       {
00086       u32bit shifts = 0;
00087       word y_top = y[y.sig_words()-1];
00088       while(y_top < MP_WORD_TOP_BIT) { y_top <<= 1; ++shifts; }
00089       y <<= shifts;
00090       r <<= shifts;
00091 
00092       const u32bit n = r.sig_words() - 1, t = y_words - 1;
00093 
00094       q.get_reg().create(n - t + 1);
00095       if(n <= t)
00096          {
00097          while(r > y) { r -= y; q++; }
00098          r >>= shifts;
00099          sign_fixup(x, y_arg, q, r);
00100          return;
00101          }
00102 
00103       BigInt temp = y << (MP_WORD_BITS * (n-t));
00104 
00105       while(r >= temp) { r -= temp; ++q[n-t]; }
00106 
00107       for(u32bit j = n; j != t; --j)
00108          {
00109          const word x_j0  = r.word_at(j);
00110          const word x_j1 = r.word_at(j-1);
00111          const word y_t  = y.word_at(t);
00112 
00113          if(x_j0 == y_t)
00114             q[j-t-1] = MP_WORD_MAX;
00115          else
00116             q[j-t-1] = bigint_divop(x_j0, x_j1, y_t);
00117 
00118          while(bigint_divcore(q[j-t-1], y_t, y.word_at(t-1),
00119                               x_j0, x_j1, r.word_at(j-2)))
00120             --q[j-t-1];
00121 
00122          r -= (q[j-t-1] * y) << (MP_WORD_BITS * (j-t-1));
00123          if(r.is_negative())
00124             {
00125             r += y << (MP_WORD_BITS * (j-t-1));
00126             --q[j-t-1];
00127             }
00128          }
00129       r >>= shifts;
00130       }
00131 
00132    sign_fixup(x, y_arg, q, r);
00133    }
00134 
00135 }
00136 } // WRAPNS_LINE
qca

divide.cpp

qca

KDE Support
