applier/src/main/java/com/google/archivepatcher/applier/bsdiff/BsPatch.java - platform/external/archive-patcher - Git at Google

 // 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;
     }
   }
 }
	// 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;
	}
	}
	}