1 // Copyright 2016 Google Inc. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //     http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
15 package com.google.archivepatcher.shared;
16 
17 import java.io.ByteArrayInputStream;
18 import java.io.ByteArrayOutputStream;
19 import java.io.IOException;
20 import java.io.UnsupportedEncodingException;
21 import java.security.MessageDigest;
22 import java.security.NoSuchAlgorithmException;
23 import java.util.Collections;
24 import java.util.HashMap;
25 import java.util.Map;
26 import java.util.zip.Deflater;
27 
28 // TODO: Skip the zlib header bytes for fingerprint computation and simply ignore the "wrapped" set
29 // of values completely. This will cut fingerprints by half and fix compatibility issues with older
30 // JVMs caused by this zlib commit that twiddled the level flag assignments in the zlib header
31 // fields: https://github.com/madler/zlib/commit/086e982175da84b3db958191031380794315f95f
32 
33 // TODO: Consider dropping support for both nowrap=false and strategies 1 and 2, since in practice
34 // they are vanishingly rare.
35 
36 // Baseline generated on 2015-11-27 using Oracle's Java Runtime Environment:
37 // Java(TM) SE Runtime Environment (build 1.8.0_66-b18)
38 // Java HotSpot(TM) 64-Bit Server VM (build 25.66-b18, mixed mode)
39 
40 /**
41  * Defines the default deflate compatibility window. This window determines compatibility with
42  * {@link java.util.zip.Deflater} with all relevant combinations of the following settings:
43  * <ul>
44  *   <li>Strategies 0, 1 and 2</li>
45  *   <li>Levels 1, 2, 3, 4, 5, 6, 7, 8 and 9</li>
46  *   <li>Wrapping on (nowrap=false) and off (nowrap=true)</li>
47  * </ul>
48  * Strategy 2, {@link java.util.zip.Deflater#HUFFMAN_ONLY}, does not utilize compression levels.
49  * For querying strategy 2, always use level 1 for the lookup.
50  * There are thus a total of <strong>38</strong> configurations:
51  * <ul>
52  *   <li>18 configurations for strategy 0 {@link java.util.zip.Deflater#DEFAULT_STRATEGY}:
53  *       compression levels 1 through 9, with wrapping on and off;</li>
54  *   <li>18 configurations for strategy 1 {@link java.util.zip.Deflater#FILTERED}:
55  *       compression levels 1 through 9, with wrapping on and off;</li>
56  *   <li>2 configurations for strategy 2 {@link java.util.zip.Deflater#HUFFMAN_ONLY}:
57  *       compression level 1 (arbitrarily chosen), with wrapping on and off.
58  * </ul>
59  * The following is a non-exhaustive list of platforms that are known to be compatible:
60  * <ul>
61  * <li>Sun/Oracle JRE version 1.6.0 or later on x86 and x86_64</li>
62  * <li>Android version 4.0 or later (Ice Cream Sandwich / API 15) on x86, arm32 and arm64</li>
63  * </ul>
64  * The minimum known-compatible version of zlib is 1.2.0.4
65  * (https://github.com/madler/zlib/commit/086e982175da84b3db958191031380794315f95f).
66  */
67 public class DefaultDeflateCompatibilityWindow {
68   /**
69    * Implementation of the lazy-holder idiom to hold and return the baseline.
70    */
71   private static final class BaselineHolder {
72     private static final Map<JreDeflateParameters, String> BASELINE_INSTANCE = generateBaseline();
73   }
74 
75   /**
76    * Generates the baseline and returns it.
77    * @return see {@link #getBaselineValues()}
78    */
generateBaseline()79   private static final Map<JreDeflateParameters, String> generateBaseline() {
80     Map<JreDeflateParameters, String> baseline = new HashMap<JreDeflateParameters, String>();
81     baseline.put(
82         JreDeflateParameters.of(1, 0, true),
83         "5e0ae60766a04b0c9ef1f677ae4ba4a83a6bc112ce3761b41b270af08821804e");
84     baseline.put(
85         JreDeflateParameters.of(2, 0, true),
86         "9b392414e62afcc64200cc39955ff75d1254f56c67bf2eb05d62f63b677080fc");
87     baseline.put(
88         JreDeflateParameters.of(3, 0, true),
89         "ce272e7f72232e80b5d00d7333a5bdd6e9d7e34268d49c5fe9bdfedba6fc0d54");
90     baseline.put(
91         JreDeflateParameters.of(4, 0, true),
92         "a8a3b59d42fe257766926d46818422216a043c8c37bb69492d9bab3bd4d6b07a");
93     baseline.put(
94         JreDeflateParameters.of(5, 0, true),
95         "49280186dd6683ae92ef25e239d7c0e2b7a4fd0e2b7dfadc8846f5157aa6aed9");
96     baseline.put(
97         JreDeflateParameters.of(6, 0, true),
98         "bec508de691537047e338825828db16308cc8dc93e22386c8eeb0bc14c4c5f45");
99     baseline.put(
100         JreDeflateParameters.of(7, 0, true),
101         "6daf3724aed1f67c7d1f6404166b5dbea1f2fc42192f20813910271bc8c40e75");
102     baseline.put(
103         JreDeflateParameters.of(8, 0, true),
104         "08cd258637bb146d33ef550fc60baaa855902837758d6489802f3b1ece6ea7f1");
105     baseline.put(
106         JreDeflateParameters.of(9, 0, true),
107         "5ea67964bb124b436130dfbbd2e36fb2b08992423be188a8edfbb8550e8bfefb");
108     baseline.put(
109         JreDeflateParameters.of(1, 1, true),
110         "5e0ae60766a04b0c9ef1f677ae4ba4a83a6bc112ce3761b41b270af08821804e");
111     baseline.put(
112         JreDeflateParameters.of(2, 1, true),
113         "9b392414e62afcc64200cc39955ff75d1254f56c67bf2eb05d62f63b677080fc");
114     baseline.put(
115         JreDeflateParameters.of(3, 1, true),
116         "ce272e7f72232e80b5d00d7333a5bdd6e9d7e34268d49c5fe9bdfedba6fc0d54");
117     baseline.put(
118         JreDeflateParameters.of(4, 1, true),
119         "6283bb35a97f4657b6aab0b0a7f218947965f135838926df295037fdca816746");
120     baseline.put(
121         JreDeflateParameters.of(5, 1, true),
122         "42594bbcf7fa83f74cdf35839debaae25e4655070fdf1fc67539de0a90f59afe");
123     baseline.put(
124         JreDeflateParameters.of(6, 1, true),
125         "1db82cae52b0bb88cf3a21cdec183c1dab8074b1d1f4341b9e9b18b1ace5a778");
126     baseline.put(
127         JreDeflateParameters.of(7, 1, true),
128         "5d0d53667944dc447b52e58b0e91e303b5662f92a085ab5a1f4b62eeab8900ef");
129     baseline.put(
130         JreDeflateParameters.of(8, 1, true),
131         "c6cdfbe16b1e530e91fd3ac1dbb2a9b2f5b3ccee5ddf92769ea349fc60fd560e");
132     baseline.put(
133         JreDeflateParameters.of(9, 1, true),
134         "f4e93a15b50c568d39785c12d373104272009bcd71028dbf0faa85441eb5130d");
135     baseline.put(
136         JreDeflateParameters.of(1, 2, true),
137         "2297dbc0a5498c9a7a89519f401936e910ddb82c9b477e7aa407a4c2bf523dbd");
138     baseline.put(
139         JreDeflateParameters.of(1, 0, false),
140         "5e06d9c9280e5b9b4832c0894e2f930f606665169ad2ac093df544e70fac4136");
141     baseline.put(
142         JreDeflateParameters.of(2, 0, false),
143         "f1c2fe9b4189c03a5ae0b1a1db51875d334fb21144e08e9c527644d66ef39797");
144     baseline.put(
145         JreDeflateParameters.of(3, 0, false),
146         "49998ee364d2668eb5a2cadf40feaa78c0c081337141ad15f7fb2a7843c833b8");
147     baseline.put(
148         JreDeflateParameters.of(4, 0, false),
149         "6911a5b04664b00b2bba72d7ba9e1d5a73b390f2cf4b20618580c13a5825fc17");
150     baseline.put(
151         JreDeflateParameters.of(5, 0, false),
152         "417f5fd21438ffb739a681af9a20eed29dd9da63e8a540415b9ec6199495e6db");
153     baseline.put(
154         JreDeflateParameters.of(6, 0, false),
155         "9a4bcc9afd8547784aff6283cafd69f46893d5131bd798fbad92dc52ca946522");
156     baseline.put(
157         JreDeflateParameters.of(7, 0, false),
158         "592ad846a99693b2f1092bac6a3bf2cf5ac562a9b38ebe34c46cbf2ddd3c13aa");
159     baseline.put(
160         JreDeflateParameters.of(8, 0, false),
161         "8d4b91929384dfd7a0dda6b6e0410de7c4c109167047d694cf36b46e68dd8d5f");
162     baseline.put(
163         JreDeflateParameters.of(9, 0, false),
164         "36bacacc32707e6498269a04d2b2cd30990ac4b0717ee4a9e4badbb6ca5fb7ea");
165     baseline.put(
166         JreDeflateParameters.of(1, 1, false),
167         "5e06d9c9280e5b9b4832c0894e2f930f606665169ad2ac093df544e70fac4136");
168     baseline.put(
169         JreDeflateParameters.of(2, 1, false),
170         "f1c2fe9b4189c03a5ae0b1a1db51875d334fb21144e08e9c527644d66ef39797");
171     baseline.put(
172         JreDeflateParameters.of(3, 1, false),
173         "49998ee364d2668eb5a2cadf40feaa78c0c081337141ad15f7fb2a7843c833b8");
174     baseline.put(
175         JreDeflateParameters.of(4, 1, false),
176         "2bd9ae26fe933102ed46ef2bf8e82d62e0104d9d1cce73a8b46df8a238fd32f8");
177     baseline.put(
178         JreDeflateParameters.of(5, 1, false),
179         "6410581a92808f97f695e796c2963cb6e111af1ec7b7e7d155dcb601192dd80a");
180     baseline.put(
181         JreDeflateParameters.of(6, 1, false),
182         "50571149806edb22b7f3a3ba52168644dd99de444e813df7e186817ccc204c01");
183     baseline.put(
184         JreDeflateParameters.of(7, 1, false),
185         "7a41b9549bcc651d3d219e7aaf3f74beefea238caf1560036cd299d62be6531b");
186     baseline.put(
187         JreDeflateParameters.of(8, 1, false),
188         "29da81b218ff50e69819375d2c008a648309dd9a0fc18683d675ce523cff744f");
189     baseline.put(
190         JreDeflateParameters.of(9, 1, false),
191         "4ce8c7903e526e2a36db168c5cf9af0b90155850899ea26ad77d6daaa7b395c3");
192     baseline.put(
193         JreDeflateParameters.of(1, 2, false),
194         "e3cc7200f308fa7756f02bebbf5046e58a4a2a7e8f1c9ea1708b96d4e1033666");
195     return Collections.unmodifiableMap(baseline);
196   }
197 
198   /**
199    * Returns the baseline that this tool expects to find on all compatible systems.
200    *
201    * @return a mapping from {@link JreDeflateParameters} to the corresponding SHA-256 of the result
202    * of compressing the corpus with those parameters. Level 0 is not used, because level 0 means
203    * "store" (and is therefore not compressed).
204    */
getBaselineValues()205   public Map<JreDeflateParameters, String> getBaselineValues() {
206     return BaselineHolder.BASELINE_INSTANCE;
207   }
208 
209   /**
210    * Base of corpus for finger-printing.
211    */
212   private static final String CORPUS_BASE_TEXT =
213       "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt "
214           + "ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation "
215           + "ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in "
216           + "reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. "
217           + "Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt "
218           + "mollit anim id est laborum.";
219 
220   /**
221    * Implementation of the lazy-holder idiom to hold and return the corpus.
222    */
223   private static final class CorpusHolder {
224     private static final byte[] CORPUS_INSTANCE = generateCorpus();
225   }
226 
227   /**
228    * Manufacture a well-known corpus.
229    * @return the corpus
230    */
generateCorpus()231   private static final byte[] generateCorpus() {
232     ByteArrayOutputStream buffer = new ByteArrayOutputStream();
233     final byte[] loremIpsumBytes;
234     try {
235       loremIpsumBytes = CORPUS_BASE_TEXT.getBytes("US-ASCII");
236     } catch (UnsupportedEncodingException e) {
237       throw new RuntimeException("System doesn't support ASCII", e);
238     }
239     // This is sufficient to create different results for all 9 compression
240     // levels of the default strategy by exercising the hash chaining
241     // longest-match logic in zlib. The data totals about 9k.
242     for (int x = 0; x < 135; x++) {
243       buffer.write(loremIpsumBytes, 0, x);
244     }
245     return buffer.toByteArray();
246   }
247 
248   /**
249    * Returns a corpus of data that produces a different compressed output for each configuration of
250    * {@link java.util.zip.Deflater} that is defined. Comparing the SHA-256 of the compression output
251    * to the well-known baseline from {@link #getBaselineValues()} indicates whether or not the
252    * runtime is compatible with this window.
253    * <p>
254    * Some configurations of deflate will produce identical output. This is because there is some
255    * overlap between (e.g., maximum match length) for some combinations of parameters. Most notably,
256    * there is no concept of compression "level" with the {@link Deflater#HUFFMAN_ONLY} strategy.
257    * @return an independent copy of the corpus, as an array of bytes
258    */
getCorpus()259   public byte[] getCorpus() {
260     return CorpusHolder.CORPUS_INSTANCE.clone();
261   }
262 
263   /**
264    * Convert the specified bytes to a fixed-length hex string.
265    * @param bytes the bytes to convert
266    * @return a string exactly twice as long as the number of bytes in the
267    * input, representing the bytes as a continuous hexadecimal stream
268    */
hexString(byte[] bytes)269   private final static String hexString(byte[] bytes) {
270     StringBuilder buffer = new StringBuilder();
271     for (int x = 0; x < bytes.length; x++) {
272       int value = bytes[x] & 0xff;
273       if (value < 0x10) {
274         buffer.append('0');
275       }
276       buffer.append(Integer.toHexString(value));
277     }
278     return buffer.toString();
279   }
280 
281   /**
282    * Checks for compatibility with the baseline.
283    * @return true if compatible, otherwise false.
284    */
isCompatible()285   public boolean isCompatible() {
286     return getIncompatibleValues().isEmpty();
287   }
288 
289   /**
290    * Return a mapping of {@link JreDeflateParameters} to SHA256 of the values for this system that
291    * are incompatible with the baseline, as computed by {@link #getSystemValues()} and
292    * {@link #getBaselineValues()}. If the resulting collection is empty, the system is compatible
293    * with the window; otherwise, the SHA256 values present in the returned collection are the
294    * incompatible values from the system.
295    * @return such a mapping, possibly empty but never null
296    */
getIncompatibleValues()297   public Map<JreDeflateParameters, String> getIncompatibleValues() {
298     Map<JreDeflateParameters, String> incompatible = new HashMap<JreDeflateParameters, String>();
299     Map<JreDeflateParameters, String> systemValues = getSystemValues();
300     for (Map.Entry<JreDeflateParameters, String> baselineEntry : getBaselineValues().entrySet()) {
301       String computedSHA256 = systemValues.get(baselineEntry.getKey());
302       if (!computedSHA256.equals(baselineEntry.getValue())) {
303         incompatible.put(baselineEntry.getKey(), computedSHA256);
304       }
305     }
306     return incompatible;
307   }
308 
309   /**
310    * Using the corpus supplied by {@link #getCorpus()}, computes and returns a mapping of the
311    * SHA256 of the compression output for the {@link java.util.zip.Deflater} for each combination of
312    * settings described in the class-level documentation.
313    * @return the mapping as described
314    */
getSystemValues()315   public Map<JreDeflateParameters, String> getSystemValues() {
316     Map<JreDeflateParameters, String> result = new HashMap<JreDeflateParameters, String>();
317     MessageDigest digester;
318     try {
319       digester = MessageDigest.getInstance("SHA-256");
320     } catch (NoSuchAlgorithmException e) {
321       throw new RuntimeException("System doesn't support SHA-256", e);
322     }
323 
324     DeflateCompressor compressor = new DeflateCompressor();
325     compressor.setCaching(true);  // Makes this computation lighter weight.
326     boolean[] nowrapValues = {true, false};
327     int[] strategies = {Deflater.DEFAULT_STRATEGY, Deflater.FILTERED, Deflater.HUFFMAN_ONLY};
328     int[] levels = {1, 2, 3, 4, 5, 6, 7, 8, 9};
329     for (final boolean nowrap : nowrapValues) {
330       compressor.setNowrap(nowrap);
331       for (final int strategy : strategies) {
332         compressor.setStrategy(strategy);
333         final int[] relevantLevels;
334         if (strategy == Deflater.HUFFMAN_ONLY) {
335           // There is no concept of a compression level with this
336           // strategy.
337           relevantLevels = new int[] {1};
338         } else {
339           relevantLevels = levels;
340         }
341         for (final int level : relevantLevels) {
342           compressor.setCompressionLevel(level);
343           ByteArrayOutputStream buffer = new ByteArrayOutputStream();
344           try {
345             compressor.compress(new ByteArrayInputStream(CorpusHolder.CORPUS_INSTANCE), buffer);
346           } catch (IOException e) {
347             throw new RuntimeException(e); // This should never occur as it's all in-memory.
348           }
349           byte[] compressedData = buffer.toByteArray();
350           digester.reset();
351           byte[] sha256OfCompressedData = digester.digest(compressedData);
352           String sha256String = hexString(sha256OfCompressedData);
353           JreDeflateParameters parameters = JreDeflateParameters.of(level, strategy, nowrap);
354           result.put(parameters, sha256String);
355         }
356       }
357     }
358     compressor.release();
359     return result;
360   }
361 }
362