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}