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