1baa3858d3f5d128a5c8466b700098109edcad5f2repo sync// LZ.BinTree 2baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 3baa3858d3f5d128a5c8466b700098109edcad5f2repo syncpackage SevenZip.Compression.LZ; 4baa3858d3f5d128a5c8466b700098109edcad5f2repo syncimport java.io.IOException; 5baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 6baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 7baa3858d3f5d128a5c8466b700098109edcad5f2repo syncpublic class BinTree extends InWindow 8baa3858d3f5d128a5c8466b700098109edcad5f2repo sync{ 9baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int _cyclicBufferPos; 10baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int _cyclicBufferSize = 0; 11baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int _matchMaxLen; 12baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 13baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int[] _son; 14baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int[] _hash; 15baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 16baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int _cutValue = 0xFF; 17baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int _hashMask; 18baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int _hashSizeSum = 0; 19baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 20baa3858d3f5d128a5c8466b700098109edcad5f2repo sync boolean HASH_ARRAY = true; 21baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 22baa3858d3f5d128a5c8466b700098109edcad5f2repo sync static final int kHash2Size = 1 << 10; 23baa3858d3f5d128a5c8466b700098109edcad5f2repo sync static final int kHash3Size = 1 << 16; 24baa3858d3f5d128a5c8466b700098109edcad5f2repo sync static final int kBT2HashSize = 1 << 16; 25baa3858d3f5d128a5c8466b700098109edcad5f2repo sync static final int kStartMaxLen = 1; 26baa3858d3f5d128a5c8466b700098109edcad5f2repo sync static final int kHash3Offset = kHash2Size; 27baa3858d3f5d128a5c8466b700098109edcad5f2repo sync static final int kEmptyHashValue = 0; 28baa3858d3f5d128a5c8466b700098109edcad5f2repo sync static final int kMaxValForNormalize = (1 << 30) - 1; 29baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 30baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int kNumHashDirectBytes = 0; 31baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int kMinMatchCheck = 4; 32baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int 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 52baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 53baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 54baa3858d3f5d128a5c8466b700098109edcad5f2repo sync public void Init() throws IOException 55baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 56baa3858d3f5d128a5c8466b700098109edcad5f2repo sync super.Init(); 57baa3858d3f5d128a5c8466b700098109edcad5f2repo sync for (int 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 void MovePos() throws IOException 64baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 65baa3858d3f5d128a5c8466b700098109edcad5f2repo sync if (++_cyclicBufferPos >= _cyclicBufferSize) 66baa3858d3f5d128a5c8466b700098109edcad5f2repo sync _cyclicBufferPos = 0; 67baa3858d3f5d128a5c8466b700098109edcad5f2repo sync super.MovePos(); 68baa3858d3f5d128a5c8466b700098109edcad5f2repo sync if (_pos == kMaxValForNormalize) 69baa3858d3f5d128a5c8466b700098109edcad5f2repo sync Normalize(); 70baa3858d3f5d128a5c8466b700098109edcad5f2repo sync } 71baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 72baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 73baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 74baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 75baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 76baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 77baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 78baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 79baa3858d3f5d128a5c8466b700098109edcad5f2repo sync public boolean Create(int historySize, int keepAddBufferBefore, 80baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int matchMaxLen, int keepAddBufferAfter) 81baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 82baa3858d3f5d128a5c8466b700098109edcad5f2repo sync if (historySize > kMaxValForNormalize - 256) 83baa3858d3f5d128a5c8466b700098109edcad5f2repo sync return false; 84baa3858d3f5d128a5c8466b700098109edcad5f2repo sync _cutValue = 16 + (matchMaxLen >> 1); 85baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 86baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int windowReservSize = (historySize + keepAddBufferBefore + 87baa3858d3f5d128a5c8466b700098109edcad5f2repo sync matchMaxLen + keepAddBufferAfter) / 2 + 256; 88baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 89baa3858d3f5d128a5c8466b700098109edcad5f2repo sync super.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize); 90baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 91baa3858d3f5d128a5c8466b700098109edcad5f2repo sync _matchMaxLen = matchMaxLen; 92baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 93baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int cyclicBufferSize = historySize + 1; 94baa3858d3f5d128a5c8466b700098109edcad5f2repo sync if (_cyclicBufferSize != cyclicBufferSize) 95baa3858d3f5d128a5c8466b700098109edcad5f2repo sync _son = new int[(_cyclicBufferSize = cyclicBufferSize) * 2]; 96baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 97baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int 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 int [_hashSizeSum = hs]; 116baa3858d3f5d128a5c8466b700098109edcad5f2repo sync return true; 117baa3858d3f5d128a5c8466b700098109edcad5f2repo sync } 118baa3858d3f5d128a5c8466b700098109edcad5f2repo sync public int GetMatches(int[] distances) throws IOException 119baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 120baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int 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 int offset = 0; 134baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; 135baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int cur = _bufferOffset + _pos; 136baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int maxLen = kStartMaxLen; // to avoid items for len < hashSize; 137baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int hashValue, hash2Value = 0, hash3Value = 0; 138baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 139baa3858d3f5d128a5c8466b700098109edcad5f2repo sync if (HASH_ARRAY) 140baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 141baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF); 142baa3858d3f5d128a5c8466b700098109edcad5f2repo sync hash2Value = temp & (kHash2Size - 1); 143baa3858d3f5d128a5c8466b700098109edcad5f2repo sync temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8); 144baa3858d3f5d128a5c8466b700098109edcad5f2repo sync hash3Value = temp & (kHash3Size - 1); 145baa3858d3f5d128a5c8466b700098109edcad5f2repo sync hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask; 146baa3858d3f5d128a5c8466b700098109edcad5f2repo sync } 147baa3858d3f5d128a5c8466b700098109edcad5f2repo sync else 148baa3858d3f5d128a5c8466b700098109edcad5f2repo sync hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8)); 149baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 150baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int curMatch = _hash[kFixHashSize + hashValue]; 151baa3858d3f5d128a5c8466b700098109edcad5f2repo sync if (HASH_ARRAY) 152baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 153baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int curMatch2 = _hash[hash2Value]; 154baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int 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 int ptr0 = (_cyclicBufferPos << 1) + 1; 182baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int ptr1 = (_cyclicBufferPos << 1); 183baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 184baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int 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 int 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 int delta = _pos - curMatch; 210baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int cyclicPos = ((delta <= _cyclicBufferPos) ? 211baa3858d3f5d128a5c8466b700098109edcad5f2repo sync (_cyclicBufferPos - delta) : 212baa3858d3f5d128a5c8466b700098109edcad5f2repo sync (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1; 213baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 214baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int pby1 = _bufferOffset + curMatch; 215baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int 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] & 0xFF) < (_bufferBase[cur + len] & 0xFF)) 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(int num) throws IOException 253baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 254baa3858d3f5d128a5c8466b700098109edcad5f2repo sync do 255baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 256baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int 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 int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; 270baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int cur = _bufferOffset + _pos; 271baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 272baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int hashValue; 273baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 274baa3858d3f5d128a5c8466b700098109edcad5f2repo sync if (HASH_ARRAY) 275baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 276baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF); 277baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int hash2Value = temp & (kHash2Size - 1); 278baa3858d3f5d128a5c8466b700098109edcad5f2repo sync _hash[hash2Value] = _pos; 279baa3858d3f5d128a5c8466b700098109edcad5f2repo sync temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8); 280baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int hash3Value = temp & (kHash3Size - 1); 281baa3858d3f5d128a5c8466b700098109edcad5f2repo sync _hash[kHash3Offset + hash3Value] = _pos; 282baa3858d3f5d128a5c8466b700098109edcad5f2repo sync hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask; 283baa3858d3f5d128a5c8466b700098109edcad5f2repo sync } 284baa3858d3f5d128a5c8466b700098109edcad5f2repo sync else 285baa3858d3f5d128a5c8466b700098109edcad5f2repo sync hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8)); 286baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 287baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int curMatch = _hash[kFixHashSize + hashValue]; 288baa3858d3f5d128a5c8466b700098109edcad5f2repo sync _hash[kFixHashSize + hashValue] = _pos; 289baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 290baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int ptr0 = (_cyclicBufferPos << 1) + 1; 291baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int ptr1 = (_cyclicBufferPos << 1); 292baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 293baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int len0, len1; 294baa3858d3f5d128a5c8466b700098109edcad5f2repo sync len0 = len1 = kNumHashDirectBytes; 295baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 296baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int 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 int delta = _pos - curMatch; 306baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int cyclicPos = ((delta <= _cyclicBufferPos) ? 307baa3858d3f5d128a5c8466b700098109edcad5f2repo sync (_cyclicBufferPos - delta) : 308baa3858d3f5d128a5c8466b700098109edcad5f2repo sync (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1; 309baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 310baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int pby1 = _bufferOffset + curMatch; 311baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int 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] & 0xFF) < (_bufferBase[cur + len] & 0xFF)) 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(int[] items, int numItems, int subValue) 345baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 346baa3858d3f5d128a5c8466b700098109edcad5f2repo sync for (int i = 0; i < numItems; i++) 347baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 348baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int 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 int subValue = _pos - _cyclicBufferSize; 360baa3858d3f5d128a5c8466b700098109edcad5f2repo sync NormalizeLinks(_son, _cyclicBufferSize * 2, subValue); 361baa3858d3f5d128a5c8466b700098109edcad5f2repo sync NormalizeLinks(_hash, _hashSizeSum, subValue); 362baa3858d3f5d128a5c8466b700098109edcad5f2repo sync ReduceOffsets(subValue); 363baa3858d3f5d128a5c8466b700098109edcad5f2repo sync } 364baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 365baa3858d3f5d128a5c8466b700098109edcad5f2repo sync public void SetCutValue(int cutValue) { _cutValue = cutValue; } 366baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 367baa3858d3f5d128a5c8466b700098109edcad5f2repo sync private static final int[] CrcTable = new int[256]; 368baa3858d3f5d128a5c8466b700098109edcad5f2repo sync 369baa3858d3f5d128a5c8466b700098109edcad5f2repo sync static 370baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 371baa3858d3f5d128a5c8466b700098109edcad5f2repo sync for (int i = 0; i < 256; i++) 372baa3858d3f5d128a5c8466b700098109edcad5f2repo sync { 373baa3858d3f5d128a5c8466b700098109edcad5f2repo sync int r = i; 374baa3858d3f5d128a5c8466b700098109edcad5f2repo sync for (int j = 0; j < 8; j++) 375baa3858d3f5d128a5c8466b700098109edcad5f2repo sync if ((r & 1) != 0) 376baa3858d3f5d128a5c8466b700098109edcad5f2repo sync r = (r >>> 1) ^ 0xEDB88320; 377baa3858d3f5d128a5c8466b700098109edcad5f2repo sync else 378baa3858d3f5d128a5c8466b700098109edcad5f2repo sync r >>>= 1; 379baa3858d3f5d128a5c8466b700098109edcad5f2repo sync CrcTable[i] = r; 380baa3858d3f5d128a5c8466b700098109edcad5f2repo sync } 381baa3858d3f5d128a5c8466b700098109edcad5f2repo sync } 382baa3858d3f5d128a5c8466b700098109edcad5f2repo sync} 383