/* xdelta 3 - delta compression tools and library
* Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007,
* 2008, 2009, 2010
* Joshua P. MacDonald
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
/* TODO: This code is heavily revised from 3.0z but still needs major
* refactoring. */
#include "xdelta3-internal.h"
typedef struct _main_blklru main_blklru;
typedef struct _main_blklru_list main_blklru_list;
struct _main_blklru_list
{
main_blklru_list *next;
main_blklru_list *prev;
};
struct _main_blklru
{
uint8_t *blk;
xoff_t blkno;
usize_t size;
main_blklru_list link;
};
#define MAX_LRU_SIZE 32U
#define XD3_MINSRCWINSZ (XD3_ALLOCSIZE * MAX_LRU_SIZE)
#define XD3_MAXSRCWINSZ (1ULL << 31)
XD3_MAKELIST(main_blklru_list,main_blklru,link);
static usize_t lru_size = 0;
static main_blklru *lru = NULL; /* array of lru_size elts */
static main_blklru_list lru_list;
static int do_src_fifo = 0; /* set to avoid lru */
static int lru_hits = 0;
static int lru_misses = 0;
static int lru_filled = 0;
static void main_lru_reset (void)
{
lru_size = 0;
lru = NULL;
do_src_fifo = 0;
lru_hits = 0;
lru_misses = 0;
lru_filled = 0;
}
static void main_lru_cleanup (void)
{
if (lru != NULL)
{
main_buffree (lru[0].blk);
}
main_free (lru);
lru = NULL;
lru_hits = 0;
lru_misses = 0;
lru_filled = 0;
}
/* This is called at different times for encoding and decoding. The
* encoder calls it immediately, the decoder delays until the
* application header is received. */
static int
main_set_source (xd3_stream *stream, xd3_cmd cmd,
main_file *sfile, xd3_source *source)
{
int ret = 0;
usize_t i;
xoff_t source_size = 0;
usize_t blksize;
XD3_ASSERT (lru == NULL);
XD3_ASSERT (stream->src == NULL);
XD3_ASSERT (option_srcwinsz >= XD3_MINSRCWINSZ);
/* TODO: this code needs refactoring into FIFO, LRU, FAKE. Yuck!
* This is simplified from 3.0z which had issues with sizing the
* source buffer memory allocation and the source blocksize. */
/* LRU-specific */
main_blklru_list_init (& lru_list);
if (allow_fake_source)
{
/* TODO: refactor
* TOOLS/recode-specific: Check "allow_fake_source" mode looks
* broken now. */
sfile->mode = XO_READ;
sfile->realname = sfile->filename;
sfile->nread = 0;
}
else
{
/* Either a regular file (possibly compressed) or a FIFO
* (possibly compressed). */
if ((ret = main_file_open (sfile, sfile->filename, XO_READ)))
{
return ret;
}
/* If the file is regular we know it's size. If the file turns
* out to be externally compressed, size_known may change. */
sfile->size_known = (main_file_stat (sfile, &source_size) == 0);
}
/* Note: The API requires a power-of-two blocksize and srcwinsz
* (-B). The logic here will use a single block if the entire file
* is known to fit into srcwinsz. */
option_srcwinsz = xd3_pow2_roundup (option_srcwinsz);
/* Though called "lru", it is not LRU-specific. We always allocate
* a maximum number of source block buffers. If the entire file
* fits into srcwinsz, this buffer will stay as the only
* (lru_size==1) source block. Otherwise, we know that at least
* option_srcwinsz bytes are available. Split the source window
* into buffers. */
if ((lru = (main_blklru*) main_malloc (MAX_LRU_SIZE *
sizeof (main_blklru))) == NULL)
{
ret = ENOMEM;
return ret;
}
memset (lru, 0, sizeof(lru[0]) * MAX_LRU_SIZE);
/* Allocate the entire buffer. */
if ((lru[0].blk = (uint8_t*) main_bufalloc (option_srcwinsz)) == NULL)
{
ret = ENOMEM;
return ret;
}
/* Main calls main_getblk_func() once before xd3_set_source(). This
* is the point at which external decompression may begin. Set the
* system for a single block. */
lru_size = 1;
lru[0].blkno = (xoff_t) -1;
blksize = option_srcwinsz;
main_blklru_list_push_back (& lru_list, & lru[0]);
XD3_ASSERT (blksize != 0);
/* Initialize xd3_source. */
source->blksize = blksize;
source->name = sfile->filename;
source->ioh = sfile;
source->curblkno = (xoff_t) -1;
source->curblk = NULL;
source->max_winsize = option_srcwinsz;
if ((ret = main_getblk_func (stream, source, 0)) != 0)
{
XPR(NT "error reading source: %s: %s\n",
sfile->filename,
xd3_mainerror (ret));
return ret;
}
source->onblk = lru[0].size; /* xd3 sets onblk */
/* If the file is smaller than a block, size is known. */
if (!sfile->size_known && source->onblk < blksize)
{
source_size = source->onblk;
sfile->size_known = 1;
}
/* If the size is not known or is greater than the buffer size, we
* split the buffer across MAX_LRU_SIZE blocks (already allocated in
* "lru"). */
if (!sfile->size_known || source_size > option_srcwinsz)
{
/* Modify block 0, change blocksize. */
blksize = option_srcwinsz / MAX_LRU_SIZE;
source->blksize = blksize;
source->onblk = blksize; /* xd3 sets onblk */
/* Note: source->max_winsize is unchanged. */
lru[0].size = blksize;
lru_size = MAX_LRU_SIZE;
/* Setup rest of blocks. */
for (i = 1; i < lru_size; i += 1)
{
lru[i].blk = lru[0].blk + (blksize * i);
lru[i].blkno = i;
lru[i].size = blksize;
main_blklru_list_push_back (& lru_list, & lru[i]);
}
}
if (! sfile->size_known)
{
/* If the size is not know, we must use FIFO discipline. */
do_src_fifo = 1;
}
/* Call the appropriate set_source method, handle errors, print
* verbose message, etc. */
if (sfile->size_known)
{
ret = xd3_set_source_and_size (stream, source, source_size);
}
else
{
ret = xd3_set_source (stream, source);
}
if (ret)
{
XPR(NT XD3_LIB_ERRMSG (stream, ret));
return ret;
}
XD3_ASSERT (stream->src == source);
XD3_ASSERT (source->blksize == blksize);
if (option_verbose)
{
static shortbuf srcszbuf;
static shortbuf srccntbuf;
static shortbuf winszbuf;
static shortbuf blkszbuf;
static shortbuf nbufs;
if (sfile->size_known)
{
short_sprintf (srcszbuf, "source size %s [%"Q"u]",
main_format_bcnt (source_size, &srccntbuf),
source_size);
}
else
{
short_sprintf (srcszbuf, "%s", "source size unknown");
}
nbufs.buf[0] = 0;
if (option_verbose > 1)
{
short_sprintf (nbufs, " #bufs %u", lru_size);
}
XPR(NT "source %s %s blksize %s window %s%s%s\n",
sfile->filename,
srcszbuf.buf,
main_format_bcnt (blksize, &blkszbuf),
main_format_bcnt (option_srcwinsz, &winszbuf),
nbufs.buf,
do_src_fifo ? " (FIFO)" : "");
}
return 0;
}
static int
main_getblk_lru (xd3_source *source, xoff_t blkno,
main_blklru** blrup, int *is_new)
{
main_blklru *blru = NULL;
usize_t i;
(*is_new) = 0;
if (do_src_fifo)
{
/* Direct lookup assumes sequential scan w/o skipping blocks. */
int idx = blkno % lru_size;
blru = & lru[idx];
if (blru->blkno == blkno)
{
(*blrup) = blru;
return 0;
}
/* No going backwards in a sequential scan. */
if (blru->blkno != (xoff_t) -1 && blru->blkno > blkno)
{
return XD3_TOOFARBACK;
}
}
else
{
/* Sequential search through LRU. */
for (i = 0; i < lru_size; i += 1)
{
blru = & lru[i];
if (blru->blkno == blkno)
{
main_blklru_list_remove (blru);
main_blklru_list_push_back (& lru_list, blru);
(*blrup) = blru;
return 0;
}
}
}
if (do_src_fifo)
{
int idx = blkno % lru_size;
blru = & lru[idx];
}
else
{
XD3_ASSERT (! main_blklru_list_empty (& lru_list));
blru = main_blklru_list_pop_front (& lru_list);
main_blklru_list_push_back (& lru_list, blru);
}
lru_filled += 1;
(*is_new) = 1;
(*blrup) = blru;
blru->blkno = -1;
return 0;
}
static int
main_read_seek_source (xd3_stream *stream,
xd3_source *source,
xoff_t blkno) {
xoff_t pos = blkno * source->blksize;
main_file *sfile = (main_file*) source->ioh;
main_blklru *blru;
int is_new;
size_t nread = 0;
int ret = 0;
if (!sfile->seek_failed)
{
ret = main_file_seek (sfile, pos);
if (ret == 0)
{
sfile->source_position = pos;
}
}
if (sfile->seek_failed || ret != 0)
{
/* For an unseekable file (or other seek error, does it
* matter?) */
if (sfile->source_position > pos)
{
/* Could assert !IS_ENCODE(), this shouldn't happen
* because of do_src_fifo during encode. */
if (!option_quiet)
{
XPR(NT "source can't seek backwards; requested block offset "
"%"Q"u source position is %"Q"u\n",
pos, sfile->source_position);
}
sfile->seek_failed = 1;
stream->msg = "non-seekable source: "
"copy is too far back (try raising -B)";
return XD3_TOOFARBACK;
}
/* There's a chance here, that an genuine lseek error will cause
* xdelta3 to shift into non-seekable mode, entering a degraded
* condition. */
if (!sfile->seek_failed && option_verbose)
{
XPR(NT "source can't seek, will use FIFO for %s\n",
sfile->filename);
if (option_verbose > 1)
{
XPR(NT "seek error at offset %"Q"u: %s\n",
pos, xd3_mainerror (ret));
}
}
sfile->seek_failed = 1;
if (option_verbose > 1 && pos != sfile->source_position)
{
XPR(NT "non-seekable source skipping %"Q"u bytes @ %"Q"u\n",
pos - sfile->source_position,
sfile->source_position);
}
while (sfile->source_position < pos)
{
xoff_t skip_blkno;
usize_t skip_offset;
xd3_blksize_div (sfile->source_position, source,
&skip_blkno, &skip_offset);
/* Read past unused data */
XD3_ASSERT (pos - sfile->source_position >= source->blksize);
XD3_ASSERT (skip_offset == 0);
if ((ret = main_getblk_lru (source, skip_blkno,
& blru, & is_new)))
{
return ret;
}
XD3_ASSERT (is_new);
blru->blkno = skip_blkno;
if ((ret = main_read_primary_input (sfile,
(uint8_t*) blru->blk,
source->blksize,
& nread)))
{
return ret;
}
if (nread != source->blksize)
{
IF_DEBUG1 (DP(RINT "[getblk] short skip block nread = %zu\n",
nread));
stream->msg = "non-seekable input is short";
return XD3_INVALID_INPUT;
}
sfile->source_position += nread;
blru->size = nread;
IF_DEBUG1 (DP(RINT "[getblk] skip blkno %"Q"u size %u\n",
skip_blkno, blru->size));
XD3_ASSERT (sfile->source_position <= pos);
}
}
return 0;
}
/* This is the callback for reading a block of source. This function
* is blocking and it implements a small LRU.
*
* Note that it is possible for main_input() to handle getblk requests
* in a non-blocking manner. If the callback is NULL then the caller
* of xd3_*_input() must handle the XD3_GETSRCBLK return value and
* fill the source in the same way. See xd3_getblk for details. To
* see an example of non-blocking getblk, see xdelta-test.h. */
static int
main_getblk_func (xd3_stream *stream,
xd3_source *source,
xoff_t blkno)
{
int ret = 0;
xoff_t pos = blkno * source->blksize;
main_file *sfile = (main_file*) source->ioh;
main_blklru *blru;
int is_new;
int did_seek = 0;
size_t nread = 0;
if (allow_fake_source)
{
source->curblkno = blkno;
source->onblk = 0;
source->curblk = lru[0].blk;
lru[0].size = 0;
return 0;
}
if ((ret = main_getblk_lru (source, blkno, & blru, & is_new)))
{
return ret;
}
if (!is_new)
{
source->curblkno = blkno;
source->onblk = blru->size;
source->curblk = blru->blk;
lru_hits++;
return 0;
}
lru_misses += 1;
if (pos != sfile->source_position)
{
/* Only try to seek when the position is wrong. This means the
* decoder will fail when the source buffer is too small, but
* only when the input is non-seekable. */
if ((ret = main_read_seek_source (stream, source, blkno)))
{
return ret;
}
/* Indicates that another call to main_getblk_lru() may be
* needed */
did_seek = 1;
}
XD3_ASSERT (sfile->source_position == pos);
if (did_seek &&
(ret = main_getblk_lru (source, blkno, & blru, & is_new)))
{
return ret;
}
if ((ret = main_read_primary_input (sfile,
(uint8_t*) blru->blk,
source->blksize,
& nread)))
{
return ret;
}
/* Save the last block read, used to handle non-seekable files. */
sfile->source_position = pos + nread;
if (option_verbose > 3)
{
if (blru->blkno != (xoff_t)-1)
{
if (blru->blkno != blkno)
{
XPR(NT "source block %"Q"u read %zu ejects %"Q"u (lru_hits=%u, "
"lru_misses=%u, lru_filled=%u)\n",
blkno, nread, blru->blkno, lru_hits, lru_misses, lru_filled);
}
else
{
XPR(NT "source block %"Q"u read %zu (lru_hits=%u, "
"lru_misses=%u, lru_filled=%u)\n",
blkno, nread, lru_hits, lru_misses, lru_filled);
}
}
else
{
XPR(NT "source block %"Q"u read %zu (lru_hits=%u, lru_misses=%u, "
"lru_filled=%u)\n", blkno, nread,
lru_hits, lru_misses, lru_filled);
}
}
source->curblk = blru->blk;
source->curblkno = blkno;
source->onblk = nread;
blru->size = nread;
blru->blkno = blkno;
IF_DEBUG1 (DP(RINT "[main_getblk] blkno %"Q"u onblk %zu pos %"Q"u "
"srcpos %"Q"u\n",
blkno, nread, pos, sfile->source_position));
return 0;
}