/* Copyright 2015 Google Inc. All Rights Reserved.

Distributed under MIT license.
See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/
namespace Org.Brotli.Dec
{
	/// <summary>API for Brotli decompression.</summary>
	internal sealed class Decode
	{
		private const int DefaultCodeLength = 8;

		private const int CodeLengthRepeatCode = 16;

		private const int NumLiteralCodes = 256;

		private const int NumInsertAndCopyCodes = 704;

		private const int NumBlockLengthCodes = 26;

		private const int LiteralContextBits = 6;

		private const int DistanceContextBits = 2;

		private const int HuffmanTableBits = 8;

		private const int HuffmanTableMask = unchecked((int)(0xFF));

		private const int CodeLengthCodes = 18;

		private static readonly int[] CodeLengthCodeOrder = new int[] { 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

		private const int NumDistanceShortCodes = 16;

		private static readonly int[] DistanceShortCodeIndexOffset = new int[] { 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 };

		private static readonly int[] DistanceShortCodeValueOffset = new int[] { 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 };

		/// <summary>Static Huffman code for the code length code lengths.</summary>
		private static readonly int[] FixedTable = new int[] { unchecked((int)(0x020000)), unchecked((int)(0x020004)), unchecked((int)(0x020003)), unchecked((int)(0x030002)), unchecked((int)(0x020000)), unchecked((int)(0x020004)), unchecked((int)(0x020003
			)), unchecked((int)(0x040001)), unchecked((int)(0x020000)), unchecked((int)(0x020004)), unchecked((int)(0x020003)), unchecked((int)(0x030002)), unchecked((int)(0x020000)), unchecked((int)(0x020004)), unchecked((int)(0x020003)), unchecked((int
			)(0x040005)) };

		/// <summary>Decodes a number in the range [0..255], by reading 1 - 11 bits.</summary>
		private static int DecodeVarLenUnsignedByte(Org.Brotli.Dec.BitReader br)
		{
			if (Org.Brotli.Dec.BitReader.ReadBits(br, 1) != 0)
			{
				int n = Org.Brotli.Dec.BitReader.ReadBits(br, 3);
				if (n == 0)
				{
					return 1;
				}
				else
				{
					return Org.Brotli.Dec.BitReader.ReadBits(br, n) + (1 << n);
				}
			}
			return 0;
		}

		private static void DecodeMetaBlockLength(Org.Brotli.Dec.BitReader br, Org.Brotli.Dec.State state)
		{
			state.inputEnd = Org.Brotli.Dec.BitReader.ReadBits(br, 1) == 1;
			state.metaBlockLength = 0;
			state.isUncompressed = false;
			state.isMetadata = false;
			if (state.inputEnd && Org.Brotli.Dec.BitReader.ReadBits(br, 1) != 0)
			{
				return;
			}
			int sizeNibbles = Org.Brotli.Dec.BitReader.ReadBits(br, 2) + 4;
			if (sizeNibbles == 7)
			{
				state.isMetadata = true;
				if (Org.Brotli.Dec.BitReader.ReadBits(br, 1) != 0)
				{
					throw new Org.Brotli.Dec.BrotliRuntimeException("Corrupted reserved bit");
				}
				int sizeBytes = Org.Brotli.Dec.BitReader.ReadBits(br, 2);
				if (sizeBytes == 0)
				{
					return;
				}
				for (int i = 0; i < sizeBytes; i++)
				{
					int bits = Org.Brotli.Dec.BitReader.ReadBits(br, 8);
					if (bits == 0 && i + 1 == sizeBytes && sizeBytes > 1)
					{
						throw new Org.Brotli.Dec.BrotliRuntimeException("Exuberant nibble");
					}
					state.metaBlockLength |= bits << (i * 8);
				}
			}
			else
			{
				for (int i = 0; i < sizeNibbles; i++)
				{
					int bits = Org.Brotli.Dec.BitReader.ReadBits(br, 4);
					if (bits == 0 && i + 1 == sizeNibbles && sizeNibbles > 4)
					{
						throw new Org.Brotli.Dec.BrotliRuntimeException("Exuberant nibble");
					}
					state.metaBlockLength |= bits << (i * 4);
				}
			}
			state.metaBlockLength++;
			if (!state.inputEnd)
			{
				state.isUncompressed = Org.Brotli.Dec.BitReader.ReadBits(br, 1) == 1;
			}
		}

		/// <summary>Decodes the next Huffman code from bit-stream.</summary>
		private static int ReadSymbol(int[] table, int offset, Org.Brotli.Dec.BitReader br)
		{
			int val = (int)((long)(((ulong)br.accumulator) >> br.bitOffset));
			offset += val & HuffmanTableMask;
			int bits = table[offset] >> 16;
			int sym = table[offset] & unchecked((int)(0xFFFF));
			if (bits <= HuffmanTableBits)
			{
				br.bitOffset += bits;
				return sym;
			}
			offset += sym;
			int mask = (1 << bits) - 1;
			offset += (int)(((uint)(val & mask)) >> HuffmanTableBits);
			br.bitOffset += ((table[offset] >> 16) + HuffmanTableBits);
			return table[offset] & unchecked((int)(0xFFFF));
		}

		private static int ReadBlockLength(int[] table, int offset, Org.Brotli.Dec.BitReader br)
		{
			Org.Brotli.Dec.BitReader.FillBitWindow(br);
			int code = ReadSymbol(table, offset, br);
			int n = Org.Brotli.Dec.Prefix.BlockLengthNBits[code];
			return Org.Brotli.Dec.Prefix.BlockLengthOffset[code] + Org.Brotli.Dec.BitReader.ReadBits(br, n);
		}

		private static int TranslateShortCodes(int code, int[] ringBuffer, int index)
		{
			if (code < NumDistanceShortCodes)
			{
				index += DistanceShortCodeIndexOffset[code];
				index &= 3;
				return ringBuffer[index] + DistanceShortCodeValueOffset[code];
			}
			return code - NumDistanceShortCodes + 1;
		}

		private static void MoveToFront(int[] v, int index)
		{
			int value = v[index];
			for (; index > 0; index--)
			{
				v[index] = v[index - 1];
			}
			v[0] = value;
		}

		private static void InverseMoveToFrontTransform(byte[] v, int vLen)
		{
			int[] mtf = new int[256];
			for (int i = 0; i < 256; i++)
			{
				mtf[i] = i;
			}
			for (int i = 0; i < vLen; i++)
			{
				int index = v[i] & unchecked((int)(0xFF));
				v[i] = unchecked((byte)mtf[index]);
				if (index != 0)
				{
					MoveToFront(mtf, index);
				}
			}
		}

		private static void ReadHuffmanCodeLengths(int[] codeLengthCodeLengths, int numSymbols, int[] codeLengths, Org.Brotli.Dec.BitReader br)
		{
			int symbol = 0;
			int prevCodeLen = DefaultCodeLength;
			int repeat = 0;
			int repeatCodeLen = 0;
			int space = 32768;
			int[] table = new int[32];
			Org.Brotli.Dec.Huffman.BuildHuffmanTable(table, 0, 5, codeLengthCodeLengths, CodeLengthCodes);
			while (symbol < numSymbols && space > 0)
			{
				Org.Brotli.Dec.BitReader.ReadMoreInput(br);
				Org.Brotli.Dec.BitReader.FillBitWindow(br);
				int p = (int)(((long)(((ulong)br.accumulator) >> br.bitOffset))) & 31;
				br.bitOffset += table[p] >> 16;
				int codeLen = table[p] & unchecked((int)(0xFFFF));
				if (codeLen < CodeLengthRepeatCode)
				{
					repeat = 0;
					codeLengths[symbol++] = codeLen;
					if (codeLen != 0)
					{
						prevCodeLen = codeLen;
						space -= 32768 >> codeLen;
					}
				}
				else
				{
					int extraBits = codeLen - 14;
					int newLen = 0;
					if (codeLen == CodeLengthRepeatCode)
					{
						newLen = prevCodeLen;
					}
					if (repeatCodeLen != newLen)
					{
						repeat = 0;
						repeatCodeLen = newLen;
					}
					int oldRepeat = repeat;
					if (repeat > 0)
					{
						repeat -= 2;
						repeat <<= extraBits;
					}
					repeat += Org.Brotli.Dec.BitReader.ReadBits(br, extraBits) + 3;
					int repeatDelta = repeat - oldRepeat;
					if (symbol + repeatDelta > numSymbols)
					{
						throw new Org.Brotli.Dec.BrotliRuntimeException("symbol + repeatDelta > numSymbols");
					}
					// COV_NF_LINE
					for (int i = 0; i < repeatDelta; i++)
					{
						codeLengths[symbol++] = repeatCodeLen;
					}
					if (repeatCodeLen != 0)
					{
						space -= repeatDelta << (15 - repeatCodeLen);
					}
				}
			}
			if (space != 0)
			{
				throw new Org.Brotli.Dec.BrotliRuntimeException("Unused space");
			}
			// COV_NF_LINE
			// TODO: Pass max_symbol to Huffman table builder instead?
			Org.Brotli.Dec.Utils.FillWithZeroes(codeLengths, symbol, numSymbols - symbol);
		}

		// TODO: Use specialized versions for smaller tables.
		internal static void ReadHuffmanCode(int alphabetSize, int[] table, int offset, Org.Brotli.Dec.BitReader br)
		{
			bool ok = true;
			int simpleCodeOrSkip;
			Org.Brotli.Dec.BitReader.ReadMoreInput(br);
			// TODO: Avoid allocation.
			int[] codeLengths = new int[alphabetSize];
			simpleCodeOrSkip = Org.Brotli.Dec.BitReader.ReadBits(br, 2);
			if (simpleCodeOrSkip == 1)
			{
				// Read symbols, codes & code lengths directly.
				int maxBitsCounter = alphabetSize - 1;
				int maxBits = 0;
				int[] symbols = new int[4];
				int numSymbols = Org.Brotli.Dec.BitReader.ReadBits(br, 2) + 1;
				while (maxBitsCounter != 0)
				{
					maxBitsCounter >>= 1;
					maxBits++;
				}
				// TODO: uncomment when codeLengths is reused.
				// Utils.fillWithZeroes(codeLengths, 0, alphabetSize);
				for (int i = 0; i < numSymbols; i++)
				{
					symbols[i] = Org.Brotli.Dec.BitReader.ReadBits(br, maxBits) % alphabetSize;
					codeLengths[symbols[i]] = 2;
				}
				codeLengths[symbols[0]] = 1;
				switch (numSymbols)
				{
					case 1:
					{
						break;
					}

					case 2:
					{
						ok = symbols[0] != symbols[1];
						codeLengths[symbols[1]] = 1;
						break;
					}

					case 3:
					{
						ok = symbols[0] != symbols[1] && symbols[0] != symbols[2] && symbols[1] != symbols[2];
						break;
					}

					case 4:
					default:
					{
						ok = symbols[0] != symbols[1] && symbols[0] != symbols[2] && symbols[0] != symbols[3] && symbols[1] != symbols[2] && symbols[1] != symbols[3] && symbols[2] != symbols[3];
						if (Org.Brotli.Dec.BitReader.ReadBits(br, 1) == 1)
						{
							codeLengths[symbols[2]] = 3;
							codeLengths[symbols[3]] = 3;
						}
						else
						{
							codeLengths[symbols[0]] = 2;
						}
						break;
					}
				}
			}
			else
			{
				// Decode Huffman-coded code lengths.
				int[] codeLengthCodeLengths = new int[CodeLengthCodes];
				int space = 32;
				int numCodes = 0;
				for (int i = simpleCodeOrSkip; i < CodeLengthCodes && space > 0; i++)
				{
					int codeLenIdx = CodeLengthCodeOrder[i];
					Org.Brotli.Dec.BitReader.FillBitWindow(br);
					int p = (int)((long)(((ulong)br.accumulator) >> br.bitOffset)) & 15;
					// TODO: Demultiplex FIXED_TABLE.
					br.bitOffset += FixedTable[p] >> 16;
					int v = FixedTable[p] & unchecked((int)(0xFFFF));
					codeLengthCodeLengths[codeLenIdx] = v;
					if (v != 0)
					{
						space -= (32 >> v);
						numCodes++;
					}
				}
				ok = (numCodes == 1 || space == 0);
				ReadHuffmanCodeLengths(codeLengthCodeLengths, alphabetSize, codeLengths, br);
			}
			if (!ok)
			{
				throw new Org.Brotli.Dec.BrotliRuntimeException("Can't readHuffmanCode");
			}
			// COV_NF_LINE
			Org.Brotli.Dec.Huffman.BuildHuffmanTable(table, offset, HuffmanTableBits, codeLengths, alphabetSize);
		}

		private static int DecodeContextMap(int contextMapSize, byte[] contextMap, Org.Brotli.Dec.BitReader br)
		{
			Org.Brotli.Dec.BitReader.ReadMoreInput(br);
			int numTrees = DecodeVarLenUnsignedByte(br) + 1;
			if (numTrees == 1)
			{
				Org.Brotli.Dec.Utils.FillWithZeroes(contextMap, 0, contextMapSize);
				return numTrees;
			}
			bool useRleForZeros = Org.Brotli.Dec.BitReader.ReadBits(br, 1) == 1;
			int maxRunLengthPrefix = 0;
			if (useRleForZeros)
			{
				maxRunLengthPrefix = Org.Brotli.Dec.BitReader.ReadBits(br, 4) + 1;
			}
			int[] table = new int[Org.Brotli.Dec.Huffman.HuffmanMaxTableSize];
			ReadHuffmanCode(numTrees + maxRunLengthPrefix, table, 0, br);
			for (int i = 0; i < contextMapSize; )
			{
				Org.Brotli.Dec.BitReader.ReadMoreInput(br);
				Org.Brotli.Dec.BitReader.FillBitWindow(br);
				int code = ReadSymbol(table, 0, br);
				if (code == 0)
				{
					contextMap[i] = 0;
					i++;
				}
				else if (code <= maxRunLengthPrefix)
				{
					int reps = (1 << code) + Org.Brotli.Dec.BitReader.ReadBits(br, code);
					while (reps != 0)
					{
						if (i >= contextMapSize)
						{
							throw new Org.Brotli.Dec.BrotliRuntimeException("Corrupted context map");
						}
						// COV_NF_LINE
						contextMap[i] = 0;
						i++;
						reps--;
					}
				}
				else
				{
					contextMap[i] = unchecked((byte)(code - maxRunLengthPrefix));
					i++;
				}
			}
			if (Org.Brotli.Dec.BitReader.ReadBits(br, 1) == 1)
			{
				InverseMoveToFrontTransform(contextMap, contextMapSize);
			}
			return numTrees;
		}

		private static void DecodeBlockTypeAndLength(Org.Brotli.Dec.State state, int treeType)
		{
			Org.Brotli.Dec.BitReader br = state.br;
			int[] ringBuffers = state.blockTypeRb;
			int offset = treeType * 2;
			Org.Brotli.Dec.BitReader.FillBitWindow(br);
			int blockType = ReadSymbol(state.blockTypeTrees, treeType * Org.Brotli.Dec.Huffman.HuffmanMaxTableSize, br);
			state.blockLength[treeType] = ReadBlockLength(state.blockLenTrees, treeType * Org.Brotli.Dec.Huffman.HuffmanMaxTableSize, br);
			if (blockType == 1)
			{
				blockType = ringBuffers[offset + 1] + 1;
			}
			else if (blockType == 0)
			{
				blockType = ringBuffers[offset];
			}
			else
			{
				blockType -= 2;
			}
			if (blockType >= state.numBlockTypes[treeType])
			{
				blockType -= state.numBlockTypes[treeType];
			}
			ringBuffers[offset] = ringBuffers[offset + 1];
			ringBuffers[offset + 1] = blockType;
		}

		private static void DecodeLiteralBlockSwitch(Org.Brotli.Dec.State state)
		{
			DecodeBlockTypeAndLength(state, 0);
			int literalBlockType = state.blockTypeRb[1];
			state.contextMapSlice = literalBlockType << LiteralContextBits;
			state.literalTreeIndex = state.contextMap[state.contextMapSlice] & unchecked((int)(0xFF));
			state.literalTree = state.hGroup0.trees[state.literalTreeIndex];
			int contextMode = state.contextModes[literalBlockType];
			state.contextLookupOffset1 = Org.Brotli.Dec.Context.LookupOffsets[contextMode];
			state.contextLookupOffset2 = Org.Brotli.Dec.Context.LookupOffsets[contextMode + 1];
		}

		private static void DecodeCommandBlockSwitch(Org.Brotli.Dec.State state)
		{
			DecodeBlockTypeAndLength(state, 1);
			state.treeCommandOffset = state.hGroup1.trees[state.blockTypeRb[3]];
		}

		private static void DecodeDistanceBlockSwitch(Org.Brotli.Dec.State state)
		{
			DecodeBlockTypeAndLength(state, 2);
			state.distContextMapSlice = state.blockTypeRb[5] << DistanceContextBits;
		}

		private static void MaybeReallocateRingBuffer(Org.Brotli.Dec.State state)
		{
			int newSize = state.maxRingBufferSize;
			if ((long)newSize > state.expectedTotalSize)
			{
				/* TODO: Handle 2GB+ cases more gracefully. */
				int minimalNewSize = (int)state.expectedTotalSize + state.customDictionary.Length;
				while ((newSize >> 1) > minimalNewSize)
				{
					newSize >>= 1;
				}
				if (!state.inputEnd && newSize < 16384 && state.maxRingBufferSize >= 16384)
				{
					newSize = 16384;
				}
			}
			if (newSize <= state.ringBufferSize)
			{
				return;
			}
			int ringBufferSizeWithSlack = newSize + Org.Brotli.Dec.Dictionary.MaxTransformedWordLength;
			byte[] newBuffer = new byte[ringBufferSizeWithSlack];
			if (state.ringBuffer != null)
			{
				System.Array.Copy(state.ringBuffer, 0, newBuffer, 0, state.ringBufferSize);
			}
			else if (state.customDictionary.Length != 0)
			{
				/* Prepend custom dictionary, if any. */
				int length = state.customDictionary.Length;
				int offset = 0;
				if (length > state.maxBackwardDistance)
				{
					offset = length - state.maxBackwardDistance;
					length = state.maxBackwardDistance;
				}
				System.Array.Copy(state.customDictionary, offset, newBuffer, 0, length);
				state.pos = length;
				state.bytesToIgnore = length;
			}
			state.ringBuffer = newBuffer;
			state.ringBufferSize = newSize;
		}

		/// <summary>Reads next metablock header.</summary>
		/// <param name="state">decoding state</param>
		private static void ReadMetablockInfo(Org.Brotli.Dec.State state)
		{
			Org.Brotli.Dec.BitReader br = state.br;
			if (state.inputEnd)
			{
				state.nextRunningState = Org.Brotli.Dec.RunningState.Finished;
				state.bytesToWrite = state.pos;
				state.bytesWritten = 0;
				state.runningState = Org.Brotli.Dec.RunningState.Write;
				return;
			}
			// TODO: Reset? Do we need this?
			state.hGroup0.codes = null;
			state.hGroup0.trees = null;
			state.hGroup1.codes = null;
			state.hGroup1.trees = null;
			state.hGroup2.codes = null;
			state.hGroup2.trees = null;
			Org.Brotli.Dec.BitReader.ReadMoreInput(br);
			DecodeMetaBlockLength(br, state);
			if (state.metaBlockLength == 0 && !state.isMetadata)
			{
				return;
			}
			if (state.isUncompressed || state.isMetadata)
			{
				Org.Brotli.Dec.BitReader.JumpToByteBoundary(br);
				state.runningState = state.isMetadata ? Org.Brotli.Dec.RunningState.ReadMetadata : Org.Brotli.Dec.RunningState.CopyUncompressed;
			}
			else
			{
				state.runningState = Org.Brotli.Dec.RunningState.CompressedBlockStart;
			}
			if (state.isMetadata)
			{
				return;
			}
			state.expectedTotalSize += state.metaBlockLength;
			if (state.ringBufferSize < state.maxRingBufferSize)
			{
				MaybeReallocateRingBuffer(state);
			}
		}

		private static void ReadMetablockHuffmanCodesAndContextMaps(Org.Brotli.Dec.State state)
		{
			Org.Brotli.Dec.BitReader br = state.br;
			for (int i = 0; i < 3; i++)
			{
				state.numBlockTypes[i] = DecodeVarLenUnsignedByte(br) + 1;
				state.blockLength[i] = 1 << 28;
				if (state.numBlockTypes[i] > 1)
				{
					ReadHuffmanCode(state.numBlockTypes[i] + 2, state.blockTypeTrees, i * Org.Brotli.Dec.Huffman.HuffmanMaxTableSize, br);
					ReadHuffmanCode(NumBlockLengthCodes, state.blockLenTrees, i * Org.Brotli.Dec.Huffman.HuffmanMaxTableSize, br);
					state.blockLength[i] = ReadBlockLength(state.blockLenTrees, i * Org.Brotli.Dec.Huffman.HuffmanMaxTableSize, br);
				}
			}
			Org.Brotli.Dec.BitReader.ReadMoreInput(br);
			state.distancePostfixBits = Org.Brotli.Dec.BitReader.ReadBits(br, 2);
			state.numDirectDistanceCodes = NumDistanceShortCodes + (Org.Brotli.Dec.BitReader.ReadBits(br, 4) << state.distancePostfixBits);
			state.distancePostfixMask = (1 << state.distancePostfixBits) - 1;
			int numDistanceCodes = state.numDirectDistanceCodes + (48 << state.distancePostfixBits);
			// TODO: Reuse?
			state.contextModes = new byte[state.numBlockTypes[0]];
			for (int i = 0; i < state.numBlockTypes[0]; )
			{
				/* Ensure that less than 256 bits read between readMoreInput. */
				int limit = System.Math.Min(i + 96, state.numBlockTypes[0]);
				for (; i < limit; ++i)
				{
					state.contextModes[i] = unchecked((byte)(Org.Brotli.Dec.BitReader.ReadBits(br, 2) << 1));
				}
				Org.Brotli.Dec.BitReader.ReadMoreInput(br);
			}
			// TODO: Reuse?
			state.contextMap = new byte[state.numBlockTypes[0] << LiteralContextBits];
			int numLiteralTrees = DecodeContextMap(state.numBlockTypes[0] << LiteralContextBits, state.contextMap, br);
			state.trivialLiteralContext = true;
			for (int j = 0; j < state.numBlockTypes[0] << LiteralContextBits; j++)
			{
				if (state.contextMap[j] != j >> LiteralContextBits)
				{
					state.trivialLiteralContext = false;
					break;
				}
			}
			// TODO: Reuse?
			state.distContextMap = new byte[state.numBlockTypes[2] << DistanceContextBits];
			int numDistTrees = DecodeContextMap(state.numBlockTypes[2] << DistanceContextBits, state.distContextMap, br);
			Org.Brotli.Dec.HuffmanTreeGroup.Init(state.hGroup0, NumLiteralCodes, numLiteralTrees);
			Org.Brotli.Dec.HuffmanTreeGroup.Init(state.hGroup1, NumInsertAndCopyCodes, state.numBlockTypes[1]);
			Org.Brotli.Dec.HuffmanTreeGroup.Init(state.hGroup2, numDistanceCodes, numDistTrees);
			Org.Brotli.Dec.HuffmanTreeGroup.Decode(state.hGroup0, br);
			Org.Brotli.Dec.HuffmanTreeGroup.Decode(state.hGroup1, br);
			Org.Brotli.Dec.HuffmanTreeGroup.Decode(state.hGroup2, br);
			state.contextMapSlice = 0;
			state.distContextMapSlice = 0;
			state.contextLookupOffset1 = Org.Brotli.Dec.Context.LookupOffsets[state.contextModes[0]];
			state.contextLookupOffset2 = Org.Brotli.Dec.Context.LookupOffsets[state.contextModes[0] + 1];
			state.literalTreeIndex = 0;
			state.literalTree = state.hGroup0.trees[0];
			state.treeCommandOffset = state.hGroup1.trees[0];
			// TODO: == 0?
			state.blockTypeRb[0] = state.blockTypeRb[2] = state.blockTypeRb[4] = 1;
			state.blockTypeRb[1] = state.blockTypeRb[3] = state.blockTypeRb[5] = 0;
		}

		private static void CopyUncompressedData(Org.Brotli.Dec.State state)
		{
			Org.Brotli.Dec.BitReader br = state.br;
			byte[] ringBuffer = state.ringBuffer;
			// Could happen if block ends at ring buffer end.
			if (state.metaBlockLength <= 0)
			{
				Org.Brotli.Dec.BitReader.Reload(br);
				state.runningState = Org.Brotli.Dec.RunningState.BlockStart;
				return;
			}
			int chunkLength = System.Math.Min(state.ringBufferSize - state.pos, state.metaBlockLength);
			Org.Brotli.Dec.BitReader.CopyBytes(br, ringBuffer, state.pos, chunkLength);
			state.metaBlockLength -= chunkLength;
			state.pos += chunkLength;
			if (state.pos == state.ringBufferSize)
			{
				state.nextRunningState = Org.Brotli.Dec.RunningState.CopyUncompressed;
				state.bytesToWrite = state.ringBufferSize;
				state.bytesWritten = 0;
				state.runningState = Org.Brotli.Dec.RunningState.Write;
				return;
			}
			Org.Brotli.Dec.BitReader.Reload(br);
			state.runningState = Org.Brotli.Dec.RunningState.BlockStart;
		}

		private static bool WriteRingBuffer(Org.Brotli.Dec.State state)
		{
			/* Ignore custom dictionary bytes. */
			if (state.bytesToIgnore != 0)
			{
				state.bytesWritten += state.bytesToIgnore;
				state.bytesToIgnore = 0;
			}
			int toWrite = System.Math.Min(state.outputLength - state.outputUsed, state.bytesToWrite - state.bytesWritten);
			if (toWrite != 0)
			{
				System.Array.Copy(state.ringBuffer, state.bytesWritten, state.output, state.outputOffset + state.outputUsed, toWrite);
				state.outputUsed += toWrite;
				state.bytesWritten += toWrite;
			}
			return state.outputUsed < state.outputLength;
		}

		internal static void SetCustomDictionary(Org.Brotli.Dec.State state, byte[] data)
		{
			state.customDictionary = (data == null) ? new byte[0] : data;
		}

		/// <summary>Actual decompress implementation.</summary>
		internal static void Decompress(Org.Brotli.Dec.State state)
		{
			if (state.runningState == Org.Brotli.Dec.RunningState.Uninitialized)
			{
				throw new System.InvalidOperationException("Can't decompress until initialized");
			}
			if (state.runningState == Org.Brotli.Dec.RunningState.Closed)
			{
				throw new System.InvalidOperationException("Can't decompress after close");
			}
			Org.Brotli.Dec.BitReader br = state.br;
			int ringBufferMask = state.ringBufferSize - 1;
			byte[] ringBuffer = state.ringBuffer;
			while (state.runningState != Org.Brotli.Dec.RunningState.Finished)
			{
				switch (state.runningState)
				{
					case Org.Brotli.Dec.RunningState.BlockStart:
					{
						// TODO: extract cases to methods for the better readability.
						if (state.metaBlockLength < 0)
						{
							throw new Org.Brotli.Dec.BrotliRuntimeException("Invalid metablock length");
						}
						ReadMetablockInfo(state);
						/* Ring-buffer would be reallocated here. */
						ringBufferMask = state.ringBufferSize - 1;
						ringBuffer = state.ringBuffer;
						continue;
					}

					case Org.Brotli.Dec.RunningState.CompressedBlockStart:
					{
						ReadMetablockHuffmanCodesAndContextMaps(state);
						state.runningState = Org.Brotli.Dec.RunningState.MainLoop;
						goto case Org.Brotli.Dec.RunningState.MainLoop;
					}

					case Org.Brotli.Dec.RunningState.MainLoop:
					{
						// Fall through
						if (state.metaBlockLength <= 0)
						{
							state.runningState = Org.Brotli.Dec.RunningState.BlockStart;
							continue;
						}
						Org.Brotli.Dec.BitReader.ReadMoreInput(br);
						if (state.blockLength[1] == 0)
						{
							DecodeCommandBlockSwitch(state);
						}
						state.blockLength[1]--;
						Org.Brotli.Dec.BitReader.FillBitWindow(br);
						int cmdCode = ReadSymbol(state.hGroup1.codes, state.treeCommandOffset, br);
						int rangeIdx = (int)(((uint)cmdCode) >> 6);
						state.distanceCode = 0;
						if (rangeIdx >= 2)
						{
							rangeIdx -= 2;
							state.distanceCode = -1;
						}
						int insertCode = Org.Brotli.Dec.Prefix.InsertRangeLut[rangeIdx] + (((int)(((uint)cmdCode) >> 3)) & 7);
						int copyCode = Org.Brotli.Dec.Prefix.CopyRangeLut[rangeIdx] + (cmdCode & 7);
						state.insertLength = Org.Brotli.Dec.Prefix.InsertLengthOffset[insertCode] + Org.Brotli.Dec.BitReader.ReadBits(br, Org.Brotli.Dec.Prefix.InsertLengthNBits[insertCode]);
						state.copyLength = Org.Brotli.Dec.Prefix.CopyLengthOffset[copyCode] + Org.Brotli.Dec.BitReader.ReadBits(br, Org.Brotli.Dec.Prefix.CopyLengthNBits[copyCode]);
						state.j = 0;
						state.runningState = Org.Brotli.Dec.RunningState.InsertLoop;
						goto case Org.Brotli.Dec.RunningState.InsertLoop;
					}

					case Org.Brotli.Dec.RunningState.InsertLoop:
					{
						// Fall through
						if (state.trivialLiteralContext)
						{
							while (state.j < state.insertLength)
							{
								Org.Brotli.Dec.BitReader.ReadMoreInput(br);
								if (state.blockLength[0] == 0)
								{
									DecodeLiteralBlockSwitch(state);
								}
								state.blockLength[0]--;
								Org.Brotli.Dec.BitReader.FillBitWindow(br);
								ringBuffer[state.pos] = unchecked((byte)ReadSymbol(state.hGroup0.codes, state.literalTree, br));
								state.j++;
								if (state.pos++ == ringBufferMask)
								{
									state.nextRunningState = Org.Brotli.Dec.RunningState.InsertLoop;
									state.bytesToWrite = state.ringBufferSize;
									state.bytesWritten = 0;
									state.runningState = Org.Brotli.Dec.RunningState.Write;
									break;
								}
							}
						}
						else
						{
							int prevByte1 = ringBuffer[(state.pos - 1) & ringBufferMask] & unchecked((int)(0xFF));
							int prevByte2 = ringBuffer[(state.pos - 2) & ringBufferMask] & unchecked((int)(0xFF));
							while (state.j < state.insertLength)
							{
								Org.Brotli.Dec.BitReader.ReadMoreInput(br);
								if (state.blockLength[0] == 0)
								{
									DecodeLiteralBlockSwitch(state);
								}
								int literalTreeIndex = state.contextMap[state.contextMapSlice + (Org.Brotli.Dec.Context.Lookup[state.contextLookupOffset1 + prevByte1] | Org.Brotli.Dec.Context.Lookup[state.contextLookupOffset2 + prevByte2])] & unchecked((int)(0xFF));
								state.blockLength[0]--;
								prevByte2 = prevByte1;
								Org.Brotli.Dec.BitReader.FillBitWindow(br);
								prevByte1 = ReadSymbol(state.hGroup0.codes, state.hGroup0.trees[literalTreeIndex], br);
								ringBuffer[state.pos] = unchecked((byte)prevByte1);
								state.j++;
								if (state.pos++ == ringBufferMask)
								{
									state.nextRunningState = Org.Brotli.Dec.RunningState.InsertLoop;
									state.bytesToWrite = state.ringBufferSize;
									state.bytesWritten = 0;
									state.runningState = Org.Brotli.Dec.RunningState.Write;
									break;
								}
							}
						}
						if (state.runningState != Org.Brotli.Dec.RunningState.InsertLoop)
						{
							continue;
						}
						state.metaBlockLength -= state.insertLength;
						if (state.metaBlockLength <= 0)
						{
							state.runningState = Org.Brotli.Dec.RunningState.MainLoop;
							continue;
						}
						if (state.distanceCode < 0)
						{
							Org.Brotli.Dec.BitReader.ReadMoreInput(br);
							if (state.blockLength[2] == 0)
							{
								DecodeDistanceBlockSwitch(state);
							}
							state.blockLength[2]--;
							Org.Brotli.Dec.BitReader.FillBitWindow(br);
							state.distanceCode = ReadSymbol(state.hGroup2.codes, state.hGroup2.trees[state.distContextMap[state.distContextMapSlice + (state.copyLength > 4 ? 3 : state.copyLength - 2)] & unchecked((int)(0xFF))], br);
							if (state.distanceCode >= state.numDirectDistanceCodes)
							{
								state.distanceCode -= state.numDirectDistanceCodes;
								int postfix = state.distanceCode & state.distancePostfixMask;
								state.distanceCode = (int)(((uint)state.distanceCode) >> state.distancePostfixBits);
								int n = ((int)(((uint)state.distanceCode) >> 1)) + 1;
								int offset = ((2 + (state.distanceCode & 1)) << n) - 4;
								state.distanceCode = state.numDirectDistanceCodes + postfix + ((offset + Org.Brotli.Dec.BitReader.ReadBits(br, n)) << state.distancePostfixBits);
							}
						}
						// Convert the distance code to the actual distance by possibly looking up past distances
						// from the ringBuffer.
						state.distance = TranslateShortCodes(state.distanceCode, state.distRb, state.distRbIdx);
						if (state.distance < 0)
						{
							throw new Org.Brotli.Dec.BrotliRuntimeException("Negative distance");
						}
						// COV_NF_LINE
						if (state.maxDistance != state.maxBackwardDistance && state.pos < state.maxBackwardDistance)
						{
							state.maxDistance = state.pos;
						}
						else
						{
							state.maxDistance = state.maxBackwardDistance;
						}
						state.copyDst = state.pos;
						if (state.distance > state.maxDistance)
						{
							state.runningState = Org.Brotli.Dec.RunningState.Transform;
							continue;
						}
						if (state.distanceCode > 0)
						{
							state.distRb[state.distRbIdx & 3] = state.distance;
							state.distRbIdx++;
						}
						if (state.copyLength > state.metaBlockLength)
						{
							throw new Org.Brotli.Dec.BrotliRuntimeException("Invalid backward reference");
						}
						// COV_NF_LINE
						state.j = 0;
						state.runningState = Org.Brotli.Dec.RunningState.CopyLoop;
						goto case Org.Brotli.Dec.RunningState.CopyLoop;
					}

					case Org.Brotli.Dec.RunningState.CopyLoop:
					{
						// fall through
						int src = (state.pos - state.distance) & ringBufferMask;
						int dst = state.pos;
						int copyLength = state.copyLength - state.j;
						if ((src + copyLength < ringBufferMask) && (dst + copyLength < ringBufferMask))
						{
							for (int k = 0; k < copyLength; ++k)
							{
								ringBuffer[dst++] = ringBuffer[src++];
							}
							state.j += copyLength;
							state.metaBlockLength -= copyLength;
							state.pos += copyLength;
						}
						else
						{
							for (; state.j < state.copyLength; )
							{
								ringBuffer[state.pos] = ringBuffer[(state.pos - state.distance) & ringBufferMask];
								state.metaBlockLength--;
								state.j++;
								if (state.pos++ == ringBufferMask)
								{
									state.nextRunningState = Org.Brotli.Dec.RunningState.CopyLoop;
									state.bytesToWrite = state.ringBufferSize;
									state.bytesWritten = 0;
									state.runningState = Org.Brotli.Dec.RunningState.Write;
									break;
								}
							}
						}
						if (state.runningState == Org.Brotli.Dec.RunningState.CopyLoop)
						{
							state.runningState = Org.Brotli.Dec.RunningState.MainLoop;
						}
						continue;
					}

					case Org.Brotli.Dec.RunningState.Transform:
					{
						if (state.copyLength >= Org.Brotli.Dec.Dictionary.MinWordLength && state.copyLength <= Org.Brotli.Dec.Dictionary.MaxWordLength)
						{
							int offset = Org.Brotli.Dec.Dictionary.OffsetsByLength[state.copyLength];
							int wordId = state.distance - state.maxDistance - 1;
							int shift = Org.Brotli.Dec.Dictionary.SizeBitsByLength[state.copyLength];
							int mask = (1 << shift) - 1;
							int wordIdx = wordId & mask;
							int transformIdx = (int)(((uint)wordId) >> shift);
							offset += wordIdx * state.copyLength;
							if (transformIdx < Org.Brotli.Dec.Transform.Transforms.Length)
							{
								int len = Org.Brotli.Dec.Transform.TransformDictionaryWord(ringBuffer, state.copyDst, Org.Brotli.Dec.Dictionary.GetData(), offset, state.copyLength, Org.Brotli.Dec.Transform.Transforms[transformIdx]);
								state.copyDst += len;
								state.pos += len;
								state.metaBlockLength -= len;
								if (state.copyDst >= state.ringBufferSize)
								{
									state.nextRunningState = Org.Brotli.Dec.RunningState.CopyWrapBuffer;
									state.bytesToWrite = state.ringBufferSize;
									state.bytesWritten = 0;
									state.runningState = Org.Brotli.Dec.RunningState.Write;
									continue;
								}
							}
							else
							{
								throw new Org.Brotli.Dec.BrotliRuntimeException("Invalid backward reference");
							}
						}
						else
						{
							// COV_NF_LINE
							throw new Org.Brotli.Dec.BrotliRuntimeException("Invalid backward reference");
						}
						// COV_NF_LINE
						state.runningState = Org.Brotli.Dec.RunningState.MainLoop;
						continue;
					}

					case Org.Brotli.Dec.RunningState.CopyWrapBuffer:
					{
						System.Array.Copy(ringBuffer, state.ringBufferSize, ringBuffer, 0, state.copyDst - state.ringBufferSize);
						state.runningState = Org.Brotli.Dec.RunningState.MainLoop;
						continue;
					}

					case Org.Brotli.Dec.RunningState.ReadMetadata:
					{
						while (state.metaBlockLength > 0)
						{
							Org.Brotli.Dec.BitReader.ReadMoreInput(br);
							// Optimize
							Org.Brotli.Dec.BitReader.ReadBits(br, 8);
							state.metaBlockLength--;
						}
						state.runningState = Org.Brotli.Dec.RunningState.BlockStart;
						continue;
					}

					case Org.Brotli.Dec.RunningState.CopyUncompressed:
					{
						CopyUncompressedData(state);
						continue;
					}

					case Org.Brotli.Dec.RunningState.Write:
					{
						if (!WriteRingBuffer(state))
						{
							// Output buffer is full.
							return;
						}
						if (state.pos >= state.maxBackwardDistance)
						{
							state.maxDistance = state.maxBackwardDistance;
						}
						state.pos &= ringBufferMask;
						state.runningState = state.nextRunningState;
						continue;
					}

					default:
					{
						throw new Org.Brotli.Dec.BrotliRuntimeException("Unexpected state " + state.runningState);
					}
				}
			}
			if (state.runningState == Org.Brotli.Dec.RunningState.Finished)
			{
				if (state.metaBlockLength < 0)
				{
					throw new Org.Brotli.Dec.BrotliRuntimeException("Invalid metablock length");
				}
				Org.Brotli.Dec.BitReader.JumpToByteBoundary(br);
				Org.Brotli.Dec.BitReader.CheckHealth(state.br, true);
			}
		}
	}
}