← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/monodevelop/oneiric

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit.Storage.Pack/DeltaStream.cs

  • Committer: Bazaar Package Importer
  • Author(s): Jo Shields
  • Date: 2011-06-27 17:03:13 UTC
  • mto: (1.8.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 54.
  • Revision ID: james.westby@ubuntu.com-20110627170313-6cvz3s19x6e9hqe9
Import upstream version 2.5.92+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/NGit/NGit.Storage.Pack/DeltaStream.cs
 
1
/*
 
2
This code is derived from jgit (http://eclipse.org/jgit).
 
3
Copyright owners are documented in jgit's IP log.
 
4
 
 
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
 
9
 
 
10
All rights reserved.
 
11
 
 
12
Redistribution and use in source and binary forms, with or
 
13
without modification, are permitted provided that the following
 
14
conditions are met:
 
15
 
 
16
- Redistributions of source code must retain the above copyright
 
17
  notice, this list of conditions and the following disclaimer.
 
18
 
 
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.
 
23
 
 
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
 
27
  written permission.
 
28
 
 
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.
 
42
*/
 
43
 
 
44
using System;
 
45
using NGit;
 
46
using NGit.Errors;
 
47
using NGit.Util;
 
48
using Sharpen;
 
49
 
 
50
namespace NGit.Storage.Pack
 
51
{
 
52
        /// <summary>Inflates a delta in an incremental way.</summary>
 
53
        /// <remarks>
 
54
        /// Inflates a delta in an incremental way.
 
55
        /// <p>
 
56
        /// Implementations must provide a means to access a stream for the base object.
 
57
        /// This stream may be accessed multiple times, in order to randomly position it
 
58
        /// to match the copy instructions. A
 
59
        /// <code>DeltaStream</code>
 
60
        /// performs an efficient
 
61
        /// skip by only moving through the delta stream, making restarts of stacked
 
62
        /// deltas reasonably efficient.
 
63
        /// </remarks>
 
64
        public abstract class DeltaStream : InputStream
 
65
        {
 
66
                private const int CMD_COPY = 0;
 
67
 
 
68
                private const int CMD_INSERT = 1;
 
69
 
 
70
                private const int CMD_EOF = 2;
 
71
 
 
72
                private readonly InputStream deltaStream;
 
73
 
 
74
                private long baseSize;
 
75
 
 
76
                private long resultSize;
 
77
 
 
78
                private readonly byte[] cmdbuf = new byte[512];
 
79
 
 
80
                private int cmdptr;
 
81
 
 
82
                private int cmdcnt;
 
83
 
 
84
                /// <summary>Stream to read from the base object.</summary>
 
85
                /// <remarks>Stream to read from the base object.</remarks>
 
86
                private InputStream baseStream;
 
87
 
 
88
                /// <summary>
 
89
                /// Current position within
 
90
                /// <see cref="baseStream">baseStream</see>
 
91
                /// .
 
92
                /// </summary>
 
93
                private long baseOffset;
 
94
 
 
95
                private int curcmd;
 
96
 
 
97
                /// <summary>
 
98
                /// If
 
99
                /// <code>curcmd == CMD_COPY</code>
 
100
                /// , position the base has to be at.
 
101
                /// </summary>
 
102
                private long copyOffset;
 
103
 
 
104
                /// <summary>Total number of bytes in this current command.</summary>
 
105
                /// <remarks>Total number of bytes in this current command.</remarks>
 
106
                private int copySize;
 
107
 
 
108
                /// <summary>Construct a delta application stream, reading instructions.</summary>
 
109
                /// <remarks>Construct a delta application stream, reading instructions.</remarks>
 
110
                /// <param name="deltaStream">the stream to read delta instructions from.</param>
 
111
                /// <exception cref="System.IO.IOException">
 
112
                /// the delta instruction stream cannot be read, or is
 
113
                /// inconsistent with the the base object information.
 
114
                /// </exception>
 
115
                public DeltaStream(InputStream deltaStream)
 
116
                {
 
117
                        this.deltaStream = deltaStream;
 
118
                        if (!Fill(cmdbuf.Length))
 
119
                        {
 
120
                                throw new EOFException();
 
121
                        }
 
122
                        // Length of the base object.
 
123
                        //
 
124
                        int c;
 
125
                        int shift = 0;
 
126
                        do
 
127
                        {
 
128
                                c = cmdbuf[cmdptr++] & unchecked((int)(0xff));
 
129
                                baseSize |= (c & unchecked((int)(0x7f))) << shift;
 
130
                                shift += 7;
 
131
                        }
 
132
                        while ((c & unchecked((int)(0x80))) != 0);
 
133
                        // Length of the resulting object.
 
134
                        //
 
135
                        shift = 0;
 
136
                        do
 
137
                        {
 
138
                                c = cmdbuf[cmdptr++] & unchecked((int)(0xff));
 
139
                                resultSize |= (c & unchecked((int)(0x7f))) << shift;
 
140
                                shift += 7;
 
141
                        }
 
142
                        while ((c & unchecked((int)(0x80))) != 0);
 
143
                        curcmd = Next();
 
144
                }
 
145
 
 
146
                /// <summary>Open the base stream.</summary>
 
147
                /// <remarks>
 
148
                /// Open the base stream.
 
149
                /// <p>
 
150
                /// The
 
151
                /// <code>DeltaStream</code>
 
152
                /// may close and reopen the base stream multiple
 
153
                /// times if copy instructions use offsets out of order. This can occur if a
 
154
                /// large block in the file was moved from near the top, to near the bottom.
 
155
                /// In such cases the reopened stream is skipped to the target offset, so
 
156
                /// <code>skip(long)</code>
 
157
                /// should be as efficient as possible.
 
158
                /// </remarks>
 
159
                /// <returns>
 
160
                /// stream to read from the base object. This stream should not be
 
161
                /// buffered (or should be only minimally buffered), and does not
 
162
                /// need to support mark/reset.
 
163
                /// </returns>
 
164
                /// <exception cref="System.IO.IOException">the base object cannot be opened for reading.
 
165
                ///     </exception>
 
166
                protected internal abstract InputStream OpenBase();
 
167
 
 
168
                /// <returns>length of the base object, in bytes.</returns>
 
169
                /// <exception cref="System.IO.IOException">the length of the base cannot be determined.
 
170
                ///     </exception>
 
171
                protected internal abstract long GetBaseSize();
 
172
 
 
173
                /// <returns>total size of this stream, in bytes.</returns>
 
174
                public virtual long GetSize()
 
175
                {
 
176
                        return resultSize;
 
177
                }
 
178
 
 
179
                /// <exception cref="System.IO.IOException"></exception>
 
180
                public override int Read()
 
181
                {
 
182
                        byte[] buf = new byte[1];
 
183
                        int n = Read(buf, 0, 1);
 
184
                        return n == 1 ? buf[0] & unchecked((int)(0xff)) : -1;
 
185
                }
 
186
 
 
187
                /// <exception cref="System.IO.IOException"></exception>
 
188
                public override void Close()
 
189
                {
 
190
                        deltaStream.Close();
 
191
                        if (baseStream != null)
 
192
                        {
 
193
                                baseStream.Close();
 
194
                        }
 
195
                }
 
196
 
 
197
                /// <exception cref="System.IO.IOException"></exception>
 
198
                public override long Skip(long len)
 
199
                {
 
200
                        long act = 0;
 
201
                        while (0 < len)
 
202
                        {
 
203
                                long n = Math.Min(len, copySize);
 
204
                                switch (curcmd)
 
205
                                {
 
206
                                        case CMD_COPY:
 
207
                                        {
 
208
                                                copyOffset += n;
 
209
                                                break;
 
210
                                        }
 
211
 
 
212
                                        case CMD_INSERT:
 
213
                                        {
 
214
                                                cmdptr += (int)n;
 
215
                                                break;
 
216
                                        }
 
217
 
 
218
                                        case CMD_EOF:
 
219
                                        {
 
220
                                                return act;
 
221
                                        }
 
222
 
 
223
                                        default:
 
224
                                        {
 
225
                                                throw new CorruptObjectException(JGitText.Get().unsupportedCommand0);
 
226
                                        }
 
227
                                }
 
228
                                act += n;
 
229
                                len -= n;
 
230
                                copySize -= (int)n;
 
231
                                if (copySize == 0)
 
232
                                {
 
233
                                        curcmd = Next();
 
234
                                }
 
235
                        }
 
236
                        return act;
 
237
                }
 
238
 
 
239
                /// <exception cref="System.IO.IOException"></exception>
 
240
                public override int Read(byte[] buf, int off, int len)
 
241
                {
 
242
                        int act = 0;
 
243
                        while (0 < len)
 
244
                        {
 
245
                                int n = Math.Min(len, copySize);
 
246
                                switch (curcmd)
 
247
                                {
 
248
                                        case CMD_COPY:
 
249
                                        {
 
250
                                                SeekBase();
 
251
                                                n = baseStream.Read(buf, off, n);
 
252
                                                if (n < 0)
 
253
                                                {
 
254
                                                        throw new CorruptObjectException(JGitText.Get().baseLengthIncorrect);
 
255
                                                }
 
256
                                                copyOffset += n;
 
257
                                                baseOffset = copyOffset;
 
258
                                                break;
 
259
                                        }
 
260
 
 
261
                                        case CMD_INSERT:
 
262
                                        {
 
263
                                                System.Array.Copy(cmdbuf, cmdptr, buf, off, n);
 
264
                                                cmdptr += n;
 
265
                                                break;
 
266
                                        }
 
267
 
 
268
                                        case CMD_EOF:
 
269
                                        {
 
270
                                                return 0 < act ? act : -1;
 
271
                                        }
 
272
 
 
273
                                        default:
 
274
                                        {
 
275
                                                throw new CorruptObjectException(JGitText.Get().unsupportedCommand0);
 
276
                                        }
 
277
                                }
 
278
                                act += n;
 
279
                                off += n;
 
280
                                len -= n;
 
281
                                copySize -= n;
 
282
                                if (copySize == 0)
 
283
                                {
 
284
                                        curcmd = Next();
 
285
                                }
 
286
                        }
 
287
                        return act;
 
288
                }
 
289
 
 
290
                /// <exception cref="System.IO.IOException"></exception>
 
291
                private bool Fill(int need)
 
292
                {
 
293
                        int n = Have();
 
294
                        if (need < n)
 
295
                        {
 
296
                                return true;
 
297
                        }
 
298
                        if (n == 0)
 
299
                        {
 
300
                                cmdptr = 0;
 
301
                                cmdcnt = 0;
 
302
                        }
 
303
                        else
 
304
                        {
 
305
                                if (cmdbuf.Length - cmdptr < need)
 
306
                                {
 
307
                                        // There isn't room for the entire worst-case copy command,
 
308
                                        // so shift the array down to make sure we can use the entire
 
309
                                        // command without having it span across the end of the array.
 
310
                                        //
 
311
                                        System.Array.Copy(cmdbuf, cmdptr, cmdbuf, 0, n);
 
312
                                        cmdptr = 0;
 
313
                                        cmdcnt = n;
 
314
                                }
 
315
                        }
 
316
                        do
 
317
                        {
 
318
                                n = deltaStream.Read(cmdbuf, cmdcnt, cmdbuf.Length - cmdcnt);
 
319
                                if (n < 0)
 
320
                                {
 
321
                                        return 0 < Have();
 
322
                                }
 
323
                                cmdcnt += n;
 
324
                        }
 
325
                        while (cmdcnt < cmdbuf.Length);
 
326
                        return true;
 
327
                }
 
328
 
 
329
                /// <exception cref="System.IO.IOException"></exception>
 
330
                private int Next()
 
331
                {
 
332
                        if (!Fill(8))
 
333
                        {
 
334
                                return CMD_EOF;
 
335
                        }
 
336
                        int cmd = cmdbuf[cmdptr++] & unchecked((int)(0xff));
 
337
                        if ((cmd & unchecked((int)(0x80))) != 0)
 
338
                        {
 
339
                                // Determine the segment of the base which should
 
340
                                // be copied into the output. The segment is given
 
341
                                // as an offset and a length.
 
342
                                //
 
343
                                copyOffset = 0;
 
344
                                if ((cmd & unchecked((int)(0x01))) != 0)
 
345
                                {
 
346
                                        copyOffset = cmdbuf[cmdptr++] & unchecked((int)(0xff));
 
347
                                }
 
348
                                if ((cmd & unchecked((int)(0x02))) != 0)
 
349
                                {
 
350
                                        copyOffset |= (cmdbuf[cmdptr++] & unchecked((int)(0xff))) << 8;
 
351
                                }
 
352
                                if ((cmd & unchecked((int)(0x04))) != 0)
 
353
                                {
 
354
                                        copyOffset |= (cmdbuf[cmdptr++] & unchecked((int)(0xff))) << 16;
 
355
                                }
 
356
                                if ((cmd & unchecked((int)(0x08))) != 0)
 
357
                                {
 
358
                                        copyOffset |= (cmdbuf[cmdptr++] & unchecked((int)(0xff))) << 24;
 
359
                                }
 
360
                                copySize = 0;
 
361
                                if ((cmd & unchecked((int)(0x10))) != 0)
 
362
                                {
 
363
                                        copySize = cmdbuf[cmdptr++] & unchecked((int)(0xff));
 
364
                                }
 
365
                                if ((cmd & unchecked((int)(0x20))) != 0)
 
366
                                {
 
367
                                        copySize |= (cmdbuf[cmdptr++] & unchecked((int)(0xff))) << 8;
 
368
                                }
 
369
                                if ((cmd & unchecked((int)(0x40))) != 0)
 
370
                                {
 
371
                                        copySize |= (cmdbuf[cmdptr++] & unchecked((int)(0xff))) << 16;
 
372
                                }
 
373
                                if (copySize == 0)
 
374
                                {
 
375
                                        copySize = unchecked((int)(0x10000));
 
376
                                }
 
377
                                return CMD_COPY;
 
378
                        }
 
379
                        else
 
380
                        {
 
381
                                if (cmd != 0)
 
382
                                {
 
383
                                        // Anything else the data is literal within the delta
 
384
                                        // itself. Page the entire thing into the cmdbuf, if
 
385
                                        // its not already there.
 
386
                                        //
 
387
                                        Fill(cmd);
 
388
                                        copySize = cmd;
 
389
                                        return CMD_INSERT;
 
390
                                }
 
391
                                else
 
392
                                {
 
393
                                        // cmd == 0 has been reserved for future encoding but
 
394
                                        // for now its not acceptable.
 
395
                                        //
 
396
                                        throw new CorruptObjectException(JGitText.Get().unsupportedCommand0);
 
397
                                }
 
398
                        }
 
399
                }
 
400
 
 
401
                private int Have()
 
402
                {
 
403
                        return cmdcnt - cmdptr;
 
404
                }
 
405
 
 
406
                /// <exception cref="System.IO.IOException"></exception>
 
407
                private void SeekBase()
 
408
                {
 
409
                        if (baseStream == null)
 
410
                        {
 
411
                                baseStream = OpenBase();
 
412
                                if (GetBaseSize() != baseSize)
 
413
                                {
 
414
                                        throw new CorruptObjectException(JGitText.Get().baseLengthIncorrect);
 
415
                                }
 
416
                                IOUtil.SkipFully(baseStream, copyOffset);
 
417
                                baseOffset = copyOffset;
 
418
                        }
 
419
                        else
 
420
                        {
 
421
                                if (baseOffset < copyOffset)
 
422
                                {
 
423
                                        IOUtil.SkipFully(baseStream, copyOffset - baseOffset);
 
424
                                        baseOffset = copyOffset;
 
425
                                }
 
426
                                else
 
427
                                {
 
428
                                        if (baseOffset > copyOffset)
 
429
                                        {
 
430
                                                baseStream.Close();
 
431
                                                baseStream = OpenBase();
 
432
                                                IOUtil.SkipFully(baseStream, copyOffset);
 
433
                                                baseOffset = copyOffset;
 
434
                                        }
 
435
                                }
 
436
                        }
 
437
                }
 
438
        }
 
439
}