X-Git-Url: https://git.localhorst.tv/?a=blobdiff_plain;f=app%2FBeat%2FEncoder.php;fp=app%2FBeat%2FEncoder.php;h=8cbb0682488e64516d985148f7ca23834106fb31;hb=35cf09cd6ca9d5f8710ceb1e4f45dbafdbb57bec;hp=0000000000000000000000000000000000000000;hpb=bb02db955fe6dbc905414d479bbe2d38d41fef63;p=alttp.git

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 @@
+<?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;
+
+}