kc3-lang/brotli/java/dec/Decode.java

• Show log

  Commit

• Hash : 5025365d
  Author :
  Date : 2016-10-17T14:04:59
  

  Add Java port of Brotli decoder.
  

Download

• java/dec/Decode.java

• /* 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.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.
   */
  public 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;
    }
  
    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
     */
    static void readMeablockInfo(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.jumpToByteBoundry(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);
      }
    }
  
    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;
    }
  
    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;
    }
  
    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");
      }
      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");
            }
            readMeablockInfo(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.jumpToByteBoundry(br);
        BitReader.checkHealth(state.br);
      }
    }
  }
  

Download