xz/LZMA2 compression for goobsdiff/goobspatch.

BUG=47199
TEST=none
Review URL: http://codereview.chromium.org/2805024

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@50527 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 290 insertions, 43 deletions

diff --git a/chrome/installer/mac/dmgdiffer.sh b/chrome/installer/mac/dmgdiffer.sh
index 0ba0dec..aa47e28 100755
--- a/chrome/installer/mac/dmgdiffer.sh
+++ b/chrome/installer/mac/dmgdiffer.sh
@@ -237,8 +237,9 @@ make_patch_fs() {
 
   if ! cp -p "${SCRIPT_DIR}/dirpatcher.sh" \
              "${SCRIPT_DIR}/goobspatch" \
+             "${SCRIPT_DIR}/liblzma_decompress.dylib" \
              "${patch_dotpatch_dir}/"; then
-    err "could not copy dirpatcher.sh and goobspatch"
+    err "could not copy patching tools"
     exit 13
   fi
 
diff --git a/chrome/installer/mac/third_party/bsdiff/README.chromium b/chrome/installer/mac/third_party/bsdiff/README.chromium
index edee853..ea79013 100644
--- a/chrome/installer/mac/third_party/bsdiff/README.chromium
+++ b/chrome/installer/mac/third_party/bsdiff/README.chromium
@@ -41,9 +41,10 @@ Local Modifications:
    blocks in the patch file, and added patch file length validation to the
    patcher.
  - Replaced custom off_t encoding with signed 64-bit little-endian integers.
- - The control, diff, and extra blocks can be compressed with bzip2 or gzip,
-   or left uncompressed, independently of one another, depending on which is
-   smallest. This often results in a net reduction in patch size of about 3%.
+ - The control, diff, and extra blocks can be compressed with bzip2, gzip, or
+   xz/lzma2, or left uncompressed, independently of one another, depending on
+   which is smallest. This often results in a net reduction in patch size of
+   about 3%-5%.
  - Error messages in the patcher are slightly more descriptive.
  - The patcher treats a few more unexpected read cases as errors than it did
    previously. This will theoretically cause it to exit with an error instead
diff --git a/chrome/installer/mac/third_party/bsdiff/goobsdiff.c b/chrome/installer/mac/third_party/bsdiff/goobsdiff.c
index 8d41ec3..d723a03 100644
--- a/chrome/installer/mac/third_party/bsdiff/goobsdiff.c
+++ b/chrome/installer/mac/third_party/bsdiff/goobsdiff.c
@@ -33,6 +33,7 @@ __FBSDID("$FreeBSD: src/usr.bin/bsdiff/bsdiff/bsdiff.c,v 1.1 2005/08/06 01:59:05
 #include <bzlib.h>
 #include <err.h>
 #include <fcntl.h>
+#include <lzma.h>
 #include <openssl/sha.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -235,26 +236,29 @@ static int compress2gzip(Bytef *dest, uLongf *destLen,
 
 /* Recompress buf of size buf_len using bzip2 or gzip. The smallest version is
  * used. The original uncompressed variant may be the smallest. Returns a
- * number identifying the encoding, 1 for uncompressed, 2 for bzip2, and 3 for
- * gzip. If the original uncompressed variant is not smallest, it is freed.
- * The caller must free any buf after this function returns. */
+ * number identifying the encoding, 1 for uncompressed, 2 for bzip2, 3 for
+ * gzip, and 4 for xz/lzma2. If the original uncompressed variant is not
+ * smallest, it is freed. The caller must free any buf after this function
+ * returns. */
 static char make_small(u_char **buf, off_t *buf_len)
 {
 	u_char *source = *buf;
 	off_t source_len = *buf_len;
-	u_char *bz2, *gz;
+	u_char *bz2, *gz, *lzma;
 	unsigned int bz2_len;
-	unsigned long gz_len;
-	int zerr;
+	size_t gz_len, lzma_len, lzma_pos;
+	int bz2_err, gz_err;
+	lzma_ret lzma_err;
+	lzma_check lzma_ck;
 	char smallest;
 
 	smallest = 1;
 
 	bz2_len = source_len + 1;
 	bz2 = malloc(bz2_len);
-	zerr = BZ2_bzBuffToBuffCompress((char*)bz2, &bz2_len, (char*)source,
-	                                source_len, 9, 0, 0);
-	if (zerr == BZ_OK) {
+	bz2_err = BZ2_bzBuffToBuffCompress((char*)bz2, &bz2_len, (char*)source,
+	                                   source_len, 9, 0, 0);
+	if (bz2_err == BZ_OK) {
 		if (bz2_len < *buf_len) {
 			smallest = 2;
 			*buf = bz2;
@@ -263,17 +267,17 @@ static char make_small(u_char **buf, off_t *buf_len)
 			free(bz2);
 			bz2 = NULL;
 		}
-	} else if (zerr == BZ_OUTBUFF_FULL) {
+	} else if (bz2_err == BZ_OUTBUFF_FULL) {
 		free(bz2);
 		bz2 = NULL;
 	} else {
-		errx(1, "BZ2_bzBuffToBuffCompress: %d", zerr);
+		errx(1, "BZ2_bzBuffToBuffCompress: %d", bz2_err);
 	}
 
 	gz_len = source_len + 1;
 	gz = malloc(gz_len);
-	zerr = compress2gzip(gz, &gz_len, source, source_len, 9);
-	if (zerr == Z_OK) {
+	gz_err = compress2gzip(gz, &gz_len, source, source_len, 9);
+	if (gz_err == Z_OK) {
 		if (gz_len < *buf_len) {
 			smallest = 3;
 			*buf = gz;
@@ -282,11 +286,39 @@ static char make_small(u_char **buf, off_t *buf_len)
 			free(gz);
 			gz = NULL;
 		}
-	} else if (zerr == Z_BUF_ERROR) {
+	} else if (gz_err == Z_BUF_ERROR) {
 		free(gz);
 		gz = NULL;
 	} else {
-		errx(1, "compress2gzip: %d", zerr);
+		errx(1, "compress2gzip: %d", gz_err);
+	}
+
+	lzma_len = source_len + 1;
+	lzma = malloc(lzma_len);
+	lzma_pos = 0;
+
+	/* Equivalent to the options used by xz -9 -e. */
+	lzma_ck = LZMA_CHECK_CRC64;
+	if (!lzma_check_is_supported(lzma_ck))
+		lzma_ck = LZMA_CHECK_CRC32;
+	lzma_err = lzma_easy_buffer_encode(9 | LZMA_PRESET_EXTREME,
+	                                   lzma_ck, NULL,
+	                                   source, source_len,
+	                                   lzma, &lzma_pos, lzma_len);
+	if (lzma_err == LZMA_OK) {
+		if (lzma_pos < *buf_len) {
+			smallest = 4;
+			*buf = lzma;
+			*buf_len = lzma_pos;
+		} else {
+			free(lzma);
+			lzma = NULL;
+		}
+	} else if (lzma_err == LZMA_BUF_ERROR) {
+		free(lzma);
+		lzma = NULL;
+	} else {
+		errx(1, "lzma_easy_buffer_encode: %d", lzma_err);
 	}
 
 	if (smallest != 1) {
@@ -367,7 +399,9 @@ int main(int argc,char *argv[])
 		96	x	compressed control block
 		96+x	y	compressed diff block
 		96+x+y	z	compressed extra block
-	Encodings are 1 (uncompressed), 2 (bzip2), and 3 (gzip). */
+	Encodings are 1 (uncompressed), 2 (bzip2), 3 (gzip), and 4 (xz/lzma2).
+	*/
+
 	memset(header, 0, sizeof(header));
 	if (fwrite(header, sizeof(header), 1, pf) != 1)
 		err(1, "fwrite(%s)", argv[3]);
diff --git a/chrome/installer/mac/third_party/bsdiff/goobsdiff.gyp b/chrome/installer/mac/third_party/bsdiff/goobsdiff.gyp
index 7fe95f8..2fd0c0b 100644
--- a/chrome/installer/mac/third_party/bsdiff/goobsdiff.gyp
+++ b/chrome/installer/mac/third_party/bsdiff/goobsdiff.gyp
@@ -16,12 +16,18 @@
   'targets': [
     {
       'target_name': 'goobsdiff',
+      'dependencies': [
+        '../xz/xz.gyp:lzma',
+      ],
       'sources': [
         'goobsdiff.c',
       ],
     },
     {
       'target_name': 'goobspatch',
+      'dependencies': [
+        '../xz/xz.gyp:lzma_decompress',
+      ],
       'sources': [
         'goobspatch.c',
       ],
diff --git a/chrome/installer/mac/third_party/bsdiff/goobspatch.c b/chrome/installer/mac/third_party/bsdiff/goobspatch.c
index e519f17..385b081 100644
--- a/chrome/installer/mac/third_party/bsdiff/goobspatch.c
+++ b/chrome/installer/mac/third_party/bsdiff/goobspatch.c
@@ -33,6 +33,7 @@ __FBSDID("$FreeBSD: src/usr.bin/bsdiff/bspatch/bspatch.c,v 1.1 2005/08/06 01:59:
 #include <bzlib.h>
 #include <err.h>
 #include <fcntl.h>
+#include <lzma.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
@@ -63,6 +64,186 @@ static void sha1tostr(const u_char *sha1, char *sha1str)
 		sprintf(&sha1str[i * 2], "%02x", sha1[i]);
 }
 
+/* xzfile is a provisional stdio-like interface to xz/lzma2-compressed data.
+ * liblzma does not currently include this functionality. The interface is
+ * read-only and only supports sequential access. */
+
+typedef struct {
+	lzma_stream ls;
+	FILE *f;
+
+	/* in and out are the underlying buffers to be used with lzma_stream. */
+	u_char *in;
+	u_char *out;
+
+	/* read_out points to the first byte in out not yet consumed by an
+	 * xzread call. read_out_len tracks the amount of data available in
+	 * out beginning at read_out. */
+	u_char *read_out;
+	size_t read_out_len;
+
+	/* Error and end-of-file indicators. */
+	lzma_ret err;
+	int eof;
+} xzfile;
+
+/* Initializes and returns a new xzfile pointer that will read from f. On
+ * failure, returns NULL. If err is non-NULL, it will be set to indicate any
+ * error that may have occurred. */
+static xzfile *xzdopen(FILE *f, lzma_ret *err)
+{
+	xzfile *xzf;
+	lzma_stream ls = LZMA_STREAM_INIT;
+	uint64_t physmem, memlimit;
+
+	if (!(xzf = malloc(sizeof(xzfile)))) {
+		if (err) *err = LZMA_MEM_ERROR;
+		return NULL;
+	}
+
+	xzf->ls = ls;
+	xzf->f = f;
+
+	xzf->in = NULL;
+	xzf->out = NULL;
+	if (!(xzf->in = malloc(BUFSIZ)) || !(xzf->out = malloc(BUFSIZ))) {
+		if (err) *err = LZMA_MEM_ERROR;
+		free(xzf->out);
+		free(xzf->in);
+		free(xzf);
+		return NULL;
+	}
+
+	xzf->read_out = xzf->out;
+	xzf->read_out_len = 0;
+
+	xzf->err = LZMA_OK;
+	xzf->eof = 0;
+
+	/* Use the same memory limits used by xzdec and xz. Use 40% of
+	 * physical memory if 80MB or more, otherwise use 80% of physical
+	 * memory if 80MB or less, otherwise use 80MB. If physical memory
+	 * can't be determined, use 128MB. These limits should be sufficient
+	 * for any decompression on any general-purpose system. */
+	physmem = lzma_physmem();
+	if (physmem == 0)
+		physmem = 128 * 1024 * 1024;
+	memlimit = 40 * physmem / 100;
+	if (memlimit < 80 * 1024 * 1024) {
+		memlimit = 80 * physmem / 100;
+		if (memlimit > 80 * 1024 * 1024)
+			memlimit = 80 * 1024 * 1024;
+	}
+
+	xzf->err = lzma_stream_decoder(&xzf->ls, memlimit,
+	                               LZMA_TELL_NO_CHECK |
+	                                   LZMA_TELL_UNSUPPORTED_CHECK);
+	if (xzf->err != LZMA_OK) {
+		if (err) *err = xzf->err;
+		free(xzf->out);
+		free(xzf->in);
+		free(xzf);
+		return NULL;
+	}
+
+	if (err) *err = xzf->err;
+	return xzf;
+}
+
+/* Closes an xzfile opened by xzopen, freeing all memory and closing all
+ * files. Returns LZMA_OK normally, or LZMA_STREAM_END if fclose fails. */
+static lzma_ret xzclose(xzfile *xzf)
+{
+	lzma_ret lzma_err = LZMA_OK;
+
+	lzma_end(&xzf->ls);
+	if (fclose(xzf->f) != 0)
+		lzma_err = LZMA_STREAM_END;
+	free(xzf->out);
+	free(xzf->in);
+	free(xzf);
+
+	return lzma_err;
+}
+
+/* Reads len uncompressed bytes from xzf into buf. Returns the number of bytes
+ * read, which may be less than len at the end of the file. Upon error, if
+ * err is non-NULL, it will be set to an appropriate value, which will either
+ * be a return value from lzma_code (with the exception of LZMA_STREAM_END,
+ * which is remapped to LZMA_OK), or LZMA_STREAM_END to indicate an I/O error.
+ */
+static size_t xzread(xzfile *xzf, u_char *buf, size_t len, lzma_ret *err)
+{
+	lzma_action action = LZMA_RUN;
+	size_t copylen;
+	size_t nread = 0;
+
+	while (xzf->err == LZMA_OK && len > 0) {
+		if (xzf->read_out_len == 0) {
+			/* No unconsumed data is available, need to run
+			 * lzma_code to decompress. */
+			if (xzf->ls.avail_in == 0 && !xzf->eof) {
+				/* No input data available, need to read. */
+				xzf->ls.next_in = xzf->in;
+				xzf->ls.avail_in = fread(xzf->in, 1, BUFSIZ,
+				                         xzf->f);
+				if (ferror(xzf->f)) {
+					/* Map I/O errors to LZMA_STREAM_END. */
+					xzf->err = LZMA_STREAM_END;
+					if (err) *err = xzf->err;
+					return 0;
+				} else if (feof(xzf->f)) {
+					xzf->eof = 1;
+					/* LZMA_FINISH is not critical because
+					 * LZMA_CONCATENATED is not in use. */
+					action = LZMA_FINISH;
+				}
+			}
+
+			/* Use the full output buffer. */
+			xzf->ls.next_out = xzf->out;
+			xzf->ls.avail_out = BUFSIZ;
+
+			/* There must be something to decode. */
+			if (xzf->ls.avail_in == 0) {
+				xzf->err = LZMA_BUF_ERROR;
+				if (err) *err = xzf->err;
+				return 0;
+			}
+
+			/* Run the decoder. */
+			xzf->err = lzma_code(&xzf->ls, action);
+			if (xzf->err == LZMA_STREAM_END) {
+				xzf->eof = 1;
+				xzf->err = LZMA_OK;
+			} else if (xzf->err != LZMA_OK) {
+				if (err) *err = xzf->err;
+				return 0;
+			}
+
+			/* Everything that was decoded is now available for
+			 * reading into buf. */
+			xzf->read_out = xzf->out;
+			xzf->read_out_len = BUFSIZ - xzf->ls.avail_out;
+		}
+
+		/* Copy everything available up to len, and push some
+		 * pointers. */
+		copylen = xzf->read_out_len;
+		if (copylen > len)
+			copylen = len;
+		memcpy(buf, xzf->read_out, copylen);
+		nread += copylen;
+		buf += copylen;
+		len -= copylen;
+		xzf->read_out += copylen;
+		xzf->read_out_len -= copylen;
+	}
+
+	if (err) *err = xzf->err;
+	return nread;
+}
+
 /* cfile is a uniform interface to read from maybe-compressed files. */
 
 typedef struct {
@@ -70,6 +251,7 @@ typedef struct {
 	union {
 		BZFILE *bz2;  /* method = 2 */
 		gzFile gz;    /* method = 3 */
+		xzfile *xz;   /* method = 4 */
 	} u;
 	const char *tag;
 	unsigned char method;
@@ -77,25 +259,34 @@ typedef struct {
 
 /* Opens a file at path, seeks to offset off, and prepares for reading using
  * the specified method. Supported methods are plain uncompressed (1), bzip2
- * (2), and gzip (3). tag is used as an identifier for error reporting. */
+ * (2), gzip (3), and xz/lzma2 (4). tag is used as an identifier for error
+ * reporting. */
 static void cfopen(cfile *cf, const char *path, off_t off,
                    const char *tag, unsigned char method)
 {
 	int fd;
-	int zerr;
+	int bz2_err, gz_err;
+	lzma_ret lzma_err;
 
-	if (method == 1 || method == 2) {
+	if (method == 1 || method == 2 || method == 4) {
 		/* Use stdio for uncompressed files. The bzip interface also
 		 * sits on top of a stdio FILE* but does not take "ownership"
-		 * of the FILE*. */
+		 * of the FILE*. The xz/lzma2 interface sits on top of a FILE*
+		 * and does take ownership of the FILE*. */
 		if ((cf->f = fopen(path, "rb")) == NULL)
 			err(1, "fdopen(%s)", tag);
 		if ((fseeko(cf->f, off, SEEK_SET)) != 0)
 			err(1, "fseeko(%s, %lld)", tag, off);
 		if (method == 2) {
-			if ((cf->u.bz2 = BZ2_bzReadOpen(&zerr, cf->f, 0, 0,
+			if ((cf->u.bz2 = BZ2_bzReadOpen(&bz2_err, cf->f, 0, 0,
 			                                NULL, 0)) == NULL)
-				errx(1, "BZ2_bzReadOpen(%s): %d", tag, zerr);
+				errx(1, "BZ2_bzReadOpen(%s): %d", tag, bz2_err);
+		} else if (method == 4) {
+			if ((cf->u.xz = xzdopen(cf->f, &lzma_err)) == NULL)
+				errx(1, "xzdopen(%s): %d", tag, lzma_err);
+			/* cf->f belongs to the xzfile now, don't access it
+			 * from here. */
+			cf->f = NULL;
 		}
 	} else if (method == 3) {
 		if ((fd = open(path, O_RDONLY)) < 0)
@@ -114,21 +305,25 @@ static void cfopen(cfile *cf, const char *path, off_t off,
 
 static void cfclose(cfile *cf)
 {
-	int zerr;
+	int bz2_err, gz_err;
+	lzma_ret lzma_err;
 
 	if (cf->method == 1 || cf->method == 2) {
 		if (cf->method == 2) {
-			zerr = BZ_OK;
-			BZ2_bzReadClose(&zerr, cf->u.bz2);
-			if (zerr != BZ_OK)
+			bz2_err = BZ_OK;
+			BZ2_bzReadClose(&bz2_err, cf->u.bz2);
+			if (bz2_err != BZ_OK)
 				errx(1, "BZ2_bzReadClose(%s): %d\n",
-				     cf->tag, zerr);
+				     cf->tag, bz2_err);
 		}
 		if (fclose(cf->f) != 0)
 			err(1, "fclose(%s)", cf->tag);
 	} else if (cf->method == 3) {
-		if ((zerr = gzclose(cf->u.gz)) != Z_OK)
-			errx(1, "gzclose(%s): %d", cf->tag, zerr);
+		if ((gz_err = gzclose(cf->u.gz)) != Z_OK)
+			errx(1, "gzclose(%s): %d", cf->tag, gz_err);
+	} else if (cf->method == 4) {
+		if ((lzma_err = xzclose(cf->u.xz)) != LZMA_OK)
+			errx(1, "xzclose(%s): %d", cf->tag, lzma_err);
 	} else {
 		errx(1, "cfclose(%s): unknown method %d", cf->tag, cf->method);
 	}
@@ -137,7 +332,8 @@ static void cfclose(cfile *cf)
 static void cfread(cfile *cf, u_char *buf, size_t len)
 {
 	size_t nread;
-	int zerr;
+	int bz2_err, gz_err;
+	lzma_ret lzma_err;
 
 	if (cf->method == 1) {
 		if ((nread = fread(buf, 1, len, cf->f)) != len) {
@@ -147,21 +343,30 @@ static void cfread(cfile *cf, u_char *buf, size_t len)
 			err(1, "fread(%s, %zd)", cf->tag, len);
 		}
 	} else if (cf->method == 2) {
-		zerr = BZ_OK;
-		if ((nread = BZ2_bzRead(&zerr, cf->u.bz2, buf, len)) != len) {
-			if (zerr == BZ_OK)
+		bz2_err = BZ_OK;
+		if ((nread = BZ2_bzRead(&bz2_err, cf->u.bz2, buf, len)) !=
+		    len) {
+			if (bz2_err == BZ_OK)
 				errx(1, "BZ2_bzRead(%s, %zd): short read %zd",
 				     cf->tag, len, nread);
-			errx(1, "BZ2_bzRead(%s, %zd): %d", cf->tag, len, zerr);
+			errx(1, "BZ2_bzRead(%s, %zd): %d",
+			     cf->tag, len, bz2_err);
 		}
 	} else if (cf->method == 3) {
 		if ((nread = gzread(cf->u.gz, buf, len)) != len) {
-			zerr = Z_OK;
-			gzerror(cf->u.gz, &zerr);
-			if (zerr == Z_OK)
+			gz_err = Z_OK;
+			gzerror(cf->u.gz, &gz_err);
+			if (gz_err == Z_OK)
 				errx(1, "gzread(%s, %zd): short read %zd",
 				     cf->tag, len, nread);
-			errx(1, "gzread(%s, %zd): %d", cf->tag, len, zerr);
+			errx(1, "gzread(%s, %zd): %d", cf->tag, len, gz_err);
+		}
+	} else if (cf->method == 4) {
+		if ((nread = xzread(cf->u.xz, buf, len, &lzma_err)) != len) {
+			if (lzma_err == LZMA_OK)
+				errx(1, "xzread(%s, %zd): short read %zd",
+				     cf->tag, len, nread);
+			errx(1, "xzread(%s, %zd): %d", cf->tag, len, lzma_err);
 		}
 	} else {
 		errx(1, "cfread(%s, %zd): unknown method %d",
@@ -208,7 +413,7 @@ int main(int argc,char * argv[])
 		96	x	compressed control block
 		96+x	y	compressed diff block
 		96+x+y	z	compressed extra block
-	Encodings are 1 (uncompressed), 2 (bzip2), and 3 (gzip).
+	Encodings are 1 (uncompressed), 2 (bzip2), 3 (gzip), and 4 (xz/lzma2).
 	The control block is a set of triples (x,y,z) meaning "add x bytes
 	from oldfile to x bytes from the diff block; copy y bytes from the
 	extra block; seek forwards in oldfile by z bytes".