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