// LZ.BinTree | |
package SevenZip.Compression.LZ; | |
import java.io.IOException; | |
public class BinTree extends InWindow | |
{ | |
int _cyclicBufferPos; | |
int _cyclicBufferSize = 0; | |
int _matchMaxLen; | |
int[] _son; | |
int[] _hash; | |
int _cutValue = 0xFF; | |
int _hashMask; | |
int _hashSizeSum = 0; | |
boolean HASH_ARRAY = true; | |
static final int kHash2Size = 1 << 10; | |
static final int kHash3Size = 1 << 16; | |
static final int kBT2HashSize = 1 << 16; | |
static final int kStartMaxLen = 1; | |
static final int kHash3Offset = kHash2Size; | |
static final int kEmptyHashValue = 0; | |
static final int kMaxValForNormalize = (1 << 30) - 1; | |
int kNumHashDirectBytes = 0; | |
int kMinMatchCheck = 4; | |
int kFixHashSize = kHash2Size + kHash3Size; | |
public void SetType(int numHashBytes) | |
{ | |
HASH_ARRAY = (numHashBytes > 2); | |
if (HASH_ARRAY) | |
{ | |
kNumHashDirectBytes = 0; | |
kMinMatchCheck = 4; | |
kFixHashSize = kHash2Size + kHash3Size; | |
} | |
else | |
{ | |
kNumHashDirectBytes = 2; | |
kMinMatchCheck = 2 + 1; | |
kFixHashSize = 0; | |
} | |
} | |
public void Init() throws IOException | |
{ | |
super.Init(); | |
for (int i = 0; i < _hashSizeSum; i++) | |
_hash[i] = kEmptyHashValue; | |
_cyclicBufferPos = 0; | |
ReduceOffsets(-1); | |
} | |
public void MovePos() throws IOException | |
{ | |
if (++_cyclicBufferPos >= _cyclicBufferSize) | |
_cyclicBufferPos = 0; | |
super.MovePos(); | |
if (_pos == kMaxValForNormalize) | |
Normalize(); | |
} | |
public boolean Create(int historySize, int keepAddBufferBefore, | |
int matchMaxLen, int keepAddBufferAfter) | |
{ | |
if (historySize > kMaxValForNormalize - 256) | |
return false; | |
_cutValue = 16 + (matchMaxLen >> 1); | |
int windowReservSize = (historySize + keepAddBufferBefore + | |
matchMaxLen + keepAddBufferAfter) / 2 + 256; | |
super.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize); | |
_matchMaxLen = matchMaxLen; | |
int cyclicBufferSize = historySize + 1; | |
if (_cyclicBufferSize != cyclicBufferSize) | |
_son = new int[(_cyclicBufferSize = cyclicBufferSize) * 2]; | |
int hs = kBT2HashSize; | |
if (HASH_ARRAY) | |
{ | |
hs = historySize - 1; | |
hs |= (hs >> 1); | |
hs |= (hs >> 2); | |
hs |= (hs >> 4); | |
hs |= (hs >> 8); | |
hs >>= 1; | |
hs |= 0xFFFF; | |
if (hs > (1 << 24)) | |
hs >>= 1; | |
_hashMask = hs; | |
hs++; | |
hs += kFixHashSize; | |
} | |
if (hs != _hashSizeSum) | |
_hash = new int [_hashSizeSum = hs]; | |
return true; | |
} | |
public int GetMatches(int[] distances) throws IOException | |
{ | |
int lenLimit; | |
if (_pos + _matchMaxLen <= _streamPos) | |
lenLimit = _matchMaxLen; | |
else | |
{ | |
lenLimit = _streamPos - _pos; | |
if (lenLimit < kMinMatchCheck) | |
{ | |
MovePos(); | |
return 0; | |
} | |
} | |
int offset = 0; | |
int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; | |
int cur = _bufferOffset + _pos; | |
int maxLen = kStartMaxLen; // to avoid items for len < hashSize; | |
int hashValue, hash2Value = 0, hash3Value = 0; | |
if (HASH_ARRAY) | |
{ | |
int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF); | |
hash2Value = temp & (kHash2Size - 1); | |
temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8); | |
hash3Value = temp & (kHash3Size - 1); | |
hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask; | |
} | |
else | |
hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8)); | |
int curMatch = _hash[kFixHashSize + hashValue]; | |
if (HASH_ARRAY) | |
{ | |
int curMatch2 = _hash[hash2Value]; | |
int curMatch3 = _hash[kHash3Offset + hash3Value]; | |
_hash[hash2Value] = _pos; | |
_hash[kHash3Offset + hash3Value] = _pos; | |
if (curMatch2 > matchMinPos) | |
if (_bufferBase[_bufferOffset + curMatch2] == _bufferBase[cur]) | |
{ | |
distances[offset++] = maxLen = 2; | |
distances[offset++] = _pos - curMatch2 - 1; | |
} | |
if (curMatch3 > matchMinPos) | |
if (_bufferBase[_bufferOffset + curMatch3] == _bufferBase[cur]) | |
{ | |
if (curMatch3 == curMatch2) | |
offset -= 2; | |
distances[offset++] = maxLen = 3; | |
distances[offset++] = _pos - curMatch3 - 1; | |
curMatch2 = curMatch3; | |
} | |
if (offset != 0 && curMatch2 == curMatch) | |
{ | |
offset -= 2; | |
maxLen = kStartMaxLen; | |
} | |
} | |
_hash[kFixHashSize + hashValue] = _pos; | |
int ptr0 = (_cyclicBufferPos << 1) + 1; | |
int ptr1 = (_cyclicBufferPos << 1); | |
int len0, len1; | |
len0 = len1 = kNumHashDirectBytes; | |
if (kNumHashDirectBytes != 0) | |
{ | |
if (curMatch > matchMinPos) | |
{ | |
if (_bufferBase[_bufferOffset + curMatch + kNumHashDirectBytes] != | |
_bufferBase[cur + kNumHashDirectBytes]) | |
{ | |
distances[offset++] = maxLen = kNumHashDirectBytes; | |
distances[offset++] = _pos - curMatch - 1; | |
} | |
} | |
} | |
int count = _cutValue; | |
while (true) | |
{ | |
if (curMatch <= matchMinPos || count-- == 0) | |
{ | |
_son[ptr0] = _son[ptr1] = kEmptyHashValue; | |
break; | |
} | |
int delta = _pos - curMatch; | |
int cyclicPos = ((delta <= _cyclicBufferPos) ? | |
(_cyclicBufferPos - delta) : | |
(_cyclicBufferPos - delta + _cyclicBufferSize)) << 1; | |
int pby1 = _bufferOffset + curMatch; | |
int len = Math.min(len0, len1); | |
if (_bufferBase[pby1 + len] == _bufferBase[cur + len]) | |
{ | |
while(++len != lenLimit) | |
if (_bufferBase[pby1 + len] != _bufferBase[cur + len]) | |
break; | |
if (maxLen < len) | |
{ | |
distances[offset++] = maxLen = len; | |
distances[offset++] = delta - 1; | |
if (len == lenLimit) | |
{ | |
_son[ptr1] = _son[cyclicPos]; | |
_son[ptr0] = _son[cyclicPos + 1]; | |
break; | |
} | |
} | |
} | |
if ((_bufferBase[pby1 + len] & 0xFF) < (_bufferBase[cur + len] & 0xFF)) | |
{ | |
_son[ptr1] = curMatch; | |
ptr1 = cyclicPos + 1; | |
curMatch = _son[ptr1]; | |
len1 = len; | |
} | |
else | |
{ | |
_son[ptr0] = curMatch; | |
ptr0 = cyclicPos; | |
curMatch = _son[ptr0]; | |
len0 = len; | |
} | |
} | |
MovePos(); | |
return offset; | |
} | |
public void Skip(int num) throws IOException | |
{ | |
do | |
{ | |
int lenLimit; | |
if (_pos + _matchMaxLen <= _streamPos) | |
lenLimit = _matchMaxLen; | |
else | |
{ | |
lenLimit = _streamPos - _pos; | |
if (lenLimit < kMinMatchCheck) | |
{ | |
MovePos(); | |
continue; | |
} | |
} | |
int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; | |
int cur = _bufferOffset + _pos; | |
int hashValue; | |
if (HASH_ARRAY) | |
{ | |
int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF); | |
int hash2Value = temp & (kHash2Size - 1); | |
_hash[hash2Value] = _pos; | |
temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8); | |
int hash3Value = temp & (kHash3Size - 1); | |
_hash[kHash3Offset + hash3Value] = _pos; | |
hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask; | |
} | |
else | |
hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8)); | |
int curMatch = _hash[kFixHashSize + hashValue]; | |
_hash[kFixHashSize + hashValue] = _pos; | |
int ptr0 = (_cyclicBufferPos << 1) + 1; | |
int ptr1 = (_cyclicBufferPos << 1); | |
int len0, len1; | |
len0 = len1 = kNumHashDirectBytes; | |
int count = _cutValue; | |
while (true) | |
{ | |
if (curMatch <= matchMinPos || count-- == 0) | |
{ | |
_son[ptr0] = _son[ptr1] = kEmptyHashValue; | |
break; | |
} | |
int delta = _pos - curMatch; | |
int cyclicPos = ((delta <= _cyclicBufferPos) ? | |
(_cyclicBufferPos - delta) : | |
(_cyclicBufferPos - delta + _cyclicBufferSize)) << 1; | |
int pby1 = _bufferOffset + curMatch; | |
int len = Math.min(len0, len1); | |
if (_bufferBase[pby1 + len] == _bufferBase[cur + len]) | |
{ | |
while (++len != lenLimit) | |
if (_bufferBase[pby1 + len] != _bufferBase[cur + len]) | |
break; | |
if (len == lenLimit) | |
{ | |
_son[ptr1] = _son[cyclicPos]; | |
_son[ptr0] = _son[cyclicPos + 1]; | |
break; | |
} | |
} | |
if ((_bufferBase[pby1 + len] & 0xFF) < (_bufferBase[cur + len] & 0xFF)) | |
{ | |
_son[ptr1] = curMatch; | |
ptr1 = cyclicPos + 1; | |
curMatch = _son[ptr1]; | |
len1 = len; | |
} | |
else | |
{ | |
_son[ptr0] = curMatch; | |
ptr0 = cyclicPos; | |
curMatch = _son[ptr0]; | |
len0 = len; | |
} | |
} | |
MovePos(); | |
} | |
while (--num != 0); | |
} | |
void NormalizeLinks(int[] items, int numItems, int subValue) | |
{ | |
for (int i = 0; i < numItems; i++) | |
{ | |
int value = items[i]; | |
if (value <= subValue) | |
value = kEmptyHashValue; | |
else | |
value -= subValue; | |
items[i] = value; | |
} | |
} | |
void Normalize() | |
{ | |
int subValue = _pos - _cyclicBufferSize; | |
NormalizeLinks(_son, _cyclicBufferSize * 2, subValue); | |
NormalizeLinks(_hash, _hashSizeSum, subValue); | |
ReduceOffsets(subValue); | |
} | |
public void SetCutValue(int cutValue) { _cutValue = cutValue; } | |
private static final int[] CrcTable = new int[256]; | |
static | |
{ | |
for (int i = 0; i < 256; i++) | |
{ | |
int r = i; | |
for (int j = 0; j < 8; j++) | |
if ((r & 1) != 0) | |
r = (r >>> 1) ^ 0xEDB88320; | |
else | |
r >>>= 1; | |
CrcTable[i] = r; | |
} | |
} | |
} |