1 | /* crypto/bn/bn_asm.c */
|
---|
2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
|
---|
3 | * All rights reserved.
|
---|
4 | *
|
---|
5 | * This package is an SSL implementation written
|
---|
6 | * by Eric Young (eay@cryptsoft.com).
|
---|
7 | * The implementation was written so as to conform with Netscapes SSL.
|
---|
8 | *
|
---|
9 | * This library is free for commercial and non-commercial use as long as
|
---|
10 | * the following conditions are aheared to. The following conditions
|
---|
11 | * apply to all code found in this distribution, be it the RC4, RSA,
|
---|
12 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation
|
---|
13 | * included with this distribution is covered by the same copyright terms
|
---|
14 | * except that the holder is Tim Hudson (tjh@cryptsoft.com).
|
---|
15 | *
|
---|
16 | * Copyright remains Eric Young's, and as such any Copyright notices in
|
---|
17 | * the code are not to be removed.
|
---|
18 | * If this package is used in a product, Eric Young should be given attribution
|
---|
19 | * as the author of the parts of the library used.
|
---|
20 | * This can be in the form of a textual message at program startup or
|
---|
21 | * in documentation (online or textual) provided with the package.
|
---|
22 | *
|
---|
23 | * Redistribution and use in source and binary forms, with or without
|
---|
24 | * modification, are permitted provided that the following conditions
|
---|
25 | * are met:
|
---|
26 | * 1. Redistributions of source code must retain the copyright
|
---|
27 | * notice, this list of conditions and the following disclaimer.
|
---|
28 | * 2. Redistributions in binary form must reproduce the above copyright
|
---|
29 | * notice, this list of conditions and the following disclaimer in the
|
---|
30 | * documentation and/or other materials provided with the distribution.
|
---|
31 | * 3. All advertising materials mentioning features or use of this software
|
---|
32 | * must display the following acknowledgement:
|
---|
33 | * "This product includes cryptographic software written by
|
---|
34 | * Eric Young (eay@cryptsoft.com)"
|
---|
35 | * The word 'cryptographic' can be left out if the rouines from the library
|
---|
36 | * being used are not cryptographic related :-).
|
---|
37 | * 4. If you include any Windows specific code (or a derivative thereof) from
|
---|
38 | * the apps directory (application code) you must include an acknowledgement:
|
---|
39 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
|
---|
40 | *
|
---|
41 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
|
---|
42 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
---|
43 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
---|
44 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
|
---|
45 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
|
---|
46 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
|
---|
47 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
---|
48 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
|
---|
49 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
|
---|
50 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
---|
51 | * SUCH DAMAGE.
|
---|
52 | *
|
---|
53 | * The licence and distribution terms for any publically available version or
|
---|
54 | * derivative of this code cannot be changed. i.e. this code cannot simply be
|
---|
55 | * copied and put under another distribution licence
|
---|
56 | * [including the GNU Public Licence.]
|
---|
57 | */
|
---|
58 |
|
---|
59 | #ifndef BN_DEBUG
|
---|
60 | # undef NDEBUG /* avoid conflicting definitions */
|
---|
61 | # define NDEBUG
|
---|
62 | #endif
|
---|
63 |
|
---|
64 | #include <stdio.h>
|
---|
65 | #include <assert.h>
|
---|
66 | #include "bn_lcl.h"
|
---|
67 | #include "openssl_mods.h"
|
---|
68 |
|
---|
69 | #if defined(BN_LLONG) || defined(BN_UMULT_HIGH)
|
---|
70 |
|
---|
71 | BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
|
---|
72 | {
|
---|
73 | BN_ULONG c1=0;
|
---|
74 |
|
---|
75 | assert(num >= 0);
|
---|
76 | if (num <= 0) return(c1);
|
---|
77 |
|
---|
78 | while (num&~3)
|
---|
79 | {
|
---|
80 | mul_add(rp[0],ap[0],w,c1);
|
---|
81 | mul_add(rp[1],ap[1],w,c1);
|
---|
82 | mul_add(rp[2],ap[2],w,c1);
|
---|
83 | mul_add(rp[3],ap[3],w,c1);
|
---|
84 | ap+=4; rp+=4; num-=4;
|
---|
85 | }
|
---|
86 | if (num)
|
---|
87 | {
|
---|
88 | mul_add(rp[0],ap[0],w,c1); if (--num==0) return c1;
|
---|
89 | mul_add(rp[1],ap[1],w,c1); if (--num==0) return c1;
|
---|
90 | mul_add(rp[2],ap[2],w,c1); return c1;
|
---|
91 | }
|
---|
92 |
|
---|
93 | return(c1);
|
---|
94 | }
|
---|
95 |
|
---|
96 | BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
|
---|
97 | {
|
---|
98 | BN_ULONG c1=0;
|
---|
99 |
|
---|
100 | assert(num >= 0);
|
---|
101 | if (num <= 0) return(c1);
|
---|
102 |
|
---|
103 | while (num&~3)
|
---|
104 | {
|
---|
105 | mul(rp[0],ap[0],w,c1);
|
---|
106 | mul(rp[1],ap[1],w,c1);
|
---|
107 | mul(rp[2],ap[2],w,c1);
|
---|
108 | mul(rp[3],ap[3],w,c1);
|
---|
109 | ap+=4; rp+=4; num-=4;
|
---|
110 | }
|
---|
111 | if (num)
|
---|
112 | {
|
---|
113 | mul(rp[0],ap[0],w,c1); if (--num == 0) return c1;
|
---|
114 | mul(rp[1],ap[1],w,c1); if (--num == 0) return c1;
|
---|
115 | mul(rp[2],ap[2],w,c1);
|
---|
116 | }
|
---|
117 | return(c1);
|
---|
118 | }
|
---|
119 |
|
---|
120 | void bn_sqr_words(BN_ULONG *r, BN_ULONG *a, int n)
|
---|
121 | {
|
---|
122 | assert(n >= 0);
|
---|
123 | if (n <= 0) return;
|
---|
124 | while (n&~3)
|
---|
125 | {
|
---|
126 | sqr(r[0],r[1],a[0]);
|
---|
127 | sqr(r[2],r[3],a[1]);
|
---|
128 | sqr(r[4],r[5],a[2]);
|
---|
129 | sqr(r[6],r[7],a[3]);
|
---|
130 | a+=4; r+=8; n-=4;
|
---|
131 | }
|
---|
132 | if (n)
|
---|
133 | {
|
---|
134 | sqr(r[0],r[1],a[0]); if (--n == 0) return;
|
---|
135 | sqr(r[2],r[3],a[1]); if (--n == 0) return;
|
---|
136 | sqr(r[4],r[5],a[2]);
|
---|
137 | }
|
---|
138 | }
|
---|
139 |
|
---|
140 | #else /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
|
---|
141 |
|
---|
142 | BN_ULONG bn_mul_add_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
|
---|
143 | {
|
---|
144 | BN_ULONG c=0;
|
---|
145 | BN_ULONG bl,bh;
|
---|
146 |
|
---|
147 | assert(num >= 0);
|
---|
148 | if (num <= 0) return((BN_ULONG)0);
|
---|
149 |
|
---|
150 | bl=LBITS(w);
|
---|
151 | bh=HBITS(w);
|
---|
152 |
|
---|
153 | for (;;)
|
---|
154 | {
|
---|
155 | mul_add(rp[0],ap[0],bl,bh,c);
|
---|
156 | if (--num == 0) break;
|
---|
157 | mul_add(rp[1],ap[1],bl,bh,c);
|
---|
158 | if (--num == 0) break;
|
---|
159 | mul_add(rp[2],ap[2],bl,bh,c);
|
---|
160 | if (--num == 0) break;
|
---|
161 | mul_add(rp[3],ap[3],bl,bh,c);
|
---|
162 | if (--num == 0) break;
|
---|
163 | ap+=4;
|
---|
164 | rp+=4;
|
---|
165 | }
|
---|
166 | return(c);
|
---|
167 | }
|
---|
168 |
|
---|
169 | BN_ULONG bn_mul_words(BN_ULONG *rp, BN_ULONG *ap, int num, BN_ULONG w)
|
---|
170 | {
|
---|
171 | BN_ULONG carry=0;
|
---|
172 | BN_ULONG bl,bh;
|
---|
173 |
|
---|
174 | assert(num >= 0);
|
---|
175 | if (num <= 0) return((BN_ULONG)0);
|
---|
176 |
|
---|
177 | bl=LBITS(w);
|
---|
178 | bh=HBITS(w);
|
---|
179 |
|
---|
180 | for (;;)
|
---|
181 | {
|
---|
182 | mul(rp[0],ap[0],bl,bh,carry);
|
---|
183 | if (--num == 0) break;
|
---|
184 | mul(rp[1],ap[1],bl,bh,carry);
|
---|
185 | if (--num == 0) break;
|
---|
186 | mul(rp[2],ap[2],bl,bh,carry);
|
---|
187 | if (--num == 0) break;
|
---|
188 | mul(rp[3],ap[3],bl,bh,carry);
|
---|
189 | if (--num == 0) break;
|
---|
190 | ap+=4;
|
---|
191 | rp+=4;
|
---|
192 | }
|
---|
193 | return(carry);
|
---|
194 | }
|
---|
195 |
|
---|
196 | void bn_sqr_words(BN_ULONG *r, BN_ULONG *a, int n)
|
---|
197 | {
|
---|
198 | assert(n >= 0);
|
---|
199 | if (n <= 0) return;
|
---|
200 | for (;;)
|
---|
201 | {
|
---|
202 | sqr64(r[0],r[1],a[0]);
|
---|
203 | if (--n == 0) break;
|
---|
204 |
|
---|
205 | sqr64(r[2],r[3],a[1]);
|
---|
206 | if (--n == 0) break;
|
---|
207 |
|
---|
208 | sqr64(r[4],r[5],a[2]);
|
---|
209 | if (--n == 0) break;
|
---|
210 |
|
---|
211 | sqr64(r[6],r[7],a[3]);
|
---|
212 | if (--n == 0) break;
|
---|
213 |
|
---|
214 | a+=4;
|
---|
215 | r+=8;
|
---|
216 | }
|
---|
217 | }
|
---|
218 |
|
---|
219 | #endif /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
|
---|
220 |
|
---|
221 | #if defined(BN_LLONG) && defined(BN_DIV2W)
|
---|
222 |
|
---|
223 | BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
|
---|
224 | {
|
---|
225 | return((BN_ULONG)(((((BN_ULLONG)h)<<BN_BITS2)|l)/(BN_ULLONG)d));
|
---|
226 | }
|
---|
227 |
|
---|
228 | #else
|
---|
229 |
|
---|
230 | /* Divide h,l by d and return the result. */
|
---|
231 | /* I need to test this some more :-( */
|
---|
232 | BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
|
---|
233 | {
|
---|
234 | BN_ULONG dh,dl,q,ret=0,th,tl,t;
|
---|
235 | int i,count=2;
|
---|
236 |
|
---|
237 | if (d == 0) return(BN_MASK2);
|
---|
238 |
|
---|
239 | i=BN_num_bits_word(d);
|
---|
240 | assert((i == BN_BITS2) || (h > (BN_ULONG)1<<i));
|
---|
241 |
|
---|
242 | i=BN_BITS2-i;
|
---|
243 | if (h >= d) h-=d;
|
---|
244 |
|
---|
245 | if (i)
|
---|
246 | {
|
---|
247 | d<<=i;
|
---|
248 | h=(h<<i)|(l>>(BN_BITS2-i));
|
---|
249 | l<<=i;
|
---|
250 | }
|
---|
251 | dh=(d&BN_MASK2h)>>BN_BITS4;
|
---|
252 | dl=(d&BN_MASK2l);
|
---|
253 | for (;;)
|
---|
254 | {
|
---|
255 | if ((h>>BN_BITS4) == dh)
|
---|
256 | q=BN_MASK2l;
|
---|
257 | else
|
---|
258 | q=h/dh;
|
---|
259 |
|
---|
260 | th=q*dh;
|
---|
261 | tl=dl*q;
|
---|
262 | for (;;)
|
---|
263 | {
|
---|
264 | t=h-th;
|
---|
265 | if ((t&BN_MASK2h) ||
|
---|
266 | ((tl) <= (
|
---|
267 | (t<<BN_BITS4)|
|
---|
268 | ((l&BN_MASK2h)>>BN_BITS4))))
|
---|
269 | break;
|
---|
270 | q--;
|
---|
271 | th-=dh;
|
---|
272 | tl-=dl;
|
---|
273 | }
|
---|
274 | t=(tl>>BN_BITS4);
|
---|
275 | tl=(tl<<BN_BITS4)&BN_MASK2h;
|
---|
276 | th+=t;
|
---|
277 |
|
---|
278 | if (l < tl) th++;
|
---|
279 | l-=tl;
|
---|
280 | if (h < th)
|
---|
281 | {
|
---|
282 | h+=d;
|
---|
283 | q--;
|
---|
284 | }
|
---|
285 | h-=th;
|
---|
286 |
|
---|
287 | if (--count == 0) break;
|
---|
288 |
|
---|
289 | ret=q<<BN_BITS4;
|
---|
290 | h=((h<<BN_BITS4)|(l>>BN_BITS4))&BN_MASK2;
|
---|
291 | l=(l&BN_MASK2l)<<BN_BITS4;
|
---|
292 | }
|
---|
293 | ret|=q;
|
---|
294 | return(ret);
|
---|
295 | }
|
---|
296 | #endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */
|
---|
297 |
|
---|
298 | #ifdef BN_LLONG
|
---|
299 | BN_ULONG bn_add_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
|
---|
300 | {
|
---|
301 | BN_ULLONG ll=0;
|
---|
302 |
|
---|
303 | assert(n >= 0);
|
---|
304 | if (n <= 0) return((BN_ULONG)0);
|
---|
305 |
|
---|
306 | for (;;)
|
---|
307 | {
|
---|
308 | ll+=(BN_ULLONG)a[0]+b[0];
|
---|
309 | r[0]=(BN_ULONG)ll&BN_MASK2;
|
---|
310 | ll>>=BN_BITS2;
|
---|
311 | if (--n <= 0) break;
|
---|
312 |
|
---|
313 | ll+=(BN_ULLONG)a[1]+b[1];
|
---|
314 | r[1]=(BN_ULONG)ll&BN_MASK2;
|
---|
315 | ll>>=BN_BITS2;
|
---|
316 | if (--n <= 0) break;
|
---|
317 |
|
---|
318 | ll+=(BN_ULLONG)a[2]+b[2];
|
---|
319 | r[2]=(BN_ULONG)ll&BN_MASK2;
|
---|
320 | ll>>=BN_BITS2;
|
---|
321 | if (--n <= 0) break;
|
---|
322 |
|
---|
323 | ll+=(BN_ULLONG)a[3]+b[3];
|
---|
324 | r[3]=(BN_ULONG)ll&BN_MASK2;
|
---|
325 | ll>>=BN_BITS2;
|
---|
326 | if (--n <= 0) break;
|
---|
327 |
|
---|
328 | a+=4;
|
---|
329 | b+=4;
|
---|
330 | r+=4;
|
---|
331 | }
|
---|
332 | return((BN_ULONG)ll);
|
---|
333 | }
|
---|
334 | #else /* !BN_LLONG */
|
---|
335 | BN_ULONG bn_add_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
|
---|
336 | {
|
---|
337 | BN_ULONG c,l,t;
|
---|
338 |
|
---|
339 | assert(n >= 0);
|
---|
340 | if (n <= 0) return((BN_ULONG)0);
|
---|
341 |
|
---|
342 | c=0;
|
---|
343 | for (;;)
|
---|
344 | {
|
---|
345 | t=a[0];
|
---|
346 | t=(t+c)&BN_MASK2;
|
---|
347 | c=(t < c);
|
---|
348 | l=(t+b[0])&BN_MASK2;
|
---|
349 | c+=(l < t);
|
---|
350 | r[0]=l;
|
---|
351 | if (--n <= 0) break;
|
---|
352 |
|
---|
353 | t=a[1];
|
---|
354 | t=(t+c)&BN_MASK2;
|
---|
355 | c=(t < c);
|
---|
356 | l=(t+b[1])&BN_MASK2;
|
---|
357 | c+=(l < t);
|
---|
358 | r[1]=l;
|
---|
359 | if (--n <= 0) break;
|
---|
360 |
|
---|
361 | t=a[2];
|
---|
362 | t=(t+c)&BN_MASK2;
|
---|
363 | c=(t < c);
|
---|
364 | l=(t+b[2])&BN_MASK2;
|
---|
365 | c+=(l < t);
|
---|
366 | r[2]=l;
|
---|
367 | if (--n <= 0) break;
|
---|
368 |
|
---|
369 | t=a[3];
|
---|
370 | t=(t+c)&BN_MASK2;
|
---|
371 | c=(t < c);
|
---|
372 | l=(t+b[3])&BN_MASK2;
|
---|
373 | c+=(l < t);
|
---|
374 | r[3]=l;
|
---|
375 | if (--n <= 0) break;
|
---|
376 |
|
---|
377 | a+=4;
|
---|
378 | b+=4;
|
---|
379 | r+=4;
|
---|
380 | }
|
---|
381 | return((BN_ULONG)c);
|
---|
382 | }
|
---|
383 | #endif /* !BN_LLONG */
|
---|
384 |
|
---|
385 | BN_ULONG bn_sub_words(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
|
---|
386 | {
|
---|
387 | BN_ULONG t1,t2;
|
---|
388 | int c=0;
|
---|
389 |
|
---|
390 | assert(n >= 0);
|
---|
391 | if (n <= 0) return((BN_ULONG)0);
|
---|
392 |
|
---|
393 | for (;;)
|
---|
394 | {
|
---|
395 | t1=a[0]; t2=b[0];
|
---|
396 | r[0]=(t1-t2-c)&BN_MASK2;
|
---|
397 | if (t1 != t2) c=(t1 < t2);
|
---|
398 | if (--n <= 0) break;
|
---|
399 |
|
---|
400 | t1=a[1]; t2=b[1];
|
---|
401 | r[1]=(t1-t2-c)&BN_MASK2;
|
---|
402 | if (t1 != t2) c=(t1 < t2);
|
---|
403 | if (--n <= 0) break;
|
---|
404 |
|
---|
405 | t1=a[2]; t2=b[2];
|
---|
406 | r[2]=(t1-t2-c)&BN_MASK2;
|
---|
407 | if (t1 != t2) c=(t1 < t2);
|
---|
408 | if (--n <= 0) break;
|
---|
409 |
|
---|
410 | t1=a[3]; t2=b[3];
|
---|
411 | r[3]=(t1-t2-c)&BN_MASK2;
|
---|
412 | if (t1 != t2) c=(t1 < t2);
|
---|
413 | if (--n <= 0) break;
|
---|
414 |
|
---|
415 | a+=4;
|
---|
416 | b+=4;
|
---|
417 | r+=4;
|
---|
418 | }
|
---|
419 | return(c);
|
---|
420 | }
|
---|
421 |
|
---|
422 | #ifdef BN_MUL_COMBA
|
---|
423 |
|
---|
424 | #undef bn_mul_comba8
|
---|
425 | #undef bn_mul_comba4
|
---|
426 | #undef bn_sqr_comba8
|
---|
427 | #undef bn_sqr_comba4
|
---|
428 |
|
---|
429 | /* mul_add_c(a,b,c0,c1,c2) -- c+=a*b for three word number c=(c2,c1,c0) */
|
---|
430 | /* mul_add_c2(a,b,c0,c1,c2) -- c+=2*a*b for three word number c=(c2,c1,c0) */
|
---|
431 | /* sqr_add_c(a,i,c0,c1,c2) -- c+=a[i]^2 for three word number c=(c2,c1,c0) */
|
---|
432 | /* sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number c=(c2,c1,c0) */
|
---|
433 |
|
---|
434 | #ifdef BN_LLONG
|
---|
435 | #define mul_add_c(a,b,c0,c1,c2) \
|
---|
436 | t=(BN_ULLONG)a*b; \
|
---|
437 | t1=(BN_ULONG)Lw(t); \
|
---|
438 | t2=(BN_ULONG)Hw(t); \
|
---|
439 | c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
|
---|
440 | c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
|
---|
441 |
|
---|
442 | #define mul_add_c2(a,b,c0,c1,c2) \
|
---|
443 | t=(BN_ULLONG)a*b; \
|
---|
444 | tt=(t+t)&BN_MASK; \
|
---|
445 | if (tt < t) c2++; \
|
---|
446 | t1=(BN_ULONG)Lw(tt); \
|
---|
447 | t2=(BN_ULONG)Hw(tt); \
|
---|
448 | c0=(c0+t1)&BN_MASK2; \
|
---|
449 | if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \
|
---|
450 | c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
|
---|
451 |
|
---|
452 | #define sqr_add_c(a,i,c0,c1,c2) \
|
---|
453 | t=(BN_ULLONG)a[i]*a[i]; \
|
---|
454 | t1=(BN_ULONG)Lw(t); \
|
---|
455 | t2=(BN_ULONG)Hw(t); \
|
---|
456 | c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
|
---|
457 | c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
|
---|
458 |
|
---|
459 | #define sqr_add_c2(a,i,j,c0,c1,c2) \
|
---|
460 | mul_add_c2((a)[i],(a)[j],c0,c1,c2)
|
---|
461 |
|
---|
462 | #elif defined(BN_UMULT_HIGH)
|
---|
463 |
|
---|
464 | #define mul_add_c(a,b,c0,c1,c2) { \
|
---|
465 | BN_ULONG ta=(a),tb=(b); \
|
---|
466 | t1 = ta * tb; \
|
---|
467 | t2 = BN_UMULT_HIGH(ta,tb); \
|
---|
468 | c0 += t1; t2 += (c0<t1)?1:0; \
|
---|
469 | c1 += t2; c2 += (c1<t2)?1:0; \
|
---|
470 | }
|
---|
471 |
|
---|
472 | #define mul_add_c2(a,b,c0,c1,c2) { \
|
---|
473 | BN_ULONG ta=(a),tb=(b),t0; \
|
---|
474 | t1 = BN_UMULT_HIGH(ta,tb); \
|
---|
475 | t0 = ta * tb; \
|
---|
476 | t2 = t1+t1; c2 += (t2<t1)?1:0; \
|
---|
477 | t1 = t0+t0; t2 += (t1<t0)?1:0; \
|
---|
478 | c0 += t1; t2 += (c0<t1)?1:0; \
|
---|
479 | c1 += t2; c2 += (c1<t2)?1:0; \
|
---|
480 | }
|
---|
481 |
|
---|
482 | #define sqr_add_c(a,i,c0,c1,c2) { \
|
---|
483 | BN_ULONG ta=(a)[i]; \
|
---|
484 | t1 = ta * ta; \
|
---|
485 | t2 = BN_UMULT_HIGH(ta,ta); \
|
---|
486 | c0 += t1; t2 += (c0<t1)?1:0; \
|
---|
487 | c1 += t2; c2 += (c1<t2)?1:0; \
|
---|
488 | }
|
---|
489 |
|
---|
490 | #define sqr_add_c2(a,i,j,c0,c1,c2) \
|
---|
491 | mul_add_c2((a)[i],(a)[j],c0,c1,c2)
|
---|
492 |
|
---|
493 | #else /* !BN_LLONG */
|
---|
494 | #define mul_add_c(a,b,c0,c1,c2) \
|
---|
495 | t1=LBITS(a); t2=HBITS(a); \
|
---|
496 | bl=LBITS(b); bh=HBITS(b); \
|
---|
497 | mul64(t1,t2,bl,bh); \
|
---|
498 | c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
|
---|
499 | c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
|
---|
500 |
|
---|
501 | #define mul_add_c2(a,b,c0,c1,c2) \
|
---|
502 | t1=LBITS(a); t2=HBITS(a); \
|
---|
503 | bl=LBITS(b); bh=HBITS(b); \
|
---|
504 | mul64(t1,t2,bl,bh); \
|
---|
505 | if (t2 & BN_TBIT) c2++; \
|
---|
506 | t2=(t2+t2)&BN_MASK2; \
|
---|
507 | if (t1 & BN_TBIT) t2++; \
|
---|
508 | t1=(t1+t1)&BN_MASK2; \
|
---|
509 | c0=(c0+t1)&BN_MASK2; \
|
---|
510 | if ((c0 < t1) && (((++t2)&BN_MASK2) == 0)) c2++; \
|
---|
511 | c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
|
---|
512 |
|
---|
513 | #define sqr_add_c(a,i,c0,c1,c2) \
|
---|
514 | sqr64(t1,t2,(a)[i]); \
|
---|
515 | c0=(c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
|
---|
516 | c1=(c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
|
---|
517 |
|
---|
518 | #define sqr_add_c2(a,i,j,c0,c1,c2) \
|
---|
519 | mul_add_c2((a)[i],(a)[j],c0,c1,c2)
|
---|
520 | #endif /* !BN_LLONG */
|
---|
521 |
|
---|
522 | void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
|
---|
523 | {
|
---|
524 | #ifdef BN_LLONG
|
---|
525 | BN_ULLONG t;
|
---|
526 | #else
|
---|
527 | BN_ULONG bl,bh;
|
---|
528 | #endif
|
---|
529 | BN_ULONG t1,t2;
|
---|
530 | BN_ULONG c1,c2,c3;
|
---|
531 |
|
---|
532 | c1=0;
|
---|
533 | c2=0;
|
---|
534 | c3=0;
|
---|
535 | mul_add_c(a[0],b[0],c1,c2,c3);
|
---|
536 | r[0]=c1;
|
---|
537 | c1=0;
|
---|
538 | mul_add_c(a[0],b[1],c2,c3,c1);
|
---|
539 | mul_add_c(a[1],b[0],c2,c3,c1);
|
---|
540 | r[1]=c2;
|
---|
541 | c2=0;
|
---|
542 | mul_add_c(a[2],b[0],c3,c1,c2);
|
---|
543 | mul_add_c(a[1],b[1],c3,c1,c2);
|
---|
544 | mul_add_c(a[0],b[2],c3,c1,c2);
|
---|
545 | r[2]=c3;
|
---|
546 | c3=0;
|
---|
547 | mul_add_c(a[0],b[3],c1,c2,c3);
|
---|
548 | mul_add_c(a[1],b[2],c1,c2,c3);
|
---|
549 | mul_add_c(a[2],b[1],c1,c2,c3);
|
---|
550 | mul_add_c(a[3],b[0],c1,c2,c3);
|
---|
551 | r[3]=c1;
|
---|
552 | c1=0;
|
---|
553 | mul_add_c(a[4],b[0],c2,c3,c1);
|
---|
554 | mul_add_c(a[3],b[1],c2,c3,c1);
|
---|
555 | mul_add_c(a[2],b[2],c2,c3,c1);
|
---|
556 | mul_add_c(a[1],b[3],c2,c3,c1);
|
---|
557 | mul_add_c(a[0],b[4],c2,c3,c1);
|
---|
558 | r[4]=c2;
|
---|
559 | c2=0;
|
---|
560 | mul_add_c(a[0],b[5],c3,c1,c2);
|
---|
561 | mul_add_c(a[1],b[4],c3,c1,c2);
|
---|
562 | mul_add_c(a[2],b[3],c3,c1,c2);
|
---|
563 | mul_add_c(a[3],b[2],c3,c1,c2);
|
---|
564 | mul_add_c(a[4],b[1],c3,c1,c2);
|
---|
565 | mul_add_c(a[5],b[0],c3,c1,c2);
|
---|
566 | r[5]=c3;
|
---|
567 | c3=0;
|
---|
568 | mul_add_c(a[6],b[0],c1,c2,c3);
|
---|
569 | mul_add_c(a[5],b[1],c1,c2,c3);
|
---|
570 | mul_add_c(a[4],b[2],c1,c2,c3);
|
---|
571 | mul_add_c(a[3],b[3],c1,c2,c3);
|
---|
572 | mul_add_c(a[2],b[4],c1,c2,c3);
|
---|
573 | mul_add_c(a[1],b[5],c1,c2,c3);
|
---|
574 | mul_add_c(a[0],b[6],c1,c2,c3);
|
---|
575 | r[6]=c1;
|
---|
576 | c1=0;
|
---|
577 | mul_add_c(a[0],b[7],c2,c3,c1);
|
---|
578 | mul_add_c(a[1],b[6],c2,c3,c1);
|
---|
579 | mul_add_c(a[2],b[5],c2,c3,c1);
|
---|
580 | mul_add_c(a[3],b[4],c2,c3,c1);
|
---|
581 | mul_add_c(a[4],b[3],c2,c3,c1);
|
---|
582 | mul_add_c(a[5],b[2],c2,c3,c1);
|
---|
583 | mul_add_c(a[6],b[1],c2,c3,c1);
|
---|
584 | mul_add_c(a[7],b[0],c2,c3,c1);
|
---|
585 | r[7]=c2;
|
---|
586 | c2=0;
|
---|
587 | mul_add_c(a[7],b[1],c3,c1,c2);
|
---|
588 | mul_add_c(a[6],b[2],c3,c1,c2);
|
---|
589 | mul_add_c(a[5],b[3],c3,c1,c2);
|
---|
590 | mul_add_c(a[4],b[4],c3,c1,c2);
|
---|
591 | mul_add_c(a[3],b[5],c3,c1,c2);
|
---|
592 | mul_add_c(a[2],b[6],c3,c1,c2);
|
---|
593 | mul_add_c(a[1],b[7],c3,c1,c2);
|
---|
594 | r[8]=c3;
|
---|
595 | c3=0;
|
---|
596 | mul_add_c(a[2],b[7],c1,c2,c3);
|
---|
597 | mul_add_c(a[3],b[6],c1,c2,c3);
|
---|
598 | mul_add_c(a[4],b[5],c1,c2,c3);
|
---|
599 | mul_add_c(a[5],b[4],c1,c2,c3);
|
---|
600 | mul_add_c(a[6],b[3],c1,c2,c3);
|
---|
601 | mul_add_c(a[7],b[2],c1,c2,c3);
|
---|
602 | r[9]=c1;
|
---|
603 | c1=0;
|
---|
604 | mul_add_c(a[7],b[3],c2,c3,c1);
|
---|
605 | mul_add_c(a[6],b[4],c2,c3,c1);
|
---|
606 | mul_add_c(a[5],b[5],c2,c3,c1);
|
---|
607 | mul_add_c(a[4],b[6],c2,c3,c1);
|
---|
608 | mul_add_c(a[3],b[7],c2,c3,c1);
|
---|
609 | r[10]=c2;
|
---|
610 | c2=0;
|
---|
611 | mul_add_c(a[4],b[7],c3,c1,c2);
|
---|
612 | mul_add_c(a[5],b[6],c3,c1,c2);
|
---|
613 | mul_add_c(a[6],b[5],c3,c1,c2);
|
---|
614 | mul_add_c(a[7],b[4],c3,c1,c2);
|
---|
615 | r[11]=c3;
|
---|
616 | c3=0;
|
---|
617 | mul_add_c(a[7],b[5],c1,c2,c3);
|
---|
618 | mul_add_c(a[6],b[6],c1,c2,c3);
|
---|
619 | mul_add_c(a[5],b[7],c1,c2,c3);
|
---|
620 | r[12]=c1;
|
---|
621 | c1=0;
|
---|
622 | mul_add_c(a[6],b[7],c2,c3,c1);
|
---|
623 | mul_add_c(a[7],b[6],c2,c3,c1);
|
---|
624 | r[13]=c2;
|
---|
625 | c2=0;
|
---|
626 | mul_add_c(a[7],b[7],c3,c1,c2);
|
---|
627 | r[14]=c3;
|
---|
628 | r[15]=c1;
|
---|
629 | }
|
---|
630 |
|
---|
631 | void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
|
---|
632 | {
|
---|
633 | #ifdef BN_LLONG
|
---|
634 | BN_ULLONG t;
|
---|
635 | #else
|
---|
636 | BN_ULONG bl,bh;
|
---|
637 | #endif
|
---|
638 | BN_ULONG t1,t2;
|
---|
639 | BN_ULONG c1,c2,c3;
|
---|
640 |
|
---|
641 | c1=0;
|
---|
642 | c2=0;
|
---|
643 | c3=0;
|
---|
644 | mul_add_c(a[0],b[0],c1,c2,c3);
|
---|
645 | r[0]=c1;
|
---|
646 | c1=0;
|
---|
647 | mul_add_c(a[0],b[1],c2,c3,c1);
|
---|
648 | mul_add_c(a[1],b[0],c2,c3,c1);
|
---|
649 | r[1]=c2;
|
---|
650 | c2=0;
|
---|
651 | mul_add_c(a[2],b[0],c3,c1,c2);
|
---|
652 | mul_add_c(a[1],b[1],c3,c1,c2);
|
---|
653 | mul_add_c(a[0],b[2],c3,c1,c2);
|
---|
654 | r[2]=c3;
|
---|
655 | c3=0;
|
---|
656 | mul_add_c(a[0],b[3],c1,c2,c3);
|
---|
657 | mul_add_c(a[1],b[2],c1,c2,c3);
|
---|
658 | mul_add_c(a[2],b[1],c1,c2,c3);
|
---|
659 | mul_add_c(a[3],b[0],c1,c2,c3);
|
---|
660 | r[3]=c1;
|
---|
661 | c1=0;
|
---|
662 | mul_add_c(a[3],b[1],c2,c3,c1);
|
---|
663 | mul_add_c(a[2],b[2],c2,c3,c1);
|
---|
664 | mul_add_c(a[1],b[3],c2,c3,c1);
|
---|
665 | r[4]=c2;
|
---|
666 | c2=0;
|
---|
667 | mul_add_c(a[2],b[3],c3,c1,c2);
|
---|
668 | mul_add_c(a[3],b[2],c3,c1,c2);
|
---|
669 | r[5]=c3;
|
---|
670 | c3=0;
|
---|
671 | mul_add_c(a[3],b[3],c1,c2,c3);
|
---|
672 | r[6]=c1;
|
---|
673 | r[7]=c2;
|
---|
674 | }
|
---|
675 |
|
---|
676 | void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a)
|
---|
677 | {
|
---|
678 | #ifdef BN_LLONG
|
---|
679 | BN_ULLONG t,tt;
|
---|
680 | #else
|
---|
681 | BN_ULONG bl,bh;
|
---|
682 | #endif
|
---|
683 | BN_ULONG t1,t2;
|
---|
684 | BN_ULONG c1,c2,c3;
|
---|
685 |
|
---|
686 | c1=0;
|
---|
687 | c2=0;
|
---|
688 | c3=0;
|
---|
689 | sqr_add_c(a,0,c1,c2,c3);
|
---|
690 | r[0]=c1;
|
---|
691 | c1=0;
|
---|
692 | sqr_add_c2(a,1,0,c2,c3,c1);
|
---|
693 | r[1]=c2;
|
---|
694 | c2=0;
|
---|
695 | sqr_add_c(a,1,c3,c1,c2);
|
---|
696 | sqr_add_c2(a,2,0,c3,c1,c2);
|
---|
697 | r[2]=c3;
|
---|
698 | c3=0;
|
---|
699 | sqr_add_c2(a,3,0,c1,c2,c3);
|
---|
700 | sqr_add_c2(a,2,1,c1,c2,c3);
|
---|
701 | r[3]=c1;
|
---|
702 | c1=0;
|
---|
703 | sqr_add_c(a,2,c2,c3,c1);
|
---|
704 | sqr_add_c2(a,3,1,c2,c3,c1);
|
---|
705 | sqr_add_c2(a,4,0,c2,c3,c1);
|
---|
706 | r[4]=c2;
|
---|
707 | c2=0;
|
---|
708 | sqr_add_c2(a,5,0,c3,c1,c2);
|
---|
709 | sqr_add_c2(a,4,1,c3,c1,c2);
|
---|
710 | sqr_add_c2(a,3,2,c3,c1,c2);
|
---|
711 | r[5]=c3;
|
---|
712 | c3=0;
|
---|
713 | sqr_add_c(a,3,c1,c2,c3);
|
---|
714 | sqr_add_c2(a,4,2,c1,c2,c3);
|
---|
715 | sqr_add_c2(a,5,1,c1,c2,c3);
|
---|
716 | sqr_add_c2(a,6,0,c1,c2,c3);
|
---|
717 | r[6]=c1;
|
---|
718 | c1=0;
|
---|
719 | sqr_add_c2(a,7,0,c2,c3,c1);
|
---|
720 | sqr_add_c2(a,6,1,c2,c3,c1);
|
---|
721 | sqr_add_c2(a,5,2,c2,c3,c1);
|
---|
722 | sqr_add_c2(a,4,3,c2,c3,c1);
|
---|
723 | r[7]=c2;
|
---|
724 | c2=0;
|
---|
725 | sqr_add_c(a,4,c3,c1,c2);
|
---|
726 | sqr_add_c2(a,5,3,c3,c1,c2);
|
---|
727 | sqr_add_c2(a,6,2,c3,c1,c2);
|
---|
728 | sqr_add_c2(a,7,1,c3,c1,c2);
|
---|
729 | r[8]=c3;
|
---|
730 | c3=0;
|
---|
731 | sqr_add_c2(a,7,2,c1,c2,c3);
|
---|
732 | sqr_add_c2(a,6,3,c1,c2,c3);
|
---|
733 | sqr_add_c2(a,5,4,c1,c2,c3);
|
---|
734 | r[9]=c1;
|
---|
735 | c1=0;
|
---|
736 | sqr_add_c(a,5,c2,c3,c1);
|
---|
737 | sqr_add_c2(a,6,4,c2,c3,c1);
|
---|
738 | sqr_add_c2(a,7,3,c2,c3,c1);
|
---|
739 | r[10]=c2;
|
---|
740 | c2=0;
|
---|
741 | sqr_add_c2(a,7,4,c3,c1,c2);
|
---|
742 | sqr_add_c2(a,6,5,c3,c1,c2);
|
---|
743 | r[11]=c3;
|
---|
744 | c3=0;
|
---|
745 | sqr_add_c(a,6,c1,c2,c3);
|
---|
746 | sqr_add_c2(a,7,5,c1,c2,c3);
|
---|
747 | r[12]=c1;
|
---|
748 | c1=0;
|
---|
749 | sqr_add_c2(a,7,6,c2,c3,c1);
|
---|
750 | r[13]=c2;
|
---|
751 | c2=0;
|
---|
752 | sqr_add_c(a,7,c3,c1,c2);
|
---|
753 | r[14]=c3;
|
---|
754 | r[15]=c1;
|
---|
755 | }
|
---|
756 |
|
---|
757 | void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a)
|
---|
758 | {
|
---|
759 | #ifdef BN_LLONG
|
---|
760 | BN_ULLONG t,tt;
|
---|
761 | #else
|
---|
762 | BN_ULONG bl,bh;
|
---|
763 | #endif
|
---|
764 | BN_ULONG t1,t2;
|
---|
765 | BN_ULONG c1,c2,c3;
|
---|
766 |
|
---|
767 | c1=0;
|
---|
768 | c2=0;
|
---|
769 | c3=0;
|
---|
770 | sqr_add_c(a,0,c1,c2,c3);
|
---|
771 | r[0]=c1;
|
---|
772 | c1=0;
|
---|
773 | sqr_add_c2(a,1,0,c2,c3,c1);
|
---|
774 | r[1]=c2;
|
---|
775 | c2=0;
|
---|
776 | sqr_add_c(a,1,c3,c1,c2);
|
---|
777 | sqr_add_c2(a,2,0,c3,c1,c2);
|
---|
778 | r[2]=c3;
|
---|
779 | c3=0;
|
---|
780 | sqr_add_c2(a,3,0,c1,c2,c3);
|
---|
781 | sqr_add_c2(a,2,1,c1,c2,c3);
|
---|
782 | r[3]=c1;
|
---|
783 | c1=0;
|
---|
784 | sqr_add_c(a,2,c2,c3,c1);
|
---|
785 | sqr_add_c2(a,3,1,c2,c3,c1);
|
---|
786 | r[4]=c2;
|
---|
787 | c2=0;
|
---|
788 | sqr_add_c2(a,3,2,c3,c1,c2);
|
---|
789 | r[5]=c3;
|
---|
790 | c3=0;
|
---|
791 | sqr_add_c(a,3,c1,c2,c3);
|
---|
792 | r[6]=c1;
|
---|
793 | r[7]=c2;
|
---|
794 | }
|
---|
795 | #else /* !BN_MUL_COMBA */
|
---|
796 |
|
---|
797 | /* hmm... is it faster just to do a multiply? */
|
---|
798 | #undef bn_sqr_comba4
|
---|
799 | void bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a)
|
---|
800 | {
|
---|
801 | BN_ULONG t[8];
|
---|
802 | bn_sqr_normal(r,a,4,t);
|
---|
803 | }
|
---|
804 |
|
---|
805 | #undef bn_sqr_comba8
|
---|
806 | void bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a)
|
---|
807 | {
|
---|
808 | BN_ULONG t[16];
|
---|
809 | bn_sqr_normal(r,a,8,t);
|
---|
810 | }
|
---|
811 |
|
---|
812 | void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
|
---|
813 | {
|
---|
814 | r[4]=bn_mul_words( &(r[0]),a,4,b[0]);
|
---|
815 | r[5]=bn_mul_add_words(&(r[1]),a,4,b[1]);
|
---|
816 | r[6]=bn_mul_add_words(&(r[2]),a,4,b[2]);
|
---|
817 | r[7]=bn_mul_add_words(&(r[3]),a,4,b[3]);
|
---|
818 | }
|
---|
819 |
|
---|
820 | void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
|
---|
821 | {
|
---|
822 | r[ 8]=bn_mul_words( &(r[0]),a,8,b[0]);
|
---|
823 | r[ 9]=bn_mul_add_words(&(r[1]),a,8,b[1]);
|
---|
824 | r[10]=bn_mul_add_words(&(r[2]),a,8,b[2]);
|
---|
825 | r[11]=bn_mul_add_words(&(r[3]),a,8,b[3]);
|
---|
826 | r[12]=bn_mul_add_words(&(r[4]),a,8,b[4]);
|
---|
827 | r[13]=bn_mul_add_words(&(r[5]),a,8,b[5]);
|
---|
828 | r[14]=bn_mul_add_words(&(r[6]),a,8,b[6]);
|
---|
829 | r[15]=bn_mul_add_words(&(r[7]),a,8,b[7]);
|
---|
830 | }
|
---|
831 |
|
---|
832 | #endif /* !BN_MUL_COMBA */
|
---|