View Javadoc
1   /*
2    * Copyright 2014 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  package io.netty.handler.codec.compression;
17  
18  import io.netty.buffer.ByteBuf;
19  import io.netty.channel.ChannelHandlerContext;
20  import io.netty.handler.codec.ByteToMessageDecoder;
21  
22  import java.util.List;
23  
24  import static io.netty.handler.codec.compression.Bzip2Constants.*;
25  
26  /**
27   * Uncompresses a {@link ByteBuf} encoded with the Bzip2 format.
28   *
29   * See <a href="http://en.wikipedia.org/wiki/Bzip2">Bzip2</a>.
30   */
31  public class Bzip2Decoder extends ByteToMessageDecoder {
32      /**
33       * Current state of stream.
34       */
35      private enum State {
36          INIT,
37          INIT_BLOCK,
38          INIT_BLOCK_PARAMS,
39          RECEIVE_HUFFMAN_USED_MAP,
40          RECEIVE_HUFFMAN_USED_BITMAPS,
41          RECEIVE_SELECTORS_NUMBER,
42          RECEIVE_SELECTORS,
43          RECEIVE_HUFFMAN_LENGTH,
44          DECODE_HUFFMAN_DATA,
45          EOF
46      }
47      private State currentState = State.INIT;
48  
49      /**
50       * A reader that provides bit-level reads.
51       */
52      private final Bzip2BitReader reader = new Bzip2BitReader();
53  
54      /**
55       * The decompressor for the current block.
56       */
57      private Bzip2BlockDecompressor blockDecompressor;
58  
59      /**
60       * Bzip2 Huffman coding stage.
61       */
62      private Bzip2HuffmanStageDecoder huffmanStageDecoder;
63  
64      /**
65       * Always: in the range 0 .. 9. The current block size is 100000 * this number.
66       */
67      private int blockSize;
68  
69      /**
70       * The CRC of the current block as read from the block header.
71       */
72      private int blockCRC;
73  
74      /**
75       * The merged CRC of all blocks decompressed so far.
76       */
77      private int streamCRC;
78  
79      @Override
80      protected void decode(ChannelHandlerContext ctx, ByteBuf in, List<Object> out) throws Exception {
81          if (!in.isReadable()) {
82              return;
83          }
84  
85          final Bzip2BitReader reader = this.reader;
86          reader.setByteBuf(in);
87  
88          for (;;) {
89              switch (currentState) {
90              case INIT:
91                  if (in.readableBytes() < 4) {
92                      return;
93                  }
94                  int magicNumber = in.readUnsignedMedium();
95                  if (magicNumber != MAGIC_NUMBER) {
96                      throw new DecompressionException("Unexpected stream identifier contents. Mismatched bzip2 " +
97                              "protocol version?");
98                  }
99                  int blockSize = in.readByte() - '0';
100                 if (blockSize < MIN_BLOCK_SIZE || blockSize > MAX_BLOCK_SIZE) {
101                     throw new DecompressionException("block size is invalid");
102                 }
103                 this.blockSize = blockSize * BASE_BLOCK_SIZE;
104 
105                 streamCRC = 0;
106                 currentState = State.INIT_BLOCK;
107             case INIT_BLOCK:
108                 if (!reader.hasReadableBytes(10)) {
109                     return;
110                 }
111                 // Get the block magic bytes.
112                 final int magic1 = reader.readBits(24);
113                 final int magic2 = reader.readBits(24);
114                 if (magic1 == END_OF_STREAM_MAGIC_1 && magic2 == END_OF_STREAM_MAGIC_2) {
115                     // End of stream was reached. Check the combined CRC.
116                     final int storedCombinedCRC = reader.readInt();
117                     if (storedCombinedCRC != streamCRC) {
118                         throw new DecompressionException("stream CRC error");
119                     }
120                     currentState = State.EOF;
121                     break;
122                 }
123                 if (magic1 != BLOCK_HEADER_MAGIC_1 || magic2 != BLOCK_HEADER_MAGIC_2) {
124                     throw new DecompressionException("bad block header");
125                 }
126                 blockCRC = reader.readInt();
127                 currentState = State.INIT_BLOCK_PARAMS;
128             case INIT_BLOCK_PARAMS:
129                 if (!reader.hasReadableBits(25)) {
130                     return;
131                 }
132                 final boolean blockRandomised = reader.readBoolean();
133                 final int bwtStartPointer = reader.readBits(24);
134 
135                 blockDecompressor = new Bzip2BlockDecompressor(this.blockSize, blockCRC,
136                                                                 blockRandomised, bwtStartPointer, reader);
137                 currentState = State.RECEIVE_HUFFMAN_USED_MAP;
138             case RECEIVE_HUFFMAN_USED_MAP:
139                 if (!reader.hasReadableBits(16)) {
140                     return;
141                 }
142                 blockDecompressor.huffmanInUse16 = reader.readBits(16);
143                 currentState = State.RECEIVE_HUFFMAN_USED_BITMAPS;
144             case RECEIVE_HUFFMAN_USED_BITMAPS:
145                 Bzip2BlockDecompressor blockDecompressor = this.blockDecompressor;
146                 final int inUse16 = blockDecompressor.huffmanInUse16;
147                 final int bitNumber = Integer.bitCount(inUse16);
148                 final byte[] huffmanSymbolMap = blockDecompressor.huffmanSymbolMap;
149 
150                 if (!reader.hasReadableBits(bitNumber * HUFFMAN_SYMBOL_RANGE_SIZE + 3)) {
151                     return;
152                 }
153 
154                 int huffmanSymbolCount = 0;
155                 if (bitNumber > 0) {
156                     for (int i = 0; i < 16; i++) {
157                         if ((inUse16 & 1 << 15 >>> i) != 0) {
158                             for (int j = 0, k = i << 4; j < HUFFMAN_SYMBOL_RANGE_SIZE; j++, k++) {
159                                 if (reader.readBoolean()) {
160                                     huffmanSymbolMap[huffmanSymbolCount++] = (byte) k;
161                                 }
162                             }
163                         }
164                     }
165                 }
166                 blockDecompressor.huffmanEndOfBlockSymbol = huffmanSymbolCount + 1;
167 
168                 int totalTables = reader.readBits(3);
169                 if (totalTables < HUFFMAN_MINIMUM_TABLES || totalTables > HUFFMAN_MAXIMUM_TABLES) {
170                     throw new DecompressionException("incorrect huffman groups number");
171                 }
172                 int alphaSize = huffmanSymbolCount + 2;
173                 if (alphaSize > HUFFMAN_MAX_ALPHABET_SIZE) {
174                     throw new DecompressionException("incorrect alphabet size");
175                 }
176                 huffmanStageDecoder = new Bzip2HuffmanStageDecoder(reader, totalTables, alphaSize);
177                 currentState = State.RECEIVE_SELECTORS_NUMBER;
178             case RECEIVE_SELECTORS_NUMBER:
179                 if (!reader.hasReadableBits(15)) {
180                     return;
181                 }
182                 int totalSelectors = reader.readBits(15);
183                 if (totalSelectors < 1 || totalSelectors > MAX_SELECTORS) {
184                     throw new DecompressionException("incorrect selectors number");
185                 }
186                 huffmanStageDecoder.selectors = new byte[totalSelectors];
187 
188                 currentState = State.RECEIVE_SELECTORS;
189             case RECEIVE_SELECTORS:
190                 Bzip2HuffmanStageDecoder huffmanStageDecoder = this.huffmanStageDecoder;
191                 byte[] selectors = huffmanStageDecoder.selectors;
192                 totalSelectors = selectors.length;
193                 final Bzip2MoveToFrontTable tableMtf = huffmanStageDecoder.tableMTF;
194 
195                 int currSelector;
196                 // Get zero-terminated bit runs (0..62) of MTF'ed Huffman table. length = 1..6
197                 for (currSelector = huffmanStageDecoder.currentSelector;
198                             currSelector < totalSelectors; currSelector++) {
199                     if (!reader.hasReadableBits(HUFFMAN_SELECTOR_LIST_MAX_LENGTH)) {
200                         // Save state if end of current ByteBuf was reached
201                         huffmanStageDecoder.currentSelector = currSelector;
202                         return;
203                     }
204                     int index = 0;
205                     while (reader.readBoolean()) {
206                         index++;
207                     }
208                     selectors[currSelector] = tableMtf.indexToFront(index);
209                 }
210 
211                 currentState = State.RECEIVE_HUFFMAN_LENGTH;
212             case RECEIVE_HUFFMAN_LENGTH:
213                 huffmanStageDecoder = this.huffmanStageDecoder;
214                 totalTables = huffmanStageDecoder.totalTables;
215                 final byte[][] codeLength = huffmanStageDecoder.tableCodeLengths;
216                 alphaSize = huffmanStageDecoder.alphabetSize;
217 
218                 /* Now the coding tables */
219                 int currGroup;
220                 int currLength = huffmanStageDecoder.currentLength;
221                 int currAlpha = 0;
222                 boolean modifyLength = huffmanStageDecoder.modifyLength;
223                 boolean saveStateAndReturn = false;
224                 loop: for (currGroup = huffmanStageDecoder.currentGroup; currGroup < totalTables; currGroup++) {
225                     // start_huffman_length
226                     if (!reader.hasReadableBits(5)) {
227                         saveStateAndReturn = true;
228                         break;
229                     }
230                     if (currLength < 0) {
231                         currLength = reader.readBits(5);
232                     }
233                     for (currAlpha = huffmanStageDecoder.currentAlpha; currAlpha < alphaSize; currAlpha++) {
234                         // delta_bit_length: 1..40
235                         if (!reader.isReadable()) {
236                             saveStateAndReturn = true;
237                             break loop;
238                         }
239                         while (modifyLength || reader.readBoolean()) {  // 0=>next symbol; 1=>alter length
240                             if (!reader.isReadable()) {
241                                 modifyLength = true;
242                                 saveStateAndReturn = true;
243                                 break loop;
244                             }
245                             // 1=>decrement length;  0=>increment length
246                             currLength += reader.readBoolean() ? -1 : 1;
247                             modifyLength = false;
248                             if (!reader.isReadable()) {
249                                 saveStateAndReturn = true;
250                                 break loop;
251                             }
252                         }
253                         codeLength[currGroup][currAlpha] = (byte) currLength;
254                     }
255                     currLength = -1;
256                     currAlpha = huffmanStageDecoder.currentAlpha = 0;
257                     modifyLength = false;
258                 }
259                 if (saveStateAndReturn) {
260                     // Save state if end of current ByteBuf was reached
261                     huffmanStageDecoder.currentGroup = currGroup;
262                     huffmanStageDecoder.currentLength = currLength;
263                     huffmanStageDecoder.currentAlpha = currAlpha;
264                     huffmanStageDecoder.modifyLength = modifyLength;
265                     return;
266                 }
267 
268                 // Finally create the Huffman tables
269                 huffmanStageDecoder.createHuffmanDecodingTables();
270                 currentState = State.DECODE_HUFFMAN_DATA;
271             case DECODE_HUFFMAN_DATA:
272                 blockDecompressor = this.blockDecompressor;
273                 final int oldReaderIndex = in.readerIndex();
274                 final boolean decoded = blockDecompressor.decodeHuffmanData(this.huffmanStageDecoder);
275                 if (!decoded) {
276                     return;
277                 }
278                 // It used to avoid "Bzip2Decoder.decode() did not read anything but decoded a message" exception.
279                 // Because previous operation may read only a few bits from Bzip2BitReader.bitBuffer and
280                 // don't read incomming ByteBuf.
281                 if (in.readerIndex() == oldReaderIndex && in.isReadable()) {
282                     reader.refill();
283                 }
284 
285                 final int blockLength = blockDecompressor.blockLength();
286                 final ByteBuf uncompressed = ctx.alloc().buffer(blockLength);
287                 boolean success = false;
288                 try {
289                     int uncByte;
290                     while ((uncByte = blockDecompressor.read()) >= 0) {
291                         uncompressed.writeByte(uncByte);
292                     }
293 
294                     int currentBlockCRC = blockDecompressor.checkCRC();
295                     streamCRC = (streamCRC << 1 | streamCRC >>> 31) ^ currentBlockCRC;
296 
297                     out.add(uncompressed);
298                     success = true;
299                 } finally {
300                     if (!success) {
301                         uncompressed.release();
302                     }
303                 }
304                 currentState = State.INIT_BLOCK;
305                 break;
306             case EOF:
307                 in.skipBytes(in.readableBytes());
308                 return;
309             default:
310                 throw new IllegalStateException();
311             }
312         }
313     }
314 
315     /**
316      * Returns {@code true} if and only if the end of the compressed stream
317      * has been reached.
318      */
319     public boolean isClosed() {
320         return currentState == State.EOF;
321     }
322 }