2 * Copyright (C) 2017 Denys Vlasenko
4 * Licensed under GPLv2, see file LICENSE in this source tree.
8 /* The file is taken almost verbatim from matrixssl-3-7-2b-open/crypto/math/.
9 * Changes are flagged with //bbox
13 * @file pstm_sqr_comba.c
14 * @version 33ef80f (HEAD, tag: MATRIXSSL-3-7-2-OPEN, tag: MATRIXSSL-3-7-2-COMM, origin/master, origin/HEAD, master)
16 * Multiprecision Squaring with Comba technique.
19 * Copyright (c) 2013-2015 INSIDE Secure Corporation
20 * Copyright (c) PeerSec Networks, 2002-2011
23 * The latest version of this code is available at http://www.matrixssl.org
25 * This software is open source; you can redistribute it and/or modify
26 * it under the terms of the GNU General Public License as published by
27 * the Free Software Foundation; either version 2 of the License, or
28 * (at your option) any later version.
30 * This General Public License does NOT permit incorporating this software
31 * into proprietary programs. If you are unable to comply with the GPL, a
32 * commercial license for this software may be purchased from INSIDE at
33 * http://www.insidesecure.com/eng/Company/Locations
35 * This program is distributed in WITHOUT ANY WARRANTY; without even the
36 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
37 * See the GNU General Public License for more details.
39 * You should have received a copy of the GNU General Public License
40 * along with this program; if not, write to the Free Software
41 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
42 * http://www.gnu.org/copyleft/gpl.html
44 /******************************************************************************/
47 //#include "../cryptoApi.h"
50 /******************************************************************************/
52 /* x86-32 optimized for 32 bit platforms. For 64 bit mode use X86_64 instead */
53 #if !defined(__GNUC__) || !defined(__i386__)
54 #error "PSTM_X86 option requires GCC and 32 bit mode x86 processor"
56 //#pragma message ("Using 32 bit x86 Assembly Optimizations")
63 #define COMBA_STORE(x) \
66 #define COMBA_STORE2(x) \
69 #define CARRY_FORWARD \
70 do { c0 = c1; c1 = c2; c2 = 0; } while (0);
74 #define SQRADD(i, j) \
76 "movl %6,%%eax \n\t" \
78 "addl %%eax,%0 \n\t" \
79 "adcl %%edx,%1 \n\t" \
81 :"=r"(c0), "=r"(c1), "=r"(c2): "0"(c0), "1"(c1), "2"(c2), "m"(i) :"%eax","%edx","%cc");
83 #define SQRADD2(i, j) \
85 "movl %6,%%eax \n\t" \
87 "addl %%eax,%0 \n\t" \
88 "adcl %%edx,%1 \n\t" \
90 "addl %%eax,%0 \n\t" \
91 "adcl %%edx,%1 \n\t" \
93 :"=r"(c0), "=r"(c1), "=r"(c2): "0"(c0), "1"(c1), "2"(c2), "m"(i), "m"(j) :"%eax","%edx","%cc");
95 #define SQRADDSC(i, j) \
97 "movl %6,%%eax \n\t" \
99 "movl %%eax,%0 \n\t" \
100 "movl %%edx,%1 \n\t" \
102 :"=r"(sc0), "=r"(sc1), "=r"(sc2): "0"(sc0), "1"(sc1), "2"(sc2), "g"(i), "g"(j) :"%eax","%edx","%cc");
104 #define SQRADDAC(i, j) \
106 "movl %6,%%eax \n\t" \
108 "addl %%eax,%0 \n\t" \
109 "adcl %%edx,%1 \n\t" \
111 :"=r"(sc0), "=r"(sc1), "=r"(sc2): "0"(sc0), "1"(sc1), "2"(sc2), "g"(i), "g"(j) :"%eax","%edx","%cc");
121 :"=r"(c0), "=r"(c1), "=r"(c2) : "0"(c0), "1"(c1), "2"(c2), "r"(sc0), "r"(sc1), "r"(sc2) : "%cc");
123 /******************************************************************************/
124 #elif defined(PSTM_X86_64)
125 /* x86-64 optimized */
126 #if !defined(__GNUC__) || !defined(__x86_64__) || !defined(PSTM_64BIT)
127 #error "PSTM_X86_64 option requires PSTM_64BIT, GCC and 64 bit mode x86 processor"
129 //#pragma message ("Using 64 bit x86_64 Assembly Optimizations")
133 #define CLEAR_CARRY \
136 #define COMBA_STORE(x) \
139 #define COMBA_STORE2(x) \
142 #define CARRY_FORWARD \
143 do { c0 = c1; c1 = c2; c2 = 0; } while (0);
147 #define SQRADD(i, j) \
149 "movq %6,%%rax \n\t" \
151 "addq %%rax,%0 \n\t" \
152 "adcq %%rdx,%1 \n\t" \
154 :"=r"(c0), "=r"(c1), "=r"(c2): "0"(c0), "1"(c1), "2"(c2), "g"(i) :"%rax","%rdx","cc");
156 #define SQRADD2(i, j) \
158 "movq %6,%%rax \n\t" \
160 "addq %%rax,%0 \n\t" \
161 "adcq %%rdx,%1 \n\t" \
163 "addq %%rax,%0 \n\t" \
164 "adcq %%rdx,%1 \n\t" \
166 :"=r"(c0), "=r"(c1), "=r"(c2): "0"(c0), "1"(c1), "2"(c2), "g"(i), "g"(j) :"%rax","%rdx","cc");
168 #define SQRADDSC(i, j) \
170 "movq %6,%%rax \n\t" \
172 "movq %%rax,%0 \n\t" \
173 "movq %%rdx,%1 \n\t" \
175 :"=r"(sc0), "=r"(sc1), "=r"(sc2): "0"(sc0), "1"(sc1), "2"(sc2), "g"(i), "g"(j) :"%rax","%rdx","cc");
177 #define SQRADDAC(i, j) \
179 "movq %6,%%rax \n\t" \
181 "addq %%rax,%0 \n\t" \
182 "adcq %%rdx,%1 \n\t" \
184 :"=r"(sc0), "=r"(sc1), "=r"(sc2): "0"(sc0), "1"(sc1), "2"(sc2), "g"(i), "g"(j) :"%rax","%rdx","cc");
194 :"=r"(c0), "=r"(c1), "=r"(c2) : "0"(c0), "1"(c1), "2"(c2), "r"(sc0), "r"(sc1), "r"(sc2) : "cc");
196 /******************************************************************************/
197 #elif defined(PSTM_ARM)
199 //#pragma message ("Using 32 bit ARM Assembly Optimizations")
203 #define CLEAR_CARRY \
206 #define COMBA_STORE(x) \
209 #define COMBA_STORE2(x) \
212 #define CARRY_FORWARD \
213 do { c0 = c1; c1 = c2; c2 = 0; } while (0);
217 /* multiplies point i and j, updates carry "c1" and digit c2 */
218 #define SQRADD(i, j) \
220 " UMULL r0,r1,%6,%6 \n\t" \
221 " ADDS %0,%0,r0 \n\t" \
222 " ADCS %1,%1,r1 \n\t" \
223 " ADC %2,%2,#0 \n\t" \
224 :"=r"(c0), "=r"(c1), "=r"(c2) : "0"(c0), "1"(c1), "2"(c2), "r"(i) : "r0", "r1", "%cc");
226 /* for squaring some of the terms are doubled... */
227 #define SQRADD2(i, j) \
229 " UMULL r0,r1,%6,%7 \n\t" \
230 " ADDS %0,%0,r0 \n\t" \
231 " ADCS %1,%1,r1 \n\t" \
232 " ADC %2,%2,#0 \n\t" \
233 " ADDS %0,%0,r0 \n\t" \
234 " ADCS %1,%1,r1 \n\t" \
235 " ADC %2,%2,#0 \n\t" \
236 :"=r"(c0), "=r"(c1), "=r"(c2) : "0"(c0), "1"(c1), "2"(c2), "r"(i), "r"(j) : "r0", "r1", "%cc");
238 #define SQRADDSC(i, j) \
240 " UMULL %0,%1,%6,%7 \n\t" \
241 " SUB %2,%2,%2 \n\t" \
242 :"=r"(sc0), "=r"(sc1), "=r"(sc2) : "0"(sc0), "1"(sc1), "2"(sc2), "r"(i), "r"(j) : "%cc");
244 #define SQRADDAC(i, j) \
246 " UMULL r0,r1,%6,%7 \n\t" \
247 " ADDS %0,%0,r0 \n\t" \
248 " ADCS %1,%1,r1 \n\t" \
249 " ADC %2,%2,#0 \n\t" \
250 :"=r"(sc0), "=r"(sc1), "=r"(sc2) : "0"(sc0), "1"(sc1), "2"(sc2), "r"(i), "r"(j) : "r0", "r1", "%cc");
254 " ADDS %0,%0,%3 \n\t" \
255 " ADCS %1,%1,%4 \n\t" \
256 " ADC %2,%2,%5 \n\t" \
257 " ADDS %0,%0,%3 \n\t" \
258 " ADCS %1,%1,%4 \n\t" \
259 " ADC %2,%2,%5 \n\t" \
260 :"=r"(c0), "=r"(c1), "=r"(c2) : "r"(sc0), "r"(sc1), "r"(sc2), "0"(c0), "1"(c1), "2"(c2) : "%cc");
262 /******************************************************************************/
263 #elif defined(PSTM_MIPS)
265 //#pragma message ("Using 32 bit MIPS Assembly Optimizations")
269 #define CLEAR_CARRY \
272 #define COMBA_STORE(x) \
275 #define COMBA_STORE2(x) \
278 #define CARRY_FORWARD \
279 do { c0 = c1; c1 = c2; c2 = 0; } while (0);
283 /* multiplies point i and j, updates carry "c1" and digit c2 */
284 #define SQRADD(i, j) \
286 " multu %6,%6 \n\t" \
289 " addu %0,%0,$12 \n\t" \
290 " sltu $12,%0,$12 \n\t" \
291 " addu %1,%1,$13 \n\t" \
292 " sltu $13,%1,$13 \n\t" \
293 " addu %1,%1,$12 \n\t" \
294 " sltu $12,%1,$12 \n\t" \
295 " addu %2,%2,$13 \n\t" \
296 " addu %2,%2,$12 \n\t" \
297 :"=r"(c0), "=r"(c1), "=r"(c2):"0"(c0), "1"(c1), "2"(c2), "r"(i):"$12","$13");
299 /* for squaring some of the terms are doubled... */
300 #define SQRADD2(i, j) \
302 " multu %6,%7 \n\t" \
306 " addu %0,%0,$12 \n\t" \
307 " sltu $14,%0,$12 \n\t" \
308 " addu %1,%1,$13 \n\t" \
309 " sltu $15,%1,$13 \n\t" \
310 " addu %1,%1,$14 \n\t" \
311 " sltu $14,%1,$14 \n\t" \
312 " addu %2,%2,$15 \n\t" \
313 " addu %2,%2,$14 \n\t" \
315 " addu %0,%0,$12 \n\t" \
316 " sltu $14,%0,$12 \n\t" \
317 " addu %1,%1,$13 \n\t" \
318 " sltu $15,%1,$13 \n\t" \
319 " addu %1,%1,$14 \n\t" \
320 " sltu $14,%1,$14 \n\t" \
321 " addu %2,%2,$15 \n\t" \
322 " addu %2,%2,$14 \n\t" \
323 :"=r"(c0), "=r"(c1), "=r"(c2):"0"(c0), "1"(c1), "2"(c2), "r"(i), "r"(j):"$12", "$13", "$14", "$15");
325 #define SQRADDSC(i, j) \
327 " multu %6,%7 \n\t" \
330 " xor %2,%2,%2 \n\t" \
331 :"=r"(sc0), "=r"(sc1), "=r"(sc2):"0"(sc0), "1"(sc1), "2"(sc2), "r"(i),"r"(j) : "%cc");
333 #define SQRADDAC(i, j) \
335 " multu %6,%7 \n\t" \
338 " addu %0,%0,$12 \n\t" \
339 " sltu $12,%0,$12 \n\t" \
340 " addu %1,%1,$13 \n\t" \
341 " sltu $13,%1,$13 \n\t" \
342 " addu %1,%1,$12 \n\t" \
343 " sltu $12,%1,$12 \n\t" \
344 " addu %2,%2,$13 \n\t" \
345 " addu %2,%2,$12 \n\t" \
346 :"=r"(sc0), "=r"(sc1), "=r"(sc2):"0"(sc0), "1"(sc1), "2"(sc2), "r"(i), "r"(j):"$12", "$13", "$14");
350 " addu %0,%0,%3 \n\t" \
351 " sltu $10,%0,%3 \n\t" \
352 " addu %1,%1,$10 \n\t" \
353 " sltu $10,%1,$10 \n\t" \
354 " addu %1,%1,%4 \n\t" \
355 " sltu $11,%1,%4 \n\t" \
356 " addu %2,%2,$10 \n\t" \
357 " addu %2,%2,$11 \n\t" \
358 " addu %2,%2,%5 \n\t" \
360 " addu %0,%0,%3 \n\t" \
361 " sltu $10,%0,%3 \n\t" \
362 " addu %1,%1,$10 \n\t" \
363 " sltu $10,%1,$10 \n\t" \
364 " addu %1,%1,%4 \n\t" \
365 " sltu $11,%1,%4 \n\t" \
366 " addu %2,%2,$10 \n\t" \
367 " addu %2,%2,$11 \n\t" \
368 " addu %2,%2,%5 \n\t" \
369 :"=r"(c0), "=r"(c1), "=r"(c2) : "r"(sc0), "r"(sc1), "r"(sc2), "0"(c0), "1"(c1), "2"(c2) : "$10", "$11");
372 /******************************************************************************/
374 /* ISO C portable code */
378 #define CLEAR_CARRY \
381 #define COMBA_STORE(x) \
384 #define COMBA_STORE2(x) \
387 #define CARRY_FORWARD \
388 do { c0 = c1; c1 = c2; c2 = 0; } while (0);
392 /* multiplies point i and j, updates carry "c1" and digit c2 */
393 #define SQRADD(i, j) \
395 t = c0 + ((pstm_word)i) * ((pstm_word)j); c0 = (pstm_digit)t; \
396 t = c1 + (t >> DIGIT_BIT); \
397 c1 = (pstm_digit)t; c2 += (pstm_digit)(t >> DIGIT_BIT); \
401 /* for squaring some of the terms are doubled... */
402 #define SQRADD2(i, j) \
404 t = ((pstm_word)i) * ((pstm_word)j); \
405 tt = (pstm_word)c0 + t; c0 = (pstm_digit)tt; \
406 tt = (pstm_word)c1 + (tt >> DIGIT_BIT); \
407 c1 = (pstm_digit)tt; c2 += (pstm_digit)(tt >> DIGIT_BIT); \
408 tt = (pstm_word)c0 + t; c0 = (pstm_digit)tt; \
409 tt = (pstm_word)c1 + (tt >> DIGIT_BIT); \
410 c1 = (pstm_digit)tt; c2 += (pstm_digit)(tt >> DIGIT_BIT); \
413 #define SQRADDSC(i, j) \
415 t = ((pstm_word)i) * ((pstm_word)j); \
416 sc0 = (pstm_digit)t; sc1 = (pstm_digit)(t >> DIGIT_BIT); sc2 = 0; \
419 #define SQRADDAC(i, j) \
421 t = ((pstm_word)sc0) + ((pstm_word)i) * ((pstm_word)j); \
422 sc0 = (pstm_digit)t; \
423 t = ((pstm_word)sc1) + (t >> DIGIT_BIT); sc1 = (pstm_digit)t; \
424 sc2 += (pstm_digit)(t >> DIGIT_BIT); \
429 t = ((pstm_word)sc0) + ((pstm_word)sc0) + ((pstm_word)c0); \
430 c0 = (pstm_digit)t; \
431 t = ((pstm_word)sc1) + ((pstm_word)sc1) + c1 + (t >> DIGIT_BIT); \
432 c1 = (pstm_digit)t; \
433 c2 = c2 + sc2 + sc2 + (pstm_digit)(t >> DIGIT_BIT); \
438 /******************************************************************************/
440 Non-unrolled comba squarer
443 #define pstm_sqr_comba_gen(pool, A, B, paD, paDlen) \
444 pstm_sqr_comba_gen( A, B, paD, paDlen)
445 static int32 pstm_sqr_comba_gen(psPool_t *pool, pstm_int *A, pstm_int *B,
446 pstm_digit *paD, uint32 paDlen)
450 pstm_digit c0, c1, c2, *dst;
456 /* get size of output and trim */
457 pa = A->used + A->used;
459 /* number of output digits to produce */
463 If b is not large enough grow it and continue
466 if (pstm_grow(B, pa) != PSTM_OKAY) {
471 if (paDlen < (sizeof(pstm_digit) * pa)) {
472 paDfail = 1; /* have a paD, but it's not big enough */
473 dst = xzalloc(sizeof(pstm_digit) * pa);//bbox
476 memset(dst, 0x0, paDlen);
479 dst = xzalloc(sizeof(pstm_digit) * pa);//bbox
482 for (ix = 0; ix < pa; ix++) {
484 pstm_digit *tmpy, *tmpx;
486 /* get offsets into the two bignums */
487 ty = min(A->used-1, ix);
490 /* setup temp aliases */
495 This is the number of times the loop will iterate,
496 while (tx++ < a->used && ty-- >= 0) { ... }
498 iy = min(A->used-tx, ty+1);
501 now for squaring tx can never equal ty. We halve the distance since
502 they approach at a rate of 2x and we have to round because odd cases
505 iy = min(iy, (ty-tx+1)>>1);
507 /* forward carries */
511 for (iz = 0; iz < iy; iz++) {
512 SQRADD2(*tmpx++, *tmpy--);
515 /* even columns have the square term in them */
517 SQRADD(A->dp[ix>>1], A->dp[ix>>1]);
521 COMBA_STORE(dst[ix]);
533 for (ix = 0; ix < pa; ix++) {
536 /* clear unused digits (that existed in the old copy of c) */
537 for (; ix < iz; ix++) {
543 if ((paD == NULL) || paDfail == 1) {
549 /******************************************************************************/
551 Unrolled Comba loop for 1024 bit keys
553 #ifdef USE_1024_KEY_SPEED_OPTIMIZATIONS
554 static int32 pstm_sqr_comba16(pstm_int *A, pstm_int *B)
556 pstm_digit *a, b[32], c0, c1, c2, sc0, sc1, sc2;
562 if (pstm_grow(B, 32) != PSTM_OKAY) {
585 SQRADD2(a[0], a[2]); SQRADD(a[1], a[1]);
590 SQRADD2(a[0], a[3]); SQRADD2(a[1], a[2]);
595 SQRADD2(a[0], a[4]); SQRADD2(a[1], a[3]); SQRADD(a[2], a[2]);
600 SQRADDSC(a[0], a[5]); SQRADDAC(a[1], a[4]); SQRADDAC(a[2], a[3]); SQRADDDB;
605 SQRADDSC(a[0], a[6]); SQRADDAC(a[1], a[5]); SQRADDAC(a[2], a[4]); SQRADDDB; SQRADD(a[3], a[3]);
610 SQRADDSC(a[0], a[7]); SQRADDAC(a[1], a[6]); SQRADDAC(a[2], a[5]); SQRADDAC(a[3], a[4]); SQRADDDB;
615 SQRADDSC(a[0], a[8]); SQRADDAC(a[1], a[7]); SQRADDAC(a[2], a[6]); SQRADDAC(a[3], a[5]); SQRADDDB; SQRADD(a[4], a[4]);
620 SQRADDSC(a[0], a[9]); SQRADDAC(a[1], a[8]); SQRADDAC(a[2], a[7]); SQRADDAC(a[3], a[6]); SQRADDAC(a[4], a[5]); SQRADDDB;
625 SQRADDSC(a[0], a[10]); SQRADDAC(a[1], a[9]); SQRADDAC(a[2], a[8]); SQRADDAC(a[3], a[7]); SQRADDAC(a[4], a[6]); SQRADDDB; SQRADD(a[5], a[5]);
630 SQRADDSC(a[0], a[11]); SQRADDAC(a[1], a[10]); SQRADDAC(a[2], a[9]); SQRADDAC(a[3], a[8]); SQRADDAC(a[4], a[7]); SQRADDAC(a[5], a[6]); SQRADDDB;
635 SQRADDSC(a[0], a[12]); SQRADDAC(a[1], a[11]); SQRADDAC(a[2], a[10]); SQRADDAC(a[3], a[9]); SQRADDAC(a[4], a[8]); SQRADDAC(a[5], a[7]); SQRADDDB; SQRADD(a[6], a[6]);
640 SQRADDSC(a[0], a[13]); SQRADDAC(a[1], a[12]); SQRADDAC(a[2], a[11]); SQRADDAC(a[3], a[10]); SQRADDAC(a[4], a[9]); SQRADDAC(a[5], a[8]); SQRADDAC(a[6], a[7]); SQRADDDB;
645 SQRADDSC(a[0], a[14]); SQRADDAC(a[1], a[13]); SQRADDAC(a[2], a[12]); SQRADDAC(a[3], a[11]); SQRADDAC(a[4], a[10]); SQRADDAC(a[5], a[9]); SQRADDAC(a[6], a[8]); SQRADDDB; SQRADD(a[7], a[7]);
650 SQRADDSC(a[0], a[15]); SQRADDAC(a[1], a[14]); SQRADDAC(a[2], a[13]); SQRADDAC(a[3], a[12]); SQRADDAC(a[4], a[11]); SQRADDAC(a[5], a[10]); SQRADDAC(a[6], a[9]); SQRADDAC(a[7], a[8]); SQRADDDB;
655 SQRADDSC(a[1], a[15]); SQRADDAC(a[2], a[14]); SQRADDAC(a[3], a[13]); SQRADDAC(a[4], a[12]); SQRADDAC(a[5], a[11]); SQRADDAC(a[6], a[10]); SQRADDAC(a[7], a[9]); SQRADDDB; SQRADD(a[8], a[8]);
660 SQRADDSC(a[2], a[15]); SQRADDAC(a[3], a[14]); SQRADDAC(a[4], a[13]); SQRADDAC(a[5], a[12]); SQRADDAC(a[6], a[11]); SQRADDAC(a[7], a[10]); SQRADDAC(a[8], a[9]); SQRADDDB;
665 SQRADDSC(a[3], a[15]); SQRADDAC(a[4], a[14]); SQRADDAC(a[5], a[13]); SQRADDAC(a[6], a[12]); SQRADDAC(a[7], a[11]); SQRADDAC(a[8], a[10]); SQRADDDB; SQRADD(a[9], a[9]);
670 SQRADDSC(a[4], a[15]); SQRADDAC(a[5], a[14]); SQRADDAC(a[6], a[13]); SQRADDAC(a[7], a[12]); SQRADDAC(a[8], a[11]); SQRADDAC(a[9], a[10]); SQRADDDB;
675 SQRADDSC(a[5], a[15]); SQRADDAC(a[6], a[14]); SQRADDAC(a[7], a[13]); SQRADDAC(a[8], a[12]); SQRADDAC(a[9], a[11]); SQRADDDB; SQRADD(a[10], a[10]);
680 SQRADDSC(a[6], a[15]); SQRADDAC(a[7], a[14]); SQRADDAC(a[8], a[13]); SQRADDAC(a[9], a[12]); SQRADDAC(a[10], a[11]); SQRADDDB;
685 SQRADDSC(a[7], a[15]); SQRADDAC(a[8], a[14]); SQRADDAC(a[9], a[13]); SQRADDAC(a[10], a[12]); SQRADDDB; SQRADD(a[11], a[11]);
690 SQRADDSC(a[8], a[15]); SQRADDAC(a[9], a[14]); SQRADDAC(a[10], a[13]); SQRADDAC(a[11], a[12]); SQRADDDB;
695 SQRADDSC(a[9], a[15]); SQRADDAC(a[10], a[14]); SQRADDAC(a[11], a[13]); SQRADDDB; SQRADD(a[12], a[12]);
700 SQRADDSC(a[10], a[15]); SQRADDAC(a[11], a[14]); SQRADDAC(a[12], a[13]); SQRADDDB;
705 SQRADD2(a[11], a[15]); SQRADD2(a[12], a[14]); SQRADD(a[13], a[13]);
710 SQRADD2(a[12], a[15]); SQRADD2(a[13], a[14]);
715 SQRADD2(a[13], a[15]); SQRADD(a[14], a[14]);
720 SQRADD2(a[14], a[15]);
725 SQRADD(a[15], a[15]);
732 memcpy(B->dp, b, 32 * sizeof(pstm_digit));
736 #endif /* USE_1024_KEY_SPEED_OPTIMIZATIONS */
739 #ifdef USE_2048_KEY_SPEED_OPTIMIZATIONS
740 static int32 pstm_sqr_comba32(pstm_int *A, pstm_int *B)
742 pstm_digit *a, b[64], c0, c1, c2, sc0, sc1, sc2;
748 if (pstm_grow(B, 64) != PSTM_OKAY) {
770 SQRADD2(a[0], a[2]); SQRADD(a[1], a[1]);
775 SQRADD2(a[0], a[3]); SQRADD2(a[1], a[2]);
780 SQRADD2(a[0], a[4]); SQRADD2(a[1], a[3]); SQRADD(a[2], a[2]);
785 SQRADDSC(a[0], a[5]); SQRADDAC(a[1], a[4]); SQRADDAC(a[2], a[3]); SQRADDDB;
790 SQRADDSC(a[0], a[6]); SQRADDAC(a[1], a[5]); SQRADDAC(a[2], a[4]); SQRADDDB; SQRADD(a[3], a[3]);
795 SQRADDSC(a[0], a[7]); SQRADDAC(a[1], a[6]); SQRADDAC(a[2], a[5]); SQRADDAC(a[3], a[4]); SQRADDDB;
800 SQRADDSC(a[0], a[8]); SQRADDAC(a[1], a[7]); SQRADDAC(a[2], a[6]); SQRADDAC(a[3], a[5]); SQRADDDB; SQRADD(a[4], a[4]);
805 SQRADDSC(a[0], a[9]); SQRADDAC(a[1], a[8]); SQRADDAC(a[2], a[7]); SQRADDAC(a[3], a[6]); SQRADDAC(a[4], a[5]); SQRADDDB;
810 SQRADDSC(a[0], a[10]); SQRADDAC(a[1], a[9]); SQRADDAC(a[2], a[8]); SQRADDAC(a[3], a[7]); SQRADDAC(a[4], a[6]); SQRADDDB; SQRADD(a[5], a[5]);
815 SQRADDSC(a[0], a[11]); SQRADDAC(a[1], a[10]); SQRADDAC(a[2], a[9]); SQRADDAC(a[3], a[8]); SQRADDAC(a[4], a[7]); SQRADDAC(a[5], a[6]); SQRADDDB;
820 SQRADDSC(a[0], a[12]); SQRADDAC(a[1], a[11]); SQRADDAC(a[2], a[10]); SQRADDAC(a[3], a[9]); SQRADDAC(a[4], a[8]); SQRADDAC(a[5], a[7]); SQRADDDB; SQRADD(a[6], a[6]);
825 SQRADDSC(a[0], a[13]); SQRADDAC(a[1], a[12]); SQRADDAC(a[2], a[11]); SQRADDAC(a[3], a[10]); SQRADDAC(a[4], a[9]); SQRADDAC(a[5], a[8]); SQRADDAC(a[6], a[7]); SQRADDDB;
830 SQRADDSC(a[0], a[14]); SQRADDAC(a[1], a[13]); SQRADDAC(a[2], a[12]); SQRADDAC(a[3], a[11]); SQRADDAC(a[4], a[10]); SQRADDAC(a[5], a[9]); SQRADDAC(a[6], a[8]); SQRADDDB; SQRADD(a[7], a[7]);
835 SQRADDSC(a[0], a[15]); SQRADDAC(a[1], a[14]); SQRADDAC(a[2], a[13]); SQRADDAC(a[3], a[12]); SQRADDAC(a[4], a[11]); SQRADDAC(a[5], a[10]); SQRADDAC(a[6], a[9]); SQRADDAC(a[7], a[8]); SQRADDDB;
840 SQRADDSC(a[0], a[16]); SQRADDAC(a[1], a[15]); SQRADDAC(a[2], a[14]); SQRADDAC(a[3], a[13]); SQRADDAC(a[4], a[12]); SQRADDAC(a[5], a[11]); SQRADDAC(a[6], a[10]); SQRADDAC(a[7], a[9]); SQRADDDB; SQRADD(a[8], a[8]);
845 SQRADDSC(a[0], a[17]); SQRADDAC(a[1], a[16]); SQRADDAC(a[2], a[15]); SQRADDAC(a[3], a[14]); SQRADDAC(a[4], a[13]); SQRADDAC(a[5], a[12]); SQRADDAC(a[6], a[11]); SQRADDAC(a[7], a[10]); SQRADDAC(a[8], a[9]); SQRADDDB;
850 SQRADDSC(a[0], a[18]); SQRADDAC(a[1], a[17]); SQRADDAC(a[2], a[16]); SQRADDAC(a[3], a[15]); SQRADDAC(a[4], a[14]); SQRADDAC(a[5], a[13]); SQRADDAC(a[6], a[12]); SQRADDAC(a[7], a[11]); SQRADDAC(a[8], a[10]); SQRADDDB; SQRADD(a[9], a[9]);
855 SQRADDSC(a[0], a[19]); SQRADDAC(a[1], a[18]); SQRADDAC(a[2], a[17]); SQRADDAC(a[3], a[16]); SQRADDAC(a[4], a[15]); SQRADDAC(a[5], a[14]); SQRADDAC(a[6], a[13]); SQRADDAC(a[7], a[12]); SQRADDAC(a[8], a[11]); SQRADDAC(a[9], a[10]); SQRADDDB;
860 SQRADDSC(a[0], a[20]); SQRADDAC(a[1], a[19]); SQRADDAC(a[2], a[18]); SQRADDAC(a[3], a[17]); SQRADDAC(a[4], a[16]); SQRADDAC(a[5], a[15]); SQRADDAC(a[6], a[14]); SQRADDAC(a[7], a[13]); SQRADDAC(a[8], a[12]); SQRADDAC(a[9], a[11]); SQRADDDB; SQRADD(a[10], a[10]);
865 SQRADDSC(a[0], a[21]); SQRADDAC(a[1], a[20]); SQRADDAC(a[2], a[19]); SQRADDAC(a[3], a[18]); SQRADDAC(a[4], a[17]); SQRADDAC(a[5], a[16]); SQRADDAC(a[6], a[15]); SQRADDAC(a[7], a[14]); SQRADDAC(a[8], a[13]); SQRADDAC(a[9], a[12]); SQRADDAC(a[10], a[11]); SQRADDDB;
870 SQRADDSC(a[0], a[22]); SQRADDAC(a[1], a[21]); SQRADDAC(a[2], a[20]); SQRADDAC(a[3], a[19]); SQRADDAC(a[4], a[18]); SQRADDAC(a[5], a[17]); SQRADDAC(a[6], a[16]); SQRADDAC(a[7], a[15]); SQRADDAC(a[8], a[14]); SQRADDAC(a[9], a[13]); SQRADDAC(a[10], a[12]); SQRADDDB; SQRADD(a[11], a[11]);
875 SQRADDSC(a[0], a[23]); SQRADDAC(a[1], a[22]); SQRADDAC(a[2], a[21]); SQRADDAC(a[3], a[20]); SQRADDAC(a[4], a[19]); SQRADDAC(a[5], a[18]); SQRADDAC(a[6], a[17]); SQRADDAC(a[7], a[16]); SQRADDAC(a[8], a[15]); SQRADDAC(a[9], a[14]); SQRADDAC(a[10], a[13]); SQRADDAC(a[11], a[12]); SQRADDDB;
880 SQRADDSC(a[0], a[24]); SQRADDAC(a[1], a[23]); SQRADDAC(a[2], a[22]); SQRADDAC(a[3], a[21]); SQRADDAC(a[4], a[20]); SQRADDAC(a[5], a[19]); SQRADDAC(a[6], a[18]); SQRADDAC(a[7], a[17]); SQRADDAC(a[8], a[16]); SQRADDAC(a[9], a[15]); SQRADDAC(a[10], a[14]); SQRADDAC(a[11], a[13]); SQRADDDB; SQRADD(a[12], a[12]);
885 SQRADDSC(a[0], a[25]); SQRADDAC(a[1], a[24]); SQRADDAC(a[2], a[23]); SQRADDAC(a[3], a[22]); SQRADDAC(a[4], a[21]); SQRADDAC(a[5], a[20]); SQRADDAC(a[6], a[19]); SQRADDAC(a[7], a[18]); SQRADDAC(a[8], a[17]); SQRADDAC(a[9], a[16]); SQRADDAC(a[10], a[15]); SQRADDAC(a[11], a[14]); SQRADDAC(a[12], a[13]); SQRADDDB;
890 SQRADDSC(a[0], a[26]); SQRADDAC(a[1], a[25]); SQRADDAC(a[2], a[24]); SQRADDAC(a[3], a[23]); SQRADDAC(a[4], a[22]); SQRADDAC(a[5], a[21]); SQRADDAC(a[6], a[20]); SQRADDAC(a[7], a[19]); SQRADDAC(a[8], a[18]); SQRADDAC(a[9], a[17]); SQRADDAC(a[10], a[16]); SQRADDAC(a[11], a[15]); SQRADDAC(a[12], a[14]); SQRADDDB; SQRADD(a[13], a[13]);
895 SQRADDSC(a[0], a[27]); SQRADDAC(a[1], a[26]); SQRADDAC(a[2], a[25]); SQRADDAC(a[3], a[24]); SQRADDAC(a[4], a[23]); SQRADDAC(a[5], a[22]); SQRADDAC(a[6], a[21]); SQRADDAC(a[7], a[20]); SQRADDAC(a[8], a[19]); SQRADDAC(a[9], a[18]); SQRADDAC(a[10], a[17]); SQRADDAC(a[11], a[16]); SQRADDAC(a[12], a[15]); SQRADDAC(a[13], a[14]); SQRADDDB;
900 SQRADDSC(a[0], a[28]); SQRADDAC(a[1], a[27]); SQRADDAC(a[2], a[26]); SQRADDAC(a[3], a[25]); SQRADDAC(a[4], a[24]); SQRADDAC(a[5], a[23]); SQRADDAC(a[6], a[22]); SQRADDAC(a[7], a[21]); SQRADDAC(a[8], a[20]); SQRADDAC(a[9], a[19]); SQRADDAC(a[10], a[18]); SQRADDAC(a[11], a[17]); SQRADDAC(a[12], a[16]); SQRADDAC(a[13], a[15]); SQRADDDB; SQRADD(a[14], a[14]);
905 SQRADDSC(a[0], a[29]); SQRADDAC(a[1], a[28]); SQRADDAC(a[2], a[27]); SQRADDAC(a[3], a[26]); SQRADDAC(a[4], a[25]); SQRADDAC(a[5], a[24]); SQRADDAC(a[6], a[23]); SQRADDAC(a[7], a[22]); SQRADDAC(a[8], a[21]); SQRADDAC(a[9], a[20]); SQRADDAC(a[10], a[19]); SQRADDAC(a[11], a[18]); SQRADDAC(a[12], a[17]); SQRADDAC(a[13], a[16]); SQRADDAC(a[14], a[15]); SQRADDDB;
910 SQRADDSC(a[0], a[30]); SQRADDAC(a[1], a[29]); SQRADDAC(a[2], a[28]); SQRADDAC(a[3], a[27]); SQRADDAC(a[4], a[26]); SQRADDAC(a[5], a[25]); SQRADDAC(a[6], a[24]); SQRADDAC(a[7], a[23]); SQRADDAC(a[8], a[22]); SQRADDAC(a[9], a[21]); SQRADDAC(a[10], a[20]); SQRADDAC(a[11], a[19]); SQRADDAC(a[12], a[18]); SQRADDAC(a[13], a[17]); SQRADDAC(a[14], a[16]); SQRADDDB; SQRADD(a[15], a[15]);
915 SQRADDSC(a[0], a[31]); SQRADDAC(a[1], a[30]); SQRADDAC(a[2], a[29]); SQRADDAC(a[3], a[28]); SQRADDAC(a[4], a[27]); SQRADDAC(a[5], a[26]); SQRADDAC(a[6], a[25]); SQRADDAC(a[7], a[24]); SQRADDAC(a[8], a[23]); SQRADDAC(a[9], a[22]); SQRADDAC(a[10], a[21]); SQRADDAC(a[11], a[20]); SQRADDAC(a[12], a[19]); SQRADDAC(a[13], a[18]); SQRADDAC(a[14], a[17]); SQRADDAC(a[15], a[16]); SQRADDDB;
920 SQRADDSC(a[1], a[31]); SQRADDAC(a[2], a[30]); SQRADDAC(a[3], a[29]); SQRADDAC(a[4], a[28]); SQRADDAC(a[5], a[27]); SQRADDAC(a[6], a[26]); SQRADDAC(a[7], a[25]); SQRADDAC(a[8], a[24]); SQRADDAC(a[9], a[23]); SQRADDAC(a[10], a[22]); SQRADDAC(a[11], a[21]); SQRADDAC(a[12], a[20]); SQRADDAC(a[13], a[19]); SQRADDAC(a[14], a[18]); SQRADDAC(a[15], a[17]); SQRADDDB; SQRADD(a[16], a[16]);
925 SQRADDSC(a[2], a[31]); SQRADDAC(a[3], a[30]); SQRADDAC(a[4], a[29]); SQRADDAC(a[5], a[28]); SQRADDAC(a[6], a[27]); SQRADDAC(a[7], a[26]); SQRADDAC(a[8], a[25]); SQRADDAC(a[9], a[24]); SQRADDAC(a[10], a[23]); SQRADDAC(a[11], a[22]); SQRADDAC(a[12], a[21]); SQRADDAC(a[13], a[20]); SQRADDAC(a[14], a[19]); SQRADDAC(a[15], a[18]); SQRADDAC(a[16], a[17]); SQRADDDB;
930 SQRADDSC(a[3], a[31]); SQRADDAC(a[4], a[30]); SQRADDAC(a[5], a[29]); SQRADDAC(a[6], a[28]); SQRADDAC(a[7], a[27]); SQRADDAC(a[8], a[26]); SQRADDAC(a[9], a[25]); SQRADDAC(a[10], a[24]); SQRADDAC(a[11], a[23]); SQRADDAC(a[12], a[22]); SQRADDAC(a[13], a[21]); SQRADDAC(a[14], a[20]); SQRADDAC(a[15], a[19]); SQRADDAC(a[16], a[18]); SQRADDDB; SQRADD(a[17], a[17]);
935 SQRADDSC(a[4], a[31]); SQRADDAC(a[5], a[30]); SQRADDAC(a[6], a[29]); SQRADDAC(a[7], a[28]); SQRADDAC(a[8], a[27]); SQRADDAC(a[9], a[26]); SQRADDAC(a[10], a[25]); SQRADDAC(a[11], a[24]); SQRADDAC(a[12], a[23]); SQRADDAC(a[13], a[22]); SQRADDAC(a[14], a[21]); SQRADDAC(a[15], a[20]); SQRADDAC(a[16], a[19]); SQRADDAC(a[17], a[18]); SQRADDDB;
940 SQRADDSC(a[5], a[31]); SQRADDAC(a[6], a[30]); SQRADDAC(a[7], a[29]); SQRADDAC(a[8], a[28]); SQRADDAC(a[9], a[27]); SQRADDAC(a[10], a[26]); SQRADDAC(a[11], a[25]); SQRADDAC(a[12], a[24]); SQRADDAC(a[13], a[23]); SQRADDAC(a[14], a[22]); SQRADDAC(a[15], a[21]); SQRADDAC(a[16], a[20]); SQRADDAC(a[17], a[19]); SQRADDDB; SQRADD(a[18], a[18]);
945 SQRADDSC(a[6], a[31]); SQRADDAC(a[7], a[30]); SQRADDAC(a[8], a[29]); SQRADDAC(a[9], a[28]); SQRADDAC(a[10], a[27]); SQRADDAC(a[11], a[26]); SQRADDAC(a[12], a[25]); SQRADDAC(a[13], a[24]); SQRADDAC(a[14], a[23]); SQRADDAC(a[15], a[22]); SQRADDAC(a[16], a[21]); SQRADDAC(a[17], a[20]); SQRADDAC(a[18], a[19]); SQRADDDB;
950 SQRADDSC(a[7], a[31]); SQRADDAC(a[8], a[30]); SQRADDAC(a[9], a[29]); SQRADDAC(a[10], a[28]); SQRADDAC(a[11], a[27]); SQRADDAC(a[12], a[26]); SQRADDAC(a[13], a[25]); SQRADDAC(a[14], a[24]); SQRADDAC(a[15], a[23]); SQRADDAC(a[16], a[22]); SQRADDAC(a[17], a[21]); SQRADDAC(a[18], a[20]); SQRADDDB; SQRADD(a[19], a[19]);
955 SQRADDSC(a[8], a[31]); SQRADDAC(a[9], a[30]); SQRADDAC(a[10], a[29]); SQRADDAC(a[11], a[28]); SQRADDAC(a[12], a[27]); SQRADDAC(a[13], a[26]); SQRADDAC(a[14], a[25]); SQRADDAC(a[15], a[24]); SQRADDAC(a[16], a[23]); SQRADDAC(a[17], a[22]); SQRADDAC(a[18], a[21]); SQRADDAC(a[19], a[20]); SQRADDDB;
960 SQRADDSC(a[9], a[31]); SQRADDAC(a[10], a[30]); SQRADDAC(a[11], a[29]); SQRADDAC(a[12], a[28]); SQRADDAC(a[13], a[27]); SQRADDAC(a[14], a[26]); SQRADDAC(a[15], a[25]); SQRADDAC(a[16], a[24]); SQRADDAC(a[17], a[23]); SQRADDAC(a[18], a[22]); SQRADDAC(a[19], a[21]); SQRADDDB; SQRADD(a[20], a[20]);
965 SQRADDSC(a[10], a[31]); SQRADDAC(a[11], a[30]); SQRADDAC(a[12], a[29]); SQRADDAC(a[13], a[28]); SQRADDAC(a[14], a[27]); SQRADDAC(a[15], a[26]); SQRADDAC(a[16], a[25]); SQRADDAC(a[17], a[24]); SQRADDAC(a[18], a[23]); SQRADDAC(a[19], a[22]); SQRADDAC(a[20], a[21]); SQRADDDB;
970 SQRADDSC(a[11], a[31]); SQRADDAC(a[12], a[30]); SQRADDAC(a[13], a[29]); SQRADDAC(a[14], a[28]); SQRADDAC(a[15], a[27]); SQRADDAC(a[16], a[26]); SQRADDAC(a[17], a[25]); SQRADDAC(a[18], a[24]); SQRADDAC(a[19], a[23]); SQRADDAC(a[20], a[22]); SQRADDDB; SQRADD(a[21], a[21]);
975 SQRADDSC(a[12], a[31]); SQRADDAC(a[13], a[30]); SQRADDAC(a[14], a[29]); SQRADDAC(a[15], a[28]); SQRADDAC(a[16], a[27]); SQRADDAC(a[17], a[26]); SQRADDAC(a[18], a[25]); SQRADDAC(a[19], a[24]); SQRADDAC(a[20], a[23]); SQRADDAC(a[21], a[22]); SQRADDDB;
980 SQRADDSC(a[13], a[31]); SQRADDAC(a[14], a[30]); SQRADDAC(a[15], a[29]); SQRADDAC(a[16], a[28]); SQRADDAC(a[17], a[27]); SQRADDAC(a[18], a[26]); SQRADDAC(a[19], a[25]); SQRADDAC(a[20], a[24]); SQRADDAC(a[21], a[23]); SQRADDDB; SQRADD(a[22], a[22]);
985 SQRADDSC(a[14], a[31]); SQRADDAC(a[15], a[30]); SQRADDAC(a[16], a[29]); SQRADDAC(a[17], a[28]); SQRADDAC(a[18], a[27]); SQRADDAC(a[19], a[26]); SQRADDAC(a[20], a[25]); SQRADDAC(a[21], a[24]); SQRADDAC(a[22], a[23]); SQRADDDB;
990 SQRADDSC(a[15], a[31]); SQRADDAC(a[16], a[30]); SQRADDAC(a[17], a[29]); SQRADDAC(a[18], a[28]); SQRADDAC(a[19], a[27]); SQRADDAC(a[20], a[26]); SQRADDAC(a[21], a[25]); SQRADDAC(a[22], a[24]); SQRADDDB; SQRADD(a[23], a[23]);
995 SQRADDSC(a[16], a[31]); SQRADDAC(a[17], a[30]); SQRADDAC(a[18], a[29]); SQRADDAC(a[19], a[28]); SQRADDAC(a[20], a[27]); SQRADDAC(a[21], a[26]); SQRADDAC(a[22], a[25]); SQRADDAC(a[23], a[24]); SQRADDDB;
1000 SQRADDSC(a[17], a[31]); SQRADDAC(a[18], a[30]); SQRADDAC(a[19], a[29]); SQRADDAC(a[20], a[28]); SQRADDAC(a[21], a[27]); SQRADDAC(a[22], a[26]); SQRADDAC(a[23], a[25]); SQRADDDB; SQRADD(a[24], a[24]);
1005 SQRADDSC(a[18], a[31]); SQRADDAC(a[19], a[30]); SQRADDAC(a[20], a[29]); SQRADDAC(a[21], a[28]); SQRADDAC(a[22], a[27]); SQRADDAC(a[23], a[26]); SQRADDAC(a[24], a[25]); SQRADDDB;
1010 SQRADDSC(a[19], a[31]); SQRADDAC(a[20], a[30]); SQRADDAC(a[21], a[29]); SQRADDAC(a[22], a[28]); SQRADDAC(a[23], a[27]); SQRADDAC(a[24], a[26]); SQRADDDB; SQRADD(a[25], a[25]);
1015 SQRADDSC(a[20], a[31]); SQRADDAC(a[21], a[30]); SQRADDAC(a[22], a[29]); SQRADDAC(a[23], a[28]); SQRADDAC(a[24], a[27]); SQRADDAC(a[25], a[26]); SQRADDDB;
1020 SQRADDSC(a[21], a[31]); SQRADDAC(a[22], a[30]); SQRADDAC(a[23], a[29]); SQRADDAC(a[24], a[28]); SQRADDAC(a[25], a[27]); SQRADDDB; SQRADD(a[26], a[26]);
1025 SQRADDSC(a[22], a[31]); SQRADDAC(a[23], a[30]); SQRADDAC(a[24], a[29]); SQRADDAC(a[25], a[28]); SQRADDAC(a[26], a[27]); SQRADDDB;
1030 SQRADDSC(a[23], a[31]); SQRADDAC(a[24], a[30]); SQRADDAC(a[25], a[29]); SQRADDAC(a[26], a[28]); SQRADDDB; SQRADD(a[27], a[27]);
1035 SQRADDSC(a[24], a[31]); SQRADDAC(a[25], a[30]); SQRADDAC(a[26], a[29]); SQRADDAC(a[27], a[28]); SQRADDDB;
1040 SQRADDSC(a[25], a[31]); SQRADDAC(a[26], a[30]); SQRADDAC(a[27], a[29]); SQRADDDB; SQRADD(a[28], a[28]);
1045 SQRADDSC(a[26], a[31]); SQRADDAC(a[27], a[30]); SQRADDAC(a[28], a[29]); SQRADDDB;
1050 SQRADD2(a[27], a[31]); SQRADD2(a[28], a[30]); SQRADD(a[29], a[29]);
1055 SQRADD2(a[28], a[31]); SQRADD2(a[29], a[30]);
1060 SQRADD2(a[29], a[31]); SQRADD(a[30], a[30]);
1065 SQRADD2(a[30], a[31]);
1070 SQRADD(a[31], a[31]);
1072 COMBA_STORE2(b[63]);
1076 B->sign = PSTM_ZPOS;
1077 memcpy(B->dp, b, 64 * sizeof(pstm_digit));
1081 #endif /* USE_2048_KEY_SPEED_OPTIMIZATIONS */
1083 /******************************************************************************/
1086 int32 pstm_sqr_comba(psPool_t *pool, pstm_int *A, pstm_int *B, pstm_digit *paD,
1089 #ifdef USE_1024_KEY_SPEED_OPTIMIZATIONS
1090 if (A->used == 16) {
1091 return pstm_sqr_comba16(A, B);
1093 #ifdef USE_2048_KEY_SPEED_OPTIMIZATIONS
1094 if (A->used == 32) {
1095 return pstm_sqr_comba32(A, B);
1097 #endif /* USE_2048_KEY_SPEED_OPTIMIZATIONS */
1098 return pstm_sqr_comba_gen(pool, A, B, paD, paDlen);
1101 #ifdef USE_2048_KEY_SPEED_OPTIMIZATIONS
1102 if (A->used == 32) {
1103 return pstm_sqr_comba32(A, B);
1105 #endif /* USE_2048_KEY_SPEED_OPTIMIZATIONS */
1106 return pstm_sqr_comba_gen(pool, A, B, paD, paDlen);
1110 #endif /* DISABLE_PSTM */
1111 /******************************************************************************/