#!/usr/bin/env python3 """ Pgmpietoncracklang+ -- reference interpreter. Input may be a PGM/PPM, a PNG, or a BMP. PNG and BMP are decoded with the standard library only (zlib plus bit twiddling); no Pillow required. PGM input dispatches on the header comment: # PROLAN/M SUM.PRM by Keymaker (A,B) Only (A,B) is read; the rest of the file is assumed. Keymaker's SUM.PRM is run on "A+B=?" and the derivation trace becomes the raster of a new P5 whose comment gains " RESULT". # XKCD Random Number cat the 4th line (the maxval) and emit the fair-dice-roll image. anything else The raster itself is taken as the SUM.PRM input string. PNG/BMP input has no header comment, so it dispatches on pixel content: 1. If the bitmap is the fair-dice-roll glyph -- at any integer scale, in either polarity, and either 4 rows (as the "4 4" header declares) or 5 rows (as the spec's data block actually lists) -- the image is stored as a PGM in memory and its 4th line is cat'd as the ink. 2. Otherwise the pixels ARE the file. Samples are read row-major, one byte each. If they spell a PNM, that is re-entered as if it had been the input file, so a PNG "looking like" the P5 above behaves exactly like the P5. If they spell a bare expression, it goes to SUM.PRM. Usage: pgmpietoncracklang_plus.py [infile] [-o out] [--text] [--newlines] [--maxval N] (infile defaults stdin) """ import sys import io import re import zlib import struct import argparse # --------------------------------------------------------------------------- # The hardwired PROLAN/M program. Rule 0 is the ($,...) comment rule, which # can never fire because '$' never occurs in the working string; the trace # numbers in the spec are indices into this list. # --------------------------------------------------------------------------- SUM_PRM = r"""($, PROLAN/M sum program, written by Keymaker ) (=?,*=) (.A,A.) (.B,B.) (.C,C.) (.D,D.) (.E,E.) (.F,F.) (.G,G.) (.H,H.) (.I,I.) (.J,J.) (.P,P.) (.=,=.) (=...........,=#) (=..........,=9) (=.........,=8) (=........,=7) (=.......,=6) (=......,=5) (=.....,=4) (=....,=3) (=...,=2) (=..,=1) (=.,=0) (0*,*A.) (1*,*B..) (2*,*C...) (3*,*D....) (4*,*E.....) (5*,*F......) (6*,*G.......) (7*,*H........) (8*,*I.........) (9*,*J..........) (+*,*P...........) (a_,_bbbbbbbbbb) (_,) (b,a) (#0,_#) (#1,_b#) (#2,_bb#) (#3,_bbb#) (#4,_bbbb#) (#5,_bbbbb#) (#6,_bbbbbb#) (#7,_bbbbbbb#) (#8,_bbbbbbbb#) (#9,_bbbbbbbbb#) (=@,=1) (0@,1) (1@,2) (2@,3) (3@,4) (4@,5) (5@,6) (6@,7) (7@,8) (8@,9) (9@,@0) (a,@) (*,) (#,) (A,0) (B,1) (C,2) (D,3) (E,4) (F,5) (G,6) (H,7) (I,8) (J,9) (P,+) (,)""" # --------------------------------------------------------------------------- # PROLAN/M # --------------------------------------------------------------------------- def parse_prolan(src): """Parse '(lhs,rhs)' rules, one per line. Splits on the FIRST comma.""" rules = [] for line in src.split("\n"): line = line.strip() if not (line.startswith("(") and line.endswith(")")): continue lhs, _, rhs = line[1:-1].partition(",") rules.append((lhs, rhs)) return rules def run_prolan(rules, s, limit=1_000_000): """ Markov-style: scan the rule list top to bottom, apply the first rule whose LHS occurs in the string (leftmost occurrence, one replacement), then start over from the top. A rule with an empty LHS is the terminator. Returns a list of (rule_index, string_after) pairs -- the derivation trace. """ trace = [] for _ in range(limit): for i, (lhs, rhs) in enumerate(rules): if lhs == "": return trace # (,) -- halt j = s.find(lhs) if j >= 0: s = s[:j] + rhs + s[j + len(lhs):] trace.append((i, s)) break else: return trace # nothing matched at all raise RuntimeError("PROLAN/M step limit exceeded") def format_trace(trace): """'%4d %s' -- rule number right-aligned in 4, two spaces, then the tape.""" return ["%4d %s" % (i, s) for i, s in trace] # --------------------------------------------------------------------------- # PGM # --------------------------------------------------------------------------- class PGM: __slots__ = ("magic", "comments", "width", "height", "maxval", "raster", "lines") def parse_pgm(data: bytes) -> PGM: """ Deliberately line-oriented rather than token-oriented: Pgmpietoncracklang+ cares about *which line* things are on. The raster is kept as raw bytes so a genuine binary P5 bitmap survives the round trip. """ p = PGM() p.lines = data.split(b"\n") it = iter(range(len(p.lines))) def nextline(): i = next(it) return i, p.lines[i].decode("latin-1") _, p.magic = nextline() p.magic = p.magic.strip() p.comments = [] idx, line = nextline() while line.lstrip().startswith("#"): p.comments.append(line.strip()) idx, line = nextline() dims = line.split() p.width, p.height = (int(dims[0]), int(dims[1])) if len(dims) >= 2 else (0, 0) idx, line = nextline() p.maxval = int(line.split()[0]) if line.split() else 255 p.raster = b"\n".join(p.lines[idx + 1:]) return p def emit_pgm(comment, lines, maxval, newlines=False): """ Build a P5 file whose raster is `lines`, space-padded to a common width. A P5 raster is exactly width*height bytes with NO separators, so by default the padded rows are concatenated flush. If you keep the newlines instead, each row is width+1 bytes long while the header still advertises width, and every row lands one byte to the left of the one above it -- the image shears into diagonal stripes. newlines=True declares width+1 so the file stays both human-readable and geometrically honest, at the cost of a column of value-10 pixels down the right edge. """ w = max((len(x) for x in lines), default=0) h = len(lines) padded = [x.ljust(w) for x in lines] if newlines: return "P5\n%s\n%d %d\n%d\n%s" % (comment, w + 1, h, maxval, "\n".join(padded) + "\n") return "P5\n%s\n%d %d\n%d\n%s" % (comment, w, h, maxval, "".join(padded)) # the glyph is not parameterised: it is guaranteed to be random DICE_GLYPH = [ [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 1, 1], [0, 0, 0, 1], [0, 0, 0, 1], ] # --------------------------------------------------------------------------- # Image input. Pgmpietoncracklang+ accepts PGM/PPM, PNG and BMP. PNG and BMP # are decoded to a 2D array of grayscale sample values with no third-party # dependency -- zlib is stdlib and everything else is bit twiddling. # --------------------------------------------------------------------------- def _unfilter(raw, w, h, ch, bd): """Undo the five PNG scanline filters.""" stride = (w * ch * bd + 7) // 8 bpp = max(1, ch * bd // 8) out = [] prev = bytearray(stride) i = 0 for _ in range(h): f = raw[i] i += 1 line = bytearray(raw[i:i + stride]) i += stride if f: for x in range(stride): a = line[x - bpp] if x >= bpp else 0 b = prev[x] c = prev[x - bpp] if x >= bpp else 0 if f == 1: line[x] = (line[x] + a) & 255 elif f == 2: line[x] = (line[x] + b) & 255 elif f == 3: line[x] = (line[x] + (a + b) // 2) & 255 elif f == 4: p = a + b - c pa, pb, pc = abs(p - a), abs(p - b), abs(p - c) pr = a if (pa <= pb and pa <= pc) else (b if pb <= pc else c) line[x] = (line[x] + pr) & 255 else: raise ValueError("bad PNG filter %d" % f) out.append(line) prev = line return out def _samples(line, w, ch, bd): """Pull w*ch samples out of one unfiltered scanline, normalised to 0..255.""" if bd == 8: return list(line[:w * ch]) if bd == 16: return list(line[0:w * ch * 2:2]) vals = [] per = 8 // bd mask = (1 << bd) - 1 scale = 255 // mask for k in range(w * ch): byte = line[k // per] shift = 8 - bd * (k % per + 1) vals.append(((byte >> shift) & mask) * scale) return vals def read_png(data): if data[:8] != b"\x89PNG\r\n\x1a\n": raise ValueError("not a PNG") pos, idat, plte = 8, b"", None w = h = bd = ct = 0 interlace = 0 while pos < len(data): (ln,) = struct.unpack(">I", data[pos:pos + 4]) typ = data[pos + 4:pos + 8] body = data[pos + 8:pos + 8 + ln] pos += 12 + ln if typ == b"IHDR": w, h, bd, ct, _, _, interlace = struct.unpack(">IIBBBBB", body) elif typ == b"PLTE": plte = body elif typ == b"IDAT": idat += body elif typ == b"IEND": break if interlace: raise ValueError("interlaced PNG unsupported") ch = {0: 1, 2: 3, 3: 1, 4: 2, 6: 4}[ct] lines = _unfilter(zlib.decompress(idat), w, h, ch, bd) px = [] for line in lines: s = _samples(line, w, ch, bd) row = [] for x in range(w): v = s[x * ch:x * ch + ch] if ct == 0 or ct == 4: g = v[0] elif ct == 3: # palette indices were scaled by _samples; undo that idx = v[0] * ((1 << bd) - 1) // 255 if bd < 8 else v[0] r, gg, b = plte[idx * 3:idx * 3 + 3] g = round(0.299 * r + 0.587 * gg + 0.114 * b) else: g = round(0.299 * v[0] + 0.587 * v[1] + 0.114 * v[2]) row.append(g) px.append(row) return px def read_bmp(data): if data[:2] != b"BM": raise ValueError("not a BMP") (off,) = struct.unpack("= 24: b, g, r = line[x * (bpp // 8):x * (bpp // 8) + 3] else: per = 8 // bpp mask = (1 << bpp) - 1 idx = (line[x // per] >> (8 - bpp * (x % per + 1))) & mask b, g, r = pal[idx * 4:idx * 4 + 3] row.append(round(0.299 * r + 0.587 * g + 0.114 * b)) rows.append(row) return rows if topdown else rows[::-1] def sniff(data): if data[:8] == b"\x89PNG\r\n\x1a\n": return "png" if data[:2] == b"BM": return "bmp" if data[:1] == b"P" and data[1:2] in b"123456": return "pnm" return "pnm" # --------------------------------------------------------------------------- # Recognising the fair-dice-roll bitmap. # # The spec's P3 block declares "4 4" but lists five rows, so a conformant # reader sees the 4-row truncation while the author meant the 5-row glyph. # Both are accepted, at any integer scale, in either polarity. # --------------------------------------------------------------------------- def dice_match(px): h = len(px) if not h: return False w = len(px[0]) for rows in (5, 4): if w % 4 or h % rows: continue k = h // rows if k == 0 or w // 4 != k: continue samp = [[px[y * k + k // 2][x * k + k // 2] for x in range(4)] for y in range(rows)] vals = sorted({v for r in samp for v in r}) if len(vals) != 2: continue for ink, bg in ((vals[1], vals[0]), (vals[0], vals[1])): if all(samp[y][x] == (ink if DICE_GLYPH[y][x] else bg) for y in range(rows) for x in range(4)): return True return False # --------------------------------------------------------------------------- # Header-comment dispatch # --------------------------------------------------------------------------- # --------------------------------------------------------------------------- # Self-hosting: a PGM whose raster IS the interpreter. # # The raster is executed as Python if and only if the header comment is # exactly "# Pgmpietoncracklang+". No other comment, and no image input # path, can ever reach exec(). This is arbitrary code execution by design: # a packed PGM is exactly as trustworthy as the .py that went into it. # # The embedded program inherits stdin untouched and sees an argv of just # [progname], so an interpreter that reads open(0) or falls back to stdin # composes without knowing it has been embedded: # # python3 thisfile.py interpreter.pgm < example_sum_0_0.pgm # --------------------------------------------------------------------------- SELF_RE = re.compile(r"^#\s*Pgmpietoncracklang\+\s*$") def unpack_source(p): """Undo the rectangular padding: chunk into rows, drop right-hand fill.""" r = p.raster.decode("latin-1") if p.width and len(r) >= p.width * p.height: rows = [r[i * p.width:(i + 1) * p.width] for i in range(p.height)] else: rows = r.split("\n") return "\n".join(x.rstrip() for x in rows) def run_embedded(source): """ exec the unpacked source, capturing stdout. stdout is a TextIOWrapper over a BytesIO rather than a bare StringIO so that embedded code writing to sys.stdout.buffer works as well as print(). """ raw = io.BytesIO() cap = io.TextIOWrapper(raw, encoding="latin-1", newline="") old_out, old_argv = sys.stdout, sys.argv[:] sys.stdout, sys.argv = cap, [sys.argv[0]] try: try: exec(compile(source, "", "exec"), {"__name__": "__main__"}) except SystemExit: pass except Exception as e: # The commonest cause by far: a chain of packed PGMs deeper than # the one stdin available to feed it, so the innermost program # reads an empty file. Say so instead of leaking an IndexError. sys.stderr.write( "embedded Pgmpietoncracklang+ program failed: %s: %s\n" "(a packed chain consumes exactly one input; if this is the\n" " innermost level, there was nothing left on stdin for it)\n" % (type(e).__name__, e)) raise SystemExit(1) cap.flush() finally: sys.stdout, sys.argv = old_out, old_argv return raw.getvalue().decode("latin-1") def pack_source(path, maxval=255, wiki=False): """ Wrap a .py file up as a runnable PGM. The header is padded with a filler comment to an exact multiple of the raster width, so the file viewed as a width-w image has the header as whole rows and one source line per row after it. Without this the header is a partial row and every line below it is offset, which shears the picture into diagonal streaks. """ lines = open(path, encoding="latin-1").read().split("\n") while lines and not lines[-1].strip(): lines.pop() if wiki: # Wiki-safe form: indent with spaces not tabs, and leave the rows # unpadded. unpack_source falls back to splitting on newlines when # the raster is shorter than width*height, so this still runs -- and # it survives an editor that strips trailing whitespace, which the # padded form does not. lines = [x.replace("\t", " ") if x[:1] == "\t" else x for x in lines] while any(x[:1] == "\t" for x in lines): lines = [x.replace("\t", " ", 1) if x[:1] == "\t" else x for x in lines] w = max(len(x) for x in lines) + 1 h = len(lines) return "P5\n# Pgmpietoncracklang+\n%d %d\n%d\n%s\n" % ( w, h, maxval, "\n".join(lines)) w = max(len(x) for x in lines) h = len(lines) magic = "# Pgmpietoncracklang+\n" head = "P5\n%s%d %d\n%d\n" % (magic, w, h, maxval) pad = (-len(head)) % w if 0 < pad < 2: pad += w # a filler comment needs at least "#\n" if pad: head = head.replace(magic, magic + "#" + " " * (pad - 2) + "\n", 1) return head + "".join(x.ljust(w) for x in lines) SUM_RE = re.compile( r"^#\s*PROLAN/M\s+SUM\.PRM\s+by\s+Keymaker\s*\(\s*(\d+)\s*,\s*(\d+)\s*\)\s*$" ) XKCD_RE = re.compile(r"^#\s*XKCD\s+Random\s+Number\s*$", re.I) def xkcd_random_number(ink): """cat the 4th line's value, then draw it.""" rows = ["".join("%3d " % (ink if px else 0) for px in row) for row in DICE_GLYPH] return ( "P3\n" "# //chosen by fair dice roll.;\\n guaranteed to be random.//\n" "4 4\n" "%d\n" % ink + "\n".join(rows) + "\n" ) def run_sum(expr): return format_trace(run_prolan(parse_prolan(SUM_PRM), expr)) def interpret(data: bytes, newlines=False, text=False, maxval=None, depth=0): kind = sniff(data) if kind in ("png", "bmp"): px = read_png(data) if kind == "png" else read_bmp(data) # The fair-dice-roll bitmap, at any scale, either polarity. The image # is stored as a PGM in memory and its 4th line -- the maxval -- is # cat'd out as the ink of the reply. It is canonicalised to the # spec's own {0,4} representation so a black/white PNG doesn't come # back with ink 255. if dice_match(px): mem = "P5\n# XKCD Random Number\n%d %d\n4\n" % ( len(px[0]), len(px)) return xkcd_random_number(int(mem.split("\n")[3])) # Otherwise the pixels ARE the file: read row-major, each sample one # byte. If that spells a PNM, re-enter the normal path; if it spells # a bare expression, hand it straight to SUM.PRM. flat = bytes(v & 255 for row in px for v in row) if depth == 0 and sniff(flat) == "pnm" and flat[:1] == b"P": return interpret(flat, newlines, text, maxval, depth + 1) expr = flat.decode("latin-1").strip() lines = run_sum(expr) if text: return "\n".join(lines) + "\n" return emit_pgm("# %s RESULT" % expr, lines, 255 if maxval is None else maxval, newlines) p = parse_pgm(data) comment = p.comments[0] if p.comments else "" mv = p.maxval if maxval is None else maxval if SELF_RE.match(comment): return run_embedded(unpack_source(p)) m = SUM_RE.match(comment) if m: expr = "%s+%s=?" % (m.group(1), m.group(2)) elif XKCD_RE.match(comment): return xkcd_random_number(p.maxval) else: expr = p.raster.decode("latin-1").strip() comment = comment or "#" lines = run_sum(expr) if text: return "\n".join(lines) + "\n" return emit_pgm(comment + " RESULT", lines, mv, newlines) def main(): ap = argparse.ArgumentParser(description="Pgmpietoncracklang+ interpreter") ap.add_argument("infile", nargs="?", help="PGM source (default: stdin)") ap.add_argument("-o", "--outfile", help="write here instead of stdout") ap.add_argument("--text", action="store_true", help="emit the bare trace instead of wrapping it in a PGM") ap.add_argument("--newlines", action="store_true", help="keep newlines between raster rows (declares width+1)") ap.add_argument("--pack", metavar="FILE", help="wrap a .py file as a runnable # Pgmpietoncracklang+ PGM") ap.add_argument("--wiki", action="store_true", help="with --pack: unpadded, tab-free, wiki-safe output") ap.add_argument("--maxval", type=int, help="override the output maxval (255 makes the text legible)") args = ap.parse_args() if args.pack: out = pack_source(args.pack, 255 if args.maxval is None else args.maxval, wiki=args.wiki) if args.outfile: open(args.outfile, "wb").write(out.encode("latin-1")) else: sys.stdout.buffer.write(out.encode("latin-1")) return data = (open(args.infile, "rb").read() if args.infile else sys.stdin.buffer.read()) out = interpret(data, newlines=args.newlines, text=args.text, maxval=args.maxval) if args.outfile: open(args.outfile, "wb").write(out.encode("latin-1")) else: sys.stdout.buffer.write(out.encode("latin-1")) if __name__ == "__main__": main()