Initial revision

1 files changed, 351 insertions, 0 deletions

diff --git a/rsync/delta.c b/rsync/delta.c
new file mode 100644
index 0000000..323c079
--- a/dev/null
+++ b/rsync/delta.c
@@ -0,0 +1,351 @@
+/*= -*- c-basic-offset: 4; indent-tabs-mode: nil; -*-
+ *
+ * librsync -- library for network deltas
+ * $Id$
+ *
+ * Copyright (C) 2000, 2001 by Martin Pool <mbp@samba.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+                                /*
+                                 | Let's climb to the TOP of that
+                                 | MOUNTAIN and think about STRIP
+                                 | MINING!!
+                                 */
+
+
+/*
+ * delta.c -- Generate in streaming mode an rsync delta given a set of
+ * signatures, and a new file.
+ *
+ * The size of blocks for signature generation is determined by the
+ * block size in the incoming signature.
+ *
+ * To calculate a signature, we need to be able to see at least one
+ * block of the new file at a time.  Once we have that, we calculate
+ * its weak signature, and see if there is any block in the signature
+ * hash table that has the same weak sum.  If there is one, then we
+ * also compute the strong sum of the new block, and cross check that.
+ * If they're the same, then we can assume we have a match.
+ *
+ * The final block of the file has to be handled a little differently,
+ * because it may be a short match.  Short blocks in the signature
+ * don't include their length -- we just allow for the final short
+ * block of the file to match any block in the signature, and if they
+ * have the same checksum we assume they must have the same length.
+ * Therefore, when we emit a COPY command, we have to send it with a
+ * length that is the same as the block matched, and not the block
+ * length from the signature.
+ */
+
+/*
+ * Profiling results as of v1.26, 2001-03-18:
+ *
+ * If everything matches, then we spend almost all our time in
+ * rs_mdfour64 and rs_weak_sum, which is unavoidable and therefore a
+ * good profile.
+ *
+ * If nothing matches, it is not so good.
+ */
+
+
+#include <config_rsync.h>
+
+#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "rsync.h"
+#include "emit.h"
+#include "stream.h"
+#include "util.h"
+#include "sumset.h"
+#include "job.h"
+#include "trace.h"
+#include "checksum.h"
+#include "search.h"
+#include "types.h"
+
+
+/**
+ * Turn this on to make all rolling checksums be checked from scratch.
+ */
+int rs_roll_paranoia = 0;
+
+
+static rs_result rs_delta_scan(rs_job_t *, rs_long_t avail_len, void *);
+
+static rs_result rs_delta_s_deferred_copy(rs_job_t *job);
+
+
+
+static rs_result rs_delta_s_end(rs_job_t *job)
+{
+    rs_emit_end_cmd(job);
+    return RS_DONE;
+}
+
+
+/**
+ * \brief Get a block of data if possible, and see if it matches.
+ *
+ * On each call, we try to process all of the input data available on
+ * the scoop and input buffer.
+ */
+static rs_result
+rs_delta_s_scan(rs_job_t *job)
+{
+    size_t         this_len, avail_len;
+    int            is_ending;
+    void           *inptr;
+    rs_result      result;
+
+    rs_job_check(job);
+
+    avail_len = rs_scoop_total_avail(job);
+    this_len = job->block_len;
+    is_ending = job->stream->eof_in;
+
+    /* Now, we have avail_len bytes, and we need to scan through them
+     * looking for a match.  We'll always end up emitting exactly one
+     * command, either a literal or a copy, and after discovering that
+     * we will skip over the appropriate number of bytes. */
+    if (avail_len == 0) {
+        if (is_ending) {
+            /* no more delta to do */
+            job->statefn = rs_delta_s_end;
+        }
+        return RS_BLOCKED;
+    } 
+
+    /* must read at least one block, or give up */
+    if ((avail_len < job->block_len) && !is_ending) {
+        /* we know we won't get it, but we have to try for a whole
+         * block anyhow so that it gets into the scoop. */
+        rs_scoop_input(job, job->block_len);
+        return RS_BLOCKED;
+    }
+    
+    result = rs_scoop_readahead(job, avail_len, &inptr);
+    if (result != RS_DONE)
+        return result;
+    
+    return rs_delta_scan(job, avail_len, inptr);
+}
+
+
+
+/**
+ * Scan for a matching block in the next \p avail_len bytes of input.
+ *
+ * If nonmatching data is found, then a LITERAL command will be put in
+ * the tube immediately.  If matching data is found, then its position
+ * will be saved in the job, and the job state set up to write out a
+ * COPY command after handling the literal.
+ */
+static rs_result
+rs_delta_scan(rs_job_t *job, rs_long_t avail_len, void *p)
+{
+    rs_long_t            match_where;
+    int                  search_pos, end_pos;
+    unsigned char        *inptr = (unsigned char *) p;
+    uint32_t             s1 = job->weak_sig & 0xFFFF;
+    uint32_t             s2 = job->weak_sig >> 16;
+    
+    /* So, we have avail_len bytes of data, and we want to look
+     * through it for a match at some point.  It's OK if it's not at
+     * the start of the available input data.  If we're approaching
+     * the end and can't get a match, then we just block and get more
+     * later. */
+
+    /* FIXME: Perhaps we should be working in signed chars for the
+     * rolling sum? */
+    
+    if (job->stream->eof_in)
+        end_pos = avail_len - 1;
+    else
+        end_pos = avail_len - job->block_len;
+    
+    for (search_pos = 0; search_pos <= end_pos; search_pos++) {
+        size_t this_len = job->block_len;
+            
+        if (search_pos + this_len > avail_len) {
+            this_len = avail_len - search_pos;
+            rs_trace("block reduced to %d", this_len);
+        } else if (job->have_weak_sig) {
+            unsigned char a = inptr[search_pos + this_len - 1];
+            /* roll in the newly added byte, if any */
+            s1 += a + RS_CHAR_OFFSET;
+            s2 += s1;
+
+            job->weak_sig = (s1 & 0xffff) | (s2 << 16);
+        }
+
+        if (!job->have_weak_sig) {
+            rs_trace("calculate weak sum from scratch");
+            job->weak_sig = rs_calc_weak_sum(inptr + search_pos, this_len);
+            s1 = job->weak_sig & 0xFFFF;
+            s2 = job->weak_sig >> 16;
+            job->have_weak_sig = 1;
+        }
+
+        if (rs_roll_paranoia) {
+            rs_weak_sum_t verify = rs_calc_weak_sum(inptr + search_pos, this_len);
+            if (verify != job->weak_sig) {
+                rs_fatal("mismatch between rolled sum %#x and check %#x",
+                         job->weak_sig, verify);
+            }
+        }            
+        
+        if (rs_search_for_block(job->weak_sig, inptr + search_pos, this_len,
+                                job->signature, &job->stats, &match_where)) {
+            /* So, we got a match.  Cool.  However, there may be
+             * leading unmatched data that we need to flush.  Thus we
+             * set our statefn to be rs_delta_s_deferred_copy so that
+             * we can write out the command later. */
+
+            rs_trace("matched %.0f bytes at %.0f!",
+                     (double) this_len, (double) match_where);
+            job->basis_pos = match_where;
+            job->basis_len = this_len;
+            job->statefn = rs_delta_s_deferred_copy;
+            job->have_weak_sig = 0;
+            break;
+        } else {
+            /* advance by one; roll out the byte we just moved over. */
+            unsigned char a = inptr[search_pos];
+            unsigned char shift = a + RS_CHAR_OFFSET;
+
+            s1 -= shift;
+            s2 -= this_len * shift;
+            job->weak_sig = (s1 & 0xffff) | (s2 << 16);
+        }
+    }
+
+    if (search_pos > 0) {
+        /* We may or may not have found a block, but we know we found
+         * some literal data at the start of the buffer.  Therefore,
+         * we have to flush that out before we can continue on and
+         * emit the copy command or keep searching. */
+         
+        /* FIXME: At the moment, if you call with very short buffers,
+         * then you will get a series of very short LITERAL commands.
+         * Perhaps this is what you deserve, or perhaps we should try
+         * to get more readahead and avoid that. */
+
+        /* There's some literal data at the start of this window which
+         * we know is not in any block. */
+        rs_trace("got %d bytes of literal data", search_pos);
+        rs_emit_literal_cmd(job, search_pos);
+        rs_tube_copy(job, search_pos);
+    }
+    
+    return RS_RUNNING;
+}
+
+
+
+static rs_result rs_delta_s_deferred_copy(rs_job_t *job)
+{
+    if (!job->basis_len) {
+        rs_log(RS_LOG_ERR, "somehow got zero basis_len");
+        return RS_INTERNAL_ERROR;
+    }
+    
+    rs_emit_copy_cmd(job, job->basis_pos, job->basis_len);
+    rs_scoop_advance(job, job->basis_len);
+
+    job->statefn = rs_delta_s_scan;
+    
+    return RS_RUNNING;
+}
+
+
+/**
+ * \brief State function that does a slack delta containing only
+ * literal data to recreate the input.
+ */
+static rs_result rs_delta_s_slack(rs_job_t *job)
+{
+    rs_buffers_t * const stream = job->stream;
+    size_t avail = stream->avail_in;
+
+    if (avail) {
+        rs_trace("emit slack delta for %.0f available bytes", (double) avail);
+        rs_emit_literal_cmd(job, avail);
+        rs_tube_copy(job, avail);
+        return RS_RUNNING;
+    } else {
+        if (rs_job_input_is_ending(job)) {
+            job->statefn = rs_delta_s_end;
+            return RS_RUNNING;
+        } else {                
+            return RS_BLOCKED;
+        }
+    }
+}
+
+
+/**
+ * State function for writing out the header of the encoding job.
+ */
+static rs_result rs_delta_s_header(rs_job_t *job)
+{
+    rs_emit_delta_header(job);
+
+    if (job->block_len) {
+        if (!job->signature) {
+            rs_error("no signature is loaded into the job");
+            return RS_PARAM_ERROR;
+        }
+        job->statefn = rs_delta_s_scan;
+    } else {
+        rs_trace("block length is zero for this delta; "
+                 "therefore using slack deltas");
+        job->statefn = rs_delta_s_slack;
+    }
+
+    return RS_RUNNING;
+}
+
+
+/**
+ * Prepare to compute a streaming delta.
+ */
+rs_job_t *rs_delta_begin(rs_signature_t *sig)
+{
+    rs_job_t *job;
+
+    job = rs_job_new("delta", rs_delta_s_header);
+    job->signature = sig;
+    
+    if ((job->block_len = sig->block_len) < 0) {
+        rs_log(RS_LOG_ERR, "unreasonable block_len %d in signature",
+               job->block_len);
+        return NULL;
+    }
+
+    job->strong_sum_len = sig->strong_sum_len;
+    if (job->strong_sum_len < 0  ||  job->strong_sum_len > RS_MD4_LENGTH) {
+        rs_log(RS_LOG_ERR, "unreasonable strong_sum_len %d in signature",
+               job->strong_sum_len);
+        return NULL;
+    }
+        
+    return job;
+}
+
+