From 46bc79f71df9953b6b3c8c079f4621054bec44e8 Mon Sep 17 00:00:00 2001 From: dotdotisdead Date: Sat, 20 Jan 2007 21:31:07 +0000 Subject: Changes to support -I IOPT_SIZE on the commandline. New support for unlimited instruction buffer size set by -I 0. The default remains 4096. --- xdelta3/xdelta3-main.h | 40 ++++++++++---- xdelta3/xdelta3-regtest.py | 12 ++-- xdelta3/xdelta3-test.h | 6 +- xdelta3/xdelta3.c | 134 ++++++++++++++++++++++++++++++--------------- xdelta3/xdelta3.h | 21 ++++--- 5 files changed, 143 insertions(+), 70 deletions(-) diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h index cada82b..44bd6e5 100755 --- a/xdelta3/xdelta3-main.h +++ b/xdelta3/xdelta3-main.h @@ -248,7 +248,7 @@ static int option_quiet = 0; static int option_level = 5; static int option_use_appheader = 1; static uint8_t* option_appheader = NULL; -static int option_use_secondary = /* until-standardized, leave this off */ 0; +static int option_use_secondary = 0; static char* option_secondary = NULL; static int option_use_checksum = 1; static int option_use_altcodetable = 0; @@ -257,6 +257,7 @@ static int option_no_compress = 0; static int option_no_output = 0; /* go through the motions, but do not open or write output */ static const char *option_source_filename = NULL; +static int option_iopt_size = XD3_DEFAULT_IOPT_SIZE; static usize_t option_winsize = XD3_DEFAULT_WINSIZE; static usize_t option_srcwinsz = XD3_DEFAULT_SRCWINSZ; static int option_srcwinsz_set = 0; @@ -2267,6 +2268,7 @@ main_input (xd3_cmd cmd, config.sec_data.ngroups = 1; config.sec_addr.ngroups = 1; config.sec_inst.ngroups = 1; + config.iopt_size = option_iopt_size; /* TODO: eliminate static variables. */ do_not_lru = 0; @@ -2553,12 +2555,22 @@ main_input (xd3_cmd cmd, { if (IS_ENCODE (cmd) || cmd == CMD_DECODE) { - int used_source = xd3_encoder_used_source (& stream); - - if (! option_quiet && IS_ENCODE (cmd) && main_file_isopen (sfile) && ! used_source) + if (! option_quiet && IS_ENCODE (cmd)) { - XPR(NT "warning: input position %"Q"u no source copies\n", - stream.current_window * option_winsize); + /* Warn when no source copies are found */ + if (main_file_isopen (sfile) && ! xd3_encoder_used_source (& stream)) + { + XPR(NT "warning: input position %"Q"u no source copies\n", + stream.current_window * option_winsize); + } + + /* Warn about bad compression due to limited instruction buffer */ + if (stream.i_slots_used > stream.iopt_size) + { + XPR(NT "warning: input position %"Q"u overflowed instruction buffer, " + "needed %u (vs. %u)\n", + stream.current_window * option_winsize, stream.i_slots_used, stream.iopt_size); + } } if (option_verbose) @@ -2723,7 +2735,7 @@ main (int argc, char **argv) main_file ifile; main_file ofile; main_file sfile; - static char *flags = "0123456789cdefhnqvDJNORTVs:B:C:E:F:L:O:P:M:W:A::S::"; + static char *flags = "0123456789cdefhnqvDJNORTVs:B:C:E:F:I:L:O:P:M:W:A::S::"; int my_optind; char *my_optarg; char *my_optstr; @@ -2925,6 +2937,13 @@ main (int argc, char **argv) goto exit; } break; + case 'I': + if ((ret = main_atou (my_optarg, & option_iopt_size, 0, + 0, 'I'))) + { + goto exit; + } + break; case 'W': if ((ret = main_atou (my_optarg, & option_winsize, XD3_ALLOCSIZE, XD3_HARDMAXWINSIZE, 'W'))) @@ -3126,6 +3145,7 @@ main_help (void) P(RINT "memory options:\n"); P(RINT " -B bytes source window size\n"); P(RINT " -W bytes input window size\n"); + P(RINT " -I size instruction buffer size (0 = unlimited)\n"); P(RINT "compression options:\n"); P(RINT " -s source source file to copy from (if any)\n"); @@ -3133,15 +3153,15 @@ main_help (void) P(RINT " -N disable small string-matching compression\n"); P(RINT " -D disable external decompression (encode/decode)\n"); P(RINT " -R disable external recompression (decode)\n"); + P(RINT " -n disable checksum (encode/decode)\n"); + P(RINT " -C soft config (encode, undocumented)\n"); + P(RINT " -A [apphead] disable/provide application header (encode)\n"); #if XD3_DEBUG > 0 P(RINT "developer options:\n"); - P(RINT " -A [apphead] disable/provide application header\n"); - P(RINT " -C soft config (see xdelta3-cfgs.h)\n"); P(RINT " -J disable output (check/compute only)\n"); P(RINT " -P repeat count (for profiling)\n"); P(RINT " -T use alternate code table\n"); - P(RINT " -n disable checksum (encode/decode)\n"); #endif return EXIT_FAILURE; } diff --git a/xdelta3/xdelta3-regtest.py b/xdelta3/xdelta3-regtest.py index 7bb7a1c..bf064bb 100755 --- a/xdelta3/xdelta3-regtest.py +++ b/xdelta3/xdelta3-regtest.py @@ -611,15 +611,15 @@ def BigFileRun(f1, f2): def RandomBigRun(f1, f2): input_ranges = [ - (7, 9, 'large_look'), - (1, 10, 'large_step'), + (7, 20, 'large_look'), + (1, 30, 'large_step'), (4, 5, 'small_look'), - (1, 20, 'small_chain'), - (1, 10, 'small_lchain'), + (1, 32, 'small_chain'), + (1, 16, 'small_lchain'), (0, 1, 'ssmatch'), (0, 1, 'trylazy'), - (1, 32, 'max_lazy'), - (1, 64, 'long_enough'), + (1, 128, 'max_lazy'), + (1, 256, 'long_enough'), (0, 1, 'promote'), ] diff --git a/xdelta3/xdelta3-test.h b/xdelta3/xdelta3-test.h index 2c7af22..36166c6 100755 --- a/xdelta3/xdelta3-test.h +++ b/xdelta3/xdelta3-test.h @@ -2049,9 +2049,9 @@ test_string_matching (xd3_stream *stream, int ignore) if ((ret = stream->smatcher.string_match (stream))) { return ret; } *rptr = 0; - while (! xd3_rlist_empty (& stream->iopt.used)) + while (! xd3_rlist_empty (& stream->iopt_used)) { - xd3_rinst *inst = xd3_rlist_pop_front (& stream->iopt.used); + xd3_rinst *inst = xd3_rlist_pop_front (& stream->iopt_used); switch (inst->type) { @@ -2072,7 +2072,7 @@ test_string_matching (xd3_stream *stream, int ignore) *rptr++ = ' '; - xd3_rlist_push_back (& stream->iopt.free, inst); + xd3_rlist_push_back (& stream->iopt_free, inst); } if (rptr != rbuf) diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c index 14a3c08..97c3390 100755 --- a/xdelta3/xdelta3.c +++ b/xdelta3/xdelta3.c @@ -550,7 +550,7 @@ static void* xd3_alloc0 (xd3_stream *stream, static xd3_output* xd3_alloc_output (xd3_stream *stream, xd3_output *old_output); - +static int xd3_alloc_iopt (xd3_stream *stream, int elts); static void xd3_free_output (xd3_stream *stream, xd3_output *output); @@ -2281,11 +2281,20 @@ xd3_free_output (xd3_stream *stream, void xd3_free_stream (xd3_stream *stream) { + xd3_iopt_buflist *blist = stream->iopt_alloc; + + do + { + xd3_iopt_buflist *tmp = blist; + blist = blist->next; + xd3_free (stream, tmp->buffer); + xd3_free (stream, tmp); + } + while (blist != NULL); xd3_free (stream, stream->large_table); xd3_free (stream, stream->small_table); xd3_free (stream, stream->small_prev); - xd3_free (stream, stream->iopt.buffer); #if XD3_ENCODER { @@ -2393,6 +2402,12 @@ xd3_config_stream(xd3_stream *stream, stream->srcwin_size = config->srcwin_size ? config->srcwin_size : XD3_DEFAULT_CKSUM_ADVANCE; stream->srcwin_maxsz = config->srcwin_maxsz ? config->srcwin_maxsz : XD3_DEFAULT_SRCWINSZ; + if (stream->iopt_size == 0) + { + stream->iopt_size = XD3_ALLOCSIZE / sizeof(xd3_rinst); + stream->iopt_unlimited = 1; + } + stream->getblk = config->getblk; stream->alloc = config->alloc ? config->alloc : __xd3_alloc_func; stream->free = config->freef ? config->freef : __xd3_free_func; @@ -2663,8 +2678,8 @@ xd3_set_appheader (xd3_stream *stream, static int xd3_iopt_check (xd3_stream *stream) { - int ul = xd3_rlist_length (& stream->iopt.used); - int fl = xd3_rlist_length (& stream->iopt.free); + int ul = xd3_rlist_length (& stream->iopt_used); + int fl = xd3_rlist_length (& stream->iopt_free); return (ul + fl + (stream->iout ? 1 : 0)) == stream->iopt_size; } @@ -2674,7 +2689,7 @@ static xd3_rinst* xd3_iopt_free (xd3_stream *stream, xd3_rinst *i) { xd3_rinst *n = xd3_rlist_remove (i); - xd3_rlist_push_back (& stream->iopt.free, i); + xd3_rlist_push_back (& stream->iopt_free, i); return n; } @@ -2683,7 +2698,7 @@ xd3_iopt_free_nonadd (xd3_stream *stream, xd3_rinst *i) { if (i->type != XD3_ADD) { - xd3_rlist_push_back (& stream->iopt.free, i); + xd3_rlist_push_back (& stream->iopt_free, i); } } @@ -2885,7 +2900,7 @@ xd3_iopt_add_finalize (xd3_stream *stream) static int xd3_iopt_flush_instructions (xd3_stream *stream, int force) { - xd3_rinst *r1 = xd3_rlist_front (& stream->iopt.used); + xd3_rinst *r1 = xd3_rlist_front (& stream->iopt_used); xd3_rinst *r2; xd3_rinst *r3; usize_t r1end; @@ -2901,8 +2916,8 @@ xd3_iopt_flush_instructions (xd3_stream *stream, int force) /* Note: once tried to skip this step if it's possible to assert there are no * overlapping instructions. Doesn't work because xd3_opt_erase leaves overlapping * instructions. */ - while (! xd3_rlist_end (& stream->iopt.used, r1) && - ! xd3_rlist_end (& stream->iopt.used, r2 = xd3_rlist_next (r1))) + while (! xd3_rlist_end (& stream->iopt_used, r1) && + ! xd3_rlist_end (& stream->iopt_used, r2 = xd3_rlist_next (r1))) { r1end = r1->pos + r1->size; @@ -2919,7 +2934,7 @@ xd3_iopt_flush_instructions (xd3_stream *stream, int force) XD3_ASSERT (r2end > (r1end + LEAST_MATCH_INCR)); /* If r3 is available... */ - if (! xd3_rlist_end (& stream->iopt.used, r3 = xd3_rlist_next (r2))) + if (! xd3_rlist_end (& stream->iopt_used, r3 = xd3_rlist_next (r2))) { /* If r3 starts before r1 finishes or just about, r2 is irrelevant */ if (r3->pos <= r1end + 1) @@ -3026,9 +3041,9 @@ xd3_iopt_flush_instructions (xd3_stream *stream, int force) /* If forcing, pick instructions until the list is empty, otherwise this empties 50% of * the queue. */ - for (flushed = 0; ! xd3_rlist_empty (& stream->iopt.used); ) + for (flushed = 0; ! xd3_rlist_empty (& stream->iopt_used); ) { - xd3_rinst *renc = xd3_rlist_pop_front (& stream->iopt.used); + xd3_rinst *renc = xd3_rlist_pop_front (& stream->iopt_used); if ((ret = xd3_iopt_add_encoding (stream, renc))) { return ret; @@ -3044,10 +3059,10 @@ xd3_iopt_flush_instructions (xd3_stream *stream, int force) /* If there are only two instructions remaining, break, because they were * not optimized. This means there were more than 50% eliminated by the * loop above. */ - r1 = xd3_rlist_front (& stream->iopt.used); - if (xd3_rlist_end(& stream->iopt.used, r1) || - xd3_rlist_end(& stream->iopt.used, r2 = xd3_rlist_next (r1)) || - xd3_rlist_end(& stream->iopt.used, r3 = xd3_rlist_next (r2))) + r1 = xd3_rlist_front (& stream->iopt_used); + if (xd3_rlist_end(& stream->iopt_used, r1) || + xd3_rlist_end(& stream->iopt_used, r2 = xd3_rlist_next (r1)) || + xd3_rlist_end(& stream->iopt_used, r3 = xd3_rlist_next (r2))) { break; } @@ -3056,7 +3071,7 @@ xd3_iopt_flush_instructions (xd3_stream *stream, int force) XD3_ASSERT (xd3_iopt_check (stream)); - XD3_ASSERT (!force || xd3_rlist_length (& stream->iopt.used) == 0); + XD3_ASSERT (!force || xd3_rlist_length (& stream->iopt_used) == 0); return 0; } @@ -3067,19 +3082,33 @@ xd3_iopt_get_slot (xd3_stream *stream, xd3_rinst** iptr) xd3_rinst *i; int ret; - if (xd3_rlist_empty (& stream->iopt.free)) + if (xd3_rlist_empty (& stream->iopt_free)) { - if ((ret = xd3_iopt_flush_instructions (stream, 0))) { return ret; } + if (stream->iopt_unlimited) + { + int elts = XD3_ALLOCSIZE / sizeof(xd3_rinst); + if ((ret = xd3_alloc_iopt (stream, elts))) + { + return ret; + } + stream->iopt_size += elts; + } + else + { + if ((ret = xd3_iopt_flush_instructions (stream, 0))) { return ret; } - XD3_ASSERT (! xd3_rlist_empty (& stream->iopt.free)); + XD3_ASSERT (! xd3_rlist_empty (& stream->iopt_free)); + } } - i = xd3_rlist_pop_back (& stream->iopt.free); + i = xd3_rlist_pop_back (& stream->iopt_free); - xd3_rlist_push_back (& stream->iopt.used, i); + xd3_rlist_push_back (& stream->iopt_used, i); (*iptr) = i; + ++stream->i_slots_used; + return 0; } @@ -3090,9 +3119,9 @@ xd3_iopt_get_slot (xd3_stream *stream, xd3_rinst** iptr) static void xd3_iopt_erase (xd3_stream *stream, usize_t pos, usize_t size) { - while (! xd3_rlist_empty (& stream->iopt.used)) + while (! xd3_rlist_empty (& stream->iopt_used)) { - xd3_rinst *r = xd3_rlist_back (& stream->iopt.used); + xd3_rinst *r = xd3_rlist_back (& stream->iopt_used); /* Verify that greedy is working. The previous instruction should end before the * new one begins. */ @@ -3110,7 +3139,8 @@ xd3_iopt_erase (xd3_stream *stream, usize_t pos, usize_t size) /* Otherwise, the new instruction covers the old one, delete it and repeat. */ xd3_rlist_remove (r); - xd3_rlist_push_back (& stream->iopt.free, r); + xd3_rlist_push_back (& stream->iopt_free, r); + --stream->i_slots_used; } } @@ -3120,12 +3150,12 @@ xd3_iopt_last_matched (xd3_stream *stream) { xd3_rinst *r; - if (xd3_rlist_empty (& stream->iopt.used)) + if (xd3_rlist_empty (& stream->iopt_used)) { return 0; } - r = xd3_rlist_back (& stream->iopt.used); + r = xd3_rlist_back (& stream->iopt_used); return r->pos + r->size; } @@ -3430,6 +3460,31 @@ xd3_encode_buffer_leftover (xd3_stream *stream) return 0; } +/* Allocates one block of xd3_rlist elements */ +static int +xd3_alloc_iopt (xd3_stream *stream, int elts) +{ + int i; + xd3_iopt_buflist* next = stream->iopt_alloc; + xd3_iopt_buflist* last = xd3_alloc (stream, sizeof (xd3_iopt_buflist), 1); + + if (last == NULL || + (last->buffer = xd3_alloc (stream, sizeof (xd3_rinst), elts)) == NULL) + { + return ENOMEM; + } + + last->next = next; + stream->iopt_alloc = last; + + for (i = 0; i < elts; i += 1) + { + xd3_rlist_push_back (& stream->iopt_free, & last->buffer[i]); + } + + return 0; +} + /* This function allocates all memory initially used by the encoder. */ static int xd3_encode_init (xd3_stream *stream) @@ -3454,9 +3509,9 @@ xd3_encode_init (xd3_stream *stream) if (small_comp) { - /* Hard-coded, keeps table small because small matches become inefficient. */ - // TODO: verify this - usize_t hash_values = min(stream->winsize, 65536U); + /* Hard-coded, keeps table small because small matches become inefficient. + * TODO: verify this stuff. */ + usize_t hash_values = min(stream->winsize, XD3_DEFAULT_SPREVSZ); xd3_size_hashtable (stream, hash_values, @@ -3474,21 +3529,13 @@ xd3_encode_init (xd3_stream *stream) } /* iopt buffer */ - xd3_rlist_init (& stream->iopt.used); - xd3_rlist_init (& stream->iopt.free); + xd3_rlist_init (& stream->iopt_used); + xd3_rlist_init (& stream->iopt_free); - if ((stream->iopt.buffer = xd3_alloc (stream, sizeof (xd3_rinst), stream->iopt_size)) == NULL) - { - goto fail; - } - - for (i = 0; i < stream->iopt_size; i += 1) - { - xd3_rlist_push_back (& stream->iopt.free, & stream->iopt.buffer[i]); - } + if (xd3_alloc_iopt (stream, stream->iopt_size) != 0) { goto fail; } - XD3_ASSERT (xd3_rlist_length (& stream->iopt.free) == stream->iopt_size); - XD3_ASSERT (xd3_rlist_length (& stream->iopt.used) == 0); + XD3_ASSERT (xd3_rlist_length (& stream->iopt_free) == stream->iopt_size); + XD3_ASSERT (xd3_rlist_length (& stream->iopt_used) == 0); /* address cache, code table */ stream->acache.s_near = stream->code_table_desc->near_modes; @@ -3532,6 +3579,7 @@ xd3_encode_reset (xd3_stream *stream) IF_DEBUG (stream->n_emit = 0); stream->avail_in = 0; stream->small_reset = 1; + stream->i_slots_used = 0; if (stream->src != NULL) { diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h index a9ca8f1..c2fe0a6 100755 --- a/xdelta3/xdelta3.h +++ b/xdelta3/xdelta3.h @@ -74,7 +74,8 @@ /* The IOPT_SIZE value sets the size of a buffer used to batch overlapping copy * instructions before they are optimized by picking the best non-overlapping ranges. The - * larger this buffer, the longer a forced xd3_srcwin_setup() decision is held off. */ + * larger this buffer, the longer a forced xd3_srcwin_setup() decision is held off. + * Setting this value to 0 causes an unlimited buffer to be used. */ #ifndef XD3_DEFAULT_IOPT_SIZE #define XD3_DEFAULT_IOPT_SIZE (1U<<12) #endif @@ -192,7 +193,7 @@ typedef struct _xd3_rpage xd3_rpage; typedef struct _xd3_addr_cache xd3_addr_cache; typedef struct _xd3_output xd3_output; typedef struct _xd3_desect xd3_desect; -typedef struct _xd3_iopt_buf xd3_iopt_buf; +typedef struct _xd3_iopt_buflist xd3_iopt_buflist; typedef struct _xd3_rlist xd3_rlist; typedef struct _xd3_sec_type xd3_sec_type; typedef struct _xd3_sec_cfg xd3_sec_cfg; @@ -484,13 +485,12 @@ struct _xd3_addr_cache usize_t *same_array; /* array of size s_same*256 */ }; -/* the IOPT buffer has a used list of (ordered) instructions, possibly overlapping in - * target addresses, awaiting a flush */ -struct _xd3_iopt_buf +/* the IOPT buffer list is just a list of buffers, which may be allocated + * during encode when using an unlimited buffer. */ +struct _xd3_iopt_buflist { - xd3_rlist used; - xd3_rlist free; xd3_rinst *buffer; + xd3_iopt_buflist *next; }; /* This is the record of a pre-compiled configuration, a subset of xd3_config. */ @@ -634,6 +634,7 @@ struct _xd3_stream usize_t sprevsz; /* small string, previous window size (power of 2) */ usize_t sprevmask; /* small string, previous window size mask */ uint iopt_size; + uint iopt_unlimited; uint srcwin_size; uint srcwin_maxsz; @@ -698,8 +699,10 @@ struct _xd3_stream xd3_output *enc_heads[4]; /* array of encoded outputs: head of chain */ xd3_output *enc_tails[4]; /* array of encoded outputs: tail of chain */ - xd3_iopt_buf iopt; /* instruction optimizing buffer */ + xd3_rlist iopt_used; /* instruction optimizing buffer */ + xd3_rlist iopt_free; xd3_rinst *iout; /* next single instruction */ + xd3_iopt_buflist *iopt_alloc; const uint8_t *enc_appheader; /* application header to encode */ usize_t enc_appheadsz; /* application header size */ @@ -785,6 +788,8 @@ struct _xd3_stream xoff_t l_add; xoff_t l_run; + usize_t i_slots_used; + #if XD3_DEBUG usize_t sh_searches; usize_t sh_compares; -- cgit v1.2.3