diff options
author | josh.macdonald <jmacd@users.noreply.github.com> | 2010-02-07 03:00:42 +0000 |
---|---|---|
committer | josh.macdonald <jmacd@users.noreply.github.com> | 2010-02-07 03:00:42 +0000 |
commit | 3dbebbe46096e17c0298f1cbe315d10b35b4f9ee (patch) | |
tree | c2ae665c490d2a4e4cd4365721f4cf807fa1e44b /xdelta3/xdelta3.c | |
parent | e7a0eda2519593950a1a0dff77e42d4da9189c3e (diff) |
Implement srcwin_maxsz in xd3_source_match_setup(), which prevents
the encoder from seeking backwards further than this parameter. This
was supposed to be implemented long ago, but was especially problematic
in the recent release, which implements source-from-FIFO.
Diffstat (limited to 'xdelta3/xdelta3.c')
-rw-r--r-- | xdelta3/xdelta3.c | 164 |
1 files changed, 107 insertions, 57 deletions
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c index 3a053ed..98c0e57 100644 --- a/xdelta3/xdelta3.c +++ b/xdelta3/xdelta3.c | |||
@@ -1,6 +1,6 @@ | |||
1 | /* xdelta 3 - delta compression tools and library | 1 | /* xdelta 3 - delta compression tools and library |
2 | * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, | 2 | * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, |
3 | * 2008, 2009. Joshua P. MacDonald | 3 | * 2008, 2009, 2010. Joshua P. MacDonald |
4 | * | 4 | * |
5 | * This program is free software; you can redistribute it and/or modify | 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 | 6 | * it under the terms of the GNU General Public License as published by |
@@ -540,7 +540,8 @@ static usize_t xd3_smatch (xd3_stream *stream, | |||
540 | usize_t scksum, | 540 | usize_t scksum, |
541 | usize_t *match_offset); | 541 | usize_t *match_offset); |
542 | static int xd3_string_match_init (xd3_stream *stream); | 542 | static int xd3_string_match_init (xd3_stream *stream); |
543 | static uint32_t xd3_scksum (uint32_t *state, const uint8_t *seg, const usize_t ln); | 543 | static uint32_t xd3_scksum (uint32_t *state, const uint8_t *seg, |
544 | const usize_t ln); | ||
544 | static usize_t xd3_comprun (const uint8_t *seg, usize_t slook, uint8_t *run_cp); | 545 | static usize_t xd3_comprun (const uint8_t *seg, usize_t slook, uint8_t *run_cp); |
545 | static int xd3_srcwin_move_point (xd3_stream *stream, | 546 | static int xd3_srcwin_move_point (xd3_stream *stream, |
546 | usize_t *next_move_point); | 547 | usize_t *next_move_point); |
@@ -764,9 +765,9 @@ const xd3_sec_type fgk_sec_type = | |||
764 | (xd3_sec_stream* (*)(xd3_stream*)) fgk_alloc, | 765 | (xd3_sec_stream* (*)(xd3_stream*)) fgk_alloc, |
765 | (void (*)(xd3_stream*, xd3_sec_stream*)) fgk_destroy, | 766 | (void (*)(xd3_stream*, xd3_sec_stream*)) fgk_destroy, |
766 | (void (*)(xd3_sec_stream*)) fgk_init, | 767 | (void (*)(xd3_sec_stream*)) fgk_init, |
767 | (int (*)(xd3_stream*, xd3_sec_stream*, const uint8_t**, const uint8_t*, | 768 | (int (*)(xd3_stream*, xd3_sec_stream*, const uint8_t**, const uint8_t*, |
768 | uint8_t**, const uint8_t*)) xd3_decode_fgk, | 769 | uint8_t**, const uint8_t*)) xd3_decode_fgk, |
769 | IF_ENCODER((int (*)(xd3_stream*, xd3_sec_stream*, xd3_output*, | 770 | IF_ENCODER((int (*)(xd3_stream*, xd3_sec_stream*, xd3_output*, |
770 | xd3_output*, xd3_sec_cfg*)) xd3_encode_fgk) | 771 | xd3_output*, xd3_sec_cfg*)) xd3_encode_fgk) |
771 | }; | 772 | }; |
772 | #endif | 773 | #endif |
@@ -781,9 +782,9 @@ const xd3_sec_type djw_sec_type = | |||
781 | (xd3_sec_stream* (*)(xd3_stream*)) djw_alloc, | 782 | (xd3_sec_stream* (*)(xd3_stream*)) djw_alloc, |
782 | (void (*)(xd3_stream*, xd3_sec_stream*)) djw_destroy, | 783 | (void (*)(xd3_stream*, xd3_sec_stream*)) djw_destroy, |
783 | (void (*)(xd3_sec_stream*)) djw_init, | 784 | (void (*)(xd3_sec_stream*)) djw_init, |
784 | (int (*)(xd3_stream*, xd3_sec_stream*, const uint8_t**, const uint8_t*, | 785 | (int (*)(xd3_stream*, xd3_sec_stream*, const uint8_t**, const uint8_t*, |
785 | uint8_t**, const uint8_t*)) xd3_decode_huff, | 786 | uint8_t**, const uint8_t*)) xd3_decode_huff, |
786 | IF_ENCODER((int (*)(xd3_stream*, xd3_sec_stream*, xd3_output*, | 787 | IF_ENCODER((int (*)(xd3_stream*, xd3_sec_stream*, xd3_output*, |
787 | xd3_output*, xd3_sec_cfg*)) xd3_encode_huff) | 788 | xd3_output*, xd3_sec_cfg*)) xd3_encode_huff) |
788 | }; | 789 | }; |
789 | #endif | 790 | #endif |
@@ -1251,7 +1252,7 @@ static usize_t __alternate_code_table_compressed_size; | |||
1251 | /* This function generates a delta describing the code table for | 1252 | /* This function generates a delta describing the code table for |
1252 | * encoding within a VCDIFF file. This function is NOT thread safe | 1253 | * encoding within a VCDIFF file. This function is NOT thread safe |
1253 | * because it is only intended that this function is used to generate | 1254 | * because it is only intended that this function is used to generate |
1254 | * statically-compiled strings. "comp_string" must be sized | 1255 | * statically-compiled strings. "comp_string" must be sized |
1255 | * CODE_TABLE_VCDIFF_SIZE. */ | 1256 | * CODE_TABLE_VCDIFF_SIZE. */ |
1256 | int xd3_compute_code_table_encoding (xd3_stream *in_stream, | 1257 | int xd3_compute_code_table_encoding (xd3_stream *in_stream, |
1257 | const xd3_dinst *code_table, | 1258 | const xd3_dinst *code_table, |
@@ -1451,7 +1452,7 @@ xd3_apply_table_encoding (xd3_stream *in_stream, const uint8_t *data, usize_t si | |||
1451 | 1452 | ||
1452 | xd3_compute_code_table_string (xd3_rfc3284_code_table (), dflt_string); | 1453 | xd3_compute_code_table_string (xd3_rfc3284_code_table (), dflt_string); |
1453 | 1454 | ||
1454 | if ((ret = xd3_decode_memory (data, size, | 1455 | if ((ret = xd3_decode_memory (data, size, |
1455 | dflt_string, CODE_TABLE_STRING_SIZE, | 1456 | dflt_string, CODE_TABLE_STRING_SIZE, |
1456 | code_string, &code_size, | 1457 | code_string, &code_size, |
1457 | CODE_TABLE_STRING_SIZE, | 1458 | CODE_TABLE_STRING_SIZE, |
@@ -1623,9 +1624,9 @@ xd3_decode_bytes (xd3_stream *stream, uint8_t *buf, usize_t *pos, usize_t size) | |||
1623 | usize_t want; | 1624 | usize_t want; |
1624 | usize_t take; | 1625 | usize_t take; |
1625 | 1626 | ||
1626 | /* Note: The case where (*pos == size) happens when a zero-length appheader or code | 1627 | /* Note: The case where (*pos == size) happens when a zero-length |
1627 | * table is transmitted, but there is nothing in the standard against that. */ | 1628 | * appheader or code table is transmitted, but there is nothing in |
1628 | 1629 | * the standard against that. */ | |
1629 | while (*pos < size) | 1630 | while (*pos < size) |
1630 | { | 1631 | { |
1631 | if (stream->avail_in == 0) | 1632 | if (stream->avail_in == 0) |
@@ -1918,7 +1919,10 @@ xd3_update_cache (xd3_addr_cache* acache, usize_t addr) | |||
1918 | #if XD3_ENCODER | 1919 | #if XD3_ENCODER |
1919 | /* OPT: this gets called a lot, can it be optimized? */ | 1920 | /* OPT: this gets called a lot, can it be optimized? */ |
1920 | static int | 1921 | static int |
1921 | xd3_encode_address (xd3_stream *stream, usize_t addr, usize_t here, uint8_t* mode) | 1922 | xd3_encode_address (xd3_stream *stream, |
1923 | usize_t addr, | ||
1924 | usize_t here, | ||
1925 | uint8_t* mode) | ||
1922 | { | 1926 | { |
1923 | usize_t d, bestd; | 1927 | usize_t d, bestd; |
1924 | usize_t i, bestm, ret; | 1928 | usize_t i, bestm, ret; |
@@ -1948,7 +1952,7 @@ xd3_encode_address (xd3_stream *stream, usize_t addr, usize_t here, uint8_t* mod | |||
1948 | { | 1952 | { |
1949 | /* Note: If we used signed computation here, we'd could compte d | 1953 | /* Note: If we used signed computation here, we'd could compte d |
1950 | * and then check (d >= 0 && d < bestd). */ | 1954 | * and then check (d >= 0 && d < bestd). */ |
1951 | if (addr >= acache->near_array[i]) | 1955 | if (addr >= acache->near_array[i]) |
1952 | { | 1956 | { |
1953 | d = addr - acache->near_array[i]; | 1957 | d = addr - acache->near_array[i]; |
1954 | 1958 | ||
@@ -1962,18 +1966,26 @@ xd3_encode_address (xd3_stream *stream, usize_t addr, usize_t here, uint8_t* mod | |||
1962 | } | 1966 | } |
1963 | } | 1967 | } |
1964 | 1968 | ||
1965 | if (acache->s_same > 0 && acache->same_array[d = addr%(acache->s_same*256)] == addr) | 1969 | if (acache->s_same > 0 && |
1970 | acache->same_array[d = addr%(acache->s_same*256)] == addr) | ||
1966 | { | 1971 | { |
1967 | bestd = d%256; | 1972 | bestd = d%256; |
1968 | bestm = acache->s_near + 2 + d/256; /* 2 + s_near offsets past the VCD_NEAR modes */ | 1973 | /* 2 + s_near offsets past the VCD_NEAR modes */ |
1974 | bestm = acache->s_near + 2 + d/256; | ||
1969 | 1975 | ||
1970 | if ((ret = xd3_emit_byte (stream, & ADDR_TAIL (stream), bestd))) { return ret; } | 1976 | if ((ret = xd3_emit_byte (stream, & ADDR_TAIL (stream), bestd))) |
1977 | { | ||
1978 | return ret; | ||
1979 | } | ||
1971 | } | 1980 | } |
1972 | else | 1981 | else |
1973 | { | 1982 | { |
1974 | good: | 1983 | good: |
1975 | 1984 | ||
1976 | if ((ret = xd3_emit_size (stream, & ADDR_TAIL (stream), bestd))) { return ret; } | 1985 | if ((ret = xd3_emit_size (stream, & ADDR_TAIL (stream), bestd))) |
1986 | { | ||
1987 | return ret; | ||
1988 | } | ||
1977 | } | 1989 | } |
1978 | 1990 | ||
1979 | xd3_update_cache (acache, addr); | 1991 | xd3_update_cache (acache, addr); |
@@ -2054,7 +2066,7 @@ xd3_alloc (xd3_stream *stream, | |||
2054 | if (a != NULL) | 2066 | if (a != NULL) |
2055 | { | 2067 | { |
2056 | IF_DEBUG (stream->alloc_cnt += 1); | 2068 | IF_DEBUG (stream->alloc_cnt += 1); |
2057 | IF_DEBUG2 (DP(RINT "[stream %p malloc] size %u ptr %p\n", | 2069 | IF_DEBUG2 (DP(RINT "[stream %p malloc] size %u ptr %p\n", |
2058 | stream, elts * size, a)); | 2070 | stream, elts * size, a)); |
2059 | } | 2071 | } |
2060 | else | 2072 | else |
@@ -2073,7 +2085,7 @@ xd3_free (xd3_stream *stream, | |||
2073 | { | 2085 | { |
2074 | IF_DEBUG (stream->free_cnt += 1); | 2086 | IF_DEBUG (stream->free_cnt += 1); |
2075 | XD3_ASSERT (stream->free_cnt <= stream->alloc_cnt); | 2087 | XD3_ASSERT (stream->free_cnt <= stream->alloc_cnt); |
2076 | IF_DEBUG2 (DP(RINT "[stream %p free] %p\n", | 2088 | IF_DEBUG2 (DP(RINT "[stream %p free] %p\n", |
2077 | stream, ptr)); | 2089 | stream, ptr)); |
2078 | stream->free (stream->opaque, ptr); | 2090 | stream->free (stream->opaque, ptr); |
2079 | } | 2091 | } |
@@ -2109,12 +2121,14 @@ xd3_alloc_output (xd3_stream *stream, | |||
2109 | } | 2121 | } |
2110 | else | 2122 | else |
2111 | { | 2123 | { |
2112 | if ((output = (xd3_output*) xd3_alloc (stream, 1, sizeof (xd3_output))) == NULL) | 2124 | if ((output = (xd3_output*) xd3_alloc (stream, 1, |
2125 | sizeof (xd3_output))) == NULL) | ||
2113 | { | 2126 | { |
2114 | return NULL; | 2127 | return NULL; |
2115 | } | 2128 | } |
2116 | 2129 | ||
2117 | if ((base = (uint8_t*) xd3_alloc (stream, XD3_ALLOCSIZE, sizeof (uint8_t))) == NULL) | 2130 | if ((base = (uint8_t*) xd3_alloc (stream, XD3_ALLOCSIZE, |
2131 | sizeof (uint8_t))) == NULL) | ||
2118 | { | 2132 | { |
2119 | xd3_free (stream, output); | 2133 | xd3_free (stream, output); |
2120 | return NULL; | 2134 | return NULL; |
@@ -2448,7 +2462,7 @@ xd3_config_stream(xd3_stream *stream, | |||
2448 | 2462 | ||
2449 | switch (level) | 2463 | switch (level) |
2450 | { | 2464 | { |
2451 | case 1: | 2465 | case 1: |
2452 | IF_BUILD_FASTEST(*smatcher = __smatcher_fastest; | 2466 | IF_BUILD_FASTEST(*smatcher = __smatcher_fastest; |
2453 | break;) | 2467 | break;) |
2454 | case 2: | 2468 | case 2: |
@@ -2478,7 +2492,7 @@ xd3_config_stream(xd3_stream *stream, | |||
2478 | return 0; | 2492 | return 0; |
2479 | } | 2493 | } |
2480 | 2494 | ||
2481 | /***************************************************************** | 2495 | /*********************************************************** |
2482 | Getblk interface | 2496 | Getblk interface |
2483 | ***********************************************************/ | 2497 | ***********************************************************/ |
2484 | 2498 | ||
@@ -2492,7 +2506,7 @@ xoff_t xd3_source_eof(const xd3_source *src) | |||
2492 | inline | 2506 | inline |
2493 | usize_t xd3_bytes_on_srcblk (xd3_source *src, xoff_t blkno) | 2507 | usize_t xd3_bytes_on_srcblk (xd3_source *src, xoff_t blkno) |
2494 | { | 2508 | { |
2495 | usize_t r = (blkno == src->max_blkno ? | 2509 | usize_t r = (blkno == src->max_blkno ? |
2496 | src->onlastblk : | 2510 | src->onlastblk : |
2497 | src->blksize); | 2511 | src->blksize); |
2498 | return r; | 2512 | return r; |
@@ -2515,15 +2529,15 @@ xd3_getblk (xd3_stream *stream, xoff_t blkno) | |||
2515 | stream->msg = "getblk source input"; | 2529 | stream->msg = "getblk source input"; |
2516 | return XD3_GETSRCBLK; | 2530 | return XD3_GETSRCBLK; |
2517 | } | 2531 | } |
2518 | 2532 | ||
2519 | ret = stream->getblk (stream, source, blkno); | 2533 | ret = stream->getblk (stream, source, blkno); |
2520 | if (ret != 0) | 2534 | if (ret != 0) |
2521 | { | 2535 | { |
2522 | IF_DEBUG1 (DP(RINT "[getblk] app error: %s\n", xd3_strerror (ret))); | 2536 | IF_DEBUG1 (DP(RINT "[getblk] app error: %s\n", xd3_strerror (ret))); |
2523 | return ret; | 2537 | return ret; |
2524 | } | 2538 | } |
2525 | } | 2539 | } |
2526 | 2540 | ||
2527 | if (blkno >= source->frontier_blkno) | 2541 | if (blkno >= source->frontier_blkno) |
2528 | { | 2542 | { |
2529 | source->max_blkno = blkno; | 2543 | source->max_blkno = blkno; |
@@ -2533,13 +2547,13 @@ xd3_getblk (xd3_stream *stream, xoff_t blkno) | |||
2533 | { | 2547 | { |
2534 | source->frontier_blkno = blkno + 1; | 2548 | source->frontier_blkno = blkno + 1; |
2535 | 2549 | ||
2536 | IF_DEBUG2 (DP(RINT "[getblk] full source blkno %"Q"u: source length unknown %"Q"u\n", | 2550 | IF_DEBUG2 (DP(RINT "[getblk] full source blkno %"Q"u: source length unknown %"Q"u\n", |
2537 | blkno, | 2551 | blkno, |
2538 | xd3_source_eof (source))); | 2552 | xd3_source_eof (source))); |
2539 | } | 2553 | } |
2540 | else | 2554 | else |
2541 | { | 2555 | { |
2542 | if (!source->eof_known) | 2556 | if (!source->eof_known) |
2543 | { | 2557 | { |
2544 | IF_DEBUG2 (DP(RINT "[getblk] eof block has %d bytes; source length known %"Q"u\n", | 2558 | IF_DEBUG2 (DP(RINT "[getblk] eof block has %d bytes; source length known %"Q"u\n", |
2545 | xd3_bytes_on_srcblk (source, blkno), | 2559 | xd3_bytes_on_srcblk (source, blkno), |
@@ -2552,7 +2566,7 @@ xd3_getblk (xd3_stream *stream, xoff_t blkno) | |||
2552 | } | 2566 | } |
2553 | 2567 | ||
2554 | XD3_ASSERT (source->curblk != NULL); | 2568 | XD3_ASSERT (source->curblk != NULL); |
2555 | IF_DEBUG2 (DP(RINT "[getblk] read source block %"Q"u onblk %u blksize %u\n", | 2569 | IF_DEBUG2 (DP(RINT "[getblk] read source block %"Q"u onblk %u blksize %u\n", |
2556 | blkno, source->onblk, source->blksize)); | 2570 | blkno, source->onblk, source->blksize)); |
2557 | 2571 | ||
2558 | if (blkno == source->max_blkno) | 2572 | if (blkno == source->max_blkno) |
@@ -2609,7 +2623,7 @@ xd3_set_source_and_size (xd3_stream *stream, xd3_source *user_source, xoff_t sou | |||
2609 | source_size)); | 2623 | source_size)); |
2610 | 2624 | ||
2611 | xd3_blksize_div(source_size, | 2625 | xd3_blksize_div(source_size, |
2612 | stream->src, | 2626 | stream->src, |
2613 | &stream->src->max_blkno, | 2627 | &stream->src->max_blkno, |
2614 | &stream->src->onlastblk); | 2628 | &stream->src->onlastblk); |
2615 | } | 2629 | } |
@@ -2773,7 +2787,7 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst) | |||
2773 | } | 2787 | } |
2774 | else | 2788 | else |
2775 | { | 2789 | { |
2776 | stream->srcwin_decided_early = (!stream->src->eof_known || | 2790 | stream->srcwin_decided_early = (!stream->src->eof_known || |
2777 | (stream->srcwin_cksum_pos < xd3_source_eof (stream->src))); | 2791 | (stream->srcwin_cksum_pos < xd3_source_eof (stream->src))); |
2778 | } | 2792 | } |
2779 | 2793 | ||
@@ -2804,7 +2818,7 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst) | |||
2804 | /* Note: used to assert inst->size >= MIN_MATCH, but not true | 2818 | /* Note: used to assert inst->size >= MIN_MATCH, but not true |
2805 | * for merge operations & identical match heuristics. */ | 2819 | * for merge operations & identical match heuristics. */ |
2806 | /* the "here" position is always offset by taroff */ | 2820 | /* the "here" position is always offset by taroff */ |
2807 | if ((ret = xd3_encode_address (stream, addr, inst->pos + stream->taroff, | 2821 | if ((ret = xd3_encode_address (stream, addr, inst->pos + stream->taroff, |
2808 | & inst->type))) | 2822 | & inst->type))) |
2809 | { | 2823 | { |
2810 | return ret; | 2824 | return ret; |
@@ -3609,7 +3623,8 @@ xd3_encode_init (xd3_stream *stream, int full_init) | |||
3609 | * identical or short inputs require no table allocation. */ | 3623 | * identical or short inputs require no table allocation. */ |
3610 | if (large_comp) | 3624 | if (large_comp) |
3611 | { | 3625 | { |
3612 | usize_t hash_values = (stream->srcwin_maxsz / stream->smatcher.large_step); | 3626 | usize_t hash_values = (stream->srcwin_maxsz / |
3627 | stream->smatcher.large_step); | ||
3613 | 3628 | ||
3614 | xd3_size_hashtable (stream, | 3629 | xd3_size_hashtable (stream, |
3615 | hash_values, | 3630 | hash_values, |
@@ -3780,7 +3795,7 @@ xd3_encode_input (xd3_stream *stream) | |||
3780 | return XD3_WINSTART; | 3795 | return XD3_WINSTART; |
3781 | 3796 | ||
3782 | case ENC_SEARCH: | 3797 | case ENC_SEARCH: |
3783 | IF_DEBUG2 (DP(RINT "[SEARCH] match_state %d avail_in %u %s\n", | 3798 | IF_DEBUG2 (DP(RINT "[SEARCH] match_state %d avail_in %u %s\n", |
3784 | stream->match_state, stream->avail_in, stream->src ? "source" : "no source")); | 3799 | stream->match_state, stream->avail_in, stream->src ? "source" : "no source")); |
3785 | 3800 | ||
3786 | /* Reentrant matching. */ | 3801 | /* Reentrant matching. */ |
@@ -3795,7 +3810,7 @@ xd3_encode_input (xd3_stream *stream) | |||
3795 | * that extends to the end of the previous window. The | 3810 | * that extends to the end of the previous window. The |
3796 | * match_srcpos field is initially zero and later set | 3811 | * match_srcpos field is initially zero and later set |
3797 | * during xd3_source_extend_match. */ | 3812 | * during xd3_source_extend_match. */ |
3798 | 3813 | ||
3799 | if (stream->avail_in > 0) | 3814 | if (stream->avail_in > 0) |
3800 | { | 3815 | { |
3801 | /* This call can't fail because the source window is | 3816 | /* This call can't fail because the source window is |
@@ -3824,7 +3839,7 @@ xd3_encode_input (xd3_stream *stream) | |||
3824 | * or else it can get stuck in a match-backward | 3839 | * or else it can get stuck in a match-backward |
3825 | * (getsrcblk) then match-forward (getsrcblk), | 3840 | * (getsrcblk) then match-forward (getsrcblk), |
3826 | * find insufficient match length, then repeat | 3841 | * find insufficient match length, then repeat |
3827 | * exactly the same search. | 3842 | * exactly the same search. |
3828 | */ | 3843 | */ |
3829 | stream->input_position += stream->match_fwd; | 3844 | stream->input_position += stream->match_fwd; |
3830 | } | 3845 | } |
@@ -3962,7 +3977,7 @@ xd3_process_stream (int is_encode, | |||
3962 | 3977 | ||
3963 | (*output_size) = 0; | 3978 | (*output_size) = 0; |
3964 | 3979 | ||
3965 | stream->flags |= XD3_FLUSH; | 3980 | stream->flags |= XD3_FLUSH; |
3966 | 3981 | ||
3967 | xd3_avail_input (stream, input + ipos, n); | 3982 | xd3_avail_input (stream, input + ipos, n); |
3968 | ipos += n; | 3983 | ipos += n; |
@@ -4085,7 +4100,7 @@ xd3_process_memory (int is_encode, | |||
4085 | } | 4100 | } |
4086 | 4101 | ||
4087 | exit: | 4102 | exit: |
4088 | if (ret != 0) | 4103 | if (ret != 0) |
4089 | { | 4104 | { |
4090 | IF_DEBUG2 (DP(RINT "process_memory: %d: %s\n", ret, stream.msg)); | 4105 | IF_DEBUG2 (DP(RINT "process_memory: %d: %s\n", ret, stream.msg)); |
4091 | } | 4106 | } |
@@ -4303,7 +4318,8 @@ xd3_srcwin_setup (xd3_stream *stream) | |||
4303 | * issued, but we have to decide the source window base and length | 4318 | * issued, but we have to decide the source window base and length |
4304 | * now. */ | 4319 | * now. */ |
4305 | src->srcbase = stream->match_minaddr; | 4320 | src->srcbase = stream->match_minaddr; |
4306 | src->srclen = max ((usize_t) length, stream->avail_in + (stream->avail_in >> 2)); | 4321 | src->srclen = max ((usize_t) length, |
4322 | stream->avail_in + (stream->avail_in >> 2)); | ||
4307 | 4323 | ||
4308 | /* OPT: If we know the source size, it might be possible to reduce | 4324 | /* OPT: If we know the source size, it might be possible to reduce |
4309 | * srclen. */ | 4325 | * srclen. */ |
@@ -4346,6 +4362,17 @@ xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos) | |||
4346 | goto bad; | 4362 | goto bad; |
4347 | } | 4363 | } |
4348 | 4364 | ||
4365 | /* Implement srcwin_maxsz, which prevents the encoder from seeking | ||
4366 | * back further than the LRU cache maintaining FIFO discipline, | ||
4367 | * which causes terrible performance. */ | ||
4368 | if (xd3_source_eof (stream->src) - srcpos > stream->srcwin_maxsz) { | ||
4369 | IF_DEBUG1(DP(RINT "[match_setup] rejected due to srcwin_maxsz " | ||
4370 | "distance eof=%"Q"u srcpos=%"Q"u maxsz=%u\n", | ||
4371 | xd3_source_eof (stream->src), | ||
4372 | srcpos, stream->srcwin_maxsz)); | ||
4373 | goto bad; | ||
4374 | } | ||
4375 | |||
4349 | /* Going backwards, the 1.5-pass algorithm allows some | 4376 | /* Going backwards, the 1.5-pass algorithm allows some |
4350 | * already-matched input may be covered by a longer source match. | 4377 | * already-matched input may be covered by a longer source match. |
4351 | * The greedy algorithm does not allow this. */ | 4378 | * The greedy algorithm does not allow this. */ |
@@ -4396,8 +4423,11 @@ xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos) | |||
4396 | } | 4423 | } |
4397 | } | 4424 | } |
4398 | 4425 | ||
4399 | IF_DEBUG2(DP(RINT "[match_setup] srcpos %"Q"u unrestricted back %u fwd %u\n", | 4426 | IF_DEBUG1(DP(RINT |
4427 | "[match_setup] srcpos %"Q"u (tgtpos %"Q"u) " | ||
4428 | "unrestricted maxback %u maxfwd %u\n", | ||
4400 | srcpos, | 4429 | srcpos, |
4430 | stream->total_in + stream->input_position, | ||
4401 | stream->match_maxback, | 4431 | stream->match_maxback, |
4402 | stream->match_maxfwd)); | 4432 | stream->match_maxfwd)); |
4403 | goto good; | 4433 | goto good; |
@@ -4407,9 +4437,10 @@ xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos) | |||
4407 | XD3_ASSERT (src->srclen > 0); | 4437 | XD3_ASSERT (src->srclen > 0); |
4408 | 4438 | ||
4409 | /* Restricted case: fail if the srcpos lies outside the source window */ | 4439 | /* Restricted case: fail if the srcpos lies outside the source window */ |
4410 | if ((srcpos < src->srcbase) || (srcpos > (src->srcbase + (xoff_t) src->srclen))) | 4440 | if ((srcpos < src->srcbase) || |
4441 | (srcpos > (src->srcbase + (xoff_t) src->srclen))) | ||
4411 | { | 4442 | { |
4412 | IF_DEBUG2(DP(RINT "[match_setup] restricted source window failure\n")); | 4443 | IF_DEBUG1(DP(RINT "[match_setup] restricted source window failure\n")); |
4413 | goto bad; | 4444 | goto bad; |
4414 | } | 4445 | } |
4415 | else | 4446 | else |
@@ -4428,8 +4459,11 @@ xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos) | |||
4428 | stream->match_maxfwd = srcavail; | 4459 | stream->match_maxfwd = srcavail; |
4429 | } | 4460 | } |
4430 | 4461 | ||
4431 | IF_DEBUG2(DP(RINT "[match_setup] srcpos %"Q"u restricted back %u fwd %u\n", | 4462 | IF_DEBUG1(DP(RINT |
4463 | "[match_setup] srcpos %"Q"u (tgtpos %"Q"u) " | ||
4464 | "restricted maxback %u maxfwd %u\n", | ||
4432 | srcpos, | 4465 | srcpos, |
4466 | stream->total_in + stream->input_position, | ||
4433 | stream->match_maxback, | 4467 | stream->match_maxback, |
4434 | stream->match_maxfwd)); | 4468 | stream->match_maxfwd)); |
4435 | goto good; | 4469 | goto good; |
@@ -4468,7 +4502,7 @@ xd3_forward_match(const uint8_t *s1c, const uint8_t *s2c, size_t n) | |||
4468 | s1[i++] == s2[j++] && | 4502 | s1[i++] == s2[j++] && |
4469 | s1[i++] == s2[j++] && | 4503 | s1[i++] == s2[j++] && |
4470 | s1[i++] == s2[j++] && | 4504 | s1[i++] == s2[j++] && |
4471 | s1[i++] == s2[j++] && | 4505 | s1[i++] == s2[j++] && |
4472 | s1[i++] == s2[j++]) { } | 4506 | s1[i++] == s2[j++]) { } |
4473 | 4507 | ||
4474 | i = (i - 1) * sizeof(int); | 4508 | i = (i - 1) * sizeof(int); |
@@ -4519,7 +4553,7 @@ xd3_source_extend_match (xd3_stream *stream) | |||
4519 | usize_t tryrem; /* tryrem is the number of matchable bytes */ | 4553 | usize_t tryrem; /* tryrem is the number of matchable bytes */ |
4520 | usize_t matched; | 4554 | usize_t matched; |
4521 | 4555 | ||
4522 | IF_DEBUG2(DP(RINT "[extend match] srcpos %"Q"u\n", | 4556 | IF_DEBUG2(DP(RINT "[extend match] srcpos %"Q"u\n", |
4523 | stream->match_srcpos)); | 4557 | stream->match_srcpos)); |
4524 | 4558 | ||
4525 | XD3_ASSERT (src != NULL); | 4559 | XD3_ASSERT (src != NULL); |
@@ -4556,7 +4590,7 @@ xd3_source_extend_match (xd3_stream *stream) | |||
4556 | } | 4590 | } |
4557 | 4591 | ||
4558 | tryrem = min (tryoff, stream->match_maxback - stream->match_back); | 4592 | tryrem = min (tryoff, stream->match_maxback - stream->match_back); |
4559 | 4593 | ||
4560 | IF_DEBUG2(DP(RINT "[maxback] maxback %u trysrc %"Q"u/%u tgt %u tryrem %u\n", | 4594 | IF_DEBUG2(DP(RINT "[maxback] maxback %u trysrc %"Q"u/%u tgt %u tryrem %u\n", |
4561 | stream->match_maxback, tryblk, tryoff, streamoff, tryrem)); | 4595 | stream->match_maxback, tryblk, tryoff, streamoff, tryrem)); |
4562 | 4596 | ||
@@ -4988,12 +5022,6 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | |||
4988 | */ | 5022 | */ |
4989 | logical_input_cksum_pos += stream->src->blksize; | 5023 | logical_input_cksum_pos += stream->src->blksize; |
4990 | 5024 | ||
4991 | IF_DEBUG1 (DP(RINT "[srcwin_move_point] T=%"Q"u{%"Q"u} S=%"Q"u EOF=%"Q"u %s\n", | ||
4992 | stream->total_in + stream->input_position, | ||
4993 | logical_input_cksum_pos, | ||
4994 | stream->srcwin_cksum_pos, | ||
4995 | xd3_source_eof (stream->src), | ||
4996 | stream->src->eof_known ? "known" : "unknown")); | ||
4997 | while (stream->srcwin_cksum_pos < logical_input_cksum_pos && | 5025 | while (stream->srcwin_cksum_pos < logical_input_cksum_pos && |
4998 | (!stream->src->eof_known || | 5026 | (!stream->src->eof_known || |
4999 | stream->srcwin_cksum_pos < xd3_source_eof (stream->src))) | 5027 | stream->srcwin_cksum_pos < xd3_source_eof (stream->src))) |
@@ -5016,14 +5044,26 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | |||
5016 | { | 5044 | { |
5017 | ret = XD3_INTERNAL; | 5045 | ret = XD3_INTERNAL; |
5018 | } | 5046 | } |
5047 | IF_DEBUG1 (DP(RINT | ||
5048 | "[srcwin_move_point] async getblk return for %"Q"u\n", | ||
5049 | blkno)); | ||
5019 | return ret; | 5050 | return ret; |
5020 | } | 5051 | } |
5021 | 5052 | ||
5053 | IF_DEBUG1 (DP(RINT | ||
5054 | "[srcwin_move_point] T=%"Q"u{%"Q"u} S=%"Q"u EOF=%"Q"u %s\n", | ||
5055 | stream->total_in + stream->input_position, | ||
5056 | logical_input_cksum_pos, | ||
5057 | stream->srcwin_cksum_pos, | ||
5058 | xd3_source_eof (stream->src), | ||
5059 | stream->src->eof_known ? "known" : "unknown")); | ||
5060 | |||
5022 | blkpos = xd3_bytes_on_srcblk (stream->src, blkno); | 5061 | blkpos = xd3_bytes_on_srcblk (stream->src, blkno); |
5023 | 5062 | ||
5024 | if (blkpos < (ssize_t) stream->smatcher.large_look) | 5063 | if (blkpos < (ssize_t) stream->smatcher.large_look) |
5025 | { | 5064 | { |
5026 | stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize; | 5065 | stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize; |
5066 | IF_DEBUG1 (DP(RINT "[srcwin_move_point] continue (end-of-block)\n")); | ||
5027 | continue; | 5067 | continue; |
5028 | } | 5068 | } |
5029 | 5069 | ||
@@ -5058,15 +5098,25 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | |||
5058 | stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize; | 5098 | stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize; |
5059 | } | 5099 | } |
5060 | 5100 | ||
5101 | IF_DEBUG1 (DP(RINT | ||
5102 | "[srcwin_move_point] exited loop T=%"Q"u{%"Q"u} S=%"Q"u EOF=%"Q"u %s\n", | ||
5103 | stream->total_in + stream->input_position, | ||
5104 | logical_input_cksum_pos, | ||
5105 | stream->srcwin_cksum_pos, | ||
5106 | xd3_source_eof (stream->src), | ||
5107 | stream->src->eof_known ? "known" : "unknown")); | ||
5108 | |||
5061 | if (stream->src->eof_known) | 5109 | if (stream->src->eof_known) |
5062 | { | 5110 | { |
5063 | source_size = xd3_source_eof (stream->src); | 5111 | source_size = xd3_source_eof (stream->src); |
5064 | 5112 | ||
5065 | if (stream->srcwin_cksum_pos >= source_size) | 5113 | if (stream->srcwin_cksum_pos >= source_size) |
5066 | { | 5114 | { |
5067 | /* This invariant is needed for xd3_source_cksum_offset() */ | 5115 | /* This invariant is needed for xd3_source_cksum_offset() */ |
5068 | stream->srcwin_cksum_pos = source_size; | 5116 | stream->srcwin_cksum_pos = source_size; |
5069 | *next_move_point = USIZE_T_MAX; | 5117 | *next_move_point = USIZE_T_MAX; |
5118 | IF_DEBUG1 (DP(RINT | ||
5119 | "[srcwin_move_point] finished with source input\n")); | ||
5070 | return 0; | 5120 | return 0; |
5071 | } | 5121 | } |
5072 | } | 5122 | } |
@@ -5260,7 +5310,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) | |||
5260 | if (stream->large_table[linx] != 0) | 5310 | if (stream->large_table[linx] != 0) |
5261 | { | 5311 | { |
5262 | /* the match_setup will fail if the source window has | 5312 | /* the match_setup will fail if the source window has |
5263 | * been decided and the match lies outside it. | 5313 | * been decided and the match lies outside it. |
5264 | * OPT: Consider forcing a window at this point to | 5314 | * OPT: Consider forcing a window at this point to |
5265 | * permit a new source window. */ | 5315 | * permit a new source window. */ |
5266 | xoff_t adj_offset = | 5316 | xoff_t adj_offset = |
@@ -5357,7 +5407,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) | |||
5357 | } | 5407 | } |
5358 | 5408 | ||
5359 | /* Compute next RUN, CKSUM */ | 5409 | /* Compute next RUN, CKSUM */ |
5360 | if (DO_RUN) | 5410 | if (DO_RUN) |
5361 | { | 5411 | { |
5362 | NEXTRUN (inp[SLOOK]); | 5412 | NEXTRUN (inp[SLOOK]); |
5363 | } | 5413 | } |