<?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;
/**
* Most bytes of the two versions compared in one piece while following
* a stretch they share
* @var int
*/
const MAX_COMPARE_LENGTH = 65536;
/**
* 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;
}
/* An edit usually leaves the start and the end of the content as
they were. Those are copied whole, and only the stretch between
is looked through, which is where the time of making a delta
goes. */
$shorter = min($source_length, $target_length);
$start = self::sameLength($source, 0, $target, 0, $shorter);
$end = self::sameLength(strrev($source), 0, strrev($target), 0,
$shorter - $start);
$target_end = $target_length - $end;
$positions = self::indexSource($source, $start,
$source_length - $end);
$delta = self::encodeSize($source_length) .
self::encodeSize($target_length);
if ($start > 0) {
$delta .= self::encodeCopy(0, $start);
}
$pending = "";
$at = $start;
while ($at < $target_end) {
$match = self::longestMatch($source, $target, $at, $target_end,
$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 ($end > 0) {
$delta .= self::encodeCopy($source_length - $end, $end);
}
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
* @param int $from where in the older version to start noting runs
* @param int $to where in the older version to stop noting runs
* @return array run of bytes to the list of positions it sits at
*/
private static function indexSource($source, $from, $to)
{
$positions = [];
$last_start = $to - self::BLOCK_LENGTH;
for ($at = $from; $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 int $target_end where in the newer version a stretch must end
* by
* @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, $target_end,
$positions)
{
$best = ["offset" => 0, "length" => 0];
if ($at + self::BLOCK_LENGTH > $target_end) {
return $best;
}
$block = substr($target, $at, self::BLOCK_LENGTH);
if (!isset($positions[$block])) {
return $best;
}
$source_length = strlen($source);
foreach ($positions[$block] as $offset) {
$length = self::BLOCK_LENGTH + self::sameLength($source,
$offset + self::BLOCK_LENGTH, $target,
$at + self::BLOCK_LENGTH, min($source_length - $offset,
$target_end - $at, self::MAX_COPY_LENGTH) -
self::BLOCK_LENGTH);
if ($length > $best["length"]) {
$best = ["offset" => $offset, "length" => $length];
}
}
return $best;
}
/**
* sameLength counts how many bytes of two strings match from given
* places on.
* Pieces of doubling size are compared at once: the exclusive or of
* two equal pieces is all zero bytes, and strspn counts how many lead
* it. This is many times faster than comparing a byte at a time.
*
* @param string $first one string
* @param int $first_at where in the first string to start
* @param string $second the other string
* @param int $second_at where in the second string to start
* @param int $limit most bytes to count
* @return int how many bytes match, at most $limit
*/
private static function sameLength($first, $first_at, $second,
$second_at, $limit)
{
$length = 0;
$step = self::BLOCK_LENGTH;
while ($length < $limit) {
$step = min($step * 2, self::MAX_COMPARE_LENGTH,
$limit - $length);
$same = strspn(substr($first, $first_at + $length, $step) ^
substr($second, $second_at + $length, $step), "\0");
$length += $same;
if ($same < $step) {
break;
}
}
return $length;
}
/**
* 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);
}
}
- Yioop Repo - Seekquarry