Skip to content

README.md

Latest commit

 

History

History
162 lines (128 loc) · 7.83 KB

README.md

File metadata and controls

162 lines (128 loc) · 7.83 KB
Raw

Malbolge interpreter + cat

A faithful Malbolge interpreter (Python) and a verified cat program, plus a heavy differential test suite that diffs the interpreter against Ben Olmstead's original 1998 reference C interpreter.

Files

File What it is
malbolge.py The interpreter. CLI: python3 malbolge.py prog.mb [--max-steps N].
cat.mb A Malbolge cat: copies stdin to stdout, halts on EOF.
hello.mb Prints Hello World!.
text2malbolge.py Linear text → Malbolge compiler (reference-safe; fast; ASCII scope).
text2malbolge_bor.py Branch-on-read compiler: full arbitrary-byte output (all 256 values).
tests/malbolge_dbg.c A from-scratch guarded+capped C interpreter, used as a fuzzing oracle.
tests/diff_test.py Interpreter differential + fuzz + edge-case + CLI suite.
tests/gen_test.py Linear compiler verification (programs run on the reference C).
tests/bor_test.py Branch-on-read verification: all 256 bytes on the reference C.

Running

printf 'Meow!' | python3 malbolge.py cat.mb            # -> Meow!
python3 malbolge.py hello.mb                            # -> Hello World!
python3 text2malbolge.py "Hi Dmitry" > p.mb && \
  python3 malbolge.py p.mb                              # -> Hi Dmitry

I/O is lazy and streaming: a program is never blocked waiting for input it does not read (/), and output appears as it is produced, exactly like the reference's getc/putc.

Conformance to the reference

malbolge.py is a line-for-line reimplementation of Olmstead's malbolge.c:

  • 59049 = 3¹⁰ words; registers a, c, d start at 0.
  • Instruction decode: xlat1[(mem[c] - 33 + c) % 94], dispatched over j i * p < / v o.
  • The crazy op is the verbatim base-9 o[9][9] table from the reference op() (not a hand-derived 3×3), so there is no transcription risk.
  • Rotate, the xlat1/xlat2 tables, memory fill op(mem[i-1], mem[i-2]), EOF → a = 59048, and output a & 0xFF all match.
  • Loader: skips C-isspace whitespace; rejects a graphical char that does not decode to one of ji*p</vo; accepts non-graphical, non-whitespace bytes (stored as-is); rejects programs longer than 59049 instructions.

Two deliberate deviations (documented)

The reference relies on C undefined behaviour in exactly two spots; we take the well-defined interpretation that every modern interpreter and the esolang spec agree on:

  1. Out-of-bounds encryption. The reference does mem[c] = xlat2[mem[c]-33] unconditionally. When c == d and a */p result leaves the cell outside 33..126, that reads past the 94-byte xlat2 array (and crashes the real interpreter — see note below). We apply encryption only when the cell is graphical. The over-written cell is never re-read in that situation, so observable output is identical for any program where the reference does not crash.

  2. Non-instruction cell. The reference's if (mem[c]<33||mem[c]>126) continue; skips the increment, so the machine spins forever with no further effect. We detect this provably-terminal state and return the output produced so far — observably identical to the hung reference.

Note: a naive linear generator that keeps d == c produces programs that trip exactly this case and crash the unmodified reference (out-of-bounds read). text2malbolge.py avoids it (see below); cat.mb/hello.mb keep d != c and run on the real reference interpreter unchanged.

text → Malbolge compiler

text2malbolge.py emits programs that keep d = c - 1: the operand of every rotate/crazy is the previous, already-encrypted cell (always graphical), and results are written behind the code pointer, so the current code cell stays graphical and the reference's encryption never goes out of bounds. The generated programs therefore run on Olmstead's unmodified interpreter.

Each output byte is reached by a breadth-first search over {nop, rotate, crazy} against the forced operand stream. The linear technique can reach about 201 of 256 byte values from the initial state -- enough for all printable ASCII (the common case). The unreachable high bytes are a property of the technique, not this implementation: the original zb3 linear generator loops forever on them, whereas text2malbolge.py raises Unreachable immediately.

Branch-on-read: full arbitrary-byte output

text2malbolge_bor.py removes the reachability limit by reading the operand from a controlled data region the code never executes, so the operand of every rotate/crazy is a byte we choose — and the accumulator can be driven to any value, so every byte 0..255 is emittable (verified on the reference C).

python3 text2malbolge_bor.py "café 🎉" > p.mb && python3 malbolge.py p.mb

It branches on the value of each data cell read, but over a fixed code/data split instead of a blind whole-program search (which is exponential — even zb3's blind BoR can't emit the bytes in ~154..208 in reasonable time). The layout, all verified by tracing the real machine:

  • pos 0: movd → after the cycle c=1, d=41.
  • pos 1: movd reads mem[41] (locked to the nop-char 121) → c=2, d=122, i.e. d = c + 120 from here on: the data pointer runs 120 cells ahead of the code pointer.
  • pos 2..121: code (rotate / crazy / out / halt); position 41 is reserved.
  • pos 122..: data. Code at position p reads mem[p+120].

Because the data pointer is 120 cells ahead, the cells it reads are not yet executed or encrypted, so we may store any byte there. We use the 155 non-whitespace, non-graphical byte values (1..8, 14..31, 127..255), which the loader stores verbatim with no instruction validation. Rotate/crazy write their result onto the data cell (d != c), so the executing code cell stays graphical and the reference's encryption never goes out of bounds.

Each output byte is reached by a tiny BFS over the accumulator (transitions a=rotr(V) and a=crazy(a,V)), usually 1–2 ops; the whole 0..255 sweep compiles in ~6 s (~24 ms/byte). Capacity is ~40–50 output bytes (120 code cells); past that it raises TooLong — use text2malbolge.py for longer ASCII text.

Test results

python3 tests/diff_test.py (needs the reference built at /tmp/malbolge_ref and tests/malbolge_dbg compiled):

  • Deliverables vs the unmodified Olmstead reference C:
    • hello.mb → Hello World! on both.
    • cat.mb → 826 inputs diffed byte-for-byte (empty, every single byte, every doubled byte, full + reversed 0–255, 300 random binary blobs): 826/826 exact matches.
  • Fuzzing vs the guarded C oracle: 10,000 random raw-byte programs + 10,000 random valid-op programs (random input, random step caps): 20,000/20,000 agreed on accept/reject and output.
  • Reference cross-check: 400 random valid programs run on the unmodified reference; all that halted there matched.
  • Spec edge cases: rotate/crazy values, empty program, whitespace-only, single v, invalid-instruction rejection, non-printable acceptance, the 59049 length cap — all pass.
  • CLI: hello.mb with stdin closed must not block; cat.mb piped/binary echo — all pass.

Total: ~21k checks, 0 failures.

python3 tests/gen_test.py (the linear compiler):

  • 228 ASCII texts compiled; every generated program reproduces its text on both the unmodified reference C and our interpreter.
  • Known-unreachable bytes raise Unreachable in <0.1s (no hang).

Total: 232 checks, 0 failures.

python3 tests/bor_test.py (the branch-on-read compiler):

  • All 256 byte values compiled and run on the unmodified reference C — 256/256 exact (~6 s total).
  • 17 multi-byte messages (UTF-8 café/Москва/日本語, high-byte runs, NULs, random up to 40 bytes), empty/NUL/0xFF edges, and clean TooLong past capacity.

Total: 277 checks, 0 failures.