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}