1// Copyright 2020 ConsenSys Software Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15// Package amd64 contains syntactic sugar to generate amd64 assembly code
16package amd64
17
18import (
19	"fmt"
20	"io"
21	"strings"
22
23	"github.com/consensys/bavard"
24
25	"github.com/consensys/bavard/amd64"
26	"github.com/consensys/gnark-crypto/field"
27)
28
29const SmallModulus = 6
30
31func NewFFAmd64(w io.Writer, F *field.Field) *FFAmd64 {
32	return &FFAmd64{F, amd64.NewAmd64(w), 0, 0}
33}
34
35type FFAmd64 struct {
36	*field.Field
37	*amd64.Amd64
38	nbElementsOnStack int
39	maxOnStack        int
40}
41
42func (f *FFAmd64) StackSize(maxNbRegistersNeeded, nbRegistersReserved, minStackSize int) int {
43	got := amd64.NbRegisters - nbRegistersReserved
44	r := got - maxNbRegistersNeeded
45	if r >= 0 {
46		return minStackSize
47	}
48	r *= -8
49	return max(r, minStackSize)
50}
51
52func max(a, b int) int {
53	if a > b {
54		return a
55	}
56	return b
57}
58
59func (f *FFAmd64) AssertCleanStack(reservedStackSize, minStackSize int) {
60	if f.nbElementsOnStack != 0 {
61		panic("missing f.Push stack elements")
62	}
63	if reservedStackSize < minStackSize {
64		panic("invalid minStackSize or reservedStackSize")
65	}
66	usedStackSize := f.maxOnStack * 8
67	if usedStackSize > reservedStackSize {
68		panic("using more stack size than reserved")
69	} else if max(usedStackSize, minStackSize) < reservedStackSize {
70		// this panic is for dev purposes as this may be by design for aligment
71		panic("reserved more stack size than needed")
72	}
73
74	f.maxOnStack = 0
75}
76
77func (f *FFAmd64) Push(registers *amd64.Registers, rIn ...amd64.Register) {
78	for _, r := range rIn {
79		if strings.HasPrefix(string(r), "s") {
80			// it's on the stack, decrease the offset
81			f.nbElementsOnStack--
82			continue
83		}
84		registers.Push(r)
85	}
86}
87
88func (f *FFAmd64) Pop(registers *amd64.Registers, forceStack ...bool) amd64.Register {
89	if registers.Available() >= 1 && !(len(forceStack) > 0 && forceStack[0]) {
90		return registers.Pop()
91	}
92	r := amd64.Register(fmt.Sprintf("s%d-%d(SP)", f.nbElementsOnStack, 8+f.nbElementsOnStack*8))
93	f.nbElementsOnStack++
94	if f.nbElementsOnStack > f.maxOnStack {
95		f.maxOnStack = f.nbElementsOnStack
96	}
97	return r
98}
99
100func (f *FFAmd64) PopN(registers *amd64.Registers, forceStack ...bool) []amd64.Register {
101	if len(forceStack) > 0 && forceStack[0] {
102		nbStack := f.NbWords
103		var u []amd64.Register
104
105		for i := f.nbElementsOnStack; i < nbStack+f.nbElementsOnStack; i++ {
106			u = append(u, amd64.Register(fmt.Sprintf("s%d-%d(SP)", i, 8+i*8)))
107		}
108		f.nbElementsOnStack += nbStack
109		if f.nbElementsOnStack > f.maxOnStack {
110			f.maxOnStack = f.nbElementsOnStack
111		}
112		return u
113	}
114	if registers.Available() >= f.NbWords {
115		return registers.PopN(f.NbWords)
116	}
117	nbStack := f.NbWords - registers.Available()
118	u := registers.PopN(registers.Available())
119
120	for i := f.nbElementsOnStack; i < nbStack+f.nbElementsOnStack; i++ {
121		u = append(u, amd64.Register(fmt.Sprintf("s%d-%d(SP)", i, 8+i*8)))
122	}
123	f.nbElementsOnStack += nbStack
124	if f.nbElementsOnStack > f.maxOnStack {
125		f.maxOnStack = f.nbElementsOnStack
126	}
127	return u
128}
129
130func (f *FFAmd64) qAt(index int) string {
131	return fmt.Sprintf("q<>+%d(SB)", index*8)
132}
133
134func (f *FFAmd64) qInv0() string {
135	return "qInv0<>(SB)"
136}
137
138// Generate generates assembly code for the base field provided to goff
139// see internal/templates/ops*
140func Generate(w io.Writer, F *field.Field) error {
141	f := NewFFAmd64(w, F)
142	f.WriteLn(bavard.Apache2Header("ConsenSys Software Inc.", 2020))
143
144	f.WriteLn("#include \"textflag.h\"")
145	f.WriteLn("#include \"funcdata.h\"")
146	f.WriteLn("")
147
148	f.GenerateDefines()
149
150	// add
151	f.generateAdd()
152
153	// sub
154	f.generateSub()
155
156	// double
157	f.generateDouble()
158
159	// neg
160	f.generateNeg()
161
162	// reduce
163	f.generateReduce()
164
165	// mul by constants
166	f.generateMulBy3()
167	f.generateMulBy5()
168	f.generateMulBy13()
169
170	return nil
171}
172
173func GenerateMul(w io.Writer, F *field.Field) error {
174	f := NewFFAmd64(w, F)
175	f.WriteLn(bavard.Apache2Header("ConsenSys Software Inc.", 2020))
176
177	f.WriteLn("#include \"textflag.h\"")
178	f.WriteLn("#include \"funcdata.h\"")
179	f.WriteLn("")
180	f.GenerateDefines()
181
182	// mul
183	f.generateMul(false)
184
185	// from mont
186	f.generateFromMont(false)
187
188	return nil
189}
190
191func GenerateMulADX(w io.Writer, F *field.Field) error {
192	f := NewFFAmd64(w, F)
193	f.WriteLn(bavard.Apache2Header("ConsenSys Software Inc.", 2020))
194
195	f.WriteLn("#include \"textflag.h\"")
196	f.WriteLn("#include \"funcdata.h\"")
197	f.WriteLn("")
198	f.GenerateDefines()
199
200	// mul
201	f.generateMul(true)
202
203	// from mont
204	f.generateFromMont(true)
205
206	return nil
207}
208