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 + keepAddBufferAfter, 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 - _cyclicBufferSize) : 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] ^ (_bufferBase[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] & 0xFF] << 5)) & _hashMask; 146 } 147 else 148 hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[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] == _bufferBase[cur]) 159 { 160 distances[offset++] = maxLen = 2; 161 distances[offset++] = _pos - curMatch2 - 1; 162 } 163 if (curMatch3 > matchMinPos) 164 if (_bufferBase[_bufferOffset + curMatch3] == _bufferBase[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 + kNumHashDirectBytes] != 192 _bufferBase[cur + kNumHashDirectBytes]) 193 { 194 distances[offset++] = maxLen = kNumHashDirectBytes; 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] != _bufferBase[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] = kEmptyHashValue; 302 break; 303 } 304 305 int delta = _pos - curMatch; 306 int cyclicPos = ((delta <= _cyclicBufferPos) ? 307 (_cyclicBufferPos - delta) : 308 (_cyclicBufferPos - delta + _cyclicBufferSize)) << 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) < (_bufferBase[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 } 383
