Remove "brute force" match-finding algorithm
authorEric Biggers <ebiggers3@gmail.com>
Fri, 25 Jul 2014 02:58:02 +0000 (21:58 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Fri, 25 Jul 2014 02:58:45 +0000 (21:58 -0500)
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
include/wimlib/lz_mf.h
include/wimlib/lz_mf_ops.h
src/lz_brute_force.c [deleted file]
src/lz_mf.c

index b5568c177d11bd8539ce97d7e1a234fb5c7d6c3d..beaedc4bc6de29a073c9c839e37e3d3baa90c368 100644 (file)
@@ -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    \
index 221418d6806270ca6c58063ed4238c0bd631ea4b..9424e19d68421bd4131a356d222a15cdecc239ac 100644 (file)
@@ -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.
         *
index 0e1cfe9da4239629d6602f9f1fb78f4cf75ee92d..d6475710ea4d1e573133a06f39e69f5605ea1992 100644 (file)
@@ -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 (file)
index 548b788..0000000
+++ /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),
-};
index bb954275cbf274263a215701ce94f92066dfb8ad..f906182731935e120198623560e0e0ec581df4b4 100644 (file)
@@ -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,