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