5 ms·
Show HN: Compile C to Not Gates
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://github.com/tomhea/flip-jump https://esolangs.org/wiki/FlipJump https://esolangs.org/wiki/FlipJump
- c2fj python package https://pypi.org/project/c2fj/ https://pypi.org/project/c2fj/
- artemonster 2y agoId appreciate more explanations from the power of combined bitflip & goto
- tomhee 2y agoSure! https://github.com/tomhea/flip-jump/wiki/Learn-FlipJump https://github.com/tomhea/flip-jump/wiki/Learn-FlipJump This will let you understand how to implement the very basic "if" in flipjump. I tried to make it as easy for newcomers, but please feel free and update me if something is written complicated. After you understand up to the macros, you can try yourself to understand the xor macro, which most of the library is built based on it: https://github.com/tomhea/flip-jump/blob/fe51448932e78db7d769e094dad742d0994b7b8b/flipjump/stl/bit/logics.fj#L23 https://github.com/tomhea/flip-jump/blob/fe51448932e78db7d76...
- dang 2y agoLooks like we banned you and this domain because of the egregious vote manipulation and bogus comments at https://news.ycombinator.com/item?id=34856792 https://news.ycombinator.com/item?id=34856792. That was a long time ago, though, and the project is interesting enough, so I'm going to assume you've learned your lesson and unban you. Please stop using multiple accounts for this though!
- tomhee 2y agoThanks man, I appreciate it.
- jimbob45 2y agoDang, I have to know what triggered you to say this. It’s not the same user account so you would have had to have recognized the URL and written based on that. Do you keep notes on each astroturfed submission and auto-trigger reposts to notify yourself? Or did you just happen to recognize this? 20 minutes from his post to your comment is absurdly good moderation.
- chicken_grease 2y ago[dead]
- dang 2y agohttps://news.ycombinator.com/item?id=42742462 https://news.ycombinator.com/item?id=42742462 was on the front page. We got an email suggesting that the URL should be https://github.com/tomhea/c2fj https://github.com/tomhea/c2fj instead of https://github.com/tomhea/flip-jump https://github.com/tomhea/flip-jump. That made sense, except it turned out that github.com/tomhea was banned. That seemed odd because we don't normally ban github domains, so I looked at the history https://news.ycombinator.com/from?site=github.com%2Ftomhea https://news.ycombinator.com/from?site=github.com%2Ftomhea (most of which will only be visible to users who have 'showdead' set to 'yes' in their profile), and it was pretty easy to see that https://news.ycombinator.com/item?id=34856792 https://news.ycombinator.com/item?id=34856792 was, let's call it, the original sin in this chain of woe. It was also pretty obvious that the other submitting accounts were all related. Since the project itself is interesting I figured the best thing to do was give the submitter a second chance, so I picked the earlier post from today (the OP) and swapped it out for the other one (42742462). I hope that answers your question!
- doormatt 2y agoYou sir, are amazing. Thank you for being so utterly transparent.
- tomhee 2y agoThere is also a brainfuck to flipjump compiler: https://github.com/tomhea/bf2fj https://github.com/tomhea/bf2fj
- david-gpu 2y agoAh, the convenience of brainfuck with the performance of flipjump. Excellent.
- bangaladore 2y agoReminds me of movfuscator [1]. This can compile programs to movs and only movs. [1] https://github.com/Battelle/movfuscator https://github.com/Battelle/movfuscator
- LPisGood 2y agoBattelle 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. [1] https://github.com/Battelle/cantordust https://github.com/Battelle/cantordust
- mmastrac 2y agoI'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 2y agoReally? You were doing offensive security work not for a government (/contractor)? What sorts companies, aside from some enterprise pen testers, employ these roles?
- 2y ago
- platz 2y agoHow is a jump realized by Not Gates?
- Jerrrry 2y agoI'm guessing by not jumping into a terminating/ halting NOOP. The logic is within the branching.
- tomhee 2y agoI dont think that the jump can be realized by NOT gates, but it's essentially "where to find the next NOT command". The jump is indeed a crucial part of the language, as it allows going back, and especially to make self-modifying code.
- tromp 2y agoAm 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 2y agoYou are indeed right
- tromp 2y agoI 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 2y agoGood point! It's mentioned in the github wiki here: https://github.com/tomhea/flip-jump/wiki/Learn-FlipJump#memory---how-can-we-implement-variable 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 https://esolangs.org/wiki/FlipJump
- int_19h 2y agoThis was actually a not uncommon approach to implementing loops in earliest mainfraims.
- tomhee 2y agoDo you have any article that I can read about it? Sounds interesting!
- dlcarrier 2y agoMaxim (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 2y agoWhat is the intended use case for such a processor?
- dlcarrier 2y agoThey 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.
- tomhee 2y agoBy the way, as a challenge, try how you can program an "If" statement in Flipjump.
- greenbit 2y agoI 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 2y agoYou 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 2y agoWould like to know the answer. Thx.
- tomhee 2y agoAlright - https://github.com/tomhea/flip-jump/wiki/Learn-FlipJump#memory---how-can-we-implement-variable https://github.com/tomhea/flip-jump/wiki/Learn-FlipJump#memo...
- alok-g 2y agoTo 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.
- deleted 2y ago[deleted]
- jumploops 2y agoAND, OR, NOT - pick 2
- jkrshnmenon 2y agoI wonder if someone has already made a Reverse Engineering CTF challenge for this concept.
- tomhee 2y agoThere actually was one with subleq: https://www.google.com/amp/s/blog.attify.com/flare-4-ctf-write-part-5/amp/ https://www.google.com/amp/s/blog.attify.com/flare-4-ctf-wri...
- jkrshnmenon 2y agoI would also be very curious to see if it's possible to make a decompiler for this type of obfuscated program.
- saagarjha 2y agoTypically these obfuscators are applied in an automated fashion so yes.
- jkrshnmenon 2y agoDEFCON Quals challenge incoming.
- saagarjha 2y agoPlease no we’ve already suffered enough :(
- og2023 2y agoI read it as reverse engineering WTF challenge... cool stuff though, seriously.
- pizza 2y agoAh 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 2y agoIf you have an answer I'd be happy to hear it!
- jpcookie 2y ago[dead]
- tonetegeatinst 2y agoLooking 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.
- kuringganteng 2y ago[flagged]
- eimrine 2y agoI was expecting to see a way to translate hello_world.c into an electronic schematic full of NAND elements, kind of Mealy machine.
- dingdingdang 2y agoIt 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?
- Imustaskforhelp 2y agohey this could actually be pretty nice if we can convert flipjump into sqlite native instructions like how it is possible for brainfuck , then you are on to something huge! You would create although highly inefficient , after many years , maybe the first , language like those lisps where you could store data in sqlite and run it fromt there (but with C)
- tomhee 2y agoThat's cool! And that's possible. Do you have any more data to read about it?
- Imustaskforhelp 2y agosee this / my comments on here https://news.ycombinator.com/item?id=42637304 https://news.ycombinator.com/item?id=42637304
- Imustaskforhelp 2y agoI really hope that you try this , this might be game changing !
- jvanderbot 2y agoIs the family of circuits using just NOT gates actually universal? Or is "flip" and "jump" secretly using a lot of other gates.
- tomhee 2y agoThe 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 2y agoA 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).
- Nevermnd 2y agoDid I miss something? I thought NAND was you're 'universal gate' ?
- Firehawke 2y agoWouldn't it be better to call it "compile C to Linux or BSD"? I kid, I kid.