Show HN: Compile C to Not Gates

82 points - yesterday at 7:36 PM


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/

Source
  • bangaladore

    yesterday at 8:14 PM

    Reminds me of movfuscator [1]. This can compile programs to movs and only movs.

    [1] https://github.com/Battelle/movfuscator

      • LPisGood

        yesterday at 9:57 PM

        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.

        [1] https://github.com/Battelle/cantordust

          • mmastrac

            yesterday at 11:12 PM

            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

                yesterday at 11:14 PM

                Really? You were doing offensive security work not for a government (/contractor)? What sorts companies, aside from some enterprise pen testers, employ these roles?

                  • mmastrac

                    yesterday at 11:20 PM

                    Email is in my profile -- happy to clarify/share some very rough details if you'd like.

        • beng-nl

          yesterday at 11:51 PM

          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.

    • tromp

      yesterday at 8:51 PM

      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

          yesterday at 9:08 PM

          You are indeed right

            • tromp

              yesterday at 9:18 PM

              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?!

    • tonetegeatinst

      yesterday at 11:57 PM

      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.

      • tomhee

        yesterday at 8:12 PM

        There is also a brainfuck to flipjump compiler: https://github.com/tomhea/bf2fj

          • david-gpu

            yesterday at 10:03 PM

            Ah, the convenience of brainfuck with the performance of flipjump. Excellent.

        • jkrshnmenon

          yesterday at 10:08 PM

          I wonder if someone has already made a Reverse Engineering CTF challenge for this concept.

            • og2023

              yesterday at 11:54 PM

              I read it as reverse engineering WTF challenge... cool stuff though, seriously.

              • tomhee

                yesterday at 10:18 PM

                There actually was one with subleq: https://www.google.com/amp/s/blog.attify.com/flare-4-ctf-wri...

                  • jkrshnmenon

                    yesterday at 11:16 PM

                    I would also be very curious to see if it's possible to make a decompiler for this type of obfuscated program.

            • pizza

              yesterday at 10:23 PM

              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

                  yesterday at 10:27 PM

                  If you have an answer I'd be happy to hear it!

              • dlcarrier

                yesterday at 9:22 PM

                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.

                • tomhee

                  yesterday at 9:17 PM

                  By the way, as a challenge, try how you can program an "If" statement in Flipjump.

                  • yesterday at 9:31 PM

                    • platz

                      yesterday at 8:48 PM

                      How is a jump realized by Not Gates?

                        • tomhee

                          yesterday at 9:15 PM

                          I 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.

                          • Jerrrry

                            yesterday at 9:14 PM

                            I'm guessing by not jumping into a terminating/ halting NOOP.

                            The logic is within the branching.

                        • jumploops

                          yesterday at 10:01 PM

                          AND, OR, NOT - pick 2

                            • sroussey

                              yesterday at 10:22 PM

                              NOR - pick 1

                          • artemonster

                            yesterday at 9:32 PM

                            Id appreciate more explanations from the power of combined bitflip & goto

                          • dang

                            yesterday at 7:57 PM

                            Looks like we banned you and this domain because of the egregious vote manipulation and bogus comments at 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

                                yesterday at 8:10 PM

                                Thanks man, I appreciate it.

                                • jimbob45

                                  yesterday at 8:09 PM

                                  Dang, 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.

                                    • dang

                                      yesterday at 8:24 PM

                                      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 instead of 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 (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 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

                                          yesterday at 10:01 PM

                                          You sir, are amazing. Thank you for being so utterly transparent.

                                      • chicken_grease

                                        yesterday at 8:15 PM

                                        [dead]

                                • jpcookie

                                  yesterday at 10:50 PM

                                  [dead]