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                  // fall through
108             case INIT_BLOCK:
109                 if (!reader.hasReadableBytes(10)) {
110                     return;
111                 }
112                 // Get the block magic bytes.
113                 final int magic1 = reader.readBits(24);
114                 final int magic2 = reader.readBits(24);
115                 if (magic1 == END_OF_STREAM_MAGIC_1 && magic2 == END_OF_STREAM_MAGIC_2) {
116                     // End of stream was reached. Check the combined CRC.
117                     final int storedCombinedCRC = reader.readInt();
118                     if (storedCombinedCRC != streamCRC) {
119                         throw new DecompressionException("stream CRC error");
120                     }
121                     currentState = State.EOF;
122                     break;
123                 }
124                 if (magic1 != BLOCK_HEADER_MAGIC_1 || magic2 != BLOCK_HEADER_MAGIC_2) {
125                     throw new DecompressionException("bad block header");
126                 }
127                 blockCRC = reader.readInt();
128                 currentState = State.INIT_BLOCK_PARAMS;
129                 // fall through
130             case INIT_BLOCK_PARAMS:
131                 if (!reader.hasReadableBits(25)) {
132                     return;
133                 }
134                 final boolean blockRandomised = reader.readBoolean();
135                 final int bwtStartPointer = reader.readBits(24);
136 
137                 blockDecompressor = new Bzip2BlockDecompressor(this.blockSize, blockCRC,
138                                                                 blockRandomised, bwtStartPointer, reader);
139                 currentState = State.RECEIVE_HUFFMAN_USED_MAP;
140                 // fall through
141             case RECEIVE_HUFFMAN_USED_MAP:
142                 if (!reader.hasReadableBits(16)) {
143                     return;
144                 }
145                 blockDecompressor.huffmanInUse16 = reader.readBits(16);
146                 currentState = State.RECEIVE_HUFFMAN_USED_BITMAPS;
147                 // fall through
148             case RECEIVE_HUFFMAN_USED_BITMAPS:
149                 Bzip2BlockDecompressor blockDecompressor = this.blockDecompressor;
150                 final int inUse16 = blockDecompressor.huffmanInUse16;
151                 final int bitNumber = Integer.bitCount(inUse16);
152                 final byte[] huffmanSymbolMap = blockDecompressor.huffmanSymbolMap;
153 
154                 if (!reader.hasReadableBits(bitNumber * HUFFMAN_SYMBOL_RANGE_SIZE + 3)) {
155                     return;
156                 }
157 
158                 int huffmanSymbolCount = 0;
159                 if (bitNumber > 0) {
160                     for (int i = 0; i < 16; i++) {
161                         if ((inUse16 & 1 << 15 >>> i) != 0) {
162                             for (int j = 0, k = i << 4; j < HUFFMAN_SYMBOL_RANGE_SIZE; j++, k++) {
163                                 if (reader.readBoolean()) {
164                                     huffmanSymbolMap[huffmanSymbolCount++] = (byte) k;
165                                 }
166                             }
167                         }
168                     }
169                 }
170                 blockDecompressor.huffmanEndOfBlockSymbol = huffmanSymbolCount + 1;
171 
172                 int totalTables = reader.readBits(3);
173                 if (totalTables < HUFFMAN_MINIMUM_TABLES || totalTables > HUFFMAN_MAXIMUM_TABLES) {
174                     throw new DecompressionException("incorrect huffman groups number");
175                 }
176                 int alphaSize = huffmanSymbolCount + 2;
177                 if (alphaSize > HUFFMAN_MAX_ALPHABET_SIZE) {
178                     throw new DecompressionException("incorrect alphabet size");
179                 }
180                 huffmanStageDecoder = new Bzip2HuffmanStageDecoder(reader, totalTables, alphaSize);
181                 currentState = State.RECEIVE_SELECTORS_NUMBER;
182                 // fall through
183             case RECEIVE_SELECTORS_NUMBER:
184                 if (!reader.hasReadableBits(15)) {
185                     return;
186                 }
187                 int totalSelectors = reader.readBits(15);
188                 if (totalSelectors < 1 || totalSelectors > MAX_SELECTORS) {
189                     throw new DecompressionException("incorrect selectors number");
190                 }
191                 huffmanStageDecoder.selectors = new byte[totalSelectors];
192 
193                 currentState = State.RECEIVE_SELECTORS;
194                 // fall through
195             case RECEIVE_SELECTORS:
196                 Bzip2HuffmanStageDecoder huffmanStageDecoder = this.huffmanStageDecoder;
197                 byte[] selectors = huffmanStageDecoder.selectors;
198                 totalSelectors = selectors.length;
199                 final Bzip2MoveToFrontTable tableMtf = huffmanStageDecoder.tableMTF;
200 
201                 int currSelector;
202                 // Get zero-terminated bit runs (0..62) of MTF'ed Huffman table. length = 1..6
203                 for (currSelector = huffmanStageDecoder.currentSelector;
204                             currSelector < totalSelectors; currSelector++) {
205                     if (!reader.hasReadableBits(HUFFMAN_SELECTOR_LIST_MAX_LENGTH)) {
206                         // Save state if end of current ByteBuf was reached
207                         huffmanStageDecoder.currentSelector = currSelector;
208                         return;
209                     }
210                     int index = 0;
211                     while (reader.readBoolean()) {
212                         index++;
213                     }
214                     selectors[currSelector] = tableMtf.indexToFront(index);
215                 }
216 
217                 currentState = State.RECEIVE_HUFFMAN_LENGTH;
218                 // fall through
219             case RECEIVE_HUFFMAN_LENGTH:
220                 huffmanStageDecoder = this.huffmanStageDecoder;
221                 totalTables = huffmanStageDecoder.totalTables;
222                 final byte[][] codeLength = huffmanStageDecoder.tableCodeLengths;
223                 alphaSize = huffmanStageDecoder.alphabetSize;
224 
225                 /* Now the coding tables */
226                 int currGroup;
227                 int currLength = huffmanStageDecoder.currentLength;
228                 int currAlpha = 0;
229                 boolean modifyLength = huffmanStageDecoder.modifyLength;
230                 boolean saveStateAndReturn = false;
231                 loop: for (currGroup = huffmanStageDecoder.currentGroup; currGroup < totalTables; currGroup++) {
232                     // start_huffman_length
233                     if (!reader.hasReadableBits(5)) {
234                         saveStateAndReturn = true;
235                         break;
236                     }
237                     if (currLength < 0) {
238                         currLength = reader.readBits(5);
239                     }
240                     for (currAlpha = huffmanStageDecoder.currentAlpha; currAlpha < alphaSize; currAlpha++) {
241                         // delta_bit_length: 1..40
242                         if (!reader.isReadable()) {
243                             saveStateAndReturn = true;
244                             break loop;
245                         }
246                         while (modifyLength || reader.readBoolean()) {  // 0=>next symbol; 1=>alter length
247                             if (!reader.isReadable()) {
248                                 modifyLength = true;
249                                 saveStateAndReturn = true;
250                                 break loop;
251                             }
252                             // 1=>decrement length;  0=>increment length
253                             currLength += reader.readBoolean() ? -1 : 1;
254                             modifyLength = false;
255                             if (!reader.isReadable()) {
256                                 saveStateAndReturn = true;
257                                 break loop;
258                             }
259                         }
260                         codeLength[currGroup][currAlpha] = (byte) currLength;
261                     }
262                     currLength = -1;
263                     currAlpha = huffmanStageDecoder.currentAlpha = 0;
264                     modifyLength = false;
265                 }
266                 if (saveStateAndReturn) {
267                     // Save state if end of current ByteBuf was reached
268                     huffmanStageDecoder.currentGroup = currGroup;
269                     huffmanStageDecoder.currentLength = currLength;
270                     huffmanStageDecoder.currentAlpha = currAlpha;
271                     huffmanStageDecoder.modifyLength = modifyLength;
272                     return;
273                 }
274 
275                 // Finally create the Huffman tables
276                 huffmanStageDecoder.createHuffmanDecodingTables();
277                 currentState = State.DECODE_HUFFMAN_DATA;
278                 // fall through
279             case DECODE_HUFFMAN_DATA:
280                 blockDecompressor = this.blockDecompressor;
281                 final int oldReaderIndex = in.readerIndex();
282                 final boolean decoded = blockDecompressor.decodeHuffmanData(this.huffmanStageDecoder);
283                 if (!decoded) {
284                     return;
285                 }
286                 // It used to avoid "Bzip2Decoder.decode() did not read anything but decoded a message" exception.
287                 // Because previous operation may read only a few bits from Bzip2BitReader.bitBuffer and
288                 // don't read incoming ByteBuf.
289                 if (in.readerIndex() == oldReaderIndex && in.isReadable()) {
290                     reader.refill();
291                 }
292 
293                 final int blockLength = blockDecompressor.blockLength();
294                 final ByteBuf uncompressed = ctx.alloc().buffer(blockLength);
295                 boolean success = false;
296                 try {
297                     int uncByte;
298                     while ((uncByte = blockDecompressor.read()) >= 0) {
299                         uncompressed.writeByte(uncByte);
300                     }
301 
302                     int currentBlockCRC = blockDecompressor.checkCRC();
303                     streamCRC = (streamCRC << 1 | streamCRC >>> 31) ^ currentBlockCRC;
304 
305                     out.add(uncompressed);
306                     success = true;
307                 } finally {
308                     if (!success) {
309                         uncompressed.release();
310                     }
311                 }
312                 currentState = State.INIT_BLOCK;
313                 break;
314             case EOF:
315                 in.skipBytes(in.readableBytes());
316                 return;
317             default:
318                 throw new IllegalStateException();
319             }
320         }
321     }
322 
323     /**
324      * Returns {@code true} if and only if the end of the compressed stream
325      * has been reached.
326      */
327     public boolean isClosed() {
328         return currentState == State.EOF;
329     }
330 }