Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(482)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: third_party/lzma/v4_65/files/CS/7zip/Compress/LZ/LzBinTree.cs

Issue 624713003: Keep only base/extractor.[cc|h]. (Closed) Base URL: https://chromium.googlesource.com/external/omaha.git@master
Patch Set: Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « third_party/lzma/v4_65/files/CS/7zip/Compress/LZ/IMatchFinder.cs ('k') | third_party/lzma/v4_65/files/CS/7zip/Compress/LZ/LzInWindow.cs » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // LzBinTree.cs
2
3 using System;
4
5 namespace SevenZip.Compression.LZ
6 {
7 public class BinTree : InWindow, IMatchFinder
8 {
9 UInt32 _cyclicBufferPos;
10 UInt32 _cyclicBufferSize = 0;
11 UInt32 _matchMaxLen;
12
13 UInt32[] _son;
14 UInt32[] _hash;
15
16 UInt32 _cutValue = 0xFF;
17 UInt32 _hashMask;
18 UInt32 _hashSizeSum = 0;
19
20 bool HASH_ARRAY = true;
21
22 const UInt32 kHash2Size = 1 << 10;
23 const UInt32 kHash3Size = 1 << 16;
24 const UInt32 kBT2HashSize = 1 << 16;
25 const UInt32 kStartMaxLen = 1;
26 const UInt32 kHash3Offset = kHash2Size;
27 const UInt32 kEmptyHashValue = 0;
28 const UInt32 kMaxValForNormalize = ((UInt32)1 << 31) - 1;
29
30 UInt32 kNumHashDirectBytes = 0;
31 UInt32 kMinMatchCheck = 4;
32 UInt32 kFixHashSize = kHash2Size + kHash3Size;
33
34 public void SetType(int numHashBytes)
35 {
36 HASH_ARRAY = (numHashBytes > 2);
37 if (HASH_ARRAY)
38 {
39 kNumHashDirectBytes = 0;
40 kMinMatchCheck = 4;
41 kFixHashSize = kHash2Size + kHash3Size;
42 }
43 else
44 {
45 kNumHashDirectBytes = 2;
46 kMinMatchCheck = 2 + 1;
47 kFixHashSize = 0;
48 }
49 }
50
51 public new void SetStream(System.IO.Stream stream) { base.SetStr eam(stream); }
52 public new void ReleaseStream() { base.ReleaseStream(); }
53
54 public new void Init()
55 {
56 base.Init();
57 for (UInt32 i = 0; i < _hashSizeSum; i++)
58 _hash[i] = kEmptyHashValue;
59 _cyclicBufferPos = 0;
60 ReduceOffsets(-1);
61 }
62
63 public new void MovePos()
64 {
65 if (++_cyclicBufferPos >= _cyclicBufferSize)
66 _cyclicBufferPos = 0;
67 base.MovePos();
68 if (_pos == kMaxValForNormalize)
69 Normalize();
70 }
71
72 public new Byte GetIndexByte(Int32 index) { return base.GetIndex Byte(index); }
73
74 public new UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt 32 limit)
75 { return base.GetMatchLen(index, distance, limit); }
76
77 public new UInt32 GetNumAvailableBytes() { return base.GetNumAva ilableBytes(); }
78
79 public void Create(UInt32 historySize, UInt32 keepAddBufferBefor e,
80 UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
81 {
82 if (historySize > kMaxValForNormalize - 256)
83 throw new Exception();
84 _cutValue = 16 + (matchMaxLen >> 1);
85
86 UInt32 windowReservSize = (historySize + keepAddBufferBe fore +
87 matchMaxLen + keepAddBufferAfter) / 2 + 256;
88
89 base.Create(historySize + keepAddBufferBefore, matchMaxL en + keepAddBufferAfter, windowReservSize);
90
91 _matchMaxLen = matchMaxLen;
92
93 UInt32 cyclicBufferSize = historySize + 1;
94 if (_cyclicBufferSize != cyclicBufferSize)
95 _son = new UInt32[(_cyclicBufferSize = cyclicBuf ferSize) * 2];
96
97 UInt32 hs = kBT2HashSize;
98
99 if (HASH_ARRAY)
100 {
101 hs = historySize - 1;
102 hs |= (hs >> 1);
103 hs |= (hs >> 2);
104 hs |= (hs >> 4);
105 hs |= (hs >> 8);
106 hs >>= 1;
107 hs |= 0xFFFF;
108 if (hs > (1 << 24))
109 hs >>= 1;
110 _hashMask = hs;
111 hs++;
112 hs += kFixHashSize;
113 }
114 if (hs != _hashSizeSum)
115 _hash = new UInt32[_hashSizeSum = hs];
116 }
117
118 public UInt32 GetMatches(UInt32[] distances)
119 {
120 UInt32 lenLimit;
121 if (_pos + _matchMaxLen <= _streamPos)
122 lenLimit = _matchMaxLen;
123 else
124 {
125 lenLimit = _streamPos - _pos;
126 if (lenLimit < kMinMatchCheck)
127 {
128 MovePos();
129 return 0;
130 }
131 }
132
133 UInt32 offset = 0;
134 UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
135 UInt32 cur = _bufferOffset + _pos;
136 UInt32 maxLen = kStartMaxLen; // to avoid items for len < hashSize;
137 UInt32 hashValue, hash2Value = 0, hash3Value = 0;
138
139 if (HASH_ARRAY)
140 {
141 UInt32 temp = CRC.Table[_bufferBase[cur]] ^ _buf ferBase[cur + 1];
142 hash2Value = temp & (kHash2Size - 1);
143 temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8);
144 hash3Value = temp & (kHash3Size - 1);
145 hashValue = (temp ^ (CRC.Table[_bufferBase[cur + 3]] << 5)) & _hashMask;
146 }
147 else
148 hashValue = _bufferBase[cur] ^ ((UInt32)(_buffer Base[cur + 1]) << 8);
149
150 UInt32 curMatch = _hash[kFixHashSize + hashValue];
151 if (HASH_ARRAY)
152 {
153 UInt32 curMatch2 = _hash[hash2Value];
154 UInt32 curMatch3 = _hash[kHash3Offset + hash3Val ue];
155 _hash[hash2Value] = _pos;
156 _hash[kHash3Offset + hash3Value] = _pos;
157 if (curMatch2 > matchMinPos)
158 if (_bufferBase[_bufferOffset + curMatch 2] == _bufferBase[cur])
159 {
160 distances[offset++] = maxLen = 2 ;
161 distances[offset++] = _pos - cur Match2 - 1;
162 }
163 if (curMatch3 > matchMinPos)
164 if (_bufferBase[_bufferOffset + curMatch 3] == _bufferBase[cur])
165 {
166 if (curMatch3 == curMatch2)
167 offset -= 2;
168 distances[offset++] = maxLen = 3 ;
169 distances[offset++] = _pos - cur Match3 - 1;
170 curMatch2 = curMatch3;
171 }
172 if (offset != 0 && curMatch2 == curMatch)
173 {
174 offset -= 2;
175 maxLen = kStartMaxLen;
176 }
177 }
178
179 _hash[kFixHashSize + hashValue] = _pos;
180
181 UInt32 ptr0 = (_cyclicBufferPos << 1) + 1;
182 UInt32 ptr1 = (_cyclicBufferPos << 1);
183
184 UInt32 len0, len1;
185 len0 = len1 = kNumHashDirectBytes;
186
187 if (kNumHashDirectBytes != 0)
188 {
189 if (curMatch > matchMinPos)
190 {
191 if (_bufferBase[_bufferOffset + curMatch + kNumHashDirectBytes] !=
192 _bufferBase[cur + kNumHa shDirectBytes])
193 {
194 distances[offset++] = maxLen = k NumHashDirectBytes;
195 distances[offset++] = _pos - cur Match - 1;
196 }
197 }
198 }
199
200 UInt32 count = _cutValue;
201
202 while(true)
203 {
204 if(curMatch <= matchMinPos || count-- == 0)
205 {
206 _son[ptr0] = _son[ptr1] = kEmptyHashValu e;
207 break;
208 }
209 UInt32 delta = _pos - curMatch;
210 UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ?
211 (_cyclicBufferPos - delt a) :
212 (_cyclicBufferPos - delt a + _cyclicBufferSize)) << 1;
213
214 UInt32 pby1 = _bufferOffset + curMatch;
215 UInt32 len = Math.Min(len0, len1);
216 if (_bufferBase[pby1 + len] == _bufferBase[cur + len])
217 {
218 while(++len != lenLimit)
219 if (_bufferBase[pby1 + len] != _ bufferBase[cur + len])
220 break;
221 if (maxLen < len)
222 {
223 distances[offset++] = maxLen = l en;
224 distances[offset++] = delta - 1;
225 if (len == lenLimit)
226 {
227 _son[ptr1] = _son[cyclic Pos];
228 _son[ptr0] = _son[cyclic Pos + 1];
229 break;
230 }
231 }
232 }
233 if (_bufferBase[pby1 + len] < _bufferBase[cur + len])
234 {
235 _son[ptr1] = curMatch;
236 ptr1 = cyclicPos + 1;
237 curMatch = _son[ptr1];
238 len1 = len;
239 }
240 else
241 {
242 _son[ptr0] = curMatch;
243 ptr0 = cyclicPos;
244 curMatch = _son[ptr0];
245 len0 = len;
246 }
247 }
248 MovePos();
249 return offset;
250 }
251
252 public void Skip(UInt32 num)
253 {
254 do
255 {
256 UInt32 lenLimit;
257 if (_pos + _matchMaxLen <= _streamPos)
258 lenLimit = _matchMaxLen;
259 else
260 {
261 lenLimit = _streamPos - _pos;
262 if (lenLimit < kMinMatchCheck)
263 {
264 MovePos();
265 continue;
266 }
267 }
268
269 UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
270 UInt32 cur = _bufferOffset + _pos;
271
272 UInt32 hashValue;
273
274 if (HASH_ARRAY)
275 {
276 UInt32 temp = CRC.Table[_bufferBase[cur] ] ^ _bufferBase[cur + 1];
277 UInt32 hash2Value = temp & (kHash2Size - 1);
278 _hash[hash2Value] = _pos;
279 temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8);
280 UInt32 hash3Value = temp & (kHash3Size - 1);
281 _hash[kHash3Offset + hash3Value] = _pos;
282 hashValue = (temp ^ (CRC.Table[_bufferBa se[cur + 3]] << 5)) & _hashMask;
283 }
284 else
285 hashValue = _bufferBase[cur] ^ ((UInt32) (_bufferBase[cur + 1]) << 8);
286
287 UInt32 curMatch = _hash[kFixHashSize + hashValue ];
288 _hash[kFixHashSize + hashValue] = _pos;
289
290 UInt32 ptr0 = (_cyclicBufferPos << 1) + 1;
291 UInt32 ptr1 = (_cyclicBufferPos << 1);
292
293 UInt32 len0, len1;
294 len0 = len1 = kNumHashDirectBytes;
295
296 UInt32 count = _cutValue;
297 while (true)
298 {
299 if (curMatch <= matchMinPos || count-- = = 0)
300 {
301 _son[ptr0] = _son[ptr1] = kEmpty HashValue;
302 break;
303 }
304
305 UInt32 delta = _pos - curMatch;
306 UInt32 cyclicPos = ((delta <= _cyclicBuf ferPos) ?
307 (_cyclicBufferPo s - delta) :
308 (_cyclicBufferPo s - delta + _cyclicBufferSize)) << 1;
309
310 UInt32 pby1 = _bufferOffset + curMatch;
311 UInt32 len = Math.Min(len0, len1);
312 if (_bufferBase[pby1 + len] == _bufferBa se[cur + len])
313 {
314 while (++len != lenLimit)
315 if (_bufferBase[pby1 + l en] != _bufferBase[cur + len])
316 break;
317 if (len == lenLimit)
318 {
319 _son[ptr1] = _son[cyclic Pos];
320 _son[ptr0] = _son[cyclic Pos + 1];
321 break;
322 }
323 }
324 if (_bufferBase[pby1 + len] < _bufferBas e[cur + len])
325 {
326 _son[ptr1] = curMatch;
327 ptr1 = cyclicPos + 1;
328 curMatch = _son[ptr1];
329 len1 = len;
330 }
331 else
332 {
333 _son[ptr0] = curMatch;
334 ptr0 = cyclicPos;
335 curMatch = _son[ptr0];
336 len0 = len;
337 }
338 }
339 MovePos();
340 }
341 while (--num != 0);
342 }
343
344 void NormalizeLinks(UInt32[] items, UInt32 numItems, UInt32 subV alue)
345 {
346 for (UInt32 i = 0; i < numItems; i++)
347 {
348 UInt32 value = items[i];
349 if (value <= subValue)
350 value = kEmptyHashValue;
351 else
352 value -= subValue;
353 items[i] = value;
354 }
355 }
356
357 void Normalize()
358 {
359 UInt32 subValue = _pos - _cyclicBufferSize;
360 NormalizeLinks(_son, _cyclicBufferSize * 2, subValue);
361 NormalizeLinks(_hash, _hashSizeSum, subValue);
362 ReduceOffsets((Int32)subValue);
363 }
364
365 public void SetCutValue(UInt32 cutValue) { _cutValue = cutValue; }
366 }
367 }
OLDNEW
« no previous file with comments | « third_party/lzma/v4_65/files/CS/7zip/Compress/LZ/IMatchFinder.cs ('k') | third_party/lzma/v4_65/files/CS/7zip/Compress/LZ/LzInWindow.cs » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698