1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
/*************************************************
* MPI Addition/Subtraction Source File *
* (C) 1999-2005 The Botan Project *
*************************************************/
#include <botan/mp_core.h>
namespace Botan {
/*************************************************
* Two Operand Addition *
*************************************************/
void bigint_add2(word x[], u32bit x_size, const word y[], u32bit y_size)
{
word carry = 0;
for(u32bit j = 0; j != y_size; j++)
{
word z = x[j] + y[j] + carry;
const u32bit top_x = x[j] >> (MP_WORD_BITS - 1);
const u32bit top_y = y[j] >> (MP_WORD_BITS - 1);
const u32bit top_z = z >> (MP_WORD_BITS - 1);
x[j] = z;
carry = ((top_x | top_y) & !top_z) | (top_x & top_y);
}
if(!carry) return;
for(u32bit j = y_size; j != x_size; j++)
{
x[j]++;
if(x[j]) return;
}
x[x_size]++;
}
/*************************************************
* Three Operand Addition *
*************************************************/
void bigint_add3(word z[], const word x[], u32bit x_size,
const word y[], u32bit y_size)
{
if(x_size < y_size)
{ bigint_add3(z, y, y_size, x, x_size); return; }
word carry = 0;
for(u32bit j = 0; j != y_size; j++)
{
z[j] = x[j] + y[j] + carry;
const u32bit top_x = x[j] >> (MP_WORD_BITS - 1);
const u32bit top_y = y[j] >> (MP_WORD_BITS - 1);
const u32bit top_z = z[j] >> (MP_WORD_BITS - 1);
carry = ((top_x | top_y) & !top_z) | (top_x & top_y);
}
for(u32bit j = y_size; j != x_size; j++)
z[j] = x[j];
if(!carry) return;
for(u32bit j = y_size; j != x_size; j++)
{
z[j]++;
if(z[j]) return;
}
z[x_size]++;
}
/*************************************************
* Two Operand Subtraction *
*************************************************/
void bigint_sub2(word x[], u32bit x_size, const word y[], u32bit y_size)
{
word borrow = 0;
for(u32bit j = 0; j != y_size; j++)
{
word r = x[j] - y[j];
word next = ((x[j] < r) ? 1 : 0);
r -= borrow;
borrow = next | ((r == MP_WORD_MAX) ? borrow : 0);
x[j] = r;
}
if(!borrow) return;
for(u32bit j = y_size; j != x_size; j++)
{
x[j]--;
if(x[j] != MP_WORD_MAX) return;
}
}
/*************************************************
* Three Operand Subtraction *
*************************************************/
void bigint_sub3(word z[], const word x[], u32bit x_size,
const word y[], u32bit y_size)
{
word borrow = 0;
for(u32bit j = 0; j != y_size; j++)
{
z[j] = x[j] - y[j];
word next = ((x[j] < z[j]) ? 1 : 0);
z[j] -= borrow;
borrow = next | ((z[j] == MP_WORD_MAX) ? borrow : 0);
}
for(u32bit j = y_size; j != x_size; j++)
z[j] = x[j];
if(!borrow) return;
for(u32bit j = y_size; j != x_size; j++)
{
z[j]--;
if(z[j] != MP_WORD_MAX) return;
}
}
}
|
