monotone

monotone Mtn Source Tree

Root/botan/mp_asm.cpp

1/*************************************************
2* Lowest Level MPI Algorithms Source File *
3* (C) 1999-2006 The Botan Project *
4*************************************************/
5
6#include <botan/mp_asm.h>
7#include <botan/mp_asmi.h>
8#include <botan/mp_core.h>
9#include <botan/mem_ops.h>
10
11namespace Botan {
12
13extern "C" {
14
15/*************************************************
16* Two Operand Addition, No Carry *
17*************************************************/
18word bigint_add2_nc(word x[], u32bit x_size, const word y[], u32bit y_size)
19 {
20 word carry = 0;
21
22 const u32bit blocks = y_size - (y_size % 8);
23
24 for(u32bit j = 0; j != blocks; j += 8)
25 carry = word8_add2(x + j, y + j, carry);
26
27 for(u32bit j = blocks; j != y_size; ++j)
28 x[j] = word_add(x[j], y[j], &carry);
29
30 if(!carry)
31 return 0;
32
33 for(u32bit j = y_size; j != x_size; ++j)
34 if(++x[j])
35 return 0;
36
37 return 1;
38 }
39
40/*************************************************
41* Three Operand Addition, No Carry *
42*************************************************/
43word bigint_add3_nc(word z[], const word x[], u32bit x_size,
44 const word y[], u32bit y_size)
45 {
46 if(x_size < y_size)
47 { return bigint_add3_nc(z, y, y_size, x, x_size); }
48
49 word carry = 0;
50
51 const u32bit blocks = y_size - (y_size % 8);
52
53 for(u32bit j = 0; j != blocks; j += 8)
54 carry = word8_add3(z + j, x + j, y + j, carry);
55
56 for(u32bit j = blocks; j != y_size; ++j)
57 z[j] = word_add(x[j], y[j], &carry);
58
59 for(u32bit j = y_size; j != x_size; ++j)
60 {
61 word x_j = x[j] + carry;
62 if(carry && x_j)
63 carry = 0;
64 z[j] = x_j;
65 }
66
67 return carry;
68 }
69
70/*************************************************
71* Two Operand Addition *
72*************************************************/
73void bigint_add2(word x[], u32bit x_size, const word y[], u32bit y_size)
74 {
75 if(bigint_add2_nc(x, x_size, y, y_size))
76 ++x[x_size];
77 }
78
79/*************************************************
80* Three Operand Addition *
81*************************************************/
82void bigint_add3(word z[], const word x[], u32bit x_size,
83 const word y[], u32bit y_size)
84 {
85 if(bigint_add3_nc(z, x, x_size, y, y_size))
86 ++z[(x_size > y_size ? x_size : y_size)];
87 }
88
89/*************************************************
90* Two Operand Subtraction *
91*************************************************/
92void bigint_sub2(word x[], u32bit x_size, const word y[], u32bit y_size)
93 {
94 word carry = 0;
95
96 const u32bit blocks = y_size - (y_size % 8);
97
98 for(u32bit j = 0; j != blocks; j += 8)
99 carry = word8_sub2(x + j, y + j, carry);
100
101 for(u32bit j = blocks; j != y_size; ++j)
102 x[j] = word_sub(x[j], y[j], &carry);
103
104 if(!carry) return;
105
106 for(u32bit j = y_size; j != x_size; ++j)
107 {
108 --x[j];
109 if(x[j] != MP_WORD_MAX) return;
110 }
111 }
112
113/*************************************************
114* Three Operand Subtraction *
115*************************************************/
116void bigint_sub3(word z[], const word x[], u32bit x_size,
117 const word y[], u32bit y_size)
118 {
119 word carry = 0;
120
121 const u32bit blocks = y_size - (y_size % 8);
122
123 for(u32bit j = 0; j != blocks; j += 8)
124 carry = word8_sub3(z + j, x + j, y + j, carry);
125
126 for(u32bit j = blocks; j != y_size; ++j)
127 z[j] = word_sub(x[j], y[j], &carry);
128
129 for(u32bit j = y_size; j != x_size; ++j)
130 {
131 word x_j = x[j] - carry;
132 if(carry && x_j != MP_WORD_MAX)
133 carry = 0;
134 z[j] = x_j;
135 }
136 }
137
138/*************************************************
139* Two Operand Linear Multiply *
140*************************************************/
141void bigint_linmul2(word x[], u32bit x_size, word y)
142 {
143 const u32bit blocks = x_size - (x_size % 8);
144
145 word carry = 0;
146
147 for(u32bit j = 0; j != blocks; j += 8)
148 carry = word8_linmul2(x + j, y, carry);
149
150 for(u32bit j = blocks; j != x_size; ++j)
151 x[j] = word_madd2(x[j], y, carry, &carry);
152
153 x[x_size] = carry;
154 }
155
156/*************************************************
157* Three Operand Linear Multiply *
158*************************************************/
159void bigint_linmul3(word z[], const word x[], u32bit x_size, word y)
160 {
161 const u32bit blocks = x_size - (x_size % 8);
162
163 word carry = 0;
164
165 for(u32bit j = 0; j != blocks; j += 8)
166 carry = word8_linmul3(z + j, x + j, y, carry);
167
168 for(u32bit j = blocks; j != x_size; ++j)
169 z[j] = word_madd2(x[j], y, carry, &carry);
170
171 z[x_size] = carry;
172 }
173
174/*************************************************
175* Montgomery Reduction Algorithm *
176*************************************************/
177void bigint_monty_redc(word z[], u32bit z_size,
178 const word x[], u32bit x_size, word u)
179 {
180 for(u32bit j = 0; j != x_size; ++j)
181 {
182 word* z_j = z + j;
183
184 const word y = z_j[0] * u;
185
186 word carry = bigint_mul_add_words(z_j, x, x_size, y);
187
188 word z_sum = z_j[x_size] + carry;
189 carry = (z_sum < z_j[x_size]);
190 z_j[x_size] = z_sum;
191
192 for(u32bit k = x_size + 1; carry && k != z_size - j; ++k)
193 {
194 ++z_j[k];
195 carry = !z_j[k];
196 }
197 }
198
199 if(bigint_cmp(z + x_size, x_size + 1, x, x_size) >= 0)
200 bigint_sub2(z + x_size, x_size + 1, x, x_size);
201 }
202
203}
204
205}

Archive Download this file

Branches

Tags

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