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