Made m64 implementations of elliptic curves the default (when available).
[BearSSL] / T0 / WordBuilder.cs
1 /*
2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24
25 using System;
26 using System.Collections.Generic;
27
28 /*
29 * A WordBuilder instance organizes construction of a new interpreted word.
30 *
31 * Opcodes are accumulated with specific methods. A control-flow stack
32 * is maintained to resolve jumps.
33 *
34 * Each instance shall be used for only one word.
35 */
36
37 class WordBuilder {
38
39 T0Comp TC;
40 string name;
41 int[] cfStack;
42 int cfPtr;
43 List<Opcode> code;
44 List<string> toResolve;
45 Dictionary<string, int> locals;
46 bool jumpToLast;
47
48 internal SType StackEffect {
49 get; set;
50 }
51
52 /*
53 * Create a new instance, with the specified word name.
54 */
55 internal WordBuilder(T0Comp TC, string name)
56 {
57 this.TC = TC;
58 this.name = name;
59 cfStack = new int[16];
60 cfPtr = -1;
61 code = new List<Opcode>();
62 toResolve = new List<string>();
63 locals = new Dictionary<string, int>();
64 jumpToLast = true;
65 StackEffect = SType.UNKNOWN;
66 }
67
68 /*
69 * Build the word. The control-flow stack must be empty. A 'ret'
70 * opcode is automatically appended if required.
71 */
72 internal Word Build()
73 {
74 if (cfPtr != -1) {
75 throw new Exception("control-flow stack is not empty");
76 }
77 if (jumpToLast || code[code.Count - 1].MayFallThrough) {
78 Ret();
79 }
80 Word w = new WordInterpreted(TC, name, locals.Count,
81 code.ToArray(), toResolve.ToArray());
82 w.StackEffect = StackEffect;
83 return w;
84 }
85
86 void Add(Opcode op)
87 {
88 Add(op, null);
89 }
90
91 void Add(Opcode op, string refName)
92 {
93 code.Add(op);
94 toResolve.Add(refName);
95 jumpToLast = false;
96 }
97
98 /*
99 * Rotate the control-flow stack at depth 'depth'.
100 */
101 internal void CSRoll(int depth)
102 {
103 int x = cfStack[cfPtr - depth];
104 Array.Copy(cfStack, cfPtr - (depth - 1),
105 cfStack, cfPtr - depth, depth);
106 cfStack[cfPtr] = x;
107 }
108
109 /*
110 * Make a copy of the control-flow element at depth 'depth', and
111 * push it on top of the control-flow stack.
112 */
113 internal void CSPick(int depth)
114 {
115 int x = cfStack[cfPtr - depth];
116 CSPush(x);
117 }
118
119 void CSPush(int x)
120 {
121 int len = cfStack.Length;
122 if (++ cfPtr == len) {
123 int[] ncf = new int[len << 1];
124 Array.Copy(cfStack, 0, ncf, 0, len);
125 cfStack = ncf;
126 }
127 cfStack[cfPtr] = x;
128 }
129
130 int CSPop()
131 {
132 return cfStack[cfPtr --];
133 }
134
135 /*
136 * Push an origin on the control-flow stack, corresponding to the
137 * next opcode to add.
138 */
139 internal void CSPushOrig()
140 {
141 CSPush(code.Count);
142 }
143
144 /*
145 * Push a destination on the control-flow stack, corresponding to
146 * the next opcode to add.
147 */
148 internal void CSPushDest()
149 {
150 CSPush(-code.Count - 1);
151 }
152
153 /*
154 * Pop an origin from the control-flow stack. An exception is
155 * thrown if the value is not an origin.
156 */
157 internal int CSPopOrig()
158 {
159 int x = CSPop();
160 if (x < 0) {
161 throw new Exception("not an origin");
162 }
163 return x;
164 }
165
166 /*
167 * Pop a destination from the control-flow stack. An exception is
168 * thrown if the value is not a destination.
169 */
170 internal int CSPopDest()
171 {
172 int x = CSPop();
173 if (x >= 0) {
174 throw new Exception("not a destination");
175 }
176 return -x - 1;
177 }
178
179 /*
180 * Add a "push literal" opcode.
181 */
182 internal void Literal(TValue v)
183 {
184 Add(new OpcodeConst(v));
185 }
186
187 /*
188 * Compile a "call" by name. This method implements the support
189 * for local variables:
190 *
191 * - If the target is '>' followed by a local variable name, then
192 * a "put local" opcode is added.
193 *
194 * - Otherwise, if the target is a local variable name, then a
195 * "get local" opcode is added.
196 *
197 * - Otherwise, a call to the named word is added. The target name
198 * will be resolved later on (typically, when the word containing
199 * the call opcode is first invoked, or when C code is generated).
200 */
201 internal void Call(string target)
202 {
203 string lname;
204 bool write;
205 if (target.StartsWith(">")) {
206 lname = target.Substring(1);
207 write = true;
208 } else {
209 lname = target;
210 write = false;
211 }
212 int lnum;
213 if (locals.TryGetValue(lname, out lnum)) {
214 if (write) {
215 Add(new OpcodePutLocal(lnum));
216 } else {
217 Add(new OpcodeGetLocal(lnum));
218 }
219 } else {
220 Add(new OpcodeCall(), target);
221 }
222 }
223
224 /*
225 * Add a "call" opcode to the designated word.
226 */
227 internal void CallExt(Word wtarget)
228 {
229 Add(new OpcodeCall(wtarget), null);
230 }
231
232 /*
233 * Add a "call" opcode to a word which is not currently resolved.
234 * This method ignores local variables.
235 */
236 internal void CallExt(string target)
237 {
238 Add(new OpcodeCall(), target);
239 }
240
241 /*
242 * Add a "get local" opcode; the provided local name must already
243 * be defined.
244 */
245 internal void GetLocal(string name)
246 {
247 int lnum;
248 if (locals.TryGetValue(name, out lnum)) {
249 Add(new OpcodeGetLocal(lnum));
250 } else {
251 throw new Exception("no such local: " + name);
252 }
253 }
254
255 /*
256 * Add a "put local" opcode; the provided local name must already
257 * be defined.
258 */
259 internal void PutLocal(string name)
260 {
261 int lnum;
262 if (locals.TryGetValue(name, out lnum)) {
263 Add(new OpcodePutLocal(lnum));
264 } else {
265 throw new Exception("no such local: " + name);
266 }
267 }
268
269 /*
270 * Define a new local name.
271 */
272 internal void DefLocal(string lname)
273 {
274 if (locals.ContainsKey(lname)) {
275 throw new Exception(String.Format(
276 "local already defined: {0}", lname));
277 }
278 locals[lname] = locals.Count;
279 }
280
281 /*
282 * Add a "call" opcode whose target is an XT value (which may be
283 * resolved or as yet unresolved).
284 */
285 internal void Call(TPointerXT xt)
286 {
287 if (xt.Target == null) {
288 Add(new OpcodeCall(), xt.Name);
289 } else {
290 Add(new OpcodeCall(xt.Target));
291 }
292 }
293
294 /*
295 * Add a "ret" opcode.
296 */
297 internal void Ret()
298 {
299 Add(new OpcodeRet());
300 }
301
302 /*
303 * Add a forward unconditional jump. The new opcode address is
304 * pushed on the control-flow stack as an origin.
305 */
306 internal void Ahead()
307 {
308 CSPushOrig();
309 Add(new OpcodeJumpUncond());
310 }
311
312 /*
313 * Add a forward conditional jump, which will be taken at runtime
314 * if the top-of-stack value is 'true'. The new opcode address is
315 * pushed on the control-flow stack as an origin.
316 */
317 internal void AheadIf()
318 {
319 CSPushOrig();
320 Add(new OpcodeJumpIf());
321 }
322
323 /*
324 * Add a forward conditional jump, which will be taken at runtime
325 * if the top-of-stack value is 'false'. The new opcode address is
326 * pushed on the control-flow stack as an origin.
327 */
328 internal void AheadIfNot()
329 {
330 CSPushOrig();
331 Add(new OpcodeJumpIfNot());
332 }
333
334 /*
335 * Resolve a previous forward jump to the current code address.
336 * The top of control-flow stack is popped and must be an origin.
337 */
338 internal void Then()
339 {
340 int x = CSPopOrig();
341 code[x].ResolveJump(code.Count - x - 1);
342 jumpToLast = true;
343 }
344
345 /*
346 * Push the current code address on the control-flow stack as a
347 * destination, to be used by an ulterior backward jump.
348 */
349 internal void Begin()
350 {
351 CSPushDest();
352 }
353
354 /*
355 * Add a backward unconditional jump. The jump target is popped
356 * from the control-flow stack as a destination.
357 */
358 internal void Again()
359 {
360 int x = CSPopDest();
361 Add(new OpcodeJumpUncond(x - code.Count - 1));
362 }
363
364 /*
365 * Add a backward conditional jump, which will be taken at runtime
366 * if the top-of-stack value is 'true'. The jump target is popped
367 * from the control-flow stack as a destination.
368 */
369 internal void AgainIf()
370 {
371 int x = CSPopDest();
372 Add(new OpcodeJumpIf(x - code.Count - 1));
373 }
374
375 /*
376 * Add a backward conditional jump, which will be taken at runtime
377 * if the top-of-stack value is 'false'. The jump target is popped
378 * from the control-flow stack as a destination.
379 */
380 internal void AgainIfNot()
381 {
382 int x = CSPopDest();
383 Add(new OpcodeJumpIfNot(x - code.Count - 1));
384 }
385 }