From b6dc8044807da8b8f993459152379ecf7a5134f3 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Thu, 24 Jul 2014 21:58:02 -0500 Subject: [PATCH] Remove "brute force" match-finding algorithm It's not of much use, and the code ended up being more complicated than I had planned. Just get rid of it. --- Makefile.am | 1 - include/wimlib/lz_mf.h | 8 -- include/wimlib/lz_mf_ops.h | 1 - src/lz_brute_force.c | 168 ------------------------------------- src/lz_mf.c | 1 - 5 files changed, 179 deletions(-) delete mode 100644 src/lz_brute_force.c diff --git a/Makefile.am b/Makefile.am index b5568c17..beaedc4b 100644 --- a/Makefile.am +++ b/Makefile.am @@ -42,7 +42,6 @@ libwim_la_SOURCES = \ src/join.c \ src/lookup_table.c \ src/lz_binary_trees.c \ - src/lz_brute_force.c \ src/lz_hash_chains.c \ src/lz_lcp_interval_tree.c \ src/lz_linked_suffix_array.c \ diff --git a/include/wimlib/lz_mf.h b/include/wimlib/lz_mf.h index 221418d6..9424e19d 100644 --- a/include/wimlib/lz_mf.h +++ b/include/wimlib/lz_mf.h @@ -109,14 +109,6 @@ enum lz_mf_algo { */ LZ_MF_NULL = 1, - /* - * Brute Force match-finding algorithm. - * - * This algorithm exists for comparison, benchmarking, and testing - * purposes only. It is not intended to be used in real compressors. - */ - LZ_MF_BRUTE_FORCE = 2, - /* * Hash Chain match-finding algorithm. * diff --git a/include/wimlib/lz_mf_ops.h b/include/wimlib/lz_mf_ops.h index 0e1cfe9d..d6475710 100644 --- a/include/wimlib/lz_mf_ops.h +++ b/include/wimlib/lz_mf_ops.h @@ -1,7 +1,6 @@ #include "wimlib/lz_mf.h" extern const struct lz_mf_ops lz_null_ops; -extern const struct lz_mf_ops lz_brute_force_ops; extern const struct lz_mf_ops lz_hash_chains_ops; extern const struct lz_mf_ops lz_binary_trees_ops; extern const struct lz_mf_ops lz_lcp_interval_tree_ops; diff --git a/src/lz_brute_force.c b/src/lz_brute_force.c deleted file mode 100644 index 548b7887..00000000 --- a/src/lz_brute_force.c +++ /dev/null @@ -1,168 +0,0 @@ -/* - * lz_brute_force.c - * - * Brute force match-finder for Lempel-Ziv compression. - * - * Copyright (c) 2014 Eric Biggers. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 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. - * - * 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. - */ - -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif - -#include "wimlib/lz_mf.h" -#include "wimlib/util.h" - -static bool -lz_bf_params_valid(const struct lz_mf_params *params) -{ - return true; -} - -static u64 -lz_bf_get_needed_memory(u32 max_window_size) -{ - return 0; -} - -static bool -lz_bf_init(struct lz_mf *mf) -{ - if (mf->params.min_match_len == 0) - mf->params.min_match_len = 2; - - if (mf->params.max_match_len == 0) - mf->params.max_match_len = mf->params.max_window_size; - - if (mf->params.max_search_depth == 0) - mf->params.max_search_depth = 32; - - mf->params.max_search_depth = DIV_ROUND_UP(mf->params.max_search_depth, 8); - - if (mf->params.nice_match_len == 0) - mf->params.nice_match_len = 24; - - if (mf->params.nice_match_len < mf->params.min_match_len) - mf->params.nice_match_len = mf->params.min_match_len; - - if (mf->params.nice_match_len > mf->params.max_match_len) - mf->params.nice_match_len = mf->params.max_match_len; - - return true; -} - -static void -lz_bf_load_window(struct lz_mf *mf, const u8 window[], u32 size) -{ -} - -static u32 -lz_bf_get_matches(struct lz_mf *mf, struct lz_match matches[]) -{ - const u8 * const strptr = lz_mf_get_window_ptr(mf); - const u32 max_len = min(lz_mf_get_bytes_remaining(mf), - mf->params.nice_match_len); - u32 best_len = mf->params.min_match_len - 1; - u32 num_matches = 0; - const u8 *matchptr = strptr; - - if (best_len >= max_len) - goto out; - - while (matchptr-- > mf->cur_window) { - - u32 len; - - if (matchptr[best_len] != strptr[best_len] || - matchptr[best_len - 1] != strptr[best_len - 1] || - matchptr[0] != strptr[0]) - goto next_match; - - for (len = 1; len < best_len - 1; len++) - if (matchptr[len] != strptr[len]) - goto next_match; - - len = best_len; - - while (++len != max_len) - if (matchptr[len] != strptr[len]) - break; - - matches[num_matches++] = (struct lz_match) { - .len = len, - .offset = strptr - matchptr, - }; - best_len = len; - if (best_len == max_len) - break; - if (num_matches == mf->params.max_search_depth) - break; - next_match: - ; - } - - /* If the longest match is @nice_match_len in length, it may have been - * truncated. Try extending it up to the maximum match length. */ - if (num_matches != 0 && - matches[num_matches - 1].len == mf->params.nice_match_len) - { - const u8 * const matchptr = strptr - matches[num_matches - 1].offset; - const u32 len_limit = min(lz_mf_get_bytes_remaining(mf), - mf->params.max_match_len); - u32 len; - - len = matches[num_matches - 1].len; - while (len < len_limit && strptr[len] == matchptr[len]) - len++; - matches[num_matches - 1].len = len; - } - -out: - mf->cur_window_pos++; - return num_matches; -} - -static void -lz_bf_skip_positions(struct lz_mf *mf, u32 n) -{ - mf->cur_window_pos += n; -} - -static void -lz_bf_destroy(struct lz_mf *mf) -{ -} - -const struct lz_mf_ops lz_brute_force_ops = { - .params_valid = lz_bf_params_valid, - .get_needed_memory = lz_bf_get_needed_memory, - .init = lz_bf_init, - .load_window = lz_bf_load_window, - .get_matches = lz_bf_get_matches, - .skip_positions = lz_bf_skip_positions, - .destroy = lz_bf_destroy, - .struct_size = sizeof(struct lz_mf), -}; diff --git a/src/lz_mf.c b/src/lz_mf.c index bb954275..f9061827 100644 --- a/src/lz_mf.c +++ b/src/lz_mf.c @@ -40,7 +40,6 @@ /* Available match-finding algorithms. */ static const struct lz_mf_ops *mf_ops[] = { [LZ_MF_NULL] = &lz_null_ops, - [LZ_MF_BRUTE_FORCE] = &lz_brute_force_ops, [LZ_MF_HASH_CHAINS] = &lz_hash_chains_ops, [LZ_MF_BINARY_TREES] = &lz_binary_trees_ops, [LZ_MF_LCP_INTERVAL_TREE] = &lz_lcp_interval_tree_ops, -- 2.43.0