PT
games/alis / src / Alis / Lang / Decoder.php · commit 9c722cf
<?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;    }}