<?php
/**
 * SeekQuarry/Yioop --
 * Open Source Pure PHP Search Engine, Crawler, and Indexer
 *
 * Copyright (C) 2009 - 2026  Chris Pollett chris@pollett.org
 *
 * LICENSE:
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * END LICENSE
 *
 * @author Chris Pollett chris@pollett.org
 * @license https://www.gnu.org/licenses/ GPL3
 * @link https://www.seekquarry.com/
 * @copyright 2009 - 2026
 * @filesource
 */
namespace seekquarry\yioop\library\version_control;

/**
 * Writes and reads the small description of how one piece of content
 * differs from another that Git calls a delta.
 *
 * Two versions of the same file usually share nearly all their bytes. A
 * delta says how to rebuild the second from the first as a short list of
 * steps: copy this run of bytes from the first version, then insert these
 * new bytes, and so on. Sending that list instead of the whole file is what
 * keeps a clone or fetch from carrying every version of every file at full
 * size.
 *
 * The wire format is Git's. Each delta opens with the length of the version
 * it is built against and the length of the version it produces, each
 * written seven bits to a byte with the top bit saying another byte
 * follows. After those come the steps: a byte with its top bit set starts a
 * copy, and its remaining bits say which of the four offset bytes and three
 * length bytes were worth writing; any other non-zero byte is a count of
 * literal bytes that follow.
 *
 * @author Chris Pollett
 */
class GitDelta
{
    /**
     * Number of bytes in the runs of content the maker indexes when looking
     * for material shared between two versions. Sixteen is small enough to
     * catch a shared line or two and large enough that chance matches are
     * rare.
     * @var int
     */
    const BLOCK_LENGTH = 16;
    /**
     * Most positions in the older version the maker will remember for any
     * one run of content. A run that repeats throughout a file, a line of
     * spaces say, would otherwise be looked at a great many times for no
     * gain.
     * @var int
     */
    const MAX_BLOCK_POSITIONS = 8;
    /**
     * Largest run of bytes one copy step may carry, being the largest
     * number the format's three length bytes can hold. A longer run is
     * written as several steps.
     * @var int
     */
    const MAX_COPY_LENGTH = 0xFFFFFF;
    /**
     * Most literal bytes one insert step may carry, the count being held in
     * the seven low bits of the step's first byte.
     * @var int
     */
    const MAX_INSERT_LENGTH = 0x7F;
    /**
     * Largest version, in bytes, the maker will work over. Making a delta
     * costs time in proportion to the two versions' lengths, so beyond this
     * the caller is better served by sending the content whole than by
     * holding the server up.
     * @var int
     */
    const MAX_DELTA_INPUT = 8388608;
    /**
     * The top bit of a step's first byte, set to say the step is a copy.
     * @var int
     */
    const COPY_FLAG = 0x80;

    /**
     * Describes how to rebuild one version of some content from another.
     *
     * Runs of bytes the two versions share become copy steps naming where
     * to find them in the older version; bytes that appear only in the
     * newer version are carried literally. Returns nothing when a delta
     * would not be worth it: when either version is too large to work over
     * quickly, or when the description comes out no smaller than the
     * content it describes.
     *
     * @param string $source the older version, which the reader already has
     * @param string $target the newer version to be rebuilt
     * @return string|null the delta, or null to send the content whole
     */
    public static function create($source, $target)
    {
        $source_length = strlen($source);
        $target_length = strlen($target);
        if ($source_length == 0 || $target_length == 0 ||
            $source_length > self::MAX_DELTA_INPUT ||
            $target_length > self::MAX_DELTA_INPUT) {
            return null;
        }
        $positions = self::indexSource($source);
        $delta = self::encodeSize($source_length) .
            self::encodeSize($target_length);
        $pending = "";
        $at = 0;
        while ($at < $target_length) {
            $match = self::longestMatch($source, $target, $at, $positions);
            if ($match["length"] < self::BLOCK_LENGTH) {
                $pending .= $target[$at];
                $at++;
                continue;
            }
            $delta .= self::encodeInsert($pending);
            $pending = "";
            $delta .= self::encodeCopy($match["offset"], $match["length"]);
            $at += $match["length"];
        }
        $delta .= self::encodeInsert($pending);
        if (strlen($delta) >= $target_length) {
            return null;
        }
        return $delta;
    }
    /**
     * Rebuilds a version of some content from the version it was described
     * against and the description of how they differ. The rebuilt content is
     * checked against the length the description declares, and every copy
     * step is checked to lie inside the older version, so a damaged
     * description is refused rather than acted on.
     *
     * @param string $base the older version the delta was built against
     * @param string $delta the delta describing how to rebuild
     * @return string the rebuilt content
     */
    public static function apply($base, $delta)
    {
        $at = 0;
        $total = strlen($delta);
        self::readSize($delta, $at, $total);
        $target_length = self::readSize($delta, $at, $total);
        if ($target_length > GitRepository::MAX_OBJECT_SIZE) {
            throw new \Exception("git_object_too_large");
        }
        $out = "";
        while ($at < $total) {
            $step = ord($delta[$at]);
            $at++;
            if ($step & self::COPY_FLAG) {
                $out .= self::copyRun($base, $delta, $at, $total, $step);
            } else if ($step != 0) {
                if ($at + $step > $total) {
                    throw new \Exception("git_delta_corrupt");
                }
                $out .= substr($delta, $at, $step);
                $at += $step;
            } else {
                throw new \Exception("git_delta_corrupt");
            }
            if (strlen($out) > GitRepository::MAX_OBJECT_SIZE) {
                throw new \Exception("git_object_too_large");
            }
        }
        if (strlen($out) !== $target_length) {
            throw new \Exception("git_delta_corrupt");
        }
        return $out;
    }
    /**
     * Notes where each run of content sits in the older version, so the
     * maker can tell at once whether the newer version repeats it. Runs are
     * taken end to end rather than at every position, which is enough to
     * find a shared stretch since any stretch longer than two runs contains
     * a whole one.
     *
     * @param string $source the older version to note the runs of
     * @return array run of bytes to the list of positions it sits at
     */
    private static function indexSource($source)
    {
        $positions = [];
        $source_length = strlen($source);
        $last_start = $source_length - self::BLOCK_LENGTH;
        for ($at = 0; $at <= $last_start; $at += self::BLOCK_LENGTH) {
            $block = substr($source, $at, self::BLOCK_LENGTH);
            if (!isset($positions[$block])) {
                $positions[$block] = [];
            }
            if (count($positions[$block]) < self::MAX_BLOCK_POSITIONS) {
                $positions[$block][] = $at;
            }
        }
        return $positions;
    }
    /**
     * Finds the longest stretch of the older version that the newer version
     * repeats starting at the given place. Every remembered position of the
     * run beginning there is followed as far as the two agree, and the
     * longest is kept.
     *
     * @param string $source the older version
     * @param string $target the newer version
     * @param int $at where in the newer version to look from
     * @param array $positions runs of the older version and where they sit
     * @return array ["offset" => where the stretch starts in the older
     *      version, "length" => how many bytes agree]
     */
    private static function longestMatch($source, $target, $at, $positions)
    {
        $best = ["offset" => 0, "length" => 0];
        $block = substr($target, $at, self::BLOCK_LENGTH);
        if (strlen($block) < self::BLOCK_LENGTH ||
            !isset($positions[$block])) {
            return $best;
        }
        $source_length = strlen($source);
        $target_length = strlen($target);
        foreach ($positions[$block] as $offset) {
            $length = self::BLOCK_LENGTH;
            while ($offset + $length < $source_length &&
                $at + $length < $target_length &&
                $length < self::MAX_COPY_LENGTH &&
                $source[$offset + $length] === $target[$at + $length]) {
                $length++;
            }
            if ($length > $best["length"]) {
                $best = ["offset" => $offset, "length" => $length];
            }
        }
        return $best;
    }
    /**
     * Writes a length the way the format asks, seven bits to a byte with
     * the top bit set on every byte but the last to say more follow.
     *
     * @param int $size the length to write
     * @return string the written length
     */
    private static function encodeSize($size)
    {
        $out = "";
        do {
            $byte = $size & 0x7F;
            $size = $size >> 7;
            if ($size > 0) {
                $byte |= 0x80;
            }
            $out .= chr($byte);
        } while ($size > 0);
        return $out;
    }
    /**
     * Reads a length written seven bits to a byte.
     *
     * @param string $delta the delta being read
     * @param int &$at read position, advanced past the length
     * @param int $total length of the delta, so a short one is caught
     * @return int the length read
     */
    private static function readSize($delta, &$at, $total)
    {
        $result = 0;
        $shift = 0;
        do {
            if ($at >= $total) {
                throw new \Exception("git_delta_corrupt");
            }
            $byte = ord($delta[$at]);
            $at++;
            $result |= ($byte & 0x7F) << $shift;
            $shift += 7;
        } while ($byte & 0x80);
        return $result;
    }
    /**
     * Writes the steps that carry bytes appearing only in the newer
     * version. One step can carry at most a hundred and twenty-seven bytes,
     * so a longer run becomes several.
     *
     * @param string $bytes the literal bytes to carry
     * @return string the written steps
     */
    private static function encodeInsert($bytes)
    {
        $out = "";
        $total = strlen($bytes);
        for ($at = 0; $at < $total; $at += self::MAX_INSERT_LENGTH) {
            $piece = substr($bytes, $at, self::MAX_INSERT_LENGTH);
            $out .= chr(strlen($piece)) . $piece;
        }
        return $out;
    }
    /**
     * Writes the steps that repeat a stretch of the older version. Only the
     * bytes of the offset and length that are not zero are written, and
     * which were written is recorded in the step's first byte. A stretch too
     * long for one step becomes several.
     *
     * @param int $offset where the stretch starts in the older version
     * @param int $length how many bytes to repeat
     * @return string the written steps
     */
    private static function encodeCopy($offset, $length)
    {
        $out = "";
        while ($length > 0) {
            $piece = min($length, self::MAX_COPY_LENGTH);
            $step = self::COPY_FLAG;
            $body = "";
            $offset_flags = [0x01 => 0, 0x02 => 8, 0x04 => 16, 0x08 => 24];
            foreach ($offset_flags as $flag => $shift) {
                $byte = ($offset >> $shift) & 0xFF;
                if ($byte != 0) {
                    $step |= $flag;
                    $body .= chr($byte);
                }
            }
            $length_flags = [0x10 => 0, 0x20 => 8, 0x40 => 16];
            foreach ($length_flags as $flag => $shift) {
                $byte = ($piece >> $shift) & 0xFF;
                if ($byte != 0) {
                    $step |= $flag;
                    $body .= chr($byte);
                }
            }
            $out .= chr($step) . $body;
            $offset += $piece;
            $length -= $piece;
        }
        return $out;
    }
    /**
     * Carries out one copy step, taking a run of bytes from the older
     * version. A run reaching past the end of that version means the delta
     * is damaged.
     *
     * @param string $base the older version
     * @param string $delta the delta being read
     * @param int &$at read position, advanced past this step
     * @param int $total length of the delta
     * @param int $step the step's first byte, saying which bytes follow
     * @return string the run of bytes copied
     */
    private static function copyRun($base, $delta, &$at, $total, $step)
    {
        $offset = 0;
        $length = 0;
        $offset_flags = [0x01 => 0, 0x02 => 8, 0x04 => 16, 0x08 => 24];
        foreach ($offset_flags as $flag => $shift) {
            if ($step & $flag) {
                if ($at >= $total) {
                    throw new \Exception("git_delta_corrupt");
                }
                $offset |= ord($delta[$at]) << $shift;
                $at++;
            }
        }
        $length_flags = [0x10 => 0, 0x20 => 8, 0x40 => 16];
        foreach ($length_flags as $flag => $shift) {
            if ($step & $flag) {
                if ($at >= $total) {
                    throw new \Exception("git_delta_corrupt");
                }
                $length |= ord($delta[$at]) << $shift;
                $at++;
            }
        }
        if ($length == 0) {
            $length = 0x10000;
        }
        if ($offset + $length > strlen($base)) {
            throw new \Exception("git_delta_corrupt");
        }
        return substr($base, $offset, $length);
    }
}
