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 SetType(int numHashBytes)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 SetStream(System.IO.Stream stream)51 public new void SetStream(System.IO.Stream stream) { base.SetStream(stream); } ReleaseStream()52 public new void ReleaseStream() { base.ReleaseStream(); } 53 Init()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 MovePos()63 public new void MovePos() 64 { 65 if (++_cyclicBufferPos >= _cyclicBufferSize) 66 _cyclicBufferPos = 0; 67 base.MovePos(); 68 if (_pos == kMaxValForNormalize) 69 Normalize(); 70 } 71 GetIndexByte(Int32 index)72 public new Byte GetIndexByte(Int32 index) { return base.GetIndexByte(index); } 73 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit)74 public new UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit) 75 { return base.GetMatchLen(index, distance, limit); } 76 GetNumAvailableBytes()77 public new UInt32 GetNumAvailableBytes() { return base.GetNumAvailableBytes(); } 78 Create(UInt32 historySize, UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter)79 public void Create(UInt32 historySize, UInt32 keepAddBufferBefore, 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 + keepAddBufferBefore + 87 matchMaxLen + keepAddBufferAfter) / 2 + 256; 88 89 base.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize); 90 91 _matchMaxLen = matchMaxLen; 92 93 UInt32 cyclicBufferSize = historySize + 1; 94 if (_cyclicBufferSize != cyclicBufferSize) 95 _son = new UInt32[(_cyclicBufferSize = cyclicBufferSize) * 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 GetMatches(UInt32[] distances)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]] ^ _bufferBase[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)(_bufferBase[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 + 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 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 + kNumHashDirectBytes]) 193 { 194 distances[offset++] = maxLen = kNumHashDirectBytes; 195 distances[offset++] = _pos - curMatch - 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] = kEmptyHashValue; 207 break; 208 } 209 UInt32 delta = _pos - curMatch; 210 UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ? 211 (_cyclicBufferPos - delta) : 212 (_cyclicBufferPos - delta + _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 = 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] < _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 Skip(UInt32 num)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[_bufferBase[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] = kEmptyHashValue; 302 break; 303 } 304 305 UInt32 delta = _pos - curMatch; 306 UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ? 307 (_cyclicBufferPos - delta) : 308 (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1; 309 310 UInt32 pby1 = _bufferOffset + curMatch; 311 UInt32 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] < _bufferBase[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 NormalizeLinks(UInt32[] items, UInt32 numItems, UInt32 subValue)344 void NormalizeLinks(UInt32[] items, UInt32 numItems, UInt32 subValue) 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 Normalize()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 SetCutValue(UInt32 cutValue)365 public void SetCutValue(UInt32 cutValue) { _cutValue = cutValue; } 366 } 367 } 368