1 /* xdelta 3 - delta compression tools and library
2 * Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007,
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 /* TODO: This code is heavily revised from 3.0z but still needs major
24 #include "xdelta3-internal.h"
26 typedef struct _main_blklru main_blklru;
27 typedef struct _main_blklru_list main_blklru_list;
29 struct _main_blklru_list
31 main_blklru_list *next;
32 main_blklru_list *prev;
40 main_blklru_list link;
43 #define MAX_LRU_SIZE 32U
44 #define XD3_MINSRCWINSZ (XD3_ALLOCSIZE * MAX_LRU_SIZE)
45 #define XD3_MAXSRCWINSZ (1ULL << 31)
47 XD3_MAKELIST(main_blklru_list,main_blklru,link);
49 static usize_t lru_size = 0;
50 static main_blklru *lru = NULL; /* array of lru_size elts */
51 static main_blklru_list lru_list;
52 static int do_src_fifo = 0; /* set to avoid lru */
54 static int lru_hits = 0;
55 static int lru_misses = 0;
56 static int lru_filled = 0;
58 static void main_lru_reset (void)
68 static void main_lru_cleanup (void)
72 main_buffree (lru[0].blk);
83 /* This is called at different times for encoding and decoding. The
84 * encoder calls it immediately, the decoder delays until the
85 * application header is received. */
87 main_set_source (xd3_stream *stream, xd3_cmd cmd,
88 main_file *sfile, xd3_source *source)
92 xoff_t source_size = 0;
95 XD3_ASSERT (lru == NULL);
96 XD3_ASSERT (stream->src == NULL);
97 XD3_ASSERT (option_srcwinsz >= XD3_MINSRCWINSZ);
99 /* TODO: this code needs refactoring into FIFO, LRU, FAKE. Yuck!
100 * This is simplified from 3.0z which had issues with sizing the
101 * source buffer memory allocation and the source blocksize. */
104 main_blklru_list_init (& lru_list);
106 if (allow_fake_source)
109 * TOOLS/recode-specific: Check "allow_fake_source" mode looks
111 sfile->mode = XO_READ;
112 sfile->realname = sfile->filename;
117 /* Either a regular file (possibly compressed) or a FIFO
118 * (possibly compressed). */
119 if ((ret = main_file_open (sfile, sfile->filename, XO_READ)))
124 /* If the file is regular we know it's size. If the file turns
125 * out to be externally compressed, size_known may change. */
126 sfile->size_known = (main_file_stat (sfile, &source_size) == 0);
129 /* Note: The API requires a power-of-two blocksize and srcwinsz
130 * (-B). The logic here will use a single block if the entire file
131 * is known to fit into srcwinsz. */
132 option_srcwinsz = xd3_pow2_roundup (option_srcwinsz);
134 /* Though called "lru", it is not LRU-specific. We always allocate
135 * a maximum number of source block buffers. If the entire file
136 * fits into srcwinsz, this buffer will stay as the only
137 * (lru_size==1) source block. Otherwise, we know that at least
138 * option_srcwinsz bytes are available. Split the source window
140 if ((lru = (main_blklru*) main_malloc (MAX_LRU_SIZE *
141 sizeof (main_blklru))) == NULL)
147 memset (lru, 0, sizeof(lru[0]) * MAX_LRU_SIZE);
149 /* Allocate the entire buffer. */
150 if ((lru[0].blk = (uint8_t*) main_bufalloc (option_srcwinsz)) == NULL)
156 /* Main calls main_getblk_func() once before xd3_set_source(). This
157 * is the point at which external decompression may begin. Set the
158 * system for a single block. */
160 lru[0].blkno = (xoff_t) -1;
161 blksize = option_srcwinsz;
162 main_blklru_list_push_back (& lru_list, & lru[0]);
163 XD3_ASSERT (blksize != 0);
165 /* Initialize xd3_source. */
166 source->blksize = blksize;
167 source->name = sfile->filename;
169 source->curblkno = (xoff_t) -1;
170 source->curblk = NULL;
171 source->max_winsize = option_srcwinsz;
173 if ((ret = main_getblk_func (stream, source, 0)) != 0)
175 XPR(NT "error reading source: %s: %s\n",
177 xd3_mainerror (ret));
181 source->onblk = lru[0].size; /* xd3 sets onblk */
183 /* If the file is smaller than a block, size is known. */
184 if (!sfile->size_known && source->onblk < blksize)
186 source_size = source->onblk;
187 sfile->size_known = 1;
190 /* If the size is not known or is greater than the buffer size, we
191 * split the buffer across MAX_LRU_SIZE blocks (already allocated in
193 if (!sfile->size_known || source_size > option_srcwinsz)
195 /* Modify block 0, change blocksize. */
196 blksize = option_srcwinsz / MAX_LRU_SIZE;
197 source->blksize = blksize;
198 source->onblk = blksize; /* xd3 sets onblk */
199 /* Note: source->max_winsize is unchanged. */
200 lru[0].size = blksize;
201 lru_size = MAX_LRU_SIZE;
203 /* Setup rest of blocks. */
204 for (i = 1; i < lru_size; i += 1)
206 lru[i].blk = lru[0].blk + (blksize * i);
208 lru[i].size = blksize;
209 main_blklru_list_push_back (& lru_list, & lru[i]);
213 if (! sfile->size_known)
215 /* If the size is not know, we must use FIFO discipline. */
219 /* Call the appropriate set_source method, handle errors, print
220 * verbose message, etc. */
221 if (sfile->size_known)
223 ret = xd3_set_source_and_size (stream, source, source_size);
227 ret = xd3_set_source (stream, source);
232 XPR(NT XD3_LIB_ERRMSG (stream, ret));
236 XD3_ASSERT (stream->src == source);
237 XD3_ASSERT (source->blksize == blksize);
241 static shortbuf srcszbuf;
242 static shortbuf srccntbuf;
243 static shortbuf winszbuf;
244 static shortbuf blkszbuf;
245 static shortbuf nbufs;
247 if (sfile->size_known)
249 short_sprintf (srcszbuf, "source size %s [%"Q"u]",
250 main_format_bcnt (source_size, &srccntbuf),
255 short_sprintf (srcszbuf, "%s", "source size unknown");
260 if (option_verbose > 1)
262 short_sprintf (nbufs, " #bufs %u", lru_size);
265 XPR(NT "source %s %s blksize %s window %s%s%s\n",
268 main_format_bcnt (blksize, &blkszbuf),
269 main_format_bcnt (option_srcwinsz, &winszbuf),
271 do_src_fifo ? " (FIFO)" : "");
278 main_getblk_lru (xd3_source *source, xoff_t blkno,
279 main_blklru** blrup, int *is_new)
281 main_blklru *blru = NULL;
288 /* Direct lookup assumes sequential scan w/o skipping blocks. */
289 int idx = blkno % lru_size;
291 if (blru->blkno == blkno)
296 /* No going backwards in a sequential scan. */
297 if (blru->blkno != (xoff_t) -1 && blru->blkno > blkno)
299 return XD3_TOOFARBACK;
304 /* Sequential search through LRU. */
305 for (i = 0; i < lru_size; i += 1)
308 if (blru->blkno == blkno)
310 main_blklru_list_remove (blru);
311 main_blklru_list_push_back (& lru_list, blru);
320 int idx = blkno % lru_size;
325 XD3_ASSERT (! main_blklru_list_empty (& lru_list));
326 blru = main_blklru_list_pop_front (& lru_list);
327 main_blklru_list_push_back (& lru_list, blru);
338 main_read_seek_source (xd3_stream *stream,
341 xoff_t pos = blkno * source->blksize;
342 main_file *sfile = (main_file*) source->ioh;
348 if (!sfile->seek_failed)
350 ret = main_file_seek (sfile, pos);
354 sfile->source_position = pos;
358 if (sfile->seek_failed || ret != 0)
360 /* For an unseekable file (or other seek error, does it
362 if (sfile->source_position > pos)
364 /* Could assert !IS_ENCODE(), this shouldn't happen
365 * because of do_src_fifo during encode. */
368 XPR(NT "source can't seek backwards; requested block offset "
369 "%"Q"u source position is %"Q"u\n",
370 pos, sfile->source_position);
373 sfile->seek_failed = 1;
374 stream->msg = "non-seekable source: "
375 "copy is too far back (try raising -B)";
376 return XD3_TOOFARBACK;
379 /* There's a chance here, that an genuine lseek error will cause
380 * xdelta3 to shift into non-seekable mode, entering a degraded
382 if (!sfile->seek_failed && option_verbose)
384 XPR(NT "source can't seek, will use FIFO for %s\n",
387 if (option_verbose > 1)
389 XPR(NT "seek error at offset %"Q"u: %s\n",
390 pos, xd3_mainerror (ret));
394 sfile->seek_failed = 1;
396 if (option_verbose > 1 && pos != sfile->source_position)
398 XPR(NT "non-seekable source skipping %"Q"u bytes @ %"Q"u\n",
399 pos - sfile->source_position,
400 sfile->source_position);
403 while (sfile->source_position < pos)
408 xd3_blksize_div (sfile->source_position, source,
409 &skip_blkno, &skip_offset);
411 /* Read past unused data */
412 XD3_ASSERT (pos - sfile->source_position >= source->blksize);
413 XD3_ASSERT (skip_offset == 0);
415 if ((ret = main_getblk_lru (source, skip_blkno,
422 blru->blkno = skip_blkno;
424 if ((ret = main_read_primary_input (sfile,
425 (uint8_t*) blru->blk,
432 if (nread != source->blksize)
434 IF_DEBUG1 (DP(RINT "[getblk] short skip block nread = %zu\n",
436 stream->msg = "non-seekable input is short";
437 return XD3_INVALID_INPUT;
440 sfile->source_position += nread;
443 IF_DEBUG1 (DP(RINT "[getblk] skip blkno %"Q"u size %u\n",
444 skip_blkno, blru->size));
446 XD3_ASSERT (sfile->source_position <= pos);
453 /* This is the callback for reading a block of source. This function
454 * is blocking and it implements a small LRU.
456 * Note that it is possible for main_input() to handle getblk requests
457 * in a non-blocking manner. If the callback is NULL then the caller
458 * of xd3_*_input() must handle the XD3_GETSRCBLK return value and
459 * fill the source in the same way. See xd3_getblk for details. To
460 * see an example of non-blocking getblk, see xdelta-test.h. */
462 main_getblk_func (xd3_stream *stream,
467 xoff_t pos = blkno * source->blksize;
468 main_file *sfile = (main_file*) source->ioh;
474 if (allow_fake_source)
476 source->curblkno = blkno;
478 source->curblk = lru[0].blk;
483 if ((ret = main_getblk_lru (source, blkno, & blru, & is_new)))
490 source->curblkno = blkno;
491 source->onblk = blru->size;
492 source->curblk = blru->blk;
499 if (pos != sfile->source_position)
501 /* Only try to seek when the position is wrong. This means the
502 * decoder will fail when the source buffer is too small, but
503 * only when the input is non-seekable. */
504 if ((ret = main_read_seek_source (stream, source, blkno)))
509 /* Indicates that another call to main_getblk_lru() may be
514 XD3_ASSERT (sfile->source_position == pos);
517 (ret = main_getblk_lru (source, blkno, & blru, & is_new)))
522 if ((ret = main_read_primary_input (sfile,
523 (uint8_t*) blru->blk,
530 /* Save the last block read, used to handle non-seekable files. */
531 sfile->source_position = pos + nread;
533 if (option_verbose > 3)
535 if (blru->blkno != (xoff_t)-1)
537 if (blru->blkno != blkno)
539 XPR(NT "source block %"Q"u read %zu ejects %"Q"u (lru_hits=%u, "
540 "lru_misses=%u, lru_filled=%u)\n",
541 blkno, nread, blru->blkno, lru_hits, lru_misses, lru_filled);
545 XPR(NT "source block %"Q"u read %zu (lru_hits=%u, "
546 "lru_misses=%u, lru_filled=%u)\n",
547 blkno, nread, lru_hits, lru_misses, lru_filled);
552 XPR(NT "source block %"Q"u read %zu (lru_hits=%u, lru_misses=%u, "
553 "lru_filled=%u)\n", blkno, nread,
554 lru_hits, lru_misses, lru_filled);
558 source->curblk = blru->blk;
559 source->curblkno = blkno;
560 source->onblk = nread;
564 IF_DEBUG1 (DP(RINT "[main_getblk] blkno %"Q"u onblk %zu pos %"Q"u "
566 blkno, nread, pos, sfile->source_position));