monotone

monotone Mtn Source Tree

Root/botan/big_ops3.cpp

1/*************************************************
2* BigInt Binary Operators Source File *
3* (C) 1999-2006 The Botan Project *
4*************************************************/
5
6#include <botan/bigint.h>
7#include <botan/numthry.h>
8#include <botan/mp_core.h>
9#include <botan/bit_ops.h>
10#include <algorithm>
11
12namespace Botan {
13
14/*************************************************
15* Addition Operator *
16*************************************************/
17BigInt operator+(const BigInt& x, const BigInt& y)
18 {
19 const u32bit x_sw = x.sig_words(), y_sw = y.sig_words();
20
21 BigInt z(x.sign(), std::max(x_sw, y_sw) + 1);
22
23 if((x.sign() == y.sign()))
24 bigint_add3(z.get_reg(), x.data(), x_sw, y.data(), y_sw);
25 else
26 {
27 s32bit relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
28
29 if(relative_size < 0)
30 {
31 bigint_sub3(z.get_reg(), y.data(), y_sw, x.data(), x_sw);
32 z.set_sign(y.sign());
33 }
34 else if(relative_size == 0)
35 z.set_sign(BigInt::Positive);
36 else if(relative_size > 0)
37 bigint_sub3(z.get_reg(), x.data(), x_sw, y.data(), y_sw);
38 }
39
40 return z;
41 }
42
43/*************************************************
44* Subtraction Operator *
45*************************************************/
46BigInt operator-(const BigInt& x, const BigInt& y)
47 {
48 const u32bit x_sw = x.sig_words(), y_sw = y.sig_words();
49
50 s32bit relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
51
52 BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1);
53
54 if(relative_size < 0)
55 {
56 if(x.sign() == y.sign())
57 bigint_sub3(z.get_reg(), y.data(), y_sw, x.data(), x_sw);
58 else
59 bigint_add3(z.get_reg(), x.data(), x_sw, y.data(), y_sw);
60 z.set_sign(y.reverse_sign());
61 }
62 else if(relative_size == 0)
63 {
64 if(x.sign() != y.sign())
65 bigint_shl2(z.get_reg(), x.data(), x_sw, 0, 1);
66 }
67 else if(relative_size > 0)
68 {
69 if(x.sign() == y.sign())
70 bigint_sub3(z.get_reg(), x.data(), x_sw, y.data(), y_sw);
71 else
72 bigint_add3(z.get_reg(), x.data(), x_sw, y.data(), y_sw);
73 z.set_sign(x.sign());
74 }
75 return z;
76 }
77
78/*************************************************
79* Multiplication Operator *
80*************************************************/
81BigInt operator*(const BigInt& x, const BigInt& y)
82 {
83 const u32bit x_sw = x.sig_words(), y_sw = y.sig_words();
84
85 BigInt z(BigInt::Positive, x.size() + y.size());
86
87 if(x_sw == 1 && y_sw)
88 bigint_linmul3(z.get_reg(), y.data(), y_sw, x.word_at(0));
89 else if(y_sw == 1 && x_sw)
90 bigint_linmul3(z.get_reg(), x.data(), x_sw, y.word_at(0));
91 else if(x_sw && y_sw)
92 {
93 SecureVector<word> workspace(z.size());
94 bigint_mul(z.get_reg(), z.size(), workspace,
95 x.data(), x.size(), x_sw,
96 y.data(), y.size(), y_sw);
97 }
98
99 if(x_sw && y_sw && x.sign() != y.sign())
100 z.flip_sign();
101 return z;
102 }
103
104/*************************************************
105* Division Operator *
106*************************************************/
107BigInt operator/(const BigInt& x, const BigInt& y)
108 {
109 BigInt q, r;
110 divide(x, y, q, r);
111 return q;
112 }
113
114/*************************************************
115* Modulo Operator *
116*************************************************/
117BigInt operator%(const BigInt& n, const BigInt& mod)
118 {
119 if(mod.is_zero())
120 throw BigInt::DivideByZero();
121 if(mod.is_negative())
122 throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
123 if(n.is_positive() && mod.is_positive() && n < mod)
124 return n;
125
126 BigInt q, r;
127 divide(n, mod, q, r);
128 return r;
129 }
130
131/*************************************************
132* Modulo Operator *
133*************************************************/
134word operator%(const BigInt& n, word mod)
135 {
136 if(mod == 0)
137 throw BigInt::DivideByZero();
138 if(power_of_2(mod))
139 return (n.word_at(0) & (mod - 1));
140
141 word remainder = 0;
142
143 for(u32bit j = n.sig_words(); j > 0; --j)
144 remainder = bigint_modop(remainder, n.word_at(j-1), mod);
145
146 if(remainder && n.sign() == BigInt::Negative)
147 return mod - remainder;
148 return remainder;
149 }
150
151/*************************************************
152* Left Shift Operator *
153*************************************************/
154BigInt operator<<(const BigInt& x, u32bit shift)
155 {
156 if(shift == 0)
157 return x;
158
159 const u32bit shift_words = shift / MP_WORD_BITS,
160 shift_bits = shift % MP_WORD_BITS;
161
162 const u32bit x_sw = x.sig_words();
163
164 BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
165 bigint_shl2(y.get_reg(), x.data(), x_sw, shift_words, shift_bits);
166 return y;
167 }
168
169/*************************************************
170* Right Shift Operator *
171*************************************************/
172BigInt operator>>(const BigInt& x, u32bit shift)
173 {
174 if(shift == 0)
175 return x;
176 if(x.bits() <= shift)
177 return 0;
178
179 const u32bit shift_words = shift / MP_WORD_BITS,
180 shift_bits = shift % MP_WORD_BITS,
181 x_sw = x.sig_words();
182
183 BigInt y(x.sign(), x_sw - shift_words);
184 bigint_shr2(y.get_reg(), x.data(), x_sw, shift_words, shift_bits);
185 return y;
186 }
187
188}

Archive Download this file

Branches

Tags

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