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    /**
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}