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