Show HN: WIP NandToTetris Emulator in pure C – logic gates to ALU to CPU to PC

[purple-leafy]

https://github.com/con-dog/hack_emulator_c

* OPEN TO CONTRIBUTIONS *

NandToTetris is a course which has you build a full computer from:

Logic gates -> Chips -> RAM -> CPU -> Computer -> Assembler -> Compiler -> OS -> Tetris

All this is done via software defined hardware emulation.

I'm building an emulator for this entire stack in C.

How is my approach different to other projects that build emulators?

    - No external dependencies (so far)
    - Start with a single software defined NAND gate in C
      - EVERYTHING is built from this base chip
    - Don't use certain programming utilities: boolean logic 
        operators, bitwise logic operators etc

    Instead we leverage the gates/chips to implement such logic

    I build more and more base chips from the NAND gate
    - Simple gates: OR, AND, NOT, XOR (5 total "gates")
    - Simple chips: DMux, Mux (11 so far, "combinatorial" 
        chips
    - 16 bit variants

For comparison, most emulator projects start right at the CPU level and don't sequentially build primitive structures. So a lay-person, or person unfamiliar with PC architectures is missing some lower-level information.

Typical emulators look at CPU truth table / Instruction set and implement that logic directly in code.

More straight forward, way fewer lines of code - but you skip all the gates/chips fun.

------

Confused? Heres example code for my NAND gate:

    void nand_gate(Nand *nand)
    {
        nand->output.out = !(nand->input.a & nand->input.b);
    }

From this gate I build a NOT gate (note, no boolean operators)

    void not_gate(Not * not )
    {
        Nand nand = {
            .input.a = not ->input.in,
            .input.b = not ->input.in,
        };
        nand_gate(&nand);
        not ->output.out = nand.output.out;
    }

Then OR / AND / XOR / MUX / DMUX ..... and their 16 bit versions.

Heres a more complex chip, a 16bit Mux-8-way chip

    /*
     * out = a if sel = 000
     *       b if sel = 001
     *       c if sel = 010
     *       d if sel = 011
     *       e if sel = 100
     *       f if sel = 101
     *       g if sel = 110
     *       h if sel = 111
    */
    void mux16_8_way_chip(Mux16_8_Way *mux16_8_way)
    {
      Mux16_4_Way mux16_4_way_chip_a, mux16_4_way_chip_b;
      Mux16 mux16_chip_c;

      // Mux a
      memcpy(mux16_4_way_chip_a.input.sel, mux16_8_way- >input.sel, sizeof(mux16_4_way_chip_a.input.sel));
      memcpy(mux16_4_way_chip_a.input.a, mux16_8_way->input.a, sizeof(mux16_4_way_chip_a.input.a));
      memcpy(mux16_4_way_chip_a.input.b, mux16_8_way->input.b, sizeof(mux16_4_way_chip_a.input.b));
      memcpy(mux16_4_way_chip_a.input.c, mux16_8_way->input.c, sizeof(mux16_4_way_chip_a.input.c));
      memcpy(mux16_4_way_chip_a.input.d, mux16_8_way->input.d, sizeof(mux16_4_way_chip_a.input.d));
      mux16_4_way_chip(&mux16_4_way_chip_a);

      // Mux b
      memcpy(mux16_4_way_chip_b.input.sel, mux16_8_way->input.sel, sizeof(mux16_4_way_chip_b.input.sel));
      memcpy(mux16_4_way_chip_b.input.a, mux16_8_way->input.e, sizeof(mux16_4_way_chip_b.input.a));
      memcpy(mux16_4_way_chip_b.input.b, mux16_8_way->input.f, sizeof(mux16_4_way_chip_b.input.b));
      memcpy(mux16_4_way_chip_b.input.c, mux16_8_way->input.g, sizeof(mux16_4_way_chip_b.input.c));
      memcpy(mux16_4_way_chip_b.input.d, mux16_8_way->input.h, sizeof(mux16_4_way_chip_b.input.d));
      mux16_4_way_chip(&mux16_4_way_chip_b);

      // Mux c
      mux16_chip_c.input.sel = mux16_8_way->input.sel[2];
      memcpy(mux16_chip_c.input.a, mux16_4_way_chip_a.output.out, sizeof(mux16_chip_c.input.a));
      memcpy(mux16_chip_c.input.b, mux16_4_way_chip_b.output.out, sizeof(mux16_chip_c.input.b));
      mux16_chip(&mux16_chip_c);

      memcpy(mux16_8_way->output.out, mux16_chip_c.output.out, sizeof(mux16_8_way->output.out));
    }

-----

Progress: I have only started this project yesterday, so have completed 1 out of 7 hardware projects so far

[duskwuff]

You may want to take a look at hardware definition languages like Verilog, if you haven't before. They're designed for this sort of thing.

(If you want to do your own thing that's fine too - just wanted to make sure you're aware of what's out there.)

[purple-leafy → duskwuff]

Thanks aware of Verilog, I was thinking of using either Verilog or VHDL as a second repo to build this emulator with an FPGA in either of those languages

Second project idea

[deosjr]

I did the same thing in Golang here: https://github.com/deosjr/nand2tetris

Be sure to check out the lispmachine folder; its essentially a fork I made after finishing the course. It implements a Lisp on the nand-gate level :)

[purple-leafy]

For anyone who wants to challenge themselves to better understand the computers we use every day, I highly recommend the NandToTetris course [0]

I have learnt more about computers in 2 weeks of this course, than years of software development.

Particularly if you are a web-developer, I challenge you to look deeper into PC architectures and low-level programming.

C is a great language to get started with.

After I build this project, I want to move on to a more powerful emulator (maybe a GameBoy or similar, but probably starting at the CPU level rather than the logic gate level!)

[0] - https://www.nand2tetris.org/

[sourcepluck → purple-leafy]

I'm waiting on "Code" by Petzold to arrive, which I'm hoping will scratch a similar itch, but this seems like a really great way to do it! The nand2tetris course seems so very great. Emulating it all in C sounds fun.

[purple-leafy → sourcepluck]

I've read that one in the past, very good book! That looks at electrical circuits as the starting piece.

You could definitely do the Nand2Tetris course alongside :)

[purple-leafy]

Open for contribution, its very simple code, and adding some testing logic would really help! I'm happy to guide and work with anyone on how to do this :)

A really simple way to start contributing would be to write some truth table tests for the nand_gate, then the other gates too.

EG: For the NAND gate, it would be as simple as the following (pseudocode):

    /* TRUTH TABLE
     * | a | b | out |
     * ---------------
     * | 0 | 0 |  1  |
     * | 0 | 1 |  1  |
     * | 1 | 0 |  1  |
     * | 1 | 1 |  0  |
     */
    
    // Define gate
    Nand nand_instance;
    
    // Set inputs to either 0 or 1
    nand_instance.input.a = 0;
    nand_instance.input.b = 0;

    // Process logic
    nand_gate(&nand_instance);

    // Check output is correct
    if (nand_instance.output.out == 1)
    {
      // PASSED
    }
    else
    {
      // FAILED
    }

Oh and for anyone who looks at this sort of low level project (hardware etc) and feels its outside their ability, its not!

I say this because thats how I have always felt seeing such projects.

Its actually very, very simple code to understand and start yourself, and working through the NandToTetris course, you could probably do better than my code within a few days.

You could write such an emulator in any programming language

[pipes]

I have worked through this book. Well 11 out of the 12 chapters. I learn so much from it.

As an extra exercise for the reader, it suggests connecting it to the internet somehow. I've no idea how I would do this and I really wish they'd add it as a proper chapter.

[signa11]

are there plans to add gate level propagation delay as well ? that is one thing that i find missing, and would push things closer to reality perhaps ?

fwiw, i did the nand2tetris from coursera, and it is indeed great fun.

[purple-leafy → signa11]

I can look into it, but may be out of scope for my first run. There will be a clock dependance though for sequential logic (rising edge etc)

[signa11 → purple-leafy]

yup exactly ! not even that, if somehow power-dissipation can also be done, then eventually all of it paves the way to have actual "place-and-route" thingies running :o) !

not for the faint-of-heart though.