From 9edb193559f48f78f3040d96147d0baea84abde7 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 4 Oct 2024 12:58:50 -0700 Subject: Optimize Loads bypassing trivial unrelated array stores. Fix some graphviz display on array loads & stores Fix bug in GCM, extra code for infinite loops now handled elsewhere. Move BrainFuck out into its own test. --- .../java/com/seaofnodes/simple/BrainFuckTest.java | 97 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter15Test.java | 94 ++------------------- .../com/seaofnodes/simple/evaluator/Evaluator.java | 2 +- 4 files changed, 106 insertions(+), 91 deletions(-) create mode 100644 chapter15/src/test/java/com/seaofnodes/simple/BrainFuckTest.java (limited to 'chapter15/src/test/java/com') diff --git a/chapter15/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter15/src/test/java/com/seaofnodes/simple/BrainFuckTest.java new file mode 100644 index 00000000..894abbf6 --- /dev/null +++ b/chapter15/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -0,0 +1,97 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import org.junit.Ignore; + +import java.nio.charset.StandardCharsets; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class BrainFuckTest { + + @Ignore + @Test + public void testBrainfuck() { + var program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.".getBytes(StandardCharsets.UTF_8); + var encoded = new StringBuilder("u8[] program = new u8[").append(program.length).append("];"); + for (int i = 0; i < program.length; i++) { + int value = program[i] & 0xFF; + encoded.append("program[").append(i).append("] = ").append(value).append(";"); + } + + Parser parser = new Parser( + encoded + """ +int pc = 0; +int d = 0; +u8[] data = new u8[10000]; +int i=0; +while(i < data#) { + data[i] = 0; + i = i + 1; +} + +u8[] output = new u8[0]; + +while (pc < program#) { + int command = program[pc]; + if (command == 62) { + d = d + 1; + } else if (command == 60) { + d = d - 1; + } else if (command == 43) { + data[d] = data[d] + 1; + } else if (command == 45) { + data[d] = data[d] - 1; + } else if (command == 46) { + u8[] old = output; + output = new u8[output# + 1]; + i = 0; + while (i < old#) { + output[i] = old[i]; + i = i + 1; + } + output[i] = data[d]; + } else if (command == 44) { + data[d] = 42; + } else if (command == 91) { + if (data[d] == 0) { + int d = 1; + while (d > 0) { + pc = pc + 1; + command = program[pc]; + if (command == 91) d = d + 1; + if (command == 93) d = d - 1; + } + } + } else if (command == 93) { + if (data[d] != 0) { + int d = 1; + while (d > 0) { + pc = pc - 1; + command = program[pc]; + if (command == 93) d = d + 1; + if (command == 91) d = d - 1; + } + } + } + pc = pc + 1; +} +int result = 0; +i = 0; +while (i < 8) { + result = (result << 8) | data[i]; + i = i + 1; +} +return result; + """); + StopNode stop = parser.parse(false).iterate(false); + long expected = 0; + for (byte b : "Hello Wo".getBytes(StandardCharsets.UTF_8)) { + expected = (expected << 8) | b; + } + assertEquals(expected, Evaluator.evaluate(stop, 0, 100000)); + } +} diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 9f5119f5..69e29826 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -346,7 +346,7 @@ if (arg) v.f=1; return i; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return .f;", stop.toString()); + assertEquals("return 2;", stop.toString()); assertEquals(2L, Evaluator.evaluate(stop, 0)); assertEquals(2L, Evaluator.evaluate(stop, 1)); } @@ -406,7 +406,7 @@ while (arg) v.f = 2; return i; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return .f;", stop.toString()); + assertEquals("return arg;", stop.toString()); } @Test diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 00ed6c6c..1aee2f0d 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -30,7 +30,7 @@ return 3.14; int[] is = new int[2]; return is[1]; """); - StopNode stop = parser.parse(false).iterate(true); + StopNode stop = parser.parse(false).iterate(false); assertEquals("return 0;", stop.toString()); assertEquals(0L, Evaluator.evaluate(stop, 0)); } @@ -43,7 +43,7 @@ int[] is = new int[2]; int[] is2 = new int[2]; return is[1]; """); - StopNode stop = parser.parse(false).iterate(true); + StopNode stop = parser.parse(false).iterate(false); assertEquals("return 0;", stop.toString()); assertEquals(0L, Evaluator.evaluate(stop, 0)); } @@ -57,8 +57,8 @@ a[0] = 1; a[1] = 2; return a[0]; """); - StopNode stop = parser.parse(false).iterate(true); - assertEquals("return .[];", stop.toString()); + StopNode stop = parser.parse(false).iterate(false); + assertEquals("return 1;", stop.toString()); assertEquals(1L, Evaluator.evaluate(stop, 0)); } @@ -166,7 +166,7 @@ while( i < ary# - 1 ) { } return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """); - StopNode stop = parser.parse(false).iterate(true); + StopNode stop = parser.parse(false).iterate(false); assertEquals("return (.[]+(.[]*1000));", stop.toString()); assertEquals(1006L, Evaluator.evaluate(stop, 4)); } @@ -209,7 +209,7 @@ while( j < nprimes ) { return rez; """); - StopNode stop = parser.parse(false).iterate(true); + StopNode stop = parser.parse(false).iterate(false); assertEquals("return int[];", stop.toString()); Evaluator.Obj obj = (Evaluator.Obj)Evaluator.evaluate(stop, 20); assertEquals("int[] {\n # :int;\n [] :int;\n}",obj.struct().toString()); @@ -267,86 +267,4 @@ return is[1]; catch( NegativeArraySizeException e ) { assertEquals("-1",e.getMessage()); } } - @Test - public void testBrainfuck() { - var program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.".getBytes(StandardCharsets.UTF_8); - var encoded = new StringBuilder("u8[] program = new u8[").append(program.length).append("];"); - for (int i = 0; i < program.length; i++) { - int value = program[i] & 0xFF; - encoded.append("program[").append(i).append("] = ").append(value).append(";"); - } - - Parser parser = new Parser( - encoded + """ -int pc = 0; -int d = 0; -u8[] data = new u8[30000]; -int i=0; -while(i < data#) { - data[i] = 0; - i = i + 1; -} - -u8[] output = new u8[0]; - -while (pc < program#) { - int command = program[pc]; - if (command == 62) { - d = d + 1; - } else if (command == 60) { - d = d - 1; - } else if (command == 43) { - data[d] = data[d] + 1; - } else if (command == 45) { - data[d] = data[d] - 1; - } else if (command == 46) { - u8[] old = output; - output = new u8[output# + 1]; - i = 0; - while (i < old#) { - output[i] = old[i]; - i = i + 1; - } - output[i] = data[d]; - } else if (command == 44) { - data[d] = 42; - } else if (command == 91) { - if (data[d] == 0) { - int d = 1; - while (d > 0) { - pc = pc + 1; - command = program[pc]; - if (command == 91) d = d + 1; - if (command == 93) d = d - 1; - } - } - } else if (command == 93) { - if (data[d] != 0) { - int d = 1; - while (d > 0) { - pc = pc - 1; - command = program[pc]; - if (command == 93) d = d + 1; - if (command == 91) d = d - 1; - } - } - } - pc = pc + 1; -} -int result = 0; -i = 0; -while (i < 8) { - result = (result << 8) | data[i]; - i = i + 1; -} -return result; - """); - StopNode stop = parser.parse(false).iterate(false); - long expected = 0; - for (byte b : "Hello Wo".getBytes(StandardCharsets.UTF_8)) { - expected = (expected << 8) | b; - } - assertEquals(expected, Evaluator.evaluate(stop, 1000000)); - } - } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index e59017e7..26860858 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -115,7 +115,7 @@ public class Evaluator { int scale = from.struct.aryScale(); long i = ((Long)off - base)>>scale; if( i < 0 || i >= len ) - throw new ArrayIndexOutOfBoundsException("Array index out of bounds " + off + " <= " + len); + throw new ArrayIndexOutOfBoundsException("Array index out of bounds " + i + " < " + len); return from.fields[(int)i+1]; } else -- cgit v1.2.3