fe_amd64_asm.go

     1  // Copyright (c) 2021 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package main
     6  
     7  import (
     8  	"fmt"
     9  
    10  	. "github.com/mmcloughlin/avo/build"
    11  	. "github.com/mmcloughlin/avo/gotypes"
    12  	. "github.com/mmcloughlin/avo/operand"
    13  	. "github.com/mmcloughlin/avo/reg"
    14  )
    15  
    16  //go:generate go run . -out ../fe_amd64.s -stubs ../fe_amd64.go -pkg field
    17  
    18  func main() {
    19  	Package("crypto/internal/fips140/edwards25519/field")
    20  	ConstraintExpr("!purego")
    21  	feMul()
    22  	Generate()
    23  }
    24  
    25  type namedComponent struct {
    26  	Component
    27  	name string
    28  }
    29  
    30  func (c namedComponent) String() string { return c.name }
    31  
    32  type uint128 struct {
    33  	name   string
    34  	hi, lo GPVirtual
    35  }
    36  
    37  func (c uint128) String() string { return c.name }
    38  
    39  func feMul() {
    40  	TEXT("feMul", NOSPLIT, "func(out, a, b *Element)")
    41  	Doc("feMul sets out = a * b. It works like feMulGeneric.")
    42  	Pragma("noescape")
    43  
    44  	a := Dereference(Param("a"))
    45  	a0 := namedComponent{a.Field("l0"), "a0"}
    46  	a1 := namedComponent{a.Field("l1"), "a1"}
    47  	a2 := namedComponent{a.Field("l2"), "a2"}
    48  	a3 := namedComponent{a.Field("l3"), "a3"}
    49  	a4 := namedComponent{a.Field("l4"), "a4"}
    50  
    51  	b := Dereference(Param("b"))
    52  	b0 := namedComponent{b.Field("l0"), "b0"}
    53  	b1 := namedComponent{b.Field("l1"), "b1"}
    54  	b2 := namedComponent{b.Field("l2"), "b2"}
    55  	b3 := namedComponent{b.Field("l3"), "b3"}
    56  	b4 := namedComponent{b.Field("l4"), "b4"}
    57  
    58  	// r0 = a0×b0 + 19×(a1×b4 + a2×b3 + a3×b2 + a4×b1)
    59  	r0 := uint128{"r0", GP64(), GP64()}
    60  	mul64(r0, 1, a0, b0)
    61  	addMul64(r0, 19, a1, b4)
    62  	addMul64(r0, 19, a2, b3)
    63  	addMul64(r0, 19, a3, b2)
    64  	addMul64(r0, 19, a4, b1)
    65  
    66  	// r1 = a0×b1 + a1×b0 + 19×(a2×b4 + a3×b3 + a4×b2)
    67  	r1 := uint128{"r1", GP64(), GP64()}
    68  	mul64(r1, 1, a0, b1)
    69  	addMul64(r1, 1, a1, b0)
    70  	addMul64(r1, 19, a2, b4)
    71  	addMul64(r1, 19, a3, b3)
    72  	addMul64(r1, 19, a4, b2)
    73  
    74  	// r2 = a0×b2 + a1×b1 + a2×b0 + 19×(a3×b4 + a4×b3)
    75  	r2 := uint128{"r2", GP64(), GP64()}
    76  	mul64(r2, 1, a0, b2)
    77  	addMul64(r2, 1, a1, b1)
    78  	addMul64(r2, 1, a2, b0)
    79  	addMul64(r2, 19, a3, b4)
    80  	addMul64(r2, 19, a4, b3)
    81  
    82  	// r3 = a0×b3 + a1×b2 + a2×b1 + a3×b0 + 19×a4×b4
    83  	r3 := uint128{"r3", GP64(), GP64()}
    84  	mul64(r3, 1, a0, b3)
    85  	addMul64(r3, 1, a1, b2)
    86  	addMul64(r3, 1, a2, b1)
    87  	addMul64(r3, 1, a3, b0)
    88  	addMul64(r3, 19, a4, b4)
    89  
    90  	// r4 = a0×b4 + a1×b3 + a2×b2 + a3×b1 + a4×b0
    91  	r4 := uint128{"r4", GP64(), GP64()}
    92  	mul64(r4, 1, a0, b4)
    93  	addMul64(r4, 1, a1, b3)
    94  	addMul64(r4, 1, a2, b2)
    95  	addMul64(r4, 1, a3, b1)
    96  	addMul64(r4, 1, a4, b0)
    97  
    98  	Comment("First reduction chain")
    99  	maskLow51Bits := GP64()
   100  	MOVQ(Imm((1<<51)-1), maskLow51Bits)
   101  	c0, r0lo := shiftRightBy51(&r0)
   102  	c1, r1lo := shiftRightBy51(&r1)
   103  	c2, r2lo := shiftRightBy51(&r2)
   104  	c3, r3lo := shiftRightBy51(&r3)
   105  	c4, r4lo := shiftRightBy51(&r4)
   106  	maskAndAdd(r0lo, maskLow51Bits, c4, 19)
   107  	maskAndAdd(r1lo, maskLow51Bits, c0, 1)
   108  	maskAndAdd(r2lo, maskLow51Bits, c1, 1)
   109  	maskAndAdd(r3lo, maskLow51Bits, c2, 1)
   110  	maskAndAdd(r4lo, maskLow51Bits, c3, 1)
   111  
   112  	Comment("Second reduction chain (carryPropagate)")
   113  	// c0 = r0 >> 51
   114  	MOVQ(r0lo, c0)
   115  	SHRQ(Imm(51), c0)
   116  	// c1 = r1 >> 51
   117  	MOVQ(r1lo, c1)
   118  	SHRQ(Imm(51), c1)
   119  	// c2 = r2 >> 51
   120  	MOVQ(r2lo, c2)
   121  	SHRQ(Imm(51), c2)
   122  	// c3 = r3 >> 51
   123  	MOVQ(r3lo, c3)
   124  	SHRQ(Imm(51), c3)
   125  	// c4 = r4 >> 51
   126  	MOVQ(r4lo, c4)
   127  	SHRQ(Imm(51), c4)
   128  	maskAndAdd(r0lo, maskLow51Bits, c4, 19)
   129  	maskAndAdd(r1lo, maskLow51Bits, c0, 1)
   130  	maskAndAdd(r2lo, maskLow51Bits, c1, 1)
   131  	maskAndAdd(r3lo, maskLow51Bits, c2, 1)
   132  	maskAndAdd(r4lo, maskLow51Bits, c3, 1)
   133  
   134  	Comment("Store output")
   135  	out := Dereference(Param("out"))
   136  	Store(r0lo, out.Field("l0"))
   137  	Store(r1lo, out.Field("l1"))
   138  	Store(r2lo, out.Field("l2"))
   139  	Store(r3lo, out.Field("l3"))
   140  	Store(r4lo, out.Field("l4"))
   141  
   142  	RET()
   143  }
   144  
   145  // mul64 sets r to i * aX * bX.
   146  func mul64(r uint128, i int, aX, bX namedComponent) {
   147  	switch i {
   148  	case 1:
   149  		Comment(fmt.Sprintf("%s = %s×%s", r, aX, bX))
   150  		Load(aX, RAX)
   151  	case 2:
   152  		Comment(fmt.Sprintf("%s = 2×%s×%s", r, aX, bX))
   153  		Load(aX, RAX)
   154  		SHLQ(Imm(1), RAX)
   155  	default:
   156  		panic("unsupported i value")
   157  	}
   158  	MULQ(mustAddr(bX)) // RDX, RAX = RAX * bX
   159  	MOVQ(RAX, r.lo)
   160  	MOVQ(RDX, r.hi)
   161  }
   162  
   163  // addMul64 sets r to r + i * aX * bX.
   164  func addMul64(r uint128, i uint64, aX, bX namedComponent) {
   165  	switch i {
   166  	case 1:
   167  		Comment(fmt.Sprintf("%s += %s×%s", r, aX, bX))
   168  		Load(aX, RAX)
   169  	case 2:
   170  		Comment(fmt.Sprintf("%s += %d×%s×%s", r, i, aX, bX))
   171  		Load(aX, RAX)
   172  		SHLQ(U8(1), RAX)
   173  	case 19:
   174  		Comment(fmt.Sprintf("%s += %d×%s×%s", r, i, aX, bX))
   175  		// 19 * v ==> v + (v+v*8)*2
   176  		tmp := Load(aX, GP64())
   177  		LEAQ(Mem{Base: tmp, Index: tmp, Scale: 8}, RAX)
   178  		LEAQ(Mem{Base: tmp, Index: RAX, Scale: 2}, RAX)
   179  	case 38:
   180  		Comment(fmt.Sprintf("%s += %d×%s×%s", r, i, aX, bX))
   181  		// 38 * v ==> (v + (v+v*8)*2) * 2
   182  		tmp := Load(aX, GP64())
   183  		LEAQ(Mem{Base: tmp, Index: tmp, Scale: 8}, RAX)
   184  		LEAQ(Mem{Base: tmp, Index: RAX, Scale: 2}, RAX)
   185  		SHLQ(U8(1), RAX)
   186  	default:
   187  		Comment(fmt.Sprintf("%s += %d×%s×%s", r, i, aX, bX))
   188  		IMUL3Q(Imm(i), Load(aX, GP64()), RAX)
   189  	}
   190  	MULQ(mustAddr(bX)) // RDX, RAX = RAX * bX
   191  	ADDQ(RAX, r.lo)
   192  	ADCQ(RDX, r.hi)
   193  }
   194  
   195  // shiftRightBy51 returns r >> 51 and r.lo.
   196  //
   197  // After this function is called, the uint128 may not be used anymore.
   198  func shiftRightBy51(r *uint128) (out, lo GPVirtual) {
   199  	out = r.hi
   200  	lo = r.lo
   201  	SHLQ(Imm(64-51), r.lo, r.hi)
   202  	r.lo, r.hi = nil, nil // make sure the uint128 is unusable
   203  	return
   204  }
   205  
   206  // maskAndAdd sets r = r&mask + c*i.
   207  func maskAndAdd(r, mask, c GPVirtual, i uint64) {
   208  	ANDQ(mask, r)
   209  	if i != 1 {
   210  		IMUL3Q(Imm(i), c, c)
   211  	}
   212  	ADDQ(c, r)
   213  }
   214  
   215  func mustAddr(c Component) Op {
   216  	b, err := c.Resolve()
   217  	if err != nil {
   218  		panic(err)
   219  	}
   220  	return b.Addr
   221  }
   222
View as plain text