001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 */ 019package org.apache.commons.compress.compressors.lz4; 020 021import java.io.IOException; 022import java.io.OutputStream; 023import java.util.Arrays; 024import java.util.Deque; 025import java.util.Iterator; 026import java.util.LinkedList; 027 028import org.apache.commons.compress.compressors.CompressorOutputStream; 029import org.apache.commons.compress.compressors.lz77support.LZ77Compressor; 030import org.apache.commons.compress.compressors.lz77support.Parameters; 031import org.apache.commons.compress.utils.ByteUtils; 032 033/** 034 * CompressorOutputStream for the LZ4 block format. 035 * 036 * @see <a href="http://lz4.github.io/lz4/lz4_Block_format.html">LZ4 Block Format Description</a> 037 * @since 1.14 038 * @NotThreadSafe 039 */ 040public class BlockLZ4CompressorOutputStream extends CompressorOutputStream { 041 042 private static final int MIN_BACK_REFERENCE_LENGTH = 4; 043 private static final int MIN_OFFSET_OF_LAST_BACK_REFERENCE = 12; 044 045 /* 046 047 The LZ4 block format has a few properties that make it less 048 straight-forward than one would hope: 049 050 * literal blocks and back-references must come in pairs (except 051 for the very last literal block), so consecutive literal 052 blocks created by the compressor must be merged into a single 053 block. 054 055 * the start of a literal/back-reference pair contains the length 056 of the back-reference (at least some part of it) so we can't 057 start writing the literal before we know how long the next 058 back-reference is going to be. 059 060 * there are special rules for the final blocks 061 062 > There are specific parsing rules to respect in order to remain 063 > compatible with assumptions made by the decoder : 064 > 065 > 1. The last 5 bytes are always literals 066 > 067 > 2. The last match must start at least 12 bytes before end of 068 > block. Consequently, a block with less than 13 bytes cannot be 069 > compressed. 070 071 which means any back-reference may need to get rewritten as a 072 literal block unless we know the next block is at least of 073 length 5 and the sum of this block's length and offset and the 074 next block's length is at least twelve. 075 076 */ 077 078 private final LZ77Compressor compressor; 079 private final OutputStream os; 080 081 // used in one-arg write method 082 private final byte[] oneByte = new byte[1]; 083 084 private boolean finished = false; 085 086 private Deque<Pair> pairs = new LinkedList<>(); 087 // keeps track of the last window-size bytes (64k) in order to be 088 // able to expand back-references when needed 089 private Deque<byte[]> expandedBlocks = new LinkedList<>(); 090 091 /** 092 * Creates a new LZ4 output stream. 093 * 094 * @param os 095 * An OutputStream to read compressed data from 096 * 097 * @throws IOException if reading fails 098 */ 099 public BlockLZ4CompressorOutputStream(final OutputStream os) throws IOException { 100 this(os, createParameterBuilder().build()); 101 } 102 103 /** 104 * Creates a new LZ4 output stream. 105 * 106 * @param os 107 * An OutputStream to read compressed data from 108 * @param params 109 * The parameters to use for LZ77 compression. 110 * 111 * @throws IOException if reading fails 112 */ 113 public BlockLZ4CompressorOutputStream(final OutputStream os, Parameters params) throws IOException { 114 this.os = os; 115 compressor = new LZ77Compressor(params, 116 new LZ77Compressor.Callback() { 117 @Override 118 public void accept(LZ77Compressor.Block block) throws IOException { 119 //System.err.println(block); 120 if (block instanceof LZ77Compressor.LiteralBlock) { 121 addLiteralBlock((LZ77Compressor.LiteralBlock) block); 122 } else if (block instanceof LZ77Compressor.BackReference) { 123 addBackReference((LZ77Compressor.BackReference) block); 124 } else if (block instanceof LZ77Compressor.EOD) { 125 writeFinalLiteralBlock(); 126 } 127 } 128 }); 129 } 130 131 @Override 132 public void write(int b) throws IOException { 133 oneByte[0] = (byte) (b & 0xff); 134 write(oneByte); 135 } 136 137 @Override 138 public void write(byte[] data, int off, int len) throws IOException { 139 compressor.compress(data, off, len); 140 } 141 142 @Override 143 public void close() throws IOException { 144 finish(); 145 os.close(); 146 } 147 148 /** 149 * Compresses all remaining data and writes it to the stream, 150 * doesn't close the underlying stream. 151 * @throws IOException if an error occurs 152 */ 153 public void finish() throws IOException { 154 if (!finished) { 155 compressor.finish(); 156 finished = true; 157 } 158 } 159 160 /** 161 * Adds some initial data to fill the window with. 162 * 163 * @param data the data to fill the window with. 164 * @param off offset of real data into the array 165 * @param len amount of data 166 * @throws IllegalStateException if the stream has already started to write data 167 * @see LZ77Compressor#prefill 168 */ 169 public void prefill(byte[] data, int off, int len) { 170 if (len > 0) { 171 byte[] b = Arrays.copyOfRange(data, off, off + len); 172 compressor.prefill(b); 173 recordLiteral(b); 174 } 175 } 176 177 private void addLiteralBlock(LZ77Compressor.LiteralBlock block) throws IOException { 178 Pair last = writeBlocksAndReturnUnfinishedPair(block.getLength()); 179 recordLiteral(last.addLiteral(block)); 180 clearUnusedBlocksAndPairs(); 181 } 182 183 private void addBackReference(LZ77Compressor.BackReference block) throws IOException { 184 Pair last = writeBlocksAndReturnUnfinishedPair(block.getLength()); 185 last.setBackReference(block); 186 recordBackReference(block); 187 clearUnusedBlocksAndPairs(); 188 } 189 190 private Pair writeBlocksAndReturnUnfinishedPair(int length) throws IOException { 191 writeWritablePairs(length); 192 Pair last = pairs.peekLast(); 193 if (last == null || last.hasBackReference()) { 194 last = new Pair(); 195 pairs.addLast(last); 196 } 197 return last; 198 } 199 200 private void recordLiteral(byte[] b) { 201 expandedBlocks.addFirst(b); 202 } 203 204 private void clearUnusedBlocksAndPairs() { 205 clearUnusedBlocks(); 206 clearUnusedPairs(); 207 } 208 209 private void clearUnusedBlocks() { 210 int blockLengths = 0; 211 int blocksToKeep = 0; 212 for (byte[] b : expandedBlocks) { 213 blocksToKeep++; 214 blockLengths += b.length; 215 if (blockLengths >= BlockLZ4CompressorInputStream.WINDOW_SIZE) { 216 break; 217 } 218 } 219 final int size = expandedBlocks.size(); 220 for (int i = blocksToKeep; i < size; i++) { 221 expandedBlocks.removeLast(); 222 } 223 } 224 225 private void recordBackReference(LZ77Compressor.BackReference block) { 226 expandedBlocks.addFirst(expand(block.getOffset(), block.getLength())); 227 } 228 229 private byte[] expand(final int offset, final int length) { 230 byte[] expanded = new byte[length]; 231 if (offset == 1) { // surprisingly common special case 232 byte[] block = expandedBlocks.peekFirst(); 233 byte b = block[block.length - 1]; 234 if (b != 0) { // the fresh array contains 0s anyway 235 Arrays.fill(expanded, b); 236 } 237 } else { 238 expandFromList(expanded, offset, length); 239 } 240 return expanded; 241 } 242 243 private void expandFromList(final byte[] expanded, int offset, int length) { 244 int offsetRemaining = offset; 245 int lengthRemaining = length; 246 int writeOffset = 0; 247 while (lengthRemaining > 0) { 248 // find block that contains offsetRemaining 249 byte[] block = null; 250 int copyLen, copyOffset; 251 if (offsetRemaining > 0) { 252 int blockOffset = 0; 253 for (byte[] b : expandedBlocks) { 254 if (b.length + blockOffset >= offsetRemaining) { 255 block = b; 256 break; 257 } 258 blockOffset += b.length; 259 } 260 if (block == null) { 261 // should not be possible 262 throw new IllegalStateException("failed to find a block containing offset " + offset); 263 } 264 copyOffset = blockOffset + block.length - offsetRemaining; 265 copyLen = Math.min(lengthRemaining, block.length - copyOffset); 266 } else { 267 // offsetRemaining is negative or 0 and points into the expanded bytes 268 block = expanded; 269 copyOffset = -offsetRemaining; 270 copyLen = Math.min(lengthRemaining, writeOffset + offsetRemaining); 271 } 272 System.arraycopy(block, copyOffset, expanded, writeOffset, copyLen); 273 offsetRemaining -= copyLen; 274 lengthRemaining -= copyLen; 275 writeOffset += copyLen; 276 } 277 } 278 279 private void clearUnusedPairs() { 280 int pairLengths = 0; 281 int pairsToKeep = 0; 282 for (Iterator<Pair> it = pairs.descendingIterator(); it.hasNext(); ) { 283 Pair p = it.next(); 284 pairsToKeep++; 285 pairLengths += p.length(); 286 if (pairLengths >= BlockLZ4CompressorInputStream.WINDOW_SIZE) { 287 break; 288 } 289 } 290 final int size = pairs.size(); 291 for (int i = pairsToKeep; i < size; i++) { 292 Pair p = pairs.peekFirst(); 293 if (p.hasBeenWritten()) { 294 pairs.removeFirst(); 295 } else { 296 break; 297 } 298 } 299 } 300 301 private void writeFinalLiteralBlock() throws IOException { 302 rewriteLastPairs(); 303 for (Pair p : pairs) { 304 if (!p.hasBeenWritten()) { 305 p.writeTo(os); 306 } 307 } 308 pairs.clear(); 309 } 310 311 private void writeWritablePairs(int lengthOfBlocksAfterLastPair) throws IOException { 312 int unwrittenLength = lengthOfBlocksAfterLastPair; 313 for (Iterator<Pair> it = pairs.descendingIterator(); it.hasNext(); ) { 314 Pair p = it.next(); 315 if (p.hasBeenWritten()) { 316 break; 317 } 318 unwrittenLength += p.length(); 319 } 320 for (Pair p : pairs) { 321 if (p.hasBeenWritten()) { 322 continue; 323 } 324 unwrittenLength -= p.length(); 325 if (p.canBeWritten(unwrittenLength)) { 326 p.writeTo(os); 327 } else { 328 break; 329 } 330 } 331 } 332 333 private void rewriteLastPairs() { 334 LinkedList<Pair> lastPairs = new LinkedList<>(); 335 LinkedList<Integer> pairLength = new LinkedList<>(); 336 int offset = 0; 337 for (Iterator<Pair> it = pairs.descendingIterator(); it.hasNext(); ) { 338 Pair p = it.next(); 339 if (p.hasBeenWritten()) { 340 break; 341 } 342 int len = p.length(); 343 pairLength.addFirst(len); 344 lastPairs.addFirst(p); 345 offset += len; 346 if (offset >= MIN_OFFSET_OF_LAST_BACK_REFERENCE) { 347 break; 348 } 349 } 350 for (Pair p : lastPairs) { 351 pairs.remove(p); 352 } 353 // lastPairs may contain between one and four Pairs: 354 // * the last pair may be a one byte literal 355 // * all other Pairs contain a back-reference which must be four bytes long at minimum 356 // we could merge them all into a single literal block but 357 // this may harm compression. For example compressing 358 // "bla.tar" from our tests yields a last block containing a 359 // back-reference of length > 2k and we'd end up with a last 360 // literal of that size rather than a 2k back-reference and a 361 // 12 byte literal at the end. 362 363 // Instead we merge all but the first of lastPairs into a new 364 // literal-only Pair "replacement" and look at the 365 // back-reference in the first of lastPairs and see if we can 366 // split it. We can split it if it is longer than 16 - 367 // replacement.length (i.e. the minimal length of four is kept 368 // while making sure the last literal is at least twelve bytes 369 // long). If we can't split it, we expand the first of the pairs 370 // as well. 371 372 // this is not optimal, we could get better compression 373 // results with more complex approaches as the last literal 374 // only needs to be five bytes long if the previous 375 // back-reference has an offset big enough 376 377 final int lastPairsSize = lastPairs.size(); 378 int toExpand = 0; 379 for (int i = 1; i < lastPairsSize; i++) { 380 toExpand += pairLength.get(i); 381 } 382 Pair replacement = new Pair(); 383 if (toExpand > 0) { 384 replacement.prependLiteral(expand(toExpand, toExpand)); 385 } 386 Pair splitCandidate = lastPairs.get(0); 387 int stillNeeded = MIN_OFFSET_OF_LAST_BACK_REFERENCE - toExpand; 388 int brLen = splitCandidate.hasBackReference() ? splitCandidate.backReferenceLength() : 0; 389 if (splitCandidate.hasBackReference() && brLen >= MIN_BACK_REFERENCE_LENGTH + stillNeeded) { 390 replacement.prependLiteral(expand(toExpand + stillNeeded, stillNeeded)); 391 pairs.add(splitCandidate.splitWithNewBackReferenceLengthOf(brLen - stillNeeded)); 392 } else { 393 if (splitCandidate.hasBackReference()) { 394 replacement.prependLiteral(expand(toExpand + brLen, brLen)); 395 } 396 splitCandidate.prependTo(replacement); 397 } 398 pairs.add(replacement); 399 } 400 401 /** 402 * Returns a builder correctly configured for the LZ4 algorithm. 403 * @return a builder correctly configured for the LZ4 algorithm 404 */ 405 public static Parameters.Builder createParameterBuilder() { 406 int maxLen = BlockLZ4CompressorInputStream.WINDOW_SIZE - 1; 407 return Parameters.builder(BlockLZ4CompressorInputStream.WINDOW_SIZE) 408 .withMinBackReferenceLength(MIN_BACK_REFERENCE_LENGTH) 409 .withMaxBackReferenceLength(maxLen) 410 .withMaxOffset(maxLen) 411 .withMaxLiteralLength(maxLen); 412 } 413 414 final static class Pair { 415 private final Deque<byte[]> literals = new LinkedList<>(); 416 private int brOffset, brLength; 417 private boolean written; 418 419 private void prependLiteral(byte[] data) { 420 literals.addFirst(data); 421 } 422 byte[] addLiteral(LZ77Compressor.LiteralBlock block) { 423 byte[] copy = Arrays.copyOfRange(block.getData(), block.getOffset(), 424 block.getOffset() + block.getLength()); 425 literals.add(copy); 426 return copy; 427 } 428 void setBackReference(LZ77Compressor.BackReference block) { 429 if (hasBackReference()) { 430 throw new IllegalStateException(); 431 } 432 brOffset = block.getOffset(); 433 brLength = block.getLength(); 434 } 435 boolean hasBackReference() { 436 return brOffset > 0; 437 } 438 boolean canBeWritten(int lengthOfBlocksAfterThisPair) { 439 return hasBackReference() 440 && lengthOfBlocksAfterThisPair >= MIN_OFFSET_OF_LAST_BACK_REFERENCE + MIN_BACK_REFERENCE_LENGTH; 441 } 442 int length() { 443 return literalLength() + brLength; 444 } 445 private boolean hasBeenWritten() { 446 return written; 447 } 448 void writeTo(OutputStream out) throws IOException { 449 int litLength = literalLength(); 450 out.write(lengths(litLength, brLength)); 451 if (litLength >= BlockLZ4CompressorInputStream.BACK_REFERENCE_SIZE_MASK) { 452 writeLength(litLength - BlockLZ4CompressorInputStream.BACK_REFERENCE_SIZE_MASK, out); 453 } 454 for (byte[] b : literals) { 455 out.write(b); 456 } 457 if (hasBackReference()) { 458 ByteUtils.toLittleEndian(out, brOffset, 2); 459 if (brLength - MIN_BACK_REFERENCE_LENGTH >= BlockLZ4CompressorInputStream.BACK_REFERENCE_SIZE_MASK) { 460 writeLength(brLength - MIN_BACK_REFERENCE_LENGTH 461 - BlockLZ4CompressorInputStream.BACK_REFERENCE_SIZE_MASK, out); 462 } 463 } 464 written = true; 465 } 466 private int literalLength() { 467 int length = 0; 468 for (byte[] b : literals) { 469 length += b.length; 470 } 471 return length; 472 } 473 private static int lengths(int litLength, int brLength) { 474 int l = litLength < 15 ? litLength : 15; 475 int br = brLength < 4 ? 0 : (brLength < 19 ? brLength - 4 : 15); 476 return (l << BlockLZ4CompressorInputStream.SIZE_BITS) | br; 477 } 478 private static void writeLength(int length, OutputStream out) throws IOException { 479 while (length >= 255) { 480 out.write(255); 481 length -= 255; 482 } 483 out.write(length); 484 } 485 private int backReferenceLength() { 486 return brLength; 487 } 488 private void prependTo(Pair other) { 489 Iterator<byte[]> listBackwards = literals.descendingIterator(); 490 while (listBackwards.hasNext()) { 491 other.prependLiteral(listBackwards.next()); 492 } 493 } 494 private Pair splitWithNewBackReferenceLengthOf(int newBackReferenceLength) { 495 Pair p = new Pair(); 496 p.literals.addAll(literals); 497 p.brOffset = brOffset; 498 p.brLength = newBackReferenceLength; 499 return p; 500 } 501 } 502}