Show HN: Compile C to Not Gates
67 comments
·January 17, 2025bangaladore
Reminds me of movfuscator [1]. This can compile programs to movs and only movs.
LPisGood
Battelle is great. They also created some software called Cantor Dust [1] that turns files into images to allow humans to easily spot obfuscated data or files.
The sad thing about this kind of work, because I love it, is that to get paid to do it you need clearances and polygraphs and periodic reinvestigations/continuous monitoring and all sorts of things that I find unpleasant.
mmastrac
I'm not sure what you mean but I was a security researcher for a large company for a bit and required none of that. I was required to work airgapped at home, however.
LPisGood
Really? You were doing offensive security work not for a government (/contractor)? What sorts companies, aside from some enterprise pen testers, employ these roles?
beng-nl
Agreed that is a fine piece of work. But the author is Chris Domas. Which is plain from the repo readme, but it’d be clearer to link to his repo.
bangaladore
I was originally going to link their repo [1]. But I saw it was forked from the one I linked so I just gave that one instead.
saagarjha
Chris used to (maybe still does?) work at Batelle.
tromp
Am I right in deducing that this language gets its power from self-modifying code? I.e. flipping bits within addresses of the opcodes of the running program?
tomhee
You are indeed right
tromp
I would have expected the language documentation to focus more on this observation and to explain for instance how self modification is used to implement while loops. But I don't even see the term mentioned anywhere?!
tomhee
Good point! It's mentioned in the github wiki here: https://github.com/tomhea/flip-jump/wiki/Learn-FlipJump#memo...
It was once in the Readme but as I kept developing it more it become longer and longer, so I moved it into the wiki, and especially to here: https://esolangs.org/wiki/FlipJump
int_19h
This was actually a not uncommon approach to implementing loops in earliest mainfraims.
tomhee
There is also a brainfuck to flipjump compiler: https://github.com/tomhea/bf2fj
david-gpu
Ah, the convenience of brainfuck with the performance of flipjump. Excellent.
tomhee
By the way, as a challenge, try how you can program an "If" statement in Flipjump.
greenbit
I wondered this as well.
Thinking about it, if all you have is "invert some (N>1?) bits somewhere and jump to somewhere" .. I could see maybe it might work if you use self modifying code and there's really a 2nd instruction that is a no-op? Seems like it might work more like a cellular automata?
Of course, one could just go look at the documentation, but where's the fun in that?
int_19h
You don't need a no-op; you can always just flip a bit you don't care about (e.g. reserve a word just for that) and then jump to next instruction.
alok-g
Would like to know the answer. Thx.
tomhee
alok-g
To the best I now understand, the jump address is allowed to be an expression using a specified bit variable. That would mean that the language has means to compile an expression for evaluation at the run time. If I am understanding correctly, then the power of flip jump is coming from those expressions, not the base flipjump instruction itself.
If I haven't understood this right, then I still do not follow how if statement works with flipjump.
pizza
Ah interesting.. wonder if you can model this with a recursively expanded algebraic expression. I've been thinking lately along similar lines about polynomials that encode pushdown automata, so this is cool to see.
tomhee
If you have an answer I'd be happy to hear it!
Firehawke
Wouldn't it be better to call it "compile C to Linux or BSD"?
I kid, I kid.
dingdingdang
It always amazes me that this is possible (to some extend anyway, I mean, the base layer is binary so obviously simpler higher-end CPU instructions are possible!)
Is there any potential performance win in this? What I mean is; since this general direction could, in principle if not in practise, enable the targeting of say, the 5-10 most efficient CPU instructions rather than attempting to use the whole surface area... would this potentially be a win?
eimrine
I was expecting to see a way to translate hello_world.c into an electronic schematic full of NAND elements, kind of Mealy machine.
tonetegeatinst
Looking forward to the poor security researcher who gets to reverse engineer some malware sample they compiles this into for obfuscation... Its going to be an interesting blog post.
jkrshnmenon
I wonder if someone has already made a Reverse Engineering CTF challenge for this concept.
tomhee
There actually was one with subleq: https://www.google.com/amp/s/blog.attify.com/flare-4-ctf-wri...
jkrshnmenon
I would also be very curious to see if it's possible to make a decompiler for this type of obfuscated program.
saagarjha
Typically these obfuscators are applied in an automated fashion so yes.
og2023
I read it as reverse engineering WTF challenge... cool stuff though, seriously.
dlcarrier
Maxim (now owned by Analog) actually manufactures a single-instruction processor series, called MAXQ. It uses a single move instruction, with a flag for literals, and a transport triggered architecture.
Zamiel_Snawley
What is the intended use case for such a processor?
dlcarrier
They are embedded microcontrollers, which run real-time deterministic tasks, with tens to hundreds of MIPS on fixed-point tasks. These are the kinds of microcontrollers used in products like household appliances or control systems.
jvanderbot
Is the family of circuits using just NOT gates actually universal? Or is "flip" and "jump" secretly using a lot of other gates.
tomhee
The power is within the self modification of the code. The jump might be implemented by a multiplexer, though it can be implemented in other ways too.
jvanderbot
A CNOT is universal (transistor effectively) I don't think a NOT is universal.
I'm sure you can self modify your code so it executes only using XOR (bit flips), which is a CNOT, but I do not think this could be compiled down to an FPGA using only a billion not gates.
Actually I just convinced myself you can make an AND from three NOT gates if you can tie outputs together to get OR, so I believe you now. Sorry for the diversion! (Though I still dont see how bit flips and jumps directly can be built into a circuit, I know AND and NOT are universal so it's all good).
Hi! I've been working on the flipjump project, a programming language with 1 opcode: flip (invert) a bit, then jump (unconditionally). So a bit-flip followed by more bit-flips. It's effectively a bunch of NOT gates. This language, as poor as it sounds, is RICH.
Today I completed my compiler from C to FlipJump. It takes C files, and compiles them into flipjump. I finished testing it all today, and it works! My key interest in this project is to stretch what we know of computing and to prove that anything can be done even with minimal power.
I appreciate you reading my announcement, and be happy to answer questions.
More links:
- The flipjump language: https://github.com/tomhea/flip-jump https://esolangs.org/wiki/FlipJump
- c2fj python package https://pypi.org/project/c2fj/