Home | History | Annotate | Download | only in dec
      1 /* Copyright 2015 Google Inc. All Rights Reserved.
      2 
      3    Distributed under MIT license.
      4    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
      5 */
      6 
      7 package org.brotli.dec;
      8 
      9 import java.io.IOException;
     10 import java.io.InputStream;
     11 
     12 /**
     13  * API for Brotli decompression.
     14  */
     15 final class Decode {
     16 
     17   //----------------------------------------------------------------------------
     18   // RunningState
     19   //----------------------------------------------------------------------------
     20   private static final int UNINITIALIZED = 0;
     21   private static final int BLOCK_START = 1;
     22   private static final int COMPRESSED_BLOCK_START = 2;
     23   private static final int MAIN_LOOP = 3;
     24   private static final int READ_METADATA = 4;
     25   private static final int COPY_UNCOMPRESSED = 5;
     26   private static final int INSERT_LOOP = 6;
     27   private static final int COPY_LOOP = 7;
     28   private static final int TRANSFORM = 8;
     29   private static final int FINISHED = 9;
     30   private static final int CLOSED = 10;
     31   private static final int INIT_WRITE = 11;
     32   private static final int WRITE = 12;
     33 
     34   private static final int DEFAULT_CODE_LENGTH = 8;
     35   private static final int CODE_LENGTH_REPEAT_CODE = 16;
     36   private static final int NUM_LITERAL_CODES = 256;
     37   private static final int NUM_INSERT_AND_COPY_CODES = 704;
     38   private static final int NUM_BLOCK_LENGTH_CODES = 26;
     39   private static final int LITERAL_CONTEXT_BITS = 6;
     40   private static final int DISTANCE_CONTEXT_BITS = 2;
     41 
     42   private static final int HUFFMAN_TABLE_BITS = 8;
     43   private static final int HUFFMAN_TABLE_MASK = 0xFF;
     44 
     45   /**
     46    * Maximum possible Huffman table size for an alphabet size of 704, max code length 15 and root
     47    * table bits 8.
     48    */
     49   static final int HUFFMAN_TABLE_SIZE = 1080;
     50 
     51   private static final int CODE_LENGTH_CODES = 18;
     52   private static final int[] CODE_LENGTH_CODE_ORDER = {
     53       1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15,
     54   };
     55 
     56   private static final int NUM_DISTANCE_SHORT_CODES = 16;
     57   private static final int[] DISTANCE_SHORT_CODE_INDEX_OFFSET = {
     58       3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2
     59   };
     60 
     61   private static final int[] DISTANCE_SHORT_CODE_VALUE_OFFSET = {
     62       0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3
     63   };
     64 
     65   /**
     66    * Static Huffman code for the code length code lengths.
     67    */
     68   private static final int[] FIXED_TABLE = {
     69       0x020000, 0x020004, 0x020003, 0x030002, 0x020000, 0x020004, 0x020003, 0x040001,
     70       0x020000, 0x020004, 0x020003, 0x030002, 0x020000, 0x020004, 0x020003, 0x040005
     71   };
     72 
     73   static final int[] DICTIONARY_OFFSETS_BY_LENGTH = {
     74     0, 0, 0, 0, 0, 4096, 9216, 21504, 35840, 44032, 53248, 63488, 74752, 87040, 93696, 100864,
     75     104704, 106752, 108928, 113536, 115968, 118528, 119872, 121280, 122016
     76   };
     77 
     78   static final int[] DICTIONARY_SIZE_BITS_BY_LENGTH = {
     79     0, 0, 0, 0, 10, 10, 11, 11, 10, 10, 10, 10, 10, 9, 9, 8, 7, 7, 8, 7, 7, 6, 6, 5, 5
     80   };
     81 
     82   static final int MIN_WORD_LENGTH = 4;
     83 
     84   static final int MAX_WORD_LENGTH = 24;
     85 
     86   static final int MAX_TRANSFORMED_WORD_LENGTH = 5 + MAX_WORD_LENGTH + 8;
     87 
     88   //----------------------------------------------------------------------------
     89   // Prefix code LUT.
     90   //----------------------------------------------------------------------------
     91   static final int[] BLOCK_LENGTH_OFFSET = {
     92       1, 5, 9, 13, 17, 25, 33, 41, 49, 65, 81, 97, 113, 145, 177, 209, 241, 305, 369, 497,
     93       753, 1265, 2289, 4337, 8433, 16625
     94   };
     95 
     96   static final int[] BLOCK_LENGTH_N_BITS = {
     97       2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 8, 9, 10, 11, 12, 13, 24
     98   };
     99 
    100   static final int[] INSERT_LENGTH_OFFSET = {
    101       0, 1, 2, 3, 4, 5, 6, 8, 10, 14, 18, 26, 34, 50, 66, 98, 130, 194, 322, 578, 1090, 2114, 6210,
    102       22594
    103   };
    104 
    105   static final int[] INSERT_LENGTH_N_BITS = {
    106       0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 12, 14, 24
    107   };
    108 
    109   static final int[] COPY_LENGTH_OFFSET = {
    110       2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 18, 22, 30, 38, 54, 70, 102, 134, 198, 326, 582, 1094,
    111       2118
    112   };
    113 
    114   static final int[] COPY_LENGTH_N_BITS = {
    115       0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 24
    116   };
    117 
    118   static final int[] INSERT_RANGE_LUT = {
    119       0, 0, 8, 8, 0, 16, 8, 16, 16
    120   };
    121 
    122   static final int[] COPY_RANGE_LUT = {
    123       0, 8, 0, 8, 16, 0, 16, 8, 16
    124   };
    125 
    126   private static int decodeWindowBits(State s) {
    127     BitReader.fillBitWindow(s);
    128     if (BitReader.readFewBits(s, 1) == 0) {
    129       return 16;
    130     }
    131     int n = BitReader.readFewBits(s, 3);
    132     if (n != 0) {
    133       return 17 + n;
    134     }
    135     n = BitReader.readFewBits(s, 3);
    136     if (n != 0) {
    137       return 8 + n;
    138     }
    139     return 17;
    140   }
    141 
    142   /**
    143    * Associate input with decoder state.
    144    *
    145    * @param s uninitialized state without associated input
    146    * @param input compressed data source
    147    */
    148   static void initState(State s, InputStream input) {
    149     if (s.runningState != UNINITIALIZED) {
    150       throw new IllegalStateException("State MUST be uninitialized");
    151     }
    152     s.blockTrees = new int[6 * HUFFMAN_TABLE_SIZE];
    153     s.input = input;
    154     BitReader.initBitReader(s);
    155     int windowBits = decodeWindowBits(s);
    156     if (windowBits == 9) { /* Reserved case for future expansion. */
    157       throw new BrotliRuntimeException("Invalid 'windowBits' code");
    158     }
    159     s.maxRingBufferSize = 1 << windowBits;
    160     s.maxBackwardDistance = s.maxRingBufferSize - 16;
    161     s.runningState = BLOCK_START;
    162   }
    163 
    164   static void close(State s) throws IOException {
    165     if (s.runningState == UNINITIALIZED) {
    166       throw new IllegalStateException("State MUST be initialized");
    167     }
    168     if (s.runningState == CLOSED) {
    169       return;
    170     }
    171     s.runningState = CLOSED;
    172     if (s.input != null) {
    173       Utils.closeInput(s.input);
    174       s.input = null;
    175     }
    176   }
    177 
    178   /**
    179    * Decodes a number in the range [0..255], by reading 1 - 11 bits.
    180    */
    181   private static int decodeVarLenUnsignedByte(State s) {
    182     BitReader.fillBitWindow(s);
    183     if (BitReader.readFewBits(s, 1) != 0) {
    184       int n = BitReader.readFewBits(s, 3);
    185       if (n == 0) {
    186         return 1;
    187       } else {
    188         return BitReader.readFewBits(s, n) + (1 << n);
    189       }
    190     }
    191     return 0;
    192   }
    193 
    194   private static void decodeMetaBlockLength(State s) {
    195     BitReader.fillBitWindow(s);
    196     s.inputEnd = BitReader.readFewBits(s, 1);
    197     s.metaBlockLength = 0;
    198     s.isUncompressed = 0;
    199     s.isMetadata = 0;
    200     if ((s.inputEnd != 0) && BitReader.readFewBits(s, 1) != 0) {
    201       return;
    202     }
    203     int sizeNibbles = BitReader.readFewBits(s, 2) + 4;
    204     if (sizeNibbles == 7) {
    205       s.isMetadata = 1;
    206       if (BitReader.readFewBits(s, 1) != 0) {
    207         throw new BrotliRuntimeException("Corrupted reserved bit");
    208       }
    209       int sizeBytes = BitReader.readFewBits(s, 2);
    210       if (sizeBytes == 0) {
    211         return;
    212       }
    213       for (int i = 0; i < sizeBytes; i++) {
    214         BitReader.fillBitWindow(s);
    215         int bits = BitReader.readFewBits(s, 8);
    216         if (bits == 0 && i + 1 == sizeBytes && sizeBytes > 1) {
    217           throw new BrotliRuntimeException("Exuberant nibble");
    218         }
    219         s.metaBlockLength |= bits << (i * 8);
    220       }
    221     } else {
    222       for (int i = 0; i < sizeNibbles; i++) {
    223         BitReader.fillBitWindow(s);
    224         int bits = BitReader.readFewBits(s, 4);
    225         if (bits == 0 && i + 1 == sizeNibbles && sizeNibbles > 4) {
    226           throw new BrotliRuntimeException("Exuberant nibble");
    227         }
    228         s.metaBlockLength |= bits << (i * 4);
    229       }
    230     }
    231     s.metaBlockLength++;
    232     if (s.inputEnd == 0) {
    233       s.isUncompressed = BitReader.readFewBits(s, 1);
    234     }
    235   }
    236 
    237   /**
    238    * Decodes the next Huffman code from bit-stream.
    239    */
    240   private static int readSymbol(int[] table, int offset, State s) {
    241     int val = BitReader.peekBits(s);
    242     offset += val & HUFFMAN_TABLE_MASK;
    243     int bits = table[offset] >> 16;
    244     int sym = table[offset] & 0xFFFF;
    245     if (bits <= HUFFMAN_TABLE_BITS) {
    246       s.bitOffset += bits;
    247       return sym;
    248     }
    249     offset += sym;
    250     int mask = (1 << bits) - 1;
    251     offset += (val & mask) >>> HUFFMAN_TABLE_BITS;
    252     s.bitOffset += ((table[offset] >> 16) + HUFFMAN_TABLE_BITS);
    253     return table[offset] & 0xFFFF;
    254   }
    255 
    256   private static int readBlockLength(int[] table, int offset, State s) {
    257     BitReader.fillBitWindow(s);
    258     int code = readSymbol(table, offset, s);
    259     int n = BLOCK_LENGTH_N_BITS[code];
    260     BitReader.fillBitWindow(s);
    261     return BLOCK_LENGTH_OFFSET[code] + BitReader.readBits(s, n);
    262   }
    263 
    264   private static int translateShortCodes(int code, int[] ringBuffer, int index) {
    265     if (code < NUM_DISTANCE_SHORT_CODES) {
    266       index += DISTANCE_SHORT_CODE_INDEX_OFFSET[code];
    267       index &= 3;
    268       return ringBuffer[index] + DISTANCE_SHORT_CODE_VALUE_OFFSET[code];
    269     }
    270     return code - NUM_DISTANCE_SHORT_CODES + 1;
    271   }
    272 
    273   private static void moveToFront(int[] v, int index) {
    274     int value = v[index];
    275     for (; index > 0; index--) {
    276       v[index] = v[index - 1];
    277     }
    278     v[0] = value;
    279   }
    280 
    281   private static void inverseMoveToFrontTransform(byte[] v, int vLen) {
    282     int[] mtf = new int[256];
    283     for (int i = 0; i < 256; i++) {
    284       mtf[i] = i;
    285     }
    286     for (int i = 0; i < vLen; i++) {
    287       int index = v[i] & 0xFF;
    288       v[i] = (byte) mtf[index];
    289       if (index != 0) {
    290         moveToFront(mtf, index);
    291       }
    292     }
    293   }
    294 
    295   private static void readHuffmanCodeLengths(
    296       int[] codeLengthCodeLengths, int numSymbols, int[] codeLengths, State s) {
    297     int symbol = 0;
    298     int prevCodeLen = DEFAULT_CODE_LENGTH;
    299     int repeat = 0;
    300     int repeatCodeLen = 0;
    301     int space = 32768;
    302     int[] table = new int[32];
    303 
    304     Huffman.buildHuffmanTable(table, 0, 5, codeLengthCodeLengths, CODE_LENGTH_CODES);
    305 
    306     while (symbol < numSymbols && space > 0) {
    307       BitReader.readMoreInput(s);
    308       BitReader.fillBitWindow(s);
    309       int p = BitReader.peekBits(s) & 31;
    310       s.bitOffset += table[p] >> 16;
    311       int codeLen = table[p] & 0xFFFF;
    312       if (codeLen < CODE_LENGTH_REPEAT_CODE) {
    313         repeat = 0;
    314         codeLengths[symbol++] = codeLen;
    315         if (codeLen != 0) {
    316           prevCodeLen = codeLen;
    317           space -= 32768 >> codeLen;
    318         }
    319       } else {
    320         int extraBits = codeLen - 14;
    321         int newLen = 0;
    322         if (codeLen == CODE_LENGTH_REPEAT_CODE) {
    323           newLen = prevCodeLen;
    324         }
    325         if (repeatCodeLen != newLen) {
    326           repeat = 0;
    327           repeatCodeLen = newLen;
    328         }
    329         int oldRepeat = repeat;
    330         if (repeat > 0) {
    331           repeat -= 2;
    332           repeat <<= extraBits;
    333         }
    334         BitReader.fillBitWindow(s);
    335         repeat += BitReader.readFewBits(s, extraBits) + 3;
    336         int repeatDelta = repeat - oldRepeat;
    337         if (symbol + repeatDelta > numSymbols) {
    338           throw new BrotliRuntimeException("symbol + repeatDelta > numSymbols"); // COV_NF_LINE
    339         }
    340         for (int i = 0; i < repeatDelta; i++) {
    341           codeLengths[symbol++] = repeatCodeLen;
    342         }
    343         if (repeatCodeLen != 0) {
    344           space -= repeatDelta << (15 - repeatCodeLen);
    345         }
    346       }
    347     }
    348     if (space != 0) {
    349       throw new BrotliRuntimeException("Unused space"); // COV_NF_LINE
    350     }
    351     // TODO: Pass max_symbol to Huffman table builder instead?
    352     Utils.fillIntsWithZeroes(codeLengths, symbol, numSymbols);
    353   }
    354 
    355   static int checkDupes(int[] symbols, int length) {
    356     for (int i = 0; i < length - 1; ++i) {
    357       for (int j = i + 1; j < length; ++j) {
    358         if (symbols[i] == symbols[j]) {
    359           return 0;
    360         }
    361       }
    362     }
    363     return 1;
    364   }
    365 
    366   // TODO: Use specialized versions for smaller tables.
    367   static void readHuffmanCode(int alphabetSize, int[] table, int offset, State s) {
    368     int ok = 1;
    369     int simpleCodeOrSkip;
    370     BitReader.readMoreInput(s);
    371     // TODO: Avoid allocation.
    372     int[] codeLengths = new int[alphabetSize];
    373     BitReader.fillBitWindow(s);
    374     simpleCodeOrSkip = BitReader.readFewBits(s, 2);
    375     if (simpleCodeOrSkip == 1) { // Read symbols, codes & code lengths directly.
    376       int maxBitsCounter = alphabetSize - 1;
    377       int maxBits = 0;
    378       int[] symbols = new int[4];
    379       int numSymbols = BitReader.readFewBits(s, 2) + 1;
    380       while (maxBitsCounter != 0) {
    381         maxBitsCounter >>= 1;
    382         maxBits++;
    383       }
    384       // TODO: uncomment when codeLengths is reused.
    385       // Utils.fillWithZeroes(codeLengths, 0, alphabetSize);
    386       for (int i = 0; i < numSymbols; i++) {
    387         BitReader.fillBitWindow(s);
    388         symbols[i] = BitReader.readFewBits(s, maxBits) % alphabetSize;
    389         codeLengths[symbols[i]] = 2;
    390       }
    391       codeLengths[symbols[0]] = 1;
    392       switch (numSymbols) {
    393         case 2:
    394           codeLengths[symbols[1]] = 1;
    395           break;
    396         case 4:
    397           if (BitReader.readFewBits(s, 1) == 1) {
    398             codeLengths[symbols[2]] = 3;
    399             codeLengths[symbols[3]] = 3;
    400           } else {
    401             codeLengths[symbols[0]] = 2;
    402           }
    403           break;
    404         default:
    405           break;
    406       }
    407       ok = checkDupes(symbols, numSymbols);
    408     } else { // Decode Huffman-coded code lengths.
    409       int[] codeLengthCodeLengths = new int[CODE_LENGTH_CODES];
    410       int space = 32;
    411       int numCodes = 0;
    412       for (int i = simpleCodeOrSkip; i < CODE_LENGTH_CODES && space > 0; i++) {
    413         int codeLenIdx = CODE_LENGTH_CODE_ORDER[i];
    414         BitReader.fillBitWindow(s);
    415         int p = BitReader.peekBits(s) & 15;
    416         // TODO: Demultiplex FIXED_TABLE.
    417         s.bitOffset += FIXED_TABLE[p] >> 16;
    418         int v = FIXED_TABLE[p] & 0xFFFF;
    419         codeLengthCodeLengths[codeLenIdx] = v;
    420         if (v != 0) {
    421           space -= (32 >> v);
    422           numCodes++;
    423         }
    424       }
    425       if (space != 0 && numCodes != 1) {
    426         ok = 0;
    427       }
    428       readHuffmanCodeLengths(codeLengthCodeLengths, alphabetSize, codeLengths, s);
    429     }
    430     if (ok == 0) {
    431       throw new BrotliRuntimeException("Can't readHuffmanCode"); // COV_NF_LINE
    432     }
    433     Huffman.buildHuffmanTable(table, offset, HUFFMAN_TABLE_BITS, codeLengths, alphabetSize);
    434   }
    435 
    436   private static int decodeContextMap(int contextMapSize, byte[] contextMap, State s) {
    437     BitReader.readMoreInput(s);
    438     int numTrees = decodeVarLenUnsignedByte(s) + 1;
    439 
    440     if (numTrees == 1) {
    441       Utils.fillBytesWithZeroes(contextMap, 0, contextMapSize);
    442       return numTrees;
    443     }
    444 
    445     BitReader.fillBitWindow(s);
    446     int useRleForZeros = BitReader.readFewBits(s, 1);
    447     int maxRunLengthPrefix = 0;
    448     if (useRleForZeros != 0) {
    449       maxRunLengthPrefix = BitReader.readFewBits(s, 4) + 1;
    450     }
    451     int[] table = new int[HUFFMAN_TABLE_SIZE];
    452     readHuffmanCode(numTrees + maxRunLengthPrefix, table, 0, s);
    453     for (int i = 0; i < contextMapSize; ) {
    454       BitReader.readMoreInput(s);
    455       BitReader.fillBitWindow(s);
    456       int code = readSymbol(table, 0, s);
    457       if (code == 0) {
    458         contextMap[i] = 0;
    459         i++;
    460       } else if (code <= maxRunLengthPrefix) {
    461         BitReader.fillBitWindow(s);
    462         int reps = (1 << code) + BitReader.readFewBits(s, code);
    463         while (reps != 0) {
    464           if (i >= contextMapSize) {
    465             throw new BrotliRuntimeException("Corrupted context map"); // COV_NF_LINE
    466           }
    467           contextMap[i] = 0;
    468           i++;
    469           reps--;
    470         }
    471       } else {
    472         contextMap[i] = (byte) (code - maxRunLengthPrefix);
    473         i++;
    474       }
    475     }
    476     BitReader.fillBitWindow(s);
    477     if (BitReader.readFewBits(s, 1) == 1) {
    478       inverseMoveToFrontTransform(contextMap, contextMapSize);
    479     }
    480     return numTrees;
    481   }
    482 
    483   private static int decodeBlockTypeAndLength(State s, int treeType, int numBlockTypes) {
    484     final int[] ringBuffers = s.rings;
    485     final int offset = 4 + treeType * 2;
    486     BitReader.fillBitWindow(s);
    487     int blockType = readSymbol(s.blockTrees, treeType * HUFFMAN_TABLE_SIZE, s);
    488     int result = readBlockLength(s.blockTrees, (treeType + 3) * HUFFMAN_TABLE_SIZE, s);
    489 
    490     if (blockType == 1) {
    491       blockType = ringBuffers[offset + 1] + 1;
    492     } else if (blockType == 0) {
    493       blockType = ringBuffers[offset];
    494     } else {
    495       blockType -= 2;
    496     }
    497     if (blockType >= numBlockTypes) {
    498       blockType -= numBlockTypes;
    499     }
    500     ringBuffers[offset] = ringBuffers[offset + 1];
    501     ringBuffers[offset + 1] = blockType;
    502     return result;
    503   }
    504 
    505   private static void decodeLiteralBlockSwitch(State s) {
    506     s.literalBlockLength = decodeBlockTypeAndLength(s, 0, s.numLiteralBlockTypes);
    507     int literalBlockType = s.rings[5];
    508     s.contextMapSlice = literalBlockType << LITERAL_CONTEXT_BITS;
    509     s.literalTreeIndex = s.contextMap[s.contextMapSlice] & 0xFF;
    510     s.literalTree = s.hGroup0[s.literalTreeIndex];
    511     int contextMode = s.contextModes[literalBlockType];
    512     s.contextLookupOffset1 = contextMode << 9;
    513     s.contextLookupOffset2 = s.contextLookupOffset1 + 256;
    514   }
    515 
    516   private static void decodeCommandBlockSwitch(State s) {
    517     s.commandBlockLength = decodeBlockTypeAndLength(s, 1, s.numCommandBlockTypes);
    518     s.treeCommandOffset = s.hGroup1[s.rings[7]];
    519   }
    520 
    521   private static void decodeDistanceBlockSwitch(State s) {
    522     s.distanceBlockLength = decodeBlockTypeAndLength(s, 2, s.numDistanceBlockTypes);
    523     s.distContextMapSlice = s.rings[9] << DISTANCE_CONTEXT_BITS;
    524   }
    525 
    526   private static void maybeReallocateRingBuffer(State s) {
    527     int newSize = s.maxRingBufferSize;
    528     if (newSize > s.expectedTotalSize) {
    529       /* TODO: Handle 2GB+ cases more gracefully. */
    530       int minimalNewSize = s.expectedTotalSize;
    531       while ((newSize >> 1) > minimalNewSize) {
    532         newSize >>= 1;
    533       }
    534       if ((s.inputEnd == 0) && newSize < 16384 && s.maxRingBufferSize >= 16384) {
    535         newSize = 16384;
    536       }
    537     }
    538     if (newSize <= s.ringBufferSize) {
    539       return;
    540     }
    541     int ringBufferSizeWithSlack = newSize + MAX_TRANSFORMED_WORD_LENGTH;
    542     byte[] newBuffer = new byte[ringBufferSizeWithSlack];
    543     if (s.ringBuffer.length != 0) {
    544       System.arraycopy(s.ringBuffer, 0, newBuffer, 0, s.ringBufferSize);
    545     }
    546     s.ringBuffer = newBuffer;
    547     s.ringBufferSize = newSize;
    548   }
    549 
    550   private static void readNextMetablockHeader(State s) {
    551     if (s.inputEnd != 0) {
    552       s.nextRunningState = FINISHED;
    553       s.runningState = INIT_WRITE;
    554       return;
    555     }
    556     // TODO: Reset? Do we need this?
    557     s.hGroup0 = new int[0];
    558     s.hGroup1 = new int[0];
    559     s.hGroup2 = new int[0];
    560 
    561     BitReader.readMoreInput(s);
    562     decodeMetaBlockLength(s);
    563     if ((s.metaBlockLength == 0) && (s.isMetadata == 0)) {
    564       return;
    565     }
    566     if ((s.isUncompressed != 0) || (s.isMetadata != 0)) {
    567       BitReader.jumpToByteBoundary(s);
    568       s.runningState = (s.isMetadata != 0) ? READ_METADATA : COPY_UNCOMPRESSED;
    569     } else {
    570       s.runningState = COMPRESSED_BLOCK_START;
    571     }
    572 
    573     if (s.isMetadata != 0) {
    574       return;
    575     }
    576     s.expectedTotalSize += s.metaBlockLength;
    577     if (s.expectedTotalSize > 1 << 30) {
    578       s.expectedTotalSize = 1 << 30;
    579     }
    580     if (s.ringBufferSize < s.maxRingBufferSize) {
    581       maybeReallocateRingBuffer(s);
    582     }
    583   }
    584 
    585   private static int readMetablockPartition(State s, int treeType, int numBlockTypes) {
    586     if (numBlockTypes <= 1) {
    587       return 1 << 28;
    588     }
    589     readHuffmanCode(numBlockTypes + 2, s.blockTrees, treeType * HUFFMAN_TABLE_SIZE, s);
    590     readHuffmanCode(NUM_BLOCK_LENGTH_CODES, s.blockTrees, (treeType + 3) * HUFFMAN_TABLE_SIZE, s);
    591     return readBlockLength(s.blockTrees, (treeType + 3) * HUFFMAN_TABLE_SIZE, s);
    592   }
    593 
    594   private static void readMetablockHuffmanCodesAndContextMaps(State s) {
    595     s.numLiteralBlockTypes = decodeVarLenUnsignedByte(s) + 1;
    596     s.literalBlockLength = readMetablockPartition(s, 0, s.numLiteralBlockTypes);
    597     s.numCommandBlockTypes = decodeVarLenUnsignedByte(s) + 1;
    598     s.commandBlockLength = readMetablockPartition(s, 1, s.numCommandBlockTypes);
    599     s.numDistanceBlockTypes = decodeVarLenUnsignedByte(s) + 1;
    600     s.distanceBlockLength = readMetablockPartition(s, 2, s.numDistanceBlockTypes);
    601 
    602     BitReader.readMoreInput(s);
    603     BitReader.fillBitWindow(s);
    604     s.distancePostfixBits = BitReader.readFewBits(s, 2);
    605     s.numDirectDistanceCodes =
    606         NUM_DISTANCE_SHORT_CODES + (BitReader.readFewBits(s, 4) << s.distancePostfixBits);
    607     s.distancePostfixMask = (1 << s.distancePostfixBits) - 1;
    608     int numDistanceCodes = s.numDirectDistanceCodes + (48 << s.distancePostfixBits);
    609     // TODO: Reuse?
    610     s.contextModes = new byte[s.numLiteralBlockTypes];
    611     for (int i = 0; i < s.numLiteralBlockTypes;) {
    612       /* Ensure that less than 256 bits read between readMoreInput. */
    613       int limit = Math.min(i + 96, s.numLiteralBlockTypes);
    614       for (; i < limit; ++i) {
    615         BitReader.fillBitWindow(s);
    616         s.contextModes[i] = (byte) (BitReader.readFewBits(s, 2));
    617       }
    618       BitReader.readMoreInput(s);
    619     }
    620 
    621     // TODO: Reuse?
    622     s.contextMap = new byte[s.numLiteralBlockTypes << LITERAL_CONTEXT_BITS];
    623     int numLiteralTrees = decodeContextMap(s.numLiteralBlockTypes << LITERAL_CONTEXT_BITS,
    624         s.contextMap, s);
    625     s.trivialLiteralContext = 1;
    626     for (int j = 0; j < s.numLiteralBlockTypes << LITERAL_CONTEXT_BITS; j++) {
    627       if (s.contextMap[j] != j >> LITERAL_CONTEXT_BITS) {
    628         s.trivialLiteralContext = 0;
    629         break;
    630       }
    631     }
    632 
    633     // TODO: Reuse?
    634     s.distContextMap = new byte[s.numDistanceBlockTypes << DISTANCE_CONTEXT_BITS];
    635     int numDistTrees = decodeContextMap(s.numDistanceBlockTypes << DISTANCE_CONTEXT_BITS,
    636         s.distContextMap, s);
    637 
    638     s.hGroup0 = decodeHuffmanTreeGroup(NUM_LITERAL_CODES, numLiteralTrees, s);
    639     s.hGroup1 =
    640         decodeHuffmanTreeGroup(NUM_INSERT_AND_COPY_CODES, s.numCommandBlockTypes, s);
    641     s.hGroup2 = decodeHuffmanTreeGroup(numDistanceCodes, numDistTrees, s);
    642 
    643     s.contextMapSlice = 0;
    644     s.distContextMapSlice = 0;
    645     s.contextLookupOffset1 = (int) (s.contextModes[0]) << 9;
    646     s.contextLookupOffset2 = s.contextLookupOffset1 + 256;
    647     s.literalTreeIndex = 0;
    648     s.literalTree = s.hGroup0[0];
    649     s.treeCommandOffset = s.hGroup1[0];
    650 
    651     s.rings[4] = 1;
    652     s.rings[5] = 0;
    653     s.rings[6] = 1;
    654     s.rings[7] = 0;
    655     s.rings[8] = 1;
    656     s.rings[9] = 0;
    657   }
    658 
    659   private static void copyUncompressedData(State s) {
    660     final byte[] ringBuffer = s.ringBuffer;
    661 
    662     // Could happen if block ends at ring buffer end.
    663     if (s.metaBlockLength <= 0) {
    664       BitReader.reload(s);
    665       s.runningState = BLOCK_START;
    666       return;
    667     }
    668 
    669     int chunkLength = Math.min(s.ringBufferSize - s.pos, s.metaBlockLength);
    670     BitReader.copyBytes(s, ringBuffer, s.pos, chunkLength);
    671     s.metaBlockLength -= chunkLength;
    672     s.pos += chunkLength;
    673     if (s.pos == s.ringBufferSize) {
    674         s.nextRunningState = COPY_UNCOMPRESSED;
    675         s.runningState = INIT_WRITE;
    676         return;
    677       }
    678 
    679     BitReader.reload(s);
    680     s.runningState = BLOCK_START;
    681   }
    682 
    683   private static int writeRingBuffer(State s) {
    684     int toWrite = Math.min(s.outputLength - s.outputUsed,
    685         s.ringBufferBytesReady - s.ringBufferBytesWritten);
    686     if (toWrite != 0) {
    687       System.arraycopy(s.ringBuffer, s.ringBufferBytesWritten, s.output,
    688           s.outputOffset + s.outputUsed, toWrite);
    689       s.outputUsed += toWrite;
    690       s.ringBufferBytesWritten += toWrite;
    691     }
    692 
    693     if (s.outputUsed < s.outputLength) {
    694       return 1;
    695     } else {
    696       return 0;
    697     }
    698   }
    699 
    700   private static int[] decodeHuffmanTreeGroup(int alphabetSize, int n, State s) {
    701     int[] group = new int[n + (n * HUFFMAN_TABLE_SIZE)];
    702     int next = n;
    703     for (int i = 0; i < n; i++) {
    704       group[i] = next;
    705       Decode.readHuffmanCode(alphabetSize, group, next, s);
    706       next += HUFFMAN_TABLE_SIZE;
    707     }
    708     return group;
    709   }
    710 
    711   // Returns offset in ringBuffer that should trigger WRITE when filled.
    712   private static int calculateFence(State s) {
    713     int result = s.ringBufferSize;
    714     if (s.isEager != 0) {
    715       result = Math.min(result, s.ringBufferBytesWritten + s.outputLength - s.outputUsed);
    716     }
    717     return result;
    718   }
    719 
    720   /**
    721    * Actual decompress implementation.
    722    */
    723   static void decompress(State s) {
    724     if (s.runningState == UNINITIALIZED) {
    725       throw new IllegalStateException("Can't decompress until initialized");
    726     }
    727     if (s.runningState == CLOSED) {
    728       throw new IllegalStateException("Can't decompress after close");
    729     }
    730     int fence = calculateFence(s);
    731     int ringBufferMask = s.ringBufferSize - 1;
    732     byte[] ringBuffer = s.ringBuffer;
    733 
    734     while (s.runningState != FINISHED) {
    735       // TODO: extract cases to methods for the better readability.
    736       switch (s.runningState) {
    737         case BLOCK_START:
    738           if (s.metaBlockLength < 0) {
    739             throw new BrotliRuntimeException("Invalid metablock length");
    740           }
    741           readNextMetablockHeader(s);
    742           /* Ring-buffer would be reallocated here. */
    743           fence = calculateFence(s);
    744           ringBufferMask = s.ringBufferSize - 1;
    745           ringBuffer = s.ringBuffer;
    746           continue;
    747 
    748         case COMPRESSED_BLOCK_START:
    749           readMetablockHuffmanCodesAndContextMaps(s);
    750           s.runningState = MAIN_LOOP;
    751           // Fall through
    752 
    753         case MAIN_LOOP:
    754           if (s.metaBlockLength <= 0) {
    755             s.runningState = BLOCK_START;
    756             continue;
    757           }
    758           BitReader.readMoreInput(s);
    759           if (s.commandBlockLength == 0) {
    760             decodeCommandBlockSwitch(s);
    761           }
    762           s.commandBlockLength--;
    763           BitReader.fillBitWindow(s);
    764           int cmdCode = readSymbol(s.hGroup1, s.treeCommandOffset, s);
    765           int rangeIdx = cmdCode >>> 6;
    766           s.distanceCode = 0;
    767           if (rangeIdx >= 2) {
    768             rangeIdx -= 2;
    769             s.distanceCode = -1;
    770           }
    771           int insertCode = INSERT_RANGE_LUT[rangeIdx] + ((cmdCode >>> 3) & 7);
    772           BitReader.fillBitWindow(s);
    773           int insertBits = INSERT_LENGTH_N_BITS[insertCode];
    774           int insertExtra = BitReader.readBits(s, insertBits);
    775           s.insertLength = INSERT_LENGTH_OFFSET[insertCode] + insertExtra;
    776           int copyCode = COPY_RANGE_LUT[rangeIdx] + (cmdCode & 7);
    777           BitReader.fillBitWindow(s);
    778           int copyBits = COPY_LENGTH_N_BITS[copyCode];
    779           int copyExtra = BitReader.readBits(s, copyBits);
    780           s.copyLength = COPY_LENGTH_OFFSET[copyCode] + copyExtra;
    781 
    782           s.j = 0;
    783           s.runningState = INSERT_LOOP;
    784 
    785           // Fall through
    786         case INSERT_LOOP:
    787           if (s.trivialLiteralContext != 0) {
    788             while (s.j < s.insertLength) {
    789               BitReader.readMoreInput(s);
    790               if (s.literalBlockLength == 0) {
    791                 decodeLiteralBlockSwitch(s);
    792               }
    793               s.literalBlockLength--;
    794               BitReader.fillBitWindow(s);
    795               ringBuffer[s.pos] =
    796                   (byte) readSymbol(s.hGroup0, s.literalTree, s);
    797               s.pos++;
    798               s.j++;
    799               if (s.pos >= fence) {
    800                 s.nextRunningState = INSERT_LOOP;
    801                 s.runningState = INIT_WRITE;
    802                 break;
    803               }
    804             }
    805           } else {
    806             int prevByte1 = ringBuffer[(s.pos - 1) & ringBufferMask] & 0xFF;
    807             int prevByte2 = ringBuffer[(s.pos - 2) & ringBufferMask] & 0xFF;
    808             while (s.j < s.insertLength) {
    809               BitReader.readMoreInput(s);
    810               if (s.literalBlockLength == 0) {
    811                 decodeLiteralBlockSwitch(s);
    812               }
    813               int literalTreeIndex = s.contextMap[s.contextMapSlice
    814                 + (Context.LOOKUP[s.contextLookupOffset1 + prevByte1]
    815                     | Context.LOOKUP[s.contextLookupOffset2 + prevByte2])] & 0xFF;
    816               s.literalBlockLength--;
    817               prevByte2 = prevByte1;
    818               BitReader.fillBitWindow(s);
    819               prevByte1 = readSymbol(
    820                   s.hGroup0, s.hGroup0[literalTreeIndex], s);
    821               ringBuffer[s.pos] = (byte) prevByte1;
    822               s.pos++;
    823               s.j++;
    824               if (s.pos >= fence) {
    825                 s.nextRunningState = INSERT_LOOP;
    826                 s.runningState = INIT_WRITE;
    827                 break;
    828               }
    829             }
    830           }
    831           if (s.runningState != INSERT_LOOP) {
    832             continue;
    833           }
    834           s.metaBlockLength -= s.insertLength;
    835           if (s.metaBlockLength <= 0) {
    836             s.runningState = MAIN_LOOP;
    837             continue;
    838           }
    839           if (s.distanceCode < 0) {
    840             BitReader.readMoreInput(s);
    841             if (s.distanceBlockLength == 0) {
    842               decodeDistanceBlockSwitch(s);
    843             }
    844             s.distanceBlockLength--;
    845             BitReader.fillBitWindow(s);
    846             s.distanceCode = readSymbol(s.hGroup2, s.hGroup2[
    847                 s.distContextMap[s.distContextMapSlice
    848                     + (s.copyLength > 4 ? 3 : s.copyLength - 2)] & 0xFF], s);
    849             if (s.distanceCode >= s.numDirectDistanceCodes) {
    850               s.distanceCode -= s.numDirectDistanceCodes;
    851               int postfix = s.distanceCode & s.distancePostfixMask;
    852               s.distanceCode >>>= s.distancePostfixBits;
    853               int n = (s.distanceCode >>> 1) + 1;
    854               int offset = ((2 + (s.distanceCode & 1)) << n) - 4;
    855               BitReader.fillBitWindow(s);
    856               int distanceExtra = BitReader.readBits(s, n);
    857               s.distanceCode = s.numDirectDistanceCodes + postfix
    858                   + ((offset + distanceExtra) << s.distancePostfixBits);
    859             }
    860           }
    861 
    862           // Convert the distance code to the actual distance by possibly looking up past distances
    863           // from the ringBuffer.
    864           s.distance = translateShortCodes(s.distanceCode, s.rings, s.distRbIdx);
    865           if (s.distance < 0) {
    866             throw new BrotliRuntimeException("Negative distance"); // COV_NF_LINE
    867           }
    868 
    869           if (s.maxDistance != s.maxBackwardDistance
    870               && s.pos < s.maxBackwardDistance) {
    871             s.maxDistance = s.pos;
    872           } else {
    873             s.maxDistance = s.maxBackwardDistance;
    874           }
    875 
    876           if (s.distance > s.maxDistance) {
    877             s.runningState = TRANSFORM;
    878             continue;
    879           }
    880 
    881           if (s.distanceCode > 0) {
    882             s.rings[s.distRbIdx & 3] = s.distance;
    883             s.distRbIdx++;
    884           }
    885 
    886           if (s.copyLength > s.metaBlockLength) {
    887             throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE
    888           }
    889           s.j = 0;
    890           s.runningState = COPY_LOOP;
    891           // fall through
    892         case COPY_LOOP:
    893           int src = (s.pos - s.distance) & ringBufferMask;
    894           int dst = s.pos;
    895           int copyLength = s.copyLength - s.j;
    896           int srcEnd = src + copyLength;
    897           int dstEnd = dst + copyLength;
    898           if ((srcEnd < ringBufferMask) && (dstEnd < ringBufferMask)) {
    899             if (copyLength < 12 || (srcEnd > dst && dstEnd > src)) {
    900               for (int k = 0; k < copyLength; ++k) {
    901                 ringBuffer[dst++] = ringBuffer[src++];
    902               }
    903             } else {
    904               Utils.copyBytesWithin(ringBuffer, dst, src, srcEnd);
    905             }
    906             s.j += copyLength;
    907             s.metaBlockLength -= copyLength;
    908             s.pos += copyLength;
    909           } else {
    910             for (; s.j < s.copyLength;) {
    911               ringBuffer[s.pos] =
    912                   ringBuffer[(s.pos - s.distance) & ringBufferMask];
    913               s.metaBlockLength--;
    914               s.pos++;
    915               s.j++;
    916               if (s.pos >= fence) {
    917                 s.nextRunningState = COPY_LOOP;
    918                 s.runningState = INIT_WRITE;
    919                 break;
    920               }
    921             }
    922           }
    923           if (s.runningState == COPY_LOOP) {
    924             s.runningState = MAIN_LOOP;
    925           }
    926           continue;
    927 
    928         case TRANSFORM:
    929           if (s.copyLength >= MIN_WORD_LENGTH
    930               && s.copyLength <= MAX_WORD_LENGTH) {
    931             int offset = DICTIONARY_OFFSETS_BY_LENGTH[s.copyLength];
    932             int wordId = s.distance - s.maxDistance - 1;
    933             int shift = DICTIONARY_SIZE_BITS_BY_LENGTH[s.copyLength];
    934             int mask = (1 << shift) - 1;
    935             int wordIdx = wordId & mask;
    936             int transformIdx = wordId >>> shift;
    937             offset += wordIdx * s.copyLength;
    938             if (transformIdx < Transform.NUM_TRANSFORMS) {
    939               int len = Transform.transformDictionaryWord(ringBuffer, s.pos,
    940                   Dictionary.getData(), offset, s.copyLength, transformIdx);
    941               s.pos += len;
    942               s.metaBlockLength -= len;
    943               if (s.pos >= fence) {
    944                 s.nextRunningState = MAIN_LOOP;
    945                 s.runningState = INIT_WRITE;
    946                 continue;
    947               }
    948             } else {
    949               throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE
    950             }
    951           } else {
    952             throw new BrotliRuntimeException("Invalid backward reference"); // COV_NF_LINE
    953           }
    954           s.runningState = MAIN_LOOP;
    955           continue;
    956 
    957         case READ_METADATA:
    958           while (s.metaBlockLength > 0) {
    959             BitReader.readMoreInput(s);
    960             // Optimize
    961             BitReader.fillBitWindow(s);
    962             BitReader.readFewBits(s, 8);
    963             s.metaBlockLength--;
    964           }
    965           s.runningState = BLOCK_START;
    966           continue;
    967 
    968 
    969         case COPY_UNCOMPRESSED:
    970           copyUncompressedData(s);
    971           continue;
    972 
    973         case INIT_WRITE:
    974           s.ringBufferBytesReady = Math.min(s.pos, s.ringBufferSize);
    975           s.runningState = WRITE;
    976           // fall through
    977         case WRITE:
    978           if (writeRingBuffer(s) == 0) {
    979             // Output buffer is full.
    980             return;
    981           }
    982           if (s.pos >= s.maxBackwardDistance) {
    983             s.maxDistance = s.maxBackwardDistance;
    984           }
    985           // Wrap the ringBuffer.
    986           if (s.pos >= s.ringBufferSize) {
    987             if (s.pos > s.ringBufferSize) {
    988               Utils.copyBytesWithin(ringBuffer, 0, s.ringBufferSize, s.pos);
    989             }
    990             s.pos &= ringBufferMask;
    991             s.ringBufferBytesWritten = 0;
    992           }
    993           s.runningState = s.nextRunningState;
    994           continue;
    995 
    996         default:
    997           throw new BrotliRuntimeException("Unexpected state " + s.runningState);
    998       }
    999     }
   1000     if (s.runningState == FINISHED) {
   1001       if (s.metaBlockLength < 0) {
   1002         throw new BrotliRuntimeException("Invalid metablock length");
   1003       }
   1004       BitReader.jumpToByteBoundary(s);
   1005       BitReader.checkHealth(s, 1);
   1006     }
   1007   }
   1008 }
   1009