    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.lz77support;
    020
    021import java.io.IOException;
    022import java.util.Arrays;
    023import java.util.Objects;
    024
    025/**
    026 * Helper class for compression algorithms that use the ideas of LZ77.
    027 *
    028 * <p>Most LZ77 derived algorithms split input data into blocks of
    029 * uncompressed data (called literal blocks) and back-references
    030 * (pairs of offsets and lengths) that state "add <code>length</code>
    031 * bytes that are the same as those already written starting
    032 * <code>offset</code> bytes before the current position. The details
    033 * of how those blocks and back-references are encoded are quite
    034 * different between the algorithms and some algorithms perform
    035 * additional steps (Huffman encoding in the case of DEFLATE for
    036 * example).</p>
    037 *
    038 * <p>This class attempts to extract the core logic - finding
    039 * back-references - so it can be re-used. It follows the algorithm
    040 * explained in section 4 of RFC 1951 (DEFLATE) and currently doesn't
    041 * implement the "lazy match" optimization. The three-byte hash
    042 * function used in this class is the same as the one used by zlib and
    043 * InfoZIP's ZIP implementation of DEFLATE. The whole class is
    044 * strongly inspired by InfoZIP's implementation.</p>
    045 *
    046 * <p>LZ77 is used vaguely here (as well as many other places that
    047 * talk about it :-), LZSS would likely be closer to the truth but
    048 * LZ77 has become the synonym for a whole family of algorithms.</p>
    049 *
    050 * <p>The API consists of a compressor that is fed <code>byte</code>s
    051 * and emits {@link Block}s to a registered callback where the blocks
    052 * represent either {@link LiteralBlock literal blocks}, {@link
    053 * BackReference back-references} or {@link EOD end of data
    054 * markers}. In order to ensure the callback receives all information,
    055 * the {@code #finish} method must be used once all data has been fed
    056 * into the compressor.</p>
    057 *
    058 * <p>Several parameters influence the outcome of the "compression":</p>
    059 * <dl>
    060 *
    061 *  <dt><code>windowSize</code></dt> <dd>the size of the sliding
    062 *  window, must be a power of two - this determines the maximum
    063 *  offset a back-reference can take. The compressor maintains a
    064 *  buffer of twice of <code>windowSize</code> - real world values are
    065 *  in the area of 32k.</dd>
    066 *
    067 *  <dt><code>minBackReferenceLength</code></dt>
    068 *  <dd>Minimal length of a back-reference found. A true minimum of 3 is
    069 *  hard-coded inside of this implementation but bigger lengths can be
    070 *  configured.</dd>
    071 *
    072 *  <dt><code>maxBackReferenceLength</code></dt>
    073 *  <dd>Maximal length of a back-reference found.</dd>
    074 *
    075 *  <dt><code>maxOffset</code></dt>
    076 *  <dd>Maximal offset of a back-reference.</dd>
    077 *
    078 *  <dt><code>maxLiteralLength</code></dt>
    079 *  <dd>Maximal length of a literal block.</dd>
    080 * </dl>
    081 *
    082 * @see "https://tools.ietf.org/html/rfc1951#section-4"
    083 * @since 1.14
    084 * @NotThreadSafe
    085 */
    086public class LZ77Compressor {
    087
    088    /**
    089     * Base class representing blocks the compressor may emit.
    090     *
    091     * <p>This class is not supposed to be subclassed by classes
    092     * outside of Commons Compress so it is considered internal and
    093     * changed that would break subclasses may get introduced with
    094     * future releases.</p>
    095     */
    096    public static abstract class Block {
    097        /** Enumeration of the block types the compressor may emit. */
    098        public enum BlockType {
    099            LITERAL, BACK_REFERENCE, EOD
    100        }
    101        public abstract BlockType getType();
    102    }
    103
    104    /**
    105     * Represents a literal block of data.
    106     *
    107     * <p>For performance reasons this encapsulates the real data, not
    108     * a copy of it. Don't modify the data and process it inside of
    109     * {@link Callback#accept} immediately as it will get overwritten
    110     * sooner or later.</p>
    111     */
    112    public static final class LiteralBlock extends Block {
    113        private final byte[] data;
    114        private final int offset, length;
    115        public LiteralBlock(final byte[] data, final int offset, final int length) {
    116            this.data = data;
    117            this.offset = offset;
    118            this.length = length;
    119        }
    120        /**
    121         * The literal data.
    122         *
    123         * <p>This returns a life view of the actual data in order to
    124         * avoid copying, modify the array at your own risk.</p>
    125         * @return the data
    126         */
    127        public byte[] getData() {
    128            return data;
    129        }
    130        /**
    131         * Offset into data where the literal block starts.
    132         * @return the offset
    133         */
    134        public int getOffset() {
    135            return offset;
    136        }
    137        /**
    138         * Length of literal block.
    139         * @return the length
    140         */
    141        public int getLength() {
    142            return length;
    143        }
    144        @Override
    145        public BlockType getType() {
    146            return BlockType.LITERAL;
    147        }
    148        @Override
    149        public String toString() {
    150            return "LiteralBlock starting at " + offset + " with length " + length;
    151        }
    152    }
    153
    154    /**
    155     * Represents a back-reference.
    156     */
    157    public static final class BackReference extends Block {
    158        private final int offset, length;
    159        public BackReference(final int offset, final int length) {
    160            this.offset = offset;
    161            this.length = length;
    162        }
    163        /**
    164         * Provides the offset of the back-reference.
    165         * @return the offset
    166         */
    167        public int getOffset() {
    168            return offset;
    169        }
    170        /**
    171         * Provides the length of the back-reference.
    172         * @return the length
    173         */
    174        public int getLength() {
    175            return length;
    176        }
    177        @Override
    178        public BlockType getType() {
    179            return BlockType.BACK_REFERENCE;
    180        }
    181        @Override
    182        public String toString() {
    183            return "BackReference with offset " + offset + " and length " + length;
    184        }
    185    }
    186
    187    /** A simple "we are done" marker. */
    188    public static final class EOD extends Block {
    189        @Override
    190        public BlockType getType() {
    191            return BlockType.EOD;
    192        }
    193    }
    194
    195    private static final Block THE_EOD = new EOD();
    196
    197    /**
    198     * Callback invoked while the compressor processes data.
    199     *
    200     * <p>The callback is invoked on the same thread that receives the
    201     * bytes to compress and may be invoked multiple times during the
    202     * execution of {@link #compress} or {@link #finish}.</p>
    203     */
    204    public interface Callback {
    205        /**
    206         * Consumes a block.
    207         * @param b the block to consume
    208         * @throws IOException in case of an error
    209         */
    210        void accept(Block b) throws IOException;
    211    }
    212
    213    static final int NUMBER_OF_BYTES_IN_HASH = 3;
    214    private static final int NO_MATCH = -1;
    215
    216    private final Parameters params;
    217    private final Callback callback;
    218
    219    // the sliding window, twice as big as "windowSize" parameter
    220    private final byte[] window;
    221    // the head of hash-chain - indexed by hash-code, points to the
    222    // location inside of window of the latest sequence of bytes with
    223    // the given hash.
    224    private final int[] head;
    225    // for each window-location points to the latest earlier location
    226    // with the same hash. Only stores values for the latest
    227    // "windowSize" elements, the index is "window location modulo
    228    // windowSize".
    229    private final int[] prev;
    230
    231    // bit mask used when indexing into prev
    232    private final int wMask;
    233
    234    private boolean initialized;
    235    // the position inside of window that shall be encoded right now
    236    private int currentPosition;
    237    // the number of bytes available to compress including the one at
    238    // currentPosition
    239    private int lookahead;
    240    // the hash of the three bytes stating at the current position
    241    private int insertHash;
    242    // the position inside of the window where the current literal
    243    // block starts (in case we are inside of a literal block).
    244    private int blockStart;
    245    // position of the current match
    246    private int matchStart = NO_MATCH;
    247    // number of missed insertString calls for the up to three last
    248    // bytes of the last match that can only be performed once more
    249    // data has been read
    250    private int missedInserts;
    251
    252    /**
    253     * Initializes a compressor with parameters and a callback.
    254     * @param params the parameters
    255     * @param callback the callback
    256     * @throws NullPointerException if either parameter is <code>null</code>
    257     */
    258    public LZ77Compressor(final Parameters params, final Callback callback) {
    259        Objects.requireNonNull(params, "params");
    260        Objects.requireNonNull(callback, "callback");
    261
    262        this.params = params;
    263        this.callback = callback;
    264
    265        final int wSize = params.getWindowSize();
    266        window = new byte[wSize * 2];
    267        wMask = wSize - 1;
    268        head = new int[HASH_SIZE];
    269        Arrays.fill(head, NO_MATCH);
    270        prev = new int[wSize];
    271    }
    272
    273    /**
    274     * Feeds bytes into the compressor which in turn may emit zero or
    275     * more blocks to the callback during the execution of this
    276     * method.
    277     * @param data the data to compress - must not be null
    278     * @throws IOException if the callback throws an exception
    279     */
    280    public void compress(final byte[] data) throws IOException {
    281        compress(data, 0, data.length);
    282    }
    283
    284    /**
    285     * Feeds bytes into the compressor which in turn may emit zero or
    286     * more blocks to the callback during the execution of this
    287     * method.
    288     * @param data the data to compress - must not be null
    289     * @param off the start offset of the data
    290     * @param len the number of bytes to compress
    291     * @throws IOException if the callback throws an exception
    292     */
    293    public void compress(final byte[] data, int off, int len) throws IOException {
    294        final int wSize = params.getWindowSize();
    295        while (len > wSize) { // chop into windowSize sized chunks
    296            doCompress(data, off, wSize);
    297            off += wSize;
    298            len -= wSize;
    299        }
    300        if (len > 0) {
    301            doCompress(data, off, len);
    302        }
    303    }
    304
    305    /**
    306     * Tells the compressor to process all remaining data and signal
    307     * end of data to the callback.
    308     *
    309     * <p>The compressor will in turn emit at least one block ({@link
    310     * EOD}) but potentially multiple blocks to the callback during
    311     * the execution of this method.</p>
    312     * @throws IOException if the callback throws an exception
    313     */
    314    public void finish() throws IOException {
    315        if (blockStart != currentPosition || lookahead > 0) {
    316            currentPosition += lookahead;
    317            flushLiteralBlock();
    318        }
    319        callback.accept(THE_EOD);
    320    }
    321
    322    /**
    323     * Adds some initial data to fill the window with.
    324     *
    325     * <p>This is used if the stream has been cut into blocks and
    326     * back-references of one block may refer to data of the previous
    327     * block(s). One such example is the LZ4 frame format using block
    328     * dependency.</p>
    329     *
    330     * @param data the data to fill the window with.
    331     * @throws IllegalStateException if the compressor has already started to accept data
    332     */
    333    public void prefill(final byte[] data) {
    334        if (currentPosition != 0 || lookahead != 0) {
    335            throw new IllegalStateException("The compressor has already started to accept data, can't prefill anymore");
    336        }
    337
    338        // don't need more than windowSize for back-references
    339        final int len = Math.min(params.getWindowSize(), data.length);
    340        System.arraycopy(data, data.length - len, window, 0, len);
    341
    342        if (len >= NUMBER_OF_BYTES_IN_HASH) {
    343            initialize();
    344            final int stop = len - NUMBER_OF_BYTES_IN_HASH + 1;
    345            for (int i = 0; i < stop; i++) {
    346                insertString(i);
    347            }
    348            missedInserts = NUMBER_OF_BYTES_IN_HASH - 1;
    349        } else { // not enough data to hash anything
    350            missedInserts = len;
    351        }
    352        blockStart = currentPosition = len;
    353    }
    354
    355    // we use a 15 bit hashcode as calculated in updateHash
    356    private static final int HASH_SIZE = 1 << 15;
    357    private static final int HASH_MASK = HASH_SIZE - 1;
    358    private static final int H_SHIFT = 5;
    359
    360    /**
    361     * Assumes we are calculating the hash for three consecutive bytes
    362     * as a rolling hash, i.e. for bytes ABCD if H is the hash of ABC
    363     * the new hash for BCD is nextHash(H, D).
    364     *
    365     * <p>The hash is shifted by five bits on each update so all
    366     * effects of A have been swapped after the third update.</p>
    367     */
    368    private int nextHash(final int oldHash, final byte nextByte) {
    369        final int nextVal = nextByte & 0xFF;
    370        return ((oldHash << H_SHIFT) ^ nextVal) & HASH_MASK;
    371    }
    372
    373    // performs the actual algorithm with the pre-condition len <= windowSize
    374    private void doCompress(final byte[] data, final int off, final int len) throws IOException {
    375        final int spaceLeft = window.length - currentPosition - lookahead;
    376        if (len > spaceLeft) {
    377            slide();
    378        }
    379        System.arraycopy(data, off, window, currentPosition + lookahead, len);
    380        lookahead += len;
    381        if (!initialized && lookahead >= params.getMinBackReferenceLength()) {
    382            initialize();
    383        }
    384        if (initialized) {
    385            compress();
    386        }
    387    }
    388
    389    private void slide() throws IOException {
    390        final int wSize = params.getWindowSize();
    391        if (blockStart != currentPosition && blockStart < wSize) {
    392            flushLiteralBlock();
    393            blockStart = currentPosition;
    394        }
    395        System.arraycopy(window, wSize, window, 0, wSize);
    396        currentPosition -= wSize;
    397        matchStart -= wSize;
    398        blockStart -= wSize;
    399        for (int i = 0; i < HASH_SIZE; i++) {
    400            final int h = head[i];
    401            head[i] = h >= wSize ? h - wSize : NO_MATCH;
    402        }
    403        for (int i = 0; i < wSize; i++) {
    404            final int p = prev[i];
    405            prev[i] = p >= wSize ? p - wSize : NO_MATCH;
    406        }
    407    }
    408
    409    private void initialize() {
    410        for (int i = 0; i < NUMBER_OF_BYTES_IN_HASH - 1; i++) {
    411            insertHash = nextHash(insertHash, window[i]);
    412        }
    413        initialized = true;
    414    }
    415
    416    private void compress() throws IOException {
    417        final int minMatch = params.getMinBackReferenceLength();
    418        final boolean lazy = params.getLazyMatching();
    419        final int lazyThreshold = params.getLazyMatchingThreshold();
    420
    421        while (lookahead >= minMatch) {
    422            catchUpMissedInserts();
    423            int matchLength = 0;
    424            final int hashHead = insertString(currentPosition);
    425            if (hashHead != NO_MATCH && hashHead - currentPosition <= params.getMaxOffset()) {
    426                // sets matchStart as a side effect
    427                matchLength = longestMatch(hashHead);
    428
    429                if (lazy && matchLength <= lazyThreshold && lookahead > minMatch) {
    430                    // try to find a longer match using the next position
    431                    matchLength = longestMatchForNextPosition(matchLength);
    432                }
    433            }
    434            if (matchLength >= minMatch) {
    435                if (blockStart != currentPosition) {
    436                    // emit preceeding literal block
    437                    flushLiteralBlock();
    438                    blockStart = NO_MATCH;
    439                }
    440                flushBackReference(matchLength);
    441                insertStringsInMatch(matchLength);
    442                lookahead -= matchLength;
    443                currentPosition += matchLength;
    444                blockStart = currentPosition;
    445            } else {
    446                // no match, append to current or start a new literal
    447                lookahead--;
    448                currentPosition++;
    449                if (currentPosition - blockStart >= params.getMaxLiteralLength()) {
    450                    flushLiteralBlock();
    451                    blockStart = currentPosition;
    452                }
    453            }
    454        }
    455    }
    456
    457    /**
    458     * Inserts the current three byte sequence into the dictionary and
    459     * returns the previous head of the hash-chain.
    460     *
    461     * <p>Updates <code>insertHash</code> and <code>prev</code> as a
    462     * side effect.</p>
    463     */
    464    private int insertString(final int pos) {
    465        insertHash = nextHash(insertHash, window[pos - 1 + NUMBER_OF_BYTES_IN_HASH]);
    466        final int hashHead = head[insertHash];
    467        prev[pos & wMask] = hashHead;
    468        head[insertHash] = pos;
    469        return hashHead;
    470    }
    471
    472    private int longestMatchForNextPosition(final int prevMatchLength) {
    473        // save a bunch of values to restore them if the next match isn't better than the current one
    474        final int prevMatchStart = matchStart;
    475        final int prevInsertHash = insertHash;
    476
    477        lookahead--;
    478        currentPosition++;
    479        final int hashHead = insertString(currentPosition);
    480        final int prevHashHead = prev[currentPosition & wMask];
    481        int matchLength = longestMatch(hashHead);
    482
    483        if (matchLength <= prevMatchLength) {
    484            // use the first match, as the next one isn't any better
    485            matchLength = prevMatchLength;
    486            matchStart = prevMatchStart;
    487
    488            // restore modified values
    489            head[insertHash] = prevHashHead;
    490            insertHash = prevInsertHash;
    491            currentPosition--;
    492            lookahead++;
    493        }
    494        return matchLength;
    495    }
    496
    497    private void insertStringsInMatch(final int matchLength) {
    498        // inserts strings contained in current match
    499        // insertString inserts the byte 2 bytes after position, which may not yet be available -> missedInserts
    500        final int stop = Math.min(matchLength - 1, lookahead - NUMBER_OF_BYTES_IN_HASH);
    501        // currentPosition has been inserted already
    502        for (int i = 1; i <= stop; i++) {
    503            insertString(currentPosition + i);
    504        }
    505        missedInserts = matchLength - stop - 1;
    506    }
    507
    508    private void catchUpMissedInserts() {
    509        while (missedInserts > 0) {
    510            insertString(currentPosition - missedInserts--);
    511        }
    512    }
    513
    514    private void flushBackReference(final int matchLength) throws IOException {
    515        callback.accept(new BackReference(currentPosition - matchStart, matchLength));
    516    }
    517
    518    private void flushLiteralBlock() throws IOException {
    519        callback.accept(new LiteralBlock(window, blockStart, currentPosition - blockStart));
    520    }
    521
    522    /**
    523     * Searches the hash chain for real matches and returns the length
    524     * of the longest match (0 if none were found) that isn't too far
    525     * away (WRT maxOffset).
    526     *
    527     * <p>Sets matchStart to the index of the start position of the
    528     * longest match as a side effect.</p>
    529     */
    530    private int longestMatch(int matchHead) {
    531        final int minLength = params.getMinBackReferenceLength();
    532        int longestMatchLength = minLength - 1;
    533        final int maxPossibleLength = Math.min(params.getMaxBackReferenceLength(), lookahead);
    534        final int minIndex = Math.max(0, currentPosition - params.getMaxOffset());
    535        final int niceBackReferenceLength = Math.min(maxPossibleLength, params.getNiceBackReferenceLength());
    536        final int maxCandidates = params.getMaxCandidates();
    537        for (int candidates = 0; candidates < maxCandidates && matchHead >= minIndex; candidates++) {
    538            int currentLength = 0;
    539            for (int i = 0; i < maxPossibleLength; i++) {
    540                if (window[matchHead + i] != window[currentPosition + i]) {
    541                    break;
    542                }
    543                currentLength++;
    544            }
    545            if (currentLength > longestMatchLength) {
    546                longestMatchLength = currentLength;
    547                matchStart = matchHead;
    548                if (currentLength >= niceBackReferenceLength) {
    549                    // no need to search any further
    550                    break;
    551                }
    552            }
    553            matchHead = prev[matchHead & wMask];
    554        }
    555        return longestMatchLength; // < minLength if no matches have been found, will be ignored in compress()
    556    }
    557}