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