system/core: move libsparse into system/core

This moves an exact copy of libsparse from
system/extras/ext4_utils/libsparse to system/core/libsparse in
preparation for linking tools in system/core against it.

Change-Id: If664e4fcfd6612844ac745589beb1517e7f9fe58

15 files changed, 2320 insertions, 0 deletions

diff --git a/libsparse/Android.mk b/libsparse/Android.mk
new file mode 100644
index 0000000..dbe4d18
--- /dev/null
+++ b/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/libsparse/backed_block.c b/libsparse/backed_block.c
new file mode 100644
index 0000000..2548138
--- /dev/null
+++ b/libsparse/backed_block.c
@@ -0,0 +1,179 @@
+/*
+ * 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.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "backed_block.h"
+#include "sparse_defs.h"
+
+struct data_block {
+	u32 block;
+	u32 len;
+	void *data;
+	const char *filename;
+	int64_t offset;
+	struct data_block *next;
+	u32 fill_val;
+	u8 fill;
+	u8 pad1;
+	u16 pad2;
+};
+
+static struct data_block *data_blocks = NULL;
+static struct data_block *last_used = NULL;
+
+static void queue_db(struct data_block *new_db)
+{
+	struct data_block *db;
+
+	if (data_blocks == NULL) {
+		data_blocks = new_db;
+		return;
+	}
+
+	if (data_blocks->block > new_db->block) {
+		new_db->next = data_blocks;
+		data_blocks = new_db;
+		return;
+	}
+
+	/* Optimization: blocks are mostly queued in sequence, so save the
+	   pointer to the last db that was added, and start searching from
+	   there if the next block number is higher */
+	if (last_used && new_db->block > last_used->block)
+		db = last_used;
+	else
+		db = data_blocks;
+	last_used = new_db;
+
+	for (; db->next && db->next->block < new_db->block; db = db->next)
+		;
+
+	if (db->next == NULL) {
+		db->next = new_db;
+	} else {
+		new_db->next = db->next;
+		db->next = new_db;
+	}
+}
+
+/* Queues a fill block of memory to be written to the specified data blocks */
+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) {
+		error_errno("malloc");
+		return;
+	}
+
+	db->block = block;
+	db->len = len;
+	db->fill = 1;
+	db->fill_val = fill_val;
+	db->data = NULL;
+	db->filename = NULL;
+	db->next = NULL;
+
+	queue_db(db);
+}
+
+/* Queues a block of memory to be written to the specified data blocks */
+void queue_data_block(void *data, unsigned int len, unsigned int block)
+{
+	struct data_block *db = malloc(sizeof(struct data_block));
+	if (db == NULL) {
+		error_errno("malloc");
+		return;
+	}
+
+	db->block = block;
+	db->len = len;
+	db->data = data;
+	db->filename = NULL;
+	db->fill = 0;
+	db->next = NULL;
+
+	queue_db(db);
+}
+
+/* Queues a chunk of a file on disk to be written to the specified data blocks */
+void queue_data_file(const char *filename, int64_t offset, unsigned int len,
+		unsigned int block)
+{
+	struct data_block *db = malloc(sizeof(struct data_block));
+	if (db == NULL) {
+		error_errno("malloc");
+		return;
+	}
+
+	db->block = block;
+	db->len = len;
+	db->filename = strdup(filename);
+	db->offset = offset;
+	db->data = NULL;
+	db->fill = 0;
+	db->next = NULL;
+
+	queue_db(db);
+}
+
+/* Iterates over the queued data blocks, calling data_func for each contiguous
+   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, unsigned int block_size)
+{
+	struct data_block *db;
+	u32 last_block = 0;
+
+	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, block_size) - 1;
+
+		if (db->filename)
+			file_func(priv, (u64)db->block * block_size, db->filename, db->offset, db->len);
+		else if (db->fill)
+			fill_func(priv, (u64)db->block * block_size, db->fill_val, db->len);
+		else
+			data_func(priv, (u64)db->block * block_size, db->data, db->len);
+	}
+}
+
+/* Frees the memory used by the linked list of data blocks */
+void free_data_blocks()
+{
+	if (!data_blocks) return;
+	struct data_block *db = data_blocks;
+	while (db) {
+		struct data_block *next = db->next;
+		free((void*)db->filename);
+
+                // There used to be a free() of db->data here, but it
+		// made the function crash since queue_data_block() is
+		// sometimes passed pointers it can't take ownership of
+		// (like a pointer into the middle of an allocated
+		// block).  It's not clear what the queue_data_block
+		// contract is supposed to be, but we'd rather leak
+		// memory than crash.
+
+		free(db);
+		db = next;
+	}
+	data_blocks = NULL;
+	last_used = NULL;
+}
diff --git a/libsparse/backed_block.h b/libsparse/backed_block.h
new file mode 100644
index 0000000..7b7c90a
--- /dev/null
+++ b/libsparse/backed_block.h
@@ -0,0 +1,39 @@
+/*
+ * 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 _BACKED_BLOCK_H_
+#define _BACKED_BLOCK_H_
+
+#include <sparse/sparse.h>
+
+typedef void (*data_block_callback_t)(void *priv, int64_t off, void *data, int len);
+typedef void (*data_block_fill_callback_t)(void *priv, int64_t off, unsigned int fill_val, int len);
+typedef void (*data_block_file_callback_t)(void *priv, int64_t off,
+					   const char *file, int64_t offset,
+					   int len);
+
+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, unsigned int);
+
+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, int64_t offset, unsigned int len,
+		unsigned int block);
+
+void free_data_blocks();
+
+#endif
diff --git a/libsparse/img2simg.c b/libsparse/img2simg.c
new file mode 100644
index 0000000..a1594df
--- /dev/null
+++ b/libsparse/img2simg.c
@@ -0,0 +1,327 @@
+/*
+ * Copyright (C) 2010-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.
+ */
+
+#define DEFAULT_BLOCK_SIZE	"4K"
+#define DEFAULT_CHUNK_SIZE	"64M"
+#define DEFAULT_SUFFIX		"%03d"
+
+#include "sparse_format.h"
+#if 0 /* endian.h is not on all platforms */
+# include <endian.h>
+#else
+  /* For now, just assume we're going to run on little-endian. */
+# define my_htole32(h) (h)
+# define my_htole16(h) (h)
+#endif
+#include <errno.h>
+#include <fcntl.h>
+#include <limits.h>
+#include <stdarg.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#define COPY_BUF_SIZE (1024*1024)
+static char *copy_buf;
+
+static const char *progname(const char *argv0)
+{
+    const char *prog_name;
+    if ((prog_name = strrchr(argv0, '/')))
+	return(prog_name + 1);	/* Advance beyond '/'. */
+    return(argv0);		/* No '/' in argv0, use it as is. */
+}
+
+static void error_exit(const char *fmt, ...)
+{
+    va_list ap;
+    va_start(ap, fmt);
+    vfprintf(stderr, fmt, ap);
+    fputc('\n', stderr);
+    va_end(ap);
+
+    exit(EXIT_FAILURE);
+}
+
+static void usage(const char *argv0, const char *error_fmt, ...)
+{
+    fprintf(stderr,
+	    "Usage: %s [OPTIONS] <raw_image_file>\n",
+	    progname(argv0));
+    fprintf(stderr, "The <raw_image_file> will be split into as many sparse\n");
+    fprintf(stderr, "files as needed.  Each sparse file will contain a single\n");
+    fprintf(stderr, "DONT CARE chunk to offset to the correct block and then\n");
+    fprintf(stderr, "a single RAW chunk containing a portion of the data from\n");
+    fprintf(stderr, "the raw image file.  The sparse files will be named by\n");
+    fprintf(stderr, "appending a number to the name of the raw image file.\n");
+    fprintf(stderr, "\n");
+    fprintf(stderr, "OPTIONS (Defaults are enclosed by square brackets):\n");
+    fprintf(stderr, "  -s SUFFIX      Format appended number with SUFFIX [%s]\n",
+	    DEFAULT_SUFFIX);
+    fprintf(stderr, "  -B SIZE        Use a block size of SIZE [%s]\n",
+	    DEFAULT_BLOCK_SIZE);
+    fprintf(stderr, "  -C SIZE        Use a chunk size of SIZE [%s]\n",
+	    DEFAULT_CHUNK_SIZE);
+    fprintf(stderr, "SIZE is a decimal integer that may optionally be\n");
+    fprintf(stderr, "followed by a suffix that specifies a multiplier for\n");
+    fprintf(stderr, "the integer:\n");
+    fprintf(stderr, "       c         1 byte (the default when omitted)\n");
+    fprintf(stderr, "       w         2 bytes\n");
+    fprintf(stderr, "       b         512 bytes\n");
+    fprintf(stderr, "       kB        1000 bytes\n");
+    fprintf(stderr, "       K         1024 bytes\n");
+    fprintf(stderr, "       MB        1000*1000 bytes\n");
+    fprintf(stderr, "       M         1024*1024 bytes\n");
+    fprintf(stderr, "       GB        1000*1000*1000 bytes\n");
+    fprintf(stderr, "       G         1024*1024*1024 bytes\n");
+
+    if (error_fmt && *error_fmt)
+    {
+	fprintf(stderr, "\n");
+	va_list ap;
+	va_start(ap, error_fmt);
+	vfprintf(stderr, error_fmt, ap);
+	va_end(ap);
+	fprintf(stderr, "\n");
+    }
+
+    exit(EXIT_FAILURE);
+}
+
+static void cpy_file(int out_fd, char *out_path, int in_fd, char *in_path,
+		     size_t len)
+{
+    ssize_t s, cpy_len = COPY_BUF_SIZE;
+
+    while (len) {
+	if (len < COPY_BUF_SIZE)
+	    cpy_len = len;
+
+	s = read(in_fd, copy_buf, cpy_len);
+	if (s < 0)
+	    error_exit("\"%s\": %s", in_path, strerror(errno));
+	if (!s)
+	    error_exit("\"%s\": Unexpected EOF", in_path);
+
+	cpy_len = s;
+
+	s = write(out_fd, copy_buf, cpy_len);
+	if (s < 0)
+	    error_exit("\"%s\": %s", out_path, strerror(errno));
+	if (s != cpy_len)
+	    error_exit("\"%s\": Short data write (%lu)", out_path,
+		       (unsigned long)s);
+
+	len -= cpy_len;
+    }
+}
+
+static int parse_size(const char *size_str, size_t *size)
+{
+    static const size_t MAX_SIZE_T = ~(size_t)0;
+    size_t mult;
+    unsigned long long int value;
+    const char *end;
+    errno = 0;
+    value = strtoull(size_str, (char **)&end, 10);
+    if (errno != 0 || end == size_str || value > MAX_SIZE_T)
+	return -1;
+    if (*end == '\0') {
+	*size = value;
+	return 0;
+    }
+    if (!strcmp(end, "c"))
+	mult = 1;
+    else if (!strcmp(end, "w"))
+	mult = 2;
+    else if (!strcmp(end, "b"))
+	mult = 512;
+    else if (!strcmp(end, "kB"))
+	mult = 1000;
+    else if (!strcmp(end, "K"))
+	mult = 1024;
+    else if (!strcmp(end, "MB"))
+	mult = (size_t)1000*1000;
+    else if (!strcmp(end, "M"))
+	mult = (size_t)1024*1024;
+    else if (!strcmp(end, "GB"))
+	mult = (size_t)1000*1000*1000;
+    else if (!strcmp(end, "G"))
+	mult = (size_t)1024*1024*1024;
+    else
+	return -1;
+
+    if (value > MAX_SIZE_T / mult)
+	return -1;
+    *size = value * mult;
+    return 0;
+}
+
+int main(int argc, char *argv[])
+{
+    char *suffix = DEFAULT_SUFFIX;
+    char *block_size_str = DEFAULT_BLOCK_SIZE;
+    char *chunk_size_str = DEFAULT_CHUNK_SIZE;
+    size_t block_size, chunk_size, blocks_per_chunk, to_write;
+    char *in_path, *out_path, *out_fmt;
+    int in_fd, out_fd;
+    struct stat in_st;
+    off_t left_to_write;
+    struct {
+	sparse_header_t sparse_hdr;
+	chunk_header_t dont_care_hdr;
+	chunk_header_t raw_hdr;
+    } file_hdr;
+    unsigned int file_count;
+    ssize_t s;
+    int i;
+
+    /* Parse the command line. */
+    while ((i = getopt(argc, argv, "s:B:C:")) != -1)
+    {
+	switch (i) {
+	case 's':
+	    suffix = optarg;
+	    break;
+	case 'B':
+	    block_size_str = optarg;
+	    break;
+	case 'C':
+	    chunk_size_str = optarg;
+	    break;
+	default:
+	    usage(argv[0], NULL);
+	    break;
+	}
+    }
+
+    if (parse_size(block_size_str, &block_size))
+	usage(argv[0], "Can not parse \"%s\" as a block size.",
+	      block_size_str);
+    if (block_size % 4096)
+	usage(argv[0], "Block size is not a multiple of 4096.");
+
+    if (parse_size(chunk_size_str, &chunk_size))
+	usage(argv[0], "Can not parse \"%s\" as a chunk size.",
+	      chunk_size_str);
+    if (chunk_size % block_size)
+	usage(argv[0], "Chunk size is not a multiple of the block size.");
+    blocks_per_chunk = chunk_size / block_size;
+
+    if ((argc - optind) != 1)
+	usage(argv[0], "Missing or extra arguments.");
+    in_path = argv[optind];
+
+    /* Open the input file and validate it. */
+    if ((in_fd = open(in_path, O_RDONLY)) < 0)
+	error_exit("open \"%s\": %s", in_path, strerror(errno));
+    if (fstat(in_fd, &in_st))
+	error_exit("fstat \"%s\": %s", in_path, strerror(errno));
+    left_to_write = in_st.st_size;
+    if (left_to_write % block_size)
+	error_exit(
+	    "\"%s\" size (%llu) is not a multiple of the block size (%llu).\n",
+	    in_path,
+	    (unsigned long long)left_to_write, (unsigned long long)block_size);
+
+    /* Get a buffer for copying the chunks. */
+    if ((copy_buf = malloc(COPY_BUF_SIZE)) == 0)
+	error_exit("malloc copy buffer: %s", strerror(errno));
+
+    /* Get a buffer for a sprintf format to form output paths. */
+    if ((out_fmt = malloc(sizeof("%s") + strlen(suffix))) == 0)
+	error_exit("malloc format buffer: %s", strerror(errno));
+    out_fmt[0] = '%';
+    out_fmt[1] = 's';
+    strcpy(out_fmt + 2, suffix);
+
+    /* Get a buffer for an output path. */
+    i = snprintf(copy_buf, COPY_BUF_SIZE, out_fmt, in_path, UINT_MAX);
+    if (i >= COPY_BUF_SIZE)
+	error_exit("Ridulously long suffix: %s", suffix);
+    if ((out_path = malloc(i + 1)) == 0)
+	error_exit("malloc output path buffer: %s", strerror(errno));
+
+    /*
+     * Each file gets a sparse_header, a Don't Care chunk to offset to
+     * where the data belongs and then a Raw chunk with the actual data.
+     */
+    memset((void *)&file_hdr.sparse_hdr, 0, sizeof(file_hdr.sparse_hdr));
+    file_hdr.sparse_hdr.magic = my_htole32(SPARSE_HEADER_MAGIC);
+    file_hdr.sparse_hdr.major_version = my_htole16(1);
+    file_hdr.sparse_hdr.minor_version = my_htole16(0);
+    file_hdr.sparse_hdr.file_hdr_sz = my_htole16(sizeof(sparse_header_t));
+    file_hdr.sparse_hdr.chunk_hdr_sz = my_htole16(sizeof(chunk_header_t));
+    file_hdr.sparse_hdr.blk_sz = my_htole32(block_size);
+    /* The total_blks will be set in the file loop below. */
+    file_hdr.sparse_hdr.total_chunks = my_htole32(2);
+    file_hdr.sparse_hdr.image_checksum = my_htole32(0); /* Typically unused. */
+
+    memset((void *)&file_hdr.dont_care_hdr, 0, sizeof(file_hdr.dont_care_hdr));
+    file_hdr.dont_care_hdr.chunk_type = my_htole16(CHUNK_TYPE_DONT_CARE);
+    /* The Don't Care's chunk_sz will be set in the file loop below. */
+    file_hdr.dont_care_hdr.total_sz = my_htole32(sizeof(chunk_header_t));
+
+    memset((void *)&file_hdr.raw_hdr, 0, sizeof(file_hdr.raw_hdr));
+    file_hdr.raw_hdr.chunk_type = my_htole16(CHUNK_TYPE_RAW);
+    file_hdr.raw_hdr.chunk_sz = my_htole32(blocks_per_chunk);
+    file_hdr.raw_hdr.total_sz = my_htole32(chunk_size + sizeof(chunk_header_t));
+
+    /* Loop through writing chunk_size to each of the output files. */
+    to_write = chunk_size;
+    for (file_count = 1; left_to_write ; file_count++) {
+	/* Fix up the headers on the last block. */
+	if (left_to_write < (off_t)chunk_size) {
+	    to_write = left_to_write;
+	    file_hdr.raw_hdr.chunk_sz = my_htole32(left_to_write / block_size);
+	    file_hdr.raw_hdr.total_sz = my_htole32(left_to_write
+						+ sizeof(chunk_header_t));
+	}
+
+	/* Form the pathname for this output file and open it. */
+	sprintf(out_path, out_fmt, in_path, file_count);
+	if ((out_fd = creat(out_path, 0666)) < 0)
+	    error_exit("\"%s\": %s", out_path, strerror(errno));
+
+	/* Update and write the headers to this output file. */
+	s = (file_count-1) * blocks_per_chunk;
+	file_hdr.dont_care_hdr.chunk_sz = my_htole32(s);
+	file_hdr.sparse_hdr.total_blks = my_htole32(s
+						+ (to_write / block_size));
+	s = write(out_fd, (void *)&file_hdr, sizeof(file_hdr));
+	if (s < 0)
+	    error_exit("\"%s\": %s", out_path, strerror(errno));
+	if (s != sizeof(file_hdr))
+	    error_exit("\"%s\": Short write (%lu)", out_path, (unsigned long)s);
+
+	/* Copy this chunk from the input file to the output file. */
+	cpy_file(out_fd, out_path, in_fd, in_path, to_write);
+
+	/* Close this output file and update the amount left to write. */
+	if (close(out_fd))
+	    error_exit("close \"%s\": %s", out_path, strerror(errno));
+	left_to_write -= to_write;
+    }
+
+    if (close(in_fd))
+	error_exit("close \"%s\": %s", in_path, strerror(errno));
+
+    exit(EXIT_SUCCESS);
+}
diff --git a/libsparse/include/sparse/sparse.h b/libsparse/include/sparse/sparse.h
new file mode 100644
index 0000000..db06884
--- /dev/null
+++ b/libsparse/include/sparse/sparse.h
@@ -0,0 +1,134 @@
+/*
+ * 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_
+
+#include <stdbool.h>
+#include <stdint.h>
+
+struct sparse_file;
+
+/**
+ * sparse_file_new - create a new sparse file cookie
+ *
+ * @block_size - minimum size of a chunk
+ * @len - size of the expanded sparse file.
+ *
+ * Creates a new sparse_file cookie that can be used to associate data
+ * blocks.  Can later be written to a file with a variety of options.
+ * block_size specifies the minimum size of a chunk in the file.  The maximum
+ * size of the file is 2**32 * block_size (16TB for 4k block size).
+ *
+ * Returns the sparse file cookie, or NULL on error.
+ */
+struct sparse_file *sparse_file_new(unsigned int block_size, int64_t len);
+
+/**
+ * sparse_file_destroy - destroy a sparse file cookie
+ *
+ * @s - sparse file cookie
+ *
+ * Destroys a sparse file cookie.  After destroy, all memory passed in to
+ * sparse_file_add_data can be freed by the caller
+ */
+void sparse_file_destroy(struct sparse_file *s);
+
+/**
+ * sparse_file_add_data - associate a data chunk with a sparse file
+ *
+ * @s - sparse file cookie
+ * @data - pointer to data block
+ * @len - length of the data block
+ * @block - offset in blocks into the sparse file to place the data chunk
+ *
+ * Associates a data chunk with a sparse file cookie.  The region
+ * [block * block_size : block * block_size + len) must not already be used in
+ * the sparse file. If len is not a multiple of the block size the data
+ * will be padded with zeros.
+ *
+ * The data pointer must remain valid until the sparse file is closed or the
+ * data block is removed from the sparse file.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_add_data(struct sparse_file *s,
+		void *data, unsigned int len, unsigned int block);
+
+/**
+ * sparse_file_add_fill - associate a fill chunk with a sparse file
+ *
+ * @s - sparse file cookie
+ * @fill_val - 32 bit fill data
+ * @len - length of the fill block
+ * @block - offset in blocks into the sparse file to place the fill chunk
+ *
+ * Associates a chunk filled with fill_val with a sparse file cookie.
+ * The region [block * block_size : block * block_size + len) must not already
+ * be used in the sparse file. If len is not a multiple of the block size the
+ * data will be padded with zeros.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_add_fill(struct sparse_file *s,
+		uint32_t fill_val, unsigned int len, unsigned int block);
+
+/**
+ * sparse_file_add_file - associate a chunk of a file with a sparse file
+ *
+ * @s - sparse file cookie
+ * @filename - filename of the file to be copied
+ * @file_offset - offset into the copied file
+ * @len - length of the copied block
+ * @block - offset in blocks into the sparse file to place the file chunk
+ *
+ * Associates a chunk of an existing file with a sparse file cookie.
+ * The region [block * block_size : block * block_size + len) must not already
+ * be used in the sparse file. If len is not a multiple of the block size the
+ * data will be padded with zeros.
+ *
+ * Allows adding large amounts of data to a sparse file without needing to keep
+ * it all mapped.  File size is limited by available virtual address space,
+ * exceptionally large files may need to be added in multiple chunks.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_add_file(struct sparse_file *s,
+		const char *filename, int64_t file_offset, unsigned int len,
+		unsigned int block);
+
+/**
+ * sparse_file_write - write a sparse file to a file
+ *
+ * @s - sparse file cookie
+ * @fd - file descriptor to write to
+ * @gz - write a gzipped file
+ * @sparse - write in the Android sparse file format
+ * @crc - append a crc chunk
+ *
+ * Writes a sparse file to a file.  If gz is true, the data will be passed
+ * through zlib.  If sparse is true, the file will be written in the Android
+ * sparse file format.  If sparse is false, the file will be written by seeking
+ * over unused chunks, producing a smaller file if the filesystem supports
+ * sparse files.  If crc is true, the crc of the expanded data will be
+ * calculated and appended in a crc chunk.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_write(struct sparse_file *s, int fd, bool gz, bool sparse,
+		bool crc);
+
+#endif
diff --git a/libsparse/output_file.c b/libsparse/output_file.c
new file mode 100644
index 0000000..2c4b557
--- /dev/null
+++ b/libsparse/output_file.c
@@ -0,0 +1,613 @@
+/*
+ * 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 _FILE_OFFSET_BITS 64
+#define _LARGEFILE64_SOURCE 1
+
+#include <fcntl.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include <zlib.h>
+
+#include "output_file.h"
+#include "sparse_format.h"
+#include "sparse_crc32.h"
+
+#ifndef USE_MINGW
+#include <sys/mman.h>
+#define O_BINARY 0
+#endif
+
+#if defined(__APPLE__) && defined(__MACH__)
+#define lseek64 lseek
+#define ftruncate64 ftruncate
+#define mmap64 mmap
+#define off64_t off_t
+#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
+#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 *, int64_t);
+	int (*write)(struct output_file *, u8 *, int);
+	void (*close)(struct output_file *);
+};
+
+struct output_file {
+	int fd;
+	gzFile gz_fd;
+	bool close_fd;
+	int sparse;
+	int64_t cur_out_ptr;
+	u32 chunk_cnt;
+	u32 crc32;
+	struct output_file_ops *ops;
+	int use_crc;
+	unsigned int block_size;
+	int64_t len;
+};
+
+static int file_seek(struct output_file *out, int64_t off)
+{
+	off64_t ret;
+
+	ret = lseek64(out->fd, off, SEEK_SET);
+	if (ret < 0) {
+		error_errno("lseek64");
+		return -1;
+	}
+	return 0;
+}
+
+static int file_write(struct output_file *out, u8 *data, int len)
+{
+	int ret;
+	ret = write(out->fd, data, len);
+	if (ret < 0) {
+		error_errno("write");
+		return -1;
+	} else if (ret < len) {
+		error("incomplete write");
+		return -1;
+	}
+
+	return 0;
+}
+
+static void file_close(struct output_file *out)
+{
+	if (out->close_fd) {
+		close(out->fd);
+	}
+}
+
+
+static struct output_file_ops file_ops = {
+	.seek = file_seek,
+	.write = file_write,
+	.close = file_close,
+};
+
+static int gz_file_seek(struct output_file *out, int64_t off)
+{
+	off64_t ret;
+
+	ret = gzseek(out->gz_fd, off, SEEK_SET);
+	if (ret < 0) {
+		error_errno("gzseek");
+		return -1;
+	}
+	return 0;
+}
+
+static int gz_file_write(struct output_file *out, u8 *data, int len)
+{
+	int ret;
+	ret = gzwrite(out->gz_fd, data, len);
+	if (ret < 0) {
+		error_errno("gzwrite");
+		return -1;
+	} else if (ret < len) {
+		error("incomplete gzwrite");
+		return -1;
+	}
+
+	return 0;
+}
+
+static void gz_file_close(struct output_file *out)
+{
+	gzclose(out->gz_fd);
+}
+
+static struct output_file_ops gz_file_ops = {
+	.seek = gz_file_seek,
+	.write = gz_file_write,
+	.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, chunk;
+
+	//DBG printf("skip chunk: 0x%llx bytes\n", skip_len);
+
+	if (skip_len % out->block_size) {
+		error("don't care size %llu is not a multiple of the block size %u",
+				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 / out->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;
+
+	out->cur_out_ptr += skip_len;
+	out->chunk_cnt++;
+
+	return 0;
+}
+
+static int write_chunk_fill(struct output_file *out, int64_t off, u32 fill_val, int len)
+{
+	chunk_header_t chunk_header;
+	int rnd_up_len, zero_len, count;
+	int ret;
+	unsigned int i;
+	u32 fill_buf[4096/sizeof(u32)]; /* Maximum size of a block */
+
+	/* 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 % out->block_size) {
+		error("write chunk offset %llu is not a multiple of the block size %u",
+				off, out->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 + (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 / out->block_size;
+	chunk_header.total_sz = CHUNK_HEADER_LEN + sizeof(fill_val);
+	ret = out->ops->write(out, (u8 *)&chunk_header, sizeof(chunk_header));
+
+	if (ret < 0)
+		return -1;
+	ret = out->ops->write(out, (u8 *)&fill_val, sizeof(fill_val));
+	if (ret < 0)
+		return -1;
+
+	if (out->use_crc) {
+                /* Initialize fill_buf with the fill_val */
+		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, out->block_size);
+			count--;
+		}
+	}
+
+	out->cur_out_ptr += rnd_up_len;
+	out->chunk_cnt++;
+
+	return 0;
+}
+
+static int write_chunk_raw(struct output_file *out, int64_t 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 % out->block_size) {
+		error("write chunk offset %llu is not a multiple of the block size %u",
+				off, out->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 + (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 / out->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;
+	}
+
+	if (out->use_crc) {
+		out->crc32 = sparse_crc32(out->crc32, data, len);
+		if (zero_len)
+			out->crc32 = sparse_crc32(out->crc32, zero_buf, zero_len);
+	}
+
+	out->cur_out_ptr += rnd_up_len;
+	out->chunk_cnt++;
+
+	return 0;
+}
+
+void close_output_file(struct output_file *out)
+{
+	int ret;
+	chunk_header_t chunk_header;
+
+	if (out->sparse) {
+		if (out->use_crc) {
+			chunk_header.chunk_type = CHUNK_TYPE_CRC32;
+			chunk_header.reserved1 = 0;
+			chunk_header.chunk_sz = 0;
+			chunk_header.total_sz = CHUNK_HEADER_LEN + 4;
+
+			out->ops->write(out, (u8 *)&chunk_header, sizeof(chunk_header));
+			out->ops->write(out, (u8 *)&out->crc32, 4);
+
+			out->chunk_cnt++;
+		}
+
+		if (out->chunk_cnt != sparse_header.total_chunks)
+			error("sparse chunk count did not match: %d %d", out->chunk_cnt,
+					sparse_header.total_chunks);
+	}
+	out->ops->close(out);
+}
+
+struct output_file *open_output_fd(int fd, unsigned int block_size, int64_t len,
+		int gz, int sparse, int chunks, int crc)
+{
+	int ret;
+	struct output_file *out = malloc(sizeof(struct output_file));
+	if (!out) {
+		error_errno("malloc struct out");
+		return NULL;
+	}
+	zero_buf = malloc(out->block_size);
+	if (!zero_buf) {
+		error_errno("malloc zero_buf");
+		free(out);
+		return NULL;
+	}
+	memset(zero_buf, '\0', out->block_size);
+
+	if (gz) {
+		out->ops = &gz_file_ops;
+		out->gz_fd = gzdopen(fd, "wb9");
+		if (!out->gz_fd) {
+			error_errno("gzopen");
+			free(out);
+			return NULL;
+		}
+	} else {
+		out->fd = fd;
+		out->ops = &file_ops;
+	}
+	out->close_fd = false;
+	out->sparse = sparse;
+	out->cur_out_ptr = 0ll;
+	out->chunk_cnt = 0;
+
+	/* Initialize the crc32 value */
+	out->crc32 = 0;
+	out->use_crc = crc;
+
+	out->len = len;
+	out->block_size = block_size;
+
+	if (out->sparse) {
+		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++;
+
+		ret = out->ops->write(out, (u8 *)&sparse_header, sizeof(sparse_header));
+		if (ret < 0)
+			return NULL;
+	}
+
+	return out;
+}
+
+struct output_file *open_output_file(const char *filename,
+		unsigned int block_size, int64_t len,
+		int gz, int sparse, int chunks, int crc)
+{
+	int fd;
+	struct output_file *file;
+
+	if (strcmp(filename, "-")) {
+		fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC | O_BINARY, 0644);
+		if (fd < 0) {
+			error_errno("open");
+			return NULL;
+		}
+	} else {
+		fd = STDOUT_FILENO;
+	}
+
+	file = open_output_fd(fd, block_size, len, gz, sparse, chunks, crc);
+	if (!file) {
+		close(fd);
+		return NULL;
+	}
+
+	file->close_fd = true; // we opened descriptor thus we responsible for closing it
+
+	return file;
+}
+
+void pad_output_file(struct output_file *out, int64_t len)
+{
+	int ret;
+
+	if (len > out->len) {
+		error("attempted to pad file %llu bytes past end of filesystem",
+				len - out->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.
+		 */
+		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, int64_t off, void *data, int len)
+{
+	int ret;
+
+	if (off + len > out->len) {
+		error("attempted to write block %llu past end of filesystem",
+				off + len - out->len);
+		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;
+	}
+}
+
+/* Write a contiguous region of data blocks with a fill value */
+void write_fill_block(struct output_file *out, int64_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 > out->len) {
+		error("attempted to write block %llu past end of filesystem",
+				off + len - out->len);
+		return;
+	}
+
+	if (out->sparse) {
+		write_chunk_fill(out, off, fill_val, len);
+	} else {
+		/* Initialize fill_buf with the fill_val */
+		for (i = 0; i < sizeof(fill_buf)/sizeof(u32); i++) {
+			fill_buf[i] = fill_val;
+		}
+
+		ret = out->ops->seek(out, off);
+		if (ret < 0)
+			return;
+
+		while (len) {
+			write_len = (len > (int)sizeof(fill_buf) ? (int)sizeof(fill_buf) : len);
+			ret = out->ops->write(out, (u8 *)fill_buf, write_len);
+			if (ret < 0) {
+				return;
+			} else {
+				len -= write_len;
+			}
+		}
+	}
+}
+
+/* Write a contiguous region of data blocks from a file */
+void write_data_file(struct output_file *out, int64_t off, const char *file,
+		int64_t offset, int len)
+{
+	int ret;
+	int64_t aligned_offset;
+	int aligned_diff;
+	int buffer_size;
+
+	if (off + len >= out->len) {
+		error("attempted to write block %llu past end of filesystem",
+				off + len - out->len);
+		return;
+	}
+
+	int file_fd = open(file, O_RDONLY | O_BINARY);
+	if (file_fd < 0) {
+		error_errno("open");
+		return;
+	}
+
+	aligned_offset = offset & ~(4096 - 1);
+	aligned_diff = offset - aligned_offset;
+	buffer_size = len + aligned_diff;
+
+#ifndef USE_MINGW
+	u8 *data = mmap64(NULL, buffer_size, PROT_READ, MAP_SHARED, file_fd,
+			aligned_offset);
+	if (data == MAP_FAILED) {
+		error_errno("mmap64");
+		close(file_fd);
+		return;
+	}
+#else
+	u8 *data = malloc(buffer_size);
+	if (!data) {
+		error_errno("malloc");
+		close(file_fd);
+		return;
+	}
+	memset(data, 0, buffer_size);
+#endif
+
+	if (out->sparse) {
+		write_chunk_raw(out, off, data + aligned_diff, len);
+	} else {
+		ret = out->ops->seek(out, off);
+		if (ret < 0)
+			goto err;
+
+		ret = out->ops->write(out, data + aligned_diff, len);
+		if (ret < 0)
+			goto err;
+	}
+
+err:
+#ifndef USE_MINGW
+	munmap(data, buffer_size);
+#else
+	write(file_fd, data, buffer_size);
+	free(data);
+#endif
+	close(file_fd);
+}
diff --git a/libsparse/output_file.h b/libsparse/output_file.h
new file mode 100644
index 0000000..b12194f
--- /dev/null
+++ b/libsparse/output_file.h
@@ -0,0 +1,36 @@
+/*
+ * 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 _OUTPUT_FILE_H_
+#define _OUTPUT_FILE_H_
+
+#include <sparse/sparse.h>
+
+struct output_file;
+
+struct output_file *open_output_file(const char *filename,
+		unsigned int block_size, int64_t len,
+		int gz, int sparse, int chunks, int crc);
+struct output_file *open_output_fd(int fd, unsigned int block_size, int64_t len,
+		int gz, int sparse, int chunks, int crc);
+void write_data_block(struct output_file *out, int64_t off, void *data, int len);
+void write_fill_block(struct output_file *out, int64_t off, unsigned int fill_val, int len);
+void write_data_file(struct output_file *out, int64_t off, const char *file,
+		int64_t offset, int len);
+void pad_output_file(struct output_file *out, int64_t len);
+void close_output_file(struct output_file *out);
+
+#endif
diff --git a/libsparse/simg2img.c b/libsparse/simg2img.c
new file mode 100644
index 0000000..486b805
--- /dev/null
+++ b/libsparse/simg2img.c
@@ -0,0 +1,321 @@
+/*
+ * 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 _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>
+
+#define COPY_BUF_SIZE (1024*1024)
+u8 *copybuf;
+
+/* This will be malloc'ed with the size of blk_sz from the sparse file header */
+u8* zerobuf;
+
+#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");
+}
+
+static int read_all(int fd, void *buf, size_t len)
+{
+	size_t total = 0;
+	int ret;
+	char *ptr = buf;
+
+	while (total < len) {
+		ret = read(fd, ptr, len - total);
+
+		if (ret < 0)
+			return ret;
+
+		if (ret == 0)
+			return total;
+
+		ptr += ret;
+		total += ret;
+	}
+
+	return total;
+}
+
+static int write_all(int fd, void *buf, size_t len)
+{
+	size_t total = 0;
+	int ret;
+	char *ptr = buf;
+
+	while (total < len) {
+		ret = write(fd, ptr, len - total);
+
+		if (ret < 0)
+			return ret;
+
+		if (ret == 0)
+			return total;
+
+		ptr += ret;
+		total += ret;
+	}
+
+	return total;
+}
+
+int process_raw_chunk(int in, int out, u32 blocks, u32 blk_sz, u32 *crc32)
+{
+	u64 len = (u64)blocks * blk_sz;
+	int ret;
+	int chunk;
+
+	while (len) {
+		chunk = (len > COPY_BUF_SIZE) ? COPY_BUF_SIZE : len;
+		ret = read_all(in, copybuf, chunk);
+		if (ret != chunk) {
+			fprintf(stderr, "read returned an error copying a raw chunk: %d %d\n",
+					ret, chunk);
+			exit(-1);
+		}
+		*crc32 = sparse_crc32(*crc32, copybuf, chunk);
+		ret = write_all(out, copybuf, chunk);
+		if (ret != chunk) {
+			fprintf(stderr, "write returned an error copying a raw chunk\n");
+			exit(-1);
+		}
+		len -= chunk;
+	}
+
+	return blocks;
+}
+
+
+int process_fill_chunk(int in, int out, u32 blocks, u32 blk_sz, u32 *crc32)
+{
+	u64 len = (u64)blocks * blk_sz;
+	int ret;
+	int chunk;
+	u32 fill_val;
+	u32 *fillbuf;
+	unsigned int i;
+
+	/* Fill copy_buf with the fill value */
+	ret = read_all(in, &fill_val, sizeof(fill_val));
+	fillbuf = (u32 *)copybuf;
+	for (i = 0; i < (COPY_BUF_SIZE / sizeof(fill_val)); i++) {
+		fillbuf[i] = fill_val;
+	}
+
+	while (len) {
+		chunk = (len > COPY_BUF_SIZE) ? COPY_BUF_SIZE : len;
+		*crc32 = sparse_crc32(*crc32, copybuf, chunk);
+		ret = write_all(out, copybuf, chunk);
+		if (ret != chunk) {
+			fprintf(stderr, "write returned an error copying a raw chunk\n");
+			exit(-1);
+		}
+		len -= chunk;
+	}
+
+	return blocks;
+}
+
+int process_skip_chunk(int 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;
+
+	lseek64(out, len, SEEK_CUR);
+
+	return blocks;
+}
+
+int process_crc32_chunk(int in, u32 crc32)
+{
+	u32 file_crc32;
+	int ret;
+
+	ret = read_all(in, &file_crc32, 4);
+	if (ret != 4) {
+		fprintf(stderr, "read returned an error copying a crc32 chunk\n");
+		exit(-1);
+	}
+
+	if (file_crc32 != crc32) {
+		fprintf(stderr, "computed crc32 of 0x%8.8x, expected 0x%8.8x\n",
+			 crc32, file_crc32);
+		exit(-1);
+	}
+
+	return 0;
+}
+
+int main(int argc, char *argv[])
+{
+	int in;
+	int out;
+	unsigned int i;
+	sparse_header_t sparse_header;
+	chunk_header_t chunk_header;
+	u32 crc32 = 0;
+	u32 total_blocks = 0;
+	int ret;
+
+	if (argc != 3) {
+		usage();
+		exit(-1);
+	}
+
+	if ( (copybuf = malloc(COPY_BUF_SIZE)) == 0) {
+		fprintf(stderr, "Cannot malloc copy buf\n");
+		exit(-1);
+	}
+
+	if (strcmp(argv[1], "-") == 0) {
+		in = STDIN_FILENO;
+	} else {
+		if ((in = open(argv[1], O_RDONLY)) == 0) {
+			fprintf(stderr, "Cannot open input file %s\n", argv[1]);
+			exit(-1);
+		}
+	}
+
+	if (strcmp(argv[2], "-") == 0) {
+		out = STDOUT_FILENO;
+	} else {
+		if ((out = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, 0666)) == 0) {
+			fprintf(stderr, "Cannot open output file %s\n", argv[2]);
+			exit(-1);
+		}
+	}
+
+	ret = read_all(in, &sparse_header, sizeof(sparse_header));
+	if (ret != sizeof(sparse_header)) {
+		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.
+		 */
+		lseek64(in, sparse_header.file_hdr_sz - SPARSE_HEADER_LEN, SEEK_CUR);
+	}
+
+	if ( (zerobuf = malloc(sparse_header.blk_sz)) == 0) {
+		fprintf(stderr, "Cannot malloc zero buf\n");
+		exit(-1);
+	}
+
+	for (i=0; i<sparse_header.total_chunks; i++) {
+		ret = read_all(in, &chunk_header, sizeof(chunk_header));
+		if (ret != sizeof(chunk_header)) {
+			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.
+			 */
+			lseek64(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_FILL:
+			if (chunk_header.total_sz != (sparse_header.chunk_hdr_sz + sizeof(u32)) ) {
+				fprintf(stderr, "Bogus chunk size for chunk %d, type Fill\n", i);
+				exit(-1);
+			}
+			total_blocks += process_fill_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;
+		    case CHUNK_TYPE_CRC32:
+			process_crc32_chunk(in, crc32);
+			break;
+		    default:
+			fprintf(stderr, "Unknown chunk type 0x%4.4x\n", chunk_header.chunk_type);
+		}
+
+	}
+
+	/* 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.
+	 */
+	if (ftruncate64(out, (u64)total_blocks * sparse_header.blk_sz)) {
+		fprintf(stderr, "Error calling ftruncate() to set the image size\n");
+		exit(-1);
+	}
+
+	close(in);
+	close(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);
+	}
+
+	exit(0);
+}
+
diff --git a/libsparse/simg_dump.py b/libsparse/simg_dump.py
new file mode 100755
index 0000000..6ece31d
--- /dev/null
+++ b/libsparse/simg_dump.py
@@ -0,0 +1,169 @@
+#! /usr/bin/env python
+
+# 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.
+
+from __future__ import print_function
+import getopt, posixpath, signal, struct, sys
+
+def usage(argv0):
+  print("""
+Usage: %s [-v] sparse_image_file ...
+ -v             verbose output
+""" % ( argv0 ))
+  sys.exit(2)
+
+def main():
+
+  signal.signal(signal.SIGPIPE, signal.SIG_DFL)
+
+  me = posixpath.basename(sys.argv[0])
+
+  # Parse the command line
+  verbose = 0			# -v
+  try:
+    opts, args = getopt.getopt(sys.argv[1:],
+                               "v",
+                               ["verbose"])
+  except getopt.GetoptError, e:
+    print(e)
+    usage(me)
+  for o, a in opts:
+    if o in ("-v", "--verbose"):
+      verbose += 1
+    else:
+      print("Unrecognized option \"%s\"" % (o))
+      usage(me)
+
+  if len(args) == 0:
+    print("No sparse_image_file specified")
+    usage(me)
+
+  for path in args:
+    FH = open(path, 'rb')
+    header_bin = FH.read(28)
+    header = struct.unpack("<I4H4I", header_bin)
+
+    magic = header[0]
+    major_version = header[1]
+    minor_version = header[2]
+    file_hdr_sz = header[3]
+    chunk_hdr_sz = header[4]
+    blk_sz = header[5]
+    total_blks = header[6]
+    total_chunks = header[7]
+    image_checksum = header[8]
+
+    if magic != 0xED26FF3A:
+      print("%s: %s: Magic should be 0xED26FF3A but is 0x%08X"
+            % (me, path, magic))
+      continue
+    if major_version != 1 or minor_version != 0:
+      print("%s: %s: I only know about version 1.0, but this is version %u.%u"
+            % (me, path, major_version, minor_version))
+      continue
+    if file_hdr_sz != 28:
+      print("%s: %s: The file header size was expected to be 28, but is %u."
+            % (me, path, file_hdr_sz))
+      continue
+    if chunk_hdr_sz != 12:
+      print("%s: %s: The chunk header size was expected to be 12, but is %u."
+            % (me, path, chunk_hdr_sz))
+      continue
+
+    print("%s: Total of %u %u-byte output blocks in %u input chunks."
+          % (path, total_blks, blk_sz, total_chunks))
+
+    if image_checksum != 0:
+      print("checksum=0x%08X" % (image_checksum))
+
+    if not verbose:
+      continue
+    print("            input_bytes      output_blocks")
+    print("chunk    offset     number  offset  number")
+    offset = 0
+    for i in xrange(1,total_chunks+1):
+      header_bin = FH.read(12)
+      header = struct.unpack("<2H2I", header_bin)
+      chunk_type = header[0]
+      reserved1 = header[1]
+      chunk_sz = header[2]
+      total_sz = header[3]
+      data_sz = total_sz - 12
+
+      print("%4u %10u %10u %7u %7u" % (i, FH.tell(), data_sz, offset, chunk_sz),
+            end=" ")
+
+      if chunk_type == 0xCAC1:
+        if data_sz != (chunk_sz * blk_sz):
+          print("Raw chunk input size (%u) does not match output size (%u)"
+                % (data_sz, chunk_sz * blk_sz))
+          break;
+        else:
+          print("Raw data", end="")
+          FH.read(data_sz)
+      elif chunk_type == 0xCAC2:
+        if data_sz != 4:
+          print("Fill chunk should have 4 bytes of fill, but this has %u"
+                % (data_sz), end="")
+          break;
+        else:
+          fill_bin = FH.read(4)
+          fill = struct.unpack("<I", fill_bin)
+          print("Fill with 0x%08X" % (fill))
+      elif chunk_type == 0xCAC3:
+        if data_sz != 0:
+          print("Don't care chunk input size is non-zero (%u)" % (data_sz))
+          break;
+        else:
+          print("Don't care", end="")
+      elif chunk_type == 0xCAC4:
+        if data_sz != 4:
+          print("CRC32 chunk should have 4 bytes of CRC, but this has %u"
+                % (data_sz), end="")
+          break;
+        else:
+          crc_bin = FH.read(4)
+          crc = struct.unpack("<I", crc)
+          print("Unverified CRC32 0x%08X" % (crc))
+      else:
+          print("Unknown chunk type 0x%04X" % (chunk_type), end="")
+          break;
+
+      if verbose > 1:
+        header = struct.unpack("<12B", header_bin)
+        print(" (%02X%02X %02X%02X %02X%02X%02X%02X %02X%02X%02X%02X)"
+              % (header[0], header[1], header[2], header[3],
+                 header[4], header[5], header[6], header[7],
+                 header[8], header[9], header[10], header[11]))
+      else:
+        print()
+
+      offset += chunk_sz
+
+    print("     %10u            %7u         End" % (FH.tell(), offset))
+
+    if total_blks != offset:
+      print("The header said we should have %u output blocks, but we saw %u"
+            % (total_blks, offset))
+
+    junk_len = len(FH.read())
+    if junk_len:
+      print("There were %u bytes of extra data at the end of the file."
+            % (junk_len))
+
+  sys.exit(0)
+
+if __name__ == "__main__":
+  main()
diff --git a/libsparse/sparse.c b/libsparse/sparse.c
new file mode 100644
index 0000000..d6f5561
--- /dev/null
+++ b/libsparse/sparse.c
@@ -0,0 +1,154 @@
+/*
+ * 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 <stdlib.h>
+
+#include <sparse/sparse.h>
+
+#include "sparse_file.h"
+
+#include "output_file.h"
+#include "backed_block.h"
+#include "sparse_defs.h"
+
+
+struct sparse_file *sparse_file_new(unsigned int block_size, int64_t len)
+{
+	struct sparse_file *s = calloc(sizeof(struct sparse_file), 1);
+	if (!s) {
+		return NULL;
+	}
+
+	/* TODO: allocate backed block list */
+
+	s->block_size = block_size;
+	s->len = len;
+
+	return s;
+}
+
+void sparse_file_destroy(struct sparse_file *s)
+{
+	free_data_blocks();
+	free(s);
+}
+
+int sparse_file_add_data(struct sparse_file *s,
+		void *data, unsigned int len, unsigned int block)
+{
+	queue_data_block(data, len, block);
+
+	return 0;
+}
+
+int sparse_file_add_fill(struct sparse_file *s,
+		uint32_t fill_val, unsigned int len, unsigned int block)
+{
+	queue_fill_block(fill_val, len, block);
+
+	return 0;
+}
+
+int sparse_file_add_file(struct sparse_file *s,
+		const char *filename, int64_t file_offset, unsigned int len,
+		unsigned int block)
+{
+	queue_data_file(filename, file_offset, len, block);
+
+	return 0;
+}
+
+struct count_chunks {
+	unsigned int chunks;
+	int64_t cur_ptr;
+	unsigned int block_size;
+};
+
+static void count_data_block(void *priv, int64_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, int64_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, int64_t off, const char *file,
+		int64_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, int64_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, int64_t off, void *data, int len)
+{
+	write_data_block(priv, off, data, len);
+}
+
+static void ext4_write_fill_block(void *priv, int64_t off, unsigned int fill_val, int len)
+{
+	write_fill_block(priv, off, fill_val, len);
+}
+
+static void ext4_write_data_file(void *priv, int64_t off, const char *file,
+		int64_t offset, int len)
+{
+	write_data_file(priv, off, file, offset, len);
+}
+
+int sparse_file_write(struct sparse_file *s, int fd, bool gz, bool sparse,
+		bool crc)
+{
+	int chunks = count_sparse_chunks(s->block_size, s->len);
+	struct output_file *out = open_output_fd(fd, s->block_size, s->len,
+			gz, sparse, chunks, crc);
+
+	if (!out)
+		return -ENOMEM;
+
+	for_each_data_block(ext4_write_data_block, ext4_write_data_file, ext4_write_fill_block, out, s->block_size);
+
+	if (s->len)
+		pad_output_file(out, s->len);
+
+	close_output_file(out);
+
+	return 0;
+}
diff --git a/libsparse/sparse_crc32.c b/libsparse/sparse_crc32.c
new file mode 100644
index 0000000..38bfe4a
--- /dev/null
+++ b/libsparse/sparse_crc32.c
@@ -0,0 +1,111 @@
+/*-
+ *  COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or
+ *  code or tables extracted from it, as desired without restriction.
+ */
+
+/*
+ *  First, the polynomial itself and its table of feedback terms.  The
+ *  polynomial is
+ *  X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0
+ *
+ *  Note that we take it "backwards" and put the highest-order term in
+ *  the lowest-order bit.  The X^32 term is "implied"; the LSB is the
+ *  X^31 term, etc.  The X^0 term (usually shown as "+1") results in
+ *  the MSB being 1
+ *
+ *  Note that the usual hardware shift register implementation, which
+ *  is what we're using (we're merely optimizing it by doing eight-bit
+ *  chunks at a time) shifts bits into the lowest-order term.  In our
+ *  implementation, that means shifting towards the right.  Why do we
+ *  do it this way?  Because the calculated CRC must be transmitted in
+ *  order from highest-order term to lowest-order term.  UARTs transmit
+ *  characters in order from LSB to MSB.  By storing the CRC this way
+ *  we hand it to the UART in the order low-byte to high-byte; the UART
+ *  sends each low-bit to hight-bit; and the result is transmission bit
+ *  by bit from highest- to lowest-order term without requiring any bit
+ *  shuffling on our part.  Reception works similarly
+ *
+ *  The feedback terms table consists of 256, 32-bit entries.  Notes
+ *
+ *      The table can be generated at runtime if desired; code to do so
+ *      is shown later.  It might not be obvious, but the feedback
+ *      terms simply represent the results of eight shift/xor opera
+ *      tions for all combinations of data and CRC register values
+ *
+ *      The values must be right-shifted by eight bits by the "updcrc
+ *      logic; the shift must be unsigned (bring in zeroes).  On some
+ *      hardware you could probably optimize the shift in assembler by
+ *      using byte-swap instructions
+ *      polynomial $edb88320
+ *
+ *
+ * CRC32 code derived from work by Gary S. Brown.
+ */
+
+/* Code taken from FreeBSD 8 */
+#include <stdint.h>
+
+static uint32_t crc32_tab[] = {
+        0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
+        0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
+        0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
+        0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
+        0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
+        0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
+        0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
+        0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
+        0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
+        0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
+        0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
+        0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
+        0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
+        0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
+        0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
+        0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
+        0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
+        0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
+        0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
+        0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
+        0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
+        0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
+        0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
+        0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
+        0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
+        0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
+        0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
+        0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
+        0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
+        0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
+        0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
+        0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
+        0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
+        0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
+        0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
+        0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
+        0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
+        0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
+        0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
+        0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
+        0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
+        0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
+        0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
+};
+
+/*
+ * A function that calculates the CRC-32 based on the table above is
+ * given below for documentation purposes. An equivalent implementation
+ * of this function that's actually used in the kernel can be found
+ * in sys/libkern.h, where it can be inlined.
+ */
+
+uint32_t sparse_crc32(uint32_t crc_in, const void *buf, int size)
+{
+        const uint8_t *p = buf;
+        uint32_t crc;
+
+        crc = crc_in ^ ~0U;
+        while (size--)
+                crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
+        return crc ^ ~0U;
+}
+
diff --git a/libsparse/sparse_crc32.h b/libsparse/sparse_crc32.h
new file mode 100644
index 0000000..21625ba
--- /dev/null
+++ b/libsparse/sparse_crc32.h
@@ -0,0 +1,18 @@
+/*
+ * 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.
+ */
+
+u32 sparse_crc32(u32 crc, const void *buf, size_t size);
+
diff --git a/libsparse/sparse_defs.h b/libsparse/sparse_defs.h
new file mode 100644
index 0000000..9f32d59
--- /dev/null
+++ b/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/libsparse/sparse_file.h b/libsparse/sparse_file.h
new file mode 100644
index 0000000..05a78d9
--- /dev/null
+++ b/libsparse/sparse_file.h
@@ -0,0 +1,30 @@
+/*
+ * 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_FILE_H_
+#define _LIBSPARSE_SPARSE_FILE_H_
+
+#include <sparse/sparse.h>
+
+struct sparse_file {
+	unsigned int block_size;
+	int64_t len;
+
+	struct output_file *out;
+};
+
+
+#endif /* _LIBSPARSE_SPARSE_FILE_H_ */
diff --git a/libsparse/sparse_format.h b/libsparse/sparse_format.h
new file mode 100644
index 0000000..c41f12a
--- /dev/null
+++ b/libsparse/sparse_format.h
@@ -0,0 +1,55 @@
+/*
+ * 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_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 */
+  __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
+#define CHUNK_TYPE_CRC32    0xCAC4
+
+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 or CRC32 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.
+ *  For a CRC32 chunk, it's 4 bytes of CRC32
+ */
+
+#endif