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}