<?phpnamespace App\Alis\Lang;/** * Reads the byte code of an unpacked ALIS script into instructions (Grammar), following the flow of the program * from its entry points (main, the "before" and "after" vectors, jumps, calls, switches). The bytes no path * reaches stay data (Script::$chunks keeps them as they are: nothing is lost). * * An instruction: ['at' => offset, 'end' => offset after it, 'op' => opcode, 'ops' => [operand...]]. * Operands: ['E'|'S'|'A', item], ['b'|'w'|'W'|'l', int], ['j', bits, target, pad], ['z', bytes], ['v', offset, long], * ['r', bytes] and the specials (see special()). An item: ['c' => code, 'a' => its own operand, 'sub' => [items]]. */final class Decoder{ private string $b = ''; private int $p = 0; private int $end = 0; /** @var list<int> */ public array $targets = []; public function __construct(private string $bytes, private int $codeStart, private int $codeEnd) { $this->b = $bytes; $this->end = $codeEnd; } /** * Decodes the program reachable from $entries. * @param list<int> $entries * @return array{0: array<int, array<string, mixed>>, 1: array<int, true>, 2: list<string>} instructions by offset, labels, problems */ public function program(array $entries): array { $ins = []; $labels = []; $problems = []; $owner = []; // byte offset => instruction start $todo = $entries; foreach ($entries as $e) { $labels[$e] = true; } while ($todo) { $at = array_pop($todo); while (true) { if (isset($ins[$at])) { break; } if (isset($owner[$at])) { $problems[] = sprintf('jump into the middle of the instruction at %04x (target %04x)', $owner[$at], $at); break; } if ($at < $this->codeStart || $at >= $this->codeEnd) { if ($at !== $this->codeEnd) { $problems[] = sprintf('flow leaves the code at %04x', $at); } break; } try { $i = $this->instruction($at); } catch (\RuntimeException $e) { $problems[] = sprintf('%04x: %s', $at, $e->getMessage()); break; } for ($k = $at; $k < $i['end']; $k++) { if (isset($owner[$k]) || isset($ins[$k])) { $problems[] = sprintf('instruction at %04x overlaps the one at %04x', $at, $owner[$k] ?? $k); break 2; } } for ($k = $at; $k < $i['end']; $k++) { $owner[$k] = $at; } $ins[$at] = $i; foreach ($this->jumpTargets() as $t) { $labels[$t] = true; $todo[] = $t; } if (self::stops($i)) { break; } $at = $i['end']; } } ksort($ins); // the gaps: dead code (a jump after a loop, an exit after a stop...) when it decodes exactly, else data $p = $this->codeStart; $gaps = []; foreach ($ins + [$this->codeEnd => ['at' => $this->codeEnd, 'end' => $this->codeEnd]] as $i) { if ($i['at'] > $p) { $gaps[] = [$p, $i['at']]; } $p = max($p, $i['end']); } foreach ($gaps as [$from, $to]) { $dead = []; $deadTargets = []; $at = $from; try { while ($at < $to) { $i = $this->instruction($at); $i['dead'] = true; $dead[$at] = $i; array_push($deadTargets, ...$this->jumpTargets()); $at = $i['end']; } } catch (\RuntimeException) { continue; } if ($at !== $to) { continue; } foreach ($deadTargets as $t) { if (!isset($ins[$t]) && !isset($dead[$t]) && $t !== $this->codeEnd) { continue 2; // a jump into nothing known: keep the bytes as data } } $ins += $dead; foreach ($deadTargets as $t) { $labels[$t] = true; } } ksort($ins); return [$ins, $labels, $problems]; } /** @return list<int> the jump targets of the last decoded instruction */ public function jumpTargets(): array { return $this->targets; } /** Does the flow stop after this instruction (no fall through)? */ public static function stops(array $i): bool { $name = Grammar::OPCODES[$i['op']][0]; return in_array($name, ['cjmp8', 'cjmp16', 'cjmp24', 'cret', 'cleave', 'cstopret'], true); } /** Decodes one instruction at $at (throws \RuntimeException on an impossible one). */ public function instruction(int $at): array { $this->targets = []; $this->p = $at; $op = $this->u8(); [$name, $spec] = Grammar::OPCODES[$op]; $ops = $spec === '' ? [] : ($spec[0] === '@' ? $this->special(substr($spec, 1)) : $this->operands($spec)); return ['at' => $at, 'end' => $this->p, 'op' => $op, 'ops' => $ops]; } /** @return list<array<int, mixed>> */ private function operands(string $spec): array { $ops = []; foreach (explode(' ', $spec) as $t) { $ops[] = match (true) { $t === 'E' => ['E', $this->item(Grammar::OPERS)], $t === 'S' => ['S', $this->item(Grammar::STORES)], $t === 'A' => ['A', $this->item(Grammar::ADDS)], $t === 'b' => ['b', $this->u8()], $t === 'w' => ['w', $this->s16()], $t === 'W' => ['W', $this->u16()], $t === 'l' => ['l', $this->s32()], $t === 'z' => ['z', $this->zstr()], $t === 'v' => $this->vaddr(), $t === 'j8' || $t === 'j16' || $t === 'j24' => $this->jump((int) substr($t, 1)), $t[0] === 'r' => ['r', $this->raw((int) substr($t, 1))], default => throw new \LogicException("grammar token $t"), }; } return $ops; } /** @return list<array<int, mixed>> */ private function special(string $name): array { switch ($name) { case 'esc1': $code = $this->u8(); if (!isset(Grammar::ESC1[$code])) { throw new \RuntimeException("unknown escape $code"); } $spec = Grammar::ESC1[$code][1]; return [['esc', $code, $spec === '' ? [] : $this->operands($spec)]]; case 'dim': $offset = $this->s16(); $counter = $this->u8(); $byte2 = $this->u8(); $vals = []; $n = $counter & 0xf; for ($i = 0; $i < $n; $i++) { $vals[] = $counter & 0x80 ? $this->s32() : $this->u16(); } $vals[] = $this->s32(); return [['dim', $offset, $counter, $byte2, $vals]]; case 'switch1': case 'switch2': $e = $this->item(Grammar::OPERS); $n = $this->u8(); $pad = null; if ($this->p & 1) { $pad = $this->u8(); } if ($name === 'switch1') { $cases = []; for ($i = 0; $i <= $n; $i++) { $test = $this->s16(); $off = $this->s16(); $cases[] = [$test, $this->target($this->p + $off)]; } return [['sw1', $e, $n, $pad, $cases]]; } $base = $this->s16(); $targets = []; for ($i = 0; $i <= $n; $i++) { $off = $this->s16(); $targets[] = $this->target($this->p + $off); } return [['sw2', $e, $n, $pad, $base, $targets]]; case 'load': $id = $this->u16(); if ($id != 0) { return [['load', $id, $this->zstr(), null]]; } return [['load', 0, null, $this->item(Grammar::OPERS)]]; case 'fopen': if ($this->peek() === 0xff) { $this->p++; return [['fopen', null, $this->item(Grammar::OPERS), $this->item(Grammar::OPERS)]]; } return [['fopen', $this->zstr(), $this->u16(), null]]; case 'send': $n = $this->u8(); $to = $this->item(Grammar::OPERS); $vals = []; for ($i = 0; $i <= $n; $i++) { $vals[] = $this->item(Grammar::OPERS); } return [['send', $n, $to, $vals]]; case 'zap': $ops = []; for ($i = 0; $i < 4; $i++) { $ops[] = ['E', $this->item(Grammar::OPERS)]; } // the VM skips the 5th operand when the length (4th) is 0: the compiler wrote none after a constant 0 if (self::constant($ops[3][1]) !== 0) { $ops[] = ['E', $this->item(Grammar::OPERS)]; } return $ops; case 'defvect': $n = $this->u8(); return [['defvect', $n, $this->raw($n * 3 + 3)]]; case 'chartmap': $ops = [$this->vaddr(), ['E', $this->item(Grammar::OPERS)]]; $mode = self::constant($ops[1][1]); $ops[] = $mode === 0 || $mode === 1 ? $this->vaddr() : ['E', $this->item(Grammar::OPERS)]; return $ops; } throw new \LogicException("special $name"); } /** The value of an item that is a plain constant, else null. */ public static function constant(array $item): ?int { return in_array($item['c'], [0x00, 0x02, 0x3c], true) ? $item['a'] : null; } /** @param array<int, array{0: string, 1: string, 2: string}> $table */ private function item(array $table): array { $c = $this->u8(); if (!isset($table[$c])) { throw new \RuntimeException(sprintf('invalid operand code %02x at %04x', $c, $this->p - 1)); } [, $spec, $kind] = $table[$c]; $a = match ($spec) { '' => null, 'b' => $this->u8(), 'w' => $this->s16(), 'h' => [$this->s16(), $this->s16()], 'i8' => $this->s8(), 'i16' => $this->s16(), 'i32' => $this->s32(), 'z' => $this->zstr(), default => throw new \LogicException("operand $spec"), }; $sub = []; if ($kind === 'b') { $sub[] = $this->item(Grammar::OPERS); } elseif ($kind === 'e' || $kind === 's') { do { $x = $this->item(Grammar::OPERS); $sub[] = $x; } while ($x['c'] !== 0x3a); if ($kind === 's') { $sub[] = $this->item($table); } } return ['c' => $c, 'a' => $a, 'sub' => $sub]; } private function jump(int $bits): array { $pad = null; if ($bits === 8) { $off = $this->s8(); } elseif ($bits === 16) { $off = $this->s16(); } else { $off = $this->s16(); $pad = $this->u8(); } return ['j', $bits, $this->target($this->p + $off), $pad]; } private function target(int $t): int { $this->targets[] = $t; return $t; } private function vaddr(): array { $o = $this->s16(); if ($o === 0) { return ['v', $this->s16(), true]; } return ['v', $o, false]; } private function need(int $n): void { if ($this->p + $n > $this->end) { throw new \RuntimeException(sprintf('reads past the end of the code (%04x)', $this->p)); } } private function peek(): int { $this->need(1); return ord($this->b[$this->p]); } private function u8(): int { $this->need(1); return ord($this->b[$this->p++]); } private function s8(): int { $v = $this->u8(); return $v >= 0x80 ? $v - 0x100 : $v; } private function u16(): int { $this->need(2); $v = ord($this->b[$this->p]) | (ord($this->b[$this->p + 1]) << 8); $this->p += 2; return $v; } private function s16(): int { $v = $this->u16(); return $v >= 0x8000 ? $v - 0x10000 : $v; } private function s32(): int { $lo = $this->u16(); $hi = $this->s16(); return $hi * 0x10000 + $lo; } private function zstr(): string { $z = strpos($this->b, "\0", $this->p); if ($z === false || $z >= $this->end) { throw new \RuntimeException('unterminated string'); } $s = substr($this->b, $this->p, $z - $this->p); $this->p = $z + 1; return $s; } private function raw(int $n): string { $this->need($n); $s = substr($this->b, $this->p, $n); $this->p += $n; return $s; }}