1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 */ 18 package org.apache.commons.compress.compressors.deflate64; 19 20 import org.apache.commons.compress.utils.BitInputStream; 21 22 import java.io.Closeable; 23 import java.io.EOFException; 24 import java.io.IOException; 25 import java.io.InputStream; 26 import java.nio.ByteOrder; 27 import java.util.Arrays; 28 29 import static org.apache.commons.compress.compressors.deflate64.HuffmanState.*; 30 31 class HuffmanDecoder implements Closeable { 32 33 /** 34 * <pre> 35 * -------------------------------------------------------------------- 36 * idx xtra base idx xtra base idx xtra base 37 * -------------------------------------------------------------------- 38 * 257 0 3 267 1 15,16 277 4 67-82 39 * 258 0 4 268 1 17,18 278 4 83-98 40 * 259 0 5 269 2 19-22 279 4 99-114 41 * 260 0 6 270 2 23-26 280 4 115-130 42 * 261 0 7 271 2 27-30 281 5 131-162 43 * 262 0 8 272 2 31-34 282 5 163-194 44 * 263 0 9 273 3 35-42 283 5 195-226 45 * 264 0 10 274 3 43-50 284 5 227-257 46 * 265 1 11,12 275 3 51-58 285 16 3 47 * 266 1 13,14 276 3 59-66 48 * -------------------------------------------------------------------- 49 * </pre> 50 * value = (base of run length) << 5 | (number of extra bits to read) 51 */ 52 private static final short[] RUN_LENGTH_TABLE = { 53 96, 128, 160, 192, 224, 256, 288, 320, 353, 417, 481, 545, 610, 738, 866, 54 994, 1123, 1379, 1635, 1891, 2148, 2660, 3172, 3684, 4197, 5221, 6245, 7269, 112 55 }; 56 57 /** 58 * <pre> 59 * -------------------------------------------------------------------- 60 * idx xtra dist idx xtra dist idx xtra dist 61 * -------------------------------------------------------------------- 62 * 0 0 1 10 4 33-48 20 9 1025-1536 63 * 1 0 2 11 4 49-64 21 9 1537-2048 64 * 2 0 3 12 5 65-96 22 10 2049-3072 65 * 3 0 4 13 5 97-128 23 10 3073-4096 66 * 4 1 5,6 14 6 129-192 24 11 4097-6144 67 * 5 1 7,8 15 6 193-256 25 11 6145-8192 68 * 6 2 9-12 16 7 257-384 26 12 8193-12288 69 * 7 2 13-16 17 7 385-512 27 12 12289-16384 70 * 8 3 17-24 18 8 513-768 28 13 16385-24576 71 * 9 3 25-32 19 8 769-1024 29 13 24577-32768 72 * 30 14 32769-49152 73 * 31 14 49153-65536 74 * -------------------------------------------------------------------- 75 * </pre> 76 * value = (base of distance) << 4 | (number of extra bits to read) 77 */ 78 private static final int[] DISTANCE_TABLE = { 79 16, 32, 48, 64, 81, 113, 146, 210, 275, 403, // 0-9 80 532, 788, 1045, 1557, 2070, 3094, 4119, 6167, 8216, 12312, // 10-19 81 16409, 24601, 32794, 49178, 65563, 98331, 131100, 196636, 262173, 393245, // 20-29 82 524318, 786462 // 30-31 83 }; 84 85 /** 86 * When using dynamic huffman codes the order in which the values are stored 87 * follows the positioning below 88 */ 89 private static final int[] CODE_LENGTHS_ORDER = 90 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 91 92 /** 93 * Huffman Fixed Literal / Distance tables for mode 1 94 */ 95 private static final int[] FIXED_LITERALS; 96 private static final int[] FIXED_DISTANCE; 97 98 static { 99 FIXED_LITERALS = new int[288]; Arrays.fill(FIXED_LITERALS, 0, 144, 8)100 Arrays.fill(FIXED_LITERALS, 0, 144, 8); Arrays.fill(FIXED_LITERALS, 144, 256, 9)101 Arrays.fill(FIXED_LITERALS, 144, 256, 9); Arrays.fill(FIXED_LITERALS, 256, 280, 7)102 Arrays.fill(FIXED_LITERALS, 256, 280, 7); Arrays.fill(FIXED_LITERALS, 280, 288, 8)103 Arrays.fill(FIXED_LITERALS, 280, 288, 8); 104 105 FIXED_DISTANCE = new int[32]; Arrays.fill(FIXED_DISTANCE, 5)106 Arrays.fill(FIXED_DISTANCE, 5); 107 } 108 109 private boolean finalBlock = false; 110 private DecoderState state; 111 private BitInputStream reader; 112 private final InputStream in; 113 114 private final DecodingMemory memory = new DecodingMemory(); 115 HuffmanDecoder(InputStream in)116 HuffmanDecoder(InputStream in) { 117 this.reader = new BitInputStream(in, ByteOrder.LITTLE_ENDIAN); 118 this.in = in; 119 state = new InitialState(); 120 } 121 122 @Override close()123 public void close() { 124 state = new InitialState(); 125 reader = null; 126 } 127 decode(byte[] b)128 public int decode(byte[] b) throws IOException { 129 return decode(b, 0, b.length); 130 } 131 decode(byte[] b, int off, int len)132 public int decode(byte[] b, int off, int len) throws IOException { 133 while (!finalBlock || state.hasData()) { 134 if (state.state() == INITIAL) { 135 finalBlock = readBits(1) == 1; 136 int mode = (int) readBits(2); 137 switch (mode) { 138 case 0: 139 switchToUncompressedState(); 140 break; 141 case 1: 142 state = new HuffmanCodes(FIXED_CODES, FIXED_LITERALS, FIXED_DISTANCE); 143 break; 144 case 2: 145 int[][] tables = readDynamicTables(); 146 state = new HuffmanCodes(DYNAMIC_CODES, tables[0], tables[1]); 147 break; 148 default: 149 throw new IllegalStateException("Unsupported compression: " + mode); 150 } 151 } else { 152 return state.read(b, off, len); 153 } 154 } 155 return -1; 156 } 157 158 /** 159 * @since 1.17 160 */ getBytesRead()161 long getBytesRead() { 162 return reader.getBytesRead(); 163 } 164 switchToUncompressedState()165 private void switchToUncompressedState() throws IOException { 166 reader.alignWithByteBoundary(); 167 long bLen = readBits(16); 168 long bNLen = readBits(16); 169 if (((bLen ^ 0xFFFF) & 0xFFFF) != bNLen) { 170 //noinspection DuplicateStringLiteralInspection 171 throw new IllegalStateException("Illegal LEN / NLEN values"); 172 } 173 state = new UncompressedState(bLen); 174 } 175 readDynamicTables()176 private int[][] readDynamicTables() throws IOException { 177 int[][] result = new int[2][]; 178 int literals = (int) (readBits(5) + 257); 179 result[0] = new int[literals]; 180 181 int distances = (int) (readBits(5) + 1); 182 result[1] = new int[distances]; 183 184 populateDynamicTables(reader, result[0], result[1]); 185 return result; 186 } 187 available()188 int available() throws IOException { 189 return state.available(); 190 } 191 192 private abstract static class DecoderState { state()193 abstract HuffmanState state(); 194 read(byte[] b, int off, int len)195 abstract int read(byte[] b, int off, int len) throws IOException; 196 hasData()197 abstract boolean hasData(); 198 available()199 abstract int available() throws IOException ; 200 } 201 202 private class UncompressedState extends DecoderState { 203 private final long blockLength; 204 private long read; 205 UncompressedState(long blockLength)206 private UncompressedState(long blockLength) { 207 this.blockLength = blockLength; 208 } 209 210 @Override state()211 HuffmanState state() { 212 return read < blockLength ? STORED : INITIAL; 213 } 214 215 @Override read(byte[] b, int off, int len)216 int read(byte[] b, int off, int len) throws IOException { 217 // as len is an int and (blockLength - read) is >= 0 the min must fit into an int as well 218 int max = (int) Math.min(blockLength - read, len); 219 int readSoFar = 0; 220 while (readSoFar < max) { 221 int readNow; 222 if (reader.bitsCached() > 0) { 223 byte next = (byte) readBits(Byte.SIZE); 224 b[off + readSoFar] = memory.add(next); 225 readNow = 1; 226 } else { 227 readNow = in.read(b, off + readSoFar, max - readSoFar); 228 if (readNow == -1) { 229 throw new EOFException("Truncated Deflate64 Stream"); 230 } 231 memory.add(b, off + readSoFar, readNow); 232 } 233 read += readNow; 234 readSoFar += readNow; 235 } 236 return max; 237 } 238 239 @Override hasData()240 boolean hasData() { 241 return read < blockLength; 242 } 243 244 @Override available()245 int available() throws IOException { 246 return (int) Math.min(blockLength - read, reader.bitsAvailable() / Byte.SIZE); 247 } 248 } 249 250 private class InitialState extends DecoderState { 251 @Override state()252 HuffmanState state() { 253 return INITIAL; 254 } 255 256 @Override read(byte[] b, int off, int len)257 int read(byte[] b, int off, int len) throws IOException { 258 throw new IllegalStateException("Cannot read in this state"); 259 } 260 261 @Override hasData()262 boolean hasData() { 263 return false; 264 } 265 266 @Override available()267 int available() { 268 return 0; 269 } 270 } 271 272 private class HuffmanCodes extends DecoderState { 273 private boolean endOfBlock = false; 274 private final HuffmanState state; 275 private final BinaryTreeNode lengthTree; 276 private final BinaryTreeNode distanceTree; 277 278 private int runBufferPos = 0; 279 private byte[] runBuffer = new byte[0]; 280 private int runBufferLength = 0; 281 HuffmanCodes(HuffmanState state, int[] lengths, int[] distance)282 HuffmanCodes(HuffmanState state, int[] lengths, int[] distance) { 283 this.state = state; 284 lengthTree = buildTree(lengths); 285 distanceTree = buildTree(distance); 286 } 287 288 @Override state()289 HuffmanState state() { 290 return endOfBlock ? INITIAL : state; 291 } 292 293 @Override read(byte[] b, int off, int len)294 int read(byte[] b, int off, int len) throws IOException { 295 return decodeNext(b, off, len); 296 } 297 decodeNext(byte[] b, int off, int len)298 private int decodeNext(byte[] b, int off, int len) throws IOException { 299 if (endOfBlock) { 300 return -1; 301 } 302 int result = copyFromRunBuffer(b, off, len); 303 304 while (result < len) { 305 int symbol = nextSymbol(reader, lengthTree); 306 if (symbol < 256) { 307 b[off + result++] = memory.add((byte) symbol); 308 } else if (symbol > 256) { 309 int runMask = RUN_LENGTH_TABLE[symbol - 257]; 310 int run = runMask >>> 5; 311 int runXtra = runMask & 0x1F; 312 run += readBits(runXtra); 313 314 int distSym = nextSymbol(reader, distanceTree); 315 316 int distMask = DISTANCE_TABLE[distSym]; 317 int dist = distMask >>> 4; 318 int distXtra = distMask & 0xF; 319 dist += readBits(distXtra); 320 321 if (runBuffer.length < run) { 322 runBuffer = new byte[run]; 323 } 324 runBufferLength = run; 325 runBufferPos = 0; 326 memory.recordToBuffer(dist, run, runBuffer); 327 328 result += copyFromRunBuffer(b, off + result, len - result); 329 } else { 330 endOfBlock = true; 331 return result; 332 } 333 } 334 335 return result; 336 } 337 copyFromRunBuffer(byte[] b, int off, int len)338 private int copyFromRunBuffer(byte[] b, int off, int len) { 339 int bytesInBuffer = runBufferLength - runBufferPos; 340 int copiedBytes = 0; 341 if (bytesInBuffer > 0) { 342 copiedBytes = Math.min(len, bytesInBuffer); 343 System.arraycopy(runBuffer, runBufferPos, b, off, copiedBytes); 344 runBufferPos += copiedBytes; 345 } 346 return copiedBytes; 347 } 348 349 @Override hasData()350 boolean hasData() { 351 return !endOfBlock; 352 } 353 354 @Override available()355 int available() { 356 return runBufferLength - runBufferPos; 357 } 358 } 359 nextSymbol(BitInputStream reader, BinaryTreeNode tree)360 private static int nextSymbol(BitInputStream reader, BinaryTreeNode tree) throws IOException { 361 BinaryTreeNode node = tree; 362 while (node != null && node.literal == -1) { 363 long bit = readBits(reader, 1); 364 node = bit == 0 ? node.leftNode : node.rightNode; 365 } 366 return node != null ? node.literal : -1; 367 } 368 populateDynamicTables(BitInputStream reader, int[] literals, int[] distances)369 private static void populateDynamicTables(BitInputStream reader, int[] literals, int[] distances) throws IOException { 370 int codeLengths = (int) (readBits(reader, 4) + 4); 371 372 int[] codeLengthValues = new int[19]; 373 for (int cLen = 0; cLen < codeLengths; cLen++) { 374 codeLengthValues[CODE_LENGTHS_ORDER[cLen]] = (int) readBits(reader, 3); 375 } 376 377 BinaryTreeNode codeLengthTree = buildTree(codeLengthValues); 378 379 final int[] auxBuffer = new int[literals.length + distances.length]; 380 381 int value = -1; 382 int length = 0; 383 int off = 0; 384 while (off < auxBuffer.length) { 385 if (length > 0) { 386 auxBuffer[off++] = value; 387 length--; 388 } else { 389 int symbol = nextSymbol(reader, codeLengthTree); 390 if (symbol < 16) { 391 value = symbol; 392 auxBuffer[off++] = value; 393 } else if (symbol == 16) { 394 length = (int) (readBits(reader, 2) + 3); 395 } else if (symbol == 17) { 396 value = 0; 397 length = (int) (readBits(reader, 3) + 3); 398 } else if (symbol == 18) { 399 value = 0; 400 length = (int) (readBits(reader, 7) + 11); 401 } 402 } 403 } 404 405 System.arraycopy(auxBuffer, 0, literals, 0, literals.length); 406 System.arraycopy(auxBuffer, literals.length, distances, 0, distances.length); 407 } 408 409 private static class BinaryTreeNode { 410 private final int bits; 411 int literal = -1; 412 BinaryTreeNode leftNode; 413 BinaryTreeNode rightNode; 414 BinaryTreeNode(int bits)415 private BinaryTreeNode(int bits) { 416 this.bits = bits; 417 } 418 leaf(int symbol)419 void leaf(int symbol) { 420 literal = symbol; 421 leftNode = null; 422 rightNode = null; 423 } 424 left()425 BinaryTreeNode left() { 426 if (leftNode == null && literal == -1) { 427 leftNode = new BinaryTreeNode(bits + 1); 428 } 429 return leftNode; 430 } 431 right()432 BinaryTreeNode right() { 433 if (rightNode == null && literal == -1) { 434 rightNode = new BinaryTreeNode(bits + 1); 435 } 436 return rightNode; 437 } 438 } 439 buildTree(int[] litTable)440 private static BinaryTreeNode buildTree(int[] litTable) { 441 int[] literalCodes = getCodes(litTable); 442 443 BinaryTreeNode root = new BinaryTreeNode(0); 444 445 for (int i = 0; i < litTable.length; i++) { 446 int len = litTable[i]; 447 if (len != 0) { 448 BinaryTreeNode node = root; 449 int lit = literalCodes[len - 1]; 450 for (int p = len - 1; p >= 0; p--) { 451 int bit = lit & (1 << p); 452 node = bit == 0 ? node.left() : node.right(); 453 } 454 node.leaf(i); 455 literalCodes[len - 1]++; 456 } 457 } 458 return root; 459 } 460 getCodes(int[] litTable)461 private static int[] getCodes(int[] litTable) { 462 int max = 0; 463 int[] blCount = new int[65]; 464 465 for (int aLitTable : litTable) { 466 max = Math.max(max, aLitTable); 467 blCount[aLitTable]++; 468 } 469 blCount = Arrays.copyOf(blCount, max + 1); 470 471 int code = 0; 472 int[] nextCode = new int[max + 1]; 473 for (int i = 0; i <= max; i++) { 474 code = (code + blCount[i]) << 1; 475 nextCode[i] = code; 476 } 477 478 return nextCode; 479 } 480 481 private static class DecodingMemory { 482 private final byte[] memory; 483 private final int mask; 484 private int wHead; 485 private boolean wrappedAround; 486 DecodingMemory()487 private DecodingMemory() { 488 this(16); 489 } 490 DecodingMemory(int bits)491 private DecodingMemory(int bits) { 492 memory = new byte[1 << bits]; 493 mask = memory.length - 1; 494 } 495 add(byte b)496 byte add(byte b) { 497 memory[wHead] = b; 498 wHead = incCounter(wHead); 499 return b; 500 } 501 add(byte[] b, int off, int len)502 void add(byte[] b, int off, int len) { 503 for (int i = off; i < off + len; i++) { 504 add(b[i]); 505 } 506 } 507 recordToBuffer(int distance, int length, byte[] buff)508 void recordToBuffer(int distance, int length, byte[] buff) { 509 if (distance > memory.length) { 510 throw new IllegalStateException("Illegal distance parameter: " + distance); 511 } 512 int start = (wHead - distance) & mask; 513 if (!wrappedAround && start >= wHead) { 514 throw new IllegalStateException("Attempt to read beyond memory: dist=" + distance); 515 } 516 for (int i = 0, pos = start; i < length; i++, pos = incCounter(pos)) { 517 buff[i] = add(memory[pos]); 518 } 519 } 520 incCounter(int counter)521 private int incCounter(int counter) { 522 final int newCounter = (counter + 1) & mask; 523 if (!wrappedAround && newCounter < counter) { 524 wrappedAround = true; 525 } 526 return newCounter; 527 } 528 } 529 readBits(int numBits)530 private long readBits(int numBits) throws IOException { 531 return readBits(reader, numBits); 532 } 533 readBits(BitInputStream reader, int numBits)534 private static long readBits(BitInputStream reader, int numBits) throws IOException { 535 long r = reader.readBits(numBits); 536 if (r == -1) { 537 throw new EOFException("Truncated Deflate64 Stream"); 538 } 539 return r; 540 } 541 } 542