diff options
Diffstat (limited to 'java/org/brotli/dec/Decode.java')
| -rwxr-xr-x | java/org/brotli/dec/Decode.java | 839 |
1 files changed, 839 insertions, 0 deletions
diff --git a/java/org/brotli/dec/Decode.java b/java/org/brotli/dec/Decode.java new file mode 100755 index 0000000..d7d3bf0 --- /dev/null +++ b/java/org/brotli/dec/Decode.java @@ -0,0 +1,839 @@ +/* Copyright 2015 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +package org.brotli.dec; + +import static org.brotli.dec.RunningState.BLOCK_START; +import static org.brotli.dec.RunningState.CLOSED; +import static org.brotli.dec.RunningState.COMPRESSED_BLOCK_START; +import static org.brotli.dec.RunningState.COPY_LOOP; +import static org.brotli.dec.RunningState.COPY_UNCOMPRESSED; +import static org.brotli.dec.RunningState.COPY_WRAP_BUFFER; +import static org.brotli.dec.RunningState.FINISHED; +import static org.brotli.dec.RunningState.INSERT_LOOP; +import static org.brotli.dec.RunningState.MAIN_LOOP; +import static org.brotli.dec.RunningState.READ_METADATA; +import static org.brotli.dec.RunningState.TRANSFORM; +import static org.brotli.dec.RunningState.UNINITIALIZED; +import static org.brotli.dec.RunningState.WRITE; + +/** + * API for Brotli decompression. + */ +final class Decode { + + private static final int DEFAULT_CODE_LENGTH = 8; + private static final int CODE_LENGTH_REPEAT_CODE = 16; + private static final int NUM_LITERAL_CODES = 256; + private static final int NUM_INSERT_AND_COPY_CODES = 704; + private static final int NUM_BLOCK_LENGTH_CODES = 26; + private static final int LITERAL_CONTEXT_BITS = 6; + private static final int DISTANCE_CONTEXT_BITS = 2; + + private static final int HUFFMAN_TABLE_BITS = 8; + private static final int HUFFMAN_TABLE_MASK = 0xFF; + + private static final int CODE_LENGTH_CODES = 18; + private static final int[] CODE_LENGTH_CODE_ORDER = { + 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15, + }; + + private static final int NUM_DISTANCE_SHORT_CODES = 16; + private static final int[] DISTANCE_SHORT_CODE_INDEX_OFFSET = { + 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 + }; + + private static final int[] DISTANCE_SHORT_CODE_VALUE_OFFSET = { + 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 + }; + + /** + * Static Huffman code for the code length code lengths. + */ + private static final int[] FIXED_TABLE = { + 0x020000, 0x020004, 0x020003, 0x030002, 0x020000, 0x020004, 0x020003, 0x040001, + 0x020000, 0x020004, 0x020003, 0x030002, 0x020000, 0x020004, 0x020003, 0x040005 + }; + + /** + * Decodes a number in the range [0..255], by reading 1 - 11 bits. + */ + private static int decodeVarLenUnsignedByte(BitReader br) { + if (BitReader.readBits(br, 1) != 0) { + int n = BitReader.readBits(br, 3); + if (n == 0) { + return 1; + } else { + return BitReader.readBits(br, n) + (1 << n); + } + } + return 0; + } + + private static void decodeMetaBlockLength(BitReader br, State state) { + state.inputEnd = BitReader.readBits(br, 1) == 1; + state.metaBlockLength = 0; + state.isUncompressed = false; + state.isMetadata = false; + if (state.inputEnd && BitReader.readBits(br, 1) != 0) { + return; + } + int sizeNibbles = BitReader.readBits(br, 2) + 4; + if (sizeNibbles == 7) { + state.isMetadata = true; + if (BitReader.readBits(br, 1) != 0) { + throw new BrotliRuntimeException("Corrupted reserved bit"); + } + int sizeBytes = BitReader.readBits(br, 2); + if (sizeBytes == 0) { + return; + } + for (int i = 0; i < sizeBytes; i++) { + int bits = BitReader.readBits(br, 8); + if (bits == 0 && i + 1 == sizeBytes && sizeBytes > 1) { + throw new BrotliRuntimeException("Exuberant nibble"); + } + state.metaBlockLength |= bits << (i * 8); + } + } else { + for (int i = 0; i < sizeNibbles; i++) { + int bits = BitReader.readBits(br, 4); + if (bits == 0 && i + 1 == sizeNibbles && sizeNibbles > 4) { + throw new BrotliRuntimeException("Exuberant nibble"); + } + state.metaBlockLength |= bits << (i * 4); + } + } + state.metaBlockLength++; + if (!state.inputEnd) { + state.isUncompressed = BitReader.readBits(br, 1) == 1; + } + } + + /** + * Decodes the next Huffman code from bit-stream. + */ + private static int readSymbol(int[] table, int offset, BitReader br) { + BitReader.fillBitWindow(br); + offset += (int) (br.accumulator >>> br.bitOffset) & HUFFMAN_TABLE_MASK; + int n = (table[offset] >> 16) - HUFFMAN_TABLE_BITS; + if (n > 0) { + br.bitOffset += HUFFMAN_TABLE_BITS; + offset += table[offset] & 0xFFFF; + offset += (br.accumulator >>> br.bitOffset) & ((1 << n) - 1); + } + br.bitOffset += table[offset] >> 16; + return table[offset] & 0xFFFF; + } + + private static int readBlockLength(int[] table, int offset, BitReader br) { + int code = readSymbol(table, offset, br); + int n = Prefix.BLOCK_LENGTH_N_BITS[code]; + return Prefix.BLOCK_LENGTH_OFFSET[code] + BitReader.readBits(br, n); + } + + private static int translateShortCodes(int code, int[] ringBuffer, int index) { + if (code < NUM_DISTANCE_SHORT_CODES) { + index += DISTANCE_SHORT_CODE_INDEX_OFFSET[code]; + index &= 3; + return ringBuffer[index] + DISTANCE_SHORT_CODE_VALUE_OFFSET[code]; + } + return code - NUM_DISTANCE_SHORT_CODES + 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] & 0xFF; + v[i] = (byte) mtf[index]; + if (index != 0) { + moveToFront(mtf, index); + } + } + } + + private static void readHuffmanCodeLengths( + int[] codeLengthCodeLengths, int numSymbols, int[] codeLengths, BitReader br) { + int symbol = 0; + int prevCodeLen = DEFAULT_CODE_LENGTH; + int repeat = 0; + int repeatCodeLen = 0; + int space = 32768; + int[] table = new int[32]; + + Huffman.buildHuffmanTable(table, 0, 5, codeLengthCodeLengths, CODE_LENGTH_CODES); + + while (symbol < numSymbols && space > 0) { + BitReader.readMoreInput(br); + BitReader.fillBitWindow(br); + int p = (int) ((br.accumulator >>> br.bitOffset)) & 31; + br.bitOffset += table[p] >> 16; + int codeLen = table[p] & 0xFFFF; + if (codeLen < CODE_LENGTH_REPEAT_CODE) { + repeat = 0; + codeLengths[symbol++] = codeLen; + if (codeLen != 0) { + prevCodeLen = codeLen; + space -= 32768 >> codeLen; + } + } else { + int extraBits = codeLen - 14; + int newLen = 0; + if (codeLen == CODE_LENGTH_REPEAT_CODE) { + newLen = prevCodeLen; + } + if (repeatCodeLen != newLen) { + repeat = 0; + repeatCodeLen = newLen; + } + int oldRepeat = repeat; + if (repeat > 0) { + repeat -= 2; + repeat <<= extraBits; + } + repeat += BitReader.readBits(br, extraBits) + 3; + int repeatDelta = repeat - oldRepeat; + if (symbol + repeatDelta > numSymbols) { + throw new 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 BrotliRuntimeException("Unused space"); // COV_NF_LINE + } + // TODO: Pass max_symbol to Huffman table builder instead? + Utils.fillWithZeroes(codeLengths, symbol, numSymbols - symbol); + } + + // TODO: Use specialized versions for smaller tables. + static void readHuffmanCode(int alphabetSize, int[] table, int offset, BitReader br) { + boolean ok = true; + int simpleCodeOrSkip; + BitReader.readMoreInput(br); + // TODO: Avoid allocation. + int[] codeLengths = new int[alphabetSize]; + simpleCodeOrSkip = 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 = BitReader.readBits(br, 2) + 1; + while (maxBitsCounter != 0) { + maxBitsCounter >>= 1; + maxBits++; + } + Utils.fillWithZeroes(codeLengths, 0, alphabetSize); + for (int i = 0; i < numSymbols; i++) { + symbols[i] = 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: + 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 (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[CODE_LENGTH_CODES]; + int space = 32; + int numCodes = 0; + for (int i = simpleCodeOrSkip; i < CODE_LENGTH_CODES && space > 0; i++) { + int codeLenIdx = CODE_LENGTH_CODE_ORDER[i]; + BitReader.fillBitWindow(br); + int p = (int) (br.accumulator >>> br.bitOffset) & 15; + // TODO: Demultiplex FIXED_TABLE. + br.bitOffset += FIXED_TABLE[p] >> 16; + int v = FIXED_TABLE[p] & 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 BrotliRuntimeException("Can't readHuffmanCode"); // COV_NF_LINE + } + Huffman.buildHuffmanTable(table, offset, HUFFMAN_TABLE_BITS, codeLengths, alphabetSize); + } + + private static int decodeContextMap(int contextMapSize, byte[] contextMap, BitReader br) { + BitReader.readMoreInput(br); + int numTrees = decodeVarLenUnsignedByte(br) + 1; + + if (numTrees == 1) { + Utils.fillWithZeroes(contextMap, 0, contextMapSize); + return numTrees; + } + + boolean useRleForZeros = BitReader.readBits(br, 1) == 1; + int maxRunLengthPrefix = 0; + if (useRleForZeros) { + maxRunLengthPrefix = BitReader.readBits(br, 4) + 1; + } + int[] table = new int[Huffman.HUFFMAN_MAX_TABLE_SIZE]; + readHuffmanCode(numTrees + maxRunLengthPrefix, table, 0, br); + for (int i = 0; i < contextMapSize; ) { + BitReader.readMoreInput(br); + int code = readSymbol(table, 0, br); + if (code == 0) { + contextMap[i] = 0; + i++; + } else if (code <= maxRunLengthPrefix) { + int reps = (1 << code) + BitReader.readBits(br, code); + while (reps != 0) { + if (i >= contextMapSize) { + throw new BrotliRuntimeException("Corrupted context map"); // COV_NF_LINE + } + contextMap[i] = 0; + i++; + reps--; + } + } else { + contextMap[i] = (byte) (code - maxRunLengthPrefix); + i++; + } + } + if (BitReader.readBits(br, 1) == 1) { + inverseMoveToFrontTransform(contextMap, contextMapSize); + } + return numTrees; + } + + private static void decodeBlockTypeAndLength(State state, int treeType) { + final BitReader br = state.br; + final int[] ringBuffers = state.blockTypeRb; + final int offset = treeType * 2; + int blockType = readSymbol( + state.blockTypeTrees, treeType * Huffman.HUFFMAN_MAX_TABLE_SIZE, br); + state.blockLength[treeType] = readBlockLength(state.blockLenTrees, + treeType * Huffman.HUFFMAN_MAX_TABLE_SIZE, 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(State state) { + decodeBlockTypeAndLength(state, 0); + int literalBlockType = state.blockTypeRb[1]; + state.contextMapSlice = literalBlockType << LITERAL_CONTEXT_BITS; + state.literalTreeIndex = state.contextMap[state.contextMapSlice] & 0xFF; + state.literalTree = state.hGroup0.trees[state.literalTreeIndex]; + int contextMode = state.contextModes[literalBlockType]; + state.contextLookupOffset1 = Context.LOOKUP_OFFSETS[contextMode]; + state.contextLookupOffset2 = Context.LOOKUP_OFFSETS[contextMode + 1]; + } + + private static void decodeCommandBlockSwitch(State state) { + decodeBlockTypeAndLength(state, 1); + state.treeCommandOffset = state.hGroup1.trees[state.blockTypeRb[3]]; + } + + private static void decodeDistanceBlockSwitch(State state) { + decodeBlockTypeAndLength(state, 2); + state.distContextMapSlice = state.blockTypeRb[5] << DISTANCE_CONTEXT_BITS; + } + + private static void maybeReallocateRingBuffer(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 + Dictionary.MAX_TRANSFORMED_WORD_LENGTH; + byte[] newBuffer = new byte[ringBufferSizeWithSlack]; + if (state.ringBuffer != null) { + System.arraycopy(state.ringBuffer, 0, newBuffer, 0, state.ringBufferSize); + } else { + /* Prepend custom dictionary, if any. */ + if (state.customDictionary.length != 0) { + int length = state.customDictionary.length; + int offset = 0; + if (length > state.maxBackwardDistance) { + offset = length - state.maxBackwardDistance; + length = state.maxBackwardDistance; + } + System.arraycopy(state.customDictionary, offset, newBuffer, 0, length); + state.pos = length; + state.bytesToIgnore = length; + } + } + state.ringBuffer = newBuffer; + state.ringBufferSize = newSize; + } + + /** + * Reads next metablock header. + * + * @param state decoding state + */ + private static void readMetablockInfo(State state) { + final BitReader br = state.br; + + if (state.inputEnd) { + state.nextRunningState = FINISHED; + state.bytesToWrite = state.pos & (state.ringBufferSize - 1); + state.bytesWritten = 0; + state.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; + + BitReader.readMoreInput(br); + decodeMetaBlockLength(br, state); + if (state.metaBlockLength == 0 && !state.isMetadata) { + return; + } + if (state.isUncompressed || state.isMetadata) { + BitReader.jumpToByteBoundary(br); + state.runningState = state.isMetadata ? READ_METADATA : COPY_UNCOMPRESSED; + } else { + state.runningState = COMPRESSED_BLOCK_START; + } + + if (state.isMetadata) { + return; + } + state.expectedTotalSize += state.metaBlockLength; + if (state.ringBufferSize < state.maxRingBufferSize) { + maybeReallocateRingBuffer(state); + } + } + + private static void readMetablockHuffmanCodesAndContextMaps(State state) { + final 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 * Huffman.HUFFMAN_MAX_TABLE_SIZE, br); + readHuffmanCode(NUM_BLOCK_LENGTH_CODES, state.blockLenTrees, + i * Huffman.HUFFMAN_MAX_TABLE_SIZE, br); + state.blockLength[i] = readBlockLength(state.blockLenTrees, + i * Huffman.HUFFMAN_MAX_TABLE_SIZE, br); + } + } + + BitReader.readMoreInput(br); + state.distancePostfixBits = BitReader.readBits(br, 2); + state.numDirectDistanceCodes = + NUM_DISTANCE_SHORT_CODES + (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 = Math.min(i + 96, state.numBlockTypes[0]); + for (; i < limit; ++i) { + state.contextModes[i] = (byte) (BitReader.readBits(br, 2) << 1); + } + BitReader.readMoreInput(br); + } + + // TODO: Reuse? + state.contextMap = new byte[state.numBlockTypes[0] << LITERAL_CONTEXT_BITS]; + int numLiteralTrees = decodeContextMap(state.numBlockTypes[0] << LITERAL_CONTEXT_BITS, + state.contextMap, br); + state.trivialLiteralContext = true; + for (int j = 0; j < state.numBlockTypes[0] << LITERAL_CONTEXT_BITS; j++) { + if (state.contextMap[j] != j >> LITERAL_CONTEXT_BITS) { + state.trivialLiteralContext = false; + break; + } + } + + // TODO: Reuse? + state.distContextMap = new byte[state.numBlockTypes[2] << DISTANCE_CONTEXT_BITS]; + int numDistTrees = decodeContextMap(state.numBlockTypes[2] << DISTANCE_CONTEXT_BITS, + state.distContextMap, br); + + HuffmanTreeGroup.init(state.hGroup0, NUM_LITERAL_CODES, numLiteralTrees); + HuffmanTreeGroup.init(state.hGroup1, NUM_INSERT_AND_COPY_CODES, state.numBlockTypes[1]); + HuffmanTreeGroup.init(state.hGroup2, numDistanceCodes, numDistTrees); + + HuffmanTreeGroup.decode(state.hGroup0, br); + HuffmanTreeGroup.decode(state.hGroup1, br); + HuffmanTreeGroup.decode(state.hGroup2, br); + + state.contextMapSlice = 0; + state.distContextMapSlice = 0; + state.contextLookupOffset1 = Context.LOOKUP_OFFSETS[state.contextModes[0]]; + state.contextLookupOffset2 = Context.LOOKUP_OFFSETS[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(State state) { + final BitReader br = state.br; + final byte[] ringBuffer = state.ringBuffer; + final int ringBufferMask = state.ringBufferSize - 1; + + while (state.metaBlockLength > 0) { + BitReader.readMoreInput(br); + // Optimize + ringBuffer[state.pos & ringBufferMask] = (byte) (BitReader.readBits(br, 8)); + state.metaBlockLength--; + if ((state.pos++ & ringBufferMask) == ringBufferMask) { + state.nextRunningState = COPY_UNCOMPRESSED; + state.bytesToWrite = state.ringBufferSize; + state.bytesWritten = 0; + state.runningState = WRITE; + return; + } + } + state.runningState = BLOCK_START; + } + + private static boolean writeRingBuffer(State state) { + /* Ignore custom dictionary bytes. */ + if (state.bytesToIgnore != 0) { + state.bytesWritten += state.bytesToIgnore; + state.bytesToIgnore = 0; + } + int toWrite = Math.min(state.outputLength - state.outputUsed, + state.bytesToWrite - state.bytesWritten); + if (toWrite != 0) { + System.arraycopy(state.ringBuffer, state.bytesWritten, state.output, + state.outputOffset + state.outputUsed, toWrite); + state.outputUsed += toWrite; + state.bytesWritten += toWrite; + } + + return state.outputUsed < state.outputLength; + } + + static void setCustomDictionary(State state, byte[] data) { + state.customDictionary = (data == null) ? new byte[0] : data; + } + + /** + * Actual decompress implementation. + */ + static void decompress(State state) { + if (state.runningState == UNINITIALIZED) { + throw new IllegalStateException("Can't decompress until initialized"); + } + if (state.runningState == CLOSED) { + throw new IllegalStateException("Can't decompress after close"); + } + final BitReader br = state.br; + int ringBufferMask = state.ringBufferSize - 1; + byte[] ringBuffer = state.ringBuffer; + + while (state.runningState != FINISHED) { + // TODO: extract cases to methods for the better readability. + switch (state.runningState) { + case BLOCK_START: + if (state.metaBlockLength < 0) { + throw new BrotliRuntimeException("Invalid metablock length"); + } + readMetablockInfo(state); + /* Ring-buffer would be reallocated here. */ + ringBufferMask = state.ringBufferSize - 1; + ringBuffer = state.ringBuffer; + continue; + + case COMPRESSED_BLOCK_START: + readMetablockHuffmanCodesAndContextMaps(state); + state.runningState = MAIN_LOOP; + // Fall through + + case MAIN_LOOP: + if (state.metaBlockLength <= 0) { + // Protect pos from overflow, wrap it around at every GB of input data. + state.pos &= 0x3fffffff; + state.runningState = BLOCK_START; + continue; + } + BitReader.readMoreInput(br); + if (state.blockLength[1] == 0) { + decodeCommandBlockSwitch(state); + } + state.blockLength[1]--; + int cmdCode = readSymbol(state.hGroup1.codes, state.treeCommandOffset, br); + int rangeIdx = cmdCode >>> 6; + state.distanceCode = 0; + if (rangeIdx >= 2) { + rangeIdx -= 2; + state.distanceCode = -1; + } + int insertCode = Prefix.INSERT_RANGE_LUT[rangeIdx] + ((cmdCode >>> 3) & 7); + int copyCode = Prefix.COPY_RANGE_LUT[rangeIdx] + (cmdCode & 7); + state.insertLength = Prefix.INSERT_LENGTH_OFFSET[insertCode] + BitReader + .readBits(br, Prefix.INSERT_LENGTH_N_BITS[insertCode]); + state.copyLength = Prefix.COPY_LENGTH_OFFSET[copyCode] + BitReader + .readBits(br, Prefix.COPY_LENGTH_N_BITS[copyCode]); + + state.j = 0; + state.runningState = INSERT_LOOP; + + // Fall through + case INSERT_LOOP: + if (state.trivialLiteralContext) { + while (state.j < state.insertLength) { + BitReader.readMoreInput(br); + if (state.blockLength[0] == 0) { + decodeLiteralBlockSwitch(state); + } + state.blockLength[0]--; + ringBuffer[state.pos & ringBufferMask] = (byte) readSymbol( + state.hGroup0.codes, state.literalTree, br); + state.j++; + if ((state.pos++ & ringBufferMask) == ringBufferMask) { + state.nextRunningState = INSERT_LOOP; + state.bytesToWrite = state.ringBufferSize; + state.bytesWritten = 0; + state.runningState = WRITE; + break; + } + } + } else { + int prevByte1 = ringBuffer[(state.pos - 1) & ringBufferMask] & 0xFF; + int prevByte2 = ringBuffer[(state.pos - 2) & ringBufferMask] & 0xFF; + while (state.j < state.insertLength) { + BitReader.readMoreInput(br); + if (state.blockLength[0] == 0) { + decodeLiteralBlockSwitch(state); + } + int literalTreeIndex = state.contextMap[state.contextMapSlice + + (Context.LOOKUP[state.contextLookupOffset1 + prevByte1] + | Context.LOOKUP[state.contextLookupOffset2 + prevByte2])] & 0xFF; + state.blockLength[0]--; + prevByte2 = prevByte1; + prevByte1 = readSymbol( + state.hGroup0.codes, state.hGroup0.trees[literalTreeIndex], br); + ringBuffer[state.pos & ringBufferMask] = (byte) prevByte1; + state.j++; + if ((state.pos++ & ringBufferMask) == ringBufferMask) { + state.nextRunningState = INSERT_LOOP; + state.bytesToWrite = state.ringBufferSize; + state.bytesWritten = 0; + state.runningState = WRITE; + break; + } + } + } + if (state.runningState != INSERT_LOOP) { + continue; + } + state.metaBlockLength -= state.insertLength; + if (state.metaBlockLength <= 0) { + state.runningState = MAIN_LOOP; + continue; + } + if (state.distanceCode < 0) { + BitReader.readMoreInput(br); + if (state.blockLength[2] == 0) { + decodeDistanceBlockSwitch(state); + } + state.blockLength[2]--; + state.distanceCode = readSymbol(state.hGroup2.codes, state.hGroup2.trees[ + state.distContextMap[state.distContextMapSlice + + (state.copyLength > 4 ? 3 : state.copyLength - 2)] & 0xFF], br); + if (state.distanceCode >= state.numDirectDistanceCodes) { + state.distanceCode -= state.numDirectDistanceCodes; + int postfix = state.distanceCode & state.distancePostfixMask; + state.distanceCode >>>= state.distancePostfixBits; + int n = (state.distanceCode >>> 1) + 1; + int offset = ((2 + (state.distanceCode & 1)) << n) - 4; + state.distanceCode = state.numDirectDistanceCodes + postfix + + ((offset + 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 BrotliRuntimeException("Negative distance"); // COV_NF_LINE + } + + if (state.pos < state.maxBackwardDistance + && state.maxDistance != state.maxBackwardDistance) { + state.maxDistance = state.pos; + } else { + state.maxDistance = state.maxBackwardDistance; + } + + state.copyDst = state.pos & ringBufferMask; + if (state.distance > state.maxDistance) { + state.runningState = TRANSFORM; + continue; + } + + if (state.distanceCode > 0) { + state.distRb[state.distRbIdx & 3] = state.distance; + state.distRbIdx++; + } + + if (state.copyLength > state.metaBlockLength) { + throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE + } + state.j = 0; + state.runningState = COPY_LOOP; + // fall through + case COPY_LOOP: + for (; state.j < state.copyLength;) { + ringBuffer[state.pos & ringBufferMask] = + ringBuffer[(state.pos - state.distance) & ringBufferMask]; + // TODO: condense + state.metaBlockLength--; + state.j++; + if ((state.pos++ & ringBufferMask) == ringBufferMask) { + state.nextRunningState = COPY_LOOP; + state.bytesToWrite = state.ringBufferSize; + state.bytesWritten = 0; + state.runningState = WRITE; + break; + } + } + if (state.runningState == COPY_LOOP) { + state.runningState = MAIN_LOOP; + } + continue; + + case TRANSFORM: + if (state.copyLength >= Dictionary.MIN_WORD_LENGTH + && state.copyLength <= Dictionary.MAX_WORD_LENGTH) { + int offset = Dictionary.OFFSETS_BY_LENGTH[state.copyLength]; + int wordId = state.distance - state.maxDistance - 1; + int shift = Dictionary.SIZE_BITS_BY_LENGTH[state.copyLength]; + int mask = (1 << shift) - 1; + int wordIdx = wordId & mask; + int transformIdx = wordId >>> shift; + offset += wordIdx * state.copyLength; + if (transformIdx < Transform.TRANSFORMS.length) { + int len = Transform.transformDictionaryWord(ringBuffer, state.copyDst, + Dictionary.getData(), offset, state.copyLength, + Transform.TRANSFORMS[transformIdx]); + state.copyDst += len; + state.pos += len; + state.metaBlockLength -= len; + if (state.copyDst >= state.ringBufferSize) { + state.nextRunningState = COPY_WRAP_BUFFER; + state.bytesToWrite = state.ringBufferSize; + state.bytesWritten = 0; + state.runningState = WRITE; + continue; + } + } else { + throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE + } + } else { + throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE + } + state.runningState = MAIN_LOOP; + continue; + + case COPY_WRAP_BUFFER: + System.arraycopy(ringBuffer, state.ringBufferSize, ringBuffer, 0, + state.copyDst - state.ringBufferSize); + state.runningState = MAIN_LOOP; + continue; + + case READ_METADATA: + while (state.metaBlockLength > 0) { + BitReader.readMoreInput(br); + // Optimize + BitReader.readBits(br, 8); + state.metaBlockLength--; + } + state.runningState = BLOCK_START; + continue; + + + case COPY_UNCOMPRESSED: + copyUncompressedData(state); + continue; + + case WRITE: + if (!writeRingBuffer(state)) { + // Output buffer is full. + return; + } + state.runningState = state.nextRunningState; + continue; + + default: + throw new BrotliRuntimeException("Unexpected state " + state.runningState); + } + } + if (state.runningState == FINISHED) { + if (state.metaBlockLength < 0) { + throw new BrotliRuntimeException("Invalid metablock length"); + } + BitReader.jumpToByteBoundary(br); + BitReader.checkHealth(state.br); + } + } +} |