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