xdelta3.c

Linux下一个可以比较二进制文件的工具xdelta3.0u的源码。

#define MIN_SMALL_LOOK    2U    /* Match-optimization stuff. */
#define MIN_LARGE_LOOK    2U
#define MIN_MATCH_OFFSET  1U
#define MAX_MATCH_SPLIT   18U   /* VCDIFF code table: 18 is the default limit
				 * for direct-coded ADD sizes */

#define LEAST_MATCH_INCR  0   /* The least number of bytes an overlapping
			       * match must beat the preceding match by.  This
			       * is a bias for the lazy match optimization.  A
			       * non-zero value means that an adjacent match
			       * has to be better by more than the step
			       * between them.  0. */

#define MIN_MATCH         4U  /* VCDIFF code table: MIN_MATCH=4 */
#define MIN_ADD           1U  /* 1 */
#define MIN_RUN           8U  /* The shortest run, if it is shorter than this
			       * an immediate add/copy will be just as good.
			       * ADD1/COPY6 = 1I+1D+1A bytes, RUN18 =
			       * 1I+1D+1A. */

#define MAX_MODES         9  /* Maximum number of nodes used for
			      * compression--does not limit decompression. */

#define ENC_SECTS         4  /* Number of separate output sections. */

#define HDR_TAIL(s)  ((s)->enc_tails[0])
#define DATA_TAIL(s) ((s)->enc_tails[1])
#define INST_TAIL(s) ((s)->enc_tails[2])
#define ADDR_TAIL(s) ((s)->enc_tails[3])

#define HDR_HEAD(s)  ((s)->enc_heads[0])
#define DATA_HEAD(s) ((s)->enc_heads[1])
#define INST_HEAD(s) ((s)->enc_heads[2])
#define ADDR_HEAD(s) ((s)->enc_heads[3])

#define SIZEOF_ARRAY(x) (sizeof(x) / sizeof(x[0]))

#define TOTAL_MODES(x) (2+(x)->acache.s_same+(x)->acache.s_near)

/* Template instances. */
#if XD3_BUILD_SLOW
#define IF_BUILD_SLOW(x) x
#else
#define IF_BUILD_SLOW(x)
#endif
#if XD3_BUILD_FAST
#define IF_BUILD_FAST(x) x
#else
#define IF_BUILD_FAST(x)
#endif
#if XD3_BUILD_FASTER
#define IF_BUILD_FASTER(x) x
#else
#define IF_BUILD_FASTER(x)
#endif
#if XD3_BUILD_FASTEST
#define IF_BUILD_FASTEST(x) x
#else
#define IF_BUILD_FASTEST(x)
#endif
#if XD3_BUILD_SOFT
#define IF_BUILD_SOFT(x) x
#else
#define IF_BUILD_SOFT(x)
#endif
#if XD3_BUILD_DEFAULT
#define IF_BUILD_DEFAULT(x) x
#else
#define IF_BUILD_DEFAULT(x)
#endif

/* Consume N bytes of input, only used by the decoder. */
#define DECODE_INPUT(n)             \
  do {                              \
  stream->total_in += (xoff_t) (n); \
  stream->avail_in -= (n);          \
  stream->next_in  += (n);          \
  } while (0)

/* Update the run-length state */
#define NEXTRUN(c) do { if ((c) == run_c) { run_l += 1; } \
  else { run_c = (c); run_l = 1; } } while (0)

/* This CPP-conditional stuff can be cleaned up... */
#if XD3_DEBUG
#define IF_DEBUG(x) x
#else
#define IF_DEBUG(x)
#endif
#if XD3_DEBUG > 1
#define IF_DEBUG1(x) x
#else
#define IF_DEBUG1(x)
#endif
#if XD3_DEBUG > 2
#define IF_DEBUG2(x) x
#else
#define IF_DEBUG2(x)
#endif
#if REGRESSION_TEST
#define IF_REGRESSION(x) x
#else
#define IF_REGRESSION(x)
#endif

/***********************************************************************/

#if XD3_ENCODER
static void*       xd3_alloc0 (xd3_stream *stream,
			       usize_t      elts,
			       usize_t      size);


static xd3_output* xd3_alloc_output (xd3_stream *stream,
				     xd3_output *old_output);

static int         xd3_alloc_iopt (xd3_stream *stream, int elts);

static void        xd3_free_output (xd3_stream *stream,
				    xd3_output *output);

static int         xd3_emit_byte (xd3_stream  *stream,
				  xd3_output **outputp,
				  uint8_t      code);

static int         xd3_emit_bytes (xd3_stream     *stream,
				   xd3_output    **outputp,
				   const uint8_t  *base,
				   usize_t          size);

static int         xd3_emit_double (xd3_stream *stream, xd3_rinst *first,
				    xd3_rinst *second, usize_t code);
static int         xd3_emit_single (xd3_stream *stream, xd3_rinst *single,
				    usize_t code);

static usize_t      xd3_sizeof_output (xd3_output *output);
static void        xd3_encode_reset (xd3_stream *stream);

static int         xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos);
static int         xd3_source_extend_match (xd3_stream *stream);
static int         xd3_srcwin_setup (xd3_stream *stream);
static usize_t     xd3_iopt_last_matched (xd3_stream *stream);
static int         xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output,
				      uint32_t num);

static usize_t xd3_smatch (xd3_stream *stream,
			   usize_t base,
			   usize_t scksum,
			   usize_t *match_offset);
static int xd3_string_match_init (xd3_stream *stream);
static uint32_t xd3_scksum (uint32_t *state, const uint8_t *seg, const int ln);
static int xd3_comprun (const uint8_t *seg, int slook, uint8_t *run_cp);
static int xd3_srcwin_move_point (xd3_stream *stream,
				  usize_t *next_move_point);

static int xd3_emit_run (xd3_stream *stream, usize_t pos,
			 usize_t size, uint8_t run_c);
static usize_t xd3_checksum_hash (const xd3_hash_cfg *cfg,
				  const usize_t cksum);
static xoff_t xd3_source_cksum_offset(xd3_stream *stream, usize_t low);
static void xd3_scksum_insert (xd3_stream *stream,
			       usize_t inx,
			       usize_t scksum,
			       usize_t pos);


#if XD3_DEBUG
static void xd3_verify_run_state (xd3_stream    *stream,
				  const uint8_t *inp,
				  int            x_run_l,
				  uint8_t        x_run_c);
static void xd3_verify_large_state (xd3_stream *stream,
				    const uint8_t *inp,
				    uint32_t x_cksum);
static void xd3_verify_small_state (xd3_stream    *stream,
				    const uint8_t *inp,
				    uint32_t          x_cksum);

#endif /* XD3_DEBUG */
#endif /* XD3_ENCODER */

static int         xd3_decode_allocate (xd3_stream *stream, usize_t size,
					uint8_t **copied1, usize_t *alloc1);

static void        xd3_compute_code_table_string (const xd3_dinst *code_table,
						  uint8_t *str);
static void*       xd3_alloc (xd3_stream *stream, usize_t elts, usize_t size);
static void        xd3_free  (xd3_stream *stream, void *ptr);

static int         xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp,
				      const uint8_t *max, uint32_t *valp);

#if REGRESSION_TEST
static int         xd3_selftest      (void);
#endif

/***********************************************************************/

#define UINT32_OFLOW_MASK 0xfe000000U
#define UINT64_OFLOW_MASK 0xfe00000000000000ULL

#ifndef UINT32_MAX
#define UINT32_MAX 4294967295U
#endif

#ifndef UINT64_MAX
#define UINT64_MAX 18446744073709551615ULL
#endif

#if SIZEOF_USIZE_T == 4
#define USIZE_T_MAX        UINT32_MAX
#define xd3_decode_size   xd3_decode_uint32_t
#define xd3_emit_size     xd3_emit_uint32_t
#define xd3_sizeof_size   xd3_sizeof_uint32_t
#define xd3_read_size     xd3_read_uint32_t
#elif SIZEOF_USIZE_T == 8
#define USIZE_T_MAX        UINT64_MAX
#define xd3_decode_size   xd3_decode_uint64_t
#define xd3_emit_size     xd3_emit_uint64_t
#define xd3_sizeof_size   xd3_sizeof_uint64_t
#define xd3_read_size     xd3_read_uint64_t
#endif

#if SIZEOF_XOFF_T == 4
#define XOFF_T_MAX        UINT32_MAX
#define xd3_decode_offset xd3_decode_uint32_t
#define xd3_emit_offset   xd3_emit_uint32_t
#elif SIZEOF_XOFF_T == 8
#define XOFF_T_MAX        UINT64_MAX
#define xd3_decode_offset xd3_decode_uint64_t
#define xd3_emit_offset   xd3_emit_uint64_t
#endif

#define USIZE_T_OVERFLOW(a,b) ((USIZE_T_MAX - (usize_t) (a)) < (usize_t) (b))
#define XOFF_T_OVERFLOW(a,b) ((XOFF_T_MAX - (xoff_t) (a)) < (xoff_t) (b))

const char* xd3_strerror (int ret)
{
  switch (ret)
    {
    case XD3_INPUT: return "XD3_INPUT";
    case XD3_OUTPUT: return "XD3_OUTPUT";
    case XD3_GETSRCBLK: return "XD3_GETSRCBLK";
    case XD3_GOTHEADER: return "XD3_GOTHEADER";
    case XD3_WINSTART: return "XD3_WINSTART";
    case XD3_WINFINISH: return "XD3_WINFINISH";
    case XD3_TOOFARBACK: return "XD3_TOOFARBACK";
    case XD3_INTERNAL: return "XD3_INTERNAL";
    case XD3_INVALID_INPUT: return "XD3_INVALID_INPUT";
    }
  return NULL;
}

/***********************************************************************/

#define xd3_sec_data(s) ((s)->sec_stream_d)
#define xd3_sec_inst(s) ((s)->sec_stream_i)
#define xd3_sec_addr(s) ((s)->sec_stream_a)

struct _xd3_sec_type
{
  int         id;
  const char *name;
  xd3_secondary_flags flags;

  /* xd3_sec_stream is opaque to the generic code */
  xd3_sec_stream* (*alloc)   (xd3_stream     *stream);
  void            (*destroy) (xd3_stream     *stream,
			      xd3_sec_stream *sec);
  void            (*init)    (xd3_sec_stream *sec);
  int             (*decode)  (xd3_stream     *stream,
			      xd3_sec_stream *sec_stream,
			      const uint8_t **input,
			      const uint8_t  *input_end,
			      uint8_t       **output,
			      const uint8_t  *output_end);
#if XD3_ENCODER
  int             (*encode)  (xd3_stream     *stream,
			      xd3_sec_stream *sec_stream,
			      xd3_output     *input,
			      xd3_output     *output,
			      xd3_sec_cfg    *cfg);
#endif
};

#define BIT_STATE_ENCODE_INIT { 0, 1 }
#define BIT_STATE_DECODE_INIT { 0, 0x100 }

typedef struct _bit_state bit_state;
struct _bit_state
{
  usize_t cur_byte;
  usize_t cur_mask;
};

#if SECONDARY_ANY == 0
#define IF_SEC(x)
#define IF_NSEC(x) x
#else /* yuck */
#define IF_SEC(x) x
#define IF_NSEC(x)
static int
xd3_decode_secondary (xd3_stream      *stream,
		      xd3_desect      *sect,
		      xd3_sec_stream **sec_streamp);
#if XD3_ENCODER
static int
xd3_encode_secondary (xd3_stream      *stream,
		      xd3_output     **head,
		      xd3_output     **tail,
		      xd3_sec_stream **sec_streamp,
		      xd3_sec_cfg     *cfg,
		      int             *did_it);
#endif
#endif /* SECONDARY_ANY */

#if SECONDARY_FGK
static const xd3_sec_type fgk_sec_type;
#define IF_FGK(x) x
#define FGK_CASE(s) \
  s->sec_type = & fgk_sec_type; \
  break;
#else
#define IF_FGK(x)
#define FGK_CASE(s) \
  s->msg = "unavailable secondary compressor: FGK Adaptive Huffman"; \
  return XD3_INTERNAL;
#endif

#if SECONDARY_DJW
static const xd3_sec_type djw_sec_type;
#define IF_DJW(x) x
#define DJW_CASE(s) \
  s->sec_type = & djw_sec_type; \
  break;
#else
#define IF_DJW(x)
#define DJW_CASE(s) \
  s->msg = "unavailable secondary compressor: DJW Static Huffman"; \
  return XD3_INTERNAL;
#endif

/***********************************************************************/

#include "xdelta3-hash.h"

/* Process template passes - this includes xdelta3.c several times. */
#define __XDELTA3_C_TEMPLATE_PASS__
#include "xdelta3-cfgs.h"
#undef __XDELTA3_C_TEMPLATE_PASS__

/* Process the inline pass. */
#define __XDELTA3_C_INLINE_PASS__
#include "xdelta3.c"
#undef __XDELTA3_C_INLINE_PASS__

/* Secondary compression */
#if SECONDARY_ANY
#include "xdelta3-second.h"
#endif

#if SECONDARY_FGK
#include "xdelta3-fgk.h"
static const xd3_sec_type fgk_sec_type =
{
  VCD_FGK_ID,
  "FGK Adaptive Huffman",
  SEC_NOFLAGS,
  (xd3_sec_stream* (*)())  fgk_alloc,
  (void (*)())             fgk_destroy,
  (void (*)())             fgk_init,
  (int (*)())              xd3_decode_fgk,
  IF_ENCODER((int (*)())   xd3_encode_fgk)
};
#endif

#if SECONDARY_DJW
#include "xdelta3-djw.h"
static const xd3_sec_type djw_sec_type =
{
  VCD_DJW_ID,
  "Static Huffman",
  SEC_COUNT_FREQS,
  (xd3_sec_stream* (*)())  djw_alloc,
  (void (*)())             djw_destroy,
  (void (*)())             djw_init,
  (int (*)())              xd3_decode_huff,
  IF_ENCODER((int (*)())   xd3_encode_huff)
};
#endif

#if XD3_MAIN || PYTHON_MODULE || SWIG_MODULE || NOT_MAIN
#include "xdelta3-main.h"
#endif