crypto/bn/asm/armv8-mont.pl

   1 #!/usr/bin/env perl
   2
   3 # ====================================================================
   4 # Written by Andy Polyakov <appro@openssl.org> for the OpenSSL
   5 # project. The module is, however, dual licensed under OpenSSL and
   6 # CRYPTOGAMS licenses depending on where you obtain it. For further
   7 # details see http://www.openssl.org/~appro/cryptogams/.
   8 # ====================================================================
   9
  10 # March 2015
  11 #
  12 # "Teaser" Montgomery multiplication module for ARMv8. Needs more
  13 # work. While it does improve RSA sign performance by 20-30% (less for
  14 # longer keys) on most processors, for some reason RSA2048 is not
  15 # faster and RSA4096 goes 15-20% slower on Cortex-A57. Multiplication
  16 # instruction issue rate is limited on processor in question, meaning
  17 # that dedicated squaring procedure is a must. Well, actually all
  18 # contemporary AArch64 processors seem to have limited multiplication
  19 # issue rate, i.e. they can't issue multiplication every cycle, which
  20 # explains moderate improvement coefficients in comparison to
  21 # compiler-generated code. Recall that compiler is instructed to use
  22 # umulh and therefore uses same amount of multiplication instructions
  23 # to do the job. Assembly's edge is to minimize number of "collateral"
  24 # instructions and of course instruction scheduling.
  25 #
  26 # April 2015
  27 #
  28 # Squaring procedure that handles lengths divisible by 8 improves
  29 # RSA/DSA performance by 25-40-60% depending on processor and key
  30 # length. Overall improvement coefficients are always positive in
  31 # comparison to compiler-generated code. On Cortex-A57 improvement
  32 # is still modest on longest key lengths, while others exhibit e.g.
  33 # 50-70% improvement for RSA4096 sign. RSA2048 sign is ~25% faster
  34 # on Cortex-A57 and ~60-100% faster on others.
  35
  36 $flavour = shift;
  37 $output  = shift;
  38
  39 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
  40 ( $xlate="${dir}arm-xlate.pl" and -f $xlate ) or
  41 ( $xlate="${dir}../../perlasm/arm-xlate.pl" and -f $xlate) or
  42 die "can't locate arm-xlate.pl";
  43
  44 open OUT,"| \"$^X\" $xlate $flavour $output";
  45 *STDOUT=*OUT;
  46
  47 ($lo0,$hi0,$aj,$m0,$alo,$ahi,
  48  $lo1,$hi1,$nj,$m1,$nlo,$nhi,
  49  $ovf, $i,$j,$tp,$tj) = map("x$_",6..17,19..24);
  50
  51 # int bn_mul_mont(
  52 $rp="x0";       # BN_ULONG *rp,
  53 $ap="x1";       # const BN_ULONG *ap,
  54 $bp="x2";       # const BN_ULONG *bp,
  55 $np="x3";       # const BN_ULONG *np,
  56 $n0="x4";       # const BN_ULONG *n0,
  57 $num="x5";      # int num);
  58
  59 $code.=<<___;
  60 .text
  61
  62 .globl  bn_mul_mont
  63 .type   bn_mul_mont,%function
  64 .align  5
  65 bn_mul_mont:
  66         tst     $num,#7
  67         b.eq    __bn_sqr8x_mont
  68         tst     $num,#3
  69         b.eq    __bn_mul4x_mont
  70 .Lmul_mont:
  71         stp     x29,x30,[sp,#-64]!
  72         add     x29,sp,#0
  73         stp     x19,x20,[sp,#16]
  74         stp     x21,x22,[sp,#32]
  75         stp     x23,x24,[sp,#48]
  76
  77         ldr     $m0,[$bp],#8            // bp[0]
  78         sub     $tp,sp,$num,lsl#3
  79         ldp     $hi0,$aj,[$ap],#16      // ap[0..1]
  80         lsl     $num,$num,#3
  81         ldr     $n0,[$n0]               // *n0
  82         and     $tp,$tp,#-16            // ABI says so
  83         ldp     $hi1,$nj,[$np],#16      // np[0..1]
  84
  85         mul     $lo0,$hi0,$m0           // ap[0]*bp[0]
  86         sub     $j,$num,#16             // j=num-2
  87         umulh   $hi0,$hi0,$m0
  88         mul     $alo,$aj,$m0            // ap[1]*bp[0]
  89         umulh   $ahi,$aj,$m0
  90
  91         mul     $m1,$lo0,$n0            // "tp[0]"*n0
  92         mov     sp,$tp                  // alloca
  93
  94         // (*)  mul     $lo1,$hi1,$m1   // np[0]*m1
  95         umulh   $hi1,$hi1,$m1
  96         mul     $nlo,$nj,$m1            // np[1]*m1
  97         // (*)  adds    $lo1,$lo1,$lo0  // discarded
  98         // (*)  As for removal of first multiplication and addition
  99         //      instructions. The outcome of first addition is
 100         //      guaranteed to be zero, which leaves two computationally
 101         //      significant outcomes: it either carries or not. Then
 102         //      question is when does it carry? Is there alternative
 103         //      way to deduce it? If you follow operations, you can
 104         //      observe that condition for carry is quite simple:
 105         //      $lo0 being non-zero. So that carry can be calculated
 106         //      by adding -1 to $lo0. That's what next instruction does.
 107         subs    xzr,$lo0,#1             // (*)
 108         umulh   $nhi,$nj,$m1
 109         adc     $hi1,$hi1,xzr
 110         cbz     $j,.L1st_skip
 111
 112 .L1st:
 113         ldr     $aj,[$ap],#8
 114         adds    $lo0,$alo,$hi0
 115         sub     $j,$j,#8                // j--
 116         adc     $hi0,$ahi,xzr
 117
 118         ldr     $nj,[$np],#8
 119         adds    $lo1,$nlo,$hi1
 120         mul     $alo,$aj,$m0            // ap[j]*bp[0]
 121         adc     $hi1,$nhi,xzr
 122         umulh   $ahi,$aj,$m0
 123
 124         adds    $lo1,$lo1,$lo0
 125         mul     $nlo,$nj,$m1            // np[j]*m1
 126         adc     $hi1,$hi1,xzr
 127         umulh   $nhi,$nj,$m1
 128         str     $lo1,[$tp],#8           // tp[j-1]
 129         cbnz    $j,.L1st
 130
 131 .L1st_skip:
 132         adds    $lo0,$alo,$hi0
 133         sub     $ap,$ap,$num            // rewind $ap
 134         adc     $hi0,$ahi,xzr
 135
 136         adds    $lo1,$nlo,$hi1
 137         sub     $np,$np,$num            // rewind $np
 138         adc     $hi1,$nhi,xzr
 139
 140         adds    $lo1,$lo1,$lo0
 141         sub     $i,$num,#8              // i=num-1
 142         adcs    $hi1,$hi1,$hi0
 143
 144         adc     $ovf,xzr,xzr            // upmost overflow bit
 145         stp     $lo1,$hi1,[$tp]
 146
 147 .Louter:
 148         ldr     $m0,[$bp],#8            // bp[i]
 149         ldp     $hi0,$aj,[$ap],#16
 150         ldr     $tj,[sp]                // tp[0]
 151         add     $tp,sp,#8
 152
 153         mul     $lo0,$hi0,$m0           // ap[0]*bp[i]
 154         sub     $j,$num,#16             // j=num-2
 155         umulh   $hi0,$hi0,$m0
 156         ldp     $hi1,$nj,[$np],#16
 157         mul     $alo,$aj,$m0            // ap[1]*bp[i]
 158         adds    $lo0,$lo0,$tj
 159         umulh   $ahi,$aj,$m0
 160         adc     $hi0,$hi0,xzr
 161
 162         mul     $m1,$lo0,$n0
 163         sub     $i,$i,#8                // i--
 164
 165         // (*)  mul     $lo1,$hi1,$m1   // np[0]*m1
 166         umulh   $hi1,$hi1,$m1
 167         mul     $nlo,$nj,$m1            // np[1]*m1
 168         // (*)  adds    $lo1,$lo1,$lo0
 169         subs    xzr,$lo0,#1             // (*)
 170         umulh   $nhi,$nj,$m1
 171         cbz     $j,.Linner_skip
 172
 173 .Linner:
 174         ldr     $aj,[$ap],#8
 175         adc     $hi1,$hi1,xzr
 176         ldr     $tj,[$tp],#8            // tp[j]
 177         adds    $lo0,$alo,$hi0
 178         sub     $j,$j,#8                // j--
 179         adc     $hi0,$ahi,xzr
 180
 181         adds    $lo1,$nlo,$hi1
 182         ldr     $nj,[$np],#8
 183         adc     $hi1,$nhi,xzr
 184
 185         mul     $alo,$aj,$m0            // ap[j]*bp[i]
 186         adds    $lo0,$lo0,$tj
 187         umulh   $ahi,$aj,$m0
 188         adc     $hi0,$hi0,xzr
 189
 190         mul     $nlo,$nj,$m1            // np[j]*m1
 191         adds    $lo1,$lo1,$lo0
 192         umulh   $nhi,$nj,$m1
 193         str     $lo1,[$tp,#-16]         // tp[j-1]
 194         cbnz    $j,.Linner
 195
 196 .Linner_skip:
 197         ldr     $tj,[$tp],#8            // tp[j]
 198         adc     $hi1,$hi1,xzr
 199         adds    $lo0,$alo,$hi0
 200         sub     $ap,$ap,$num            // rewind $ap
 201         adc     $hi0,$ahi,xzr
 202
 203         adds    $lo1,$nlo,$hi1
 204         sub     $np,$np,$num            // rewind $np
 205         adcs    $hi1,$nhi,$ovf
 206         adc     $ovf,xzr,xzr
 207
 208         adds    $lo0,$lo0,$tj
 209         adc     $hi0,$hi0,xzr
 210
 211         adds    $lo1,$lo1,$lo0
 212         adcs    $hi1,$hi1,$hi0
 213         adc     $ovf,$ovf,xzr           // upmost overflow bit
 214         stp     $lo1,$hi1,[$tp,#-16]
 215
 216         cbnz    $i,.Louter
 217
 218         // Final step. We see if result is larger than modulus, and
 219         // if it is, subtract the modulus. But comparison implies
 220         // subtraction. So we subtract modulus, see if it borrowed,
 221         // and conditionally copy original value.
 222         ldr     $tj,[sp]                // tp[0]
 223         add     $tp,sp,#8
 224         ldr     $nj,[$np],#8            // np[0]
 225         subs    $j,$num,#8              // j=num-1 and clear borrow
 226         mov     $ap,$rp
 227 .Lsub:
 228         sbcs    $aj,$tj,$nj             // tp[j]-np[j]
 229         ldr     $tj,[$tp],#8
 230         sub     $j,$j,#8                // j--
 231         ldr     $nj,[$np],#8
 232         str     $aj,[$ap],#8            // rp[j]=tp[j]-np[j]
 233         cbnz    $j,.Lsub
 234
 235         sbcs    $aj,$tj,$nj
 236         sbcs    $ovf,$ovf,xzr           // did it borrow?
 237         str     $aj,[$ap],#8            // rp[num-1]
 238
 239         ldr     $tj,[sp]                // tp[0]
 240         add     $tp,sp,#8
 241         ldr     $aj,[$rp],#8            // rp[0]
 242         sub     $num,$num,#8            // num--
 243         nop
 244 .Lcond_copy:
 245         sub     $num,$num,#8            // num--
 246         csel    $nj,$tj,$aj,lo          // did it borrow?
 247         ldr     $tj,[$tp],#8
 248         ldr     $aj,[$rp],#8
 249         str     xzr,[$tp,#-16]          // wipe tp
 250         str     $nj,[$rp,#-16]
 251         cbnz    $num,.Lcond_copy
 252
 253         csel    $nj,$tj,$aj,lo
 254         str     xzr,[$tp,#-8]           // wipe tp
 255         str     $nj,[$rp,#-8]
 256
 257         ldp     x19,x20,[x29,#16]
 258         mov     sp,x29
 259         ldp     x21,x22,[x29,#32]
 260         mov     x0,#1
 261         ldp     x23,x24,[x29,#48]
 262         ldr     x29,[sp],#64
 263         ret
 264 .size   bn_mul_mont,.-bn_mul_mont
 265 ___
 266 {
 267 ########################################################################
 268 # Following is ARMv8 adaptation of sqrx8x_mont from x86_64-mont5 module.
 269
 270 my ($a0,$a1,$a2,$a3,$a4,$a5,$a6,$a7)=map("x$_",(6..13));
 271 my ($t0,$t1,$t2,$t3)=map("x$_",(14..17));
 272 my ($acc0,$acc1,$acc2,$acc3,$acc4,$acc5,$acc6,$acc7)=map("x$_",(19..26));
 273 my ($cnt,$carry,$topmost)=("x27","x28","x30");
 274 my ($tp,$ap_end,$na0)=($bp,$np,$carry);
 275
 276 $code.=<<___;
 277 .type   __bn_sqr8x_mont,%function
 278 .align  5
 279 __bn_sqr8x_mont:
 280         cmp     $ap,$bp
 281         b.ne    __bn_mul4x_mont
 282 .Lsqr8x_mont:
 283         stp     x29,x30,[sp,#-128]!
 284         add     x29,sp,#0
 285         stp     x19,x20,[sp,#16]
 286         stp     x21,x22,[sp,#32]
 287         stp     x23,x24,[sp,#48]
 288         stp     x25,x26,[sp,#64]
 289         stp     x27,x28,[sp,#80]
 290         stp     $rp,$np,[sp,#96]        // offload rp and np
 291
 292         ldp     $a0,$a1,[$ap,#8*0]
 293         ldp     $a2,$a3,[$ap,#8*2]
 294         ldp     $a4,$a5,[$ap,#8*4]
 295         ldp     $a6,$a7,[$ap,#8*6]
 296
 297         sub     $tp,sp,$num,lsl#4
 298         lsl     $num,$num,#3
 299         ldr     $n0,[$n0]               // *n0
 300         mov     sp,$tp                  // alloca
 301         sub     $cnt,$num,#8*8
 302         b       .Lsqr8x_zero_start
 303
 304 .Lsqr8x_zero:
 305         sub     $cnt,$cnt,#8*8
 306         stp     xzr,xzr,[$tp,#8*0]
 307         stp     xzr,xzr,[$tp,#8*2]
 308         stp     xzr,xzr,[$tp,#8*4]
 309         stp     xzr,xzr,[$tp,#8*6]
 310 .Lsqr8x_zero_start:
 311         stp     xzr,xzr,[$tp,#8*8]
 312         stp     xzr,xzr,[$tp,#8*10]
 313         stp     xzr,xzr,[$tp,#8*12]
 314         stp     xzr,xzr,[$tp,#8*14]
 315         add     $tp,$tp,#8*16
 316         cbnz    $cnt,.Lsqr8x_zero
 317
 318         add     $ap_end,$ap,$num
 319         add     $ap,$ap,#8*8
 320         mov     $acc0,xzr
 321         mov     $acc1,xzr
 322         mov     $acc2,xzr
 323         mov     $acc3,xzr
 324         mov     $acc4,xzr
 325         mov     $acc5,xzr
 326         mov     $acc6,xzr
 327         mov     $acc7,xzr
 328         mov     $tp,sp
 329         str     $n0,[x29,#112]          // offload n0
 330
 331         // Multiply everything but a[i]*a[i]
 332 .align  4
 333 .Lsqr8x_outer_loop:
 334         //                                                 a[1]a[0]     (i)
 335         //                                             a[2]a[0]
 336         //                                         a[3]a[0]
 337         //                                     a[4]a[0]
 338         //                                 a[5]a[0]
 339         //                             a[6]a[0]
 340         //                         a[7]a[0]
 341         //                                         a[2]a[1]             (ii)
 342         //                                     a[3]a[1]
 343         //                                 a[4]a[1]
 344         //                             a[5]a[1]
 345         //                         a[6]a[1]
 346         //                     a[7]a[1]
 347         //                                 a[3]a[2]                     (iii)
 348         //                             a[4]a[2]
 349         //                         a[5]a[2]
 350         //                     a[6]a[2]
 351         //                 a[7]a[2]
 352         //                         a[4]a[3]                             (iv)
 353         //                     a[5]a[3]
 354         //                 a[6]a[3]
 355         //             a[7]a[3]
 356         //                 a[5]a[4]                                     (v)
 357         //             a[6]a[4]
 358         //         a[7]a[4]
 359         //         a[6]a[5]                                             (vi)
 360         //     a[7]a[5]
 361         // a[7]a[6]                                                     (vii)
 362
 363         mul     $t0,$a1,$a0             // lo(a[1..7]*a[0])             (i)
 364         mul     $t1,$a2,$a0
 365         mul     $t2,$a3,$a0
 366         mul     $t3,$a4,$a0
 367         adds    $acc1,$acc1,$t0         // t[1]+lo(a[1]*a[0])
 368         mul     $t0,$a5,$a0
 369         adcs    $acc2,$acc2,$t1
 370         mul     $t1,$a6,$a0
 371         adcs    $acc3,$acc3,$t2
 372         mul     $t2,$a7,$a0
 373         adcs    $acc4,$acc4,$t3
 374         umulh   $t3,$a1,$a0             // hi(a[1..7]*a[0])
 375         adcs    $acc5,$acc5,$t0
 376         umulh   $t0,$a2,$a0
 377         adcs    $acc6,$acc6,$t1
 378         umulh   $t1,$a3,$a0
 379         adcs    $acc7,$acc7,$t2
 380         umulh   $t2,$a4,$a0
 381         stp     $acc0,$acc1,[$tp],#8*2  // t[0..1]
 382         adc     $acc0,xzr,xzr           // t[8]
 383         adds    $acc2,$acc2,$t3         // t[2]+lo(a[1]*a[0])
 384         umulh   $t3,$a5,$a0
 385         adcs    $acc3,$acc3,$t0
 386         umulh   $t0,$a6,$a0
 387         adcs    $acc4,$acc4,$t1
 388         umulh   $t1,$a7,$a0
 389         adcs    $acc5,$acc5,$t2
 390          mul    $t2,$a2,$a1             // lo(a[2..7]*a[1])             (ii)
 391         adcs    $acc6,$acc6,$t3
 392          mul    $t3,$a3,$a1
 393         adcs    $acc7,$acc7,$t0
 394          mul    $t0,$a4,$a1
 395         adc     $acc0,$acc0,$t1
 396
 397         mul     $t1,$a5,$a1
 398         adds    $acc3,$acc3,$t2
 399         mul     $t2,$a6,$a1
 400         adcs    $acc4,$acc4,$t3
 401         mul     $t3,$a7,$a1
 402         adcs    $acc5,$acc5,$t0
 403         umulh   $t0,$a2,$a1             // hi(a[2..7]*a[1])
 404         adcs    $acc6,$acc6,$t1
 405         umulh   $t1,$a3,$a1
 406         adcs    $acc7,$acc7,$t2
 407         umulh   $t2,$a4,$a1
 408         adcs    $acc0,$acc0,$t3
 409         umulh   $t3,$a5,$a1
 410         stp     $acc2,$acc3,[$tp],#8*2  // t[2..3]
 411         adc     $acc1,xzr,xzr           // t[9]
 412         adds    $acc4,$acc4,$t0
 413         umulh   $t0,$a6,$a1
 414         adcs    $acc5,$acc5,$t1
 415         umulh   $t1,$a7,$a1
 416         adcs    $acc6,$acc6,$t2
 417          mul    $t2,$a3,$a2             // lo(a[3..7]*a[2])             (iii)
 418         adcs    $acc7,$acc7,$t3
 419          mul    $t3,$a4,$a2
 420         adcs    $acc0,$acc0,$t0
 421          mul    $t0,$a5,$a2
 422         adc     $acc1,$acc1,$t1
 423
 424         mul     $t1,$a6,$a2
 425         adds    $acc5,$acc5,$t2
 426         mul     $t2,$a7,$a2
 427         adcs    $acc6,$acc6,$t3
 428         umulh   $t3,$a3,$a2             // hi(a[3..7]*a[2])
 429         adcs    $acc7,$acc7,$t0
 430         umulh   $t0,$a4,$a2
 431         adcs    $acc0,$acc0,$t1
 432         umulh   $t1,$a5,$a2
 433         adcs    $acc1,$acc1,$t2
 434         umulh   $t2,$a6,$a2
 435         stp     $acc4,$acc5,[$tp],#8*2  // t[4..5]
 436         adc     $acc2,xzr,xzr           // t[10]
 437         adds    $acc6,$acc6,$t3
 438         umulh   $t3,$a7,$a2
 439         adcs    $acc7,$acc7,$t0
 440          mul    $t0,$a4,$a3             // lo(a[4..7]*a[3])             (iv)
 441         adcs    $acc0,$acc0,$t1
 442          mul    $t1,$a5,$a3
 443         adcs    $acc1,$acc1,$t2
 444          mul    $t2,$a6,$a3
 445         adc     $acc2,$acc2,$t3
 446
 447         mul     $t3,$a7,$a3
 448         adds    $acc7,$acc7,$t0
 449         umulh   $t0,$a4,$a3             // hi(a[4..7]*a[3])
 450         adcs    $acc0,$acc0,$t1
 451         umulh   $t1,$a5,$a3
 452         adcs    $acc1,$acc1,$t2
 453         umulh   $t2,$a6,$a3
 454         adcs    $acc2,$acc2,$t3
 455         umulh   $t3,$a7,$a3
 456         stp     $acc6,$acc7,[$tp],#8*2  // t[6..7]
 457         adc     $acc3,xzr,xzr           // t[11]
 458         adds    $acc0,$acc0,$t0
 459          mul    $t0,$a5,$a4             // lo(a[5..7]*a[4])             (v)
 460         adcs    $acc1,$acc1,$t1
 461          mul    $t1,$a6,$a4
 462         adcs    $acc2,$acc2,$t2
 463          mul    $t2,$a7,$a4
 464         adc     $acc3,$acc3,$t3
 465
 466         umulh   $t3,$a5,$a4             // hi(a[5..7]*a[4])
 467         adds    $acc1,$acc1,$t0
 468         umulh   $t0,$a6,$a4
 469         adcs    $acc2,$acc2,$t1
 470         umulh   $t1,$a7,$a4
 471         adcs    $acc3,$acc3,$t2
 472          mul    $t2,$a6,$a5             // lo(a[6..7]*a[5])             (vi)
 473         adc     $acc4,xzr,xzr           // t[12]
 474         adds    $acc2,$acc2,$t3
 475          mul    $t3,$a7,$a5
 476         adcs    $acc3,$acc3,$t0
 477          umulh  $t0,$a6,$a5             // hi(a[6..7]*a[5])
 478         adc     $acc4,$acc4,$t1
 479
 480         umulh   $t1,$a7,$a5
 481         adds    $acc3,$acc3,$t2
 482          mul    $t2,$a7,$a6             // lo(a[7]*a[6])                (vii)
 483         adcs    $acc4,$acc4,$t3
 484          umulh  $t3,$a7,$a6             // hi(a[7]*a[6])
 485         adc     $acc5,xzr,xzr           // t[13]
 486         adds    $acc4,$acc4,$t0
 487         sub     $cnt,$ap_end,$ap        // done yet?
 488         adc     $acc5,$acc5,$t1
 489
 490         adds    $acc5,$acc5,$t2
 491         sub     $t0,$ap_end,$num        // rewinded ap
 492         adc     $acc6,xzr,xzr           // t[14]
 493         add     $acc6,$acc6,$t3
 494
 495         cbz     $cnt,.Lsqr8x_outer_break
 496
 497         mov     $n0,$a0
 498         ldp     $a0,$a1,[$tp,#8*0]
 499         ldp     $a2,$a3,[$tp,#8*2]
 500         ldp     $a4,$a5,[$tp,#8*4]
 501         ldp     $a6,$a7,[$tp,#8*6]
 502         adds    $acc0,$acc0,$a0
 503         adcs    $acc1,$acc1,$a1
 504         ldp     $a0,$a1,[$ap,#8*0]
 505         adcs    $acc2,$acc2,$a2
 506         adcs    $acc3,$acc3,$a3
 507         ldp     $a2,$a3,[$ap,#8*2]
 508         adcs    $acc4,$acc4,$a4
 509         adcs    $acc5,$acc5,$a5
 510         ldp     $a4,$a5,[$ap,#8*4]
 511         adcs    $acc6,$acc6,$a6
 512         mov     $rp,$ap
 513         adcs    $acc7,xzr,$a7
 514         ldp     $a6,$a7,[$ap,#8*6]
 515         add     $ap,$ap,#8*8
 516         //adc   $carry,xzr,xzr          // moved below
 517         mov     $cnt,#-8*8
 518
 519         //                                                         a[8]a[0]
 520         //                                                     a[9]a[0]
 521         //                                                 a[a]a[0]
 522         //                                             a[b]a[0]
 523         //                                         a[c]a[0]
 524         //                                     a[d]a[0]
 525         //                                 a[e]a[0]
 526         //                             a[f]a[0]
 527         //                                                     a[8]a[1]
 528         //                         a[f]a[1]........................
 529         //                                                 a[8]a[2]
 530         //                     a[f]a[2]........................
 531         //                                             a[8]a[3]
 532         //                 a[f]a[3]........................
 533         //                                         a[8]a[4]
 534         //             a[f]a[4]........................
 535         //                                     a[8]a[5]
 536         //         a[f]a[5]........................
 537         //                                 a[8]a[6]
 538         //     a[f]a[6]........................
 539         //                             a[8]a[7]
 540         // a[f]a[7]........................
 541 .Lsqr8x_mul:
 542         mul     $t0,$a0,$n0
 543         adc     $carry,xzr,xzr          // carry bit, modulo-scheduled
 544         mul     $t1,$a1,$n0
 545         add     $cnt,$cnt,#8
 546         mul     $t2,$a2,$n0
 547         mul     $t3,$a3,$n0
 548         adds    $acc0,$acc0,$t0
 549         mul     $t0,$a4,$n0
 550         adcs    $acc1,$acc1,$t1
 551         mul     $t1,$a5,$n0
 552         adcs    $acc2,$acc2,$t2
 553         mul     $t2,$a6,$n0
 554         adcs    $acc3,$acc3,$t3
 555         mul     $t3,$a7,$n0
 556         adcs    $acc4,$acc4,$t0
 557         umulh   $t0,$a0,$n0
 558         adcs    $acc5,$acc5,$t1
 559         umulh   $t1,$a1,$n0
 560         adcs    $acc6,$acc6,$t2
 561         umulh   $t2,$a2,$n0
 562         adcs    $acc7,$acc7,$t3
 563         umulh   $t3,$a3,$n0
 564         adc     $carry,$carry,xzr
 565         str     $acc0,[$tp],#8
 566         adds    $acc0,$acc1,$t0
 567         umulh   $t0,$a4,$n0
 568         adcs    $acc1,$acc2,$t1
 569         umulh   $t1,$a5,$n0
 570         adcs    $acc2,$acc3,$t2
 571         umulh   $t2,$a6,$n0
 572         adcs    $acc3,$acc4,$t3
 573         umulh   $t3,$a7,$n0
 574         ldr     $n0,[$rp,$cnt]
 575         adcs    $acc4,$acc5,$t0
 576         adcs    $acc5,$acc6,$t1
 577         adcs    $acc6,$acc7,$t2
 578         adcs    $acc7,$carry,$t3
 579         //adc   $carry,xzr,xzr          // moved above
 580         cbnz    $cnt,.Lsqr8x_mul
 581                                         // note that carry flag is guaranteed
 582                                         // to be zero at this point
 583         cmp     $ap,$ap_end             // done yet?
 584         b.eq    .Lsqr8x_break
 585
 586         ldp     $a0,$a1,[$tp,#8*0]
 587         ldp     $a2,$a3,[$tp,#8*2]
 588         ldp     $a4,$a5,[$tp,#8*4]
 589         ldp     $a6,$a7,[$tp,#8*6]
 590         adds    $acc0,$acc0,$a0
 591         ldr     $n0,[$rp,#-8*8]
 592         adcs    $acc1,$acc1,$a1
 593         ldp     $a0,$a1,[$ap,#8*0]
 594         adcs    $acc2,$acc2,$a2
 595         adcs    $acc3,$acc3,$a3
 596         ldp     $a2,$a3,[$ap,#8*2]
 597         adcs    $acc4,$acc4,$a4
 598         adcs    $acc5,$acc5,$a5
 599         ldp     $a4,$a5,[$ap,#8*4]
 600         adcs    $acc6,$acc6,$a6
 601         mov     $cnt,#-8*8
 602         adcs    $acc7,$acc7,$a7
 603         ldp     $a6,$a7,[$ap,#8*6]
 604         add     $ap,$ap,#8*8
 605         //adc   $carry,xzr,xzr          // moved above
 606         b       .Lsqr8x_mul
 607
 608 .align  4
 609 .Lsqr8x_break:
 610         ldp     $a0,$a1,[$rp,#8*0]
 611         add     $ap,$rp,#8*8
 612         ldp     $a2,$a3,[$rp,#8*2]
 613         sub     $t0,$ap_end,$ap         // is it last iteration?
 614         ldp     $a4,$a5,[$rp,#8*4]
 615         sub     $t1,$tp,$t0
 616         ldp     $a6,$a7,[$rp,#8*6]
 617         cbz     $t0,.Lsqr8x_outer_loop
 618
 619         stp     $acc0,$acc1,[$tp,#8*0]
 620         ldp     $acc0,$acc1,[$t1,#8*0]
 621         stp     $acc2,$acc3,[$tp,#8*2]
 622         ldp     $acc2,$acc3,[$t1,#8*2]
 623         stp     $acc4,$acc5,[$tp,#8*4]
 624         ldp     $acc4,$acc5,[$t1,#8*4]
 625         stp     $acc6,$acc7,[$tp,#8*6]
 626         mov     $tp,$t1
 627         ldp     $acc6,$acc7,[$t1,#8*6]
 628         b       .Lsqr8x_outer_loop
 629
 630 .align  4
 631 .Lsqr8x_outer_break:
 632         // Now multiply above result by 2 and add a[n-1]*a[n-1]|...|a[0]*a[0]
 633         ldp     $a1,$a3,[$t0,#8*0]      // recall that $t0 is &a[0]
 634         ldp     $t1,$t2,[sp,#8*1]
 635         ldp     $a5,$a7,[$t0,#8*2]
 636         add     $ap,$t0,#8*4
 637         ldp     $t3,$t0,[sp,#8*3]
 638
 639         stp     $acc0,$acc1,[$tp,#8*0]
 640         mul     $acc0,$a1,$a1
 641         stp     $acc2,$acc3,[$tp,#8*2]
 642         umulh   $a1,$a1,$a1
 643         stp     $acc4,$acc5,[$tp,#8*4]
 644         mul     $a2,$a3,$a3
 645         stp     $acc6,$acc7,[$tp,#8*6]
 646         mov     $tp,sp
 647         umulh   $a3,$a3,$a3
 648         adds    $acc1,$a1,$t1,lsl#1
 649         extr    $t1,$t2,$t1,#63
 650         sub     $cnt,$num,#8*4
 651
 652 .Lsqr4x_shift_n_add:
 653         adcs    $acc2,$a2,$t1
 654         extr    $t2,$t3,$t2,#63
 655         sub     $cnt,$cnt,#8*4
 656         adcs    $acc3,$a3,$t2
 657         ldp     $t1,$t2,[$tp,#8*5]
 658         mul     $a4,$a5,$a5
 659         ldp     $a1,$a3,[$ap],#8*2
 660         umulh   $a5,$a5,$a5
 661         mul     $a6,$a7,$a7
 662         umulh   $a7,$a7,$a7
 663         extr    $t3,$t0,$t3,#63
 664         stp     $acc0,$acc1,[$tp,#8*0]
 665         adcs    $acc4,$a4,$t3
 666         extr    $t0,$t1,$t0,#63
 667         stp     $acc2,$acc3,[$tp,#8*2]
 668         adcs    $acc5,$a5,$t0
 669         ldp     $t3,$t0,[$tp,#8*7]
 670         extr    $t1,$t2,$t1,#63
 671         adcs    $acc6,$a6,$t1
 672         extr    $t2,$t3,$t2,#63
 673         adcs    $acc7,$a7,$t2
 674         ldp     $t1,$t2,[$tp,#8*9]
 675         mul     $a0,$a1,$a1
 676         ldp     $a5,$a7,[$ap],#8*2
 677         umulh   $a1,$a1,$a1
 678         mul     $a2,$a3,$a3
 679         umulh   $a3,$a3,$a3
 680         stp     $acc4,$acc5,[$tp,#8*4]
 681         extr    $t3,$t0,$t3,#63
 682         stp     $acc6,$acc7,[$tp,#8*6]
 683         add     $tp,$tp,#8*8
 684         adcs    $acc0,$a0,$t3
 685         extr    $t0,$t1,$t0,#63
 686         adcs    $acc1,$a1,$t0
 687         ldp     $t3,$t0,[$tp,#8*3]
 688         extr    $t1,$t2,$t1,#63
 689         cbnz    $cnt,.Lsqr4x_shift_n_add
 690 ___
 691 my ($np,$np_end)=($ap,$ap_end);
 692 $code.=<<___;
 693          ldp    $np,$n0,[x29,#104]      // pull np and n0
 694
 695         adcs    $acc2,$a2,$t1
 696         extr    $t2,$t3,$t2,#63
 697         adcs    $acc3,$a3,$t2
 698         ldp     $t1,$t2,[$tp,#8*5]
 699         mul     $a4,$a5,$a5
 700         umulh   $a5,$a5,$a5
 701         stp     $acc0,$acc1,[$tp,#8*0]
 702         mul     $a6,$a7,$a7
 703         umulh   $a7,$a7,$a7
 704         stp     $acc2,$acc3,[$tp,#8*2]
 705         extr    $t3,$t0,$t3,#63
 706         adcs    $acc4,$a4,$t3
 707         extr    $t0,$t1,$t0,#63
 708          ldp    $acc0,$acc1,[sp,#8*0]
 709         adcs    $acc5,$a5,$t0
 710         extr    $t1,$t2,$t1,#63
 711          ldp    $a0,$a1,[$np,#8*0]
 712         adcs    $acc6,$a6,$t1
 713         extr    $t2,xzr,$t2,#63
 714          ldp    $a2,$a3,[$np,#8*2]
 715         adc     $acc7,$a7,$t2
 716          ldp    $a4,$a5,[$np,#8*4]
 717
 718         // Reduce by 512 bits per iteration
 719         mul     $na0,$n0,$acc0          // t[0]*n0
 720         ldp     $a6,$a7,[$np,#8*6]
 721         add     $np_end,$np,$num
 722         ldp     $acc2,$acc3,[sp,#8*2]
 723         stp     $acc4,$acc5,[$tp,#8*4]
 724         ldp     $acc4,$acc5,[sp,#8*4]
 725         stp     $acc6,$acc7,[$tp,#8*6]
 726         ldp     $acc6,$acc7,[sp,#8*6]
 727         add     $np,$np,#8*8
 728         mov     $topmost,xzr            // initial top-most carry
 729         mov     $tp,sp
 730         mov     $cnt,#8
 731
 732 .Lsqr8x_reduction:
 733         // (*)  mul     $t0,$a0,$na0    // lo(n[0-7])*lo(t[0]*n0)
 734         mul     $t1,$a1,$na0
 735         sub     $cnt,$cnt,#1
 736         mul     $t2,$a2,$na0
 737         str     $na0,[$tp],#8           // put aside t[0]*n0 for tail processing
 738         mul     $t3,$a3,$na0
 739         // (*)  adds    xzr,$acc0,$t0
 740         subs    xzr,$acc0,#1            // (*)
 741         mul     $t0,$a4,$na0
 742         adcs    $acc0,$acc1,$t1
 743         mul     $t1,$a5,$na0
 744         adcs    $acc1,$acc2,$t2
 745         mul     $t2,$a6,$na0
 746         adcs    $acc2,$acc3,$t3
 747         mul     $t3,$a7,$na0
 748         adcs    $acc3,$acc4,$t0
 749         umulh   $t0,$a0,$na0            // hi(n[0-7])*lo(t[0]*n0)
 750         adcs    $acc4,$acc5,$t1
 751         umulh   $t1,$a1,$na0
 752         adcs    $acc5,$acc6,$t2
 753         umulh   $t2,$a2,$na0
 754         adcs    $acc6,$acc7,$t3
 755         umulh   $t3,$a3,$na0
 756         adc     $acc7,xzr,xzr
 757         adds    $acc0,$acc0,$t0
 758         umulh   $t0,$a4,$na0
 759         adcs    $acc1,$acc1,$t1
 760         umulh   $t1,$a5,$na0
 761         adcs    $acc2,$acc2,$t2
 762         umulh   $t2,$a6,$na0
 763         adcs    $acc3,$acc3,$t3
 764         umulh   $t3,$a7,$na0
 765         mul     $na0,$n0,$acc0          // next t[0]*n0
 766         adcs    $acc4,$acc4,$t0
 767         adcs    $acc5,$acc5,$t1
 768         adcs    $acc6,$acc6,$t2
 769         adc     $acc7,$acc7,$t3
 770         cbnz    $cnt,.Lsqr8x_reduction
 771
 772         ldp     $t0,$t1,[$tp,#8*0]
 773         ldp     $t2,$t3,[$tp,#8*2]
 774         mov     $rp,$tp
 775         sub     $cnt,$np_end,$np        // done yet?
 776         adds    $acc0,$acc0,$t0
 777         adcs    $acc1,$acc1,$t1
 778         ldp     $t0,$t1,[$tp,#8*4]
 779         adcs    $acc2,$acc2,$t2
 780         adcs    $acc3,$acc3,$t3
 781         ldp     $t2,$t3,[$tp,#8*6]
 782         adcs    $acc4,$acc4,$t0
 783         adcs    $acc5,$acc5,$t1
 784         adcs    $acc6,$acc6,$t2
 785         adcs    $acc7,$acc7,$t3
 786         //adc   $carry,xzr,xzr          // moved below
 787         cbz     $cnt,.Lsqr8x8_post_condition
 788
 789         ldr     $n0,[$tp,#-8*8]
 790         ldp     $a0,$a1,[$np,#8*0]
 791         ldp     $a2,$a3,[$np,#8*2]
 792         ldp     $a4,$a5,[$np,#8*4]
 793         mov     $cnt,#-8*8
 794         ldp     $a6,$a7,[$np,#8*6]
 795         add     $np,$np,#8*8
 796
 797 .Lsqr8x_tail:
 798         mul     $t0,$a0,$n0
 799         adc     $carry,xzr,xzr          // carry bit, modulo-scheduled
 800         mul     $t1,$a1,$n0
 801         add     $cnt,$cnt,#8
 802         mul     $t2,$a2,$n0
 803         mul     $t3,$a3,$n0
 804         adds    $acc0,$acc0,$t0
 805         mul     $t0,$a4,$n0
 806         adcs    $acc1,$acc1,$t1
 807         mul     $t1,$a5,$n0
 808         adcs    $acc2,$acc2,$t2
 809         mul     $t2,$a6,$n0
 810         adcs    $acc3,$acc3,$t3
 811         mul     $t3,$a7,$n0
 812         adcs    $acc4,$acc4,$t0
 813         umulh   $t0,$a0,$n0
 814         adcs    $acc5,$acc5,$t1
 815         umulh   $t1,$a1,$n0
 816         adcs    $acc6,$acc6,$t2
 817         umulh   $t2,$a2,$n0
 818         adcs    $acc7,$acc7,$t3
 819         umulh   $t3,$a3,$n0
 820         adc     $carry,$carry,xzr
 821         str     $acc0,[$tp],#8
 822         adds    $acc0,$acc1,$t0
 823         umulh   $t0,$a4,$n0
 824         adcs    $acc1,$acc2,$t1
 825         umulh   $t1,$a5,$n0
 826         adcs    $acc2,$acc3,$t2
 827         umulh   $t2,$a6,$n0
 828         adcs    $acc3,$acc4,$t3
 829         umulh   $t3,$a7,$n0
 830         ldr     $n0,[$rp,$cnt]
 831         adcs    $acc4,$acc5,$t0
 832         adcs    $acc5,$acc6,$t1
 833         adcs    $acc6,$acc7,$t2
 834         adcs    $acc7,$carry,$t3
 835         //adc   $carry,xzr,xzr          // moved above
 836         cbnz    $cnt,.Lsqr8x_tail
 837                                         // note that carry flag is guaranteed
 838                                         // to be zero at this point
 839         ldp     $a0,$a1,[$tp,#8*0]
 840         sub     $cnt,$np_end,$np        // done yet?
 841         sub     $t2,$np_end,$num        // rewinded np
 842         ldp     $a2,$a3,[$tp,#8*2]
 843         ldp     $a4,$a5,[$tp,#8*4]
 844         ldp     $a6,$a7,[$tp,#8*6]
 845         cbz     $cnt,.Lsqr8x_tail_break
 846
 847         ldr     $n0,[$rp,#-8*8]
 848         adds    $acc0,$acc0,$a0
 849         adcs    $acc1,$acc1,$a1
 850         ldp     $a0,$a1,[$np,#8*0]
 851         adcs    $acc2,$acc2,$a2
 852         adcs    $acc3,$acc3,$a3
 853         ldp     $a2,$a3,[$np,#8*2]
 854         adcs    $acc4,$acc4,$a4
 855         adcs    $acc5,$acc5,$a5
 856         ldp     $a4,$a5,[$np,#8*4]
 857         adcs    $acc6,$acc6,$a6
 858         mov     $cnt,#-8*8
 859         adcs    $acc7,$acc7,$a7
 860         ldp     $a6,$a7,[$np,#8*6]
 861         add     $np,$np,#8*8
 862         //adc   $carry,xzr,xzr          // moved above
 863         b       .Lsqr8x_tail
 864
 865 .align  4
 866 .Lsqr8x_tail_break:
 867         ldr     $n0,[x29,#112]          // pull n0
 868         add     $cnt,$tp,#8*8           // end of current t[num] window
 869
 870         subs    xzr,$topmost,#1         // "move" top-most carry to carry bit
 871         adcs    $t0,$acc0,$a0
 872         adcs    $t1,$acc1,$a1
 873         ldp     $acc0,$acc1,[$rp,#8*0]
 874         adcs    $acc2,$acc2,$a2
 875         ldp     $a0,$a1,[$t2,#8*0]      // recall that $t2 is &n[0]
 876         adcs    $acc3,$acc3,$a3
 877         ldp     $a2,$a3,[$t2,#8*2]
 878         adcs    $acc4,$acc4,$a4
 879         adcs    $acc5,$acc5,$a5
 880         ldp     $a4,$a5,[$t2,#8*4]
 881         adcs    $acc6,$acc6,$a6
 882         adcs    $acc7,$acc7,$a7
 883         ldp     $a6,$a7,[$t2,#8*6]
 884         add     $np,$t2,#8*8
 885         adc     $topmost,xzr,xzr        // top-most carry
 886         mul     $na0,$n0,$acc0
 887         stp     $t0,$t1,[$tp,#8*0]
 888         stp     $acc2,$acc3,[$tp,#8*2]
 889         ldp     $acc2,$acc3,[$rp,#8*2]
 890         stp     $acc4,$acc5,[$tp,#8*4]
 891         ldp     $acc4,$acc5,[$rp,#8*4]
 892         cmp     $cnt,x29                // did we hit the bottom?
 893         stp     $acc6,$acc7,[$tp,#8*6]
 894         mov     $tp,$rp                 // slide the window
 895         ldp     $acc6,$acc7,[$rp,#8*6]
 896         mov     $cnt,#8
 897         b.ne    .Lsqr8x_reduction
 898
 899         // Final step. We see if result is larger than modulus, and
 900         // if it is, subtract the modulus. But comparison implies
 901         // subtraction. So we subtract modulus, see if it borrowed,
 902         // and conditionally copy original value.
 903         ldr     $rp,[x29,#96]           // pull rp
 904         add     $tp,$tp,#8*8
 905         subs    $t0,$acc0,$a0
 906         sbcs    $t1,$acc1,$a1
 907         sub     $cnt,$num,#8*8
 908         mov     $ap_end,$rp             // $rp copy
 909
 910 .Lsqr8x_sub:
 911         sbcs    $t2,$acc2,$a2
 912         ldp     $a0,$a1,[$np,#8*0]
 913         sbcs    $t3,$acc3,$a3
 914         stp     $t0,$t1,[$rp,#8*0]
 915         sbcs    $t0,$acc4,$a4
 916         ldp     $a2,$a3,[$np,#8*2]
 917         sbcs    $t1,$acc5,$a5
 918         stp     $t2,$t3,[$rp,#8*2]
 919         sbcs    $t2,$acc6,$a6
 920         ldp     $a4,$a5,[$np,#8*4]
 921         sbcs    $t3,$acc7,$a7
 922         ldp     $a6,$a7,[$np,#8*6]
 923         add     $np,$np,#8*8
 924         ldp     $acc0,$acc1,[$tp,#8*0]
 925         sub     $cnt,$cnt,#8*8
 926         ldp     $acc2,$acc3,[$tp,#8*2]
 927         ldp     $acc4,$acc5,[$tp,#8*4]
 928         ldp     $acc6,$acc7,[$tp,#8*6]
 929         add     $tp,$tp,#8*8
 930         stp     $t0,$t1,[$rp,#8*4]
 931         sbcs    $t0,$acc0,$a0
 932         stp     $t2,$t3,[$rp,#8*6]
 933         add     $rp,$rp,#8*8
 934         sbcs    $t1,$acc1,$a1
 935         cbnz    $cnt,.Lsqr8x_sub
 936
 937         sbcs    $t2,$acc2,$a2
 938          mov    $tp,sp
 939          add    $ap,sp,$num
 940          ldp    $a0,$a1,[$ap_end,#8*0]
 941         sbcs    $t3,$acc3,$a3
 942         stp     $t0,$t1,[$rp,#8*0]
 943         sbcs    $t0,$acc4,$a4
 944          ldp    $a2,$a3,[$ap_end,#8*2]
 945         sbcs    $t1,$acc5,$a5
 946         stp     $t2,$t3,[$rp,#8*2]
 947         sbcs    $t2,$acc6,$a6
 948          ldp    $acc0,$acc1,[$ap,#8*0]
 949         sbcs    $t3,$acc7,$a7
 950          ldp    $acc2,$acc3,[$ap,#8*2]
 951         sbcs    xzr,$topmost,xzr        // did it borrow?
 952         ldr     x30,[x29,#8]            // pull return address
 953         stp     $t0,$t1,[$rp,#8*4]
 954         stp     $t2,$t3,[$rp,#8*6]
 955
 956         sub     $cnt,$num,#8*4
 957 .Lsqr4x_cond_copy:
 958         sub     $cnt,$cnt,#8*4
 959         csel    $t0,$acc0,$a0,lo
 960          stp    xzr,xzr,[$tp,#8*0]
 961         csel    $t1,$acc1,$a1,lo
 962         ldp     $a0,$a1,[$ap_end,#8*4]
 963         ldp     $acc0,$acc1,[$ap,#8*4]
 964         csel    $t2,$acc2,$a2,lo
 965          stp    xzr,xzr,[$tp,#8*2]
 966          add    $tp,$tp,#8*4
 967         csel    $t3,$acc3,$a3,lo
 968         ldp     $a2,$a3,[$ap_end,#8*6]
 969         ldp     $acc2,$acc3,[$ap,#8*6]
 970         add     $ap,$ap,#8*4
 971         stp     $t0,$t1,[$ap_end,#8*0]
 972         stp     $t2,$t3,[$ap_end,#8*2]
 973         add     $ap_end,$ap_end,#8*4
 974          stp    xzr,xzr,[$ap,#8*0]
 975          stp    xzr,xzr,[$ap,#8*2]
 976         cbnz    $cnt,.Lsqr4x_cond_copy
 977
 978         csel    $t0,$acc0,$a0,lo
 979          stp    xzr,xzr,[$tp,#8*0]
 980         csel    $t1,$acc1,$a1,lo
 981          stp    xzr,xzr,[$tp,#8*2]
 982         csel    $t2,$acc2,$a2,lo
 983         csel    $t3,$acc3,$a3,lo
 984         stp     $t0,$t1,[$ap_end,#8*0]
 985         stp     $t2,$t3,[$ap_end,#8*2]
 986
 987         b       .Lsqr8x_done
 988
 989 .align  4
 990 .Lsqr8x8_post_condition:
 991         adc     $carry,xzr,xzr
 992         ldr     x30,[x29,#8]            // pull return address
 993         // $acc0-7,$carry hold result, $a0-7 hold modulus
 994         subs    $a0,$acc0,$a0
 995         ldr     $ap,[x29,#96]           // pull rp
 996         sbcs    $a1,$acc1,$a1
 997          stp    xzr,xzr,[sp,#8*0]
 998         sbcs    $a2,$acc2,$a2
 999          stp    xzr,xzr,[sp,#8*2]
1000         sbcs    $a3,$acc3,$a3
1001          stp    xzr,xzr,[sp,#8*4]
1002         sbcs    $a4,$acc4,$a4
1003          stp    xzr,xzr,[sp,#8*6]
1004         sbcs    $a5,$acc5,$a5
1005          stp    xzr,xzr,[sp,#8*8]
1006         sbcs    $a6,$acc6,$a6
1007          stp    xzr,xzr,[sp,#8*10]
1008         sbcs    $a7,$acc7,$a7
1009          stp    xzr,xzr,[sp,#8*12]
1010         sbcs    $carry,$carry,xzr       // did it borrow?
1011          stp    xzr,xzr,[sp,#8*14]
1012
1013         // $a0-7 hold result-modulus
1014         csel    $a0,$acc0,$a0,lo
1015         csel    $a1,$acc1,$a1,lo
1016         csel    $a2,$acc2,$a2,lo
1017         csel    $a3,$acc3,$a3,lo
1018         stp     $a0,$a1,[$ap,#8*0]
1019         csel    $a4,$acc4,$a4,lo
1020         csel    $a5,$acc5,$a5,lo
1021         stp     $a2,$a3,[$ap,#8*2]
1022         csel    $a6,$acc6,$a6,lo
1023         csel    $a7,$acc7,$a7,lo
1024         stp     $a4,$a5,[$ap,#8*4]
1025         stp     $a6,$a7,[$ap,#8*6]
1026
1027 .Lsqr8x_done:
1028         ldp     x19,x20,[x29,#16]
1029         mov     sp,x29
1030         ldp     x21,x22,[x29,#32]
1031         mov     x0,#1
1032         ldp     x23,x24,[x29,#48]
1033         ldp     x25,x26,[x29,#64]
1034         ldp     x27,x28,[x29,#80]
1035         ldr     x29,[sp],#128
1036         ret
1037 .size   __bn_sqr8x_mont,.-__bn_sqr8x_mont
1038 ___
1039 }
1040
1041 {
1042 ########################################################################
1043 # Even though this might look as ARMv8 adaptation of mulx4x_mont from
1044 # x86_64-mont5 module, it's different in sense that it performs
1045 # reduction 256 bits at a time.
1046
1047 my ($a0,$a1,$a2,$a3,
1048     $t0,$t1,$t2,$t3,
1049     $m0,$m1,$m2,$m3,
1050     $acc0,$acc1,$acc2,$acc3,$acc4,
1051     $bi,$mi,$tp,$ap_end,$cnt) = map("x$_",(6..17,19..28));
1052 my  $bp_end=$rp;
1053 my  ($carry,$topmost) = ($rp,"x30");
1054
1055 $code.=<<___;
1056 .type   __bn_mul4x_mont,%function
1057 .align  5
1058 __bn_mul4x_mont:
1059         stp     x29,x30,[sp,#-128]!
1060         add     x29,sp,#0
1061         stp     x19,x20,[sp,#16]
1062         stp     x21,x22,[sp,#32]
1063         stp     x23,x24,[sp,#48]
1064         stp     x25,x26,[sp,#64]
1065         stp     x27,x28,[sp,#80]
1066
1067         sub     $tp,sp,$num,lsl#3
1068         lsl     $num,$num,#3
1069         ldr     $n0,[$n0]               // *n0
1070         sub     sp,$tp,#8*4             // alloca
1071
1072         add     $t0,$bp,$num
1073         add     $ap_end,$ap,$num
1074         stp     $rp,$t0,[x29,#96]       // offload rp and &b[num]
1075
1076         ldr     $bi,[$bp,#8*0]          // b[0]
1077         ldp     $a0,$a1,[$ap,#8*0]      // a[0..3]
1078         ldp     $a2,$a3,[$ap,#8*2]
1079         add     $ap,$ap,#8*4
1080         mov     $acc0,xzr
1081         mov     $acc1,xzr
1082         mov     $acc2,xzr
1083         mov     $acc3,xzr
1084         ldp     $m0,$m1,[$np,#8*0]      // n[0..3]
1085         ldp     $m2,$m3,[$np,#8*2]
1086         adds    $np,$np,#8*4            // clear carry bit
1087         mov     $carry,xzr
1088         mov     $cnt,#0
1089         mov     $tp,sp
1090
1091 .Loop_mul4x_1st_reduction:
1092         mul     $t0,$a0,$bi             // lo(a[0..3]*b[0])
1093         adc     $carry,$carry,xzr       // modulo-scheduled
1094         mul     $t1,$a1,$bi
1095         add     $cnt,$cnt,#8
1096         mul     $t2,$a2,$bi
1097         and     $cnt,$cnt,#31
1098         mul     $t3,$a3,$bi
1099         adds    $acc0,$acc0,$t0
1100         umulh   $t0,$a0,$bi             // hi(a[0..3]*b[0])
1101         adcs    $acc1,$acc1,$t1
1102         mul     $mi,$acc0,$n0           // t[0]*n0
1103         adcs    $acc2,$acc2,$t2
1104         umulh   $t1,$a1,$bi
1105         adcs    $acc3,$acc3,$t3
1106         umulh   $t2,$a2,$bi
1107         adc     $acc4,xzr,xzr
1108         umulh   $t3,$a3,$bi
1109         ldr     $bi,[$bp,$cnt]          // next b[i] (or b[0])
1110         adds    $acc1,$acc1,$t0
1111         // (*)  mul     $t0,$m0,$mi     // lo(n[0..3]*t[0]*n0)
1112         str     $mi,[$tp],#8            // put aside t[0]*n0 for tail processing
1113         adcs    $acc2,$acc2,$t1
1114         mul     $t1,$m1,$mi
1115         adcs    $acc3,$acc3,$t2
1116         mul     $t2,$m2,$mi
1117         adc     $acc4,$acc4,$t3         // can't overflow
1118         mul     $t3,$m3,$mi
1119         // (*)  adds    xzr,$acc0,$t0
1120         subs    xzr,$acc0,#1            // (*)
1121         umulh   $t0,$m0,$mi             // hi(n[0..3]*t[0]*n0)
1122         adcs    $acc0,$acc1,$t1
1123         umulh   $t1,$m1,$mi
1124         adcs    $acc1,$acc2,$t2
1125         umulh   $t2,$m2,$mi
1126         adcs    $acc2,$acc3,$t3
1127         umulh   $t3,$m3,$mi
1128         adcs    $acc3,$acc4,$carry
1129         adc     $carry,xzr,xzr
1130         adds    $acc0,$acc0,$t0
1131         sub     $t0,$ap_end,$ap
1132         adcs    $acc1,$acc1,$t1
1133         adcs    $acc2,$acc2,$t2
1134         adcs    $acc3,$acc3,$t3
1135         //adc   $carry,$carry,xzr
1136         cbnz    $cnt,.Loop_mul4x_1st_reduction
1137
1138         cbz     $t0,.Lmul4x4_post_condition
1139
1140         ldp     $a0,$a1,[$ap,#8*0]      // a[4..7]
1141         ldp     $a2,$a3,[$ap,#8*2]
1142         add     $ap,$ap,#8*4
1143         ldr     $mi,[sp]                // a[0]*n0
1144         ldp     $m0,$m1,[$np,#8*0]      // n[4..7]
1145         ldp     $m2,$m3,[$np,#8*2]
1146         add     $np,$np,#8*4
1147
1148 .Loop_mul4x_1st_tail:
1149         mul     $t0,$a0,$bi             // lo(a[4..7]*b[i])
1150         adc     $carry,$carry,xzr       // modulo-scheduled
1151         mul     $t1,$a1,$bi
1152         add     $cnt,$cnt,#8
1153         mul     $t2,$a2,$bi
1154         and     $cnt,$cnt,#31
1155         mul     $t3,$a3,$bi
1156         adds    $acc0,$acc0,$t0
1157         umulh   $t0,$a0,$bi             // hi(a[4..7]*b[i])
1158         adcs    $acc1,$acc1,$t1
1159         umulh   $t1,$a1,$bi
1160         adcs    $acc2,$acc2,$t2
1161         umulh   $t2,$a2,$bi
1162         adcs    $acc3,$acc3,$t3
1163         umulh   $t3,$a3,$bi
1164         adc     $acc4,xzr,xzr
1165         ldr     $bi,[$bp,$cnt]          // next b[i] (or b[0])
1166         adds    $acc1,$acc1,$t0
1167         mul     $t0,$m0,$mi             // lo(n[4..7]*a[0]*n0)
1168         adcs    $acc2,$acc2,$t1
1169         mul     $t1,$m1,$mi
1170         adcs    $acc3,$acc3,$t2
1171         mul     $t2,$m2,$mi
1172         adc     $acc4,$acc4,$t3         // can't overflow
1173         mul     $t3,$m3,$mi
1174         adds    $acc0,$acc0,$t0
1175         umulh   $t0,$m0,$mi             // hi(n[4..7]*a[0]*n0)
1176         adcs    $acc1,$acc1,$t1
1177         umulh   $t1,$m1,$mi
1178         adcs    $acc2,$acc2,$t2
1179         umulh   $t2,$m2,$mi
1180         adcs    $acc3,$acc3,$t3
1181         adcs    $acc4,$acc4,$carry
1182         umulh   $t3,$m3,$mi
1183         adc     $carry,xzr,xzr
1184         ldr     $mi,[sp,$cnt]           // next t[0]*n0
1185         str     $acc0,[$tp],#8          // result!!!
1186         adds    $acc0,$acc1,$t0
1187         sub     $t0,$ap_end,$ap         // done yet?
1188         adcs    $acc1,$acc2,$t1
1189         adcs    $acc2,$acc3,$t2
1190         adcs    $acc3,$acc4,$t3
1191         //adc   $carry,$carry,xzr
1192         cbnz    $cnt,.Loop_mul4x_1st_tail
1193
1194         sub     $t1,$ap_end,$num        // rewinded $ap
1195         cbz     $t0,.Lmul4x_proceed
1196
1197         ldp     $a0,$a1,[$ap,#8*0]
1198         ldp     $a2,$a3,[$ap,#8*2]
1199         add     $ap,$ap,#8*4
1200         ldp     $m0,$m1,[$np,#8*0]
1201         ldp     $m2,$m3,[$np,#8*2]
1202         add     $np,$np,#8*4
1203         b       .Loop_mul4x_1st_tail
1204
1205 .align  5
1206 .Lmul4x_proceed:
1207         ldr     $bi,[$bp,#8*4]!         // *++b
1208         adc     $topmost,$carry,xzr
1209         ldp     $a0,$a1,[$t1,#8*0]      // a[0..3]
1210         sub     $np,$np,$num            // rewind np
1211         ldp     $a2,$a3,[$t1,#8*2]
1212         add     $ap,$t1,#8*4
1213
1214         stp     $acc0,$acc1,[$tp,#8*0]  // result!!!
1215         ldp     $acc0,$acc1,[sp,#8*4]   // t[0..3]
1216         stp     $acc2,$acc3,[$tp,#8*2]  // result!!!
1217         ldp     $acc2,$acc3,[sp,#8*6]
1218
1219         ldp     $m0,$m1,[$np,#8*0]      // n[0..3]
1220         mov     $tp,sp
1221         ldp     $m2,$m3,[$np,#8*2]
1222         adds    $np,$np,#8*4            // clear carry bit
1223         mov     $carry,xzr
1224
1225 .align  4
1226 .Loop_mul4x_reduction:
1227         mul     $t0,$a0,$bi             // lo(a[0..3]*b[4])
1228         adc     $carry,$carry,xzr       // modulo-scheduled
1229         mul     $t1,$a1,$bi
1230         add     $cnt,$cnt,#8
1231         mul     $t2,$a2,$bi
1232         and     $cnt,$cnt,#31
1233         mul     $t3,$a3,$bi
1234         adds    $acc0,$acc0,$t0
1235         umulh   $t0,$a0,$bi             // hi(a[0..3]*b[4])
1236         adcs    $acc1,$acc1,$t1
1237         mul     $mi,$acc0,$n0           // t[0]*n0
1238         adcs    $acc2,$acc2,$t2
1239         umulh   $t1,$a1,$bi
1240         adcs    $acc3,$acc3,$t3
1241         umulh   $t2,$a2,$bi
1242         adc     $acc4,xzr,xzr
1243         umulh   $t3,$a3,$bi
1244         ldr     $bi,[$bp,$cnt]          // next b[i]
1245         adds    $acc1,$acc1,$t0
1246         // (*)  mul     $t0,$m0,$mi
1247         str     $mi,[$tp],#8            // put aside t[0]*n0 for tail processing
1248         adcs    $acc2,$acc2,$t1
1249         mul     $t1,$m1,$mi             // lo(n[0..3]*t[0]*n0
1250         adcs    $acc3,$acc3,$t2
1251         mul     $t2,$m2,$mi
1252         adc     $acc4,$acc4,$t3         // can't overflow
1253         mul     $t3,$m3,$mi
1254         // (*)  adds    xzr,$acc0,$t0
1255         subs    xzr,$acc0,#1            // (*)
1256         umulh   $t0,$m0,$mi             // hi(n[0..3]*t[0]*n0
1257         adcs    $acc0,$acc1,$t1
1258         umulh   $t1,$m1,$mi
1259         adcs    $acc1,$acc2,$t2
1260         umulh   $t2,$m2,$mi
1261         adcs    $acc2,$acc3,$t3
1262         umulh   $t3,$m3,$mi
1263         adcs    $acc3,$acc4,$carry
1264         adc     $carry,xzr,xzr
1265         adds    $acc0,$acc0,$t0
1266         adcs    $acc1,$acc1,$t1
1267         adcs    $acc2,$acc2,$t2
1268         adcs    $acc3,$acc3,$t3
1269         //adc   $carry,$carry,xzr
1270         cbnz    $cnt,.Loop_mul4x_reduction
1271
1272         adc     $carry,$carry,xzr
1273         ldp     $t0,$t1,[$tp,#8*4]      // t[4..7]
1274         ldp     $t2,$t3,[$tp,#8*6]
1275         ldp     $a0,$a1,[$ap,#8*0]      // a[4..7]
1276         ldp     $a2,$a3,[$ap,#8*2]
1277         add     $ap,$ap,#8*4
1278         adds    $acc0,$acc0,$t0
1279         adcs    $acc1,$acc1,$t1
1280         adcs    $acc2,$acc2,$t2
1281         adcs    $acc3,$acc3,$t3
1282         //adc   $carry,$carry,xzr
1283
1284         ldr     $mi,[sp]                // t[0]*n0
1285         ldp     $m0,$m1,[$np,#8*0]      // n[4..7]
1286         ldp     $m2,$m3,[$np,#8*2]
1287         add     $np,$np,#8*4
1288
1289 .align  4
1290 .Loop_mul4x_tail:
1291         mul     $t0,$a0,$bi             // lo(a[4..7]*b[4])
1292         adc     $carry,$carry,xzr       // modulo-scheduled
1293         mul     $t1,$a1,$bi
1294         add     $cnt,$cnt,#8
1295         mul     $t2,$a2,$bi
1296         and     $cnt,$cnt,#31
1297         mul     $t3,$a3,$bi
1298         adds    $acc0,$acc0,$t0
1299         umulh   $t0,$a0,$bi             // hi(a[4..7]*b[4])
1300         adcs    $acc1,$acc1,$t1
1301         umulh   $t1,$a1,$bi
1302         adcs    $acc2,$acc2,$t2
1303         umulh   $t2,$a2,$bi
1304         adcs    $acc3,$acc3,$t3
1305         umulh   $t3,$a3,$bi
1306         adc     $acc4,xzr,xzr
1307         ldr     $bi,[$bp,$cnt]          // next b[i]
1308         adds    $acc1,$acc1,$t0
1309         mul     $t0,$m0,$mi             // lo(n[4..7]*t[0]*n0)
1310         adcs    $acc2,$acc2,$t1
1311         mul     $t1,$m1,$mi
1312         adcs    $acc3,$acc3,$t2
1313         mul     $t2,$m2,$mi
1314         adc     $acc4,$acc4,$t3         // can't overflow
1315         mul     $t3,$m3,$mi
1316         adds    $acc0,$acc0,$t0
1317         umulh   $t0,$m0,$mi             // hi(n[4..7]*t[0]*n0)
1318         adcs    $acc1,$acc1,$t1
1319         umulh   $t1,$m1,$mi
1320         adcs    $acc2,$acc2,$t2
1321         umulh   $t2,$m2,$mi
1322         adcs    $acc3,$acc3,$t3
1323         umulh   $t3,$m3,$mi
1324         adcs    $acc4,$acc4,$carry
1325         ldr     $mi,[sp,$cnt]           // next a[0]*n0
1326         adc     $carry,xzr,xzr
1327         str     $acc0,[$tp],#8          // result!!!
1328         adds    $acc0,$acc1,$t0
1329         sub     $t0,$ap_end,$ap         // done yet?
1330         adcs    $acc1,$acc2,$t1
1331         adcs    $acc2,$acc3,$t2
1332         adcs    $acc3,$acc4,$t3
1333         //adc   $carry,$carry,xzr
1334         cbnz    $cnt,.Loop_mul4x_tail
1335
1336         sub     $t1,$np,$num            // rewinded np?
1337         adc     $carry,$carry,xzr
1338         cbz     $t0,.Loop_mul4x_break
1339
1340         ldp     $t0,$t1,[$tp,#8*4]
1341         ldp     $t2,$t3,[$tp,#8*6]
1342         ldp     $a0,$a1,[$ap,#8*0]
1343         ldp     $a2,$a3,[$ap,#8*2]
1344         add     $ap,$ap,#8*4
1345         adds    $acc0,$acc0,$t0
1346         adcs    $acc1,$acc1,$t1
1347         adcs    $acc2,$acc2,$t2
1348         adcs    $acc3,$acc3,$t3
1349         //adc   $carry,$carry,xzr
1350         ldp     $m0,$m1,[$np,#8*0]
1351         ldp     $m2,$m3,[$np,#8*2]
1352         add     $np,$np,#8*4
1353         b       .Loop_mul4x_tail
1354
1355 .align  4
1356 .Loop_mul4x_break:
1357         ldp     $t2,$t3,[x29,#96]       // pull rp and &b[num]
1358         adds    $acc0,$acc0,$topmost
1359         add     $bp,$bp,#8*4            // bp++
1360         adcs    $acc1,$acc1,xzr
1361         sub     $ap,$ap,$num            // rewind ap
1362         adcs    $acc2,$acc2,xzr
1363         stp     $acc0,$acc1,[$tp,#8*0]  // result!!!
1364         adcs    $acc3,$acc3,xzr
1365         ldp     $acc0,$acc1,[sp,#8*4]   // t[0..3]
1366         adc     $topmost,$carry,xzr
1367         stp     $acc2,$acc3,[$tp,#8*2]  // result!!!
1368         cmp     $bp,$t3                 // done yet?
1369         ldp     $acc2,$acc3,[sp,#8*6]
1370         ldp     $m0,$m1,[$t1,#8*0]      // n[0..3]
1371         ldp     $m2,$m3,[$t1,#8*2]
1372         add     $np,$t1,#8*4
1373         b.eq    .Lmul4x_post
1374
1375         ldr     $bi,[$bp]
1376         ldp     $a0,$a1,[$ap,#8*0]      // a[0..3]
1377         ldp     $a2,$a3,[$ap,#8*2]
1378         adds    $ap,$ap,#8*4            // clear carry bit
1379         mov     $carry,xzr
1380         mov     $tp,sp
1381         b       .Loop_mul4x_reduction
1382
1383 .align  4
1384 .Lmul4x_post:
1385         // Final step. We see if result is larger than modulus, and
1386         // if it is, subtract the modulus. But comparison implies
1387         // subtraction. So we subtract modulus, see if it borrowed,
1388         // and conditionally copy original value.
1389         mov     $rp,$t2
1390         mov     $ap_end,$t2             // $rp copy
1391         subs    $t0,$acc0,$m0
1392         add     $tp,sp,#8*8
1393         sbcs    $t1,$acc1,$m1
1394         sub     $cnt,$num,#8*4
1395
1396 .Lmul4x_sub:
1397         sbcs    $t2,$acc2,$m2
1398         ldp     $m0,$m1,[$np,#8*0]
1399         sub     $cnt,$cnt,#8*4
1400         ldp     $acc0,$acc1,[$tp,#8*0]
1401         sbcs    $t3,$acc3,$m3
1402         ldp     $m2,$m3,[$np,#8*2]
1403         add     $np,$np,#8*4
1404         ldp     $acc2,$acc3,[$tp,#8*2]
1405         add     $tp,$tp,#8*4
1406         stp     $t0,$t1,[$rp,#8*0]
1407         sbcs    $t0,$acc0,$m0
1408         stp     $t2,$t3,[$rp,#8*2]
1409         add     $rp,$rp,#8*4
1410         sbcs    $t1,$acc1,$m1
1411         cbnz    $cnt,.Lmul4x_sub
1412
1413         sbcs    $t2,$acc2,$m2
1414          mov    $tp,sp
1415          add    $ap,sp,#8*4
1416          ldp    $a0,$a1,[$ap_end,#8*0]
1417         sbcs    $t3,$acc3,$m3
1418         stp     $t0,$t1,[$rp,#8*0]
1419          ldp    $a2,$a3,[$ap_end,#8*2]
1420         stp     $t2,$t3,[$rp,#8*2]
1421          ldp    $acc0,$acc1,[$ap,#8*0]
1422          ldp    $acc2,$acc3,[$ap,#8*2]
1423         sbcs    xzr,$topmost,xzr        // did it borrow?
1424         ldr     x30,[x29,#8]            // pull return address
1425
1426         sub     $cnt,$num,#8*4
1427 .Lmul4x_cond_copy:
1428         sub     $cnt,$cnt,#8*4
1429         csel    $t0,$acc0,$a0,lo
1430          stp    xzr,xzr,[$tp,#8*0]
1431         csel    $t1,$acc1,$a1,lo
1432         ldp     $a0,$a1,[$ap_end,#8*4]
1433         ldp     $acc0,$acc1,[$ap,#8*4]
1434         csel    $t2,$acc2,$a2,lo
1435          stp    xzr,xzr,[$tp,#8*2]
1436          add    $tp,$tp,#8*4
1437         csel    $t3,$acc3,$a3,lo
1438         ldp     $a2,$a3,[$ap_end,#8*6]
1439         ldp     $acc2,$acc3,[$ap,#8*6]
1440         add     $ap,$ap,#8*4
1441         stp     $t0,$t1,[$ap_end,#8*0]
1442         stp     $t2,$t3,[$ap_end,#8*2]
1443         add     $ap_end,$ap_end,#8*4
1444         cbnz    $cnt,.Lmul4x_cond_copy
1445
1446         csel    $t0,$acc0,$a0,lo
1447          stp    xzr,xzr,[$tp,#8*0]
1448         csel    $t1,$acc1,$a1,lo
1449          stp    xzr,xzr,[$tp,#8*2]
1450         csel    $t2,$acc2,$a2,lo
1451          stp    xzr,xzr,[$tp,#8*3]
1452         csel    $t3,$acc3,$a3,lo
1453          stp    xzr,xzr,[$tp,#8*4]
1454         stp     $t0,$t1,[$ap_end,#8*0]
1455         stp     $t2,$t3,[$ap_end,#8*2]
1456
1457         b       .Lmul4x_done
1458
1459 .align  4
1460 .Lmul4x4_post_condition:
1461         adc     $carry,$carry,xzr
1462         ldr     $ap,[x29,#96]           // pull rp
1463         // $acc0-3,$carry hold result, $m0-7 hold modulus
1464         subs    $a0,$acc0,$m0
1465         ldr     x30,[x29,#8]            // pull return address
1466         sbcs    $a1,$acc1,$m1
1467          stp    xzr,xzr,[sp,#8*0]
1468         sbcs    $a2,$acc2,$m2
1469          stp    xzr,xzr,[sp,#8*2]
1470         sbcs    $a3,$acc3,$m3
1471          stp    xzr,xzr,[sp,#8*4]
1472         sbcs    xzr,$carry,xzr          // did it borrow?
1473          stp    xzr,xzr,[sp,#8*6]
1474
1475         // $a0-3 hold result-modulus
1476         csel    $a0,$acc0,$a0,lo
1477         csel    $a1,$acc1,$a1,lo
1478         csel    $a2,$acc2,$a2,lo
1479         csel    $a3,$acc3,$a3,lo
1480         stp     $a0,$a1,[$ap,#8*0]
1481         stp     $a2,$a3,[$ap,#8*2]
1482
1483 .Lmul4x_done:
1484         ldp     x19,x20,[x29,#16]
1485         mov     sp,x29
1486         ldp     x21,x22,[x29,#32]
1487         mov     x0,#1
1488         ldp     x23,x24,[x29,#48]
1489         ldp     x25,x26,[x29,#64]
1490         ldp     x27,x28,[x29,#80]
1491         ldr     x29,[sp],#128
1492         ret
1493 .size   __bn_mul4x_mont,.-__bn_mul4x_mont
1494 ___
1495 }
1496 $code.=<<___;
1497 .asciz  "Montgomery Multiplication for ARMv8, CRYPTOGAMS by <appro\@openssl.org>"
1498 .align  4
1499 ___
1500
1501 print $code;
1502
1503 close STDOUT;