*/
/*
- * Copyright (C) 2013 Eric Biggers
+ * Copyright (c) 2013 Eric Biggers. All rights reserved.
*
- * This file is part of wimlib, a library for working with WIM files.
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
*
- * wimlib 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 3 of the License, or (at your option)
- * any later version.
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
*
- * wimlib 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.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
*
- * You should have received a copy of the GNU General Public License
- * along with wimlib; if not, see http://www.gnu.org/licenses/.
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+ * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
+ * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/* Define the following structures before including this header:
#define LZ_MC_INFINITE_COST (~(lz_mc_cost_t)0)
+struct lz_mc_pos_data;
+
+/* State of the Lempel-Ziv match-chooser.
+ *
+ * This is defined here for benefit of the inlined code. It's not intended for
+ * code outside the match-chooser itself to read or write members from this
+ * structure. */
+struct lz_match_chooser {
+ /* Temporary space used for the match-choosing algorithm. The size of
+ * this array must be at least one more than @nice_len but otherwise is
+ * arbitrary. More space decreases the frequency at which the algorithm
+ * is forced to terminate early. 4096 spaces seems sufficient for most
+ * real data. */
+ struct lz_mc_pos_data *optimum;
+ input_idx_t array_space;
+
+ /* When a match with length greater than or equal to this length is
+ * found, choose it immediately without further consideration. */
+ input_idx_t nice_len;
+
+ /* When matches have been chosen, optimum_cur_idx is set to the position
+ * in the window of the next match/literal to return and optimum_end_idx
+ * is set to the position in the window at the end of the last
+ * match/literal to return. */
+ input_idx_t optimum_cur_idx;
+ input_idx_t optimum_end_idx;
+};
+
/*
* Match chooser position data:
*
LZ_ADAPTIVE_STATE state;
};
-struct lz_match_chooser {
- /* Temporary space used for the match-choosing algorithm. The size of
- * this array must be at least one more than @nice_len but otherwise is
- * arbitrary. More space decreases the frequency at which the algorithm
- * is forced to terminate early. 4096 spaces seems sufficient for most
- * real data. */
- struct lz_mc_pos_data *optimum;
- input_idx_t array_space;
-
- /* When a match with length greater than or equal to this length is
- * found, choose it immediately without further consideration. */
- input_idx_t nice_len;
-
- /* When matches have been chosen, optimum_cur_idx is set to the position
- * in the window of the next match/literal to return and optimum_end_idx
- * is set to the position in the window at the end of the last
- * match/literal to return. */
- input_idx_t optimum_cur_idx;
- input_idx_t optimum_end_idx;
-};
-
/* Initialize the match-chooser.
*
* After calling this, multiple data buffers can be scanned with it if each is
return true;
}
+static inline u64
+lz_match_chooser_get_needed_memory(input_idx_t array_space,
+ input_idx_t nice_len,
+ input_idx_t max_match_len)
+{
+ input_idx_t extra_len = min(nice_len, max_match_len);
+ return ((u64)(array_space + extra_len) *
+ sizeof(((struct lz_match_chooser*)0)->optimum[0]));
+}
+
/* Free memory allocated in lz_match_chooser_init(). */
static void
lz_match_chooser_destroy(struct lz_match_chooser *mc)
* be the number of matches found (which may be 0) and a pointer to the returned
* matches must be written into @matches_ret. Matches must be of distinct
* lengths and sorted in decreasing order by length. Furthermore, match lengths
- * may not exceed the @max_match_len passed to lz_match_chooser_init(). */
+ * may not exceed the @max_match_len passed to lz_match_chooser_init(), and all
+ * match lengths must be at least 2. */
typedef u32 (*lz_get_matches_t)(LZ_COMPRESSOR *ctx,
const LZ_ADAPTIVE_STATE *state,
struct raw_match **matches_ret);
* most recently been searched. This can optionally update the @state to take
* into account format-dependent state that affects match costs, such as repeat
* offsets. */
-typedef lz_mc_cost_t (lz_get_prev_literal_cost_t)(LZ_COMPRESSOR *ctx,
- LZ_ADAPTIVE_STATE *state);
+typedef lz_mc_cost_t (*lz_get_prev_literal_cost_t)(LZ_COMPRESSOR *ctx,
+ LZ_ADAPTIVE_STATE *state);
/* Get the cost of a match. This can optionally update the @state to take into
* account format-dependent state that affects match costs, such as repeat
* offsets. */
-typedef lz_mc_cost_t (lz_get_match_cost_t)(LZ_COMPRESSOR *ctx,
- LZ_ADAPTIVE_STATE *state,
- input_idx_t length,
- input_idx_t offset);
+typedef lz_mc_cost_t (*lz_get_match_cost_t)(LZ_COMPRESSOR *ctx,
+ LZ_ADAPTIVE_STATE *state,
+ input_idx_t length,
+ input_idx_t offset);
/*
* lz_get_near_optimal_match() -
*
* This is based on the algorithm used in 7-Zip's DEFLATE encoder, written by
* Igor Pavlov. However it also attempts to account for adaptive state, such as
- * a LRU queue of recent match offsets.
+ * an LRU queue of recent match offsets.
*
* Unlike a greedy parser that always takes the longest match, or even a "lazy"
* parser with one match/literal look-ahead like zlib, the algorithm used here
* at that position after the minimum-cost path is taken. The @cur_pos
* variable stores the position at which the algorithm is currently
* considering coding choices, and the @len_end variable stores the
- * greatest offset at which the costs of coding choices have been saved.
- * (The algorithm guarantees that all positions before @len_end are
- * reachable by at least one path and therefore have costs computed.)
+ * greatest position at which the costs of coding choices have been
+ * saved. (Actually, the algorithm guarantees that all positions up to
+ * and including @len_end are reachable by at least one path.)
*
* The loop terminates when any one of the following conditions occurs:
*
- * 1. A match greater than @nice_len is found. When this is found, the
- * algorithm chooses this match unconditionally, and consequently the
- * near-optimal match/literal sequence up to and including that match
- * is fully determined.
+ * 1. A match with length greater than or equal to @nice_len is found.
+ * When this occurs, the algorithm chooses this match
+ * unconditionally, and consequently the near-optimal match/literal
+ * sequence up to and including that match is fully determined and it
+ * can begin returning the match/literal list.
*
* 2. @cur_pos reaches a position not overlapped by a preceding match.
* In such cases, the near-optimal match/literal sequence up to
- * @cur_pos is fully determined.
+ * @cur_pos is fully determined and it can begin returning the
+ * match/literal list.
*
* 3. Failing either of the above in a degenerate case, the loop
* terminates when space in the @mc->optimum array is exhausted.
* This terminates the algorithm and forces it to start returning
* matches/literals even though they may not be globally optimal.
*
- * Upon loop termination, a nonempty list of matches/literals has been
- * produced and stored in the @optimum array. They are linked in
- * reverse order, so the last thing this function does is reverse the
- * links and return the first match/literal, leaving the rest to be
- * returned immediately by subsequent calls to this function.
+ * Upon loop termination, a nonempty list of matches/literals will have
+ * been produced and stored in the @optimum array. These
+ * matches/literals are linked in reverse order, so the last thing this
+ * function does is reverse this list and return the first
+ * match/literal, leaving the rest to be returned immediately by
+ * subsequent calls to this function.
*/
input_idx_t cur_pos = 0;
input_idx_t len_end = longest_match_len;
git://wimlib.net / wimlib / blobdiff