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.
44
using NGit.Storage.Pack;
47
namespace NGit.Storage.Pack
49
/// <summary>Index of blocks in a source file.</summary>
51
/// Index of blocks in a source file.
53
/// The index can be passed a result buffer, and output an instruction sequence
54
/// that transforms the source buffer used by the index into the result buffer.
55
/// The instruction sequence can be executed by
56
/// <see cref="BinaryDelta">BinaryDelta</see>
58
/// <see cref="DeltaStream">DeltaStream</see>
59
/// to recreate the result buffer.
61
/// An index stores the entire contents of the source buffer, but also a table of
62
/// block identities mapped to locations where the block appears in the source
63
/// buffer. The mapping table uses 12 bytes for every 16 bytes of source buffer,
64
/// and is therefore ~75% of the source buffer size. The overall index is ~1.75x
65
/// the size of the source buffer. This relationship holds for any JVM, as only a
66
/// constant number of objects are allocated per index. Callers can use the
68
/// <see cref="GetIndexSize()">GetIndexSize()</see>
69
/// to obtain a reasonably accurate estimate of
70
/// the complete heap space used by this index.
73
/// <code>DeltaIndex</code>
74
/// is thread-safe. Concurrent threads can use the same
75
/// index to encode delta instructions for different result buffers.
77
public class DeltaIndex
79
/// <summary>Number of bytes in a block.</summary>
80
/// <remarks>Number of bytes in a block.</remarks>
81
internal const int BLKSZ = 16;
83
// must be 16, see unrolled loop in hashBlock
84
/// <summary>Estimate the size of an index for a given source.</summary>
86
/// Estimate the size of an index for a given source.
88
/// This is roughly a worst-case estimate. The actual index may be smaller.
90
/// <param name="sourceLength">length of the source, in bytes.</param>
92
/// estimated size. Approximately
93
/// <code>1.75 * sourceLength</code>
96
public static long EstimateIndexSize(int sourceLength)
98
return sourceLength + (sourceLength * 3 / 4);
101
/// <summary>Maximum number of positions to consider for a given content hash.</summary>
103
/// Maximum number of positions to consider for a given content hash.
105
/// All positions with the same content hash are stored into a single chain.
106
/// The chain size is capped to ensure delta encoding stays linear time at
107
/// O(len_src + len_dst) rather than quadratic at O(len_src * len_dst).
109
private const int MAX_CHAIN_LENGTH = 64;
111
/// <summary>Original source file that we indexed.</summary>
112
/// <remarks>Original source file that we indexed.</remarks>
113
private readonly byte[] src;
116
/// Pointers into the
117
/// <see cref="entries">entries</see>
118
/// table, indexed by block hash.
120
/// A block hash is masked with
121
/// <see cref="tableMask">tableMask</see>
122
/// to become the array index
123
/// of this table. The value stored here is the first index within
124
/// <see cref="entries">entries</see>
125
/// that starts the consecutive list of blocks with that
126
/// same masked hash. If there are no matching blocks, 0 is stored instead.
128
/// Note that this table is always a power of 2 in size, to support fast
129
/// normalization of a block hash into an array index.
131
private readonly int[] table;
134
/// Pairs of block hash value and
135
/// <see cref="src">src</see>
138
/// The very first entry in this table at index 0 is always empty, this is to
139
/// allow fast evaluation when
140
/// <see cref="table">table</see>
141
/// has no values under any given
142
/// slot. Remaining entries are pairs of integers, with the upper 32 bits
143
/// holding the block hash and the lower 32 bits holding the source offset.
145
private readonly long[] entries;
148
/// Mask to make block hashes into an array index for
149
/// <see cref="table">table</see>
152
private readonly int tableMask;
154
/// <summary>Construct an index from the source file.</summary>
155
/// <remarks>Construct an index from the source file.</remarks>
156
/// <param name="sourceBuffer">
157
/// the source file's raw contents. The buffer will be held by the
158
/// index instance to facilitate matching, and therefore must not
159
/// be modified by the caller.
161
public DeltaIndex(byte[] sourceBuffer)
164
DeltaIndexScanner scan = new DeltaIndexScanner(src, src.Length);
165
// Reuse the same table the scanner made. We will replace the
166
// values at each position, but we want the same-length array.
169
tableMask = scan.tableMask;
170
// Because entry index 0 means there are no entries for the
171
// slot in the table, we have to allocate one extra position.
173
entries = new long[1 + CountEntries(scan)];
177
private int CountEntries(DeltaIndexScanner scan)
179
// Figure out exactly how many entries we need. As we do the
180
// enumeration truncate any delta chains longer than what we
181
// are willing to scan during encode. This keeps the encode
182
// logic linear in the size of the input rather than quadratic.
185
for (int i = 0; i < table.Length; i++)
195
if (++len == MAX_CHAIN_LENGTH)
208
private void CopyEntries(DeltaIndexScanner scan)
210
// Rebuild the entries list from the scanner, positioning all
211
// blocks in the same hash chain next to each other. We can
212
// then later discard the next list, along with the scanner.
215
for (int i = 0; i < table.Length; i++)
225
entries[next++] = scan.entries[h];
232
/// <returns>size of the source buffer this index has scanned.</returns>
233
public virtual long GetSourceSize()
238
/// <summary>Get an estimate of the memory required by this index.</summary>
239
/// <remarks>Get an estimate of the memory required by this index.</remarks>
241
/// an approximation of the number of bytes used by this index in
242
/// memory. The size includes the cached source buffer size from
243
/// <see cref="GetSourceSize()">GetSourceSize()</see>
244
/// , as well as a rough approximation of JVM
245
/// object overheads.
247
public virtual long GetIndexSize()
253
sz += SizeOf(entries);
257
private static long SizeOf(byte[] b)
259
return SizeOfArray(1, b.Length);
262
private static long SizeOf(int[] b)
264
return SizeOfArray(4, b.Length);
267
private static long SizeOf(long[] b)
269
return SizeOfArray(8, b.Length);
272
private static int SizeOfArray(int entSize, int len)
274
return 12 + (len * entSize);
277
/// <summary>Generate a delta sequence to recreate the result buffer.</summary>
279
/// Generate a delta sequence to recreate the result buffer.
281
/// There is no limit on the size of the delta sequence created. This is the
283
/// <code>encode(out, res, 0)</code>
286
/// <param name="out">
287
/// stream to receive the delta instructions that can transform
288
/// this index's source buffer into
291
/// should be buffered, as instructions are written directly to it
294
/// <param name="res">
295
/// the desired result buffer. The generated instructions will
296
/// recreate this buffer when applied to the source buffer stored
297
/// within this index.
299
/// <exception cref="System.IO.IOException">the output stream refused to write the instructions.
301
public virtual void Encode(OutputStream @out, byte[] res)
303
Encode(@out, res, 0);
306
/// <summary>Generate a delta sequence to recreate the result buffer.</summary>
307
/// <remarks>Generate a delta sequence to recreate the result buffer.</remarks>
308
/// <param name="out">
309
/// stream to receive the delta instructions that can transform
310
/// this index's source buffer into
313
/// should be buffered, as instructions are written directly to it
314
/// in small bursts. If the caller might need to discard the
315
/// instructions (such as when deltaSizeLimit would be exceeded)
316
/// the caller is responsible for discarding or rewinding the
317
/// stream when this method returns false.
319
/// <param name="res">
320
/// the desired result buffer. The generated instructions will
321
/// recreate this buffer when applied to the source buffer stored
322
/// within this index.
324
/// <param name="deltaSizeLimit">
325
/// maximum number of bytes that the delta instructions can
326
/// occupy. If the generated instructions would be longer than
327
/// this amount, this method returns false. If 0, there is no
328
/// limit on the length of delta created.
331
/// true if the delta is smaller than deltaSizeLimit; false if the
332
/// encoder aborted because the encoded delta instructions would be
333
/// longer than deltaSizeLimit bytes.
335
/// <exception cref="System.IO.IOException">the output stream refused to write the instructions.
337
public virtual bool Encode(OutputStream @out, byte[] res, int deltaSizeLimit)
339
int end = res.Length;
340
DeltaEncoder enc = NewEncoder(@out, end, deltaSizeLimit);
341
// If either input is smaller than one full block, we simply punt
342
// and construct a delta as a literal. This implies that any file
343
// smaller than our block size is never delta encoded as the delta
344
// will always be larger than the file itself would be.
346
if (end < BLKSZ || table.Length == 0)
348
return enc.Insert(res);
350
// Bootstrap the scan by constructing a hash for the first block
355
int hash = HashBlock(res, 0);
359
int tableIdx = hash & tableMask;
360
int entryIdx = table[tableIdx];
363
// No matching blocks, slide forward one byte.
365
hash = Step(hash, res[blkPtr++], res[blkEnd++]);
368
// For every possible location of the current block, try to
369
// extend the match out to the longest common substring.
376
long ent = entries[entryIdx++];
377
if (KeyOf(ent) == hash)
382
// If we need to do an insertion, check to see if
383
// moving the starting point of the copy backwards
384
// will allow us to shorten the insert. Our hash
385
// may not have allowed us to identify this area.
386
// Since it is quite fast to perform a negative
387
// scan, try to stretch backwards too.
389
neg = blkPtr - resPtr;
390
neg = Negmatch(res, blkPtr, src, ValOf(ent), neg);
392
int len = neg + Fwdmatch(res, blkPtr, src, ValOf(ent));
396
bestPtr = ValOf(ent);
402
if ((KeyOf(ent) & tableMask) != tableIdx)
408
while (bestLen < 4096 && entryIdx < entries.Length);
411
// All of the locations were false positives, or the copy
412
// is shorter than a block. In the latter case this won't
413
// give us a very great copy instruction, so delay and try
416
hash = Step(hash, res[blkPtr++], res[blkEnd++]);
422
// There are bytes between the last instruction we made
423
// and the current block pointer. None of these matched
424
// during the earlier iteration so insert them directly
425
// into the instruction stream.
427
int cnt = blkPtr - resPtr;
428
if (!enc.Insert(res, resPtr, cnt))
433
if (!enc.Copy(bestPtr - bestNeg, bestLen))
439
blkEnd = blkPtr + BLKSZ;
440
// If we don't have a full block available to us, abort now.
446
// Start a new hash of the block after the copy region.
448
hash = HashBlock(res, blkPtr);
452
// There were bytes at the end which didn't match, or maybe
453
// didn't make a full block. Insert whatever is left over.
455
int cnt = end - resPtr;
456
return enc.Insert(res, resPtr, cnt);
461
/// <exception cref="System.IO.IOException"></exception>
462
private DeltaEncoder NewEncoder(OutputStream @out, long resSize, int limit)
464
return new DeltaEncoder(@out, GetSourceSize(), resSize, limit);
467
private static int Fwdmatch(byte[] res, int resPtr, byte[] src, int srcPtr)
470
for (; resPtr < res.Length && srcPtr < src.Length; resPtr++, srcPtr++)
472
if (res[resPtr] != src[srcPtr])
477
return resPtr - start;
480
private static int Negmatch(byte[] res, int resPtr, byte[] src, int srcPtr, int limit
492
if (res[resPtr] != src[srcPtr])
499
while (0 <= srcPtr && 0 < --limit);
500
return start - resPtr;
503
public override string ToString()
505
string[] units = new string[] { "bytes", "KiB", "MiB", "GiB" };
506
long sz = GetIndexSize();
508
while (1024 <= sz && u < units.Length - 1)
510
int rem = (int)(sz % 1024);
518
return "DeltaIndex[" + sz + " " + units[u] + "]";
521
internal static int HashBlock(byte[] raw, int ptr)
524
// The first 4 steps collapse out into a 4 byte big-endian decode,
525
// with a larger right shift as we combined shift lefts together.
527
hash = ((raw[ptr] & unchecked((int)(0xff))) << 24) | ((raw[ptr + 1] & unchecked((
528
int)(0xff))) << 16) | ((raw[ptr + 2] & unchecked((int)(0xff))) << 8) | (raw[ptr
529
+ 3] & unchecked((int)(0xff)));
533
hash ^= T[(int)(((uint)hash) >> 31)];
534
hash = ((hash << 8) | (raw[ptr + 4] & unchecked((int)(0xff)))) ^ T[(int)(((uint)hash
536
hash = ((hash << 8) | (raw[ptr + 5] & unchecked((int)(0xff)))) ^ T[(int)(((uint)hash
538
hash = ((hash << 8) | (raw[ptr + 6] & unchecked((int)(0xff)))) ^ T[(int)(((uint)hash
540
hash = ((hash << 8) | (raw[ptr + 7] & unchecked((int)(0xff)))) ^ T[(int)(((uint)hash
542
hash = ((hash << 8) | (raw[ptr + 8] & unchecked((int)(0xff)))) ^ T[(int)(((uint)hash
544
hash = ((hash << 8) | (raw[ptr + 9] & unchecked((int)(0xff)))) ^ T[(int)(((uint)hash
546
hash = ((hash << 8) | (raw[ptr + 10] & unchecked((int)(0xff)))) ^ T[(int)(((uint)
548
hash = ((hash << 8) | (raw[ptr + 11] & unchecked((int)(0xff)))) ^ T[(int)(((uint)
550
hash = ((hash << 8) | (raw[ptr + 12] & unchecked((int)(0xff)))) ^ T[(int)(((uint)
552
hash = ((hash << 8) | (raw[ptr + 13] & unchecked((int)(0xff)))) ^ T[(int)(((uint)
554
hash = ((hash << 8) | (raw[ptr + 14] & unchecked((int)(0xff)))) ^ T[(int)(((uint)
556
hash = ((hash << 8) | (raw[ptr + 15] & unchecked((int)(0xff)))) ^ T[(int)(((uint)
561
private static int Step(int hash, byte toRemove, byte toAdd)
563
hash ^= U[toRemove & unchecked((int)(0xff))];
564
return ((hash << 8) | (toAdd & unchecked((int)(0xff)))) ^ T[(int)(((uint)hash) >>
568
private static int KeyOf(long ent)
570
return (int)((long)(((ulong)ent) >> 32));
573
private static int ValOf(long ent)
578
private static readonly int[] T = new int[] { unchecked((int)(0x00000000)), unchecked(
579
(int)(0xd4c6b32d)), unchecked((int)(0x7d4bd577)), unchecked((int)(0xa98d665a)),
580
unchecked((int)(0x2e5119c3)), unchecked((int)(0xfa97aaee)), unchecked((int)(0x531accb4
581
)), unchecked((int)(0x87dc7f99)), unchecked((int)(0x5ca23386)), unchecked((int)(
582
0x886480ab)), unchecked((int)(0x21e9e6f1)), unchecked((int)(0xf52f55dc)), unchecked(
583
(int)(0x72f32a45)), unchecked((int)(0xa6359968)), unchecked((int)(0x0fb8ff32)),
584
unchecked((int)(0xdb7e4c1f)), unchecked((int)(0x6d82d421)), unchecked((int)(0xb944670c
585
)), unchecked((int)(0x10c90156)), unchecked((int)(0xc40fb27b)), unchecked((int)(
586
0x43d3cde2)), unchecked((int)(0x97157ecf)), unchecked((int)(0x3e981895)), unchecked(
587
(int)(0xea5eabb8)), unchecked((int)(0x3120e7a7)), unchecked((int)(0xe5e6548a)),
588
unchecked((int)(0x4c6b32d0)), unchecked((int)(0x98ad81fd)), unchecked((int)(0x1f71fe64
589
)), unchecked((int)(0xcbb74d49)), unchecked((int)(0x623a2b13)), unchecked((int)(
590
0xb6fc983e)), unchecked((int)(0x0fc31b6f)), unchecked((int)(0xdb05a842)), unchecked(
591
(int)(0x7288ce18)), unchecked((int)(0xa64e7d35)), unchecked((int)(0x219202ac)),
592
unchecked((int)(0xf554b181)), unchecked((int)(0x5cd9d7db)), unchecked((int)(0x881f64f6
593
)), unchecked((int)(0x536128e9)), unchecked((int)(0x87a79bc4)), unchecked((int)(
594
0x2e2afd9e)), unchecked((int)(0xfaec4eb3)), unchecked((int)(0x7d30312a)), unchecked(
595
(int)(0xa9f68207)), unchecked((int)(0x007be45d)), unchecked((int)(0xd4bd5770)),
596
unchecked((int)(0x6241cf4e)), unchecked((int)(0xb6877c63)), unchecked((int)(0x1f0a1a39
597
)), unchecked((int)(0xcbcca914)), unchecked((int)(0x4c10d68d)), unchecked((int)(
598
0x98d665a0)), unchecked((int)(0x315b03fa)), unchecked((int)(0xe59db0d7)), unchecked(
599
(int)(0x3ee3fcc8)), unchecked((int)(0xea254fe5)), unchecked((int)(0x43a829bf)),
600
unchecked((int)(0x976e9a92)), unchecked((int)(0x10b2e50b)), unchecked((int)(0xc4745626
601
)), unchecked((int)(0x6df9307c)), unchecked((int)(0xb93f8351)), unchecked((int)(
602
0x1f8636de)), unchecked((int)(0xcb4085f3)), unchecked((int)(0x62cde3a9)), unchecked(
603
(int)(0xb60b5084)), unchecked((int)(0x31d72f1d)), unchecked((int)(0xe5119c30)),
604
unchecked((int)(0x4c9cfa6a)), unchecked((int)(0x985a4947)), unchecked((int)(0x43240558
605
)), unchecked((int)(0x97e2b675)), unchecked((int)(0x3e6fd02f)), unchecked((int)(
606
0xeaa96302)), unchecked((int)(0x6d751c9b)), unchecked((int)(0xb9b3afb6)), unchecked(
607
(int)(0x103ec9ec)), unchecked((int)(0xc4f87ac1)), unchecked((int)(0x7204e2ff)),
608
unchecked((int)(0xa6c251d2)), unchecked((int)(0x0f4f3788)), unchecked((int)(0xdb8984a5
609
)), unchecked((int)(0x5c55fb3c)), unchecked((int)(0x88934811)), unchecked((int)(
610
0x211e2e4b)), unchecked((int)(0xf5d89d66)), unchecked((int)(0x2ea6d179)), unchecked(
611
(int)(0xfa606254)), unchecked((int)(0x53ed040e)), unchecked((int)(0x872bb723)),
612
unchecked((int)(0x00f7c8ba)), unchecked((int)(0xd4317b97)), unchecked((int)(0x7dbc1dcd
613
)), unchecked((int)(0xa97aaee0)), unchecked((int)(0x10452db1)), unchecked((int)(
614
0xc4839e9c)), unchecked((int)(0x6d0ef8c6)), unchecked((int)(0xb9c84beb)), unchecked(
615
(int)(0x3e143472)), unchecked((int)(0xead2875f)), unchecked((int)(0x435fe105)),
616
unchecked((int)(0x97995228)), unchecked((int)(0x4ce71e37)), unchecked((int)(0x9821ad1a
617
)), unchecked((int)(0x31accb40)), unchecked((int)(0xe56a786d)), unchecked((int)(
618
0x62b607f4)), unchecked((int)(0xb670b4d9)), unchecked((int)(0x1ffdd283)), unchecked(
619
(int)(0xcb3b61ae)), unchecked((int)(0x7dc7f990)), unchecked((int)(0xa9014abd)),
620
unchecked((int)(0x008c2ce7)), unchecked((int)(0xd44a9fca)), unchecked((int)(0x5396e053
621
)), unchecked((int)(0x8750537e)), unchecked((int)(0x2edd3524)), unchecked((int)(
622
0xfa1b8609)), unchecked((int)(0x2165ca16)), unchecked((int)(0xf5a3793b)), unchecked(
623
(int)(0x5c2e1f61)), unchecked((int)(0x88e8ac4c)), unchecked((int)(0x0f34d3d5)),
624
unchecked((int)(0xdbf260f8)), unchecked((int)(0x727f06a2)), unchecked((int)(0xa6b9b58f
625
)), unchecked((int)(0x3f0c6dbc)), unchecked((int)(0xebcade91)), unchecked((int)(
626
0x4247b8cb)), unchecked((int)(0x96810be6)), unchecked((int)(0x115d747f)), unchecked(
627
(int)(0xc59bc752)), unchecked((int)(0x6c16a108)), unchecked((int)(0xb8d01225)),
628
unchecked((int)(0x63ae5e3a)), unchecked((int)(0xb768ed17)), unchecked((int)(0x1ee58b4d
629
)), unchecked((int)(0xca233860)), unchecked((int)(0x4dff47f9)), unchecked((int)(
630
0x9939f4d4)), unchecked((int)(0x30b4928e)), unchecked((int)(0xe47221a3)), unchecked(
631
(int)(0x528eb99d)), unchecked((int)(0x86480ab0)), unchecked((int)(0x2fc56cea)),
632
unchecked((int)(0xfb03dfc7)), unchecked((int)(0x7cdfa05e)), unchecked((int)(0xa8191373
633
)), unchecked((int)(0x01947529)), unchecked((int)(0xd552c604)), unchecked((int)(
634
0x0e2c8a1b)), unchecked((int)(0xdaea3936)), unchecked((int)(0x73675f6c)), unchecked(
635
(int)(0xa7a1ec41)), unchecked((int)(0x207d93d8)), unchecked((int)(0xf4bb20f5)),
636
unchecked((int)(0x5d3646af)), unchecked((int)(0x89f0f582)), unchecked((int)(0x30cf76d3
637
)), unchecked((int)(0xe409c5fe)), unchecked((int)(0x4d84a3a4)), unchecked((int)(
638
0x99421089)), unchecked((int)(0x1e9e6f10)), unchecked((int)(0xca58dc3d)), unchecked(
639
(int)(0x63d5ba67)), unchecked((int)(0xb713094a)), unchecked((int)(0x6c6d4555)),
640
unchecked((int)(0xb8abf678)), unchecked((int)(0x11269022)), unchecked((int)(0xc5e0230f
641
)), unchecked((int)(0x423c5c96)), unchecked((int)(0x96faefbb)), unchecked((int)(
642
0x3f7789e1)), unchecked((int)(0xebb13acc)), unchecked((int)(0x5d4da2f2)), unchecked(
643
(int)(0x898b11df)), unchecked((int)(0x20067785)), unchecked((int)(0xf4c0c4a8)),
644
unchecked((int)(0x731cbb31)), unchecked((int)(0xa7da081c)), unchecked((int)(0x0e576e46
645
)), unchecked((int)(0xda91dd6b)), unchecked((int)(0x01ef9174)), unchecked((int)(
646
0xd5292259)), unchecked((int)(0x7ca44403)), unchecked((int)(0xa862f72e)), unchecked(
647
(int)(0x2fbe88b7)), unchecked((int)(0xfb783b9a)), unchecked((int)(0x52f55dc0)),
648
unchecked((int)(0x8633eeed)), unchecked((int)(0x208a5b62)), unchecked((int)(0xf44ce84f
649
)), unchecked((int)(0x5dc18e15)), unchecked((int)(0x89073d38)), unchecked((int)(
650
0x0edb42a1)), unchecked((int)(0xda1df18c)), unchecked((int)(0x739097d6)), unchecked(
651
(int)(0xa75624fb)), unchecked((int)(0x7c2868e4)), unchecked((int)(0xa8eedbc9)),
652
unchecked((int)(0x0163bd93)), unchecked((int)(0xd5a50ebe)), unchecked((int)(0x52797127
653
)), unchecked((int)(0x86bfc20a)), unchecked((int)(0x2f32a450)), unchecked((int)(
654
0xfbf4177d)), unchecked((int)(0x4d088f43)), unchecked((int)(0x99ce3c6e)), unchecked(
655
(int)(0x30435a34)), unchecked((int)(0xe485e919)), unchecked((int)(0x63599680)),
656
unchecked((int)(0xb79f25ad)), unchecked((int)(0x1e1243f7)), unchecked((int)(0xcad4f0da
657
)), unchecked((int)(0x11aabcc5)), unchecked((int)(0xc56c0fe8)), unchecked((int)(
658
0x6ce169b2)), unchecked((int)(0xb827da9f)), unchecked((int)(0x3ffba506)), unchecked(
659
(int)(0xeb3d162b)), unchecked((int)(0x42b07071)), unchecked((int)(0x9676c35c)),
660
unchecked((int)(0x2f49400d)), unchecked((int)(0xfb8ff320)), unchecked((int)(0x5202957a
661
)), unchecked((int)(0x86c42657)), unchecked((int)(0x011859ce)), unchecked((int)(
662
0xd5deeae3)), unchecked((int)(0x7c538cb9)), unchecked((int)(0xa8953f94)), unchecked(
663
(int)(0x73eb738b)), unchecked((int)(0xa72dc0a6)), unchecked((int)(0x0ea0a6fc)),
664
unchecked((int)(0xda6615d1)), unchecked((int)(0x5dba6a48)), unchecked((int)(0x897cd965
665
)), unchecked((int)(0x20f1bf3f)), unchecked((int)(0xf4370c12)), unchecked((int)(
666
0x42cb942c)), unchecked((int)(0x960d2701)), unchecked((int)(0x3f80415b)), unchecked(
667
(int)(0xeb46f276)), unchecked((int)(0x6c9a8def)), unchecked((int)(0xb85c3ec2)),
668
unchecked((int)(0x11d15898)), unchecked((int)(0xc517ebb5)), unchecked((int)(0x1e69a7aa
669
)), unchecked((int)(0xcaaf1487)), unchecked((int)(0x632272dd)), unchecked((int)(
670
0xb7e4c1f0)), unchecked((int)(0x3038be69)), unchecked((int)(0xe4fe0d44)), unchecked(
671
(int)(0x4d736b1e)), unchecked((int)(0x99b5d833)) };
673
private static readonly int[] U = new int[] { unchecked((int)(0x00000000)), unchecked(
674
(int)(0x12c6e90f)), unchecked((int)(0x258dd21e)), unchecked((int)(0x374b3b11)),
675
unchecked((int)(0x4b1ba43c)), unchecked((int)(0x59dd4d33)), unchecked((int)(0x6e967622
676
)), unchecked((int)(0x7c509f2d)), unchecked((int)(0x42f1fb55)), unchecked((int)(
677
0x5037125a)), unchecked((int)(0x677c294b)), unchecked((int)(0x75bac044)), unchecked(
678
(int)(0x09ea5f69)), unchecked((int)(0x1b2cb666)), unchecked((int)(0x2c678d77)),
679
unchecked((int)(0x3ea16478)), unchecked((int)(0x51254587)), unchecked((int)(0x43e3ac88
680
)), unchecked((int)(0x74a89799)), unchecked((int)(0x666e7e96)), unchecked((int)(
681
0x1a3ee1bb)), unchecked((int)(0x08f808b4)), unchecked((int)(0x3fb333a5)), unchecked(
682
(int)(0x2d75daaa)), unchecked((int)(0x13d4bed2)), unchecked((int)(0x011257dd)),
683
unchecked((int)(0x36596ccc)), unchecked((int)(0x249f85c3)), unchecked((int)(0x58cf1aee
684
)), unchecked((int)(0x4a09f3e1)), unchecked((int)(0x7d42c8f0)), unchecked((int)(
685
0x6f8421ff)), unchecked((int)(0x768c3823)), unchecked((int)(0x644ad12c)), unchecked(
686
(int)(0x5301ea3d)), unchecked((int)(0x41c70332)), unchecked((int)(0x3d979c1f)),
687
unchecked((int)(0x2f517510)), unchecked((int)(0x181a4e01)), unchecked((int)(0x0adca70e
688
)), unchecked((int)(0x347dc376)), unchecked((int)(0x26bb2a79)), unchecked((int)(
689
0x11f01168)), unchecked((int)(0x0336f867)), unchecked((int)(0x7f66674a)), unchecked(
690
(int)(0x6da08e45)), unchecked((int)(0x5aebb554)), unchecked((int)(0x482d5c5b)),
691
unchecked((int)(0x27a97da4)), unchecked((int)(0x356f94ab)), unchecked((int)(0x0224afba
692
)), unchecked((int)(0x10e246b5)), unchecked((int)(0x6cb2d998)), unchecked((int)(
693
0x7e743097)), unchecked((int)(0x493f0b86)), unchecked((int)(0x5bf9e289)), unchecked(
694
(int)(0x655886f1)), unchecked((int)(0x779e6ffe)), unchecked((int)(0x40d554ef)),
695
unchecked((int)(0x5213bde0)), unchecked((int)(0x2e4322cd)), unchecked((int)(0x3c85cbc2
696
)), unchecked((int)(0x0bcef0d3)), unchecked((int)(0x190819dc)), unchecked((int)(
697
0x39dec36b)), unchecked((int)(0x2b182a64)), unchecked((int)(0x1c531175)), unchecked(
698
(int)(0x0e95f87a)), unchecked((int)(0x72c56757)), unchecked((int)(0x60038e58)),
699
unchecked((int)(0x5748b549)), unchecked((int)(0x458e5c46)), unchecked((int)(0x7b2f383e
700
)), unchecked((int)(0x69e9d131)), unchecked((int)(0x5ea2ea20)), unchecked((int)(
701
0x4c64032f)), unchecked((int)(0x30349c02)), unchecked((int)(0x22f2750d)), unchecked(
702
(int)(0x15b94e1c)), unchecked((int)(0x077fa713)), unchecked((int)(0x68fb86ec)),
703
unchecked((int)(0x7a3d6fe3)), unchecked((int)(0x4d7654f2)), unchecked((int)(0x5fb0bdfd
704
)), unchecked((int)(0x23e022d0)), unchecked((int)(0x3126cbdf)), unchecked((int)(
705
0x066df0ce)), unchecked((int)(0x14ab19c1)), unchecked((int)(0x2a0a7db9)), unchecked(
706
(int)(0x38cc94b6)), unchecked((int)(0x0f87afa7)), unchecked((int)(0x1d4146a8)),
707
unchecked((int)(0x6111d985)), unchecked((int)(0x73d7308a)), unchecked((int)(0x449c0b9b
708
)), unchecked((int)(0x565ae294)), unchecked((int)(0x4f52fb48)), unchecked((int)(
709
0x5d941247)), unchecked((int)(0x6adf2956)), unchecked((int)(0x7819c059)), unchecked(
710
(int)(0x04495f74)), unchecked((int)(0x168fb67b)), unchecked((int)(0x21c48d6a)),
711
unchecked((int)(0x33026465)), unchecked((int)(0x0da3001d)), unchecked((int)(0x1f65e912
712
)), unchecked((int)(0x282ed203)), unchecked((int)(0x3ae83b0c)), unchecked((int)(
713
0x46b8a421)), unchecked((int)(0x547e4d2e)), unchecked((int)(0x6335763f)), unchecked(
714
(int)(0x71f39f30)), unchecked((int)(0x1e77becf)), unchecked((int)(0x0cb157c0)),
715
unchecked((int)(0x3bfa6cd1)), unchecked((int)(0x293c85de)), unchecked((int)(0x556c1af3
716
)), unchecked((int)(0x47aaf3fc)), unchecked((int)(0x70e1c8ed)), unchecked((int)(
717
0x622721e2)), unchecked((int)(0x5c86459a)), unchecked((int)(0x4e40ac95)), unchecked(
718
(int)(0x790b9784)), unchecked((int)(0x6bcd7e8b)), unchecked((int)(0x179de1a6)),
719
unchecked((int)(0x055b08a9)), unchecked((int)(0x321033b8)), unchecked((int)(0x20d6dab7
720
)), unchecked((int)(0x73bd86d6)), unchecked((int)(0x617b6fd9)), unchecked((int)(
721
0x563054c8)), unchecked((int)(0x44f6bdc7)), unchecked((int)(0x38a622ea)), unchecked(
722
(int)(0x2a60cbe5)), unchecked((int)(0x1d2bf0f4)), unchecked((int)(0x0fed19fb)),
723
unchecked((int)(0x314c7d83)), unchecked((int)(0x238a948c)), unchecked((int)(0x14c1af9d
724
)), unchecked((int)(0x06074692)), unchecked((int)(0x7a57d9bf)), unchecked((int)(
725
0x689130b0)), unchecked((int)(0x5fda0ba1)), unchecked((int)(0x4d1ce2ae)), unchecked(
726
(int)(0x2298c351)), unchecked((int)(0x305e2a5e)), unchecked((int)(0x0715114f)),
727
unchecked((int)(0x15d3f840)), unchecked((int)(0x6983676d)), unchecked((int)(0x7b458e62
728
)), unchecked((int)(0x4c0eb573)), unchecked((int)(0x5ec85c7c)), unchecked((int)(
729
0x60693804)), unchecked((int)(0x72afd10b)), unchecked((int)(0x45e4ea1a)), unchecked(
730
(int)(0x57220315)), unchecked((int)(0x2b729c38)), unchecked((int)(0x39b47537)),
731
unchecked((int)(0x0eff4e26)), unchecked((int)(0x1c39a729)), unchecked((int)(0x0531bef5
732
)), unchecked((int)(0x17f757fa)), unchecked((int)(0x20bc6ceb)), unchecked((int)(
733
0x327a85e4)), unchecked((int)(0x4e2a1ac9)), unchecked((int)(0x5cecf3c6)), unchecked(
734
(int)(0x6ba7c8d7)), unchecked((int)(0x796121d8)), unchecked((int)(0x47c045a0)),
735
unchecked((int)(0x5506acaf)), unchecked((int)(0x624d97be)), unchecked((int)(0x708b7eb1
736
)), unchecked((int)(0x0cdbe19c)), unchecked((int)(0x1e1d0893)), unchecked((int)(
737
0x29563382)), unchecked((int)(0x3b90da8d)), unchecked((int)(0x5414fb72)), unchecked(
738
(int)(0x46d2127d)), unchecked((int)(0x7199296c)), unchecked((int)(0x635fc063)),
739
unchecked((int)(0x1f0f5f4e)), unchecked((int)(0x0dc9b641)), unchecked((int)(0x3a828d50
740
)), unchecked((int)(0x2844645f)), unchecked((int)(0x16e50027)), unchecked((int)(
741
0x0423e928)), unchecked((int)(0x3368d239)), unchecked((int)(0x21ae3b36)), unchecked(
742
(int)(0x5dfea41b)), unchecked((int)(0x4f384d14)), unchecked((int)(0x78737605)),
743
unchecked((int)(0x6ab59f0a)), unchecked((int)(0x4a6345bd)), unchecked((int)(0x58a5acb2
744
)), unchecked((int)(0x6fee97a3)), unchecked((int)(0x7d287eac)), unchecked((int)(
745
0x0178e181)), unchecked((int)(0x13be088e)), unchecked((int)(0x24f5339f)), unchecked(
746
(int)(0x3633da90)), unchecked((int)(0x0892bee8)), unchecked((int)(0x1a5457e7)),
747
unchecked((int)(0x2d1f6cf6)), unchecked((int)(0x3fd985f9)), unchecked((int)(0x43891ad4
748
)), unchecked((int)(0x514ff3db)), unchecked((int)(0x6604c8ca)), unchecked((int)(
749
0x74c221c5)), unchecked((int)(0x1b46003a)), unchecked((int)(0x0980e935)), unchecked(
750
(int)(0x3ecbd224)), unchecked((int)(0x2c0d3b2b)), unchecked((int)(0x505da406)),
751
unchecked((int)(0x429b4d09)), unchecked((int)(0x75d07618)), unchecked((int)(0x67169f17
752
)), unchecked((int)(0x59b7fb6f)), unchecked((int)(0x4b711260)), unchecked((int)(
753
0x7c3a2971)), unchecked((int)(0x6efcc07e)), unchecked((int)(0x12ac5f53)), unchecked(
754
(int)(0x006ab65c)), unchecked((int)(0x37218d4d)), unchecked((int)(0x25e76442)),
755
unchecked((int)(0x3cef7d9e)), unchecked((int)(0x2e299491)), unchecked((int)(0x1962af80
756
)), unchecked((int)(0x0ba4468f)), unchecked((int)(0x77f4d9a2)), unchecked((int)(
757
0x653230ad)), unchecked((int)(0x52790bbc)), unchecked((int)(0x40bfe2b3)), unchecked(
758
(int)(0x7e1e86cb)), unchecked((int)(0x6cd86fc4)), unchecked((int)(0x5b9354d5)),
759
unchecked((int)(0x4955bdda)), unchecked((int)(0x350522f7)), unchecked((int)(0x27c3cbf8
760
)), unchecked((int)(0x1088f0e9)), unchecked((int)(0x024e19e6)), unchecked((int)(
761
0x6dca3819)), unchecked((int)(0x7f0cd116)), unchecked((int)(0x4847ea07)), unchecked(
762
(int)(0x5a810308)), unchecked((int)(0x26d19c25)), unchecked((int)(0x3417752a)),
763
unchecked((int)(0x035c4e3b)), unchecked((int)(0x119aa734)), unchecked((int)(0x2f3bc34c
764
)), unchecked((int)(0x3dfd2a43)), unchecked((int)(0x0ab61152)), unchecked((int)(
765
0x1870f85d)), unchecked((int)(0x64206770)), unchecked((int)(0x76e68e7f)), unchecked(
766
(int)(0x41adb56e)), unchecked((int)(0x536b5c61)) };
added
removed
contrib/NGit/NGit.Storage.Pack/DeltaIndex.cs
