ext4_utils: brought over from master

31 files changed, 5310 insertions, 0 deletions

diff --git a/ext4_utils/Android.mk b/ext4_utils/Android.mk
new file mode 100644
index 00000000..14702540
--- /dev/null
+++ b/ext4_utils/Android.mk
@@ -0,0 +1,81 @@
+# Copyright 2010 The Android Open Source Project
+
+LOCAL_PATH:= $(call my-dir)
+include $(CLEAR_VARS)
+
+libext4_utils_src_files := \
+	make_ext4fs.c \
+        ext4_utils.c \
+        allocate.c \
+        backed_block.c \
+        output_file.c \
+        contents.c \
+        extent.c \
+        indirect.c \
+        uuid.c \
+        sha1.c \
+
+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_PRELINK_MODULE := false
+
+include $(BUILD_SHARED_LIBRARY)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := $(libext4_utils_src_files)
+LOCAL_MODULE := libext4_utils
+LOCAL_MODULE_TAGS := optional
+LOCAL_C_INCLUDES += external/zlib
+LOCAL_STATIC_LIBRARIES := libz
+LOCAL_PRELINK_MODULE := false
+
+include $(BUILD_STATIC_LIBRARY)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := $(libext4_utils_src_files)
+LOCAL_MODULE := libext4_utils
+LOCAL_MODULE_TAGS := optional
+LOCAL_SHARED_LIBRARIES := libz
+
+include $(BUILD_HOST_STATIC_LIBRARY)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := make_ext4fs_main.c
+LOCAL_MODULE := make_ext4fs
+LOCAL_MODULE_TAGS := optional
+LOCAL_SHARED_LIBRARIES += libext4_utils libz
+
+include $(BUILD_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := make_ext4fs_main.c
+LOCAL_MODULE := make_ext4fs
+LOCAL_STATIC_LIBRARIES += libext4_utils libz
+
+include $(BUILD_HOST_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := simg2img.c
+LOCAL_MODULE := simg2img
+
+include $(BUILD_HOST_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_MODULE := mkuserimg.sh
+LOCAL_SRC_FILES := mkuserimg.sh
+LOCAL_MODULE_CLASS := EXECUTABLES
+# We don't need any additional suffix.
+LOCAL_MODULE_SUFFIX :=
+LOCAL_BUILT_MODULE_STEM := $(notdir $(LOCAL_SRC_FILES))
+LOCAL_IS_HOST_MODULE := true
+
+include $(BUILD_PREBUILT)
diff --git a/ext4_utils/MODULE_LICENSE_APACHE2 b/ext4_utils/MODULE_LICENSE_APACHE2
new file mode 100644
index 00000000..e69de29b
--- /dev/null
+++ b/ext4_utils/MODULE_LICENSE_APACHE2
diff --git a/ext4_utils/NOTICE b/ext4_utils/NOTICE
new file mode 100644
index 00000000..5d142934
--- /dev/null
+++ b/ext4_utils/NOTICE
@@ -0,0 +1,190 @@
+
+   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.
+
+   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.
+
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
diff --git a/ext4_utils/allocate.c b/ext4_utils/allocate.c
new file mode 100644
index 00000000..20ba1548
--- /dev/null
+++ b/ext4_utils/allocate.c
@@ -0,0 +1,747 @@
+/*
+ * 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 <stdio.h>
+#include <stdlib.h>
+
+#include "ext4_utils.h"
+#include "allocate.h"
+#include "backed_block.h"
+#include "ext4.h"
+
+struct region_list {
+	struct region *first;
+	struct region *last;
+	struct region *iter;
+	u32 partial_iter;
+};
+
+struct block_allocation {
+	struct region_list list;
+	struct region_list oob_list;
+};
+
+struct region {
+	u32 block;
+	u32 len;
+	int bg;
+	struct region *next;
+	struct region *prev;
+};
+
+struct block_group_info {
+	u32 first_block;
+	int header_blocks;
+	int data_blocks_used;
+	int has_superblock;
+	u8 *bitmaps;
+	u8 *block_bitmap;
+	u8 *inode_bitmap;
+	u8 *inode_table;
+	u32 free_blocks;
+	u32 first_free_block;
+	u32 free_inodes;
+	u32 first_free_inode;
+	u16 used_dirs;
+};
+
+struct block_allocation *create_allocation()
+{
+	struct block_allocation *alloc = malloc(sizeof(struct block_allocation));
+	alloc->list.first = NULL;
+	alloc->list.last = NULL;
+	alloc->oob_list.first = NULL;
+	alloc->oob_list.last = NULL;
+	alloc->list.iter = NULL;
+	alloc->list.partial_iter = 0;
+	alloc->oob_list.iter = NULL;
+	alloc->oob_list.partial_iter = 0;
+	return alloc;
+}
+
+static void region_list_remove(struct region_list *list, struct region *reg)
+{
+	if (reg->prev)
+		reg->prev->next = reg->next;
+
+	if (reg->next)
+		reg->next->prev = reg->prev;
+
+	if (list->first == reg)
+		list->first = reg->next;
+
+	if (list->last == reg)
+		list->last = reg->prev;
+
+	reg->next = NULL;
+	reg->prev = NULL;
+}
+
+static void region_list_append(struct region_list *list, struct region *reg)
+{
+	if (list->first == NULL) {
+		list->first = reg;
+		list->last = reg;
+		list->iter = reg;
+		list->partial_iter = 0;
+		reg->prev = NULL;
+	} else {
+		list->last->next = reg;
+		reg->prev = list->last;
+		list->last = reg;
+	}
+	reg->next = NULL;
+}
+
+#if 0
+static void dump_starting_from(struct region *reg)
+{
+	for (; reg; reg = reg->next) {
+		printf("%p: Blocks %d-%d (%d)\n", reg,
+				reg->bg * info.blocks_per_group + reg->block,
+				reg->bg * info.blocks_per_group + reg->block + reg->len - 1,
+				reg->len);
+	}
+}
+
+static void dump_region_lists(struct block_allocation *alloc) {
+
+	printf("Main list:\n");
+	dump_starting_from(alloc->list.first);
+
+	printf("OOB list:\n");
+	dump_starting_from(alloc->oob_list.first);
+}
+#endif
+
+void append_region(struct block_allocation *alloc,
+		u32 block, u32 len, int bg_num)
+{
+	struct region *reg;
+	reg = malloc(sizeof(struct region));
+	reg->block = block;
+	reg->len = len;
+	reg->bg = bg_num;
+	reg->next = NULL;
+
+	region_list_append(&alloc->list, reg);
+}
+
+static void allocate_bg_inode_table(struct block_group_info *bg)
+{
+	if (bg->inode_table != NULL)
+		return;
+
+	u32 block = bg->first_block + 2;
+
+	if (bg->has_superblock)
+		block += aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks + 1;
+
+	bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size);
+	if (bg->inode_table == NULL)
+		critical_error_errno("calloc");
+
+	queue_data_block(bg->inode_table, aux_info.inode_table_blocks
+			* info.block_size, block);
+}
+
+static int bitmap_set_bit(u8 *bitmap, u32 bit)
+{
+	if (bitmap[bit / 8] & 1 << (bit % 8))
+		return 1;
+
+	bitmap[bit / 8] |= 1 << (bit % 8);
+	return 0;
+}
+
+static int bitmap_set_8_bits(u8 *bitmap, u32 bit)
+{
+	int ret = bitmap[bit / 8];
+	bitmap[bit / 8] = 0xFF;
+	return ret;
+}
+
+/* Marks a the first num_blocks blocks in a block group as used, and accounts
+ for them in the block group free block info. */
+static int reserve_blocks(struct block_group_info *bg, u32 start, u32 num)
+{
+	unsigned int i = 0;
+
+	u32 block = start;
+	if (num > bg->free_blocks)
+		return -1;
+
+	for (i = 0; i < num && block % 8 != 0; i++, block++) {
+		if (bitmap_set_bit(bg->block_bitmap, block)) {
+			error("attempted to reserve already reserved block");
+			return -1;
+		}
+	}
+
+	for (; i + 8 <= (num & ~7); i += 8, block += 8) {
+		if (bitmap_set_8_bits(bg->block_bitmap, block)) {
+			error("attempted to reserve already reserved block");
+			return -1;
+		}
+	}
+
+	for (; i < num; i++, block++) {
+		if (bitmap_set_bit(bg->block_bitmap, block)) {
+			error("attempted to reserve already reserved block");
+			return -1;
+		}
+	}
+
+	bg->free_blocks -= num;
+	if (start == bg->first_free_block)
+		bg->first_free_block = start + num;
+
+	return 0;
+}
+
+static void free_blocks(struct block_group_info *bg, u32 num_blocks)
+{
+	unsigned int i;
+	u32 block = bg->first_free_block - 1;
+	for (i = 0; i < num_blocks; i++, block--)
+		bg->block_bitmap[block / 8] &= ~(1 << (block % 8));
+	bg->free_blocks += num_blocks;
+	bg->first_free_block -= num_blocks;
+}
+
+/* Reduces an existing allocation by len blocks by return the last blocks
+   to the free pool in their block group. Assumes that the blocks being
+   returned were the last ones allocated out of the block group */
+void reduce_allocation(struct block_allocation *alloc, u32 len)
+{
+	while (len) {
+		struct region *last_reg = alloc->list.last;
+
+		if (last_reg->len > len) {
+			free_blocks(&aux_info.bgs[last_reg->bg], len);
+			last_reg->len -= len;
+			len = 0;
+		} else {
+			struct region *reg = alloc->list.last->prev;
+			free_blocks(&aux_info.bgs[last_reg->bg], last_reg->len);
+			len -= last_reg->len;
+			if (reg) {
+				reg->next = NULL;
+			} else {
+				alloc->list.first = NULL;
+				alloc->list.last = NULL;
+				alloc->list.iter = NULL;
+				alloc->list.partial_iter = 0;
+			}
+			free(last_reg);
+		}
+	}
+}
+
+static void init_bg(struct block_group_info *bg, unsigned int i)
+{
+	int header_blocks = 2 + aux_info.inode_table_blocks;
+
+	bg->has_superblock = ext4_bg_has_super_block(i);
+
+	if (bg->has_superblock)
+		header_blocks += 1 + aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks;
+
+	bg->bitmaps = calloc(info.block_size, 2);
+	bg->block_bitmap = bg->bitmaps;
+	bg->inode_bitmap = bg->bitmaps + info.block_size;
+
+	bg->header_blocks = header_blocks;
+	bg->first_block = aux_info.first_data_block + i * info.blocks_per_group;
+
+	u32 block = bg->first_block;
+	if (bg->has_superblock)
+		block += 1 + aux_info.bg_desc_blocks +  aux_info.bg_desc_reserve_blocks;
+	queue_data_block(bg->bitmaps, 2 * info.block_size, block);
+
+	bg->data_blocks_used = 0;
+	bg->free_blocks = info.blocks_per_group;
+	bg->first_free_block = 0;
+	bg->free_inodes = info.inodes_per_group;
+	bg->first_free_inode = 1;
+
+	if (reserve_blocks(bg, bg->first_free_block, bg->header_blocks) < 0)
+		error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i);
+
+	u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks;
+	if (overrun > 0)
+		reserve_blocks(bg, info.blocks_per_group - overrun, overrun);
+}
+
+void block_allocator_init()
+{
+	unsigned int i;
+
+	aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups);
+	if (aux_info.bgs == NULL)
+		critical_error_errno("calloc");
+
+	for (i = 0; i < aux_info.groups; i++)
+		init_bg(&aux_info.bgs[i], i);
+}
+
+void block_allocator_free()
+{
+	unsigned int i;
+
+	for (i = 0; i < aux_info.groups; i++) {
+		free(aux_info.bgs[i].bitmaps);
+		free(aux_info.bgs[i].inode_table);
+	}
+	free(aux_info.bgs);
+}
+
+static u32 ext4_allocate_blocks_from_block_group(u32 len, int bg_num)
+{
+	if (get_free_blocks(bg_num) < len)
+		return EXT4_ALLOCATE_FAILED;
+
+	u32 block = aux_info.bgs[bg_num].first_free_block;
+	struct block_group_info *bg = &aux_info.bgs[bg_num];
+	if (reserve_blocks(bg, bg->first_free_block, len) < 0) {
+		error("failed to reserve %u blocks in block group %u\n", len, bg_num);
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	aux_info.bgs[bg_num].data_blocks_used += len;
+
+	return bg->first_block + block;
+}
+
+static struct region *ext4_allocate_contiguous_blocks(u32 len)
+{
+	unsigned int i;
+	struct region *reg;
+
+	for (i = 0; i < aux_info.groups; i++) {
+		u32 block = ext4_allocate_blocks_from_block_group(len, i);
+
+		if (block != EXT4_ALLOCATE_FAILED) {
+			reg = malloc(sizeof(struct region));
+			reg->block = block;
+			reg->len = len;
+			reg->next = NULL;
+			reg->prev = NULL;
+			reg->bg = i;
+			return reg;
+		}
+	}
+
+	return NULL;
+}
+
+/* Allocate a single block and return its block number */
+u32 allocate_block()
+{
+	unsigned int i;
+	for (i = 0; i < aux_info.groups; i++) {
+		u32 block = ext4_allocate_blocks_from_block_group(1, i);
+
+		if (block != EXT4_ALLOCATE_FAILED)
+			return block;
+	}
+
+	return EXT4_ALLOCATE_FAILED;
+}
+
+static struct region *ext4_allocate_partial(u32 len)
+{
+	unsigned int i;
+	struct region *reg;
+
+	for (i = 0; i < aux_info.groups; i++) {
+		if (aux_info.bgs[i].data_blocks_used == 0) {
+			u32 bg_len = aux_info.bgs[i].free_blocks;
+			u32 block;
+
+			if (len <= bg_len) {
+				/* If the requested length would fit in a block group,
+				 use the regular allocator to try to fit it in a partially
+				 used block group */
+				bg_len = len;
+				reg = ext4_allocate_contiguous_blocks(len);
+			} else {
+				block = ext4_allocate_blocks_from_block_group(bg_len, i);
+
+				if (block == EXT4_ALLOCATE_FAILED) {
+					error("failed to allocate %d blocks in block group %d", bg_len, i);
+					return NULL;
+				}
+
+				reg = malloc(sizeof(struct region));
+				reg->block = block;
+				reg->len = bg_len;
+				reg->next = NULL;
+				reg->prev = NULL;
+				reg->bg = i;
+			}
+
+			return reg;
+		}
+	}
+	return NULL;
+}
+
+static struct region *ext4_allocate_multiple_contiguous_blocks(u32 len)
+{
+	struct region *first_reg = NULL;
+	struct region *prev_reg = NULL;
+	struct region *reg;
+
+	while (len > 0) {
+		reg = ext4_allocate_partial(len);
+		if (reg == NULL)
+			return NULL;
+
+		if (first_reg == NULL)
+			first_reg = reg;
+
+		if (prev_reg) {
+			prev_reg->next = reg;
+			reg->prev = prev_reg;
+		}
+
+		prev_reg = reg;
+		len -= reg->len;
+	}
+
+	return first_reg;
+}
+
+struct region *do_allocate(u32 len)
+{
+	struct region *reg = ext4_allocate_contiguous_blocks(len);
+
+	if (reg == NULL)
+		reg = ext4_allocate_multiple_contiguous_blocks(len);
+
+	return reg;
+}
+
+/* Allocate len blocks.  The blocks may be spread across multiple block groups,
+   and are returned in a linked list of the blocks in each block group.  The
+   allocation algorithm is:
+      1.  Try to allocate the entire block len in each block group
+      2.  If the request doesn't fit in any block group, allocate as many
+          blocks as possible into each block group that is completely empty
+      3.  Put the last set of blocks in the first block group they fit in
+*/
+struct block_allocation *allocate_blocks(u32 len)
+{
+	struct region *reg = do_allocate(len);
+
+	if (reg == NULL)
+		return NULL;
+
+	struct block_allocation *alloc = create_allocation();
+	alloc->list.first = reg;
+	alloc->list.last = reg;
+	alloc->list.iter = alloc->list.first;
+	alloc->list.partial_iter = 0;
+	return alloc;
+}
+
+/* Returns the number of discontiguous regions used by an allocation */
+int block_allocation_num_regions(struct block_allocation *alloc)
+{
+	unsigned int i;
+	struct region *reg = alloc->list.first;
+
+	for (i = 0; reg != NULL; reg = reg->next)
+		i++;
+
+	return i;
+}
+
+int block_allocation_len(struct block_allocation *alloc)
+{
+	unsigned int i;
+	struct region *reg = alloc->list.first;
+
+	for (i = 0; reg != NULL; reg = reg->next)
+		i += reg->len;
+
+	return i;
+}
+
+/* Returns the block number of the block'th block in an allocation */
+u32 get_block(struct block_allocation *alloc, u32 block)
+{
+	struct region *reg = alloc->list.iter;
+	block += alloc->list.partial_iter;
+
+	for (; reg; reg = reg->next) {
+		if (block < reg->len)
+			return reg->block + block;
+		block -= reg->len;
+	}
+	return EXT4_ALLOCATE_FAILED;
+}
+
+u32 get_oob_block(struct block_allocation *alloc, u32 block)
+{
+	struct region *reg = alloc->oob_list.iter;
+	block += alloc->oob_list.partial_iter;
+
+	for (; reg; reg = reg->next) {
+		if (block < reg->len)
+			return reg->block + block;
+		block -= reg->len;
+	}
+	return EXT4_ALLOCATE_FAILED;
+}
+
+/* Gets the starting block and length in blocks of the first region
+   of an allocation */
+void get_region(struct block_allocation *alloc, u32 *block, u32 *len)
+{
+	*block = alloc->list.iter->block;
+	*len = alloc->list.iter->len - alloc->list.partial_iter;
+}
+
+/* Move to the next region in an allocation */
+void get_next_region(struct block_allocation *alloc)
+{
+	alloc->list.iter = alloc->list.iter->next;
+	alloc->list.partial_iter = 0;
+}
+
+/* Returns the number of free blocks in a block group */
+u32 get_free_blocks(u32 bg)
+{
+	return aux_info.bgs[bg].free_blocks;
+}
+
+int last_region(struct block_allocation *alloc)
+{
+	return (alloc->list.iter == NULL);
+}
+
+void rewind_alloc(struct block_allocation *alloc)
+{
+	alloc->list.iter = alloc->list.first;
+	alloc->list.partial_iter = 0;
+}
+
+static struct region *do_split_allocation(struct block_allocation *alloc, u32 len)
+{
+	struct region *reg = alloc->list.iter;
+	struct region *new;
+	struct region *tmp;
+
+	while (reg && len >= reg->len) {
+		len -= reg->len;
+		reg = reg->next;
+	}
+
+	if (reg == NULL && len > 0)
+		return NULL;
+
+	if (len > 0) {
+		new = malloc(sizeof(struct region));
+
+		new->bg = reg->bg;
+		new->block = reg->block + len;
+		new->len = reg->len - len;
+		new->next = reg->next;
+		new->prev = reg;
+
+		reg->next = new;
+		reg->len = len;
+
+		tmp = alloc->list.iter;
+		alloc->list.iter = new;
+		return tmp;
+	} else {
+		return reg;
+	}
+}
+
+/* Splits an allocation into two allocations.  The returned allocation will
+   point to the first half, and the original allocation ptr will point to the
+   second half. */
+static struct region *split_allocation(struct block_allocation *alloc, u32 len)
+{
+	/* First make sure there is a split at the current ptr */
+	do_split_allocation(alloc, alloc->list.partial_iter);
+
+	/* Then split off len blocks */
+	struct region *middle = do_split_allocation(alloc, len);
+	alloc->list.partial_iter = 0;
+	return middle;
+}
+
+/* Reserve the next blocks for oob data (indirect or extent blocks) */
+int reserve_oob_blocks(struct block_allocation *alloc, int blocks)
+{
+	struct region *oob = split_allocation(alloc, blocks);
+	struct region *next;
+
+	if (oob == NULL)
+		return -1;
+
+	while (oob && oob != alloc->list.iter) {
+		next = oob->next;
+		region_list_remove(&alloc->list, oob);
+		region_list_append(&alloc->oob_list, oob);
+		oob = next;
+	}
+
+	return 0;
+}
+
+static int advance_list_ptr(struct region_list *list, int blocks)
+{
+	struct region *reg = list->iter;
+
+	while (reg != NULL && blocks > 0) {
+		if (reg->len > list->partial_iter + blocks) {
+			list->partial_iter += blocks;
+			return 0;
+		}
+
+		blocks -= (reg->len - list->partial_iter);
+		list->partial_iter = 0;
+		reg = reg->next;
+	}
+
+	if (blocks > 0)
+		return -1;
+
+	return 0;
+}
+
+/* Move the allocation pointer forward */
+int advance_blocks(struct block_allocation *alloc, int blocks)
+{
+	return advance_list_ptr(&alloc->list, blocks);
+}
+
+int advance_oob_blocks(struct block_allocation *alloc, int blocks)
+{
+	return advance_list_ptr(&alloc->oob_list, blocks);
+}
+
+int append_oob_allocation(struct block_allocation *alloc, u32 len)
+{
+	struct region *reg = do_allocate(len);
+
+	if (reg == NULL) {
+		error("failed to allocate %d blocks", len);
+		return -1;
+	}
+
+	for (; reg; reg = reg->next)
+		region_list_append(&alloc->oob_list, reg);
+
+	return 0;
+}
+
+/* Returns an ext4_inode structure for an inode number */
+struct ext4_inode *get_inode(u32 inode)
+{
+	inode -= 1;
+	int bg = inode / info.inodes_per_group;
+	inode %= info.inodes_per_group;
+
+	allocate_bg_inode_table(&aux_info.bgs[bg]);
+	return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode *
+		info.inode_size);
+}
+
+/* Mark the first len inodes in a block group as used */
+u32 reserve_inodes(int bg, u32 num)
+{
+	unsigned int i;
+	u32 inode;
+
+	if (get_free_inodes(bg) < num)
+		return EXT4_ALLOCATE_FAILED;
+
+	for (i = 0; i < num; i++) {
+		inode = aux_info.bgs[bg].first_free_inode + i - 1;
+		aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8);
+	}
+
+	inode = aux_info.bgs[bg].first_free_inode;
+
+	aux_info.bgs[bg].first_free_inode += num;
+	aux_info.bgs[bg].free_inodes -= num;
+
+	return inode;
+}
+
+/* Returns the first free inode number
+   TODO: Inodes should be allocated in the block group of the data? */
+u32 allocate_inode()
+{
+	unsigned int bg;
+	u32 inode;
+
+	for (bg = 0; bg < aux_info.groups; bg++) {
+		inode = reserve_inodes(bg, 1);
+		if (inode != EXT4_ALLOCATE_FAILED)
+			return bg * info.inodes_per_group + inode;
+	}
+
+	return EXT4_ALLOCATE_FAILED;
+}
+
+/* Returns the number of free inodes in a block group */
+u32 get_free_inodes(u32 bg)
+{
+	return aux_info.bgs[bg].free_inodes;
+}
+
+/* Increments the directory count of the block group that contains inode */
+void add_directory(u32 inode)
+{
+	int bg = (inode - 1) / info.inodes_per_group;
+	aux_info.bgs[bg].used_dirs += 1;
+}
+
+/* Returns the number of inodes in a block group that are directories */
+u16 get_directories(int bg)
+{
+	return aux_info.bgs[bg].used_dirs;
+}
+
+/* Frees the memory used by a linked list of allocation regions */
+void free_alloc(struct block_allocation *alloc)
+{
+	struct region *reg;
+
+	reg = alloc->list.first;
+	while (reg) {
+		struct region *next = reg->next;
+		free(reg);
+		reg = next;
+	}
+
+	reg = alloc->oob_list.first;
+	while (reg) {
+		struct region *next = reg->next;
+		free(reg);
+		reg = next;
+	}
+
+	free(alloc);
+}
diff --git a/ext4_utils/allocate.h b/ext4_utils/allocate.h
new file mode 100644
index 00000000..f4bed412
--- /dev/null
+++ b/ext4_utils/allocate.h
@@ -0,0 +1,51 @@
+/*
+ * 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 EXT4_ALLOCATE_FAILED (u32)(~0)
+
+#include "ext4_utils.h"
+#include "ext4.h"
+
+struct block_allocation;
+
+void block_allocator_init();
+void block_allocator_free();
+u32 allocate_block();
+struct block_allocation *allocate_blocks(u32 len);
+int block_allocation_num_regions(struct block_allocation *alloc);
+int block_allocation_len(struct block_allocation *alloc);
+struct ext4_inode *get_inode(u32 inode);
+void reduce_allocation(struct block_allocation *alloc, u32 len);
+u32 get_block(struct block_allocation *alloc, u32 block);
+u32 get_oob_block(struct block_allocation *alloc, u32 block);
+void get_next_region(struct block_allocation *alloc);
+void get_region(struct block_allocation *alloc, u32 *block, u32 *len);
+u32 get_free_blocks(u32 bg);
+u32 get_free_inodes(u32 bg);
+u32 reserve_inodes(int bg, u32 inodes);
+void add_directory(u32 inode);
+u16 get_directories(int bg);
+u32 allocate_inode();
+void free_alloc(struct block_allocation *alloc);
+int reserve_oob_blocks(struct block_allocation *alloc, int blocks);
+int advance_blocks(struct block_allocation *alloc, int blocks);
+int advance_oob_blocks(struct block_allocation *alloc, int blocks);
+int last_region(struct block_allocation *alloc);
+void rewind_alloc(struct block_allocation *alloc);
+void append_region(struct block_allocation *alloc,
+	u32 block, u32 len, int bg);
+struct block_allocation *create_allocation();
+int append_oob_allocation(struct block_allocation *alloc, u32 len);
diff --git a/ext4_utils/backed_block.c b/ext4_utils/backed_block.c
new file mode 100644
index 00000000..c1a2f202
--- /dev/null
+++ b/ext4_utils/backed_block.c
@@ -0,0 +1,144 @@
+/*
+ * 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 "ext4_utils.h"
+#include "backed_block.h"
+
+struct data_block {
+	u32 block;
+	u32 len;
+	u8 *data;
+	const char *filename;
+	off_t offset;
+	struct data_block *next;
+};
+
+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 block of memory to be written to the specified data blocks */
+void queue_data_block(u8 *data, u32 len, u32 block)
+{
+	struct data_block *db = malloc(sizeof(struct data_block));
+	if (db == NULL)
+		critical_error_errno("malloc");
+
+	db->block = block;
+	db->len = len;
+	db->data = data;
+	db->filename = NULL;
+	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, off_t offset, u32 len,
+	u32 block)
+{
+	struct data_block *db = malloc(sizeof(struct data_block));
+	if (db == NULL)
+		critical_error_errno("malloc");
+
+	db->block = block;
+	db->len = len;
+	db->filename = strdup(filename);
+	db->offset = offset;
+	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, struct output_file *out)
+{
+	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, info.block_size) - 1;
+
+		if (db->filename)
+			file_func(out, (u64)db->block * info.block_size, db->filename, db->offset, db->len);
+		else
+			data_func(out, (u64)db->block * info.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/ext4_utils/backed_block.h b/ext4_utils/backed_block.h
new file mode 100644
index 00000000..5304f00e
--- /dev/null
+++ b/ext4_utils/backed_block.h
@@ -0,0 +1,38 @@
+/*
+ * 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 <sys/types.h>
+#include <unistd.h>
+#include "ext4_utils.h"
+#include "output_file.h"
+
+typedef void (*data_block_callback_t)(struct output_file *out, u64 off,
+	u8 *data, int len);
+typedef void (*data_block_file_callback_t)(struct output_file *out, u64 off,
+					   const char *file, off_t offset,
+					   int len);
+
+void queue_data_block(u8 *data, u32 len, u32 block);
+void queue_data_file(const char *filename, off_t offset, u32 len,
+	u32 block);
+void for_each_data_block(data_block_callback_t data_func,
+	data_block_file_callback_t file_func, struct output_file *out);
+void free_data_blocks();
+
+#endif
diff --git a/ext4_utils/contents.c b/ext4_utils/contents.c
new file mode 100644
index 00000000..0ecdfd43
--- /dev/null
+++ b/ext4_utils/contents.c
@@ -0,0 +1,241 @@
+/*
+ * 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 <sys/stat.h>
+#include <string.h>
+#include <stdio.h>
+
+#include "ext4_utils.h"
+#include "ext4.h"
+#include "make_ext4fs.h"
+#include "allocate.h"
+#include "contents.h"
+#include "extent.h"
+#include "indirect.h"
+
+static u32 dentry_size(u32 entries, struct dentry *dentries)
+{
+	u32 len = 24;
+	unsigned int i;
+	unsigned int dentry_len;
+
+	for (i = 0; i < entries; i++) {
+		dentry_len = 8 + ALIGN(strlen(dentries[i].filename), 4);
+		if (len % info.block_size + dentry_len > info.block_size)
+			len += info.block_size - (len % info.block_size);
+		len += dentry_len;
+	}
+
+	return len;
+}
+
+static struct ext4_dir_entry_2 *add_dentry(u8 *data, u32 *offset,
+		struct ext4_dir_entry_2 *prev, u32 inode, const char *name,
+		u8 file_type)
+{
+	u8 name_len = strlen(name);
+	u16 rec_len = 8 + ALIGN(name_len, 4);
+	struct ext4_dir_entry_2 *dentry;
+
+	u32 start_block = *offset / info.block_size;
+	u32 end_block = (*offset + rec_len) / info.block_size;
+	if (start_block != end_block) {
+		/* Adding this dentry will cross a block boundary, so pad the previous
+		   dentry to the block boundary */
+		if (!prev)
+			critical_error("no prev");
+		prev->rec_len += end_block * info.block_size - *offset;
+		*offset = end_block * info.block_size;
+	}
+
+	dentry = (struct ext4_dir_entry_2 *)(data + *offset);
+	dentry->inode = inode;
+	dentry->rec_len = rec_len;
+	dentry->name_len = name_len;
+	dentry->file_type = file_type;
+	memcpy(dentry->name, name, name_len);
+
+	*offset += rec_len;
+	return dentry;
+}
+
+/* Creates a directory structure for an array of directory entries, dentries,
+   and stores the location of the structure in an inode.  The new inode's
+   .. link is set to dir_inode_num.  Stores the location of the inode number
+   of each directory entry into dentries[i].inode, to be filled in later
+   when the inode for the entry is allocated.  Returns the inode number of the
+   new directory */
+u32 make_directory(u32 dir_inode_num, u32 entries, struct dentry *dentries,
+	u32 dirs)
+{
+	struct ext4_inode *inode;
+	u32 blocks;
+	u32 len;
+	u32 offset = 0;
+	u32 inode_num;
+	u8 *data;
+	unsigned int i;
+	struct ext4_dir_entry_2 *dentry;
+
+	blocks = DIV_ROUND_UP(dentry_size(entries, dentries), info.block_size);
+	len = blocks * info.block_size;
+
+	if (dir_inode_num) {
+		inode_num = allocate_inode(info);
+	} else {
+		dir_inode_num = EXT4_ROOT_INO;
+		inode_num = EXT4_ROOT_INO;
+	}
+
+	if (inode_num == EXT4_ALLOCATE_FAILED) {
+		error("failed to allocate inode\n");
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	add_directory(inode_num);
+
+	inode = get_inode(inode_num);
+	if (inode == NULL) {
+		error("failed to get inode %u", inode_num);
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	data = inode_allocate_data_extents(inode, len, len);
+	if (data == NULL) {
+		error("failed to allocate %llu extents", len);
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	inode->i_mode = S_IFDIR;
+	inode->i_links_count = dirs + 2;
+	inode->i_flags |= aux_info.default_i_flags;
+
+	dentry = NULL;
+
+	dentry = add_dentry(data, &offset, NULL, inode_num, ".", EXT4_FT_DIR);
+	if (!dentry) {
+		error("failed to add . directory");
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	dentry = add_dentry(data, &offset, dentry, dir_inode_num, "..", EXT4_FT_DIR);
+	if (!dentry) {
+		error("failed to add .. directory");
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	for (i = 0; i < entries; i++) {
+		dentry = add_dentry(data, &offset, dentry, 0,
+				dentries[i].filename, dentries[i].file_type);
+		if (offset > len || (offset == len && i != entries - 1))
+			critical_error("internal error: dentry for %s ends at %d, past %d\n",
+				dentries[i].filename, offset, len);
+		dentries[i].inode = &dentry->inode;
+		if (!dentry) {
+			error("failed to add directory");
+			return EXT4_ALLOCATE_FAILED;
+		}
+	}
+
+	dentry = (struct ext4_dir_entry_2 *)(data + offset);
+	dentry->inode = 0;
+	dentry->rec_len = len - offset;
+	dentry->name_len = 0;
+	dentry->file_type = EXT4_FT_UNKNOWN;
+
+	return inode_num;
+}
+
+/* Creates a file on disk.  Returns the inode number of the new file */
+u32 make_file(const char *filename, u64 len)
+{
+	struct ext4_inode *inode;
+	u32 inode_num;
+
+	inode_num = allocate_inode(info);
+	if (inode_num == EXT4_ALLOCATE_FAILED) {
+		error("failed to allocate inode\n");
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	inode = get_inode(inode_num);
+	if (inode == NULL) {
+		error("failed to get inode %u", inode_num);
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	if (len > 0)
+		inode_allocate_file_extents(inode, len, filename);
+
+	inode->i_mode = S_IFREG;
+	inode->i_links_count = 1;
+	inode->i_flags |= aux_info.default_i_flags;
+
+	return inode_num;
+}
+
+/* Creates a file on disk.  Returns the inode number of the new file */
+u32 make_link(const char *filename, const char *link)
+{
+	struct ext4_inode *inode;
+	u32 inode_num;
+	u32 len = strlen(link);
+
+	inode_num = allocate_inode(info);
+	if (inode_num == EXT4_ALLOCATE_FAILED) {
+		error("failed to allocate inode\n");
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	inode = get_inode(inode_num);
+	if (inode == NULL) {
+		error("failed to get inode %u", inode_num);
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	inode->i_mode = S_IFLNK;
+	inode->i_links_count = 1;
+	inode->i_flags |= aux_info.default_i_flags;
+	inode->i_size_lo = len;
+
+	if (len + 1 <= sizeof(inode->i_block)) {
+		/* Fast symlink */
+		memcpy((char*)inode->i_block, link, len);
+	} else {
+		u8 *data = inode_allocate_data_indirect(inode, info.block_size, info.block_size);
+		memcpy(data, link, len);
+		inode->i_blocks_lo = info.block_size / 512;
+	}
+
+	return inode_num;
+}
+
+int inode_set_permissions(u32 inode_num, u16 mode, u16 uid, u16 gid, u32 mtime)
+{
+	struct ext4_inode *inode = get_inode(inode_num);
+
+	if (!inode)
+		return -1;
+
+	inode->i_mode |= mode;
+	inode->i_uid = uid;
+	inode->i_gid = gid;
+	inode->i_mtime = mtime;
+	inode->i_atime = mtime;
+	inode->i_ctime = mtime;
+
+	return 0;
+}
diff --git a/ext4_utils/contents.h b/ext4_utils/contents.h
new file mode 100644
index 00000000..3aafb1ee
--- /dev/null
+++ b/ext4_utils/contents.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 _DIRECTORY_H_
+#define _DIRECTORY_H_
+
+struct dentry {
+	char *path;
+	char *full_path;
+	const char *filename;
+	char *link;
+	unsigned long size;
+	u8 file_type;
+	u16 mode;
+	u16 uid;
+	u16 gid;
+	u32 *inode;
+	u32 mtime;
+};
+
+u32 make_directory(u32 dir_inode_num, u32 entries, struct dentry *dentries,
+	u32 dirs);
+u32 make_file(const char *filename, u64 len);
+u32 make_link(const char *filename, const char *link);
+int inode_set_permissions(u32 inode_num, u16 mode, u16 uid, u16 gid, u32 mtime);
+#endif
diff --git a/ext4_utils/ext4.h b/ext4_utils/ext4.h
new file mode 100644
index 00000000..68b5233a
--- /dev/null
+++ b/ext4_utils/ext4.h
@@ -0,0 +1,577 @@
+/****************************************************************************
+ ****************************************************************************
+ ***
+ ***   This header was automatically generated from a Linux kernel header
+ ***   of the same name, to make information necessary for userspace to
+ ***   call into the kernel available to libc.  It contains only constants,
+ ***   structures, and macros generated from the original header, and thus,
+ ***   contains no copyrightable information.
+ ***
+ ****************************************************************************
+ ****************************************************************************/
+#ifndef _EXT4_H
+#define _EXT4_H
+
+#include <sys/types.h>
+
+#undef EXT4FS_DEBUG
+
+#ifdef EXT4FS_DEBUG
+#define ext4_debug(f, a...)   do {   printk(KERN_DEBUG "EXT4-fs DEBUG (%s, %d): %s:",   __FILE__, __LINE__, __func__);   printk(KERN_DEBUG f, ## a);   } while (0)
+#else
+#define ext4_debug(f, a...) do {} while (0)
+#endif
+
+#define EXT4_ERROR_INODE(inode, fmt, a...)   ext4_error_inode(__func__, (inode), (fmt), ## a);
+
+#define EXT4_ERROR_FILE(file, fmt, a...)   ext4_error_file(__func__, (file), (fmt), ## a);
+
+typedef int ext4_grpblk_t;
+
+typedef unsigned long long ext4_fsblk_t;
+
+typedef __u32 ext4_lblk_t;
+
+typedef unsigned int ext4_group_t;
+
+#define EXT4_MB_HINT_MERGE 0x0001
+
+#define EXT4_MB_HINT_RESERVED 0x0002
+
+#define EXT4_MB_HINT_METADATA 0x0004
+
+#define EXT4_MB_HINT_FIRST 0x0008
+
+#define EXT4_MB_HINT_BEST 0x0010
+
+#define EXT4_MB_HINT_DATA 0x0020
+
+#define EXT4_MB_HINT_NOPREALLOC 0x0040
+
+#define EXT4_MB_HINT_GROUP_ALLOC 0x0080
+
+#define EXT4_MB_HINT_GOAL_ONLY 0x0100
+
+#define EXT4_MB_HINT_TRY_GOAL 0x0200
+
+#define EXT4_MB_DELALLOC_RESERVED 0x0400
+
+#define EXT4_MB_STREAM_ALLOC 0x0800
+
+struct ext4_allocation_request {
+
+ struct inode *inode;
+
+ unsigned int len;
+
+ ext4_lblk_t logical;
+
+ ext4_lblk_t lleft;
+
+ ext4_lblk_t lright;
+
+ ext4_fsblk_t goal;
+
+ ext4_fsblk_t pleft;
+
+ ext4_fsblk_t pright;
+
+ unsigned int flags;
+};
+
+#define EXT4_BAD_INO 1  
+#define EXT4_ROOT_INO 2  
+#define EXT4_BOOT_LOADER_INO 5  
+#define EXT4_UNDEL_DIR_INO 6  
+#define EXT4_RESIZE_INO 7  
+#define EXT4_JOURNAL_INO 8  
+
+#define EXT4_GOOD_OLD_FIRST_INO 11
+
+#define EXT4_LINK_MAX 65000
+
+#define EXT4_MIN_BLOCK_SIZE 1024
+#define EXT4_MAX_BLOCK_SIZE 65536
+#define EXT4_MIN_BLOCK_LOG_SIZE 10
+#define EXT4_BLOCK_SIZE(s) (EXT4_MIN_BLOCK_SIZE << (s)->s_log_block_size)
+#define EXT4_ADDR_PER_BLOCK(s) (EXT4_BLOCK_SIZE(s) / sizeof(__u32))
+#define EXT4_BLOCK_SIZE_BITS(s) ((s)->s_log_block_size + 10)
+#define EXT4_INODE_SIZE(s) (((s)->s_rev_level == EXT4_GOOD_OLD_REV) ?   EXT4_GOOD_OLD_INODE_SIZE :   (s)->s_inode_size)
+#define EXT4_FIRST_INO(s) (((s)->s_rev_level == EXT4_GOOD_OLD_REV) ?   EXT4_GOOD_OLD_FIRST_INO :   (s)->s_first_ino)
+#define EXT4_BLOCK_ALIGN(size, blkbits) ALIGN((size), (1 << (blkbits)))
+
+struct ext4_group_desc
+{
+ __le32 bg_block_bitmap_lo;
+ __le32 bg_inode_bitmap_lo;
+ __le32 bg_inode_table_lo;
+ __le16 bg_free_blocks_count_lo;
+ __le16 bg_free_inodes_count_lo;
+ __le16 bg_used_dirs_count_lo;
+ __le16 bg_flags;
+ __u32 bg_reserved[2];
+ __le16 bg_itable_unused_lo;
+ __le16 bg_checksum;
+ __le32 bg_block_bitmap_hi;
+ __le32 bg_inode_bitmap_hi;
+ __le32 bg_inode_table_hi;
+ __le16 bg_free_blocks_count_hi;
+ __le16 bg_free_inodes_count_hi;
+ __le16 bg_used_dirs_count_hi;
+ __le16 bg_itable_unused_hi;
+ __u32 bg_reserved2[3];
+};
+
+#define EXT4_BG_INODE_UNINIT 0x0001  
+#define EXT4_BG_BLOCK_UNINIT 0x0002  
+#define EXT4_BG_INODE_ZEROED 0x0004  
+
+#define EXT4_MIN_DESC_SIZE 32
+#define EXT4_MIN_DESC_SIZE_64BIT 64
+#define EXT4_MAX_DESC_SIZE EXT4_MIN_BLOCK_SIZE
+#define EXT4_DESC_SIZE(s) (EXT4_SB(s)->s_desc_size)
+#define EXT4_BLOCKS_PER_GROUP(s) ((s)->s_blocks_per_group)
+#define EXT4_DESC_PER_BLOCK(s) (EXT4_BLOCK_SIZE(s) / EXT4_DESC_SIZE(s))
+#define EXT4_INODES_PER_GROUP(s) ((s)->s_inodes_per_group)
+
+#define EXT4_NDIR_BLOCKS 12
+#define EXT4_IND_BLOCK EXT4_NDIR_BLOCKS
+#define EXT4_DIND_BLOCK (EXT4_IND_BLOCK + 1)
+#define EXT4_TIND_BLOCK (EXT4_DIND_BLOCK + 1)
+#define EXT4_N_BLOCKS (EXT4_TIND_BLOCK + 1)
+
+#define EXT4_SECRM_FL 0x00000001  
+#define EXT4_UNRM_FL 0x00000002  
+#define EXT4_COMPR_FL 0x00000004  
+#define EXT4_SYNC_FL 0x00000008  
+#define EXT4_IMMUTABLE_FL 0x00000010  
+#define EXT4_APPEND_FL 0x00000020  
+#define EXT4_NODUMP_FL 0x00000040  
+#define EXT4_NOATIME_FL 0x00000080  
+
+#define EXT4_DIRTY_FL 0x00000100
+#define EXT4_COMPRBLK_FL 0x00000200  
+#define EXT4_NOCOMPR_FL 0x00000400  
+#define EXT4_ECOMPR_FL 0x00000800  
+
+#define EXT4_INDEX_FL 0x00001000  
+#define EXT4_IMAGIC_FL 0x00002000  
+#define EXT4_JOURNAL_DATA_FL 0x00004000  
+#define EXT4_NOTAIL_FL 0x00008000  
+#define EXT4_DIRSYNC_FL 0x00010000  
+#define EXT4_TOPDIR_FL 0x00020000  
+#define EXT4_HUGE_FILE_FL 0x00040000  
+#define EXT4_EXTENTS_FL 0x00080000  
+#define EXT4_EA_INODE_FL 0x00200000  
+#define EXT4_EOFBLOCKS_FL 0x00400000  
+#define EXT4_RESERVED_FL 0x80000000  
+
+#define EXT4_FL_USER_VISIBLE 0x004BDFFF  
+#define EXT4_FL_USER_MODIFIABLE 0x004B80FF  
+
+#define EXT4_FL_INHERITED (EXT4_SECRM_FL | EXT4_UNRM_FL | EXT4_COMPR_FL |  EXT4_SYNC_FL | EXT4_IMMUTABLE_FL | EXT4_APPEND_FL |  EXT4_NODUMP_FL | EXT4_NOATIME_FL |  EXT4_NOCOMPR_FL | EXT4_JOURNAL_DATA_FL |  EXT4_NOTAIL_FL | EXT4_DIRSYNC_FL)
+
+#define EXT4_REG_FLMASK (~(EXT4_DIRSYNC_FL | EXT4_TOPDIR_FL))
+
+#define EXT4_OTHER_FLMASK (EXT4_NODUMP_FL | EXT4_NOATIME_FL)
+
+struct ext4_new_group_data {
+ __u32 group;
+ __u64 block_bitmap;
+ __u64 inode_bitmap;
+ __u64 inode_table;
+ __u32 blocks_count;
+ __u16 reserved_blocks;
+ __u16 unused;
+ __u32 free_blocks_count;
+};
+
+#define EXT4_GET_BLOCKS_CREATE 0x0001
+
+#define EXT4_GET_BLOCKS_UNINIT_EXT 0x0002
+#define EXT4_GET_BLOCKS_CREATE_UNINIT_EXT (EXT4_GET_BLOCKS_UNINIT_EXT|  EXT4_GET_BLOCKS_CREATE)
+
+#define EXT4_GET_BLOCKS_DELALLOC_RESERVE 0x0004
+
+#define EXT4_GET_BLOCKS_PRE_IO 0x0008
+#define EXT4_GET_BLOCKS_CONVERT 0x0010
+#define EXT4_GET_BLOCKS_IO_CREATE_EXT (EXT4_GET_BLOCKS_PRE_IO|  EXT4_GET_BLOCKS_CREATE_UNINIT_EXT)
+
+#define EXT4_GET_BLOCKS_IO_CONVERT_EXT (EXT4_GET_BLOCKS_CONVERT|  EXT4_GET_BLOCKS_CREATE_UNINIT_EXT)
+
+#define EXT4_FREE_BLOCKS_METADATA 0x0001
+#define EXT4_FREE_BLOCKS_FORGET 0x0002
+#define EXT4_FREE_BLOCKS_VALIDATED 0x0004
+
+#define EXT4_IOC_GETFLAGS FS_IOC_GETFLAGS
+#define EXT4_IOC_SETFLAGS FS_IOC_SETFLAGS
+#define EXT4_IOC_GETVERSION _IOR('f', 3, long)
+#define EXT4_IOC_SETVERSION _IOW('f', 4, long)
+#define EXT4_IOC_GETVERSION_OLD FS_IOC_GETVERSION
+#define EXT4_IOC_SETVERSION_OLD FS_IOC_SETVERSION
+#define EXT4_IOC_GETRSVSZ _IOR('f', 5, long)
+#define EXT4_IOC_SETRSVSZ _IOW('f', 6, long)
+#define EXT4_IOC_GROUP_EXTEND _IOW('f', 7, unsigned long)
+#define EXT4_IOC_GROUP_ADD _IOW('f', 8, struct ext4_new_group_input)
+#define EXT4_IOC_MIGRATE _IO('f', 9)
+
+#define EXT4_IOC_ALLOC_DA_BLKS _IO('f', 12)
+#define EXT4_IOC_MOVE_EXT _IOWR('f', 15, struct move_extent)
+
+#define EXT4_IOC32_GETFLAGS FS_IOC32_GETFLAGS
+#define EXT4_IOC32_SETFLAGS FS_IOC32_SETFLAGS
+#define EXT4_IOC32_GETVERSION _IOR('f', 3, int)
+#define EXT4_IOC32_SETVERSION _IOW('f', 4, int)
+#define EXT4_IOC32_GETRSVSZ _IOR('f', 5, int)
+#define EXT4_IOC32_SETRSVSZ _IOW('f', 6, int)
+#define EXT4_IOC32_GROUP_EXTEND _IOW('f', 7, unsigned int)
+#define EXT4_IOC32_GETVERSION_OLD FS_IOC32_GETVERSION
+#define EXT4_IOC32_SETVERSION_OLD FS_IOC32_SETVERSION
+
+#define EXT4_MAX_BLOCK_FILE_PHYS 0xFFFFFFFF
+
+struct ext4_inode {
+ __le16 i_mode;
+ __le16 i_uid;
+ __le32 i_size_lo;
+ __le32 i_atime;
+ __le32 i_ctime;
+ __le32 i_mtime;
+ __le32 i_dtime;
+ __le16 i_gid;
+ __le16 i_links_count;
+ __le32 i_blocks_lo;
+ __le32 i_flags;
+ union {
+ struct {
+ __le32 l_i_version;
+ } linux1;
+ struct {
+ __u32 h_i_translator;
+ } hurd1;
+ struct {
+ __u32 m_i_reserved1;
+ } masix1;
+ } osd1;
+ __le32 i_block[EXT4_N_BLOCKS];
+ __le32 i_generation;
+ __le32 i_file_acl_lo;
+ __le32 i_size_high;
+ __le32 i_obso_faddr;
+ union {
+ struct {
+ __le16 l_i_blocks_high;
+ __le16 l_i_file_acl_high;
+ __le16 l_i_uid_high;
+ __le16 l_i_gid_high;
+ __u32 l_i_reserved2;
+ } linux2;
+ struct {
+ __le16 h_i_reserved1;
+ __u16 h_i_mode_high;
+ __u16 h_i_uid_high;
+ __u16 h_i_gid_high;
+ __u32 h_i_author;
+ } hurd2;
+ struct {
+ __le16 h_i_reserved1;
+ __le16 m_i_file_acl_high;
+ __u32 m_i_reserved2[2];
+ } masix2;
+ } osd2;
+ __le16 i_extra_isize;
+ __le16 i_pad1;
+ __le32 i_ctime_extra;
+ __le32 i_mtime_extra;
+ __le32 i_atime_extra;
+ __le32 i_crtime;
+ __le32 i_crtime_extra;
+ __le32 i_version_hi;
+};
+
+struct move_extent {
+ __u32 reserved;
+ __u32 donor_fd;
+ __u64 orig_start;
+ __u64 donor_start;
+ __u64 len;
+ __u64 moved_len;
+};
+
+#define EXT4_EPOCH_BITS 2
+#define EXT4_EPOCH_MASK ((1 << EXT4_EPOCH_BITS) - 1)
+#define EXT4_NSEC_MASK (~0UL << EXT4_EPOCH_BITS)
+
+#define EXT4_FITS_IN_INODE(ext4_inode, einode, field)   ((offsetof(typeof(*ext4_inode), field) +   sizeof((ext4_inode)->field))   <= (EXT4_GOOD_OLD_INODE_SIZE +   (einode)->i_extra_isize))  
+#define EXT4_INODE_SET_XTIME(xtime, inode, raw_inode)  do {   (raw_inode)->xtime = cpu_to_le32((inode)->xtime.tv_sec);   if (EXT4_FITS_IN_INODE(raw_inode, EXT4_I(inode), xtime ## _extra))   (raw_inode)->xtime ## _extra =   ext4_encode_extra_time(&(inode)->xtime);  } while (0)
+#define EXT4_EINODE_SET_XTIME(xtime, einode, raw_inode)  do {   if (EXT4_FITS_IN_INODE(raw_inode, einode, xtime))   (raw_inode)->xtime = cpu_to_le32((einode)->xtime.tv_sec);   if (EXT4_FITS_IN_INODE(raw_inode, einode, xtime ## _extra))   (raw_inode)->xtime ## _extra =   ext4_encode_extra_time(&(einode)->xtime);  } while (0)
+#define EXT4_INODE_GET_XTIME(xtime, inode, raw_inode)  do {   (inode)->xtime.tv_sec = (signed)le32_to_cpu((raw_inode)->xtime);   if (EXT4_FITS_IN_INODE(raw_inode, EXT4_I(inode), xtime ## _extra))   ext4_decode_extra_time(&(inode)->xtime,   raw_inode->xtime ## _extra);  } while (0)
+#define EXT4_EINODE_GET_XTIME(xtime, einode, raw_inode)  do {   if (EXT4_FITS_IN_INODE(raw_inode, einode, xtime))   (einode)->xtime.tv_sec =   (signed)le32_to_cpu((raw_inode)->xtime);   if (EXT4_FITS_IN_INODE(raw_inode, einode, xtime ## _extra))   ext4_decode_extra_time(&(einode)->xtime,   raw_inode->xtime ## _extra);  } while (0)
+#define i_disk_version osd1.linux1.l_i_version
+
+#define i_reserved1 osd1.linux1.l_i_reserved1
+#define i_file_acl_high osd2.linux2.l_i_file_acl_high
+#define i_blocks_high osd2.linux2.l_i_blocks_high
+#define i_uid_low i_uid
+#define i_gid_low i_gid
+#define i_uid_high osd2.linux2.l_i_uid_high
+#define i_gid_high osd2.linux2.l_i_gid_high
+#define i_reserved2 osd2.linux2.l_i_reserved2
+
+#define EXT4_VALID_FS 0x0001  
+#define EXT4_ERROR_FS 0x0002  
+#define EXT4_ORPHAN_FS 0x0004  
+
+#define EXT2_FLAGS_SIGNED_HASH 0x0001  
+#define EXT2_FLAGS_UNSIGNED_HASH 0x0002  
+#define EXT2_FLAGS_TEST_FILESYS 0x0004  
+
+#define EXT4_MOUNT_OLDALLOC 0x00002  
+#define EXT4_MOUNT_GRPID 0x00004  
+#define EXT4_MOUNT_DEBUG 0x00008  
+#define EXT4_MOUNT_ERRORS_CONT 0x00010  
+#define EXT4_MOUNT_ERRORS_RO 0x00020  
+#define EXT4_MOUNT_ERRORS_PANIC 0x00040  
+#define EXT4_MOUNT_MINIX_DF 0x00080  
+#define EXT4_MOUNT_NOLOAD 0x00100  
+#define EXT4_MOUNT_DATA_FLAGS 0x00C00  
+#define EXT4_MOUNT_JOURNAL_DATA 0x00400  
+#define EXT4_MOUNT_ORDERED_DATA 0x00800  
+#define EXT4_MOUNT_WRITEBACK_DATA 0x00C00  
+#define EXT4_MOUNT_UPDATE_JOURNAL 0x01000  
+#define EXT4_MOUNT_NO_UID32 0x02000  
+#define EXT4_MOUNT_XATTR_USER 0x04000  
+#define EXT4_MOUNT_POSIX_ACL 0x08000  
+#define EXT4_MOUNT_NO_AUTO_DA_ALLOC 0x10000  
+#define EXT4_MOUNT_BARRIER 0x20000  
+#define EXT4_MOUNT_NOBH 0x40000  
+#define EXT4_MOUNT_QUOTA 0x80000  
+#define EXT4_MOUNT_USRQUOTA 0x100000  
+#define EXT4_MOUNT_GRPQUOTA 0x200000  
+#define EXT4_MOUNT_DIOREAD_NOLOCK 0x400000  
+#define EXT4_MOUNT_JOURNAL_CHECKSUM 0x800000  
+#define EXT4_MOUNT_JOURNAL_ASYNC_COMMIT 0x1000000  
+#define EXT4_MOUNT_I_VERSION 0x2000000  
+#define EXT4_MOUNT_DELALLOC 0x8000000  
+#define EXT4_MOUNT_DATA_ERR_ABORT 0x10000000  
+#define EXT4_MOUNT_BLOCK_VALIDITY 0x20000000  
+#define EXT4_MOUNT_DISCARD 0x40000000  
+
+#define clear_opt(o, opt) o &= ~EXT4_MOUNT_##opt
+#define set_opt(o, opt) o |= EXT4_MOUNT_##opt
+#define test_opt(sb, opt) (EXT4_SB(sb)->s_mount_opt &   EXT4_MOUNT_##opt)
+
+#define ext4_set_bit ext2_set_bit
+#define ext4_set_bit_atomic ext2_set_bit_atomic
+#define ext4_clear_bit ext2_clear_bit
+#define ext4_clear_bit_atomic ext2_clear_bit_atomic
+#define ext4_test_bit ext2_test_bit
+#define ext4_find_first_zero_bit ext2_find_first_zero_bit
+#define ext4_find_next_zero_bit ext2_find_next_zero_bit
+#define ext4_find_next_bit ext2_find_next_bit
+
+#define EXT4_DFL_MAX_MNT_COUNT 20  
+#define EXT4_DFL_CHECKINTERVAL 0  
+
+#define EXT4_ERRORS_CONTINUE 1  
+#define EXT4_ERRORS_RO 2  
+#define EXT4_ERRORS_PANIC 3  
+#define EXT4_ERRORS_DEFAULT EXT4_ERRORS_CONTINUE
+
+struct ext4_super_block {
+  __le32 s_inodes_count;
+ __le32 s_blocks_count_lo;
+ __le32 s_r_blocks_count_lo;
+ __le32 s_free_blocks_count_lo;
+  __le32 s_free_inodes_count;
+ __le32 s_first_data_block;
+ __le32 s_log_block_size;
+ __le32 s_obso_log_frag_size;
+  __le32 s_blocks_per_group;
+ __le32 s_obso_frags_per_group;
+ __le32 s_inodes_per_group;
+ __le32 s_mtime;
+  __le32 s_wtime;
+ __le16 s_mnt_count;
+ __le16 s_max_mnt_count;
+ __le16 s_magic;
+ __le16 s_state;
+ __le16 s_errors;
+ __le16 s_minor_rev_level;
+  __le32 s_lastcheck;
+ __le32 s_checkinterval;
+ __le32 s_creator_os;
+ __le32 s_rev_level;
+  __le16 s_def_resuid;
+ __le16 s_def_resgid;
+
+ __le32 s_first_ino;
+ __le16 s_inode_size;
+ __le16 s_block_group_nr;
+ __le32 s_feature_compat;
+  __le32 s_feature_incompat;
+ __le32 s_feature_ro_compat;
+  __u8 s_uuid[16];
+  char s_volume_name[16];
+  char s_last_mounted[64];
+  __le32 s_algorithm_usage_bitmap;
+
+ __u8 s_prealloc_blocks;
+ __u8 s_prealloc_dir_blocks;
+ __le16 s_reserved_gdt_blocks;
+
+  __u8 s_journal_uuid[16];
+  __le32 s_journal_inum;
+ __le32 s_journal_dev;
+ __le32 s_last_orphan;
+ __le32 s_hash_seed[4];
+ __u8 s_def_hash_version;
+ __u8 s_reserved_char_pad;
+ __le16 s_desc_size;
+  __le32 s_default_mount_opts;
+ __le32 s_first_meta_bg;
+ __le32 s_mkfs_time;
+ __le32 s_jnl_blocks[17];
+
+  __le32 s_blocks_count_hi;
+ __le32 s_r_blocks_count_hi;
+ __le32 s_free_blocks_count_hi;
+ __le16 s_min_extra_isize;
+ __le16 s_want_extra_isize;
+ __le32 s_flags;
+ __le16 s_raid_stride;
+ __le16 s_mmp_interval;
+ __le64 s_mmp_block;
+ __le32 s_raid_stripe_width;
+ __u8 s_log_groups_per_flex;
+ __u8 s_reserved_char_pad2;
+ __le16 s_reserved_pad;
+ __le64 s_kbytes_written;
+ __u32 s_reserved[160];
+};
+
+#define EXT4_SB(sb) (sb)
+
+#define NEXT_ORPHAN(inode) EXT4_I(inode)->i_dtime
+
+#define EXT4_OS_LINUX 0
+#define EXT4_OS_HURD 1
+#define EXT4_OS_MASIX 2
+#define EXT4_OS_FREEBSD 3
+#define EXT4_OS_LITES 4
+
+#define EXT4_GOOD_OLD_REV 0  
+#define EXT4_DYNAMIC_REV 1  
+
+#define EXT4_CURRENT_REV EXT4_GOOD_OLD_REV
+#define EXT4_MAX_SUPP_REV EXT4_DYNAMIC_REV
+
+#define EXT4_GOOD_OLD_INODE_SIZE 128
+
+#define EXT4_HAS_COMPAT_FEATURE(sb,mask)   ((EXT4_SB(sb)->s_es->s_feature_compat & cpu_to_le32(mask)) != 0)
+#define EXT4_HAS_RO_COMPAT_FEATURE(sb,mask)   ((EXT4_SB(sb)->s_es->s_feature_ro_compat & cpu_to_le32(mask)) != 0)
+#define EXT4_HAS_INCOMPAT_FEATURE(sb,mask)   ((EXT4_SB(sb)->s_es->s_feature_incompat & cpu_to_le32(mask)) != 0)
+#define EXT4_SET_COMPAT_FEATURE(sb,mask)   EXT4_SB(sb)->s_es->s_feature_compat |= cpu_to_le32(mask)
+#define EXT4_SET_RO_COMPAT_FEATURE(sb,mask)   EXT4_SB(sb)->s_es->s_feature_ro_compat |= cpu_to_le32(mask)
+#define EXT4_SET_INCOMPAT_FEATURE(sb,mask)   EXT4_SB(sb)->s_es->s_feature_incompat |= cpu_to_le32(mask)
+#define EXT4_CLEAR_COMPAT_FEATURE(sb,mask)   EXT4_SB(sb)->s_es->s_feature_compat &= ~cpu_to_le32(mask)
+#define EXT4_CLEAR_RO_COMPAT_FEATURE(sb,mask)   EXT4_SB(sb)->s_es->s_feature_ro_compat &= ~cpu_to_le32(mask)
+#define EXT4_CLEAR_INCOMPAT_FEATURE(sb,mask)   EXT4_SB(sb)->s_es->s_feature_incompat &= ~cpu_to_le32(mask)
+
+#define EXT4_FEATURE_COMPAT_DIR_PREALLOC 0x0001
+#define EXT4_FEATURE_COMPAT_IMAGIC_INODES 0x0002
+#define EXT4_FEATURE_COMPAT_HAS_JOURNAL 0x0004
+#define EXT4_FEATURE_COMPAT_EXT_ATTR 0x0008
+#define EXT4_FEATURE_COMPAT_RESIZE_INODE 0x0010
+#define EXT4_FEATURE_COMPAT_DIR_INDEX 0x0020
+
+#define EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER 0x0001
+#define EXT4_FEATURE_RO_COMPAT_LARGE_FILE 0x0002
+#define EXT4_FEATURE_RO_COMPAT_BTREE_DIR 0x0004
+#define EXT4_FEATURE_RO_COMPAT_HUGE_FILE 0x0008
+#define EXT4_FEATURE_RO_COMPAT_GDT_CSUM 0x0010
+#define EXT4_FEATURE_RO_COMPAT_DIR_NLINK 0x0020
+#define EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE 0x0040
+
+#define EXT4_FEATURE_INCOMPAT_COMPRESSION 0x0001
+#define EXT4_FEATURE_INCOMPAT_FILETYPE 0x0002
+#define EXT4_FEATURE_INCOMPAT_RECOVER 0x0004  
+#define EXT4_FEATURE_INCOMPAT_JOURNAL_DEV 0x0008  
+#define EXT4_FEATURE_INCOMPAT_META_BG 0x0010
+#define EXT4_FEATURE_INCOMPAT_EXTENTS 0x0040  
+#define EXT4_FEATURE_INCOMPAT_64BIT 0x0080
+#define EXT4_FEATURE_INCOMPAT_MMP 0x0100
+#define EXT4_FEATURE_INCOMPAT_FLEX_BG 0x0200
+#define EXT4_FEATURE_INCOMPAT_EA_INODE 0x0400  
+#define EXT4_FEATURE_INCOMPAT_DIRDATA 0x1000  
+
+#define EXT4_FEATURE_COMPAT_SUPP EXT2_FEATURE_COMPAT_EXT_ATTR
+#define EXT4_FEATURE_INCOMPAT_SUPP (EXT4_FEATURE_INCOMPAT_FILETYPE|   EXT4_FEATURE_INCOMPAT_RECOVER|   EXT4_FEATURE_INCOMPAT_META_BG|   EXT4_FEATURE_INCOMPAT_EXTENTS|   EXT4_FEATURE_INCOMPAT_64BIT|   EXT4_FEATURE_INCOMPAT_FLEX_BG)
+#define EXT4_FEATURE_RO_COMPAT_SUPP (EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER|   EXT4_FEATURE_RO_COMPAT_LARGE_FILE|   EXT4_FEATURE_RO_COMPAT_GDT_CSUM|   EXT4_FEATURE_RO_COMPAT_DIR_NLINK |   EXT4_FEATURE_RO_COMPAT_EXTRA_ISIZE |   EXT4_FEATURE_RO_COMPAT_BTREE_DIR |  EXT4_FEATURE_RO_COMPAT_HUGE_FILE)
+
+#define EXT4_DEF_RESUID 0
+#define EXT4_DEF_RESGID 0
+
+#define EXT4_DEF_INODE_READAHEAD_BLKS 32
+
+#define EXT4_DEFM_DEBUG 0x0001
+#define EXT4_DEFM_BSDGROUPS 0x0002
+#define EXT4_DEFM_XATTR_USER 0x0004
+#define EXT4_DEFM_ACL 0x0008
+#define EXT4_DEFM_UID16 0x0010
+#define EXT4_DEFM_JMODE 0x0060
+#define EXT4_DEFM_JMODE_DATA 0x0020
+#define EXT4_DEFM_JMODE_ORDERED 0x0040
+#define EXT4_DEFM_JMODE_WBACK 0x0060
+
+#define EXT4_DEF_MIN_BATCH_TIME 0
+#define EXT4_DEF_MAX_BATCH_TIME 15000  
+
+#define EXT4_FLEX_SIZE_DIR_ALLOC_SCHEME 4
+
+#define EXT4_NAME_LEN 255
+
+struct ext4_dir_entry {
+ __le32 inode;
+ __le16 rec_len;
+ __le16 name_len;
+ char name[EXT4_NAME_LEN];
+};
+
+struct ext4_dir_entry_2 {
+ __le32 inode;
+ __le16 rec_len;
+ __u8 name_len;
+ __u8 file_type;
+ char name[EXT4_NAME_LEN];
+};
+
+#define EXT4_FT_UNKNOWN 0
+#define EXT4_FT_REG_FILE 1
+#define EXT4_FT_DIR 2
+#define EXT4_FT_CHRDEV 3
+#define EXT4_FT_BLKDEV 4
+#define EXT4_FT_FIFO 5
+#define EXT4_FT_SOCK 6
+#define EXT4_FT_SYMLINK 7
+
+#define EXT4_FT_MAX 8
+
+#define EXT4_DIR_PAD 4
+#define EXT4_DIR_ROUND (EXT4_DIR_PAD - 1)
+#define EXT4_DIR_REC_LEN(name_len) (((name_len) + 8 + EXT4_DIR_ROUND) &   ~EXT4_DIR_ROUND)
+#define EXT4_MAX_REC_LEN ((1<<16)-1)
+
+#define is_dx(dir) (EXT4_HAS_COMPAT_FEATURE(dir->i_sb,   EXT4_FEATURE_COMPAT_DIR_INDEX) &&   (EXT4_I(dir)->i_flags & EXT4_INDEX_FL))
+#define EXT4_DIR_LINK_MAX(dir) (!is_dx(dir) && (dir)->i_nlink >= EXT4_LINK_MAX)
+#define EXT4_DIR_LINK_EMPTY(dir) ((dir)->i_nlink == 2 || (dir)->i_nlink == 1)
+
+#define DX_HASH_LEGACY 0
+#define DX_HASH_HALF_MD4 1
+#define DX_HASH_TEA 2
+#define DX_HASH_LEGACY_UNSIGNED 3
+#define DX_HASH_HALF_MD4_UNSIGNED 4
+#define DX_HASH_TEA_UNSIGNED 5
+
+#endif
+
diff --git a/ext4_utils/ext4_extents.h b/ext4_utils/ext4_extents.h
new file mode 100644
index 00000000..b1290f4b
--- /dev/null
+++ b/ext4_utils/ext4_extents.h
@@ -0,0 +1,88 @@
+/****************************************************************************
+ ****************************************************************************
+ ***
+ ***   This header was automatically generated from a Linux kernel header
+ ***   of the same name, to make information necessary for userspace to
+ ***   call into the kernel available to libc.  It contains only constants,
+ ***   structures, and macros generated from the original header, and thus,
+ ***   contains no copyrightable information.
+ ***
+ ****************************************************************************
+ ****************************************************************************/
+#ifndef _EXT4_EXTENTS
+#define _EXT4_EXTENTS
+
+#include "ext4.h"
+
+#define AGGRESSIVE_TEST_
+
+#define EXTENTS_STATS__
+
+#define CHECK_BINSEARCH__
+
+#define EXT_DEBUG__
+#ifdef EXT_DEBUG
+#define ext_debug(a...) printk(a)
+#else
+#define ext_debug(a...)
+#endif
+
+#define EXT_STATS_
+
+struct ext4_extent {
+ __le32 ee_block;
+ __le16 ee_len;
+ __le16 ee_start_hi;
+ __le32 ee_start_lo;
+};
+
+struct ext4_extent_idx {
+ __le32 ei_block;
+ __le32 ei_leaf_lo;
+ __le16 ei_leaf_hi;
+ __u16 ei_unused;
+};
+
+struct ext4_extent_header {
+ __le16 eh_magic;
+ __le16 eh_entries;
+ __le16 eh_max;
+ __le16 eh_depth;
+ __le32 eh_generation;
+};
+
+#define EXT4_EXT_MAGIC 0xf30a
+
+struct ext4_ext_path {
+ ext4_fsblk_t p_block;
+ __u16 p_depth;
+ struct ext4_extent *p_ext;
+ struct ext4_extent_idx *p_idx;
+ struct ext4_extent_header *p_hdr;
+ struct buffer_head *p_bh;
+};
+
+#define EXT4_EXT_CACHE_NO 0
+#define EXT4_EXT_CACHE_GAP 1
+#define EXT4_EXT_CACHE_EXTENT 2
+
+#define EXT_CONTINUE 0
+#define EXT_BREAK 1
+#define EXT_REPEAT 2
+
+#define EXT_MAX_BLOCK 0xffffffff
+
+#define EXT_INIT_MAX_LEN (1UL << 15)
+#define EXT_UNINIT_MAX_LEN (EXT_INIT_MAX_LEN - 1)
+
+#define EXT_FIRST_EXTENT(__hdr__)   ((struct ext4_extent *) (((char *) (__hdr__)) +   sizeof(struct ext4_extent_header)))
+#define EXT_FIRST_INDEX(__hdr__)   ((struct ext4_extent_idx *) (((char *) (__hdr__)) +   sizeof(struct ext4_extent_header)))
+#define EXT_HAS_FREE_INDEX(__path__)   (le16_to_cpu((__path__)->p_hdr->eh_entries)   < le16_to_cpu((__path__)->p_hdr->eh_max))
+#define EXT_LAST_EXTENT(__hdr__)   (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1)
+#define EXT_LAST_INDEX(__hdr__)   (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_entries) - 1)
+#define EXT_MAX_EXTENT(__hdr__)   (EXT_FIRST_EXTENT((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)
+#define EXT_MAX_INDEX(__hdr__)   (EXT_FIRST_INDEX((__hdr__)) + le16_to_cpu((__hdr__)->eh_max) - 1)
+
+#endif
+
+
diff --git a/ext4_utils/ext4_jbd2.h b/ext4_utils/ext4_jbd2.h
new file mode 100644
index 00000000..d937f5cd
--- /dev/null
+++ b/ext4_utils/ext4_jbd2.h
@@ -0,0 +1,53 @@
+/****************************************************************************
+ ****************************************************************************
+ ***
+ ***   This header was automatically generated from a Linux kernel header
+ ***   of the same name, to make information necessary for userspace to
+ ***   call into the kernel available to libc.  It contains only constants,
+ ***   structures, and macros generated from the original header, and thus,
+ ***   contains no copyrightable information.
+ ***
+ ****************************************************************************
+ ****************************************************************************/
+#ifndef _EXT4_JBD2_H
+#define _EXT4_JBD2_H
+
+#include "ext4.h"
+
+#define EXT4_JOURNAL(inode) (EXT4_SB((inode)->i_sb)->s_journal)
+
+#define EXT4_SINGLEDATA_TRANS_BLOCKS(sb)   (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)   ? 27U : 8U)
+
+#define EXT4_XATTR_TRANS_BLOCKS 6U
+
+#define EXT4_DATA_TRANS_BLOCKS(sb) (EXT4_SINGLEDATA_TRANS_BLOCKS(sb) +   EXT4_XATTR_TRANS_BLOCKS - 2 +   EXT4_MAXQUOTAS_TRANS_BLOCKS(sb))
+
+#define EXT4_META_TRANS_BLOCKS(sb) (EXT4_XATTR_TRANS_BLOCKS +   EXT4_MAXQUOTAS_TRANS_BLOCKS(sb))
+
+#define EXT4_DELETE_TRANS_BLOCKS(sb) (2 * EXT4_DATA_TRANS_BLOCKS(sb) + 64)
+
+#define EXT4_MAX_TRANS_DATA 64U
+
+#define EXT4_RESERVE_TRANS_BLOCKS 12U
+
+#define EXT4_INDEX_EXTRA_TRANS_BLOCKS 8
+
+#define EXT4_QUOTA_TRANS_BLOCKS(sb) 0
+#define EXT4_QUOTA_INIT_BLOCKS(sb) 0
+#define EXT4_QUOTA_DEL_BLOCKS(sb) 0
+#define EXT4_MAXQUOTAS_TRANS_BLOCKS(sb) (MAXQUOTAS*EXT4_QUOTA_TRANS_BLOCKS(sb))
+#define EXT4_MAXQUOTAS_INIT_BLOCKS(sb) (MAXQUOTAS*EXT4_QUOTA_INIT_BLOCKS(sb))
+#define EXT4_MAXQUOTAS_DEL_BLOCKS(sb) (MAXQUOTAS*EXT4_QUOTA_DEL_BLOCKS(sb))
+
+#define ext4_journal_get_undo_access(handle, bh)   __ext4_journal_get_undo_access(__func__, (handle), (bh))
+#define ext4_journal_get_write_access(handle, bh)   __ext4_journal_get_write_access(__func__, (handle), (bh))
+#define ext4_forget(handle, is_metadata, inode, bh, block_nr)   __ext4_forget(__func__, (handle), (is_metadata), (inode), (bh),  (block_nr))
+#define ext4_journal_get_create_access(handle, bh)   __ext4_journal_get_create_access(__func__, (handle), (bh))
+#define ext4_handle_dirty_metadata(handle, inode, bh)   __ext4_handle_dirty_metadata(__func__, (handle), (inode), (bh))
+
+#define EXT4_NOJOURNAL_MAX_REF_COUNT ((unsigned long) 4096)
+
+#define ext4_journal_stop(handle)   __ext4_journal_stop(__func__, (handle))
+
+#endif
+
diff --git a/ext4_utils/ext4_utils.c b/ext4_utils/ext4_utils.c
new file mode 100644
index 00000000..f34985f5
--- /dev/null
+++ b/ext4_utils/ext4_utils.c
@@ -0,0 +1,404 @@
+/*
+ * 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 <fcntl.h>
+#include <arpa/inet.h>
+#include <sys/ioctl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <string.h>
+
+#if defined(__linux__)
+#include <linux/fs.h>
+#elif defined(__APPLE__) && defined(__MACH__)
+#include <sys/disk.h>
+#endif
+
+#include "ext4_utils.h"
+#include "output_file.h"
+#include "backed_block.h"
+#include "uuid.h"
+#include "allocate.h"
+#include "indirect.h"
+#include "extent.h"
+
+#include "ext4.h"
+#include "jbd2.h"
+
+int force = 0;
+struct fs_info info;
+struct fs_aux_info aux_info;
+
+/* returns 1 if a is a power of b */
+static int is_power_of(int a, int b)
+{
+	while (a > b) {
+		if (a % b)
+			return 0;
+		a /= b;
+	}
+
+	return (a == b) ? 1 : 0;
+}
+
+/* Returns 1 if the bg contains a backup superblock.  On filesystems with
+   the sparse_super feature, only block groups 0, 1, and powers of 3, 5,
+   and 7 have backup superblocks.  Otherwise, all block groups have backup
+   superblocks */
+int ext4_bg_has_super_block(int bg)
+{
+	/* Without sparse_super, every block group has a superblock */
+	if (!(info.feat_ro_compat & EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER))
+		return 1;
+
+	if (bg == 0 || bg == 1)
+		return 1;
+
+	if (is_power_of(bg, 3) || is_power_of(bg, 5) || is_power_of(bg, 7))
+		return 1;
+
+	return 0;
+}
+
+/* Write the filesystem image to a file */
+void write_ext4_image(const char *filename, int gz, int sparse)
+{
+	int ret = 0;
+	struct output_file *out = open_output_file(filename, gz, sparse);
+	off_t off;
+
+	if (!out)
+		return;
+
+	/* The write_data* functions expect only block aligned calls.
+	 * This is not an issue, except when we write out the super
+	 * block on a system with a block size > 1K.  So, we need to
+	 * deal with that here.
+	 */
+	if (info.block_size > 1024) {
+		u8 buf[4096] = { 0 }; 	/* The larget supported ext4 block size */
+		memcpy(buf + 1024, (u8*)aux_info.sb, 1024);
+		write_data_block(out, 0, buf, info.block_size);
+
+	} else {
+		write_data_block(out, 1024, (u8*)aux_info.sb, 1024);
+	}
+
+	write_data_block(out, (u64)(aux_info.first_data_block + 1) * info.block_size,
+			 (u8*)aux_info.bg_desc,
+			 aux_info.bg_desc_blocks * info.block_size);
+
+	for_each_data_block(write_data_block, write_data_file, out);
+
+	pad_output_file(out, info.len);
+
+	close_output_file(out);
+}
+
+/* Compute the rest of the parameters of the filesystem from the basic info */
+void ext4_create_fs_aux_info()
+{
+	aux_info.first_data_block = (info.block_size > 1024) ? 0 : 1;
+	aux_info.len_blocks = info.len / info.block_size;
+	aux_info.inode_table_blocks = DIV_ROUND_UP(info.inodes_per_group * info.inode_size,
+		info.block_size);
+	aux_info.groups = DIV_ROUND_UP(aux_info.len_blocks - aux_info.first_data_block,
+		info.blocks_per_group);
+	aux_info.blocks_per_ind = info.block_size / sizeof(u32);
+	aux_info.blocks_per_dind = aux_info.blocks_per_ind * aux_info.blocks_per_ind;
+	aux_info.blocks_per_tind = aux_info.blocks_per_dind * aux_info.blocks_per_dind;
+
+	aux_info.bg_desc_blocks =
+		DIV_ROUND_UP(aux_info.groups * sizeof(struct ext2_group_desc),
+			info.block_size);
+
+	aux_info.bg_desc_reserve_blocks =
+		DIV_ROUND_UP(aux_info.groups * 1024 * sizeof(struct ext2_group_desc),
+			info.block_size) - aux_info.bg_desc_blocks;
+
+	if (aux_info.bg_desc_reserve_blocks > aux_info.blocks_per_ind)
+		aux_info.bg_desc_reserve_blocks = aux_info.blocks_per_ind;
+
+	aux_info.default_i_flags = EXT4_NOATIME_FL;
+
+	u32 last_group_size = aux_info.len_blocks % info.blocks_per_group;
+	u32 last_header_size = 2 + aux_info.inode_table_blocks;
+	if (ext4_bg_has_super_block(aux_info.groups - 1))
+		last_header_size += 1 + aux_info.bg_desc_blocks +
+			aux_info.bg_desc_reserve_blocks;
+	if (last_group_size > 0 && last_group_size < last_header_size) {
+		aux_info.groups--;
+		aux_info.len_blocks -= last_group_size;
+	}
+
+	aux_info.sb = calloc(info.block_size, 1);
+	if (!aux_info.sb)
+		critical_error_errno("calloc");
+
+	aux_info.bg_desc = calloc(info.block_size, aux_info.bg_desc_blocks);
+	if (!aux_info.bg_desc)
+		critical_error_errno("calloc");
+}
+
+void ext4_free_fs_aux_info()
+{
+	free(aux_info.sb);
+	free(aux_info.bg_desc);
+}
+
+/* Fill in the superblock memory buffer based on the filesystem parameters */
+void ext4_fill_in_sb()
+{
+	unsigned int i;
+	struct ext4_super_block *sb = aux_info.sb;
+
+	sb->s_inodes_count = info.inodes_per_group * aux_info.groups;
+	sb->s_blocks_count_lo = aux_info.len_blocks;
+	sb->s_r_blocks_count_lo = 0;
+	sb->s_free_blocks_count_lo = 0;
+	sb->s_free_inodes_count = 0;
+	sb->s_first_data_block = aux_info.first_data_block;
+	sb->s_log_block_size = log_2(info.block_size / 1024);
+	sb->s_obso_log_frag_size = log_2(info.block_size / 1024);
+	sb->s_blocks_per_group = info.blocks_per_group;
+	sb->s_obso_frags_per_group = info.blocks_per_group;
+	sb->s_inodes_per_group = info.inodes_per_group;
+	sb->s_mtime = 0;
+	sb->s_wtime = 0;
+	sb->s_mnt_count = 0;
+	sb->s_max_mnt_count = 0xFFFF;
+	sb->s_magic = EXT4_SUPER_MAGIC;
+	sb->s_state = EXT4_VALID_FS;
+	sb->s_errors = EXT4_ERRORS_RO;
+	sb->s_minor_rev_level = 0;
+	sb->s_lastcheck = 0;
+	sb->s_checkinterval = 0;
+	sb->s_creator_os = EXT4_OS_LINUX;
+	sb->s_rev_level = EXT4_DYNAMIC_REV;
+	sb->s_def_resuid = EXT4_DEF_RESUID;
+	sb->s_def_resgid = EXT4_DEF_RESGID;
+
+	sb->s_first_ino = EXT4_GOOD_OLD_FIRST_INO;
+	sb->s_inode_size = info.inode_size;
+	sb->s_block_group_nr = 0;
+	sb->s_feature_compat = info.feat_compat;
+	sb->s_feature_incompat = info.feat_incompat;
+	sb->s_feature_ro_compat = info.feat_ro_compat;
+	generate_uuid("extandroid/make_ext4fs", info.label, sb->s_uuid);
+	memset(sb->s_volume_name, 0, sizeof(sb->s_volume_name));
+	strncpy(sb->s_volume_name, info.label, sizeof(sb->s_volume_name));
+	memset(sb->s_last_mounted, 0, sizeof(sb->s_last_mounted));
+	sb->s_algorithm_usage_bitmap = 0;
+
+	sb->s_reserved_gdt_blocks = aux_info.bg_desc_reserve_blocks;
+	sb->s_prealloc_blocks = 0;
+	sb->s_prealloc_dir_blocks = 0;
+
+	//memcpy(sb->s_journal_uuid, sb->s_uuid, sizeof(sb->s_journal_uuid));
+	if (info.feat_compat & EXT4_FEATURE_COMPAT_HAS_JOURNAL)
+		sb->s_journal_inum = EXT4_JOURNAL_INO;
+	sb->s_journal_dev = 0;
+	sb->s_last_orphan = 0;
+	sb->s_hash_seed[0] = 0; /* FIXME */
+	sb->s_def_hash_version = DX_HASH_TEA;
+	sb->s_reserved_char_pad = EXT4_JNL_BACKUP_BLOCKS;
+	sb->s_desc_size = sizeof(struct ext2_group_desc);
+	sb->s_default_mount_opts = 0; /* FIXME */
+	sb->s_first_meta_bg = 0;
+	sb->s_mkfs_time = 0;
+	//sb->s_jnl_blocks[17]; /* FIXME */
+
+	sb->s_blocks_count_hi = aux_info.len_blocks >> 32;
+	sb->s_r_blocks_count_hi = 0;
+	sb->s_free_blocks_count_hi = 0;
+	sb->s_min_extra_isize = sizeof(struct ext4_inode) -
+		EXT4_GOOD_OLD_INODE_SIZE;
+	sb->s_want_extra_isize = sizeof(struct ext4_inode) -
+		EXT4_GOOD_OLD_INODE_SIZE;
+	sb->s_flags = 0;
+	sb->s_raid_stride = 0;
+	sb->s_mmp_interval = 0;
+	sb->s_mmp_block = 0;
+	sb->s_raid_stripe_width = 0;
+	sb->s_log_groups_per_flex = 0;
+	sb->s_kbytes_written = 0;
+
+	for (i = 0; i < aux_info.groups; i++) {
+		u64 group_start_block = aux_info.first_data_block + i *
+			info.blocks_per_group;
+		u32 header_size = 0;
+		if (ext4_bg_has_super_block(i)) {
+			if (i != 0) {
+				queue_data_block((u8 *)sb, info.block_size, group_start_block);
+				queue_data_block((u8 *)aux_info.bg_desc,
+					aux_info.bg_desc_blocks * info.block_size,
+					group_start_block + 1);
+			}
+			header_size = 1 + aux_info.bg_desc_blocks + aux_info.bg_desc_reserve_blocks;
+		}
+
+		aux_info.bg_desc[i].bg_block_bitmap = group_start_block + header_size;
+		aux_info.bg_desc[i].bg_inode_bitmap = group_start_block + header_size + 1;
+		aux_info.bg_desc[i].bg_inode_table = group_start_block + header_size + 2;
+
+		aux_info.bg_desc[i].bg_free_blocks_count = sb->s_blocks_per_group;
+		aux_info.bg_desc[i].bg_free_inodes_count = sb->s_inodes_per_group;
+		aux_info.bg_desc[i].bg_used_dirs_count = 0;
+	}
+}
+
+void ext4_create_resize_inode()
+{
+	struct block_allocation *reserve_inode_alloc = create_allocation();
+	u32 reserve_inode_len = 0;
+	unsigned int i;
+
+	struct ext4_inode *inode = get_inode(EXT4_RESIZE_INO);
+	if (inode == NULL) {
+		error("failed to get resize inode");
+		return;
+	}
+
+	for (i = 0; i < aux_info.groups; i++) {
+		if (ext4_bg_has_super_block(i)) {
+			u64 group_start_block = aux_info.first_data_block + i *
+				info.blocks_per_group;
+			u32 reserved_block_start = group_start_block + 1 +
+				aux_info.bg_desc_blocks;
+			u32 reserved_block_len = aux_info.bg_desc_reserve_blocks;
+			append_region(reserve_inode_alloc, reserved_block_start,
+				reserved_block_len, i);
+			reserve_inode_len += reserved_block_len;
+		}
+	}
+
+	inode_attach_resize(inode, reserve_inode_alloc);
+
+	inode->i_mode = S_IFREG | S_IRUSR | S_IWUSR;
+	inode->i_links_count = 1;
+
+	free_alloc(reserve_inode_alloc);
+}
+
+/* Allocate the blocks to hold a journal inode and connect them to the
+   reserved journal inode */
+void ext4_create_journal_inode()
+{
+	struct ext4_inode *inode = get_inode(EXT4_JOURNAL_INO);
+	if (inode == NULL) {
+		error("failed to get journal inode");
+		return;
+	}
+
+	u8 *journal_data = inode_allocate_data_extents(inode,
+			info.journal_blocks * info.block_size,
+			info.block_size);
+	if (!journal_data) {
+		error("failed to allocate extents for journal data");
+		return;
+	}
+
+	inode->i_mode = S_IFREG | S_IRUSR | S_IWUSR;
+	inode->i_links_count = 1;
+
+	journal_superblock_t *jsb = (journal_superblock_t *)journal_data;
+	jsb->s_header.h_magic = htonl(JBD2_MAGIC_NUMBER);
+	jsb->s_header.h_blocktype = htonl(JBD2_SUPERBLOCK_V2);
+	jsb->s_blocksize = htonl(info.block_size);
+	jsb->s_maxlen = htonl(info.journal_blocks);
+	jsb->s_nr_users = htonl(1);
+	jsb->s_first = htonl(1);
+	jsb->s_sequence = htonl(1);
+
+	memcpy(aux_info.sb->s_jnl_blocks, &inode->i_block, sizeof(inode->i_block));
+}
+
+/* Update the number of free blocks and inodes in the filesystem and in each
+   block group */
+void ext4_update_free()
+{
+	unsigned int i;
+
+	for (i = 0; i < aux_info.groups; i++) {
+		u32 bg_free_blocks = get_free_blocks(i);
+		u32 bg_free_inodes = get_free_inodes(i);
+
+		aux_info.bg_desc[i].bg_free_blocks_count = bg_free_blocks;
+		aux_info.sb->s_free_blocks_count_lo += bg_free_blocks;
+
+		aux_info.bg_desc[i].bg_free_inodes_count = bg_free_inodes;
+		aux_info.sb->s_free_inodes_count += bg_free_inodes;
+
+		aux_info.bg_desc[i].bg_used_dirs_count += get_directories(i);
+	}
+}
+
+static u64 get_block_device_size(const char *filename)
+{
+	int fd = open(filename, O_RDONLY);
+	u64 size = 0;
+	int ret;
+
+	if (fd < 0)
+		return 0;
+
+#if defined(__linux__)
+	ret = ioctl(fd, BLKGETSIZE64, &size);
+#elif defined(__APPLE__) && defined(__MACH__)
+	ret = ioctl(fd, DKIOCGETBLOCKCOUNT, &size);
+#else
+	return 0;
+#endif
+
+	close(fd);
+
+	if (ret)
+		return 0;
+
+	return size;
+}
+
+u64 get_file_size(const char *filename)
+{
+	struct stat buf;
+	int ret;
+
+	ret = stat(filename, &buf);
+	if (ret)
+		return 0;
+
+	if (S_ISREG(buf.st_mode))
+		return buf.st_size;
+	else if (S_ISBLK(buf.st_mode))
+		return get_block_device_size(filename);
+	else
+		return 0;
+}
+
+u64 parse_num(const char *arg)
+{
+	char *endptr;
+	u64 num = strtoull(arg, &endptr, 10);
+	if (*endptr == 'k' || *endptr == 'K')
+		num *= 1024LL;
+	else if (*endptr == 'm' || *endptr == 'M')
+		num *= 1024LL * 1024LL;
+	else if (*endptr == 'g' || *endptr == 'G')
+		num *= 1024LL * 1024LL * 1024LL;
+
+	return num;
+}
+
diff --git a/ext4_utils/ext4_utils.h b/ext4_utils/ext4_utils.h
new file mode 100644
index 00000000..697c8d90
--- /dev/null
+++ b/ext4_utils/ext4_utils.h
@@ -0,0 +1,129 @@
+/*
+ * 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 _EXT4_UTILS_H_
+#define _EXT4_UTILS_H_
+
+#include <sys/types.h>
+#include <errno.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+extern int force;
+
+#define warn(fmt, args...) do { fprintf(stderr, "warning: %s: " fmt "\n", __func__, ## args); } while (0)
+#define error(fmt, args...) do { fprintf(stderr, "error: %s: " fmt "\n", __func__, ## args); if (!force) exit(EXIT_FAILURE); } while (0)
+#define error_errno(s) error(s ": %s", strerror(errno))
+#define critical_error(fmt, args...) do { fprintf(stderr, "critical error: %s: " fmt "\n", __func__, ## args); exit(EXIT_FAILURE); } while (0)
+#define critical_error_errno(s) critical_error(s ": %s", strerror(errno))
+
+#define EXT4_SUPER_MAGIC 0xEF53
+#define EXT4_JNL_BACKUP_BLOCKS 1
+
+#define min(a, b) ((a) < (b) ? (a) : (b))
+
+#define DIV_ROUND_UP(x, y) (((x) + (y) - 1)/(y))
+#define ALIGN(x, y) ((y) * DIV_ROUND_UP((x), (y)))
+
+#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 unsigned int u32;
+typedef unsigned short int u16;
+typedef unsigned char u8;
+
+struct block_group_info;
+
+struct ext2_group_desc {
+	__le32 bg_block_bitmap;
+	__le32 bg_inode_bitmap;
+	__le32 bg_inode_table;
+	__le16 bg_free_blocks_count;
+	__le16 bg_free_inodes_count;
+	__le16 bg_used_dirs_count;
+	__le16 bg_pad;
+	__le32 bg_reserved[3];
+};
+
+struct fs_info {
+	u64 len;
+	u32 block_size;
+	u32 blocks_per_group;
+	u32 inodes_per_group;
+	u32 inode_size;
+	u32 inodes;
+	u32 journal_blocks;
+	u16 feat_ro_compat;
+	u16 feat_compat;
+	u16 feat_incompat;
+	const char *label;
+	u8 no_journal;
+};
+
+struct fs_aux_info {
+	struct ext4_super_block *sb;
+	struct ext2_group_desc *bg_desc;
+	struct block_group_info *bgs;
+	u32 first_data_block;
+	u64 len_blocks;
+	u32 inode_table_blocks;
+	u32 groups;
+	u32 bg_desc_blocks;
+	u32 bg_desc_reserve_blocks;
+	u32 default_i_flags;
+	u32 blocks_per_ind;
+	u32 blocks_per_dind;
+	u32 blocks_per_tind;
+};
+
+extern struct fs_info info;
+extern struct fs_aux_info aux_info;
+
+static inline int log_2(int j)
+{
+	int i;
+
+	for (i = 0; j > 0; i++)
+		j >>= 1;
+
+	return i - 1;
+}
+
+int ext4_bg_has_super_block(int bg);
+void write_ext4_image(const char *filename, int gz, int sparse);
+void ext4_create_fs_aux_info(void);
+void ext4_free_fs_aux_info(void);
+void ext4_fill_in_sb(void);
+void ext4_create_resize_inode(void);
+void ext4_create_journal_inode(void);
+void ext4_update_free(void);
+u64 get_file_size(const char *filename);
+u64 parse_num(const char *arg);
+
+#endif
diff --git a/ext4_utils/extent.c b/ext4_utils/extent.c
new file mode 100644
index 00000000..1d2581d9
--- /dev/null
+++ b/ext4_utils/extent.c
@@ -0,0 +1,231 @@
+/*
+ * 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 <stdio.h>
+
+#include "ext4_utils.h"
+#include "ext4.h"
+#include "ext4_extents.h"
+#include "backed_block.h"
+
+#include "extent.h"
+
+/* Creates data buffers for the first backing_len bytes of a block allocation
+   and queues them to be written */
+static u8 *extent_create_backing(struct block_allocation *alloc,
+	u64 backing_len)
+{
+	u8 *data = calloc(backing_len, 1);
+	if (!data)
+		critical_error_errno("calloc");
+
+	u8 *ptr = data;
+	for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) {
+		u32 region_block;
+		u32 region_len;
+		u32 len;
+		get_region(alloc, &region_block, &region_len);
+
+		len = min(region_len * info.block_size, backing_len);
+
+		queue_data_block(ptr, len, region_block);
+		ptr += len;
+		backing_len -= len;
+	}
+
+	return data;
+}
+
+/* Queues each chunk of a file to be written to contiguous data block
+   regions */
+static void extent_create_backing_file(struct block_allocation *alloc,
+	u64 backing_len, const char *filename)
+{
+	off_t offset = 0;
+	for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) {
+		u32 region_block;
+		u32 region_len;
+		u32 len;
+		get_region(alloc, &region_block, &region_len);
+
+		len = min(region_len * info.block_size, backing_len);
+
+		queue_data_file(filename, offset, len, region_block);
+		offset += len;
+		backing_len -= len;
+	}
+}
+
+static struct block_allocation *do_inode_allocate_extents(
+	struct ext4_inode *inode, u64 len)
+{
+	u32 block_len = DIV_ROUND_UP(len, info.block_size);
+	struct block_allocation *alloc = allocate_blocks(block_len + 1);
+	u32 extent_block = 0;
+	u32 file_block = 0;
+	struct ext4_extent *extent;
+	u64 blocks;
+
+	if (alloc == NULL) {
+		error("Failed to allocate %d blocks\n", block_len + 1);
+		return NULL;
+	}
+
+	int allocation_len = block_allocation_num_regions(alloc);
+	if (allocation_len <= 3) {
+		reduce_allocation(alloc, 1);
+	} else {
+		reserve_oob_blocks(alloc, 1);
+		extent_block = get_oob_block(alloc, 0);
+	}
+
+	if (!extent_block) {
+		struct ext4_extent_header *hdr =
+			(struct ext4_extent_header *)&inode->i_block[0];
+		hdr->eh_magic = EXT4_EXT_MAGIC;
+		hdr->eh_entries = allocation_len;
+		hdr->eh_max = 3;
+		hdr->eh_generation = 0;
+		hdr->eh_depth = 0;
+
+		extent = (struct ext4_extent *)&inode->i_block[3];
+	} else {
+		struct ext4_extent_header *hdr =
+			(struct ext4_extent_header *)&inode->i_block[0];
+		hdr->eh_magic = EXT4_EXT_MAGIC;
+		hdr->eh_entries = 1;
+		hdr->eh_max = 3;
+		hdr->eh_generation = 0;
+		hdr->eh_depth = 1;
+
+		struct ext4_extent_idx *idx =
+			(struct ext4_extent_idx *)&inode->i_block[3];
+		idx->ei_block = 0;
+		idx->ei_leaf_lo = extent_block;
+		idx->ei_leaf_hi = 0;
+		idx->ei_unused = 0;
+
+		u8 *data = calloc(info.block_size, 1);
+		if (!data)
+			critical_error_errno("calloc");
+
+		queue_data_block(data, info.block_size, extent_block);
+
+		if (((int)(info.block_size - sizeof(struct ext4_extent_header) /
+				sizeof(struct ext4_extent))) < allocation_len) {
+			error("File size %llu is too big to fit in a single extent block\n",
+					len);
+			return NULL;
+		}
+
+		hdr = (struct ext4_extent_header *)data;
+		hdr->eh_magic = EXT4_EXT_MAGIC;
+		hdr->eh_entries = allocation_len;
+		hdr->eh_max = (info.block_size - sizeof(struct ext4_extent_header)) /
+			sizeof(struct ext4_extent);
+		hdr->eh_generation = 0;
+		hdr->eh_depth = 0;
+
+		extent = (struct ext4_extent *)(data +
+			sizeof(struct ext4_extent_header));
+	}
+
+	for (; !last_region(alloc); extent++, get_next_region(alloc)) {
+		u32 region_block;
+		u32 region_len;
+
+		get_region(alloc, &region_block, &region_len);
+		extent->ee_block = file_block;
+		extent->ee_len = region_len;
+		extent->ee_start_hi = 0;
+		extent->ee_start_lo = region_block;
+		file_block += region_len;
+	}
+
+	if (extent_block)
+		block_len += 1;
+
+	blocks = (u64)block_len * info.block_size / 512;
+
+	inode->i_flags |= EXT4_EXTENTS_FL;
+	inode->i_size_lo = len;
+	inode->i_size_high = len >> 32;
+	inode->i_blocks_lo = blocks;
+	inode->osd2.linux2.l_i_blocks_high = blocks >> 32;
+
+	rewind_alloc(alloc);
+
+	return alloc;
+}
+
+/* Allocates enough blocks to hold len bytes, with backing_len bytes in a data
+   buffer, and connects them to an inode.  Returns a pointer to the data
+   buffer. */
+u8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len,
+	u64 backing_len)
+{
+	struct block_allocation *alloc;
+	u8 *data = NULL;
+
+	alloc = do_inode_allocate_extents(inode, len);
+	if (alloc == NULL) {
+		error("failed to allocate extents for %llu bytes", len);
+		return NULL;
+	}
+
+	if (backing_len) {
+		data = extent_create_backing(alloc, backing_len);
+		if (!data)
+			error("failed to create backing for %llu bytes", backing_len);
+	}
+
+	free_alloc(alloc);
+
+	return data;
+}
+
+/* Allocates enough blocks to hold len bytes, queues them to be written
+   from a file, and connects them to an inode. */
+void inode_allocate_file_extents(struct ext4_inode *inode, u64 len,
+	const char *filename)
+{
+	struct block_allocation *alloc;
+
+	alloc = do_inode_allocate_extents(inode, len);
+	if (alloc == NULL) {
+		error("failed to allocate extents for %llu bytes", len);
+		return;
+	}
+
+	extent_create_backing_file(alloc, len, filename);
+
+	free_alloc(alloc);
+}
+
+/* Allocates enough blocks to hold len bytes and connects them to an inode */
+void inode_allocate_extents(struct ext4_inode *inode, u64 len)
+{
+	struct block_allocation *alloc;
+
+	alloc = do_inode_allocate_extents(inode, len);
+	if (alloc == NULL) {
+		error("failed to allocate extents for %llu bytes", len);
+		return;
+	}
+
+	free_alloc(alloc);
+}
diff --git a/ext4_utils/extent.h b/ext4_utils/extent.h
new file mode 100644
index 00000000..a1ddeb15
--- /dev/null
+++ b/ext4_utils/extent.h
@@ -0,0 +1,30 @@
+/*
+ * 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 _EXTENT_H_
+#define _EXTENT_H_
+
+#include "allocate.h"
+#include "ext4_utils.h"
+
+void inode_allocate_extents(struct ext4_inode *inode, u64 len);
+void inode_allocate_file_extents(struct ext4_inode *inode, u64 len,
+	const char *filename);
+u8 *inode_allocate_data_extents(struct ext4_inode *inode, u64 len,
+	u64 backing_len);
+void free_extent_blocks();
+
+#endif
diff --git a/ext4_utils/indirect.c b/ext4_utils/indirect.c
new file mode 100644
index 00000000..2d9d7104
--- /dev/null
+++ b/ext4_utils/indirect.c
@@ -0,0 +1,504 @@
+/*
+ * 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 <stdio.h>
+
+#include "ext4_utils.h"
+#include "ext4.h"
+#include "ext4_extents.h"
+#include "backed_block.h"
+#include "indirect.h"
+#include "allocate.h"
+
+/* Creates data buffers for the first backing_len bytes of a block allocation
+   and queues them to be written */
+static u8 *create_backing(struct block_allocation *alloc,
+		unsigned long backing_len)
+{
+	if (DIV_ROUND_UP(backing_len, info.block_size) > EXT4_NDIR_BLOCKS)
+		critical_error("indirect backing larger than %d blocks", EXT4_NDIR_BLOCKS);
+
+	u8 *data = calloc(backing_len, 1);
+	if (!data)
+		critical_error_errno("calloc");
+
+	u8 *ptr = data;
+	for (; alloc != NULL && backing_len > 0; get_next_region(alloc)) {
+		u32 region_block;
+		u32 region_len;
+		u32 len;
+		get_region(alloc, &region_block, &region_len);
+
+		len = min(region_len * info.block_size, backing_len);
+
+		queue_data_block(ptr, len, region_block);
+		ptr += len;
+		backing_len -= len;
+	}
+
+	return data;
+}
+
+static void reserve_indirect_block(struct block_allocation *alloc, int len)
+{
+	if (reserve_oob_blocks(alloc, 1)) {
+		error("failed to reserve oob block");
+		return;
+	}
+
+	if (advance_blocks(alloc, len)) {
+		error("failed to advance %d blocks", len);
+		return;
+	}
+}
+
+static void reserve_dindirect_block(struct block_allocation *alloc, int len)
+{
+	if (reserve_oob_blocks(alloc, 1)) {
+		error("failed to reserve oob block");
+		return;
+	}
+
+	while (len > 0) {
+		int ind_block_len = min((int)aux_info.blocks_per_ind, len);
+
+		reserve_indirect_block(alloc, ind_block_len);
+
+		len -= ind_block_len;
+	}
+
+}
+
+static void reserve_tindirect_block(struct block_allocation *alloc, int len)
+{
+	if (reserve_oob_blocks(alloc, 1)) {
+		error("failed to reserve oob block");
+		return;
+	}
+
+	while (len > 0) {
+		int dind_block_len = min((int)aux_info.blocks_per_dind, len);
+
+		reserve_dindirect_block(alloc, dind_block_len);
+
+		len -= dind_block_len;
+	}
+}
+
+static void fill_indirect_block(u32 *ind_block, int len, struct block_allocation *alloc)
+{
+	int i;
+	for (i = 0; i < len; i++) {
+		ind_block[i] = get_block(alloc, i);
+	}
+}
+
+static void fill_dindirect_block(u32 *dind_block, int len, struct block_allocation *alloc)
+{
+	int i;
+	u32 ind_block;
+
+	for (i = 0; len >  0; i++) {
+		ind_block = get_oob_block(alloc, 0);
+		if (advance_oob_blocks(alloc, 1)) {
+			error("failed to reserve oob block");
+			return;
+		}
+
+		dind_block[i] = ind_block;
+
+		u32 *ind_block_data = calloc(info.block_size, 1);
+		queue_data_block((u8*)ind_block_data, info.block_size, ind_block);
+		int ind_block_len = min((int)aux_info.blocks_per_ind, len);
+
+		fill_indirect_block(ind_block_data, ind_block_len, alloc);
+
+		if (advance_blocks(alloc, ind_block_len)) {
+			error("failed to advance %d blocks", ind_block_len);
+			return;
+		}
+
+		len -= ind_block_len;
+	}
+}
+
+static void fill_tindirect_block(u32 *tind_block, int len, struct block_allocation *alloc)
+{
+	int i;
+	u32 dind_block;
+
+	for (i = 0; len > 0; i++) {
+		dind_block = get_oob_block(alloc, 0);
+		if (advance_oob_blocks(alloc, 1)) {
+			error("failed to reserve oob block");
+			return;
+		}
+
+		tind_block[i] = dind_block;
+
+		u32 *dind_block_data = calloc(info.block_size, 1);
+		queue_data_block((u8*)dind_block_data, info.block_size, dind_block);
+		int dind_block_len = min((int)aux_info.blocks_per_dind, len);
+
+		fill_dindirect_block(dind_block_data, dind_block_len, alloc);
+
+		len -= dind_block_len;
+	}
+}
+
+/* Given an allocation, attach as many blocks as possible to direct inode
+   blocks, and return the rest */
+static int inode_attach_direct_blocks(struct ext4_inode *inode,
+		struct block_allocation *alloc, u32 *block_len)
+{
+	int len = min(*block_len, EXT4_NDIR_BLOCKS);
+	int i;
+
+	for (i = 0; i < len; i++) {
+		inode->i_block[i] = get_block(alloc, i);
+	}
+
+	if (advance_blocks(alloc, len)) {
+		error("failed to advance %d blocks", len);
+		return -1;
+	}
+
+	*block_len -= len;
+	return 0;
+}
+
+/* Given an allocation, attach as many blocks as possible to indirect blocks,
+   and return the rest
+   Assumes that the blocks necessary to hold the indirect blocks were included
+   as part of the allocation */
+static int inode_attach_indirect_blocks(struct ext4_inode *inode,
+		struct block_allocation *alloc, u32 *block_len)
+{
+	int len = min(*block_len, aux_info.blocks_per_ind);
+
+	int ind_block = get_oob_block(alloc, 0);
+	inode->i_block[EXT4_IND_BLOCK] = ind_block;
+
+	if (advance_oob_blocks(alloc, 1)) {
+		error("failed to advance oob block");
+		return -1;
+	}
+
+	u32 *ind_block_data = calloc(info.block_size, 1);
+	queue_data_block((u8*)ind_block_data, info.block_size, ind_block);
+
+	fill_indirect_block(ind_block_data, len, alloc);
+
+	if (advance_blocks(alloc, len)) {
+		error("failed to advance %d blocks", len);
+		return -1;
+	}
+
+	*block_len -= len;
+	return 0;
+}
+
+/* Given an allocation, attach as many blocks as possible to doubly indirect
+   blocks, and return the rest.
+   Assumes that the blocks necessary to hold the indirect and doubly indirect
+   blocks were included as part of the allocation */
+static int inode_attach_dindirect_blocks(struct ext4_inode *inode,
+		struct block_allocation *alloc, u32 *block_len)
+{
+	int len = min(*block_len, aux_info.blocks_per_dind);
+
+	int dind_block = get_oob_block(alloc, 0);
+	inode->i_block[EXT4_DIND_BLOCK] = dind_block;
+
+	if (advance_oob_blocks(alloc, 1)) {
+		error("failed to advance oob block");
+		return -1;
+	}
+
+	u32 *dind_block_data = calloc(info.block_size, 1);
+	queue_data_block((u8*)dind_block_data, info.block_size, dind_block);
+
+	fill_dindirect_block(dind_block_data, len, alloc);
+
+	if (advance_blocks(alloc, len)) {
+		error("failed to advance %d blocks", len);
+		return -1;
+	}
+
+	*block_len -= len;
+	return 0;
+}
+
+/* Given an allocation, attach as many blocks as possible to triply indirect
+   blocks, and return the rest.
+   Assumes that the blocks necessary to hold the indirect, doubly indirect and
+   triply indirect blocks were included as part of the allocation */
+static int inode_attach_tindirect_blocks(struct ext4_inode *inode,
+		struct block_allocation *alloc, u32 *block_len)
+{
+	int len = min(*block_len, aux_info.blocks_per_tind);
+
+	int tind_block = get_oob_block(alloc, 0);
+	inode->i_block[EXT4_TIND_BLOCK] = tind_block;
+
+	if (advance_oob_blocks(alloc, 1)) {
+		error("failed to advance oob block");
+		return -1;
+	}
+
+	u32 *tind_block_data = calloc(info.block_size, 1);
+	queue_data_block((u8*)tind_block_data, info.block_size, tind_block);
+
+	fill_tindirect_block(tind_block_data, len, alloc);
+
+	if (advance_blocks(alloc, len)) {
+		error("failed to advance %d blocks", len);
+		return -1;
+	}
+
+	*block_len -= len;
+	return 0;
+}
+
+static void reserve_all_indirect_blocks(struct block_allocation *alloc, u32 len)
+{
+	if (len <= EXT4_NDIR_BLOCKS)
+		return;
+
+	len -= EXT4_NDIR_BLOCKS;
+	advance_blocks(alloc, EXT4_NDIR_BLOCKS);
+
+	u32 ind_block_len = min(aux_info.blocks_per_ind, len);
+	reserve_indirect_block(alloc, ind_block_len);
+
+	len -= ind_block_len;
+	if (len == 0)
+		return;
+
+	u32 dind_block_len = min(aux_info.blocks_per_dind, len);
+	reserve_dindirect_block(alloc, dind_block_len);
+
+	len -= dind_block_len;
+	if (len == 0)
+		return;
+
+	u32 tind_block_len = min(aux_info.blocks_per_tind, len);
+	reserve_tindirect_block(alloc, tind_block_len);
+
+	len -= tind_block_len;
+	if (len == 0)
+		return;
+
+	error("%d blocks remaining", len);
+}
+
+static u32 indirect_blocks_needed(u32 len)
+{
+	u32 ind = 0;
+
+	if (len <= EXT4_NDIR_BLOCKS)
+		return ind;
+
+	len -= EXT4_NDIR_BLOCKS;
+
+	/* We will need an indirect block for the rest of the blocks */
+	ind += DIV_ROUND_UP(len, aux_info.blocks_per_ind);
+
+	if (len <= aux_info.blocks_per_ind)
+		return ind;
+
+	len -= aux_info.blocks_per_ind;
+
+	ind += DIV_ROUND_UP(len, aux_info.blocks_per_dind);
+
+	if (len <= aux_info.blocks_per_dind)
+		return ind;
+
+	len -= aux_info.blocks_per_dind;
+
+	ind += DIV_ROUND_UP(len, aux_info.blocks_per_tind);
+
+	if (len <= aux_info.blocks_per_tind)
+		return ind;
+
+	critical_error("request too large");
+	return 0;
+}
+
+static int do_inode_attach_indirect(struct ext4_inode *inode,
+		struct block_allocation *alloc, u32 block_len)
+{
+	u32 count = block_len;
+
+	if (inode_attach_direct_blocks(inode, alloc, &count)) {
+		error("failed to attach direct blocks to inode");
+		return -1;
+	}
+
+	if (count > 0) {
+		if (inode_attach_indirect_blocks(inode, alloc, &count)) {
+			error("failed to attach indirect blocks to inode");
+			return -1;
+		}
+	}
+
+	if (count > 0) {
+		if (inode_attach_dindirect_blocks(inode, alloc, &count)) {
+			error("failed to attach dindirect blocks to inode");
+			return -1;
+		}
+	}
+
+	if (count > 0) {
+		if (inode_attach_tindirect_blocks(inode, alloc, &count)) {
+			error("failed to attach tindirect blocks to inode");
+			return -1;
+		}
+	}
+
+	if (count) {
+		error("blocks left after triply-indirect allocation");
+		return -1;
+	}
+
+	rewind_alloc(alloc);
+
+	return 0;
+}
+
+static struct block_allocation *do_inode_allocate_indirect(
+		struct ext4_inode *inode, u32 block_len)
+{
+	u32 indirect_len = indirect_blocks_needed(block_len);
+
+	struct block_allocation *alloc = allocate_blocks(block_len + indirect_len);
+
+	if (alloc == NULL) {
+		error("Failed to allocate %d blocks", block_len + indirect_len);
+		return NULL;
+	}
+
+	return alloc;
+}
+
+/* Allocates enough blocks to hold len bytes and connects them to an inode */
+void inode_allocate_indirect(struct ext4_inode *inode, unsigned long len)
+{
+	struct block_allocation *alloc;
+	u32 block_len = DIV_ROUND_UP(len, info.block_size);
+	u32 indirect_len = indirect_blocks_needed(block_len);
+
+	alloc = do_inode_allocate_indirect(inode, block_len);
+	if (alloc == NULL) {
+		error("failed to allocate extents for %lu bytes", len);
+		return;
+	}
+
+	reserve_all_indirect_blocks(alloc, block_len);
+	rewind_alloc(alloc);
+
+	if (do_inode_attach_indirect(inode, alloc, block_len))
+		error("failed to attach blocks to indirect inode");
+
+	inode->i_flags = 0;
+	inode->i_blocks_lo = (block_len + indirect_len) * info.block_size / 512;
+	inode->i_size_lo = len;
+
+	free_alloc(alloc);
+}
+
+void inode_attach_resize(struct ext4_inode *inode,
+		struct block_allocation *alloc)
+{
+	u32 block_len = block_allocation_len(alloc);
+	u32 superblocks = block_len / aux_info.bg_desc_reserve_blocks;
+	u32 i, j;
+	u64 blocks;
+	u64 size;
+
+	if (block_len % aux_info.bg_desc_reserve_blocks)
+		critical_error("reserved blocks not a multiple of %d",
+				aux_info.bg_desc_reserve_blocks);
+
+	append_oob_allocation(alloc, 1);
+	u32 dind_block = get_oob_block(alloc, 0);
+
+	u32 *dind_block_data = calloc(info.block_size, 1);
+	if (!dind_block_data)
+		critical_error_errno("calloc");
+	queue_data_block((u8 *)dind_block_data, info.block_size, dind_block);
+
+	u32 *ind_block_data = calloc(info.block_size, aux_info.bg_desc_reserve_blocks);
+	if (!ind_block_data)
+		critical_error_errno("calloc");
+	queue_data_block((u8 *)ind_block_data,
+			info.block_size * aux_info.bg_desc_reserve_blocks,
+			get_block(alloc, 0));
+
+	for (i = 0; i < aux_info.bg_desc_reserve_blocks; i++) {
+		int r = (i - aux_info.bg_desc_blocks) % aux_info.bg_desc_reserve_blocks;
+		if (r < 0)
+			r += aux_info.bg_desc_reserve_blocks;
+
+		dind_block_data[i] = get_block(alloc, r);
+
+		for (j = 1; j < superblocks; j++) {
+			u32 b = j * aux_info.bg_desc_reserve_blocks + r;
+			ind_block_data[r * aux_info.blocks_per_ind + j - 1] = get_block(alloc, b);
+		}
+	}
+
+	u32 last_block = EXT4_NDIR_BLOCKS + aux_info.blocks_per_ind +
+			aux_info.blocks_per_ind * (aux_info.bg_desc_reserve_blocks - 1) +
+			superblocks - 2;
+
+	blocks = ((u64)block_len + 1) * info.block_size / 512;
+	size = (u64)last_block * info.block_size;
+
+	inode->i_block[EXT4_DIND_BLOCK] = dind_block;
+	inode->i_flags = 0;
+	inode->i_blocks_lo = blocks;
+	inode->osd2.linux2.l_i_blocks_high = blocks >> 32;
+	inode->i_size_lo = size;
+	inode->i_size_high = size >> 32;
+}
+
+/* Allocates enough blocks to hold len bytes, with backing_len bytes in a data
+   buffer, and connects them to an inode.  Returns a pointer to the data
+   buffer. */
+u8 *inode_allocate_data_indirect(struct ext4_inode *inode, unsigned long len,
+		unsigned long backing_len)
+{
+	struct block_allocation *alloc;
+	u8 *data = NULL;
+
+	alloc = do_inode_allocate_indirect(inode, len);
+	if (alloc == NULL) {
+		error("failed to allocate extents for %lu bytes", len);
+		return NULL;
+	}
+
+	if (backing_len) {
+		data = create_backing(alloc, backing_len);
+		if (!data)
+			error("failed to create backing for %lu bytes", backing_len);
+	}
+
+	free_alloc(alloc);
+
+	return data;
+}
diff --git a/ext4_utils/indirect.h b/ext4_utils/indirect.h
new file mode 100644
index 00000000..cee89790
--- /dev/null
+++ b/ext4_utils/indirect.h
@@ -0,0 +1,29 @@
+/*
+ * 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 _INDIRECT_H_
+#define _INDIRECT_H_
+
+#include "allocate.h"
+
+void inode_allocate_indirect(struct ext4_inode *inode, unsigned long len);
+u8 *inode_allocate_data_indirect(struct ext4_inode *inode, unsigned long len,
+	unsigned long backing_len);
+void inode_attach_resize(struct ext4_inode *inode,
+		struct block_allocation *alloc);
+void free_indirect_blocks();
+
+#endif
diff --git a/ext4_utils/jbd2.h b/ext4_utils/jbd2.h
new file mode 100644
index 00000000..1c816417
--- /dev/null
+++ b/ext4_utils/jbd2.h
@@ -0,0 +1,141 @@
+/****************************************************************************
+ ****************************************************************************
+ ***
+ ***   This header was automatically generated from a Linux kernel header
+ ***   of the same name, to make information necessary for userspace to
+ ***   call into the kernel available to libc.  It contains only constants,
+ ***   structures, and macros generated from the original header, and thus,
+ ***   contains no copyrightable information.
+ ***
+ ****************************************************************************
+ ****************************************************************************/
+#ifndef _LINUX_JBD2_H
+#define _LINUX_JBD2_H
+
+#define JBD2_DEBUG
+#define jfs_debug jbd_debug
+
+#define journal_oom_retry 1
+
+#undef JBD2_PARANOID_IOFAIL
+
+#define JBD2_DEFAULT_MAX_COMMIT_AGE 5
+
+#define jbd_debug(f, a...)  
+
+#define JBD2_MIN_JOURNAL_BLOCKS 1024
+
+#define JBD2_MAGIC_NUMBER 0xc03b3998U  
+
+#define JBD2_DESCRIPTOR_BLOCK 1
+#define JBD2_COMMIT_BLOCK 2
+#define JBD2_SUPERBLOCK_V1 3
+#define JBD2_SUPERBLOCK_V2 4
+#define JBD2_REVOKE_BLOCK 5
+
+typedef struct journal_header_s
+{
+ __be32 h_magic;
+ __be32 h_blocktype;
+ __be32 h_sequence;
+} journal_header_t;
+
+#define JBD2_CRC32_CHKSUM 1
+#define JBD2_MD5_CHKSUM 2
+#define JBD2_SHA1_CHKSUM 3
+
+#define JBD2_CRC32_CHKSUM_SIZE 4
+
+#define JBD2_CHECKSUM_BYTES (32 / sizeof(u32))
+
+struct commit_header {
+ __be32 h_magic;
+ __be32 h_blocktype;
+ __be32 h_sequence;
+ unsigned char h_chksum_type;
+ unsigned char h_chksum_size;
+ unsigned char h_padding[2];
+ __be32 h_chksum[JBD2_CHECKSUM_BYTES];
+ __be64 h_commit_sec;
+ __be32 h_commit_nsec;
+};
+
+typedef struct journal_block_tag_s
+{
+ __be32 t_blocknr;
+ __be32 t_flags;
+ __be32 t_blocknr_high;
+} journal_block_tag_t;
+
+#define JBD2_TAG_SIZE32 (offsetof(journal_block_tag_t, t_blocknr_high))
+#define JBD2_TAG_SIZE64 (sizeof(journal_block_tag_t))
+
+typedef struct jbd2_journal_revoke_header_s
+{
+ journal_header_t r_header;
+ __be32 r_count;
+} jbd2_journal_revoke_header_t;
+
+#define JBD2_FLAG_ESCAPE 1  
+#define JBD2_FLAG_SAME_UUID 2  
+#define JBD2_FLAG_DELETED 4  
+#define JBD2_FLAG_LAST_TAG 8  
+
+typedef struct journal_superblock_s
+{
+
+ journal_header_t s_header;
+
+ __be32 s_blocksize;
+ __be32 s_maxlen;
+ __be32 s_first;
+
+ __be32 s_sequence;
+ __be32 s_start;
+
+ __be32 s_errno;
+
+ __be32 s_feature_compat;
+ __be32 s_feature_incompat;
+ __be32 s_feature_ro_compat;
+
+ __u8 s_uuid[16];
+
+ __be32 s_nr_users;
+
+ __be32 s_dynsuper;
+
+ __be32 s_max_transaction;
+ __be32 s_max_trans_data;
+
+ __u32 s_padding[44];
+
+ __u8 s_users[16*48];
+
+} journal_superblock_t;
+
+#define JBD2_HAS_COMPAT_FEATURE(j,mask)   ((j)->j_format_version >= 2 &&   ((j)->j_superblock->s_feature_compat & cpu_to_be32((mask))))
+#define JBD2_HAS_RO_COMPAT_FEATURE(j,mask)   ((j)->j_format_version >= 2 &&   ((j)->j_superblock->s_feature_ro_compat & cpu_to_be32((mask))))
+#define JBD2_HAS_INCOMPAT_FEATURE(j,mask)   ((j)->j_format_version >= 2 &&   ((j)->j_superblock->s_feature_incompat & cpu_to_be32((mask))))
+
+#define JBD2_FEATURE_COMPAT_CHECKSUM 0x00000001
+
+#define JBD2_FEATURE_INCOMPAT_REVOKE 0x00000001
+#define JBD2_FEATURE_INCOMPAT_64BIT 0x00000002
+#define JBD2_FEATURE_INCOMPAT_ASYNC_COMMIT 0x00000004
+
+#define JBD2_KNOWN_COMPAT_FEATURES JBD2_FEATURE_COMPAT_CHECKSUM
+#define JBD2_KNOWN_ROCOMPAT_FEATURES 0
+#define JBD2_KNOWN_INCOMPAT_FEATURES (JBD2_FEATURE_INCOMPAT_REVOKE |   JBD2_FEATURE_INCOMPAT_64BIT |   JBD2_FEATURE_INCOMPAT_ASYNC_COMMIT)
+
+#define BJ_None 0  
+#define BJ_Metadata 1  
+#define BJ_Forget 2  
+#define BJ_IO 3  
+#define BJ_Shadow 4  
+#define BJ_LogCtl 5  
+#define BJ_Reserved 6  
+#define BJ_Types 7
+
+#endif
+
diff --git a/ext4_utils/make_ext4fs.c b/ext4_utils/make_ext4fs.c
new file mode 100644
index 00000000..87588ab6
--- /dev/null
+++ b/ext4_utils/make_ext4fs.c
@@ -0,0 +1,327 @@
+/*
+ * 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 _GNU_SOURCE
+
+#include <dirent.h>
+#include <libgen.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include "make_ext4fs.h"
+#include "output_file.h"
+#include "ext4_utils.h"
+#include "allocate.h"
+#include "contents.h"
+#include "uuid.h"
+
+#ifdef ANDROID
+#include <private/android_filesystem_config.h>
+#endif
+
+/* TODO: Not implemented:
+   Allocating blocks in the same block group as the file inode
+   Hash or binary tree directories
+   Special files: sockets, devices, fifos
+ */
+
+static int filter_dot(const struct dirent *d)
+{
+	return (strcmp(d->d_name, "..") && strcmp(d->d_name, "."));
+}
+
+static u32 build_default_directory_structure()
+{
+	u32 inode;
+	u32 root_inode;
+	struct dentry dentries = {
+			.filename = "lost+found",
+			.file_type = EXT4_FT_DIR,
+			.mode = S_IRWXU,
+			.uid = 0,
+			.gid = 0,
+			.mtime = 0,
+	};
+	root_inode = make_directory(0, 1, &dentries, 1);
+	inode = make_directory(root_inode, 0, NULL, 0);
+	*dentries.inode = inode;
+	inode_set_permissions(inode, dentries.mode,
+		dentries.uid, dentries.gid, dentries.mtime);
+
+	return root_inode;
+}
+
+/* Read a local directory and create the same tree in the generated filesystem.
+   Calls itself recursively with each directory in the given directory */
+static u32 build_directory_structure(const char *full_path, const char *dir_path,
+		u32 dir_inode, int android)
+{
+	int entries = 0;
+	struct dentry *dentries;
+	struct dirent **namelist;
+	struct stat stat;
+	int ret;
+	int i;
+	u32 inode;
+	u32 entry_inode;
+	u32 dirs = 0;
+
+	entries = scandir(full_path, &namelist, filter_dot, (void*)alphasort);
+	if (entries < 0) {
+		error_errno("scandir");
+		return EXT4_ALLOCATE_FAILED;
+	}
+
+	dentries = calloc(entries, sizeof(struct dentry));
+	if (dentries == NULL)
+		critical_error_errno("malloc");
+
+	for (i = 0; i < entries; i++) {
+		dentries[i].filename = strdup(namelist[i]->d_name);
+		if (dentries[i].filename == NULL)
+			critical_error_errno("strdup");
+
+		asprintf(&dentries[i].path, "%s/%s", dir_path, namelist[i]->d_name);
+		asprintf(&dentries[i].full_path, "%s/%s", full_path, namelist[i]->d_name);
+
+		free(namelist[i]);
+
+		ret = lstat(dentries[i].full_path, &stat);
+		if (ret < 0) {
+			error_errno("lstat");
+			i--;
+			entries--;
+			continue;
+		}
+
+		dentries[i].size = stat.st_size;
+		dentries[i].mode = stat.st_mode & (S_ISUID|S_ISGID|S_ISVTX|S_IRWXU|S_IRWXG|S_IRWXO);
+		dentries[i].mtime = stat.st_mtime;
+		if (android) {
+#ifdef ANDROID
+			unsigned int mode = 0;
+			unsigned int uid = 0;
+			unsigned int gid = 0;
+			int dir = S_ISDIR(stat.st_mode);
+			fs_config(dentries[i].path, dir, &uid, &gid, &mode);
+			dentries[i].mode = mode;
+			dentries[i].uid = uid;
+			dentries[i].gid = gid;
+#else
+			error("can't set android permissions - built without android support");
+#endif
+		}
+
+		if (S_ISREG(stat.st_mode)) {
+			dentries[i].file_type = EXT4_FT_REG_FILE;
+		} else if (S_ISDIR(stat.st_mode)) {
+			dentries[i].file_type = EXT4_FT_DIR;
+			dirs++;
+		} else if (S_ISCHR(stat.st_mode)) {
+			dentries[i].file_type = EXT4_FT_CHRDEV;
+		} else if (S_ISBLK(stat.st_mode)) {
+			dentries[i].file_type = EXT4_FT_BLKDEV;
+		} else if (S_ISFIFO(stat.st_mode)) {
+			dentries[i].file_type = EXT4_FT_FIFO;
+		} else if (S_ISSOCK(stat.st_mode)) {
+			dentries[i].file_type = EXT4_FT_SOCK;
+		} else if (S_ISLNK(stat.st_mode)) {
+			dentries[i].file_type = EXT4_FT_SYMLINK;
+			dentries[i].link = calloc(info.block_size, 1);
+			readlink(dentries[i].full_path, dentries[i].link, info.block_size - 1);
+		} else {
+			error("unknown file type on %s", dentries[i].path);
+			i--;
+			entries--;
+		}
+	}
+	free(namelist);
+
+	inode = make_directory(dir_inode, entries, dentries, dirs);
+
+	for (i = 0; i < entries; i++) {
+		if (dentries[i].file_type == EXT4_FT_REG_FILE) {
+			entry_inode = make_file(dentries[i].full_path, dentries[i].size);
+		} else if (dentries[i].file_type == EXT4_FT_DIR) {
+			entry_inode = build_directory_structure(dentries[i].full_path,
+					dentries[i].path, inode, android);
+		} else if (dentries[i].file_type == EXT4_FT_SYMLINK) {
+			entry_inode = make_link(dentries[i].full_path, dentries[i].link);
+		} else {
+			error("unknown file type on %s", dentries[i].path);
+			entry_inode = 0;
+		}
+		*dentries[i].inode = entry_inode;
+
+		ret = inode_set_permissions(entry_inode, dentries[i].mode,
+			dentries[i].uid, dentries[i].gid,
+			dentries[i].mtime);
+		if (ret)
+			error("failed to set permissions on %s\n", dentries[i].path);
+
+		free(dentries[i].path);
+		free(dentries[i].full_path);
+		free(dentries[i].link);
+		free((void *)dentries[i].filename);
+	}
+
+	free(dentries);
+	return inode;
+}
+
+static u32 compute_block_size()
+{
+	return 4096;
+}
+
+static u32 compute_journal_blocks()
+{
+	u32 journal_blocks = DIV_ROUND_UP(info.len, info.block_size) / 64;
+	if (journal_blocks < 1024)
+		journal_blocks = 1024;
+	if (journal_blocks > 32768)
+		journal_blocks = 32768;
+	return journal_blocks;
+}
+
+static u32 compute_blocks_per_group()
+{
+	return info.block_size * 8;
+}
+
+static u32 compute_inodes()
+{
+	return DIV_ROUND_UP(info.len, info.block_size) / 4;
+}
+
+static u32 compute_inodes_per_group()
+{
+	u32 blocks = DIV_ROUND_UP(info.len, info.block_size);
+	u32 block_groups = DIV_ROUND_UP(blocks, info.blocks_per_group);
+	return DIV_ROUND_UP(info.inodes, block_groups);
+}
+
+void reset_ext4fs_info() {
+    // Reset all the global data structures used by make_ext4fs so it
+    // can be called again.
+    memset(&info, 0, sizeof(info));
+    memset(&aux_info, 0, sizeof(aux_info));
+    free_data_blocks();
+}
+
+int make_ext4fs(const char *filename, const char *directory,
+                char *mountpoint, int android, int gzip, int sparse)
+{
+        u32 root_inode_num;
+        u16 root_mode;
+
+	if (info.len == 0)
+		info.len = get_file_size(filename);
+
+	if (info.len <= 0) {
+		fprintf(stderr, "Need size of filesystem\n");
+                return EXIT_FAILURE;
+	}
+
+	if (info.block_size <= 0)
+		info.block_size = compute_block_size();
+
+	if (info.journal_blocks == 0)
+		info.journal_blocks = compute_journal_blocks();
+
+	if (info.no_journal == 0)
+		info.feat_compat = EXT4_FEATURE_COMPAT_HAS_JOURNAL;
+	else
+		info.journal_blocks = 0;
+
+	if (info.blocks_per_group <= 0)
+		info.blocks_per_group = compute_blocks_per_group();
+
+	if (info.inodes <= 0)
+		info.inodes = compute_inodes();
+
+	if (info.inode_size <= 0)
+		info.inode_size = 256;
+
+	if (info.label == NULL)
+		info.label = "";
+
+	info.inodes_per_group = compute_inodes_per_group();
+
+	info.feat_compat |=
+			EXT4_FEATURE_COMPAT_RESIZE_INODE;
+
+	info.feat_ro_compat |=
+			EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER |
+			EXT4_FEATURE_RO_COMPAT_LARGE_FILE;
+
+	info.feat_incompat |=
+			EXT4_FEATURE_INCOMPAT_EXTENTS |
+			EXT4_FEATURE_INCOMPAT_FILETYPE;
+
+
+	printf("Creating filesystem with parameters:\n");
+	printf("    Size: %llu\n", info.len);
+	printf("    Block size: %d\n", info.block_size);
+	printf("    Blocks per group: %d\n", info.blocks_per_group);
+	printf("    Inodes per group: %d\n", info.inodes_per_group);
+	printf("    Inode size: %d\n", info.inode_size);
+	printf("    Journal blocks: %d\n", info.journal_blocks);
+	printf("    Label: %s\n", info.label);
+
+	ext4_create_fs_aux_info();
+
+	printf("    Blocks: %llu\n", aux_info.len_blocks);
+	printf("    Block groups: %d\n", aux_info.groups);
+	printf("    Reserved block group size: %d\n", aux_info.bg_desc_reserve_blocks);
+
+	block_allocator_init();
+
+	ext4_fill_in_sb();
+
+	if (reserve_inodes(0, 10) == EXT4_ALLOCATE_FAILED)
+		error("failed to reserve first 10 inodes");
+
+	if (info.feat_compat & EXT4_FEATURE_COMPAT_HAS_JOURNAL)
+		ext4_create_journal_inode();
+
+	if (info.feat_compat & EXT4_FEATURE_COMPAT_RESIZE_INODE)
+		ext4_create_resize_inode();
+
+	if (directory)
+		root_inode_num = build_directory_structure(directory, mountpoint, 0, android);
+	else
+		root_inode_num = build_default_directory_structure();
+
+	root_mode = S_IRWXU | S_IRGRP | S_IXGRP | S_IROTH | S_IXOTH;
+	inode_set_permissions(root_inode_num, root_mode, 0, 0, 0);
+
+	ext4_update_free();
+
+	printf("Created filesystem with %d/%d inodes and %d/%d blocks\n",
+			aux_info.sb->s_inodes_count - aux_info.sb->s_free_inodes_count,
+			aux_info.sb->s_inodes_count,
+			aux_info.sb->s_blocks_count_lo - aux_info.sb->s_free_blocks_count_lo,
+			aux_info.sb->s_blocks_count_lo);
+
+	write_ext4_image(filename, gzip, sparse);
+
+	return 0;
+}
diff --git a/ext4_utils/make_ext4fs.h b/ext4_utils/make_ext4fs.h
new file mode 100644
index 00000000..8c6b2592
--- /dev/null
+++ b/ext4_utils/make_ext4fs.h
@@ -0,0 +1,27 @@
+/*
+ * 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 _MAKE_EXT4FS_H_
+#define _MAKE_EXT4FS_H_
+
+#include "ext4_utils.h"
+#include "ext4.h"
+
+void reset_ext4fs_info();
+int make_ext4fs(const char *filename, const char *directory,
+                char *mountpoint, int android, int gzip, int sparse);
+
+#endif
diff --git a/ext4_utils/make_ext4fs_main.c b/ext4_utils/make_ext4fs_main.c
new file mode 100644
index 00000000..66d7aac6
--- /dev/null
+++ b/ext4_utils/make_ext4fs_main.c
@@ -0,0 +1,119 @@
+/*
+ * 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 <unistd.h>
+#include <libgen.h>
+
+#if defined(__linux__)
+#include <linux/fs.h>
+#elif defined(__APPLE__) && defined(__MACH__)
+#include <sys/disk.h>
+#endif
+
+#include "make_ext4fs.h"
+
+extern struct fs_info info;
+
+
+static void usage(char *path)
+{
+        fprintf(stderr, "%s [ -l <len> ] [ -j <journal size> ] [ -b <block_size> ]\n", basename(path));
+        fprintf(stderr, "    [ -g <blocks per group> ] [ -i <inodes> ] [ -I <inode size> ]\n");
+        fprintf(stderr, "    [ -L <label> ] [ -f ] [ -a <android mountpoint> ]\n");
+        fprintf(stderr, "    [ -z | -s ] [ -J ]\n");
+        fprintf(stderr, "    <filename> [<directory>]\n");
+}
+
+int main(int argc, char **argv)
+{
+        int opt;
+        const char *filename = NULL;
+        const char *directory = NULL;
+        char *mountpoint = "";
+        int android = 0;
+        int gzip = 0;
+        int sparse = 0;
+
+        while ((opt = getopt(argc, argv, "l:j:b:g:i:I:L:a:fzJs")) != -1) {
+                switch (opt) {
+                case 'l':
+                        info.len = parse_num(optarg);
+                        break;
+                case 'j':
+                        info.journal_blocks = parse_num(optarg);
+                        break;
+                case 'b':
+                        info.block_size = parse_num(optarg);
+                        break;
+                case 'g':
+                        info.blocks_per_group = parse_num(optarg);
+                        break;
+                case 'i':
+                        info.inodes = parse_num(optarg);
+                        break;
+                case 'I':
+                        info.inode_size = parse_num(optarg);
+                        break;
+                case 'L':
+                        info.label = optarg;
+                        break;
+                case 'f':
+                        force = 1;
+                        break;
+                case 'a':
+                        android = 1;
+                        mountpoint = optarg;
+                        break;
+                case 'z':
+                        gzip = 1;
+                        break;
+		case 'J':
+			info.no_journal = 1;
+			break;
+                case 's':
+                        sparse = 1;
+                        break;
+                default: /* '?' */
+                        usage(argv[0]);
+                        exit(EXIT_FAILURE);
+                }
+        }
+
+	if (gzip && sparse) {
+                fprintf(stderr, "Cannot specify both gzip and sparse\n");
+                usage(argv[0]);
+                exit(EXIT_FAILURE);
+	}
+
+        if (optind >= argc) {
+                fprintf(stderr, "Expected filename after options\n");
+                usage(argv[0]);
+                exit(EXIT_FAILURE);
+        }
+
+        filename = argv[optind++];
+
+        if (optind < argc)
+                directory = argv[optind++];
+
+        if (optind < argc) {
+                fprintf(stderr, "Unexpected argument: %s\n", argv[optind]);
+                usage(argv[0]);
+                exit(EXIT_FAILURE);
+        }
+
+        return make_ext4fs(filename, directory, mountpoint, android, gzip, sparse);
+}
diff --git a/ext4_utils/mkuserimg.sh b/ext4_utils/mkuserimg.sh
new file mode 100755
index 00000000..ced64125
--- /dev/null
+++ b/ext4_utils/mkuserimg.sh
@@ -0,0 +1,48 @@
+#!/bin/bash
+#
+# To call this script, make sure make_ext4fs is somewhere in PATH
+
+function usage() {
+cat<<EOT
+Usage:
+mkuserimg.sh SRC_DIR OUTPUT_FILE EXT_VARIANT LABEL SIZE
+EOT
+}
+
+echo "in mkuserimg.sh PATH=$PATH"
+
+if [ $# -ne 4 -a $# -ne 5 ]; then
+  usage
+  exit 1
+fi
+
+SRC_DIR=$1
+if [ ! -d $SRC_DIR ]; then
+  echo "Can not find directory $SRC_DIR!"
+  exit 2
+fi
+
+OUTPUT_FILE=$2
+EXT_VARIANT=$3
+LABEL=$4
+SIZE=$5
+
+case $EXT_VARIANT in
+  ext4) ;;
+  *) echo "Only ext4 is supported!"; exit 3 ;;
+esac
+
+if [ -z $LABEL ]; then
+  echo "Label is required"
+  exit 2
+fi
+
+if [ -z $SIZE ]; then
+    SIZE=128M
+fi
+
+echo "make_ext4fs -l $SIZE -a $LABEL $OUTPUT_FILE $SRC_DIR"
+make_ext4fs -l $SIZE -a $LABEL $OUTPUT_FILE $SRC_DIR
+if [ $? -ne 0 ]; then
+  exit 4
+fi
diff --git a/ext4_utils/output_file.c b/ext4_utils/output_file.c
new file mode 100644
index 00000000..2705701c
--- /dev/null
+++ b/ext4_utils/output_file.c
@@ -0,0 +1,417 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#define _LARGEFILE64_SOURCE
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <sys/mman.h>
+#include <unistd.h>
+#include <fcntl.h>
+
+#include <zlib.h>
+
+#include "ext4_utils.h"
+#include "output_file.h"
+#include "sparse_format.h"
+
+#if defined(__APPLE__) && defined(__MACH__)
+#define lseek64 lseek
+#define off64_t off_t
+#endif
+
+#define 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 *, off64_t);
+	int (*write)(struct output_file *, u8 *, int);
+	void (*close)(struct output_file *);
+};
+
+struct output_file {
+	int fd;
+	gzFile gz_fd;
+	int sparse;
+	u64 cur_out_ptr;
+	int chunk_cnt;
+	u32 crc32;
+	struct output_file_ops *ops;
+};
+
+static int file_seek(struct output_file *out, off64_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)
+{
+	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, off64_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;
+
+	//DBG printf("skip chunk: 0x%llx bytes\n", skip_len);
+
+	if (skip_len % info.block_size) {
+		error("don't care size %llu is not a multiple of the block size %u",
+				skip_len, info.block_size);
+		return -1;
+	}
+
+	/* We are skipping data, so emit a don't care chunk. */
+	chunk_header.chunk_type = CHUNK_TYPE_DONT_CARE;
+	chunk_header.reserved1 = 0;
+	chunk_header.chunk_sz = skip_len / info.block_size;
+	chunk_header.total_sz = CHUNK_HEADER_LEN;
+	ret = out->ops->write(out, (u8 *)&chunk_header, sizeof(chunk_header));
+	if (ret < 0)
+		return -1;
+	// KEN: TODO: CRC computation
+	out->cur_out_ptr += skip_len;
+	out->chunk_cnt++;
+
+	return 0;
+}
+
+static int write_chunk_raw(struct output_file *out, u64 off, u8 *data, int len)
+{
+	chunk_header_t chunk_header;
+	int rnd_up_len, zero_len;
+	int ret;
+
+	/* We can assume that all the chunks to be written are in
+	 * ascending order, block-size aligned, and non-overlapping.
+	 * So, if the offset is less than the current output pointer,
+	 * throw an error, and if there is a gap, emit a "don't care"
+	 * chunk.  The first write (of the super block) may not be
+	 * blocksize aligned, so we need to deal with that too.
+	 */
+	//DBG printf("write chunk: offset 0x%llx, length 0x%x bytes\n", off, len);
+
+	if (off < out->cur_out_ptr) {
+		error("offset %llu is less than the current output offset %llu",
+				off, out->cur_out_ptr);
+		return -1;
+	}
+
+	if (off > out->cur_out_ptr) {
+		emit_skip_chunk(out, off - out->cur_out_ptr);
+	}
+
+	if (off % info.block_size) {
+		error("write chunk offset %llu is not a multiple of the block size %u",
+				off, info.block_size);
+		return -1;
+	}
+
+	if (off != out->cur_out_ptr) {
+		error("internal error, offset accounting screwy in write_chunk_raw()");
+		return -1;
+	}
+
+	/* Round up the file length to a multiple of the block size */
+	rnd_up_len = (len + (info.block_size - 1)) & (~(info.block_size -1));
+	zero_len = rnd_up_len - len;
+
+	/* Finally we can safely emit a chunk of data */
+	chunk_header.chunk_type = CHUNK_TYPE_RAW;
+	chunk_header.reserved1 = 0;
+	chunk_header.chunk_sz = rnd_up_len / info.block_size;
+	chunk_header.total_sz = CHUNK_HEADER_LEN + rnd_up_len;
+	ret = out->ops->write(out, (u8 *)&chunk_header, sizeof(chunk_header));
+
+	if (ret < 0)
+		return -1;
+	ret = out->ops->write(out, data, len);
+	if (ret < 0)
+		return -1;
+	if (zero_len) {
+		ret = out->ops->write(out, zero_buf, zero_len);
+		if (ret < 0)
+			return -1;
+	}
+
+	// KEN: TODO: CRC computation of both the raw data and and zero buf data written */
+	out->cur_out_ptr += rnd_up_len;
+	out->chunk_cnt++;
+
+	return 0;
+}
+
+void close_output_file(struct output_file *out)
+{
+	int ret;
+
+	if (out->sparse) {
+		/* we need to seek back to the beginning and update the file header */
+		sparse_header.total_chunks = out->chunk_cnt;
+		sparse_header.image_checksum = out->crc32;
+
+		ret = out->ops->seek(out, 0);
+		if (ret < 0)
+			error("failure seeking to start of sparse file");
+
+		ret = out->ops->write(out, (u8 *)&sparse_header, sizeof(sparse_header));
+		if (ret < 0)
+			error("failure updating sparse file header");
+	}
+	out->ops->close(out);
+}
+
+struct output_file *open_output_file(const char *filename, int gz, int sparse)
+{
+	int ret;
+	struct output_file *out = malloc(sizeof(struct output_file));
+	if (!out) {
+		error_errno("malloc struct out");
+		return NULL;
+	}
+	zero_buf = malloc(info.block_size);
+	if (!zero_buf) {
+		error_errno("malloc zero_buf");
+		return NULL;
+	}
+	memset(zero_buf, '\0', info.block_size);
+
+	if (gz) {
+		out->ops = &gz_file_ops;
+		out->gz_fd = gzopen(filename, "wb9");
+		if (!out->gz_fd) {
+			error_errno("gzopen");
+			free(out);
+			return NULL;
+		}
+	} else {
+		out->ops = &file_ops;
+		out->fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC, 0644);
+		if (out->fd < 0) {
+			error_errno("open");
+			free(out);
+			return NULL;
+		}
+	}
+	out->sparse = sparse;
+	out->cur_out_ptr = 0ll;
+	out->chunk_cnt = 0;
+	if (out->sparse) {
+		/* Write out the file header.  We'll update the unknown fields
+		 * when we close the file.
+		 */
+		sparse_header.blk_sz = info.block_size,
+		sparse_header.total_blks = info.len / info.block_size,
+		ret = out->ops->write(out, (u8 *)&sparse_header, sizeof(sparse_header));
+		if (ret < 0)
+			return NULL;
+	}
+
+	return out;
+}
+
+void pad_output_file(struct output_file *out, u64 len)
+{
+	int ret;
+
+	if (len > info.len) {
+		error("attempted to pad file %llu bytes past end of filesystem",
+				len - info.len);
+		return;
+	}
+	if (out->sparse) {
+		/* We need to emit a DONT_CARE chunk to pad out the file if the
+		 * cur_out_ptr is not already at the end of the filesystem.
+		 * We also need to compute the CRC for it.
+		 */
+		 //KEN: TODO: CRC computation!
+		if (len < out->cur_out_ptr) {
+			error("attempted to pad file %llu bytes less than the current output pointer",
+					out->cur_out_ptr - len);
+			return;
+		}
+		if (len > out->cur_out_ptr) {
+			emit_skip_chunk(out, len - out->cur_out_ptr);
+		}
+	} else {
+		//KEN TODO: Fixme.  If the filesystem image needs no padding,
+		//          this will overwrite the last byte in the file with 0
+		//          The answer is to do accounting like the sparse image
+		//          code does and know if there is already data there.
+		ret = out->ops->seek(out, len - 1);
+		if (ret < 0)
+			return;
+
+		ret = out->ops->write(out, (u8*)"", 1);
+		if (ret < 0)
+			return;
+	}
+}
+
+/* Write a contiguous region of data blocks from a memory buffer */
+void write_data_block(struct output_file *out, u64 off, u8 *data, int len)
+{
+	int ret;
+	
+	if (off + len > info.len) {
+		error("attempted to write block %llu past end of filesystem",
+				off + len - info.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 from a file */
+void write_data_file(struct output_file *out, u64 off, const char *file,
+		     off_t offset, int len)
+{
+	int ret;
+
+	if (off + len >= info.len) {
+		error("attempted to write block %llu past end of filesystem",
+				off + len - info.len);
+		return;
+	}
+
+	int file_fd = open(file, O_RDONLY);
+	if (file_fd < 0) {
+		error_errno("open");
+		return;
+	}
+
+	u8 *data = mmap(NULL, len, PROT_READ, MAP_SHARED, file_fd, offset);
+	if (data == MAP_FAILED) {
+		error_errno("mmap");
+		close(file_fd);
+		return;
+	}
+
+	if (out->sparse) {
+		write_chunk_raw(out, off, data, len);
+	} else {
+		ret = out->ops->seek(out, off);
+		if (ret < 0)
+			goto err;
+
+		ret = out->ops->write(out, data, len);
+		if (ret < 0)
+			goto err;
+	}
+
+	munmap(data, len);
+
+	close(file_fd);
+
+err:
+	munmap(data, len);
+	close(file_fd);
+}
+
diff --git a/ext4_utils/output_file.h b/ext4_utils/output_file.h
new file mode 100644
index 00000000..82b09521
--- /dev/null
+++ b/ext4_utils/output_file.h
@@ -0,0 +1,24 @@
+/*
+ * 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.
+ */
+
+struct output_file;
+
+struct output_file *open_output_file(const char *filename, int gz, int sparse);
+void write_data_block(struct output_file *out, u64 off, u8 *data, int len);
+void write_data_file(struct output_file *out, u64 off, const char *file,
+		     off_t offset, int len);
+void pad_output_file(struct output_file *out, u64 len);
+void close_output_file(struct output_file *out);
diff --git a/ext4_utils/sha1.c b/ext4_utils/sha1.c
new file mode 100644
index 00000000..1db9134a
--- /dev/null
+++ b/ext4_utils/sha1.c
@@ -0,0 +1,271 @@
+/*	$NetBSD: sha1.c,v 1.1 2005/12/20 20:29:40 christos Exp $	*/
+/*	$OpenBSD: sha1.c,v 1.9 1997/07/23 21:12:32 kstailey Exp $	*/
+
+/*
+ * SHA-1 in C
+ * By Steve Reid <steve@edmweb.com>
+ * 100% Public Domain
+ *
+ * Test Vectors (from FIPS PUB 180-1)
+ * "abc"
+ *   A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D
+ * "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
+ *   84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1
+ * A million repetitions of "a"
+ *   34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F
+ */
+
+#define SHA1HANDSOFF		/* Copies data before messing with it. */
+
+#include <sys/cdefs.h>
+#include <sys/types.h>
+#include <assert.h>
+#include <string.h>
+
+#include "sha1.h"
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#if !HAVE_SHA1_H
+
+#define rol(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))
+
+/*
+ * blk0() and blk() perform the initial expand.
+ * I got the idea of expanding during the round function from SSLeay
+ */
+#if BYTE_ORDER == LITTLE_ENDIAN
+# define blk0(i) (block->l[i] = (rol(block->l[i],24)&0xFF00FF00) \
+    |(rol(block->l[i],8)&0x00FF00FF))
+#else
+# define blk0(i) block->l[i]
+#endif
+#define blk(i) (block->l[i&15] = rol(block->l[(i+13)&15]^block->l[(i+8)&15] \
+    ^block->l[(i+2)&15]^block->l[i&15],1))
+
+/*
+ * (R0+R1), R2, R3, R4 are the different operations (rounds) used in SHA1
+ */
+#define R0(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk0(i)+0x5A827999+rol(v,5);w=rol(w,30);
+#define R1(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk(i)+0x5A827999+rol(v,5);w=rol(w,30);
+#define R2(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0x6ED9EBA1+rol(v,5);w=rol(w,30);
+#define R3(v,w,x,y,z,i) z+=(((w|x)&y)|(w&x))+blk(i)+0x8F1BBCDC+rol(v,5);w=rol(w,30);
+#define R4(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0xCA62C1D6+rol(v,5);w=rol(w,30);
+
+typedef union {
+    u_char c[64];
+    u_int l[16];
+} CHAR64LONG16;
+
+/* old sparc64 gcc could not compile this */
+#undef SPARC64_GCC_WORKAROUND
+#if defined(__sparc64__) && defined(__GNUC__) && __GNUC__ < 3
+#define SPARC64_GCC_WORKAROUND
+#endif
+
+#ifdef SPARC64_GCC_WORKAROUND
+void do_R01(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *);
+void do_R2(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *);
+void do_R3(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *);
+void do_R4(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *);
+
+#define nR0(v,w,x,y,z,i) R0(*v,*w,*x,*y,*z,i)
+#define nR1(v,w,x,y,z,i) R1(*v,*w,*x,*y,*z,i)
+#define nR2(v,w,x,y,z,i) R2(*v,*w,*x,*y,*z,i)
+#define nR3(v,w,x,y,z,i) R3(*v,*w,*x,*y,*z,i)
+#define nR4(v,w,x,y,z,i) R4(*v,*w,*x,*y,*z,i)
+
+void
+do_R01(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *block)
+{
+    nR0(a,b,c,d,e, 0); nR0(e,a,b,c,d, 1); nR0(d,e,a,b,c, 2); nR0(c,d,e,a,b, 3);
+    nR0(b,c,d,e,a, 4); nR0(a,b,c,d,e, 5); nR0(e,a,b,c,d, 6); nR0(d,e,a,b,c, 7);
+    nR0(c,d,e,a,b, 8); nR0(b,c,d,e,a, 9); nR0(a,b,c,d,e,10); nR0(e,a,b,c,d,11);
+    nR0(d,e,a,b,c,12); nR0(c,d,e,a,b,13); nR0(b,c,d,e,a,14); nR0(a,b,c,d,e,15);
+    nR1(e,a,b,c,d,16); nR1(d,e,a,b,c,17); nR1(c,d,e,a,b,18); nR1(b,c,d,e,a,19);
+}
+
+void
+do_R2(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *block)
+{
+    nR2(a,b,c,d,e,20); nR2(e,a,b,c,d,21); nR2(d,e,a,b,c,22); nR2(c,d,e,a,b,23);
+    nR2(b,c,d,e,a,24); nR2(a,b,c,d,e,25); nR2(e,a,b,c,d,26); nR2(d,e,a,b,c,27);
+    nR2(c,d,e,a,b,28); nR2(b,c,d,e,a,29); nR2(a,b,c,d,e,30); nR2(e,a,b,c,d,31);
+    nR2(d,e,a,b,c,32); nR2(c,d,e,a,b,33); nR2(b,c,d,e,a,34); nR2(a,b,c,d,e,35);
+    nR2(e,a,b,c,d,36); nR2(d,e,a,b,c,37); nR2(c,d,e,a,b,38); nR2(b,c,d,e,a,39);
+}
+
+void
+do_R3(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *block)
+{
+    nR3(a,b,c,d,e,40); nR3(e,a,b,c,d,41); nR3(d,e,a,b,c,42); nR3(c,d,e,a,b,43);
+    nR3(b,c,d,e,a,44); nR3(a,b,c,d,e,45); nR3(e,a,b,c,d,46); nR3(d,e,a,b,c,47);
+    nR3(c,d,e,a,b,48); nR3(b,c,d,e,a,49); nR3(a,b,c,d,e,50); nR3(e,a,b,c,d,51);
+    nR3(d,e,a,b,c,52); nR3(c,d,e,a,b,53); nR3(b,c,d,e,a,54); nR3(a,b,c,d,e,55);
+    nR3(e,a,b,c,d,56); nR3(d,e,a,b,c,57); nR3(c,d,e,a,b,58); nR3(b,c,d,e,a,59);
+}
+
+void
+do_R4(u_int32_t *a, u_int32_t *b, u_int32_t *c, u_int32_t *d, u_int32_t *e, CHAR64LONG16 *block)
+{
+    nR4(a,b,c,d,e,60); nR4(e,a,b,c,d,61); nR4(d,e,a,b,c,62); nR4(c,d,e,a,b,63);
+    nR4(b,c,d,e,a,64); nR4(a,b,c,d,e,65); nR4(e,a,b,c,d,66); nR4(d,e,a,b,c,67);
+    nR4(c,d,e,a,b,68); nR4(b,c,d,e,a,69); nR4(a,b,c,d,e,70); nR4(e,a,b,c,d,71);
+    nR4(d,e,a,b,c,72); nR4(c,d,e,a,b,73); nR4(b,c,d,e,a,74); nR4(a,b,c,d,e,75);
+    nR4(e,a,b,c,d,76); nR4(d,e,a,b,c,77); nR4(c,d,e,a,b,78); nR4(b,c,d,e,a,79);
+}
+#endif
+
+/*
+ * Hash a single 512-bit block. This is the core of the algorithm.
+ */
+void SHA1Transform(state, buffer)
+    u_int32_t state[5];
+    const u_char buffer[64];
+{
+    u_int32_t a, b, c, d, e;
+    CHAR64LONG16 *block;
+
+#ifdef SHA1HANDSOFF
+    CHAR64LONG16 workspace;
+#endif
+
+    assert(buffer != 0);
+    assert(state != 0);
+
+#ifdef SHA1HANDSOFF
+    block = &workspace;
+    (void)memcpy(block, buffer, 64);
+#else
+    block = (CHAR64LONG16 *)(void *)buffer;
+#endif
+
+    /* Copy context->state[] to working vars */
+    a = state[0];
+    b = state[1];
+    c = state[2];
+    d = state[3];
+    e = state[4];
+
+#ifdef SPARC64_GCC_WORKAROUND
+    do_R01(&a, &b, &c, &d, &e, block);
+    do_R2(&a, &b, &c, &d, &e, block);
+    do_R3(&a, &b, &c, &d, &e, block);
+    do_R4(&a, &b, &c, &d, &e, block);
+#else
+    /* 4 rounds of 20 operations each. Loop unrolled. */
+    R0(a,b,c,d,e, 0); R0(e,a,b,c,d, 1); R0(d,e,a,b,c, 2); R0(c,d,e,a,b, 3);
+    R0(b,c,d,e,a, 4); R0(a,b,c,d,e, 5); R0(e,a,b,c,d, 6); R0(d,e,a,b,c, 7);
+    R0(c,d,e,a,b, 8); R0(b,c,d,e,a, 9); R0(a,b,c,d,e,10); R0(e,a,b,c,d,11);
+    R0(d,e,a,b,c,12); R0(c,d,e,a,b,13); R0(b,c,d,e,a,14); R0(a,b,c,d,e,15);
+    R1(e,a,b,c,d,16); R1(d,e,a,b,c,17); R1(c,d,e,a,b,18); R1(b,c,d,e,a,19);
+    R2(a,b,c,d,e,20); R2(e,a,b,c,d,21); R2(d,e,a,b,c,22); R2(c,d,e,a,b,23);
+    R2(b,c,d,e,a,24); R2(a,b,c,d,e,25); R2(e,a,b,c,d,26); R2(d,e,a,b,c,27);
+    R2(c,d,e,a,b,28); R2(b,c,d,e,a,29); R2(a,b,c,d,e,30); R2(e,a,b,c,d,31);
+    R2(d,e,a,b,c,32); R2(c,d,e,a,b,33); R2(b,c,d,e,a,34); R2(a,b,c,d,e,35);
+    R2(e,a,b,c,d,36); R2(d,e,a,b,c,37); R2(c,d,e,a,b,38); R2(b,c,d,e,a,39);
+    R3(a,b,c,d,e,40); R3(e,a,b,c,d,41); R3(d,e,a,b,c,42); R3(c,d,e,a,b,43);
+    R3(b,c,d,e,a,44); R3(a,b,c,d,e,45); R3(e,a,b,c,d,46); R3(d,e,a,b,c,47);
+    R3(c,d,e,a,b,48); R3(b,c,d,e,a,49); R3(a,b,c,d,e,50); R3(e,a,b,c,d,51);
+    R3(d,e,a,b,c,52); R3(c,d,e,a,b,53); R3(b,c,d,e,a,54); R3(a,b,c,d,e,55);
+    R3(e,a,b,c,d,56); R3(d,e,a,b,c,57); R3(c,d,e,a,b,58); R3(b,c,d,e,a,59);
+    R4(a,b,c,d,e,60); R4(e,a,b,c,d,61); R4(d,e,a,b,c,62); R4(c,d,e,a,b,63);
+    R4(b,c,d,e,a,64); R4(a,b,c,d,e,65); R4(e,a,b,c,d,66); R4(d,e,a,b,c,67);
+    R4(c,d,e,a,b,68); R4(b,c,d,e,a,69); R4(a,b,c,d,e,70); R4(e,a,b,c,d,71);
+    R4(d,e,a,b,c,72); R4(c,d,e,a,b,73); R4(b,c,d,e,a,74); R4(a,b,c,d,e,75);
+    R4(e,a,b,c,d,76); R4(d,e,a,b,c,77); R4(c,d,e,a,b,78); R4(b,c,d,e,a,79);
+#endif
+
+    /* Add the working vars back into context.state[] */
+    state[0] += a;
+    state[1] += b;
+    state[2] += c;
+    state[3] += d;
+    state[4] += e;
+
+    /* Wipe variables */
+    a = b = c = d = e = 0;
+}
+
+
+/*
+ * SHA1Init - Initialize new context
+ */
+void SHA1Init(context)
+    SHA1_CTX *context;
+{
+
+    assert(context != 0);
+
+    /* SHA1 initialization constants */
+    context->state[0] = 0x67452301;
+    context->state[1] = 0xEFCDAB89;
+    context->state[2] = 0x98BADCFE;
+    context->state[3] = 0x10325476;
+    context->state[4] = 0xC3D2E1F0;
+    context->count[0] = context->count[1] = 0;
+}
+
+
+/*
+ * Run your data through this.
+ */
+void SHA1Update(context, data, len)
+    SHA1_CTX *context;
+    const u_char *data;
+    u_int len;
+{
+    u_int i, j;
+
+    assert(context != 0);
+    assert(data != 0);
+
+    j = context->count[0];
+    if ((context->count[0] += len << 3) < j)
+	context->count[1] += (len>>29)+1;
+    j = (j >> 3) & 63;
+    if ((j + len) > 63) {
+	(void)memcpy(&context->buffer[j], data, (i = 64-j));
+	SHA1Transform(context->state, context->buffer);
+	for ( ; i + 63 < len; i += 64)
+	    SHA1Transform(context->state, &data[i]);
+	j = 0;
+    } else {
+	i = 0;
+    }
+    (void)memcpy(&context->buffer[j], &data[i], len - i);
+}
+
+
+/*
+ * Add padding and return the message digest.
+ */
+void SHA1Final(digest, context)
+    u_char digest[20];
+    SHA1_CTX* context;
+{
+    u_int i;
+    u_char finalcount[8];
+
+    assert(digest != 0);
+    assert(context != 0);
+
+    for (i = 0; i < 8; i++) {
+	finalcount[i] = (u_char)((context->count[(i >= 4 ? 0 : 1)]
+	 >> ((3-(i & 3)) * 8) ) & 255);	 /* Endian independent */
+    }
+    SHA1Update(context, (const u_char *)"\200", 1);
+    while ((context->count[0] & 504) != 448)
+	SHA1Update(context, (const u_char *)"\0", 1);
+    SHA1Update(context, finalcount, 8);  /* Should cause a SHA1Transform() */
+
+    if (digest) {
+	for (i = 0; i < 20; i++)
+	    digest[i] = (u_char)
+		((context->state[i>>2] >> ((3-(i & 3)) * 8) ) & 255);
+    }
+}
+
+#endif /* HAVE_SHA1_H */
diff --git a/ext4_utils/sha1.h b/ext4_utils/sha1.h
new file mode 100644
index 00000000..71334c83
--- /dev/null
+++ b/ext4_utils/sha1.h
@@ -0,0 +1,32 @@
+/*	$NetBSD: sha1.h,v 1.13 2005/12/26 18:41:36 perry Exp $	*/
+
+/*
+ * SHA-1 in C
+ * By Steve Reid <steve@edmweb.com>
+ * 100% Public Domain
+ */
+
+#ifndef _SYS_SHA1_H_
+#define	_SYS_SHA1_H_
+
+#include <sys/cdefs.h>
+#include <sys/types.h>
+#include <stdint.h>
+
+#define SHA1_DIGEST_LENGTH		20
+#define SHA1_DIGEST_STRING_LENGTH	41
+
+typedef struct {
+	uint32_t state[5];
+	uint32_t count[2];
+	u_char buffer[64];
+} SHA1_CTX;
+
+__BEGIN_DECLS
+void	SHA1Transform(uint32_t[5], const u_char[64]);
+void	SHA1Init(SHA1_CTX *);
+void	SHA1Update(SHA1_CTX *, const u_char *, u_int);
+void	SHA1Final(u_char[SHA1_DIGEST_LENGTH], SHA1_CTX *);
+__END_DECLS
+
+#endif /* _SYS_SHA1_H_ */
diff --git a/ext4_utils/simg2img.c b/ext4_utils/simg2img.c
new file mode 100644
index 00000000..9c1ad370
--- /dev/null
+++ b/ext4_utils/simg2img.c
@@ -0,0 +1,198 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#define _LARGEFILE64_SOURCE
+#define _FILE_OFFSET_BITS 64
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <sys/mman.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <stdio.h>
+
+#include "ext4_utils.h"
+#include "output_file.h"
+#include "sparse_format.h"
+
+#if defined(__APPLE__) && defined(__MACH__)
+#define lseek64 lseek
+#define off64_t off_t
+#endif
+
+#define COPY_BUF_SIZE (1024*1024)
+u8 *copybuf;
+
+#define SPARSE_HEADER_MAJOR_VER 1
+#define SPARSE_HEADER_LEN       (sizeof(sparse_header_t))
+#define CHUNK_HEADER_LEN (sizeof(chunk_header_t))
+
+void usage()
+{
+  fprintf(stderr, "Usage: simg2img <sparse_image_file> <raw_image_file>\n");
+}
+
+int process_raw_chunk(FILE *in, FILE *out, u32 blocks, u32 blk_sz, u32 *crc32)
+{
+	u64 len = (u64)blocks * blk_sz;
+	int chunk;
+
+	while (len) {
+		chunk = (len > COPY_BUF_SIZE) ? COPY_BUF_SIZE : len;
+		fread(copybuf, chunk, 1, in);
+		fwrite(copybuf, chunk, 1, out);
+		len -= chunk;
+	}
+
+	return blocks;
+}
+
+
+int process_skip_chunk(FILE *out, u32 blocks, u32 blk_sz, u32 *crc32)
+{
+	/* len needs to be 64 bits, as the sparse file specifies the skip amount
+	 * as a 32 bit value of blocks.
+	 */
+	u64 len = (u64)blocks * blk_sz;
+	long skip_chunk;
+
+	/* Fseek takes the offset as a long, which may be 32 bits on some systems.
+	 * So, lets do a sequence of fseeks() with SEEK_CUR to get the file pointer
+	 * where we want it.
+	 */
+	while (len) {
+		skip_chunk = (len > 0x80000000) ? 0x80000000 : len;
+		fseek(out, skip_chunk, SEEK_CUR);
+		len -= skip_chunk;
+	}
+
+	return blocks;
+}
+
+int main(int argc, char *argv[])
+{
+	FILE *in, *out;
+	unsigned int i;
+	sparse_header_t sparse_header;
+	chunk_header_t chunk_header;
+	u32 crc32 = 0;
+	u32 total_blocks = 0;
+
+	if (argc != 3) {
+		usage();
+		exit(-1);
+	}
+
+	if ( (copybuf = malloc(COPY_BUF_SIZE)) == 0) {
+		fprintf(stderr, "Cannot malloc copy buf\n");
+		exit(-1);
+	}
+
+	if ((in = fopen(argv[1], "rb")) == 0) {
+		fprintf(stderr, "Cannot open input file %s\n", argv[1]);
+		exit(-1);
+	}
+
+	if ((out = fopen(argv[2], "wb")) == 0) {
+		fprintf(stderr, "Cannot open output file %s\n", argv[2]);
+		exit(-1);
+	}
+
+	if (fread(&sparse_header, sizeof(sparse_header), 1, in) != 1) {
+		fprintf(stderr, "Error reading sparse file header\n");
+		exit(-1);
+	}
+
+	if (sparse_header.magic != SPARSE_HEADER_MAGIC) {
+		fprintf(stderr, "Bad magic\n");
+		exit(-1);
+	}
+
+	if (sparse_header.major_version != SPARSE_HEADER_MAJOR_VER) {
+		fprintf(stderr, "Unknown major version number\n");
+		exit(-1);
+	}
+
+	if (sparse_header.file_hdr_sz > SPARSE_HEADER_LEN) {
+		/* Skip the remaining bytes in a header that is longer than
+		 * we expected.
+		 */
+		fseek(in, sparse_header.file_hdr_sz - SPARSE_HEADER_LEN, SEEK_CUR);
+	}
+
+	for (i=0; i<sparse_header.total_chunks; i++) {
+		if (fread(&chunk_header, sizeof(chunk_header), 1, in) != 1) {
+			fprintf(stderr, "Error reading chunk header\n");
+			exit(-1);
+		}
+ 
+		if (sparse_header.chunk_hdr_sz > CHUNK_HEADER_LEN) {
+			/* Skip the remaining bytes in a header that is longer than
+			 * we expected.
+			 */
+			fseek(in, sparse_header.chunk_hdr_sz - CHUNK_HEADER_LEN, SEEK_CUR);
+		}
+
+		switch (chunk_header.chunk_type) {
+		    case CHUNK_TYPE_RAW:
+			if (chunk_header.total_sz != (sparse_header.chunk_hdr_sz +
+				 (chunk_header.chunk_sz * sparse_header.blk_sz)) ) {
+				fprintf(stderr, "Bogus chunk size for chunk %d, type Raw\n", i);
+				exit(-1);
+			}
+			total_blocks += process_raw_chunk(in, out,
+					 chunk_header.chunk_sz, sparse_header.blk_sz, &crc32);
+			break;
+		    case CHUNK_TYPE_DONT_CARE:
+			if (chunk_header.total_sz != sparse_header.chunk_hdr_sz) {
+				fprintf(stderr, "Bogus chunk size for chunk %d, type Dont Care\n", i);
+				exit(-1);
+			}
+			total_blocks += process_skip_chunk(out,
+					 chunk_header.chunk_sz, sparse_header.blk_sz, &crc32);
+			break;
+		    default:
+			fprintf(stderr, "Unknown chunk type 0x%4.4x\n", chunk_header.chunk_type);
+			exit(-1);
+		}
+
+	}
+
+	/* If the last chunk was a skip, then the code just did a seek, but
+	 * no write, and the file won't actually be the correct size.  This
+	 * will make the file the correct size.  Make sure the offset is
+	 * computed in 64 bits, and the function called can handle 64 bits.
+	 */
+	ftruncate(fileno(out), (u64)total_blocks * sparse_header.blk_sz);
+
+	fclose(in);
+	fclose(out);
+
+	if (sparse_header.total_blks != total_blocks) {
+		fprintf(stderr, "Wrote %d blocks, expected to write %d blocks\n",
+			 total_blocks, sparse_header.total_blks);
+		exit(-1);
+	}
+
+	if (sparse_header.image_checksum != crc32) {
+		fprintf(stderr, "computed crc32 of %d, expected %d\n",
+			 crc32, sparse_header.image_checksum);
+		exit(-1);
+	}
+
+	exit(0);
+}
+
diff --git a/ext4_utils/sparse_format.h b/ext4_utils/sparse_format.h
new file mode 100644
index 00000000..ba132140
--- /dev/null
+++ b/ext4_utils/sparse_format.h
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+typedef struct sparse_header {
+  __le32	magic;		/* 0xed26ff3a */
+  __le16	major_version;	/* (0x1) - reject images with higher major versions */
+  __le16	minor_version;	/* (0x0) - allow images with higer minor versions */
+  __le16	file_hdr_sz;	/* 28 bytes for first revision of the file format */
+  __le16	chunk_hdr_sz;	/* 12 bytes for first revision of the file format */
+  __le32	blk_sz;		/* block size in bytes, must be a multiple of 4 (4096) */
+  __le32	total_blks;	/* total blocks in the non-sparse output image */
+  __le32	total_chunks;	/* total chunks in the sparse input image */
+  __le32	image_checksum; /* CRC32 checksum of the original data, counting "don't care" */
+				/* as 0. Standard 802.3 polynomial, use a Public Domain */
+				/* table implementation */
+} sparse_header_t;
+
+#define SPARSE_HEADER_MAGIC	0xed26ff3a
+
+#define CHUNK_TYPE_RAW		0xCAC1
+#define CHUNK_TYPE_FILL		0xCAC2
+#define CHUNK_TYPE_DONT_CARE	0xCAC3
+
+typedef struct chunk_header {
+  __le16	chunk_type;	/* 0xCAC1 -> raw; 0xCAC2 -> fill; 0xCAC3 -> don't care */
+  __le16	reserved1;
+  __le32	chunk_sz;	/* in blocks in output image */
+  __le32	total_sz;	/* in bytes of chunk input file including chunk header and data */
+} chunk_header_t;
+
+/* Following a Raw or Fill chunk is data.  For a Raw chunk, it's the data in chunk_sz * blk_sz.
+ *  For a Fill chunk, it's 4 bytes of the fill data.
+ */
+
diff --git a/ext4_utils/uuid.c b/ext4_utils/uuid.c
new file mode 100644
index 00000000..ac9b518c
--- /dev/null
+++ b/ext4_utils/uuid.c
@@ -0,0 +1,59 @@
+/*
+ * 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 <string.h>
+#include <arpa/inet.h>
+
+#include "ext4_utils.h"
+#include "sha1.h"
+#include "uuid.h"
+
+struct uuid {
+	u32 time_low;
+	u32 time_mid;
+	u16 time_hi_and_version;
+	u8 clk_seq_hi_res;
+	u8 clk_seq_low;
+	u16 node0_1;
+	u32 node2_5;
+};
+
+static void sha1_hash(const char *namespace, const char *name,
+	unsigned char sha1[SHA1_DIGEST_LENGTH])
+{
+	SHA1_CTX ctx;
+	SHA1Init(&ctx);
+	SHA1Update(&ctx, (const u8*)namespace, strlen(namespace));
+	SHA1Update(&ctx, (const u8*)name, strlen(name));
+	SHA1Final(sha1, &ctx);
+}
+
+void generate_uuid(const char *namespace, const char *name, u8 result[16])
+{
+	unsigned char sha1[SHA1_DIGEST_LENGTH];
+	struct uuid *uuid = (struct uuid *)result;
+
+	sha1_hash(namespace, name, (unsigned char*)sha1);
+	memcpy(uuid, sha1, sizeof(struct uuid));
+
+	uuid->time_low = ntohl(uuid->time_low);
+	uuid->time_mid = ntohs(uuid->time_mid);
+	uuid->time_hi_and_version = ntohs(uuid->time_hi_and_version);
+	uuid->time_hi_and_version &= 0x0FFF;
+	uuid->time_hi_and_version |= (5 << 12);
+	uuid->clk_seq_hi_res &= ~(1 << 6);
+	uuid->clk_seq_hi_res |= 1 << 7;
+}
diff --git a/ext4_utils/uuid.h b/ext4_utils/uuid.h
new file mode 100644
index 00000000..ff1b4385
--- /dev/null
+++ b/ext4_utils/uuid.h
@@ -0,0 +1,24 @@
+/*
+ * 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 _UUID_H_
+#define _UUID_H_
+
+#include "ext4_utils.h"
+
+void generate_uuid(const char *namespace, const char *name, u8 result[16]);
+
+#endif