monotone

monotone Mtn Source Tree

Root/botan/mp_comba.cpp

1/*************************************************
2* Comba Multiplication Source File *
3* (C) 1999-2005 The Botan Project *
4*************************************************/
5
6#include <botan/mp_core.h>
7#include <botan/mp_madd.h>
8
9namespace Botan {
10
11namespace {
12
13/*************************************************
14* Multiply-Add Accumulator *
15*************************************************/
16void word3_muladd(word* w2, word* w1, word* w0, word x, word y)
17 {
18 word temp = 0;
19 bigint_madd(x, y, *w0, 0, w0, &temp);
20 *w1 += temp;
21 *w2 += (*w1 < temp) ? 1 : 0;
22 }
23
24}
25
26/*************************************************
27* Comba 4x4 Multiplication *
28*************************************************/
29void bigint_comba4(word z[8], const word x[4], const word y[4])
30 {
31 word w2 = 0, w1 = 0, w0 = 0;
32
33 word3_muladd(&w2, &w1, &w0, x[0], y[0]);
34 z[0] = w0; w0 = w1; w1 = w2; w2 = 0;
35
36 word3_muladd(&w2, &w1, &w0, x[0], y[1]);
37 word3_muladd(&w2, &w1, &w0, x[1], y[0]);
38 z[1] = w0; w0 = w1; w1 = w2; w2 = 0;
39
40 word3_muladd(&w2, &w1, &w0, x[0], y[2]);
41 word3_muladd(&w2, &w1, &w0, x[1], y[1]);
42 word3_muladd(&w2, &w1, &w0, x[2], y[0]);
43 z[2] = w0; w0 = w1; w1 = w2; w2 = 0;
44
45 word3_muladd(&w2, &w1, &w0, x[0], y[3]);
46 word3_muladd(&w2, &w1, &w0, x[1], y[2]);
47 word3_muladd(&w2, &w1, &w0, x[2], y[1]);
48 word3_muladd(&w2, &w1, &w0, x[3], y[0]);
49 z[3] = w0; w0 = w1; w1 = w2; w2 = 0;
50
51 word3_muladd(&w2, &w1, &w0, x[1], y[3]);
52 word3_muladd(&w2, &w1, &w0, x[2], y[2]);
53 word3_muladd(&w2, &w1, &w0, x[3], y[1]);
54 z[4] = w0; w0 = w1; w1 = w2; w2 = 0;
55
56 word3_muladd(&w2, &w1, &w0, x[2], y[3]);
57 word3_muladd(&w2, &w1, &w0, x[3], y[2]);
58 z[5] = w0; w0 = w1; w1 = w2; w2 = 0;
59
60 word3_muladd(&w2, &w1, &w0, x[3], y[3]);
61 z[6] = w0;
62 z[7] = w1;
63 }
64
65/*************************************************
66* Comba 6x6 Multiplication *
67*************************************************/
68void bigint_comba6(word z[12], const word x[6], const word y[6])
69 {
70 word w2 = 0, w1 = 0, w0 = 0;
71
72 word3_muladd(&w2, &w1, &w0, x[0], y[0]);
73 z[0] = w0; w0 = w1; w1 = w2; w2 = 0;
74
75 word3_muladd(&w2, &w1, &w0, x[0], y[1]);
76 word3_muladd(&w2, &w1, &w0, x[1], y[0]);
77 z[1] = w0; w0 = w1; w1 = w2; w2 = 0;
78
79 word3_muladd(&w2, &w1, &w0, x[0], y[2]);
80 word3_muladd(&w2, &w1, &w0, x[1], y[1]);
81 word3_muladd(&w2, &w1, &w0, x[2], y[0]);
82 z[2] = w0; w0 = w1; w1 = w2; w2 = 0;
83
84 word3_muladd(&w2, &w1, &w0, x[0], y[3]);
85 word3_muladd(&w2, &w1, &w0, x[1], y[2]);
86 word3_muladd(&w2, &w1, &w0, x[2], y[1]);
87 word3_muladd(&w2, &w1, &w0, x[3], y[0]);
88 z[3] = w0; w0 = w1; w1 = w2; w2 = 0;
89
90 word3_muladd(&w2, &w1, &w0, x[0], y[4]);
91 word3_muladd(&w2, &w1, &w0, x[1], y[3]);
92 word3_muladd(&w2, &w1, &w0, x[2], y[2]);
93 word3_muladd(&w2, &w1, &w0, x[3], y[1]);
94 word3_muladd(&w2, &w1, &w0, x[4], y[0]);
95 z[4] = w0; w0 = w1; w1 = w2; w2 = 0;
96
97 word3_muladd(&w2, &w1, &w0, x[0], y[5]);
98 word3_muladd(&w2, &w1, &w0, x[1], y[4]);
99 word3_muladd(&w2, &w1, &w0, x[2], y[3]);
100 word3_muladd(&w2, &w1, &w0, x[3], y[2]);
101 word3_muladd(&w2, &w1, &w0, x[4], y[1]);
102 word3_muladd(&w2, &w1, &w0, x[5], y[0]);
103 z[5] = w0; w0 = w1; w1 = w2; w2 = 0;
104
105 word3_muladd(&w2, &w1, &w0, x[1], y[5]);
106 word3_muladd(&w2, &w1, &w0, x[2], y[4]);
107 word3_muladd(&w2, &w1, &w0, x[3], y[3]);
108 word3_muladd(&w2, &w1, &w0, x[4], y[2]);
109 word3_muladd(&w2, &w1, &w0, x[5], y[1]);
110 z[6] = w0; w0 = w1; w1 = w2; w2 = 0;
111
112 word3_muladd(&w2, &w1, &w0, x[2], y[5]);
113 word3_muladd(&w2, &w1, &w0, x[3], y[4]);
114 word3_muladd(&w2, &w1, &w0, x[4], y[3]);
115 word3_muladd(&w2, &w1, &w0, x[5], y[2]);
116 z[7] = w0; w0 = w1; w1 = w2; w2 = 0;
117
118 word3_muladd(&w2, &w1, &w0, x[3], y[5]);
119 word3_muladd(&w2, &w1, &w0, x[4], y[4]);
120 word3_muladd(&w2, &w1, &w0, x[5], y[3]);
121 z[8] = w0; w0 = w1; w1 = w2; w2 = 0;
122
123 word3_muladd(&w2, &w1, &w0, x[4], y[5]);
124 word3_muladd(&w2, &w1, &w0, x[5], y[4]);
125 z[9] = w0; w0 = w1; w1 = w2; w2 = 0;
126
127 word3_muladd(&w2, &w1, &w0, x[5], y[5]);
128 z[10] = w0;
129 z[11] = w1;
130 }
131
132/*************************************************
133* Comba 8x8 Multiplication *
134*************************************************/
135void bigint_comba8(word z[16], const word x[8], const word y[8])
136 {
137 word w2 = 0, w1 = 0, w0 = 0;
138
139 word3_muladd(&w2, &w1, &w0, x[0], y[0]);
140 z[0] = w0; w0 = w1; w1 = w2; w2 = 0;
141
142 word3_muladd(&w2, &w1, &w0, x[0], y[1]);
143 word3_muladd(&w2, &w1, &w0, x[1], y[0]);
144 z[1] = w0; w0 = w1; w1 = w2; w2 = 0;
145
146 word3_muladd(&w2, &w1, &w0, x[0], y[2]);
147 word3_muladd(&w2, &w1, &w0, x[1], y[1]);
148 word3_muladd(&w2, &w1, &w0, x[2], y[0]);
149 z[2] = w0; w0 = w1; w1 = w2; w2 = 0;
150
151 word3_muladd(&w2, &w1, &w0, x[0], y[3]);
152 word3_muladd(&w2, &w1, &w0, x[1], y[2]);
153 word3_muladd(&w2, &w1, &w0, x[2], y[1]);
154 word3_muladd(&w2, &w1, &w0, x[3], y[0]);
155 z[3] = w0; w0 = w1; w1 = w2; w2 = 0;
156
157 word3_muladd(&w2, &w1, &w0, x[0], y[4]);
158 word3_muladd(&w2, &w1, &w0, x[1], y[3]);
159 word3_muladd(&w2, &w1, &w0, x[2], y[2]);
160 word3_muladd(&w2, &w1, &w0, x[3], y[1]);
161 word3_muladd(&w2, &w1, &w0, x[4], y[0]);
162 z[4] = w0; w0 = w1; w1 = w2; w2 = 0;
163
164 word3_muladd(&w2, &w1, &w0, x[0], y[5]);
165 word3_muladd(&w2, &w1, &w0, x[1], y[4]);
166 word3_muladd(&w2, &w1, &w0, x[2], y[3]);
167 word3_muladd(&w2, &w1, &w0, x[3], y[2]);
168 word3_muladd(&w2, &w1, &w0, x[4], y[1]);
169 word3_muladd(&w2, &w1, &w0, x[5], y[0]);
170 z[5] = w0; w0 = w1; w1 = w2; w2 = 0;
171
172 word3_muladd(&w2, &w1, &w0, x[0], y[6]);
173 word3_muladd(&w2, &w1, &w0, x[1], y[5]);
174 word3_muladd(&w2, &w1, &w0, x[2], y[4]);
175 word3_muladd(&w2, &w1, &w0, x[3], y[3]);
176 word3_muladd(&w2, &w1, &w0, x[4], y[2]);
177 word3_muladd(&w2, &w1, &w0, x[5], y[1]);
178 word3_muladd(&w2, &w1, &w0, x[6], y[0]);
179 z[6] = w0; w0 = w1; w1 = w2; w2 = 0;
180
181 word3_muladd(&w2, &w1, &w0, x[0], y[7]);
182 word3_muladd(&w2, &w1, &w0, x[1], y[6]);
183 word3_muladd(&w2, &w1, &w0, x[2], y[5]);
184 word3_muladd(&w2, &w1, &w0, x[3], y[4]);
185 word3_muladd(&w2, &w1, &w0, x[4], y[3]);
186 word3_muladd(&w2, &w1, &w0, x[5], y[2]);
187 word3_muladd(&w2, &w1, &w0, x[6], y[1]);
188 word3_muladd(&w2, &w1, &w0, x[7], y[0]);
189 z[7] = w0; w0 = w1; w1 = w2; w2 = 0;
190
191 word3_muladd(&w2, &w1, &w0, x[1], y[7]);
192 word3_muladd(&w2, &w1, &w0, x[2], y[6]);
193 word3_muladd(&w2, &w1, &w0, x[3], y[5]);
194 word3_muladd(&w2, &w1, &w0, x[4], y[4]);
195 word3_muladd(&w2, &w1, &w0, x[5], y[3]);
196 word3_muladd(&w2, &w1, &w0, x[6], y[2]);
197 word3_muladd(&w2, &w1, &w0, x[7], y[1]);
198 z[8] = w0; w0 = w1; w1 = w2; w2 = 0;
199
200 word3_muladd(&w2, &w1, &w0, x[2], y[7]);
201 word3_muladd(&w2, &w1, &w0, x[3], y[6]);
202 word3_muladd(&w2, &w1, &w0, x[4], y[5]);
203 word3_muladd(&w2, &w1, &w0, x[5], y[4]);
204 word3_muladd(&w2, &w1, &w0, x[6], y[3]);
205 word3_muladd(&w2, &w1, &w0, x[7], y[2]);
206 z[9] = w0; w0 = w1; w1 = w2; w2 = 0;
207
208 word3_muladd(&w2, &w1, &w0, x[3], y[7]);
209 word3_muladd(&w2, &w1, &w0, x[4], y[6]);
210 word3_muladd(&w2, &w1, &w0, x[5], y[5]);
211 word3_muladd(&w2, &w1, &w0, x[6], y[4]);
212 word3_muladd(&w2, &w1, &w0, x[7], y[3]);
213 z[10] = w0; w0 = w1; w1 = w2; w2 = 0;
214
215 word3_muladd(&w2, &w1, &w0, x[4], y[7]);
216 word3_muladd(&w2, &w1, &w0, x[5], y[6]);
217 word3_muladd(&w2, &w1, &w0, x[6], y[5]);
218 word3_muladd(&w2, &w1, &w0, x[7], y[4]);
219 z[11] = w0; w0 = w1; w1 = w2; w2 = 0;
220
221 word3_muladd(&w2, &w1, &w0, x[5], y[7]);
222 word3_muladd(&w2, &w1, &w0, x[6], y[6]);
223 word3_muladd(&w2, &w1, &w0, x[7], y[5]);
224 z[12] = w0; w0 = w1; w1 = w2; w2 = 0;
225
226 word3_muladd(&w2, &w1, &w0, x[6], y[7]);
227 word3_muladd(&w2, &w1, &w0, x[7], y[6]);
228 z[13] = w0; w0 = w1; w1 = w2; w2 = 0;
229
230 word3_muladd(&w2, &w1, &w0, x[7], y[7]);
231 z[14] = w0;
232 z[15] = w1;
233 }
234
235}

Archive Download this file

Branches

Tags

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