Initial commit for syspatch, a binary patching tool for large files.

Change-Id: I3519f6b1a40d95d36a0317e14d53bcbfc20eba6e

1 files changed, 566 insertions, 0 deletions

diff --git a/syspatch.c b/syspatch.c
new file mode 100644
index 0000000..070dfd5
--- /dev/null
+++ b/syspatch.c
@@ -0,0 +1,566 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA.
+ */
+
+#include <errno.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "xdelta3.c"
+#include "xdelta3.h"
+#include "xz.h"
+
+// XZ_DICT_SIZE represents the size of the dictionary used for XZ decompression.
+// Higher values improve compression, but consume more memory.
+#define XZ_DICT_SIZE (1U<<26)
+// XZ_OUTPUT_SIZE tunes the amount of data that XZ buffers before handing it off
+// to the patcher. Settings lower than TARGET_WINDOW_SIZE or higher than
+// SOURCE_WINDOW_SIZE probably don't make any sense, but this is untested. The
+// primary tradeoff made here is between memory and extra calls to the decoder.
+#define XZ_OUTPUT_SIZE (1U<<23)
+// TARGET_WINDOW_SIZE determines how large writes to the target file are. There
+// isn't a lot of science behind this yet, excepting the notes about the write
+// queue below.
+#define TARGET_WINDOW_SIZE (1U<<23)
+// SOURCE_WINDOW_SIZE is one of the primary tunables. Higher values increase
+// compression ratios and improve decoder speed, but consume more memory.
+#define SOURCE_WINDOW_SIZE (1U<<26)
+// WRITE_QUEUE_LENGTH * TARGET_WINDOW_SIZE must be >= SOURCE_WINDOW_SIZE / 2.
+// This ensures that writes will always happen behind an area where a read
+// might occur. This is enforced by the READ_FRONTIER check.
+#define WRITE_QUEUE_LENGTH (4)
+// READ_CACHE_LENGTH is defined based on the acceptability of a time/memory
+// tradeoff. A value of at least one is necessary to not completely suck, and
+// two or higher is recommended. Higher than 8 will probably not yield
+// reasonable returns for realistic patches.
+#define READ_CACHE_LENGTH (2)
+
+static uint8_t in[XZ_OUTPUT_SIZE];
+static uint8_t out[XZ_OUTPUT_SIZE];
+
+typedef struct TargetWrite TargetWrite;
+struct TargetWrite {
+    size_t start;
+    size_t length;
+    uint8_t data[TARGET_WINDOW_SIZE];
+};
+
+typedef struct SourceRead SourceRead;
+struct SourceRead {
+    size_t blkno;
+    size_t length;
+    uint8_t data[SOURCE_WINDOW_SIZE];
+};
+
+static SourceRead* READ_CACHE[READ_CACHE_LENGTH];
+static size_t SOURCE_WINDOWS_CACHED;
+
+typedef struct XZContext XZContext;
+struct XZContext {
+    struct xz_buf b;
+    struct xz_dec *s;
+    enum xz_ret ret;
+    const char *msg;
+};
+
+static TargetWrite* WRITE_QUEUE[WRITE_QUEUE_LENGTH];
+static size_t TARGET_WINDOWS_WRITTEN;
+static size_t READ_FRONTIER;
+
+//============================================================================//
+//                                 Source I/O                                 //
+//============================================================================//
+
+static SourceRead *shuffle_cache(SourceRead *tmp, size_t index) {
+    SourceRead *current = READ_CACHE[index];
+    READ_CACHE[index] = tmp;
+    return current;
+}
+
+static int add_to_read_cache(SourceRead *source_read) {
+    int i = 0;
+    SourceRead *tmp = NULL;
+    for (i; i < READ_CACHE_LENGTH; i++) {
+        if (tmp == source_read)
+            break;
+        tmp = shuffle_cache(tmp, i);
+    }
+    if (tmp != source_read)
+        free(tmp);
+    READ_CACHE[0] = source_read;
+    return 0;
+}
+
+static size_t read_source_file(uint8_t *data, FILE *file) {
+    size_t size;
+    fflush(file);
+    size = fread((void*)data, 1, SOURCE_WINDOW_SIZE, file);
+    fflush(file);
+    return size;
+}
+
+static int check_read(size_t pos, size_t frontier) {
+    if (pos < frontier) {
+        fprintf(stderr, "Read past frontier: %zu > %zu\n", pos, frontier);
+        return -1;
+    }
+    return 0;
+}
+
+static SourceRead *get_source_window_from_file(xd3_source *source) {
+    size_t read_position = source->getblkno * source->blksize;
+    SourceRead *source_read = malloc(sizeof(SourceRead));
+    memset(source_read, 0, sizeof(SourceRead));
+    if (check_read(read_position, READ_FRONTIER) < 0)
+        return NULL;
+    if (fseek(source->ioh, read_position, SEEK_SET) != 0) {
+        fprintf(stderr, "Couldn't seek to %zu\n", read_position);
+        return NULL;
+    }
+    source_read->blkno = source->getblkno;
+    source_read->length = read_source_file(source_read->data, source->ioh);
+    return source_read;
+}
+
+static SourceRead *get_source_window_from_cache(size_t blkno) {
+    int i = 0;
+    for (i; i < READ_CACHE_LENGTH; i++) {
+        if (READ_CACHE[i]->blkno == blkno) {
+            return READ_CACHE[i];
+        }
+    }
+    return NULL;
+}
+
+static int read_to_source(SourceRead *source_read, xd3_source *source) {
+    source->onblk = source_read->length;
+    source->curblkno = source->getblkno;
+    source->curblk = source_read->data;
+    return 0;
+}
+
+static int process_source_data(xd3_source *source) {
+    SourceRead *source_read = get_source_window_from_cache(source->getblkno);
+    if (source_read == NULL) {
+        source_read = get_source_window_from_file(source);
+    }
+    if (source_read == NULL) {
+        return -1;
+    }
+    add_to_read_cache(source_read);
+    return read_to_source(source_read, source);
+}
+
+//============================================================================//
+//                                Patch I/O                                   //
+//============================================================================//
+
+static int read_compressed_input(XZContext *context, FILE *infile) {
+    if (context->b.in_pos == context->b.in_size) {
+        context->b.in_size = fread(in, 1, XZ_OUTPUT_SIZE, infile);
+        context->b.in_pos = 0;
+    }
+    return 0;
+}
+
+//============================================================================//
+//                                 Target I/O                                 //
+//============================================================================//
+
+static int write_target(TargetWrite *tgt, FILE *target_file) {
+    if (tgt->length > 0) {
+        if (fseek(target_file, tgt->start, SEEK_SET) != 0)
+            return -1;
+        if (fwrite(tgt->data, 1, tgt->length, target_file) != tgt->length)
+            return -1;
+        if (fflush(target_file) != 0)
+            return -1;
+    }
+    READ_FRONTIER = ftell(target_file);
+    return 0;
+}
+
+static int stream_to_target_write(xd3_stream *stream, TargetWrite *tgt) {
+    if (stream->avail_out) {
+        tgt->start = TARGET_WINDOWS_WRITTEN * TARGET_WINDOW_SIZE;
+        tgt->length = stream->avail_out;
+        memcpy(tgt->data, stream->next_out, tgt->length);
+        xd3_consume_output(stream);
+    }
+    return 0;
+}
+
+static int advance_target_buffer(xd3_stream *stream, FILE *target_file) {
+    TargetWrite *tgt = WRITE_QUEUE[TARGET_WINDOWS_WRITTEN % WRITE_QUEUE_LENGTH];
+    if (write_target(tgt, target_file) != 0)
+        return -1;
+    if (stream_to_target_write(stream, tgt) != 0)
+        return -1;
+    TARGET_WINDOWS_WRITTEN += 1;
+    return 0;
+}
+
+static int process_target_data(xd3_stream *stream, FILE *target, int force) {
+    size_t iters = (force == 0) + (force * WRITE_QUEUE_LENGTH);
+    while (iters) {
+        if (advance_target_buffer(stream, target) < 0)
+            return -1;
+        iters -= 1;
+    }
+    return 0;
+}
+
+//============================================================================//
+//                          Read Cache Setup and Teardown                     //
+//============================================================================//
+
+static int setup_read_cache(FILE *source_file) {
+    int i = 0;
+    size_t length;
+    for (i; i < READ_CACHE_LENGTH; i++) {
+        READ_CACHE[i] = malloc(sizeof(SourceRead));
+        if (READ_CACHE[i] == NULL)
+            return -1;
+        READ_CACHE[i]->blkno = i;
+        length = read_source_file(READ_CACHE[i]->data, source_file);
+        READ_CACHE[i]->length = length;
+    }
+    SOURCE_WINDOWS_CACHED = READ_CACHE_LENGTH;
+    return 0;
+}
+
+static int teardown_read_cache() {
+    int i = 0;
+    for (i; i < READ_CACHE_LENGTH; i++) {
+        free(READ_CACHE[i]);
+    }
+    return 0;
+}
+
+//============================================================================//
+//                        Write Queue Setup and Teardown                      //
+//============================================================================//
+
+static int setup_write_queue() {
+    TARGET_WINDOWS_WRITTEN = 0;
+    int i = 0;
+    for (i; i < WRITE_QUEUE_LENGTH; i++) {
+        WRITE_QUEUE[i] = malloc(sizeof(TargetWrite));
+        if (WRITE_QUEUE[i] == NULL)
+            return -1;
+        WRITE_QUEUE[i]->start = 0;
+        WRITE_QUEUE[i]->length = 0;
+        memset(WRITE_QUEUE[i]->data, 0, TARGET_WINDOW_SIZE);
+    }
+    return 0;
+}
+
+static int teardown_write_queue() {
+    int i = 0;
+    for (i; i < WRITE_QUEUE_LENGTH; i++) {
+        free(WRITE_QUEUE[i]);
+    }
+    return 0;
+}
+
+//============================================================================//
+//                        Decompressor Setup and Teardown                     //
+//============================================================================//
+static int setup_xz_buf(struct xz_buf *b) {
+    b->in = in;
+    b->in_pos = 0;
+    b->in_size = 0;
+    b->out = out;
+    b->out_pos = 0;
+    b->out_size = XZ_OUTPUT_SIZE;
+    return 0;
+}
+
+static int setup_xz_dec(struct xz_dec **s) {
+    *s = xz_dec_init(XZ_DYNALLOC, XZ_DICT_SIZE);
+    if (*s == NULL)
+        return -1;
+    return 0;
+}
+
+static int setup_xz_context(XZContext *context) {
+    xz_crc32_init();
+    setup_xz_dec(&context->s);
+    if (setup_xz_buf(&context->b) < 0)
+        return -1;
+    return 0;
+}
+
+//============================================================================//
+//                          Patcher Setup and Teardown                        //
+//============================================================================//
+
+static int setup_xdelta_config(xd3_config *config, xd3_stream *stream) {
+    int ret;
+    memset(config, 0, sizeof(*config));
+    xd3_init_config(config, 0);
+    config->winsize = TARGET_WINDOW_SIZE;
+    config->getblk = NULL;
+    ret = xd3_config_stream(stream, config);
+    if (ret != 0) {
+        fprintf(stderr, "xd3_config_stream error: %s\n", xd3_strerror(ret));
+        return -1;
+    }
+    return 0;
+}
+
+static int setup_xdelta_source( xd3_source *source,
+                                xd3_stream *stream,
+                                FILE *source_file) {
+    int ret;
+    memset(source, 0, sizeof(*source));
+    source->name = "source";
+    source->ioh = source_file;
+    source->blksize = SOURCE_WINDOW_SIZE;
+    source->curblkno = 0;
+    source->curblk = NULL;
+    source->onblk = 0;
+    READ_FRONTIER = 0;
+
+    ret = xd3_set_source(stream, source);
+    if (ret != 0) {
+        fprintf(stderr, "xd3_set_source error: %s\n", xd3_strerror(ret));
+        return -1;
+    }
+    return 0;
+}
+
+static void teardown_xdelta_stream(xd3_stream *stream) {
+    xd3_close_stream(stream);
+    xd3_free_stream(stream);
+}
+
+//============================================================================//
+//                             Decompression Loop                             //
+//============================================================================//
+
+static int run_decompressor(XZContext *context, FILE *infile) {
+    context->ret = xz_dec_run(context->s, &context->b);
+    read_compressed_input(context, infile);
+    return context->b.out_pos == XZ_OUTPUT_SIZE;
+}
+
+static int decompress_into_buffer(
+        XZContext *context,
+        FILE *infile,
+        int *buffer_filled,
+        int *done) {
+
+    *buffer_filled = run_decompressor(context, infile);
+    if (context->ret == XZ_OK)
+        return 0;
+
+    switch (context->ret) {
+        case XZ_STREAM_END:
+            *buffer_filled = 1;
+            *done = 1;
+            return 0;
+        case XZ_MEM_ERROR:
+        case XZ_MEMLIMIT_ERROR:
+        case XZ_FORMAT_ERROR:
+        case XZ_OPTIONS_ERROR:
+        case XZ_DATA_ERROR:
+        case XZ_BUF_ERROR:
+            context->msg = "File is corrupt\n";
+            return -1;
+        default:
+            context->msg = "Bug!\n";
+            return -1;
+    }
+}
+
+static int decompress(XZContext *context, FILE *patch_file) {
+    int done = 0;
+    int filled = 0;
+    while (!filled) {
+        if (decompress_into_buffer(context, patch_file, &filled, &done) < 0)
+            return -1;
+    }
+    return done;
+}
+
+static int decompress_patch(XZContext *context,
+                            FILE *patch_file,
+                            xd3_stream *stream) {
+    int done = decompress(context, patch_file);
+    xd3_avail_input(stream, out, context->b.out_pos);
+    context->b.out_pos = 0;
+    return done;
+}
+
+//============================================================================//
+//                                Patching Loop                               //
+//============================================================================//
+
+static int patch(
+        XZContext *context,
+        xd3_stream *stream,
+        xd3_source *source,
+        FILE *patch_file,
+        FILE *target_file) {
+
+    int ret = 0;
+    int decompression_done;
+
+    fprintf(stderr, "Hello?\n");
+    source->curblk = READ_CACHE[0]->data;
+    source->onblk = READ_CACHE[0]->length;
+    source->curblkno = 0;
+
+    do {
+        decompression_done = decompress_patch(context, patch_file, stream);
+        if (decompression_done < 0)
+            goto err;
+        if (decompression_done)
+            xd3_set_flags(stream, XD3_FLUSH);
+process:
+        ret = xd3_decode_input(stream);
+        switch (ret) {
+            case XD3_INPUT:
+                continue;
+            case XD3_OUTPUT:
+                if (process_target_data(stream, target_file, 0) < 0)
+                    goto err;
+                goto process;
+            case XD3_GETSRCBLK:
+                if (process_source_data(source) < 0)
+                    goto err;
+                goto process;
+            case XD3_GOTHEADER:
+                goto process;
+            case XD3_WINSTART:
+                goto process;
+            case XD3_WINFINISH:
+                goto process;
+            default:
+                goto err;
+        }
+    } while (!decompression_done);
+
+    process_target_data(stream, target_file, 1);
+
+    ret = 0;
+    goto out;
+
+err:
+    fprintf(stderr, "error: %s (%s)\n", xd3_strerror(ret), stream->msg);
+    ret = -1;
+out:
+    xz_dec_end(context->s);
+    return ret;
+}
+
+//============================================================================//
+//                                 Main Logic                                 //
+//============================================================================//
+static int syspatch(FILE *source_file, FILE *patch_file, FILE *target_file) {
+    XZContext xz_context;
+    xd3_stream stream;
+    xd3_config config;
+    xd3_source source;
+
+    if (setup_read_cache(source_file) != 0)
+        return -1;
+
+    if (setup_write_queue() != 0)
+        return -1;
+
+    if (setup_xz_context(&xz_context) != 0)
+        return -1;
+
+    if (setup_xdelta_config(&config, &stream) != 0)
+        return -1;
+
+    if (setup_xdelta_source(&source, &stream, source_file) != 0)
+        return -1;
+
+    if (patch(&xz_context, &stream, &source, patch_file, target_file) != 0)
+        return -1;
+
+    teardown_read_cache();
+    teardown_write_queue();
+    teardown_xdelta_stream(&stream);
+    return 0;
+}
+
+//============================================================================//
+//                                Test Harness                                //
+//============================================================================//
+
+static int usage(char *progname) {
+    return fprintf(stderr, "%s: <source> <patch> <target>", progname);
+}
+
+static int parse_arguments(
+        int argc,
+        char **argv,
+        FILE **source_file,
+        FILE **patch_file,
+        FILE **target_file) {
+
+    if (argc < 4) {
+        usage(argv[1]);
+        return -1;
+    }
+
+    *source_file = fopen(argv[1], "r");
+    if (*source_file == NULL) {
+        fprintf(stderr, "Error opening source file: %s\n", strerror(errno));
+        return -1;
+    }
+
+    *patch_file = fopen(argv[2], "r");
+    if (*patch_file == NULL) {
+        fprintf(stderr, "Error opening patch file: %s\n", strerror(errno));
+        return -1;
+    }
+
+    *target_file = fopen(argv[3], "r+");
+    if (*target_file == NULL) {
+        fprintf(stderr, "Error opening target file: %s\n", strerror(errno));
+        return -1;
+    }
+
+    return 0;
+}
+
+int main(int argc, char **argv)
+{
+    int retval;
+    FILE *source_file;
+    FILE *patch_file;
+    FILE *target_file;
+
+    if (parse_arguments(argc, argv, &source_file, &patch_file, &target_file))
+        return 1;
+
+    retval = syspatch(source_file, patch_file, target_file);
+
+    fclose(source_file);
+    fclose(patch_file);
+    fclose(target_file);
+
+    return (retval != 0);
+}