| OLD | NEW |
|---|
| (Empty) |
| 1 // LZ.BinTree | |
| 2 | |
| 3 package SevenZip.Compression.LZ; | |
| 4 import java.io.IOException; | |
| 5 | |
| 6 | |
| 7 public class BinTree extends InWindow | |
| 8 { | |
| 9 int _cyclicBufferPos; | |
| 10 int _cyclicBufferSize = 0; | |
| 11 int _matchMaxLen; | |
| 12 | |
| 13 int[] _son; | |
| 14 int[] _hash; | |
| 15 | |
| 16 int _cutValue = 0xFF; | |
| 17 int _hashMask; | |
| 18 int _hashSizeSum = 0; | |
| 19 | |
| 20 boolean HASH_ARRAY = true; | |
| 21 | |
| 22 static final int kHash2Size = 1 << 10; | |
| 23 static final int kHash3Size = 1 << 16; | |
| 24 static final int kBT2HashSize = 1 << 16; | |
| 25 static final int kStartMaxLen = 1; | |
| 26 static final int kHash3Offset = kHash2Size; | |
| 27 static final int kEmptyHashValue = 0; | |
| 28 static final int kMaxValForNormalize = (1 << 30) - 1; | |
| 29 | |
| 30 int kNumHashDirectBytes = 0; | |
| 31 int kMinMatchCheck = 4; | |
| 32 int 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 | |
| 52 | |
| 53 | |
| 54 public void Init() throws IOException | |
| 55 { | |
| 56 super.Init(); | |
| 57 for (int i = 0; i < _hashSizeSum; i++) | |
| 58 _hash[i] = kEmptyHashValue; | |
| 59 _cyclicBufferPos = 0; | |
| 60 ReduceOffsets(-1); | |
| 61 } | |
| 62 | |
| 63 public void MovePos() throws IOException | |
| 64 { | |
| 65 if (++_cyclicBufferPos >= _cyclicBufferSize) | |
| 66 _cyclicBufferPos = 0; | |
| 67 super.MovePos(); | |
| 68 if (_pos == kMaxValForNormalize) | |
| 69 Normalize(); | |
| 70 } | |
| 71 | |
| 72 | |
| 73 | |
| 74 | |
| 75 | |
| 76 | |
| 77 | |
| 78 | |
| 79 public boolean Create(int historySize, int keepAddBufferBefore, | |
| 80 int matchMaxLen, int keepAddBufferAfter) | |
| 81 { | |
| 82 if (historySize > kMaxValForNormalize - 256) | |
| 83 return false; | |
| 84 _cutValue = 16 + (matchMaxLen >> 1); | |
| 85 | |
| 86 int windowReservSize = (historySize + keepAddBufferBefore + | |
| 87 matchMaxLen + keepAddBufferAfter) / 2 + 256; | |
| 88 | |
| 89 super.Create(historySize + keepAddBufferBefore, matchMaxLen + ke
epAddBufferAfter, windowReservSize); | |
| 90 | |
| 91 _matchMaxLen = matchMaxLen; | |
| 92 | |
| 93 int cyclicBufferSize = historySize + 1; | |
| 94 if (_cyclicBufferSize != cyclicBufferSize) | |
| 95 _son = new int[(_cyclicBufferSize = cyclicBufferSize) *
2]; | |
| 96 | |
| 97 int 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 int [_hashSizeSum = hs]; | |
| 116 return true; | |
| 117 } | |
| 118 public int GetMatches(int[] distances) throws IOException | |
| 119 { | |
| 120 int 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 int offset = 0; | |
| 134 int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBu
fferSize) : 0; | |
| 135 int cur = _bufferOffset + _pos; | |
| 136 int maxLen = kStartMaxLen; // to avoid items for len < hashSize; | |
| 137 int hashValue, hash2Value = 0, hash3Value = 0; | |
| 138 | |
| 139 if (HASH_ARRAY) | |
| 140 { | |
| 141 int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferB
ase[cur + 1] & 0xFF); | |
| 142 hash2Value = temp & (kHash2Size - 1); | |
| 143 temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8); | |
| 144 hash3Value = temp & (kHash3Size - 1); | |
| 145 hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xF
F] << 5)) & _hashMask; | |
| 146 } | |
| 147 else | |
| 148 hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferB
ase[cur + 1] & 0xFF) << 8)); | |
| 149 | |
| 150 int curMatch = _hash[kFixHashSize + hashValue]; | |
| 151 if (HASH_ARRAY) | |
| 152 { | |
| 153 int curMatch2 = _hash[hash2Value]; | |
| 154 int curMatch3 = _hash[kHash3Offset + hash3Value]; | |
| 155 _hash[hash2Value] = _pos; | |
| 156 _hash[kHash3Offset + hash3Value] = _pos; | |
| 157 if (curMatch2 > matchMinPos) | |
| 158 if (_bufferBase[_bufferOffset + curMatch2] == _b
ufferBase[cur]) | |
| 159 { | |
| 160 distances[offset++] = maxLen = 2; | |
| 161 distances[offset++] = _pos - curMatch2 -
1; | |
| 162 } | |
| 163 if (curMatch3 > matchMinPos) | |
| 164 if (_bufferBase[_bufferOffset + curMatch3] == _b
ufferBase[cur]) | |
| 165 { | |
| 166 if (curMatch3 == curMatch2) | |
| 167 offset -= 2; | |
| 168 distances[offset++] = maxLen = 3; | |
| 169 distances[offset++] = _pos - curMatch3 -
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 int ptr0 = (_cyclicBufferPos << 1) + 1; | |
| 182 int ptr1 = (_cyclicBufferPos << 1); | |
| 183 | |
| 184 int len0, len1; | |
| 185 len0 = len1 = kNumHashDirectBytes; | |
| 186 | |
| 187 if (kNumHashDirectBytes != 0) | |
| 188 { | |
| 189 if (curMatch > matchMinPos) | |
| 190 { | |
| 191 if (_bufferBase[_bufferOffset + curMatch + kNumH
ashDirectBytes] != | |
| 192 _bufferBase[cur + kNumHashDirect
Bytes]) | |
| 193 { | |
| 194 distances[offset++] = maxLen = kNumHashD
irectBytes; | |
| 195 distances[offset++] = _pos - curMatch -
1; | |
| 196 } | |
| 197 } | |
| 198 } | |
| 199 | |
| 200 int count = _cutValue; | |
| 201 | |
| 202 while (true) | |
| 203 { | |
| 204 if (curMatch <= matchMinPos || count-- == 0) | |
| 205 { | |
| 206 _son[ptr0] = _son[ptr1] = kEmptyHashValue; | |
| 207 break; | |
| 208 } | |
| 209 int delta = _pos - curMatch; | |
| 210 int cyclicPos = ((delta <= _cyclicBufferPos) ? | |
| 211 (_cyclicBufferPos - delta) : | |
| 212 (_cyclicBufferPos - delta + _cyclicBufferSize))
<< 1; | |
| 213 | |
| 214 int pby1 = _bufferOffset + curMatch; | |
| 215 int len = Math.min(len0, len1); | |
| 216 if (_bufferBase[pby1 + len] == _bufferBase[cur + len]) | |
| 217 { | |
| 218 while(++len != lenLimit) | |
| 219 if (_bufferBase[pby1 + len] != _bufferBa
se[cur + len]) | |
| 220 break; | |
| 221 if (maxLen < len) | |
| 222 { | |
| 223 distances[offset++] = maxLen = len; | |
| 224 distances[offset++] = delta - 1; | |
| 225 if (len == lenLimit) | |
| 226 { | |
| 227 _son[ptr1] = _son[cyclicPos]; | |
| 228 _son[ptr0] = _son[cyclicPos + 1]
; | |
| 229 break; | |
| 230 } | |
| 231 } | |
| 232 } | |
| 233 if ((_bufferBase[pby1 + len] & 0xFF) < (_bufferBase[cur
+ len] & 0xFF)) | |
| 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(int num) throws IOException | |
| 253 { | |
| 254 do | |
| 255 { | |
| 256 int 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 int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _
cyclicBufferSize) : 0; | |
| 270 int cur = _bufferOffset + _pos; | |
| 271 | |
| 272 int hashValue; | |
| 273 | |
| 274 if (HASH_ARRAY) | |
| 275 { | |
| 276 int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (
_bufferBase[cur + 1] & 0xFF); | |
| 277 int hash2Value = temp & (kHash2Size - 1); | |
| 278 _hash[hash2Value] = _pos; | |
| 279 temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8
); | |
| 280 int hash3Value = temp & (kHash3Size - 1); | |
| 281 _hash[kHash3Offset + hash3Value] = _pos; | |
| 282 hashValue = (temp ^ (CrcTable[_bufferBase[cur +
3] & 0xFF] << 5)) & _hashMask; | |
| 283 } | |
| 284 else | |
| 285 hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(
_bufferBase[cur + 1] & 0xFF) << 8)); | |
| 286 | |
| 287 int curMatch = _hash[kFixHashSize + hashValue]; | |
| 288 _hash[kFixHashSize + hashValue] = _pos; | |
| 289 | |
| 290 int ptr0 = (_cyclicBufferPos << 1) + 1; | |
| 291 int ptr1 = (_cyclicBufferPos << 1); | |
| 292 | |
| 293 int len0, len1; | |
| 294 len0 = len1 = kNumHashDirectBytes; | |
| 295 | |
| 296 int count = _cutValue; | |
| 297 while (true) | |
| 298 { | |
| 299 if (curMatch <= matchMinPos || count-- == 0) | |
| 300 { | |
| 301 _son[ptr0] = _son[ptr1] = kEmptyHashValu
e; | |
| 302 break; | |
| 303 } | |
| 304 | |
| 305 int delta = _pos - curMatch; | |
| 306 int cyclicPos = ((delta <= _cyclicBufferPos) ? | |
| 307 (_cyclicBufferPos - delta) : | |
| 308 (_cyclicBufferPos - delta + _cyclicBuffe
rSize)) << 1; | |
| 309 | |
| 310 int pby1 = _bufferOffset + curMatch; | |
| 311 int len = Math.min(len0, len1); | |
| 312 if (_bufferBase[pby1 + len] == _bufferBase[cur +
len]) | |
| 313 { | |
| 314 while (++len != lenLimit) | |
| 315 if (_bufferBase[pby1 + len] != _
bufferBase[cur + len]) | |
| 316 break; | |
| 317 if (len == lenLimit) | |
| 318 { | |
| 319 _son[ptr1] = _son[cyclicPos]; | |
| 320 _son[ptr0] = _son[cyclicPos + 1]
; | |
| 321 break; | |
| 322 } | |
| 323 } | |
| 324 if ((_bufferBase[pby1 + len] & 0xFF) < (_bufferB
ase[cur + len] & 0xFF)) | |
| 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(int[] items, int numItems, int subValue) | |
| 345 { | |
| 346 for (int i = 0; i < numItems; i++) | |
| 347 { | |
| 348 int 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 int subValue = _pos - _cyclicBufferSize; | |
| 360 NormalizeLinks(_son, _cyclicBufferSize * 2, subValue); | |
| 361 NormalizeLinks(_hash, _hashSizeSum, subValue); | |
| 362 ReduceOffsets(subValue); | |
| 363 } | |
| 364 | |
| 365 public void SetCutValue(int cutValue) { _cutValue = cutValue; } | |
| 366 | |
| 367 private static final int[] CrcTable = new int[256]; | |
| 368 | |
| 369 static | |
| 370 { | |
| 371 for (int i = 0; i < 256; i++) | |
| 372 { | |
| 373 int r = i; | |
| 374 for (int j = 0; j < 8; j++) | |
| 375 if ((r & 1) != 0) | |
| 376 r = (r >>> 1) ^ 0xEDB88320; | |
| 377 else | |
| 378 r >>>= 1; | |
| 379 CrcTable[i] = r; | |
| 380 } | |
| 381 } | |
| 382 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 624713003:
Keep only base/extractor.[cc|h]. (Closed)
Base URL: https://chromium.googlesource.com/external/omaha.git@master