encoder.java

一个7ZIP的解压源码。比较详细。里面含有四种语言的实现代码。

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;




	static final int kIfinityPrice = 0xFFFFFFF;

	static byte[] g_FastPos = new byte[1 << 11];

	static
	{
		int kFastSlots = 22;
		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 << 11))
			return g_FastPos[pos];
		if (pos < (1 << 21))
			return (g_FastPos[pos >> 10] + 20);
		return (g_FastPos[pos >> 20] + 40);
	}

	static int GetPosSlot2(int pos)
	{
		if (pos < (1 << 17))
			return (g_FastPos[pos >> 6] + 12);
		if (pos < (1 << 27))
			return (g_FastPos[pos >> 16] + 32);
		return (g_FastPos[pos >> 26] + 52);
	}

	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 = 22;
	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 void SetPrices(int posState, int numSymbols, int[] prices, int st)
		{
			int a0 = SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_choice[0]);
			int a1 = SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_choice[0]);
			int b0 = a1 + SevenZip.Compression.RangeCoder.Encoder.GetPrice0(_choice[1]);
			int b1 = a1 + SevenZip.Compression.RangeCoder.Encoder.GetPrice1(_choice[1]);
			int i = 0;
			for (i = 0; i < Base.kNumLowLenSymbols; i++)
			{
				if (i >= numSymbols)
					return;
				prices[st + i] = a0 + _lowCoder[posState].GetPrice(i);
			}
			for (; i < Base.kNumLowLenSymbols + Base.kNumMidLenSymbols; i++)
			{
				if (i >= numSymbols)
					return;
				prices[st + i] = b0 + _midCoder[posState].GetPrice(i - Base.kNumLowLenSymbols);
			}
			for (; i < numSymbols; i++)
				prices[st + i] = b1 + _highCoder.GetPrice(i - Base.kNumLowLenSymbols - Base.kNumMidLenSymbols);
		}
	};

	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[posState * Base.kNumLenSymbols + symbol];
		}

		void UpdateTable(int posState)
		{
			SetPrices(posState, _tableSize, _prices, posState * Base.kNumLenSymbols);
			_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);
		}
	}

	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;
		public int BackPrev;

		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;
	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*2+2];

	int _numFastBytes = kNumFastBytesDefault;
	int _longestMatchLength;
	int _numDistancePairs;

	int _additionalOffset;

	int _optimumEndIndex;
	int _optimumCurrentIndex;

	boolean _longestMatchWasFound;

	int[] _posSlotPrices = new int[1<<(Base.kNumPosSlotBits+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 nowPos64;
	boolean _finished;
	java.io.InputStream _inStream;

	int _matchFinderType = EMatchFinderTypeBT4;
	boolean _writeEndMark = false;

	boolean _needReleaseMFStream = false;

	void Create()
	{
		if (_matchFinder == null)
		{
			SevenZip.Compression.LZ.BinTree bt = new SevenZip.Compression.LZ.BinTree();
			int numHashBytes = 4;
			if (_matchFinderType == EMatchFinderTypeBT2)
				numHashBytes = 2;
			bt.SetType(numHashBytes);
			_matchFinder = bt;
		}
		_literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits);

		if (_dictionarySize == _dictionarySizePrev && _numFastBytesPrev == _numFastBytes)
			return;
		_matchFinder.Create(_dictionarySize, kNumOpts, _numFastBytes, Base.kMatchMaxLen + 1);
		_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 SetWriteEndMarkerMode(boolean writeEndMarker)
	{
		_writeEndMark = writeEndMarker;
	}

	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 = 0;
		_numDistancePairs = _matchFinder.GetMatches(_matchDistances);
		if (_numDistancePairs > 0)
		{
			lenRes = _matchDistances[_numDistancePairs - 2];
			if (lenRes == _numFastBytes)
				lenRes += _matchFinder.GetMatchLen((int)lenRes - 1, _matchDistances[_numDistancePairs - 1],
					Base.kMatchMaxLen - lenRes);
		}
		_additionalOffset++;
		return lenRes;
	}

	void MovePos(int num) throws java.io.IOException
	{
		if (num > 0)
		{
			_matchFinder.Skip(num);
			_additionalOffset += num;
		}
	}

	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 GetPureRepPrice(int repIndex, int state, int posState)
	{
		int price;
		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]);