applier/bsdiff/BsPatch.java

// 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.applier.bsdiff;

import com.google.archivepatcher.applier.PatchFormatException;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.RandomAccessFile;

/**
 * A Java implementation of the "bspatch" algorithm based on the BSD-2 licensed source code
 * available here: https://github.com/mendsley/bsdiff. This implementation supports a maximum file
 * size of 2GB for all binaries involved (old, new and patch binaries).
 */
public class BsPatch {
  /**
   * Standard header found at the start of every patch.
   */
  private static final String SIGNATURE = "ENDSLEY/BSDIFF43";

  /**
   * Default buffer size is 50 kibibytes, a reasonable tradeoff between size and speed.
   */
  private static final int PATCH_BUFFER_SIZE = 1024 * 50;

  /**
   * Masks the upper bit of a long, used to determine if a long is positive or negative.
   */
  private static final long NEGATIVE_LONG_SIGN_MASK = 1L << 63;

  /**
   * The patch is typically compressed and the input stream is decompressing on-the-fly. A small
   * buffer greatly improves efficiency on complicated patches with lots of short directives.
   */
  private static final int PATCH_STREAM_BUFFER_SIZE = 4 * 1024;

  /**
   * Complicated patches with lots of short directives result in many calls to write small amounts
   * of data. A buffer greatly improves efficiency for these patches.
   */
  private static final int OUTPUT_STREAM_BUFFER_SIZE = 16 * 1024;

  /**
   * Applies a patch from |patchData| to the data in |oldData|, writing the result to |newData|.
   *
   * @param oldData data to which the patch should be applied
   * @param newData stream to write the new artifact to
   * @param patchData stream to read patch instructions from
   * @throws PatchFormatException if the patch stream is invalid
   * @throws IOException if unable to read or write any of the data
   */
  public static void applyPatch(
      RandomAccessFile oldData, OutputStream newData, InputStream patchData)
      throws PatchFormatException, IOException {
    patchData = new BufferedInputStream(patchData, PATCH_STREAM_BUFFER_SIZE);
    newData = new BufferedOutputStream(newData, OUTPUT_STREAM_BUFFER_SIZE);
    try {
      applyPatchInternal(oldData, newData, patchData);
    } finally {
      newData.flush();
    }
  }

  /**
   * Does the work of the public applyPatch method.
   */
  private static void applyPatchInternal(
      final RandomAccessFile oldData,
      final OutputStream newData,
      final InputStream patchData)
      throws PatchFormatException, IOException {
    final byte[] signatureBuffer = new byte[SIGNATURE.length()];
    try {
      readFully(patchData, signatureBuffer, 0, signatureBuffer.length);
    } catch (IOException e) {
      throw new PatchFormatException("truncated signature");
    }

    String signature = new String(signatureBuffer, 0, signatureBuffer.length, "US-ASCII");
    if (!SIGNATURE.equals(signature)) {
      throw new PatchFormatException("bad signature");
    }

    // Sanity-check: ensure a-priori knowledge matches patch expectations
    final long oldSize = oldData.length();
    if (oldSize > Integer.MAX_VALUE) {
      throw new PatchFormatException("bad oldSize");
    }
    final long newSize = readBsdiffLong(patchData);
    if (newSize < 0 || newSize > Integer.MAX_VALUE) {
      throw new PatchFormatException("bad newSize");
    }

    // These buffers are used for performing transformations and copies. They are not stateful.
    final byte[] buffer1 = new byte[PATCH_BUFFER_SIZE];
    final byte[] buffer2 = new byte[PATCH_BUFFER_SIZE];

    // Offsets into |oldData| and |newData|.
    long oldDataOffset = 0; // strobes |oldData| in order specified by the patch file
    long newDataBytesWritten = 0; // monotonically increases from 0 .. |expectedNewSize|

    while (newDataBytesWritten < newSize) {
      // Read "control data" for the operation. There are three values here:
      // 1. |diffSegmentLength| defines a number of "similar" bytes that can be transformed
      //    from |oldData| to |newData| by applying byte-by-byte addends. The addend bytes are
      //    read from |patchData|. If zero, no "similar" bytes are transformed in this
      //    operation.
      final long diffSegmentLength = readBsdiffLong(patchData);

      // 2. |copySegmentLength| defines a number of identical bytes that can be copied from
      //    |oldData| to |newData|. If zero, no identical bytes are copied in this operation.
      final long copySegmentLength = readBsdiffLong(patchData);

      // 3. |offsetToNextInput| defines a relative offset to the next position in |oldData| to
      //    jump do after the current operation completes. Strangely, this compensates for
      //    |diffSegmentLength| but not for |copySegmentLength|, so |diffSegmentLength| must
      //    be accumulated into |oldDataOffset| while |copySegmentLength| must NOT be.
      final long offsetToNextInput = readBsdiffLong(patchData);

      // Sanity-checks
      if (diffSegmentLength < 0 || diffSegmentLength > Integer.MAX_VALUE) {
        throw new PatchFormatException("bad diffSegmentLength");
      }
      if (copySegmentLength < 0 || copySegmentLength > Integer.MAX_VALUE) {
        throw new PatchFormatException("bad copySegmentLength");
      }
      if (offsetToNextInput < Integer.MIN_VALUE || offsetToNextInput > Integer.MAX_VALUE) {
        throw new PatchFormatException("bad offsetToNextInput");
      }

      final long expectedFinalNewDataBytesWritten =
          newDataBytesWritten + diffSegmentLength + copySegmentLength;
      if (expectedFinalNewDataBytesWritten > newSize) {
        throw new PatchFormatException("expectedFinalNewDataBytesWritten too large");
      }

      final long expectedFinalOldDataOffset = oldDataOffset + diffSegmentLength + offsetToNextInput;
      if (expectedFinalOldDataOffset > oldSize) {
        throw new PatchFormatException("expectedFinalOldDataOffset too large");
      }
      if (expectedFinalOldDataOffset < 0) {
        throw new PatchFormatException("expectedFinalOldDataOffset is negative");
      }

      // At this point everything is known to be sane, and the operations should all succeed.
      oldData.seek(oldDataOffset);
      if (diffSegmentLength > 0) {
        transformBytes((int) diffSegmentLength, patchData, oldData, newData, buffer1, buffer2);
      }
      if (copySegmentLength > 0) {
        pipe(patchData, newData, buffer1, (int) copySegmentLength);
      }
      newDataBytesWritten = expectedFinalNewDataBytesWritten;
      oldDataOffset = expectedFinalOldDataOffset;
    }
  }

  /**
   * Transforms bytes from |oldData| into |newData| by applying byte-for-byte addends from
   * |patchData|. The number of bytes consumed from |oldData| and |patchData|, as well as the
   * number of bytes written to |newData|, is |diffLength|. The contents of the buffers are
   * ignored and overwritten, and no guarantee is made as to their contents when this method
   * returns. This is the core of the bsdiff patching algorithm. |buffer1.length| must equal
   * |buffer2.length|, and |buffer1| and |buffer2| must be distinct objects.
   *
   * @param diffLength the length of the BsDiff entry (how many bytes to read and apply).
   * @param patchData the input stream from the BsDiff patch containing diff bytes. This stream
   *                  must be positioned so that the first byte read is the first addend to be
   *                  applied to the first byte of data to be read from |oldData|.
   * @param oldData the old file, for the diff bytes to be applied to. This input source must be
   *                positioned so that the first byte read is the first byte of data to which the
   *                first byte of addends from |patchData| should be applied.
   * @param newData the stream to write the resulting data to.
   * @param buffer1 temporary buffer to use for data transformation; contents are ignored, may be
   *                overwritten, and are undefined when this method returns.
   * @param buffer2 temporary buffer to use for data transformation; contents are ignored, may be
   *                overwritten, and are undefined when this method returns.
   */
  // Visible for testing only
  static void transformBytes(
      final int diffLength,
      final InputStream patchData,
      final RandomAccessFile oldData,
      final OutputStream newData,
      final byte[] buffer1,
      final byte[] buffer2)
      throws IOException {
    int numBytesLeft = diffLength;
    while (numBytesLeft > 0) {
      final int numBytesThisRound = Math.min(numBytesLeft, buffer1.length);
      oldData.readFully(buffer1, 0, numBytesThisRound);
      readFully(patchData, buffer2, 0, numBytesThisRound);
      for (int i = 0; i < numBytesThisRound; i++) {
        buffer1[i] += buffer2[i];
      }
      newData.write(buffer1, 0, numBytesThisRound);
      numBytesLeft -= numBytesThisRound;
    }
  }

  /**
   * Reads a long value in little-endian, signed-magnitude format (the format used by the C++
   * bsdiff implementation).
   *
   * @param in the stream to read from
   * @return the long value
   * @throws PatchFormatException if the value is negative zero (unsupported)
   * @throws IOException if unable to read all 8 bytes from the stream
   */
  // Visible for testing only
  static final long readBsdiffLong(InputStream in) throws PatchFormatException, IOException {
    long result = 0;
    for (int bitshift = 0; bitshift < 64; bitshift += 8) {
      result |= ((long) in.read()) << bitshift;
    }

    if (result == NEGATIVE_LONG_SIGN_MASK) {
      // "Negative zero", which is valid in signed-magnitude format.
      // NB: No sane patch generator should ever produce such a value.
      throw new PatchFormatException("read negative zero");
    }

    if ((result & NEGATIVE_LONG_SIGN_MASK) != 0) {
      result = -(result & ~NEGATIVE_LONG_SIGN_MASK);
    }

    return result;
  }

  /**
   * Read exactly the specified number of bytes into the specified buffer.
   *
   * @param in the input stream to read from
   * @param destination where to write the bytes to
   * @param startAt the offset at which to start writing bytes in the destination buffer
   * @param numBytes the number of bytes to read
   * @throws IOException if reading from the stream fails
   */
  // Visible for testing only
  static void readFully(
      final InputStream in, final byte[] destination, final int startAt, final int numBytes)
      throws IOException {
    int numRead = 0;
    while (numRead < numBytes) {
      int readNow = in.read(destination, startAt + numRead, numBytes - numRead);
      if (readNow == -1) {
        throw new IOException("truncated input stream");
      }
      numRead += readNow;
    }
  }

  /**
   * Use an intermediate buffer to pipe bytes from an InputStream directly to an OutputStream. The
   * buffer's contents may be destroyed by this operation.
   *
   * @param in the stream to read bytes from.
   * @param out the stream to write bytes to.
   * @param buffer the buffer to use for copying bytes; must have length > 0
   * @param copyLength the number of bytes to copy from the input stream to the output stream
   */
  // Visible for testing only
  static void pipe(
      final InputStream in, final OutputStream out, final byte[] buffer, int copyLength)
      throws IOException {
    while (copyLength > 0) {
      int maxCopy = Math.min(buffer.length, copyLength);
      readFully(in, buffer, 0, maxCopy);
      out.write(buffer, 0, maxCopy);
      copyLength -= maxCopy;
    }
  }
}