From 75249edab0b22ea9aae9c7278b9f2c196c7d25d4 Mon Sep 17 00:00:00 2001
From: Ken Sumrall <ksumrall@android.com>
Date: Fri, 13 Aug 2010 16:04:49 -0700
Subject: [PATCH] Add support for sparse ext4 image creation.

This adds the -s option to the make_ext4fs tool, which now creates
"sparse" filesystem images, which is very useful for the large 32 Gbyte
filesystems we are now building.
This check-in also fixes make_ext4fs to properly create filesystems
larger thatn 4 Gbytes on 64-bit Linux, 32-bit android and Macs.

Change-Id: Ie5838492fcf944f5c875481693c0dbd7013deae4
---
 ext4_utils/Android.mk         |   7 ++
 ext4_utils/backed_block.c     |   4 +-
 ext4_utils/ext4_utils.c       |  45 +++++---
 ext4_utils/ext4_utils.h       |   2 +-
 ext4_utils/make_ext4fs.c      |   6 +-
 ext4_utils/make_ext4fs.h      |   2 +-
 ext4_utils/make_ext4fs_main.c |  15 ++-
 ext4_utils/output_file.c      | 248 ++++++++++++++++++++++++++++++++++++++----
 ext4_utils/output_file.h      |   3 +-
 ext4_utils/simg2img.c         | 198 +++++++++++++++++++++++++++++++++
 ext4_utils/sparse_format.h    |  47 ++++++++
 11 files changed, 530 insertions(+), 47 deletions(-)
 create mode 100644 ext4_utils/simg2img.c
 create mode 100644 ext4_utils/sparse_format.h

diff --git a/ext4_utils/Android.mk b/ext4_utils/Android.mk
index 3f8b10ea..14702540 100644
--- a/ext4_utils/Android.mk
+++ b/ext4_utils/Android.mk
@@ -63,6 +63,13 @@ include $(BUILD_HOST_EXECUTABLE)
 
 include $(CLEAR_VARS)
 
+LOCAL_SRC_FILES := simg2img.c
+LOCAL_MODULE := simg2img
+
+include $(BUILD_HOST_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
 LOCAL_MODULE := mkuserimg.sh
 LOCAL_SRC_FILES := mkuserimg.sh
 LOCAL_MODULE_CLASS := EXECUTABLES
diff --git a/ext4_utils/backed_block.c b/ext4_utils/backed_block.c
index 5fa69435..c1a2f202 100644
--- a/ext4_utils/backed_block.c
+++ b/ext4_utils/backed_block.c
@@ -113,9 +113,9 @@ void for_each_data_block(data_block_callback_t data_func,
 		last_block = db->block + DIV_ROUND_UP(db->len, info.block_size) - 1;
 
 		if (db->filename)
-			file_func(out, db->block * info.block_size, db->filename, db->offset, db->len);
+			file_func(out, (u64)db->block * info.block_size, db->filename, db->offset, db->len);
 		else
-			data_func(out, db->block * info.block_size, db->data, db->len);
+			data_func(out, (u64)db->block * info.block_size, db->data, db->len);
 	}
 }
 
diff --git a/ext4_utils/ext4_utils.c b/ext4_utils/ext4_utils.c
index cd82827a..f34985f5 100644
--- a/ext4_utils/ext4_utils.c
+++ b/ext4_utils/ext4_utils.c
@@ -14,22 +14,12 @@
  * limitations under the License.
  */
 
-#include "ext4_utils.h"
-#include "output_file.h"
-#include "backed_block.h"
-#include "uuid.h"
-#include "allocate.h"
-#include "indirect.h"
-#include "extent.h"
-
-#include "ext4.h"
-#include "jbd2.h"
-
 #include <fcntl.h>
 #include <arpa/inet.h>
 #include <sys/ioctl.h>
 #include <sys/stat.h>
 #include <sys/types.h>
+#include <string.h>
 
 #if defined(__linux__)
 #include <linux/fs.h>
@@ -37,6 +27,17 @@
 #include <sys/disk.h>
 #endif
 
+#include "ext4_utils.h"
+#include "output_file.h"
+#include "backed_block.h"
+#include "uuid.h"
+#include "allocate.h"
+#include "indirect.h"
+#include "extent.h"
+
+#include "ext4.h"
+#include "jbd2.h"
+
 int force = 0;
 struct fs_info info;
 struct fs_aux_info aux_info;
@@ -73,24 +74,36 @@ int ext4_bg_has_super_block(int bg)
 }
 
 /* Write the filesystem image to a file */
-void write_ext4_image(const char *filename, int gz)
+void write_ext4_image(const char *filename, int gz, int sparse)
 {
 	int ret = 0;
-	struct output_file *out = open_output_file(filename, gz);
+	struct output_file *out = open_output_file(filename, gz, sparse);
 	off_t off;
 
 	if (!out)
 		return;
 
-	write_data_block(out, 1024, (u8*)aux_info.sb, 1024);
+	/* The write_data* functions expect only block aligned calls.
+	 * This is not an issue, except when we write out the super
+	 * block on a system with a block size > 1K.  So, we need to
+	 * deal with that here.
+	 */
+	if (info.block_size > 1024) {
+		u8 buf[4096] = { 0 }; 	/* The larget supported ext4 block size */
+		memcpy(buf + 1024, (u8*)aux_info.sb, 1024);
+		write_data_block(out, 0, buf, info.block_size);
+
+	} else {
+		write_data_block(out, 1024, (u8*)aux_info.sb, 1024);
+	}
 
-	write_data_block(out, (aux_info.first_data_block + 1) * info.block_size,
+	write_data_block(out, (u64)(aux_info.first_data_block + 1) * info.block_size,
 			 (u8*)aux_info.bg_desc,
 			 aux_info.bg_desc_blocks * info.block_size);
 
 	for_each_data_block(write_data_block, write_data_file, out);
 
-	write_data_block(out, info.len - 1, (u8*)"", 1);
+	pad_output_file(out, info.len);
 
 	close_output_file(out);
 }
diff --git a/ext4_utils/ext4_utils.h b/ext4_utils/ext4_utils.h
index 0a2b542a..697c8d90 100644
--- a/ext4_utils/ext4_utils.h
+++ b/ext4_utils/ext4_utils.h
@@ -116,7 +116,7 @@ static inline int log_2(int j)
 }
 
 int ext4_bg_has_super_block(int bg);
-void write_ext4_image(const char *filename, int gz);
+void write_ext4_image(const char *filename, int gz, int sparse);
 void ext4_create_fs_aux_info(void);
 void ext4_free_fs_aux_info(void);
 void ext4_fill_in_sb(void);
diff --git a/ext4_utils/make_ext4fs.c b/ext4_utils/make_ext4fs.c
index f77af0c9..87588ab6 100644
--- a/ext4_utils/make_ext4fs.c
+++ b/ext4_utils/make_ext4fs.c
@@ -62,6 +62,8 @@ static u32 build_default_directory_structure()
 	root_inode = make_directory(0, 1, &dentries, 1);
 	inode = make_directory(root_inode, 0, NULL, 0);
 	*dentries.inode = inode;
+	inode_set_permissions(inode, dentries.mode,
+		dentries.uid, dentries.gid, dentries.mtime);
 
 	return root_inode;
 }
@@ -225,7 +227,7 @@ void reset_ext4fs_info() {
 }
 
 int make_ext4fs(const char *filename, const char *directory,
-                char *mountpoint, int android, int gzip)
+                char *mountpoint, int android, int gzip, int sparse)
 {
         u32 root_inode_num;
         u16 root_mode;
@@ -319,7 +321,7 @@ int make_ext4fs(const char *filename, const char *directory,
 			aux_info.sb->s_blocks_count_lo - aux_info.sb->s_free_blocks_count_lo,
 			aux_info.sb->s_blocks_count_lo);
 
-	write_ext4_image(filename, gzip);
+	write_ext4_image(filename, gzip, sparse);
 
 	return 0;
 }
diff --git a/ext4_utils/make_ext4fs.h b/ext4_utils/make_ext4fs.h
index 4045e6a0..8c6b2592 100644
--- a/ext4_utils/make_ext4fs.h
+++ b/ext4_utils/make_ext4fs.h
@@ -22,6 +22,6 @@
 
 void reset_ext4fs_info();
 int make_ext4fs(const char *filename, const char *directory,
-                char *mountpoint, int android, int gzip);
+                char *mountpoint, int android, int gzip, int sparse);
 
 #endif
diff --git a/ext4_utils/make_ext4fs_main.c b/ext4_utils/make_ext4fs_main.c
index afea6622..66d7aac6 100644
--- a/ext4_utils/make_ext4fs_main.c
+++ b/ext4_utils/make_ext4fs_main.c
@@ -33,6 +33,7 @@ static void usage(char *path)
         fprintf(stderr, "%s [ -l <len> ] [ -j <journal size> ] [ -b <block_size> ]\n", basename(path));
         fprintf(stderr, "    [ -g <blocks per group> ] [ -i <inodes> ] [ -I <inode size> ]\n");
         fprintf(stderr, "    [ -L <label> ] [ -f ] [ -a <android mountpoint> ]\n");
+        fprintf(stderr, "    [ -z | -s ] [ -J ]\n");
         fprintf(stderr, "    <filename> [<directory>]\n");
 }
 
@@ -44,8 +45,9 @@ int main(int argc, char **argv)
         char *mountpoint = "";
         int android = 0;
         int gzip = 0;
+        int sparse = 0;
 
-        while ((opt = getopt(argc, argv, "l:j:b:g:i:I:L:a:fzJ")) != -1) {
+        while ((opt = getopt(argc, argv, "l:j:b:g:i:I:L:a:fzJs")) != -1) {
                 switch (opt) {
                 case 'l':
                         info.len = parse_num(optarg);
@@ -81,12 +83,21 @@ int main(int argc, char **argv)
 		case 'J':
 			info.no_journal = 1;
 			break;
+                case 's':
+                        sparse = 1;
+                        break;
                 default: /* '?' */
                         usage(argv[0]);
                         exit(EXIT_FAILURE);
                 }
         }
 
+	if (gzip && sparse) {
+                fprintf(stderr, "Cannot specify both gzip and sparse\n");
+                usage(argv[0]);
+                exit(EXIT_FAILURE);
+	}
+
         if (optind >= argc) {
                 fprintf(stderr, "Expected filename after options\n");
                 usage(argv[0]);
@@ -104,5 +115,5 @@ int main(int argc, char **argv)
                 exit(EXIT_FAILURE);
         }
 
-        return make_ext4fs(filename, directory, mountpoint, android, gzip);
+        return make_ext4fs(filename, directory, mountpoint, android, gzip, sparse);
 }
diff --git a/ext4_utils/output_file.c b/ext4_utils/output_file.c
index fa6af5f0..2705701c 100644
--- a/ext4_utils/output_file.c
+++ b/ext4_utils/output_file.c
@@ -26,9 +26,20 @@
 
 #include "ext4_utils.h"
 #include "output_file.h"
+#include "sparse_format.h"
+
+#if defined(__APPLE__) && defined(__MACH__)
+#define lseek64 lseek
+#define off64_t off_t
+#endif
+
+#define SPARSE_HEADER_MAJOR_VER 1
+#define SPARSE_HEADER_MINOR_VER 0
+#define SPARSE_HEADER_LEN       (sizeof(sparse_header_t))
+#define CHUNK_HEADER_LEN (sizeof(chunk_header_t))
 
 struct output_file_ops {
-	int (*seek)(struct output_file *, off_t);
+	int (*seek)(struct output_file *, off64_t);
 	int (*write)(struct output_file *, u8 *, int);
 	void (*close)(struct output_file *);
 };
@@ -36,16 +47,20 @@ struct output_file_ops {
 struct output_file {
 	int fd;
 	gzFile gz_fd;
+	int sparse;
+	u64 cur_out_ptr;
+	int chunk_cnt;
+	u32 crc32;
 	struct output_file_ops *ops;
 };
 
-static int file_seek(struct output_file *out, off_t off)
+static int file_seek(struct output_file *out, off64_t off)
 {
-	off_t ret;
+	off64_t ret;
 
-	ret = lseek(out->fd, off, SEEK_SET);
+	ret = lseek64(out->fd, off, SEEK_SET);
 	if (ret < 0) {
-		error_errno("lseek");
+		error_errno("lseek64");
 		return -1;
 	}
 	return 0;
@@ -78,9 +93,9 @@ static struct output_file_ops file_ops = {
 	.close = file_close,
 };
 
-static int gz_file_seek(struct output_file *out, off_t off)
+static int gz_file_seek(struct output_file *out, off64_t off)
 {
-	off_t ret;
+	off64_t ret;
 
 	ret = gzseek(out->gz_fd, off, SEEK_SET);
 	if (ret < 0) {
@@ -116,18 +131,147 @@ static struct output_file_ops gz_file_ops = {
 	.close = gz_file_close,
 };
 
+static sparse_header_t sparse_header = {
+	.magic = SPARSE_HEADER_MAGIC,
+	.major_version = SPARSE_HEADER_MAJOR_VER,
+	.minor_version = SPARSE_HEADER_MINOR_VER,
+	.file_hdr_sz = SPARSE_HEADER_LEN,
+	.chunk_hdr_sz = CHUNK_HEADER_LEN,
+	.blk_sz = 0,
+	.total_blks = 0,
+	.total_chunks = 0,
+	.image_checksum = 0
+};
+
+static u8 *zero_buf;
+
+static int emit_skip_chunk(struct output_file *out, u64 skip_len)
+{
+	chunk_header_t chunk_header;
+	int ret;
+
+	//DBG printf("skip chunk: 0x%llx bytes\n", skip_len);
+
+	if (skip_len % info.block_size) {
+		error("don't care size %llu is not a multiple of the block size %u",
+				skip_len, info.block_size);
+		return -1;
+	}
+
+	/* We are skipping data, so emit a don't care chunk. */
+	chunk_header.chunk_type = CHUNK_TYPE_DONT_CARE;
+	chunk_header.reserved1 = 0;
+	chunk_header.chunk_sz = skip_len / info.block_size;
+	chunk_header.total_sz = CHUNK_HEADER_LEN;
+	ret = out->ops->write(out, (u8 *)&chunk_header, sizeof(chunk_header));
+	if (ret < 0)
+		return -1;
+	// KEN: TODO: CRC computation
+	out->cur_out_ptr += skip_len;
+	out->chunk_cnt++;
+
+	return 0;
+}
+
+static int write_chunk_raw(struct output_file *out, u64 off, u8 *data, int len)
+{
+	chunk_header_t chunk_header;
+	int rnd_up_len, zero_len;
+	int ret;
+
+	/* We can assume that all the chunks to be written are in
+	 * ascending order, block-size aligned, and non-overlapping.
+	 * So, if the offset is less than the current output pointer,
+	 * throw an error, and if there is a gap, emit a "don't care"
+	 * chunk.  The first write (of the super block) may not be
+	 * blocksize aligned, so we need to deal with that too.
+	 */
+	//DBG printf("write chunk: offset 0x%llx, length 0x%x bytes\n", off, len);
+
+	if (off < out->cur_out_ptr) {
+		error("offset %llu is less than the current output offset %llu",
+				off, out->cur_out_ptr);
+		return -1;
+	}
+
+	if (off > out->cur_out_ptr) {
+		emit_skip_chunk(out, off - out->cur_out_ptr);
+	}
+
+	if (off % info.block_size) {
+		error("write chunk offset %llu is not a multiple of the block size %u",
+				off, info.block_size);
+		return -1;
+	}
+
+	if (off != out->cur_out_ptr) {
+		error("internal error, offset accounting screwy in write_chunk_raw()");
+		return -1;
+	}
+
+	/* Round up the file length to a multiple of the block size */
+	rnd_up_len = (len + (info.block_size - 1)) & (~(info.block_size -1));
+	zero_len = rnd_up_len - len;
+
+	/* Finally we can safely emit a chunk of data */
+	chunk_header.chunk_type = CHUNK_TYPE_RAW;
+	chunk_header.reserved1 = 0;
+	chunk_header.chunk_sz = rnd_up_len / info.block_size;
+	chunk_header.total_sz = CHUNK_HEADER_LEN + rnd_up_len;
+	ret = out->ops->write(out, (u8 *)&chunk_header, sizeof(chunk_header));
+
+	if (ret < 0)
+		return -1;
+	ret = out->ops->write(out, data, len);
+	if (ret < 0)
+		return -1;
+	if (zero_len) {
+		ret = out->ops->write(out, zero_buf, zero_len);
+		if (ret < 0)
+			return -1;
+	}
+
+	// KEN: TODO: CRC computation of both the raw data and and zero buf data written */
+	out->cur_out_ptr += rnd_up_len;
+	out->chunk_cnt++;
+
+	return 0;
+}
+
 void close_output_file(struct output_file *out)
 {
+	int ret;
+
+	if (out->sparse) {
+		/* we need to seek back to the beginning and update the file header */
+		sparse_header.total_chunks = out->chunk_cnt;
+		sparse_header.image_checksum = out->crc32;
+
+		ret = out->ops->seek(out, 0);
+		if (ret < 0)
+			error("failure seeking to start of sparse file");
+
+		ret = out->ops->write(out, (u8 *)&sparse_header, sizeof(sparse_header));
+		if (ret < 0)
+			error("failure updating sparse file header");
+	}
 	out->ops->close(out);
 }
 
-struct output_file *open_output_file(const char *filename, int gz)
+struct output_file *open_output_file(const char *filename, int gz, int sparse)
 {
+	int ret;
 	struct output_file *out = malloc(sizeof(struct output_file));
 	if (!out) {
-		error_errno("malloc");
+		error_errno("malloc struct out");
 		return NULL;
 	}
+	zero_buf = malloc(info.block_size);
+	if (!zero_buf) {
+		error_errno("malloc zero_buf");
+		return NULL;
+	}
+	memset(zero_buf, '\0', info.block_size);
 
 	if (gz) {
 		out->ops = &gz_file_ops;
@@ -146,9 +290,61 @@ struct output_file *open_output_file(const char *filename, int gz)
 			return NULL;
 		}
 	}
+	out->sparse = sparse;
+	out->cur_out_ptr = 0ll;
+	out->chunk_cnt = 0;
+	if (out->sparse) {
+		/* Write out the file header.  We'll update the unknown fields
+		 * when we close the file.
+		 */
+		sparse_header.blk_sz = info.block_size,
+		sparse_header.total_blks = info.len / info.block_size,
+		ret = out->ops->write(out, (u8 *)&sparse_header, sizeof(sparse_header));
+		if (ret < 0)
+			return NULL;
+	}
+
 	return out;
 }
 
+void pad_output_file(struct output_file *out, u64 len)
+{
+	int ret;
+
+	if (len > info.len) {
+		error("attempted to pad file %llu bytes past end of filesystem",
+				len - info.len);
+		return;
+	}
+	if (out->sparse) {
+		/* We need to emit a DONT_CARE chunk to pad out the file if the
+		 * cur_out_ptr is not already at the end of the filesystem.
+		 * We also need to compute the CRC for it.
+		 */
+		 //KEN: TODO: CRC computation!
+		if (len < out->cur_out_ptr) {
+			error("attempted to pad file %llu bytes less than the current output pointer",
+					out->cur_out_ptr - len);
+			return;
+		}
+		if (len > out->cur_out_ptr) {
+			emit_skip_chunk(out, len - out->cur_out_ptr);
+		}
+	} else {
+		//KEN TODO: Fixme.  If the filesystem image needs no padding,
+		//          this will overwrite the last byte in the file with 0
+		//          The answer is to do accounting like the sparse image
+		//          code does and know if there is already data there.
+		ret = out->ops->seek(out, len - 1);
+		if (ret < 0)
+			return;
+
+		ret = out->ops->write(out, (u8*)"", 1);
+		if (ret < 0)
+			return;
+	}
+}
+
 /* Write a contiguous region of data blocks from a memory buffer */
 void write_data_block(struct output_file *out, u64 off, u8 *data, int len)
 {
@@ -160,13 +356,17 @@ void write_data_block(struct output_file *out, u64 off, u8 *data, int len)
 		return;
 	}
 
-	ret = out->ops->seek(out, off);
-	if (ret < 0)
-		return;
+	if (out->sparse) {
+		write_chunk_raw(out, off, data, len);
+	} else {
+		ret = out->ops->seek(out, off);
+		if (ret < 0)
+			return;
 
-	ret = out->ops->write(out, data, len);
-	if (ret < 0)
-		return;
+		ret = out->ops->write(out, data, len);
+		if (ret < 0)
+			return;
+	}
 }
 
 /* Write a contiguous region of data blocks from a file */
@@ -194,14 +394,17 @@ void write_data_file(struct output_file *out, u64 off, const char *file,
 		return;
 	}
 
-	ret = out->ops->seek(out, off);
-	if (ret < 0)
-		goto err;
-
-	ret = out->ops->write(out, data, len);
-	if (ret < 0)
-		goto err;
+	if (out->sparse) {
+		write_chunk_raw(out, off, data, len);
+	} else {
+		ret = out->ops->seek(out, off);
+		if (ret < 0)
+			goto err;
 
+		ret = out->ops->write(out, data, len);
+		if (ret < 0)
+			goto err;
+	}
 
 	munmap(data, len);
 
@@ -211,3 +414,4 @@ err:
 	munmap(data, len);
 	close(file_fd);
 }
+
diff --git a/ext4_utils/output_file.h b/ext4_utils/output_file.h
index 1df9e812..82b09521 100644
--- a/ext4_utils/output_file.h
+++ b/ext4_utils/output_file.h
@@ -16,8 +16,9 @@
 
 struct output_file;
 
-struct output_file *open_output_file(const char *filename, int gz);
+struct output_file *open_output_file(const char *filename, int gz, int sparse);
 void write_data_block(struct output_file *out, u64 off, u8 *data, int len);
 void write_data_file(struct output_file *out, u64 off, const char *file,
 		     off_t offset, int len);
+void pad_output_file(struct output_file *out, u64 len);
 void close_output_file(struct output_file *out);
diff --git a/ext4_utils/simg2img.c b/ext4_utils/simg2img.c
new file mode 100644
index 00000000..9c1ad370
--- /dev/null
+++ b/ext4_utils/simg2img.c
@@ -0,0 +1,198 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * 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.
+ */
+#define _LARGEFILE64_SOURCE
+#define _FILE_OFFSET_BITS 64
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <sys/mman.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <stdio.h>
+
+#include "ext4_utils.h"
+#include "output_file.h"
+#include "sparse_format.h"
+
+#if defined(__APPLE__) && defined(__MACH__)
+#define lseek64 lseek
+#define off64_t off_t
+#endif
+
+#define COPY_BUF_SIZE (1024*1024)
+u8 *copybuf;
+
+#define SPARSE_HEADER_MAJOR_VER 1
+#define SPARSE_HEADER_LEN       (sizeof(sparse_header_t))
+#define CHUNK_HEADER_LEN (sizeof(chunk_header_t))
+
+void usage()
+{
+  fprintf(stderr, "Usage: simg2img <sparse_image_file> <raw_image_file>\n");
+}
+
+int process_raw_chunk(FILE *in, FILE *out, u32 blocks, u32 blk_sz, u32 *crc32)
+{
+	u64 len = (u64)blocks * blk_sz;
+	int chunk;
+
+	while (len) {
+		chunk = (len > COPY_BUF_SIZE) ? COPY_BUF_SIZE : len;
+		fread(copybuf, chunk, 1, in);
+		fwrite(copybuf, chunk, 1, out);
+		len -= chunk;
+	}
+
+	return blocks;
+}
+
+
+int process_skip_chunk(FILE *out, u32 blocks, u32 blk_sz, u32 *crc32)
+{
+	/* len needs to be 64 bits, as the sparse file specifies the skip amount
+	 * as a 32 bit value of blocks.
+	 */
+	u64 len = (u64)blocks * blk_sz;
+	long skip_chunk;
+
+	/* Fseek takes the offset as a long, which may be 32 bits on some systems.
+	 * So, lets do a sequence of fseeks() with SEEK_CUR to get the file pointer
+	 * where we want it.
+	 */
+	while (len) {
+		skip_chunk = (len > 0x80000000) ? 0x80000000 : len;
+		fseek(out, skip_chunk, SEEK_CUR);
+		len -= skip_chunk;
+	}
+
+	return blocks;
+}
+
+int main(int argc, char *argv[])
+{
+	FILE *in, *out;
+	unsigned int i;
+	sparse_header_t sparse_header;
+	chunk_header_t chunk_header;
+	u32 crc32 = 0;
+	u32 total_blocks = 0;
+
+	if (argc != 3) {
+		usage();
+		exit(-1);
+	}
+
+	if ( (copybuf = malloc(COPY_BUF_SIZE)) == 0) {
+		fprintf(stderr, "Cannot malloc copy buf\n");
+		exit(-1);
+	}
+
+	if ((in = fopen(argv[1], "rb")) == 0) {
+		fprintf(stderr, "Cannot open input file %s\n", argv[1]);
+		exit(-1);
+	}
+
+	if ((out = fopen(argv[2], "wb")) == 0) {
+		fprintf(stderr, "Cannot open output file %s\n", argv[2]);
+		exit(-1);
+	}
+
+	if (fread(&sparse_header, sizeof(sparse_header), 1, in) != 1) {
+		fprintf(stderr, "Error reading sparse file header\n");
+		exit(-1);
+	}
+
+	if (sparse_header.magic != SPARSE_HEADER_MAGIC) {
+		fprintf(stderr, "Bad magic\n");
+		exit(-1);
+	}
+
+	if (sparse_header.major_version != SPARSE_HEADER_MAJOR_VER) {
+		fprintf(stderr, "Unknown major version number\n");
+		exit(-1);
+	}
+
+	if (sparse_header.file_hdr_sz > SPARSE_HEADER_LEN) {
+		/* Skip the remaining bytes in a header that is longer than
+		 * we expected.
+		 */
+		fseek(in, sparse_header.file_hdr_sz - SPARSE_HEADER_LEN, SEEK_CUR);
+	}
+
+	for (i=0; i<sparse_header.total_chunks; i++) {
+		if (fread(&chunk_header, sizeof(chunk_header), 1, in) != 1) {
+			fprintf(stderr, "Error reading chunk header\n");
+			exit(-1);
+		}
+ 
+		if (sparse_header.chunk_hdr_sz > CHUNK_HEADER_LEN) {
+			/* Skip the remaining bytes in a header that is longer than
+			 * we expected.
+			 */
+			fseek(in, sparse_header.chunk_hdr_sz - CHUNK_HEADER_LEN, SEEK_CUR);
+		}
+
+		switch (chunk_header.chunk_type) {
+		    case CHUNK_TYPE_RAW:
+			if (chunk_header.total_sz != (sparse_header.chunk_hdr_sz +
+				 (chunk_header.chunk_sz * sparse_header.blk_sz)) ) {
+				fprintf(stderr, "Bogus chunk size for chunk %d, type Raw\n", i);
+				exit(-1);
+			}
+			total_blocks += process_raw_chunk(in, out,
+					 chunk_header.chunk_sz, sparse_header.blk_sz, &crc32);
+			break;
+		    case CHUNK_TYPE_DONT_CARE:
+			if (chunk_header.total_sz != sparse_header.chunk_hdr_sz) {
+				fprintf(stderr, "Bogus chunk size for chunk %d, type Dont Care\n", i);
+				exit(-1);
+			}
+			total_blocks += process_skip_chunk(out,
+					 chunk_header.chunk_sz, sparse_header.blk_sz, &crc32);
+			break;
+		    default:
+			fprintf(stderr, "Unknown chunk type 0x%4.4x\n", chunk_header.chunk_type);
+			exit(-1);
+		}
+
+	}
+
+	/* If the last chunk was a skip, then the code just did a seek, but
+	 * no write, and the file won't actually be the correct size.  This
+	 * will make the file the correct size.  Make sure the offset is
+	 * computed in 64 bits, and the function called can handle 64 bits.
+	 */
+	ftruncate(fileno(out), (u64)total_blocks * sparse_header.blk_sz);
+
+	fclose(in);
+	fclose(out);
+
+	if (sparse_header.total_blks != total_blocks) {
+		fprintf(stderr, "Wrote %d blocks, expected to write %d blocks\n",
+			 total_blocks, sparse_header.total_blks);
+		exit(-1);
+	}
+
+	if (sparse_header.image_checksum != crc32) {
+		fprintf(stderr, "computed crc32 of %d, expected %d\n",
+			 crc32, sparse_header.image_checksum);
+		exit(-1);
+	}
+
+	exit(0);
+}
+
diff --git a/ext4_utils/sparse_format.h b/ext4_utils/sparse_format.h
new file mode 100644
index 00000000..ba132140
--- /dev/null
+++ b/ext4_utils/sparse_format.h
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * 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.
+ */
+
+typedef struct sparse_header {
+  __le32	magic;		/* 0xed26ff3a */
+  __le16	major_version;	/* (0x1) - reject images with higher major versions */
+  __le16	minor_version;	/* (0x0) - allow images with higer minor versions */
+  __le16	file_hdr_sz;	/* 28 bytes for first revision of the file format */
+  __le16	chunk_hdr_sz;	/* 12 bytes for first revision of the file format */
+  __le32	blk_sz;		/* block size in bytes, must be a multiple of 4 (4096) */
+  __le32	total_blks;	/* total blocks in the non-sparse output image */
+  __le32	total_chunks;	/* total chunks in the sparse input image */
+  __le32	image_checksum; /* CRC32 checksum of the original data, counting "don't care" */
+				/* as 0. Standard 802.3 polynomial, use a Public Domain */
+				/* table implementation */
+} sparse_header_t;
+
+#define SPARSE_HEADER_MAGIC	0xed26ff3a
+
+#define CHUNK_TYPE_RAW		0xCAC1
+#define CHUNK_TYPE_FILL		0xCAC2
+#define CHUNK_TYPE_DONT_CARE	0xCAC3
+
+typedef struct chunk_header {
+  __le16	chunk_type;	/* 0xCAC1 -> raw; 0xCAC2 -> fill; 0xCAC3 -> don't care */
+  __le16	reserved1;
+  __le32	chunk_sz;	/* in blocks in output image */
+  __le32	total_sz;	/* in bytes of chunk input file including chunk header and data */
+} chunk_header_t;
+
+/* Following a Raw or Fill chunk is data.  For a Raw chunk, it's the data in chunk_sz * blk_sz.
+ *  For a Fill chunk, it's 4 bytes of the fill data.
+ */
+
-- 
2.11.0