xdelta3.h

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