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; 085 086 private final 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 final 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, final Parameters params) throws IOException { 114 this.os = os; 115 compressor = new LZ77Compressor(params, 116 block -> { 117 switch (block.getType()) { 118 case LITERAL: 119 addLiteralBlock((LZ77Compressor.LiteralBlock) block); 120 break; 121 case BACK_REFERENCE: 122 addBackReference((LZ77Compressor.BackReference) block); 123 break; 124 case EOD: 125 writeFinalLiteralBlock(); 126 break; 127 } 128 }); 129 } 130 131 @Override 132 public void write(final int b) throws IOException { 133 oneByte[0] = (byte) (b & 0xff); 134 write(oneByte); 135 } 136 137 @Override 138 public void write(final byte[] data, final int off, final int len) throws IOException { 139 compressor.compress(data, off, len); 140 } 141 142 @Override 143 public void close() throws IOException { 144 try { 145 finish(); 146 } finally { 147 os.close(); 148 } 149 } 150 151 /** 152 * Compresses all remaining data and writes it to the stream, 153 * doesn't close the underlying stream. 154 * @throws IOException if an error occurs 155 */ 156 public void finish() throws IOException { 157 if (!finished) { 158 compressor.finish(); 159 finished = true; 160 } 161 } 162 163 /** 164 * Adds some initial data to fill the window with. 165 * 166 * @param data the data to fill the window with. 167 * @param off offset of real data into the array 168 * @param len amount of data 169 * @throws IllegalStateException if the stream has already started to write data 170 * @see LZ77Compressor#prefill 171 */ 172 public void prefill(final byte[] data, final int off, final int len) { 173 if (len > 0) { 174 final byte[] b = Arrays.copyOfRange(data, off, off + len); 175 compressor.prefill(b); 176 recordLiteral(b); 177 } 178 } 179 180 private void addLiteralBlock(final LZ77Compressor.LiteralBlock block) throws IOException { 181 final Pair last = writeBlocksAndReturnUnfinishedPair(block.getLength()); 182 recordLiteral(last.addLiteral(block)); 183 clearUnusedBlocksAndPairs(); 184 } 185 186 private void addBackReference(final LZ77Compressor.BackReference block) throws IOException { 187 final Pair last = writeBlocksAndReturnUnfinishedPair(block.getLength()); 188 last.setBackReference(block); 189 recordBackReference(block); 190 clearUnusedBlocksAndPairs(); 191 } 192 193 private Pair writeBlocksAndReturnUnfinishedPair(final int length) throws IOException { 194 writeWritablePairs(length); 195 Pair last = pairs.peekLast(); 196 if (last == null || last.hasBackReference()) { 197 last = new Pair(); 198 pairs.addLast(last); 199 } 200 return last; 201 } 202 203 private void recordLiteral(final byte[] b) { 204 expandedBlocks.addFirst(b); 205 } 206 207 private void clearUnusedBlocksAndPairs() { 208 clearUnusedBlocks(); 209 clearUnusedPairs(); 210 } 211 212 private void clearUnusedBlocks() { 213 int blockLengths = 0; 214 int blocksToKeep = 0; 215 for (final byte[] b : expandedBlocks) { 216 blocksToKeep++; 217 blockLengths += b.length; 218 if (blockLengths >= BlockLZ4CompressorInputStream.WINDOW_SIZE) { 219 break; 220 } 221 } 222 final int size = expandedBlocks.size(); 223 for (int i = blocksToKeep; i < size; i++) { 224 expandedBlocks.removeLast(); 225 } 226 } 227 228 private void recordBackReference(final LZ77Compressor.BackReference block) { 229 expandedBlocks.addFirst(expand(block.getOffset(), block.getLength())); 230 } 231 232 private byte[] expand(final int offset, final int length) { 233 final byte[] expanded = new byte[length]; 234 if (offset == 1) { // surprisingly common special case 235 final byte[] block = expandedBlocks.peekFirst(); 236 final byte b = block[block.length - 1]; 237 if (b != 0) { // the fresh array contains 0s anyway 238 Arrays.fill(expanded, b); 239 } 240 } else { 241 expandFromList(expanded, offset, length); 242 } 243 return expanded; 244 } 245 246 private void expandFromList(final byte[] expanded, final int offset, final int length) { 247 int offsetRemaining = offset; 248 int lengthRemaining = length; 249 int writeOffset = 0; 250 while (lengthRemaining > 0) { 251 // find block that contains offsetRemaining 252 byte[] block = null; 253 final int copyLen; 254 final int copyOffset; 255 if (offsetRemaining > 0) { 256 int blockOffset = 0; 257 for (final byte[] b : expandedBlocks) { 258 if (b.length + blockOffset >= offsetRemaining) { 259 block = b; 260 break; 261 } 262 blockOffset += b.length; 263 } 264 if (block == null) { 265 // should not be possible 266 throw new IllegalStateException("Failed to find a block containing offset " + offset); 267 } 268 copyOffset = blockOffset + block.length - offsetRemaining; 269 copyLen = Math.min(lengthRemaining, block.length - copyOffset); 270 } else { 271 // offsetRemaining is negative or 0 and points into the expanded bytes 272 block = expanded; 273 copyOffset = -offsetRemaining; 274 copyLen = Math.min(lengthRemaining, writeOffset + offsetRemaining); 275 } 276 System.arraycopy(block, copyOffset, expanded, writeOffset, copyLen); 277 offsetRemaining -= copyLen; 278 lengthRemaining -= copyLen; 279 writeOffset += copyLen; 280 } 281 } 282 283 private void clearUnusedPairs() { 284 int pairLengths = 0; 285 int pairsToKeep = 0; 286 for (final Iterator<Pair> it = pairs.descendingIterator(); it.hasNext(); ) { 287 final Pair p = it.next(); 288 pairsToKeep++; 289 pairLengths += p.length(); 290 if (pairLengths >= BlockLZ4CompressorInputStream.WINDOW_SIZE) { 291 break; 292 } 293 } 294 final int size = pairs.size(); 295 for (int i = pairsToKeep; i < size; i++) { 296 final Pair p = pairs.peekFirst(); 297 if (!p.hasBeenWritten()) { 298 break; 299 } 300 pairs.removeFirst(); 301 } 302 } 303 304 private void writeFinalLiteralBlock() throws IOException { 305 rewriteLastPairs(); 306 for (final Pair p : pairs) { 307 if (!p.hasBeenWritten()) { 308 p.writeTo(os); 309 } 310 } 311 pairs.clear(); 312 } 313 314 private void writeWritablePairs(final int lengthOfBlocksAfterLastPair) throws IOException { 315 int unwrittenLength = lengthOfBlocksAfterLastPair; 316 for (final Iterator<Pair> it = pairs.descendingIterator(); it.hasNext(); ) { 317 final Pair p = it.next(); 318 if (p.hasBeenWritten()) { 319 break; 320 } 321 unwrittenLength += p.length(); 322 } 323 for (final Pair p : pairs) { 324 if (p.hasBeenWritten()) { 325 continue; 326 } 327 unwrittenLength -= p.length(); 328 if (!p.canBeWritten(unwrittenLength)) { 329 break; 330 } 331 p.writeTo(os); 332 } 333 } 334 335 private void rewriteLastPairs() { 336 final LinkedList<Pair> lastPairs = new LinkedList<>(); 337 final LinkedList<Integer> pairLength = new LinkedList<>(); 338 int offset = 0; 339 for (final Iterator<Pair> it = pairs.descendingIterator(); it.hasNext(); ) { 340 final Pair p = it.next(); 341 if (p.hasBeenWritten()) { 342 break; 343 } 344 final int len = p.length(); 345 pairLength.addFirst(len); 346 lastPairs.addFirst(p); 347 offset += len; 348 if (offset >= MIN_OFFSET_OF_LAST_BACK_REFERENCE) { 349 break; 350 } 351 } 352 for (final Pair p : lastPairs) { 353 pairs.remove(p); 354 } 355 // lastPairs may contain between one and four Pairs: 356 // * the last pair may be a one byte literal 357 // * all other Pairs contain a back-reference which must be four bytes long at minimum 358 // we could merge them all into a single literal block but 359 // this may harm compression. For example compressing 360 // "bla.tar" from our tests yields a last block containing a 361 // back-reference of length > 2k and we'd end up with a last 362 // literal of that size rather than a 2k back-reference and a 363 // 12 byte literal at the end. 364 365 // Instead we merge all but the first of lastPairs into a new 366 // literal-only Pair "replacement" and look at the 367 // back-reference in the first of lastPairs and see if we can 368 // split it. We can split it if it is longer than 16 - 369 // replacement.length (i.e. the minimal length of four is kept 370 // while making sure the last literal is at least twelve bytes 371 // long). If we can't split it, we expand the first of the pairs 372 // as well. 373 374 // this is not optimal, we could get better compression 375 // results with more complex approaches as the last literal 376 // only needs to be five bytes long if the previous 377 // back-reference has an offset big enough 378 379 final int lastPairsSize = lastPairs.size(); 380 int toExpand = 0; 381 for (int i = 1; i < lastPairsSize; i++) { 382 toExpand += pairLength.get(i); 383 } 384 final Pair replacement = new Pair(); 385 if (toExpand > 0) { 386 replacement.prependLiteral(expand(toExpand, toExpand)); 387 } 388 final Pair splitCandidate = lastPairs.get(0); 389 final int stillNeeded = MIN_OFFSET_OF_LAST_BACK_REFERENCE - toExpand; 390 final int brLen = splitCandidate.hasBackReference() ? splitCandidate.backReferenceLength() : 0; 391 if (splitCandidate.hasBackReference() && brLen >= MIN_BACK_REFERENCE_LENGTH + stillNeeded) { 392 replacement.prependLiteral(expand(toExpand + stillNeeded, stillNeeded)); 393 pairs.add(splitCandidate.splitWithNewBackReferenceLengthOf(brLen - stillNeeded)); 394 } else { 395 if (splitCandidate.hasBackReference()) { 396 replacement.prependLiteral(expand(toExpand + brLen, brLen)); 397 } 398 splitCandidate.prependTo(replacement); 399 } 400 pairs.add(replacement); 401 } 402 403 /** 404 * Returns a builder correctly configured for the LZ4 algorithm. 405 * @return a builder correctly configured for the LZ4 algorithm 406 */ 407 public static Parameters.Builder createParameterBuilder() { 408 final int maxLen = BlockLZ4CompressorInputStream.WINDOW_SIZE - 1; 409 return Parameters.builder(BlockLZ4CompressorInputStream.WINDOW_SIZE) 410 .withMinBackReferenceLength(MIN_BACK_REFERENCE_LENGTH) 411 .withMaxBackReferenceLength(maxLen) 412 .withMaxOffset(maxLen) 413 .withMaxLiteralLength(maxLen); 414 } 415 416 final static class Pair { 417 private final Deque<byte[]> literals = new LinkedList<>(); 418 private int brOffset, brLength; 419 private boolean written; 420 421 private void prependLiteral(final byte[] data) { 422 literals.addFirst(data); 423 } 424 byte[] addLiteral(final LZ77Compressor.LiteralBlock block) { 425 final byte[] copy = Arrays.copyOfRange(block.getData(), block.getOffset(), 426 block.getOffset() + block.getLength()); 427 literals.add(copy); 428 return copy; 429 } 430 void setBackReference(final LZ77Compressor.BackReference block) { 431 if (hasBackReference()) { 432 throw new IllegalStateException(); 433 } 434 brOffset = block.getOffset(); 435 brLength = block.getLength(); 436 } 437 boolean hasBackReference() { 438 return brOffset > 0; 439 } 440 boolean canBeWritten(final int lengthOfBlocksAfterThisPair) { 441 return hasBackReference() 442 && lengthOfBlocksAfterThisPair >= MIN_OFFSET_OF_LAST_BACK_REFERENCE + MIN_BACK_REFERENCE_LENGTH; 443 } 444 int length() { 445 return literalLength() + brLength; 446 } 447 private boolean hasBeenWritten() { 448 return written; 449 } 450 void writeTo(final OutputStream out) throws IOException { 451 final int litLength = literalLength(); 452 out.write(lengths(litLength, brLength)); 453 if (litLength >= BlockLZ4CompressorInputStream.BACK_REFERENCE_SIZE_MASK) { 454 writeLength(litLength - BlockLZ4CompressorInputStream.BACK_REFERENCE_SIZE_MASK, out); 455 } 456 for (final byte[] b : literals) { 457 out.write(b); 458 } 459 if (hasBackReference()) { 460 ByteUtils.toLittleEndian(out, brOffset, 2); 461 if (brLength - MIN_BACK_REFERENCE_LENGTH >= BlockLZ4CompressorInputStream.BACK_REFERENCE_SIZE_MASK) { 462 writeLength(brLength - MIN_BACK_REFERENCE_LENGTH 463 - BlockLZ4CompressorInputStream.BACK_REFERENCE_SIZE_MASK, out); 464 } 465 } 466 written = true; 467 } 468 private int literalLength() { 469 int length = 0; 470 for (final byte[] b : literals) { 471 length += b.length; 472 } 473 return length; 474 } 475 private static int lengths(final int litLength, final int brLength) { 476 final int l = litLength < 15 ? litLength : 15; 477 final int br = brLength < 4 ? 0 : (brLength < 19 ? brLength - 4 : 15); 478 return (l << BlockLZ4CompressorInputStream.SIZE_BITS) | br; 479 } 480 private static void writeLength(int length, final OutputStream out) throws IOException { 481 while (length >= 255) { 482 out.write(255); 483 length -= 255; 484 } 485 out.write(length); 486 } 487 private int backReferenceLength() { 488 return brLength; 489 } 490 private void prependTo(final Pair other) { 491 final Iterator<byte[]> listBackwards = literals.descendingIterator(); 492 while (listBackwards.hasNext()) { 493 other.prependLiteral(listBackwards.next()); 494 } 495 } 496 private Pair splitWithNewBackReferenceLengthOf(final int newBackReferenceLength) { 497 final Pair p = new Pair(); 498 p.literals.addAll(literals); 499 p.brOffset = brOffset; 500 p.brLength = newBackReferenceLength; 501 return p; 502 } 503 } 504}