<?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;

}