Show HN: CPU simulator in 60 lines of code | Hacker News Reader

Show HN: CPU simulator in 60 lines of code

github.com

60 pointswkoszek33 comments

Very nice! Shows that it's possible to do something concise while still remain readability and educational value.

My mind was absolutely blown when I first realized that the function of a CPU is pretty much to read tokens from a stream and perform an action for each. - no magic!

For me the fun realization was when I cottoned on how nicely instruction microcode lines up as a concept with stored functions in a language with first class functions.

Your instruction look up becomes your execution step in one go: https://github.com/jarcane/MicroMini/blob/master/main.rkt

> My mind was absolutely blown when I first realized that the function of a CPU is pretty much to read tokens from a stream and perform an action for each. - no magic!

The magic is mostly in the pipelining bit :)

> My mind was absolutely blown when I first realized that the function of a CPU is pretty much to read tokens from a stream and perform an action for each.

My "aha!" moment when I first learned about CPUs was the program counter, or if you're an Intel guy, you'd call it the instruction pointer.

The PC might seem obvious, but if you think about it for a moment, you'll realize that someone had to have invented it. It's not totally obvious. And as far as I can tell, the inventor is unknown.

Note also that the featured program does not have a PC, so there are things it can't do that a normal CPU can do.

And if you look at computers based on drum memory, then you probably didn't have a PC, the optimal place for the next instruction then wasn't the next address, but instead how far the drum rotated during execution, at least in some of those machines the next instruction was encoded in the current instruction.

Having RAM seems to be important to having a PC, that works well.

Small security hole in this: since i0/i1/i2 are signed ints, i0 % 8 etc can be negative, and thus allow writing in the 7 bytes before r[], quite possibly leading to a stack smashing attack. So you probably don't want to run this in production :)

You're right: I didn't design it to be run with UID 0.

However I fixed the issue and gave you the credit:

https://github.com/wkoszek/cpu60/commit/672711f3e06bba424b98...

I think this is more like an ALU simulator (plus registers) than a CPU simulator. There are no jumps, either conditional or unconditional, because it's reading the instruction stream from standard input.

https://github.com/kragen/calculusvaporis/blob/master/cavosi... is a CPU simulator in 70 lines of code, but it's perhaps a bit impractical; you have to synthesize addition from subtraction, for example, and AND and OR from NAND. The design objective of Calculus Vaporis, however, is to use as few logic gates as possible, rather than to be as simple as possible in C.

http://canonical.org/~kragen/sw/aspmisc/brainfuck.c is a 66-line BF interpreter, but BF is not a very good CPU design, in that it doesn't support subroutines.

There are no cmp, branch instructions. How is this turing complete?

> There are no cmp, branch instructions. How is this turing complete?

I see no claim for it to be?

CPU by common sense should be Turing complete.

This is a partial ALU and Register File. It is not a CPU.

All you need is logical AND, logical OR, and logical NOT. I suppose they could compose them from the operations there.

Looks quite elegant :-) You should probably use else-if instead of ifs though, otherwise it is (immediately) complicated to e.g. count the number of instructions you execute.

I don't get it. How does using else-if make it less complicated to count the number of instructions?

Because it will force only to execute one of the conditional branch. https://github.com/wkoszek/cpu60/blob/master/cpu60.c might execute several. (It may be on purpose though.)

It won't execute more than one, because only one can match. The other sscanfs will all fail. I agree it would make sense to stop trying patterns once one has matched, though.

Personally, my inclination would be to rewrite the loop to tighten it up. But maybe the point was to show how quickly and dirtily one can do this... it definitely looks quick and dirty.

Quick, dirty and primitive was my primary motivation for this exercise :-)

How would you rewrite it to "tighten it up"?

I would make that series of if-statements more obviously deterministic, for starters. One way of accomplishing that would be a bunch of nested if-else blocks. However, that would be ugly. I'd prefer something like continue statements -- which would necessitate redesigning the loop to avoid bypassing the code at the bottom. Either way, the way this currently gives the appearance of being possibly nondeterministic makes me uncomfortable... and besides, executing those extra conditionals wastes CPU cycles.

With the current code, you would need a counter increment for every if statement.

And with the else-if code you would need a counter increment for every else-if statement

No, you'd just need one increment after all of them. An increment in every else-if block is redundant because only one condition can be executed per loop.

Well, use fseek to implement jumps (use fixed length lines or "assemble" the source file so that has byte offsets for branch targets).

Thats probably 10 lines of lisp ...

... and one line of perl.

He could have saved another 10 lines by dropping the braces around the if statements :P

The idea was to make it small, but not too "compressed". And I always like having braces everywhere for clarity.

I, too, prefer braces for clarity.

Great work! Add some branching and it's Turing-complete :)

Will think about it. I suspect it'll be cpu70 afterwards.

Is it possible do branching on an IO stream (without using a buffer, or what would really be some memory for CPU60)?

neat project. I like it.

Reply on news.ycombinator.com