    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
    021/**
    022 * Parameters of the {@link LZ77Compressor compressor}.
    023 */
    024public final class Parameters {
    025    /**
    026     * Builder for {@link Parameters} instances.
    027     */
    028    public static class Builder {
    029        private final int windowSize;
    030        private int minBackReferenceLength, maxBackReferenceLength, maxOffset, maxLiteralLength;
    031        private Integer niceBackReferenceLength, maxCandidates, lazyThreshold;
    032        private Boolean lazyMatches;
    033
    034        private Builder(final int windowSize) {
    035            if (windowSize < 2 || !isPowerOfTwo(windowSize)) {
    036                throw new IllegalArgumentException("windowSize must be a power of two");
    037            }
    038            this.windowSize = windowSize;
    039            minBackReferenceLength = TRUE_MIN_BACK_REFERENCE_LENGTH;
    040            maxBackReferenceLength = windowSize - 1;
    041            maxOffset = windowSize - 1;
    042            maxLiteralLength = windowSize;
    043        }
    044
    045        /**
    046         * Creates the {@link Parameters} instance.
    047         * @return the configured {@link Parameters} instance.
    048         */
    049        public Parameters build() {
    050            // default settings tuned for a compromise of good compression and acceptable speed
    051            final int niceLen = niceBackReferenceLength != null ? niceBackReferenceLength
    052                : Math.max(minBackReferenceLength, maxBackReferenceLength / 2);
    053            final int candidates = maxCandidates != null ? maxCandidates : Math.max(256, windowSize / 128);
    054            final boolean lazy = lazyMatches == null || lazyMatches;
    055            final int threshold = lazy ? lazyThreshold != null ? lazyThreshold : niceLen : minBackReferenceLength;
    056
    057            return new Parameters(windowSize, minBackReferenceLength, maxBackReferenceLength,
    058                maxOffset, maxLiteralLength, niceLen, candidates, lazy, threshold);
    059        }
    060
    061        /**
    062         * Changes the default setting for "nice back-reference length" and "maximum number of candidates" for improved
    063         * compression ratio at the cost of compression speed.
    064         *
    065         * <p>Use this method after configuring "maximum back-reference length".</p>
    066         * @return the builder
    067         */
    068        public Builder tunedForCompressionRatio() {
    069            niceBackReferenceLength = lazyThreshold = maxBackReferenceLength;
    070            maxCandidates = Math.max(32, windowSize / 16);
    071            lazyMatches = true;
    072            return this;
    073        }
    074
    075        /**
    076         * Changes the default setting for "nice back-reference length" and "maximum number of candidates" for improved
    077         * compression speed at the cost of compression ratio.
    078         *
    079         * <p>Use this method after configuring "maximum back-reference length".</p>
    080         * @return the builder
    081         */
    082        public Builder tunedForSpeed() {
    083            niceBackReferenceLength = Math.max(minBackReferenceLength, maxBackReferenceLength / 8);
    084            maxCandidates = Math.max(32, windowSize / 1024);
    085            lazyMatches = false;
    086            lazyThreshold = minBackReferenceLength;
    087            return this;
    088        }
    089
    090        /**
    091         * Sets whether lazy matching should be performed.
    092         *
    093         * <p>Lazy matching means that after a back-reference for a certain position has been found the compressor will
    094         * try to find a longer match for the next position.</p>
    095         *
    096         * <p>Lazy matching is enabled by default and disabled when tuning for speed.</p>
    097         * @param lazy whether lazy matching should be performed
    098         * @return the builder
    099         */
    100        public Builder withLazyMatching(final boolean lazy) {
    101            lazyMatches = lazy;
    102            return this;
    103        }
    104
    105        /**
    106         * Sets the threshold for lazy matching.
    107         *
    108         * <p>Even if lazy matching is enabled it will not be performed if the length of the back-reference found for
    109         * the current position is longer than this value.</p>
    110         * @param threshold the threshold for lazy matching
    111         * @return the builder
    112         */
    113        public Builder withLazyThreshold(final int threshold) {
    114            lazyThreshold = threshold;
    115            return this;
    116        }
    117
    118        /**
    119         * Sets the maximal length of a back-reference.
    120         *
    121         * <p>It is recommended to not use this method directly but
    122         * rather tune a pre-configured builder created by a format
    123         * specific factory like {@link
    124         * org.apache.commons.compress.compressors.snappy.SnappyCompressorOutputStream#createParameterBuilder}.</p>
    125         *
    126         * @param maxBackReferenceLength maximal length of a
    127         * back-reference found. A value smaller than
    128         * {@code minBackReferenceLength} is interpreted as
    129         * {@code minBackReferenceLength}. {@code maxBackReferenceLength}
    130         * is capped at {@code windowSize - 1}.
    131         * @return the builder
    132         */
    133        public Builder withMaxBackReferenceLength(final int maxBackReferenceLength) {
    134            this.maxBackReferenceLength = maxBackReferenceLength < minBackReferenceLength ? minBackReferenceLength
    135                : Math.min(maxBackReferenceLength, windowSize - 1);
    136            return this;
    137        }
    138
    139        /**
    140         * Sets the maximal length of a literal block.
    141         *
    142         * <p>It is recommended to not use this method directly but
    143         * rather tune a pre-configured builder created by a format
    144         * specific factory like {@link
    145         * org.apache.commons.compress.compressors.snappy.SnappyCompressorOutputStream#createParameterBuilder}.</p>
    146         *
    147         * @param maxLiteralLength maximal length of a literal
    148         * block. Negative numbers and 0 as well as values bigger than
    149         * {@code windowSize} are interpreted as
    150         * {@code windowSize}.
    151         * @return the builder
    152         */
    153        public Builder withMaxLiteralLength(final int maxLiteralLength) {
    154            this.maxLiteralLength = maxLiteralLength < 1 ? windowSize
    155                : Math.min(maxLiteralLength, windowSize);
    156            return this;
    157        }
    158
    159        /**
    160         * Sets the maximum number of back-reference candidates that should be consulted.
    161         *
    162         * <p>This settings can be used to tune the tradeoff between compression speed and compression ratio.</p>
    163         * @param maxCandidates maximum number of back-reference candidates
    164         * @return the builder
    165         */
    166        public Builder withMaxNumberOfCandidates(final int maxCandidates) {
    167            this.maxCandidates = maxCandidates;
    168            return this;
    169        }
    170
    171        /**
    172         * Sets the maximal offset of a back-reference.
    173         *
    174         * <p>It is recommended to not use this method directly but
    175         * rather tune a pre-configured builder created by a format
    176         * specific factory like {@link
    177         * org.apache.commons.compress.compressors.snappy.SnappyCompressorOutputStream#createParameterBuilder}.</p>
    178         *
    179         * @param maxOffset maximal offset of a back-reference. A
    180         * non-positive value as well as values bigger than
    181         * {@code windowSize - 1} are interpreted as <code>windowSize
    182         * - 1</code>.
    183         * @return the builder
    184         */
    185        public Builder withMaxOffset(final int maxOffset) {
    186            this.maxOffset = maxOffset < 1 ? windowSize - 1 : Math.min(maxOffset, windowSize - 1);
    187            return this;
    188        }
    189
    190        /**
    191         * Sets the minimal length of a back-reference.
    192         *
    193         * <p>Ensures {@code maxBackReferenceLength} is not
    194         * smaller than {@code minBackReferenceLength}.
    195         *
    196         * <p>It is recommended to not use this method directly but
    197         * rather tune a pre-configured builder created by a format
    198         * specific factory like {@link
    199         * org.apache.commons.compress.compressors.snappy.SnappyCompressorOutputStream#createParameterBuilder}.</p>
    200         *
    201         * @param minBackReferenceLength the minimal length of a back-reference found. A
    202         * true minimum of 3 is hard-coded inside of this implementation
    203         * but bigger lengths can be configured.
    204         * @throws IllegalArgumentException if {@code windowSize}
    205         * is smaller than {@code minBackReferenceLength}.
    206         * @return the builder
    207         */
    208        public Builder withMinBackReferenceLength(final int minBackReferenceLength) {
    209            this.minBackReferenceLength = Math.max(TRUE_MIN_BACK_REFERENCE_LENGTH, minBackReferenceLength);
    210            if (windowSize < this.minBackReferenceLength) {
    211                throw new IllegalArgumentException("minBackReferenceLength can't be bigger than windowSize");
    212            }
    213            if (maxBackReferenceLength < this.minBackReferenceLength) {
    214                maxBackReferenceLength = this.minBackReferenceLength;
    215            }
    216            return this;
    217        }
    218
    219        /**
    220         * Sets the "nice length" of a back-reference.
    221         *
    222         * <p>When a back-references if this size has been found, stop searching for longer back-references.</p>
    223         *
    224         * <p>This settings can be used to tune the tradeoff between compression speed and compression ratio.</p>
    225         * @param niceLen the "nice length" of a back-reference
    226         * @return the builder
    227         */
    228        public Builder withNiceBackReferenceLength(final int niceLen) {
    229            niceBackReferenceLength = niceLen;
    230            return this;
    231        }
    232    }
    233
    234    /**
    235     * The hard-coded absolute minimal length of a back-reference.
    236     */
    237    public static final int TRUE_MIN_BACK_REFERENCE_LENGTH = LZ77Compressor.NUMBER_OF_BYTES_IN_HASH;
    238
    239    /**
    240     * Initializes the builder for the compressor's parameters with a
    241     * {@code minBackReferenceLength} of 3 and {@code max*Length}
    242     * equal to {@code windowSize - 1}.
    243     *
    244     * <p>It is recommended to not use this method directly but rather
    245     * tune a pre-configured builder created by a format specific
    246     * factory like {@link
    247     * org.apache.commons.compress.compressors.snappy.SnappyCompressorOutputStream#createParameterBuilder}.</p>
    248     *
    249     * @param windowSize the size of the sliding window - this
    250     * determines the maximum offset a back-reference can take. Must
    251     * be a power of two.
    252     * @throws IllegalArgumentException if windowSize is not a power of two.
    253     * @return a builder configured for the given window size
    254     */
    255    public static Builder builder(final int windowSize) {
    256        return new Builder(windowSize);
    257    }
    258
    259    private static boolean isPowerOfTwo(final int x) {
    260        // pre-condition: x > 0
    261        return (x & x - 1) == 0;
    262    }
    263    private final int windowSize, minBackReferenceLength, maxBackReferenceLength, maxOffset, maxLiteralLength,
    264        niceBackReferenceLength, maxCandidates, lazyThreshold;
    265
    266    private final boolean lazyMatching;
    267
    268    private Parameters(final int windowSize, final int minBackReferenceLength, final int maxBackReferenceLength, final int maxOffset,
    269            final int maxLiteralLength, final int niceBackReferenceLength, final int maxCandidates, final boolean lazyMatching,
    270            final int lazyThreshold) {
    271        this.windowSize = windowSize;
    272        this.minBackReferenceLength = minBackReferenceLength;
    273        this.maxBackReferenceLength = maxBackReferenceLength;
    274        this.maxOffset = maxOffset;
    275        this.maxLiteralLength = maxLiteralLength;
    276        this.niceBackReferenceLength = niceBackReferenceLength;
    277        this.maxCandidates = maxCandidates;
    278        this.lazyMatching = lazyMatching;
    279        this.lazyThreshold = lazyThreshold;
    280    }
    281    /**
    282     * Gets whether to perform lazy matching.
    283     * @return whether to perform lazy matching
    284     */
    285    public boolean getLazyMatching() {
    286        return lazyMatching;
    287    }
    288    /**
    289     * Gets the threshold for lazy matching.
    290     * @return the threshold for lazy matching
    291     */
    292    public int getLazyMatchingThreshold() {
    293        return lazyThreshold;
    294    }
    295    /**
    296     * Gets the maximal length of a back-reference found.
    297     * @return the maximal length of a back-reference found
    298     */
    299    public int getMaxBackReferenceLength() {
    300        return maxBackReferenceLength;
    301    }
    302    /**
    303     * Gets the maximum number of back-reference candidates to consider.
    304     * @return the maximum number of back-reference candidates to consider
    305     */
    306    public int getMaxCandidates() {
    307        return maxCandidates;
    308    }
    309
    310    /**
    311     * Gets the maximal length of a literal block.
    312     * @return the maximal length of a literal block
    313     */
    314    public int getMaxLiteralLength() {
    315        return maxLiteralLength;
    316    }
    317
    318    /**
    319     * Gets the maximal offset of a back-reference found.
    320     * @return the maximal offset of a back-reference found
    321     */
    322    public int getMaxOffset() {
    323        return maxOffset;
    324    }
    325
    326    /**
    327     * Gets the minimal length of a back-reference found.
    328     * @return the minimal length of a back-reference found
    329     */
    330    public int getMinBackReferenceLength() {
    331        return minBackReferenceLength;
    332    }
    333
    334    /**
    335     * Gets the length of a back-reference that is considered nice enough to stop searching for longer ones.
    336     * @return the length of a back-reference that is considered nice enough to stop searching
    337     */
    338    public int getNiceBackReferenceLength() {
    339        return niceBackReferenceLength;
    340    }
    341
    342    /**
    343     * Gets the size of the sliding window - this determines the
    344     * maximum offset a back-reference can take.
    345     * @return the size of the sliding window
    346     */
    347    public int getWindowSize() {
    348        return windowSize;
    349    }
    350}