svndiff.c

subversion-1.4.3-1.tar.gz 配置svn的源码

/* 
 * svndiff.c -- Encoding and decoding svndiff-format deltas.
 * 
 * ====================================================================
 * Copyright (c) 2000-2006 CollabNet.  All rights reserved.
 *
 * This software is licensed as described in the file COPYING, which
 * you should have received as part of this distribution.  The terms
 * are also available at http://subversion.tigris.org/license-1.html.
 * If newer versions of this license are posted there, you may use a
 * newer version instead, at your option.
 *
 * This software consists of voluntary contributions made by many
 * individuals.  For exact contribution history, see the revision
 * history and logs, available at http://subversion.tigris.org/.
 * ====================================================================
 */


#include <assert.h>
#include <string.h>
#include "svn_delta.h"
#include "svn_io.h"
#include "delta.h"
#include "svn_pools.h"
#include "svn_private_config.h"
#include <zlib.h>

/* This macro is taken from zlib, and was originally the function
   compressBound.  It shouldn't ever change, but once every millenium,
   it may be useful for someone to make sure. */
#define svnCompressBound(LEN) ((LEN) + ((LEN) >> 12) + ((LEN) >> 14) + 11)

/* For svndiff1, address/instruction/new data under this size will not
   be compressed using zlib as a secondary compressor.  */
#define MIN_COMPRESS_SIZE 512

/* For svndiff, this is the compression level we pass to zlib.  It
   should be between 0 and 9, with higher numbers being greater
   compression.  */
#define SVNDIFF1_COMPRESS_LEVEL 5
#define NORMAL_BITS 7
#define LENGTH_BITS 5


/* ----- Text delta to svndiff ----- */

/* We make one of these and get it passed back to us in calls to the
   window handler.  We only use it to record the write function and
   baton passed to svn_txdelta_to_svndiff ().  */
struct encoder_baton {
  svn_stream_t *output;
  svn_boolean_t header_done;
  int version;
  apr_pool_t *pool;
};


/* Encode VAL into the buffer P using the variable-length svndiff
   integer format.  Return the incremented value of P after the
   encoded bytes have been written.

   This encoding uses the high bit of each byte as a continuation bit
   and the other seven bits as data bits.  High-order data bits are
   encoded first, followed by lower-order bits, so the value can be
   reconstructed by concatenating the data bits from left to right and
   interpreting the result as a binary number.  Examples (brackets
   denote byte boundaries, spaces are for clarity only):

           1 encodes as [0 0000001]
          33 encodes as [0 0100001]
         129 encodes as [1 0000001] [0 0000001]
        2000 encodes as [1 0001111] [0 1010000]
*/

static char *
encode_int(char *p, svn_filesize_t val)
{
  int n;
  svn_filesize_t v;
  unsigned char cont;

  assert(val >= 0);

  /* Figure out how many bytes we'll need.  */
  v = val >> 7;
  n = 1;
  while (v > 0)
    {
      v = v >> 7;
      n++;
    }

  /* Encode the remaining bytes; n is always the number of bytes
     coming after the one we're encoding.  */
  while (--n >= 0)
    {
      cont = ((n > 0) ? 0x1 : 0x0) << 7;
      *p++ = (char)(((val >> (n * 7)) & 0x7f) | cont);
    }

  return p;
}


/* Append an encoded integer to a string.  */
static void
append_encoded_int(svn_stringbuf_t *header, svn_filesize_t val)
{
  char buf[128], *p;

  p = encode_int(buf, val);
  svn_stringbuf_appendbytes(header, buf, p - buf);
}

/* If IN is a string that is >= MIN_COMPRESS_SIZE, zlib compress it and
   place the result in OUT, with an integer prepended specifying the
   original size.  If IN is < MIN_COMPRESS_SIZE, or if the compressed
   version of IN was no smaller than the original IN, OUT will be a copy
   of IN with the size prepended as an integer. */
static svn_error_t *
zlib_encode(const char *data, apr_size_t len, svn_stringbuf_t *out)
{
  unsigned long endlen;
  unsigned int intlen;
  
  append_encoded_int(out, len);
  intlen = out->len;
  
  if (len < MIN_COMPRESS_SIZE)
    {
      svn_stringbuf_appendbytes(out, data, len);
    }
  else
    {
      svn_stringbuf_ensure(out, svnCompressBound(len) + intlen);
      endlen = out->blocksize;    
      
      if (compress2((unsigned char *)out->data + intlen, &endlen, 
                    (const unsigned char *)data, len,
                    SVNDIFF1_COMPRESS_LEVEL) != Z_OK)        
        return svn_error_create(SVN_ERR_SVNDIFF_INVALID_COMPRESSED_DATA, 
                                NULL,
                                _("Compression of svndiff data failed"));

      /* Compression didn't help :(, just append the original text */
      if (endlen >= len)
        {
          svn_stringbuf_appendbytes(out, data, len);
          return SVN_NO_ERROR;
        }
      out->len = endlen + intlen;
    }
  return SVN_NO_ERROR;
}

static svn_error_t *
window_handler(svn_txdelta_window_t *window, void *baton)
{
  struct encoder_baton *eb = baton;
  apr_pool_t *pool = svn_pool_create(eb->pool);
  svn_stringbuf_t *instructions = svn_stringbuf_create("", pool);
  svn_stringbuf_t *i1 = svn_stringbuf_create("", pool);
  svn_stringbuf_t *header = svn_stringbuf_create("", pool);
  const svn_string_t *newdata;
  char ibuf[128], *ip;
  const svn_txdelta_op_t *op;
  apr_size_t len;

  /* Make sure we write the header.  */
  if (eb->header_done == FALSE)
    {
      char svnver[4] = "SVN\0";
      len = 4;
      svnver[3] = eb->version;
      SVN_ERR(svn_stream_write(eb->output, svnver, &len));
      eb->header_done = TRUE;
    }

  if (window == NULL)
    {
      svn_stream_t *output = eb->output;

      /* We're done; clean up.

         We clean our pool first. Given that the output stream was passed
         TO us, we'll assume it has a longer lifetime, and that it will not
         be affected by our pool destruction.

         The contrary point of view (close the stream first): that could
         tell our user that everything related to the output stream is done,
         and a cleanup of the user pool should occur. However, that user
         pool could include the subpool we created for our work (eb->pool),
         which would then make our call to svn_pool_destroy() puke.
       */
      svn_pool_destroy(eb->pool);

      return svn_stream_close(output);
    }

  /* Encode the instructions.  */
  for (op = window->ops; op < window->ops + window->num_ops; op++)
    {
      /* Encode the action code and length.  */
      ip = ibuf;
      switch (op->action_code)
        {
        case svn_txdelta_source: *ip = (char)0; break;
        case svn_txdelta_target: *ip = (char)(0x1 << 6); break;
        case svn_txdelta_new:    *ip = (char)(0x2 << 6); break;
        }
      if (op->length >> 6 == 0)
        *ip++ |= op->length;
      else
        ip = encode_int(ip + 1, op->length);
      if (op->action_code != svn_txdelta_new)
        ip = encode_int(ip, op->offset);
      svn_stringbuf_appendbytes(instructions, ibuf, ip - ibuf);
    }

  /* Encode the header.  */
  append_encoded_int(header, window->sview_offset);
  append_encoded_int(header, window->sview_len);
  append_encoded_int(header, window->tview_len);
  if (eb->version == 1)
    {
      SVN_ERR(zlib_encode(instructions->data, instructions->len, i1));
      instructions = i1;
    }
  append_encoded_int(header, instructions->len);
  if (eb->version == 1)
    {
      svn_stringbuf_t *temp = svn_stringbuf_create("", pool);
      svn_string_t *tempstr = svn_string_create("", pool);
      SVN_ERR(zlib_encode(window->new_data->data, window->new_data->len,
                          temp));
      tempstr->data = temp->data;
      tempstr->len = temp->len;
      newdata = tempstr;
    }
  else
    newdata = window->new_data;

  append_encoded_int(header, newdata->len);

  /* Write out the window.  */
  len = header->len;
  SVN_ERR(svn_stream_write(eb->output, header->data, &len));
  if (instructions->len > 0)
    {
      len = instructions->len;
      SVN_ERR(svn_stream_write(eb->output, instructions->data, &len));
    }
  if (newdata->len > 0)
    {
      len = newdata->len;
      SVN_ERR(svn_stream_write(eb->output, newdata->data, &len));
    }

  svn_pool_destroy(pool);
  return SVN_NO_ERROR;
}

void
svn_txdelta_to_svndiff2(svn_txdelta_window_handler_t *handler,
                        void **handler_baton,
                        svn_stream_t *output,
                        int svndiff_version,
                        apr_pool_t *pool)
{
  apr_pool_t *subpool = svn_pool_create(pool);
  struct encoder_baton *eb;

  eb = apr_palloc(subpool, sizeof(*eb));
  eb->output = output;
  eb->header_done = FALSE;
  eb->pool = subpool;
  eb->version = svndiff_version;
  
  *handler = window_handler;
  *handler_baton = eb;
}

void
svn_txdelta_to_svndiff(svn_stream_t *output,
                       apr_pool_t *pool,
                       svn_txdelta_window_handler_t *handler,
                       void **handler_baton)
{
  svn_txdelta_to_svndiff2(handler, handler_baton, output, 0, pool);
}


/* ----- svndiff to text delta ----- */

/* An svndiff parser object.  */
struct decode_baton
{
  /* Once the svndiff parser has enough data buffered to create a
     "window", it passes this window to the caller's consumer routine.  */
  svn_txdelta_window_handler_t consumer_func;
  void *consumer_baton;

  /* Pool to create subpools from; each developing window will be a
     subpool.  */
  apr_pool_t *pool;

  /* The current subpool which contains our current window-buffer.  */
  apr_pool_t *subpool;

  /* The actual svndiff data buffer, living within subpool.  */
  svn_stringbuf_t *buffer;

  /* The offset and size of the last source view, so that we can check
     to make sure the next one isn't sliding backwards.  */
  svn_filesize_t last_sview_offset;
  apr_size_t last_sview_len;

  /* We have to discard four bytes at the beginning for the header.
     This field keeps track of how many of those bytes we have read.  */
  int header_bytes;

  /* Do we want an error to occur when we close the stream that
     indicates we didn't send the whole svndiff data?  If you plan to
     not transmit the whole svndiff data stream, you will want this to
     be FALSE. */
  svn_boolean_t error_on_early_close;
  
  /* svndiff version in use by delta.  */
  unsigned char version;
};


/* Decode an svndiff-encoded integer into VAL and return a pointer to
   the byte after the integer.  The bytes to be decoded live in the
   range [P..END-1].  See the comment for encode_int earlier in this
   file for more detail on the encoding format.  */

static const unsigned char *
decode_file_offset(svn_filesize_t *val,
                   const unsigned char *p,
                   const unsigned char *end)
{
  /* Decode bytes until we're done.  */
  *val = 0;
  while (p < end)
    {
      *val = (*val << 7) | (*p & 0x7f);
      if (((*p++ >> 7) & 0x1) == 0)
        return p;
    }
  return NULL;
}


/* Same as above, only decide into a size variable. */

static const unsigned char *
decode_size(apr_size_t *val,
            const unsigned char *p,
            const unsigned char *end)
{
  /* Decode bytes until we're done.  */
  *val = 0;
  while (p < end)
    {
      *val = (*val << 7) | (*p & 0x7f);
      if (((*p++ >> 7) & 0x1) == 0)
        return p;
    }
  return NULL;
}

/* Decode the possibly-zlib compressed string that is in IN, into OUT.
   We expect an integer is prepended to IN that specifies the original
   size, and that if encoded size == original size, that the remaining
   data is not compressed.  */

static svn_error_t *
zlib_decode(svn_stringbuf_t *in, svn_stringbuf_t *out)
{
  apr_size_t len;
  char *oldplace = in->data;

  /* First thing in the string is the original length.  */
  in->data = (char *)decode_size(&len, (unsigned char *)in->data, 
                                 (unsigned char *)in->data+in->len);  
  /* We need to subtract the size of the encoded original length off the
   *      still remaining input length.  */
  in->len -= (in->data - oldplace);
  if (in->len == len)
    {
      svn_stringbuf_appendstr(out, in);
      return SVN_NO_ERROR;
    }
  else
    {
      unsigned long zliblen;

      svn_stringbuf_ensure(out, len);
      
      zliblen = len;
      if (uncompress  ((unsigned char *)out->data, &zliblen, 
                       (const unsigned char *)in->data, in->len) != Z_OK)
        return svn_error_create(SVN_ERR_SVNDIFF_INVALID_COMPRESSED_DATA, 
                                NULL,
                                _("Decompression of svndiff data failed"));
      
      /* Zlib should not produce something that has a different size than the
         original length we stored. */
      if (zliblen != len)
        return svn_error_create(SVN_ERR_SVNDIFF_INVALID_COMPRESSED_DATA, 
                                NULL,
                                _("Size of uncompressed data "
                                  "does not match stored original length"));
      out->len = zliblen;
    }
  return SVN_NO_ERROR;  
}

/* Decode an instruction into OP, returning a pointer to the text
   after the instruction.  Note that if the action code is
   svn_txdelta_new, the offset field of *OP will not be set.  */

static const unsigned char *
decode_instruction(svn_txdelta_op_t *op,
                   const unsigned char *p,
                   const unsigned char *end)
{
  if (p == end)
    return NULL;

  /* Decode the instruction selector.  */
  switch ((*p >> 6) & 0x3)
    {
    case 0x0: op->action_code = svn_txdelta_source; break;
    case 0x1: op->action_code = svn_txdelta_target; break;
    case 0x2: op->action_code = svn_txdelta_new; break;
    case 0x3: return NULL;
    }

  /* Decode the length and offset.  */
  op->length = *p++ & 0x3f;
  if (op->length == 0)
    {
      p = decode_size(&op->length, p, end);