| // Copyright 2016 Google Inc. All rights reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| package com.google.archivepatcher.shared; |
| |
| import java.io.ByteArrayInputStream; |
| import java.io.ByteArrayOutputStream; |
| import java.io.IOException; |
| import java.io.UnsupportedEncodingException; |
| import java.security.MessageDigest; |
| import java.security.NoSuchAlgorithmException; |
| import java.util.Collections; |
| import java.util.HashMap; |
| import java.util.Map; |
| import java.util.zip.Deflater; |
| |
| // TODO: Skip the zlib header bytes for fingerprint computation and simply ignore the "wrapped" set |
| // of values completely. This will cut fingerprints by half and fix compatibility issues with older |
| // JVMs caused by this zlib commit that twiddled the level flag assignments in the zlib header |
| // fields: https://github.com/madler/zlib/commit/086e982175da84b3db958191031380794315f95f |
| |
| // TODO: Consider dropping support for both nowrap=false and strategies 1 and 2, since in practice |
| // they are vanishingly rare. |
| |
| // Baseline generated on 2015-11-27 using Oracle's Java Runtime Environment: |
| // Java(TM) SE Runtime Environment (build 1.8.0_66-b18) |
| // Java HotSpot(TM) 64-Bit Server VM (build 25.66-b18, mixed mode) |
| |
| /** |
| * Defines the default deflate compatibility window. This window determines compatibility with |
| * {@link java.util.zip.Deflater} with all relevant combinations of the following settings: |
| * <ul> |
| * <li>Strategies 0, 1 and 2</li> |
| * <li>Levels 1, 2, 3, 4, 5, 6, 7, 8 and 9</li> |
| * <li>Wrapping on (nowrap=false) and off (nowrap=true)</li> |
| * </ul> |
| * Strategy 2, {@link java.util.zip.Deflater#HUFFMAN_ONLY}, does not utilize compression levels. |
| * For querying strategy 2, always use level 1 for the lookup. |
| * There are thus a total of <strong>38</strong> configurations: |
| * <ul> |
| * <li>18 configurations for strategy 0 {@link java.util.zip.Deflater#DEFAULT_STRATEGY}: |
| * compression levels 1 through 9, with wrapping on and off;</li> |
| * <li>18 configurations for strategy 1 {@link java.util.zip.Deflater#FILTERED}: |
| * compression levels 1 through 9, with wrapping on and off;</li> |
| * <li>2 configurations for strategy 2 {@link java.util.zip.Deflater#HUFFMAN_ONLY}: |
| * compression level 1 (arbitrarily chosen), with wrapping on and off. |
| * </ul> |
| * The following is a non-exhaustive list of platforms that are known to be compatible: |
| * <ul> |
| * <li>Sun/Oracle JRE version 1.6.0 or later on x86 and x86_64</li> |
| * <li>Android version 4.0 or later (Ice Cream Sandwich / API 15) on x86, arm32 and arm64</li> |
| * </ul> |
| * The minimum known-compatible version of zlib is 1.2.0.4 |
| * (https://github.com/madler/zlib/commit/086e982175da84b3db958191031380794315f95f). |
| */ |
| public class DefaultDeflateCompatibilityWindow { |
| /** |
| * Implementation of the lazy-holder idiom to hold and return the baseline. |
| */ |
| private static final class BaselineHolder { |
| private static final Map<JreDeflateParameters, String> BASELINE_INSTANCE = generateBaseline(); |
| } |
| |
| /** |
| * Generates the baseline and returns it. |
| * @return see {@link #getBaselineValues()} |
| */ |
| private static final Map<JreDeflateParameters, String> generateBaseline() { |
| Map<JreDeflateParameters, String> baseline = new HashMap<JreDeflateParameters, String>(); |
| baseline.put( |
| JreDeflateParameters.of(1, 0, true), |
| "5e0ae60766a04b0c9ef1f677ae4ba4a83a6bc112ce3761b41b270af08821804e"); |
| baseline.put( |
| JreDeflateParameters.of(2, 0, true), |
| "9b392414e62afcc64200cc39955ff75d1254f56c67bf2eb05d62f63b677080fc"); |
| baseline.put( |
| JreDeflateParameters.of(3, 0, true), |
| "ce272e7f72232e80b5d00d7333a5bdd6e9d7e34268d49c5fe9bdfedba6fc0d54"); |
| baseline.put( |
| JreDeflateParameters.of(4, 0, true), |
| "a8a3b59d42fe257766926d46818422216a043c8c37bb69492d9bab3bd4d6b07a"); |
| baseline.put( |
| JreDeflateParameters.of(5, 0, true), |
| "49280186dd6683ae92ef25e239d7c0e2b7a4fd0e2b7dfadc8846f5157aa6aed9"); |
| baseline.put( |
| JreDeflateParameters.of(6, 0, true), |
| "bec508de691537047e338825828db16308cc8dc93e22386c8eeb0bc14c4c5f45"); |
| baseline.put( |
| JreDeflateParameters.of(7, 0, true), |
| "6daf3724aed1f67c7d1f6404166b5dbea1f2fc42192f20813910271bc8c40e75"); |
| baseline.put( |
| JreDeflateParameters.of(8, 0, true), |
| "08cd258637bb146d33ef550fc60baaa855902837758d6489802f3b1ece6ea7f1"); |
| baseline.put( |
| JreDeflateParameters.of(9, 0, true), |
| "5ea67964bb124b436130dfbbd2e36fb2b08992423be188a8edfbb8550e8bfefb"); |
| baseline.put( |
| JreDeflateParameters.of(1, 1, true), |
| "5e0ae60766a04b0c9ef1f677ae4ba4a83a6bc112ce3761b41b270af08821804e"); |
| baseline.put( |
| JreDeflateParameters.of(2, 1, true), |
| "9b392414e62afcc64200cc39955ff75d1254f56c67bf2eb05d62f63b677080fc"); |
| baseline.put( |
| JreDeflateParameters.of(3, 1, true), |
| "ce272e7f72232e80b5d00d7333a5bdd6e9d7e34268d49c5fe9bdfedba6fc0d54"); |
| baseline.put( |
| JreDeflateParameters.of(4, 1, true), |
| "6283bb35a97f4657b6aab0b0a7f218947965f135838926df295037fdca816746"); |
| baseline.put( |
| JreDeflateParameters.of(5, 1, true), |
| "42594bbcf7fa83f74cdf35839debaae25e4655070fdf1fc67539de0a90f59afe"); |
| baseline.put( |
| JreDeflateParameters.of(6, 1, true), |
| "1db82cae52b0bb88cf3a21cdec183c1dab8074b1d1f4341b9e9b18b1ace5a778"); |
| baseline.put( |
| JreDeflateParameters.of(7, 1, true), |
| "5d0d53667944dc447b52e58b0e91e303b5662f92a085ab5a1f4b62eeab8900ef"); |
| baseline.put( |
| JreDeflateParameters.of(8, 1, true), |
| "c6cdfbe16b1e530e91fd3ac1dbb2a9b2f5b3ccee5ddf92769ea349fc60fd560e"); |
| baseline.put( |
| JreDeflateParameters.of(9, 1, true), |
| "f4e93a15b50c568d39785c12d373104272009bcd71028dbf0faa85441eb5130d"); |
| baseline.put( |
| JreDeflateParameters.of(1, 2, true), |
| "2297dbc0a5498c9a7a89519f401936e910ddb82c9b477e7aa407a4c2bf523dbd"); |
| baseline.put( |
| JreDeflateParameters.of(1, 0, false), |
| "5e06d9c9280e5b9b4832c0894e2f930f606665169ad2ac093df544e70fac4136"); |
| baseline.put( |
| JreDeflateParameters.of(2, 0, false), |
| "f1c2fe9b4189c03a5ae0b1a1db51875d334fb21144e08e9c527644d66ef39797"); |
| baseline.put( |
| JreDeflateParameters.of(3, 0, false), |
| "49998ee364d2668eb5a2cadf40feaa78c0c081337141ad15f7fb2a7843c833b8"); |
| baseline.put( |
| JreDeflateParameters.of(4, 0, false), |
| "6911a5b04664b00b2bba72d7ba9e1d5a73b390f2cf4b20618580c13a5825fc17"); |
| baseline.put( |
| JreDeflateParameters.of(5, 0, false), |
| "417f5fd21438ffb739a681af9a20eed29dd9da63e8a540415b9ec6199495e6db"); |
| baseline.put( |
| JreDeflateParameters.of(6, 0, false), |
| "9a4bcc9afd8547784aff6283cafd69f46893d5131bd798fbad92dc52ca946522"); |
| baseline.put( |
| JreDeflateParameters.of(7, 0, false), |
| "592ad846a99693b2f1092bac6a3bf2cf5ac562a9b38ebe34c46cbf2ddd3c13aa"); |
| baseline.put( |
| JreDeflateParameters.of(8, 0, false), |
| "8d4b91929384dfd7a0dda6b6e0410de7c4c109167047d694cf36b46e68dd8d5f"); |
| baseline.put( |
| JreDeflateParameters.of(9, 0, false), |
| "36bacacc32707e6498269a04d2b2cd30990ac4b0717ee4a9e4badbb6ca5fb7ea"); |
| baseline.put( |
| JreDeflateParameters.of(1, 1, false), |
| "5e06d9c9280e5b9b4832c0894e2f930f606665169ad2ac093df544e70fac4136"); |
| baseline.put( |
| JreDeflateParameters.of(2, 1, false), |
| "f1c2fe9b4189c03a5ae0b1a1db51875d334fb21144e08e9c527644d66ef39797"); |
| baseline.put( |
| JreDeflateParameters.of(3, 1, false), |
| "49998ee364d2668eb5a2cadf40feaa78c0c081337141ad15f7fb2a7843c833b8"); |
| baseline.put( |
| JreDeflateParameters.of(4, 1, false), |
| "2bd9ae26fe933102ed46ef2bf8e82d62e0104d9d1cce73a8b46df8a238fd32f8"); |
| baseline.put( |
| JreDeflateParameters.of(5, 1, false), |
| "6410581a92808f97f695e796c2963cb6e111af1ec7b7e7d155dcb601192dd80a"); |
| baseline.put( |
| JreDeflateParameters.of(6, 1, false), |
| "50571149806edb22b7f3a3ba52168644dd99de444e813df7e186817ccc204c01"); |
| baseline.put( |
| JreDeflateParameters.of(7, 1, false), |
| "7a41b9549bcc651d3d219e7aaf3f74beefea238caf1560036cd299d62be6531b"); |
| baseline.put( |
| JreDeflateParameters.of(8, 1, false), |
| "29da81b218ff50e69819375d2c008a648309dd9a0fc18683d675ce523cff744f"); |
| baseline.put( |
| JreDeflateParameters.of(9, 1, false), |
| "4ce8c7903e526e2a36db168c5cf9af0b90155850899ea26ad77d6daaa7b395c3"); |
| baseline.put( |
| JreDeflateParameters.of(1, 2, false), |
| "e3cc7200f308fa7756f02bebbf5046e58a4a2a7e8f1c9ea1708b96d4e1033666"); |
| return Collections.unmodifiableMap(baseline); |
| } |
| |
| /** |
| * Returns the baseline that this tool expects to find on all compatible systems. |
| * |
| * @return a mapping from {@link JreDeflateParameters} to the corresponding SHA-256 of the result |
| * of compressing the corpus with those parameters. Level 0 is not used, because level 0 means |
| * "store" (and is therefore not compressed). |
| */ |
| public Map<JreDeflateParameters, String> getBaselineValues() { |
| return BaselineHolder.BASELINE_INSTANCE; |
| } |
| |
| /** |
| * Base of corpus for finger-printing. |
| */ |
| private static final String CORPUS_BASE_TEXT = |
| "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt " |
| + "ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation " |
| + "ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in " |
| + "reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. " |
| + "Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt " |
| + "mollit anim id est laborum."; |
| |
| /** |
| * Implementation of the lazy-holder idiom to hold and return the corpus. |
| */ |
| private static final class CorpusHolder { |
| private static final byte[] CORPUS_INSTANCE = generateCorpus(); |
| } |
| |
| /** |
| * Manufacture a well-known corpus. |
| * @return the corpus |
| */ |
| private static final byte[] generateCorpus() { |
| ByteArrayOutputStream buffer = new ByteArrayOutputStream(); |
| final byte[] loremIpsumBytes; |
| try { |
| loremIpsumBytes = CORPUS_BASE_TEXT.getBytes("US-ASCII"); |
| } catch (UnsupportedEncodingException e) { |
| throw new RuntimeException("System doesn't support ASCII", e); |
| } |
| // This is sufficient to create different results for all 9 compression |
| // levels of the default strategy by exercising the hash chaining |
| // longest-match logic in zlib. The data totals about 9k. |
| for (int x = 0; x < 135; x++) { |
| buffer.write(loremIpsumBytes, 0, x); |
| } |
| return buffer.toByteArray(); |
| } |
| |
| /** |
| * Returns a corpus of data that produces a different compressed output for each configuration of |
| * {@link java.util.zip.Deflater} that is defined. Comparing the SHA-256 of the compression output |
| * to the well-known baseline from {@link #getBaselineValues()} indicates whether or not the |
| * runtime is compatible with this window. |
| * <p> |
| * Some configurations of deflate will produce identical output. This is because there is some |
| * overlap between (e.g., maximum match length) for some combinations of parameters. Most notably, |
| * there is no concept of compression "level" with the {@link Deflater#HUFFMAN_ONLY} strategy. |
| * @return an independent copy of the corpus, as an array of bytes |
| */ |
| public byte[] getCorpus() { |
| return CorpusHolder.CORPUS_INSTANCE.clone(); |
| } |
| |
| /** |
| * Convert the specified bytes to a fixed-length hex string. |
| * @param bytes the bytes to convert |
| * @return a string exactly twice as long as the number of bytes in the |
| * input, representing the bytes as a continuous hexadecimal stream |
| */ |
| private final static String hexString(byte[] bytes) { |
| StringBuilder buffer = new StringBuilder(); |
| for (int x = 0; x < bytes.length; x++) { |
| int value = bytes[x] & 0xff; |
| if (value < 0x10) { |
| buffer.append('0'); |
| } |
| buffer.append(Integer.toHexString(value)); |
| } |
| return buffer.toString(); |
| } |
| |
| /** |
| * Checks for compatibility with the baseline. |
| * @return true if compatible, otherwise false. |
| */ |
| public boolean isCompatible() { |
| return getIncompatibleValues().isEmpty(); |
| } |
| |
| /** |
| * Return a mapping of {@link JreDeflateParameters} to SHA256 of the values for this system that |
| * are incompatible with the baseline, as computed by {@link #getSystemValues()} and |
| * {@link #getBaselineValues()}. If the resulting collection is empty, the system is compatible |
| * with the window; otherwise, the SHA256 values present in the returned collection are the |
| * incompatible values from the system. |
| * @return such a mapping, possibly empty but never null |
| */ |
| public Map<JreDeflateParameters, String> getIncompatibleValues() { |
| Map<JreDeflateParameters, String> incompatible = new HashMap<JreDeflateParameters, String>(); |
| Map<JreDeflateParameters, String> systemValues = getSystemValues(); |
| for (Map.Entry<JreDeflateParameters, String> baselineEntry : getBaselineValues().entrySet()) { |
| String computedSHA256 = systemValues.get(baselineEntry.getKey()); |
| if (!computedSHA256.equals(baselineEntry.getValue())) { |
| incompatible.put(baselineEntry.getKey(), computedSHA256); |
| } |
| } |
| return incompatible; |
| } |
| |
| /** |
| * Using the corpus supplied by {@link #getCorpus()}, computes and returns a mapping of the |
| * SHA256 of the compression output for the {@link java.util.zip.Deflater} for each combination of |
| * settings described in the class-level documentation. |
| * @return the mapping as described |
| */ |
| public Map<JreDeflateParameters, String> getSystemValues() { |
| Map<JreDeflateParameters, String> result = new HashMap<JreDeflateParameters, String>(); |
| MessageDigest digester; |
| try { |
| digester = MessageDigest.getInstance("SHA-256"); |
| } catch (NoSuchAlgorithmException e) { |
| throw new RuntimeException("System doesn't support SHA-256", e); |
| } |
| |
| DeflateCompressor compressor = new DeflateCompressor(); |
| compressor.setCaching(true); // Makes this computation lighter weight. |
| boolean[] nowrapValues = {true, false}; |
| int[] strategies = {Deflater.DEFAULT_STRATEGY, Deflater.FILTERED, Deflater.HUFFMAN_ONLY}; |
| int[] levels = {1, 2, 3, 4, 5, 6, 7, 8, 9}; |
| for (final boolean nowrap : nowrapValues) { |
| compressor.setNowrap(nowrap); |
| for (final int strategy : strategies) { |
| compressor.setStrategy(strategy); |
| final int[] relevantLevels; |
| if (strategy == Deflater.HUFFMAN_ONLY) { |
| // There is no concept of a compression level with this |
| // strategy. |
| relevantLevels = new int[] {1}; |
| } else { |
| relevantLevels = levels; |
| } |
| for (final int level : relevantLevels) { |
| compressor.setCompressionLevel(level); |
| ByteArrayOutputStream buffer = new ByteArrayOutputStream(); |
| try { |
| compressor.compress(new ByteArrayInputStream(CorpusHolder.CORPUS_INSTANCE), buffer); |
| } catch (IOException e) { |
| throw new RuntimeException(e); // This should never occur as it's all in-memory. |
| } |
| byte[] compressedData = buffer.toByteArray(); |
| digester.reset(); |
| byte[] sha256OfCompressedData = digester.digest(compressedData); |
| String sha256String = hexString(sha256OfCompressedData); |
| JreDeflateParameters parameters = JreDeflateParameters.of(level, strategy, nowrap); |
| result.put(parameters, sha256String); |
| } |
| } |
| } |
| compressor.release(); |
| return result; |
| } |
| } |
