BinaryDelta.java

  1. /*
  2.  * Copyright (C) 2007, Robin Rosenberg <robin.rosenberg@dewire.com>
  3.  * Copyright (C) 2006-2007, Shawn O. Pearce <spearce@spearce.org> and others
  4.  *
  5.  * This program and the accompanying materials are made available under the
  6.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  7.  * https://www.eclipse.org/org/documents/edl-v10.php.
  8.  *
  9.  * SPDX-License-Identifier: BSD-3-Clause
  10.  */

  12. package org.eclipse.jgit.internal.storage.pack;

  14. import org.eclipse.jgit.internal.JGitText;
  15. import org.eclipse.jgit.util.QuotedString;
  16. import org.eclipse.jgit.util.RawParseUtils;

  18. /**
  19.  * Recreate a stream from a base stream and a GIT pack delta.
  20.  * <p>
  21.  * This entire class is heavily cribbed from <code>patch-delta.c</code> in the
  22.  * GIT project. The original delta patching code was written by Nicolas Pitre
  23.  * (&lt;nico@cam.org&gt;).
  24.  * </p>
  25.  */
  26. public class BinaryDelta {
  27.     /**
  28.      * Length of the base object in the delta stream.
  29.      *
  30.      * @param delta
  31.      *            the delta stream, or at least the header of it.
  32.      * @return the base object's size.
  33.      */
  34.     public static long getBaseSize(byte[] delta) {
  35.         int p = 0;
  36.         long baseLen = 0;
  37.         int c, shift = 0;
  38.         do {
  39.             c = delta[p++] & 0xff;
  40.             baseLen |= ((long) (c & 0x7f)) << shift;
  41.             shift += 7;
  42.         } while ((c & 0x80) != 0);
  43.         return baseLen;
  44.     }

  46.     /**
  47.      * Length of the resulting object in the delta stream.
  48.      *
  49.      * @param delta
  50.      *            the delta stream, or at least the header of it.
  51.      * @return the resulting object's size.
  52.      */
  53.     public static long getResultSize(byte[] delta) {
  54.         int p = 0;

  56.         // Skip length of the base object.
  57.         //
  58.         int c;
  59.         do {
  60.             c = delta[p++] & 0xff;
  61.         } while ((c & 0x80) != 0);

  63.         long resLen = 0;
  64.         int shift = 0;
  65.         do {
  66.             c = delta[p++] & 0xff;
  67.             resLen |= ((long) (c & 0x7f)) << shift;
  68.             shift += 7;
  69.         } while ((c & 0x80) != 0);
  70.         return resLen;
  71.     }

  73.     /**
  74.      * Apply the changes defined by delta to the data in base, yielding a new
  75.      * array of bytes.
  76.      *
  77.      * @param base
  78.      *            some byte representing an object of some kind.
  79.      * @param delta
  80.      *            a git pack delta defining the transform from one version to
  81.      *            another.
  82.      * @return patched base
  83.      */
  84.     public static final byte[] apply(byte[] base, byte[] delta) {
  85.         return apply(base, delta, null);
  86.     }

  88.     /**
  89.      * Apply the changes defined by delta to the data in base, yielding a new
  90.      * array of bytes.
  91.      *
  92.      * @param base
  93.      *            some byte representing an object of some kind.
  94.      * @param delta
  95.      *            a git pack delta defining the transform from one version to
  96.      *            another.
  97.      * @param result
  98.      *            array to store the result into. If null the result will be
  99.      *            allocated and returned.
  100.      * @return either {@code result}, or the result array allocated.
  101.      */
  102.     public static final byte[] apply(final byte[] base, final byte[] delta,
  103.             byte[] result) {
  104.         int deltaPtr = 0;

  106.         // Length of the base object (a variable length int).
  107.         //
  108.         int baseLen = 0;
  109.         int c, shift = 0;
  110.         do {
  111.             c = delta[deltaPtr++] & 0xff;
  112.             baseLen |= (c & 0x7f) << shift;
  113.             shift += 7;
  114.         } while ((c & 0x80) != 0);
  115.         if (base.length != baseLen)
  116.             throw new IllegalArgumentException(
  117.                     JGitText.get().baseLengthIncorrect);

  119.         // Length of the resulting object (a variable length int).
  120.         //
  121.         int resLen = 0;
  122.         shift = 0;
  123.         do {
  124.             c = delta[deltaPtr++] & 0xff;
  125.             resLen |= (c & 0x7f) << shift;
  126.             shift += 7;
  127.         } while ((c & 0x80) != 0);

  129.         if (result == null)
  130.             result = new byte[resLen];
  131.         else if (result.length != resLen)
  132.             throw new IllegalArgumentException(
  133.                     JGitText.get().resultLengthIncorrect);

  135.         int resultPtr = 0;
  136.         while (deltaPtr < delta.length) {
  137.             final int cmd = delta[deltaPtr++] & 0xff;
  138.             if ((cmd & 0x80) != 0) {
  139.                 // Determine the segment of the base which should
  140.                 // be copied into the output. The segment is given
  141.                 // as an offset and a length.
  142.                 //
  143.                 int copyOffset = 0;
  144.                 if ((cmd & 0x01) != 0)
  145.                     copyOffset = delta[deltaPtr++] & 0xff;
  146.                 if ((cmd & 0x02) != 0)
  147.                     copyOffset |= (delta[deltaPtr++] & 0xff) << 8;
  148.                 if ((cmd & 0x04) != 0)
  149.                     copyOffset |= (delta[deltaPtr++] & 0xff) << 16;
  150.                 if ((cmd & 0x08) != 0)
  151.                     copyOffset |= (delta[deltaPtr++] & 0xff) << 24;

  153.                 int copySize = 0;
  154.                 if ((cmd & 0x10) != 0)
  155.                     copySize = delta[deltaPtr++] & 0xff;
  156.                 if ((cmd & 0x20) != 0)
  157.                     copySize |= (delta[deltaPtr++] & 0xff) << 8;
  158.                 if ((cmd & 0x40) != 0)
  159.                     copySize |= (delta[deltaPtr++] & 0xff) << 16;
  160.                 if (copySize == 0)
  161.                     copySize = 0x10000;

  163.                 System.arraycopy(base, copyOffset, result, resultPtr, copySize);
  164.                 resultPtr += copySize;
  165.             } else if (cmd != 0) {
  166.                 // Anything else the data is literal within the delta
  167.                 // itself.
  168.                 //
  169.                 System.arraycopy(delta, deltaPtr, result, resultPtr, cmd);
  170.                 deltaPtr += cmd;
  171.                 resultPtr += cmd;
  172.             } else {
  173.                 // cmd == 0 has been reserved for future encoding but
  174.                 // for now its not acceptable.
  175.                 //
  176.                 throw new IllegalArgumentException(
  177.                         JGitText.get().unsupportedCommand0);
  178.             }
  179.         }

  181.         return result;
  182.     }

  184.     /**
  185.      * Format this delta as a human readable string.
  186.      *
  187.      * @param delta
  188.      *            the delta instruction sequence to format.
  189.      * @return the formatted delta.
  190.      */
  191.     public static String format(byte[] delta) {
  192.         return format(delta, true);
  193.     }

  195.     /**
  196.      * Format this delta as a human readable string.
  197.      *
  198.      * @param delta
  199.      *            the delta instruction sequence to format.
  200.      * @param includeHeader
  201.      *            true if the header (base size and result size) should be
  202.      *            included in the formatting.
  203.      * @return the formatted delta.
  204.      */
  205.     public static String format(byte[] delta, boolean includeHeader) {
  206.         StringBuilder r = new StringBuilder();
  207.         int deltaPtr = 0;

  209.         long baseLen = 0;
  210.         int c, shift = 0;
  211.         do {
  212.             c = delta[deltaPtr++] & 0xff;
  213.             baseLen |= ((long) (c & 0x7f)) << shift;
  214.             shift += 7;
  215.         } while ((c & 0x80) != 0);

  217.         long resLen = 0;
  218.         shift = 0;
  219.         do {
  220.             c = delta[deltaPtr++] & 0xff;
  221.             resLen |= ((long) (c & 0x7f)) << shift;
  222.             shift += 7;
  223.         } while ((c & 0x80) != 0);

  225.         if (includeHeader) {
  226.             r.append("DELTA( BASE="); //$NON-NLS-1$
  227.             r.append(baseLen);
  228.             r.append(" RESULT="); //$NON-NLS-1$
  229.             r.append(resLen);
  230.             r.append(" )\n"); //$NON-NLS-1$
  231.         }

  233.         while (deltaPtr < delta.length) {
  234.             final int cmd = delta[deltaPtr++] & 0xff;
  235.             if ((cmd & 0x80) != 0) {
  236.                 // Determine the segment of the base which should
  237.                 // be copied into the output. The segment is given
  238.                 // as an offset and a length.
  239.                 //
  240.                 int copyOffset = 0;
  241.                 if ((cmd & 0x01) != 0)
  242.                     copyOffset = delta[deltaPtr++] & 0xff;
  243.                 if ((cmd & 0x02) != 0)
  244.                     copyOffset |= (delta[deltaPtr++] & 0xff) << 8;
  245.                 if ((cmd & 0x04) != 0)
  246.                     copyOffset |= (delta[deltaPtr++] & 0xff) << 16;
  247.                 if ((cmd & 0x08) != 0)
  248.                     copyOffset |= (delta[deltaPtr++] & 0xff) << 24;

  250.                 int copySize = 0;
  251.                 if ((cmd & 0x10) != 0)
  252.                     copySize = delta[deltaPtr++] & 0xff;
  253.                 if ((cmd & 0x20) != 0)
  254.                     copySize |= (delta[deltaPtr++] & 0xff) << 8;
  255.                 if ((cmd & 0x40) != 0)
  256.                     copySize |= (delta[deltaPtr++] & 0xff) << 16;
  257.                 if (copySize == 0)
  258.                     copySize = 0x10000;

  260.                 r.append("  COPY  ("); //$NON-NLS-1$
  261.                 r.append(copyOffset);
  262.                 r.append(", "); //$NON-NLS-1$
  263.                 r.append(copySize);
  264.                 r.append(")\n"); //$NON-NLS-1$
  265.             } else if (cmd != 0) {
  266.                 // Anything else the data is literal within the delta
  267.                 // itself.
  268.                 //
  269.                 r.append("  INSERT("); //$NON-NLS-1$
  270.                 r.append(QuotedString.GIT_PATH.quote(RawParseUtils.decode(
  271.                         delta, deltaPtr, deltaPtr + cmd)));
  272.                 r.append(")\n"); //$NON-NLS-1$
  273.                 deltaPtr += cmd;
  274.             } else {
  275.                 // cmd == 0 has been reserved for future encoding but
  276.                 // for now its not acceptable.
  277.                 //
  278.                 throw new IllegalArgumentException(
  279.                         JGitText.get().unsupportedCommand0);
  280.             }
  281.         }

  283.         return r.toString();
  284.     }
  285. }
Created with JaCoCo 0.8.6.202009150832