misc/libphysfs/lzma/CS/7zip/Compress/LZ/LzBinTree.cs
changeset 13886 99b265e0d1d0
parent 13885 5f819b90d479
child 13887 b172a5d40eee
equal deleted inserted replaced
13885:5f819b90d479 13886:99b265e0d1d0
     1 // LzBinTree.cs
       
     2 
       
     3 using System;
       
     4 
       
     5 namespace SevenZip.Compression.LZ
       
     6 {
       
     7 	public class BinTree : InWindow, IMatchFinder
       
     8 	{
       
     9 		UInt32 _cyclicBufferPos;
       
    10 		UInt32 _cyclicBufferSize = 0;
       
    11 		UInt32 _matchMaxLen;
       
    12 
       
    13 		UInt32[] _son;
       
    14 		UInt32[] _hash;
       
    15 
       
    16 		UInt32 _cutValue = 0xFF;
       
    17 		UInt32 _hashMask;
       
    18 		UInt32 _hashSizeSum = 0;
       
    19 
       
    20 		bool HASH_ARRAY = true;
       
    21 
       
    22 		const UInt32 kHash2Size = 1 << 10;
       
    23 		const UInt32 kHash3Size = 1 << 16;
       
    24 		const UInt32 kBT2HashSize = 1 << 16;
       
    25 		const UInt32 kStartMaxLen = 1;
       
    26 		const UInt32 kHash3Offset = kHash2Size;
       
    27 		const UInt32 kEmptyHashValue = 0;
       
    28 		const UInt32 kMaxValForNormalize = ((UInt32)1 << 31) - 1;
       
    29 	
       
    30 		UInt32 kNumHashDirectBytes = 0;
       
    31 		UInt32 kMinMatchCheck = 4;
       
    32 		UInt32 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 		public new void SetStream(System.IO.Stream stream) { base.SetStream(stream); }
       
    52 		public new void ReleaseStream() { base.ReleaseStream(); }
       
    53 		
       
    54 		public new void Init()
       
    55 		{
       
    56 			base.Init();
       
    57 			for (UInt32 i = 0; i < _hashSizeSum; i++)
       
    58 				_hash[i] = kEmptyHashValue;
       
    59 			_cyclicBufferPos = 0;
       
    60 			ReduceOffsets(-1);
       
    61 		}
       
    62 
       
    63 		public new void MovePos()
       
    64 		{
       
    65 			if (++_cyclicBufferPos >= _cyclicBufferSize)
       
    66 				_cyclicBufferPos = 0;
       
    67 			base.MovePos();
       
    68 			if (_pos == kMaxValForNormalize)
       
    69 				Normalize();
       
    70 		}
       
    71 
       
    72 		public new Byte GetIndexByte(Int32 index) { return base.GetIndexByte(index); }
       
    73 
       
    74 		public new UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit)
       
    75 		{ return base.GetMatchLen(index, distance, limit); }
       
    76 
       
    77 		public new UInt32 GetNumAvailableBytes() { return base.GetNumAvailableBytes(); }
       
    78 
       
    79 		public void Create(UInt32 historySize, UInt32 keepAddBufferBefore,
       
    80 				UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
       
    81 		{
       
    82 			if (historySize > kMaxValForNormalize - 256)
       
    83 				throw new Exception();
       
    84 			_cutValue = 16 + (matchMaxLen >> 1);
       
    85 				
       
    86 			UInt32 windowReservSize = (historySize + keepAddBufferBefore +
       
    87 					matchMaxLen + keepAddBufferAfter) / 2 + 256;
       
    88 
       
    89 			base.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize);
       
    90 
       
    91 			_matchMaxLen = matchMaxLen;
       
    92 
       
    93 			UInt32 cyclicBufferSize = historySize + 1;
       
    94 			if (_cyclicBufferSize != cyclicBufferSize)
       
    95 				_son = new UInt32[(_cyclicBufferSize = cyclicBufferSize) * 2];
       
    96 
       
    97 			UInt32 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 UInt32[_hashSizeSum = hs];
       
   116 		}
       
   117 
       
   118 		public UInt32 GetMatches(UInt32[] distances)
       
   119 		{
       
   120 			UInt32 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 			UInt32 offset = 0;
       
   134 			UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
       
   135 			UInt32 cur = _bufferOffset + _pos;
       
   136 			UInt32 maxLen = kStartMaxLen; // to avoid items for len < hashSize;
       
   137 			UInt32 hashValue, hash2Value = 0, hash3Value = 0;
       
   138 
       
   139 			if (HASH_ARRAY)
       
   140 			{
       
   141 				UInt32 temp = CRC.Table[_bufferBase[cur]] ^ _bufferBase[cur + 1];
       
   142 				hash2Value = temp & (kHash2Size - 1);
       
   143 				temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8);
       
   144 				hash3Value = temp & (kHash3Size - 1);
       
   145 				hashValue = (temp ^ (CRC.Table[_bufferBase[cur + 3]] << 5)) & _hashMask;
       
   146 			}
       
   147 			else
       
   148 				hashValue = _bufferBase[cur] ^ ((UInt32)(_bufferBase[cur + 1]) << 8);
       
   149 
       
   150 			UInt32 curMatch = _hash[kFixHashSize + hashValue];
       
   151 			if (HASH_ARRAY)
       
   152 			{
       
   153 				UInt32 curMatch2 = _hash[hash2Value];
       
   154 				UInt32 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 			UInt32 ptr0 = (_cyclicBufferPos << 1) + 1;
       
   182 			UInt32 ptr1 = (_cyclicBufferPos << 1);
       
   183 
       
   184 			UInt32 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 			UInt32 count = _cutValue;
       
   201 			
       
   202 			while(true)
       
   203 			{
       
   204 				if(curMatch <= matchMinPos || count-- == 0)
       
   205 				{
       
   206 					_son[ptr0] = _son[ptr1] = kEmptyHashValue;
       
   207 					break;
       
   208 				}
       
   209 				UInt32 delta = _pos - curMatch;
       
   210 				UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ?
       
   211 							(_cyclicBufferPos - delta) :
       
   212 							(_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
       
   213 
       
   214 				UInt32 pby1 = _bufferOffset + curMatch;
       
   215 				UInt32 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] < _bufferBase[cur + len])
       
   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(UInt32 num)
       
   253 		{
       
   254 			do
       
   255 			{
       
   256 				UInt32 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 				UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
       
   270 				UInt32 cur = _bufferOffset + _pos;
       
   271 
       
   272 				UInt32 hashValue;
       
   273 
       
   274 				if (HASH_ARRAY)
       
   275 				{
       
   276 					UInt32 temp = CRC.Table[_bufferBase[cur]] ^ _bufferBase[cur + 1];
       
   277 					UInt32 hash2Value = temp & (kHash2Size - 1);
       
   278 					_hash[hash2Value] = _pos;
       
   279 					temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8);
       
   280 					UInt32 hash3Value = temp & (kHash3Size - 1);
       
   281 					_hash[kHash3Offset + hash3Value] = _pos;
       
   282 					hashValue = (temp ^ (CRC.Table[_bufferBase[cur + 3]] << 5)) & _hashMask;
       
   283 				}
       
   284 				else
       
   285 					hashValue = _bufferBase[cur] ^ ((UInt32)(_bufferBase[cur + 1]) << 8);
       
   286 
       
   287 				UInt32 curMatch = _hash[kFixHashSize + hashValue];
       
   288 				_hash[kFixHashSize + hashValue] = _pos;
       
   289 
       
   290 				UInt32 ptr0 = (_cyclicBufferPos << 1) + 1;
       
   291 				UInt32 ptr1 = (_cyclicBufferPos << 1);
       
   292 
       
   293 				UInt32 len0, len1;
       
   294 				len0 = len1 = kNumHashDirectBytes;
       
   295 
       
   296 				UInt32 count = _cutValue;
       
   297 				while (true)
       
   298 				{
       
   299 					if (curMatch <= matchMinPos || count-- == 0)
       
   300 					{
       
   301 						_son[ptr0] = _son[ptr1] = kEmptyHashValue;
       
   302 						break;
       
   303 					}
       
   304 
       
   305 					UInt32 delta = _pos - curMatch;
       
   306 					UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ?
       
   307 								(_cyclicBufferPos - delta) :
       
   308 								(_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
       
   309 
       
   310 					UInt32 pby1 = _bufferOffset + curMatch;
       
   311 					UInt32 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] < _bufferBase[cur + len])
       
   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(UInt32[] items, UInt32 numItems, UInt32 subValue)
       
   345 		{
       
   346 			for (UInt32 i = 0; i < numItems; i++)
       
   347 			{
       
   348 				UInt32 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 			UInt32 subValue = _pos - _cyclicBufferSize;
       
   360 			NormalizeLinks(_son, _cyclicBufferSize * 2, subValue);
       
   361 			NormalizeLinks(_hash, _hashSizeSum, subValue);
       
   362 			ReduceOffsets((Int32)subValue);
       
   363 		}
       
   364 
       
   365 		public void SetCutValue(UInt32 cutValue) { _cutValue = cutValue; }
       
   366 	}
       
   367 }