Refactor sparse file support into libsparse

Minimal refactoring of output_file.c into libsparse in preparation
for completely separating libsparse from ext4_utils.

Moves output_file.c, backed_block.c, and parts of ext4_utils.c
into libsparse.  The only changes to the remanining files in
ext4_utils are using the new sparse.h header, and moving the
wipe call out of output_file.c and into make_ext4fs.c.

Change-Id: I1f66f6c3e05230a350023c5b4ea4422f16a73c4b

23 files changed, 422 insertions, 234 deletions

diff --git a/ext4_utils/Android.mk b/ext4_utils/Android.mk
index 5dae31f2..4273963a 100644
--- a/ext4_utils/Android.mk
+++ b/ext4_utils/Android.mk
@@ -8,14 +8,11 @@ libext4_utils_src_files := \
         ext4fixup.c \
         ext4_utils.c \
         allocate.c \
-        backed_block.c \
-        output_file.c \
         contents.c \
         extent.c \
         indirect.c \
         uuid.c \
         sha1.c \
-        sparse_crc32.c \
         wipe.c
 
 # -- All host/targets including windows
@@ -24,6 +21,7 @@ LOCAL_SRC_FILES := $(libext4_utils_src_files)
 LOCAL_MODULE := libext4_utils
 LOCAL_MODULE_TAGS := optional
 LOCAL_C_INCLUDES += external/zlib
+LOCAL_STATIC_LIBRARIES += libsparse
 
 ifeq ($(HAVE_SELINUX), true)
 LOCAL_C_INCLUDES += external/libselinux/include
@@ -37,7 +35,7 @@ include $(CLEAR_VARS)
 
 LOCAL_SRC_FILES := make_ext4fs_main.c
 LOCAL_MODULE := make_ext4fs
-LOCAL_STATIC_LIBRARIES += libext4_utils libz
+LOCAL_STATIC_LIBRARIES += libext4_utils libsparse libz
 ifeq ($(HOST_OS),windows)
 LOCAL_LDLIBS += -lws2_32
 else
@@ -58,7 +56,7 @@ LOCAL_SRC_FILES := $(libext4_utils_src_files)
 LOCAL_MODULE := libext4_utils
 LOCAL_MODULE_TAGS := optional
 LOCAL_C_INCLUDES += external/zlib
-LOCAL_SHARED_LIBRARIES := libz
+LOCAL_SHARED_LIBRARIES := libsparse libz
 
 ifeq ($(HAVE_SELINUX), true)
 LOCAL_C_INCLUDES += external/libselinux/include
@@ -74,6 +72,7 @@ LOCAL_SRC_FILES := $(libext4_utils_src_files)
 LOCAL_MODULE := libext4_utils
 LOCAL_MODULE_TAGS := optional
 LOCAL_C_INCLUDES += external/zlib
+LOCAL_STATIC_LIBRARIES += libsparse
 
 ifeq ($(HAVE_SELINUX), true)
 LOCAL_C_INCLUDES += external/libselinux/include
@@ -103,7 +102,7 @@ include $(CLEAR_VARS)
 LOCAL_SRC_FILES := ext2simg.c
 LOCAL_MODULE := ext2simg
 LOCAL_MODULE_TAGS := optional
-LOCAL_SHARED_LIBRARIES += libext4_utils libz
+LOCAL_SHARED_LIBRARIES += libext4_utils libsparse libz
 
 ifeq ($(HAVE_SELINUX), true)
 LOCAL_C_INCLUDES += external/libselinux/include
@@ -118,7 +117,7 @@ include $(CLEAR_VARS)
 LOCAL_SRC_FILES := ext2simg.c
 LOCAL_MODULE := ext2simg
 LOCAL_MODULE_TAGS := optional
-LOCAL_STATIC_LIBRARIES += libext4_utils libz
+LOCAL_STATIC_LIBRARIES += libext4_utils libsparse libz
 
 ifeq ($(HAVE_SELINUX), true)
 LOCAL_C_INCLUDES += external/libselinux/include
@@ -129,40 +128,6 @@ endif # HAVE_SELINUX
 include $(BUILD_HOST_EXECUTABLE)
 
 include $(CLEAR_VARS)
-
-LOCAL_SRC_FILES := simg2img.c \
-	sparse_crc32.c
-LOCAL_MODULE := simg2img
-LOCAL_MODULE_TAGS := debug
-
-include $(BUILD_HOST_EXECUTABLE)
-
-include $(CLEAR_VARS)
-
-LOCAL_SRC_FILES := simg2img.c \
-	sparse_crc32.c
-LOCAL_MODULE := simg2img
-LOCAL_MODULE_TAGS := optional
-
-include $(BUILD_EXECUTABLE)
-
-include $(CLEAR_VARS)
-
-LOCAL_SRC_FILES := img2simg.c
-LOCAL_MODULE := img2simg
-LOCAL_MODULE_TAGS := debug
-
-include $(BUILD_HOST_EXECUTABLE)
-
-include $(CLEAR_VARS)
-
-LOCAL_SRC_FILES := img2simg.c
-LOCAL_MODULE := img2simg
-LOCAL_MODULE_TAGS := optional
-
-include $(BUILD_EXECUTABLE)
-
-include $(CLEAR_VARS)
 LOCAL_SRC_FILES := setup_fs.c
 LOCAL_MODULE := setup_fs
 LOCAL_MODULE_TAGS := optional
@@ -174,7 +139,7 @@ include $(CLEAR_VARS)
 LOCAL_SRC_FILES := ext4fixup_main.c
 LOCAL_MODULE := ext4fixup
 LOCAL_MODULE_TAGS := optional
-LOCAL_SHARED_LIBRARIES += libext4_utils libz
+LOCAL_SHARED_LIBRARIES += libext4_utils libsparse libz
 
 include $(BUILD_EXECUTABLE)
 
@@ -183,7 +148,7 @@ include $(CLEAR_VARS)
 LOCAL_SRC_FILES := ext4fixup_main.c
 LOCAL_MODULE := ext4fixup
 LOCAL_MODULE_TAGS := optional
-LOCAL_STATIC_LIBRARIES += libext4_utils libz
+LOCAL_STATIC_LIBRARIES += libext4_utils libsparse libz
 
 include $(BUILD_HOST_EXECUTABLE)
 
@@ -199,14 +164,6 @@ LOCAL_IS_HOST_MODULE := true
 
 include $(BUILD_PREBUILT)
 
-include $(CLEAR_VARS)
-
-LOCAL_MODULE := simg_dump.py
-LOCAL_MODULE_TAGS := debug
-LOCAL_SRC_FILES := simg_dump.py
-LOCAL_MODULE_CLASS := EXECUTABLES
-LOCAL_IS_HOST_MODULE := true
-
-include $(BUILD_PREBUILT)
-
 endif
+
+include $(LOCAL_PATH)/libsparse/Android.mk
diff --git a/ext4_utils/allocate.c b/ext4_utils/allocate.c
index 0e162851..dfc3f165 100644
--- a/ext4_utils/allocate.c
+++ b/ext4_utils/allocate.c
@@ -16,9 +16,10 @@
 
 #include "ext4_utils.h"
 #include "allocate.h"
-#include "backed_block.h"
 #include "ext4.h"
 
+#include <sparse/sparse.h>
+
 #include <stdio.h>
 #include <stdlib.h>
 
diff --git a/ext4_utils/ext2simg.c b/ext4_utils/ext2simg.c
index 1fe085a9..e8f26c67 100644
--- a/ext4_utils/ext2simg.c
+++ b/ext4_utils/ext2simg.c
@@ -14,10 +14,10 @@
  * limitations under the License.
  */
 
+#include <sparse/sparse.h>
+
 #include "ext4_utils.h"
 #include "make_ext4fs.h"
-#include "output_file.h"
-#include "backed_block.h"
 #include "allocate.h"
 
 #include <sys/types.h>
@@ -236,7 +236,7 @@ int main(int argc, char **argv)
 		outfd = STDOUT_FILENO;
 	}
 
-	write_ext4_image(outfd, gzip, sparse, crc, 0);
+	write_ext4_image(outfd, gzip, sparse, crc);
 	close(outfd);
 
 	return 0;
diff --git a/ext4_utils/ext4_utils.c b/ext4_utils/ext4_utils.c
index 7f226c8b..a2102818 100644
--- a/ext4_utils/ext4_utils.c
+++ b/ext4_utils/ext4_utils.c
@@ -15,13 +15,13 @@
  */
 
 #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 <sparse/sparse.h>
+
 #include <fcntl.h>
 #include <sys/stat.h>
 #include <sys/types.h>
@@ -80,83 +80,10 @@ int ext4_bg_has_super_block(int bg)
 	return 0;
 }
 
-struct count_chunks {
-	u32 chunks;
-	u64 cur_ptr;
-};
-
-void count_data_block(void *priv, u64 off, u8 *data, int len)
-{
-	struct count_chunks *count_chunks = priv;
-	if (off > count_chunks->cur_ptr)
-		count_chunks->chunks++;
-	count_chunks->cur_ptr = off + ALIGN(len, info.block_size);
-	count_chunks->chunks++;
-}
-
-void count_fill_block(void *priv, u64 off, u32 fill_val, int len)
-{
-	struct count_chunks *count_chunks = priv;
-	if (off > count_chunks->cur_ptr)
-		count_chunks->chunks++;
-	count_chunks->cur_ptr = off + ALIGN(len, info.block_size);
-	count_chunks->chunks++;
-}
-
-void count_file_block(void *priv, u64 off, const char *file,
-		off64_t offset, int len)
-{
-	struct count_chunks *count_chunks = priv;
-	if (off > count_chunks->cur_ptr)
-		count_chunks->chunks++;
-	count_chunks->cur_ptr = off + ALIGN(len, info.block_size);
-	count_chunks->chunks++;
-}
-
-int count_sparse_chunks()
-{
-	struct count_chunks count_chunks = {0, 0};
-
-	for_each_data_block(count_data_block, count_file_block, count_fill_block, &count_chunks);
-
-	if (count_chunks.cur_ptr != (u64) info.len)
-		count_chunks.chunks++;
-
-	return count_chunks.chunks;
-}
-
-static void ext4_write_data_block(void *priv, u64 off, u8 *data, int len)
-{
-	write_data_block(priv, off, data, len);
-}
-
-static void ext4_write_fill_block(void *priv, u64 off, u32 fill_val, int len)
-{
-	write_fill_block(priv, off, fill_val, len);
-}
-
-static void ext4_write_data_file(void *priv, u64 off, const char *file,
-		off64_t offset, int len)
-{
-	write_data_file(priv, off, file, offset, len);
-}
-
 /* Write the filesystem image to a file */
-void write_ext4_image(int fd, int gz, int sparse, int crc, int wipe)
+void write_ext4_image(int fd, int gz, int sparse, int crc)
 {
-	int ret = 0;
-
-	struct output_file *out = open_output_fd(fd, gz, sparse,
-	        count_sparse_chunks(), crc, wipe);
-
-	if (!out)
-		return;
-
-	for_each_data_block(ext4_write_data_block, ext4_write_data_file, ext4_write_fill_block, out);
-
-	pad_output_file(out, info.len);
-
-	close_output_file(out);
+	write_sparse_image(fd, gz, sparse, crc, info.block_size, info.len);
 }
 
 /* Compute the rest of the parameters of the filesystem from the basic info */
diff --git a/ext4_utils/ext4_utils.h b/ext4_utils/ext4_utils.h
index 1d701d0d..9ee6929b 100644
--- a/ext4_utils/ext4_utils.h
+++ b/ext4_utils/ext4_utils.h
@@ -25,7 +25,7 @@ extern "C" {
 #define _GNU_SOURCE
 #endif
 #define _FILE_OFFSET_BITS 64
-#define _LARGEFILE64_SOURCE
+#define _LARGEFILE64_SOURCE 1
 #include <sys/types.h>
 #include <unistd.h>
 
@@ -153,8 +153,7 @@ static inline int log_2(int j)
 }
 
 int ext4_bg_has_super_block(int bg);
-void write_ext4_image(int fd, int gz, int sparse, int crc,
-		int wipe);
+void write_ext4_image(int fd, int gz, int sparse, int crc);
 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/ext4fixup.c b/ext4_utils/ext4fixup.c
index c664ac3a..f0124f88 100644
--- a/ext4_utils/ext4fixup.c
+++ b/ext4_utils/ext4fixup.c
@@ -16,11 +16,11 @@
 #include "ext4_utils.h"
 #include "make_ext4fs.h"
 #include "ext4_extents.h"
-#include "output_file.h"
-#include "backed_block.h"
 #include "allocate.h"
 #include "ext4fixup.h"
 
+#include <sparse/sparse.h>
+
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <sys/types.h>
diff --git a/ext4_utils/extent.c b/ext4_utils/extent.c
index daa25413..905a378b 100644
--- a/ext4_utils/extent.c
+++ b/ext4_utils/extent.c
@@ -17,9 +17,10 @@
 #include "ext4_utils.h"
 #include "ext4.h"
 #include "ext4_extents.h"
-#include "backed_block.h"
 #include "extent.h"
 
+#include <sparse/sparse.h>
+
 #include <stdlib.h>
 #include <stdio.h>
 
diff --git a/ext4_utils/indirect.c b/ext4_utils/indirect.c
index 70f04d6e..d0490f2c 100644
--- a/ext4_utils/indirect.c
+++ b/ext4_utils/indirect.c
@@ -17,10 +17,11 @@
 #include "ext4_utils.h"
 #include "ext4.h"
 #include "ext4_extents.h"
-#include "backed_block.h"
 #include "indirect.h"
 #include "allocate.h"
 
+#include <sparse/sparse.h>
+
 #include <stdlib.h>
 #include <stdio.h>
 
diff --git a/ext4_utils/libsparse/Android.mk b/ext4_utils/libsparse/Android.mk
new file mode 100644
index 00000000..dbe4d184
--- /dev/null
+++ b/ext4_utils/libsparse/Android.mk
@@ -0,0 +1,86 @@
+# Copyright 2010 The Android Open Source Project
+
+LOCAL_PATH:= $(call my-dir)
+
+libsparse_src_files := \
+        backed_block.c \
+        output_file.c \
+        sparse.c \
+        sparse_crc32.c
+
+include $(CLEAR_VARS)
+
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
+LOCAL_SRC_FILES := $(libsparse_src_files)
+LOCAL_MODULE := libsparse
+LOCAL_MODULE_TAGS := optional
+LOCAL_STATIC_LIBRARIES := libz
+LOCAL_C_INCLUDES += $(LOCAL_PATH)/include external/zlib
+
+include $(BUILD_HOST_STATIC_LIBRARY)
+
+include $(CLEAR_VARS)
+
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
+LOCAL_SRC_FILES := $(libsparse_src_files)
+LOCAL_MODULE := libsparse
+LOCAL_MODULE_TAGS := optional
+LOCAL_C_INCLUDES += $(LOCAL_PATH)/include external/zlib
+LOCAL_SHARED_LIBRARIES := libz
+
+include $(BUILD_SHARED_LIBRARY)
+
+include $(CLEAR_VARS)
+
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
+LOCAL_SRC_FILES := $(libsparse_src_files)
+LOCAL_MODULE := libsparse
+LOCAL_MODULE_TAGS := optional
+LOCAL_C_INCLUDES += $(LOCAL_PATH)/include external/zlib
+LOCAL_STATIC_LIBRARIES := libz
+
+include $(BUILD_STATIC_LIBRARY)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := simg2img.c \
+	sparse_crc32.c
+LOCAL_MODULE := simg2img
+LOCAL_MODULE_TAGS := debug
+
+include $(BUILD_HOST_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := simg2img.c \
+	sparse_crc32.c
+LOCAL_MODULE := simg2img
+LOCAL_MODULE_TAGS := optional
+
+include $(BUILD_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := img2simg.c
+LOCAL_MODULE := img2simg
+LOCAL_MODULE_TAGS := debug
+
+include $(BUILD_HOST_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := img2simg.c
+LOCAL_MODULE := img2simg
+LOCAL_MODULE_TAGS := optional
+
+include $(BUILD_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_MODULE := simg_dump.py
+LOCAL_MODULE_TAGS := debug
+LOCAL_SRC_FILES := simg_dump.py
+LOCAL_MODULE_CLASS := EXECUTABLES
+LOCAL_IS_HOST_MODULE := true
+
+include $(BUILD_PREBUILT)
diff --git a/ext4_utils/backed_block.c b/ext4_utils/libsparse/backed_block.c
index c0070f1a..2975b7d7 100644
--- a/ext4_utils/backed_block.c
+++ b/ext4_utils/libsparse/backed_block.c
@@ -14,15 +14,18 @@
  * limitations under the License.
  */
 
-#include "ext4_utils.h"
+#include <sparse/sparse.h>
+
 #include "backed_block.h"
+#include "sparse_defs.h"
 
 #include <stdlib.h>
+#include <string.h>
 
 struct data_block {
 	u32 block;
 	u32 len;
-	u8 *data;
+	void *data;
 	const char *filename;
 	off64_t offset;
 	struct data_block *next;
@@ -71,11 +74,13 @@ static void queue_db(struct data_block *new_db)
 }
 
 /* Queues a fill block of memory to be written to the specified data blocks */
-void queue_fill_block(u32 fill_val, u32 len, u32 block)
+void queue_fill_block(unsigned int fill_val, unsigned int len, unsigned int block)
 {
 	struct data_block *db = malloc(sizeof(struct data_block));
-	if (db == NULL)
-		critical_error_errno("malloc");
+	if (db == NULL) {
+		error_errno("malloc");
+		return;
+	}
 
 	db->block = block;
 	db->len = len;
@@ -89,11 +94,13 @@ void queue_fill_block(u32 fill_val, u32 len, u32 block)
 }
 
 /* Queues a block of memory to be written to the specified data blocks */
-void queue_data_block(u8 *data, u32 len, u32 block)
+void queue_data_block(void *data, unsigned int len, unsigned int block)
 {
 	struct data_block *db = malloc(sizeof(struct data_block));
-	if (db == NULL)
-		critical_error_errno("malloc");
+	if (db == NULL) {
+		error_errno("malloc");
+		return;
+	}
 
 	db->block = block;
 	db->len = len;
@@ -106,12 +113,14 @@ void queue_data_block(u8 *data, u32 len, u32 block)
 }
 
 /* Queues a chunk of a file on disk to be written to the specified data blocks */
-void queue_data_file(const char *filename, off64_t offset, u32 len,
-	u32 block)
+void queue_data_file(const char *filename, off64_t offset, unsigned int len,
+		unsigned int block)
 {
 	struct data_block *db = malloc(sizeof(struct data_block));
-	if (db == NULL)
-		critical_error_errno("malloc");
+	if (db == NULL) {
+		error_errno("malloc");
+		return;
+	}
 
 	db->block = block;
 	db->len = len;
@@ -128,7 +137,7 @@ void queue_data_file(const char *filename, off64_t offset, u32 len,
    data block, and file_func for each contiguous file block */
 void for_each_data_block(data_block_callback_t data_func,
 	data_block_file_callback_t file_func,
-	data_block_fill_callback_t fill_func, void *priv)
+	data_block_fill_callback_t fill_func, void *priv, unsigned int block_size)
 {
 	struct data_block *db;
 	u32 last_block = 0;
@@ -136,14 +145,14 @@ void for_each_data_block(data_block_callback_t data_func,
 	for (db = data_blocks; db; db = db->next) {
 		if (db->block < last_block)
 			error("data blocks out of order: %u < %u", db->block, last_block);
-		last_block = db->block + DIV_ROUND_UP(db->len, info.block_size) - 1;
+		last_block = db->block + DIV_ROUND_UP(db->len, block_size) - 1;
 
 		if (db->filename)
-			file_func(priv, (u64)db->block * info.block_size, db->filename, db->offset, db->len);
+			file_func(priv, (u64)db->block * block_size, db->filename, db->offset, db->len);
 		else if (db->fill)
-			fill_func(priv, (u64)db->block * info.block_size, db->fill_val, db->len);
+			fill_func(priv, (u64)db->block * block_size, db->fill_val, db->len);
 		else
-			data_func(priv, (u64)db->block * info.block_size, db->data, db->len);
+			data_func(priv, (u64)db->block * block_size, db->data, db->len);
 	}
 }
 
diff --git a/ext4_utils/backed_block.h b/ext4_utils/libsparse/backed_block.h
index e3c4ac4a..bcacc551 100644
--- a/ext4_utils/backed_block.h
+++ b/ext4_utils/libsparse/backed_block.h
@@ -17,22 +17,16 @@
 #ifndef _BACKED_BLOCK_H_
 #define _BACKED_BLOCK_H_
 
-#include "ext4_utils.h"
-#include "output_file.h"
+#include <sparse/sparse.h>
 
-typedef void (*data_block_callback_t)(void *priv, u64 off, u8 *data, int len);
-typedef void (*data_block_fill_callback_t)(void *priv, u64 off, u32 fill_val, int len);
-typedef void (*data_block_file_callback_t)(void *priv, u64 off,
+typedef void (*data_block_callback_t)(void *priv, off64_t off, void *data, int len);
+typedef void (*data_block_fill_callback_t)(void *priv, off64_t off, unsigned int fill_val, int len);
+typedef void (*data_block_file_callback_t)(void *priv, off64_t off,
 					   const char *file, off64_t offset,
 					   int len);
 
-void queue_data_block(u8 *data, u32 len, u32 block);
-void queue_fill_block(u32 fill_val, u32 len, u32 block);
-void queue_data_file(const char *filename, off64_t offset, u32 len,
-	u32 block);
 void for_each_data_block(data_block_callback_t data_func,
 	data_block_file_callback_t file_func,
-	data_block_fill_callback_t fill_func, void *priv);
-void free_data_blocks();
+	data_block_fill_callback_t fill_func, void *priv, unsigned int);
 
 #endif
diff --git a/ext4_utils/img2simg.c b/ext4_utils/libsparse/img2simg.c
index 3b466132..a1594df6 100644
--- a/ext4_utils/img2simg.c
+++ b/ext4_utils/libsparse/img2simg.c
@@ -18,7 +18,6 @@
 #define DEFAULT_CHUNK_SIZE	"64M"
 #define DEFAULT_SUFFIX		"%03d"
 
-#include "ext4_utils.h"
 #include "sparse_format.h"
 #if 0 /* endian.h is not on all platforms */
 # include <endian.h>
diff --git a/ext4_utils/libsparse/include/sparse/sparse.h b/ext4_utils/libsparse/include/sparse/sparse.h
new file mode 100644
index 00000000..11093748
--- /dev/null
+++ b/ext4_utils/libsparse/include/sparse/sparse.h
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2012 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.
+ */
+
+#ifndef _LIBSPARSE_SPARSE_H_
+#define _LIBSPARSE_SPARSE_H_
+
+#define _FILE_OFFSET_BITS 64
+#define _LARGEFILE64_SOURCE 1
+#include <sys/types.h>
+#include <unistd.h>
+
+#if defined(__APPLE__) && defined(__MACH__)
+#define off64_t off_t
+#endif
+
+void write_sparse_image(int fd, int gz, int sparse, int crc, unsigned int block_size, off64_t len);
+void queue_data_block(void *data, unsigned int len, unsigned int block);
+void queue_fill_block(unsigned int fill_val, unsigned int len, unsigned int block);
+void queue_data_file(const char *filename, off64_t offset, unsigned int len,
+		unsigned int block);
+void free_data_blocks();
+
+#endif
diff --git a/ext4_utils/output_file.c b/ext4_utils/libsparse/output_file.c
index 40655a92..6520e63f 100644
--- a/ext4_utils/output_file.c
+++ b/ext4_utils/libsparse/output_file.c
@@ -14,15 +14,16 @@
  * limitations under the License.
  */
 
-#include "ext4_utils.h"
+#include <sparse/sparse.h>
+
 #include "output_file.h"
 #include "sparse_format.h"
 #include "sparse_crc32.h"
-#include "wipe.h"
 
 #include <fcntl.h>
 #include <stdbool.h>
-#include <sys/types.h>
+#include <stdlib.h>
+#include <string.h>
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <unistd.h>
@@ -33,10 +34,19 @@
 #define O_BINARY 0
 #endif
 
-
 #if defined(__APPLE__) && defined(__MACH__)
 #define lseek64 lseek
-#define off64_t off_t
+#define ftruncate64 ftruncate
+#define mmap64 mmap
+#endif
+
+#ifdef __BIONIC__
+extern void*  __mmap2(void *, size_t, int, int, int, off_t);
+static inline void *mmap64(void *addr, size_t length, int prot, int flags,
+        int fd, off64_t offset)
+{
+    return __mmap2(addr, length, prot, flags, fd, offset >> 12);
+}
 #endif
 
 #define SPARSE_HEADER_MAJOR_VER 1
@@ -55,11 +65,13 @@ struct output_file {
 	gzFile gz_fd;
 	bool close_fd;
 	int sparse;
-	u64 cur_out_ptr;
+	off64_t cur_out_ptr;
 	u32 chunk_cnt;
 	u32 crc32;
 	struct output_file_ops *ops;
 	int use_crc;
+	unsigned int block_size;
+	off64_t len;
 };
 
 static int file_seek(struct output_file *out, off64_t off)
@@ -162,16 +174,16 @@ static int emit_skip_chunk(struct output_file *out, u64 skip_len)
 
 	//DBG printf("skip chunk: 0x%llx bytes\n", skip_len);
 
-	if (skip_len % info.block_size) {
+	if (skip_len % out->block_size) {
 		error("don't care size %llu is not a multiple of the block size %u",
-				skip_len, info.block_size);
+				skip_len, out->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.chunk_sz = skip_len / out->block_size;
 	chunk_header.total_sz = CHUNK_HEADER_LEN;
 	ret = out->ops->write(out, (u8 *)&chunk_header, sizeof(chunk_header));
 	if (ret < 0)
@@ -183,7 +195,7 @@ static int emit_skip_chunk(struct output_file *out, u64 skip_len)
 	return 0;
 }
 
-static int write_chunk_fill(struct output_file *out, u64 off, u32 fill_val, int len)
+static int write_chunk_fill(struct output_file *out, off64_t off, u32 fill_val, int len)
 {
 	chunk_header_t chunk_header;
 	int rnd_up_len, zero_len, count;
@@ -210,9 +222,9 @@ static int write_chunk_fill(struct output_file *out, u64 off, u32 fill_val, int
 		emit_skip_chunk(out, off - out->cur_out_ptr);
 	}
 
-	if (off % info.block_size) {
+	if (off % out->block_size) {
 		error("write chunk offset %llu is not a multiple of the block size %u",
-				off, info.block_size);
+				off, out->block_size);
 		return -1;
 	}
 
@@ -222,12 +234,12 @@ static int write_chunk_fill(struct output_file *out, u64 off, u32 fill_val, int
 	}
 
 	/* Round up the file length to a multiple of the block size */
-	rnd_up_len = (len + (info.block_size - 1)) & (~(info.block_size -1));
+	rnd_up_len = (len + (out->block_size - 1)) & (~(out->block_size -1));
 
 	/* Finally we can safely emit a chunk of data */
 	chunk_header.chunk_type = CHUNK_TYPE_FILL;
 	chunk_header.reserved1 = 0;
-	chunk_header.chunk_sz = rnd_up_len / info.block_size;
+	chunk_header.chunk_sz = rnd_up_len / out->block_size;
 	chunk_header.total_sz = CHUNK_HEADER_LEN + sizeof(fill_val);
 	ret = out->ops->write(out, (u8 *)&chunk_header, sizeof(chunk_header));
 
@@ -239,13 +251,13 @@ static int write_chunk_fill(struct output_file *out, u64 off, u32 fill_val, int
 
 	if (out->use_crc) {
                 /* Initialize fill_buf with the fill_val */
-		for (i = 0; i < (info.block_size / sizeof(u32)); i++) {
+		for (i = 0; i < (out->block_size / sizeof(u32)); i++) {
 			fill_buf[i] = fill_val;
 		}
 
 		count = chunk_header.chunk_sz;
 		while (count) {
-			out->crc32 = sparse_crc32(out->crc32, fill_buf, info.block_size);
+			out->crc32 = sparse_crc32(out->crc32, fill_buf, out->block_size);
 			count--;
 		}
 	}
@@ -256,7 +268,7 @@ static int write_chunk_fill(struct output_file *out, u64 off, u32 fill_val, int
 	return 0;
 }
 
-static int write_chunk_raw(struct output_file *out, u64 off, u8 *data, int len)
+static int write_chunk_raw(struct output_file *out, off64_t off, u8 *data, int len)
 {
 	chunk_header_t chunk_header;
 	int rnd_up_len, zero_len;
@@ -281,9 +293,9 @@ static int write_chunk_raw(struct output_file *out, u64 off, u8 *data, int len)
 		emit_skip_chunk(out, off - out->cur_out_ptr);
 	}
 
-	if (off % info.block_size) {
+	if (off % out->block_size) {
 		error("write chunk offset %llu is not a multiple of the block size %u",
-				off, info.block_size);
+				off, out->block_size);
 		return -1;
 	}
 
@@ -293,13 +305,13 @@ static int write_chunk_raw(struct output_file *out, u64 off, u8 *data, int len)
 	}
 
 	/* Round up the file length to a multiple of the block size */
-	rnd_up_len = (len + (info.block_size - 1)) & (~(info.block_size -1));
+	rnd_up_len = (len + (out->block_size - 1)) & (~(out->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.chunk_sz = rnd_up_len / out->block_size;
 	chunk_header.total_sz = CHUNK_HEADER_LEN + rnd_up_len;
 	ret = out->ops->write(out, (u8 *)&chunk_header, sizeof(chunk_header));
 
@@ -351,8 +363,8 @@ void close_output_file(struct output_file *out)
 	out->ops->close(out);
 }
 
-struct output_file *open_output_fd(int fd, int gz, int sparse,
-        int chunks, int crc, int wipe)
+struct output_file *open_output_fd(int fd, unsigned int block_size, off64_t len,
+		int gz, int sparse, int chunks, int crc)
 {
 	int ret;
 	struct output_file *out = malloc(sizeof(struct output_file));
@@ -360,13 +372,13 @@ struct output_file *open_output_fd(int fd, int gz, int sparse,
 		error_errno("malloc struct out");
 		return NULL;
 	}
-	zero_buf = malloc(info.block_size);
+	zero_buf = malloc(out->block_size);
 	if (!zero_buf) {
 		error_errno("malloc zero_buf");
 		free(out);
 		return NULL;
 	}
-	memset(zero_buf, '\0', info.block_size);
+	memset(zero_buf, '\0', out->block_size);
 
 	if (gz) {
 		out->ops = &gz_file_ops;
@@ -389,12 +401,12 @@ struct output_file *open_output_fd(int fd, int gz, int sparse,
 	out->crc32 = 0;
 	out->use_crc = crc;
 
-	if (wipe)
-		wipe_block_device(out->fd, info.len);
+	out->len = len;
+	out->block_size = block_size;
 
 	if (out->sparse) {
-		sparse_header.blk_sz = info.block_size,
-		sparse_header.total_blks = info.len / info.block_size,
+		sparse_header.blk_sz = out->block_size,
+		sparse_header.total_blks = out->len / out->block_size,
 		sparse_header.total_chunks = chunks;
 		if (out->use_crc)
 			sparse_header.total_chunks++;
@@ -407,9 +419,10 @@ struct output_file *open_output_fd(int fd, int gz, int sparse,
 	return out;
 }
 
-struct output_file *open_output_file(const char *filename, int gz, int sparse,
-        int chunks, int crc, int wipe) {
-
+struct output_file *open_output_file(const char *filename,
+		unsigned int block_size, off64_t len,
+		int gz, int sparse, int chunks, int crc)
+{
 	int fd;
 	struct output_file *file;
 
@@ -423,7 +436,7 @@ struct output_file *open_output_file(const char *filename, int gz, int sparse,
 		fd = STDOUT_FILENO;
 	}
 
-	file = open_output_fd(fd, gz, sparse, chunks, crc, wipe);
+	file = open_output_fd(fd, block_size, len, gz, sparse, chunks, crc);
 	if (!file) {
 		close(fd);
 		return NULL;
@@ -434,13 +447,13 @@ struct output_file *open_output_file(const char *filename, int gz, int sparse,
 	return file;
 }
 
-void pad_output_file(struct output_file *out, u64 len)
+void pad_output_file(struct output_file *out, off64_t len)
 {
 	int ret;
 
-	if (len > (u64) info.len) {
+	if (len > out->len) {
 		error("attempted to pad file %llu bytes past end of filesystem",
-				len - info.len);
+				len - out->len);
 		return;
 	}
 	if (out->sparse) {
@@ -471,13 +484,13 @@ void pad_output_file(struct output_file *out, u64 len)
 }
 
 /* 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)
+void write_data_block(struct output_file *out, off64_t off, void *data, int len)
 {
 	int ret;
 
-	if (off + len > (u64) info.len) {
+	if (off + len > out->len) {
 		error("attempted to write block %llu past end of filesystem",
-				off + len - info.len);
+				off + len - out->len);
 		return;
 	}
 
@@ -495,16 +508,16 @@ void write_data_block(struct output_file *out, u64 off, u8 *data, int len)
 }
 
 /* Write a contiguous region of data blocks with a fill value */
-void write_fill_block(struct output_file *out, u64 off, u32 fill_val, int len)
+void write_fill_block(struct output_file *out, off64_t off, unsigned int fill_val, int len)
 {
 	int ret;
 	unsigned int i;
 	int write_len;
 	u32 fill_buf[4096/sizeof(u32)]; /* Maximum size of a block */
 
-	if (off + len > (u64) info.len) {
+	if (off + len > out->len) {
 		error("attempted to write block %llu past end of filesystem",
-				off + len - info.len);
+				off + len - out->len);
 		return;
 	}
 
@@ -533,7 +546,7 @@ void write_fill_block(struct output_file *out, u64 off, u32 fill_val, int len)
 }
 
 /* Write a contiguous region of data blocks from a file */
-void write_data_file(struct output_file *out, u64 off, const char *file,
+void write_data_file(struct output_file *out, off64_t off, const char *file,
 		     off64_t offset, int len)
 {
 	int ret;
@@ -541,9 +554,9 @@ void write_data_file(struct output_file *out, u64 off, const char *file,
 	int aligned_diff;
 	int buffer_size;
 
-	if (off + len >= (u64) info.len) {
+	if (off + len >= out->len) {
 		error("attempted to write block %llu past end of filesystem",
-				off + len - info.len);
+				off + len - out->len);
 		return;
 	}
 
diff --git a/ext4_utils/output_file.h b/ext4_utils/libsparse/output_file.h
index a578c80f..9e822e35 100644
--- a/ext4_utils/output_file.h
+++ b/ext4_utils/libsparse/output_file.h
@@ -17,17 +17,20 @@
 #ifndef _OUTPUT_FILE_H_
 #define _OUTPUT_FILE_H_
 
+#include <sparse/sparse.h>
+
 struct output_file;
 
-struct output_file *open_output_file(const char *filename, int gz, int sparse,
-        int chunks, int crc, int wipe);
-struct output_file *open_output_fd(int fd, int gz, int sparse,
-        int chunks, int crc, int wipe);
-void write_data_block(struct output_file *out, u64 off, u8 *data, int len);
-void write_fill_block(struct output_file *out, u64 off, u32 fill_val, int len);
-void write_data_file(struct output_file *out, u64 off, const char *file,
+struct output_file *open_output_file(const char *filename,
+		unsigned int block_size, off64_t len,
+		int gz, int sparse, int chunks, int crc);
+struct output_file *open_output_fd(int fd, unsigned int block_size, off64_t len,
+		int gz, int sparse, int chunks, int crc);
+void write_data_block(struct output_file *out, off64_t off, void *data, int len);
+void write_fill_block(struct output_file *out, off64_t off, unsigned int fill_val, int len);
+void write_data_file(struct output_file *out, off64_t off, const char *file,
 		     off64_t offset, int len);
-void pad_output_file(struct output_file *out, u64 len);
+void pad_output_file(struct output_file *out, off64_t len);
 void close_output_file(struct output_file *out);
 
 #endif
diff --git a/ext4_utils/simg2img.c b/ext4_utils/libsparse/simg2img.c
index 12b92eb7..486b8054 100644
--- a/ext4_utils/simg2img.c
+++ b/ext4_utils/libsparse/simg2img.c
@@ -14,17 +14,24 @@
  * limitations under the License.
  */
 
-#include "ext4_utils.h"
+#define _FILE_OFFSET_BITS 64
+#define _LARGEFILE64_SOURCE 1
+#include <sys/types.h>
+#include <unistd.h>
+
+#include "sparse_defs.h"
 #include "sparse_format.h"
 #include "sparse_crc32.h"
 
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
 #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>
 
 #define COPY_BUF_SIZE (1024*1024)
 u8 *copybuf;
diff --git a/ext4_utils/simg_dump.py b/ext4_utils/libsparse/simg_dump.py
index 6ece31d0..6ece31d0 100755
--- a/ext4_utils/simg_dump.py
+++ b/ext4_utils/libsparse/simg_dump.py
diff --git a/ext4_utils/libsparse/sparse.c b/ext4_utils/libsparse/sparse.c
new file mode 100644
index 00000000..2c91a8ea
--- /dev/null
+++ b/ext4_utils/libsparse/sparse.c
@@ -0,0 +1,98 @@
+/*
+ * Copyright (C) 2012 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.
+ */
+
+#include "output_file.h"
+#include "backed_block.h"
+#include "sparse_defs.h"
+
+struct count_chunks {
+	unsigned int chunks;
+	off64_t cur_ptr;
+	unsigned int block_size;
+};
+
+static void count_data_block(void *priv, off64_t off, void *data, int len)
+{
+	struct count_chunks *count_chunks = priv;
+	if (off > count_chunks->cur_ptr)
+		count_chunks->chunks++;
+	count_chunks->cur_ptr = off + ALIGN(len, count_chunks->block_size);
+	count_chunks->chunks++;
+}
+
+static void count_fill_block(void *priv, off64_t off, unsigned int fill_val, int len)
+{
+	struct count_chunks *count_chunks = priv;
+	if (off > count_chunks->cur_ptr)
+		count_chunks->chunks++;
+	count_chunks->cur_ptr = off + ALIGN(len, count_chunks->block_size);
+	count_chunks->chunks++;
+}
+
+static void count_file_block(void *priv, off64_t off, const char *file,
+		off64_t offset, int len)
+{
+	struct count_chunks *count_chunks = priv;
+	if (off > count_chunks->cur_ptr)
+		count_chunks->chunks++;
+	count_chunks->cur_ptr = off + ALIGN(len, count_chunks->block_size);
+	count_chunks->chunks++;
+}
+
+static int count_sparse_chunks(unsigned int block_size, off64_t len)
+{
+	struct count_chunks count_chunks = {0, 0, block_size};
+
+	for_each_data_block(count_data_block, count_file_block, count_fill_block, &count_chunks, block_size);
+
+	if (count_chunks.cur_ptr != len)
+		count_chunks.chunks++;
+
+	return count_chunks.chunks;
+}
+
+static void ext4_write_data_block(void *priv, off64_t off, void *data, int len)
+{
+	write_data_block(priv, off, data, len);
+}
+
+static void ext4_write_fill_block(void *priv, off64_t off, unsigned int fill_val, int len)
+{
+	write_fill_block(priv, off, fill_val, len);
+}
+
+static void ext4_write_data_file(void *priv, off64_t off, const char *file,
+		off64_t offset, int len)
+{
+	write_data_file(priv, off, file, offset, len);
+}
+
+/* Write the filesystem image to a file */
+void write_sparse_image(int fd, int gz, int sparse, int crc, unsigned int block_size, off64_t len)
+{
+	int chunks = count_sparse_chunks(block_size, len);
+	struct output_file *out = open_output_fd(fd, block_size, len,
+			gz, sparse, chunks, crc);
+
+	if (!out)
+		return;
+
+	for_each_data_block(ext4_write_data_block, ext4_write_data_file, ext4_write_fill_block, out, block_size);
+
+	pad_output_file(out, len);
+
+	close_output_file(out);
+}
diff --git a/ext4_utils/sparse_crc32.c b/ext4_utils/libsparse/sparse_crc32.c
index 9336b1d8..38bfe4aa 100644
--- a/ext4_utils/sparse_crc32.c
+++ b/ext4_utils/libsparse/sparse_crc32.c
@@ -43,9 +43,9 @@
  */
 
 /* Code taken from FreeBSD 8 */
-#include "ext4_utils.h"
+#include <stdint.h>
 
-static u32 crc32_tab[] = {
+static uint32_t crc32_tab[] = {
         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
         0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
         0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
@@ -98,10 +98,10 @@ static u32 crc32_tab[] = {
  * in sys/libkern.h, where it can be inlined.
  */
 
-u32 sparse_crc32(u32 crc_in, const void *buf, int size)
+uint32_t sparse_crc32(uint32_t crc_in, const void *buf, int size)
 {
-        const u8 *p = buf;
-        u32 crc;
+        const uint8_t *p = buf;
+        uint32_t crc;
 
         crc = crc_in ^ ~0U;
         while (size--)
diff --git a/ext4_utils/sparse_crc32.h b/ext4_utils/libsparse/sparse_crc32.h
index 21625bac..21625bac 100644
--- a/ext4_utils/sparse_crc32.h
+++ b/ext4_utils/libsparse/sparse_crc32.h
diff --git a/ext4_utils/libsparse/sparse_defs.h b/ext4_utils/libsparse/sparse_defs.h
new file mode 100644
index 00000000..9f32d592
--- /dev/null
+++ b/ext4_utils/libsparse/sparse_defs.h
@@ -0,0 +1,48 @@
+/*
+ * 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.
+ */
+
+#ifndef _LIBSPARSE_SPARSE_DEFS_
+#define _LIBSPARSE_SPARSE_DEFS_
+
+#include <errno.h>
+#include <stdio.h>
+
+#define __le64 u64
+#define __le32 u32
+#define __le16 u16
+
+#define __be64 u64
+#define __be32 u32
+#define __be16 u16
+
+#define __u64 u64
+#define __u32 u32
+#define __u16 u16
+#define __u8 u8
+
+typedef unsigned long long u64;
+typedef signed long long s64;
+typedef unsigned int u32;
+typedef unsigned short int u16;
+typedef unsigned char u8;
+
+#define DIV_ROUND_UP(x, y) (((x) + (y) - 1)/(y))
+#define ALIGN(x, y) ((y) * DIV_ROUND_UP((x), (y)))
+
+#define error(fmt, args...) do { fprintf(stderr, "error: %s: " fmt "\n", __func__, ## args); } while (0)
+#define error_errno(s, args...) error(s ": %s", ##args, strerror(errno))
+
+#endif
diff --git a/ext4_utils/sparse_format.h b/ext4_utils/libsparse/sparse_format.h
index 6c62c34c..c41f12a5 100644
--- a/ext4_utils/sparse_format.h
+++ b/ext4_utils/libsparse/sparse_format.h
@@ -14,6 +14,10 @@
  * limitations under the License.
  */
 
+#ifndef _LIBSPARSE_SPARSE_FORMAT_H_
+#define _LIBSPARSE_SPARSE_FORMAT_H_
+#include "sparse_defs.h"
+
 typedef struct sparse_header {
   __le32	magic;		/* 0xed26ff3a */
   __le16	major_version;	/* (0x1) - reject images with higher major versions */
@@ -48,3 +52,4 @@ typedef struct chunk_header {
  *  For a CRC32 chunk, it's 4 bytes of CRC32
  */
 
+#endif
diff --git a/ext4_utils/make_ext4fs.c b/ext4_utils/make_ext4fs.c
index 6cd5adec..228c421e 100644
--- a/ext4_utils/make_ext4fs.c
+++ b/ext4_utils/make_ext4fs.c
@@ -15,12 +15,13 @@
  */
 
 #include "make_ext4fs.h"
-#include "output_file.h"
 #include "ext4_utils.h"
 #include "allocate.h"
 #include "contents.h"
 #include "uuid.h"
-#include "backed_block.h"
+#include "wipe.h"
+
+#include <sparse/sparse.h>
 
 #include <assert.h>
 #include <dirent.h>
@@ -456,7 +457,10 @@ int make_ext4fs_internal(int fd, 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(fd, gzip, sparse, crc, wipe);
+	if (wipe)
+		wipe_block_device(fd, info.len);
+
+	write_ext4_image(fd, gzip, sparse, crc);
 
 	return 0;
 }