Source code

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(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(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 mininal 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 implemention
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(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(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(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(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(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(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(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(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            int niceLen = niceBackReferenceLength != null ? niceBackReferenceLength
249                : Math.max(minBackReferenceLength, maxBackReferenceLength / 2);
250            int candidates = maxCandidates != null ? maxCandidates : Math.max(256, windowSize / 128);
251            boolean lazy = lazyMatches == null || lazyMatches;
252            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(int windowSize, int minBackReferenceLength, int maxBackReferenceLength, int maxOffset,
264            int maxLiteralLength, int niceBackReferenceLength, int maxCandidates, boolean lazyMatching,
265            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 final boolean isPowerOfTwo(int x) {
347        // pre-condition: x > 0
348        return (x & (x - 1)) == 0;
349    }
350}