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 }