monotone

monotone Mtn Source Tree

Root/botan/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
9namespace Botan {
10
11namespace {
12
13/*************************************************
14* Handle signed operands, if necessary *
15*************************************************/
16void 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*************************************************/
32void 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}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status