1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one 3 * or more contributor license agreements. See the NOTICE file 4 * distributed with this work for additional information 5 * regarding copyright ownership. The ASF licenses this file 6 * to you under the Apache License, Version 2.0 (the 7 * "License"); you may not use this file except in compliance 8 * with the License. You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, 13 * software distributed under the License is distributed on an 14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 15 * KIND, either express or implied. See the License for the 16 * specific language governing permissions and limitations 17 * under the License. 18 */ 19 package org.apache.commons.compress.archivers.zip; 20 21 import java.io.IOException; 22 import java.io.InputStream; 23 import java.nio.ByteOrder; 24 25 import org.apache.commons.compress.compressors.lzw.LZWInputStream; 26 27 /** 28 * Input stream that decompresses ZIP method 1 (unshrinking). A variation of the LZW algorithm, with some twists. 29 * @NotThreadSafe 30 * @since 1.7 31 */ 32 class UnshrinkingInputStream extends LZWInputStream { 33 private static final int MAX_CODE_SIZE = 13; 34 private static final int MAX_TABLE_SIZE = 1 << MAX_CODE_SIZE; 35 private final boolean[] isUsed; 36 37 /** 38 * IOException is not actually thrown! 39 * 40 * @param inputStream 41 * @throws IOException IOException is not actually thrown! 42 */ UnshrinkingInputStream(final InputStream inputStream)43 public UnshrinkingInputStream(final InputStream inputStream) throws IOException { 44 super(inputStream, ByteOrder.LITTLE_ENDIAN); 45 setClearCode(DEFAULT_CODE_SIZE); 46 initializeTables(MAX_CODE_SIZE); 47 isUsed = new boolean[getPrefixesLength()]; 48 for (int i = 0; i < (1 << 8); i++) { 49 isUsed[i] = true; 50 } 51 setTableSize(getClearCode() + 1); 52 } 53 54 @Override addEntry(final int previousCode, final byte character)55 protected int addEntry(final int previousCode, final byte character) throws IOException { 56 int tableSize = getTableSize(); 57 while ((tableSize < MAX_TABLE_SIZE) && isUsed[tableSize]) { 58 tableSize++; 59 } 60 setTableSize(tableSize); 61 final int idx = addEntry(previousCode, character, MAX_TABLE_SIZE); 62 if (idx >= 0) { 63 isUsed[idx] = true; 64 } 65 return idx; 66 } 67 partialClear()68 private void partialClear() { 69 final boolean[] isParent = new boolean[MAX_TABLE_SIZE]; 70 for (int i = 0; i < isUsed.length; i++) { 71 if (isUsed[i] && getPrefix(i) != UNUSED_PREFIX) { 72 isParent[getPrefix(i)] = true; 73 } 74 } 75 for (int i = getClearCode() + 1; i < isParent.length; i++) { 76 if (!isParent[i]) { 77 isUsed[i] = false; 78 setPrefix(i, UNUSED_PREFIX); 79 } 80 } 81 } 82 83 @Override decompressNextSymbol()84 protected int decompressNextSymbol() throws IOException { 85 // 86 // table entry table entry 87 // _____________ _____ 88 // table entry / \ / \ 89 // ____________/ \ \ 90 // / / \ / \ \ 91 // +---+---+---+---+---+---+---+---+---+---+ 92 // | . | . | . | . | . | . | . | . | . | . | 93 // +---+---+---+---+---+---+---+---+---+---+ 94 // |<--------->|<------------->|<----->|<->| 95 // symbol symbol symbol symbol 96 // 97 final int code = readNextCode(); 98 if (code < 0) { 99 return -1; 100 } else if (code == getClearCode()) { 101 final int subCode = readNextCode(); 102 if (subCode < 0) { 103 throw new IOException("Unexpected EOF;"); 104 } else if (subCode == 1) { 105 if (getCodeSize() < MAX_CODE_SIZE) { 106 incrementCodeSize(); 107 } else { 108 throw new IOException("Attempt to increase code size beyond maximum"); 109 } 110 } else if (subCode == 2) { 111 partialClear(); 112 setTableSize(getClearCode() + 1); 113 } else { 114 throw new IOException("Invalid clear code subcode " + subCode); 115 } 116 return 0; 117 } else { 118 boolean addedUnfinishedEntry = false; 119 int effectiveCode = code; 120 if (!isUsed[code]) { 121 effectiveCode = addRepeatOfPreviousCode(); 122 addedUnfinishedEntry = true; 123 } 124 return expandCodeToOutputStack(effectiveCode, addedUnfinishedEntry); 125 } 126 } 127 } 128