"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/xdelta3.h" (8 Jan 2016, 48998 Bytes) of package /linux/misc/xdelta3-3.1.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "xdelta3.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.0.11_vs_3.1.0.

    1 /* xdelta 3 - delta compression tools and library
    2  * Copyright (C) Joshua P. MacDonald
    3  *
    4  *  This program is free software; you can redistribute it and/or modify
    5  *  it under the terms of the GNU General Public License as published by
    6  *  the Free Software Foundation; either version 2 of the License, or
    7  *  (at your option) any later version.
    8  *
    9  *  This program is distributed in the hope that it will be useful,
   10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   12  *  GNU General Public License for more details.
   13  *
   14  *  You should have received a copy of the GNU General Public License
   15  *  along with this program; if not, write to the Free Software
   16  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   17  */
   18 
   19 /* To learn more about Xdelta, start by reading xdelta3.c.  If you are
   20  * ready to use the API, continue reading here.  There are two
   21  * interfaces -- xd3_encode_input and xd3_decode_input -- plus a dozen
   22  * or so related calls.  This interface is styled after Zlib. */
   23 
   24 #ifndef _XDELTA3_H_
   25 #define _XDELTA3_H_
   26 
   27 #define _POSIX_SOURCE 200112L
   28 #define _ISOC99_SOURCE
   29 #define _C99_SOURCE
   30 
   31 #if HAVE_CONFIG_H
   32 #include "config.h"
   33 #endif
   34 
   35 #include <errno.h>
   36 #include <stdarg.h>
   37 #include <stddef.h>
   38 #include <stdio.h>
   39 #include <stdlib.h>
   40 #include <string.h>
   41 #include <sys/types.h>
   42 
   43 /****************************************************************/
   44 
   45 /* Default configured value of stream->winsize.  If the program
   46  * supplies xd3_encode_input() with data smaller than winsize the
   47  * stream will automatically buffer the input, otherwise the input
   48  * buffer is used directly.
   49  */
   50 #ifndef XD3_DEFAULT_WINSIZE
   51 #define XD3_DEFAULT_WINSIZE (1U << 23)
   52 #endif
   53 
   54 /* Default total size of the source window used in xdelta3-main.h */
   55 #ifndef XD3_DEFAULT_SRCWINSZ
   56 #define XD3_DEFAULT_SRCWINSZ (1U << 26)
   57 #endif
   58 
   59 /* When Xdelta requests a memory allocation for certain buffers, it
   60  * rounds up to units of at least this size.  The code assumes (and
   61  * asserts) that this is a power-of-two. */
   62 #ifndef XD3_ALLOCSIZE
   63 #define XD3_ALLOCSIZE (1U<<14)
   64 #endif
   65 
   66 /* The XD3_HARDMAXWINSIZE parameter is a safety mechanism to protect
   67  * decoders against malicious files.  The decoder will never decode a
   68  * window larger than this.  If the file specifies VCD_TARGET the
   69  * decoder may require two buffers of this size.
   70  *
   71  * 8-16MB is reasonable, probably don't need to go larger. */
   72 #ifndef XD3_HARDMAXWINSIZE
   73 #define XD3_HARDMAXWINSIZE (1U<<26)
   74 #endif
   75 /* The IOPT_SIZE value sets the size of a buffer used to batch
   76  * overlapping copy instructions before they are optimized by picking
   77  * the best non-overlapping ranges.  The larger this buffer, the
   78  * longer a forced xd3_srcwin_setup() decision is held off.  Setting
   79  * this value to 0 causes an unlimited buffer to be used. */
   80 #ifndef XD3_DEFAULT_IOPT_SIZE
   81 #define XD3_DEFAULT_IOPT_SIZE    (1U<<15)
   82 #endif
   83 
   84 /* The maximum distance backward to search for small matches */
   85 #ifndef XD3_DEFAULT_SPREVSZ
   86 #define XD3_DEFAULT_SPREVSZ (1U<<18)
   87 #endif
   88 
   89 /* The default compression level */
   90 #ifndef XD3_DEFAULT_LEVEL
   91 #define XD3_DEFAULT_LEVEL 3
   92 #endif
   93 
   94 #ifndef XD3_DEFAULT_SECONDARY_LEVEL
   95 #define XD3_DEFAULT_SECONDARY_LEVEL 6
   96 #endif
   97 
   98 #ifndef XD3_USE_LARGEFILE64
   99 #define XD3_USE_LARGEFILE64 1
  100 #endif
  101 
  102 /* The source window size is limited to 2GB unless
  103  * XD3_USE_LARGESIZET is defined to 1. */
  104 #ifndef XD3_USE_LARGESIZET
  105 #define XD3_USE_LARGESIZET 1
  106 #endif
  107 
  108 /* Sizes and addresses within VCDIFF windows are represented as usize_t
  109  *
  110  * For source-file offsets and total file sizes, total input and
  111  * output counts, the xoff_t type is used.  The decoder and encoder
  112  * generally check for overflow of the xoff_t size (this is tested at
  113  * the 32bit boundary [xdelta3-test.h]).
  114  */
  115 #ifndef _WIN32
  116 #define __STDC_FORMAT_MACROS
  117 #include <inttypes.h>
  118 #include <stdint.h>
  119 #else /* WIN32 case */
  120 #define WIN32_LEAN_AND_MEAN
  121 
  122 #ifndef WINVER
  123 #if XD3_USE_LARGEFILE64
  124 /* 64 bit file offsets: uses GetFileSizeEx and SetFilePointerEx. */
  125 #define WINVER      0x0500
  126 #define _WIN32_WINNT    0x0500
  127 #else /* xoff_t is 32bit */
  128 /* 32 bit file offsets: uses GetFileSize and SetFilePointer. */
  129 #define WINVER      0x0400
  130 #define _WIN32_WINNT    0x0400
  131 #endif /* if XD3_USE_LARGEFILE64 */
  132 #endif /* ifndef WINVER */
  133 
  134 #include <windows.h>
  135 
  136 /* _MSV_VER is defined by Microsoft tools, not by Mingw32 */
  137 #ifdef _MSC_VER
  138 typedef signed int     ssize_t;
  139 #if _MSC_VER < 1600
  140 typedef unsigned char  uint8_t;
  141 typedef unsigned short uint16_t;
  142 typedef unsigned long  uint32_t;
  143 typedef ULONGLONG      uint64_t;
  144 #else /* _MSC_VER >= 1600 */
  145 /* For MSVC10 and above */
  146 #include <stdint.h>
  147 #endif /* _MSC_VER < 1600 */
  148 #else /* _MSC_VER not defined  */
  149 /* Mingw32 */
  150 #include <stdint.h>
  151 #endif /* _MSC_VER defined */
  152 
  153 #endif /* _WIN32 defined */
  154 
  155 /* Settings based on the size of xoff_t (32 vs 64 file offsets) */
  156 #if XD3_USE_LARGEFILE64
  157 /* xoff_t is a 64-bit type */
  158 #define __USE_FILE_OFFSET64 1 /* GLIBC: for 64bit fileops. */
  159 
  160 #ifndef _LARGEFILE_SOURCE
  161 #define _LARGEFILE_SOURCE
  162 #endif
  163 
  164 #ifndef _FILE_OFFSET_BITS
  165 #define _FILE_OFFSET_BITS 64
  166 #endif
  167 
  168 /* Set a xoff_t typedef and the "Q" printf insert. */
  169 #if defined(_WIN32)
  170 typedef uint64_t xoff_t;
  171 /* Note: The following generates benign warnings in a mingw
  172  * cross-compiler */
  173 #define Q "I64"
  174 #elif SIZEOF_UNSIGNED_LONG == 8
  175 typedef unsigned long xoff_t;
  176 #define Q "l"
  177 #elif SIZEOF_SIZE_T == 8
  178 typedef size_t xoff_t;
  179 #define Q "z"
  180 #elif SIZEOF_UNSIGNED_LONG_LONG == 8
  181 typedef unsigned long long xoff_t;
  182 #define Q "ll"
  183 #endif /* typedef and #define Q */
  184 
  185 #define SIZEOF_XOFF_T 8
  186 
  187 #else /* XD3_USE_LARGEFILE64 == 0 */
  188 
  189 #if SIZEOF_UNSIGNED_INT == 4
  190 typedef unsigned int xoff_t;
  191 #elif SIZEOF_UNSIGNED_LONG == 4
  192 typedef unsigned long xoff_t;
  193 #else
  194 typedef uint32_t xoff_t;
  195 #endif /* xoff_t is 32 bits */
  196 
  197 #define SIZEOF_XOFF_T 4
  198 #define Q
  199 #endif /* 64 vs 32 bit xoff_t */
  200 
  201 /* Settings based on the size of usize_t (32 and 64 bit window size) */
  202 #if XD3_USE_LARGESIZET
  203 
  204 /* Set a usize_ttypedef and the "W" printf insert. */
  205 #if defined(_WIN32)
  206 typedef uint64_t usize_t;
  207 /* Note: The following generates benign warnings in a mingw
  208  * cross-compiler */
  209 #define W "I64"
  210 #elif SIZEOF_UNSIGNED_LONG == 8
  211 typedef unsigned long usize_t;
  212 #define W "l"
  213 #elif SIZEOF_SIZE_T == 8
  214 typedef size_t usize_t;
  215 #define W "z"
  216 #elif SIZEOF_UNSIGNED_LONG_LONG == 8
  217 typedef unsigned long long usize_t;
  218 #define W "ll"
  219 #endif /* typedef and #define W */
  220 
  221 #define SIZEOF_USIZE_T 8
  222 
  223 #else /* XD3_USE_LARGESIZET == 0 */
  224 
  225 #if SIZEOF_UNSIGNED_INT == 4
  226 typedef unsigned int usize_t;
  227 #elif SIZEOF_UNSIGNED_LONG == 4
  228 typedef unsigned long usize_t;
  229 #else
  230 typedef uint32_t usize_t;
  231 #endif /* usize_t is 32 bits */
  232 
  233 #define SIZEOF_USIZE_T 4
  234 #define W
  235 
  236 #endif /* 64 vs 32 bit usize_t */
  237 
  238 /* Settings based on the size of size_t (the system-provided,
  239  * usually-but-maybe-not an unsigned type) */
  240 #if SIZEOF_SIZE_T == 4
  241 #define Z "z"
  242 #elif SIZEOF_SIZE_T == 8
  243 #ifdef _WIN32
  244 #define Z "I64"
  245 #else /* !_WIN32 */
  246 #define Z "z"
  247 #endif /* Windows or not */
  248 #else
  249 #error Bad configure script
  250 #endif /* size_t printf flags */
  251 
  252 #define USE_UINT32 (SIZEOF_USIZE_T == 4 || \
  253             SIZEOF_XOFF_T == 4 || REGRESSION_TEST)
  254 #define USE_UINT64 (SIZEOF_USIZE_T == 8 || \
  255             SIZEOF_XOFF_T == 8 || REGRESSION_TEST)
  256 
  257 #ifndef UNALIGNED_OK
  258 #ifdef HAVE_ALIGNED_ACCESS_REQUIRED
  259 #define UNALIGNED_OK 0
  260 #else
  261 /* This generally includes all Windows builds. */
  262 #define UNALIGNED_OK 1
  263 #endif
  264 #endif
  265 
  266 /**********************************************************************/
  267 
  268 /* Whether to build the encoder, otherwise only build the decoder. */
  269 #ifndef XD3_ENCODER
  270 #define XD3_ENCODER 1
  271 #endif
  272 
  273 /* The code returned when main() fails, also defined in system
  274    includes. */
  275 #ifndef EXIT_FAILURE
  276 #define EXIT_FAILURE 1
  277 #endif
  278 
  279 /* REGRESSION TEST enables the "xdelta3 test" command, which runs a
  280    series of self-tests. */
  281 #ifndef REGRESSION_TEST
  282 #define REGRESSION_TEST 0
  283 #endif
  284 
  285 /* XD3_DEBUG=1 enables assertions and various statistics.  Levels > 1
  286  * enable some additional output only useful during development and
  287  * debugging. */
  288 #ifndef XD3_DEBUG
  289 #define XD3_DEBUG 0
  290 #endif
  291 
  292 #ifndef PYTHON_MODULE
  293 #define PYTHON_MODULE 0
  294 #endif
  295 
  296 #ifndef SWIG_MODULE
  297 #define SWIG_MODULE 0
  298 #endif
  299 
  300 #ifndef NOT_MAIN
  301 #define NOT_MAIN 0
  302 #endif
  303 
  304 /* There are three string matching functions supplied: one fast, one
  305  * slow (default), and one soft-configurable.  To disable any of
  306  * these, use the following definitions. */
  307 #ifndef XD3_BUILD_SLOW
  308 #define XD3_BUILD_SLOW 1
  309 #endif
  310 #ifndef XD3_BUILD_FAST
  311 #define XD3_BUILD_FAST 1
  312 #endif
  313 #ifndef XD3_BUILD_FASTER
  314 #define XD3_BUILD_FASTER 1
  315 #endif
  316 #ifndef XD3_BUILD_FASTEST
  317 #define XD3_BUILD_FASTEST 1
  318 #endif
  319 #ifndef XD3_BUILD_SOFT
  320 #define XD3_BUILD_SOFT 1
  321 #endif
  322 #ifndef XD3_BUILD_DEFAULT
  323 #define XD3_BUILD_DEFAULT 1
  324 #endif
  325 
  326 #if XD3_DEBUG
  327 #include <stdio.h>
  328 #endif
  329 
  330 typedef struct _xd3_stream             xd3_stream;
  331 typedef struct _xd3_source             xd3_source;
  332 typedef struct _xd3_hash_cfg           xd3_hash_cfg;
  333 typedef struct _xd3_smatcher           xd3_smatcher;
  334 typedef struct _xd3_rinst              xd3_rinst;
  335 typedef struct _xd3_dinst              xd3_dinst;
  336 typedef struct _xd3_hinst              xd3_hinst;
  337 typedef struct _xd3_winst              xd3_winst;
  338 typedef struct _xd3_rpage              xd3_rpage;
  339 typedef struct _xd3_addr_cache         xd3_addr_cache;
  340 typedef struct _xd3_output             xd3_output;
  341 typedef struct _xd3_desect             xd3_desect;
  342 typedef struct _xd3_iopt_buflist       xd3_iopt_buflist;
  343 typedef struct _xd3_rlist              xd3_rlist;
  344 typedef struct _xd3_sec_type           xd3_sec_type;
  345 typedef struct _xd3_sec_cfg            xd3_sec_cfg;
  346 typedef struct _xd3_sec_stream         xd3_sec_stream;
  347 typedef struct _xd3_config             xd3_config;
  348 typedef struct _xd3_code_table_desc    xd3_code_table_desc;
  349 typedef struct _xd3_code_table_sizes   xd3_code_table_sizes;
  350 typedef struct _xd3_slist              xd3_slist;
  351 typedef struct _xd3_whole_state        xd3_whole_state;
  352 typedef struct _xd3_wininfo            xd3_wininfo;
  353 
  354 /* The stream configuration has three callbacks functions, all of
  355  * which may be supplied with NULL values.  If config->getblk is
  356  * provided as NULL, the stream returns XD3_GETSRCBLK. */
  357 
  358 typedef void*  (xd3_alloc_func)    (void       *opaque,
  359                     size_t      items,
  360                     usize_t     size);
  361 typedef void   (xd3_free_func)     (void       *opaque,
  362                     void       *address);
  363 
  364 typedef int    (xd3_getblk_func)   (xd3_stream *stream,
  365                     xd3_source *source,
  366                     xoff_t      blkno);
  367 
  368 typedef const xd3_dinst* (xd3_code_table_func) (void);
  369 
  370 
  371 #ifdef _WIN32
  372 #define vsnprintf_func _vsnprintf
  373 #define snprintf_func _snprintf
  374 #else
  375 #define vsnprintf_func vsnprintf
  376 #define snprintf_func snprintf
  377 #endif
  378 #define short_sprintf(sb,fmt,...) \
  379   snprintf_func((sb).buf,sizeof((sb).buf),fmt,__VA_ARGS__)
  380 
  381 /* Type used for short snprintf calls. */
  382 typedef struct {
  383   char buf[48];
  384 } shortbuf;
  385 
  386 #ifndef PRINTF_ATTRIBUTE
  387 #define PRINTF_ATTRIBUTE(x,y) __attribute__ ((__format__ (__printf__, x, y)))
  388 #endif
  389 
  390 /* Underlying xprintf() */
  391 int xsnprintf_func (char *str, size_t n, const char *fmt, ...)
  392   PRINTF_ATTRIBUTE(3,4);
  393 
  394 /* XPR(NT "", ...) (used by main) prefixes an "xdelta3: " to the output. */
  395 void xprintf(const char *fmt, ...) PRINTF_ATTRIBUTE(1,2);
  396 #define XPR xprintf
  397 #define NT "xdelta3: "
  398 #define NTR ""
  399 /* DP(RINT ...) */
  400 #define DP   xprintf
  401 #define RINT ""
  402 
  403 #if XD3_DEBUG
  404 #define XD3_ASSERT(x)                    \
  405   do {                           \
  406     if (! (x)) {                     \
  407       DP(RINT "%s:%d: XD3 assertion failed: %s\n",   \
  408      __FILE__, __LINE__, #x);            \
  409       abort (); } } while (0)
  410 #else
  411 #define XD3_ASSERT(x) (void)0
  412 #endif  /* XD3_DEBUG */
  413 
  414 #define xd3_max(x,y) ((x) < (y) ? (y) : (x))
  415 #define xd3_min(x,y) ((x) < (y) ? (x) : (y))
  416 
  417 /****************************************************************
  418  PUBLIC ENUMS
  419  ******************************************************************/
  420 
  421 /* These are the five ordinary status codes returned by the
  422  * xd3_encode_input() and xd3_decode_input() state machines. */
  423 typedef enum {
  424 
  425   /* An application must be prepared to handle these five return
  426    * values from either xd3_encode_input or xd3_decode_input, except
  427    * in the case of no-source compression, in which case XD3_GETSRCBLK
  428    * is never returned.  More detailed comments for these are given in
  429    * xd3_encode_input and xd3_decode_input comments, below. */
  430   XD3_INPUT     = -17703, /* need input */
  431   XD3_OUTPUT    = -17704, /* have output */
  432   XD3_GETSRCBLK = -17705, /* need a block of source input (with no
  433                * xd3_getblk function), a chance to do
  434                * non-blocking read. */
  435   XD3_GOTHEADER = -17706, /* (decode-only) after the initial VCDIFF &
  436                  first window header */
  437   XD3_WINSTART  = -17707, /* notification: returned before a window is
  438                * processed, giving a chance to
  439                * XD3_SKIP_WINDOW or not XD3_SKIP_EMIT that
  440                * window. */
  441   XD3_WINFINISH  = -17708, /* notification: returned after
  442                   encode/decode & output for a window */
  443   XD3_TOOFARBACK = -17709, /* (encoder only) may be returned by
  444                   getblk() if the block is too old */
  445   XD3_INTERNAL   = -17710, /* internal error */
  446   XD3_INVALID    = -17711, /* invalid config */
  447   XD3_INVALID_INPUT = -17712, /* invalid input/decoder error */
  448   XD3_NOSECOND    = -17713, /* when secondary compression finds no
  449                    improvement. */
  450   XD3_UNIMPLEMENTED = -17714  /* currently VCD_TARGET, VCD_CODETABLE */
  451 } xd3_rvalues;
  452 
  453 /* special values in config->flags */
  454 typedef enum
  455 {
  456   XD3_JUST_HDR       = (1 << 1),   /* used by VCDIFF tools, see
  457                       xdelta3-main.h. */
  458   XD3_SKIP_WINDOW    = (1 << 2),   /* used by VCDIFF tools, see
  459                       xdelta3-main.h. */
  460   XD3_SKIP_EMIT      = (1 << 3),   /* used by VCDIFF tools, see
  461                       xdelta3-main.h. */
  462   XD3_FLUSH          = (1 << 4),   /* flush the stream buffer to
  463                       prepare for
  464                       xd3_stream_close(). */
  465 
  466   XD3_SEC_DJW        = (1 << 5),   /* use DJW static huffman */
  467   XD3_SEC_FGK        = (1 << 6),   /* use FGK adaptive huffman */
  468   XD3_SEC_LZMA       = (1 << 24),  /* use LZMA secondary */
  469 
  470   XD3_SEC_TYPE       = (XD3_SEC_DJW | XD3_SEC_FGK | XD3_SEC_LZMA),
  471 
  472   XD3_SEC_NODATA     = (1 << 7),   /* disable secondary compression of
  473                       the data section. */
  474   XD3_SEC_NOINST     = (1 << 8),   /* disable secondary compression of
  475                       the inst section. */
  476   XD3_SEC_NOADDR     = (1 << 9),   /* disable secondary compression of
  477                       the addr section. */
  478 
  479   XD3_SEC_NOALL      = (XD3_SEC_NODATA | XD3_SEC_NOINST | XD3_SEC_NOADDR),
  480 
  481   XD3_ADLER32        = (1 << 10),  /* enable checksum computation in
  482                       the encoder. */
  483   XD3_ADLER32_NOVER  = (1 << 11),  /* disable checksum verification in
  484                       the decoder. */
  485 
  486   XD3_NOCOMPRESS     = (1 << 13),  /* disable ordinary data
  487                     * compression feature, only search
  488                     * the source, not the target. */
  489   XD3_BEGREEDY       = (1 << 14),  /* disable the "1.5-pass
  490                     * algorithm", instead use greedy
  491                     * matching.  Greedy is off by
  492                     * default. */
  493   XD3_ADLER32_RECODE = (1 << 15),  /* used by "recode". */
  494 
  495   /* 4 bits to set the compression level the same as the command-line
  496    * setting -1 through -9 (-0 corresponds to the XD3_NOCOMPRESS flag,
  497    * and is independent of compression level).  This is for
  498    * convenience, especially with xd3_encode_memory(). */
  499 
  500   XD3_COMPLEVEL_SHIFT = 20,  /* 20 - 23 */
  501   XD3_COMPLEVEL_MASK = (0xF << XD3_COMPLEVEL_SHIFT),
  502   XD3_COMPLEVEL_1 = (1 << XD3_COMPLEVEL_SHIFT),
  503   XD3_COMPLEVEL_2 = (2 << XD3_COMPLEVEL_SHIFT),
  504   XD3_COMPLEVEL_3 = (3 << XD3_COMPLEVEL_SHIFT),
  505   XD3_COMPLEVEL_6 = (6 << XD3_COMPLEVEL_SHIFT),
  506   XD3_COMPLEVEL_9 = (9 << XD3_COMPLEVEL_SHIFT)
  507 
  508 } xd3_flags;
  509 
  510 /* The values of this enumeration are set in xd3_config using the
  511  * smatch_cfg variable.  It can be set to default, slow, fast, etc.,
  512  * and soft. */
  513 typedef enum
  514 {
  515   XD3_SMATCH_DEFAULT = 0, /* Flags may contain XD3_COMPLEVEL bits,
  516                  else default. */
  517   XD3_SMATCH_SLOW    = 1,
  518   XD3_SMATCH_FAST    = 2,
  519   XD3_SMATCH_FASTER  = 3,
  520   XD3_SMATCH_FASTEST = 4,
  521   XD3_SMATCH_SOFT    = 5
  522 } xd3_smatch_cfg;
  523 
  524 /*********************************************************************
  525  PRIVATE ENUMS
  526 **********************************************************************/
  527 
  528 /* stream->match_state is part of the xd3_encode_input state machine
  529  *  for source matching:
  530  *
  531  *  1. the XD3_GETSRCBLK block-read mechanism means reentrant matching
  532  *  2. this state spans encoder windows: a match and end-of-window
  533  *  will continue in the next 3. the initial target byte and source
  534  *  byte are a presumed match, to avoid some computation in case the
  535  *  inputs are identical.
  536  */
  537 typedef enum {
  538 
  539   MATCH_TARGET    = 0, /* in this state, attempt to match the start of
  540             * the target with the previously set source
  541             * address (initially 0). */
  542   MATCH_BACKWARD  = 1, /* currently expanding a match backward in the
  543               source/target. */
  544   MATCH_FORWARD   = 2, /* currently expanding a match forward in the
  545               source/target. */
  546   MATCH_SEARCHING = 3  /* currently searching for a match. */
  547 
  548 } xd3_match_state;
  549 
  550 /* The xd3_encode_input state machine steps through these states in
  551  * the following order.  The matcher is reentrant and returns
  552  * XD3_INPUT whenever it requires more data.  After receiving
  553  * XD3_INPUT, if the application reads EOF it should call
  554  * xd3_stream_close().
  555  */
  556 typedef enum {
  557 
  558   ENC_INIT      = 0, /* xd3_encode_input has never been called. */
  559   ENC_INPUT     = 1, /* waiting for xd3_avail_input () to be called. */
  560   ENC_SEARCH    = 2, /* currently searching for matches. */
  561   ENC_INSTR     = 3, /* currently formatting output. */
  562   ENC_FLUSH     = 4, /* currently emitting output. */
  563   ENC_POSTOUT   = 5, /* after an output section. */
  564   ENC_POSTWIN   = 6, /* after all output sections. */
  565   ENC_ABORTED   = 7  /* abort. */
  566 } xd3_encode_state;
  567 
  568 /* The xd3_decode_input state machine steps through these states in
  569  * the following order.  The matcher is reentrant and returns
  570  * XD3_INPUT whenever it requires more data.  After receiving
  571  * XD3_INPUT, if the application reads EOF it should call
  572  * xd3_stream_close().
  573  *
  574  * 0-8:   the VCDIFF header
  575  * 9-18:  the VCDIFF window header
  576  * 19-21: the three primary sections: data, inst, addr
  577  * 22:    producing output: returns XD3_OUTPUT, possibly XD3_GETSRCBLK,
  578  * 23:    return XD3_WINFINISH, set state=9 to decode more input
  579  */
  580 typedef enum {
  581 
  582   DEC_VCHEAD   = 0, /* VCDIFF header */
  583   DEC_HDRIND   = 1, /* header indicator */
  584 
  585   DEC_SECONDID = 2, /* secondary compressor ID */
  586 
  587   DEC_TABLEN   = 3, /* code table length */
  588   DEC_NEAR     = 4, /* code table near */
  589   DEC_SAME     = 5, /* code table same */
  590   DEC_TABDAT   = 6, /* code table data */
  591 
  592   DEC_APPLEN   = 7, /* application data length */
  593   DEC_APPDAT   = 8, /* application data */
  594 
  595   DEC_WININD   = 9, /* window indicator */
  596 
  597   DEC_CPYLEN   = 10, /* copy window length */
  598   DEC_CPYOFF   = 11, /* copy window offset */
  599 
  600   DEC_ENCLEN   = 12, /* length of delta encoding */
  601   DEC_TGTLEN   = 13, /* length of target window */
  602   DEC_DELIND   = 14, /* delta indicator */
  603 
  604   DEC_DATALEN  = 15, /* length of ADD+RUN data */
  605   DEC_INSTLEN  = 16, /* length of instruction data */
  606   DEC_ADDRLEN  = 17, /* length of address data */
  607 
  608   DEC_CKSUM    = 18, /* window checksum */
  609 
  610   DEC_DATA     = 19, /* data section */
  611   DEC_INST     = 20, /* instruction section */
  612   DEC_ADDR     = 21, /* address section */
  613 
  614   DEC_EMIT     = 22, /* producing data */
  615 
  616   DEC_FINISH   = 23, /* window finished */
  617 
  618   DEC_ABORTED  = 24  /* xd3_abort_stream */
  619 } xd3_decode_state;
  620 
  621 /************************************************************
  622  internal types
  623  ************************************************************/
  624 
  625 /* instruction lists used in the IOPT buffer */
  626 struct _xd3_rlist
  627 {
  628   xd3_rlist  *next;
  629   xd3_rlist  *prev;
  630 };
  631 
  632 /* the raw encoding of an instruction used in the IOPT buffer */
  633 struct _xd3_rinst
  634 {
  635   uint8_t     type;
  636   uint8_t     xtra;
  637   uint8_t     code1;
  638   uint8_t     code2;
  639   usize_t      pos;
  640   usize_t      size;
  641   xoff_t      addr;
  642   xd3_rlist   link;
  643 };
  644 
  645 /* the code-table form of an single- or double-instruction */
  646 struct _xd3_dinst
  647 {
  648   uint8_t     type1;
  649   uint8_t     size1;
  650   uint8_t     type2;
  651   uint8_t     size2;
  652 };
  653 
  654 /* the decoded form of a single (half) instruction. */
  655 struct _xd3_hinst
  656 {
  657   uint8_t    type;
  658   usize_t    size;
  659   usize_t    addr;
  660 };
  661 
  662 /* the form of a whole-file instruction */
  663 struct _xd3_winst
  664 {
  665   uint8_t type;  /* RUN, ADD, COPY */
  666   uint8_t mode;  /* 0, VCD_SOURCE, VCD_TARGET */
  667   usize_t size;
  668   xoff_t  addr;
  669   xoff_t  position;  /* absolute position of this inst */
  670 };
  671 
  672 /* used by the encoder to buffer output in sections.  list of blocks. */
  673 struct _xd3_output
  674 {
  675   uint8_t    *base;
  676   usize_t     next;
  677   usize_t     avail;
  678   xd3_output *next_page;
  679 };
  680 
  681 /* used by the decoder to buffer input in sections. */
  682 struct _xd3_desect
  683 {
  684   const uint8_t *buf;
  685   const uint8_t *buf_max;
  686   usize_t        size;
  687   usize_t        pos;
  688 
  689   /* used in xdelta3-decode.h */
  690   uint8_t       *copied1;
  691   usize_t        alloc1;
  692 
  693   /* used in xdelta3-second.h */
  694   uint8_t       *copied2;
  695   usize_t        alloc2;
  696 };
  697 
  698 /* the VCDIFF address cache, see the RFC */
  699 struct _xd3_addr_cache
  700 {
  701   usize_t  s_near;
  702   usize_t  s_same;
  703   usize_t  next_slot;  /* the circular index for near */
  704   usize_t *near_array; /* array of size s_near        */
  705   usize_t *same_array; /* array of size s_same*256    */
  706 };
  707 
  708 /* the IOPT buffer list is just a list of buffers, which may be allocated
  709  * during encode when using an unlimited buffer. */
  710 struct _xd3_iopt_buflist
  711 {
  712   xd3_rinst *buffer;
  713   xd3_iopt_buflist *next;
  714 };
  715 
  716 /* This is the record of a pre-compiled configuration, a subset of
  717    xd3_config. */
  718 struct _xd3_smatcher
  719 {
  720   const char        *name;
  721   int             (*string_match) (xd3_stream  *stream);
  722   usize_t            large_look;
  723   usize_t            large_step;
  724   usize_t            small_look;
  725   usize_t            small_chain;
  726   usize_t            small_lchain;
  727   usize_t            max_lazy;
  728   usize_t            long_enough;
  729 };
  730 
  731 /* hash table size & power-of-two hash function. */
  732 struct _xd3_hash_cfg
  733 {
  734   usize_t  size;       // Number of buckets
  735   usize_t  shift;
  736   usize_t  mask;
  737   usize_t  look;       // How wide is this checksum
  738   usize_t  multiplier; // K * powers[0]
  739   usize_t *powers;     // Array of [0,look) where powers[look-1] == 1
  740                        // and powers[N] = powers[N+1]*K (Rabin-Karp)
  741 };
  742 
  743 /* the sprev list */
  744 struct _xd3_slist
  745 {
  746   usize_t     last_pos;
  747 };
  748 
  749 /* window info (for whole state) */
  750 struct _xd3_wininfo {
  751   xoff_t offset;
  752   usize_t length;
  753   uint32_t adler32;
  754 };
  755 
  756 /* whole state for, e.g., merge */
  757 struct _xd3_whole_state {
  758   usize_t addslen;
  759   uint8_t *adds;
  760   usize_t  adds_alloc;
  761 
  762   usize_t instlen;
  763   xd3_winst *inst;
  764   usize_t  inst_alloc;
  765 
  766   usize_t wininfolen;
  767   xd3_wininfo *wininfo;
  768   usize_t wininfo_alloc;
  769 
  770   xoff_t length;
  771 };
  772 
  773 /********************************************************************
  774  public types
  775  *******************************************************************/
  776 
  777 /* Settings for the secondary compressor. */
  778 struct _xd3_sec_cfg
  779 {
  780   int                data_type;     /* Which section. (set automatically) */
  781   usize_t            ngroups;       /* Number of DJW Huffman groups. */
  782   usize_t            sector_size;   /* Sector size. */
  783   int                inefficient;   /* If true, ignore efficiency check [avoid XD3_NOSECOND]. */
  784 };
  785 
  786 /* This is the user-visible stream configuration. */
  787 struct _xd3_config
  788 {
  789   usize_t             winsize;       /* The encoder window size. */
  790   usize_t             sprevsz;       /* How far back small string
  791                     matching goes */
  792   usize_t             iopt_size;     /* entries in the
  793                     instruction-optimizing
  794                     buffer */
  795 
  796   xd3_getblk_func   *getblk;        /* The three callbacks. */
  797   xd3_alloc_func    *alloc;
  798   xd3_free_func     *freef;
  799   void              *opaque;        /* Not used. */
  800   uint32_t           flags;         /* stream->flags are initialized
  801                      * from xd3_config & never
  802                      * modified by the library.  Use
  803                      * xd3_set_flags to modify flags
  804                      * settings mid-stream. */
  805 
  806   xd3_sec_cfg       sec_data;       /* Secondary compressor config: data */
  807   xd3_sec_cfg       sec_inst;       /* Secondary compressor config: inst */
  808   xd3_sec_cfg       sec_addr;       /* Secondary compressor config: addr */
  809 
  810   xd3_smatch_cfg     smatch_cfg;    /* See enum: use fields below  for
  811                        soft config */
  812   xd3_smatcher       smatcher_soft;
  813 };
  814 
  815 /* The primary source file object. You create one of these objects and
  816  * initialize the first four fields.  This library maintains the next
  817  * 5 fields.  The configured getblk implementation is responsible for
  818  * setting the final 3 fields when called (and/or when XD3_GETSRCBLK
  819  * is returned).
  820  */
  821 struct _xd3_source
  822 {
  823   /* you set */
  824   usize_t             blksize;       /* block size */
  825   const char         *name;          /* its name, for debug/print
  826                     purposes */
  827   void               *ioh;           /* opaque handle */
  828   xoff_t              max_winsize;   /* maximum visible buffer */
  829 
  830   /* getblk sets */
  831   xoff_t              curblkno;      /* current block number: client
  832                     sets after getblk request */
  833   usize_t             onblk;         /* number of bytes on current
  834                     block: client sets,  must be >= 0
  835                         and <= blksize */
  836   const uint8_t      *curblk;        /* current block array: client
  837                     sets after getblk request */
  838 
  839   /* xd3 sets */
  840   usize_t             srclen;        /* length of this source window */
  841   xoff_t              srcbase;       /* offset of this source window
  842                     in the source itself */
  843   usize_t             shiftby;       /* for power-of-two blocksizes */
  844   usize_t             maskby;        /* for power-of-two blocksizes */
  845   xoff_t              cpyoff_blocks; /* offset of dec_cpyoff in blocks */
  846   usize_t             cpyoff_blkoff; /* offset of copy window in
  847                     blocks, remainder */
  848   xoff_t              getblkno;      /* request block number: xd3 sets
  849                     current getblk request */
  850 
  851   /* See xd3_getblk() */
  852   xoff_t              max_blkno;  /* Maximum block, if eof is known,
  853                    * otherwise, equals frontier_blkno
  854                    * (initially 0). */
  855   usize_t             onlastblk;  /* Number of bytes on max_blkno */
  856   int                 eof_known;  /* Set to true when the first
  857                    * partial block is read. */
  858 };
  859 
  860 /* The primary xd3_stream object, used for encoding and decoding.  You
  861  * may access only two fields: avail_out, next_out.  Use the methods
  862  * above to operate on xd3_stream. */
  863 struct _xd3_stream
  864 {
  865   /* input state */
  866   const uint8_t    *next_in;          /* next input byte */
  867   usize_t           avail_in;         /* number of bytes available at
  868                      next_in */
  869   xoff_t            total_in;         /* how many bytes in */
  870 
  871   /* output state */
  872   uint8_t          *next_out;         /* next output byte */
  873   usize_t           avail_out;        /* number of bytes available at
  874                      next_out */
  875   usize_t           space_out;        /* total out space */
  876   xoff_t            current_window;   /* number of windows encoded/decoded */
  877   xoff_t            total_out;        /* how many bytes out */
  878 
  879   /* to indicate an error, xd3 sets */
  880   const char       *msg;              /* last error message, NULL if
  881                      no error */
  882 
  883   /* source configuration */
  884   xd3_source       *src;              /* source array */
  885 
  886   /* encoder memory configuration */
  887   usize_t           winsize;          /* suggested window size */
  888   usize_t           sprevsz;          /* small string, previous window
  889                      size (power of 2) */
  890   usize_t           sprevmask;        /* small string, previous window
  891                      size mask */
  892   usize_t           iopt_size;
  893   usize_t           iopt_unlimited;
  894 
  895   /* general configuration */
  896   xd3_getblk_func  *getblk;           /* set nxtblk, nxtblkno to scanblkno */
  897   xd3_alloc_func   *alloc;            /* malloc function */
  898   xd3_free_func    *free;             /* free function */
  899   void*             opaque;           /* private data object passed to
  900                      alloc, free, and getblk */
  901   uint32_t          flags;            /* various options */
  902 
  903   /* secondary compressor configuration */
  904   xd3_sec_cfg       sec_data;         /* Secondary compressor config: data */
  905   xd3_sec_cfg       sec_inst;         /* Secondary compressor config: inst */
  906   xd3_sec_cfg       sec_addr;         /* Secondary compressor config: addr */
  907 
  908   xd3_smatcher      smatcher;
  909 
  910   usize_t           *large_table;      /* table of large checksums */
  911   xd3_hash_cfg       large_hash;       /* large hash config */
  912 
  913   usize_t           *small_table;      /* table of small checksums */
  914   xd3_slist         *small_prev;       /* table of previous offsets,
  915                       circular linked list */
  916   int                small_reset;      /* true if small table should
  917                       be reset */
  918 
  919   xd3_hash_cfg       small_hash;       /* small hash config */
  920   xd3_addr_cache     acache;           /* the vcdiff address cache */
  921   xd3_encode_state   enc_state;        /* state of the encoder */
  922 
  923   usize_t            taroff;           /* base offset of the target input */
  924   usize_t            input_position;   /* current input position */
  925   usize_t            min_match;        /* current minimum match
  926                       length, avoids redundent
  927                       matches */
  928   usize_t            unencoded_offset; /* current input, first
  929                        * unencoded offset. this value
  930                        * is <= the first instruction's
  931                        * position in the iopt buffer,
  932                        * if there is at least one
  933                        * match in the buffer. */
  934 
  935   /* SRCWIN */
  936   int                srcwin_decided;    /* boolean: true if srclen and
  937                        srcbase have been
  938                        decided. */
  939   int                srcwin_decided_early;  /* boolean: true if srclen
  940                            and srcbase were
  941                            decided early. */
  942   xoff_t             srcwin_cksum_pos;  /* Source checksum position */
  943 
  944   /* MATCH */
  945   xd3_match_state    match_state;      /* encoder match state */
  946   xoff_t             match_srcpos;     /* current match source
  947                       position relative to
  948                       srcbase */
  949   xoff_t             match_last_srcpos;  /* previously attempted
  950                       * srcpos, to avoid loops. */
  951   xoff_t             match_minaddr;    /* smallest matching address to
  952                        * set window params (reset each
  953                        * window xd3_encode_reset) */
  954   xoff_t             match_maxaddr;    /* largest matching address to
  955                        * set window params (reset each
  956                        * window xd3_encode_reset) */
  957   usize_t            match_back;       /* match extends back so far */
  958   usize_t            match_maxback;    /* match extends back maximum */
  959   usize_t            match_fwd;        /* match extends forward so far */
  960   usize_t            match_maxfwd;     /* match extends forward maximum */
  961 
  962   xoff_t             maxsrcaddr;      /* address of the last source
  963                      match (across windows) */
  964 
  965   uint8_t          *buf_in;           /* for saving buffered input */
  966   usize_t           buf_avail;        /* amount of saved input */
  967   const uint8_t    *buf_leftover;     /* leftover content of next_in
  968                      (i.e., user's buffer) */
  969   usize_t            buf_leftavail;    /* amount of leftover content */
  970 
  971   xd3_output       *enc_current;      /* current output buffer */
  972   xd3_output       *enc_free;         /* free output buffers */
  973   xd3_output       *enc_heads[4];     /* array of encoded outputs:
  974                      head of chain */
  975   xd3_output       *enc_tails[4];     /* array of encoded outputs:
  976                      tail of chain */
  977   uint32_t          recode_adler32;   /* set the adler32 checksum
  978                        * during "recode". */
  979 
  980   xd3_rlist         iopt_used;        /* instruction optimizing buffer */
  981   xd3_rlist         iopt_free;
  982   xd3_rinst        *iout;             /* next single instruction */
  983   xd3_iopt_buflist *iopt_alloc;
  984 
  985   const uint8_t    *enc_appheader;    /* application header to encode */
  986   usize_t            enc_appheadsz;    /* application header size */
  987 
  988   /* decoder stuff */
  989   xd3_decode_state  dec_state;        /* current DEC_XXX value */
  990   usize_t           dec_hdr_ind;      /* VCDIFF header indicator */
  991   usize_t           dec_win_ind;      /* VCDIFF window indicator */
  992   usize_t           dec_del_ind;      /* VCDIFF delta indicator */
  993 
  994   uint8_t           dec_magic[4];     /* First four bytes */
  995   usize_t           dec_magicbytes;   /* Magic position. */
  996 
  997   usize_t           dec_secondid;     /* Optional secondary compressor ID. */
  998 
  999   usize_t           dec_codetblsz;    /* Optional code table: length. */
 1000   uint8_t          *dec_codetbl;      /* Optional code table: storage. */
 1001   usize_t           dec_codetblbytes; /* Optional code table: position. */
 1002 
 1003   usize_t           dec_appheadsz;    /* Optional application header:
 1004                      size. */
 1005   uint8_t          *dec_appheader;    /* Optional application header:
 1006                      storage */
 1007   usize_t           dec_appheadbytes; /* Optional application header:
 1008                      position. */
 1009 
 1010   usize_t            dec_cksumbytes;   /* Optional checksum: position. */
 1011   uint8_t           dec_cksum[4];     /* Optional checksum: storage. */
 1012   uint32_t          dec_adler32;      /* Optional checksum: value. */
 1013 
 1014   usize_t            dec_cpylen;       /* length of copy window
 1015                       (VCD_SOURCE or VCD_TARGET) */
 1016   xoff_t             dec_cpyoff;       /* offset of copy window
 1017                       (VCD_SOURCE or VCD_TARGET) */
 1018   usize_t            dec_enclen;       /* length of delta encoding */
 1019   usize_t            dec_tgtlen;       /* length of target window */
 1020 
 1021 #if USE_UINT64
 1022   uint64_t          dec_64part;       /* part of a decoded uint64_t */
 1023 #endif
 1024 #if USE_UINT32
 1025   uint32_t          dec_32part;       /* part of a decoded uint32_t */
 1026 #endif
 1027 
 1028   xoff_t            dec_winstart;     /* offset of the start of
 1029                                          current target window */
 1030   xoff_t            dec_window_count; /* == current_window + 1 in
 1031                                          DEC_FINISH */
 1032   usize_t            dec_winbytes;     /* bytes of the three sections
 1033                                           so far consumed */
 1034   usize_t            dec_hdrsize;      /* VCDIFF + app header size */
 1035 
 1036   const uint8_t    *dec_tgtaddrbase;  /* Base of decoded target
 1037                                          addresses (addr >=
 1038                                          dec_cpylen). */
 1039   const uint8_t    *dec_cpyaddrbase;  /* Base of decoded copy
 1040                                          addresses (addr <
 1041                                          dec_cpylen). */
 1042 
 1043   usize_t            dec_position;     /* current decoder position
 1044                                           counting the cpylen
 1045                                           offset */
 1046   usize_t            dec_maxpos;       /* maximum decoder position
 1047                                           counting the cpylen
 1048                                           offset */
 1049   xd3_hinst         dec_current1;     /* current instruction */
 1050   xd3_hinst         dec_current2;     /* current instruction */
 1051 
 1052   uint8_t          *dec_buffer;       /* Decode buffer */
 1053   uint8_t          *dec_lastwin;      /* In case of VCD_TARGET, the
 1054                                          last target window. */
 1055   usize_t            dec_lastlen;      /* length of the last target
 1056                                           window */
 1057   xoff_t            dec_laststart;    /* offset of the start of last
 1058                                          target window */
 1059   usize_t            dec_lastspace;    /* allocated space of last
 1060                                           target window, for reuse */
 1061 
 1062   xd3_desect        inst_sect;        /* staging area for decoding
 1063                                          window sections */
 1064   xd3_desect        addr_sect;
 1065   xd3_desect        data_sect;
 1066 
 1067   xd3_code_table_func       *code_table_func;
 1068   const xd3_dinst           *code_table;
 1069   const xd3_code_table_desc *code_table_desc;
 1070   xd3_dinst                 *code_table_alloc;
 1071 
 1072   /* secondary compression */
 1073   const xd3_sec_type *sec_type;
 1074   xd3_sec_stream     *sec_stream_d;
 1075   xd3_sec_stream     *sec_stream_i;
 1076   xd3_sec_stream     *sec_stream_a;
 1077 
 1078   /* state for reconstructing whole files (e.g., for merge), this only
 1079    * supports loading USIZE_T_MAX instructions, adds, etc. */
 1080   xd3_whole_state     whole_target;
 1081 
 1082   /* statistics */
 1083   xoff_t            n_scpy;
 1084   xoff_t            n_tcpy;
 1085   xoff_t            n_add;
 1086   xoff_t            n_run;
 1087 
 1088   xoff_t            l_scpy;
 1089   xoff_t            l_tcpy;
 1090   xoff_t            l_add;
 1091   xoff_t            l_run;
 1092 
 1093   usize_t           i_slots_used;
 1094 
 1095 #if XD3_DEBUG
 1096   usize_t            large_ckcnt;
 1097 
 1098   /* memory usage */
 1099   usize_t            alloc_cnt;
 1100   usize_t            free_cnt;
 1101 #endif
 1102 };
 1103 
 1104 /**************************************************************************
 1105  PUBLIC FUNCTIONS
 1106  **************************************************************************/
 1107 
 1108 /* This function configures an xd3_stream using the provided in-memory
 1109  * input buffer, source buffer, output buffer, and flags.  The output
 1110  * array must be large enough or else ENOSPC will be returned.  This
 1111  * is the simplest in-memory encoding interface. */
 1112 int     xd3_encode_memory (const uint8_t *input,
 1113                usize_t        input_size,
 1114                const uint8_t *source,
 1115                usize_t        source_size,
 1116                uint8_t       *output_buffer,
 1117                usize_t       *output_size,
 1118                usize_t        avail_output,
 1119                int            flags);
 1120 
 1121 /* The reverse of xd3_encode_memory. */
 1122 int     xd3_decode_memory (const uint8_t *input,
 1123                usize_t        input_size,
 1124                const uint8_t *source,
 1125                usize_t        source_size,
 1126                uint8_t       *output_buf,
 1127                usize_t       *output_size,
 1128                usize_t        avail_output,
 1129                int            flags);
 1130 
 1131 /* This function encodes an in-memory input using a pre-configured
 1132  * xd3_stream.  This allows the caller to set a variety of options
 1133  * which are not available in the xd3_encode/decode_memory()
 1134  * functions.
 1135  *
 1136  * The output array must be large enough to hold the output or else
 1137  * ENOSPC is returned.  The source (if any) should be set using
 1138  * xd3_set_source_and_size() with a single-block xd3_source.  This
 1139  * calls the underlying non-blocking interfaces,
 1140  * xd3_encode/decode_input(), handling the necessary input/output
 1141  * states.  This method may be considered a reference for any
 1142  * application using xd3_encode_input() directly.
 1143  *
 1144  *   xd3_stream stream;
 1145  *   xd3_config config;
 1146  *   xd3_source src;
 1147  *
 1148  *   memset (& src, 0, sizeof (src));
 1149  *   memset (& stream, 0, sizeof (stream));
 1150  *   memset (& config, 0, sizeof (config));
 1151  *
 1152  *   if (source != NULL)
 1153  *     {
 1154  *       src.size = source_size;
 1155  *       src.blksize = source_size;
 1156  *       src.curblkno = 0;
 1157  *       src.onblk = source_size;
 1158  *       src.curblk = source;
 1159  *       src.max_winsize = source_size;
 1160  *       xd3_set_source(&stream, &src);
 1161  *     }
 1162  *
 1163  *   config.flags = flags;
 1164  *   config.winsize = input_size;
 1165  *
 1166  *   ... set smatcher, appheader, encoding-table, compression-level, etc.
 1167  *
 1168  *   xd3_config_stream(&stream, &config);
 1169  *   xd3_encode_stream(&stream, ...);
 1170  *   xd3_free_stream(&stream);
 1171  */
 1172 int     xd3_encode_stream (xd3_stream    *stream,
 1173                const uint8_t *input,
 1174                usize_t         input_size,
 1175                uint8_t       *output,
 1176                usize_t        *output_size,
 1177                usize_t         avail_output);
 1178 
 1179 /* The reverse of xd3_encode_stream. */
 1180 int     xd3_decode_stream (xd3_stream    *stream,
 1181                const uint8_t *input,
 1182                usize_t        input_size,
 1183                uint8_t       *output,
 1184                usize_t       *output_size,
 1185                usize_t        avail_size);
 1186 
 1187 /* This is the non-blocking interface.
 1188  *
 1189  * Handling input and output states is the same for encoding or
 1190  * decoding using the xd3_avail_input() and xd3_consume_output()
 1191  * routines, inlined below.
 1192  *
 1193  * Return values:
 1194  *
 1195  *   XD3_INPUT: the process requires more input: call
 1196  *               xd3_avail_input() then repeat
 1197  *
 1198  *   XD3_OUTPUT: the process has more output: read stream->next_out,
 1199  *               stream->avail_out, then call xd3_consume_output(),
 1200  *               then repeat
 1201  *
 1202  *   XD3_GOTHEADER: (decoder-only) notification returned following the
 1203  *               VCDIFF header and first window header.  the decoder
 1204  *               may use the header to configure itself.
 1205  *
 1206  *   XD3_WINSTART: a general notification returned once for each
 1207  *               window except the 0-th window, which is implied by
 1208  *               XD3_GOTHEADER.  It is recommended to use a
 1209  *               switch-stmt such as:
 1210  *
 1211  *                 ...
 1212  *               again:
 1213  *                 switch ((ret = xd3_decode_input (stream))) {
 1214  *                    case XD3_GOTHEADER: {
 1215  *                      assert(stream->current_window == 0);
 1216  *                      stuff;
 1217  *                    }
 1218  *                    // fallthrough
 1219  *                    case XD3_WINSTART: {
 1220  *                      something(stream->current_window);
 1221  *                      goto again;
 1222  *                    }
 1223  *                    ...
 1224  *
 1225  *   XD3_WINFINISH: a general notification, following the complete
 1226  *               input & output of a window.  at this point,
 1227  *               stream->total_in and stream->total_out are consistent
 1228  *               for either encoding or decoding.
 1229  *
 1230  *   XD3_GETSRCBLK: If the xd3_getblk() callback is NULL, this value
 1231  *               is returned to initiate a non-blocking source read.
 1232  */
 1233 int     xd3_decode_input  (xd3_stream    *stream);
 1234 int     xd3_encode_input  (xd3_stream    *stream);
 1235 
 1236 /* The xd3_config structure is used to initialize a stream - all data
 1237  * is copied into stream so config may be a temporary variable.  See
 1238  * the [documentation] or comments on the xd3_config structure. */
 1239 int     xd3_config_stream (xd3_stream    *stream,
 1240                xd3_config    *config);
 1241 
 1242 /* Since Xdelta3 doesn't open any files, xd3_close_stream is just an
 1243  * error check that the stream is in a proper state to be closed: this
 1244  * means the encoder is flushed and the decoder is at a window
 1245  * boundary.  The application is responsible for freeing any of the
 1246  * resources it supplied. */
 1247 int     xd3_close_stream (xd3_stream    *stream);
 1248 
 1249 /* This arranges for closes the stream to succeed.  Does not free the
 1250  * stream.*/
 1251 void    xd3_abort_stream (xd3_stream    *stream);
 1252 
 1253 /* xd3_free_stream frees all memory allocated for the stream.  The
 1254  * application is responsible for freeing any of the resources it
 1255  * supplied. */
 1256 void    xd3_free_stream   (xd3_stream    *stream);
 1257 
 1258 /* This function informs the encoder or decoder that source matching
 1259  * (i.e., delta-compression) is possible.  For encoding, this should
 1260  * be called before the first xd3_encode_input.  A NULL source is
 1261  * ignored.  For decoding, this should be called before the first
 1262  * window is decoded, but the appheader may be read first
 1263  * (XD3_GOTHEADER).  After decoding the header, call xd3_set_source()
 1264  * if you have a source file.  Note: if (stream->dec_win_ind & VCD_SOURCE)
 1265  * is true, it means the first window expects there to be a source file.
 1266  */
 1267 int     xd3_set_source    (xd3_stream    *stream,
 1268                xd3_source    *source);
 1269 
 1270 /* If the source size is known, call this instead of xd3_set_source().
 1271  * to avoid having stream->getblk called (and/or to avoid XD3_GETSRCBLK).
 1272  *
 1273  * Follow these steps:
 1274   xd3_source source;
 1275   memset(&source, 0, sizeof(source));
 1276   source.blksize  = size;
 1277   source.onblk    = size;
 1278   source.curblk   = buf;
 1279   source.curblkno = 0;
 1280   int ret = xd3_set_source_and_size(&stream, &source, size);
 1281   ...
 1282  */
 1283 int     xd3_set_source_and_size (xd3_stream    *stream,
 1284                  xd3_source    *source,
 1285                  xoff_t         source_size);
 1286 
 1287 /* This should be called before the first call to xd3_encode_input()
 1288  * to include application-specific data in the VCDIFF header. */
 1289 void    xd3_set_appheader (xd3_stream    *stream,
 1290                const uint8_t *data,
 1291                usize_t        size);
 1292 
 1293 /* xd3_get_appheader may be called in the decoder after XD3_GOTHEADER.
 1294  * For convenience, the decoder always adds a single byte padding to
 1295  * the end of the application header, which is set to zero in case the
 1296  * application header is a string. */
 1297 int     xd3_get_appheader (xd3_stream     *stream,
 1298                uint8_t       **data,
 1299                usize_t        *size);
 1300 
 1301 /* To generate a VCDIFF encoded delta with xd3_encode_init() from
 1302  * another format, use:
 1303  *
 1304  *   xd3_encode_init_partial() -- initialze encoder state (w/o hash tables)
 1305  *   xd3_init_cache() -- reset VCDIFF address cache
 1306  *   xd3_found_match() -- to report a copy instruction
 1307  *
 1308  * set stream->enc_state to ENC_INSTR and call xd3_encode_input as usual.
 1309  */
 1310 int xd3_encode_init_partial (xd3_stream *stream);
 1311 void xd3_init_cache (xd3_addr_cache* acache);
 1312 int xd3_found_match (xd3_stream *stream,
 1313              usize_t pos, usize_t size,
 1314              xoff_t addr, int is_source);
 1315 
 1316 /* Gives an error string for xdelta3-speficic errors, returns NULL for
 1317    system errors */
 1318 const char* xd3_strerror (int ret);
 1319 
 1320 /* For convenience, zero & initialize the xd3_config structure with
 1321    specified flags. */
 1322 static inline
 1323 void    xd3_init_config (xd3_config *config,
 1324              uint32_t    flags)
 1325 {
 1326   memset (config, 0, sizeof (*config));
 1327   config->flags = flags;
 1328 }
 1329 
 1330 /* This supplies some input to the stream.
 1331  *
 1332  * For encoding, if the input is larger than the configured window
 1333  * size (xd3_config.winsize), the entire input will be consumed and
 1334  * encoded anyway.  If you wish to strictly limit the window size,
 1335  * limit the buffer passed to xd3_avail_input to the window size.
 1336  *
 1337  * For encoding, if the input is smaller than the configured window
 1338  * size (xd3_config.winsize), the library will create a window-sized
 1339  * buffer and accumulate input until a full-sized window can be
 1340  * encoded.  XD3_INPUT will be returned.  The input must remain valid
 1341  * until the next time xd3_encode_input() returns XD3_INPUT.
 1342  *
 1343  * For decoding, the input will be consumed entirely before XD3_INPUT
 1344  * is returned again.
 1345  */
 1346 static inline
 1347 void    xd3_avail_input  (xd3_stream    *stream,
 1348               const uint8_t *idata,
 1349               usize_t         isize)
 1350 {
 1351   /* Even if isize is zero, the code expects a non-NULL idata.  Why?
 1352    * It uses this value to determine whether xd3_avail_input has ever
 1353    * been called.  If xd3_encode_input is called before
 1354    * xd3_avail_input it will return XD3_INPUT right away without
 1355    * allocating a stream->winsize buffer.  This is to avoid an
 1356    * unwanted allocation. */
 1357   XD3_ASSERT (idata != NULL || isize == 0);
 1358 
 1359   stream->next_in  = idata;
 1360   stream->avail_in = isize;
 1361 }
 1362 
 1363 /* This acknowledges receipt of output data, must be called after any
 1364  * XD3_OUTPUT return. */
 1365 static inline
 1366 void xd3_consume_output (xd3_stream  *stream)
 1367 {
 1368   stream->avail_out  = 0;
 1369 }
 1370 
 1371 /* These are set for each XD3_WINFINISH return. */
 1372 static inline
 1373 int xd3_encoder_used_source (xd3_stream *stream) {
 1374   return stream->src != NULL && stream->src->srclen > 0;
 1375 }
 1376 static inline
 1377 xoff_t xd3_encoder_srcbase (xd3_stream *stream) {
 1378   return stream->src->srcbase;
 1379 }
 1380 static inline
 1381 usize_t xd3_encoder_srclen (xd3_stream *stream) {
 1382   return stream->src->srclen;
 1383 }
 1384 
 1385 /* Checks for legal flag changes. */
 1386 static inline
 1387 void xd3_set_flags (xd3_stream *stream, uint32_t flags)
 1388 {
 1389   /* The bitwise difference should contain only XD3_FLUSH or
 1390      XD3_SKIP_WINDOW */
 1391   XD3_ASSERT(((flags ^ stream->flags) & ~(XD3_FLUSH | XD3_SKIP_WINDOW)) == 0);
 1392   stream->flags = flags;
 1393 }
 1394 
 1395 /* Gives some extra information about the latest library error, if any
 1396  * is known. */
 1397 static inline
 1398 const char* xd3_errstring (xd3_stream  *stream)
 1399 {
 1400   return stream->msg ? stream->msg : "";
 1401 }
 1402 
 1403 
 1404 /* 64-bit divisions are expensive, which is why we require a
 1405  * power-of-two source->blksize.  To relax this restriction is
 1406  * relatively easy, see the history for xd3_blksize_div(). */
 1407 static inline
 1408 void xd3_blksize_div (const xoff_t offset,
 1409               const xd3_source *source,
 1410               xoff_t *blkno,
 1411               usize_t *blkoff) {
 1412   *blkno = offset >> source->shiftby;
 1413   *blkoff = offset & source->maskby;
 1414   XD3_ASSERT (*blkoff < source->blksize);
 1415 }
 1416 
 1417 static inline
 1418 void xd3_blksize_add (xoff_t *blkno,
 1419               usize_t *blkoff,
 1420               const xd3_source *source,
 1421               const usize_t add)
 1422 {
 1423   usize_t blkdiff;
 1424 
 1425   /* Does not check for overflow, checked in xdelta3-decode.h. */
 1426   *blkoff += add;
 1427   blkdiff = *blkoff >> source->shiftby;
 1428 
 1429   if (blkdiff)
 1430     {
 1431       *blkno += blkdiff;
 1432       *blkoff &= source->maskby;
 1433     }
 1434 
 1435   XD3_ASSERT (*blkoff < source->blksize);
 1436 }
 1437 
 1438 #define XD3_NOOP 0U
 1439 #define XD3_ADD 1U
 1440 #define  XD3_RUN 2U
 1441 #define  XD3_CPY 3U /* XD3_CPY rtypes are represented as (XD3_CPY +
 1442                      * copy-mode value) */
 1443 
 1444 #if XD3_DEBUG
 1445 #define IF_DEBUG(x) x
 1446 #else
 1447 #define IF_DEBUG(x)
 1448 #endif
 1449 #if XD3_DEBUG > 1
 1450 #define IF_DEBUG1(x) x
 1451 #else
 1452 #define IF_DEBUG1(x)
 1453 #endif
 1454 #if XD3_DEBUG > 2
 1455 #define IF_DEBUG2(x) x
 1456 #else
 1457 #define IF_DEBUG2(x)
 1458 #endif
 1459 
 1460 #define SIZEOF_ARRAY(x) (sizeof(x) / sizeof(x[0]))
 1461 
 1462 #endif /* _XDELTA3_H_ */