forked from dotnet/Nerdbank.GitVersioning
/
GitPackIndexMappedReader.cs
166 lines (140 loc) · 6.27 KB
/
GitPackIndexMappedReader.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
using System;
using System.Buffers.Binary;
using System.Diagnostics;
using System.IO;
using System.IO.MemoryMappedFiles;
namespace Nerdbank.GitVersioning.ManagedGit
{
/// <summary>
/// A <see cref="GitPackIndexReader"/> which uses a memory-mapped file to read from the index.
/// </summary>
/// <seealso href="https://git-scm.com/docs/pack-format"/>
public unsafe class GitPackIndexMappedReader : GitPackIndexReader
{
private readonly MemoryMappedFile file;
private readonly MemoryMappedViewAccessor accessor;
// The fanout table consists of
// 256 4-byte network byte order integers.
// The N-th entry of this table records the number of objects in the corresponding pack,
// the first byte of whose object name is less than or equal to N.
private readonly int[] fanoutTable = new int[257];
private byte* ptr;
private bool initialized;
/// <summary>
/// Initializes a new instance of the <see cref="GitPackIndexMappedReader"/> class.
/// </summary>
/// <param name="stream">
/// A <see cref="FileStream"/> which points to the index file.
/// </param>
public GitPackIndexMappedReader(FileStream stream)
{
if (stream == null)
{
throw new ArgumentNullException(nameof(stream));
}
this.file = MemoryMappedFile.CreateFromFile(stream, mapName: null, capacity: 0, MemoryMappedFileAccess.Read, HandleInheritability.None, leaveOpen: false);
this.accessor = this.file.CreateViewAccessor(0, 0, MemoryMappedFileAccess.Read);
this.accessor.SafeMemoryMappedViewHandle.AcquirePointer(ref this.ptr);
}
private ReadOnlySpan<byte> Value
{
get
{
return new ReadOnlySpan<byte>(this.ptr, (int)this.accessor.Capacity);
}
}
/// <inheritdoc/>
public override (long?, GitObjectId?) GetOffset(Span<byte> objectName, bool endsWithHalfByte = false)
{
this.Initialize();
var packStart = this.fanoutTable[objectName[0]];
var packEnd = this.fanoutTable[objectName[0] + 1];
var objectCount = this.fanoutTable[256];
// The fanout table is followed by a table of sorted 20-byte SHA-1 object names.
// These are packed together without offset values to reduce the cache footprint of the binary search for a specific object name.
// The object names start at: 4 (header) + 4 (version) + 256 * 4 (fanout table) + 20 * (packStart)
// and end at 4 (header) + 4 (version) + 256 * 4 (fanout table) + 20 * (packEnd)
var i = 0;
var order = 0;
var tableSize = 20 * (packEnd - packStart + 1);
var table = this.Value.Slice(4 + 4 + 256 * 4 + 20 * packStart, tableSize);
int originalPackStart = packStart;
packEnd -= originalPackStart;
packStart = 0;
while (packStart <= packEnd)
{
i = (packStart + packEnd) / 2;
ReadOnlySpan<byte> comparand = table.Slice(20 * i, objectName.Length);
if (endsWithHalfByte)
{
// Copy out the value to be checked so we can zero out the last four bits,
// so that it matches the last 4 bits of the objectName that isn't supposed to be compared.
Span<byte> buffer = stackalloc byte[20];
comparand.CopyTo(buffer);
buffer[objectName.Length - 1] &= 0xf0;
order = buffer.Slice(0, objectName.Length).SequenceCompareTo(objectName);
}
else
{
order = comparand.SequenceCompareTo(objectName);
}
if (order < 0)
{
packStart = i + 1;
}
else if (order > 0)
{
packEnd = i - 1;
}
else
{
break;
}
}
if (order != 0)
{
return (null, null);
}
// Get the offset value. It's located at:
// 4 (header) + 4 (version) + 256 * 4 (fanout table) + 20 * objectCount (SHA1 object name table) + 4 * objectCount (CRC32) + 4 * i (offset values)
int offsetTableStart = 4 + 4 + 256 * 4 + 20 * objectCount + 4 * objectCount;
var offsetBuffer = this.Value.Slice(offsetTableStart + 4 * (i + originalPackStart), 4);
var offset = BinaryPrimitives.ReadUInt32BigEndian(offsetBuffer);
if (offsetBuffer[0] < 128)
{
return (offset, GitObjectId.Parse(table.Slice(20 * i, 20)));
}
else
{
// If the first bit of the offset address is set, the offset is stored as a 64-bit value in the table of 8-byte offset entries,
// which follows the table of 4-byte offset entries: "large offsets are encoded as an index into the next table with the msbit set."
offset = offset & 0x7FFFFFFF;
offsetBuffer = this.Value.Slice(offsetTableStart + 4 * objectCount + 8 * (int)offset, 8);
var offset64 = BinaryPrimitives.ReadInt64BigEndian(offsetBuffer);
return (offset64, GitObjectId.Parse(table.Slice(20 * i, 20)));
}
}
/// <inheritdoc/>
public override void Dispose()
{
this.accessor.Dispose();
this.file.Dispose();
}
private void Initialize()
{
if (!this.initialized)
{
var value = this.Value;
var header = value.Slice(0, 4);
var version = BinaryPrimitives.ReadInt32BigEndian(value.Slice(4, 4));
Debug.Assert(header.SequenceEqual(Header));
Debug.Assert(version == 2);
for (int i = 1; i <= 256; i++)
{
this.fanoutTable[i] = BinaryPrimitives.ReadInt32BigEndian(value.Slice(4 + 4 * i, 4));
}
this.initialized = true;
}
}
}
}