xdelta3.h

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

/* xdelta 3 - delta compression tools and library
 * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007.  Joshua P. 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

/* To know more about Xdelta, start by reading xdelta3.c.  If you are
 * ready to use the API, continue reading here.  There are two
 * interfaces -- xd3_encode_input and xd3_decode_input -- plus a dozen
 * or so related calls.  This interface is styled after Zlib. */

#ifndef _XDELTA3_H_
#define _XDELTA3_H_

#include <stdlib.h>
#include <string.h>
#include <sys/types.h>

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

/* Default configured value of stream->winsize.  If the program
 * supplies xd3_encode_input() with data smaller than winsize the
 * stream will automatically buffer the input, otherwise the input
 * buffer is used directly.
 */
#ifndef XD3_DEFAULT_WINSIZE
#define XD3_DEFAULT_WINSIZE (1U << 23)
#endif

/* Default total size of the source window used in xdelta3-main.h */
#ifndef XD3_DEFAULT_SRCWINSZ
#define XD3_DEFAULT_SRCWINSZ (1U << 26)
#endif

/* When Xdelta requests a memory allocation for certain buffers, it
 * rounds up to units of at least this size.  The code assumes (and
 * asserts) that this is a power-of-two. */
#ifndef XD3_ALLOCSIZE
#define XD3_ALLOCSIZE (1U<<14)
#endif

/* The XD3_HARDMAXWINSIZE parameter is a safety mechanism to protect
 * decoders against malicious files.  The decoder will never decode a
 * window larger than this.  If the file specifies VCD_TARGET the
 * decoder may require two buffers of this size.
 *
 * 8-16MB is reasonable, probably don't need to go larger. */
#ifndef XD3_HARDMAXWINSIZE
#define XD3_HARDMAXWINSIZE (1U<<24)
#endif
/* The IOPT_SIZE value sets the size of a buffer used to batch
 * overlapping copy instructions before they are optimized by picking
 * the best non-overlapping ranges.  The larger this buffer, the
 * longer a forced xd3_srcwin_setup() decision is held off.  Setting
 * this value to 0 causes an unlimited buffer to be used. */
#ifndef XD3_DEFAULT_IOPT_SIZE
#define XD3_DEFAULT_IOPT_SIZE    (1U<<15)
#endif

/* The maximum distance backward to search for small matches */
#ifndef XD3_DEFAULT_SPREVSZ
#define XD3_DEFAULT_SPREVSZ (1U<<18)
#endif

/* The default compression level
 */
#ifndef XD3_DEFAULT_LEVEL
#define XD3_DEFAULT_LEVEL 3
#endif

#ifndef XD3_DEFAULT_SECONDARY_LEVEL
#define XD3_DEFAULT_SECONDARY_LEVEL 6
#endif

#ifndef XD3_USE_LARGEFILE64
#define XD3_USE_LARGEFILE64 1
#endif

/* Sizes and addresses within VCDIFF windows are represented as usize_t
 *
 * For source-file offsets and total file sizes, total input and
 * output counts, the xoff_t type is used.  The decoder and encoder
 * generally check for overflow of the xoff_t size (this is tested at
 * the 32bit boundary [xdelta3-test.h]).
 */
#ifndef _WIN32
#include <stdint.h>
typedef unsigned int usize_t;
#else
#define WIN32_LEAN_AND_MEAN
#if XD3_USE_LARGEFILE64
/* 64 bit file offsets: uses GetFileSizeEx and SetFilePointerEx.
 * requires Win2000 or newer version of WinNT */
#define WINVER		0x0500
#define _WIN32_WINNT	0x0500
#else
/* 32 bit (DWORD) file offsets: uses GetFileSize and
 * SetFilePointer. compatible with win9x-me and WinNT4 */
#define WINVER		0x0400
#define _WIN32_WINNT	0x0400
#endif
#include <windows.h>
typedef unsigned int   usize_t;
#ifdef _MSC_VER
#define inline
typedef signed int     ssize_t;
typedef unsigned char  uint8_t;
typedef unsigned short uint16_t;
typedef unsigned long  uint32_t;
typedef ULONGLONG      uint64_t;
#else
/* mingw32, lcc and watcom provide a proper header */
#include <stdint.h>
#endif
#endif

/* TODO: note that SIZEOF_USIZE_T is never set to 8, although it should be for
 * a 64bit platform.  OTOH, may be that using 32bits is appropriate even on a
 * 64bit platform because we allocate large arrays of these values. */
#if XD3_USE_LARGEFILE64
#define __USE_FILE_OFFSET64 1 /* GLIBC: for 64bit fileops, ... ? */
typedef uint64_t xoff_t;
#define SIZEOF_XOFF_T 8
#define SIZEOF_USIZE_T 4
#ifndef WIN32
#define Q "ll"
#else
#define Q "I64"
#endif
#else
typedef uint32_t xoff_t;
#define SIZEOF_XOFF_T 4
#define SIZEOF_USIZE_T 4
#define Q
#endif

#define USE_UINT32 (SIZEOF_USIZE_T == 4 || \
		    SIZEOF_XOFF_T == 4 || REGRESSION_TEST)
#define USE_UINT64 (SIZEOF_USIZE_T == 8 || \
		    SIZEOF_XOFF_T == 8 || REGRESSION_TEST)

/* TODO: probably should do something better here. */
#ifndef UNALIGNED_OK
#if defined(__i386__) || defined(__i486__) || defined(__i586__) || \
  defined(__i686__) || defined(_X86_) || defined(__x86_64__)
#define UNALIGNED_OK 1
#else
#define UNALIGNED_OK 0
#endif
#endif

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

/* Whether to build the encoder, otherwise only build the decoder. */
#ifndef XD3_ENCODER
#define XD3_ENCODER 1
#endif

/* The code returned when main() fails, also defined in system
   includes. */
#ifndef EXIT_FAILURE
#define EXIT_FAILURE 1
#endif

/* REGRESSION TEST enables the "xdelta3 test" command, which runs a
   series of self-tests. */
#ifndef REGRESSION_TEST
#define REGRESSION_TEST 0
#endif

/* XD3_DEBUG=1 enables assertions and various statistics.  Levels > 1
 * enable some additional output only useful during development and
 * debugging. */
#ifndef XD3_DEBUG
#define XD3_DEBUG 0
#endif

#ifndef PYTHON_MODULE
#define PYTHON_MODULE 0
#endif

#ifndef SWIG_MODULE
#define SWIG_MODULE 0
#endif

/* There are three string matching functions supplied: one fast, one
 * slow (default), and one soft-configurable.  To disable any of
 * these, use the following definitions. */
#ifndef XD3_BUILD_SLOW
#define XD3_BUILD_SLOW 1
#endif
#ifndef XD3_BUILD_FAST
#define XD3_BUILD_FAST 1
#endif
#ifndef XD3_BUILD_FASTER
#define XD3_BUILD_FASTER 1
#endif
#ifndef XD3_BUILD_FASTEST
#define XD3_BUILD_FASTEST 1
#endif
#ifndef XD3_BUILD_SOFT
#define XD3_BUILD_SOFT 1
#endif
#ifndef XD3_BUILD_DEFAULT
#define XD3_BUILD_DEFAULT 1
#endif

#if XD3_DEBUG
#include <stdio.h>
#endif

/* XPRINT.  Debug output and VCDIFF_TOOLS functions report to stderr.
 * I have used an irregular style to abbreviate [fprintf(stderr, "] as
 * [DP(RINT "]. */
#define DP   fprintf
#define RINT stderr,

typedef struct _xd3_stream             xd3_stream;
typedef struct _xd3_source             xd3_source;
typedef struct _xd3_hash_cfg           xd3_hash_cfg;
typedef struct _xd3_smatcher           xd3_smatcher;
typedef struct _xd3_rinst              xd3_rinst;
typedef struct _xd3_dinst              xd3_dinst;
typedef struct _xd3_hinst              xd3_hinst;
typedef struct _xd3_winst              xd3_winst;
typedef struct _xd3_rpage              xd3_rpage;
typedef struct _xd3_addr_cache         xd3_addr_cache;
typedef struct _xd3_output             xd3_output;
typedef struct _xd3_desect             xd3_desect;
typedef struct _xd3_iopt_buflist       xd3_iopt_buflist;
typedef struct _xd3_rlist              xd3_rlist;
typedef struct _xd3_sec_type           xd3_sec_type;
typedef struct _xd3_sec_cfg            xd3_sec_cfg;
typedef struct _xd3_sec_stream         xd3_sec_stream;
typedef struct _xd3_config             xd3_config;
typedef struct _xd3_code_table_desc    xd3_code_table_desc;
typedef struct _xd3_code_table_sizes   xd3_code_table_sizes;
typedef struct _xd3_slist              xd3_slist;
typedef struct _xd3_whole_state        xd3_whole_state;
typedef struct _xd3_wininfo            xd3_wininfo;

/* The stream configuration has three callbacks functions, all of
 * which may be supplied with NULL values.  If config->getblk is
 * provided as NULL, the stream returns XD3_GETSRCBLK. */

typedef void*  (xd3_alloc_func)    (void       *opaque,
				    usize_t      items,
				    usize_t      size);
typedef void   (xd3_free_func)     (void       *opaque,
				    void       *address);

typedef int    (xd3_getblk_func)   (xd3_stream *stream,
				    xd3_source *source,
				    xoff_t      blkno);

/* These are internal functions to delay construction of encoding
 * tables and support alternate code tables.  See the comments & code
 * enabled by GENERIC_ENCODE_TABLES. */

typedef const xd3_dinst* (xd3_code_table_func) (void);
typedef int              (xd3_comp_table_func) (xd3_stream *stream,
						const uint8_t **data,
						usize_t *size);



#if XD3_DEBUG
#define XD3_ASSERT(x) \
    do { if (! (x)) { DP(RINT "%s:%d: XD3 assertion failed: %s\n", __FILE__, __LINE__, #x); \
    abort (); } } while (0)
#else
#define XD3_ASSERT(x) (void)0
#endif

#ifdef __GNUC__
/* As seen on linux-kernel. */
#ifndef max
#define max(x,y) ({ \
	const typeof(x) _x = (x);	\
	const typeof(y) _y = (y);	\
	(void) (&_x == &_y);		\
	_x > _y ? _x : _y; })
#endif

#ifndef min
#define min(x,y) ({ \
	const typeof(x) _x = (x);	\
	const typeof(y) _y = (y);	\
	(void) (&_x == &_y);		\
	_x < _y ? _x : _y; })
#endif
#else
#ifndef max
#define max(x,y) ((x) < (y) ? (y) : (x))
#endif
#ifndef min
#define min(x,y) ((x) < (y) ? (x) : (y))
#endif
#endif

/****************************************************************
 PUBLIC ENUMS
 ******************************************************************/

/* These are the five ordinary status codes returned by the
 * xd3_encode_input() and xd3_decode_input() state machines. */
typedef enum {

  /* An application must be prepared to handle these five return
   * values from either xd3_encode_input or xd3_decode_input, except
   * in the case of no-source compression, in which case XD3_GETSRCBLK
   * is never returned.  More detailed comments for these are given in
   * xd3_encode_input and xd3_decode_input comments, below. */
  XD3_INPUT     = -17703, /* need input */
  XD3_OUTPUT    = -17704, /* have output */
  XD3_GETSRCBLK = -17705, /* need a block of source input (with no
			   * xd3_getblk function), a chance to do
			   * non-blocking read. */
  XD3_GOTHEADER = -17706, /* (decode-only) after the initial VCDIFF &
			     first window header */
  XD3_WINSTART  = -17707, /* notification: returned before a window is
			   * processed, giving a chance to
			   * XD3_SKIP_WINDOW or not XD3_SKIP_EMIT that
			   * window. */
  XD3_WINFINISH  = -17708, /* notification: returned after
			      encode/decode & output for a window */
  XD3_TOOFARBACK = -17709, /* (encoder only) may be returned by
			      getblk() if the block is too old */
  XD3_INTERNAL   = -17710, /* internal error */
  XD3_INVALID    = -17711, /* invalid config */
  XD3_INVALID_INPUT = -17712, /* invalid input/decoder error */
  XD3_NOSECOND  = -17713, /* when secondary compression finds no
			     improvement. */

} xd3_rvalues;

/* special values in config->flags */
typedef enum
{
  XD3_JUST_HDR       = (1 << 1),   /* used by VCDIFF tools, see
				      xdelta3-main.h. */
  XD3_SKIP_WINDOW    = (1 << 2),   /* used by VCDIFF tools, see
				      xdelta3-main.h. */
  XD3_SKIP_EMIT      = (1 << 3),   /* used by VCDIFF tools, see
				      xdelta3-main.h. */
  XD3_FLUSH          = (1 << 4),   /* flush the stream buffer to
				      prepare for
				      xd3_stream_close(). */

  XD3_SEC_DJW        = (1 << 5),   /* use DJW static huffman */
  XD3_SEC_FGK        = (1 << 6),   /* use FGK adaptive huffman */
  XD3_SEC_TYPE       = (XD3_SEC_DJW | XD3_SEC_FGK),

  XD3_SEC_NODATA     = (1 << 7),   /* disable secondary compression of
				      the data section. */
  XD3_SEC_NOINST     = (1 << 8),   /* disable secondary compression of
				      the inst section. */
  XD3_SEC_NOADDR     = (1 << 9),   /* disable secondary compression of
				      the addr section. */

  XD3_SEC_NOALL      = (XD3_SEC_NODATA | XD3_SEC_NOINST | XD3_SEC_NOADDR),

  XD3_ADLER32        = (1 << 10),  /* enable checksum computation in
				      the encoder. */
  XD3_ADLER32_NOVER  = (1 << 11),  /* disable checksum verification in
				      the decoder. */

  XD3_ALT_CODE_TABLE = (1 << 12),  /* for testing th
				      e alternate code table encoding. */

  XD3_NOCOMPRESS     = (1 << 13),  /* disable ordinary data
				    * compression feature, only search
				    * the source, not the target. */
  XD3_BEGREEDY       = (1 << 14),  /* disable the "1.5-pass
				    * algorithm", instead use greedy
				    * matching.  Greedy is off by
				    * default. */
  XD3_ADLER32_RECODE = (1 << 15),  /* used by "recode". */

  /* 4 bits to set the compression level the same as the command-line
   * setting -1 through -9 (-0 corresponds to the XD3_NOCOMPRESS flag,
   * and is independent of compression level).  This is for
   * convenience, especially with xd3_encode_memory(). */

  XD3_COMPLEVEL_SHIFT = 20,  /* 20 - 24 */
  XD3_COMPLEVEL_MASK = (0xF << XD3_COMPLEVEL_SHIFT),
  XD3_COMPLEVEL_1 = (1 << XD3_COMPLEVEL_SHIFT),
  XD3_COMPLEVEL_2 = (2 << XD3_COMPLEVEL_SHIFT),
  XD3_COMPLEVEL_3 = (3 << XD3_COMPLEVEL_SHIFT),
  XD3_COMPLEVEL_6 = (6 << XD3_COMPLEVEL_SHIFT),
  XD3_COMPLEVEL_9 = (9 << XD3_COMPLEVEL_SHIFT),

} xd3_flags;

/* The values of this enumeration are set in xd3_config using the
 * smatch_cfg variable.  It can be set to default, slow, fast, etc.,
 * and soft. */
typedef enum
{
  XD3_SMATCH_DEFAULT = 0, /* Flags may contain XD3_COMPLEVEL bits,
			     else default. */
  XD3_SMATCH_SLOW    = 1,
  XD3_SMATCH_FAST    = 2,
  XD3_SMATCH_FASTER  = 3,
  XD3_SMATCH_FASTEST = 4,
  XD3_SMATCH_SOFT    = 5,
} xd3_smatch_cfg;

/*********************************************************************
 PRIVATE ENUMS
**********************************************************************/

/* stream->match_state is part of the xd3_encode_input state machine
 *  for source matching:
 *
 *  1. the XD3_GETSRCBLK block-read mechanism means reentrant matching
 *  2. this state spans encoder windows: a match and end-of-window
 *  will continue in the next 3. the initial target byte and source
 *  byte are a presumed match, to avoid some computation in case the
 *  inputs are identical.
 */
typedef enum {

  MATCH_TARGET    = 0, /* in this state, attempt to match the start of
			* the target with the previously set source