beat codec

[alttp.git] / app / Beat / Encoder.php

diff --git a/app/Beat/Encoder.php b/app/Beat/Encoder.php
new file mode 100644 (file)
index 0000000..8cbb068
--- /dev/null
+++ b/app/Beat/Encoder.php
@@ -0,0 +1,167 @@
+<?php
+
+namespace App\Beat;
+
+class Encoder {
+
+       public function __construct($source) {
+               $this->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;
+
+}