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