monotone

monotone Mtn Source Tree

Root/botan/big_ops3.cpp

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

Archive Download this file

Branches

Tags

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