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