encoder.java

LZMA 是 7-Zip 程序中 7z 格式 的默认压缩算法。LZMA 能提供给用户极高的压缩比及较快的压缩速度

	int Backward(int[] backRes, int cur)
	{
		_optimumEndIndex = cur;
		int posMem = _optimum[cur].PosPrev;
		int backMem = _optimum[cur].BackPrev;
		do
		{
			if (_optimum[cur].Prev1IsChar)
			{
				_optimum[posMem].MakeAsChar();
				_optimum[posMem].PosPrev = posMem - 1;
				if (_optimum[cur].Prev2)
				{
					_optimum[posMem - 1].Prev1IsChar = false;
					_optimum[posMem - 1].PosPrev = _optimum[cur].PosPrev2;
					_optimum[posMem - 1].BackPrev = _optimum[cur].BackPrev2;
				}
			}
			int posPrev = posMem;
			int backCur = backMem;
			
			backMem = _optimum[posPrev].BackPrev;
			posMem = _optimum[posPrev].PosPrev;
			
			_optimum[posPrev].BackPrev = backCur;
			_optimum[posPrev].PosPrev = cur;
			cur = posPrev;
		}
		while (cur > 0);
		backRes[0] = _optimum[0].BackPrev;
		_optimumCurrentIndex = _optimum[0].PosPrev;
		return _optimumCurrentIndex;
	}
	
	int[] reps = new int[Base.kNumRepDistances];
	int[] repLens = new int[Base.kNumRepDistances];
	
	int GetOptimum(int position, int []backRes) throws IOException
	{
		if (_optimumEndIndex != _optimumCurrentIndex)
		{
			int lenRes = _optimum[_optimumCurrentIndex].PosPrev - _optimumCurrentIndex;
			backRes[0] = _optimum[_optimumCurrentIndex].BackPrev;
			_optimumCurrentIndex = _optimum[_optimumCurrentIndex].PosPrev;
			return lenRes;
		}
		_optimumCurrentIndex = 0;
		_optimumEndIndex = 0; // test it;
		
		int lenMain;
		if (!_longestMatchWasFound)
		{
			lenMain = ReadMatchDistances();
		}
		else
		{
			lenMain = _longestMatchLength;
			_longestMatchWasFound = false;
		}
		
		int repMaxIndex = 0;
		int i;
		for (i = 0; i < Base.kNumRepDistances; i++)
		{
			reps[i] = _repDistances[i];
			repLens[i] = _matchFinder.GetMatchLen(0 - 1, reps[i], Base.kMatchMaxLen);
			if (i == 0 || repLens[i] > repLens[repMaxIndex])
				repMaxIndex = i;
		}
		if (repLens[repMaxIndex] >= _numFastBytes)
		{
			backRes[0] = repMaxIndex;
			int lenRes = repLens[repMaxIndex];
			MovePos(lenRes - 1);
			return lenRes;
		}
		
		if (lenMain >= _numFastBytes)
		{
			int backMain = (lenMain < _numFastBytes) ? _matchDistances[lenMain] :
				_matchDistances[_numFastBytes];
			backRes[0] = backMain + Base.kNumRepDistances;
			MovePos(lenMain - 1);
			return lenMain;
		}
		byte currentByte = _matchFinder.GetIndexByte(0 - 1);
		
		_optimum[0].State = _state;
		
		byte matchByte;
		
		matchByte = _matchFinder.GetIndexByte(0 - _repDistances[0] - 1 - 1);
		
		int posState = (position & _posStateMask);
		
		_optimum[1].Price =
				SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_isMatch[(_state << Base.kNumPosStatesBitsMax) + posState]) +
				_literalEncoder.GetSubCoder(position, _previousByte).GetPrice(!Base.StateIsCharState(_state), matchByte, currentByte);
		_optimum[1].MakeAsChar();
		
		_optimum[1].PosPrev = 0;
		
		_optimum[0].Backs0 = reps[0];
		_optimum[0].Backs1 = reps[1];
		_optimum[0].Backs2 = reps[2];
		_optimum[0].Backs3 = reps[3];
		
		
		int matchPrice = SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isMatch[(_state << Base.kNumPosStatesBitsMax) + posState]);
		int repMatchPrice = matchPrice + SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isRep[_state]);
		
		if (matchByte == currentByte)
		{
			int shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState);
			if (shortRepPrice < _optimum[1].Price)
			{
				_optimum[1].Price = shortRepPrice;
				_optimum[1].MakeAsShortRep();
			}
		}
		if (lenMain < 2)
		{
			backRes[0] = _optimum[1].BackPrev;
			return 1;
		}
		
		
		int normalMatchPrice = matchPrice + SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_isRep[_state]);
		
		if (lenMain <= repLens[repMaxIndex])
			lenMain = 0;
		
		int len;
		for (len = 2; len <= lenMain; len++)
		{
			_optimum[len].PosPrev = 0;
			_optimum[len].BackPrev = _matchDistances[len] + Base.kNumRepDistances;
			_optimum[len].Price = normalMatchPrice +
					GetPosLenPrice(_matchDistances[len], len, posState);
			_optimum[len].Prev1IsChar = false;
		}
		
		if (lenMain < repLens[repMaxIndex])
			lenMain = repLens[repMaxIndex];
		
		for (; len <= lenMain; len++)
			_optimum[len].Price = kIfinityPrice;
		
		for (i = 0; i < Base.kNumRepDistances; i++)
		{
			int repLen = repLens[i];
			for (int lenTest = 2; lenTest <= repLen; lenTest++)
			{
				int curAndLenPrice = repMatchPrice + GetRepPrice(i, lenTest, _state, posState);
				Optimal optimum = _optimum[lenTest];
				if (curAndLenPrice < optimum.Price)
				{
					optimum.Price = curAndLenPrice;
					optimum.PosPrev = 0;
					optimum.BackPrev = i;
					optimum.Prev1IsChar = false;
				}
			}
		}
		
		int cur = 0;
		int lenEnd = lenMain;
		
		while (true)
		{
			cur++;
			if (cur == lenEnd)
			{
				return Backward(backRes, cur);
			}
			position++;
			int posPrev = _optimum[cur].PosPrev;
			int state;
			if (_optimum[cur].Prev1IsChar)
			{
				posPrev--;
				if (_optimum[cur].Prev2)
				{
					state = _optimum[_optimum[cur].PosPrev2].State;
					if (_optimum[cur].BackPrev2 < Base.kNumRepDistances)
						state = Base.StateUpdateRep(state);
					else
						state = Base.StateUpdateMatch(state);
				}
				else
					state = _optimum[posPrev].State;
				state = Base.StateUpdateChar(state);
			}
			else
				state = _optimum[posPrev].State;
			if (posPrev == cur - 1)
			{
				if (_optimum[cur].IsShortRep())
					state = Base.StateUpdateShortRep(state);
				else
					state = Base.StateUpdateChar(state);
			}
			else
			{
				int pos;
				if (_optimum[cur].Prev1IsChar && _optimum[cur].Prev2)
				{
					posPrev = _optimum[cur].PosPrev2;
					pos = _optimum[cur].BackPrev2;
					state = Base.StateUpdateRep(state);
				}
				else
				{
					pos = _optimum[cur].BackPrev;
					if (pos < Base.kNumRepDistances)
						state = Base.StateUpdateRep(state);
					else
						state = Base.StateUpdateMatch(state);
				}
				Optimal opt = _optimum[posPrev];
				if (pos < Base.kNumRepDistances)
				{
					if (pos == 0)
					{
						reps[0] = opt.Backs0;
						reps[1] = opt.Backs1;
						reps[2] = opt.Backs2;
						reps[3] = opt.Backs3;
					}
					else if (pos == 1)
					{
						reps[0] = opt.Backs1;
						reps[1] = opt.Backs0;
						reps[2] = opt.Backs2;
						reps[3] = opt.Backs3;
					}
					else if (pos == 2)
					{
						reps[0] = opt.Backs2;
						reps[1] = opt.Backs0;
						reps[2] = opt.Backs1;
						reps[3] = opt.Backs3;
					}
					else
					{
						reps[0] = opt.Backs3;
						reps[1] = opt.Backs0;
						reps[2] = opt.Backs1;
						reps[3] = opt.Backs2;
					}
				}
				else
				{
					reps[0] = (pos - Base.kNumRepDistances);
					reps[1] = opt.Backs0;
					reps[2] = opt.Backs1;
					reps[3] = opt.Backs2;
				}
			}
			_optimum[cur].State = state;
			_optimum[cur].Backs0 = reps[0];
			_optimum[cur].Backs1 = reps[1];
			_optimum[cur].Backs2 = reps[2];
			_optimum[cur].Backs3 = reps[3];
			int newLen = ReadMatchDistances();
			if (newLen >= _numFastBytes)
			{
				_longestMatchLength = newLen;
				_longestMatchWasFound = true;
				return Backward(backRes, cur);
			}
			int curPrice = _optimum[cur].Price;
			
			currentByte = _matchFinder.GetIndexByte(0 - 1);
			matchByte = _matchFinder.GetIndexByte(0 - reps[0] - 1 - 1);
			
			posState = (position & _posStateMask);
			
			int curAnd1Price = curPrice +
					SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_isMatch[(state << Base.kNumPosStatesBitsMax) + posState]) +
					_literalEncoder.GetSubCoder(position, _matchFinder.GetIndexByte(0 - 2)).
					GetPrice(!Base.StateIsCharState(state), matchByte, currentByte);
			
			Optimal nextOptimum = _optimum[cur + 1];
			
			boolean nextIsChar = false;
			if (curAnd1Price < nextOptimum.Price)
			{
				nextOptimum.Price = curAnd1Price;
				nextOptimum.PosPrev = cur;
				nextOptimum.MakeAsChar();
				nextIsChar = true;
			}
			
			matchPrice = curPrice + SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isMatch[(state << Base.kNumPosStatesBitsMax) + posState]);
			repMatchPrice = matchPrice + SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isRep[state]);
			
			if (matchByte == currentByte &&
					!(nextOptimum.PosPrev < cur && nextOptimum.BackPrev == 0))
			{
				int shortRepPrice = repMatchPrice + GetRepLen1Price(state, posState);
				if (shortRepPrice <= nextOptimum.Price)
				{
					nextOptimum.Price = shortRepPrice;
					nextOptimum.PosPrev = cur;
					nextOptimum.MakeAsShortRep();
					// nextIsChar = false;
				}
			}
			
			int numAvailableBytesFull = _matchFinder.GetNumAvailableBytes() + 1;
			numAvailableBytesFull = Math.min(kNumOpts - 1 - cur, numAvailableBytesFull);
			int numAvailableBytes = numAvailableBytesFull;
			
			if (numAvailableBytes < 2)
				continue;
			if (numAvailableBytes > _numFastBytes)
				numAvailableBytes = _numFastBytes;
			if (numAvailableBytes >= 3 && !nextIsChar)
			{
				int backOffset = reps[0] + 1;
				int temp;
				for (temp = 1; temp < numAvailableBytes; temp++)
					// if (data[temp] != data[(size_t)temp - backOffset])
					if (_matchFinder.GetIndexByte(temp - 1) != _matchFinder.GetIndexByte(temp - backOffset - 1))
						break;
				int lenTest2 = temp - 1;
				if (lenTest2 >= 2)
				{
					int state2 = Base.StateUpdateChar(state);
					int posStateNext = (position + 1) & _posStateMask;
					int nextRepMatchPrice = curAnd1Price +
							SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isMatch[(state2 << Base.kNumPosStatesBitsMax) + posStateNext]) +
							SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isRep[state2]);
					// for (; lenTest2 >= 2; lenTest2--)
					{
						while (lenEnd < cur + 1 + lenTest2)
							_optimum[++lenEnd].Price = kIfinityPrice;
						int curAndLenPrice = nextRepMatchPrice + GetRepPrice(
								0, lenTest2, state2, posStateNext);
						Optimal optimum = _optimum[cur + 1 + lenTest2];
						if (curAndLenPrice < optimum.Price)
						{
							optimum.Price = curAndLenPrice;
							optimum.PosPrev = cur + 1;
							optimum.BackPrev = 0;
							optimum.Prev1IsChar = true;
							optimum.Prev2 = false;
						}
					}
				}
			}
			for (int repIndex = 0; repIndex < Base.kNumRepDistances; repIndex++)
			{
				// int repLen = _matchFinder->GetMatchLen(0 - 1, reps[repIndex], newLen); // test it;
				int backOffset = reps[repIndex] + 1;
				if (_matchFinder.GetIndexByte(-1) !=
						_matchFinder.GetIndexByte(-1 - backOffset) ||
						_matchFinder.GetIndexByte(0) !=
						_matchFinder.GetIndexByte(0 - backOffset))
					continue;
				int lenTest;
				for (lenTest = 2; lenTest < numAvailableBytes; lenTest++)
					if (_matchFinder.GetIndexByte(lenTest - 1) !=
						_matchFinder.GetIndexByte(lenTest - 1 - backOffset))
						break;
				int lenTestTemp = lenTest;
				do
				{
					while (lenEnd < cur + lenTest)
						_optimum[++lenEnd].Price = kIfinityPrice;
					int curAndLenPrice = repMatchPrice + GetRepPrice(repIndex, lenTest, state, posState);
					Optimal optimum = _optimum[cur + lenTest];
					if (curAndLenPrice < optimum.Price)
					{
						optimum.Price = curAndLenPrice;
						optimum.PosPrev = cur;
						optimum.BackPrev = repIndex;
						optimum.Prev1IsChar = false;
					}
				}
				while(--lenTest >= 2);
				lenTest = lenTestTemp;
				
				if (_maxMode)
				{
					int lenTest2 = lenTest + 1;
					int limit = Math.min(numAvailableBytesFull, lenTest2 + _numFastBytes);
					for (; lenTest2 < limit; lenTest2++)
						if (_matchFinder.GetIndexByte(lenTest2 - 1) !=
							_matchFinder.GetIndexByte(lenTest2 - 1 - backOffset))
							break;
					lenTest2 -= lenTest + 1;
					if (lenTest2 >= 2)
					{
						int state2 = Base.StateUpdateRep(state);
						int posStateNext = (position + lenTest) & _posStateMask;
						int curAndLenCharPrice =
								repMatchPrice + GetRepPrice(repIndex, lenTest, state, posState) +
								SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_isMatch[(state2 << Base.kNumPosStatesBitsMax) + posStateNext]) +
								_literalEncoder.GetSubCoder(position + lenTest,
								_matchFinder.GetIndexByte(lenTest - 1 - 1)).GetPrice(true,
								_matchFinder.GetIndexByte(lenTest - 1 - backOffset),
								_matchFinder.GetIndexByte(lenTest - 1));
						state2 = Base.StateUpdateChar(state2);
						posStateNext = (position + lenTest + 1) & _posStateMask;
						int nextMatchPrice = curAndLenCharPrice +
								SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isMatch[(state2 << Base.kNumPosStatesBitsMax) + posStateNext]);
						int nextRepMatchPrice = nextMatchPrice +
								SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isRep[state2]);
						
						// for(; lenTest2 >= 2; lenTest2--)
						{
							int offset = lenTest + 1 + lenTest2;
							while(lenEnd < cur + offset)
								_optimum[++lenEnd].Price = kIfinityPrice;
							int curAndLenPrice = nextRepMatchPrice + GetRepPrice(0, lenTest2, state2, posStateNext);
							Optimal optimum = _optimum[cur + offset];
							if (curAndLenPrice < optimum.Price)
							{
								optimum.Price = curAndLenPrice;
								optimum.PosPrev = cur + lenTest + 1;
								optimum.BackPrev = 0;
								optimum.Prev1IsChar = true;
								optimum.Prev2 = true;
								optimum.PosPrev2 = cur;
								optimum.BackPrev2 = repIndex;
							}
						}
					}
				}
			}
			
			//    for(UInt32 lenTest = 2; lenTest <= newLen; lenTest++)
			if (newLen > numAvailableBytes)
				newLen = numAvailableBytes;
			if (newLen >= 2)
			{
				if (newLen == 2 && _matchDistances[2] >= 0x80)
					continue;
				normalMatchPrice = matchPrice + SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_isRep[state]);
				while (lenEnd < cur + newLen)
					_optimum[++lenEnd].Price = kIfinityPrice;
				
				for (int lenTest = newLen; lenTest >= 2; lenTest--)
				{
					int curBack = _matchDistances[lenTest];
					int curAndLenPrice = normalMatchPrice + GetPosLenPrice(curBack, lenTest, posState);
					Optimal optimum = _optimum[cur + lenTest];
					if (curAndLenPrice < optimum.Price)
					{
						optimum.Price = curAndLenPrice;
						optimum.PosPrev = cur;
						optimum.BackPrev = curBack + Base.kNumRepDistances;
						optimum.Prev1IsChar = false;
					}
					
					if (_maxMode && (lenTest == newLen || curBack != _matchDistances[lenTest + 1]))
					{
						int backOffset = curBack + 1;
						int lenTest2 = lenTest + 1;
						int limit = Math.min(numAvailableBytesFull, lenTest2 + _numFastBytes);
						for (; lenTest2 < limit; lenTest2++)
							if (_matchFinder.GetIndexByte(lenTest2 - 1) != _matchFinder.GetIndexByte(lenTest2 - backOffset - 1))
								break;
						lenTest2 -= lenTest + 1;
						if (lenTest2 >= 2)
						{
							int state2 = Base.StateUpdateMatch(state);
							int posStateNext = (position + lenTest) & _posStateMask;
							int curAndLenCharPrice = curAndLenPrice +
									SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_isMatch[(state2 << Base.kNumPosStatesBitsMax) + posStateNext]) +
									_literalEncoder.GetSubCoder(position + lenTest,
									_matchFinder.GetIndexByte(lenTest - 1 - 1)).
									GetPrice(true,
									_matchFinder.GetIndexByte(lenTest - backOffset - 1),
									_matchFinder.GetIndexByte(lenTest - 1)
									);
							state2 = Base.StateUpdateChar(state2);
							posStateNext = (position + lenTest + 1) & _posStateMask;
							int nextMatchPrice = curAndLenCharPrice + SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isMatch[(state2 << Base.kNumPosStatesBitsMax) + posStateNext]);
							int nextRepMatchPrice = nextMatchPrice + SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isRep[state2]);
							
							// for(; lenTest2 >= 2; lenTest2--)
							{
								int offset = lenTest + 1 + lenTest2;
								while (lenEnd < cur + offset)
									_optimum[++lenEnd].Price = kIfinityPrice;
								curAndLenPrice = nextRepMatchPrice + GetRepPrice(
										0, lenTest2, state2, posStateNext);
								optimum = _optimum[cur + offset];
								if (curAndLenPrice < optimum.Price)
								{
									optimum.Price = curAndLenPrice;
									optimum.PosPrev = cur + lenTest + 1;
									optimum.BackPrev = 0;
									optimum.Prev1IsChar = true;
									optimum.Prev2 = true;
									optimum.PosPrev2 = cur;
									optimum.BackPrev2 = curBack + Base.kNumRepDistances;