diff options
Diffstat (limited to 'synth.zig')
| -rw-r--r-- | synth.zig | 172 |
1 files changed, 148 insertions, 24 deletions
diff --git a/synth.zig b/synth.zig index 3e04407..e82f85b 100644 --- a/synth.zig +++ b/synth.zig @@ -16,6 +16,7 @@ // You should have received a copy of the GNU Affero General Public License // along with taosc. If not, see <https://www.gnu.org/licenses/>. +const Allocator = std.mem.Allocator; const ArenaAllocator = std.heap.ArenaAllocator; const CompareOperator = std.math.CompareOperator; const Writer = std.io.Writer; @@ -23,37 +24,107 @@ const argsAlloc = std.process.argsAlloc; const argsFree = std.process.argsFree; const assert = std.debug.assert; const compare = std.math.compare; -const enums = std.enums; +const divTrunc = std.math.divTrunc; const exit = std.process.exit; const page_allocator = std.heap.page_allocator; const parseUnsigned = std.fmt.parseUnsigned; const print = std.debug.print; +const rem = std.math.rem; +const shl = std.math.shl; +const shr = std.math.shr; const std = @import("std"); const stdout = std.fs.File.stdout; +const tags = std.meta.tags; +const Register = Variables.Register; const RegisterEnum = Variables.RegisterEnum; const Variables = @import("Variables.zig"); const signed_integers = Variables.signed_integers; -const Variable = RegisterEnum; -const Expression = Variable; +comptime { + _ = Variables; // for test discovery +} + +const UnaryOperator = enum { + @"+", + @"-", + @"~", + + fn apply(op: UnaryOperator, val: Register) Register { + return switch (op) { + .@"+" => val, + .@"-" => -%val, + .@"~" => ~val, + }; + } +}; + +const Unary = struct { + op: UnaryOperator, + val: Variables.Query, + + pub fn format(un: Unary, writer: *Writer) Writer.Error!void { + try writer.print("{s}{f}", .{ @tagName(un.op), un.val }); + } +}; + +const ArithmeticOperator = enum { + @"+", @"-", @"*", @"/", @"%", + @"&", @"|", @"^", @"<<", @">>", + + fn apply(op: ArithmeticOperator, lhs: Register, rhs: Register) !Register { + return switch (op) { + .@"+" => lhs +% rhs, + .@"-" => lhs -% rhs, + .@"*" => lhs *% rhs, + .@"/" => try divTrunc(Register, lhs, rhs), + .@"%" => try rem(Register, lhs, rhs), + .@"&" => lhs & rhs, + .@"|" => lhs | rhs, + .@"^" => lhs ^ rhs, + .@"<<" => shl(Register, lhs, rhs), + .@">>" => shr(Register, lhs, rhs), + }; + } +}; + +const Arithmetic = struct { + lhs: Unary, + op: ArithmeticOperator, + rhs: Unary, + + pub fn format(arith: Arithmetic, writer: *Writer) Writer.Error!void { + try writer.print("{f} {s} {f}", .{ + arith.lhs, + @tagName(arith.op), + arith.rhs, + }); + } +}; + const Comparison = struct { - lhs: Expression, + lhs: Unary, op: CompareOperator, - rhs: Expression, + rhs: Arithmetic, - fn check(cmp: Comparison, bot: Variables, top: Variables) !bool { - for (try bot.register(cmp.lhs), try bot.register(cmp.rhs)) |lhs, rhs| - if (compare(lhs, cmp.op, rhs)) + fn check(cmp: Comparison, vars: Variables, expected: bool, + tmp: Temporaries) !bool { + for (try vars.get(cmp.lhs.val, tmp[0]), + try vars.get(cmp.rhs.lhs.val, tmp[1]), + try vars.get(cmp.rhs.rhs.val, tmp[2])) |v0, v1, v2| { + const arith = cmp.rhs.op.apply(cmp.rhs.lhs.op.apply(v1), + cmp.rhs.lhs.op.apply(v2)) catch return false; - for (try top.register(cmp.lhs), try top.register(cmp.rhs)) |lhs, rhs| - if (!compare(lhs, cmp.op, rhs)) + const actual = compare(cmp.lhs.op.apply(v0), cmp.op, arith); + if (if (expected) !actual else actual) return false; + } return true; } pub fn format(cmp: Comparison, writer: *Writer) Writer.Error!void { - try writer.print("{s} {f} {f}", .{ + try writer.print("{f} {s} {f}", .{ + cmp.lhs, switch (cmp.op) { .lt => "<", .lte => "<=", @@ -62,12 +133,74 @@ const Comparison = struct { .gt => ">", .neq => "!=", }, - cmp.lhs, cmp.rhs, }); } }; +const Temporaries = [3][]Register; + +fn process(writer: *Writer, bot: Variables, top: Variables, + v0: Variables.Query, v1: Variables.Query, v2: Variables.Query, + o0: UnaryOperator, o1: UnaryOperator, o2: UnaryOperator, + arith: ArithmeticOperator, cmp: CompareOperator, + bot_tmp: Temporaries, top_tmp: Temporaries) !void { + const predicate = Comparison{ + .lhs = .{ .op = o0, .val = v0 }, + .op = cmp, + .rhs = .{ + .lhs = .{ .op = o1, .val = v1 }, + .op = arith, + .rhs = .{ .op = o2, .val = v2 }, + }, + }; + if (try predicate.check(bot, false, bot_tmp)) + return; + if (try predicate.check(top, true, top_tmp)) + return; + try writer.print("{f}\n", .{ predicate }); +} + +fn mineOperator(writer: *Writer, bot: Variables, top: Variables, + v0: Variables.Query, v1: Variables.Query, v2: Variables.Query, + bot_tmp: Temporaries, top_tmp: Temporaries) !void { + for (tags(UnaryOperator)) |o0| + for (tags(UnaryOperator)) |o1| + for (tags(UnaryOperator)) |o2| + for (tags(ArithmeticOperator)) |arith| + for (tags(CompareOperator)) |cmp| + try process(writer, bot, top, v0, v1, v2, o0, o1, o2, + arith, cmp, bot_tmp, top_tmp); +} + +fn alloc_tmp(allocator: Allocator, len: usize) Allocator.Error!Temporaries { + var tmp = [_][]Register{ &.{} } ** 3; + errdefer free_tmp(allocator, tmp); + for (&tmp) |*variable| + variable.* = try allocator.alloc(Register, len); + return tmp; +} + +fn free_tmp(allocator: Allocator, tmp: Temporaries) void { + for (tmp) |variable| + allocator.free(variable); +} + +fn mine(allocator: Allocator, writer: *Writer, + bot: Variables, top: Variables) !void { + const bot_tmp = try alloc_tmp(allocator, bot.samples); + defer free_tmp(allocator, bot_tmp); + const top_tmp = try alloc_tmp(allocator, top.samples); + defer free_tmp(allocator, top_tmp); + + const variables = try Variables.Query.all(allocator); + defer allocator.free(variables); + for (variables) |v0| for (variables) |v1| for (variables) |v2| + if (!v0.skip(v1, v2)) + try mineOperator(writer, bot, top, v0, v1, v2, bot_tmp, top_tmp); + try writer.flush(); +} + pub fn main() !void { var buffer: [80]u8 = undefined; var writer = stdout().writer(&buffer); @@ -84,20 +217,11 @@ pub fn main() !void { exit(1); } const stack_size = try parseUnsigned(usize, args[1], 0); - inline for (signed_integers) |Int| - assert(stack_size % @sizeOf(Int) == 0); + inline for (signed_integers) |SignedInt| + assert(stack_size % @sizeOf(SignedInt) == 0); const bot = try Variables.init(allocator, stack_size, args[2]); defer bot.deinit(allocator); const top = try Variables.init(allocator, stack_size, args[3]); defer top.deinit(allocator); - - for (enums.values(RegisterEnum)) |lhs| - for (enums.values(RegisterEnum)) |rhs| - if (@intFromEnum(lhs) < @intFromEnum(rhs)) - for (enums.values(CompareOperator)) |op| { - const cmp = Comparison{ .lhs = lhs, .op = op, .rhs = rhs }; - if (try cmp.check(bot, top)) - try writer.interface.print("{f}\n", .{ cmp }); - }; - try writer.interface.flush(); + try mine(allocator, &writer.interface, bot, top); } |