misc/libphysfs/lzma/Java/SevenZip/Compression/LZ/BinTree.java
changeset 12213 bb5522e88ab2
equal deleted inserted replaced
12212:ea891871f481 12213:bb5522e88ab2
       
     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 }