2
This code is derived from jgit (http://eclipse.org/jgit).
3
Copyright owners are documented in jgit's IP log.
5
This program and the accompanying materials are made available
6
under the terms of the Eclipse Distribution License v1.0 which
7
accompanies this distribution, is reproduced below, and is
8
available at http://www.eclipse.org/org/documents/edl-v10.php
12
Redistribution and use in source and binary forms, with or
13
without modification, are permitted provided that the following
16
- Redistributions of source code must retain the above copyright
17
notice, this list of conditions and the following disclaimer.
19
- Redistributions in binary form must reproduce the above
20
copyright notice, this list of conditions and the following
21
disclaimer in the documentation and/or other materials provided
22
with the distribution.
24
- Neither the name of the Eclipse Foundation, Inc. nor the
25
names of its contributors may be used to endorse or promote
26
products derived from this software without specific prior
29
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
48
namespace NGit.Storage.Pack
51
/// Encodes an instruction stream for
52
/// <see cref="BinaryDelta">BinaryDelta</see>
55
public class DeltaEncoder
57
/// <summary>Maximum number of bytes to be copied in pack v2 format.</summary>
59
/// Maximum number of bytes to be copied in pack v2 format.
61
/// Historical limitations have this at 64k, even though current delta
62
/// decoders recognize larger copy instructions.
64
private const int MAX_V2_COPY = unchecked((int)(0x10000));
66
/// <summary>Maximum number of bytes used by a copy instruction.</summary>
67
/// <remarks>Maximum number of bytes used by a copy instruction.</remarks>
68
private const int MAX_COPY_CMD_SIZE = 8;
70
/// <summary>Maximum length that an an insert command can encode at once.</summary>
71
/// <remarks>Maximum length that an an insert command can encode at once.</remarks>
72
private const int MAX_INSERT_DATA_SIZE = 127;
74
private readonly OutputStream @out;
76
private readonly byte[] buf = new byte[MAX_COPY_CMD_SIZE * 4];
78
private readonly int limit;
82
/// <summary>Create an encoder with no upper bound on the instruction stream size.</summary>
83
/// <remarks>Create an encoder with no upper bound on the instruction stream size.</remarks>
84
/// <param name="out">buffer to store the instructions written.</param>
85
/// <param name="baseSize">size of the base object, in bytes.</param>
86
/// <param name="resultSize">
87
/// size of the resulting object, after applying this instruction
88
/// stream to the base object, in bytes.
90
/// <exception cref="System.IO.IOException">
91
/// the output buffer cannot store the instruction stream's
92
/// header with the size fields.
94
public DeltaEncoder(OutputStream @out, long baseSize, long resultSize) : this(@out
95
, baseSize, resultSize, 0)
99
/// <summary>Create an encoder with an upper limit on the instruction size.</summary>
100
/// <remarks>Create an encoder with an upper limit on the instruction size.</remarks>
101
/// <param name="out">buffer to store the instructions written.</param>
102
/// <param name="baseSize">size of the base object, in bytes.</param>
103
/// <param name="resultSize">
104
/// size of the resulting object, after applying this instruction
105
/// stream to the base object, in bytes.
107
/// <param name="limit">
108
/// maximum number of bytes to write to the out buffer declaring
109
/// the stream is over limit and should be discarded. May be 0 to
110
/// specify an infinite limit.
112
/// <exception cref="System.IO.IOException">
113
/// the output buffer cannot store the instruction stream's
114
/// header with the size fields.
116
public DeltaEncoder(OutputStream @out, long baseSize, long resultSize, int limit)
118
// private static final int MAX_V3_COPY = (0xff << 16) | (0xff << 8) | 0xff;
121
WriteVarint(baseSize);
122
WriteVarint(resultSize);
125
/// <exception cref="System.IO.IOException"></exception>
126
private void WriteVarint(long sz)
129
while (sz >= unchecked((int)(0x80)))
131
buf[p++] = unchecked((byte)(unchecked((int)(0x80)) | (((int)sz) & unchecked((int)
133
sz = (long)(((ulong)sz) >> 7);
135
buf[p++] = unchecked((byte)(((int)sz) & unchecked((int)(0x7f))));
137
if (limit <= 0 || size < limit)
139
@out.Write(buf, 0, p);
143
/// <returns>current size of the delta stream, in bytes.</returns>
144
public virtual int GetSize()
149
/// <summary>Insert a literal string of text, in UTF-8 encoding.</summary>
150
/// <remarks>Insert a literal string of text, in UTF-8 encoding.</remarks>
151
/// <param name="text">the string to insert.</param>
153
/// true if the insert fits within the limit; false if the insert
154
/// would cause the instruction stream to exceed the limit.
156
/// <exception cref="System.IO.IOException">the instruction buffer can't store the instructions.
158
public virtual bool Insert(string text)
160
return Insert(Constants.Encode(text));
163
/// <summary>Insert a literal binary sequence.</summary>
164
/// <remarks>Insert a literal binary sequence.</remarks>
165
/// <param name="text">the binary to insert.</param>
167
/// true if the insert fits within the limit; false if the insert
168
/// would cause the instruction stream to exceed the limit.
170
/// <exception cref="System.IO.IOException">the instruction buffer can't store the instructions.
172
public virtual bool Insert(byte[] text)
174
return Insert(text, 0, text.Length);
177
/// <summary>Insert a literal binary sequence.</summary>
178
/// <remarks>Insert a literal binary sequence.</remarks>
179
/// <param name="text">the binary to insert.</param>
180
/// <param name="off">
182
/// <code>text</code>
183
/// to start copying from.
185
/// <param name="cnt">number of bytes to insert.</param>
187
/// true if the insert fits within the limit; false if the insert
188
/// would cause the instruction stream to exceed the limit.
190
/// <exception cref="System.IO.IOException">the instruction buffer can't store the instructions.
192
public virtual bool Insert(byte[] text, int off, int cnt)
200
int hdrs = cnt / MAX_INSERT_DATA_SIZE;
201
if (cnt % MAX_INSERT_DATA_SIZE != 0)
205
if (limit < size + hdrs + cnt)
212
int n = Math.Min(MAX_INSERT_DATA_SIZE, cnt);
213
@out.Write(unchecked((byte)n));
214
@out.Write(text, off, n);
223
/// <summary>Create a copy instruction to copy from the base object.</summary>
224
/// <remarks>Create a copy instruction to copy from the base object.</remarks>
225
/// <param name="offset">
226
/// position in the base object to copy from. This is absolute,
227
/// from the beginning of the base.
229
/// <param name="cnt">number of bytes to copy.</param>
231
/// true if the copy fits within the limit; false if the copy
232
/// would cause the instruction stream to exceed the limit.
234
/// <exception cref="System.IO.IOException">the instruction buffer cannot store the instructions.
236
public virtual bool Copy(long offset, int cnt)
243
// We cannot encode more than MAX_V2_COPY bytes in a single
244
// command, so encode that much and start a new command.
245
// This limit is imposed by the pack file format rules.
247
while (MAX_V2_COPY < cnt)
249
p = EncodeCopy(p, offset, MAX_V2_COPY);
250
offset += MAX_V2_COPY;
252
if (buf.Length < p + MAX_COPY_CMD_SIZE)
254
if (0 < limit && limit < size + p)
258
@out.Write(buf, 0, p);
263
p = EncodeCopy(p, offset, cnt);
264
if (0 < limit && limit < size + p)
268
@out.Write(buf, 0, p);
273
private int EncodeCopy(int p, long offset, int cnt)
275
int cmd = unchecked((int)(0x80));
277
// save room for the command
278
if ((offset & unchecked((int)(0xff))) != 0)
280
cmd |= unchecked((int)(0x01));
281
buf[p++] = unchecked((byte)(offset & unchecked((int)(0xff))));
283
if ((offset & (unchecked((int)(0xff)) << 8)) != 0)
285
cmd |= unchecked((int)(0x02));
286
buf[p++] = unchecked((byte)(((long)(((ulong)offset) >> 8)) & unchecked((int)(0xff
289
if ((offset & (unchecked((int)(0xff)) << 16)) != 0)
291
cmd |= unchecked((int)(0x04));
292
buf[p++] = unchecked((byte)(((long)(((ulong)offset) >> 16)) & unchecked((int)(0xff
295
if ((offset & (unchecked((int)(0xff)) << 24)) != 0)
297
cmd |= unchecked((int)(0x08));
298
buf[p++] = unchecked((byte)(((long)(((ulong)offset) >> 24)) & unchecked((int)(0xff
301
if (cnt != MAX_V2_COPY)
303
if ((cnt & unchecked((int)(0xff))) != 0)
305
cmd |= unchecked((int)(0x10));
306
buf[p++] = unchecked((byte)(cnt & unchecked((int)(0xff))));
308
if ((cnt & (unchecked((int)(0xff)) << 8)) != 0)
310
cmd |= unchecked((int)(0x20));
311
buf[p++] = unchecked((byte)(((int)(((uint)cnt) >> 8)) & unchecked((int)(0xff))));
313
if ((cnt & (unchecked((int)(0xff)) << 16)) != 0)
315
cmd |= unchecked((int)(0x40));
316
buf[p++] = unchecked((byte)(((int)(((uint)cnt) >> 16)) & unchecked((int)(0xff))));
319
buf[cmdPtr] = unchecked((byte)cmd);