contrib/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 }