diff options
| author | Simon J. Gerraty <sjg@FreeBSD.org> | 2019-01-21 20:23:49 +0000 |
|---|---|---|
| committer | Simon J. Gerraty <sjg@FreeBSD.org> | 2019-01-21 20:23:49 +0000 |
| commit | f55287d3221d3d9128a6529f97e55fb74250aec2 (patch) | |
| tree | 9f1232240de5b9c8dc773240213b7eb3ad319df1 /T0 | |
Diffstat (limited to 'T0')
33 files changed, 5772 insertions, 0 deletions
diff --git a/T0/BlobWriter.cs b/T0/BlobWriter.cs new file mode 100644 index 000000000000..3bbc8e6ac29f --- /dev/null +++ b/T0/BlobWriter.cs @@ -0,0 +1,112 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.IO; +using System.Text; + +/* + * A simple class for writing out bytes as hexadecimal constants or + * explicit expressions for the initializer of a C array of 'unsigned + * char'. It starts every line with a given number of tabs, and aims at + * keeping lines below a given threshold (each indentation tab counts as + * 8 characters). An explicit newline is inserted before the first + * element, and commas are used as separators. + */ + +class BlobWriter { + + TextWriter w; + int maxLineLen; + int indent; + int lineLen; + + /* + * Create a new instance. 'maxLineLen' is in characters, and + * 'indent' is the number of tab characters at the start of + * each line. + */ + internal BlobWriter(TextWriter w, int maxLineLen, int indent) + { + this.w = w; + this.maxLineLen = maxLineLen; + this.indent = indent; + lineLen = -1; + } + + void DoNL() + { + w.WriteLine(); + for (int i = 0; i < indent; i ++) { + w.Write('\t'); + } + lineLen = (indent << 3); + } + + /* + * Append a new byte value; it will be converted to an hexadecimal + * constant in the output. + */ + internal void Append(byte b) + { + if (lineLen < 0) { + DoNL(); + } else { + w.Write(','); + lineLen ++; + if ((lineLen + 5) > maxLineLen) { + DoNL(); + } else { + w.Write(' '); + lineLen ++; + } + } + w.Write("0x{0:X2}", b); + lineLen += 4; + } + + /* + * Append a C expression, which will be used as is. The expression + * may resolve to several bytes if it uses internal commas. The + * writer will try to honour the expected line length, but it + * won't insert a newline character inside the expression. + */ + internal void Append(string expr) + { + if (lineLen < 0) { + DoNL(); + } else { + w.Write(','); + lineLen ++; + if ((lineLen + 1 + expr.Length) > maxLineLen) { + DoNL(); + } else { + w.Write(' '); + lineLen ++; + } + } + w.Write("{0}", expr); + lineLen += expr.Length; + } +} diff --git a/T0/CPU.cs b/T0/CPU.cs new file mode 100644 index 000000000000..22f1a1793aad --- /dev/null +++ b/T0/CPU.cs @@ -0,0 +1,181 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +/* + * Execution of code during compilation is done in a virtual CPU + * incarnated by this class, that contains the relevant registers. + * + * Accesses to the data on the stack are mapped to accesses to an + * internal array, with no explicit control on boundaries. Since the + * internal array may be larger than the actual stack contents, + * nonsensical accesses may still "work" to some extent. The whole + * thing won't derail beyond the CLR VM, though. + */ + +class CPU { + + /* + * Next instruction to execute is in ipBuf[ipOff]. + */ + internal Opcode[] ipBuf; + internal int ipOff; + + /* + * stackBuf and stackPtr implement the data stack. The system + * stack uses frames; 'rsp' points to the current top frame. + */ + TValue[] stackBuf; + int stackPtr; + Frame rsp; + + internal CPU() + { + stackBuf = new TValue[16]; + stackPtr = -1; + rsp = null; + } + + /* + * Enter a function, reserving space for 'numLocals' local variables. + */ + internal void Enter(Opcode[] code, int numLocals) + { + Frame f = new Frame(rsp, numLocals); + rsp = f; + f.savedIpBuf = ipBuf; + f.savedIpOff = ipOff; + ipBuf = code; + ipOff = 0; + } + + /* + * Exit the current function. + */ + internal void Exit() + { + ipBuf = rsp.savedIpBuf; + ipOff = rsp.savedIpOff; + rsp = rsp.upper; + } + + /* + * Get the current stack depth (number of elements). + */ + internal int Depth { + get { + return stackPtr + 1; + } + } + + /* + * Pop a value from the stack. + */ + internal TValue Pop() + { + return stackBuf[stackPtr --]; + } + + /* + * Push a value on the stack. + */ + internal void Push(TValue v) + { + int len = stackBuf.Length; + if (++ stackPtr == len) { + TValue[] nbuf = new TValue[len << 1]; + Array.Copy(stackBuf, 0, nbuf, 0, len); + stackBuf = nbuf; + } + stackBuf[stackPtr] = v; + } + + /* + * Look at the value at depth 'depth' (0 is top of stack). The + * stack is unchanged. + */ + internal TValue Peek(int depth) + { + return stackBuf[stackPtr - depth]; + } + + /* + * Rotate the stack at depth 'depth': the value at that depth + * is moved to the top of stack. + */ + internal void Rot(int depth) + { + TValue v = stackBuf[stackPtr - depth]; + Array.Copy(stackBuf, stackPtr - (depth - 1), + stackBuf, stackPtr - depth, depth); + stackBuf[stackPtr] = v; + } + + /* + * Inverse-rotate the stack at depth 'depth': the value at the + * top of stack is moved to that depth. + */ + internal void NRot(int depth) + { + TValue v = stackBuf[stackPtr]; + Array.Copy(stackBuf, stackPtr - depth, + stackBuf, stackPtr - (depth - 1), depth); + stackBuf[stackPtr - depth] = v; + } + + /* + * Get the current contents of the local variable 'num'. + */ + internal TValue GetLocal(int num) + { + return rsp.locals[num]; + } + + /* + * Set the contents of the local variable 'num'. + */ + internal void PutLocal(int num, TValue v) + { + rsp.locals[num] = v; + } + + /* + * The system stack really is a linked list of Frame instances. + */ + class Frame { + + internal Frame upper; + internal Opcode[] savedIpBuf; + internal int savedIpOff; + internal TValue[] locals; + + internal Frame(Frame upper, int numLocals) + { + this.upper = upper; + locals = new TValue[numLocals]; + } + } +} diff --git a/T0/CodeElement.cs b/T0/CodeElement.cs new file mode 100644 index 000000000000..471a61f903f2 --- /dev/null +++ b/T0/CodeElement.cs @@ -0,0 +1,100 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; + +abstract class CodeElement { + + internal int Address { get; set; } + + internal int LastLength { get; set; } + + // internal abstract int Length { get; } + + internal CodeElement() + { + Address = -1; + } + + internal virtual void SetJumpTarget(CodeElement target) + { + throw new Exception("Code element accepts no target"); + } + + internal abstract int GetLength(bool oneByteCode); + + internal abstract int Encode(BlobWriter bw, bool oneByteCode); + + internal static int EncodeOneByte(uint val, BlobWriter bw) + { + if (val > 255) { + throw new Exception(string.Format( + "Cannot encode '{0}' over one byte", val)); + } + bw.Append((byte)val); + return 1; + } + + internal static int Encode7EUnsigned(uint val, BlobWriter bw) + { + int len = 1; + for (uint w = val; w >= 0x80; w >>= 7) { + len ++; + } + if (bw != null) { + for (int k = (len - 1) * 7; k >= 0; k -= 7) { + int x = (int)(val >> k) & 0x7F; + if (k > 0) { + x |= 0x80; + } + bw.Append((byte)x); + } + } + return len; + } + + internal static int Encode7ESigned(int val, BlobWriter bw) + { + int len = 1; + if (val < 0) { + for (int w = val; w < -0x40; w >>= 7) { + len ++; + } + } else { + for (int w = val; w >= 0x40; w >>= 7) { + len ++; + } + } + if (bw != null) { + for (int k = (len - 1) * 7; k >= 0; k -= 7) { + int x = (int)(val >> k) & 0x7F; + if (k > 0) { + x |= 0x80; + } + bw.Append((byte)x); + } + } + return len; + } +} diff --git a/T0/CodeElementJump.cs b/T0/CodeElementJump.cs new file mode 100644 index 000000000000..4dae0bc8c059 --- /dev/null +++ b/T0/CodeElementJump.cs @@ -0,0 +1,97 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; + +class CodeElementJump : CodeElement { + + uint jumpType; + CodeElement target; + + internal CodeElementJump(uint jumpType) + { + this.jumpType = jumpType; + } + + /* obsolete + internal override int Length { + get { + int len = Encode7EUnsigned(jumpType, null); + int joff = JumpOff; + if (joff == Int32.MinValue) { + len ++; + } else { + len += Encode7ESigned(joff, null); + } + return len; + } + } + */ + + internal override int GetLength(bool oneByteCode) + { + int len = oneByteCode ? 1 : Encode7EUnsigned(jumpType, null); + int joff = JumpOff; + if (joff == Int32.MinValue) { + len ++; + } else { + len += Encode7ESigned(joff, null); + } + return len; + } + + internal override void SetJumpTarget(CodeElement target) + { + this.target = target; + } + + int JumpOff { + get { + if (target == null || Address < 0 || target.Address < 0) + { + return Int32.MinValue; + } else { + return target.Address - (Address + LastLength); + } + } + } + + internal override int Encode(BlobWriter bw, bool oneByteCode) + { + if (bw == null) { + return GetLength(oneByteCode); + } + int len; + if (oneByteCode) { + len = EncodeOneByte(jumpType, bw); + } else { + len = Encode7EUnsigned(jumpType, bw); + } + int joff = JumpOff; + if (joff == Int32.MinValue) { + throw new Exception("Unresolved addresses"); + } + return len + Encode7ESigned(joff, bw); + } +} diff --git a/T0/CodeElementUInt.cs b/T0/CodeElementUInt.cs new file mode 100644 index 000000000000..049cdad642e1 --- /dev/null +++ b/T0/CodeElementUInt.cs @@ -0,0 +1,55 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; + +class CodeElementUInt : CodeElement { + + uint val; + + internal CodeElementUInt(uint val) : base() + { + this.val = val; + } + + /* obsolete + internal override int Length { + get { + return Encode7EUnsigned(val, null); + } + } + */ + + internal override int GetLength(bool oneByteCode) + { + return oneByteCode ? 1 : Encode7EUnsigned(val, null); + } + + internal override int Encode(BlobWriter bw, bool oneByteCode) + { + return oneByteCode + ? EncodeOneByte(val, bw) + : Encode7EUnsigned(val, bw); + } +} diff --git a/T0/CodeElementUIntExpr.cs b/T0/CodeElementUIntExpr.cs new file mode 100644 index 000000000000..8dd55a54d953 --- /dev/null +++ b/T0/CodeElementUIntExpr.cs @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; + +class CodeElementUIntExpr : CodeElement { + + uint val; + TPointerExpr cx; + int off; + + internal CodeElementUIntExpr(uint val, + TPointerExpr cx, int off) : base() + { + this.val = val; + this.cx = cx; + this.off = off; + } + + /* obsolete + internal override int Length { + get { + return Encode7EUnsigned(val, null) + + (cx.GetMaxBitLength(off) + 6) / 7; + } + } + */ + + internal override int GetLength(bool oneByteCode) + { + int len = oneByteCode ? 1 : Encode7EUnsigned(val, null); + return len + (cx.GetMaxBitLength(off) + 6) / 7; + } + + internal override int Encode(BlobWriter bw, bool oneByteCode) + { + int len1 = oneByteCode + ? EncodeOneByte(val, bw) + : Encode7EUnsigned(val, bw); + int len2 = (cx.GetMaxBitLength(off) + 6) / 7; + bw.Append(String.Format("T0_INT{0}({1})", + len2, cx.ToCExpr(off))); + return len1 + len2; + } +} diff --git a/T0/CodeElementUIntInt.cs b/T0/CodeElementUIntInt.cs new file mode 100644 index 000000000000..0223e27719af --- /dev/null +++ b/T0/CodeElementUIntInt.cs @@ -0,0 +1,61 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; + +class CodeElementUIntInt : CodeElement { + + uint val1; + int val2; + + internal CodeElementUIntInt(uint val1, int val2) : base() + { + this.val1 = val1; + this.val2 = val2; + } + + /* obsolete + internal override int Length { + get { + return Encode7EUnsigned(val1, null) + + Encode7ESigned(val2, null); + } + } + */ + + internal override int GetLength(bool oneByteCode) + { + return (oneByteCode ? 1 : Encode7EUnsigned(val1, null)) + + Encode7ESigned(val2, null); + } + + internal override int Encode(BlobWriter bw, bool oneByteCode) + { + int len = oneByteCode + ? EncodeOneByte(val1, bw) + : Encode7EUnsigned(val1, bw); + len += Encode7ESigned(val2, bw); + return len; + } +} diff --git a/T0/CodeElementUIntUInt.cs b/T0/CodeElementUIntUInt.cs new file mode 100644 index 000000000000..6f94de54f9d2 --- /dev/null +++ b/T0/CodeElementUIntUInt.cs @@ -0,0 +1,60 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; + +class CodeElementUIntUInt : CodeElement { + + uint val1, val2; + + internal CodeElementUIntUInt(uint val1, uint val2) : base() + { + this.val1 = val1; + this.val2 = val2; + } + + /* obsolete + internal override int Length { + get { + return Encode7EUnsigned(val1, null) + + Encode7EUnsigned(val2, null); + } + } + */ + + internal override int GetLength(bool oneByteCode) + { + return (oneByteCode ? 1 : Encode7EUnsigned(val1, null)) + + Encode7EUnsigned(val2, null); + } + + internal override int Encode(BlobWriter bw, bool oneByteCode) + { + int len = oneByteCode + ? EncodeOneByte(val1, bw) + : Encode7EUnsigned(val1, bw); + len += Encode7EUnsigned(val2, bw); + return len; + } +} diff --git a/T0/ConstData.cs b/T0/ConstData.cs new file mode 100644 index 000000000000..6a06b64ed145 --- /dev/null +++ b/T0/ConstData.cs @@ -0,0 +1,198 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; +using System.Text; + +class ConstData { + + internal long ID { get; private set; } + internal int Address { get; set; } + internal int Length { + get { + return len; + } + } + + byte[] buf; + int len; + + internal ConstData(T0Comp ctx) + { + ID = ctx.NextBlobID(); + buf = new byte[4]; + len = 0; + } + + void Expand(int elen) + { + int tlen = len + elen; + if (tlen > buf.Length) { + int nlen = Math.Max(buf.Length << 1, tlen); + byte[] nbuf = new byte[nlen]; + Array.Copy(buf, 0, nbuf, 0, len); + buf = nbuf; + } + } + + internal void Add8(byte b) + { + Expand(1); + buf[len ++] = b; + } + + internal void Add16(int x) + { + Expand(2); + buf[len ++] = (byte)(x >> 8); + buf[len ++] = (byte)x; + } + + internal void Add24(int x) + { + Expand(3); + buf[len ++] = (byte)(x >> 16); + buf[len ++] = (byte)(x >> 8); + buf[len ++] = (byte)x; + } + + internal void Add32(int x) + { + Expand(4); + buf[len ++] = (byte)(x >> 24); + buf[len ++] = (byte)(x >> 16); + buf[len ++] = (byte)(x >> 8); + buf[len ++] = (byte)x; + } + + internal void AddString(string s) + { + byte[] sd = Encoding.UTF8.GetBytes(s); + Expand(sd.Length + 1); + Array.Copy(sd, 0, buf, len, sd.Length); + buf[len + sd.Length] = 0; + len += sd.Length + 1; + } + + void CheckIndex(int off, int dlen) + { + if (off < 0 || off > (len - dlen)) { + throw new IndexOutOfRangeException(); + } + } + + internal void Set8(int off, byte v) + { + CheckIndex(off, 1); + buf[off] = v; + } + + internal byte Read8(int off) + { + CheckIndex(off, 1); + return buf[off]; + } + + internal int Read16(int off) + { + CheckIndex(off, 2); + return (buf[off] << 8) | buf[off + 1]; + } + + internal int Read24(int off) + { + CheckIndex(off, 3); + return (buf[off] << 16) | (buf[off + 1] << 8) | buf[off + 2]; + } + + internal int Read32(int off) + { + CheckIndex(off, 4); + return (buf[off] << 24) | (buf[off + 1] << 16) + | (buf[off + 2] << 8) | buf[off + 3]; + } + + internal string ToString(int off) + { + StringBuilder sb = new StringBuilder(); + for (;;) { + int x = DecodeUTF8(ref off); + if (x == 0) { + return sb.ToString(); + } + if (x < 0x10000) { + sb.Append((char)x); + } else { + x -= 0x10000; + sb.Append((char)(0xD800 + (x >> 10))); + sb.Append((char)(0xDC00 + (x & 0x3FF))); + } + } + } + + int DecodeUTF8(ref int off) + { + if (off >= len) { + throw new IndexOutOfRangeException(); + } + int x = buf[off ++]; + if (x < 0xC0 || x > 0xF7) { + return x; + } + int elen, acc; + if (x >= 0xF0) { + elen = 3; + acc = x & 0x07; + } else if (x >= 0xE0) { + elen = 2; + acc = x & 0x0F; + } else { + elen = 1; + acc = x & 0x1F; + } + if (off + elen > len) { + return x; + } + for (int i = 0; i < elen; i ++) { + int y = buf[off + i]; + if (y < 0x80 || y >= 0xC0) { + return x; + } + acc = (acc << 6) + (y & 0x3F); + } + if (acc > 0x10FFFF) { + return x; + } + off += elen; + return acc; + } + + internal void Encode(BlobWriter bw) + { + for (int i = 0; i < len; i ++) { + bw.Append(buf[i]); + } + } +} diff --git a/T0/Opcode.cs b/T0/Opcode.cs new file mode 100644 index 000000000000..81d1e9d7d3d8 --- /dev/null +++ b/T0/Opcode.cs @@ -0,0 +1,117 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +abstract class Opcode { + + internal Opcode() + { + } + + /* + * Execute this opcode. + */ + internal abstract void Run(CPU cpu); + + /* + * Resolve the target (word reference) for this opcode. + */ + internal virtual void ResolveTarget(Word target) + { + throw new Exception("Not a call opcode"); + } + + /* + * Resolve the jump offset for this opcode. Displacement is + * relative to the address of the opcode that immediately follows + * the jump code; thus, 0 implies no jump at all. + */ + internal virtual void ResolveJump(int disp) + { + throw new Exception("Not a jump opcode"); + } + + /* + * Get the Word that this opcode references; this can happen + * only with "call" and "const" opcodes. For all other opcodes, + * this method returns null. + */ + internal virtual Word GetReference(T0Comp ctx) + { + return null; + } + + /* + * Get the data block that this opcode references; this can happen + * only with "const" opcodes. For all other opcodes, this method + * returns null. + */ + internal virtual ConstData GetDataBlock(T0Comp ctx) + { + return null; + } + + /* + * Test whether this opcode may "fall through", i.e. execution + * may at least potentially proceed to the next opcode. + */ + internal virtual bool MayFallThrough { + get { + return true; + } + } + + /* + * Get jump displacement. For non-jump opcodes, this returns 0. + */ + internal virtual int JumpDisp { + get { + return 0; + } + } + + /* + * Get stack effect for this opcode (number of elements added to + * the stack, could be negative). For OpcodeCall, this returns + * 0. + */ + internal virtual int StackAction { + get { + return 0; + } + } + + internal abstract CodeElement ToCodeElement(); + + /* + * This method is called for the CodeElement corresponding to + * this opcode, at gcode[off]; it is used to compute actual + * byte jump offsets when converting code to C. + */ + internal virtual void FixUp(CodeElement[] gcode, int off) + { + } +} diff --git a/T0/OpcodeCall.cs b/T0/OpcodeCall.cs new file mode 100644 index 000000000000..098004225dce --- /dev/null +++ b/T0/OpcodeCall.cs @@ -0,0 +1,71 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class OpcodeCall : Opcode { + + Word target; + + internal OpcodeCall() : this(null) + { + } + + internal OpcodeCall(Word target) + { + this.target = target; + } + + internal override void ResolveTarget(Word target) + { + if (this.target != null) { + throw new Exception("Opcode already resolved"); + } + this.target = target; + } + + internal override void Run(CPU cpu) + { + target.Run(cpu); + } + + internal override Word GetReference(T0Comp ctx) + { + if (target == null) { + throw new Exception("Unresolved call target"); + } + return target; + } + + internal override CodeElement ToCodeElement() + { + return new CodeElementUInt((uint)target.Slot); + } + + public override string ToString() + { + return "call " + (target == null ? "UNRESOLVED" : target.Name); + } +} diff --git a/T0/OpcodeConst.cs b/T0/OpcodeConst.cs new file mode 100644 index 000000000000..ae75ae59d651 --- /dev/null +++ b/T0/OpcodeConst.cs @@ -0,0 +1,95 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class OpcodeConst : Opcode { + + TValue val; + + internal OpcodeConst(TValue val) + { + this.val = val; + } + + internal override void Run(CPU cpu) + { + cpu.Push(val); + } + + internal override Word GetReference(T0Comp ctx) + { + TPointerXT xt = val.ptr as TPointerXT; + if (xt == null) { + return null; + } + xt.Resolve(ctx); + return xt.Target; + } + + internal override ConstData GetDataBlock(T0Comp ctx) + { + TPointerBlob bp = val.ptr as TPointerBlob; + return bp == null ? null : bp.Blob; + } + + internal override CodeElement ToCodeElement() + { + if (val.ptr == null) { + return new CodeElementUIntInt(1, val.Int); + } + TPointerXT xt = val.ptr as TPointerXT; + if (xt != null) { + if (val.x != 0) { + throw new Exception( + "Cannot compile XT: non-zero offset"); + } + return new CodeElementUIntInt(1, xt.Target.Slot); + } + TPointerBlob bp = val.ptr as TPointerBlob; + if (bp != null) { + return new CodeElementUIntInt(1, + val.x + bp.Blob.Address); + } + TPointerExpr cx = val.ptr as TPointerExpr; + if (cx != null) { + return new CodeElementUIntExpr(1, cx, val.x); + } + throw new Exception(String.Format( + "Cannot embed constant (type = {0})", + val.ptr.GetType().FullName)); + } + + internal override int StackAction { + get { + return 1; + } + } + + public override string ToString() + { + return "const " + val.ToString(); + } +} diff --git a/T0/OpcodeGetLocal.cs b/T0/OpcodeGetLocal.cs new file mode 100644 index 000000000000..59d24fc5c361 --- /dev/null +++ b/T0/OpcodeGetLocal.cs @@ -0,0 +1,57 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class OpcodeGetLocal : Opcode { + + int num; + + internal OpcodeGetLocal(int num) + { + this.num = num; + } + + internal override void Run(CPU cpu) + { + cpu.Push(cpu.GetLocal(num)); + } + + internal override CodeElement ToCodeElement() + { + return new CodeElementUIntUInt(2, (uint)num); + } + + internal override int StackAction { + get { + return 1; + } + } + + public override string ToString() + { + return "getlocal " + num; + } +} diff --git a/T0/OpcodeJump.cs b/T0/OpcodeJump.cs new file mode 100644 index 000000000000..4f3ec684d881 --- /dev/null +++ b/T0/OpcodeJump.cs @@ -0,0 +1,64 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +abstract class OpcodeJump : Opcode { + + int disp; + + internal OpcodeJump() : this(Int32.MinValue) + { + } + + internal OpcodeJump(int disp) + { + this.disp = disp; + } + + internal override int JumpDisp { + get { + return disp; + } + } + + internal override void Run(CPU cpu) + { + cpu.ipOff += disp; + } + + internal override void ResolveJump(int disp) + { + if (this.disp != Int32.MinValue) { + throw new Exception("Jump already resolved"); + } + this.disp = disp; + } + + internal override void FixUp(CodeElement[] gcode, int off) + { + gcode[off].SetJumpTarget(gcode[off + 1 + disp]); + } +} diff --git a/T0/OpcodeJumpIf.cs b/T0/OpcodeJumpIf.cs new file mode 100644 index 000000000000..d70243449202 --- /dev/null +++ b/T0/OpcodeJumpIf.cs @@ -0,0 +1,65 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class OpcodeJumpIf : OpcodeJump { + + internal OpcodeJumpIf() : base() + { + } + + internal OpcodeJumpIf(int disp) : base(disp) + { + } + + internal override void Run(CPU cpu) + { + TValue v = cpu.Pop(); + if (v.Bool) { + base.Run(cpu); + } + } + + internal override int StackAction { + get { + return -1; + } + } + + internal override CodeElement ToCodeElement() + { + return new CodeElementJump(5); + } + + public override string ToString() + { + if (JumpDisp == Int32.MinValue) { + return "jumpif UNRESOLVED"; + } else { + return "jumpif disp=" + JumpDisp; + } + } +} diff --git a/T0/OpcodeJumpIfNot.cs b/T0/OpcodeJumpIfNot.cs new file mode 100644 index 000000000000..afbf19de5eb5 --- /dev/null +++ b/T0/OpcodeJumpIfNot.cs @@ -0,0 +1,65 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class OpcodeJumpIfNot : OpcodeJump { + + internal OpcodeJumpIfNot() : base() + { + } + + internal OpcodeJumpIfNot(int disp) : base(disp) + { + } + + internal override void Run(CPU cpu) + { + TValue v = cpu.Pop(); + if (!v.Bool) { + base.Run(cpu); + } + } + + internal override int StackAction { + get { + return -1; + } + } + + internal override CodeElement ToCodeElement() + { + return new CodeElementJump(6); + } + + public override string ToString() + { + if (JumpDisp == Int32.MinValue) { + return "jumpifnot UNRESOLVED"; + } else { + return "jumpifnot disp=" + JumpDisp; + } + } +} diff --git a/T0/OpcodeJumpUncond.cs b/T0/OpcodeJumpUncond.cs new file mode 100644 index 000000000000..e7d8a82bda3d --- /dev/null +++ b/T0/OpcodeJumpUncond.cs @@ -0,0 +1,61 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class OpcodeJumpUncond : OpcodeJump { + + internal OpcodeJumpUncond() : base() + { + } + + internal OpcodeJumpUncond(int disp) : base(disp) + { + } + + /* + * Unconditional jumps do not "fall through" unless they + * happen to be a jump to the next instruction... + */ + internal override bool MayFallThrough { + get { + return JumpDisp == 0; + } + } + + internal override CodeElement ToCodeElement() + { + return new CodeElementJump(4); + } + + public override string ToString() + { + if (JumpDisp == Int32.MinValue) { + return "jump UNRESOLVED"; + } else { + return "jump disp=" + JumpDisp; + } + } +} diff --git a/T0/OpcodePutLocal.cs b/T0/OpcodePutLocal.cs new file mode 100644 index 000000000000..b148a65b9ca2 --- /dev/null +++ b/T0/OpcodePutLocal.cs @@ -0,0 +1,57 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class OpcodePutLocal : Opcode { + + int num; + + internal OpcodePutLocal(int num) + { + this.num = num; + } + + internal override void Run(CPU cpu) + { + cpu.PutLocal(num, cpu.Pop()); + } + + internal override CodeElement ToCodeElement() + { + return new CodeElementUIntUInt(3, (uint)num); + } + + internal override int StackAction { + get { + return -1; + } + } + + public override string ToString() + { + return "putlocal " + num; + } +} diff --git a/T0/OpcodeRet.cs b/T0/OpcodeRet.cs new file mode 100644 index 000000000000..187473b1d60e --- /dev/null +++ b/T0/OpcodeRet.cs @@ -0,0 +1,50 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class OpcodeRet : Opcode { + + internal override void Run(CPU cpu) + { + cpu.Exit(); + } + + internal override bool MayFallThrough { + get { + return false; + } + } + + internal override CodeElement ToCodeElement() + { + return new CodeElementUInt(0); + } + + public override string ToString() + { + return "ret"; + } +} diff --git a/T0/SType.cs b/T0/SType.cs new file mode 100644 index 000000000000..80e9f0176e18 --- /dev/null +++ b/T0/SType.cs @@ -0,0 +1,129 @@ +using System; + +/* + * This structure contains the stack effect of a word: number of stack + * element consumed on input, and number of stack element produced on + * output. + */ + +struct SType { + + /* + * Get number of stack elements consumed on input; this is -1 if + * the stack effect is not known. + */ + internal int DataIn { + get { + return din; + } + } + + /* + * Get number of stack elements produced on output; this is -1 if + * either the stack effect is not known, or if the word never + * exits. + */ + internal int DataOut { + get { + return dout; + } + } + + /* + * Tell whether the stack effect is known. + */ + internal bool IsKnown { + get { + return din >= 0; + } + } + + /* + * Tell whether the stack effect is known and the word never exits. + */ + internal bool NoExit { + get { + return din >= 0 && dout < 0; + } + } + + int din, dout; + + internal SType(int din, int dout) + { + if (din < 0) { + din = -1; + } + if (dout < 0) { + dout = -1; + } + this.din = din; + this.dout = dout; + } + + /* + * Special value for the unknown stack effect. + */ + internal static SType UNKNOWN = new SType(-1, -1); + + /* + * Constant for the "blank stack effect". + */ + internal static SType BLANK = new SType(0, 0); + + public static bool operator ==(SType s1, SType s2) + { + return s1.din == s2.din && s1.dout == s2.dout; + } + + public static bool operator !=(SType s1, SType s2) + { + return s1.din != s2.din || s1.dout != s2.dout; + } + + public override bool Equals(Object obj) + { + return (obj is SType) && ((SType)obj == this); + } + + public override int GetHashCode() + { + return din * 31 + dout * 17; + } + + public override string ToString() + { + if (!IsKnown) { + return "UNKNOWN"; + } else if (NoExit) { + return string.Format("in:{0},noexit", din); + } else { + return string.Format("in:{0},out:{1}", din, dout); + } + } + + /* + * Test whether this stack effect is a sub-effect of the provided + * stack effect s. Stack effect s1 is a sub-effect of stack-effect + * s2 if any of the following holds: + * -- s1 and s2 are known, s1.din <= s2.din and s1 does not exit. + * -- s1 and s2 are known, s1.din <= s2.din, s1 and s2 exit, + * and s1.din - s1.dout == s2.din - s2.dout. + */ + internal bool IsSubOf(SType s) + { + if (!IsKnown || !s.IsKnown) { + return false; + } + if (din > s.din) { + return false; + } + if (NoExit) { + return true; + } + if (s.NoExit) { + return false; + } + return (din - dout) == (s.din - s.dout); + } +} diff --git a/T0/T0Comp.cs b/T0/T0Comp.cs new file mode 100644 index 000000000000..7a397f7cbc48 --- /dev/null +++ b/T0/T0Comp.cs @@ -0,0 +1,2123 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; +using System.IO; +using System.Reflection; +using System.Text; + +/* + * This is the main compiler class. + */ + +public class T0Comp { + + /* + * Command-line entry point. + */ + public static void Main(string[] args) + { + try { + List<string> r = new List<string>(); + string outBase = null; + List<string> entryPoints = new List<string>(); + string coreRun = null; + bool flow = true; + int dsLim = 32; + int rsLim = 32; + for (int i = 0; i < args.Length; i ++) { + string a = args[i]; + if (!a.StartsWith("-")) { + r.Add(a); + continue; + } + if (a == "--") { + for (;;) { + if (++ i >= args.Length) { + break; + } + r.Add(args[i]); + } + break; + } + while (a.StartsWith("-")) { + a = a.Substring(1); + } + int j = a.IndexOf('='); + string pname; + string pval, pval2; + if (j < 0) { + pname = a.ToLowerInvariant(); + pval = null; + pval2 = (i + 1) < args.Length + ? args[i + 1] : null; + } else { + pname = a.Substring(0, j).Trim() + .ToLowerInvariant(); + pval = a.Substring(j + 1); + pval2 = null; + } + switch (pname) { + case "o": + case "out": + if (pval == null) { + if (pval2 == null) { + Usage(); + } + i ++; + pval = pval2; + } + if (outBase != null) { + Usage(); + } + outBase = pval; + break; + case "r": + case "run": + if (pval == null) { + if (pval2 == null) { + Usage(); + } + i ++; + pval = pval2; + } + coreRun = pval; + break; + case "m": + case "main": + if (pval == null) { + if (pval2 == null) { + Usage(); + } + i ++; + pval = pval2; + } + foreach (string ep in pval.Split(',')) { + string epz = ep.Trim(); + if (epz.Length > 0) { + entryPoints.Add(epz); + } + } + break; + case "nf": + case "noflow": + flow = false; + break; + default: + Usage(); + break; + } + } + if (r.Count == 0) { + Usage(); + } + if (outBase == null) { + outBase = "t0out"; + } + if (entryPoints.Count == 0) { + entryPoints.Add("main"); + } + if (coreRun == null) { + coreRun = outBase; + } + T0Comp tc = new T0Comp(); + tc.enableFlowAnalysis = flow; + tc.dsLimit = dsLim; + tc.rsLimit = rsLim; + using (TextReader tr = new StreamReader( + Assembly.GetExecutingAssembly() + .GetManifestResourceStream("t0-kernel"))) + { + tc.ProcessInput(tr); + } + foreach (string a in r) { + Console.WriteLine("[{0}]", a); + using (TextReader tr = File.OpenText(a)) { + tc.ProcessInput(tr); + } + } + tc.Generate(outBase, coreRun, entryPoints.ToArray()); + } catch (Exception e) { + Console.WriteLine(e.ToString()); + Environment.Exit(1); + } + } + + static void Usage() + { + Console.WriteLine( +"usage: T0Comp.exe [ options... ] file..."); + Console.WriteLine( +"options:"); + Console.WriteLine( +" -o file use 'file' as base for output file name (default: 't0out')"); + Console.WriteLine( +" -r name use 'name' as base for run function (default: same as output)"); + Console.WriteLine( +" -m name[,name...]"); + Console.WriteLine( +" define entry point(s)"); + Console.WriteLine( +" -nf disable flow analysis"); + Environment.Exit(1); + } + + /* + * If 'delayedChar' is Int32.MinValue then there is no delayed + * character. + * If 'delayedChar' equals x >= 0 then there is one delayed + * character of value x. + * If 'delayedChar' equals y < 0 then there are two delayed + * characters, a newline (U+000A) followed by character of + * value -(y+1). + */ + TextReader currentInput; + int delayedChar; + + /* + * Common StringBuilder used to parse tokens; it is reused for + * each new token. + */ + StringBuilder tokenBuilder; + + /* + * There may be a delayed token in some cases. + */ + String delayedToken; + + /* + * Defined words are referenced by name in this map. Names are + * string-sensitive; for better reproducibility, the map is sorted + * (ordinal order). + */ + IDictionary<string, Word> words; + + /* + * Last defined word is also referenced in 'lastWord'. This is + * used by 'immediate'. + */ + Word lastWord; + + /* + * When compiling, this builder is used. A stack saves other + * builders in case of nested definition. + */ + WordBuilder wordBuilder; + Stack<WordBuilder> savedWordBuilders; + + /* + * C code defined for words is kept in this map, by word name. + */ + IDictionary<string, string> allCCode; + + /* + * 'compiling' is true when compiling tokens to a word, false + * when interpreting them. + */ + bool compiling; + + /* + * 'quitRunLoop' is set to true to trigger exit of the + * interpretation loop when the end of the current input file + * is reached. + */ + bool quitRunLoop; + + /* + * 'extraCode' is for C code that is to be added as preamble to + * the C output. + */ + List<string> extraCode; + + /* + * 'extraCodeDefer' is for C code that is to be added in the C + * output _after_ the data and code blocks. + */ + List<string> extraCodeDefer; + + /* + * 'dataBlock' is the data block in which constant data bytes + * are accumulated. + */ + ConstData dataBlock; + + /* + * Counter for blocks of constant data. + */ + long currentBlobID; + + /* + * Flow analysis enable flag. + */ + bool enableFlowAnalysis; + + /* + * Data stack size limit. + */ + int dsLimit; + + /* + * Return stack size limit. + */ + int rsLimit; + + T0Comp() + { + tokenBuilder = new StringBuilder(); + words = new SortedDictionary<string, Word>( + StringComparer.Ordinal); + savedWordBuilders = new Stack<WordBuilder>(); + allCCode = new SortedDictionary<string, string>( + StringComparer.Ordinal); + compiling = false; + extraCode = new List<string>(); + extraCodeDefer = new List<string>(); + enableFlowAnalysis = true; + + /* + * Native words are predefined and implemented only with + * native code. Some may be part of the generated output, + * if C code is set for them. + */ + + /* + * add-cc: + * Parses next token as a word name, then a C code snippet. + * Sets the C code for that word. + */ + AddNative("add-cc:", false, SType.BLANK, cpu => { + string tt = Next(); + if (tt == null) { + throw new Exception( + "EOF reached (missing name)"); + } + if (allCCode.ContainsKey(tt)) { + throw new Exception( + "C code already set for: " + tt); + } + allCCode[tt] = ParseCCode(); + }); + + /* + * cc: + * Parses next token as a word name, then a C code snippet. + * A new word is defined, that throws an exception when + * invoked during compilation. The C code is set for that + * new word. + */ + AddNative("cc:", false, SType.BLANK, cpu => { + string tt = Next(); + if (tt == null) { + throw new Exception( + "EOF reached (missing name)"); + } + Word w = AddNative(tt, false, cpu2 => { + throw new Exception( + "C-only word: " + tt); + }); + if (allCCode.ContainsKey(tt)) { + throw new Exception( + "C code already set for: " + tt); + } + SType stackEffect; + allCCode[tt] = ParseCCode(out stackEffect); + w.StackEffect = stackEffect; + }); + + /* + * preamble + * Parses a C code snippet, then adds it to the generated + * output preamble. + */ + AddNative("preamble", false, SType.BLANK, cpu => { + extraCode.Add(ParseCCode()); + }); + + /* + * postamble + * Parses a C code snippet, then adds it to the generated + * output after the data and code blocks. + */ + AddNative("postamble", false, SType.BLANK, cpu => { + extraCodeDefer.Add(ParseCCode()); + }); + + /* + * make-CX + * Expects two integers and a string, and makes a + * constant that stands for the string as a C constant + * expression. The two integers are the expected range + * (min-max, inclusive). + */ + AddNative("make-CX", false, new SType(3, 1), cpu => { + TValue c = cpu.Pop(); + if (!(c.ptr is TPointerBlob)) { + throw new Exception(string.Format( + "'{0}' is not a string", c)); + } + int max = cpu.Pop(); + int min = cpu.Pop(); + TValue tv = new TValue(0, new TPointerExpr( + c.ToString(), min, max)); + cpu.Push(tv); + }); + + /* + * CX (immediate) + * Parses two integer constants, then a C code snippet. + * It then pushes on the stack, or compiles to the + * current word, a value consisting of the given C + * expression; the two integers indicate the expected + * range (min-max, inclusive) of the C expression when + * evaluated. + */ + AddNative("CX", true, cpu => { + string tt = Next(); + if (tt == null) { + throw new Exception( + "EOF reached (missing min value)"); + } + int min = ParseInteger(tt); + tt = Next(); + if (tt == null) { + throw new Exception( + "EOF reached (missing max value)"); + } + int max = ParseInteger(tt); + if (max < min) { + throw new Exception("min/max in wrong order"); + } + TValue tv = new TValue(0, new TPointerExpr( + ParseCCode().Trim(), min, max)); + if (compiling) { + wordBuilder.Literal(tv); + } else { + cpu.Push(tv); + } + }); + + /* + * co + * Interrupt the current execution. This implements + * coroutines. It cannot be invoked during compilation. + */ + AddNative("co", false, SType.BLANK, cpu => { + throw new Exception("No coroutine in compile mode"); + }); + + /* + * : + * Parses next token as word name. It begins definition + * of that word, setting it as current target for + * word building. Any previously opened word is saved + * and will become available again as a target when that + * new word is finished building. + */ + AddNative(":", false, cpu => { + string tt = Next(); + if (tt == null) { + throw new Exception( + "EOF reached (missing name)"); + } + if (compiling) { + savedWordBuilders.Push(wordBuilder); + } else { + compiling = true; + } + wordBuilder = new WordBuilder(this, tt); + tt = Next(); + if (tt == null) { + throw new Exception( + "EOF reached (while compiling)"); + } + if (tt == "(") { + SType stackEffect = ParseStackEffectNF(); + if (!stackEffect.IsKnown) { + throw new Exception( + "Invalid stack effect syntax"); + } + wordBuilder.StackEffect = stackEffect; + } else { + delayedToken = tt; + } + }); + + /* + * Pops a string as word name, and two integers as stack + * effect. It begins definition of that word, setting it + * as current target for word building. Any previously + * opened word is saved and will become available again as + * a target when that new word is finished building. + * + * Stack effect is the pair 'din dout'. If din is negative, + * then the stack effect is "unknown". If din is nonnegative + * but dout is negative, then the word is reputed never to + * return. + */ + AddNative("define-word", false, cpu => { + int dout = cpu.Pop(); + int din = cpu.Pop(); + TValue s = cpu.Pop(); + if (!(s.ptr is TPointerBlob)) { + throw new Exception(string.Format( + "Not a string: '{0}'", s)); + } + string tt = s.ToString(); + if (compiling) { + savedWordBuilders.Push(wordBuilder); + } else { + compiling = true; + } + wordBuilder = new WordBuilder(this, tt); + wordBuilder.StackEffect = new SType(din, dout); + }); + + /* + * ; (immediate) + * Ends current word. The current word is registered under + * its name, and the previously opened word (if any) becomes + * again the building target. + */ + AddNative(";", true, cpu => { + if (!compiling) { + throw new Exception("Not compiling"); + } + Word w = wordBuilder.Build(); + string name = w.Name; + if (words.ContainsKey(name)) { + throw new Exception( + "Word already defined: " + name); + } + words[name] = w; + lastWord = w; + if (savedWordBuilders.Count > 0) { + wordBuilder = savedWordBuilders.Pop(); + } else { + wordBuilder = null; + compiling = false; + } + }); + + /* + * immediate + * Sets the last defined word as immediate. + */ + AddNative("immediate", false, cpu => { + if (lastWord == null) { + throw new Exception("No word defined yet"); + } + lastWord.Immediate = true; + }); + + /* + * literal (immediate) + * Pops the current TOS value, and add in the current word + * the action of pushing that value. This cannot be used + * when no word is being built. + */ + WordNative wliteral = AddNative("literal", true, cpu => { + CheckCompiling(); + wordBuilder.Literal(cpu.Pop()); + }); + + /* + * compile + * Pops the current TOS value, which must be an XT (pointer + * to a word); the action of calling that word is compiled + * in the current word. + */ + WordNative wcompile = AddNative("compile", false, cpu => { + CheckCompiling(); + wordBuilder.Call(cpu.Pop().ToXT()); + }); + + /* + * postpone (immediate) + * Parses the next token as a word name, and add to the + * current word the action of calling that word. This + * basically removes immediatety from the next word. + */ + AddNative("postpone", true, cpu => { + CheckCompiling(); + string tt = Next(); + if (tt == null) { + throw new Exception( + "EOF reached (missing name)"); + } + TValue v; + bool isVal = TryParseLiteral(tt, out v); + Word w = LookupNF(tt); + if (isVal && w != null) { + throw new Exception(String.Format( + "Ambiguous: both defined word and" + + " literal: {0}", tt)); + } + if (isVal) { + wordBuilder.Literal(v); + wordBuilder.CallExt(wliteral); + } else if (w != null) { + if (w.Immediate) { + wordBuilder.CallExt(w); + } else { + wordBuilder.Literal(new TValue(0, + new TPointerXT(w))); + wordBuilder.CallExt(wcompile); + } + } else { + wordBuilder.Literal(new TValue(0, + new TPointerXT(tt))); + wordBuilder.CallExt(wcompile); + } + }); + + /* + * Interrupt compilation with an error. + */ + AddNative("exitvm", false, cpu => { + throw new Exception(); + }); + + /* + * Open a new data block. Its symbolic address is pushed + * on the stack. + */ + AddNative("new-data-block", false, cpu => { + dataBlock = new ConstData(this); + cpu.Push(new TValue(0, new TPointerBlob(dataBlock))); + }); + + /* + * Define a new data word. The data address and name are + * popped from the stack. + */ + AddNative("define-data-word", false, cpu => { + string name = cpu.Pop().ToString(); + TValue va = cpu.Pop(); + TPointerBlob tb = va.ptr as TPointerBlob; + if (tb == null) { + throw new Exception( + "Address is not a data area"); + } + Word w = new WordData(this, name, tb.Blob, va.x); + if (words.ContainsKey(name)) { + throw new Exception( + "Word already defined: " + name); + } + words[name] = w; + lastWord = w; + }); + + /* + * Get an address pointing at the end of the current + * data block. This is the address of the next byte that + * will be added. + */ + AddNative("current-data", false, cpu => { + if (dataBlock == null) { + throw new Exception( + "No current data block"); + } + cpu.Push(new TValue(dataBlock.Length, + new TPointerBlob(dataBlock))); + }); + + /* + * Add a byte value to the data block. + */ + AddNative("data-add8", false, cpu => { + if (dataBlock == null) { + throw new Exception( + "No current data block"); + } + int v = cpu.Pop(); + if (v < 0 || v > 0xFF) { + throw new Exception( + "Byte value out of range: " + v); + } + dataBlock.Add8((byte)v); + }); + + /* + * Set a byte value in the data block. + */ + AddNative("data-set8", false, cpu => { + TValue va = cpu.Pop(); + TPointerBlob tb = va.ptr as TPointerBlob; + if (tb == null) { + throw new Exception( + "Address is not a data area"); + } + int v = cpu.Pop(); + if (v < 0 || v > 0xFF) { + throw new Exception( + "Byte value out of range: " + v); + } + tb.Blob.Set8(va.x, (byte)v); + }); + + /* + * Get a byte value from a data block. + */ + AddNative("data-get8", false, new SType(1, 1), cpu => { + TValue va = cpu.Pop(); + TPointerBlob tb = va.ptr as TPointerBlob; + if (tb == null) { + throw new Exception( + "Address is not a data area"); + } + int v = tb.Blob.Read8(va.x); + cpu.Push(v); + }); + + /* + * + */ + AddNative("compile-local-read", false, cpu => { + CheckCompiling(); + wordBuilder.GetLocal(cpu.Pop().ToString()); + }); + AddNative("compile-local-write", false, cpu => { + CheckCompiling(); + wordBuilder.PutLocal(cpu.Pop().ToString()); + }); + + AddNative("ahead", true, cpu => { + CheckCompiling(); + wordBuilder.Ahead(); + }); + AddNative("begin", true, cpu => { + CheckCompiling(); + wordBuilder.Begin(); + }); + AddNative("again", true, cpu => { + CheckCompiling(); + wordBuilder.Again(); + }); + AddNative("until", true, cpu => { + CheckCompiling(); + wordBuilder.AgainIfNot(); + }); + AddNative("untilnot", true, cpu => { + CheckCompiling(); + wordBuilder.AgainIf(); + }); + AddNative("if", true, cpu => { + CheckCompiling(); + wordBuilder.AheadIfNot(); + }); + AddNative("ifnot", true, cpu => { + CheckCompiling(); + wordBuilder.AheadIf(); + }); + AddNative("then", true, cpu => { + CheckCompiling(); + wordBuilder.Then(); + }); + AddNative("cs-pick", false, cpu => { + CheckCompiling(); + wordBuilder.CSPick(cpu.Pop()); + }); + AddNative("cs-roll", false, cpu => { + CheckCompiling(); + wordBuilder.CSRoll(cpu.Pop()); + }); + AddNative("next-word", false, cpu => { + string s = Next(); + if (s == null) { + throw new Exception("No next word (EOF)"); + } + cpu.Push(StringToBlob(s)); + }); + AddNative("parse", false, cpu => { + int d = cpu.Pop(); + string s = ReadTerm(d); + cpu.Push(StringToBlob(s)); + }); + AddNative("char", false, cpu => { + int c = NextChar(); + if (c < 0) { + throw new Exception("No next character (EOF)"); + } + cpu.Push(c); + }); + AddNative("'", false, cpu => { + string name = Next(); + cpu.Push(new TValue(0, new TPointerXT(name))); + }); + + /* + * The "execute" word is valid in generated C code, but + * since it jumps to a runtime pointer, its actual stack + * effect cannot be computed in advance. + */ + AddNative("execute", false, cpu => { + cpu.Pop().Execute(this, cpu); + }); + + AddNative("[", true, cpu => { + CheckCompiling(); + compiling = false; + }); + AddNative("]", false, cpu => { + compiling = true; + }); + AddNative("(local)", false, cpu => { + CheckCompiling(); + wordBuilder.DefLocal(cpu.Pop().ToString()); + }); + AddNative("ret", true, cpu => { + CheckCompiling(); + wordBuilder.Ret(); + }); + + AddNative("drop", false, new SType(1, 0), cpu => { + cpu.Pop(); + }); + AddNative("dup", false, new SType(1, 2), cpu => { + cpu.Push(cpu.Peek(0)); + }); + AddNative("swap", false, new SType(2, 2), cpu => { + cpu.Rot(1); + }); + AddNative("over", false, new SType(2, 3), cpu => { + cpu.Push(cpu.Peek(1)); + }); + AddNative("rot", false, new SType(3, 3), cpu => { + cpu.Rot(2); + }); + AddNative("-rot", false, new SType(3, 3), cpu => { + cpu.NRot(2); + }); + + /* + * "roll" and "pick" are special in that the stack slot + * they inspect might be known only at runtime, so an + * absolute stack effect cannot be attributed. Instead, + * we simply hope that the caller knows what it is doing, + * and we use a simple stack effect for just the count + * value and picked value. + */ + AddNative("roll", false, new SType(1, 0), cpu => { + cpu.Rot(cpu.Pop()); + }); + AddNative("pick", false, new SType(1, 1), cpu => { + cpu.Push(cpu.Peek(cpu.Pop())); + }); + + AddNative("+", false, new SType(2, 1), cpu => { + TValue b = cpu.Pop(); + TValue a = cpu.Pop(); + if (b.ptr == null) { + a.x += (int)b; + cpu.Push(a); + } else if (a.ptr is TPointerBlob + && b.ptr is TPointerBlob) + { + cpu.Push(StringToBlob( + a.ToString() + b.ToString())); + } else { + throw new Exception(string.Format( + "Cannot add '{0}' to '{1}'", b, a)); + } + }); + AddNative("-", false, new SType(2, 1), cpu => { + /* + * We can subtract two pointers, provided that + * they point to the same blob. Otherwise, + * the subtraction second operand must be an + * integer. + */ + TValue b = cpu.Pop(); + TValue a = cpu.Pop(); + TPointerBlob ap = a.ptr as TPointerBlob; + TPointerBlob bp = b.ptr as TPointerBlob; + if (ap != null && bp != null && ap.Blob == bp.Blob) { + cpu.Push(new TValue(a.x - b.x)); + return; + } + int bx = b; + a.x -= bx; + cpu.Push(a); + }); + AddNative("neg", false, new SType(1, 1), cpu => { + int ax = cpu.Pop(); + cpu.Push(-ax); + }); + AddNative("*", false, new SType(2, 1), cpu => { + int bx = cpu.Pop(); + int ax = cpu.Pop(); + cpu.Push(ax * bx); + }); + AddNative("/", false, new SType(2, 1), cpu => { + int bx = cpu.Pop(); + int ax = cpu.Pop(); + cpu.Push(ax / bx); + }); + AddNative("u/", false, new SType(2, 1), cpu => { + uint bx = cpu.Pop(); + uint ax = cpu.Pop(); + cpu.Push(ax / bx); + }); + AddNative("%", false, new SType(2, 1), cpu => { + int bx = cpu.Pop(); + int ax = cpu.Pop(); + cpu.Push(ax % bx); + }); + AddNative("u%", false, new SType(2, 1), cpu => { + uint bx = cpu.Pop(); + uint ax = cpu.Pop(); + cpu.Push(ax % bx); + }); + AddNative("<", false, new SType(2, 1), cpu => { + int bx = cpu.Pop(); + int ax = cpu.Pop(); + cpu.Push(ax < bx); + }); + AddNative("<=", false, new SType(2, 1), cpu => { + int bx = cpu.Pop(); + int ax = cpu.Pop(); + cpu.Push(ax <= bx); + }); + AddNative(">", false, new SType(2, 1), cpu => { + int bx = cpu.Pop(); + int ax = cpu.Pop(); + cpu.Push(ax > bx); + }); + AddNative(">=", false, new SType(2, 1), cpu => { + int bx = cpu.Pop(); + int ax = cpu.Pop(); + cpu.Push(ax >= bx); + }); + AddNative("=", false, new SType(2, 1), cpu => { + TValue b = cpu.Pop(); + TValue a = cpu.Pop(); + cpu.Push(a.Equals(b)); + }); + AddNative("<>", false, new SType(2, 1), cpu => { + TValue b = cpu.Pop(); + TValue a = cpu.Pop(); + cpu.Push(!a.Equals(b)); + }); + AddNative("u<", false, new SType(2, 1), cpu => { + uint bx = cpu.Pop().UInt; + uint ax = cpu.Pop().UInt; + cpu.Push(new TValue(ax < bx)); + }); + AddNative("u<=", false, new SType(2, 1), cpu => { + uint bx = cpu.Pop().UInt; + uint ax = cpu.Pop().UInt; + cpu.Push(new TValue(ax <= bx)); + }); + AddNative("u>", false, new SType(2, 1), cpu => { + uint bx = cpu.Pop().UInt; + uint ax = cpu.Pop().UInt; + cpu.Push(new TValue(ax > bx)); + }); + AddNative("u>=", false, new SType(2, 1), cpu => { + uint bx = cpu.Pop(); + uint ax = cpu.Pop(); + cpu.Push(ax >= bx); + }); + AddNative("and", false, new SType(2, 1), cpu => { + uint bx = cpu.Pop(); + uint ax = cpu.Pop(); + cpu.Push(ax & bx); + }); + AddNative("or", false, new SType(2, 1), cpu => { + uint bx = cpu.Pop(); + uint ax = cpu.Pop(); + cpu.Push(ax | bx); + }); + AddNative("xor", false, new SType(2, 1), cpu => { + uint bx = cpu.Pop(); + uint ax = cpu.Pop(); + cpu.Push(ax ^ bx); + }); + AddNative("not", false, new SType(1, 1), cpu => { + uint ax = cpu.Pop(); + cpu.Push(~ax); + }); + AddNative("<<", false, new SType(2, 1), cpu => { + int count = cpu.Pop(); + if (count < 0 || count > 31) { + throw new Exception("Invalid shift count"); + } + uint ax = cpu.Pop(); + cpu.Push(ax << count); + }); + AddNative(">>", false, new SType(2, 1), cpu => { + int count = cpu.Pop(); + if (count < 0 || count > 31) { + throw new Exception("Invalid shift count"); + } + int ax = cpu.Pop(); + cpu.Push(ax >> count); + }); + AddNative("u>>", false, new SType(2, 1), cpu => { + int count = cpu.Pop(); + if (count < 0 || count > 31) { + throw new Exception("Invalid shift count"); + } + uint ax = cpu.Pop(); + cpu.Push(ax >> count); + }); + + AddNative(".", false, new SType(1, 0), cpu => { + Console.Write(" {0}", cpu.Pop().ToString()); + }); + AddNative(".s", false, SType.BLANK, cpu => { + int n = cpu.Depth; + for (int i = n - 1; i >= 0; i --) { + Console.Write(" {0}", cpu.Peek(i).ToString()); + } + }); + AddNative("putc", false, new SType(1, 0), cpu => { + Console.Write((char)cpu.Pop()); + }); + AddNative("puts", false, new SType(1, 0), cpu => { + Console.Write("{0}", cpu.Pop().ToString()); + }); + AddNative("cr", false, SType.BLANK, cpu => { + Console.WriteLine(); + }); + AddNative("eqstr", false, new SType(2, 1), cpu => { + string s2 = cpu.Pop().ToString(); + string s1 = cpu.Pop().ToString(); + cpu.Push(s1 == s2); + }); + } + + WordNative AddNative(string name, bool immediate, + WordNative.NativeRun code) + { + return AddNative(name, immediate, SType.UNKNOWN, code); + } + + WordNative AddNative(string name, bool immediate, SType stackEffect, + WordNative.NativeRun code) + { + if (words.ContainsKey(name)) { + throw new Exception( + "Word already defined: " + name); + } + WordNative w = new WordNative(this, name, code); + w.Immediate = immediate; + w.StackEffect = stackEffect; + words[name] = w; + return w; + } + + internal long NextBlobID() + { + return currentBlobID ++; + } + + int NextChar() + { + int c = delayedChar; + if (c >= 0) { + delayedChar = Int32.MinValue; + } else if (c > Int32.MinValue) { + delayedChar = -(c + 1); + c = '\n'; + } else { + c = currentInput.Read(); + } + if (c == '\r') { + if (delayedChar >= 0) { + c = delayedChar; + delayedChar = Int32.MinValue; + } else { + c = currentInput.Read(); + } + if (c != '\n') { + delayedChar = c; + c = '\n'; + } + } + return c; + } + + /* + * Un-read the character value 'c'. That value MUST be the one + * that was obtained from NextChar(). + */ + void Unread(int c) + { + if (c < 0) { + return; + } + if (delayedChar < 0) { + if (delayedChar != Int32.MinValue) { + throw new Exception( + "Already two delayed characters"); + } + delayedChar = c; + } else if (c != '\n') { + throw new Exception("Cannot delay two characters"); + } else { + delayedChar = -(delayedChar + 1); + } + } + + string Next() + { + string r = delayedToken; + if (r != null) { + delayedToken = null; + return r; + } + tokenBuilder.Length = 0; + int c; + for (;;) { + c = NextChar(); + if (c < 0) { + return null; + } + if (!IsWS(c)) { + break; + } + } + if (c == '"') { + return ParseString(); + } + for (;;) { + tokenBuilder.Append((char)c); + c = NextChar(); + if (c < 0 || IsWS(c)) { + Unread(c); + return tokenBuilder.ToString(); + } + } + } + + string ParseCCode() + { + SType stackEffect; + string r = ParseCCode(out stackEffect); + if (stackEffect.IsKnown) { + throw new Exception( + "Stack effect forbidden in this declaration"); + } + return r; + } + + string ParseCCode(out SType stackEffect) + { + string s = ParseCCodeNF(out stackEffect); + if (s == null) { + throw new Exception("Error while parsing C code"); + } + return s; + } + + string ParseCCodeNF(out SType stackEffect) + { + stackEffect = SType.UNKNOWN; + for (;;) { + int c = NextChar(); + if (c < 0) { + return null; + } + if (!IsWS(c)) { + if (c == '(') { + if (stackEffect.IsKnown) { + Unread(c); + return null; + } + stackEffect = ParseStackEffectNF(); + if (!stackEffect.IsKnown) { + return null; + } + continue; + } else if (c != '{') { + Unread(c); + return null; + } + break; + } + } + StringBuilder sb = new StringBuilder(); + int count = 1; + for (;;) { + int c = NextChar(); + if (c < 0) { + return null; + } + switch (c) { + case '{': + count ++; + break; + case '}': + if (-- count == 0) { + return sb.ToString(); + } + break; + } + sb.Append((char)c); + } + } + + /* + * Parse a stack effect declaration. This method assumes that the + * opening parenthesis has just been read. If the parsing fails, + * then this method returns SType.UNKNOWN. + */ + SType ParseStackEffectNF() + { + bool seenSep = false; + bool seenBang = false; + int din = 0, dout = 0; + for (;;) { + string t = Next(); + if (t == null) { + return SType.UNKNOWN; + } + if (t == "--") { + if (seenSep) { + return SType.UNKNOWN; + } + seenSep = true; + } else if (t == ")") { + if (seenSep) { + if (seenBang && dout == 1) { + dout = -1; + } + return new SType(din, dout); + } else { + return SType.UNKNOWN; + } + } else { + if (seenSep) { + if (dout == 0 && t == "!") { + seenBang = true; + } + dout ++; + } else { + din ++; + } + } + } + } + + string ParseString() + { + StringBuilder sb = new StringBuilder(); + sb.Append('"'); + bool lcwb = false; + int hexNum = 0; + int acc = 0; + for (;;) { + int c = NextChar(); + if (c < 0) { + throw new Exception( + "Unfinished literal string"); + } + if (hexNum > 0) { + int d = HexVal(c); + if (d < 0) { + throw new Exception(String.Format( + "not an hex digit: U+{0:X4}", + c)); + } + acc = (acc << 4) + d; + if (-- hexNum == 0) { + sb.Append((char)acc); + acc = 0; + } + } else if (lcwb) { + lcwb = false; + switch (c) { + case '\n': SkipNL(); break; + case 'x': + hexNum = 2; + break; + case 'u': + hexNum = 4; + break; + default: + sb.Append(SingleCharEscape(c)); + break; + } + } else { + switch (c) { + case '"': + return sb.ToString(); + case '\\': + lcwb = true; + break; + default: + sb.Append((char)c); + break; + } + } + } + } + + static char SingleCharEscape(int c) + { + switch (c) { + case 'n': return '\n'; + case 'r': return '\r'; + case 't': return '\t'; + case 's': return ' '; + default: + return (char)c; + } + } + + /* + * A backslash+newline sequence occurred in a literal string; we + * check and consume the newline escape sequence (whitespace at + * start of next line, then a double-quote character). + */ + void SkipNL() + { + for (;;) { + int c = NextChar(); + if (c < 0) { + throw new Exception("EOF in literal string"); + } + if (c == '\n') { + throw new Exception( + "Unescaped newline in literal string"); + } + if (IsWS(c)) { + continue; + } + if (c == '"') { + return; + } + throw new Exception( + "Invalid newline escape in literal string"); + } + } + + static char DecodeCharConst(string t) + { + if (t.Length == 1 && t[0] != '\\') { + return t[0]; + } + if (t.Length >= 2 && t[0] == '\\') { + switch (t[1]) { + case 'x': + if (t.Length == 4) { + int x = DecHex(t.Substring(2)); + if (x >= 0) { + return (char)x; + } + } + break; + case 'u': + if (t.Length == 6) { + int x = DecHex(t.Substring(2)); + if (x >= 0) { + return (char)x; + } + } + break; + default: + if (t.Length == 2) { + return SingleCharEscape(t[1]); + } + break; + } + } + throw new Exception("Invalid literal char: `" + t); + } + + static int DecHex(string s) + { + int acc = 0; + foreach (char c in s) { + int d = HexVal(c); + if (d < 0) { + return -1; + } + acc = (acc << 4) + d; + } + return acc; + } + + static int HexVal(int c) + { + if (c >= '0' && c <= '9') { + return c - '0'; + } else if (c >= 'A' && c <= 'F') { + return c - ('A' - 10); + } else if (c >= 'a' && c <= 'f') { + return c - ('a' - 10); + } else { + return -1; + } + } + + string ReadTerm(int ct) + { + StringBuilder sb = new StringBuilder(); + for (;;) { + int c = NextChar(); + if (c < 0) { + throw new Exception(String.Format( + "EOF reached before U+{0:X4}", ct)); + } + if (c == ct) { + return sb.ToString(); + } + sb.Append((char)c); + } + } + + static bool IsWS(int c) + { + return c <= 32; + } + + void ProcessInput(TextReader tr) + { + this.currentInput = tr; + delayedChar = -1; + Word w = new WordNative(this, "toplevel", + xcpu => { CompileStep(xcpu); }); + CPU cpu = new CPU(); + Opcode[] code = new Opcode[] { + new OpcodeCall(w), + new OpcodeJumpUncond(-2) + }; + quitRunLoop = false; + cpu.Enter(code, 0); + for (;;) { + if (quitRunLoop) { + break; + } + Opcode op = cpu.ipBuf[cpu.ipOff ++]; + op.Run(cpu); + } + } + + void CompileStep(CPU cpu) + { + string tt = Next(); + if (tt == null) { + if (compiling) { + throw new Exception("EOF while compiling"); + } + quitRunLoop = true; + return; + } + TValue v; + bool isVal = TryParseLiteral(tt, out v); + Word w = LookupNF(tt); + if (isVal && w != null) { + throw new Exception(String.Format( + "Ambiguous: both defined word and literal: {0}", + tt)); + } + if (compiling) { + if (isVal) { + wordBuilder.Literal(v); + } else if (w != null) { + if (w.Immediate) { + w.Run(cpu); + } else { + wordBuilder.CallExt(w); + } + } else { + wordBuilder.Call(tt); + } + } else { + if (isVal) { + cpu.Push(v); + } else if (w != null) { + w.Run(cpu); + } else { + throw new Exception(String.Format( + "Unknown word: '{0}'", tt)); + } + } + } + + string GetCCode(string name) + { + string ccode; + allCCode.TryGetValue(name, out ccode); + return ccode; + } + + void Generate(string outBase, string coreRun, + params string[] entryPoints) + { + /* + * Gather all words that are part of the generated + * code. This is done by exploring references + * transitively. All such words are thus implicitly + * resolved. + */ + IDictionary<string, Word> wordSet = + new SortedDictionary<string, Word>( + StringComparer.Ordinal); + Queue<Word> tx = new Queue<Word>(); + foreach (string ep in entryPoints) { + if (wordSet.ContainsKey(ep)) { + continue; + } + Word w = Lookup(ep); + wordSet[w.Name] = w; + tx.Enqueue(w); + } + while (tx.Count > 0) { + Word w = tx.Dequeue(); + foreach (Word w2 in w.GetReferences()) { + if (wordSet.ContainsKey(w2.Name)) { + continue; + } + wordSet[w2.Name] = w2; + tx.Enqueue(w2); + } + } + + /* + * Do flow analysis. + */ + if (enableFlowAnalysis) { + foreach (string ep in entryPoints) { + Word w = wordSet[ep]; + w.AnalyseFlow(); + Console.WriteLine("{0}: ds={1} rs={2}", + ep, w.MaxDataStack, w.MaxReturnStack); + if (w.MaxDataStack > dsLimit) { + throw new Exception("'" + ep + + "' exceeds data stack limit"); + } + if (w.MaxReturnStack > rsLimit) { + throw new Exception("'" + ep + + "' exceeds return stack" + + " limit"); + } + } + } + + /* + * Gather referenced data areas and compute their + * addresses in the generated data block. The address + * 0 in the data block is unaffected so that no + * valid runtime pointer is equal to null. + */ + IDictionary<long, ConstData> blocks = + new SortedDictionary<long, ConstData>(); + foreach (Word w in wordSet.Values) { + foreach (ConstData cd in w.GetDataBlocks()) { + blocks[cd.ID] = cd; + } + } + int dataLen = 1; + foreach (ConstData cd in blocks.Values) { + cd.Address = dataLen; + dataLen += cd.Length; + } + + /* + * Generated code is a sequence of "slot numbers", each + * referencing either a piece of explicit C code, or an + * entry in the table of interpreted words. + * + * Opcodes other than "call" get the slots 0 to 6: + * + * 0 ret no argument + * 1 const signed value + * 2 get local local number + * 3 put local local number + * 4 jump signed offset + * 5 jump if signed offset + * 6 jump if not signed offset + * + * The argument, if any, is in "7E" format: the value is + * encoded in 7-bit chunk, with big-endian signed + * convention. Each 7-bit chunk is encoded over one byte; + * the upper bit is 1 for all chunks except the last one. + * + * Words with explicit C code get the slot numbers + * immediately after 6. Interpreted words come afterwards. + */ + IDictionary<string, int> slots = new Dictionary<string, int>(); + int curSlot = 7; + + /* + * Get explicit C code for words which have such code. + * We use string equality on C code so that words with + * identical implementations get merged. + * + * We also check that words with no explicit C code are + * interpreted. + */ + IDictionary<string, int> ccodeUni = + new Dictionary<string, int>(); + IDictionary<int, string> ccodeNames = + new Dictionary<int, string>(); + foreach (Word w in wordSet.Values) { + string ccode = GetCCode(w.Name); + if (ccode == null) { + if (w is WordNative) { + throw new Exception(String.Format( + "No C code for native '{0}'", + w.Name)); + } + continue; + } + int sn; + if (ccodeUni.ContainsKey(ccode)) { + sn = ccodeUni[ccode]; + ccodeNames[sn] += " " + EscapeCComment(w.Name); + } else { + sn = curSlot ++; + ccodeUni[ccode] = sn; + ccodeNames[sn] = EscapeCComment(w.Name); + } + slots[w.Name] = sn; + w.Slot = sn; + } + + /* + * Assign slot values to all remaining words; we know they + * are all interpreted. + */ + int slotInterpreted = curSlot; + foreach (Word w in wordSet.Values) { + if (GetCCode(w.Name) != null) { + continue; + } + int sn = curSlot ++; + slots[w.Name] = sn; + w.Slot = sn; + } + int numInterpreted = curSlot - slotInterpreted; + + /* + * Verify that all entry points are interpreted words. + */ + foreach (string ep in entryPoints) { + if (GetCCode(ep) != null) { + throw new Exception( + "Non-interpreted entry point"); + } + } + + /* + * Compute the code block. Each word (without any C code) + * yields some CodeElement instances. + */ + List<CodeElement> gcodeList = new List<CodeElement>(); + CodeElement[] interpretedEntry = + new CodeElement[numInterpreted]; + foreach (Word w in wordSet.Values) { + if (GetCCode(w.Name) != null) { + continue; + } + int n = gcodeList.Count; + w.GenerateCodeElements(gcodeList); + interpretedEntry[w.Slot - slotInterpreted] = + gcodeList[n]; + } + CodeElement[] gcode = gcodeList.ToArray(); + + /* + * If there are less than 256 words in total (C + + * interpreted) then we can use "one-byte code" which is + * more compact when the number of words is in the + * 128..255 range. + */ + bool oneByteCode; + if (slotInterpreted + numInterpreted >= 256) { + Console.WriteLine("WARNING: more than 255 words"); + oneByteCode = false; + } else { + oneByteCode = true; + } + + /* + * Compute all addresses and offsets. This loops until + * the addresses stabilize. + */ + int totalLen = -1; + int[] gcodeLen = new int[gcode.Length]; + for (;;) { + for (int i = 0; i < gcode.Length; i ++) { + gcodeLen[i] = gcode[i].GetLength(oneByteCode); + } + int off = 0; + for (int i = 0; i < gcode.Length; i ++) { + gcode[i].Address = off; + gcode[i].LastLength = gcodeLen[i]; + off += gcodeLen[i]; + } + if (off == totalLen) { + break; + } + totalLen = off; + } + + /* + * Produce output file. + */ + using (TextWriter tw = File.CreateText(outBase + ".c")) { + tw.NewLine = "\n"; + + tw.WriteLine("{0}", +@"/* Automatically generated code; do not modify directly. */ + +#include <stddef.h> +#include <stdint.h> + +typedef struct { + uint32_t *dp; + uint32_t *rp; + const unsigned char *ip; +} t0_context; + +static uint32_t +t0_parse7E_unsigned(const unsigned char **p) +{ + uint32_t x; + + x = 0; + for (;;) { + unsigned y; + + y = *(*p) ++; + x = (x << 7) | (uint32_t)(y & 0x7F); + if (y < 0x80) { + return x; + } + } +} + +static int32_t +t0_parse7E_signed(const unsigned char **p) +{ + int neg; + uint32_t x; + + neg = ((**p) >> 6) & 1; + x = (uint32_t)-neg; + for (;;) { + unsigned y; + + y = *(*p) ++; + x = (x << 7) | (uint32_t)(y & 0x7F); + if (y < 0x80) { + if (neg) { + return -(int32_t)~x - 1; + } else { + return (int32_t)x; + } + } + } +} + +#define T0_VBYTE(x, n) (unsigned char)((((uint32_t)(x) >> (n)) & 0x7F) | 0x80) +#define T0_FBYTE(x, n) (unsigned char)(((uint32_t)(x) >> (n)) & 0x7F) +#define T0_SBYTE(x) (unsigned char)((((uint32_t)(x) >> 28) + 0xF8) ^ 0xF8) +#define T0_INT1(x) T0_FBYTE(x, 0) +#define T0_INT2(x) T0_VBYTE(x, 7), T0_FBYTE(x, 0) +#define T0_INT3(x) T0_VBYTE(x, 14), T0_VBYTE(x, 7), T0_FBYTE(x, 0) +#define T0_INT4(x) T0_VBYTE(x, 21), T0_VBYTE(x, 14), T0_VBYTE(x, 7), T0_FBYTE(x, 0) +#define T0_INT5(x) T0_SBYTE(x), T0_VBYTE(x, 21), T0_VBYTE(x, 14), T0_VBYTE(x, 7), T0_FBYTE(x, 0) + +/* static const unsigned char t0_datablock[]; */ +"); + + /* + * Add declarations (not definitions) for the + * entry point initialisation functions, and the + * runner. + */ + tw.WriteLine(); + foreach (string ep in entryPoints) { + tw.WriteLine("void {0}_init_{1}(void *t0ctx);", + coreRun, ep); + } + tw.WriteLine(); + tw.WriteLine("void {0}_run(void *t0ctx);", coreRun); + + /* + * Add preamble elements here. They may be needed + * for evaluating constant expressions in the + * code block. + */ + foreach (string pp in extraCode) { + tw.WriteLine(); + tw.WriteLine("{0}", pp); + } + + BlobWriter bw; + tw.WriteLine(); + tw.Write("static const unsigned char" + + " t0_datablock[] = {"); + bw = new BlobWriter(tw, 78, 1); + bw.Append((byte)0); + foreach (ConstData cd in blocks.Values) { + cd.Encode(bw); + } + tw.WriteLine(); + tw.WriteLine("};"); + + tw.WriteLine(); + tw.Write("static const unsigned char" + + " t0_codeblock[] = {"); + bw = new BlobWriter(tw, 78, 1); + foreach (CodeElement ce in gcode) { + ce.Encode(bw, oneByteCode); + } + tw.WriteLine(); + tw.WriteLine("};"); + + tw.WriteLine(); + tw.Write("static const uint16_t t0_caddr[] = {"); + for (int i = 0; i < interpretedEntry.Length; i ++) { + if (i != 0) { + tw.Write(','); + } + tw.WriteLine(); + tw.Write("\t{0}", interpretedEntry[i].Address); + } + tw.WriteLine(); + tw.WriteLine("};"); + + tw.WriteLine(); + tw.WriteLine("#define T0_INTERPRETED {0}", + slotInterpreted); + tw.WriteLine(); + tw.WriteLine("{0}", +@"#define T0_ENTER(ip, rp, slot) do { \ + const unsigned char *t0_newip; \ + uint32_t t0_lnum; \ + t0_newip = &t0_codeblock[t0_caddr[(slot) - T0_INTERPRETED]]; \ + t0_lnum = t0_parse7E_unsigned(&t0_newip); \ + (rp) += t0_lnum; \ + *((rp) ++) = (uint32_t)((ip) - &t0_codeblock[0]) + (t0_lnum << 16); \ + (ip) = t0_newip; \ + } while (0)"); + tw.WriteLine(); + tw.WriteLine("{0}", +@"#define T0_DEFENTRY(name, slot) \ +void \ +name(void *ctx) \ +{ \ + t0_context *t0ctx = ctx; \ + t0ctx->ip = &t0_codeblock[0]; \ + T0_ENTER(t0ctx->ip, t0ctx->rp, slot); \ +}"); + + tw.WriteLine(); + foreach (string ep in entryPoints) { + tw.WriteLine("T0_DEFENTRY({0}, {1})", + coreRun + "_init_" + ep, + wordSet[ep].Slot); + } + tw.WriteLine(); + if (oneByteCode) { + tw.WriteLine("{0}", +@"#define T0_NEXT(t0ipp) (*(*(t0ipp)) ++)"); + } else { + tw.WriteLine("{0}", +@"#define T0_NEXT(t0ipp) t0_parse7E_unsigned(t0ipp)"); + } + tw.WriteLine(); + tw.WriteLine("void"); + tw.WriteLine("{0}_run(void *t0ctx)", coreRun); + tw.WriteLine("{0}", +@"{ + uint32_t *dp, *rp; + const unsigned char *ip; + +#define T0_LOCAL(x) (*(rp - 2 - (x))) +#define T0_POP() (*-- dp) +#define T0_POPi() (*(int32_t *)(-- dp)) +#define T0_PEEK(x) (*(dp - 1 - (x))) +#define T0_PEEKi(x) (*(int32_t *)(dp - 1 - (x))) +#define T0_PUSH(v) do { *dp = (v); dp ++; } while (0) +#define T0_PUSHi(v) do { *(int32_t *)dp = (v); dp ++; } while (0) +#define T0_RPOP() (*-- rp) +#define T0_RPOPi() (*(int32_t *)(-- rp)) +#define T0_RPUSH(v) do { *rp = (v); rp ++; } while (0) +#define T0_RPUSHi(v) do { *(int32_t *)rp = (v); rp ++; } while (0) +#define T0_ROLL(x) do { \ + size_t t0len = (size_t)(x); \ + uint32_t t0tmp = *(dp - 1 - t0len); \ + memmove(dp - t0len - 1, dp - t0len, t0len * sizeof *dp); \ + *(dp - 1) = t0tmp; \ +} while (0) +#define T0_SWAP() do { \ + uint32_t t0tmp = *(dp - 2); \ + *(dp - 2) = *(dp - 1); \ + *(dp - 1) = t0tmp; \ +} while (0) +#define T0_ROT() do { \ + uint32_t t0tmp = *(dp - 3); \ + *(dp - 3) = *(dp - 2); \ + *(dp - 2) = *(dp - 1); \ + *(dp - 1) = t0tmp; \ +} while (0) +#define T0_NROT() do { \ + uint32_t t0tmp = *(dp - 1); \ + *(dp - 1) = *(dp - 2); \ + *(dp - 2) = *(dp - 3); \ + *(dp - 3) = t0tmp; \ +} while (0) +#define T0_PICK(x) do { \ + uint32_t t0depth = (x); \ + T0_PUSH(T0_PEEK(t0depth)); \ +} while (0) +#define T0_CO() do { \ + goto t0_exit; \ +} while (0) +#define T0_RET() goto t0_next + + dp = ((t0_context *)t0ctx)->dp; + rp = ((t0_context *)t0ctx)->rp; + ip = ((t0_context *)t0ctx)->ip; + goto t0_next; + for (;;) { + uint32_t t0x; + + t0_next: + t0x = T0_NEXT(&ip); + if (t0x < T0_INTERPRETED) { + switch (t0x) { + int32_t t0off; + + case 0: /* ret */ + t0x = T0_RPOP(); + rp -= (t0x >> 16); + t0x &= 0xFFFF; + if (t0x == 0) { + ip = NULL; + goto t0_exit; + } + ip = &t0_codeblock[t0x]; + break; + case 1: /* literal constant */ + T0_PUSHi(t0_parse7E_signed(&ip)); + break; + case 2: /* read local */ + T0_PUSH(T0_LOCAL(t0_parse7E_unsigned(&ip))); + break; + case 3: /* write local */ + T0_LOCAL(t0_parse7E_unsigned(&ip)) = T0_POP(); + break; + case 4: /* jump */ + t0off = t0_parse7E_signed(&ip); + ip += t0off; + break; + case 5: /* jump if */ + t0off = t0_parse7E_signed(&ip); + if (T0_POP()) { + ip += t0off; + } + break; + case 6: /* jump if not */ + t0off = t0_parse7E_signed(&ip); + if (!T0_POP()) { + ip += t0off; + } + break;"); + + SortedDictionary<int, string> nccode = + new SortedDictionary<int, string>(); + foreach (string k in ccodeUni.Keys) { + nccode[ccodeUni[k]] = k; + } + foreach (int sn in nccode.Keys) { + tw.WriteLine( +@" case {0}: {{ + /* {1} */ +{2} + }} + break;", sn, ccodeNames[sn], nccode[sn]); + } + + tw.WriteLine( +@" } + + } else { + T0_ENTER(ip, rp, t0x); + } + } +t0_exit: + ((t0_context *)t0ctx)->dp = dp; + ((t0_context *)t0ctx)->rp = rp; + ((t0_context *)t0ctx)->ip = ip; +}"); + + /* + * Add the "postamblr" elements here. These are + * elements that may need access to the data + * block or code block, so they must occur after + * their definition. + */ + foreach (string pp in extraCodeDefer) { + tw.WriteLine(); + tw.WriteLine("{0}", pp); + } + } + + int codeLen = 0; + foreach (CodeElement ce in gcode) { + codeLen += ce.GetLength(oneByteCode); + } + int dataBlockLen = 0; + foreach (ConstData cd in blocks.Values) { + dataBlockLen += cd.Length; + } + + /* + * Write some statistics on produced code. + */ + Console.WriteLine("code length: {0,6} byte(s)", codeLen); + Console.WriteLine("data length: {0,6} byte(s)", dataLen); + Console.WriteLine("total words: {0} (interpreted: {1})", + slotInterpreted + numInterpreted, numInterpreted); + } + + internal Word Lookup(string name) + { + Word w = LookupNF(name); + if (w != null) { + return w; + } + throw new Exception(String.Format("No such word: '{0}'", name)); + } + + internal Word LookupNF(string name) + { + Word w; + words.TryGetValue(name, out w); + return w; + } + + internal TValue StringToBlob(string s) + { + return new TValue(0, new TPointerBlob(this, s)); + } + + internal bool TryParseLiteral(string tt, out TValue tv) + { + tv = new TValue(0); + if (tt.StartsWith("\"")) { + tv = StringToBlob(tt.Substring(1)); + return true; + } + if (tt.StartsWith("`")) { + tv = DecodeCharConst(tt.Substring(1)); + return true; + } + bool neg = false; + if (tt.StartsWith("-")) { + neg = true; + tt = tt.Substring(1); + } else if (tt.StartsWith("+")) { + tt = tt.Substring(1); + } + uint radix = 10; + if (tt.StartsWith("0x") || tt.StartsWith("0X")) { + radix = 16; + tt = tt.Substring(2); + } else if (tt.StartsWith("0b") || tt.StartsWith("0B")) { + radix = 2; + tt = tt.Substring(2); + } + if (tt.Length == 0) { + return false; + } + uint acc = 0; + bool overflow = false; + uint maxV = uint.MaxValue / radix; + foreach (char c in tt) { + int d = HexVal(c); + if (d < 0 || d >= radix) { + return false; + } + if (acc > maxV) { + overflow = true; + } + acc *= radix; + if ((uint)d > uint.MaxValue - acc) { + overflow = true; + } + acc += (uint)d; + } + int x = (int)acc; + if (neg) { + if (acc > (uint)0x80000000) { + overflow = true; + } + x = -x; + } + if (overflow) { + throw new Exception( + "invalid literal integer (overflow)"); + } + tv = x; + return true; + } + + int ParseInteger(string tt) + { + TValue tv; + if (!TryParseLiteral(tt, out tv)) { + throw new Exception("not an integer: " + ToString()); + } + return (int)tv; + } + + void CheckCompiling() + { + if (!compiling) { + throw new Exception("Not in compilation mode"); + } + } + + static string EscapeCComment(string s) + { + StringBuilder sb = new StringBuilder(); + foreach (char c in s) { + if (c >= 33 && c <= 126 && c != '%') { + sb.Append(c); + } else if (c < 0x100) { + sb.AppendFormat("%{0:X2}", (int)c); + } else if (c < 0x800) { + sb.AppendFormat("%{0:X2}%{0:X2}", + ((int)c >> 6) | 0xC0, + ((int)c & 0x3F) | 0x80); + } else { + sb.AppendFormat("%{0:X2}%{0:X2}%{0:X2}", + ((int)c >> 12) | 0xE0, + (((int)c >> 6) & 0x3F) | 0x80, + ((int)c & 0x3F) | 0x80); + } + } + return sb.ToString().Replace("*/", "%2A/"); + } +} diff --git a/T0/TPointerBase.cs b/T0/TPointerBase.cs new file mode 100644 index 000000000000..f996d8d878cf --- /dev/null +++ b/T0/TPointerBase.cs @@ -0,0 +1,64 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class TPointerBase { + + /* obsolete + internal virtual TValue Get(TValue vp) + { + throw new Exception( + "cannot get values from this pointer"); + } + + internal virtual void Set(TValue vp, TValue nval) + { + throw new Exception( + "cannot set values to this pointer"); + } + */ + + internal virtual bool ToBool(TValue vp) + { + return true; + } + + internal virtual void Execute(T0Comp ctx, CPU cpu) + { + throw new Exception("value is not an xt: " + ToString()); + } + + internal virtual string ToString(TValue vp) + { + return String.Format("{0}+{1}", + GetType().Name, vp.x); + } + + internal virtual bool Equals(TPointerBase tp) + { + return this == tp; + } +} diff --git a/T0/TPointerBlob.cs b/T0/TPointerBlob.cs new file mode 100644 index 000000000000..d4aeff647c52 --- /dev/null +++ b/T0/TPointerBlob.cs @@ -0,0 +1,75 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class TPointerBlob : TPointerBase { + + internal ConstData Blob { get; private set; } + + internal TPointerBlob(ConstData cd) + { + this.Blob = cd; + } + + internal TPointerBlob(T0Comp owner, string s) + { + Blob = new ConstData(owner); + Blob.AddString(s); + } + + /* obsolete + internal override TValue Get8(TValue vp) + { + return new TValue((int)Blob.Read8(vp.x)); + } + + internal override TValue Get16(TValue vp) + { + return new TValue((int)Blob.Read16(vp.x)); + } + + internal override TValue Get24(TValue vp) + { + return new TValue((int)Blob.Read24(vp.x)); + } + + internal override TValue Get32(TValue vp) + { + return new TValue((int)Blob.Read32(vp.x)); + } + */ + + internal override string ToString(TValue vp) + { + return Blob.ToString(vp.x); + } + + internal override bool Equals(TPointerBase tp) + { + TPointerBlob tb = tp as TPointerBlob; + return tb != null && Blob == tb.Blob; + } +} diff --git a/T0/TPointerExpr.cs b/T0/TPointerExpr.cs new file mode 100644 index 000000000000..314b27208971 --- /dev/null +++ b/T0/TPointerExpr.cs @@ -0,0 +1,97 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; + +class TPointerExpr : TPointerBase { + + string expr; + int min, max; + + internal TPointerExpr(string expr, int min, int max) + { + this.expr = expr; + this.min = min; + this.max = max; + } + + internal override bool ToBool(TValue vp) + { + throw new Exception("Cannot evaluate C-expr at compile time"); + } + + internal override string ToString(TValue vp) + { + return ToCExpr(vp.x); + } + + internal string ToCExpr(int off) + { + if (off == 0) { + return expr; + } else if (off > 0) { + return String.Format( + "(uint32_t)({0}) + {1}", expr, off); + } else { + return String.Format( + "(uint32_t)({0}) - {1}", expr, -(long)off); + } + } + + internal int GetMaxBitLength(int off) + { + long rmin = (long)min + off; + long rmax = (long)max + off; + int numBits = 1; + if (rmin < 0) { + numBits = Math.Max(numBits, BitLength(rmin)); + } + if (rmax > 0) { + numBits = Math.Max(numBits, BitLength(rmax)); + } + return Math.Min(numBits, 32); + } + + /* + * Get the minimal bit length of a value. This is for a signed + * representation: the length includes a sign bit. Thus, the + * returned value will be at least 1. + */ + static int BitLength(long v) + { + int num = 1; + if (v < 0) { + while (v != -1) { + num ++; + v >>= 1; + } + } else { + while (v != 0) { + num ++; + v >>= 1; + } + } + return num; + } +} diff --git a/T0/TPointerNull.cs b/T0/TPointerNull.cs new file mode 100644 index 000000000000..f8eb11e42f20 --- /dev/null +++ b/T0/TPointerNull.cs @@ -0,0 +1,44 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class TPointerNull : TPointerBase { + + internal override bool ToBool(TValue vp) + { + return false; + } + + internal override string ToString(TValue vp) + { + return "null"; + } + + internal override bool Equals(TPointerBase tp) + { + return tp is TPointerNull; + } +} diff --git a/T0/TPointerXT.cs b/T0/TPointerXT.cs new file mode 100644 index 000000000000..883f31296417 --- /dev/null +++ b/T0/TPointerXT.cs @@ -0,0 +1,73 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class TPointerXT : TPointerBase { + + internal string Name { + get; private set; + } + + internal Word Target { + get; private set; + } + + internal TPointerXT(string name) + { + this.Name = name; + this.Target = null; + } + + internal TPointerXT(Word target) + { + this.Name = target.Name; + this.Target = target; + } + + internal void Resolve(T0Comp ctx) + { + if (Target == null) { + Target = ctx.Lookup(Name); + } + } + + internal override void Execute(T0Comp ctx, CPU cpu) + { + Resolve(ctx); + Target.Run(cpu); + } + + internal override string ToString(TValue vp) + { + return String.Format("<'{0}>", Name); + } + + internal override bool Equals(TPointerBase tp) + { + TPointerXT tx = tp as TPointerXT; + return tx != null && Name == tx.Name; + } +} diff --git a/T0/TValue.cs b/T0/TValue.cs new file mode 100644 index 000000000000..e4f225574c8e --- /dev/null +++ b/T0/TValue.cs @@ -0,0 +1,231 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +/* + * Each value is represented with a TValue structure. Integers use the 'x' + * field, and 'ptr' is null; for pointers, the 'ptr' field is used, and the + * 'x' is then an offset in the object represented by 'ptr'. + */ + +struct TValue { + + internal int x; + internal TPointerBase ptr; + + internal TValue(int x) + { + this.x = x; + this.ptr = null; + } + + internal TValue(uint x) + { + this.x = (int)x; + this.ptr = null; + } + + internal TValue(bool b) + { + this.x = b ? -1 : 0; + this.ptr = null; + } + + internal TValue(int x, TPointerBase ptr) + { + this.x = x; + this.ptr = ptr; + } + + /* + * Convert this value to a boolean; integer 0 and null pointer are + * 'false', other values are 'true'. + */ + internal bool Bool { + get { + if (ptr == null) { + return x != 0; + } else { + return ptr.ToBool(this); + } + } + } + + /* + * Get this value as an integer. Pointers cannot be converted to + * integers. + */ + internal int Int { + get { + if (ptr == null) { + return x; + } + throw new Exception("not an integer: " + ToString()); + } + } + + /* + * Get this value as an unsigned integer. This is the integer + * value, reduced modulo 2^32 in the 0..2^32-1 range. + */ + internal uint UInt { + get { + return (uint)Int; + } + } + + /* + * String format of integers uses decimal representation. For + * pointers, this depends on the pointed-to value. + */ + public override string ToString() + { + if (ptr == null) { + return String.Format("{0}", x); + } else { + return ptr.ToString(this); + } + } + + /* + * If this value is an XT, then execute it. Otherwise, an exception + * is thrown. + */ + internal void Execute(T0Comp ctx, CPU cpu) + { + ToXT().Execute(ctx, cpu); + } + + /* + * Convert this value to an XT. On failure, an exception is thrown. + */ + internal TPointerXT ToXT() + { + TPointerXT xt = ptr as TPointerXT; + if (xt == null) { + throw new Exception( + "value is not an xt: " + ToString()); + } + return xt; + } + + /* + * Compare this value to another. + */ + internal bool Equals(TValue v) + { + if (x != v.x) { + return false; + } + if (ptr == v.ptr) { + return true; + } + if (ptr == null || v.ptr == null) { + return false; + } + return ptr.Equals(v.ptr); + } + + public static implicit operator TValue(bool val) + { + return new TValue(val); + } + + public static implicit operator TValue(sbyte val) + { + return new TValue((int)val); + } + + public static implicit operator TValue(byte val) + { + return new TValue((int)val); + } + + public static implicit operator TValue(short val) + { + return new TValue((int)val); + } + + public static implicit operator TValue(ushort val) + { + return new TValue((int)val); + } + + public static implicit operator TValue(char val) + { + return new TValue((int)val); + } + + public static implicit operator TValue(int val) + { + return new TValue((int)val); + } + + public static implicit operator TValue(uint val) + { + return new TValue((int)val); + } + + public static implicit operator bool(TValue v) + { + return v.Bool; + } + + public static implicit operator sbyte(TValue v) + { + return (sbyte)v.Int; + } + + public static implicit operator byte(TValue v) + { + return (byte)v.Int; + } + + public static implicit operator short(TValue v) + { + return (short)v.Int; + } + + public static implicit operator ushort(TValue v) + { + return (ushort)v.Int; + } + + public static implicit operator char(TValue v) + { + return (char)v.Int; + } + + public static implicit operator int(TValue v) + { + return (int)v.Int; + } + + public static implicit operator uint(TValue v) + { + return (uint)v.Int; + } +} diff --git a/T0/Word.cs b/T0/Word.cs new file mode 100644 index 000000000000..2dfb66ef0691 --- /dev/null +++ b/T0/Word.cs @@ -0,0 +1,172 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +/* + * A "word" is a function with a name. Words can be either native or + * interpreted; native words are implemented as some in-compiler special + * code. + * + * Some native words (not all of them) have a C implementation and can + * thus be part of the generated C code. Native words with no C + * implementation can be used only during compilation; this is typically + * the case for words that support the syntax (e.g. 'if'). + */ + +abstract class Word { + + /* + * The compiler context for this word. + */ + internal T0Comp TC { + get; private set; + } + + /* + * Immediate words are executed immediately when encountered in the + * source code, even while compiling another word. + */ + internal bool Immediate { + get; set; + } + + /* + * Each word has a unique name. Names are case-sensitive. + */ + internal string Name { + get; private set; + } + + /* + * Words are allocated slot numbers when output code is generated. + */ + internal int Slot { + get; set; + } + + /* + * Each word may have a known stack effect. + */ + internal SType StackEffect { + get; set; + } + + internal Word(T0Comp owner, string name) + { + TC = owner; + Name = name; + StackEffect = SType.UNKNOWN; + } + + /* + * Resolving a word means looking up all references to external + * words. + */ + internal virtual void Resolve() + { + } + + /* + * Execute this word. If the word is native, then its code is + * run right away; if the word is interpreted, then the entry + * sequence is executed. + */ + internal virtual void Run(CPU cpu) + { + throw new Exception(String.Format( + "cannot run '{0}' at compile-time", Name)); + } + + /* + * All words may have an explicit C implementations. To be part + * of the generated C code, a word must either be interpreted, + * or have an explicit C implementation, or both. + */ + internal string CCode { + get; set; + } + + /* + * Get all words referenced from this one. This implies + * resolving the word. + */ + internal virtual List<Word> GetReferences() + { + return new List<Word>(); + } + + /* + * Get all data blocks directly referenced from this one. This + * implies resolving the word. + */ + internal virtual List<ConstData> GetDataBlocks() + { + return new List<ConstData>(); + } + + /* + * Produce the code elements for this word. + */ + internal virtual void GenerateCodeElements(List<CodeElement> dst) + { + throw new Exception("Word does not yield code elements"); + } + + /* + * Compute/verify stack effect for this word. + */ + internal virtual void AnalyseFlow() + { + } + + /* + * Get maximum data stack usage for this word. This is the number + * of extra slots that this word may need on the data stack. If + * the stack effect is not known, this returns -1. + */ + internal virtual int MaxDataStack { + get { + SType se = StackEffect; + if (!se.IsKnown) { + return -1; + } + if (se.NoExit) { + return 0; + } else { + return Math.Min(0, se.DataOut - se.DataIn); + } + } + } + + /* + * Get maximum return stack usage for this word. + */ + internal virtual int MaxReturnStack { + get { + return 0; + } + } +} diff --git a/T0/WordBuilder.cs b/T0/WordBuilder.cs new file mode 100644 index 000000000000..c410930eab78 --- /dev/null +++ b/T0/WordBuilder.cs @@ -0,0 +1,385 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +/* + * A WordBuilder instance organizes construction of a new interpreted word. + * + * Opcodes are accumulated with specific methods. A control-flow stack + * is maintained to resolve jumps. + * + * Each instance shall be used for only one word. + */ + +class WordBuilder { + + T0Comp TC; + string name; + int[] cfStack; + int cfPtr; + List<Opcode> code; + List<string> toResolve; + Dictionary<string, int> locals; + bool jumpToLast; + + internal SType StackEffect { + get; set; + } + + /* + * Create a new instance, with the specified word name. + */ + internal WordBuilder(T0Comp TC, string name) + { + this.TC = TC; + this.name = name; + cfStack = new int[16]; + cfPtr = -1; + code = new List<Opcode>(); + toResolve = new List<string>(); + locals = new Dictionary<string, int>(); + jumpToLast = true; + StackEffect = SType.UNKNOWN; + } + + /* + * Build the word. The control-flow stack must be empty. A 'ret' + * opcode is automatically appended if required. + */ + internal Word Build() + { + if (cfPtr != -1) { + throw new Exception("control-flow stack is not empty"); + } + if (jumpToLast || code[code.Count - 1].MayFallThrough) { + Ret(); + } + Word w = new WordInterpreted(TC, name, locals.Count, + code.ToArray(), toResolve.ToArray()); + w.StackEffect = StackEffect; + return w; + } + + void Add(Opcode op) + { + Add(op, null); + } + + void Add(Opcode op, string refName) + { + code.Add(op); + toResolve.Add(refName); + jumpToLast = false; + } + + /* + * Rotate the control-flow stack at depth 'depth'. + */ + internal void CSRoll(int depth) + { + int x = cfStack[cfPtr - depth]; + Array.Copy(cfStack, cfPtr - (depth - 1), + cfStack, cfPtr - depth, depth); + cfStack[cfPtr] = x; + } + + /* + * Make a copy of the control-flow element at depth 'depth', and + * push it on top of the control-flow stack. + */ + internal void CSPick(int depth) + { + int x = cfStack[cfPtr - depth]; + CSPush(x); + } + + void CSPush(int x) + { + int len = cfStack.Length; + if (++ cfPtr == len) { + int[] ncf = new int[len << 1]; + Array.Copy(cfStack, 0, ncf, 0, len); + cfStack = ncf; + } + cfStack[cfPtr] = x; + } + + int CSPop() + { + return cfStack[cfPtr --]; + } + + /* + * Push an origin on the control-flow stack, corresponding to the + * next opcode to add. + */ + internal void CSPushOrig() + { + CSPush(code.Count); + } + + /* + * Push a destination on the control-flow stack, corresponding to + * the next opcode to add. + */ + internal void CSPushDest() + { + CSPush(-code.Count - 1); + } + + /* + * Pop an origin from the control-flow stack. An exception is + * thrown if the value is not an origin. + */ + internal int CSPopOrig() + { + int x = CSPop(); + if (x < 0) { + throw new Exception("not an origin"); + } + return x; + } + + /* + * Pop a destination from the control-flow stack. An exception is + * thrown if the value is not a destination. + */ + internal int CSPopDest() + { + int x = CSPop(); + if (x >= 0) { + throw new Exception("not a destination"); + } + return -x - 1; + } + + /* + * Add a "push literal" opcode. + */ + internal void Literal(TValue v) + { + Add(new OpcodeConst(v)); + } + + /* + * Compile a "call" by name. This method implements the support + * for local variables: + * + * - If the target is '>' followed by a local variable name, then + * a "put local" opcode is added. + * + * - Otherwise, if the target is a local variable name, then a + * "get local" opcode is added. + * + * - Otherwise, a call to the named word is added. The target name + * will be resolved later on (typically, when the word containing + * the call opcode is first invoked, or when C code is generated). + */ + internal void Call(string target) + { + string lname; + bool write; + if (target.StartsWith(">")) { + lname = target.Substring(1); + write = true; + } else { + lname = target; + write = false; + } + int lnum; + if (locals.TryGetValue(lname, out lnum)) { + if (write) { + Add(new OpcodePutLocal(lnum)); + } else { + Add(new OpcodeGetLocal(lnum)); + } + } else { + Add(new OpcodeCall(), target); + } + } + + /* + * Add a "call" opcode to the designated word. + */ + internal void CallExt(Word wtarget) + { + Add(new OpcodeCall(wtarget), null); + } + + /* + * Add a "call" opcode to a word which is not currently resolved. + * This method ignores local variables. + */ + internal void CallExt(string target) + { + Add(new OpcodeCall(), target); + } + + /* + * Add a "get local" opcode; the provided local name must already + * be defined. + */ + internal void GetLocal(string name) + { + int lnum; + if (locals.TryGetValue(name, out lnum)) { + Add(new OpcodeGetLocal(lnum)); + } else { + throw new Exception("no such local: " + name); + } + } + + /* + * Add a "put local" opcode; the provided local name must already + * be defined. + */ + internal void PutLocal(string name) + { + int lnum; + if (locals.TryGetValue(name, out lnum)) { + Add(new OpcodePutLocal(lnum)); + } else { + throw new Exception("no such local: " + name); + } + } + + /* + * Define a new local name. + */ + internal void DefLocal(string lname) + { + if (locals.ContainsKey(lname)) { + throw new Exception(String.Format( + "local already defined: {0}", lname)); + } + locals[lname] = locals.Count; + } + + /* + * Add a "call" opcode whose target is an XT value (which may be + * resolved or as yet unresolved). + */ + internal void Call(TPointerXT xt) + { + if (xt.Target == null) { + Add(new OpcodeCall(), xt.Name); + } else { + Add(new OpcodeCall(xt.Target)); + } + } + + /* + * Add a "ret" opcode. + */ + internal void Ret() + { + Add(new OpcodeRet()); + } + + /* + * Add a forward unconditional jump. The new opcode address is + * pushed on the control-flow stack as an origin. + */ + internal void Ahead() + { + CSPushOrig(); + Add(new OpcodeJumpUncond()); + } + + /* + * Add a forward conditional jump, which will be taken at runtime + * if the top-of-stack value is 'true'. The new opcode address is + * pushed on the control-flow stack as an origin. + */ + internal void AheadIf() + { + CSPushOrig(); + Add(new OpcodeJumpIf()); + } + + /* + * Add a forward conditional jump, which will be taken at runtime + * if the top-of-stack value is 'false'. The new opcode address is + * pushed on the control-flow stack as an origin. + */ + internal void AheadIfNot() + { + CSPushOrig(); + Add(new OpcodeJumpIfNot()); + } + + /* + * Resolve a previous forward jump to the current code address. + * The top of control-flow stack is popped and must be an origin. + */ + internal void Then() + { + int x = CSPopOrig(); + code[x].ResolveJump(code.Count - x - 1); + jumpToLast = true; + } + + /* + * Push the current code address on the control-flow stack as a + * destination, to be used by an ulterior backward jump. + */ + internal void Begin() + { + CSPushDest(); + } + + /* + * Add a backward unconditional jump. The jump target is popped + * from the control-flow stack as a destination. + */ + internal void Again() + { + int x = CSPopDest(); + Add(new OpcodeJumpUncond(x - code.Count - 1)); + } + + /* + * Add a backward conditional jump, which will be taken at runtime + * if the top-of-stack value is 'true'. The jump target is popped + * from the control-flow stack as a destination. + */ + internal void AgainIf() + { + int x = CSPopDest(); + Add(new OpcodeJumpIf(x - code.Count - 1)); + } + + /* + * Add a backward conditional jump, which will be taken at runtime + * if the top-of-stack value is 'false'. The jump target is popped + * from the control-flow stack as a destination. + */ + internal void AgainIfNot() + { + int x = CSPopDest(); + Add(new OpcodeJumpIfNot(x - code.Count - 1)); + } +} diff --git a/T0/WordData.cs b/T0/WordData.cs new file mode 100644 index 000000000000..2d74bd3effe3 --- /dev/null +++ b/T0/WordData.cs @@ -0,0 +1,96 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +class WordData : Word { + + ConstData blob; + string baseBlobName; + int offset; + bool ongoingResolution; + + internal WordData(T0Comp owner, string name, + ConstData blob, int offset) + : base(owner, name) + { + this.blob = blob; + this.offset = offset; + StackEffect = new SType(0, 1); + } + + internal WordData(T0Comp owner, string name, + string baseBlobName, int offset) + : base(owner, name) + { + this.baseBlobName = baseBlobName; + this.offset = offset; + StackEffect = new SType(0, 1); + } + + internal override void Resolve() + { + if (blob != null) { + return; + } + if (ongoingResolution) { + throw new Exception(String.Format( + "circular reference in blobs ({0})", Name)); + } + ongoingResolution = true; + WordData wd = TC.Lookup(baseBlobName) as WordData; + if (wd == null) { + throw new Exception(String.Format( + "data word '{0}' based on non-data word '{1}'", + Name, baseBlobName)); + } + wd.Resolve(); + blob = wd.blob; + offset += wd.offset; + ongoingResolution = false; + } + + internal override void Run(CPU cpu) + { + Resolve(); + cpu.Push(new TValue(offset, new TPointerBlob(blob))); + } + + internal override List<ConstData> GetDataBlocks() + { + Resolve(); + List<ConstData> r = new List<ConstData>(); + r.Add(blob); + return r; + } + + internal override void GenerateCodeElements(List<CodeElement> dst) + { + Resolve(); + dst.Add(new CodeElementUInt(0)); + dst.Add(new CodeElementUIntInt(1, blob.Address + offset)); + dst.Add(new CodeElementUInt(0)); + } +} diff --git a/T0/WordInterpreted.cs b/T0/WordInterpreted.cs new file mode 100644 index 000000000000..882170b23930 --- /dev/null +++ b/T0/WordInterpreted.cs @@ -0,0 +1,283 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +/* + * The implementation for interpreted words. + */ + +class WordInterpreted : Word { + + /* + * Get the number of local variables for this word. + */ + internal int NumLocals { + get; private set; + } + + /* + * Get the sequence of opcodes for this word. + */ + internal Opcode[] Code { + get; private set; + } + + string[] toResolve; + + internal WordInterpreted(T0Comp owner, string name, + int numLocals, Opcode[] code, string[] toResolve) + : base(owner, name) + { + this.Code = code; + this.toResolve = toResolve; + NumLocals = numLocals; + } + + internal override void Resolve() + { + if (toResolve == null) { + return; + } + for (int i = 0; i < toResolve.Length; i ++) { + string tt = toResolve[i]; + if (tt == null) { + continue; + } + Code[i].ResolveTarget(TC.Lookup(tt)); + } + toResolve = null; + } + + internal override void Run(CPU cpu) + { + Resolve(); + cpu.Enter(Code, NumLocals); + } + + internal override List<Word> GetReferences() + { + Resolve(); + List<Word> r = new List<Word>(); + foreach (Opcode op in Code) { + Word w = op.GetReference(TC); + if (w != null) { + r.Add(w); + } + } + return r; + } + + internal override List<ConstData> GetDataBlocks() + { + Resolve(); + List<ConstData> r = new List<ConstData>(); + foreach (Opcode op in Code) { + ConstData cd = op.GetDataBlock(TC); + if (cd != null) { + r.Add(cd); + } + } + return r; + } + + internal override void GenerateCodeElements(List<CodeElement> dst) + { + Resolve(); + int n = Code.Length; + CodeElement[] gcode = new CodeElement[n]; + for (int i = 0; i < n; i ++) { + gcode[i] = Code[i].ToCodeElement(); + } + for (int i = 0; i < n; i ++) { + Code[i].FixUp(gcode, i); + } + dst.Add(new CodeElementUInt((uint)NumLocals)); + for (int i = 0; i < n; i ++) { + dst.Add(gcode[i]); + } + } + + int flowAnalysis; + int maxDataStack; + int maxReturnStack; + + bool MergeSA(int[] sa, int j, int c) + { + if (sa[j] == Int32.MinValue) { + sa[j] = c; + return true; + } else if (sa[j] != c) { + throw new Exception(string.Format( + "In word '{0}', offset {1}:" + + " stack action mismatch ({2} / {3})", + Name, j, sa[j], c)); + } else { + return false; + } + } + + internal override void AnalyseFlow() + { + switch (flowAnalysis) { + case 0: + break; + case 1: + return; + default: + throw new Exception("recursive call detected in '" + + Name + "'"); + } + flowAnalysis = 2; + int n = Code.Length; + int[] sa = new int[n]; + for (int i = 0; i < n; i ++) { + sa[i] = Int32.MinValue; + } + sa[0] = 0; + int[] toExplore = new int[n]; + int tX = 0, tY = 0; + int off = 0; + + int exitSA = Int32.MinValue; + int mds = 0; + int mrs = 0; + + int maxDepth = 0; + + for (;;) { + Opcode op = Code[off]; + bool mft = op.MayFallThrough; + int c = sa[off]; + int a; + if (op is OpcodeCall) { + Word w = op.GetReference(TC); + w.AnalyseFlow(); + SType se = w.StackEffect; + if (!se.IsKnown) { + throw new Exception(string.Format( + "call from '{0}' to '{1}'" + + " with unknown stack effect", + Name, w.Name)); + } + if (se.NoExit) { + mft = false; + a = 0; + } else { + a = se.DataOut - se.DataIn; + } + mds = Math.Max(mds, c + w.MaxDataStack); + mrs = Math.Max(mrs, w.MaxReturnStack); + maxDepth = Math.Min(maxDepth, c - se.DataIn); + } else if (op is OpcodeRet) { + if (exitSA == Int32.MinValue) { + exitSA = c; + } else if (exitSA != c) { + throw new Exception(string.Format( + "'{0}': exit stack action" + + " mismatch: {1} / {2}" + + " (offset {3})", + Name, exitSA, c, off)); + } + a = 0; + } else { + a = op.StackAction; + mds = Math.Max(mds, c + a); + } + c += a; + maxDepth = Math.Min(maxDepth, c); + + int j = op.JumpDisp; + if (j != 0) { + j += off + 1; + toExplore[tY ++] = j; + MergeSA(sa, j, c); + } + off ++; + if (!mft || !MergeSA(sa, off, c)) { + if (tX < tY) { + off = toExplore[tX ++]; + } else { + break; + } + } + } + + maxDataStack = mds; + maxReturnStack = 1 + NumLocals + mrs; + + /* + * TODO: see about this warning. Usage of a 'fail' + * word (that does not exit) within a 'case..endcase' + * structure will make an unreachable opcode. In a future + * version we might want to automatically remove dead + * opcodes. + for (int i = 0; i < n; i ++) { + if (sa[i] == Int32.MinValue) { + Console.WriteLine("warning: word '{0}'," + + " offset {1}: unreachable opcode", + Name, i); + continue; + } + } + */ + + SType computed; + if (exitSA == Int32.MinValue) { + computed = new SType(-maxDepth, -1); + } else { + computed = new SType(-maxDepth, -maxDepth + exitSA); + } + + if (StackEffect.IsKnown) { + if (!computed.IsSubOf(StackEffect)) { + throw new Exception(string.Format( + "word '{0}':" + + " computed stack effect {1}" + + " does not match declared {2}", + Name, computed.ToString(), + StackEffect.ToString())); + } + } else { + StackEffect = computed; + } + + flowAnalysis = 1; + } + + internal override int MaxDataStack { + get { + AnalyseFlow(); + return maxDataStack; + } + } + + internal override int MaxReturnStack { + get { + AnalyseFlow(); + return maxReturnStack; + } + } +} diff --git a/T0/WordNative.cs b/T0/WordNative.cs new file mode 100644 index 000000000000..786887253762 --- /dev/null +++ b/T0/WordNative.cs @@ -0,0 +1,59 @@ +/* + * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +using System; +using System.Collections.Generic; + +/* + * Class for native words. + */ + +class WordNative : Word { + + /* + * A type for the native implementation: a method that takes a + * CPU as parameter, and returns nothing. + */ + internal delegate void NativeRun(CPU cpu); + + NativeRun code; + + internal WordNative(T0Comp owner, string name, NativeRun code) + : base(owner, name) + { + this.code = code; + } + + internal WordNative(T0Comp owner, string name, + SType stackEffect, NativeRun code) + : this(owner, name, code) + { + StackEffect = stackEffect; + } + + internal override void Run(CPU cpu) + { + code(cpu); + } +} diff --git a/T0/kern.t0 b/T0/kern.t0 new file mode 100644 index 000000000000..9fce4f84d301 --- /dev/null +++ b/T0/kern.t0 @@ -0,0 +1,309 @@ +: \ `\n parse drop ; immediate + +\ This file defines the core non-native functions (mainly used for +\ parsing words, i.e. not part of the generated output). The line above +\ defines the syntax for comments. + +\ Define parenthesis comments. +\ : ( `) parse drop ; immediate + +: else postpone ahead 1 cs-roll postpone then ; immediate +: while postpone if 1 cs-roll ; immediate +: repeat postpone again postpone then ; immediate + +: ['] ' ; immediate +: [compile] compile ; immediate + +: 2drop drop drop ; +: dup2 over over ; + +\ Local variables are defined with the native word '(local)'. We define +\ a helper construction that mimics what is found in Apple's Open Firmware +\ implementation. The syntax is: { a b ... ; c d ... } +\ I.e. there is an opening brace, then some names. Names appearing before +\ the semicolon are locals that are both defined and then filled with the +\ values on stack (in stack order: { a b } fills 'b' with the top-of-stack, +\ and 'a' with the value immediately below). Names appearing after the +\ semicolon are not initialized. +: __deflocal ( from_stack name -- ) + dup (local) swap if + compile-local-write + else + drop + then ; +: __deflocals ( from_stack -- ) + next-word + dup "}" eqstr if + 2drop ret + then + dup ";" eqstr if + 2drop 0 __deflocals ret + then + over __deflocals + __deflocal ; +: { + -1 __deflocals ; immediate + +\ Data building words. +: data: + new-data-block next-word define-data-word ; +: hexb| + 0 0 { acc z } + begin + char + dup `| = if + z if "Truncated hexadecimal byte" puts cr exitvm then + ret + then + dup 0x20 > if + hexval + z if acc 4 << + data-add8 else >acc then + z not >z + then + again ; + +\ Convert hexadecimal character to number. Complain loudly if conversion +\ is not possible. +: hexval ( char -- x ) + hexval-nf dup 0 < if "Not an hex digit: " puts . cr exitvm then ; + +\ Convert hexadecimal character to number. If not an hexadecimal digit, +\ return -1. +: hexval-nf ( char -- x ) + dup dup `0 >= swap `9 <= and if `0 - ret then + dup dup `A >= swap `F <= and if `A - 10 + ret then + dup dup `a >= swap `f <= and if `a - 10 + ret then + drop -1 ; + +\ Convert decimal character to number. Complain loudly if conversion +\ is not possible. +: decval ( char -- x ) + decval-nf dup 0 < if "Not a decimal digit: " puts . cr exitvm then ; + +\ Convert decimal character to number. If not a decimal digit, +\ return -1. +: decval-nf ( char -- x ) + dup dup `0 >= swap `9 <= and if `0 - ret then + drop -1 ; + +\ Commonly used shorthands. +: 1+ 1 + ; +: 2+ 2 + ; +: 1- 1 - ; +: 2- 2 - ; +: 0= 0 = ; +: 0<> 0 <> ; +: 0< 0 < ; +: 0> 0 > ; + +\ Get a 16-bit value from the constant data block. This uses big-endian +\ encoding. +: data-get16 ( addr -- x ) + dup data-get8 8 << swap 1+ data-get8 + ; + +\ The case..endcase construction is the equivalent of 'switch' is C. +\ Usage: +\ case +\ E1 of C1 endof +\ E2 of C2 endof +\ ... +\ CN +\ endcase +\ +\ Upon entry, it considers the TOS (let's call it X). It will then evaluate +\ E1, which should yield a single value Y1; at that point, the X value is +\ still on the stack, just below Y1, and must remain untouched. The 'of' +\ word compares X with Y1; if they are equal, C1 is executed, and then +\ control jumps to after the 'endcase'. The X value is popped from the +\ stack immediately before evaluating C1. +\ +\ If X and Y1 are not equal, flow proceeds to E2, to obtain a value Y2 to +\ compare with X. And so on. +\ +\ If none of the 'of' clauses found a match, then CN is evaluated. When CN +\ is evaluated, the X value is on the TOS, and CN must either leave it on +\ the stack, or replace it with exactly one value; the 'endcase' word +\ expects (and drops) one value. +\ +\ Implementation: this is mostly copied from ANS Forth specification, +\ although simplified a bit because we know that our control-flow stack +\ is independent of the data stack. During compilation, the number of +\ clauses is maintained on the stack; each of..endof clause really is +\ an 'if..else' that must be terminated with a matching 'then' in 'endcase'. + +: case 0 ; immediate +: of 1+ postpone over postpone = postpone if postpone drop ; immediate +: endof postpone else ; immediate +: endcase + postpone drop + begin dup while 1- postpone then repeat drop ; immediate + +\ A simpler and more generic "case": there is no management for a value +\ on the stack, and each test is supposed to come up with its own boolean +\ value. +: choice 0 ; immediate +: uf 1+ postpone if ; immediate +: ufnot 1+ postpone ifnot ; immediate +: enduf postpone else ; immediate +: endchoice begin dup while 1- postpone then repeat drop ; immediate + +\ C implementations for native words that can be used in generated code. +add-cc: co { T0_CO(); } +add-cc: execute { T0_ENTER(ip, rp, T0_POP()); } +add-cc: drop { (void)T0_POP(); } +add-cc: dup { T0_PUSH(T0_PEEK(0)); } +add-cc: swap { T0_SWAP(); } +add-cc: over { T0_PUSH(T0_PEEK(1)); } +add-cc: rot { T0_ROT(); } +add-cc: -rot { T0_NROT(); } +add-cc: roll { T0_ROLL(T0_POP()); } +add-cc: pick { T0_PICK(T0_POP()); } +add-cc: + { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(a + b); +} +add-cc: - { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(a - b); +} +add-cc: neg { + uint32_t a = T0_POP(); + T0_PUSH(-a); +} +add-cc: * { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(a * b); +} +add-cc: / { + int32_t b = T0_POPi(); + int32_t a = T0_POPi(); + T0_PUSHi(a / b); +} +add-cc: u/ { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(a / b); +} +add-cc: % { + int32_t b = T0_POPi(); + int32_t a = T0_POPi(); + T0_PUSHi(a % b); +} +add-cc: u% { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(a % b); +} +add-cc: < { + int32_t b = T0_POPi(); + int32_t a = T0_POPi(); + T0_PUSH(-(uint32_t)(a < b)); +} +add-cc: <= { + int32_t b = T0_POPi(); + int32_t a = T0_POPi(); + T0_PUSH(-(uint32_t)(a <= b)); +} +add-cc: > { + int32_t b = T0_POPi(); + int32_t a = T0_POPi(); + T0_PUSH(-(uint32_t)(a > b)); +} +add-cc: >= { + int32_t b = T0_POPi(); + int32_t a = T0_POPi(); + T0_PUSH(-(uint32_t)(a >= b)); +} +add-cc: = { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(-(uint32_t)(a == b)); +} +add-cc: <> { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(-(uint32_t)(a != b)); +} +add-cc: u< { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(-(uint32_t)(a < b)); +} +add-cc: u<= { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(-(uint32_t)(a <= b)); +} +add-cc: u> { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(-(uint32_t)(a > b)); +} +add-cc: u>= { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(-(uint32_t)(a >= b)); +} +add-cc: and { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(a & b); +} +add-cc: or { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(a | b); +} +add-cc: xor { + uint32_t b = T0_POP(); + uint32_t a = T0_POP(); + T0_PUSH(a ^ b); +} +add-cc: not { + uint32_t a = T0_POP(); + T0_PUSH(~a); +} +add-cc: << { + int c = (int)T0_POPi(); + uint32_t x = T0_POP(); + T0_PUSH(x << c); +} +add-cc: >> { + int c = (int)T0_POPi(); + int32_t x = T0_POPi(); + T0_PUSHi(x >> c); +} +add-cc: u>> { + int c = (int)T0_POPi(); + uint32_t x = T0_POP(); + T0_PUSH(x >> c); +} +add-cc: data-get8 { + size_t addr = T0_POP(); + T0_PUSH(t0_datablock[addr]); +} + +add-cc: . { + extern int printf(const char *fmt, ...); + printf(" %ld", (long)T0_POPi()); +} +add-cc: putc { + extern int printf(const char *fmt, ...); + printf("%c", (char)T0_POPi()); +} +add-cc: puts { + extern int printf(const char *fmt, ...); + printf("%s", &t0_datablock[T0_POPi()]); +} +add-cc: cr { + extern int printf(const char *fmt, ...); + printf("\n"); +} +add-cc: eqstr { + const void *b = &t0_datablock[T0_POPi()]; + const void *a = &t0_datablock[T0_POPi()]; + T0_PUSH(-(int32_t)(strcmp(a, b) == 0)); +} |
