/* -*- 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;
}