<?phpnamespace App\Titus;/** * Decompresses the original "SQZ" files (OpenTitus sqz.c): a 4-byte header (output size on 20 bits, * compression type) followed by LZW (type 0x10) or Huffman + run-length data. * * Integers stay below 2^24 so the decoder also works with the 32-bit integers of the browser. */final class Sqz{ private const LZW_CLEAR_CODE = 0x100; private const LZW_END_CODE = 0x101; private const LZW_FIRST = 0x102; private const LZW_MAX_TABLE = 4096; /** @return string the decompressed bytes */ public static function load(string $file): string { $data = @file_get_contents($file); if ($data === false) { throw new \RuntimeException("Can't open input file: $file"); } return self::decode($data, $file); } public static function decode(string $data, string $name = 'data'): string { if (strlen($data) < 4) { throw new \RuntimeException("File too short: $name"); } $outLen = ((ord($data[0]) & 0x0F) << 16) | (ord($data[3]) << 8) | ord($data[2]); if ($outLen === 0) { throw new \RuntimeException("Invalid file: $name"); } // byte strings, not arrays: big PHP arrays make the browser runtime reallocate huge blocks $input = substr($data, 4); $out = ord($data[1]) === 0x10 ? self::lzw($input, $outLen) : self::huffman($input, $outLen); return str_pad(substr($out, 0, $outLen), $outLen, "\0"); } private static function lzw(string $input, int $outLen): string { $inLen = strlen($input); $nbit = 9; $bitadd = 0; $kPos = 0; $w = 0; $addToDict = false; $prefix = []; $char = []; $dictLength = 0; $stack = []; $out = ''; $outPos = 0; while ($kPos < $inLen && $outPos < $outLen) { // the code is at most 12 bits starting at bit $bitadd (< 8): 3 bytes are enough $k = 0; for ($i = 0; $i < 3; $i++) { $k = ($k << 8) | ($kPos + $i < $inLen ? ord($input[$kPos + $i]) : 0); } $k = ($k >> (24 - $bitadd - $nbit)) & ((1 << $nbit) - 1); $bitadd += $nbit; while ($bitadd > 8) { $bitadd -= 8; $kPos++; } if ($k === self::LZW_CLEAR_CODE) { $nbit = 9; $dictLength = 0; $addToDict = false; } elseif ($k !== self::LZW_END_CODE) { if ($k > 255 && $k < self::LZW_FIRST + $dictLength) { $i = 0; $tmp = $k; while ($tmp >= self::LZW_FIRST) { $stack[$i] = $char[$tmp - self::LZW_FIRST]; $tmp = $prefix[$tmp - self::LZW_FIRST]; if (++$i > self::LZW_MAX_TABLE) { throw new \RuntimeException('SQZ: dictionary overflow'); } } $stack[$i++] = $tmp; $last = $i - 1; while (--$i > 0) { $out .= chr($stack[$i]); $outPos++; } $out .= chr($stack[0]); $outPos++; $stack[0] = $stack[$last]; } elseif ($k > 255) { $i = 1; $tmp = $w; while ($tmp >= self::LZW_FIRST) { $stack[$i] = $char[$tmp - self::LZW_FIRST]; $tmp = $prefix[$tmp - self::LZW_FIRST]; if (++$i > self::LZW_MAX_TABLE) { throw new \RuntimeException('SQZ: dictionary overflow'); } } $stack[$i++] = $tmp; $stack[0] = $dictLength > 0 ? $char[$dictLength - 1] : $w; $last = $i - 1; while (--$i > 0) { $out .= chr($stack[$i]); $outPos++; } $out .= chr($stack[0]); $outPos++; $stack[0] = $stack[$last]; } else { $out .= chr($k); $outPos++; $stack[0] = $k; } if ($addToDict && self::LZW_FIRST + $dictLength < self::LZW_MAX_TABLE) { $char[$dictLength] = $stack[0]; $prefix[$dictLength] = $w; $dictLength++; } $w = $k; $addToDict = true; } if (self::LZW_FIRST + $dictLength === (1 << $nbit) && $nbit < 12) { $nbit++; } } return $out; } private static function huffman(string $input, int $outLen): string { $inLen = strlen($input); $treeSize = ord($input[0]) | (ord($input[1]) << 8); $tree = array_values(unpack('v*', substr($input, 2, $treeSize) . "\0\0") ?: []); $node = 0; $state = 0; $count = 0; $last = 0; $out = ''; for ($i = 2 + $treeSize; $i < $inLen && strlen($out) < $outLen; $i++) { for ($bit = 128; $bit >= 1; $bit >>= 1) { if (ord($input[$i]) & $bit) { $node++; } $bintree = $tree[$node] ?? 0; if ($bintree <= 0x7FFF) { $node = $bintree >> 1; continue; } $node = $bintree & 0x7FFF; $nodeL = $node & 0xFF; if ($state === 0) { if ($node < 0x100) { $last = chr($nodeL); $out .= $last; } elseif ($nodeL === 0) { $state = 1; } elseif ($nodeL === 1) { $state = 2; } else { $out .= str_repeat((string)$last, $nodeL); } } elseif ($state === 1) { $out .= str_repeat((string)$last, $node); $state = 0; } elseif ($state === 2) { $count = 256 * $nodeL; $state = 3; } else { $out .= str_repeat((string)$last, $count + $nodeL); $state = 0; } $node = 0; } } return $out; }}