From 35cf09cd6ca9d5f8710ceb1e4f45dbafdbb57bec Mon Sep 17 00:00:00 2001 From: Daniel Karbach Date: Mon, 9 May 2022 16:07:43 +0200 Subject: [PATCH] beat codec --- app/Beat/Decoder.php | 155 ++++++++++++++++++++ app/Beat/Encoder.php | 167 ++++++++++++++++++++++ app/Console/Commands/BeatDiffCommand.php | 38 +++++ app/Console/Commands/BeatPatchCommand.php | 38 +++++ 4 files changed, 398 insertions(+) create mode 100644 app/Beat/Decoder.php create mode 100644 app/Beat/Encoder.php create mode 100644 app/Console/Commands/BeatDiffCommand.php create mode 100644 app/Console/Commands/BeatPatchCommand.php diff --git a/app/Beat/Decoder.php b/app/Beat/Decoder.php new file mode 100644 index 0000000..7dc654c --- /dev/null +++ b/app/Beat/Decoder.php @@ -0,0 +1,155 @@ +source = $source; + } + + public function applyPatch($patch) { + $this->patch = $patch; + $this->patchCursor = 0; + $this->outputOffset = 0; + $this->sourceRelativeOffset = 0; + $this->targetRelativeOffset = 0; + + $this->readHeader(); + while ($this->hasAction()) { + $this->handleAction(); + } + + $sourceCrc = $this->read32(); + $targetCrc = $this->read32(); + $patchCrc = $this->read32(); + + if (crc32($this->source) != $sourceCrc) { + throw new Exception('source checksum mismatch'); + } + if (crc32($this->target) != $targetCrc) { + throw new Exception('target checksum mismatch'); + } + if (crc32(substr($this->patch, 0, -4)) != $patchCrc) { + throw new Exception('patch checksum mismatch'); + } + + return $this->target; + } + + + private function readHeader() { + $header = $this->readString(4); + if ($header != 'BPS1') { + throw new Exception('invalid header: '.$header); + } + + $sourceSize = $this->readNumber(); + $targetSize = $this->readNumber(); + $metadataSize = $this->readNumber(); + $this->metadata = $this->readString($metadataSize); + if ($sourceSize != strlen($this->source)) { + throw new Exception('source size mismatch. source: '.strlen($this->source).', patch: '.$sourceSize); + } + $this->target = str_repeat("\0", $targetSize); + } + + private function hasAction() { + return $this->patchCursor < strlen($this->patch) - 12; + } + + private function handleAction() { + $data = $this->readNumber(); + $command = $data & 3; + $length = ($data >> 2) + 1; + switch ($command) { + case 0: + $this->handleSourceRead($length); + break; + case 1: + $this->handleTargetRead($length); + break; + case 2: + $this->handleSourceCopy($length); + break; + case 3: + $this->handleTargetCopy($length); + break; + } + } + + private function handleSourceRead($length) { + while ($length--) { + $this->target[$this->outputOffset] = $this->source[$this->outputOffset]; + ++$this->outputOffset; + } + } + + private function handleTargetRead($length) { + while ($length--) { + $this->target[$this->outputOffset++] = $this->readByte(); + } + } + + private function handleSourceCopy($length) { + $this->sourceRelativeOffset += $this->readSignedNumber(); + while ($length--) { + $this->target[$this->outputOffset++] = $this->source[$this->sourceRelativeOffset++]; + } + } + + private function handleTargetCopy($length) { + $this->targetRelativeOffset += $this->readSignedNumber(); + while ($length--) { + $this->target[$this->outputOffset++] = $this->target[$this->targetRelativeOffset++]; + } + } + + private function read32() { + $a = ord($this->readByte()); + $b = ord($this->readByte()); + $c = ord($this->readByte()); + $d = ord($this->readByte()); + return $a | ($b << 8) | ($c << 16) | ($d << 24); + } + + private function readByte() { + return $this->patch[$this->patchCursor++]; + } + + private function readNumber() { + $data = 0; + $shift = 1; + for ($i = 0; $i < 16; ++$i) { + $x = ord($this->readByte()); + $data += ($x & 0x7f) * $shift; + if ($x & 0x80) break; + $shift <<= 7; + $data += $shift; + } + return $data; + } + + private function readSignedNumber() { + $data = $this->readNumber(); + return ($data & 1 ? -1 : 1) * ($data >> 1); + } + + private function readString($length) { + $string = substr($this->patch, $this->patchCursor, $length); + $this->patchCursor += $length; + return $string; + } + + + private $source; + private $patch = ''; + private $target = ''; + private $metadata = ''; + + private $patchCursor = 0; + private $outputOffset = 0; + private $sourceRelativeOffset = 0; + private $targetRelativeOffset = 0; + +} diff --git a/app/Beat/Encoder.php b/app/Beat/Encoder.php new file mode 100644 index 0000000..8cbb068 --- /dev/null +++ b/app/Beat/Encoder.php @@ -0,0 +1,167 @@ +source = $source; + } + + public function createPatch($target, $metadata = '') { + $this->target = $target; + $this->patch = ''; + $this->sourceCursor = 0; + $this->targetCursor = 0; + + $this->writeString('BPS1'); + $this->writeNumber(strlen($this->source)); + $this->writeNumber(strlen($this->target)); + $this->writeNumber(strlen($metadata)); + $this->writeString($metadata); + + $lastKnownChange = 0; + $targetCopyPos = 0; + while ($this->targetCursor < strlen($this->target)) { + $numUnchanged = 0; + while ($this->sourceLeft($numUnchanged) && $this->sourceEqual($numUnchanged, $numUnchanged, 1)) { + ++$numUnchanged; + } + if ($numUnchanged > 1 || $numUnchanged == (strlen($this->target) - $this->targetCursor)) { + $this->writeNumber(($numUnchanged - 1) << 2); + $this->sourceCursor += $numUnchanged; + $this->targetCursor += $numUnchanged; + } + + $numChanged = 0; + if ($lastKnownChange > $this->targetCursor) { + $numChanged = $lastKnownChange - $this->targetCursor; + } + while ((!$this->sourceLeft($numChanged) || !$this->sourceEqual($numChanged, $numChanged, 3)) + && $this->targetLeft($numChanged) + ) { + ++$numChanged; + if (!$this->sourceLeft($numChanged)) { + $numChanged = strlen($this->target) - $this->targetCursor; + } + } + $lastKnownChange = $this->targetCursor + $numChanged; + if ($numChanged) { + $rle1Start = $this->targetCursor == 0 ? 1 : 0; + while (true) { + if ($this->targetEqual($rle1Start - 1, $rle1Start, 4) + || $this->targetEqual($rle1Start - 2, $rle1Start, 5) + ) { + $numChanged = $rle1Start; + break; + } + if ($rle1Start + 3 > $numChanged) { + break; + } + ++$rle1Start; + } + if ($numChanged) { + $this->writeNumber(($numChanged - 1) << 2 | 1); + $this->writeString(substr($this->target, $this->targetCursor, $numChanged)); + $this->sourceCursor += $numChanged; + $this->targetCursor += $numChanged; + } + if ($this->targetEqual(-2, 0, 3)) { + $rleLen = 0; + while ($this->targetLeft($rleLen) && $this->targetEqual(0, $rleLen, 2)) { + $rleLen += 2; + } + $this->writeNumber(($rleLen - 1) << 2 | 3); + $this->writeNumber(($this->targetCursor - $targetCopyPos - 2) << 1); + $this->sourceCursor += $rleLen; + $this->targetCursor += $rleLen; + $targetCopyPos = $this->targetCursor - 2; + } else if ($this->targetEqual(-1, 0, 2)) { + $rleLen = 0; + while ($this->targetLeft($rleLen) && $this->targetEqual(0, $rleLen, 1)) { + $rleLen += 1; + } + $this->writeNumber(($rleLen - 1) << 2 | 3); + $this->writeNumber(($this->targetCursor - $targetCopyPos - 1) << 1); + $this->sourceCursor += $rleLen; + $this->targetCursor += $rleLen; + $targetCopyPos = $this->targetCursor - 1; + } + } + } + + $this->write32(crc32($this->source)); + $this->write32(crc32($this->target)); + $this->write32(crc32($this->patch)); + + return $this->patch; + } + + + private function sourceChar($offset = 0) { + return $this->source[$this->sourceCursor + $offset]; + } + + private function sourceEqual($aOff, $bOff, $len) { + $aStr = substr($this->source, $this->sourceCursor + $aOff, $len); + $bStr = substr($this->target, $this->targetCursor + $bOff, $len); + return $aStr == $bStr; + } + + private function sourceLeft($num) { + return $this->sourceCursor + $num < strlen($this->source); + } + + private function targetChar($offset = 0) { + return $this->target[$this->targetCursor + $offset]; + } + + private function targetEqual($aOff, $bOff, $len) { + $aStr = substr($this->target, $this->targetCursor + $aOff, $len); + $bStr = substr($this->target, $this->targetCursor + $bOff, $len); + return $aStr == $bStr; + } + + private function targetLeft($num) { + return $this->targetCursor + $num < strlen($this->target); + } + + + private function write32($val) { + $this->writeByte($val & 0xFF); + $this->writeByte(($val >> 8) & 0xFF); + $this->writeByte(($val >> 16) & 0xFF); + $this->writeByte(($val >> 24) & 0xFF); + } + + private function writeByte($val) { + $this->patch .= chr($val); + } + + private function writeNumber($val) { + $tmpval = $val; + for ($i = 0; $i < 16; ++$i) { + $tmpbyte = $tmpval & 0x7f; + $tmpval >>= 7; + if (!$tmpval) { + $this->writeByte($tmpbyte | 0x80); + break; + } + $this->writeByte($tmpbyte); + --$tmpval; + } + } + + private function writeString($str) { + $this->patch .= $str; + } + + + private $source; + private $target = ''; + private $patch = ''; + + private $sourceCursor = 0; + private $targetCursor = 0; + +} diff --git a/app/Console/Commands/BeatDiffCommand.php b/app/Console/Commands/BeatDiffCommand.php new file mode 100644 index 0000000..cf8f9dd --- /dev/null +++ b/app/Console/Commands/BeatDiffCommand.php @@ -0,0 +1,38 @@ +argument('source')); + $target = file_get_contents($this->argument('target')); + $encoder = new Encoder($source); + $patch = $encoder->createPatch($target); + file_put_contents($this->argument('patch'), $patch); + return 0; + } +} diff --git a/app/Console/Commands/BeatPatchCommand.php b/app/Console/Commands/BeatPatchCommand.php new file mode 100644 index 0000000..12ad968 --- /dev/null +++ b/app/Console/Commands/BeatPatchCommand.php @@ -0,0 +1,38 @@ +argument('source')); + $patch = file_get_contents($this->argument('patch')); + $decoder = new Decoder($source); + $target = $decoder->applyPatch($patch); + file_put_contents($this->argument('target'), $target); + return 0; + } +} -- 2.39.2