Logo Search packages:      
Sourcecode: xdelta version File versions  Download package

xdrsync.c

/* -*- Mode: C;-*-
 *
 * This file is part of XDelta - A binary delta generator.
 *
 * Copyright (C) 1997, 1998, 1999  Josh MacDonald
 *
 * 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., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * Author: Josh MacDonald <jmacd@CS.Berkeley.EDU>
 *
 * $Id: xdrsync.c 1.2 Thu, 01 Apr 1999 23:29:11 -0800 jmacd $
 */

#include <string.h>
#include <stdlib.h>

#include "xdelta.h"
#include "xdeltapriv.h"

/* Rsync
 */

static void
init_long_checksum (const guint8 *buf, guint len, XdeltaChecksum *cksum)
{
  guint16 low  = cksum->low;
  guint16 high = cksum->high;

  /* @@@ unroll me? */
  for (; len > 0; len -= 1)
    {
      low  += CHEW(*buf++);
      high += low;
    }

  cksum->low  = low;
  cksum->high = high;
}

static XdeltaRsync*
xdp_rsync_index_int (XdeltaStream      *str,
                 guint              seg_len)
{
  guint to_index = seg_len;
  XdeltaPos pos;
  XdeltaChecksum cksum;
  GArray    *index;
  EdsioMD5Ctx ctx;

  index = g_array_new (FALSE, FALSE, sizeof (XdeltaRsyncElt));

  init_pos (str, &pos);

  memset (&cksum, 0, sizeof (cksum));

  edsio_md5_init (& ctx);

  for (;;)
    {
      gint consume;

      if (! map_page (str, &pos))
      return NULL;

      consume = MIN (to_index, pos.mem_rem - pos.off);

      if (consume == 0)
      break;

      to_index -= consume;

      edsio_md5_update (& ctx, pos.mem + pos.off, consume);
      init_long_checksum (pos.mem + pos.off, consume, &cksum);

      if (to_index == 0)
      {
        XdeltaRsyncElt elt;

        edsio_md5_final (elt.md5, &ctx);

        elt.cksum = cksum;

        g_array_append_val (index, elt);

        edsio_md5_init (& ctx);
        memset (&cksum, 0, sizeof (cksum));
        to_index = seg_len;
      }

      pos.off += consume;

      FLIP_FORWARD (pos);
    }

  if (! unmap_page (str, &pos))
    return NULL;

  {
    XdeltaRsync* rsync = g_new (XdeltaRsync, 1);

    rsync->seg_len = seg_len;
    rsync->file_len = handle_length (str);

    memcpy (rsync->file_md5, handle_checksum_md5 (str), 16);

    rsync->index = &g_array_index (index, XdeltaRsyncElt, 0);
    rsync->index_len = index->len;

    return rsync;
  }
}

static XdeltaRsync*
xdp_rsync_read_index (XdeltaStream*    cache_in)
{
  SerialSource* src = handle_source (cache_in);
  XdeltaRsync* rsync;

  if (! src)
    return NULL;

  if (! unserialize_rsyncindex (src, &rsync))
    return NULL;

  return rsync;
}

static gboolean
xdp_rsync_write_index (XdeltaRsync*     rsync,
                   XdeltaOutStream* cache_out)
{
  SerialSink* sink = handle_sink (cache_out, NULL, NULL, NULL, NULL);

  if (! sink)
    return FALSE;

  if (! serialize_rsyncindex_obj (sink, rsync))
    return FALSE;

  if (! handle_close (cache_out, 0))
    return FALSE;

  return TRUE;
}

XdeltaRsync*
xdp_rsync_index (XdeltaStream      *str,
             guint              seg_len,
             XdeltaStream      *cache_in,
             XdeltaOutStream   *cache_out)
{
  XdeltaRsync* rsync;

  if (cache_in)
    {
      if (! (rsync = xdp_rsync_read_index (cache_in)))
      return NULL;

      if (seg_len != rsync->seg_len ||
        (str && ! check_stream_integrity (str, rsync->file_md5, rsync->file_len)))
      {
        xd_generate_void_event (EC_XdInvalidRsyncCache);
        goto bail;
      }

      return rsync;
    }
  else
    {
      if (! (rsync = xdp_rsync_index_int (str, seg_len)))
      return NULL;

      if (cache_out)
      {
        if (! xdp_rsync_write_index (rsync, cache_out))
          goto bail;
      }

      return rsync;
    }

bail:

  xdp_rsync_index_free (rsync);

  return NULL;
}

void
xdp_rsync_index_free (XdeltaRsync *rsync)
{
  /* ??? */
}

static
gboolean xdp_rsync_hash (XdeltaRsync* rsync)
{
  guint i, index, prime = 0;
  gboolean already_hashed = rsync->table != NULL;
  SerialRsyncIndexElt** table = NULL;

  if (! already_hashed)
    {
      prime = rsync->table_size = g_spaced_primes_closest (rsync->index_len);
      table = rsync->table = g_new0 (SerialRsyncIndexElt*, prime);
    }

  for (i = 0; i < rsync->index_len; i += 1)
    {
      SerialRsyncIndexElt* elt = rsync->index + i;

      elt->match_offset = -1;

      if (! already_hashed)
      {
        index = c_hash (& elt->cksum) % prime;

        elt->next = table[index];
        table[index] = elt;
      }
    }

  return TRUE;
}

static void
incr_by (XdeltaPos* pos, gint incr)
{
  do
    {
      gint rem = MIN (incr, pos->mem_rem - pos->off);

      pos->off += incr;
      incr -= rem;
      FLIP_FORWARD (*pos);
    }
  while (incr > 0 && pos->mem_rem != pos->page_size);
}

GArray*
xdp_rsync_request (XdeltaStream      *file,
               XdeltaRsync       *rsync)
{
  XdeltaPos opos, npos;
  XdeltaChecksum cksum;
  guint max_buffer_index = handle_length (file);
  GArray *request = g_array_new (FALSE, FALSE, sizeof (guint));
  const guint8* n_pointer, *o_pointer;
  guint thistime;
  guint prime, index;
  SerialRsyncIndexElt **table;
  guint i;
  guint matched = 0;
  guint16 old_c, new_c;

  if (max_buffer_index < rsync->seg_len)
    return request;

  max_buffer_index -= rsync->seg_len;

  if (! xdp_rsync_hash (rsync))
    return NULL;

  g_assert (rsync->seg_len < handle_pagesize (file));

  init_pos (file, &opos);
  init_pos (file, &npos);
  memset (&cksum, 0, sizeof (cksum));

  prime = rsync->table_size;
  table = rsync->table;

  if (!map_page (file, &opos))
    return NULL;

  init_long_checksum (opos.mem, rsync->seg_len, &cksum);

  npos.off += rsync->seg_len;

  for (; XPOS (opos) < max_buffer_index; )
    {
      if (!map_page (file, &opos))
      return FALSE;

      if (!map_page (file, &npos))
      return FALSE;

      if (matched == rsync->index_len)
      break;

      thistime = MIN (opos.mem_rem - opos.off,
                  npos.mem_rem - npos.off);

      o_pointer = opos.mem + opos.off;
      n_pointer = npos.mem + npos.off;

      for (; ; o_pointer += 1, n_pointer += 1)
      {
        index = c_hash (&cksum) % prime;

        if (table[index])
          {
            gboolean md5_computed = FALSE;
            gboolean found = FALSE;
            guint8 md5[16];
            SerialRsyncIndexElt* elt;

            for (elt = table[index]; elt; elt = elt->next)
            {
              if (elt->match_offset >= 0)
                continue;

              if (elt->cksum.high != cksum.high ||
                  elt->cksum.low  != cksum.low)
                continue;

              if (! md5_computed)
                {
                  EdsioMD5Ctx ctx;

                  edsio_md5_init (& ctx);

                  if (opos.page == npos.page)
                  edsio_md5_update (& ctx, opos.mem + opos.off, rsync->seg_len);
                  else
                  {
                    edsio_md5_update (& ctx, opos.mem + opos.off, opos.mem_rem - opos.off);
                    edsio_md5_update (& ctx, npos.mem, rsync->seg_len - (opos.mem_rem - opos.off));
                  }

                  edsio_md5_final (md5, & ctx);

                  md5_computed = TRUE;
                }

              if (memcmp (md5, elt->md5, 16) == 0)
                {
                  matched += 1;
                  found = TRUE;
                  elt->match_offset = XPOS (opos);
                }
            }

            if (found)
            {
              incr_by (&opos, rsync->seg_len);
              incr_by (&npos, rsync->seg_len);
              goto reenter;
            }
          }

        if (thistime == 0)
          goto nextpage;

        thistime -= 1;
        opos.off += 1;
        npos.off += 1;

        old_c = CHEW(*o_pointer);
        new_c = CHEW(*n_pointer);

        cksum.low -= old_c;
        cksum.low += new_c;

        cksum.high -= old_c * rsync->seg_len;
        cksum.high += cksum.low;
      }

    nextpage:

      FLIP_FORWARD (opos);
      FLIP_FORWARD (npos);

    reenter:
      (void) 0;
    }

  for (i = 0; i < rsync->index_len; i += 1)
    {
      SerialRsyncIndexElt* elt = rsync->index + i;

      if (elt->match_offset < 0)
      {
#ifdef DEBUG_RSYNC_REQUEST
        g_print ("request segment %d\n", i);
#endif
        g_array_append_val (request, i);
      }
    }

  return request;
}

gboolean
xdp_apply_rsync_reply (XdeltaRsync       *rsync,
                   XdeltaStream      *from,
                   XdeltaStream      *reply,
                   XdeltaStream      *out)
{
  gint i;
  guint reply_offset = 0;

  for (i = 0; i < rsync->index_len; i += 1)
    {
      SerialRsyncIndexElt* elt = rsync->index + i;

      if (elt->match_offset >= 0)
      {
        if (! handle_copy (from, out, elt->match_offset, rsync->seg_len))
          return FALSE;
      }
      else
      {
        if (! handle_copy (reply, out, reply_offset, rsync->seg_len))
          return FALSE;

        reply_offset += rsync->seg_len;
      }
    }

  if (! handle_copy (reply, out, reply_offset, rsync->file_len % rsync->seg_len))
    return FALSE;

  if (! handle_close (out, 0))
    return FALSE;

  if (! check_stream_integrity (out, rsync->file_md5, rsync->file_len))
    return FALSE;

  return TRUE;
}

Generated by  Doxygen 1.6.0   Back to index