encoder.java

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

package SevenZip.Compression.LZMA;

import SevenZip.Compression.RangeCoder.BitTreeEncoder;
import SevenZip.Compression.LZMA.Base;
import SevenZip.Compression.LZ.BinTree;
import SevenZip.ICodeProgress;
import java.io.IOException;

public class Encoder
{
	public static final int EMatchFinderTypeBT2 = 0;
	public static final int EMatchFinderTypeBT4 = 1;
	public static final int EMatchFinderTypeBT4B = 2;
	
	
	static final int kIfinityPrice = 0xFFFFFFF;
	
	static byte[] g_FastPos = new byte[1024];
	
	static
	{
		int kFastSlots = 20;
		int c = 2;
		g_FastPos[0] = 0;
		g_FastPos[1] = 1;
		for (int slotFast = 2; slotFast < kFastSlots; slotFast++)
		{
			int k = (1 << ((slotFast >> 1) - 1));
			for (int j = 0; j < k; j++, c++)
				g_FastPos[c] = (byte)slotFast;
		}
	}
	
	static int GetPosSlot(int pos)
	{
		if (pos < (1 << 10))
			return g_FastPos[pos];
		if (pos < (1 << 19))
			return g_FastPos[pos >> 9] + 18;
		return g_FastPos[pos >> 18] + 36;
	}
	
	static int GetPosSlot2(int pos)
	{
		if (pos < (1 << 16))
			return g_FastPos[pos >> 6] + 12;
		if (pos < (1 << 25))
			return g_FastPos[pos >> 15] + 30;
		return g_FastPos[pos >> 24] + 48;
	}
	
	int _state = Base.StateInit();
	byte _previousByte;
	int[] _repDistances = new int[Base.kNumRepDistances];
	
	void BaseInit()
	{
		_state = Base.StateInit();
		_previousByte = 0;
		for (int i = 0; i < Base.kNumRepDistances; i++)
			_repDistances[i] = 0;
	}
	
	static final int kDefaultDictionaryLogSize = 20;
	static final int kNumFastBytesDefault = 0x20;
	
	class LiteralEncoder
	{
		class Encoder2
		{
			short[] m_Encoders = new short[0x300];
			
			public void Init()
			{
				SevenZip.Compression.RangeCoder.Encoder.InitBitModels(m_Encoders);
			}
			
			public void Encode(SevenZip.Compression.RangeCoder.Encoder rangeEncoder, byte symbol) throws IOException
			{
				int context = 1;
				for (int i = 7; i >= 0; i--)
				{
					int bit = ((symbol >> i) & 1);
					rangeEncoder.Encode(m_Encoders, context, bit);
					context = (context << 1) | bit;
				}
			}
			
			public void EncodeMatched(SevenZip.Compression.RangeCoder.Encoder rangeEncoder, byte matchByte, byte symbol) throws IOException
			{
				int context = 1;
				boolean same = true;
				for (int i = 7; i >= 0; i--)
				{
					int bit = ((symbol >> i) & 1);
					int state = context;
					if (same)
					{
						int matchBit = ((matchByte >> i) & 1);
						state += ((1 + matchBit) << 8);
						same = (matchBit == bit);
					}
					rangeEncoder.Encode(m_Encoders, state, bit);
					context = (context << 1) | bit;
				}
			}
			
			public int GetPrice(boolean matchMode, byte matchByte, byte symbol)
			{
				int price = 0;
				int context = 1;
				int i = 7;
				if (matchMode)
				{
					for (; i >= 0; i--)
					{
						int matchBit = (matchByte >> i) & 1;
						int bit = (symbol >> i) & 1;
						price += SevenZip.Compression.RangeCoder.Encoder.GetPrice(m_Encoders[((1 + matchBit) << 8) + context], bit);
						context = (context << 1) | bit;
						if (matchBit != bit)
						{
							i--;
							break;
						}
					}
				}
				for (; i >= 0; i--)
				{
					int bit = (symbol >> i) & 1;
					price += SevenZip.Compression.RangeCoder.Encoder.GetPrice(m_Encoders[context], bit);
					context = (context << 1) | bit;
				}
				return price;
			}
		}
		
		Encoder2[] m_Coders;
		int m_NumPrevBits;
		int m_NumPosBits;
		int m_PosMask;
		
		public void Create(int numPosBits, int numPrevBits)
		{
			if (m_Coders != null && m_NumPrevBits == numPrevBits && m_NumPosBits == numPosBits)
				return;
			m_NumPosBits = numPosBits;
			m_PosMask = (1 << numPosBits) - 1;
			m_NumPrevBits = numPrevBits;
			int numStates = 1 << (m_NumPrevBits + m_NumPosBits);
			m_Coders = new Encoder2[numStates];
			for (int i = 0; i < numStates; i++)
				m_Coders[i] = new Encoder2();
		}
		
		public void Init()
		{
			int numStates = 1 << (m_NumPrevBits + m_NumPosBits);
			for (int i = 0; i < numStates; i++)
				m_Coders[i].Init();
		}
		
		public Encoder2 GetSubCoder(int pos, byte prevByte)
		{ return m_Coders[((pos & m_PosMask) << m_NumPrevBits) + ((prevByte & 0xFF) >>> (8 - m_NumPrevBits))]; }
	}
	
	class LenEncoder
	{
		short[] _choice = new short[2];
		BitTreeEncoder[] _lowCoder = new BitTreeEncoder[Base.kNumPosStatesEncodingMax];
		BitTreeEncoder[] _midCoder = new BitTreeEncoder[Base.kNumPosStatesEncodingMax];
		BitTreeEncoder _highCoder = new BitTreeEncoder(Base.kNumHighLenBits);
		
		public LenEncoder()
		{
			for (int posState = 0; posState < Base.kNumPosStatesEncodingMax; posState++)
			{
				_lowCoder[posState] = new BitTreeEncoder(Base.kNumLowLenBits);
				_midCoder[posState] = new BitTreeEncoder(Base.kNumMidLenBits);
			}
		}
		
		public void Init(int numPosStates)
		{
			SevenZip.Compression.RangeCoder.Encoder.InitBitModels(_choice);
			for (int posState = 0; posState < numPosStates; posState++)
			{
				_lowCoder[posState].Init();
				_midCoder[posState].Init();
			}
			_highCoder.Init();
		}
		
		public void Encode(SevenZip.Compression.RangeCoder.Encoder rangeEncoder, int symbol, int posState) throws IOException
		{
			if (symbol < Base.kNumLowLenSymbols)
			{
				rangeEncoder.Encode(_choice, 0, 0);
				_lowCoder[posState].Encode(rangeEncoder, symbol);
			}
			else
			{
				symbol -= Base.kNumLowLenSymbols;
				rangeEncoder.Encode(_choice, 0, 1);
				if (symbol < Base.kNumMidLenSymbols)
				{
					rangeEncoder.Encode(_choice, 1, 0);
					_midCoder[posState].Encode(rangeEncoder, symbol);
				}
				else
				{
					rangeEncoder.Encode(_choice, 1, 1);
					_highCoder.Encode(rangeEncoder, symbol - Base.kNumMidLenSymbols);
				}
			}
		}
		
		public int GetPrice(int symbol, int posState)
		{
			int price = 0;
			if (symbol < Base.kNumLowLenSymbols)
			{
				price += SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_choice[0]);
				price += _lowCoder[posState].GetPrice(symbol);
			}
			else
			{
				symbol -= Base.kNumLowLenSymbols;
				price += SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_choice[0]);
				if (symbol < Base.kNumMidLenSymbols)
				{
					price += SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_choice[1]);
					price += _midCoder[posState].GetPrice(symbol);
				}
				else
				{
					price += SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_choice[1]);
					price += _highCoder.GetPrice(symbol - Base.kNumMidLenSymbols);
				}
			}
			return price;
		}
	};
	
	public static final int kNumLenSpecSymbols = Base.kNumLowLenSymbols + Base.kNumMidLenSymbols;
	
	class LenPriceTableEncoder extends LenEncoder
	{
		int[] _prices = new int[Base.kNumLenSymbols << Base.kNumPosStatesBitsEncodingMax];
		int _tableSize;
		int[] _counters = new int[Base.kNumPosStatesEncodingMax];
		
		public void SetTableSize(int tableSize)
		{ _tableSize = tableSize; }
		
		public int GetPrice(int symbol, int posState)
		{
			return _prices[(symbol << Base.kNumPosStatesBitsEncodingMax) + posState];
		}
		
		void UpdateTable(int posState)
		{
			for (int len = 0; len < _tableSize; len++)
				_prices[(len << Base.kNumPosStatesBitsEncodingMax) + posState] = super.GetPrice(len, posState);
			_counters[posState] = _tableSize;
		}
		
		public void UpdateTables(int numPosStates)
		{
			for (int posState = 0; posState < numPosStates; posState++)
				UpdateTable(posState);
		}
		
		public void Encode(SevenZip.Compression.RangeCoder.Encoder rangeEncoder, int symbol, int posState) throws IOException
		{
			super.Encode(rangeEncoder, symbol, posState);
			if (--_counters[posState] == 0)
				UpdateTable(posState);
		}
	}
	
	public static final int kNumOpts = 1 << 12;
	class Optimal
	{
		public int State;
		
		public boolean Prev1IsChar;
		public boolean Prev2;
		
		public int PosPrev2;
		public int BackPrev2;
		
		public int Price;
		public int PosPrev;         // posNext;
		public int BackPrev;
		
		// public UInt32 []Backs = new UInt32[Base.kNumRepDistances];
		public int Backs0;
		public int Backs1;
		public int Backs2;
		public int Backs3;
		
		public void MakeAsChar()
		{ BackPrev = -1; Prev1IsChar = false; }
		public void MakeAsShortRep()
		{ BackPrev = 0; ; Prev1IsChar = false; }
		public boolean IsShortRep()
		{ return (BackPrev == 0); }
	};
	Optimal[] _optimum = new Optimal[kNumOpts];
	
	SevenZip.Compression.LZ.BinTree _matchFinder = null; // test it
	SevenZip.Compression.RangeCoder.Encoder _rangeEncoder = new SevenZip.Compression.RangeCoder.Encoder();
	
	short[] _isMatch = new short[Base.kNumStates << Base.kNumPosStatesBitsMax];
	short[] _isRep = new short[Base.kNumStates];
	short[] _isRepG0 = new short[Base.kNumStates];
	short[] _isRepG1 = new short[Base.kNumStates];
	short[] _isRepG2 = new short[Base.kNumStates];
	short[] _isRep0Long = new short[Base.kNumStates << Base.kNumPosStatesBitsMax];
	
	BitTreeEncoder[] _posSlotEncoder = new BitTreeEncoder[Base.kNumLenToPosStates]; // kNumPosSlotBits
	short[] _posEncoders = new short[Base.kNumFullDistances - Base.kEndPosModelIndex];
	BitTreeEncoder _posAlignEncoder = new BitTreeEncoder(Base.kNumAlignBits);
	
	LenPriceTableEncoder _lenEncoder = new LenPriceTableEncoder();
	LenPriceTableEncoder _repMatchLenEncoder = new LenPriceTableEncoder();
	
	LiteralEncoder _literalEncoder = new LiteralEncoder();
	
	int[] _matchDistances = new int[Base.kMatchMaxLen + 1];
	boolean _fastMode = false;
	boolean _maxMode = true;
	int _numFastBytes = kNumFastBytesDefault;
	int _longestMatchLength;
	int _additionalOffset;
	
	int _optimumEndIndex;
	int _optimumCurrentIndex;
	
	boolean _longestMatchWasFound;
	
	int [] _posSlotPrices = new int [Base.kDistTableSizeMax << Base.kNumLenToPosStatesBits];
	int [] _distancesPrices = new int [Base.kNumFullDistances << Base.kNumLenToPosStatesBits];
	int [] _alignPrices = new int [Base.kAlignTableSize];
	int _alignPriceCount;
	
	int _distTableSize = (kDefaultDictionaryLogSize * 2);
	
	int _posStateBits = 2;
	int _posStateMask = (4 - 1);
	int _numLiteralPosStateBits = 0;
	int _numLiteralContextBits = 3;
	
	int _dictionarySize = (1 << kDefaultDictionaryLogSize);
	int _dictionarySizePrev = -1;
	int _numFastBytesPrev = -1;
	
	long lastPosSlotFillingPos;
	long nowPos64;
	boolean _finished;
	
	java.io.InputStream _inStream;
	int _matchFinderType = EMatchFinderTypeBT4;
	boolean _writeEndMark = false;
	boolean _needReleaseMFStream = false;
	
	void Create()
	{
		// _rangeEncoder.Create(1 << 20);
		if (_matchFinder == null)
		{
			SevenZip.Compression.LZ.BinTree bt = new SevenZip.Compression.LZ.BinTree();
			int numHashBytes = 4;
			boolean big = false;
			switch (_matchFinderType)
			{
				case EMatchFinderTypeBT2:
					numHashBytes = 2;
					break;
				case EMatchFinderTypeBT4:
					break;
				case EMatchFinderTypeBT4B:
					big = true;
					break;
				default:
					break;
			}
			bt.SetType(numHashBytes, big);
			_matchFinder = bt;
		}
		_literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits);
		
		if (_dictionarySize == _dictionarySizePrev && _numFastBytesPrev == _numFastBytes)
			return;
		_matchFinder.Create(_dictionarySize, kNumOpts, _numFastBytes,
				Base.kMatchMaxLen * 2 + 1 - _numFastBytes);
		_dictionarySizePrev = _dictionarySize;
		_numFastBytesPrev = _numFastBytes;
	}
	
	public Encoder()
	{
		for (int i = 0; i < kNumOpts; i++)
			_optimum[i] = new Optimal();
		for (int i = 0; i < Base.kNumLenToPosStates; i++)
			_posSlotEncoder[i] = new BitTreeEncoder(Base.kNumPosSlotBits);
	}
	
	void Init()
	{
		BaseInit();
		_rangeEncoder.Init();
		
		SevenZip.Compression.RangeCoder.Encoder.InitBitModels(_isMatch);
		SevenZip.Compression.RangeCoder.Encoder.InitBitModels(_isRep0Long);
		SevenZip.Compression.RangeCoder.Encoder.InitBitModels(_isRep);
		SevenZip.Compression.RangeCoder.Encoder.InitBitModels(_isRepG0);
		SevenZip.Compression.RangeCoder.Encoder.InitBitModels(_isRepG1);
		SevenZip.Compression.RangeCoder.Encoder.InitBitModels(_isRepG2);
		SevenZip.Compression.RangeCoder.Encoder.InitBitModels(_posEncoders);
		
		_literalEncoder.Init();
		for (int i = 0; i < Base.kNumLenToPosStates; i++)
			_posSlotEncoder[i].Init();
		
		_lenEncoder.Init(1 << _posStateBits);
		_repMatchLenEncoder.Init(1 << _posStateBits);
		
		_posAlignEncoder.Init();
		
		_longestMatchWasFound = false;
		_optimumEndIndex = 0;
		_optimumCurrentIndex = 0;
		_additionalOffset = 0;
	}
	
	int ReadMatchDistances() throws java.io.IOException
	{
		int lenRes = _matchFinder.GetLongestMatch(_matchDistances);
		if (lenRes == _numFastBytes)
			lenRes += _matchFinder.GetMatchLen((int)lenRes, _matchDistances[lenRes],
					Base.kMatchMaxLen - lenRes);
		_additionalOffset++;
		_matchFinder.MovePos();
		return lenRes;
	}
	
	void MovePos(int num) throws java.io.IOException
	{
		for (; num > 0; num--)
		{
			_matchFinder.DummyLongestMatch();
			_matchFinder.MovePos();
			_additionalOffset++;
		}
	}
	
	int GetRepLen1Price(int state, int posState)
	{
		return SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_isRepG0[state]) +
				SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_isRep0Long[(state << Base.kNumPosStatesBitsMax) + posState]);
	}
	
	int GetRepPrice(int repIndex, int len, int state, int posState)
	{
		int price = _repMatchLenEncoder.GetPrice(len - Base.kMatchMinLen, posState);
		if (repIndex == 0)
		{
			price += SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_isRepG0[state]);
			price += SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isRep0Long[(state << Base.kNumPosStatesBitsMax) + posState]);
		}
		else
		{
			price += SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isRepG0[state]);
			if (repIndex == 1)
				price += SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_isRepG1[state]);
			else
			{
				price += SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_isRepG1[state]);
				price += SevenZip.Compression.RangeCoder.Encoder.GetPrice(_isRepG2[state], repIndex - 2);
			}
		}
		return price;
	}
	
	int GetPosLenPrice(int pos, int len, int posState)
	{
		if (len == 2 && pos >= 0x80)
			return kIfinityPrice;
		int price;
		int lenToPosState = Base.GetLenToPosState(len);
		if (pos < Base.kNumFullDistances)
			price = _distancesPrices[(pos << Base.kNumLenToPosStatesBits) + lenToPosState];
		else
			price = _posSlotPrices[(GetPosSlot2(pos) << Base.kNumLenToPosStatesBits) + lenToPosState] +
					_alignPrices[pos & Base.kAlignMask];
		return price + _lenEncoder.GetPrice(len - Base.kMatchMinLen, posState);
	}