I decided to write my own language of hardware synthesis, for Minecraft and what came of it

I always wondered how people do complex engineering designs in games, and I always wanted to try to repeat. A long time ago I saw a video on YouTube about how one person built a processor on a redstone. And I decided to try: why am I worse? Then I assembled several prototypes of individual elements and realized that I could not do this task. By this time, I learned a little Verilog. The thought was born: why did nobody try to use hardware synthesis languages ​​to build complex logic circuits in minecraft? Slightly delving into various forums, I did not find any similar utility, and I really wanted my processor on the redstone. I had to start writing the compiler myself. What came out of it, read under the cut.

The project turned out to be very large in terms of this, it had to be divided into separate stages:

Stage 1: To study how large products of microelectronics synthesis and software for development on plis work.
Step 2: Conduct reverse engineering of the netlist storage format in popular products for working with FPGAs.
Stage 3: Make your implementation of FPGA elements (LUT cells, triggers)
Stage 4: Make your netlist tracer for minecraft.
Stage 5: Suddenly I had to write a simulator of redstone to simplify the debugging process, without it the process of further development stalled me greatly.
Step 6: Develop a simplified syntax for a hardware synthesis language.
Stage 7: Write a compiler.
')
So let's get started. For starters, I tried several Verilog synthesizing compilers, the most successful choice was Qartus II, since it supports several synthesis languages, such as Verilog VHDL. There is a good graphical environment for visual modeling, it is possible to visualize netlists, it is possible to unload intermediate netlists in a digestible form.

My first utility was a program for converting files in VQM format into simplified MNET format. VQM is a descriptor of cells, triggers, their parameters, connection scheme. In turn, MNET is a simple list of network nodes and connections between them. After I had to look for a way to further decompose to the level of the gates, since the implementation of even one universal 16-bit LUT cell was too cumbersome. This method was quickly found in the face of the logical optimizer espresso. And in just a few days, I counted a library of all possible implementations of 65,536 logical cells.

Then I began to draw separate gates in Minecraft, for which I made a simple text binhl storage format, which stores all the inputs and outputs of the node and the layer-by-layer implementation of the redson scheme. Also found a way to download redstone schemes in Minecraft via worldedit via javaScript. Having written the code-generator for converting the circuits, I started writing one of the most difficult parts of the project — the tracer.

The tracer has two tasks: placement of elements and placement of connections. Placing the elements is somewhat more complicated than it seems at first glance, since the length of the joints and intersections of the honey depends on their position and, consequently, the number of layers in the scheme. I tried a lot of options and stopped at the following algorithm: place the input / output ports, then place the element that has the most connections to the already placed elements, go to the next element until we place everything. Then the space is divided into layers of 3 blocks, in which we place the connections between the gates. Connections are placed using a modified A-Star algorithm, where after placing each connection, the mask is updated. Also, due to the peculiarities of redstone in minecraft, the maximum length of a connection should not exceed 16 blocks, which causes additional difficulties in the rules for placing connections.

And then a surprise happened: it turned out that it was extremely difficult to debug a similar system. I had to start writing a simulator of redstone to make a set of automatic tests of all elements of the system. I built the emulator on the basis of a cellular automaton, where a matrix of all elements is built, in which each element looks at its neighbors and changes its state depending on the rules. After writing the emulator, the debugging and development process went faster.



After I managed to steadily collect Redstone schemes from VQM, I started writing the actual synthesis language, I took Verilog as a basis and simplified it a little for ease of use in minecraft. To write a compiler, I took a well-known lexer and compiler for COCO / R compilers. Made a description of the syntax in the extended Backus-Naur form, compiled the first version of the compiler.

As a result, I realized that it is possible to develop a fairly complex project alone, but this requires tremendous patience and a desire to learn new things. Now I'm working on compiler, optimization, and documentation on how to use it all.

Here is a small video:



GitHub link