Awesome

ohno - Interpreter for "ohno"

"ohno" is an esoteric "programming language" designed to be cryptographically difficult.

"ohno" does not stand for "overly hard, nonsensical language"

What.

"ohno" is a highly advanced language. For example, it uses the very modern hashing algorithm Keccak to compile the input into ohno bytecode. Thus, portability is guaranteed, as Keccak has been implemented on lots of platforms so far. This way, even large programs can be compiled very quickly.

The generated bytecode is then interpreted essentially as Brainfuck instructions, yet another example of the progressive, highly advanced nature of ohno.

Since it uses a secure hashing algorithm to generate the byteode, disassembly of complex programs is as hard as preimage attacks on SHA3.

The overly difficult nature of ohno makes sure that only the best programmers with the most advanced hardware can hope to find an ohno program that does something somewhat useful.

Feel free to use the program search with grep to search for good ohno programs. The cat example was found using these tools.

Seriously. What?!

Of course all of this isn't to be taken too seriously. Obviously ohno isn't truly compiled, as it uses an interpreter. But it could be. Shoot me a PR that compiles ohno into actual assembly, probably using LLVM? :D

Ohno is intended to rival Malbolge in difficulty, as now the "hashing" isn't some home-made algorithm that may or may not have nice properties, but instead uses industry-grade hashing.

Spec for .ohno files

A valid .ohno-file needs to:

• Contain at least 4 bytes
• Start with 4 bytes, big endian, which is the amount of bytes of the bytecode.
• The rest is used to seed the hashing function.

Thus, nearly all files are ohno programs; albeit they probably don't do anything useful. Especially not if the first byte is not 0x00.

ohno bytecode

The ohno bytecode is nibble-based, and technically not even that: only the last three bits of each nibble are considered, and mapped to the Brainfuck instructions (in order) +-{}><,., while ignoring the highest bit. Note that {} is similar to Brainfuck's [] but not identical.

As Brainfuck is underspecified, here's the filled-in details:

• The tape is infinite in both directions and initialized to 0. Well, as infinite as something can be on a finite machine.
• The tape can hold values from 0 to 255, inclusively, and will wrap. (Unless you have an optimizing compiler that actually exploits the UB on integer overflow. In that case, it doesn't wrap, but UB's.)
• Where [xxx] in Brainfuck is equivalent to while (*tape_ptr) { xxx } in C, ohno's {xxx} behaves like do { xxx } while (*tape_ptr); in C. Note that this probably is still Turing-complete.
• Technically, the } only behaves as specified above if there is an appropriate { to which it can jump. Otherwise, the program hangs and never terminates.
• You can stack at least 4 billion (2^32 - 1) brackets.
• Stack depth at the end of the program is ignored. Notice that this means that you don't really need to care about balanced brackets, as it will either hang or terminate successfully, but never crash! (Unless you're a weirdo and want to do something useful.)
• , (read) stores the current input byte on the tape. Good luck with doing anything Unicode-related.
• If , (read) encounters the end of stdin, then the program terminates with exit code 0.

cat.ohno

I believe there is only one somewhat meaningful program that is short enough to be discovered by brute force: cat -, or in words: copy stdin to stdout.

The desired bytecode in Brainfuck should to match this regular expression:

^\{,\.[<>][-\+]\}$

Oh god. Let's try the actual bytecode/nibblecode:

^[2A][6E][7F][45CD][0189][3B]$

Not much better.

This essentially means: "read and write, then move to a new cell and make sure that it's not zero (otherwise we wouldn't loop back)". Since that's only 6 instructions, and fixes only 16 bits, we need on average 65536 tries to find an ohno program that compiles to this bytecode.

Of course, there's even more general versions. Can you find a regex that captures all Brainfuck-bytecodes that are equivalent to cat -?

(Hint: No. At least not if this Brainfuck dialect is Turing-complete, because then you'd be solving, among other things, the halting problem. Not only that, you'd solve it with merely a Finite State Machine!)

So, after all, cat.ohno was computed like this, where ohno-search.c says #define OUTPUT_BYTES (6/2) (because we want 6 instructions, each taking up half of a byte):

./search | grep '^[2a][6e][7f][45cd][0189][3b] '

As you can see for yourself, there's lots of matches.

Let's measure throughput:

cat /dev/zero | pv -bartT | ./ohno example/cat/cat.ohno

Wow! This implementation reaches roughly 1 MiB/s on my machine, which is incredibly fast for being so shitty.

spacecat.ohno

The previous cat implementation uses a new cell for each character, which is bad™.

Changing OUTPUT_BYTES to (8/2) in ohno-search.c and recompiling let's us do this:

./search | grep '^[2a][6e][7f][2a][0189][3b][0189][3b] '

Which finds the included space-efficient cat implementation in a reasonable time. Note that I fixed 22 bits, so this should take (on average) 2 million guesses until something is found. In fact, the first such program is found on attempt 1779300. It seems that ./search is pleasently fast for being written so carelessly.

cat /dev/zero | pv -bartT | ./ohno example/spacecat/spacecat.ohno

It seems that this program only achieves 241KiB/s, which is probably due to having to rewind each character. As I'm using /dev/zero here, which always hits the worst-case, it may be a bit faster on real-life data.

TODO

The current implementation doesn't seem to be very fast at squeezing out several megabytes of ohno bytecode. Of course, this needs to be improved significantly in order to write literally-large programs that require gigabytes of bytecode, like MATLAB or AutoCAD.

Calculating cat.ohno took only 1 second. Obviously, that's too fast. Future versions of ohno thus should incorporate some hash function that is more time-intensive. bcrypt might be the way to go. Yes, this item is in direct contradiction to the previous point.

As already mentioned, this is just an interpreter, but a true compiler should be easily possible. This could seriously improve the execution time for the "jump back" instruction!

Are there other interesting ohno programs you can find? Something that does something even slightly advanced? Maybe Caesar encoding with wraparound?

Shoot me a Pull Request! :D

(Or just shoot me! Aargh, the pain from writing this! Oh god! Help!)