<?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;
/**
* 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);
}
}
- Yioop Repo - Seekquarry