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