getdown/src/getdown/core/src/main/java/com/threerings/getdown/tools/JarDiff.java

   1 //
   2 // Getdown - application installer, patcher and launcher
   3 // Copyright (C) 2004-2018 Getdown authors
   4 // https://github.com/threerings/getdown/blob/master/LICENSE
   5
   6 /*
   7  * @(#)JarDiff.java 1.7 05/11/17
   8  *
   9  * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions are met:
  13  *
  14  * -Redistribution of source code must retain the above copyright notice, this
  15  *  list of conditions and the following disclaimer.
  16  *
  17  * -Redistribution in binary form must reproduce the above copyright notice,
  18  *  this list of conditions and the following disclaimer in the documentation
  19  *  and/or other materials provided with the distribution.
  20  *
  21  * Neither the name of Sun Microsystems, Inc. or the names of contributors may
  22  * be used to endorse or promote products derived from this software without
  23  * specific prior written permission.
  24  *
  25  * This software is provided "AS IS," without a warranty of any kind. ALL
  26  * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING
  27  * ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE
  28  * OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN MIDROSYSTEMS, INC. ("SUN")
  29  * AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE
  30  * AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
  31  * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST
  32  * REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL,
  33  * INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY
  34  * OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE,
  35  * EVEN IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
  36  *
  37  * You acknowledge that this software is not designed, licensed or intended
  38  * for use in the design, construction, operation or maintenance of any
  39  * nuclear facility.
  40  */
  41
  42 package com.threerings.getdown.tools;
  43
  44 import java.io.*;
  45 import java.util.*;
  46 import java.util.jar.*;
  47
  48 import static java.nio.charset.StandardCharsets.UTF_8;
  49
  50 /**
  51  * JarDiff is able to create a jar file containing the delta between two jar files (old and new).
  52  * The delta jar file can then be applied to the old jar file to reconstruct the new jar file.
  53  *
  54  * <p> Refer to the JNLP spec for details on how this is done.
  55  *
  56  * @version 1.13, 06/26/03
  57  */
  58 public class JarDiff implements JarDiffCodes
  59 {
  60     private static final int DEFAULT_READ_SIZE = 2048;
  61     private static byte[] newBytes = new byte[DEFAULT_READ_SIZE];
  62     private static byte[] oldBytes = new byte[DEFAULT_READ_SIZE];
  63
  64     // The JARDiff.java is the stand-alone jardiff.jar tool. Thus, we do not depend on Globals.java
  65     // and other stuff here. Instead, we use an explicit _debug flag.
  66     private static boolean _debug;
  67
  68     /**
  69      * Creates a patch from the two passed in files, writing the result to <code>os</code>.
  70      */
  71     public static void createPatch (String oldPath, String newPath,
  72                                     OutputStream os, boolean minimal) throws IOException
  73     {
  74         try (JarFile2 oldJar = new JarFile2(oldPath);
  75              JarFile2 newJar = new JarFile2(newPath)) {
  76
  77             HashMap<String,String> moved = new HashMap<>();
  78             HashSet<String> implicit = new HashSet<>();
  79             HashSet<String> moveSrc = new HashSet<>();
  80             HashSet<String> newEntries = new HashSet<>();
  81
  82             // FIRST PASS
  83             // Go through the entries in new jar and
  84             // determine which files are candidates for implicit moves
  85             // ( files that has the same filename and same content in old.jar
  86             // and new.jar )
  87             // and for files that cannot be implicitly moved, we will either
  88             // find out whether it is moved or new (modified)
  89             for (JarEntry newEntry : newJar) {
  90                 String newname = newEntry.getName();
  91
  92                 // Return best match of contents, will return a name match if possible
  93                 String oldname = oldJar.getBestMatch(newJar, newEntry);
  94                 if (oldname == null) {
  95                     // New or modified entry
  96                     if (_debug) {
  97                         System.out.println("NEW: "+ newname);
  98                     }
  99                     newEntries.add(newname);
 100                 } else {
 101                     // Content already exist - need to do a move
 102
 103                     // Should do implicit move? Yes, if names are the same, and
 104                     // no move command already exist from oldJar
 105                     if (oldname.equals(newname) && !moveSrc.contains(oldname)) {
 106                         if (_debug) {
 107                             System.out.println(newname + " added to implicit set!");
 108                         }
 109                         implicit.add(newname);
 110                     } else {
 111                         // The 1.0.1/1.0 JarDiffPatcher cannot handle
 112                         // multiple MOVE command with same src.
 113                         // The work around here is if we are going to generate
 114                         // a MOVE command with duplicate src, we will
 115                         // instead add the target as a new file.  This way
 116                         // the jardiff can be applied by 1.0.1/1.0
 117                         // JarDiffPatcher also.
 118                         if (!minimal && (implicit.contains(oldname) ||
 119                                          moveSrc.contains(oldname) )) {
 120
 121                             // generate non-minimal jardiff
 122                             // for backward compatibility
 123
 124                             if (_debug) {
 125
 126                                 System.out.println("NEW: "+ newname);
 127                             }
 128                             newEntries.add(newname);
 129                         } else {
 130                             // Use newname as key, since they are unique
 131                             if (_debug) {
 132                                 System.err.println("moved.put " + newname + " " + oldname);
 133                             }
 134                             moved.put(newname, oldname);
 135                             moveSrc.add(oldname);
 136                         }
 137                         // Check if this disables an implicit 'move <oldname> <oldname>'
 138                         if (implicit.contains(oldname) && minimal) {
 139
 140                             if (_debug) {
 141                                 System.err.println("implicit.remove " + oldname);
 142
 143                                 System.err.println("moved.put " + oldname + " " + oldname);
 144
 145                             }
 146                             implicit.remove(oldname);
 147                             moved.put(oldname, oldname);
 148                             moveSrc.add(oldname);
 149                         }
 150                     }
 151                 }
 152             }
 153
 154             // SECOND PASS: <deleted files> = <oldjarnames> - <implicitmoves> -
 155             // <source of move commands> - <new or modified entries>
 156             ArrayList<String> deleted = new ArrayList<>();
 157             for (JarEntry oldEntry : oldJar) {
 158                 String oldName = oldEntry.getName();
 159                 if (!implicit.contains(oldName) && !moveSrc.contains(oldName)
 160                     && !newEntries.contains(oldName)) {
 161                     if (_debug) {
 162                         System.err.println("deleted.add " + oldName);
 163                     }
 164                     deleted.add(oldName);
 165                 }
 166             }
 167
 168             //DEBUG
 169             if (_debug) {
 170                 //DEBUG:  print out moved map
 171                 System.out.println("MOVED MAP!!!");
 172                 for (Map.Entry<String,String> entry : moved.entrySet()) {
 173                     System.out.println(entry);
 174                 }
 175
 176                 //DEBUG:  print out IMOVE map
 177                 System.out.println("IMOVE MAP!!!");
 178                 for (String newName : implicit) {
 179                     System.out.println("key is " + newName);
 180                 }
 181             }
 182
 183             JarOutputStream jos = new JarOutputStream(os);
 184
 185             // Write out all the MOVEs and REMOVEs
 186             createIndex(jos, deleted, moved);
 187
 188             // Put in New and Modified entries
 189             for (String newName : newEntries) {
 190                 if (_debug) {
 191                     System.out.println("New File: " + newName);
 192                 }
 193                 writeEntry(jos, newJar.getEntryByName(newName), newJar);
 194             }
 195
 196             jos.finish();
 197 //            jos.close();
 198         }
 199     }
 200
 201     /**
 202      * Writes the index file out to <code>jos</code>.
 203      * <code>oldEntries</code> gives the names of the files that were removed,
 204      * <code>movedMap</code> maps from the new name to the old name.
 205      */
 206     private static void createIndex (JarOutputStream jos, List<String> oldEntries,
 207                                      Map<String,String> movedMap)
 208         throws IOException
 209     {
 210         StringWriter writer = new StringWriter();
 211         writer.write(VERSION_HEADER);
 212         writer.write("\r\n");
 213
 214         // Write out entries that have been removed
 215         for (String name : oldEntries) {
 216             writer.write(REMOVE_COMMAND);
 217             writer.write(" ");
 218             writeEscapedString(writer, name);
 219             writer.write("\r\n");
 220         }
 221
 222         // And those that have moved
 223         for (String newName : movedMap.keySet()) {
 224             String oldName = movedMap.get(newName);
 225             writer.write(MOVE_COMMAND);
 226             writer.write(" ");
 227             writeEscapedString(writer, oldName);
 228             writer.write(" ");
 229             writeEscapedString(writer, newName);
 230             writer.write("\r\n");
 231         }
 232
 233         jos.putNextEntry(new JarEntry(INDEX_NAME));
 234         byte[] bytes = writer.toString().getBytes(UTF_8);
 235         jos.write(bytes, 0, bytes.length);
 236     }
 237
 238     protected static Writer writeEscapedString (Writer writer, String string)
 239         throws IOException
 240     {
 241         int index = 0;
 242         int last = 0;
 243         char[] chars = null;
 244
 245         while ((index = string.indexOf(' ', index)) != -1) {
 246             if (last != index) {
 247                 if (chars == null) {
 248                     chars = string.toCharArray();
 249                 }
 250                 writer.write(chars, last, index - last);
 251             }
 252             last = index;
 253             index++;
 254             writer.write('\\');
 255         }
 256         if (last != 0 && chars != null) {
 257             writer.write(chars, last, chars.length - last);
 258         }
 259         else {
 260             // no spaces
 261             writer.write(string);
 262         }
 263
 264         return writer;
 265     }
 266
 267     private static void writeEntry (JarOutputStream jos, JarEntry entry, JarFile2 file)
 268         throws IOException
 269     {
 270         try (InputStream data = file.getJarFile().getInputStream(entry)) {
 271             jos.putNextEntry(entry);
 272             int size = data.read(newBytes);
 273             while (size != -1) {
 274                 jos.write(newBytes, 0, size);
 275                 size = data.read(newBytes);
 276             }
 277         }
 278     }
 279
 280     /**
 281      * JarFile2 wraps a JarFile providing some convenience methods.
 282      */
 283     private static class JarFile2 implements Iterable<JarEntry>, Closeable
 284     {
 285         private JarFile _jar;
 286         private List<JarEntry> _entries;
 287         private HashMap<String,JarEntry> _nameToEntryMap;
 288         private HashMap<Long,LinkedList<JarEntry>> _crcToEntryMap;
 289
 290         public JarFile2 (String path) throws IOException {
 291             _jar = new JarFile(new File(path));
 292             index();
 293         }
 294
 295         public JarFile getJarFile () {
 296             return _jar;
 297         }
 298
 299         // from interface Iterable<JarEntry>
 300         @Override
 301         public Iterator<JarEntry> iterator () {
 302             return _entries.iterator();
 303         }
 304
 305         public JarEntry getEntryByName (String name) {
 306             return _nameToEntryMap.get(name);
 307         }
 308
 309         /**
 310          * Returns true if the two InputStreams differ.
 311          */
 312         private static boolean differs (InputStream oldIS, InputStream newIS) throws IOException {
 313             int newSize = 0;
 314             int oldSize;
 315             int total = 0;
 316             boolean retVal = false;
 317
 318             while (newSize != -1) {
 319                 newSize = newIS.read(newBytes);
 320                 oldSize = oldIS.read(oldBytes);
 321
 322                 if (newSize != oldSize) {
 323                     if (_debug) {
 324                         System.out.println("\tread sizes differ: " + newSize +
 325                                            " " + oldSize + " total " + total);
 326                     }
 327                     retVal = true;
 328                     break;
 329                 }
 330                 if (newSize > 0) {
 331                     while (--newSize >= 0) {
 332                         total++;
 333                         if (newBytes[newSize] != oldBytes[newSize]) {
 334                             if (_debug) {
 335                                 System.out.println("\tbytes differ at " +
 336                                                    total);
 337                             }
 338                             retVal = true;
 339                             break;
 340                         }
 341                         if ( retVal ) {
 342                             //Jump out
 343                             break;
 344                         }
 345                         newSize = 0;
 346                     }
 347                 }
 348             }
 349
 350             return retVal;
 351         }
 352
 353         public String getBestMatch (JarFile2 file, JarEntry entry) throws IOException {
 354             // check for same name and same content, return name if found
 355             if (contains(file, entry)) {
 356                 return (entry.getName());
 357             }
 358
 359             // return name of same content file or null
 360             return (hasSameContent(file,entry));
 361         }
 362
 363         public boolean contains (JarFile2 f, JarEntry e) throws IOException {
 364
 365             JarEntry thisEntry = getEntryByName(e.getName());
 366
 367             // Look up name in 'this' Jar2File - if not exist return false
 368             if (thisEntry == null)
 369                 return false;
 370
 371             // Check CRC - if no match - return false
 372             if (thisEntry.getCrc() != e.getCrc())
 373                 return false;
 374
 375             // Check contents - if no match - return false
 376             try (InputStream oldIS = getJarFile().getInputStream(thisEntry);
 377                  InputStream newIS = f.getJarFile().getInputStream(e)) {
 378                 return !differs(oldIS, newIS);
 379             }
 380         }
 381
 382         public String hasSameContent (JarFile2 file, JarEntry entry) throws IOException {
 383             String thisName = null;
 384             Long crcL = Long.valueOf(entry.getCrc());
 385             // check if this jar contains files with the passed in entry's crc
 386             if (_crcToEntryMap.containsKey(crcL)) {
 387                 // get the Linked List with files with the crc
 388                 LinkedList<JarEntry> ll = _crcToEntryMap.get(crcL);
 389                 // go through the list and check for content match
 390                 ListIterator<JarEntry> li = ll.listIterator(0);
 391                 while (li.hasNext()) {
 392                     JarEntry thisEntry = li.next();
 393                     // check for content match
 394                     try (InputStream oldIS = getJarFile().getInputStream(thisEntry);
 395                          InputStream newIS = file.getJarFile().getInputStream(entry)) {
 396                         if (!differs(oldIS, newIS)) {
 397                             thisName = thisEntry.getName();
 398                             return thisName;
 399                         }
 400                     }
 401                 }
 402             }
 403             return thisName;
 404         }
 405
 406         private void index () throws IOException {
 407             Enumeration<JarEntry> entries = _jar.entries();
 408
 409             _nameToEntryMap = new HashMap<>();
 410             _crcToEntryMap = new HashMap<>();
 411             _entries = new ArrayList<>();
 412             if (_debug) {
 413                 System.out.println("indexing: " + _jar.getName());
 414             }
 415             if (entries != null) {
 416                 while (entries.hasMoreElements()) {
 417                     JarEntry entry = entries.nextElement();
 418                     long crc = entry.getCrc();
 419                     Long crcL = Long.valueOf(crc);
 420                     if (_debug) {
 421                         System.out.println("\t" + entry.getName() + " CRC " + crc);
 422                     }
 423
 424                     _nameToEntryMap.put(entry.getName(), entry);
 425                     _entries.add(entry);
 426
 427                     // generate the CRC to entries map
 428                     if (_crcToEntryMap.containsKey(crcL)) {
 429                         // key exist, add the entry to the correcponding linked list
 430                         LinkedList<JarEntry> ll = _crcToEntryMap.get(crcL);
 431                         ll.add(entry);
 432                         _crcToEntryMap.put(crcL, ll);
 433
 434                     } else {
 435                         // create a new entry in the hashmap for the new key
 436                         LinkedList<JarEntry> ll = new LinkedList<JarEntry>();
 437                         ll.add(entry);
 438                         _crcToEntryMap.put(crcL, ll);
 439                     }
 440                 }
 441             }
 442         }
 443
 444         @Override
 445         public void close() throws IOException {
 446             _jar.close();
 447         }
 448     }
 449 }