1 /*
2 * Copyright (C) 2007, Robin Rosenberg <robin.rosenberg@dewire.com>
3 * Copyright (C) 2006-2007, Shawn O. Pearce <spearce@spearce.org>
4 * and other copyright owners as documented in the project's IP log.
5 *
6 * This program and the accompanying materials are made available
7 * under the terms of the Eclipse Distribution License v1.0 which
8 * accompanies this distribution, is reproduced below, and is
9 * available at http://www.eclipse.org/org/documents/edl-v10.php
10 *
11 * All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or
14 * without modification, are permitted provided that the following
15 * conditions are met:
16 *
17 * - Redistributions of source code must retain the above copyright
18 * notice, this list of conditions and the following disclaimer.
19 *
20 * - Redistributions in binary form must reproduce the above
21 * copyright notice, this list of conditions and the following
22 * disclaimer in the documentation and/or other materials provided
23 * with the distribution.
24 *
25 * - Neither the name of the Eclipse Foundation, Inc. nor the
26 * names of its contributors may be used to endorse or promote
27 * products derived from this software without specific prior
28 * written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
31 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
32 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
33 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
34 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
35 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
36 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
37 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
38 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
39 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
41 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
42 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43 */
44
45 package org.eclipse.jgit.internal.storage.pack;
46
47 import org.eclipse.jgit.internal.JGitText;
48 import org.eclipse.jgit.util.QuotedString;
49 import org.eclipse.jgit.util.RawParseUtils;
50
51 /**
52 * Recreate a stream from a base stream and a GIT pack delta.
53 * <p>
54 * This entire class is heavily cribbed from <code>patch-delta.c</code> in the
55 * GIT project. The original delta patching code was written by Nicolas Pitre
56 * (<nico@cam.org>).
57 * </p>
58 */
59 public class BinaryDelta {
60 /**
61 * Length of the base object in the delta stream.
62 *
63 * @param delta
64 * the delta stream, or at least the header of it.
65 * @return the base object's size.
66 */
67 public static long getBaseSize(byte[] delta) {
68 int p = 0;
69 long baseLen = 0;
70 int c, shift = 0;
71 do {
72 c = delta[p++] & 0xff;
73 baseLen |= ((long) (c & 0x7f)) << shift;
74 shift += 7;
75 } while ((c & 0x80) != 0);
76 return baseLen;
77 }
78
79 /**
80 * Length of the resulting object in the delta stream.
81 *
82 * @param delta
83 * the delta stream, or at least the header of it.
84 * @return the resulting object's size.
85 */
86 public static long getResultSize(byte[] delta) {
87 int p = 0;
88
89 // Skip length of the base object.
90 //
91 int c;
92 do {
93 c = delta[p++] & 0xff;
94 } while ((c & 0x80) != 0);
95
96 long resLen = 0;
97 int shift = 0;
98 do {
99 c = delta[p++] & 0xff;
100 resLen |= ((long) (c & 0x7f)) << shift;
101 shift += 7;
102 } while ((c & 0x80) != 0);
103 return resLen;
104 }
105
106 /**
107 * Apply the changes defined by delta to the data in base, yielding a new
108 * array of bytes.
109 *
110 * @param base
111 * some byte representing an object of some kind.
112 * @param delta
113 * a git pack delta defining the transform from one version to
114 * another.
115 * @return patched base
116 */
117 public static final byte[] apply(byte[] base, byte[] delta) {
118 return apply(base, delta, null);
119 }
120
121 /**
122 * Apply the changes defined by delta to the data in base, yielding a new
123 * array of bytes.
124 *
125 * @param base
126 * some byte representing an object of some kind.
127 * @param delta
128 * a git pack delta defining the transform from one version to
129 * another.
130 * @param result
131 * array to store the result into. If null the result will be
132 * allocated and returned.
133 * @return either {@code result}, or the result array allocated.
134 */
135 public static final byte[] apply(final byte[] base, final byte[] delta,
136 byte[] result) {
137 int deltaPtr = 0;
138
139 // Length of the base object (a variable length int).
140 //
141 int baseLen = 0;
142 int c, shift = 0;
143 do {
144 c = delta[deltaPtr++] & 0xff;
145 baseLen |= ((long) (c & 0x7f)) << shift;
146 shift += 7;
147 } while ((c & 0x80) != 0);
148 if (base.length != baseLen)
149 throw new IllegalArgumentException(
150 JGitText.get().baseLengthIncorrect);
151
152 // Length of the resulting object (a variable length int).
153 //
154 int resLen = 0;
155 shift = 0;
156 do {
157 c = delta[deltaPtr++] & 0xff;
158 resLen |= ((long) (c & 0x7f)) << shift;
159 shift += 7;
160 } while ((c & 0x80) != 0);
161
162 if (result == null)
163 result = new byte[resLen];
164 else if (result.length != resLen)
165 throw new IllegalArgumentException(
166 JGitText.get().resultLengthIncorrect);
167
168 int resultPtr = 0;
169 while (deltaPtr < delta.length) {
170 final int cmd = delta[deltaPtr++] & 0xff;
171 if ((cmd & 0x80) != 0) {
172 // Determine the segment of the base which should
173 // be copied into the output. The segment is given
174 // as an offset and a length.
175 //
176 int copyOffset = 0;
177 if ((cmd & 0x01) != 0)
178 copyOffset = delta[deltaPtr++] & 0xff;
179 if ((cmd & 0x02) != 0)
180 copyOffset |= (delta[deltaPtr++] & 0xff) << 8;
181 if ((cmd & 0x04) != 0)
182 copyOffset |= (delta[deltaPtr++] & 0xff) << 16;
183 if ((cmd & 0x08) != 0)
184 copyOffset |= (delta[deltaPtr++] & 0xff) << 24;
185
186 int copySize = 0;
187 if ((cmd & 0x10) != 0)
188 copySize = delta[deltaPtr++] & 0xff;
189 if ((cmd & 0x20) != 0)
190 copySize |= (delta[deltaPtr++] & 0xff) << 8;
191 if ((cmd & 0x40) != 0)
192 copySize |= (delta[deltaPtr++] & 0xff) << 16;
193 if (copySize == 0)
194 copySize = 0x10000;
195
196 System.arraycopy(base, copyOffset, result, resultPtr, copySize);
197 resultPtr += copySize;
198 } else if (cmd != 0) {
199 // Anything else the data is literal within the delta
200 // itself.
201 //
202 System.arraycopy(delta, deltaPtr, result, resultPtr, cmd);
203 deltaPtr += cmd;
204 resultPtr += cmd;
205 } else {
206 // cmd == 0 has been reserved for future encoding but
207 // for now its not acceptable.
208 //
209 throw new IllegalArgumentException(
210 JGitText.get().unsupportedCommand0);
211 }
212 }
213
214 return result;
215 }
216
217 /**
218 * Format this delta as a human readable string.
219 *
220 * @param delta
221 * the delta instruction sequence to format.
222 * @return the formatted delta.
223 */
224 public static String format(byte[] delta) {
225 return format(delta, true);
226 }
227
228 /**
229 * Format this delta as a human readable string.
230 *
231 * @param delta
232 * the delta instruction sequence to format.
233 * @param includeHeader
234 * true if the header (base size and result size) should be
235 * included in the formatting.
236 * @return the formatted delta.
237 */
238 public static String format(byte[] delta, boolean includeHeader) {
239 StringBuilder r = new StringBuilder();
240 int deltaPtr = 0;
241
242 long baseLen = 0;
243 int c, shift = 0;
244 do {
245 c = delta[deltaPtr++] & 0xff;
246 baseLen |= ((long) (c & 0x7f)) << shift;
247 shift += 7;
248 } while ((c & 0x80) != 0);
249
250 long resLen = 0;
251 shift = 0;
252 do {
253 c = delta[deltaPtr++] & 0xff;
254 resLen |= ((long) (c & 0x7f)) << shift;
255 shift += 7;
256 } while ((c & 0x80) != 0);
257
258 if (includeHeader) {
259 r.append("DELTA( BASE="); //$NON-NLS-1$
260 r.append(baseLen);
261 r.append(" RESULT="); //$NON-NLS-1$
262 r.append(resLen);
263 r.append(" )\n"); //$NON-NLS-1$
264 }
265
266 while (deltaPtr < delta.length) {
267 final int cmd = delta[deltaPtr++] & 0xff;
268 if ((cmd & 0x80) != 0) {
269 // Determine the segment of the base which should
270 // be copied into the output. The segment is given
271 // as an offset and a length.
272 //
273 int copyOffset = 0;
274 if ((cmd & 0x01) != 0)
275 copyOffset = delta[deltaPtr++] & 0xff;
276 if ((cmd & 0x02) != 0)
277 copyOffset |= (delta[deltaPtr++] & 0xff) << 8;
278 if ((cmd & 0x04) != 0)
279 copyOffset |= (delta[deltaPtr++] & 0xff) << 16;
280 if ((cmd & 0x08) != 0)
281 copyOffset |= (delta[deltaPtr++] & 0xff) << 24;
282
283 int copySize = 0;
284 if ((cmd & 0x10) != 0)
285 copySize = delta[deltaPtr++] & 0xff;
286 if ((cmd & 0x20) != 0)
287 copySize |= (delta[deltaPtr++] & 0xff) << 8;
288 if ((cmd & 0x40) != 0)
289 copySize |= (delta[deltaPtr++] & 0xff) << 16;
290 if (copySize == 0)
291 copySize = 0x10000;
292
293 r.append(" COPY ("); //$NON-NLS-1$
294 r.append(copyOffset);
295 r.append(", "); //$NON-NLS-1$
296 r.append(copySize);
297 r.append(")\n"); //$NON-NLS-1$
298 } else if (cmd != 0) {
299 // Anything else the data is literal within the delta
300 // itself.
301 //
302 r.append(" INSERT("); //$NON-NLS-1$
303 r.append(QuotedString.GIT_PATH.quote(RawParseUtils.decode(
304 delta, deltaPtr, deltaPtr + cmd)));
305 r.append(")\n"); //$NON-NLS-1$
306 deltaPtr += cmd;
307 } else {
308 // cmd == 0 has been reserved for future encoding but
309 // for now its not acceptable.
310 //
311 throw new IllegalArgumentException(
312 JGitText.get().unsupportedCommand0);
313 }
314 }
315
316 return r.toString();
317 }
318 }