ec/asm/p256_beeu-armv8-asm.pl

# Copyright Amazon.com Inc. or its affiliates. All Rights Reserved.
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
# SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
# OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
# CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
#
#
# This code is based on p256_beeu-x86_64-asm.pl (which is based on BN_mod_inverse_odd).
#

# The first two arguments should always be the flavour and output file path.
if ($#ARGV < 1) { die "Not enough arguments provided.
  Two arguments are necessary: the flavour and the output file path."; }

$flavour = shift;
$output  = shift;

$0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
( $xlate="${dir}arm-xlate.pl" and -f $xlate ) or
( $xlate="${dir}../../../perlasm/arm-xlate.pl" and -f $xlate) or
die "can't locate arm-xlate.pl";

open OUT,"| \"$^X\" $xlate $flavour $output";
*STDOUT=*OUT;
#############################################################################
# extern int beeu_mod_inverse_vartime(BN_ULONG out[P256_LIMBS],
#                                     BN_ULONG a[P256_LIMBS],
#                                     BN_ULONG n[P256_LIMBS]);
#
# (Binary Extended GCD (Euclidean) Algorithm.
#  See A. Menezes, P. vanOorschot, and S. Vanstone's Handbook of Applied Cryptography,
#  Chapter 14, Algorithm 14.61 and Note 14.64
#  http://cacr.uwaterloo.ca/hac/about/chap14.pdf)

# Assumption 1: n is odd for the BEEU
# Assumption 2: 1 < a < n < 2^256

# Details
# The inverse of x modulo y can be calculated using Alg. 14.61, where "a" would be that inverse.
# In other words,
# ax == 1 (mod y) (where the symbol “==“ denotes ”congruent“)
#  a == x^{-1} (mod y)
#
# It can be shown that throughout all the iterations of the algorithm, the following holds:
#    u = Ax + By
#    v = Cx + Dy
# The values B and D are not of interest in this case, so they need not be computed by the algorithm.
# This means the following congruences hold through the iterations of the algorithm.
#    Ax == u (mod y)
#    Cx == v (mod y)

# Now we will modify the notation to match that of BN_mod_inverse_odd()
# on which beeu_mod_inverse_vartime() in `p256_beeu-x86_64-asm` is based.
# In those functions:
#    x, y -> a, n
#    u, v -> B, A
#    A, C -> X, Y’, where Y’ = -Y
# Hence, the following holds throughout the algorithm iterations
#    Xa == B (mod n)
#   -Ya == A (mod n)
#
# Same algorithm in Python:
# def beeu(a, n):
#     X = 1
#     Y = 0
#     B = a
#     A = n
#     while (B != 0):
#         while (B % 2) == 0:
#             B >>= 1
#             if (X % 2) == 1:
#                 X = X + n
#             X >>= 1
#         while (A % 2) == 0:
#             A >>= 1
#             if (Y % 2) == 1:
#                 Y = Y + n
#             Y >>= 1
#         if (B >= A):
#             B = B - A
#             X = X + Y
#         else:
#             A = A - B
#             Y = Y + X
#     if (A != 1):
#         # error
#         return 0
#     else:
#         while (Y > n):
#             Y = Y - n
#         Y = n - Y
#         return Y


# For the internal variables,
# x0-x2, x30 are used to hold the modulus n. The input parameters passed in
# x1,x2 are copied first before corrupting them. x0 (out) is stored on the stack.
# x3-x7 are used for parameters, which is not the case in this function, so they are corruptible
# x8 is corruptible here
# (the function doesn't return a struct, hence x8 doesn't contain a passed-in address
#  for that struct).
# x9-x15 are corruptible registers
# x19-x28 are callee-saved registers

# X/Y will hold the inverse parameter
# Assumption: a,n,X,Y < 2^(256)
# Initially, X := 1, Y := 0
#            A := n, B := a

# Function parameters (as per the Procedure Call Standard)
my($out, $a_in, $n_in)=map("x$_",(0..2));
# Internal variables
my($n0, $n1, $n2, $n3)=map("x$_",(0..2,30));
my($x0, $x1, $x2, $x3, $x4)=map("x$_",(3..7));
my($y0, $y1, $y2, $y3, $y4)=map("x$_",(8..12));
my($shift)=("x13");
my($t0, $t1, $t2, $t3)=map("x$_",(14,15,19,20));
my($a0, $a1, $a2, $a3)=map("x$_",(21..24));
my($b0, $b1, $b2, $b3)=map("x$_",(25..28));

# if B == 0, jump to end of loop
sub TEST_B_ZERO {
  return <<___;
    orr     $t0, $b0, $b1
    orr     $t0, $t0, $b2

    // reverse the bit order of $b0. This is needed for clz after this macro
    rbit     $t1, $b0

    orr     $t0, $t0, $b3
    cbz     $t0,.Lbeeu_loop_end
___
}

# Shift right by 1 bit, adding the modulus first if the variable is odd
# if least_sig_bit(var0) == 0,
#     goto shift1_<ctr>
# else
#     add n and goto shift1_<ctr>
# Prerequisite: t0 = 0
$g_next_label = 0;
sub SHIFT1 {
  my ($var0, $var1, $var2, $var3, $var4) = @_;
  my $label = ".Lshift1_${g_next_label}";
  $g_next_label++;
  return <<___;
    tbz     $var0, #0, $label
    adds    $var0, $var0, $n0
    adcs    $var1, $var1, $n1
    adcs    $var2, $var2, $n2
    adcs    $var3, $var3, $n3
    adc     $var4, $var4, $t0
$label:
    // var0 := [var1|var0]<64..1>;
    // i.e. concatenate var1 and var0,
    //      extract bits <64..1> from the resulting 128-bit value
    //      and put them in var0
    extr    $var0, $var1, $var0, #1
    extr    $var1, $var2, $var1, #1
    extr    $var2, $var3, $var2, #1
    extr    $var3, $var4, $var3, #1
    lsr     $var4, $var4, #1
___
}

# compilation by clang 10.0.0 with -O2/-O3 of
#      a[0] = (a[0] >> count) | (a[1] << (64-count));
#      a[1] = (a[1] >> count) | (a[2] << (64-count));
#      a[2] = (a[2] >> count) | (a[3] << (64-count));
#      a[3] >>= count;
# Note: EXTR instruction used in SHIFT1 is similar to x86_64's SHRDQ
# except that the second source operand of EXTR is only immediate;
# that's why it cannot be used here where $shift is a variable
#
# In the following,
# t0 := 0 - shift
#
# then var0, for example, will be shifted right as follows:
# var0 := (var0 >> (uint(shift) mod 64)) | (var1 << (uint(t0) mod 64))
# "uint() mod 64" is from the definition of LSL and LSR instructions.
#
# What matters here is the order of instructions relative to certain other
# instructions, i.e.
# - lsr and lsl must precede orr of the corresponding registers.
# - lsl must preced the lsr of the same register afterwards.
# The chosen order of the instructions overall is to try and maximize
# the pipeline usage.
sub SHIFT256 {
  my ($var0, $var1, $var2, $var3) = @_;
  return <<___;
    neg $t0, $shift
    lsr $var0, $var0, $shift
    lsl $t1, $var1, $t0

    lsr $var1, $var1, $shift
    lsl $t2, $var2, $t0

    orr $var0, $var0, $t1

    lsr $var2, $var2, $shift
    lsl $t3, $var3, $t0

    orr $var1, $var1, $t2

    lsr $var3, $var3, $shift

    orr $var2, $var2, $t3
___
}

$code.=<<___;
#include "openssl/arm_arch.h"

.text
.globl  beeu_mod_inverse_vartime
.type   beeu_mod_inverse_vartime, %function
.align  4
beeu_mod_inverse_vartime:
    // Reserve enough space for 14 8-byte registers on the stack
    // in the first stp call for x29, x30.
    // Then store the remaining callee-saved registers.
    //
    //    | x29 | x30 | x19 | x20 | ... | x27 | x28 |  x0 |  x2 |
    //    ^                                                     ^
    //    sp  <------------------- 112 bytes ----------------> old sp
    //   x29 (FP)
    //
    AARCH64_SIGN_LINK_REGISTER
    stp     x29,x30,[sp,#-112]!
    add     x29,sp,#0
    stp     x19,x20,[sp,#16]
    stp     x21,x22,[sp,#32]
    stp     x23,x24,[sp,#48]
    stp     x25,x26,[sp,#64]
    stp     x27,x28,[sp,#80]
    stp     x0,x2,[sp,#96]

    // B = b3..b0 := a
    ldp     $b0,$b1,[$a_in]
    ldp     $b2,$b3,[$a_in,#16]

    // n3..n0 := n
    // Note: the value of input params are changed in the following.
    ldp     $n0,$n1,[$n_in]
    ldp     $n2,$n3,[$n_in,#16]

    // A = a3..a0 := n
    mov     $a0, $n0
    mov     $a1, $n1
    mov     $a2, $n2
    mov     $a3, $n3

    // X = x4..x0 := 1
    mov     $x0, #1
    eor     $x1, $x1, $x1
    eor     $x2, $x2, $x2
    eor     $x3, $x3, $x3
    eor     $x4, $x4, $x4

    // Y = y4..y0 := 0
    eor     $y0, $y0, $y0
    eor     $y1, $y1, $y1
    eor     $y2, $y2, $y2
    eor     $y3, $y3, $y3
    eor     $y4, $y4, $y4

.Lbeeu_loop:
    // if B == 0, jump to .Lbeeu_loop_end
    ${\TEST_B_ZERO}

    // 0 < B < |n|,
    // 0 < A <= |n|,
    // (1)      X*a  ==  B   (mod |n|),
    // (2) (-1)*Y*a  ==  A   (mod |n|)

    // Now divide B by the maximum possible power of two in the
    // integers, and divide X by the same value mod |n|.
    // When we're done, (1) still holds.

    // shift := number of trailing 0s in $b0
    // (      = number of leading 0s in $t1; see the "rbit" instruction in TEST_B_ZERO)
    clz     $shift, $t1

    // If there is no shift, goto shift_A_Y
    cbz     $shift, .Lbeeu_shift_A_Y

    // Shift B right by "$shift" bits
    ${\SHIFT256($b0, $b1, $b2, $b3)}

    // Shift X right by "$shift" bits, adding n whenever X becomes odd.
    // $shift--;
    // $t0 := 0; needed in the addition to the most significant word in SHIFT1
    eor     $t0, $t0, $t0
.Lbeeu_shift_loop_X:
    ${\SHIFT1($x0, $x1, $x2, $x3, $x4)}
    subs    $shift, $shift, #1
    bne     .Lbeeu_shift_loop_X

    // Note: the steps above perform the same sequence as in p256_beeu-x86_64-asm.pl
    // with the following differences:
    // - "$shift" is set directly to the number of trailing 0s in B
    //   (using rbit and clz instructions)
    // - The loop is only used to call SHIFT1(X)
    //   and $shift is decreased while executing the X loop.
    // - SHIFT256(B, $shift) is performed before right-shifting X; they are independent

.Lbeeu_shift_A_Y:
    // Same for A and Y.
    // Afterwards, (2) still holds.
    // Reverse the bit order of $a0
    // $shift := number of trailing 0s in $a0 (= number of leading 0s in $t1)
    rbit    $t1, $a0
    clz     $shift, $t1

    // If there is no shift, goto |B-A|, X+Y update
    cbz     $shift, .Lbeeu_update_B_X_or_A_Y

    // Shift A right by "$shift" bits
    ${\SHIFT256($a0, $a1, $a2, $a3)}

    // Shift Y right by "$shift" bits, adding n whenever Y becomes odd.
    // $shift--;
    // $t0 := 0; needed in the addition to the most significant word in SHIFT1
    eor     $t0, $t0, $t0
.Lbeeu_shift_loop_Y:
    ${\SHIFT1($y0, $y1, $y2, $y3, $y4)}
    subs    $shift, $shift, #1
    bne     .Lbeeu_shift_loop_Y

.Lbeeu_update_B_X_or_A_Y:
    // Try T := B - A; if cs, continue with B > A (cs: carry set = no borrow)
    // Note: this is a case of unsigned arithmetic, where T fits in 4 64-bit words
    //       without taking a sign bit if generated. The lack of a carry would
    //       indicate a negative result. See, for example,
    //       https://community.arm.com/developer/ip-products/processors/b/processors-ip-blog/posts/condition-codes-1-condition-flags-and-codes
    subs    $t0, $b0, $a0
    sbcs    $t1, $b1, $a1
    sbcs    $t2, $b2, $a2
    sbcs    $t3, $b3, $a3
    bcs     .Lbeeu_B_greater_than_A

    // Else A > B =>
    // A := A - B; Y := Y + X; goto beginning of the loop
    subs    $a0, $a0, $b0
    sbcs    $a1, $a1, $b1
    sbcs    $a2, $a2, $b2
    sbcs    $a3, $a3, $b3

    adds    $y0, $y0, $x0
    adcs    $y1, $y1, $x1
    adcs    $y2, $y2, $x2
    adcs    $y3, $y3, $x3
    adc     $y4, $y4, $x4
    b       .Lbeeu_loop

.Lbeeu_B_greater_than_A:
    // Continue with B > A =>
    // B := B - A; X := X + Y; goto beginning of the loop
    mov     $b0, $t0
    mov     $b1, $t1
    mov     $b2, $t2
    mov     $b3, $t3

    adds    $x0, $x0, $y0
    adcs    $x1, $x1, $y1
    adcs    $x2, $x2, $y2
    adcs    $x3, $x3, $y3
    adc     $x4, $x4, $y4
    b       .Lbeeu_loop

.Lbeeu_loop_end:
    // The Euclid's algorithm loop ends when A == gcd(a,n);
    // this would be 1, when a and n are co-prime (i.e. do not have a common factor).
    // Since (-1)*Y*a == A (mod |n|), Y>0
    // then out = -Y mod n

    // Verify that A = 1 ==> (-1)*Y*a = A = 1  (mod |n|)
    // Is A-1 == 0?
    // If not, fail.
    sub     $t0, $a0, #1
    orr     $t0, $t0, $a1
    orr     $t0, $t0, $a2
    orr     $t0, $t0, $a3
    cbnz    $t0, .Lbeeu_err

    // If Y>n ==> Y:=Y-n
.Lbeeu_reduction_loop:
    // x_i := y_i - n_i (X is no longer needed, use it as temp)
    // ($t0 = 0 from above)
    subs    $x0, $y0, $n0
    sbcs    $x1, $y1, $n1
    sbcs    $x2, $y2, $n2
    sbcs    $x3, $y3, $n3
    sbcs    $x4, $y4, $t0

    // If result is non-negative (i.e., cs = carry set = no borrow),
    // y_i := x_i; goto reduce again
    // else
    // y_i := y_i; continue
    csel    $y0, $x0, $y0, cs
    csel    $y1, $x1, $y1, cs
    csel    $y2, $x2, $y2, cs
    csel    $y3, $x3, $y3, cs
    csel    $y4, $x4, $y4, cs
    bcs     .Lbeeu_reduction_loop

    // Now Y < n (Y cannot be equal to n, since the inverse cannot be 0)
    // out = -Y = n-Y
    subs    $y0, $n0, $y0
    sbcs    $y1, $n1, $y1
    sbcs    $y2, $n2, $y2
    sbcs    $y3, $n3, $y3

    // Save Y in output (out (x0) was saved on the stack)
    ldr     x3, [sp,#96]
    stp     $y0, $y1, [x3]
    stp     $y2, $y3, [x3,#16]
    // return 1 (success)
    mov     x0, #1
    b       .Lbeeu_finish

.Lbeeu_err:
    // return 0 (error)
    eor     x0, x0, x0

.Lbeeu_finish:
    // Restore callee-saved registers, except x0, x2
    add     sp,x29,#0
    ldp     x19,x20,[sp,#16]
    ldp     x21,x22,[sp,#32]
    ldp     x23,x24,[sp,#48]
    ldp     x25,x26,[sp,#64]
    ldp     x27,x28,[sp,#80]
    ldp     x29,x30,[sp],#112

    AARCH64_VALIDATE_LINK_REGISTER
    ret
.size beeu_mod_inverse_vartime,.-beeu_mod_inverse_vartime
___


foreach (split("\n",$code)) {
    s/\`([^\`]*)\`/eval $1/ge;

    print $_,"\n";
}
close STDOUT or die "error closing STDOUT: $!"; # enforce flush