org.spearce.jgit/src/org/spearce/jgit/lib/BinaryDelta.java

   1 /*
   2  * Copyright (C) 2007, Robin Rosenberg <robin.rosenberg@dewire.com>
   3  * Copyright (C) 2007, Shawn O. Pearce <spearce@spearce.org>
   4  *
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or
   8  * without modification, are permitted provided that the following
   9  * conditions are met:
  10  *
  11  * - Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  *
  14  * - Redistributions in binary form must reproduce the above
  15  *   copyright notice, this list of conditions and the following
  16  *   disclaimer in the documentation and/or other materials provided
  17  *   with the distribution.
  18  *
  19  * - Neither the name of the Git Development Community nor the
  20  *   names of its contributors may be used to endorse or promote
  21  *   products derived from this software without specific prior
  22  *   written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  25  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  26  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  27  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  28  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  29  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  31  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  34  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  35  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  36  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  37  */
  38
  39 package org.spearce.jgit.lib;
  40
  41 /**
  42  * Recreate a stream from a base stream and a GIT pack delta.
  43  * <p>
  44  * This entire class is heavily cribbed from <code>patch-delta.c</code> in the
  45  * GIT project. The original delta patching code was written by Nicolas Pitre
  46  * (&lt;nico@cam.org&gt;).
  47  * </p>
  48  */
  49 public class BinaryDelta {
  50
  51         /**
  52          * Apply the changes defined by delta to the data in base, yielding a new
  53          * array of bytes.
  54          *
  55          * @param base
  56          *            some byte representing an object of some kind.
  57          * @param delta
  58          *            a git pack delta defining the transform from one version to
  59          *            another.
  60          * @return patched base
  61          */
  62         public static final byte[] apply(final byte[] base, final byte[] delta) {
  63                 int deltaPtr = 0;
  64
  65                 // Length of the base object (a variable length int).
  66                 //
  67                 int baseLen = 0;
  68                 int c, shift = 0;
  69                 do {
  70                         c = delta[deltaPtr++] & 0xff;
  71                         baseLen |= (c & 0x7f) << shift;
  72                         shift += 7;
  73                 } while ((c & 0x80) != 0);
  74                 if (base.length != baseLen)
  75                         throw new IllegalArgumentException("base length incorrect");
  76
  77                 // Length of the resulting object (a variable length int).
  78                 //
  79                 int resLen = 0;
  80                 shift = 0;
  81                 do {
  82                         c = delta[deltaPtr++] & 0xff;
  83                         resLen |= (c & 0x7f) << shift;
  84                         shift += 7;
  85                 } while ((c & 0x80) != 0);
  86
  87                 final byte[] result = new byte[resLen];
  88                 int resultPtr = 0;
  89                 while (deltaPtr < delta.length) {
  90                         final int cmd = delta[deltaPtr++] & 0xff;
  91                         if ((cmd & 0x80) != 0) {
  92                                 // Determine the segment of the base which should
  93                                 // be copied into the output. The segment is given
  94                                 // as an offset and a length.
  95                                 //
  96                                 int copyOffset = 0;
  97                                 if ((cmd & 0x01) != 0)
  98                                         copyOffset = delta[deltaPtr++] & 0xff;
  99                                 if ((cmd & 0x02) != 0)
 100                                         copyOffset |= (delta[deltaPtr++] & 0xff) << 8;
 101                                 if ((cmd & 0x04) != 0)
 102                                         copyOffset |= (delta[deltaPtr++] & 0xff) << 16;
 103                                 if ((cmd & 0x08) != 0)
 104                                         copyOffset |= (delta[deltaPtr++] & 0xff) << 24;
 105
 106                                 int copySize = 0;
 107                                 if ((cmd & 0x10) != 0)
 108                                         copySize = delta[deltaPtr++] & 0xff;
 109                                 if ((cmd & 0x20) != 0)
 110                                         copySize |= (delta[deltaPtr++] & 0xff) << 8;
 111                                 if ((cmd & 0x40) != 0)
 112                                         copySize |= (delta[deltaPtr++] & 0xff) << 16;
 113                                 if (copySize == 0)
 114                                         copySize = 0x10000;
 115
 116                                 System.arraycopy(base, copyOffset, result, resultPtr, copySize);
 117                                 resultPtr += copySize;
 118                         } else if (cmd != 0) {
 119                                 // Anything else the data is literal within the delta
 120                                 // itself.
 121                                 //
 122                                 System.arraycopy(delta, deltaPtr, result, resultPtr, cmd);
 123                                 deltaPtr += cmd;
 124                                 resultPtr += cmd;
 125                         } else {
 126                                 // cmd == 0 has been reserved for future encoding but
 127                                 // for now its not acceptable.
 128                                 //
 129                                 throw new IllegalArgumentException("unsupported command 0");
 130                         }
 131                 }
 132
 133                 return result;
 134         }
 135 }