← Back to branch summary

~ubuntu-branches/debian/sid/botan/sid

« back to all changes in this revision

Viewing changes to src/divide.cpp

  • Committer: Package Import Robot
  • Author(s): Laszlo Boszormenyi (GCS)
  • Date: 2018-03-01 22:23:25 UTC
  • mfrom: (1.2.2)
  • Revision ID: package-import@ubuntu.com-20180301222325-7p7vc45gu3hta34d
Tags: 2.4.0-2
* Don't remove .doctrees from the manual if it doesn't exist.
* Don't specify parallel to debhelper.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/divide.cpp
1
 
/*************************************************
2
 
* Division Algorithm Source File                 *
3
 
* (C) 1999-2007 The Botan Project                *
4
 
*************************************************/
5
 
 
6
 
#include <botan/numthry.h>
7
 
#include <botan/mp_core.h>
8
 
 
9
 
namespace Botan {
10
 
 
11
 
namespace {
12
 
 
13
 
/*************************************************
14
 
* Handle signed operands, if necessary           *
15
 
*************************************************/
16
 
void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r)
17
 
   {
18
 
   if(x.sign() == BigInt::Negative)
19
 
      {
20
 
      q.flip_sign();
21
 
      if(r.is_nonzero()) { --q; r = y.abs() - r; }
22
 
      }
23
 
   if(y.sign() == BigInt::Negative)
24
 
      q.flip_sign();
25
 
   }
26
 
 
27
 
}
28
 
 
29
 
/*************************************************
30
 
* Solve x = q * y + r                            *
31
 
*************************************************/
32
 
void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r)
33
 
   {
34
 
   if(y_arg.is_zero())
35
 
      throw BigInt::DivideByZero();
36
 
 
37
 
   BigInt y = y_arg;
38
 
   const u32bit y_words = y.sig_words();
39
 
   r = x;
40
 
 
41
 
   r.set_sign(BigInt::Positive);
42
 
   y.set_sign(BigInt::Positive);
43
 
 
44
 
   s32bit compare = r.cmp(y);
45
 
 
46
 
   if(compare < 0)
47
 
      q = 0;
48
 
   else if(compare ==  0)
49
 
      {
50
 
      q = 1;
51
 
      r = 0;
52
 
      }
53
 
   else
54
 
      {
55
 
      u32bit shifts = 0;
56
 
      word y_top = y[y.sig_words()-1];
57
 
      while(y_top < MP_WORD_TOP_BIT) { y_top <<= 1; ++shifts; }
58
 
      y <<= shifts;
59
 
      r <<= shifts;
60
 
 
61
 
      const u32bit n = r.sig_words() - 1, t = y_words - 1;
62
 
 
63
 
      q.get_reg().create(n - t + 1);
64
 
      if(n <= t)
65
 
         {
66
 
         while(r > y) { r -= y; q++; }
67
 
         r >>= shifts;
68
 
         sign_fixup(x, y_arg, q, r);
69
 
         return;
70
 
         }
71
 
 
72
 
      BigInt temp = y << (MP_WORD_BITS * (n-t));
73
 
 
74
 
      while(r >= temp) { r -= temp; ++q[n-t]; }
75
 
 
76
 
      for(u32bit j = n; j != t; --j)
77
 
         {
78
 
         const word x_j0  = r.word_at(j);
79
 
         const word x_j1 = r.word_at(j-1);
80
 
         const word y_t  = y.word_at(t);
81
 
 
82
 
         if(x_j0 == y_t)
83
 
            q[j-t-1] = MP_WORD_MAX;
84
 
         else
85
 
            q[j-t-1] = bigint_divop(x_j0, x_j1, y_t);
86
 
 
87
 
         while(bigint_divcore(q[j-t-1], y_t, y.word_at(t-1),
88
 
                              x_j0, x_j1, r.word_at(j-2)))
89
 
            --q[j-t-1];
90
 
 
91
 
         r -= (q[j-t-1] * y) << (MP_WORD_BITS * (j-t-1));
92
 
         if(r.is_negative())
93
 
            {
94
 
            r += y << (MP_WORD_BITS * (j-t-1));
95
 
            --q[j-t-1];
96
 
            }
97
 
         }
98
 
      r >>= shifts;
99
 
      }
100
 
 
101
 
   sign_fixup(x, y_arg, q, r);
102
 
   }
103
 
 
104
 
}